《深入分布式緩存》之“分布式理論：CAP是三選二嗎？”

版權聲明：本文為半吊子子全棧工匠（wireless_com，同公衆号)原創文章，未經允許不得轉載。 https://blog.csdn.net/wireless_com/article/details/79153643

CAP是什麼？

CAP理論，被戲稱為[帽子理論]。CAP理論由Eric Brewer在ACM研讨會上提出，而後CAP被奉為分布式領域的重要理論[1] 。

分布式系統的CAP理論：首先把分布式系統中的三個特性進行了如下歸納：

● 一緻性（C）：在分布式系統中的所有資料備份，在同一時刻是否同樣的值。（等同于所有節點通路同一份最新的資料副本）

● 可用性（A）：在叢集中一部分節點故障後，叢集整體是否還能響應用戶端的讀寫請求。（對資料更新具備高可用性）

● 分區容忍性（P）：以實際效果而言，分區相當于對通信的時限要求。系統如果不能在時限内達成資料一緻性，就意味着發生了分區的情況，必須就目前操作在C和A之間做出選擇。（分區狀态可以了解為部分機器不連通了，比如機器挂了，繁忙失去響應，單機房故障等）

Partition字面意思是網絡分區，即因網絡因素将系統分隔為多個單獨的部分，有人可能會說，網絡分區的情況發生機率非常小啊，是不是不用考慮P，保證CA就好。要了解P，我們看回CAP證明中P的定義：

In order to model partition tolerance, the network will be allowed to losearbitrarily many messages sent from one node to another.

網絡分區的情況符合該定義，網絡丢包的情況也符合以上定義，另外節點當機，其他節點發往當機節點的包也将丢失，這種情況同樣符合定義。現實情況下我們面對的是一個不可靠的網絡、有一定機率當機的裝置，這兩個因素都會導緻Partition，因而分布式系統實作中 P 是一個必須項，而不是可選項。

高可用、資料一緻性是很多系統設計的目标，但是分區又是不可避免的事情。我們來看一看分别擁有CA、CP和AP的情況。

CA without P：如果不要求P（不允許分區），則C（強一緻性）和A（可用性）是可以保證的。但其實分區不是你想不想的問題，而是始終會存在，CA系統基本上是單機系統，比如單機資料庫。2PC是實作強一緻性的具體手段。

from http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

CP without A：如果不要求A（可用），相當于每個請求都需要在Server之間強一緻，而P（分區）會導緻同步時間無限延長，如此CP也是可以保證的。很多傳統的資料庫分布式事務都屬于這種模式。

from 同上

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聯合呈現,非常精彩[2]，文章表達了幾個觀點。

“三選二”是一個僞命題

不是為了P（分區容忍性），要在A和C之間選擇一個。分區很少出現，CAP在大多數時候允許完美的C和A。但當分區存在或可感覺其影響的情況下，就要預備一種政策去探知分區并顯式處理其影響。這樣的政策應分為三個步驟：探知分區發生，進入顯式的分區模式以限制某些操作，啟動恢複過程以恢複資料一緻性并補償分區期間發生的錯誤。

“一緻性的作用範圍”其實反映了這樣一種觀念，即在一定的邊界内狀态是一緻的，但超出了邊界就無從談起。比如在一個主分區内可以保證完備的一緻性和可用性，而在分區外服務是不可用的。Paxos算法和原子性多點傳播（atomic multicast）系統一般符合這樣的場景。像Google的一般做法是将主分區歸屬在單個資料中心裡面，然後交給Paxos算法去解決跨區域的問題，一方面保證全局協商一緻（global consensus）如Chubby，一方面實作高可用的持久性存儲如Megastore。

ACID、BASE、CAP

ACID和BASE 這兩個術語都好記有餘而精确不足，出現較晚的BASE硬湊的感覺更明顯，它是“Basically Available, Softstate, Eventually consistent（基本可用、軟狀态、最終一緻性）”的首字母縮寫。其中的軟狀态和最終一緻性這兩種技巧擅于對付存在分區的場合，并是以提高了可用性。

CAP與ACID的關系更複雜一些，也是以引起更多誤解。其中一個原因是ACID的C和A字母所代表的概念不同于CAP的C和A。還有一個原因是選擇可用性隻部分地影響ACID限制。

進一步看[分區]之後

