一致性

簡述

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

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

面臨著的問題

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

如下形象demo：

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


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

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

在這個前提下，P（分區(qū)容錯性）是必然要滿足的，因為畢竟是分布式，不能把所有的應(yīng)用全放到一個服務(wù)器里面，這樣服務(wù)器是吃不消的，而且也存在單點故障問題。所以，只能從一致性和可用性中找平衡。

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

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

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

2PC

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

階段1

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

階段2

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

實例

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

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

階段1：

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

階段2：

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

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

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

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

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

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

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

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

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

優(yōu)缺點

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

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

缺點：

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

1. 同步阻塞

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

2. 單點問題

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

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

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

4. 容錯性不好

二階段提交協(xié)議沒有設(shè)計較為完善的容錯機制，任意一個節(jié)點是失敗都會導致整個事務(wù)的失敗。

3PC

三階段提交（Three-phase commit），是二階段提交（2PC）的改進版本。與兩階段提交不同的是，三階段提交有兩個改動點。

1. 引入超時機制。同時在協(xié)調(diào)者和參與者中都引入超時機制。
2. 在第一階段和第二階段中插入一個 準備階段。保證了在最后提交階段之前各參與節(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ù)參與者的反應(yīng)情況來決定是否可以記性事務(wù)的PreCommit操作。根據(jù)響應(yīng)情況，有以下兩種可能。假如協(xié)調(diào)者從所有的參與者獲得的反饋都是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)，同時開始等待最終指令。

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

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

第三階段doCommit

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

執(zhí)行提交

1. 發(fā)送提交請求 協(xié)調(diào)接收到參與者發(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)者沒有接收到參與者發(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ù)的中斷。

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

優(yōu)缺點

與2PC區(qū)別：

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

優(yōu)點：

改善同步阻塞 改善單點故障

缺點：

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

Paxos算法

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

第一階段

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

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

第二階段

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

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

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

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

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

形象解說

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

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

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

Paxos算法是這樣解決這個問題：

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

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

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

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

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

我們再次對P2a進行修改：P2b:一旦一個提議被大家同意，那么之后的人再次提議，提議中的公司舉辦年會的地址必須跟之前其它人解決的地址一致。

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

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

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

重點

所以整個投票決議分兩個階段：

1. 準備階段

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

2. 同意階段

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

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

提案階段

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

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

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

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

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

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

同意階段

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

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

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

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

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

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

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

Raft

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

什么是 Raft 算法

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

什么是一致性呢？

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

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

領(lǐng)導人選舉

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

而每個 server 都可能會在 3 個身份之間切換：

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

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

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

答：當一次選舉失?。ū热缯擅總€人都投了自己），就執(zhí)行一次 加時賽，每個 Server 會在一個隨機的時間里重新投票，這樣就能保證不沖突了。所以，當 term 3 選舉失敗，等了幾十毫秒，執(zhí)行 term 4 選舉，并成功選舉出領(lǐng)導人。

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

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

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

注意：

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

日志復(fù)制

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

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

4 個步驟：

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

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

可視化的Raft算法

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

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

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

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

總結(jié)

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

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

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

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

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

ZAB

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

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

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

ZAB特性

1. 一致性保證

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

2. 全局有序(Total order)

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

3. 因果有序(Causal order) -

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

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

ZAB的具體實現(xiàn)

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

ZXID

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

實際上當新的leader選舉成功后，會拿到當前集群中最大的一個ZXID(因為數(shù)據(jù)最新)，并去除這個ZXID的epoch,并將此epoch進行加1操作，作為自己的epoch。

歷史隊列(history queue)

每一個follower節(jié)點都會有一個先進先出（FIFO)的隊列用來存放收到的事務(wù)請求，保證執(zhí)行事務(wù)的順序

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

ZAB工作模式

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

廣播(broadcast)模式

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

恢復(fù)(recovery)模式

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

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

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

當 leader產(chǎn)生某個proprosal之后但在發(fā)出消息之前宕機，即只有老leader自己有這個proproal，當老的leader重啟后(此時左右follower),新的leader必須保證老的leader必須丟棄這個proprosal.(新的leader會通知上線后的老leader截斷其epoch對應(yīng)的最后一個commit的位置)

ZK選舉機制

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

腦裂

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

參考

2PC跟3PC通俗說

Paxos形象說

知乎李凱講Paxos

不錯的Paxos講解

小灰淺談