一致性協(xié)議算法-2PC、3PC、Paxos、Raft、ZAB、NWR超詳細解析

背景

在常見的分布式系統(tǒng)中，總會發(fā)生諸如機器宕機或網(wǎng)絡(luò)異常（包括消息的延遲、丟失、重復(fù)、亂序，還有網(wǎng)絡(luò)分區(qū)）等情況。

一致性算法需要解決的問題就是如何在一個可能發(fā)生上述異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對某個數(shù)據(jù)的值達成一致，并且保證不論發(fā)生以上任何異常，都不會破壞整個系統(tǒng)的一致性。

CAP 定理

CAP 理論告訴我們，一個分布式系統(tǒng)不可能同時滿足一致性（C:Consistency)，可用性（A: Availability）和分區(qū)容錯性（P：Partition tolerance）這三個基本需求，最多只能同時滿足其中的2個。

Base 理論

BASE：全稱：Basically Available(基本可用)，Soft state（軟狀態(tài)）,和 Eventually consistent（最終一致性）。

Base 理論是對 CAP 中一致性和可用性權(quán)衡的結(jié)果，其來源于對大型互聯(lián)網(wǎng)分布式實踐的總結(jié)，是基于 CAP 定理逐步演化而來的。其核心思想是：既是無法做到強一致性（Strong consistency），但每個應(yīng)用都可以根據(jù)自身的業(yè)務(wù)特點，采用適當?shù)姆绞絹硎瓜到y(tǒng)達到最終一致性（Eventual consistency）。

解釋一下：什么是軟狀態(tài)呢？相對于原子性而言，要求多個節(jié)點的數(shù)據(jù)副本都是一致的，這是一種 “硬狀態(tài)”。軟狀態(tài)指的是：允許系統(tǒng)中的數(shù)據(jù)存在中間狀態(tài)，并認為該狀態(tài)不影響系統(tǒng)的整體可用性，即允許系統(tǒng)在多個不同節(jié)點的數(shù)據(jù)副本存在數(shù)據(jù)延時。

2PC

Two-Phase Commit，事務(wù)的提交過程分成了兩個階段來進行處理。

2PC 階段一

1.事務(wù)詢問

協(xié)調(diào)者向所有的參與者詢問，是否準備好了執(zhí)行事務(wù)，并開始等待各參與者的響應(yīng)。

1.執(zhí)行事務(wù)

各參與者節(jié)點執(zhí)行事務(wù)操作，并將 Undo 和 Redo 信息記入事務(wù)日志中

1.各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)

如果參與者成功執(zhí)行了事務(wù)操作，那么就反饋給協(xié)調(diào)者 Yes 響應(yīng)，表示事務(wù)可以執(zhí)行；如果參與者沒有成功執(zhí)行事務(wù)，就返回 No 給協(xié)調(diào)者，表示事務(wù)不可以執(zhí)行。

2PC 階段二

在階段二中，會根據(jù)階段一的投票結(jié)果執(zhí)行 2 種操作：執(zhí)行事務(wù)提交，中斷事務(wù)。

執(zhí)行事務(wù)提交步驟如下：

?發(fā)送提交請求：協(xié)調(diào)者向所有參與者發(fā)出 commit 請求。?事務(wù)提交：參與者收到 commit 請求后，會正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放整個事務(wù)執(zhí)行期間占用的事務(wù)資源。?反饋事務(wù)提交結(jié)果：參與者在完成事務(wù)提交之后，向協(xié)調(diào)者發(fā)送 Ack 信息。?協(xié)調(diào)者接收到所有參與者反饋的 Ack 信息后，完成事務(wù)。

中斷事務(wù)步驟如下：

?發(fā)送回滾請求：協(xié)調(diào)者向所有參與者發(fā)出 Rollback 請求。?事務(wù)回滾：參與者接收到 Rollback 請求后，會利用其在階段一種記錄的 Undo 信息來執(zhí)行事務(wù)回滾操作，并在完成回滾之后釋放在整個事務(wù)執(zhí)行期間占用的資源。?反饋事務(wù)回滾結(jié)果：參與者在完成事務(wù)回滾之后，想?yún)f(xié)調(diào)者發(fā)送 Ack 信息。?中斷事務(wù)：協(xié)調(diào)者接收到所有參與者反饋的 Ack 信息后，完成事務(wù)中斷。

從上面的邏輯可以看出，二階段提交就做了2個事情：投票，執(zhí)行。

舉個例子：

二階段提交看起來確實能夠提供原子性的操作，但是不幸的事，二階段提交還是有幾個缺點的：

1、同步阻塞問題。執(zhí)行過程中，所有參與節(jié)點都是事務(wù)阻塞型的。當參與者占有公共資源時，其他第三方節(jié)點訪問公共資源不得不處于阻塞狀態(tài)。

2、單點故障。由于協(xié)調(diào)者的重要性，一旦協(xié)調(diào)者發(fā)生故障。參與者會一直阻塞下去。尤其在第二階段，協(xié)調(diào)者發(fā)生故障，那么所有的參與者還都處于鎖定事務(wù)資源的狀態(tài)中，而無法繼續(xù)完成事務(wù)操作。（如果是協(xié)調(diào)者掛掉，可以重新選舉一個協(xié)調(diào)者，但是無法解決因為協(xié)調(diào)者宕機導(dǎo)致的參與者處于阻塞狀態(tài)的問題）

3、數(shù)據(jù)不一致。在二階段提交的階段二中，當協(xié)調(diào)者向參與者發(fā)送commit請求之后，發(fā)生了局部網(wǎng)絡(luò)異?；蛘咴诎l(fā)送commit請求過程中協(xié)調(diào)者發(fā)生了故障，這回導(dǎo)致只有一部分參與者接受到了commit請求。而在這部分參與者接到commit請求之后就會執(zhí)行commit操作。但是其他部分未接到commit請求的機器則無法執(zhí)行事務(wù)提交。于是整個分布式系統(tǒng)便出現(xiàn)了數(shù)據(jù)部一致性的現(xiàn)象。

4、二階段無法解決的問題：協(xié)調(diào)者再發(fā)出commit消息之后宕機，而唯一接收到這條消息的參與者同時也宕機了。那么即使協(xié)調(diào)者通過選舉協(xié)議產(chǎn)生了新的協(xié)調(diào)者，這條事務(wù)的狀態(tài)也是不確定的，沒人知道事務(wù)是否被已經(jīng)提交。

由于二階段提交存在著諸如同步阻塞、單點問題、腦裂等缺陷，所以，研究者們在二階段提交的基礎(chǔ)上做了改進，提出了三階段提交。

3PC

