背景

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

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

CAP 定理

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

Base 理論

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

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

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

2PC

Two-Phase Commit，事務(wù)的提交過(guò)程分成了兩個(gè)階段來(lái)進(jìn)行處理。

2PC 階段一

1.事務(wù)詢(xún)問(wèn)

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

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

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

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

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

2PC 階段二

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

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

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

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

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

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

舉個(gè)例子：

二階段提交看起來(lái)確實(shí)能夠提供原子性的操作，但是不幸的事，二階段提交還是有幾個(gè)缺點(diǎn)的：

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

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

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

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

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

3PC

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

與兩階段提交不同的是，三階段提交有兩個(gè)改動(dòng)點(diǎn)。

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

也就是說(shuō)，除了引入超時(shí)機(jī)制之外，3PC把2PC的準(zhǔn)備階段再次一分為二，這樣三階段提交就有CanCommit、PreCommit、DoCommit三個(gè)階段。

CanCommit階段

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

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

PreCommit階段

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

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

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

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

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

doCommit階段

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

執(zhí)行提交

1.發(fā)送提交請(qǐng)求 協(xié)調(diào)接在preCommit階段收到參與者發(fā)送的ACK響應(yīng)，那么他將從預(yù)提交狀態(tài)進(jìn)入到提交狀態(tài)。并向所有參與者發(fā)送doCommit請(qǐng)求。2.事務(wù)提交 參與者接收到doCommit請(qǐng)求之后，執(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階段沒(méi)有接收到參與者發(fā)送的ACK響應(yīng)（可能是接受者發(fā)送的不是ACK響應(yīng)，也可能響應(yīng)超時(shí)），那么就會(huì)執(zhí)行中斷事務(wù)。

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

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

小結(jié)

沒(méi)有任何事情是完美的。特別是在分布式的情況下。事實(shí)上，分布式在某個(gè)程度上其實(shí)是人類(lèi)社會(huì)發(fā)展的一個(gè)極佳寫(xiě)真。因?yàn)槿祟?lèi)社會(huì)中個(gè)體的可靠性顯然比分布式系統(tǒng)節(jié)點(diǎn)的可靠性要低很多。

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

兩階段的問(wèn)題可以這樣分解：

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

顯然第4種不是問(wèn)題。所以實(shí)際上只有3個(gè)問(wèn)題。而問(wèn)題2可以通過(guò)簡(jiǎn)單地NEW一個(gè)新的協(xié)調(diào)者來(lái)解決。問(wèn)題3的錯(cuò)則顯然正是兩階段提交協(xié)議的解決目標(biāo)，所以也沒(méi)有問(wèn)題。有問(wèn)題的只有協(xié)調(diào)者出錯(cuò)，參與者也出錯(cuò)的問(wèn)題。

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

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

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

Paxos算法

Google Chubby的作者M(jìn)ike Burrows說(shuō)過(guò)這個(gè)世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

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

第一階段

（a） 提議者選擇一個(gè)提議編號(hào)n，并向大多數(shù)接受者發(fā)送一個(gè)編號(hào)n的準(zhǔn)備請(qǐng)求。

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

第二階段

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

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

翻譯一下：

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

Paxos是第一個(gè)被證明的共識(shí)算法，原理基于兩階段提交并進(jìn)行擴(kuò)展。算法中將節(jié)點(diǎn)分為三種類(lèi)型：

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

每個(gè)節(jié)點(diǎn)在協(xié)議中可以擔(dān)任多個(gè)角色。

Paxos的特點(diǎn)：

?一個(gè)或多個(gè)節(jié)點(diǎn)可以提出提議。?系統(tǒng)針對(duì)所有提案中的某個(gè)提案必須達(dá)成一致。?最多只能對(duì)一個(gè)確定的提案達(dá)成一致。?只要超過(guò)半數(shù)的節(jié)點(diǎn)存活且可互相通信，整個(gè)系統(tǒng)一定能達(dá)成一致?tīng)顟B(tài)。

第一階段A

Proposer選擇一個(gè)提議編號(hào)n，向所有的Acceptor廣播Prepare（n）請(qǐng)求。

第一階段B

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

第二階段A

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