用一下這張圖[引用自 link 2]，在狀态S的時候是非分區狀态，而分區模式則演化出來了S1，S2，那麼問題來了，分區恢複之後，狀态究竟是多少呢？有幾種解決方案。

分區恢複政策：可交換多副本資料類型 

注意，能支援此類處理的場景是有限的。

riak_dt 就是這樣一種保障最終一緻性實作的資料結構，它分為Operation-based CRDTs、State-based CRDTs 2種形态。

riak_dt   link參見 link [3]。

State-based CRDTs

State-based CRDTs are called convergent replicated data types,or CvRDTs. In contrast to CmRDTs, CvRDTs send their full localstate to other replicas. CvRDTs have the following local interface:

·      query - reads the state of the replica, with no sideeffects

·      update - writes to the replica state in accordance withcertain restrictions

·      merge - merges local state with the state of some remotereplica

The merge function must be commutative, associative, andidempotent. It provides a join for any pair of replica states, so theset of all states forms asemilattice. The update functionmust monotonically increase the internal state, according to thesame partial order rules as the semilattice.

from：https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

 分區恢複政策：回放合并

在分區恢複過程中，設計師必須解決兩個問題：

• 分區兩側的狀态最終必須保持一緻，
• 并且必須補償分區期間産生的錯誤。

如上圖所示，對于分區恢複的狀态S*可以通過未分區時的狀态S為起點，然後按順序[回放]相應的變化事件[以特定方式推進分區兩側的一系列操作，并在過程中一直保持一緻的狀态。]。Bayou[link 4]就是這個實作機制，它會復原資料庫到正确的時刻并按無歧義的、确定性的順序重新執行所有的操作，最終使所有的節點達到相同的狀态。

對于有沖突的情況，比如版本管理軟體cvs，存在人工介入、消除沖突的處理政策。

 有限制處理

有限制處理：[link 2]提的自動櫃員機補償問題，比較形象說明了這個問題。此問題本質上是可用性和一緻性的折衷處理。

以自動櫃員機（ATM）的設計來說，強一緻性看似符合邏輯的選擇，但現實情況是可用性遠比一緻性重要。理由很簡單：高可用性意味着高收入。不管怎麼樣，讨論如何補償分區期間被破壞的不變性限制，ATM的設計很适合作為例子。

ATM的基本操作是存款、取款、檢視餘額。關鍵的不變性限制是餘額應大于或等于零。因為隻有取款操作會觸犯這項不變性限制，也就隻有取款操作将受到特别對待，其他兩種操作随時都可以執行。

ATM系統設計師可以選擇在分區期間禁止取款操作，因為在那段時間裡沒辦法知道真實的餘額，當然這樣會損害可用性。現代ATM的做法正相反，在stand-in模式下（即分區模式），ATM限制淨取款額不得高于k，比如k為$200。低于限額的時候，取款完全正常；當超過限額的時候，系統拒絕取款操作。這樣，ATM成功将可用性限制在一個合理的水準上，既允許取款操作，又限制了風險。

分區結束的時候，必須有一些措施來恢複一緻性和補償分區期間系統所造成的錯誤。狀态的恢複比較簡單，因為操作都是符合交換率的，補償就要分幾種情況去考慮。最後的餘額低于零違反了不變性限制。由于ATM已經把錢吐出去了，錯誤成了外部實在。銀行的補償辦法是收取透支費并指望顧客償還。因為風險已經受到限制，問題并不嚴重。還有一種情況是分區期間的某一刻餘額已經小于零（但ATM不知道），此時一筆存款重新将餘額變為正的。銀行可以追溯産生透支費，也可以因為顧客已經繳付而忽略該違反情況。

總而言之，因為通信延遲的存在，銀行系統不依靠一緻性來保證正确性，而更多地依靠審計和補償。“空頭支票詐騙”也是類似的例子，顧客趕在多家分行對賬之前分别取出錢來然後逃跑。透支的錯誤過後才會被發現，對錯誤的補償也許展現為法律行動的形式。

此前，中行IBM大型機當機，系統沒有第一時間切換到熱備或者異地容災上，直接影響中行的信用卡支付相關業務，直到4小時之後才恢複服務。有對應的的原因包括日常演練等問題，等更重要的是在[可用性和一緻性]之間選擇了一緻性，4H之後提供服務，備庫仍然主要起資料備份的作用。