三階段提交（Three-phase commit），也叫三階段提交協(xié)議（Three-phase commit protocol），是二階段提交（2PC）的改進版本。

與兩階段提交不同的是，三階段提交有兩個改動點。

?引入超時機制。同時在協(xié)調(diào)者和參與者中都引入超時機制。?在第一階段和第二階段中插入一個準備階段。保證了在最后提交階段之前各參與節(jié)點的狀態(tài)是一致的。

也就是說，除了引入超時機制之外，3PC把2PC的準備階段再次一分為二，這樣三階段提交就有CanCommit、PreCommit、DoCommit三個階段。

CanCommit階段

3PC的CanCommit階段其實和2PC的準備階段很像。協(xié)調(diào)者向參與者發(fā)送commit請求，參與者如果可以提交就返回Yes響應(yīng)，否則返回No響應(yīng)。

1.事務(wù)詢問 協(xié)調(diào)者向參與者發(fā)送CanCommit請求。詢問是否可以執(zhí)行事務(wù)提交操作。然后開始等待參與者的響應(yīng)。2.響應(yīng)反饋 參與者接到CanCommit請求之后，正常情況下，如果其自身認為可以順利執(zhí)行事務(wù)，則返回Yes響應(yīng)，并進入預(yù)備狀態(tài)。否則反饋No

PreCommit階段

協(xié)調(diào)者根據(jù)canCommit階段參與者的反應(yīng)情況來決定是否可以繼續(xù)事務(wù)的PreCommit操作。根據(jù)響應(yīng)情況，有以下兩種可能。

假如協(xié)調(diào)者在CanCommit階段從所有的參與者獲得的反饋都是Yes響應(yīng)，那么就會執(zhí)行事務(wù)的預(yù)執(zhí)行。

1.發(fā)送預(yù)提交請求 協(xié)調(diào)者向參與者發(fā)送PreCommit請求，并進入Prepared階段。2.事務(wù)預(yù)提交 參與者接收到PreCommit請求后，會執(zhí)行事務(wù)操作，并將undo和redo信息記錄到事務(wù)日志中。3.響應(yīng)反饋 如果參與者成功的執(zhí)行了事務(wù)操作，則返回ACK響應(yīng)，同時開始等待最終指令。

假如canCommit階段有任何一個參與者向協(xié)調(diào)者發(fā)送了No響應(yīng)，或者等待超時之后，協(xié)調(diào)者都沒有接到參與者的響應(yīng)，那么就執(zhí)行事務(wù)的中斷。

1.發(fā)送中斷請求 協(xié)調(diào)者向所有參與者發(fā)送abort請求。2.中斷事務(wù) 參與者收到來自協(xié)調(diào)者的abort請求之后（或超時之后，仍未收到協(xié)調(diào)者的請求），執(zhí)行事務(wù)的中斷。

doCommit階段

該階段進行真正的事務(wù)提交，也可以分為以下兩種情況。

執(zhí)行提交

1.發(fā)送提交請求 協(xié)調(diào)接在preCommit階段收到參與者發(fā)送的ACK響應(yīng)，那么他將從預(yù)提交狀態(tài)進入到提交狀態(tài)。并向所有參與者發(fā)送doCommit請求。2.事務(wù)提交 參與者接收到doCommit請求之后，執(zhí)行正式的事務(wù)提交。并在完成事務(wù)提交之后釋放所有事務(wù)資源。3.響應(yīng)反饋 事務(wù)提交完之后，向協(xié)調(diào)者發(fā)送Ack響應(yīng)。4.完成事務(wù) 協(xié)調(diào)者接收到所有參與者的ack響應(yīng)之后，完成事務(wù)。

中斷事務(wù)協(xié)調(diào)者在preCommit階段沒有接收到參與者發(fā)送的ACK響應(yīng)（可能是接受者發(fā)送的不是ACK響應(yīng)，也可能響應(yīng)超時），那么就會執(zhí)行中斷事務(wù)。

1.發(fā)送中斷請求 協(xié)調(diào)者向所有參與者發(fā)送abort請求2.事務(wù)回滾 參與者接收到abort請求之后，利用其在階段二記錄的undo信息來執(zhí)行事務(wù)的回滾操作，并在完成回滾之后釋放所有的事務(wù)資源。3.反饋結(jié)果 參與者完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送ACK消息4.中斷事務(wù) 協(xié)調(diào)者接收到參與者反饋的ACK消息之后，執(zhí)行事務(wù)的中斷。

在doCommit階段，如果參與者無法及時接收到來自協(xié)調(diào)者的doCommit或者abort請求時，會在等待超時之后，會繼續(xù)進行事務(wù)的提交。（其實這個應(yīng)該是基于概率來決定的，當進入第三階段時，說明參與者在第二階段已經(jīng)收到了PreCommit請求，那么協(xié)調(diào)者產(chǎn)生PreCommit請求的前提條件是他在第二階段開始之前，收到所有參與者的CanCommit響應(yīng)都是Yes。（一旦參與者收到了PreCommit，意味他知道大家其實都同意修改了）所以，一句話概括就是，當進入第三階段時，由于網(wǎng)絡(luò)超時等原因，雖然參與者沒有收到commit或者abort響應(yīng)，但是他有理由相信：成功提交的幾率很大。）

小結(jié)

沒有任何事情是完美的。特別是在分布式的情況下。事實上，分布式在某個程度上其實是人類社會發(fā)展的一個極佳寫真。因為人類社會中個體的可靠性顯然比分布式系統(tǒng)節(jié)點的可靠性要低很多。

三階段提交也不完美。但是它比兩階段好。

兩階段的問題可以這樣分解：

?協(xié)調(diào)者出錯，參與者也出錯；?協(xié)調(diào)者出錯，參與者不出錯；?協(xié)調(diào)者不出錯，參與者出錯；?協(xié)調(diào)者不出錯，參與者也不出錯。

顯然第4種不是問題。所以實際上只有3個問題。而問題2可以通過簡單地NEW一個新的協(xié)調(diào)者來解決。問題3的錯則顯然正是兩階段提交協(xié)議的解決目標，所以也沒有問題。有問題的只有協(xié)調(diào)者出錯，參與者也出錯的問題。

無論2pc還是3pc只有在以下的情況才會出現(xiàn)數(shù)據(jù)不一致性：協(xié)調(diào)者掛了，備份協(xié)調(diào)者恢復(fù)協(xié)議時，某個參與者掛了，在剩下參與者都是“YES”的狀態(tài)下, 備份協(xié)調(diào)者沒法分辨掛了的參與者狀態(tài)。（此處掛了可理解為宕機或者時網(wǎng)絡(luò)連不上）

