一致性

簡述

一致性，是指對(duì)每個(gè)節(jié)點(diǎn)一個(gè)數(shù)據(jù)的更新，整個(gè)集群都知道更新，并且是一致的。假設(shè)一個(gè)具有N個(gè)節(jié)點(diǎn)的分布式系統(tǒng)，當(dāng)其滿足以下條件時(shí)，我們說這個(gè)系統(tǒng)滿足一致性：

• 全認(rèn)同: 所有N個(gè)節(jié)點(diǎn)都認(rèn)同一個(gè)結(jié)果
• 值合法: 該結(jié)果必須由N個(gè)節(jié)點(diǎn)中的過半節(jié)點(diǎn)提出
• 可結(jié)束: 決議過程在一定時(shí)間內(nèi)結(jié)束，不會(huì)無休止地進(jìn)行下去

面臨著的問題

1. 消息傳遞異步無序: 現(xiàn)實(shí)網(wǎng)絡(luò)不是一個(gè)可靠的信道，存在消息延時(shí)、丟失，節(jié)點(diǎn)間消息傳遞做不到同步有序
2. 節(jié)點(diǎn)宕機(jī): 節(jié)點(diǎn)持續(xù)宕機(jī)，不會(huì)恢復(fù)
3. 節(jié)點(diǎn)宕機(jī)恢復(fù): 節(jié)點(diǎn)宕機(jī)一段時(shí)間后恢復(fù)，在分布式系統(tǒng)中最常見
4. 網(wǎng)絡(luò)分化: 網(wǎng)絡(luò)鏈路出現(xiàn)問題，將N個(gè)節(jié)點(diǎn)隔離成多個(gè)部分
5. 拜占庭將軍問題: 節(jié)點(diǎn)或宕機(jī)或邏輯失敗，甚至不按套路出牌拋出干擾決議的信息

如下形象demo：

周五
我：晚上下班吃雞
周六凌晨
xc：好的?????????????????????????????//?消息延遲
我：WC
---------------------------------
我：晚上下班吃雞
xc：No
(兩小時(shí)后)
xc：No problem！?????????????????????//?宕機(jī)節(jié)點(diǎn)恢復(fù)
我：WC
---------------------------------
我：晚上下班吃雞
...?????????????????????????????????//?節(jié)點(diǎn)宕機(jī)


---------------------------------
我：晚上下班吃雞
cx:好，我們?nèi)ゴ蟊＝。?????????????????//?拜占庭將軍
我：WC

前面 已經(jīng)討論過，在分布式環(huán)境下，有很多不確定性因素，故障隨時(shí)都回發(fā)生，也講了CAP理論，BASE理論。我們希望達(dá)到在分布式環(huán)境下能搭建一個(gè)高可用的，且數(shù)據(jù)高一致性的服務(wù)，目標(biāo)是這樣，但CAP理論告訴我們要達(dá)到這樣的理想環(huán)境是不可能的。這三者最多完全滿足2個(gè)。

在這個(gè)前提下，P（分區(qū)容錯(cuò)性）是必然要滿足的，因?yàn)楫吘故欠植际?，不能把所有的?yīng)用全放到一個(gè)服務(wù)器里面，這樣服務(wù)器是吃不消的，而且也存在單點(diǎn)故障問題。所以，只能從一致性和可用性中找平衡。

怎么個(gè)平衡法？在這種環(huán)境下出現(xiàn)了BASE理論：即使無法做到強(qiáng)一致性，但分布式系統(tǒng)可以根據(jù)自己的業(yè)務(wù)特點(diǎn)，采用適當(dāng)?shù)姆绞絹硎瓜到y(tǒng)達(dá)到最終的一致性；BASE由Basically Avaliable 基本可用、Soft state 軟狀態(tài)、Eventually consistent 最終一致性組成，一句話概括就是：平時(shí)系統(tǒng)要求是基本可用，除開成功失敗，運(yùn)行有可容忍的延遲狀態(tài)，但是，無論如何經(jīng)過一段時(shí)間的延遲后系統(tǒng)最終必須達(dá)成數(shù)據(jù)是一致的。

其實(shí)可能發(fā)現(xiàn)不管是CAP理論，還是BASE理論，他們都是理論，這些理論是需要算法來實(shí)現(xiàn)的，今天講的2PC、3PC、Paxos算法，ZAB算法就是干這事情。

所以今天要講的這些的前提一定是分布式，解決的問題全部都是在分布式環(huán)境下，怎么讓系統(tǒng)盡可能的高可用，而且數(shù)據(jù)能最終能達(dá)到一致。

2PC

2PC(tow phase commit)兩階段提交。它本身是一致強(qiáng)一致性算法，所謂的兩個(gè)階段是指：第一階段：準(zhǔn)備階段(投票階段) 第二階段：提交階段(執(zhí)行階段)。我們將提議的節(jié)點(diǎn)稱為協(xié)調(diào)者(coordinator)，其他參與決議節(jié)點(diǎn)稱為參與者(participants, 或cohorts)。

階段1

在階段1中，協(xié)調(diào)者發(fā)起一個(gè)提議，分別問詢各參與者是否接受，如下圖：

階段2

在階段2中，協(xié)調(diào)者根據(jù)參與者的反饋，提交或中止事務(wù)，如果參與者全部同意則提交，只要有一個(gè)參與者不同意就中止。如下圖：

實(shí)例