有限制處理方案是需要冒險滴，為了保障可用性，無法保障資料100%精确，可以折衷提供部分有損服務。比如取款根據信用是不是能限制一定金額，而存款是Ok的等等。大額對公業務也可以采取具體辦法，當然這将在精細化管理服務能力及配套能力上付出更多的IT成本。

有關中行IBM大型機當機的報道link：

http://digi.tech.qq.com/zt2013/syibm/

http://www.infoq.com/cn/news/2013/04/BOC-Downtime/

超越CAP？

Nathan Marz：How to beat theCAP theorem

2011年11月Twitter的首席工程師Nathan Marz寫了一篇文章，描述了他是如何試圖打敗CAP定理的： How to beat the CAP theorem

作者表示不是要“擊敗”CAP，而是嘗試對資料存儲系統進行重新設計，以可控的複雜度來實作CAP。Marz認為一個分布式系統面臨CAP難題的兩大問題就是：在資料庫中如何使用不斷變化的資料，如何使用算法來更新資料庫中的資料。

Marz提出了2個基本思路：

1) 資料不存在update，隻存在append操作。這樣就把對資料的處理由CRUD變為CR；同樣的，delete操作也可以處理為add一條新記錄：比如 友強取消了對山丘的關注，傳統關系型資料庫是在關系表删除一條記錄，而Marz也可以新增一條關系為[取消]的記錄。

2) 所有的資料的操作就隻剩下Create和Read。把Read作為一個Query來處理，而一個Query就是一個對整個資料集執行一個函數操作。

總結，在有一定時序性，且對實時一緻性要求不高的場景下可以選擇使用，畢竟在問題解決域多了一把錘子。Query過程中的跨分區函數仍然是一種合并的變種（Merge）！

OceanBase的另類之路

既然更新資料涉及到分區問題，那麼能不能把更新放到一個伺服器呢[腦洞大開]？然後通過強大的軟體+硬體能力一起去保障它！同時已經不修改的資料天然具備可擴充性！這是我粗暴了解OceanBase的基本設計思想。

link[5] 寫道：作為電子商務企業，淘寶和其他公司的業務對一緻性和可用性的要求高于分區容錯性，資料特征是資料總量龐大且逐漸增加，機關時間内的資料更新量并不大，但實時性要求很高。這就要求我們提供一套更加偏重于支援CA特性的系統，同時兼顧可分區性，并且在實時性、成本、性能等方面表現良好。

OceanBase的邏輯架構簡圖

關于UpdateServer的性能問題

其實大部分資料庫每天的修改次數相當有限，隻有少數修改比較頻繁的資料庫才有每天幾億次的修改次數。另外，資料庫平均每次修改涉及的資料量很少，很多時候隻有幾十個位元組到幾百個位元組。假設資料庫每天更新1億次，平均每次需要消耗100位元組，每天插入1000萬次，平均每次需要消耗1000位元組，那麼，一天的修改量為：1億 * 100 + 1000萬 *1000 = 20GB，如果記憶體資料結構膨脹2倍，占用記憶體隻有40GB。而目前主流的伺服器都可以配置96GB記憶體，一些高檔的伺服器甚至可以配置192GB、384GB乃至更多記憶體。

TiDB 

TiDB 是國内 PingCAP 團隊開發的一個分布式 SQL 資料庫。其靈感來自于 Google 的 F1, TiDB 支援包括傳統 RDBMS 和 NoSQL 的特性。從下面這篇訪談來看，分布式事務早期版本中，他們參考的是Google 的 Percolator 的模型。目前該項目逐漸納入商用，有興趣的朋友參考下面的link[6]。

[1] link：http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

[2] link：http://www.infoq.com/cn/articles/cap-twelve-years-later-how-the-rules-have-changed/

[3] link：https://github.com/basho/riak_dt 

[4] link：http://www.cs.berkeley.edu/~brewer/cs262b/update-conflicts.pdf

[5] link：http://code.taobao.org/p/OceanBase/wiki/intro/

[6] link：http://mt.sohu.com/20160122/n435472384.shtml

總結：CAP是分布式領域的重要理論，但不代表完全不能有延展的解讀和思考。另外[三選二]本身也是有條件成立的，不能簡單誤讀，一切取決于應用場景。如果不加選擇按照理論形式無異于刻舟求劍。

欲了解更多有關分布式緩存方面的内容，請閱讀《深入分布式緩存:從原理到實踐》一書。

京東購書，掃描二維碼：