接下來將對上面段落使用一些替代詞：協(xié)調(diào)者A，備份協(xié)調(diào)者B，掛了參與者C

?在2pc中，B需要分辨兩種情形：1是C提交了事務(wù)（phase 2），2是C在原始投票是abort（phase 1）。如果B決定abort，會違反情形1，如果決定commit，則違背C在表決時的意愿，這個時候需要blocking 。（上面的"YES", 在這里可認為剩下的參與者在原始投票都是yes。）?在3pc中，B需要分辨兩種情形：1是C提交了事務(wù)（phase 3），2是B不知道C有沒有收到prepare commit(phase 2)，在這種情況下，因為我們已經(jīng)phase 1對大家的意愿進行了收集，得到的都是commit，所以此處會用比較激進做法，非blocking，所以才有上面的腦裂容錯策略，這樣也會降低阻塞范圍。

Paxos算法

Google Chubby的作者Mike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

Paxos在原作者的《Paxos Made Simple》中內(nèi)容是比較精簡的：

第一階段

（a） 提議者選擇一個提議編號n，并向大多數(shù)接受者發(fā)送一個編號n的準備請求。

（b） 如果承兌人收到的準備請求的編號n大于其已答復(fù)的任何準備請求的編號，則承兌人對該請求作出答復(fù)，并承諾不接受任何編號小于n且其已接受的編號最高的提案（如有）。

第二階段

（a） 如果提案人從大多數(shù)接受人處收到對其準備請求（編號n）的響應(yīng)，則它向這些接受人中的每一個發(fā)送一個接受請求，請求編號n的提案，其值為v，其中v是響應(yīng)中編號最高的提案的值，或者如果響應(yīng)報告沒有提案，則v是任何值。

（b） 如果承兌人收到編號為n的提案的接受請求，則除非承兌人已對編號大于n的準備請求作出響應(yīng)，否則接受該提案。

翻譯一下：

Paxos問題指分布式系統(tǒng)中存在故障fault，但不存在惡意corrupt節(jié)點場景（消息可能丟失但不會造假）下的共識達成（Consensus）問題。

Paxos是第一個被證明的共識算法，原理基于兩階段提交并進行擴展。算法中將節(jié)點分為三種類型：

?倡議者proposer：提交一個提案，等待大家批準為結(jié)案，往往是客戶端擔任。?接受者acceptor：負責(zé)對提案進行投票，往往服務(wù)器擔任。提議超過半數(shù)的接受者投票及被選中。?學(xué)習(xí)者learner：被告知提案結(jié)果，并與之統(tǒng)一，不參與投票過程?？蛻舳撕头?wù)端都可擔任。

每個節(jié)點在協(xié)議中可以擔任多個角色。

Paxos的特點：

?一個或多個節(jié)點可以提出提議。?系統(tǒng)針對所有提案中的某個提案必須達成一致。?最多只能對一個確定的提案達成一致。?只要超過半數(shù)的節(jié)點存活且可互相通信，整個系統(tǒng)一定能達成一致狀態(tài)。

第一階段A

Proposer選擇一個提議編號n，向所有的Acceptor廣播Prepare（n）請求。

第一階段B

Acceptor接收到Prepare（n）請求，若提議編號n比之前接收的Prepare請求都要大，則承諾將不會接收提議編號比n小的提議，并且?guī)现癆ccept的提議中編號小于n的最大的提議，否則不予理會。

第二階段A

Proposer得到了多數(shù)Acceptor的承諾后，如果沒有發(fā)現(xiàn)有一個Acceptor接受過一個值，那么向所有的Acceptor發(fā)起自己的值和提議編號n，否則，從所有接受過的值中選擇對應(yīng)的提議編號最大的，作為提議的值，提議編號仍然為n。

第二階段B

Acceptor接收到提議后，如果該提議編號不違反自己做過的承諾，則接受該提議。

Paxos 例子說明

樓主這個例子來自中文維基百科，但樓主為了形象化，輔以圖片解釋，但愿不會讓人更迷糊。

例子：

在 Paxos 島上，有A1, A2, A3, A4, A5 5位議員，就稅率問題進行決議。我們假設(shè)幾個場景來解釋：

場景 1：

假設(shè) A1 說：稅率應(yīng)該是 10%。而此時只有他一個人提這個建議。如下圖：

很完美，沒有任何人和他競爭提案，他的這個提案毫無阻撓的通過了。A2 - A5 都會回應(yīng)他：我們收到了你的提案，等待最終的批準。而 A1 在收到 2 份回復(fù)后，就可以發(fā)布最終的決議：稅率定位 10%，不用再討論了。

這里有個注意的地方就是：為什么收到了 2 份回復(fù)就可以確定提案了呢？答：因為包括他自己，就達到 3 個人了，少數(shù)服從多數(shù)。如果各位聽說過鴿籠原理/抽屜原理，就明白個大概了。有人說，鴿籠原理/抽屜原理就是 Paxos 的核心思想。

場景 2：

現(xiàn)在我們假設(shè)在 A1 提出 10% 稅率提案的同時, A5 決定將稅率定為 20%，如果這個提案要通過侍從送到其他議員的案頭，A1 的草案將由 4 位侍從送到 A2-A5 那里。但是侍從不靠譜（代表分布式環(huán)境不靠譜），負責(zé) A2 和 A3 的侍從順利送達，而負責(zé) A4 和 A5 的侍從則開溜了！

而 A5 的草案則送到了 A4 和 A3 的手中。

現(xiàn)在，A1 ，A2，A3 收到了 A1 的提案，A3，A4， A5 收到 A5 的提案，按照 Paxos 的協(xié)議，A1，A2，A4，A5 4個侍從將接受他們的提案，侍從拿著回復(fù)：我已收到你的提案，等待最終批準 回到提案者那里。

而 A3 的行為將決定批準哪一個。

當 A3 同時收到了 A1 和 A5 的請求，該如何抉擇呢？不同的抉擇將會導(dǎo)致不同的結(jié)果。

有 3 種情況，我們分析一下：

場景2：情況一

假設(shè) A1 的提案先送到 A3 那里，并且 A3 接受了該提案并回復(fù)了侍從。這樣，A1 加上 A2 加上 A3，構(gòu)成了多數(shù)派，成功確定了稅率為 10%。而 A5 的侍從由于路上喝酒喝多了，晚到了一天，等他到了，稅率已經(jīng)確定了，A3 回復(fù) A5：兄弟，你來的太晚了，稅率已經(jīng)定好了，不用折騰了，聽 A1 的吧。

如下圖：

場景2：情況二

