CAP 理論與分布式系統設計
CAP 和 分布式系統的討論和研究很多，但我認為這一篇肯定給大家帶來不一樣的收獲，歡迎留言討論。
| Author |
Taosheng Shi |
||||||||||
| WeChat Contact |
data-lake |
||||||||||
| Mail Contact |
tshshi@126.com |
||||||||||
| Organization |
NOKIA |
||||||||||
| Document category |
Distributed System |
||||||||||
| Document location |
https://github.com/stone-note/articles |
||||||||||
|
|||||||||||
Contents
1 .................... 引言
2 .................. 全球規模分布式系統
3 .................. 分布式系統設計的兩大原則
3.1 ................ 通過復制來提高可用性
3.2 ............... 使用 CAP 理論指導分布式系統設計
4 .................. 重新理解 CAP
4.1 ................ CAP 三者并不對等，三選二是誤導
4.2 ............... 保證不發生分區， CA 也不容易兼得
4.3 ............... 發生分區時，也不要隨意犧牲 CA
5 .................. 分解，分解，分解
5.1 ................ P 分解：延遲？故障？分區？
5.2 ............... C 分解：服務器端與客戶端
5.3 ............... A 分解：出來混，遲早要還的
6 ................... 真正的難題
7 ................... 總結
8 ................... 附錄
8.1 ................ 附錄 1 ：不變性如何打敗 CAP 定理？
8.2 ............... 附錄 2 ：放棄 P, 選擇 C
8.3 ............... 附錄 3 ：用 PACELC 替換 CAP
9 .................. 參考文獻
1 引言
在現代分布式系統中，節點數目是巨大的。在 CAP 理論的范圍內， MichaelStonebraker 斷言分區必然會發生，并且系統內發生節點失敗的機會隨著節點數的增加而呈指數級增加：
基于這樣的事實，很多人會問：
如果發生分區（故障），系統會犧牲什么？一致性還是可用性？
對于這個問題，我有幾個反問：
發生分區這個假設在多大概率上會成立？哪些因素會造成分區？
如果發生分區，一致性如何定義？應用需要什么樣的一致性？
如果發生分區，可用性如何定義？應用需要什么樣的可用性？
如果不發生分區，一致性和可用性又該如何取舍？
2 全球規模分布式系統
分布式系統是指聯網的計算機通過消息傳遞來協調行為的系統。在這樣的系統中機器之間并發執行，獨立故障，并且沒有全局狀態和全局鎖。
隨著互聯網公司的全球化，為了保證服務質量和響應速度，各大互聯網公司（ Google,Amzon,非死book,Alibaba 等）紛紛在全球建立數據中心，部署服務和放置數據。為了提高可用性和響應速度，以及滿足容災等需求，這些系統都采用了復制技術。這就帶來了服務和數據狀態的全球范圍內的數據復制和一致性問題。
類似這樣的系統有： Dynamo ， PNUTS ， Cassandra ， Megastore ， Mesa ， Walter ， COPS ， Spanner ， Gemini 等。
3 分布式系統設計的兩大原則
分布式系統設計的原則有很多，這里介紹兩個基礎性的原則。
3.1 通過復制來提高可用性
通過復制來提高可用性，這是分布式系統設計的首要原則。從復制類型來看，復制可以分為主動復制和被動復制。
在 主動復制 中，每個客戶端請求都由所有服務器處理。主動復制首先由 Leslie Lamport 以“狀態機復制”命名。這要求由服務器托管的進程是確定性的。確定性意味著，給定相同的初始狀態和請求序列，所有過程將產生相同的響應序列，并且最終處于相同的最終狀態。為了使所有的服務器接收到相同的操作序列，一般都使用原子廣播協議。原子廣播協議保證所有服務器都接收到消息或沒有消息，并且他們都以相同的順序接收消息。主動復制的主要缺點是實際上大多數真實世界的服務器都是非確定性的。
在 被動復制中 ，只有一個服務器（稱為主服務器）處理客戶機請求。處理請求后，主服務器更新其他（備份）服務器上的狀態，并將響應發送回客戶端。如果主服務器發生故障，則其中一臺備份服務器就會接管它。被動復制可以用于非確定性過程。被動復制與主動復制相比的主要缺點是在失敗的情況下，客戶端的響應會被延遲。
從進程與系統交互角度來看，復制分為同步復制和異步復制。
同步復制 - 通過原子寫入操作來保證“零數據丟失”，即完全寫入。在本地和遠程副本存儲的確認之前，寫入不被認為是完整的。
異步復制 - 本地存儲確認后，寫入即被認為是完整的。遠程存儲已更新，但可能滯后很小。系統性能會因異步復制而大大提高。但是在丟失本地存儲的情況下，遠程存儲不能保證具有當前的數據副本，并且最近的數據可能會丟失。
關于復制技術，目前有三大模型：事務復制， paxos 復制和虛擬同步。事務復制， paxos 復制討論的已經比較多，虛擬同步則較少看到有產品采用。虛擬同步定義了一個動態的自組織進程組，這個進程組本身可以看作是一個復制變量，那么這個變量需要特定應用中保持一致。虛擬同步常用的場景是訂閱發布和 DHT 中相鄰節點的成員關系。虛擬同步和 paxos 協議的區別在于不同的層次： paxos 協議可以用來保證虛擬同步的進程組視圖一致。事務復制和 paxos 復制的區別在于：事務復制滿足 ACID 語義，有明確的 begin/commit/abort 接口； paxos 復制內部可能使用弱一致性的傳言協議，并可以呈現外部的一致性。 paxos 復制沒有保證提供 ACID 語義和 begin/commit/abort 接口。
https://en.wikipedia.org/wiki/Virtual_synchrony
https://en.wikipedia.org/wiki/Replication_(computing)
我個人認為復制的分類方式可以根據節點組織關系分為以下三種： master/slave 復制， paxos 復制和鏈式復制。這里不贅述。
關于復制副本的數量，通常我們討論的都是 3 個副本，已經滿足容災和高可用的需要。但是在 Chubby ， F1 和 Aurora 中為了更高的可用性，都采用了 5 或 6 個副本。結合同步復制和異步復制，以及鏈式復制，可以實現混合復制類型的系統，即 5 個副本中部分是實時同步，其他副本可以采用鏈式復制的方式，或者 paxos 多數原則的方式，實現異步復制。異步復制的副本可以作為快照讀取的副本和 OLAP 的副本。
3.2 使用 CAP 理論指導分布式系統設計
復制技術是產生一致性問題的根源。由此帶來了分布式系統設計的第二個原則。
對于 Internet 這樣的全球規模的分布式系統，一直以來討論最多的是 AP 和 CP 系統。
CP 系統是犧牲可用性的系統。復制同步的協議一般使用嚴格的法定數協議 (paxos, raft, zab) 或者 2PC 協議。 CP 類型的系統有 MongoDB ， HBase ， Zookeeper 等。
AP 系統是犧牲一致性的系統。復制同步的協議一般使用非嚴格的法定數協議。 AP 類型的系統有 Couch DB ， Cassandra ， Amazon Dynamo 等。
那么有沒有 CA 系統？如何實現 CA 系統？本文將嘗試解答這個問題。
4 重新理解 CAP
4.1 CAP 三者并不對等： P 是基礎， CA 之間 tradeoff
在全球廣域地理分布環境下（全球規模的分布式系統），網絡分區是一個自然的事實，甚至有人認為是必然的。
在這樣的情況下，有兩種聲音：
-
因為分區是必然的，系統設計時，只能實現 AP 和 CP 系統， CA 系統是不可能的。
-
從技術上來說，分區確實會出現，但從效果來說，或者從概率來說，分區很少出現，可以認為系統不會發生分區。由于分區很少發生，那么在系統不存在分區的情況下沒什么理由犧牲 C 或 A 。
從更廣闊的分布式計算理論背景下審視 CAP 理論，可以發現 C ， A ， P 三者并不對等。
CAP 之父在《 Spanner ，真時， CAP 理論》一文中寫道：如果說 Spanner 真有什么特別之處，那就是谷歌的廣域網。 Google 通過建立私有網絡以及強大的網絡工程能力來保證 P ，在多年運營改進的基礎上，在生產環境中可以最大程度的減少分區發生，從而實現高可用性。
從 Google 的經驗中可以得到的結論是，一直以來我們可能被 CAP 理論蒙蔽了雙眼， CAP 三者之間并不對稱， C 和 A 不是 P 的原因啊（ P 不能和 CA trade-off ， CP 和 AP 中不存在 tradeoff ， tradeoff 在 CA 之間）。提高一個系統的抗毀能力，或者說提高 P （分區容忍能力）是通過提高基礎設施的穩定性來獲得的，而不是通過降低 C 和 A 來獲得的。也就說犧牲 C 和 A 也不能提高 P 。
還有一種說法是，放棄 C 不是為了獲得 A ，而是為了低延遲（延遲不也是可用性的內涵嗎？我這里有疑問）。 PNUTS 為了降低 WAN 上的消息事務的延遲（幾百毫秒，對于像亞馬遜和雅虎這樣的企業需要實施的許多 Web 應用程序來說，成本太高），采用放棄一致性的做法。
而 CA 是系統的剛性強需求，但是 CA 兩者也不對等。系統無論如何要保證一致性（無論事先還是事后，這是系統設計的最大不變性約束，后文會詳述），在這個前提下，可以談談可用性的程度。 Google 的 Spanner 就是這樣的思路。
總結： P 是一個自然的事實， CA 是強需求。三者并不對等。
補充：文章寫完之后，看到最新出版的文章《分布式數據庫中一致性與可用性的關系》，值得一讀。
4.2 保證不發生分區， CA 也不容易兼得
在分布式系統中，安全性，活性是本質需求，并且廣泛的研究結果是分布式系統中一直存在一個廣泛意義的 trade-off ：在不可靠的分布式系統中無法同時實現安全性和活性。分布式系統的設計中充滿了安全性和活性的 trade-off ， FLA 著名的論文《 Impossibility of Distributed Consensus withOne Faulty process 》就是說我們不可能設計一個算法既可以絕對保證一致性（安全性）又無需時間等待的實現一致性（活性）。
CAP 就是這個 trade-off 的的集中體現。分別對應于 :
-
Safety: 非正式的說，一個算法沒有任何壞的事情發生，那么該算法就是安全的。 CAP 中的 C 就是典型的 safety 屬性：所有對客戶的響應都是正確的。
-
Liveness: 相反，一個算法最終有有一些好的事情發生，那么該算法就是活性的。 CAP 中的 A 就是典型的 liveness 屬性：所有的客戶最終都會收到回應。
FLA 中的故障是指：
Unreliable: 有很多種方式可以讓一個系統不可靠， CAP 中的 P ，以及其他故障：系統崩潰，消息丟失，惡意攻擊，拜占庭故障等。
所以， CAP 理論可以說是 FLA 不可能性的不同表達方式。 P 只是 Unreliable 的一種極端形式而已。在 Google 的 Chubby 文章中，指出 paxos 協議維護系統的 safety ，引入時鐘來保證 liveness ，由此克服 FLA 的不可能性。實際上，基本的 Paxos 協議可以保證值一旦被選出后就一定不會改變，但不能保證一定會選出值來。換句話說，這個投票算法不一定收斂。所以在系統設計時， paxos 算法的使用是有條件的。
在數據庫領域， CAP 也正是 ACID 和 BASE 長期博弈 (tradeoff) 的結果。 ACID 伴隨數據庫的誕生定義了系統基本設計思路，所謂先入為主。 2000 年左右，隨著互聯網的發展，高可用的話題被擺上桌面，所以提出了 BASE 。從此 C 和 A 的取舍消長此起彼伏，其結晶就是 CAP 理論。
從 ACID 和 BASE 來說， ACID 是為了保證一致性而誕生，因而側重一致性； BASE 是為了高可用系統的設計而誕生，因而側重可用性。在分解 C 和 A 的情況時，肯定要涉及 P ，所以 CAP 理論統一了這一切。如果非要說酸堿，或者說酸堿平衡，那就是平衡于 CAP 理論。
CAP 并不與 ACID 中的 A （原子性）沖突，值得討論的是 ACID 中的 C （一致性）和 I （隔離性）。 ACID 的 C 指的是事務不能破壞任何數據庫規則，如鍵的唯一性。與之相比， CAP 的 C 僅指單一副本這個意義上的一致性，因此只是 ACID 一致性約束的一個嚴格的子集。如果系統要求 ACID 中的 I （隔離性），那么它在分區期間最多可以在分區一側維持操作。事務的可串行性（ serializability ）要求全局的通信，因此在分區的情況下不能成立。
C 與 A 之間的取舍可以在同一系統內以非常細小的粒度反復發生，而每一次的決策可能因為具體的操作，乃至因為牽涉到特定的數據或用戶而有所不同。我們在分布式系統設計的兩大原則中討論過保持一致性的手段：同步復制和異步復制，結合復制協議的各種模式，請參考下表。例如簡單滿足了 C ，但延遲升高了，吞吐量下來了，還有什么可用性？我覺得延遲是包含在可用性的范圍內的，不可用就是延遲的極大極限值。還有文章就只討論一致性，可用性和性能問題（比如阿里何登成的《數據一致性 - 分區可用性 - 性能 —— 多副本強同步數據庫系統實現之我見》），說明在不考慮分區的情況下， CA 問題依然是系統設計的難點。
重新審視本文的時候，恰好看到一個新的理論 PACELC ： even when the system is running normally in theabsence of partitions, one has to choose between latency (L) and consistency(C). 可謂和我的想法不謀而合。
PACELC ： In case of network partitioning (P) in a distributed computersystem, one has to choose between availability (A) and consistency (C) (as perthe CAP theorem), but else (E), even when the system is running normally in theabsence of partitions, one has to choose between latency (L) and consistency(C).（https://en.wikipedia.org/wiki/PACELC_theorem）
可用性并不是簡單的網絡連通，服務可以訪問，數據可以讀取就是可用性，對于互聯網業務，可用性是完整的用戶體驗，甚至會延伸到用戶現實生活中（補償）。有的系統必須容忍大規模可靠分布式系統中的數據不一致，其中原因就是為了在高并發條件下提高讀寫性能。
必須容忍大規模可靠分布式系統中的數據不一致，有兩個原因：在高并發條件下提高讀寫性能， 并要區分物理上導致的不一致和協議規定的不一致：
-
節點已經宕機，副本無法訪問（物理）
-
法定數模型會使部分系統不可用的分區情況，即使節點已啟動并運行（ paxos 協議）
-
網絡斷開，節點孤立（物理）
所以，保證不發生分區， CA 也不是免費午餐： 盡管保證了網絡可靠性，盡量不發生分區，同時獲得 CA 也不是一件簡單的事情。
CA 系統才是真正的難點。
宣稱是 CA 系統的，目前有兩家：一家是 Google 的 Spanner ，一家是 Alibaba 的 OceanBase 。
4.3 發生分區時，也不要隨意犧牲 CA
雖然架構師仍然需要在分區的前提下對數據一致性和可用性做取舍，但具體如何處理分區和恢復一致性，這里面有不計其數的變通方案和靈活度。
當發生分區時，系統設計人員不應該盲目地犧牲一致性或可用性。 當分區存在或可感知其影響的情況下，就要預備一種策略去探知分區并顯式處理其影響。這樣的策略應分為三個步驟：探知分區發生，進入顯式的分區模式以限制某些操作，啟動恢復過程以恢復數據一致性并補償分區期間發生的錯誤。
這一切都需要在系統設計之初考慮到，并在測試時模擬各種故障保證覆蓋到你的測試點。
構建高度穩健的基礎設施永遠是第一要務，所以我不認為網絡分區與 CA 屬性是對等的。
5 分解，分解，分解
分解 CAP ： “三選二”的公式一直存在著誤導性，它會過分簡單化各性質之間的相互關系。現在我們有必要辨析其中的細節。
CAP 三種性質都可以在程度上衡量，并不是非黑即白的有或無。可用性顯然是在 0% 到 100% 之間連續變化的，一致性分很多級別，連分區也可以細分為不同含義，如系統內的不同部分對于是否存在分區可以有不一樣的認知。
5.1 P 分解：延遲？故障？分區？
if you're working with distributed systems,you should always be thinking about failure.
如果你正在使用分布式系統，你應該永遠考慮失敗。
故障，延遲，分區，是一組非常相關的概念。
在通信網絡中，最重要的兩個屬性是帶寬和延遲。延遲也往往取決于鏈路轉發節點的效率。由于延遲的存在，系統很難就全局狀態達成一致。當鏈路發生故障，就會導致網絡分區。由于延遲的特性，就算鏈路沒有發生故障，系統也可能判斷發生了分區。
對 P 的分解需要從網絡開始。網絡包含了基礎設施，光速限制以及軟件配置與升級等。 Google 通過建設自己廣域網獲得高可靠的基礎設施支撐，對于 Google Spanner 的 CA 系統， CAP 之父曾總結說網絡才是根本。
而光速限制則告誡我們：一致性是一個結果，不是實時的狀態。由于光速無法超越，則延遲必然存在（下圖顯示從加拿大到荷蘭的網絡延遲在 150 毫秒左右）。延遲的存在讓一個節點無法獲得對方節點的實時狀態。
https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html
由于延遲的存在， 有人說，即時性和全球性的一致性是不可能的。宇宙根本不允許它。我以前從事分布式系統研發時，帶我的博士總是告誡說，系統設計不要超越時空的限制。
軟件配置與升級則體現基礎設施搭建工程能力和運維能力。 Google 調查了 Spanner 事故的內部原因分類顯示，網絡類別的事故是由網絡分區和網絡配置問題造成的。
Michael Stonebraker 在《 Errors in Database Systems, Eventual Consistency, and the CAP Theorem 》一文中通過對故障進行分解，給出進入 CAP 討論范圍的部分故障列表：
1 ）應用程序錯誤。應用程序執行一個或多個不正確的更新。一般來說，這不是幾分鐘到幾個小時之后才發現的。必須將數據庫備份到違規事務之前的一個時間點，然后重做后續活動。
2 ）可重復的 DBMS 錯誤。 DBMS 在處理節點上崩潰。在具有副本的處理節點上執行相同的事務將導致備份崩潰。這些錯誤被稱為 Bohr 錯誤。
3 ）不可重復的 DBMS 錯誤。數據庫崩潰了，但是一個副本很可能沒問題。這些通常是由處理異步操作的奇怪角落造成的，并且被稱為 Heisenbugs 。
4 ）操作系統錯誤。操作系統崩潰在一個節點，產生“藍屏死亡”。
5 ）本地集群中的硬件故障。這些包括內存故障，磁盤故障等。通常，這些會導致操作系統或 DBMS 的“緊急停止”。但是，有些時候這些失敗就像 Heisenbugs 一樣。
6 ）本地集群中的網絡分區。 LAN 失敗，節點不能再相互通信。
7 ）災難。地方數據中心被洪水，地震等等所消滅。群集不再存在。
8 ） WAN 中的網絡故障將集群連接在一起。 WAN 失敗，群集不能再相互通信。
Michael Stonebraker 總結認為錯誤 1,2 和 7 是 CAP 定理根本不適用的情況的示例， 3,4,5 和 6 是本地故障，錯誤 8 是 WAN 網絡中的一個分區，但是是非常罕見的。所以不要盲目的 follow CAP 理論，輕易的放棄一致性。分解故障，進行針對性的設計。
PACELC 理論本質就是對分區進行分解：發生分區時，在 CA 之間取舍；沒有發生分區時，在 C 和延遲之間取舍。（我們系統設計的大多數情況就是在沒有發生分區的時候）
如何探知分區？這涉及到分布式系統中常見且重要的話題：故障檢測。故障檢測需要從從分布式系統的定義談起：節點和連線的模型。在分布式系統中，通過消息通信建立的連接，連接兩端的節點在任意時刻，以及節點中運行的進程，隨時都可能發生故障。
在分布式系統中，節點故障判斷必然依賴超時（時限設置），在一定的超時時間內，消息可能延遲，也可能鏈路故障造成的節點不可達，在這樣的情況下，如何判斷節點故障？常見的策略是間隔一段時間重新嘗試連接，降低誤判的風險，這樣就增加了系統的延遲時間，也就是降低了可用性。遠端節點無法準確的判斷存活還是故障，就無法準確的判斷分區是否真的發生。所以 CAP 之父在其著名的文章《 CAP Twelve Years Later: How the "Rules" Have Changed 》中提出了分布式設計的核心問題：分區兩側是否能夠在無通信的情況下繼續其操作？
下面舉一個復雜的例子。在分布式事務這樣的場景中，涉及的消息和操作很多。每一條消息和操作都有可能故障，如下圖所示。這就要求我們在程序的設計和實現過程中，針對大量的異常和故障編寫代碼。這就是故障檢測之后的故障處理。
故障處理如何做？有以下模型可以考慮。
Fail-Fast ：從字面含義看就是“快速失敗”，盡可能的發現系統中的錯誤，使系統能夠按照事先設定好的錯誤的流程執行，對應的方式是“ fault-tolerant （容錯）”。只發起一次調用，失敗立即報錯 , 通常用于非冪等性的寫操作。 如果有機器正在重啟，可能會出現調用失敗 。
Fail-Over ：含義為“失效轉移”，是一種備份操作模式，當主要組件異常時，其功能轉移到備份組件。其要點在于有主有備，且主故障時備可啟用，并設置為主。如 Mysql 的雙 Master 模式，當正在使用的 Master 出現故障時，可以拿備 Master 做主使用。阿里同學認為這里可以指失敗自動切換。當出現失敗，重試其它服務器，通常用于讀操作（推薦使用）。 重試會帶來更長延遲。
Fail-Safe ：含義為“失效安全”，即使在故障的情況下也不會造成傷害或者盡量減少傷害。維基百科上一個形象的例子是紅綠燈的“沖突監測模塊”當監測到錯誤或者沖突的信號時會將十字路口的紅綠燈變為閃爍錯誤模式，而不是全部顯示為綠燈。有時候來指代“自動功能降級” (Auto-Degrade) 。阿里的同學認為失敗安全，出現異常時，直接忽略，通常用于寫入審計日志等操作。調用信息丟失 可用于生產環境 Monitor 。
Fail-Back ： Fail-over 之后的自動恢復，在簇網絡系統（有兩臺或多臺服務器互聯的網絡）中，由于要某臺服務器進行維修，需要網絡資源和服務暫時重定向到備用系統。在此之后將網絡資源和服務器恢復為由原始主機提供的過程，稱為自動恢復。阿里的同學認為失敗自動恢復，后臺記錄失敗請求，定時重發。通常用于消息通知操作 不可靠，重啟丟失。可用于生產環境 Registry 。
Forking 并行調用多個服務器，只要一個成功即返回，通常用于實時性要求較高的讀操作。 需要浪費更多服務資源 。
Broadcast 廣播調用，所有提供逐個調用，任意一臺報錯則報錯。通常用于更新提供方本地狀態速度慢，任意一臺報錯則報錯。
上述故障模型是從系統設計的角度出發的，根據不同的需要設計不同故障處理方案。現在看來，系統的外延已經擴大。系統的容錯性，或者分區容錯能力，不能僅僅使用事先和事中的方案解決，系統的容錯性還包括事后處理。
總之，分區發現的要義是工程問題，即如何構建和加強基礎設置的穩定性，如何設計出準確高效的故障檢測算法。
5.2 C 分解：服務器端與客戶端
曾經，透明性也是系統的一個要求和屬性（透明性：對于系統的用戶來說，只能感受到一個系統而不是多個協作系統）。曾經，系統的一致性模型只有一個：當進行更新時，所有觀察者都會看到更新。曾經，我們的系統可以用 “ 鄰國相望，雞犬之聲相聞，民至老死不相往來 ” 來描述，不是全球部署，不需要復制技術來保證高可用性，也就不會有一致性問題。然而，隨著互聯網的發展，可用性被認為是互聯網系統中最重要的屬性，特別是 CAP 理論的提出，使得我們不得不重新審視當初的一些系統原則。我們必須打破系統透明性，把其中的內部細節暴露出來，同時也思考我們到底需要什么？并且需要付出什么？
關于一致性的討論主要分為三個方面：這個分法也是性能與一致性之間的平衡。
強一致性
Spanner
PNUTS: Yahoo!’s Hosted Data ServingPlatform
弱一致性
Dynamo: Amazon’s Highly Available Key-valueStore
CAP 理論：一致性與性能之間的 trade-off ，目前關于這方面的研究有很多。比如：
Consistency tradeoffs in modern distributeddatabase system design: CAP is only part of the story
Don’t Settle for Eventual:Scalable CausalConsistency for Wide-Area Storage with COPS
Consistency Tradeoffs in Modern DistributedDatabase System Design
Consistency rationing in the cloud pay onlywhen it matters
Making Geo-Replicated Systems Fast asPossible, Consistent when Necessary
分解一致性的目的是，在系統設計時，不要盲目的談 CAP 的三選二，而是通過分解不同業務場景和業務操作，使用合適的一致性模型。如上圖所示，有大量操作是屬于一致性的灰色區域。系統的設計不要以 CAP 為中心，而是以業務為中心。例如，用戶名和密碼必須強一致，而用戶的屬性信息可以是弱一致性的。
一致性模型本質上是進程和數據存儲之間關于一致性所達成的約定（ contract ）。
首先，我們從客戶端的角度，看看有哪些一致性類型。
強一致性：更新完成后，所有的后續讀操作都會返回更新值。
弱一致性：系統并不保證后續讀操作獲得更新值的時間點。
最終一致性：如果沒有更新，最終系統會返回最后更新的值。換句話說，如果系統在持續更新，則永遠無法達到一致性。
因果一致性：和寫進程具有因果關系的進程將會讀取到更新的數據，寫進程保證取代上次更更新。
讀己所寫一致性：進程永遠讀取自己上次更新寫入的最新值，而不可能讀取到任何歷史數據。這是傳統操作系統默認的一致性行為。
會話一致性：在同一個會話內，系統保證讀己所寫的一致性。
單調讀一致性：進程在讀取到系統的一個特定值，則系統永遠不會再返回該值以前的任何值。
單調寫一致性：系統保證同一個進程寫入操作的串行化。對于多副本系統來說，保證寫順序的一致性（串行化），是很重要的。
然后我們看下服務器端。
強一致性：
為讀而優化：
為寫而優化：
還有一種一致性模型是 PNUTS 中中提出的，僅保證“時間線一致性”來放松一致性，其中副本可能不一致，但保證在所有副本上以相同的順序應用更新。
Azure Cosmos DB 中也提出了幾種支持的一致性模型，并宣稱可選的支持幾種不同的一致性模型。
5.3 A 分解：出來混，遲早要還的
可用性首先體現在容錯。容錯不是系統能夠在各種故障情況下都能工作，容錯是系統發生故障時，系統能夠以明確的預定方式運行。下面列出一下可用性指標。
| Availability % |
How much downtime is allowed per year? |
| 90% ("one nine") |
More than a month |
| 99% ("two nines") |
Less than 4 days |
| 99.9% ("three nines") |
Less than 9 hours |
| 99.99% ("four nines") |
Less than an hour |
| 99.999% ("five nines") |
~ 5 minutes |
| 99.9999% ("six nines") |
~ 31 seconds |
在系統設計之初，要考慮系統提供什么程度的可用性，并采用相應的一致性模型。可用性體現在用戶體驗。在現實生活中，更高的可用性意味著更高的收入。
另外，因為分區引起的可用性問題可以通過事后補償來獲得。
C = A + compensation
總結起來， C>A>P ，這里的大于號，不是包含關系，也不是優先級關系，而是盡力保證 P 是為了 CA ，為了保證 C, 需要犧牲一點點 A 。或者也可以說 A> C>P ，為了保證可用性，需要犧牲暫時的不一致性。
這里有人可能有疑問，在某一個場景下，我選擇了可用性，放棄了一致性啊？那我說，你一定有補償措施。也就是說無論事先還是事后，你總要保證一致性。
當代 CAP 實踐應將目標定為針對具體的應用，在合理范圍內最大化數據一致性和可用性的“合力”。這樣的思路延伸為如何規劃分區期間的操作和分區之后的恢復，從而啟發設計師加深對 CAP 的認識，突破過去由于 CAP 理論的表述而產生的思維局限。
當發生分區時，如何設計可用性？以下幾個方面供思考和探討。
明確系統的不變性約束：通過仔細分析和管理在分區期間系統的不變性約束來優化 CA 屬性。我認為系統唯一的不變性約束就是數據的一致性約束。當然你也可以設計 C 和 A 都是系統的不變性約束，然后用 C=A+compensation 來保證一致性，這樣就是 CA 系統。就一致性不變性約束來說，唯一的是不變性，有兩種：系統內加鎖訪問的對象和現實生活設置的閾值。例如航空公司，不變性約束必須至少與乘客座位一樣多。如果乘客太多，有人會失去座位，理想的客戶服務會以某種方式補償這些乘客。在飛機航班“超售”的情況下，可以把乘客登機看作是對之前售票情況的分區恢復，必須恢復“座位數不少于乘客數”這項不變性約束。那么當乘客太多的時候，有些乘客將失去座位，客服需要補償他們。航空公司的例子就是系統內需要加鎖訪問的對象成為不變性約束。而像 ATM 機最后的余額不能低于零的例子就是現實生活設置的閾值，這也是不能違背的不變性約束。 ATM 機的例子也可以引入政府或者操作者的背書機制：比如引入操作者的信用，如果操作者具有超過閾值的信用，就可以繼續操作。還有一種補償方式法律的形式，透支的金額由用戶補償，多扣的手續費退回給客戶（和信用綁定：既然一致性已經打破系統的透明性，應用已經參與進來，那就干脆引入社會信用吧）。現在很多系統設計時沒有梳理清楚系統的所有不變性約束，并且對其影響也不明確，大多選擇了一致性，犧牲一點可用性。
設計補償機制：管理分區就是管理補償。根據 C=A+compensation 的思考，所謂不變性約束，前提是無法補償，如果可以補償，一切都是可變性約束。一般的補償分為內部補償和外部補償。以重復的訂單為例（還有一種情況是刪除的數據重新出現），系統可以將合并后的訂單中取消一個重復的訂單，并不通知用戶，這是內部補償。如果這次錯誤產生了外在影響，補償策略可以是自動生成一封電子郵件，向顧客解釋系統意外將訂單執行了兩次，現在錯誤已經被糾正，附上一張優惠券下次可以用。但 C=A+compensation 并沒有打破數據一致性約束，只是讓用戶在分區的情況下繼續保持可用性。
設計數據不變性：補償依賴完善的日志，我在這里借用《 How to beat the CAP theorem 》的數據不變性原理，把日志稱為數據不變性。 這里的日志是廣泛意義的日志，不僅包含數據的所有歷史版本，還包括分區歷史（時間，地點，人物，加上這些，世界上不存在重復的數據主鍵）和分區合并歷史，以及節點成員關系等。是系統重構？還是節點啟動加入系統？還是系統發生了分區？這些都要記錄下來。這樣當節點加入系統，應該能夠找到自己曾經所在的父分區。我認為數據不變性 + 補償機制可以打敗 CAP 定理。 如果分區之后要保證可用性，用于用戶繼續操作數據。那么在分區合并之后，繼續保持數據的分區狀態也是可以的（相當于多了一條分支數據）。可以讓數據的元數據中記錄分區信息，甚至記錄所有分區歷史。分區模式操作的跟蹤和限制確保知道哪些不變量可能被違反，這又使得設計者能夠為每個這樣的不變量創建恢復策略。這里和不變性原理是一致的：設計利用的基本原則是“數據本質上是不可變的”。這是因為數據總是與一個時間，人物，地點（分區）相關聯，你可以將數據視為當時的事實。所以當你的銀行帳戶的余額可能會從時間 T 到時間 T+ 1 從 10 變化到 20 ，以及操作的分區，這些數據，時間，人物，地點永遠是真實的。有了這些數據，我們可以任何的補償操作。上面訂單重復的例子，假如沒有完善的歷史記錄，就只好靠顧客親自去發現錯誤了。
應用分解：有兩個層面。第一是分解業務細節，有些時候這些細節也對應于系統調用或者 API 。例如 ATM 的基本操作是存款、取款、查看余額。在分區發生時，存款和查看是可以進行的，取款可以設置取款限額或者不設限額后續補償。第二是應用程序處理補償。不一致是否可以接受取決于客戶端應用程序。在所有情況下，開發人員需要注意，存儲系統提供一致性保證，并在開發應用程序時需要考慮。最終的一致性模型有一些實際的改進，例如會話級一致性和單調讀取，為開發人員提供更好的工具。許多時候，應用程序能夠處理存儲系統的最終一致性保證，沒有任何問題。從可用性的角度來看，阿里 OceanBase 的觀點可見一斑：數據庫一定是時延很低的，時延高就會導致應用出問題，實際上這個問題要花另外一個篇幅去講，那就是應用程序必須要去適應這種時延高的數據庫系統。當然用了 batching 和 pipeling 技術，本質上都是通用的工程優化，讓跨網絡多副本同步變得高效，但是時延一定會增加。
6 真正的難題
分布式并發讀寫事務。如果下圖所示，進程 A 和 B 是地理上分布的兩個進程， A 進程對系統發起寫操作， B 進程同時并發的讀取。
首先第一個難題，是否允許任意節點并發可寫。在 Google 的 F1 ，螞蟻的 OceanBase ，亞馬遜的 Aurora 中，都是指定一個寫節點或者更新節點的（據說 OB 升級 1.0 后，所有節點都是同等地位的）。
第二個難題，是否支持讀寫并發。這里涉及到讀寫一致性的問題。比如上圖，當用戶 A 在寫入系統的時候，用戶 B 的讀取情況是什么樣子的？是讀取數據的上一個快照，還是讀取 A 寫入的最新數據？用戶 A 和用戶 B 在讀取的過程中如何加鎖？特別跨越廣域網的不同的數據中心的時候。這里 tricky 的地方在于是否要對整個數據加讀寫鎖。目前我看 Google 的主要方法是目前 A 進程在寫的時候采用多版本數據存儲，并保證分布式事務。 B 進程可以實現無鎖的快照讀取。基于中心節點的機制，如果讀寫沖突或者寫寫沖突，會被鎖機制拒絕，用戶操作失敗。
這個問題還涉及到分布式事務的隔離性問題。傳統數據庫 ANSISQL 標準定義了四個 “ 隔離等級 ” ：
-
未提交讀：一個事務可以讀任何已提交或未提交的數據。這可以通過“讀操作不需要請求任何鎖”來實現。
-
已提交讀：一個事務可以讀任何已提交的數據。對于同一個對象的重復讀可能導致讀到不同版本的數據。實現方式是，讀數據前必須首先獲得一個讀操作鎖，一旦數據讀取之后該鎖被立即釋放。
-
可重復讀：一個事務只能讀取一個已提交數據的一個版本；一旦該事務讀取了一個對象，那么，它將只能讀取該對象的同一個版本。實現方式是，事務在請求讀數據之前必須獲得一個鎖，并且保持該鎖直到事務結束。
-
可串行化：保證完全的可串行化。
分布式數據庫如何滿足，是設計分布式系統的首要問題。嚴格說來，Google的實現應該是一種可重復讀（這里還要存疑）。
第三個難題，元數據如何保存。用戶 A 或 B 在讀取或者寫入系統的時候，如何獲得數據的版本和時間戳？這在 OceanBase ， spanner/F1 ，以及 TiDB 中 PD 機制中略有涉及，但都不詳細。如果元數據在異地數據中心，獲得元數據將會有一個廣域網延遲到時間開銷。我認為 Google 的 truetime 是用了物理時間代替經典的邏輯時鐘，并且作為副本的時間戳，也就是版本號，這樣基于 truetime 的精巧 API 設計，讓版本號和物理時間線性對齊，無需去查詢副本的元數據信息。相反的例子是 Google Chubby 提到的：在一個已經初步成熟的復雜應用程序的每次操作中引入版本號的開銷是非常大的。所以后來退一步求其次， Chubby 采用了僅僅在所有使用鎖的操作中引入版本號。
第四個難題，在讀寫事務期間，節點故障。注意，這里是指任意節點故障，包括一次事務中的 leader 節點，參與節點，以及用戶節點。特別是用戶所在的節點故障要求系統必須有加鎖租約等自恢復機制。
關于鎖的設計，在 CAP 的范圍內，需要滿足三點：
-
鎖對象信息的要寫入多副本以應對故障
-
不同對象的鎖信息需要分布化和負載均衡
-
鎖信息寫入持久化存儲系統
注意，這里鎖的概念和 Google Chubby 中鎖的概念是不同的。這里是一種粗粒度的鎖（ leader 選舉），其作者也不建議把 Chubby 應用在細粒度鎖（事務更新）的場景中。這兩種鎖在 CAP 的范圍內使用時值得非常細心的研究和討論，特別是在分布式數據庫領域內。
第五個難題，嵌套事務或者鏈式事務。這是電子商務的基礎。下面以 Percolator 的實現說明這個問題。銀行轉賬， Bob 向 Joe 轉賬 7 元。該事務于 start timestamp =7 開始， commit timestamp=8 結束。具體過程如下：
1. 初始狀態下， Bob 的帳戶下有 10 （首先查詢 column write 獲取最新時間戳數據 , 獲取到 data@5, 然后從 column data 里面獲取時間戳為 5 的數據，即 $10 ）， Joe 的帳戶下有 2 。
2 、轉賬開始，使用 stattimestamp=7 作為當前事務的開始時間戳，將 Bob 選為本事務的 primary ，通過寫入 Column Lock 鎖定 Bob 的帳戶，同時將數據 7:$3 寫入到 Column,data 列。
3 、同樣的，使用 stat timestamp=7 ，鎖定 Joe 的帳戶，并將 Joe 改變后的余額寫入到 Column,data, 當前鎖作為 secondary 并存儲一個指向 primary 的引用（當失敗時，能夠快速定位到 primary 鎖，并根據其狀態異步清理）
4 、事務帶著當前時間戳 commit timestamp=8 進入 commit 階段：刪除 primary 所在的 lock ，并在 write 列中寫入從提交時間戳指向數據存儲的一個指針 commit_ts=>data @7 。至此，讀請求過來時將看到 Bob 的余額為 3 。
5 、依次在 secondary 項中寫入 write 并清理鎖，整個事務提交結束。在本例中，只有一個 secondary:Joe.
7 總結
本文的主要觀點是：
-
CAP 中的三個因素并不對等， P 是基礎， CA 之間需要 tradeoff 。系統設計不是三選二的取舍。
-
延遲作為可用性的指標和體現，系統設計通常需要在 C 和延遲之間 tradeoff 。
-
CAP 真正的 trade-off 在 CA 之間，系統設計需要細心分解 C 和 A ，不同的系統有不同的需求。本文在對 CAP 分解的基礎上，提供了系統設計的一些思考方法。未來系統的設計必然是要滿足多種一致性模型和多種可用性需求（例如微軟的 cosmos DB 聲稱支持多種一致性模型）。
-
針對分區設計數據不變性，記錄所有的分區歷史，這讓分區合并之后的 compensation 有據可依。借助社會和法律因素，一致性最終都是可以保證的。另外，如果像阿里日照的見解，可用性是一定時間延遲（可能是一天）之后返回響應（在這期間實現服務切換），那么可用性也是可以保證的。
-
在第 3 點的基礎上，未來分布式系統需要從整體上考慮，即需要考慮 IT 基礎設施，也要考慮應用的適應和配合，以及人類社會中的法律和補償。
-
本文討論了在 CAP 范圍內，分布式系統設計的一些難點。
注意本文的分區和數據庫的分片（分區）不是一個概念。
8 附錄
8.1 附錄 1 ：不變性如何打敗 CAP 定理？
以下翻譯自《 how to beat CAP 》。
CAP 定理仍然適用，所以你需要在可用性和一致性上做出選擇，這里的漂亮之處在于，一旦你權衡之后做出了選擇，你就做完了所有的事情。通常的那些因為 CAP 定理帶來的問題，都可以通過不可改變的數據和從原始數據中計算查詢來規避。
如果你選擇一致性而不是可用性，那么跟以前并沒有多大的區別，因為你放棄了可用性，所以一些時候你將無法讀取或者寫入數據。當然這只是針對對強一致性有要求的系統。
如果你選擇可用性而不是一致性，在這種情況下，系統可以達到最終一致性而且規避了所有最終一致性帶來的復雜問題。由于系統總是可用的，所以你總可以寫入新數據或者進行查詢。在出錯情況下，查詢可能返回的不是最近寫入的數據，但根據最終一致性，這個數據最終會一致，而查詢函數最終會把這個數據計算進去。
這里的關鍵在于數據是不可變的。不可變數據意味著這里沒有更新操作，所以不可能出現數據復制不同這種不一致的情況，也意味著不需要版本化的數據、矢量時鐘或者讀取修復。在一個查詢場景中，一個數據只有存在或者不存在兩種情況。這里只有數據和在數據之上的函數。這里沒有需要你為確保最終一致性額外做的事情，最終一致性也不會因此使你的系統變得復雜。
8.2 附錄 2 ：放棄 P, 選擇 C
在《 Errors in DatabaseSystems, Eventual Consistency, and the CAP Theorem 》一文中， Michael Stonebraker 指出：
A partition in a WAN network. There is enough redundancy engineered into today’s WANs that apartition is quite rare. My experience is that local failures andapplication errors are way more likely. Moreover, the most likely WANfailure is to separate a small portion of the network from the majority. Inthis case, the majority can continue with straightforward algorithms, and onlythe small portion must block. Hence, itseems unwise to give up consistency all the time in exchange for availabilityof a small subset of the nodes in a fairly rare scenario.
In summary, one should not throw out the C so quickly, since there are realerror scenarios where CAP does not apply and it seems like a bad tradeoff inmany of the other situations.
8.3 附錄 3 ：用 PACELC 替換 CAP
《 Problems with CAP,and Yahoo’s little known NoSQL system 》
Not only is the asymmetry of thecontributions of C, A, and P confusing, but the lack of latency considerationsin CAP significantly reduces its utility.
In conclusion, rewriting CAP as PACELC removessome confusing asymmetry in CAP, and, in my opinion, comes closer to explainingthe design of NoSQL systems.
9 參考文獻
Immutability Changes Everything
Transactions Across Datacenters
https://snarfed.org/transactions_across_datacenters_io.html
From the Ground Up: Reasoning AboutDistributed Systems in the Real World
http://bravenewgeek.com/from-the-ground-up-reasoning-about-distributed-systems-in-the-real-world/
How Google Serves Data From MultipleDatacenters
http://highscalability.com/blog/2009/8/24/how-google-serves-data-from-multiple-datacenters.html
Everything You Know About Latency Is Wrong
http://bravenewgeek.com/everything-you-know-about-latency-is-wrong/
You Can’t Sacrifice Partition Tolerance
https://codahale.com/you-cant-sacrifice-partition-tolerance/
Distributed systems for fun and profit
http://book.mixu.net/distsys/single-page.html
Distributed Systems and the CAP Theorem
http://ternarysearch.blogspot.fi/2014/03/distributed-systems-and-cap-theorem.html
CAP Twelve Years Later: How the"Rules" Have Changed
http://www.infoq.com/cn/articles/cap-twelve-years-later-how-the-rules-have-changed
《 How to beat the CAPtheorem 》
A Conversation with Bruce Lindsay
http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html
http://ternarysearch.blogspot.fi/2014/03/distributed-systems-and-cap-theorem.html
Rethinking Eventual Consistency: Can we dobetter?
Rethinking Eventual Consistency
Perspectives on the CAP Theorem
Spanner, TrueTime & The CAP Theorem
Eventual Consistent Databases: State of theArt
Incremental Consistency Guarantees forReplicated Objects
http://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
https://github.com/aphyr/partitions-post
https://ying-zhang.github.io/cloud/2017/spanner-truetime-cap/index.html
《數據一致性 - 分區可用性 - 性能 —— 多副本強同步數據庫系統實現之我見》
來自：http://mp.weixin.qq.com/s/gV7DqSgSkz_X56p2X_x_cQ