下面我們通過一個(gè)例子來說明兩階段提交協(xié)議的工作過程：A組織B、C和D三個(gè)人去爬山：如果所有人都同意去爬山，那么活動(dòng)將舉行；如果有一人不同意去爬山，那么活動(dòng)將取消。用 2PC 算法解決該問題的過程如下：

首先A將成為該活動(dòng)的協(xié)調(diào)者，B、C和D將成為該活動(dòng)的參與者。

階段1：

1. A發(fā)郵件給B、C和D，提出下周三去爬山，問是否同意。那么此時(shí)A需要 等待B、C和D的郵件。
2. B、C和D分別查看自己的日程安排表。B、C發(fā)現(xiàn)自己在當(dāng)日沒有活動(dòng)安排，則發(fā)郵件告訴A它們同意下周三去爬山。由于某種原因， D白天沒有查看郵 件。那么此時(shí)A、B和C均 需要等待。到晚上的時(shí)候，D發(fā)現(xiàn)了A的郵件，然后查看日程安排，發(fā)現(xiàn)周三當(dāng)天已經(jīng)有別的安排，那么D回復(fù)A說活動(dòng)取消吧。

階段2：

1. 此時(shí)A收到了所有活動(dòng)參與者的郵件，并且A發(fā)現(xiàn)D下周三不能去爬山。那么A將發(fā)郵件通知B、C和D，下周三爬山活動(dòng)取消。
2. 此時(shí)B、C回復(fù)A太可惜了，D回復(fù)A不好意思。至此該事務(wù)終止。

數(shù)據(jù)庫中的2PC

在innodb存儲(chǔ)引擎，對(duì)數(shù)據(jù)庫的修改都會(huì)寫到undo和redo中，不只是數(shù)據(jù)庫，很多需要事務(wù)支持的都會(huì)用到這個(gè)思路。

對(duì)一條數(shù)據(jù)的修改操作首先寫undo日志，記錄的數(shù)據(jù)原來的樣子，接下來執(zhí)行事務(wù)修改操作，把數(shù)據(jù)寫到redo日志里面，萬一捅婁子，事務(wù)失敗了，可從undo里面回復(fù)數(shù)據(jù)。

不只是數(shù)據(jù)庫，在很多企業(yè)里面，比如華為等提交數(shù)據(jù)庫修改都回要求這樣，你要新增一個(gè)字段，首先要把修改數(shù)據(jù)庫的字段SQL提交給DBA（redo），這不夠，還需要把刪除你提交字段，把數(shù)據(jù)還原成你修改之前的語句也一并提交者叫（undo）

數(shù)據(jù)庫通過undo與redo能保證數(shù)據(jù)的強(qiáng)一致性，要解決分布式事務(wù)的前提就是當(dāng)個(gè)節(jié)點(diǎn)是支持事務(wù)的。

這在個(gè)前提下，2pc借鑒這失效，首先把整個(gè)分布式事務(wù)分兩節(jié)點(diǎn)，首先第一階段叫準(zhǔn)備節(jié)點(diǎn)，事務(wù)的請(qǐng)求都發(fā)送給一個(gè)個(gè)的資源，這里的資源可以是數(shù)據(jù)庫，也可以是其他支持事務(wù)的框架，他們會(huì)分別執(zhí)行自己的事務(wù)，寫日志到undo與redo，但是不提交事務(wù)。

當(dāng)事務(wù)管理器收到了所以資源的反饋，事務(wù)都執(zhí)行沒報(bào)錯(cuò)后，事務(wù)管理器再發(fā)送commit指令讓資源把事務(wù)提交，一旦發(fā)現(xiàn)任何一個(gè)資源在準(zhǔn)備階段沒有執(zhí)行成功，事務(wù)管理器會(huì)發(fā)送rollback，讓所有的資源都回滾。這就是2pc，非常非常簡單。

說他是強(qiáng)一致性的是他需要保證任何一個(gè)資源都成功，整個(gè)分布式事務(wù)才成功。

優(yōu)缺點(diǎn)

在異步環(huán)境并且沒有節(jié)點(diǎn)宕機(jī)的模型下，2PC可以滿足全認(rèn)同、值合法、可結(jié)束，是解決一致性問題的一種協(xié)議。從協(xié)調(diào)者接收到一次事務(wù)請(qǐng)求、發(fā)起提議到事務(wù)完成，經(jīng)過2PC協(xié)議后增加了2次RTT(propose+commit)，帶來的時(shí)延增加相對(duì)較少。優(yōu)點(diǎn)：

優(yōu)點(diǎn)：原理簡單，實(shí)現(xiàn)方便

缺點(diǎn)：

缺點(diǎn)：同步阻塞，單點(diǎn)問題，數(shù)據(jù)不一致，容錯(cuò)性不好

1. 同步阻塞

在二階段提交的過程中，所有的節(jié)點(diǎn)都在等待其他節(jié)點(diǎn)的響應(yīng)，無法進(jìn)行其他操作。這種同步阻塞極大的限制了分布式系統(tǒng)的性能。

2. 單點(diǎn)問題

協(xié)調(diào)者在整個(gè)二階段提交過程中很重要，如果協(xié)調(diào)者在提交階段出現(xiàn)問題，那么整個(gè)流程將無法運(yùn)轉(zhuǎn)。更重要的是，其他參與者將會(huì)處于一直鎖定事務(wù)資源的狀態(tài)中，而無法繼續(xù)完成事務(wù)操作。

3. 數(shù)據(jù)不一致