依然假設(shè) A1 的提案先送到 A3 處，但是這次 A5 的侍從不是放假了，只是中途耽擱了一會。這次, A3 依然會將"接受"回復(fù)給 A1 .但是在決議成型之前它又收到了 A5 的提案。這時協(xié)議根據(jù) A5 的身份地位有兩種處理方式，但結(jié)果相同。

?當 A5 地位很高，例如 CEO，就回復(fù) A5：我已收到您的提案，等待最終批準，但是您之前有人提出將稅率定為10%,請明察。?當 A5 沒地位，普通碼農(nóng)一個，直接不回復(fù)。等待 A1 廣播：稅率定為 10% 啦?。?！

如下圖：

場景2：情況三

在這個情況中，我們將看見，根據(jù)提案的時間及提案者的權(quán)勢決定是否應(yīng)答是有意義的。在這里，時間和提案者的權(quán)勢就構(gòu)成了給提案編號的依據(jù)。這樣的編號符合"任何兩個提案之間構(gòu)成偏序"的要求。

A1 和 A5 同樣提出上述提案，這時 A1 可以正常聯(lián)系 A2 和 A3，A5 也可以正常聯(lián)系這兩個人。這次 A2 先收到 A1 的提案; A3 則先收到 A5 的提案。而 A5 更有地位。

在這種情況下，已經(jīng)回答 A1 的 A2 發(fā)現(xiàn)有比 A1 更有權(quán)勢的 A5 提出了稅率 20% 的新提案，于是回復(fù)A5說：我已收到您的提案，等待最終批準。

而回復(fù) A5 的 A3 發(fā)現(xiàn)新的提案者A1是個小人物，沒地位不予應(yīng)答。

此時，A5 得到了 A2，A3 的回復(fù)，于是 A5 說：稅率定為 20%，別再討論了。

那 A4 呢？A4 由于睡過頭了，迷迷糊糊的說：現(xiàn)有的稅率是什么? 如果沒有決定，則建議將其定為 15%.

這個時候，其他的議員就告訴他：哥們，已經(jīng)定為 20% 了，別折騰了。洗洗繼續(xù)睡吧。

整個過程如下圖：

Paxos的死鎖情況

“活鎖”的根本原因在于兩個proposer交替提案，避免“活鎖”的方式為，如果一個proposer通過accpter返回的消息知道此時有更高編號的提案被提出時，該proposer靜默一段時間，而不是馬上提出更高的方案，靜默期長短為一個提案從提出到被接受的大概時間長度即可，靜默期過后，proposer重新提案。系統(tǒng)中之所以要有主proposer的原因在于，如果每次數(shù)據(jù)更改都用paxos，那實在是太慢了，還是通過主節(jié)點下發(fā)請求這樣來的快，因為省去了不必要的paxos時間。所以選擇主proposer用paxos算法，因為選主的頻率要比更改數(shù)據(jù)頻率低太多。但是主proposer掛了咋整，整個集群就一直處于不可用狀態(tài)，所以一般都用租約的方式，如果proposer掛了，則租約會過期，其它proposer就可以再重新選主，如果不掛，則主proposer自己續(xù)租。

小結(jié)：

Paxos協(xié)議最終解決什么問題？

當一個提議被多數(shù)派接受后，這個提議對應(yīng)的值被Chosen（選定），一旦有一個值被Chosen，那么只要按照協(xié)議的規(guī)則繼續(xù)交互，后續(xù)被Chosen的值都是同一個值，也就是這個Chosen值的一致性問題。

Paxos 的目標：保證最終有一個提案會被選定，當提案被選定后，其他議員最終也能獲取到被選定的提案。

Paxos 協(xié)議用來解決的問題可以用一句話來簡化：將所有節(jié)點都寫入同一個值，且被寫入后不再更改。

Raft一致性算法

Raft算法是Paxos算法的一種簡化實現(xiàn)。

包括三種角色：leader，candidate和follower。

?follow:所有節(jié)點都以follower的狀態(tài)開始，如果沒有收到leader消息則會變成candidate狀態(tài)。?candidate：會向其他節(jié)點拉選票，如果得到大部分的票則成為leader，這個過程是Leader選舉。?leader：所有對系統(tǒng)的修改都會先經(jīng)過leader。

其有兩個基本過程：

?Leader選舉：每個candidate隨機經(jīng)過一定時間都會提出選舉方案，最近階段中的票最多者被選為leader。?同步log：leader會找到系統(tǒng)中l(wèi)og（各種事件的發(fā)生記錄）最新的記錄，并強制所有的follow來刷新到這個記錄。

Raft一致性算法是通過選出一個leader來簡化日志副本的管理，例如日志項（log entry）只允許從leader流向follower。

下面是動畫演示Raft，清晰理解Raft共識如何達成。

http://thesecretlivesofdata.com/raft/

1.針對簡化版拜占庭將軍問題，Raft 解決方案

假設(shè)將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們?nèi)绾芜_成一致性決定？

Raft 的解決方案大概可以理解成 先在所有將軍中選出一個大將軍，所有的決定由大將軍來做。選舉環(huán)節(jié)：比如說現(xiàn)在一共有3個將軍 A, B, C，每個將軍都有一個隨機時間的倒計時器，倒計時一結(jié)束，這個將軍就會把自己當成大將軍候選人，然后派信使去問其他幾個將軍，能不能選我為總將軍？假設(shè)現(xiàn)在將軍A倒計時結(jié)束了，他派信使傳遞選舉投票的信息給將軍B和C，如果將軍B和C還沒把自己當成候選人（倒計時還沒有結(jié)束），并且沒有把選舉票投給其他，他們把票投給將軍A，信使在回到將軍A時，將軍A知道自己收到了足夠的票數(shù)，成為了大將軍。在這之后，是否要進攻就由大將軍決定，然后派信使去通知另外兩個將軍，如果在一段時間后還沒有收到回復(fù)（可能信使被暗殺），那就再重派一個信使，直到收到回復(fù)。

1.選主 Leader Election

2.1 正常情況下選主

假設(shè)現(xiàn)在有如圖5個節(jié)點，5個節(jié)點一開始的狀態(tài)都是 Follower。

在一個節(jié)點倒計時結(jié)束 (Timeout) 后，這個節(jié)點的狀態(tài)變成 Candidate 開始選舉，它給其他幾個節(jié)點發(fā)送選舉請求 (RequestVote)

其他四個節(jié)點都返回成功，這個節(jié)點的狀態(tài)由 Candidate 變成了 Leader，并在每個一小段時間后，就給所有的 Follower 發(fā)送一個 Heartbeat 以保持所有節(jié)點的狀態(tài)，F(xiàn)ollower 收到 Leader 的 Heartbeat 后重設(shè) Timeout。