第二階段B

Acceptor接收到提議后，如果該提議編號(hào)不違反自己做過(guò)的承諾，則接受該提議。

Paxos 例子說(shuō)明

樓主這個(gè)例子來(lái)自中文維基百科，但樓主為了形象化，輔以圖片解釋?zhuān)覆粫?huì)讓人更迷糊。

例子：

在 Paxos 島上，有A1, A2, A3, A4, A5 5位議員，就稅率問(wèn)題進(jìn)行決議。我們假設(shè)幾個(gè)場(chǎng)景來(lái)解釋?zhuān)?

場(chǎng)景 1：

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

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

這里有個(gè)注意的地方就是：為什么收到了 2 份回復(fù)就可以確定提案了呢？答：因?yàn)榘ㄋ约?，就達(dá)到 3 個(gè)人了，少數(shù)服從多數(shù)。如果各位聽(tīng)說(shuō)過(guò)鴿籠原理/抽屜原理，就明白個(gè)大概了。有人說(shuō)，鴿籠原理/抽屜原理就是 Paxos 的核心思想。

場(chǎng)景 2：

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

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

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

而 A3 的行為將決定批準(zhǔn)哪一個(gè)。

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

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

場(chǎng)景2：情況一

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

如下圖：

場(chǎng)景2：情況二

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

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

如下圖：

場(chǎng)景2：情況三

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

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

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

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

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

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

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

整個(gè)過(guò)程如下圖：

Paxos的死鎖情況

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

小結(jié)：

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

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

Paxos 的目標(biāo)：保證最終有一個(gè)提案會(huì)被選定，當(dāng)提案被選定后，其他議員最終也能獲取到被選定的提案。

Paxos 協(xié)議用來(lái)解決的問(wèn)題可以用一句話(huà)來(lái)簡(jiǎn)化：將所有節(jié)點(diǎn)都寫(xiě)入同一個(gè)值，且被寫(xiě)入后不再更改。

Raft一致性算法

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

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

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

其有兩個(gè)基本過(guò)程：

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

Raft一致性算法是通過(guò)選出一個(gè)leader來(lái)簡(jiǎn)化日志副本的管理，例如日志項(xiàng)（log entry）只允許從leader流向follower。

下面是動(dòng)畫(huà)演示Raft，清晰理解Raft共識(shí)如何達(dá)成。

http://thesecretlivesofdata.com/raft/

1.針對(duì)簡(jiǎn)化版拜占庭將軍問(wèn)題，Raft 解決方案

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

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

1.選主 Leader Election

2.1 正常情況下選主

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

在一個(gè)節(jié)點(diǎn)倒計(jì)時(shí)結(jié)束 (Timeout) 后，這個(gè)節(jié)點(diǎn)的狀態(tài)變成 Candidate 開(kāi)始選舉，它給其他幾個(gè)節(jié)點(diǎn)發(fā)送選舉請(qǐng)求 (RequestVote)

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

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

2.2 Leader 出故障情況下的選主

一開(kāi)始已經(jīng)有一個(gè) Leader，所有節(jié)點(diǎn)正常運(yùn)行。

Leader 出故障掛掉了，其他四個(gè) Follower 將進(jìn)行重新選主。

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

2.3 多個(gè) Candidate 情況下的選主

假設(shè)一開(kāi)始有4個(gè)節(jié)點(diǎn)，都還是 Follower。

有兩個(gè) Follower 同時(shí) Timeout，都變成了 Candidate 開(kāi)始選舉，分別給一個(gè) Follower 發(fā)送了投票請(qǐng)求。

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

兩個(gè) Candidate 會(huì)分別給另外一個(gè)還沒(méi)有給自己投票的 Follower 發(fā)送投票請(qǐng)求。

但是因?yàn)?Follower 在這一輪選舉中，都已經(jīng)投完票了，所以都拒絕了他們的請(qǐng)求。所以在 Term 2 沒(méi)有 Leader 被選出來(lái)。

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

兩個(gè) Follower 在 Term 3 還沒(méi)投過(guò)票，所以返回 OK，這時(shí) Candidate 一共有三票，被選為了 Leader。