假設(shè)當(dāng)協(xié)調(diào)者向所有的參與者發(fā)送commit請(qǐng)求之后，發(fā)生了局部網(wǎng)絡(luò)異常，或者是協(xié)調(diào)者在尚未發(fā)送完所有 commit請(qǐng)求之前自身發(fā)生了崩潰，導(dǎo)致最終只有部分參與者收到了commit請(qǐng)求。這將導(dǎo)致嚴(yán)重的數(shù)據(jù)不一致問題。

4. 容錯(cuò)性不好

二階段提交協(xié)議沒有設(shè)計(jì)較為完善的容錯(cuò)機(jī)制，任意一個(gè)節(jié)點(diǎn)是失敗都會(huì)導(dǎo)致整個(gè)事務(wù)的失敗。

3PC

三階段提交（Three-phase commit），是二階段提交（2PC）的改進(jìn)版本。與兩階段提交不同的是，三階段提交有兩個(gè)改動(dòng)點(diǎn)。

1. 引入超時(shí)機(jī)制。同時(shí)在協(xié)調(diào)者和參與者中都引入超時(shí)機(jī)制。
2. 在第一階段和第二階段中插入一個(gè) 準(zhǔn)備階段。保證了在最后提交階段之前各參與節(jié)點(diǎn)的狀態(tài)是一致的。也就是說，除了引入超時(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ù)詢問 協(xié)調(diào)者向參與者發(fā)送CanCommit請(qǐng)求。詢問是否可以執(zhí)行事務(wù)提交操作。然后開始等待參與者的響應(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ù)參與者的反應(yīng)情況來決定是否可以記性事務(wù)的PreCommit操作。根據(jù)響應(yīng)情況，有以下兩種可能。假如協(xié)調(diào)者從所有的參與者獲得的反饋都是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í)開始等待最終指令。

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

發(fā)送中斷請(qǐng)求 協(xié)調(diào)者向所有參與者發(fā)送abort請(qǐng)求。中斷事務(wù) 參與者收到來自協(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)接收到參與者發(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)者沒有接收到參與者發(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信息來執(zhí)行事務(wù)的回滾操作，并在完成回滾之后釋放所有的事務(wù)資源。
3. 反饋結(jié)果 參與者完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送ACK消息
4. 中斷事務(wù) 協(xié)調(diào)者接收到參與者反饋的ACK消息之后，執(zhí)行事務(wù)的中斷。

所有數(shù)據(jù)庫的分布式事務(wù)一般都是二階段提交，而這三階段的思想更多的被借鑒擴(kuò)散成其他的算法。

優(yōu)缺點(diǎn)

與2PC區(qū)別：

第二階段才寫undo和redo事務(wù)日志 第三階段協(xié)調(diào)者出現(xiàn)異?；蚓W(wǎng)絡(luò)超時(shí)參與者也會(huì)commit

優(yōu)點(diǎn)：

改善同步阻塞 改善單點(diǎn)故障

缺點(diǎn)：

同步阻塞 單點(diǎn)故障 數(shù)據(jù)不一致 容錯(cuò)機(jī)制不完善

Paxos算法

這算法的提出者萊斯利·蘭伯特在前面幾篇論文中都不是以嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)公式進(jìn)行的。其實(shí)這個(gè)paxos算法也分成兩階段。首先這個(gè)圖有2個(gè)角色，提議者與接收者。

第一階段

提議者對(duì)接收者吼了一嗓子，我有個(gè)事情要告訴你們，當(dāng)然這里接受者不只一個(gè)(一半要奇數(shù)個(gè))，它也是個(gè)分布式集相當(dāng)于星期一開早會(huì)，可恥的領(lǐng)導(dǎo)吼了句：“要開會(huì)了啊，我要公布一個(gè)編號(hào)為001的提案，收到請(qǐng)回復(fù)”。這個(gè)時(shí)候領(lǐng)導(dǎo)就會(huì)等著，等員工回復(fù)1“好的”，如果回復(fù)的數(shù)目超過一半，就會(huì)進(jìn)行下一步。如果由于某些原因（接收者死機(jī)，網(wǎng)絡(luò)問題，本身業(yè)務(wù)問題），導(dǎo)致通過的協(xié)議未超過一半，

這個(gè)時(shí)候的領(lǐng)導(dǎo)又會(huì)再吼一嗓子，當(dāng)然氣勢沒那兇殘：“好了，怕了你們了，我要公布一個(gè)新的編號(hào)為002的提案，收到請(qǐng)回復(fù)1”【其實(shí)和上學(xué)時(shí)候老師講課很像，老師經(jīng)常問聽懂了嗎？聽懂的回1，沒懂的回2，只有回復(fù)1的占了大多數(shù)，才能講下個(gè)知識(shí)點(diǎn)】

第二階段

接下來到第二階段，領(lǐng)導(dǎo)苦口婆心的把你們叫來開會(huì)了，今天編號(hào)002提案的內(nèi)容是：“由于項(xiàng)目緊張，今天加班到12點(diǎn)，同意的請(qǐng)舉手”這個(gè)時(shí)候如果絕大多少的接收者都同意，那么好，議案就這么決定了，如果員工反對(duì)或者直接奪門而去，那么領(lǐng)導(dǎo)又只能從第一個(gè)階段開始：“大哥，大姐們，我有個(gè)新的提案003，快回會(huì)議室吧。?！?/p>

paxos的核心就是少數(shù)服從多數(shù)。