這是最簡單的選主情況，只要有超過一半的節(jié)點投支持票了，Candidate 才會被選舉為 Leader，5個節(jié)點的情況下，3個節(jié)點 (包括 Candidate 本身) 投了支持就行。

2.2 Leader 出故障情況下的選主

一開始已經(jīng)有一個 Leader，所有節(jié)點正常運行。

Leader 出故障掛掉了，其他四個 Follower 將進行重新選主。

4個節(jié)點的選主過程和5個節(jié)點的類似，在選出一個新的 Leader 后，原來的 Leader 恢復(fù)了又重新加入了，這個時候怎么處理？在 Raft 里，第幾輪選舉是有記錄的，重新加入的 Leader 是第一輪選舉 (Term 1) 選出來的，而現(xiàn)在的 Leader 則是 Term 2，所有原來的 Leader 會自覺降級為 Follower

2.3 多個 Candidate 情況下的選主

假設(shè)一開始有4個節(jié)點，都還是 Follower。

有兩個 Follower 同時 Timeout，都變成了 Candidate 開始選舉，分別給一個 Follower 發(fā)送了投票請求。

兩個 Follower 分別返回了ok，這時兩個 Candidate 都只有2票，要3票才能被選成 Leader。

兩個 Candidate 會分別給另外一個還沒有給自己投票的 Follower 發(fā)送投票請求。

但是因為 Follower 在這一輪選舉中，都已經(jīng)投完票了，所以都拒絕了他們的請求。所以在 Term 2 沒有 Leader 被選出來。

這時，兩個節(jié)點的狀態(tài)是 Candidate，兩個是 Follower，但是他們的倒計時器仍然在運行，最先 Timeout 的那個節(jié)點會進行發(fā)起新一輪 Term 3 的投票。

兩個 Follower 在 Term 3 還沒投過票，所以返回 OK，這時 Candidate 一共有三票，被選為了 Leader。

如果 Leader Heartbeat 的時間晚于另外一個 Candidate timeout 的時間，另外一個 Candidate 仍然會發(fā)送選舉請求。

兩個 Follower 已經(jīng)投完票了，拒絕了這個 Candidate 的投票請求。

Leader 進行 Heartbeat， Candidate 收到后狀態(tài)自動轉(zhuǎn)為 Follower，完成選主。

以上是 Raft 最重要活動之一選主的介紹，以及在不同情況下如何進行選主。

3. 復(fù)制日志 Log Replication

3.1 正常情況下復(fù)制日志

Raft 在實際應(yīng)用場景中的一致性更多的是體現(xiàn)在不同節(jié)點之間的數(shù)據(jù)一致性，客戶端發(fā)送請求到任何一個節(jié)點都能收到一致的返回，當一個節(jié)點出故障后，其他節(jié)點仍然能以已有的數(shù)據(jù)正常進行。在選主之后的復(fù)制日志就是為了達到這個目的。

一開始，Leader 和 兩個 Follower 都沒有任何數(shù)據(jù)。

客戶端發(fā)送請求給 Leader，儲存數(shù)據(jù) “sally”，Leader 先將數(shù)據(jù)寫在本地日志，這時候數(shù)據(jù)還是 Uncommitted (還沒最終確認，紅色表示)

Leader 給兩個 Follower 發(fā)送 AppendEntries 請求，數(shù)據(jù)在 Follower 上沒有沖突，則將數(shù)據(jù)暫時寫在本地日志，F(xiàn)ollower 的數(shù)據(jù)也還是 Uncommitted。

Follower 將數(shù)據(jù)寫到本地后，返回 OK。Leader 收到后成功返回，只要收到的成功的返回數(shù)量超過半數(shù) (包含Leader)，Leader 將數(shù)據(jù) “sally” 的狀態(tài)改成 Committed。( 這個時候 Leader 就可以返回給客戶端了)

Leader 再次給 Follower 發(fā)送 AppendEntries 請求，收到請求后，F(xiàn)ollower 將本地日志里 Uncommitted 數(shù)據(jù)改成 Committed。這樣就完成了一整個復(fù)制日志的過程，三個節(jié)點的數(shù)據(jù)是一致的，

3.2 Network Partition 情況下進行復(fù)制日志

在 Network Partition 的情況下，部分節(jié)點之間沒辦法互相通信，Raft 也能保證在這種情況下數(shù)據(jù)的一致性。

一開始有 5 個節(jié)點處于同一網(wǎng)絡(luò)狀態(tài)下。

Network Partition 將節(jié)點分成兩邊，一邊有兩個節(jié)點，一邊三個節(jié)點。

兩個節(jié)點這邊已經(jīng)有 Leader 了，來自客戶端的數(shù)據(jù) “bob” 通過 Leader 同步到 Follower。

因為只有兩個節(jié)點，少于3個節(jié)點，所以 “bob” 的狀態(tài)仍是 Uncommitted。所以在這里，服務(wù)器會返回錯誤給客戶端

另外一個 Partition 有三個節(jié)點，進行重新選主?？蛻舳藬?shù)據(jù) “tom” 發(fā)到新的 Leader，通過和上節(jié)網(wǎng)絡(luò)狀態(tài)下相似的過程，同步到另外兩個 Follower。

因為這個 Partition 有3個節(jié)點，超過半數(shù)，所以數(shù)據(jù) “tom” 都 Commit 了。

網(wǎng)絡(luò)狀態(tài)恢復(fù)，5個節(jié)點再次處于同一個網(wǎng)絡(luò)狀態(tài)下。但是這里出現(xiàn)了數(shù)據(jù)沖突 “bob" 和 “tom"

三個節(jié)點的 Leader 廣播 AppendEntries

兩個節(jié)點 Partition 的 Leader 自動降級為 Follower，因為這個 Partition 的數(shù)據(jù) “bob” 沒有 Commit，返回給客戶端的是錯誤，客戶端知道請求沒有成功，所以 Follower 在收到 AppendEntries 請求時，可以把 “bob“ 刪除，然后同步 ”tom”，通過這么一個過程，就完成了在 Network Partition 情況下的復(fù)制日志，保證了數(shù)據(jù)的一致性。

小結(jié)

Raft 是能夠?qū)崿F(xiàn)分布式系統(tǒng)強一致性的算法，每個系統(tǒng)節(jié)點有三種狀態(tài) Follower，Candidate，Leader。實現(xiàn) Raft 算法兩個最重要的事是：選主和復(fù)制日志。

一致性協(xié)議之 ZAB

什么是 ZAB 協(xié)議？ZAB 協(xié)議介紹

ZAB 協(xié)議全稱：Zookeeper Atomic Broadcast（Zookeeper 原子廣播協(xié)議）。