如果 Leader Heartbeat 的時(shí)間晚于另外一個(gè) Candidate timeout 的時(shí)間，另外一個(gè) Candidate 仍然會(huì)發(fā)送選舉請(qǐng)求。

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

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

以上是 Raft 最重要活動(dòng)之一選主的介紹，以及在不同情況下如何進(jìn)行選主。

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

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

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

一開(kāi)始，Leader 和 兩個(gè) Follower 都沒(méi)有任何數(shù)據(jù)。

客戶(hù)端發(fā)送請(qǐng)求給 Leader，儲(chǔ)存數(shù)據(jù) “sally”，Leader 先將數(shù)據(jù)寫(xiě)在本地日志，這時(shí)候數(shù)據(jù)還是 Uncommitted (還沒(méi)最終確認(rèn)，紅色表示)

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

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

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

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

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

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

Network Partition 將節(jié)點(diǎn)分成兩邊，一邊有兩個(gè)節(jié)點(diǎn)，一邊三個(gè)節(jié)點(diǎn)。

兩個(gè)節(jié)點(diǎn)這邊已經(jīng)有 Leader 了，來(lái)自客戶(hù)端的數(shù)據(jù) “bob” 通過(guò) Leader 同步到 Follower。

因?yàn)橹挥袃蓚€(gè)節(jié)點(diǎn)，少于3個(gè)節(jié)點(diǎn)，所以 “bob” 的狀態(tài)仍是 Uncommitted。所以在這里，服務(wù)器會(huì)返回錯(cuò)誤給客戶(hù)端

另外一個(gè) Partition 有三個(gè)節(jié)點(diǎn)，進(jìn)行重新選主。客戶(hù)端數(shù)據(jù) “tom” 發(fā)到新的 Leader，通過(guò)和上節(jié)網(wǎng)絡(luò)狀態(tài)下相似的過(guò)程，同步到另外兩個(gè) Follower。

因?yàn)檫@個(gè) Partition 有3個(gè)節(jié)點(diǎn)，超過(guò)半數(shù)，所以數(shù)據(jù) “tom” 都 Commit 了。

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

三個(gè)節(jié)點(diǎn)的 Leader 廣播 AppendEntries

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

小結(jié)

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

一致性協(xié)議之 ZAB

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

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

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

整個(gè) Zookeeper 就是在這兩個(gè)模式之間切換。簡(jiǎn)而言之，當(dāng) Leader 服務(wù)可以正常使用，就進(jìn)入消息廣播模式，當(dāng) Leader 不可用時(shí)，則進(jìn)入崩潰恢復(fù)模式。

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

選擇機(jī)制中的概念

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

比如有三臺(tái)服務(wù)器，編號(hào)分別是1,2,3。

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

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

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

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

3、Epoch：邏輯時(shí)鐘

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

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

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

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

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

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

選舉消息內(nèi)容

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

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

消息廣播

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

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

消息廣播具體步驟

1）客戶(hù)端發(fā)起一個(gè)寫(xiě)操作請(qǐng)求。

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

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

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

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

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

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

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

崩潰恢復(fù)

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

zookeeper是如何選取主leader的？

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

Zookeeper選主流程 選舉流程詳述

一、首先開(kāi)始選舉階段，每個(gè)Server讀取自身的zxid。

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

a、首先，每個(gè)Server第一輪都會(huì)投票給自己。

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

三、接收投票信息

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

1）首先，判斷邏輯時(shí)鐘值：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于以上策略:

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

小結(jié)

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

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

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

NWR模型

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

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

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

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

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

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

Amazon的Dynamo把版本沖突這個(gè)問(wèn)題巧妙地回避掉了——版本沖突這個(gè)事交給用戶(hù)自己來(lái)處理。

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

下面，我們來(lái)看一個(gè)操作序列：

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

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

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

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

5）好，最精彩的事情來(lái)了：如果這個(gè)時(shí)候來(lái)了一個(gè)讀請(qǐng)求，我們要記得，我們的W=1 那么R=N=3，所以R會(huì)從所有三個(gè)節(jié)點(diǎn)上讀，此時(shí)，他會(huì)讀到三個(gè)版本：

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

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

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

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