苦逼的領(lǐng)導(dǎo)（單點(diǎn)問題）：有這一幫兇殘的下屬，這領(lǐng)導(dǎo)要不可能被氣死，要不也會(huì)辭職，這是單點(diǎn)問題。兇神惡煞的下屬（一致性問題）：如果員工一直都拒絕，故意和領(lǐng)導(dǎo)抬桿，最終要產(chǎn)生一個(gè)一致性的解決方案是不可能的。

所以paxos協(xié)議肯定不會(huì)只有一個(gè)提議者，作為下屬的員工也不會(huì)那么強(qiáng)勢

協(xié)議要求：如果接收者沒有收到過提案編號(hào)，他必須接受第一個(gè)提案編號(hào) 如果接收者沒有收到過其他協(xié)議，他必須接受第一個(gè)協(xié)議。一旦一個(gè)提議被大家同意，那么之后的人再次提議，也是無效的，結(jié)果必須跟先前被大家接受的一致。

形象解說

Paxos算法解決的問題是在一個(gè)可能發(fā)生消息延遲、丟失、重復(fù)的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致，保證不論發(fā)生以上任何異常，都不會(huì)破壞決議的一致性。這 個(gè)“值”可能是一個(gè)數(shù)據(jù)的某，也可能是一條LOG等；根據(jù)不同的應(yīng)用環(huán)境這個(gè)“值”也不同。

一個(gè)典型的場景是，在一個(gè)分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)一致性算法以保證每個(gè)節(jié)點(diǎn)看到的指令一致。

例如：公司商定年會(huì)舉辦的地點(diǎn)，每個(gè)人都可以提出建議。在現(xiàn)實(shí)環(huán)境中我們可以在一個(gè)會(huì)議室共同討論或在微信群中討論（基于內(nèi)存共享方式）；但在基于消息傳遞的分布式環(huán)境中每個(gè)人只能通過手機(jī)短信與其它人通過。如何在這種會(huì)延遲、丟失的環(huán)境中確定一個(gè)年會(huì)舉辦地點(diǎn)；

Paxos算法是這樣解決這個(gè)問題：

1、每個(gè)人都可以提出建議、同意建議、接受建議 2、少數(shù)服從多數(shù)。只要建議被多數(shù)人同意即可確定該建議。于是確定以下討論方式：1、只有被提出來的建議才能被大家同意。2、最終只能確定一個(gè)建議 3、如果某個(gè)人認(rèn)為大家同意了某 個(gè)建議，那么這個(gè)建議必須真的是被大家同意的

算法推論：情況一：如果只有一個(gè)人提出建議怎么辦？如果只有一個(gè)建議被提出來那么大家必須贊同這個(gè)建議，因?yàn)槿绻煌膺@個(gè)建議就無法確定一個(gè)年會(huì)舉辦地點(diǎn)。P1:每一個(gè)人必須同意他收到的第一個(gè)建議， 基于這樣的結(jié)論會(huì)出現(xiàn)以下問題：

張三給王五發(fā)短信說：我建議去上海舉辦年會(huì)！王五給李四發(fā)短信說：我建議去廣州舉辦年會(huì)！李四給張三發(fā)短信說：我建議去北京舉辦年會(huì)！

根據(jù)P1：每個(gè)人必須同意他收到的第一個(gè)建議，那么張三、李四、王五最終獲得的信息是不一致的。所以再次規(guī)定：一個(gè)提議必須被大多數(shù)人同意才能生效。那么說明一個(gè)人可以同時(shí)同意多個(gè)建議，如果一個(gè)人可以同時(shí)同意多個(gè)建議最終可能出現(xiàn)拜占庭將軍問題導(dǎo)致最終結(jié)果不一致。（例如：張三同意到北京舉辦也同意到廣州舉辦，那么李四將獲得2票一票自己的，一票張三的。他會(huì)認(rèn)為自己獲得多數(shù)人支持所以就確定最終是到北京舉辦，同理王五也會(huì)同時(shí)獲得2票，也認(rèn)為大家最終決定到廣州舉辦）。? ?所以要避免出現(xiàn)這種問題，某個(gè)人只能同意的多個(gè)提議中的內(nèi)容相同（公司舉辦的地址）就不會(huì)出現(xiàn)這種問題。最終協(xié)商結(jié)果是有2票是到同一個(gè)地方，這樣就可以確認(rèn)最終舉辦地！那么就會(huì)引出 這樣的一個(gè)結(jié)論：一旦同意某個(gè)建議，那么之后同意的建議中提議公司舉辦年會(huì)的地址必須一致。問題出來了：如何確定什么是之前，什么 是之后所以必須為提議分配一個(gè)編號(hào)，在提議之間建立一個(gè)全序關(guān)系。