ZAB 協(xié)議是為分布式協(xié)調(diào)服務(wù) Zookeeper 專門設(shè)計的一種支持 崩潰恢復(fù) 和 原子廣播 協(xié)議。

整個 Zookeeper 就是在這兩個模式之間切換。簡而言之，當 Leader 服務(wù)可以正常使用，就進入消息廣播模式，當 Leader 不可用時，則進入崩潰恢復(fù)模式。

基于該協(xié)議，Zookeeper 實現(xiàn)了一種 主備模式 的系統(tǒng)架構(gòu)來保持集群中各個副本之間數(shù)據(jù)一致性。其中所有客戶端寫入數(shù)據(jù)都是寫入到 主進程（稱為 Leader）中，然后，由 Leader 復(fù)制到備份進程（稱為 Follower）中?！旧婕暗?PC單點問題的解決，崩潰恢復(fù)】

選擇機制中的概念

1、Serverid：服務(wù)器ID

比如有三臺服務(wù)器，編號分別是1,2,3。

編號越大在選擇算法中的權(quán)重越大。

2、Zxid：數(shù)據(jù)ID

服務(wù)器中存放的最大數(shù)據(jù)ID?！緕xid實際上是一個64位的數(shù)字，高32位是epoch（時期; 紀元; 世; 新時代）用來標識leader是否發(fā)生改變，如果有新的leader產(chǎn)生出來，epoch會自增，低32位用來遞增計數(shù)?！?

值越大說明數(shù)據(jù)越新，在選舉算法中數(shù)據(jù)越新權(quán)重越大。

3、Epoch：邏輯時鐘

或者叫投票的次數(shù)，同一輪投票過程中的邏輯時鐘值是相同的。每投完一次票這個數(shù)據(jù)就會增加，然后與接收到的其它服務(wù)器返回的投票信息中的數(shù)值相比，根據(jù)不同的值做出不同的判斷。

4、Server狀態(tài)：選舉狀態(tài)

LOOKING，競選狀態(tài)。

FOLLOWING，隨從狀態(tài)，同步leader狀態(tài)，參與投票。

OBSERVING，觀察狀態(tài),同步leader狀態(tài)，不參與投票。

LEADING，領(lǐng)導(dǎo)者狀態(tài)。

選舉消息內(nèi)容

在投票完成后，需要將投票信息發(fā)送給集群中的所有服務(wù)器，它包含如下內(nèi)容：服務(wù)器ID、數(shù)據(jù)ID、邏輯時鐘、選舉狀態(tài)。

zookeeper是如何保證事務(wù)的順序一致性的（保證消息有序） 在整個消息廣播中，Leader會將每一個事務(wù)請求轉(zhuǎn)換成對應(yīng)的 proposal 來進行廣播，并且在廣播 事務(wù)Proposal 之前，Leader服務(wù)器會首先為這個事務(wù)Proposal分配一個全局單遞增的唯一ID，稱之為事務(wù)ID（即zxid），由于Zab協(xié)議需要保證每一個消息的嚴格的順序關(guān)系，因此必須將每一個proposal按照其zxid的先后順序進行排序和處理。

消息廣播

1）在zookeeper集群中，數(shù)據(jù)副本的傳遞策略就是采用消息廣播模式。zookeeper中農(nóng)數(shù)據(jù)副本的同步方式與二段提交相似，但是卻又不同。二段提交要求協(xié)調(diào)者必須等到所有的參與者全部反饋ACK確認消息后，再發(fā)送commit消息。要求所有的參與者要么全部成功，要么全部失敗。二段提交會產(chǎn)生嚴重的阻塞問題。

2）Zab協(xié)議中 Leader 等待 Follower 的ACK反饋消息是指“只要半數(shù)以上的Follower成功反饋即可，不需要收到全部Follower反饋”。

消息廣播具體步驟

1）客戶端發(fā)起一個寫操作請求。

2）Leader 服務(wù)器將客戶端的請求轉(zhuǎn)化為事務(wù) Proposal 提案，同時為每個 Proposal 分配一個全局的ID，即zxid。

3）Leader 服務(wù)器為每個 Follower 服務(wù)器分配一個單獨的隊列，然后將需要廣播的 Proposal 依次放到隊列中取，并且根據(jù) FIFO 策略進行消息發(fā)送。

4）Follower 接收到 Proposal 后，會首先將其以事務(wù)日志的方式寫入本地磁盤中，寫入成功后向 Leader 反饋一個 Ack 響應(yīng)消息。

5）Leader 接收到超過半數(shù)以上 Follower 的 Ack 響應(yīng)消息后，即認為消息發(fā)送成功，可以發(fā)送 commit 消息。

6）Leader 向所有 Follower 廣播 commit 消息，同時自身也會完成事務(wù)提交。Follower 接收到 commit 消息后，會將上一條事務(wù)提交。

zookeeper 采用 Zab 協(xié)議的核心，就是只要有一臺服務(wù)器提交了 Proposal，就要確保所有的服務(wù)器最終都能正確提交 Proposal。這也是 CAP/BASE 實現(xiàn)最終一致性的一個體現(xiàn)。

Leader 服務(wù)器與每一個 Follower 服務(wù)器之間都維護了一個單獨的 FIFO 消息隊列進行收發(fā)消息，使用隊列消息可以做到異步解耦。Leader 和 Follower 之間只需要往隊列中發(fā)消息即可。如果使用同步的方式會引起阻塞，性能要下降很多。

崩潰恢復(fù)

崩潰恢復(fù)主要包括兩部分：Leader選舉 和 數(shù)據(jù)恢復(fù)

zookeeper是如何選取主leader的？

當leader崩潰或者leader失去大多數(shù)的follower，這時zk進入恢復(fù)模式，恢復(fù)模式需要重新選舉出一個新的leader，讓所有的Server都恢復(fù)到一個正確的狀態(tài)。

Zookeeper選主流程 選舉流程詳述

一、首先開始選舉階段，每個Server讀取自身的zxid。

二、發(fā)送投票信息

a、首先，每個Server第一輪都會投票給自己。

b、投票信息包含 ：所選舉leader的Serverid，Zxid，Epoch。Epoch會隨著選舉輪數(shù)的增加而遞增。

三、接收投票信息

1、如果服務(wù)器B接收到服務(wù)器A的數(shù)據(jù)（服務(wù)器A處于選舉狀態(tài)(LOOKING 狀態(tài))

1）首先，判斷邏輯時鐘值：

