喔家ArchiSelf

一半是20多年老程式設計師的技術生涯，一半是人到中年卻仍嚮往青春的生活感悟，交織起來，是一個享受生活的老碼農。------Architect oneSelf 架構自己

Author

Taosheng Shi

WeChat Contact

data-lake

Mail Contact

[email protected]

Organization

NOKIA

Document category

Distributed System

Document location

https://github.com/stone-note/articles

Version

Status

Date

Author

Description of changes

0.1

Draft

12/7/2017

Taosheng Shi

Initiate

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,Facebook,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理論指導分散式系統設計

複製技術是產生一致性問題的根源。由此帶來了分散式系統設計的第二個原則。

CP系統是犧牲可用性的系統。複製同步的協議一般使用嚴格的法定數協議 (paxos, raft, zab)或者2PC協議。CP型別的系統有 MongoDB， HBase， Zookeeper等。

AP系統是犧牲一致性的系統。複製同步的協議一般使用非嚴格的法定數協議。AP型別的系統有 Couch DB，Cassandra，Amazon Dynamo等。

那麼有沒有CA系統？如何實現CA系統？本文將嘗試解答這個問題。

4 重新理解CAP4.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事故的內部原因分類顯示，網路類別的事故是由網路分割槽和網路配置問題造成的。

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鎖，並根據其狀態非同步清理）

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範圍內，分散式系統設計的一些難點。

注意本文的分割槽和資料庫的分片（分割槽）不是一個概念。