情況二：當(dāng)張三、李四、王五三個(gè)人確定最終到鄭州舉辦年會(huì)后。趙六、孫七2人由于手機(jī)沒電，沒收到通知，當(dāng)他們2人開機(jī)后趙六給孫七發(fā)短信提議到海南舉辦，這個(gè)提議是孫七開機(jī)后第一次收到的提議，根據(jù)P1原則，他必須同意他接收到的第一個(gè)提議，所以孫七同意到海南舉行年會(huì)。但這樣就會(huì)導(dǎo)致孫七與張三、李四、王五他們確定的舉辦地點(diǎn)不一致。為了避免出現(xiàn)以上問題。對(duì)P2進(jìn)行具體說明：P2a:一旦一個(gè)提議被大家同意，那么之后的人再次同意的提議中的公司舉辦年會(huì)的地址必須一致。也就是說，孫七在開機(jī)后同意的第一個(gè)提議必須是“到鄭州舉辦”才不會(huì)出現(xiàn)信息不一致的現(xiàn)象。但孫七開機(jī)后必須得接受第一個(gè)提議（P1原則），并且無法干涉提議中的內(nèi)容（公司舉辦年會(huì)的地址）。所以最好的辦法通過某種方式讓趙六的提議中的內(nèi)容與張三、李四同意的地址相同（到鄭州舉行）。這樣孫七同意的第一個(gè)提議就是“到鄭州舉辦”

我們?cè)俅螌?duì)P2a進(jìn)行修改：P2b:一旦一個(gè)提議被大家同意，那么之后的人再次提議，提議中的公司舉辦年會(huì)的地址必須跟之前其它人解決的地址一致。

如何讓剛開機(jī)的趙六提議的內(nèi)容必須與張三、李四、王五討論出來的一致（到鄭州舉行）？

我們繼續(xù)對(duì)P2b進(jìn)行強(qiáng)化修改：P2C:如果有一個(gè)編號(hào)為N的提議具有V(提議的內(nèi)容)，那么存在一個(gè)多數(shù)派，要么他們中所有人都沒有同意編號(hào)小于N的任何提議，要么他們已經(jīng)同意的所有編號(hào)小于N的提案中編號(hào)最大的那個(gè)提案具有V。

要滿足P2C的要求，提議人在提議之前，首先要和多數(shù)人通信并獲得他們進(jìn)行的最后一次同意的提議。之后根據(jù)反饋的信息決定這次提議的內(nèi)容，形成提議開始投票！

重點(diǎn)

所以整個(gè)投票決議分兩個(gè)階段：

1. 準(zhǔn)備階段

1、提議人選擇一個(gè)編號(hào)N，并將準(zhǔn)備信息發(fā)送給多數(shù)人。2、如果收信人收到準(zhǔn)備消息后，如果提議的編號(hào)大于它已經(jīng)回復(fù)的所有準(zhǔn)備信息。那么收信人將自己上次接受的提議內(nèi)容回復(fù)給提議人，并承諾不再回復(fù)小于N的提議。

2. 同意階段

1、當(dāng)一個(gè)提議人收到多數(shù)人反饋的信息后，就進(jìn)入同意階段。它要向反饋給它信息的人再次發(fā)送一個(gè)請(qǐng)同意該提議的請(qǐng)求。包含編號(hào)N和根據(jù)P2C決定的提議內(nèi)容（如果回復(fù)中沒有反饋他們已經(jīng)接受過的提議內(nèi)容，則可以自由決定提議內(nèi)容） 2、在不違背向其它人承諾的前提下，收到該提議請(qǐng)求后立即同意該請(qǐng)求。

假設(shè)：只有User1、User2、User3 三個(gè)人決定1+1等于幾！

提案階段

1. User1 提案編號(hào)為 1 并發(fā)送給User2和User3。

因User2 和User3 根據(jù)P2c它們并沒有接受過小于編號(hào)為1的提案。所以它們可以接受該提議，并反饋給User1 不再接受小于編號(hào)1的提案。這時(shí)User1收到多數(shù)人的回復(fù)，將進(jìn)入第2階段。（如果收到的回復(fù)并不能形成多數(shù)人，那么將再次進(jìn)入階段1）

2. User2 提案編號(hào)為2 ；并發(fā)送給User1和User3。

因User1第一次收到提案，并且根據(jù)P2C它并沒有同意過小于編號(hào)為2的提議，所以它可以接受該提議。User3由于接受過User1編號(hào)為1的提案，但User2的提案編號(hào) 2 > 1 所以User3也可以同意User2的提議，并反饋不再接受小于2的提議。User2也收到多數(shù)人的回復(fù)，將進(jìn)行第2階段。

3. User3提案編號(hào)為3 ；并發(fā)送給user1 和user2 .

因user1收到user3編號(hào)為3的提案 > user2編號(hào)為2的提案，所以接受user3的提案。因user2收到User3編號(hào)為3的提案 > user1 編號(hào)為1的提案，所以接受user3的提案。至此user3也收到多數(shù)人回復(fù)，將進(jìn)行第2階段。

同意階段

1. user1 發(fā)送編號(hào)為1的提議，提議內(nèi)容為：1+1=1；并發(fā)送給user2和User3 。