a）如果發(fā)送過來的邏輯時鐘Epoch大于目前的邏輯時鐘。首先，更新本邏輯時鐘Epoch，同時清空本輪邏輯時鐘收集到的來自其他server的選舉數(shù)據(jù)。然后，判斷是否需要更新當前自己的選舉leader Serverid。判斷規(guī)則rules judging：保存的zxid最大值和leader Serverid來進行判斷的。先看數(shù)據(jù)zxid,數(shù)據(jù)zxid大者勝出;其次再判斷l(xiāng)eader Serverid,leader Serverid大者勝出；然后再將自身最新的選舉結(jié)果(也就是上面提到的三種數(shù)據(jù)（leader Serverid，Zxid，Epoch）廣播給其他server)

b）如果發(fā)送過來的邏輯時鐘Epoch小于目前的邏輯時鐘。說明對方server在一個相對較早的Epoch中，這里只需要將本機的三種數(shù)據(jù)（leader Serverid，Zxid，Epoch）發(fā)送過去就行。

c）如果發(fā)送過來的邏輯時鐘Epoch等于目前的邏輯時鐘。再根據(jù)上述判斷規(guī)則rules judging來選舉leader ，然后再將自身最新的選舉結(jié)果(也就是上面提到的三種數(shù)據(jù)（leader Serverid，Zxid，Epoch）廣播給其他server)。

2）其次，判斷服務(wù)器是不是已經(jīng)收集到了所有服務(wù)器的選舉狀態(tài)：若是，根據(jù)選舉結(jié)果設(shè)置自己的角色(FOLLOWING還是LEADER)，退出選舉過程就是了。

最后，若沒有收集到所有服務(wù)器的選舉狀態(tài)：也可以判斷一下根據(jù)以上過程之后最新的選舉leader是不是得到了超過半數(shù)以上服務(wù)器的支持,如果是,那么嘗試在200ms內(nèi)接收一下數(shù)據(jù),如果沒有新的數(shù)據(jù)到來,說明大家都已經(jīng)默認了這個結(jié)果,同樣也設(shè)置角色退出選舉過程。

2、 如果所接收服務(wù)器A處在其它狀態(tài)（FOLLOWING或者LEADING）。

a)邏輯時鐘Epoch等于目前的邏輯時鐘，將該數(shù)據(jù)保存到recvset。此時Server已經(jīng)處于LEADING狀態(tài)，說明此時這個server已經(jīng)投票選出結(jié)果。若此時這個接收服務(wù)器宣稱自己是leader, 那么將判斷是不是有半數(shù)以上的服務(wù)器選舉它，如果是則設(shè)置選舉狀態(tài)退出選舉過程。

b) 否則這是一條與當前邏輯時鐘不符合的消息，那么說明在另一個選舉過程中已經(jīng)有了選舉結(jié)果，于是將該選舉結(jié)果加入到outofelection集合中，再根據(jù)outofelection來判斷是否可以結(jié)束選舉,如果可以也是保存邏輯時鐘，設(shè)置選舉狀態(tài)，退出選舉過程。【recvset：用來記錄選票信息，以方便后續(xù)統(tǒng)計;outofelection：用來記錄選舉邏輯之外的選票，例如當一個服務(wù)器加入zookeeper集群時，因為集群已經(jīng)存在，不用重新選舉，只需要在滿足一定條件下加入集群即可。】

描述Leader選擇過程中的狀態(tài)變化，這是假設(shè)全部實例中均沒有數(shù)據(jù)，假設(shè)服務(wù)器啟動順序分別為：A,B,C。

Zab 協(xié)議如何保證數(shù)據(jù)一致性

假設(shè)兩種異常情況：1、一個事務(wù)在 Leader 上提交了，并且過半的 Folower 都響應(yīng) Ack 了，但是 Leader 在 Commit 消息發(fā)出之前掛了。2、假設(shè)一個事務(wù)在 Leader 提出之后，Leader 掛了。

要確保如果發(fā)生上述兩種情況，數(shù)據(jù)還能保持一致性，那么 Zab 協(xié)議選舉算法必須滿足以下要求：

Zab 協(xié)議崩潰恢復(fù)要求滿足以下兩個要求：1）確保已經(jīng)被 Leader 提交的 Proposal 必須最終被所有的 Follower 服務(wù)器提交。2）確保丟棄已經(jīng)被 Leader 提出的但是沒有被提交的 Proposal。

根據(jù)上述要求 Zab協(xié)議需要保證選舉出來的Leader需要滿足以下條件：1）新選舉出來的 Leader 不能包含未提交的 Proposal 。即新選舉的 Leader 必須都是已經(jīng)提交了 Proposal 的 Follower 服務(wù)器節(jié)點。2）新選舉的 Leader 節(jié)點中含有最大的 zxid 。這樣做的好處是可以避免 Leader 服務(wù)器檢查 Proposal 的提交和丟棄工作。

Zab 如何數(shù)據(jù)同步

1）完成 Leader 選舉后（新的 Leader 具有最高的zxid），在正式開始工作之前（接收事務(wù)請求，然后提出新的 Proposal），Leader 服務(wù)器會首先確認事務(wù)日志中的所有的 Proposal 是否已經(jīng)被集群中過半的服務(wù)器 Commit。

2）Leader 服務(wù)器需要確保所有的 Follower 服務(wù)器能夠接收到每一條事務(wù)的 Proposal ，并且能將所有已經(jīng)提交的事務(wù) Proposal 應(yīng)用到內(nèi)存數(shù)據(jù)中。等到 Follower 將所有尚未同步的事務(wù) Proposal 都從 Leader 服務(wù)器上同步過啦并且應(yīng)用到內(nèi)存數(shù)據(jù)中以后，Leader 才會把該 Follower 加入到真正可用的 Follower 列表中。

Zab 數(shù)據(jù)同步過程中，如何處理需要丟棄的 Proposal

在 Zab 的事務(wù)編號 zxid 設(shè)計中，zxid是一個64位的數(shù)字。

其中低32位可以看成一個簡單的單增計數(shù)器，針對客戶端每一個事務(wù)請求，Leader 在產(chǎn)生新的 Proposal 事務(wù)時，都會對該計數(shù)器加1。而高32位則代表了 Leader 周期的 epoch 編號。

epoch 編號可以理解為當前集群所處的年代，或者周期。每次Leader變更之后都會在 epoch 的基礎(chǔ)上加1，這樣舊的 Leader 崩潰恢復(fù)之后，其他Follower 也不會聽它的了，因為 Follower 只服從epoch最高的 Leader 命令。

每當選舉產(chǎn)生一個新的 Leader ，就會從這個 Leader 服務(wù)器上取出本地事務(wù)日志充最大編號 Proposal 的 zxid，并從 zxid 中解析得到對應(yīng)的 epoch 編號，然后再對其加1，之后該編號就作為新的 epoch 值，并將低32位數(shù)字歸零，由0開始重新生成zxid。

