CAP 理論與分布式系統(tǒng)設(shè)計
2018-07-20 來源：編程學習網(wǎng)
CAP 和 分布式系統(tǒng)的討論和研究很多，但我認為這一篇肯定給大家?guī)聿灰粯拥氖斋@，歡迎留言討論。
| 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 |
||||||||||
|
|||||||||||
Contents
1 .................... 引言
2 .................. 全球規(guī)模分布式系統(tǒng)
3 .................. 分布式系統(tǒng)設(shè)計的兩大原則
3.1 ................ 通過復(fù)制來提高可用性
3.2 ............... 使用 CAP 理論指導分布式系統(tǒng)設(shè)計
4 .................. 重新理解 CAP
4.1 ................ CAP 三者并不對等，三選二是誤導
4.2 ............... 保證不發(fā)生分區(qū)， CA 也不容易兼得
4.3 ............... 發(fā)生分區(qū)時，也不要隨意犧牲 CA
5 .................. 分解，分解，分解
5.1 ................ P 分解：延遲？故障？分區(qū)？
5.2 ............... C 分解：服務(wù)器端與客戶端
5.3 ............... A 分解：出來混，遲早要還的
6 ................... 真正的難題
7 ................... 總結(jié)
8 ................... 附錄
8.1 ................ 附錄 1 ：不變性如何打敗 CAP 定理？
8.2 ............... 附錄 2 ：放棄 P, 選擇 C
8.3 ............... 附錄 3 ：用 PACELC 替換 CAP
9 .................. 參考文獻
1 引言
在現(xiàn)代分布式系統(tǒng)中，節(jié)點數(shù)目是巨大的。在 CAP 理論的范圍內(nèi)， MichaelStonebraker 斷言分區(qū)必然會發(fā)生，并且系統(tǒng)內(nèi)發(fā)生節(jié)點失敗的機會隨著節(jié)點數(shù)的增加而呈指數(shù)級增加：
基于這樣的事實，很多人會問：
如果發(fā)生分區(qū)（故障），系統(tǒng)會犧牲什么？一致性還是可用性？
對于這個問題，我有幾個反問：
發(fā)生分區(qū)這個假設(shè)在多大概率上會成立？哪些因素會造成分區(qū)？
如果發(fā)生分區(qū)，一致性如何定義？應(yīng)用需要什么樣的一致性？
如果發(fā)生分區(qū)，可用性如何定義？應(yīng)用需要什么樣的可用性？
如果不發(fā)生分區(qū)，一致性和可用性又該如何取舍？
2 全球規(guī)模分布式系統(tǒng)
分布式系統(tǒng)是指聯(lián)網(wǎng)的計算機通過消息傳遞來協(xié)調(diào)行為的系統(tǒng)。在這樣的系統(tǒng)中機器之間并發(fā)執(zhí)行，獨立故障，并且沒有全局狀態(tài)和全局鎖。
隨著互聯(lián)網(wǎng)公司的全球化，為了保證服務(wù)質(zhì)量和響應(yīng)速度，各大互聯(lián)網(wǎng)公司（ Google,Amzon,Facebook,Alibaba 等）紛紛在全球建立數(shù)據(jù)中心，部署服務(wù)和放置數(shù)據(jù)。為了提高可用性和響應(yīng)速度，以及滿足容災(zāi)等需求，這些系統(tǒng)都采用了復(fù)制技術(shù)。這就帶來了服務(wù)和數(shù)據(jù)狀態(tài)的全球范圍內(nèi)的數(shù)據(jù)復(fù)制和一致性問題。
類似這樣的系統(tǒng)有： Dynamo ， PNUTS ， Cassandra ， Megastore ， Mesa ， Walter ， COPS ， Spanner ， Gemini 等。
3 分布式系統(tǒng)設(shè)計的兩大原則
分布式系統(tǒng)設(shè)計的原則有很多，這里介紹兩個基礎(chǔ)性的原則。
3.1 通過復(fù)制來提高可用性
通過復(fù)制來提高可用性，這是分布式系統(tǒng)設(shè)計的首要原則。從復(fù)制類型來看，復(fù)制可以分為主動復(fù)制和被動復(fù)制。
在 主動復(fù)制 中，每個客戶端請求都由所有服務(wù)器處理。主動復(fù)制首先由 Leslie Lamport 以“狀態(tài)機復(fù)制”命名。這要求由服務(wù)器托管的進程是確定性的。確定性意味著，給定相同的初始狀態(tài)和請求序列，所有過程將產(chǎn)生相同的響應(yīng)序列，并且最終處于相同的最終狀態(tài)。為了使所有的服務(wù)器接收到相同的操作序列，一般都使用原子廣播協(xié)議。原子廣播協(xié)議保證所有服務(wù)器都接收到消息或沒有消息，并且他們都以相同的順序接收消息。主動復(fù)制的主要缺點是實際上大多數(shù)真實世界的服務(wù)器都是非確定性的。
在 被動復(fù)制中 ，只有一個服務(wù)器（稱為主服務(wù)器）處理客戶機請求。處理請求后，主服務(wù)器更新其他（備份）服務(wù)器上的狀態(tài)，并將響應(yīng)發(fā)送回客戶端。如果主服務(wù)器發(fā)生故障，則其中一臺備份服務(wù)器就會接管它。被動復(fù)制可以用于非確定性過程。被動復(fù)制與主動復(fù)制相比的主要缺點是在失敗的情況下，客戶端的響應(yīng)會被延遲。
從進程與系統(tǒng)交互角度來看，復(fù)制分為同步復(fù)制和異步復(fù)制。
同步復(fù)制 - 通過原子寫入操作來保證“零數(shù)據(jù)丟失”，即完全寫入。在本地和遠程副本存儲的確認之前，寫入不被認為是完整的。
異步復(fù)制 - 本地存儲確認后，寫入即被認為是完整的。遠程存儲已更新，但可能滯后很小。系統(tǒng)性能會因異步復(fù)制而大大提高。但是在丟失本地存儲的情況下，遠程存儲不能保證具有當前的數(shù)據(jù)副本，并且最近的數(shù)據(jù)可能會丟失。
關(guān)于復(fù)制技術(shù)，目前有三大模型：事務(wù)復(fù)制， paxos 復(fù)制和虛擬同步。事務(wù)復(fù)制， paxos 復(fù)制討論的已經(jīng)比較多，虛擬同步則較少看到有產(chǎn)品采用。虛擬同步定義了一個動態(tài)的自組織進程組，這個進程組本身可以看作是一個復(fù)制變量，那么這個變量需要特定應(yīng)用中保持一致。虛擬同步常用的場景是訂閱發(fā)布和 DHT 中相鄰節(jié)點的成員關(guān)系。虛擬同步和 paxos 協(xié)議的區(qū)別在于不同的層次： paxos 協(xié)議可以用來保證虛擬同步的進程組視圖一致。事務(wù)復(fù)制和 paxos 復(fù)制的區(qū)別在于：事務(wù)復(fù)制滿足 ACID 語義，有明確的 begin/commit/abort 接口； paxos 復(fù)制內(nèi)部可能使用弱一致性的傳言協(xié)議，并可以呈現(xiàn)外部的一致性。 paxos 復(fù)制沒有保證提供 ACID 語義和 begin/commit/abort 接口。
https://en.wikipedia.org/wiki/Virtual_synchrony
https://en.wikipedia.org/wiki/Replication_(computing)
我個人認為復(fù)制的分類方式可以根據(jù)節(jié)點組織關(guān)系分為以下三種： master/slave 復(fù)制， paxos 復(fù)制和鏈式復(fù)制。這里不贅述。
關(guān)于復(fù)制副本的數(shù)量，通常我們討論的都是 3 個副本，已經(jīng)滿足容災(zāi)和高可用的需要。但是在 Chubby ， F1 和 Aurora 中為了更高的可用性，都采用了 5 或 6 個副本。結(jié)合同步復(fù)制和異步復(fù)制，以及鏈式復(fù)制，可以實現(xiàn)混合復(fù)制類型的系統(tǒng)，即 5 個副本中部分是實時同步，其他副本可以采用鏈式復(fù)制的方式，或者 paxos 多數(shù)原則的方式，實現(xiàn)異步復(fù)制。異步復(fù)制的副本可以作為快照讀取的副本和 OLAP 的副本。
3.2 使用 CAP 理論指導分布式系統(tǒng)設(shè)計
復(fù)制技術(shù)是產(chǎn)生一致性問題的根源。由此帶來了分布式系統(tǒng)設(shè)計的第二個原則。
對于 Internet 這樣的全球規(guī)模的分布式系統(tǒng)，一直以來討論最多的是 AP 和 CP 系統(tǒng)。
CP 系統(tǒng)是犧牲可用性的系統(tǒng)。復(fù)制同步的協(xié)議一般使用嚴格的法定數(shù)協(xié)議 (paxos, raft, zab) 或者 2PC 協(xié)議。 CP 類型的系統(tǒng)有 MongoDB ， HBase ， Zookeeper 等。
AP 系統(tǒng)是犧牲一致性的系統(tǒng)。復(fù)制同步的協(xié)議一般使用非嚴格的法定數(shù)協(xié)議。 AP 類型的系統(tǒng)有 Couch DB ， Cassandra ， Amazon Dynamo 等。
那么有沒有 CA 系統(tǒng)？如何實現(xiàn) CA 系統(tǒng)？本文將嘗試解答這個問題。
4 重新理解 CAP
4.1 CAP 三者并不對等： P 是基礎(chǔ)， CA 之間 tradeoff
在全球廣域地理分布環(huán)境下（全球規(guī)模的分布式系統(tǒng)），網(wǎng)絡(luò)分區(qū)是一個自然的事實，甚至有人認為是必然的。
在這樣的情況下，有兩種聲音：
-
因為分區(qū)是必然的，系統(tǒng)設(shè)計時，只能實現(xiàn) AP 和 CP 系統(tǒng)， CA 系統(tǒng)是不可能的。
-
從技術(shù)上來說，分區(qū)確實會出現(xiàn)，但從效果來說，或者從概率來說，分區(qū)很少出現(xiàn)，可以認為系統(tǒng)不會發(fā)生分區(qū)。由于分區(qū)很少發(fā)生，那么在系統(tǒng)不存在分區(qū)的情況下沒什么理由犧牲 C 或 A 。
從更廣闊的分布式計算理論背景下審視 CAP 理論，可以發(fā)現(xiàn) C ， A ， P 三者并不對等。
CAP 之父在《 Spanner ，真時， CAP 理論》一文中寫道：如果說 Spanner 真有什么特別之處，那就是谷歌的廣域網(wǎng)。 Google 通過建立私有網(wǎng)絡(luò)以及強大的網(wǎng)絡(luò)工程能力來保證 P ，在多年運營改進的基礎(chǔ)上，在生產(chǎn)環(huán)境中可以最大程度的減少分區(qū)發(fā)生，從而實現(xiàn)高可用性。
從 Google 的經(jīng)驗中可以得到的結(jié)論是，一直以來我們可能被 CAP 理論蒙蔽了雙眼， CAP 三者之間并不對稱， C 和 A 不是 P 的原因啊（ P 不能和 CA trade-off ， CP 和 AP 中不存在 tradeoff ， tradeoff 在 CA 之間）。提高一個系統(tǒng)的抗毀能力，或者說提高 P （分區(qū)容忍能力）是通過提高基礎(chǔ)設(shè)施的穩(wěn)定性來獲得的，而不是通過降低 C 和 A 來獲得的。也就說犧牲 C 和 A 也不能提高 P 。
還有一種說法是，放棄 C 不是為了獲得 A ，而是為了低延遲（延遲不也是可用性的內(nèi)涵嗎？我這里有疑問）。 PNUTS 為了降低 WAN 上的消息事務(wù)的延遲（幾百毫秒，對于像亞馬遜和雅虎這樣的企業(yè)需要實施的許多 Web 應(yīng)用程序來說，成本太高），采用放棄一致性的做法。
而 CA 是系統(tǒng)的剛性強需求，但是 CA 兩者也不對等。系統(tǒng)無論如何要保證一致性（無論事先還是事后，這是系統(tǒng)設(shè)計的最大不變性約束，后文會詳述），在這個前提下，可以談?wù)効捎眯缘某潭取?Google 的 Spanner 就是這樣的思路。
總結(jié)： P 是一個自然的事實， CA 是強需求。三者并不對等。
補充：文章寫完之后，看到最新出版的文章《分布式數(shù)據(jù)庫中一致性與可用性的關(guān)系》，值得一讀。
4.2 保證不發(fā)生分區(qū)， CA 也不容易兼得
在分布式系統(tǒng)中，安全性，活性是本質(zhì)需求，并且廣泛的研究結(jié)果是分布式系統(tǒng)中一直存在一個廣泛意義的 trade-off ：在不可靠的分布式系統(tǒng)中無法同時實現(xiàn)安全性和活性。分布式系統(tǒng)的設(shè)計中充滿了安全性和活性的 trade-off ， FLA 著名的論文《 Impossibility of Distributed Consensus withOne Faulty process 》就是說我們不可能設(shè)計一個算法既可以絕對保證一致性（安全性）又無需時間等待的實現(xiàn)一致性（活性）。
CAP 就是這個 trade-off 的的集中體現(xiàn)。分別對應(yīng)于 :
-
Safety: 非正式的說，一個算法沒有任何壞的事情發(fā)生，那么該算法就是安全的。 CAP 中的 C 就是典型的 safety 屬性：所有對客戶的響應(yīng)都是正確的。
-
Liveness: 相反，一個算法最終有有一些好的事情發(fā)生，那么該算法就是活性的。 CAP 中的 A 就是典型的 liveness 屬性：所有的客戶最終都會收到回應(yīng)。
FLA 中的故障是指：
Unreliable: 有很多種方式可以讓一個系統(tǒng)不可靠， CAP 中的 P ，以及其他故障：系統(tǒng)崩潰，消息丟失，惡意攻擊，拜占庭故障等。
所以， CAP 理論可以說是 FLA 不可能性的不同表達方式。 P 只是 Unreliable 的一種極端形式而已。在 Google 的 Chubby 文章中，指出 paxos 協(xié)議維護系統(tǒng)的 safety ，引入時鐘來保證 liveness ，由此克服 FLA 的不可能性。實際上，基本的 Paxos 協(xié)議可以保證值一旦被選出后就一定不會改變，但不能保證一定會選出值來。換句話說，這個投票算法不一定收斂。所以在系統(tǒng)設(shè)計時， paxos 算法的使用是有條件的。
在數(shù)據(jù)庫領(lǐng)域， CAP 也正是 ACID 和 BASE 長期博弈 (tradeoff) 的結(jié)果。 ACID 伴隨數(shù)據(jù)庫的誕生定義了系統(tǒng)基本設(shè)計思路，所謂先入為主。 2000 年左右，隨著互聯(lián)網(wǎng)的發(fā)展，高可用的話題被擺上桌面，所以提出了 BASE 。從此 C 和 A 的取舍消長此起彼伏，其結(jié)晶就是 CAP 理論。
從 ACID 和 BASE 來說， ACID 是為了保證一致性而誕生，因而側(cè)重一致性； BASE 是為了高可用系統(tǒng)的設(shè)計而誕生，因而側(cè)重可用性。在分解 C 和 A 的情況時，肯定要涉及 P ，所以 CAP 理論統(tǒng)一了這一切。如果非要說酸堿，或者說酸堿平衡，那就是平衡于 CAP 理論。
CAP 并不與 ACID 中的 A （原子性）沖突，值得討論的是 ACID 中的 C （一致性）和 I （隔離性）。 ACID 的 C 指的是事務(wù)不能破壞任何數(shù)據(jù)庫規(guī)則，如鍵的唯一性。與之相比， CAP 的 C 僅指單一副本這個意義上的一致性，因此只是 ACID 一致性約束的一個嚴格的子集。如果系統(tǒng)要求 ACID 中的 I （隔離性），那么它在分區(qū)期間最多可以在分區(qū)一側(cè)維持操作。事務(wù)的可串行性（ serializability ）要求全局的通信，因此在分區(qū)的情況下不能成立。
C 與 A 之間的取舍可以在同一系統(tǒng)內(nèi)以非常細小的粒度反復(fù)發(fā)生，而每一次的決策可能因為具體的操作，乃至因為牽涉到特定的數(shù)據(jù)或用戶而有所不同。我們在分布式系統(tǒng)設(shè)計的兩大原則中討論過保持一致性的手段：同步復(fù)制和異步復(fù)制，結(jié)合復(fù)制協(xié)議的各種模式，請參考下表。例如簡單滿足了 C ，但延遲升高了，吞吐量下來了，還有什么可用性？我覺得延遲是包含在可用性的范圍內(nèi)的，不可用就是延遲的極大極限值。還有文章就只討論一致性，可用性和性能問題（比如阿里何登成的《數(shù)據(jù)一致性 - 分區(qū)可用性 - 性能 —— 多副本強同步數(shù)據(jù)庫系統(tǒng)實現(xiàn)之我見》），說明在不考慮分區(qū)的情況下， CA 問題依然是系統(tǒng)設(shè)計的難點。
重新審視本文的時候，恰好看到一個新的理論 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）
可用性并不是簡單的網(wǎng)絡(luò)連通，服務(wù)可以訪問，數(shù)據(jù)可以讀取就是可用性，對于互聯(lián)網(wǎng)業(yè)務(wù)，可用性是完整的用戶體驗，甚至會延伸到用戶現(xiàn)實生活中（補償）。有的系統(tǒng)必須容忍大規(guī)�？煽糠植际较到y(tǒng)中的數(shù)據(jù)不一致，其中原因就是為了在高并發(fā)條件下提高讀寫性能。
必須容忍大規(guī)模可靠分布式系統(tǒng)中的數(shù)據(jù)不一致，有兩個原因：在高并發(fā)條件下提高讀寫性能， 并要區(qū)分物理上導致的不一致和協(xié)議規(guī)定的不一致：
-
節(jié)點已經(jīng)宕機，副本無法訪問（物理）
-
法定數(shù)模型會使部分系統(tǒng)不可用的分區(qū)情況，即使節(jié)點已啟動并運行（ paxos 協(xié)議）
-
網(wǎng)絡(luò)斷開，節(jié)點孤立（物理）
所以，保證不發(fā)生分區(qū)， CA 也不是免費午餐： 盡管保證了網(wǎng)絡(luò)可靠性，盡量不發(fā)生分區(qū)，同時獲得 CA 也不是一件簡單的事情。
CA 系統(tǒng)才是真正的難點。
宣稱是 CA 系統(tǒng)的，目前有兩家：一家是 Google 的 Spanner ，一家是 Alibaba 的 OceanBase 。
4.3 發(fā)生分區(qū)時，也不要隨意犧牲 CA
雖然架構(gòu)師仍然需要在分區(qū)的前提下對數(shù)據(jù)一致性和可用性做取舍，但具體如何處理分區(qū)和恢復(fù)一致性，這里面有不計其數(shù)的變通方案和靈活度。
當發(fā)生分區(qū)時，系統(tǒng)設(shè)計人員不應(yīng)該盲目地犧牲一致性或可用性。 當分區(qū)存在或可感知其影響的情況下，就要預(yù)備一種策略去探知分區(qū)并顯式處理其影響。這樣的策略應(yīng)分為三個步驟：探知分區(qū)發(fā)生，進入顯式的分區(qū)模式以限制某些操作，啟動恢復(fù)過程以恢復(fù)數(shù)據(jù)一致性并補償分區(qū)期間發(fā)生的錯誤。
這一切都需要在系統(tǒng)設(shè)計之初考慮到，并在測試時模擬各種故障保證覆蓋到你的測試點。
構(gòu)建高度穩(wěn)健的基礎(chǔ)設(shè)施永遠是第一要務(wù)，所以我不認為網(wǎng)絡(luò)分區(qū)與 CA 屬性是對等的。
5 分解，分解，分解
分解 CAP ： “三選二”的公式一直存在著誤導性，它會過分簡單化各性質(zhì)之間的相互關(guān)系。現(xiàn)在我們有必要辨析其中的細節(jié)。
CAP 三種性質(zhì)都可以在程度上衡量，并不是非黑即白的有或無�？捎眯燥@然是在 0% 到 100% 之間連續(xù)變化的，一致性分很多級別，連分區(qū)也可以細分為不同含義，如系統(tǒng)內(nèi)的不同部分對于是否存在分區(qū)可以有不一樣的認知。
5.1 P 分解：延遲？故障？分區(qū)？
if you're working with distributed systems,you should always be thinking about failure.
如果你正在使用分布式系統(tǒng)，你應(yīng)該永遠考慮失敗。
故障，延遲，分區(qū)，是一組非常相關(guān)的概念。
在通信網(wǎng)絡(luò)中，最重要的兩個屬性是帶寬和延遲。延遲也往往取決于鏈路轉(zhuǎn)發(fā)節(jié)點的效率。由于延遲的存在，系統(tǒng)很難就全局狀態(tài)達成一致。當鏈路發(fā)生故障，就會導致網(wǎng)絡(luò)分區(qū)。由于延遲的特性，就算鏈路沒有發(fā)生故障，系統(tǒng)也可能判斷發(fā)生了分區(qū)。
對 P 的分解需要從網(wǎng)絡(luò)開始。網(wǎng)絡(luò)包含了基礎(chǔ)設(shè)施，光速限制以及軟件配置與升級等。 Google 通過建設(shè)自己廣域網(wǎng)獲得高可靠的基礎(chǔ)設(shè)施支撐，對于 Google Spanner 的 CA 系統(tǒng)， CAP 之父曾總結(jié)說網(wǎng)絡(luò)才是根本。
而光速限制則告誡我們：一致性是一個結(jié)果，不是實時的狀態(tài)。由于光速無法超越，則延遲必然存在（下圖顯示從加拿大到荷蘭的網(wǎng)絡(luò)延遲在 150 毫秒左右）。延遲的存在讓一個節(jié)點無法獲得對方節(jié)點的實時狀態(tài)。
https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html
由于延遲的存在， 有人說，即時性和全球性的一致性是不可能的。宇宙根本不允許它。我以前從事分布式系統(tǒng)研發(fā)時，帶我的博士總是告誡說，系統(tǒng)設(shè)計不要超越時空的限制。
軟件配置與升級則體現(xiàn)基礎(chǔ)設(shè)施搭建工程能力和運維能力。 Google 調(diào)查了 Spanner 事故的內(nèi)部原因分類顯示，網(wǎng)絡(luò)類別的事故是由網(wǎng)絡(luò)分區(qū)和網(wǎng)絡(luò)配置問題造成的。
Michael Stonebraker 在《 Errors in Database Systems, Eventual Consistency, and the CAP Theorem 》一文中通過對故障進行分解，給出進入 CAP 討論范圍的部分故障列表：
1 ）應(yīng)用程序錯誤。應(yīng)用程序執(zhí)行一個或多個不正確的更新。一般來說，這不是幾分鐘到幾個小時之后才發(fā)現(xiàn)的。必須將數(shù)據(jù)庫備份到違規(guī)事務(wù)之前的一個時間點，然后重做后續(xù)活動。
2 ）可重復(fù)的 DBMS 錯誤。 DBMS 在處理節(jié)點上崩潰。在具有副本的處理節(jié)點上執(zhí)行相同的事務(wù)將導致備份崩潰。這些錯誤被稱為 Bohr 錯誤。
3 ）不可重復(fù)的 DBMS 錯誤。數(shù)據(jù)庫崩潰了，但是一個副本很可能沒問題。這些通常是由處理異步操作的奇怪角落造成的，并且被稱為 Heisenbugs 。
4 ）操作系統(tǒng)錯誤。操作系統(tǒng)崩潰在一個節(jié)點，產(chǎn)生“藍屏死亡”。
5 ）本地集群中的硬件故障。這些包括內(nèi)存故障，磁盤故障等。通常，這些會導致操作系統(tǒng)或 DBMS 的“緊急停止”。但是，有些時候這些失敗就像 Heisenbugs 一樣。
6 ）本地集群中的網(wǎng)絡(luò)分區(qū)。 LAN 失敗，節(jié)點不能再相互通信。
7 ）災(zāi)難。地方數(shù)據(jù)中心被洪水，地震等等所消滅。群集不再存在。
8 ） WAN 中的網(wǎng)絡(luò)故障將集群連接在一起。 WAN 失敗，群集不能再相互通信。
Michael Stonebraker 總結(jié)認為錯誤 1,2 和 7 是 CAP 定理根本不適用的情況的示例， 3,4,5 和 6 是本地故障，錯誤 8 是 WAN 網(wǎng)絡(luò)中的一個分區(qū)，但是是非常罕見的。所以不要盲目的 follow CAP 理論，輕易的放棄一致性。分解故障，進行針對性的設(shè)計。
PACELC 理論本質(zhì)就是對分區(qū)進行分解：發(fā)生分區(qū)時，在 CA 之間取舍；沒有發(fā)生分區(qū)時，在 C 和延遲之間取舍。（我們系統(tǒng)設(shè)計的大多數(shù)情況就是在沒有發(fā)生分區(qū)的時候）
如何探知分區(qū)？這涉及到分布式系統(tǒng)中常見且重要的話題：故障檢測。故障檢測需要從從分布式系統(tǒng)的定義談起：節(jié)點和連線的模型。在分布式系統(tǒng)中，通過消息通信建立的連接，連接兩端的節(jié)點在任意時刻，以及節(jié)點中運行的進程，隨時都可能發(fā)生故障。
在分布式系統(tǒng)中，節(jié)點故障判斷必然依賴超時（時限設(shè)置），在一定的超時時間內(nèi)，消息可能延遲，也可能鏈路故障造成的節(jié)點不可達，在這樣的情況下，如何判斷節(jié)點故障？常見的策略是間隔一段時間重新嘗試連接，降低誤判的風險，這樣就增加了系統(tǒng)的延遲時間，也就是降低了可用性。遠端節(jié)點無法準確的判斷存活還是故障，就無法準確的判斷分區(qū)是否真的發(fā)生。所以 CAP 之父在其著名的文章《 CAP Twelve Years Later: How the "Rules" Have Changed 》中提出了分布式設(shè)計的核心問題：分區(qū)兩側(cè)是否能夠在無通信的情況下繼續(xù)其操作？
下面舉一個復(fù)雜的例子。在分布式事務(wù)這樣的場景中，涉及的消息和操作很多。每一條消息和操作都有可能故障，如下圖所示。這就要求我們在程序的設(shè)計和實現(xiàn)過程中，針對大量的異常和故障編寫代碼。這就是故障檢測之后的故障處理。
故障處理如何做？有以下模型可以考慮。
Fail-Fast ：從字面含義看就是“快速失敗”，盡可能的發(fā)現(xiàn)系統(tǒng)中的錯誤，使系統(tǒng)能夠按照事先設(shè)定好的錯誤的流程執(zhí)行，對應(yīng)的方式是“ fault-tolerant （容錯）”。只發(fā)起一次調(diào)用，失敗立即報錯 , 通常用于非冪等性的寫操作。 如果有機器正在重啟，可能會出現(xiàn)調(diào)用失敗 。
Fail-Over ：含義為“失效轉(zhuǎn)移”，是一種備份操作模式，當主要組件異常時，其功能轉(zhuǎn)移到備份組件。其要點在于有主有備，且主故障時備可啟用，并設(shè)置為主。如 Mysql 的雙 Master 模式，當正在使用的 Master 出現(xiàn)故障時，可以拿備 Master 做主使用。阿里同學認為這里可以指失敗自動切換。當出現(xiàn)失敗，重試其它服務(wù)器，通常用于讀操作（推薦使用）。 重試會帶來更長延遲。
Fail-Safe ：含義為“失效安全”，即使在故障的情況下也不會造成傷害或者盡量減少傷害。維基百科上一個形象的例子是紅綠燈的“沖突監(jiān)測模塊”當監(jiān)測到錯誤或者沖突的信號時會將十字路口的紅綠燈變?yōu)殚W爍錯誤模式，而不是全部顯示為綠燈。有時候來指代“自動功能降級” (Auto-Degrade) 。阿里的同學認為失敗安全，出現(xiàn)異常時，直接忽略，通常用于寫入審計日志等操作。調(diào)用信息丟失 可用于生產(chǎn)環(huán)境 Monitor 。
Fail-Back ： Fail-over 之后的自動恢復(fù)，在簇網(wǎng)絡(luò)系統(tǒng)（有兩臺或多臺服務(wù)器互聯(lián)的網(wǎng)絡(luò)）中，由于要某臺服務(wù)器進行維修，需要網(wǎng)絡(luò)資源和服務(wù)暫時重定向到備用系統(tǒng)。在此之后將網(wǎng)絡(luò)資源和服務(wù)器恢復(fù)為由原始主機提供的過程，稱為自動恢復(fù)。阿里的同學認為失敗自動恢復(fù)，后臺記錄失敗請求，定時重發(fā)。通常用于消息通知操作 不可靠，重啟丟失�？捎糜谏a(chǎn)環(huán)境 Registry 。
Forking 并行調(diào)用多個服務(wù)器，只要一個成功即返回，通常用于實時性要求較高的讀操作。 需要浪費更多服務(wù)資源 。
Broadcast 廣播調(diào)用，所有提供逐個調(diào)用，任意一臺報錯則報錯。通常用于更新提供方本地狀態(tài)速度慢，任意一臺報錯則報錯。
上述故障模型是從系統(tǒng)設(shè)計的角度出發(fā)的，根據(jù)不同的需要設(shè)計不同故障處理方案。現(xiàn)在看來，系統(tǒng)的外延已經(jīng)擴大。系統(tǒng)的容錯性，或者分區(qū)容錯能力，不能僅僅使用事先和事中的方案解決，系統(tǒng)的容錯性還包括事后處理。
總之，分區(qū)發(fā)現(xiàn)的要義是工程問題，即如何構(gòu)建和加強基礎(chǔ)設(shè)置的穩(wěn)定性，如何設(shè)計出準確高效的故障檢測算法。
5.2 C 分解：服務(wù)器端與客戶端
曾經(jīng)，透明性也是系統(tǒng)的一個要求和屬性（透明性：對于系統(tǒng)的用戶來說，只能感受到一個系統(tǒng)而不是多個協(xié)作系統(tǒng)）。曾經(jīng)，系統(tǒng)的一致性模型只有一個：當進行更新時，所有觀察者都會看到更新。曾經(jīng)，我們的系統(tǒng)可以用 “ 鄰國相望，雞犬之聲相聞，民至老死不相往來 ” 來描述，不是全球部署，不需要復(fù)制技術(shù)來保證高可用性，也就不會有一致性問題。然而，隨著互聯(lián)網(wǎng)的發(fā)展，可用性被認為是互聯(lián)網(wǎng)系統(tǒng)中最重要的屬性，特別是 CAP 理論的提出，使得我們不得不重新審視當初的一些系統(tǒng)原則。我們必須打破系統(tǒng)透明性，把其中的內(nèi)部細節(jié)暴露出來，同時也思考我們到底需要什么？并且需要付出什么？
關(guān)于一致性的討論主要分為三個方面：這個分法也是性能與一致性之間的平衡。
強一致性
Spanner
PNUTS: Yahoo!’s Hosted Data ServingPlatform
弱一致性
Dynamo: Amazon’s Highly Available Key-valueStore
CAP 理論：一致性與性能之間的 trade-off ，目前關(guān)于這方面的研究有很多。比如：
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
分解一致性的目的是，在系統(tǒng)設(shè)計時，不要盲目的談 CAP 的三選二，而是通過分解不同業(yè)務(wù)場景和業(yè)務(wù)操作，使用合適的一致性模型。如上圖所示，有大量操作是屬于一致性的灰色區(qū)域。系統(tǒng)的設(shè)計不要以 CAP 為中心，而是以業(yè)務(wù)為中心。例如，用戶名和密碼必須強一致，而用戶的屬性信息可以是弱一致性的。
一致性模型本質(zhì)上是進程和數(shù)據(jù)存儲之間關(guān)于一致性所達成的約定（ contract ）。
首先，我們從客戶端的角度，看看有哪些一致性類型。
強一致性：更新完成后，所有的后續(xù)讀操作都會返回更新值。
弱一致性：系統(tǒng)并不保證后續(xù)讀操作獲得更新值的時間點。
最終一致性：如果沒有更新，最終系統(tǒng)會返回最后更新的值。換句話說，如果系統(tǒng)在持續(xù)更新，則永遠無法達到一致性。
因果一致性：和寫進程具有因果關(guān)系的進程將會讀取到更新的數(shù)據(jù)，寫進程保證取代上次更更新。
讀己所寫一致性：進程永遠讀取自己上次更新寫入的最新值，而不可能讀取到任何歷史數(shù)據(jù)。這是傳統(tǒng)操作系統(tǒng)默認的一致性行為。
會話一致性：在同一個會話內(nèi)，系統(tǒng)保證讀己所寫的一致性。
單調(diào)讀一致性：進程在讀取到系統(tǒng)的一個特定值，則系統(tǒng)永遠不會再返回該值以前的任何值。
單調(diào)寫一致性：系統(tǒng)保證同一個進程寫入操作的串行化。對于多副本系統(tǒng)來說，保證寫順序的一致性（串行化），是很重要的。
然后我們看下服務(wù)器端。
強一致性：
為讀而優(yōu)化：
為寫而優(yōu)化：
還有一種一致性模型是 PNUTS 中中提出的，僅保證“時間線一致性”來放松一致性，其中副本可能不一致，但保證在所有副本上以相同的順序應(yīng)用更新。
Azure Cosmos DB 中也提出了幾種支持的一致性模型，并宣稱可選的支持幾種不同的一致性模型。
5.3 A 分解：出來混，遲早要還的
可用性首先體現(xiàn)在容錯。容錯不是系統(tǒng)能夠在各種故障情況下都能工作，容錯是系統(tǒng)發(fā)生故障時，系統(tǒng)能夠以明確的預(yù)定方式運行。下面列出一下可用性指標。
| 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 |
在系統(tǒng)設(shè)計之初，要考慮系統(tǒng)提供什么程度的可用性，并采用相應(yīng)的一致性模型�？捎眯泽w現(xiàn)在用戶體驗。在現(xiàn)實生活中，更高的可用性意味著更高的收入。
另外，因為分區(qū)引起的可用性問題可以通過事后補償來獲得。
C = A + compensation
總結(jié)起來， C>A>P ，這里的大于號，不是包含關(guān)系，也不是優(yōu)先級關(guān)系，而是盡力保證 P 是為了 CA ，為了保證 C, 需要犧牲一點點 A �；蛘咭部梢哉f A> C>P ，為了保證可用性，需要犧牲暫時的不一致性。
這里有人可能有疑問，在某一個場景下，我選擇了可用性，放棄了一致性�。磕俏艺f，你一定有補償措施。也就是說無論事先還是事后，你總要保證一致性。
當代 CAP 實踐應(yīng)將目標定為針對具體的應(yīng)用，在合理范圍內(nèi)最大化數(shù)據(jù)一致性和可用性的“合力”。這樣的思路延伸為如何規(guī)劃分區(qū)期間的操作和分區(qū)之后的恢復(fù)，從而啟發(fā)設(shè)計師加深對 CAP 的認識，突破過去由于 CAP 理論的表述而產(chǎn)生的思維局限。
當發(fā)生分區(qū)時，如何設(shè)計可用性？以下幾個方面供思考和探討。
明確系統(tǒng)的不變性約束：通過仔細分析和管理在分區(qū)期間系統(tǒng)的不變性約束來優(yōu)化 CA 屬性。我認為系統(tǒng)唯一的不變性約束就是數(shù)據(jù)的一致性約束。當然你也可以設(shè)計 C 和 A 都是系統(tǒng)的不變性約束，然后用 C=A+compensation 來保證一致性，這樣就是 CA 系統(tǒng)。就一致性不變性約束來說，唯一的是不變性，有兩種：系統(tǒng)內(nèi)加鎖訪問的對象和現(xiàn)實生活設(shè)置的閾值。例如航空公司，不變性約束必須至少與乘客座位一樣多。如果乘客太多，有人會失去座位，理想的客戶服務(wù)會以某種方式補償這些乘客。在飛機航班“超售”的情況下，可以把乘客登機看作是對之前售票情況的分區(qū)恢復(fù)，必須恢復(fù)“座位數(shù)不少于乘客數(shù)”這項不變性約束。那么當乘客太多的時候，有些乘客將失去座位，客服需要補償他們。航空公司的例子就是系統(tǒng)內(nèi)需要加鎖訪問的對象成為不變性約束。而像 ATM 機最后的余額不能低于零的例子就是現(xiàn)實生活設(shè)置的閾值，這也是不能違背的不變性約束。 ATM 機的例子也可以引入政府或者操作者的背書機制：比如引入操作者的信用，如果操作者具有超過閾值的信用，就可以繼續(xù)操作。還有一種補償方式法律的形式，透支的金額由用戶補償，多扣的手續(xù)費退回給客戶（和信用綁定：既然一致性已經(jīng)打破系統(tǒng)的透明性，應(yīng)用已經(jīng)參與進來，那就干脆引入社會信用吧）�，F(xiàn)在很多系統(tǒng)設(shè)計時沒有梳理清楚系統(tǒng)的所有不變性約束，并且對其影響也不明確，大多選擇了一致性，犧牲一點可用性。
設(shè)計補償機制：管理分區(qū)就是管理補償。根據(jù) C=A+compensation 的思考，所謂不變性約束，前提是無法補償，如果可以補償，一切都是可變性約束。一般的補償分為內(nèi)部補償和外部補償。以重復(fù)的訂單為例（還有一種情況是刪除的數(shù)據(jù)重新出現(xiàn)），系統(tǒng)可以將合并后的訂單中取消一個重復(fù)的訂單，并不通知用戶，這是內(nèi)部補償。如果這次錯誤產(chǎn)生了外在影響，補償策略可以是自動生成一封電子郵件，向顧客解釋系統(tǒng)意外將訂單執(zhí)行了兩次，現(xiàn)在錯誤已經(jīng)被糾正，附上一張優(yōu)惠券下次可以用。但 C=A+compensation 并沒有打破數(shù)據(jù)一致性約束，只是讓用戶在分區(qū)的情況下繼續(xù)保持可用性。
設(shè)計數(shù)據(jù)不變性：補償依賴完善的日志，我在這里借用《 How to beat the CAP theorem 》的數(shù)據(jù)不變性原理，把日志稱為數(shù)據(jù)不變性。 這里的日志是廣泛意義的日志，不僅包含數(shù)據(jù)的所有歷史版本，還包括分區(qū)歷史（時間，地點，人物，加上這些，世界上不存在重復(fù)的數(shù)據(jù)主鍵）和分區(qū)合并歷史，以及節(jié)點成員關(guān)系等。是系統(tǒng)重構(gòu)？還是節(jié)點啟動加入系統(tǒng)？還是系統(tǒng)發(fā)生了分區(qū)？這些都要記錄下來。這樣當節(jié)點加入系統(tǒng)，應(yīng)該能夠找到自己曾經(jīng)所在的父分區(qū)。我認為數(shù)據(jù)不變性 + 補償機制可以打敗 CAP 定理。 如果分區(qū)之后要保證可用性，用于用戶繼續(xù)操作數(shù)據(jù)。那么在分區(qū)合并之后，繼續(xù)保持數(shù)據(jù)的分區(qū)狀態(tài)也是可以的（相當于多了一條分支數(shù)據(jù)）�？梢宰寯�(shù)據(jù)的元數(shù)據(jù)中記錄分區(qū)信息，甚至記錄所有分區(qū)歷史。分區(qū)模式操作的跟蹤和限制確保知道哪些不變量可能被違反，這又使得設(shè)計者能夠為每個這樣的不變量創(chuàng)建恢復(fù)策略。這里和不變性原理是一致的：設(shè)計利用的基本原則是“數(shù)據(jù)本質(zhì)上是不可變的”。這是因為數(shù)據(jù)總是與一個時間，人物，地點（分區(qū)）相關(guān)聯(lián)，你可以將數(shù)據(jù)視為當時的事實。所以當你的銀行帳戶的余額可能會從時間 T 到時間 T+ 1 從 10 變化到 20 ，以及操作的分區(qū)，這些數(shù)據(jù)，時間，人物，地點永遠是真實的。有了這些數(shù)據(jù)，我們可以任何的補償操作。上面訂單重復(fù)的例子，假如沒有完善的歷史記錄，就只好靠顧客親自去發(fā)現(xiàn)錯誤了。
應(yīng)用分解：有兩個層面。第一是分解業(yè)務(wù)細節(jié)，有些時候這些細節(jié)也對應(yīng)于系統(tǒng)調(diào)用或者 API 。例如 ATM 的基本操作是存款、取款、查看余額。在分區(qū)發(fā)生時，存款和查看是可以進行的，取款可以設(shè)置取款限額或者不設(shè)限額后續(xù)補償。第二是應(yīng)用程序處理補償。不一致是否可以接受取決于客戶端應(yīng)用程序。在所有情況下，開發(fā)人員需要注意，存儲系統(tǒng)提供一致性保證，并在開發(fā)應(yīng)用程序時需要考慮。最終的一致性模型有一些實際的改進，例如會話級一致性和單調(diào)讀取，為開發(fā)人員提供更好的工具。許多時候，應(yīng)用程序能夠處理存儲系統(tǒng)的最終一致性保證，沒有任何問題。從可用性的角度來看，阿里 OceanBase 的觀點可見一斑：數(shù)據(jù)庫一定是時延很低的，時延高就會導致應(yīng)用出問題，實際上這個問題要花另外一個篇幅去講，那就是應(yīng)用程序必須要去適應(yīng)這種時延高的數(shù)據(jù)庫系統(tǒng)。當然用了 batching 和 pipeling 技術(shù)，本質(zhì)上都是通用的工程優(yōu)化，讓跨網(wǎng)絡(luò)多副本同步變得高效，但是時延一定會增加。
6 真正的難題
分布式并發(fā)讀寫事務(wù)。如果下圖所示，進程 A 和 B 是地理上分布的兩個進程， A 進程對系統(tǒng)發(fā)起寫操作， B 進程同時并發(fā)的讀取。
首先第一個難題，是否允許任意節(jié)點并發(fā)可寫。在 Google 的 F1 ，螞蟻的 OceanBase ，亞馬遜的 Aurora 中，都是指定一個寫節(jié)點或者更新節(jié)點的（據(jù)說 OB 升級 1.0 后，所有節(jié)點都是同等地位的）。
第二個難題，是否支持讀寫并發(fā)。這里涉及到讀寫一致性的問題。比如上圖，當用戶 A 在寫入系統(tǒng)的時候，用戶 B 的讀取情況是什么樣子的？是讀取數(shù)據(jù)的上一個快照，還是讀取 A 寫入的最新數(shù)據(jù)？用戶 A 和用戶 B 在讀取的過程中如何加鎖？特別跨越廣域網(wǎng)的不同的數(shù)據(jù)中心的時候。這里 tricky 的地方在于是否要對整個數(shù)據(jù)加讀寫鎖。目前我看 Google 的主要方法是目前 A 進程在寫的時候采用多版本數(shù)據(jù)存儲，并保證分布式事務(wù)。 B 進程可以實現(xiàn)無鎖的快照讀取�；谥行墓�(jié)點的機制，如果讀寫沖突或者寫寫沖突，會被鎖機制拒絕，用戶操作失敗。
這個問題還涉及到分布式事務(wù)的隔離性問題。傳統(tǒng)數(shù)據(jù)庫 ANSISQL 標準定義了四個 “ 隔離等級 ” ：
-
未提交讀：一個事務(wù)可以讀任何已提交或未提交的數(shù)據(jù)。這可以通過“讀操作不需要請求任何鎖”來實現(xiàn)。
-
已提交讀：一個事務(wù)可以讀任何已提交的數(shù)據(jù)。對于同一個對象的重復(fù)讀可能導致讀到不同版本的數(shù)據(jù)。實現(xiàn)方式是，讀數(shù)據(jù)前必須首先獲得一個讀操作鎖，一旦數(shù)據(jù)讀取之后該鎖被立即釋放。
-
可重復(fù)讀：一個事務(wù)只能讀取一個已提交數(shù)據(jù)的一個版本；一旦該事務(wù)讀取了一個對象，那么，它將只能讀取該對象的同一個版本。實現(xiàn)方式是，事務(wù)在請求讀數(shù)據(jù)之前必須獲得一個鎖，并且保持該鎖直到事務(wù)結(jié)束。
-
可串行化：保證完全的可串行化。
分布式數(shù)據(jù)庫如何滿足，是設(shè)計分布式系統(tǒng)的首要問題。嚴格說來，Google的實現(xiàn)應(yīng)該是一種可重復(fù)讀（這里還要存疑）。
第三個難題，元數(shù)據(jù)如何保存。用戶 A 或 B 在讀取或者寫入系統(tǒng)的時候，如何獲得數(shù)據(jù)的版本和時間戳？這在 OceanBase ， spanner/F1 ，以及 TiDB 中 PD 機制中略有涉及，但都不詳細。如果元數(shù)據(jù)在異地數(shù)據(jù)中心，獲得元數(shù)據(jù)將會有一個廣域網(wǎng)延遲到時間開銷。我認為 Google 的 truetime 是用了物理時間代替經(jīng)典的邏輯時鐘，并且作為副本的時間戳，也就是版本號，這樣基于 truetime 的精巧 API 設(shè)計，讓版本號和物理時間線性對齊，無需去查詢副本的元數(shù)據(jù)信息。相反的例子是 Google Chubby 提到的：在一個已經(jīng)初步成熟的復(fù)雜應(yīng)用程序的每次操作中引入版本號的開銷是非常大的。所以后來退一步求其次， Chubby 采用了僅僅在所有使用鎖的操作中引入版本號。
第四個難題，在讀寫事務(wù)期間，節(jié)點故障。注意，這里是指任意節(jié)點故障，包括一次事務(wù)中的 leader 節(jié)點，參與節(jié)點，以及用戶節(jié)點。特別是用戶所在的節(jié)點故障要求系統(tǒng)必須有加鎖租約等自恢復(fù)機制。
關(guān)于鎖的設(shè)計，在 CAP 的范圍內(nèi)，需要滿足三點：
-
鎖對象信息的要寫入多副本以應(yīng)對故障
-
不同對象的鎖信息需要分布化和負載均衡
-
鎖信息寫入持久化存儲系統(tǒng)
注意，這里鎖的概念和 Google Chubby 中鎖的概念是不同的。這里是一種粗粒度的鎖（ leader 選舉），其作者也不建議把 Chubby 應(yīng)用在細粒度鎖（事務(wù)更新）的場景中。這兩種鎖在 CAP 的范圍內(nèi)使用時值得非常細心的研究和討論，特別是在分布式數(shù)據(jù)庫領(lǐng)域內(nèi)。
第五個難題，嵌套事務(wù)或者鏈式事務(wù)。這是電子商務(wù)的基礎(chǔ)。下面以 Percolator 的實現(xiàn)說明這個問題。銀行轉(zhuǎn)賬， Bob 向 Joe 轉(zhuǎn)賬 7 元。該事務(wù)于 start timestamp =7 開始， commit timestamp=8 結(jié)束。具體過程如下：
1. 初始狀態(tài)下， Bob 的帳戶下有 10 （首先查詢 column write 獲取最新時間戳數(shù)據(jù) , 獲取到 [email protected], 然后從 column data 里面獲取時間戳為 5 的數(shù)據(jù)，即 $10 ）， Joe 的帳戶下有 2 。
2 、轉(zhuǎn)賬開始，使用 stattimestamp=7 作為當前事務(wù)的開始時間戳，將 Bob 選為本事務(wù)的 primary ，通過寫入 Column Lock 鎖定 Bob 的帳戶，同時將數(shù)據(jù) 7:$3 寫入到 Column,data 列。
3 、同樣的，使用 stat timestamp=7 ，鎖定 Joe 的帳戶，并將 Joe 改變后的余額寫入到 Column,data, 當前鎖作為 secondary 并存儲一個指向 primary 的引用（當失敗時，能夠快速定位到 primary 鎖，并根據(jù)其狀態(tài)異步清理）
4 、事務(wù)帶著當前時間戳 commit timestamp=8 進入 commit 階段：刪除 primary 所在的 lock ，并在 write 列中寫入從提交時間戳指向數(shù)據(jù)存儲的一個指針 commit_ts=>data @7 。至此，讀請求過來時將看到 Bob 的余額為 3 。
5 、依次在 secondary 項中寫入 write 并清理鎖，整個事務(wù)提交結(jié)束。在本例中，只有一個 secondary:Joe.
7 總結(jié)
本文的主要觀點是：
-
CAP 中的三個因素并不對等， P 是基礎(chǔ)， CA 之間需要 tradeoff 。系統(tǒng)設(shè)計不是三選二的取舍。
-
延遲作為可用性的指標和體現(xiàn)，系統(tǒng)設(shè)計通常需要在 C 和延遲之間 tradeoff 。
-
CAP 真正的 trade-off 在 CA 之間，系統(tǒng)設(shè)計需要細心分解 C 和 A ，不同的系統(tǒng)有不同的需求。本文在對 CAP 分解的基礎(chǔ)上，提供了系統(tǒng)設(shè)計的一些思考方法。未來系統(tǒng)的設(shè)計必然是要滿足多種一致性模型和多種可用性需求（例如微軟的 cosmos DB 聲稱支持多種一致性模型）。
-
針對分區(qū)設(shè)計數(shù)據(jù)不變性，記錄所有的分區(qū)歷史，這讓分區(qū)合并之后的 compensation 有據(jù)可依。借助社會和法律因素，一致性最終都是可以保證的。另外，如果像阿里日照的見解，可用性是一定時間延遲（可能是一天）之后返回響應(yīng)（在這期間實現(xiàn)服務(wù)切換），那么可用性也是可以保證的。
-
在第 3 點的基礎(chǔ)上，未來分布式系統(tǒng)需要從整體上考慮，即需要考慮 IT 基礎(chǔ)設(shè)施，也要考慮應(yīng)用的適應(yīng)和配合，以及人類社會中的法律和補償。
-
本文討論了在 CAP 范圍內(nèi)，分布式系統(tǒng)設(shè)計的一些難點。
注意本文的分區(qū)和數(shù)據(jù)庫的分片（分區(qū)）不是一個概念。
8 附錄
8.1 附錄 1 ：不變性如何打敗 CAP 定理？
以下翻譯自《 how to beat CAP 》。
CAP 定理仍然適用，所以你需要在可用性和一致性上做出選擇，這里的漂亮之處在于，一旦你權(quán)衡之后做出了選擇，你就做完了所有的事情。通常的那些因為 CAP 定理帶來的問題，都可以通過不可改變的數(shù)據(jù)和從原始數(shù)據(jù)中計算查詢來規(guī)避。
如果你選擇一致性而不是可用性，那么跟以前并沒有多大的區(qū)別，因為你放棄了可用性，所以一些時候你將無法讀取或者寫入數(shù)據(jù)。當然這只是針對對強一致性有要求的系統(tǒng)。
如果你選擇可用性而不是一致性，在這種情況下，系統(tǒng)可以達到最終一致性而且規(guī)避了所有最終一致性帶來的復(fù)雜問題。由于系統(tǒng)總是可用的，所以你總可以寫入新數(shù)據(jù)或者進行查詢。在出錯情況下，查詢可能返回的不是最近寫入的數(shù)據(jù)，但根據(jù)最終一致性，這個數(shù)據(jù)最終會一致，而查詢函數(shù)最終會把這個數(shù)據(jù)計算進去。
這里的關(guān)鍵在于數(shù)據(jù)是不可變的。不可變數(shù)據(jù)意味著這里沒有更新操作，所以不可能出現(xiàn)數(shù)據(jù)復(fù)制不同這種不一致的情況，也意味著不需要版本化的數(shù)據(jù)、矢量時鐘或者讀取修復(fù)。在一個查詢場景中，一個數(shù)據(jù)只有存在或者不存在兩種情況。這里只有數(shù)據(jù)和在數(shù)據(jù)之上的函數(shù)。這里沒有需要你為確保最終一致性額外做的事情，最終一致性也不會因此使你的系統(tǒng)變得復(fù)雜。
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
《數(shù)據(jù)一致性 - 分區(qū)可用性 - 性能 —— 多副本強同步數(shù)據(jù)庫系統(tǒng)實現(xiàn)之我見》
來自：http://mp.weixin.qq.com/s/gV7DqSgSkz_X56p2X_x_cQ
標簽： Google Mysql 安全 代碼 電子商務(wù) 電子郵件 服務(wù)器 服務(wù)器端 服務(wù)器恢復(fù) 服務(wù)器托管 谷歌 互聯(lián)網(wǎng) 互聯(lián)網(wǎng)的發(fā)展 互聯(lián)網(wǎng)公司 互聯(lián)網(wǎng)業(yè)務(wù) 數(shù)據(jù)庫
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
