在理論計算機科學中，CAP定理（CAP theorem），又被稱作佈魯爾定理（Brewer’s theorem），它指出對於一個分佈式計算系統來說，不可能同時滿足以下三點：
- 一致性 (Consistency)（等同於所有節點訪問同一份最新的數據副本）
- 可用性（Availability）（對數據更新具備高可用性）
- 網絡分區容忍性（Partition tolerance）（以實際效果而言，分區相當於對通信的時限要求。系統如果不能在時限內達成數據一致性，就意味著發生瞭分區的情況，必須就當前操作在C和A之間做出選擇。）
根據定理，分佈式系統隻能滿足三項中的兩項而不可能滿足全部三項。
理解CAP理論的最簡單方式是想象兩個節點分處分區兩側。 允許至少一個節點更新狀態會導致數據不一致，即喪失瞭C性質。 如果為瞭保證數據一致性，將分區一側的節點設置為不可用，那麼又喪失瞭A性質。 除非兩個節點可以互相通信，才能既保證C又保證A，這又會導致喪失P性質。
這個定理起源於加州大學伯克利分校（University of California, Berkeley）的計算機科學傢埃裡克·佈魯爾在2000年的分佈式計算原則研討會 （Symposium on Principles of Distributed Computing（PODC））上提出的一個猜想。 在2002年，麻省理工學院（MIT）的賽斯·吉爾伯特和南希·林奇發表瞭佈魯爾猜想的證明， 使之成為一個定理。 吉爾伯特和林奇證明的CAP定理比佈魯爾設想的某種程度上更加狹義。 定理討論瞭在兩個互相矛盾的請求到達彼此連接不通的兩個不同的分佈式節點的時候的處理方案。
From：WikiPedia.org
當我第一次讀完WikiPedia的解釋是似懂非懂的，現在懂瞭覺得WikiPedia這個條目的撰寫者真是字字珠璣。
CAP原理實例推導
我們以數據庫為例，討論一下CAP原理。
單實例
首先，我們討論一種最簡單的情況："單數據庫實例"。 這也是最常見的小站點、個人博客、小論壇的架構。
我們可以很容易分析出來，由於單實例，所以不存在“網絡分區”、“不一致”， 但單點故障後會導致整個數據庫癱瘓，所以可用性不能保證。
這就是CAP定理中的，保證"C"和"P"，舍棄"A"。
所有單機版的系統都屬於這個范疇，例如MySQL、memcached、redis。
Sharding
Sharding可以翻譯為分片。
為瞭提升可用性，我們在實際生產環境下經常會在客戶端應用一些哈希算法，進行數據分片存放，如下圖所示：
由於數據是分片存儲在每個數據庫中，所以依舊能保證數據一致性。
由於數據庫之間沒有互相通信，並不依賴彼此的存在，所以分區可容忍性依舊沒有破壞。
那麼可用性呢？很多時候會有人直接拍腦袋，這裡我們用數學的方式來解答這個問題。
假設，集群有兩臺服務器，數據分佈均勻，我們數據庫實例宕機的概率是p。 那麼這種利用哈希進行數據分片的集群的可用性為：
即使，數據分佈均勻或者集群數量增大，結果也是一樣的：“集群可用性依舊為p”。
那我們折騰瞭半天，CAP和單機竟然是一樣的，為瞭個球啊？ 這種情況下CAP各項指標雖然沒有提升，但好處是：
- 單個服務器宕機隻會導致服務降級；
- 集群有瞭擴容縮容的可能性，這就叫做scalability。
這種分佈式的方式常用於：
- 分佈式memcached、redis
- 傳統的數據庫Sharding
- BigTable (列存儲式數據庫)
- Hypertable (列存儲式數據庫)
- HBase (列存儲式數據庫)
- MongoDB (文檔式數據庫)
- Terrastore (文檔式數據庫)
- Redis (KV數據庫)
- Scalaris (KV數據庫)
- MemcacheDB (KV數據庫)
- Berkeley DB (KV數據庫)
多副本寫入
如果我們想要保證更高的可用性，那應該怎麼辦呢？我們就有瞭下面的做法：
Client多副本寫入，就是Client在寫數據庫的時候對多個數據庫進行寫入，並且在兩個都寫入成功後才認為成功。 由於數據存在多個副本，這種方式會大大的提高讀取的可用性。但由於寫入的時候要多寫， 副本所在的所有實例都必須可用才能成功。所以寫入的可用性反而下降瞭。
假設單機數據庫的故障率為p（p<1.0），那麼單機數據庫的可用性為1-p。 總結就是：
- 在寫入的場景下，一致性( C )和分區可容忍性( P )沒有變化，可用性( A )反而有所下降， 從1-p降低到1-2p+p²
- 在讀取的場景下，一致性( C )和分區可容忍性( P )依舊沒有變化，可用性( A )有所上升， 從1-p上升到1-p²
我們可以進一步得到結論：
"Client多副本寫入"這種寫入方式非常適合於在"讀多寫少"的場景下提高可用性。