Zab 協(xié)議通過 epoch 編號來區(qū)分 Leader 變化周期，能夠有效避免不同的 Leader 錯誤的使用了相同的 zxid 編號提出了不一樣的 Proposal 的異常情況。

基于以上策略:

當一個包含了上一個 Leader 周期中尚未提交過的事務(wù) Proposal 的服務(wù)器啟動時，當這臺機器加入集群中，以 Follower 角色連上 Leader 服務(wù)器后，Leader 服務(wù)器會根據(jù)自己服務(wù)器上最后提交的 Proposal 來和 Follower 服務(wù)器的 Proposal 進行比對，比對的結(jié)果肯定是 Leader 要求 Follower 進行一個回退操作，回退到一個確實已經(jīng)被集群中過半機器 Commit 的最新 Proposal。

小結(jié)

ZAB 協(xié)議和我們之前看的 Raft 協(xié)議實際上是有相似之處的，比如都有一個 Leader，用來保證一致性（Paxos 并沒有使用 Leader 機制保證一致性）。再有采取過半即成功的機制保證服務(wù)可用（實際上 Paxos 和 Raft 都是這么做的）。

ZAB 讓整個 Zookeeper 集群在兩個模式之間轉(zhuǎn)換，消息廣播和崩潰恢復(fù)，消息廣播可以說是一個簡化版本的 2PC，通過崩潰恢復(fù)解決了 2PC 的單點問題，通過隊列解決了 2PC 的同步阻塞問題。

而支持崩潰恢復(fù)后數(shù)據(jù)準確性的就是數(shù)據(jù)同步了，數(shù)據(jù)同步基于事務(wù)的 ZXID 的唯一性來保證。通過 + 1 操作可以辨別事務(wù)的先后順序。

NWR模型

Amazon Dynamo的NWR模型。NWR模型把CAP的選擇權(quán)交給了用戶，讓用戶自己的選擇你的CAP中的哪兩個。

所謂NWR模型。N代表N個備份，W代表要寫入至少W份才認為成功，R表示至少讀取R個備份。配置的時候要求W+R > N。因為W+R > N， 所以 R > N-W 這個是什么意思呢？就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫成功的倍數(shù)的差值要大。

也就是說，每次讀取，都至少讀取到一個最新的版本。從而不會讀到一份舊數(shù)據(jù)。當我們需要高可寫的環(huán)境的時候，我們可以配置W = 1 如果N=3 那么R = 3。這個時候只要寫任何節(jié)點成功就認為成功，但是讀的時候必須從所有的節(jié)點都讀出數(shù)據(jù)。如果我們要求讀的高效率，我們可以配置 W=N R=1。這個時候任何一個節(jié)點讀成功就認為成功，但是寫的時候必須寫所有三個節(jié)點成功才認為成功。

NWR模型的一些設(shè)置會造成臟數(shù)據(jù)的問題，因為這很明顯不是像Paxos一樣是一個強一致的東西，所以，可能每次的讀寫操作都不在同一個結(jié)點上，于是會出現(xiàn)一些結(jié)點上的數(shù)據(jù)并不是最新版本，但卻進行了最新的操作。

所以，Amazon Dynamo引了數(shù)據(jù)版本的設(shè)計。也就是說，如果你讀出來數(shù)據(jù)的版本是v1，當你計算完成后要回填數(shù)據(jù)后，卻發(fā)現(xiàn)數(shù)據(jù)的版本號已經(jīng)被人更新成了v2，那么服務(wù)器就會拒絕你。版本這個事就像“樂觀鎖”一樣。

但是，對于分布式和NWR模型來說，版本也會有惡夢的時候——就是版本沖的問題，比如：我們設(shè)置了N=3 W=1，如果A結(jié)點上接受了一個值，版本由v1 -> v2，但還沒有來得及同步到結(jié)點B上（異步的，應(yīng)該W=1，寫一份就算成功），B結(jié)點上還是v1版本，此時，B結(jié)點接到寫請求，按道理來說，他需要拒絕掉，但是他一方面并不知道別的結(jié)點已經(jīng)被更新到v2，另一方面他也無法拒絕，因為W=1，所以寫一分就成功了。于是，出現(xiàn)了嚴重的版本沖突。

Amazon的Dynamo把版本沖突這個問題巧妙地回避掉了——版本沖突這個事交給用戶自己來處理。

于是，Dynamo引入了Vector Clock（矢量鐘）這個設(shè)計。這個設(shè)計讓每個結(jié)點各自記錄自己的版本信息，也就是說，對于同一個數(shù)據(jù)，需要記錄兩個事：1）誰更新的我，2）我的版本號是什么。

下面，我們來看一個操作序列：

1）一個寫請求，第一次被節(jié)點A處理了。節(jié)點A會增加一個版本信息(A，1)。我們把這個時候的數(shù)據(jù)記做D1(A，1)。然后另外一個對同樣key的請求還是被A處理了于是有D2(A，2)。這個時候，D2是可以覆蓋D1的，不會有沖突產(chǎn)生。

2）現(xiàn)在我們假設(shè)D2傳播到了所有節(jié)點(B和C)，B和C收到的數(shù)據(jù)不是從客戶產(chǎn)生的，而是別人復(fù)制給他們的，所以他們不產(chǎn)生新的版本信息，所以現(xiàn)在B和C所持有的數(shù)據(jù)還是D2(A，2)。于是A，B，C上的數(shù)據(jù)及其版本號都是一樣的。

3）如果我們有一個新的寫請求到了B結(jié)點上，于是B結(jié)點生成數(shù)據(jù)D3(A,2; B,1)，意思是：數(shù)據(jù)D全局版本號為3，A升了兩新，B升了一次。這不就是所謂的代碼版本的log么？

4）如果D3沒有傳播到C的時候又一個請求被C處理了，于是，以C結(jié)點上的數(shù)據(jù)是D4(A,2; C,1)。

5）好，最精彩的事情來了：如果這個時候來了一個讀請求，我們要記得，我們的W=1 那么R=N=3，所以R會從所有三個節(jié)點上讀，此時，他會讀到三個版本：

?A結(jié)點：D2(A,2)?B結(jié)點：D3(A,2; B,1);?C結(jié)點：D4(A,2; C,1)

6）這個時候可以判斷出，D2已經(jīng)是舊版本（已經(jīng)包含在D3/D4中），可以舍棄。

7）但是D3和D4是明顯的版本沖突。于是，交給調(diào)用方自己去做版本沖突處理。就像源代碼版本管理一樣。

很明顯，上述的Dynamo的配置用的是CAP里的A和P。