## CAP 是什么 CAP 理論，被戲稱為【帽子理論】。CAP 理論由 Eric Brewer 在 ACM 研討會上提出，而后 CAP 被奉為分布式領域的重要理論 。 分布式系統的 CAP 理論：首先把分布式系統中的三個特性進行了如下歸納： * 一致性（C）：在分布式系統中的所有數據備份，在同一時刻是否同樣的值。（等同于所有節點訪問同一份最新的數據副本） * 可用性（A）：在集群中一部分節點故障后，集群整體是否還能響應客戶端的讀寫請求。（對數據更新具備高可用性） * 分區容忍性（P）：以實際效果而言，分區相當于對通信的時限要求。系統如果不能在時限內達成數據一致性，就意味著發生了分區的情況，必須就當前操作在 C 和 A 之間做出選擇。（分區狀態可以理解為部分機器不連通了，比如機器掛了，繁忙失去響應，單機房故障等） Partition 字面意思是網絡分區，即因網絡因素將系統分隔為多個單獨的部分，有人可能會說，網絡分區的情況發生概率非常小啊，是不是不用考慮 P，保證 CA 就好。要理解 P，我們看回 CAP 證明中 P 的定義: `In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.` 網絡分區的情況符合該定義，網絡丟包的情況也符合以上定義，另外節點宕機，其他節點發往宕機節點的包也將丟失，這種情況同樣符合定義。現實情況下我們面對的是一個不可靠的網絡、有一定概率宕機的設備，這兩個因素都會導致 Partition，因而分布式系統實現中 P 是一個必須項，而不是可選項。 高可用、數據一致性是很多系統設計的目標，但是分區又是不可避免的事情。我們來看一看分別擁有 CA、CP 和 AP 的情況。 ### CA without P CA without P：如果不要求 P（不允許分區），則 C（強一致性）和 A（可用性）是可以保證的。但其實分區不是你想不想的問題，而是始終會存在，CA 系統基本上是單機系統，比如單機數據庫。2PC 是實現強一致性的具體手段。  ### CP without A CP without A：如果不要求 A（可用），相當于每個請求都需要在 Server 之間強一致，而 P（分區）會導致同步時間無限延長，如此 CP 也是可以保證的。很多傳統的數據庫分布式事務都屬于這種模式。  ### AP wihtout C AP wihtout C：要高可用并允許分區，則需放棄一致性。一旦分區發生，節點之間可能會失去聯系，為了高可用，每個節點只能用本地數據提供服務，而這樣會導致全局數據的不一致性。現在眾多的 NoSQL 都屬于此類。  ## CAP 理論的證明 該理論由 Brewer 提出，2 年后就是 2002 年，Lynch 與其他人證明了 Brewer 猜想，從而把 CAP 上升為一個定理。但是，它只是證明了 CAP 三者不可能同時滿足，并沒有證明任意二者都可滿足的問題，所以，該證明被認為是一個收窄的結果。 Lynch 的證明相對比較簡單：采用反證法，如果三者可同時滿足，則因為允許 P 的存在，一定存在 Server 之間的丟包，如此則不能保證 C，證明簡潔而嚴謹。 在該證明中，對 CAP 的定義進行了更明確的聲明： * C：一致性被稱為原子對象，任何的讀寫都應該看起來是“原子“的，或串行的。寫后面的讀一定能讀到前面寫的內容。所有的讀寫請求都好像被全局排序一樣。 * A：對任何非失敗節點都應該在有限時間內給出請求的回應。（請求的可終止性） * P：允許節點之間丟失任意多的消息，當網絡分區發生時，節點之間的消息可能會完全丟失。 ## 對于 CAP 進一步的案例解釋 2010 年的這篇文章《brewers-cap-theorem-on-distributed-systems》，用了三個例子來闡述CAP: example1：單點的mysql； example2：兩個mysql，但不同的mysql存儲不同的數據子集,相當于sharding； example3：兩個mysql，對A的一個insert操作，需要在B上執行成功才認為操作完成（類似復制集）。 作者認為在 example1 和 example2 上都能保證強一致性，但不能保證可用性；在 example3 這個例子，由于分區（partition）的存在，就需要在一致性與可用性之間權衡。對于復制而言，在很多場景下不追求強一致性。比如用戶支付之后，交易記錄落地了；但可能消費記錄的消息同步存在延遲，比如消息阻塞了。在金融業務中，采取類似兩地三中心架構，往往可能采取本地數據和異地機房數據同時寫成功再返回的方式。這樣付出了性能的損耗，響應時間變長。但發生機房故障后，能確保數據是完全可以讀寫的，保障了一致性。 ## CAP 理論澄清 【CAP理論十二年回顧："規則"變了】一文首發于 Computer 雜志，后由InfoQ和IEEE聯合呈現,非常精彩，文章表達了幾個觀點。 ### “三選二”是一個偽命題 不是為了 P （分區容忍性），要在 A 和 C 之間選擇一個。分區很少出現，CAP 在大多數時候允許完美的 C 和 A 。但當分區存在或可感知其影響的情況下，就要預備一種策略去探知分區并顯式處理其影響。這樣的策略應分為三個步驟：探知分區發生，進入顯式的分區模式以限制某些操作，啟動恢復過程以恢復數據一致性并補償分區期間發生的錯誤。 “一致性的作用范圍”其實反映了這樣一種觀念，即在一定的邊界內狀態是一致的，但超出了邊界就無從談起。比如在一個主分區內可以保證完備的一致性和可用性，而在分區外服務是不可用的。Paxos 算法和原子性多播（atomic multicast）系統一般符合這樣的場景。像 Google 的一般做法是將主分區歸屬在單個數據中心里面，然后交給 Paxos 算法去解決跨區域的問題，一方面保證全局協商一致（global consensus）如 Chubby，一方面實現高可用的持久性存儲如 Megastore。 ### ACID、BASE、CAP ACID 和 BASE 這兩個術語都好記有余而精確不足，出現較晚的 BASE 硬湊的感覺更明顯，它是“Basically Available, Soft state, Eventually consistent（基本可用、軟狀態、最終一致性）”的首字母縮寫。其中的軟狀態和最終一致性這兩種技巧擅于對付存在分區的場合，并因此提高了可用性 CAP 與 ACID 的關系更復雜一些，也因此引起更多誤解。其中一個原因是 ACID 的 C 和 A 字母所代表的概念不同于 CAP 的 C 和 A。還有一個原因是選擇可用性只部分地影響 ACID 約束。 進一步看分區之后  用一下這張圖引用，在狀態 S 的時候是非分區狀態，而分區模式則演化出來了 S1，S2，那么問題來了，分區恢復之后，狀態究竟是多少呢？有幾種解決方案。 ### 分區恢復策略：可交換多副本數據類型 注意，能支持此類處理的場景是有限的。 riak_dt 就是這樣一種保障最終一致性實現的數據結構。它分為基于狀態的 CRDTs（State-based CRDTs）和基于操作的 CRDTs（Operation-based CRDTs），基于狀態的 CRDTs 是于傳播狀態的復制，而基于操作的 CRDTs 則是傳播操作。 State-based CRDTs 被稱為復制收斂的數據類型(CvRDTs)，不同于 CmRDTs，CvRDTs 會將其所有本地狀態發送到其他副本。CvRDTs 具有以下本地接口： 查詢-讀取副本的狀態，沒有副作用 更新-根據某些限制向復制狀態寫入 合并-將本地狀態與遠程副本狀態合并 合并函數必須是可交換的、結合的和冪等的。它為任意一對復制狀態提供了一個連接，因此所有狀態集都形成了連接狀態。更新函數必須按照與半格相同的偏序規則單調地增加內部狀態。 Operation-based CRDTs 被稱為可交換多副本數據類型(CmRDTs)，操作分為兩個階段：prepare 和 effect，prepare 在本地節點上執行。它著眼于操作和（可選）當前狀態，并產生一個代表操作的消息，然后分發給所有的其他節點。 ### 分區恢復策略：回放合并 在分區恢復過程中，設計師必須解決兩個問題： 分區兩側的狀態最終必須保持一致， 并且必須補償分區期間產生的錯誤。 如上圖所示，對于分區恢復的狀態 S* 可以通過未分區時的狀態 S 為起點，然后按順序回放相應的變化事件以特定方式推進分區兩側的一系列操作，并在過程中一直保持一致的狀態。Bayou 就是這個實現機制，它會回滾數據庫到正確的時刻并按無歧義的、確定性的順序重新執行所有的操作，最終使所有的節點達到相同的狀態。 對于有沖突的情況，比如版本管理軟件 cvs，存在人工介入、消除沖突的處理策略。 ### 有限制處理 有限制處理提的自動柜員機補償問題，比較形象說明了這個問題。此問題本質上是可用性和一致性的折衷處理。 以自動柜員機（ATM）的設計來說，強一致性看似符合邏輯的選擇，但實際情況也可能有保障部分業務可用的降級處理。因此，討論如何補償分區期間被破壞的不變性約束，ATM 的設計很適合作為例子。 ATM 的基本操作是存款、取款、查看余額。關鍵的不變性約束是余額應大于或等于零。因為只有取款操作會觸犯這項不變性約束，也就只有取款操作將受到特別對待，其他兩種操作隨時都可以執行。 ATM 系統設計師可以選擇在分區期間禁止取款操作，因為在那段時間里沒辦法知道真實的余額，當然這樣會損害可用性。現代 ATM 的做法做了一些折中，在 stand-in 模式下（即分區模式），ATM 限制凈取款額不得高于 k，比如 k 為 $200。低于限額的時候，取款完全正常；當超過限額的時候，系統拒絕取款操作。這樣，ATM 成功將可用性限制在一個合理的水平上，既允許取款操作，又限制了風險。 分區結束的時候，必須有一些措施來恢復一致性和補償分區期間系統所造成的錯誤。狀態的恢復比較簡單，因為操作都是符合交換率的，補償就要分幾種情況去考慮。最后的余額低于零違反了不變性約束。由于 ATM 已經把錢吐出去了，錯誤成了外部事實。銀行的補償辦法是收取透支費并指望顧客償還。因為風險已經受到限制，問題并不嚴重。還有一種情況是分區期間的某一刻余額已經小于零（但 ATM 不知道），此時一筆存款重新將余額變為正的。銀行可以追溯產生透支費，也可以因為顧客已經繳付而忽略該違反情況。 總而言之，因為通信延遲的存在，銀行系統不依靠一致性來保證正確性，而更多地依靠審計和補償。“空頭支票詐騙”也是類似的例子，顧客趕在多家分行對賬之前分別取出錢來然后逃跑。透支的錯誤過后才會被發現，對錯誤的補償也許體現為法律行動的形式。 此前，國內某行 IBM 大型機宕機，系統沒有第一時間切換到熱備或者異地容災上，直接影響國內某行的信用卡支付相關業務，直到 4 小時之后才恢復服務。有對應的的原因包括日常演練等問題，等更重要的是在可用性和一致性之間選擇了一致性，4H 之后提供服務，備庫仍然主要起數據備份的作用。 有限制處理方案是需要冒險滴，為了保障可用性，無法保障數據 100% 精確，可以折衷提供部分有損服務。比如取款根據信用是不是能限制一定金額，而存款是 OK 的等等。大額對公業務也可以采取具體辦法，當然這將在精細化管理服務能力及配套能力上付出更多的IT成本。 ## 超越 CAP？ 2011 年 11 月 Twitter 的首席工程師 Nathan Marz 寫了一篇文章，描述了他是如何試圖打敗 CAP 定理的： How to beat the CAP theorem。 作者表示不是要“擊敗”CAP，而是嘗試對數據存儲系統進行重新設計，以可控的復雜度來實現 CAP。Marz 認為一個分布式系統面臨 CAP 難題的兩大問題就是：在數據庫中如何使用不斷變化的數據，如何使用算法來更新數據庫中的數據。 Marz 提出了 2 個基本思路： 數據不存在 update，只存在 append 操作。這樣就把對數據的處理由 CRUD 變為 CR；同樣的，delete 操作也可以處理為 add 一條新記錄：比如友強取消了對山丘的關注，傳統關系型數據庫是在關系表刪除一條記錄，而 Marz 也可以新增一條關系為取消的記錄。 所有的數據的操作就只剩下 Create和Read。把 Read 作為一個 Query 來處理，而一個 Query 就是一個對整個數據集執行一個函數操作。 總結，在有一定時序性，且對實時一致性要求不高的場景下可以選擇使用，畢竟在問題解決域多了一把錘子。Query 過程中的跨分區函數仍然是一種合并的變種（Merge） ## OceanBase 的另類之路 既然更新數據涉及到分區問題，那么能不能把更新放到一個服務器呢腦洞大開？然后通過強大的軟件+硬件能力一起去保障它！同時已經不修改的數據天然具備可擴展性！這是我粗暴理解 OceanBase 的基本設計思想。  ### 關于 UpdateServer 的性能問題 其實大部分數據庫每天的修改次數相當有限，只有少數修改比較頻繁的數據庫才有每天幾億次的修改次數。另外，數據庫平均每次修改涉及的數據量很少，很多時候只有幾十個字節到幾百個字節。假設數據庫每天更新 1 億次，平均每次需要消耗 100 字節，每天插入 1000 萬次，平均每次需要消耗 1000 字節，那么，一天的修改量為：1億 * 100 + 1000萬 * 1000 = 20GB，如果內存數據結構膨脹 2 倍，占用內存只有 40GB。而當前主流的服務器都可以配置 96GB 內存，一些高檔的服務器甚至可以配置 192GB、384GB 乃至更多內存。 ## 總 結 CAP 是分布式領域的重要理論，但不代表完全不能有延展的解讀和思考。另外三選二本身也是有條件成立的，不能簡單誤讀，一切取決于應用場景。如果不加選擇按照理論形式無異于刻舟求劍。