由于user2已經(jīng)聲明不再接受小于3的提案，所以拒絕user1的提案。由于User3已經(jīng)聲明不再接受小于2的提案，所以同樣拒絕User1的提案。User1提議被多數(shù)人拒絕，再次`進(jìn)入階段1**.

2. user2 發(fā)送編號(hào)為2的提議，提議內(nèi)容為：1+1=2；并發(fā)送給User1和User3

由于User1已經(jīng)聲明不再接受小于3的提案，所以拒絕user2的提議。由于User3已經(jīng)聲明不再接受小于2的提案，該提案編號(hào)=2所以u(píng)ser3同意User2的提議。但User2并沒有獲得多數(shù)人的同意，所以同樣進(jìn)行階段1.

3. User3 發(fā)送編號(hào)為3的提議，提議內(nèi)容為：1+1=3；并發(fā)送給User1和User2;

由于 user1 聲明不再接受小于3的提案，所以同意User3的提議。由于 user2 聲明不再接受小于3的提案，所以同意User3的提議。

至此最終User3可以獲得多數(shù)人的同意。

Raft

Raft 也是一個(gè)一致性算法，和 Paxos 目標(biāo)相同。但他還有另一個(gè)名字：易于理解的一致性算法。也就是說，他的目標(biāo)就是成為一個(gè)易于理解的一致性算法。以替代 Paxos 的晦澀難懂。

什么是 Raft 算法

首先說什么是 Raft 算法：Raft 是一種為了管理復(fù)制日志的一致性算法。

什么是一致性呢？

Raft 的論文這么說的：一致性算法允許一組機(jī)器像一個(gè)整體一樣工作，即使其中一些機(jī)器出現(xiàn)故障也能夠繼續(xù)工作下去。

這里的一致性針對(duì)分布式系統(tǒng)。

領(lǐng)導(dǎo)人選舉

Raft 通過選舉一個(gè)高貴的領(lǐng)導(dǎo)人，然后給予他全部的管理復(fù)制日志的責(zé)任來實(shí)現(xiàn)一致性。

而每個(gè) server 都可能會(huì)在 3 個(gè)身份之間切換：

領(lǐng)導(dǎo)者 候選者 跟隨者

而影響他們身份變化的則是 選舉。當(dāng)所有服務(wù)器初始化的時(shí)候，都是 跟隨者，這個(gè)時(shí)候需要一個(gè) 領(lǐng)導(dǎo)者，所有人都變成 候選者，直到有人成功當(dāng)選 領(lǐng)導(dǎo)者。角色輪換如下圖：而領(lǐng)導(dǎo)者也有宕機(jī)的時(shí)候，宕機(jī)后引發(fā)新的 選舉，所以，整個(gè)集群在選舉和正常運(yùn)行之間切換，具體如下圖：

從上圖可以看出，選舉和正常運(yùn)行之間切換，但請(qǐng)注意， 上圖中的 term 3 有一個(gè)地方，后面沒有跟著 正常運(yùn)行 階段，為什么呢?

答：當(dāng)一次選舉失敗（比如正巧每個(gè)人都投了自己），就執(zhí)行一次 加時(shí)賽，每個(gè) Server 會(huì)在一個(gè)隨機(jī)的時(shí)間里重新投票，這樣就能保證不沖突了。所以，當(dāng) term 3 選舉失敗，等了幾十毫秒，執(zhí)行 term 4 選舉，并成功選舉出領(lǐng)導(dǎo)人。

接著，領(lǐng)導(dǎo)者周期性的向所有跟隨者發(fā)送心跳包來維持自己的權(quán)威。如果一個(gè)跟隨者在一段時(shí)間里沒有接收到任何消息，也就是選舉超時(shí)，那么他就會(huì)認(rèn)為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者,并且發(fā)起選舉以選出新的領(lǐng)導(dǎo)者。

要開始一次選舉過程，跟隨者先要增加自己的當(dāng)前任期號(hào)并且轉(zhuǎn)換到候選人狀態(tài)。然后請(qǐng)求其他服務(wù)器為自己投票。那么會(huì)產(chǎn)生 3 種結(jié)果：

a. 自己成功當(dāng)選 b. 其他的服務(wù)器成為領(lǐng)導(dǎo)者 c. 僵住，沒有任何一個(gè)人成為領(lǐng)導(dǎo)者

注意：

每一個(gè) server 最多在一個(gè)任期內(nèi)投出一張選票（有任期號(hào)約束），先到先得。要求最多只能有一個(gè)人贏得選票。一旦成功，立即成為領(lǐng)導(dǎo)人，然后廣播所有服務(wù)器停止投票阻止新得領(lǐng)導(dǎo)產(chǎn)生。僵住怎么辦？Raft 通過使用隨機(jī)選舉超時(shí)時(shí)間（例如 150 - 300 毫秒）的方法將服務(wù)器打散投票。每個(gè)候選人在僵住的時(shí)候會(huì)隨機(jī)從一個(gè)時(shí)間開始重新選舉。以上，就是 Raft 所有關(guān)于領(lǐng)導(dǎo)選舉的策略。

日志復(fù)制

一旦一個(gè)領(lǐng)導(dǎo)人被選舉出來，他就開始為客戶端提供服務(wù)?？蛻舳税l(fā)送日志給領(lǐng)導(dǎo)者，隨后領(lǐng)導(dǎo)者將日志復(fù)制到其他的服務(wù)器。如果跟隨者故障，領(lǐng)導(dǎo)者將會(huì)嘗試重試。直到所有的跟隨者都成功存儲(chǔ)了所有日志。

下圖表示了當(dāng)一個(gè)客戶端發(fā)送一個(gè)日志給領(lǐng)導(dǎo)者，隨后領(lǐng)導(dǎo)者復(fù)制給跟隨者的整個(gè)過程

4 個(gè)步驟：

1. 客戶端提交
2. 復(fù)制數(shù)據(jù)到所有跟隨者
3. 跟隨者回復(fù) 確認(rèn)收到
4. 領(lǐng)導(dǎo)者回復(fù)客戶端和所有跟隨者 確認(rèn)提交。

可以看到，直到第四步驟，整個(gè)事務(wù)才會(huì)達(dá)成。中間任何一個(gè)步驟發(fā)生故障，都不會(huì)影響日志一致性。

可視化的Raft算法

github上有一個(gè)幫助大家理解算法的頁面，地址是 https://raft.github.io/raftscope/index.html

建議用電腦瀏覽器打開，如果在手機(jī)微信里打開，需要選擇“訪問原網(wǎng)頁”

我截了一個(gè)運(yùn)行狀態(tài)的截圖，左側(cè)顯示五臺(tái)服務(wù)器，右側(cè)顯示日志。

在服務(wù)器圖標(biāo)上點(diǎn)擊鼠標(biāo)右鍵會(huì)出現(xiàn)操作菜單。操作菜單對(duì)應(yīng)服務(wù)節(jié)點(diǎn)的狀態(tài)改變，其中request模擬客戶端請(qǐng)求服務(wù)器集群執(zhí)行任務(wù)，會(huì)在右邊產(chǎn)生日志。

總結(jié)

Raft算法具備強(qiáng)一致、高可靠、高可用等優(yōu)點(diǎn)，具體體現(xiàn)在：

強(qiáng)一致性：雖然所有節(jié)點(diǎn)的數(shù)據(jù)并非實(shí)時(shí)一致，但Raft算法保證Leader節(jié)點(diǎn)的數(shù)據(jù)最全，同時(shí)所有請(qǐng)求都由Leader處理，所以在客戶端角度看是強(qiáng)一致性的。

高可靠性：Raft算法保證了Committed的日志不會(huì)被修改，State Matchine只應(yīng)用Committed的日志，所以當(dāng)客戶端收到請(qǐng)求成功即代表數(shù)據(jù)不再改變。Committed日志在大多數(shù)節(jié)點(diǎn)上冗余存儲(chǔ)，少于一半的磁盤故障數(shù)據(jù)不會(huì)丟失。

高可用性：從Raft算法原理可以看出，選舉和日志同步都只需要大多數(shù)的節(jié)點(diǎn)正?；ヂ?lián)即可，所以少量節(jié)點(diǎn)故障或網(wǎng)絡(luò)異常不會(huì)影響系統(tǒng)的可用性。即使Leader故障，在選舉超時(shí)到期后，集群自發(fā)選舉新Leader，無需人工干預(yù)，不可用時(shí)間極小。但Leader故障時(shí)存在重復(fù)數(shù)據(jù)問題，需要業(yè)務(wù)去重或冪等性保證。

高性能：與必須將數(shù)據(jù)寫到所有節(jié)點(diǎn)才能返回客戶端成功的算法相比，Raft算法只需要大多數(shù)節(jié)點(diǎn)成功即可，少量節(jié)點(diǎn)處理緩慢不會(huì)延緩整體系統(tǒng)運(yùn)行。

ZAB

很多人會(huì)誤以為ZAB協(xié)議是Paxos的一種特殊實(shí)現(xiàn)，事實(shí)上他們是兩種不同的協(xié)議。ZAB和Paxos最大的不同是，ZAB主要是為分布式主備系統(tǒng)設(shè)計(jì)的，而Paxos的實(shí)現(xiàn)是一致性狀態(tài)機(jī)(state machine replication)

盡管ZAB不是Paxos的實(shí)現(xiàn)，但是ZAB也參考了一些Paxos的一些設(shè)計(jì)思想，比如：

1. leader向follows提出提案(proposal)
2. leader 需要在達(dá)到法定數(shù)量(半數(shù)以上)的follows確認(rèn)之后才會(huì)進(jìn)行commit
3. 每一個(gè)proposal都有一個(gè)紀(jì)元(epoch)號(hào)，類似于Paxos中的選票(ballot)

ZAB特性

1. 一致性保證

可靠提交(Reliable delivery) -如果一個(gè)事務(wù) A 被一個(gè)server提交(committed)了，那么它最終一定會(huì)被所有的server提交

2. 全局有序(Total order)

假設(shè)有A、B兩個(gè)事務(wù)，有一臺(tái)server先執(zhí)行A再執(zhí)行B，那么可以保證所有server上A始終都被在B之前執(zhí)行

3. 因果有序(Causal order) -

如果發(fā)送者在事務(wù)A提交之后再發(fā)送B,那么B必將在A之后執(zhí)行

4. 只要大多數(shù)（法定數(shù)量）節(jié)點(diǎn)啟動(dòng)，系統(tǒng)就行正常運(yùn)行
5. 當(dāng)節(jié)點(diǎn)下線后重啟，它必須保證能恢復(fù)到當(dāng)前正在執(zhí)行的事務(wù)

ZAB的具體實(shí)現(xiàn)

• ZooKeeper由 client、 server兩部分構(gòu)成
• client可以在任何一個(gè) server節(jié)點(diǎn)上進(jìn)行 讀操作
• client可以在任何一個(gè) server節(jié)點(diǎn)上發(fā)起 寫請(qǐng)求，非leader節(jié)點(diǎn)會(huì)把此次寫請(qǐng)求轉(zhuǎn)發(fā)到 leader節(jié)點(diǎn)上。由leader節(jié)點(diǎn)執(zhí)行
• ZooKeeper使用改編的兩階段提交協(xié)議來保證server節(jié)點(diǎn)的事務(wù)一致性

ZXID

ZooKeeper會(huì)為每一個(gè)事務(wù)生成一個(gè)唯一且遞增長度為64位的ZXID,ZXID由兩部分組成：低32位表示計(jì)數(shù)器(counter)和高32位的紀(jì)元號(hào)(epoch)。epoch為當(dāng)前l(fā)eader在成為leader的時(shí)候生成的，且保證會(huì)比前一個(gè)leader的epoch大

實(shí)際上當(dāng)新的leader選舉成功后，會(huì)拿到當(dāng)前集群中最大的一個(gè)ZXID(因?yàn)閿?shù)據(jù)最新)，并去除這個(gè)ZXID的epoch,并將此epoch進(jìn)行加1操作，作為自己的epoch。

歷史隊(duì)列(history queue)

每一個(gè)follower節(jié)點(diǎn)都會(huì)有一個(gè)先進(jìn)先出（FIFO)的隊(duì)列用來存放收到的事務(wù)請(qǐng)求，保證執(zhí)行事務(wù)的順序

• 可靠提交由ZAB的事務(wù)一致性協(xié)議保證
• 全局有序由TCP協(xié)議保證
• 因果有序由follower的歷史隊(duì)列(history queue)保證

ZAB工作模式

ZAB 協(xié)議是為分布式協(xié)調(diào)服務(wù) ZooKeeper 專門設(shè)計(jì)的一種支持崩潰恢復(fù)的原子廣播協(xié)議。在 ZooKeeper 中，主要依賴 ZAB 協(xié)議來實(shí)現(xiàn)分布式數(shù)據(jù)一致性。ZAB協(xié)議兩種模式：消息廣播和崩潰恢復(fù)`。

廣播(broadcast)模式

1. leader從客戶端收到一個(gè)寫請(qǐng)求
2. leader生成一個(gè)新的事務(wù)并為這個(gè)事務(wù)生成一個(gè)唯一的ZXID，
3. leader將這個(gè)事務(wù)發(fā)送給所有的follows節(jié)點(diǎn)，將帶有 zxid 的消息作為一個(gè)提案(proposal)分發(fā)給所有 follower。
4. follower節(jié)點(diǎn)將收到的事務(wù)請(qǐng)求加入到歷史隊(duì)列(history queue)中，當(dāng) follower 接收到 proposal，先將 proposal 寫到硬盤，寫硬盤成功后再向 leader 回一個(gè) ACK。
5. 當(dāng)leader收到大多數(shù)follower（超過法定數(shù)量）的ack消息，leader會(huì)發(fā)送commit請(qǐng)求
6. 當(dāng)follower收到commit請(qǐng)求時(shí)，會(huì)判斷該事務(wù)的ZXID是不是比歷史隊(duì)列中的任何事務(wù)的ZXID都小，如果是則提交，如果不是則等待比它更小的事務(wù)的commit(保證順序性)

恢復(fù)(recovery)模式

恢復(fù)模式大致可以分為四個(gè)階段 ?選舉、發(fā)現(xiàn)、同步、廣播。

1. 當(dāng)leader崩潰后，集群進(jìn)入選舉階段，開始選舉出潛在的新leader(一般為集群中擁有最大 ZXID的節(jié)點(diǎn))
2. 進(jìn)入發(fā)現(xiàn)階段，follower與潛在的新leader進(jìn)行溝通，如果發(fā)現(xiàn)超過法定人數(shù)的follower同意，則潛在的新leader將epoch加1，進(jìn)入新的紀(jì)元。新的leader產(chǎn)生
3. 集群間進(jìn)行數(shù)據(jù)同步，保證集群中各個(gè)節(jié)點(diǎn)的事務(wù)一致
4. 集群恢復(fù)到廣播模式，開始接受客戶端的寫請(qǐng)求

當(dāng) leader在commit之后但在發(fā)出commit消息之前宕機(jī)，即只有老leader自己commit了，而其它follower都沒有收到commit消息 新的leader也必須保證這個(gè)proposal被提交.(新的leader會(huì)重新發(fā)送該proprosal的commit消息)

當(dāng) leader產(chǎn)生某個(gè)proprosal之后但在發(fā)出消息之前宕機(jī)，即只有老leader自己有這個(gè)proproal，當(dāng)老的leader重啟后(此時(shí)左右follower),新的leader必須保證老的leader必須丟棄這個(gè)proprosal.(新的leader會(huì)通知上線后的老leader截?cái)嗥鋏poch對(duì)應(yīng)的最后一個(gè)commit的位置)

ZK選舉機(jī)制

1. 每個(gè)Server會(huì)發(fā)出一個(gè)投票,第一次都是投自己。投票信息：（myid，ZXID）
2. 收集來自各個(gè)服務(wù)器的投票
3. 處理投票并重新投票，處理邏輯：優(yōu)先比較ZXID,然后比較myid
4. 統(tǒng)計(jì)投票，只要超過半數(shù)的機(jī)器接收到同樣的投票信息，就可以確定leader
5. 改變服務(wù)器狀態(tài)

腦裂

ZAB為解決腦裂問題，要求集群內(nèi)的節(jié)點(diǎn)數(shù)量為2N+1, 當(dāng)網(wǎng)絡(luò)分裂后，始終有一個(gè)集群的節(jié)點(diǎn)數(shù)量過半數(shù)，而另一個(gè)節(jié)點(diǎn)數(shù)量小于N+1, 因?yàn)檫x主需要過半數(shù)節(jié)點(diǎn)同意，所以任何情況下集群中都不可能出現(xiàn)大于一個(gè)leader的情況。

參考

2PC跟3PC通俗說

Paxos形象說

知乎李凱講Paxos

不錯(cuò)的Paxos講解

小灰淺談