超詳細解析 | 一緻性協定算法-2PC、3PC、Paxos、Raft、ZAB、NWR

背景

在常見的分布式系統中，總會發生諸如機器當機或網絡異常（包括消息的延遲、丢失、重複、亂序，還有網絡分區）等情況。

一緻性算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正确地在叢集内部對某個資料的值達成一緻，并且保證不論發生以上任何異常，都不會破壞整個系統的一緻性。

CAP 定理

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

Base 理論

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

Base 理論是對 CAP 中一緻性和可用性權衡的結果，其來源于對大型網際網路分布式實踐的總結，是基于 CAP 定理逐漸演化而來的。其核心思想是：既是無法做到強一緻性（Strong consistency），但每個應用都可以根據自身的業務特點，采用适當的方式來使系統達到最終一緻性（Eventual consistency）。

解釋一下：

什麼是軟狀态呢？相對于原子性而言，要求多個節點的資料副本都是一緻的，這是一種 “硬狀态”。軟狀态指的是：允許系統中的資料存在中間狀态，并認為該狀态不影響系統的整體可用性，即允許系統在多個不同節點的資料副本存在資料延時。

2PC

Two-Phase Commit，事務的送出過程分成了兩個階段來進行處理。

2PC 階段一

1.事務詢問

協調者向所有的參與者詢問，是否準備好了執行事務，并開始等待各參與者的響應。

1.執行事務

各參與者節點執行事務操作，并将 Undo 和 Redo 資訊記入事務日志中

1.各參與者向協調者回報事務詢問的響應

如果參與者成功執行了事務操作，那麼就回報給協調者 Yes 響應，表示事務可以執行；如果參與者沒有成功執行事務，就傳回 No 給協調者，表示事務不可以執行。

2PC 階段二

在階段二中，會根據階段一的投票結果執行 2 種操作：執行事務送出，中斷事務。

執行事務送出步驟如下：

•發送送出請求：協調者向所有參與者發出 commit 請求。•事務送出：參與者收到 commit 請求後，會正式執行事務送出操作，并在完成送出之後釋放整個事務執行期間占用的事務資源。•回報事務送出結果：參與者在完成事務送出之後，向協調者發送 Ack 資訊。•協調者接收到所有參與者回報的 Ack 資訊後，完成事務。

中斷事務步驟如下：

•發送復原請求：協調者向所有參與者發出 Rollback 請求。•事務復原：參與者接收到 Rollback 請求後，會利用其在階段一種記錄的 Undo 資訊來執行事務復原操作，并在完成復原之後釋放在整個事務執行期間占用的資源。•回報事務復原結果：參與者在完成事務復原之後，想協調者發送 Ack 資訊。•中斷事務：協調者接收到所有參與者回報的 Ack 資訊後，完成事務中斷。

從上面的邏輯可以看出，二階段送出就做了2個事情：投票，執行。

舉個例子：

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

1、同步阻塞問題。執行過程中，所有參與節點都是事務阻塞型的。當參與者占有公共資源時，其他第三方節點通路公共資源不得不處于阻塞狀态。

2、單點故障。由于協調者的重要性，一旦協調者發生故障。參與者會一直阻塞下去。尤其在第二階段，協調者發生故障，那麼所有的參與者還都處于鎖定事務資源的狀态中，而無法繼續完成事務操作。（如果是協調者挂掉，可以重新選舉一個協調者，但是無法解決因為協調者當機導緻的參與者處于阻塞狀态的問題）

3、資料不一緻。在二階段送出的階段二中，當協調者向參與者發送commit請求之後，發生了局部網絡異常或者在發送commit請求過程中協調者發生了故障，這回導緻隻有一部分參與者接受到了commit請求。而在這部分參與者接到commit請求之後就會執行commit操作。但是其他部分未接到commit請求的機器則無法執行事務送出。于是整個分布式系統便出現了資料部一緻性的現象。

4、二階段無法解決的問題：協調者再發出commit消息之後當機，而唯一接收到這條消息的參與者同時也當機了。那麼即使協調者通過選舉協定産生了新的協調者，這條事務的狀态也是不确定的，沒人知道事務是否被已經送出。

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

3PC

三階段送出（Three-phase commit），也叫三階段送出協定（Three-phase commit protocol），是二階段送出（2PC）的改進版本。

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

•引入逾時機制。同時在協調者和參與者中都引入逾時機制。•在第一階段和第二階段中插入一個準備階段。保證了在最後送出階段之前各參與節點的狀态是一緻的。

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

CanCommit階段

3PC的CanCommit階段其實和2PC的準備階段很像。協調者向參與者發送commit請求，參與者如果可以送出就傳回Yes響應，否則傳回No響應。

1.事務詢問 協調者向參與者發送CanCommit請求。詢問是否可以執行事務送出操作。然後開始等待參與者的響應。2.響應回報 參與者接到CanCommit請求之後，正常情況下，如果其自身認為可以順利執行事務，則傳回Yes響應，并進入預備狀态。否則回報No

PreCommit階段

協調者根據canCommit階段參與者的反應情況來決定是否可以繼續事務的PreCommit操作。根據響應情況，有以下兩種可能。

假如協調者在CanCommit階段從所有的參與者獲得的回報都是Yes響應，那麼就會執行事務的預執行。

1.發送預送出請求 協調者向參與者發送PreCommit請求，并進入Prepared階段。2.事務預送出 參與者接收到PreCommit請求後，會執行事務操作，并将undo和redo資訊記錄到事務日志中。3.響應回報 如果參與者成功的執行了事務操作，則傳回ACK響應，同時開始等待最終指令。

假如canCommit階段有任何一個參與者向協調者發送了No響應，或者等待逾時之後，協調者都沒有接到參與者的響應，那麼就執行事務的中斷。

1.發送中斷請求 協調者向所有參與者發送abort請求。2.中斷事務 參與者收到來自協調者的abort請求之後（或逾時之後，仍未收到協調者的請求），執行事務的中斷。

doCommit階段

該階段進行真正的事務送出，也可以分為以下兩種情況。

執行送出

1.發送送出請求 協調接在preCommit階段收到參與者發送的ACK響應，那麼他将從預送出狀态進入到送出狀态。并向所有參與者發送doCommit請求。2.事務送出 參與者接收到doCommit請求之後，執行正式的事務送出。并在完成事務送出之後釋放所有事務資源。3.響應回報 事務送出完之後，向協調者發送Ack響應。4.完成事務 協調者接收到所有參與者的ack響應之後，完成事務。

中斷事務協調者在preCommit階段沒有接收到參與者發送的ACK響應（可能是接受者發送的不是ACK響應，也可能響應逾時），那麼就會執行中斷事務。

1.發送中斷請求 協調者向所有參與者發送abort請求2.事務復原 參與者接收到abort請求之後，利用其在階段二記錄的undo資訊來執行事務的復原操作，并在完成復原之後釋放所有的事務資源。3.回報結果 參與者完成事務復原之後，向協調者發送ACK消息4.中斷事務 協調者接收到參與者回報的ACK消息之後，執行事務的中斷。

在doCommit階段，如果參與者無法及時接收到來自協調者的doCommit或者abort請求時，會在等待逾時之後，會繼續進行事務的送出。（其實這個應該是基于機率來決定的，當進入第三階段時，說明參與者在第二階段已經收到了PreCommit請求，那麼協調者産生PreCommit請求的前提條件是他在第二階段開始之前，收到所有參與者的CanCommit響應都是Yes。（一旦參與者收到了PreCommit，意味他知道大家其實都同意修改了）是以，一句話概括就是，當進入第三階段時，由于網絡逾時等原因，雖然參與者沒有收到commit或者abort響應，但是他有理由相信：成功送出的幾率很大。）

小結

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

三階段送出也不完美。但是它比兩階段好。

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

•協調者出錯，參與者也出錯；•協調者出錯，參與者不出錯；•協調者不出錯，參與者出錯；•協調者不出錯，參與者也不出錯。

顯然第4種不是問題。是以實際上隻有3個問題。而問題2可以通過簡單地NEW一個新的協調者來解決。問題3的錯則顯然正是兩階段送出協定的解決目标，是以也沒有問題。有問題的隻有協調者出錯，參與者也出錯的問題。

無論2pc還是3pc隻有在以下的情況才會出現資料不一緻性：協調者挂了，備份協調者恢複協定時，某個參與者挂了，在剩下參與者都是“YES”的狀态下, 備份協調者沒法分辨挂了的參與者狀态。（此處挂了可了解為當機或者時網絡連不上）

接下來将對上面段落使用一些替代詞：協調者A，備份協調者B，挂了參與者C

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

Paxos算法

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

Paxos在原作者的《Paxos Made Simple》中内容是比較精簡的：

第一階段

（a） 提議者選擇一個提議編号n，并向大多數接受者發送一個編号n的準備請求。

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

第二階段

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

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

翻譯一下：

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

Paxos是第一個被證明的共識算法，原理基于兩階段送出并進行擴充。算法中将節點分為三種類型：

•倡議者proposer：送出一個提案，等待大家準許為結案，往往是用戶端擔任。•接受者acceptor：負責對提案進行投票，往往伺服器擔任。提議超過半數的接受者投票及被選中。•學習者learner：被告知提案結果，并與之統一，不參與投票過程。用戶端和服務端都可擔任。

每個節點在協定中可以擔任多個角色。

Paxos的特點：

•一個或多個節點可以提出提議。•系統針對所有提案中的某個提案必須達成一緻。•最多隻能對一個确定的提案達成一緻。•隻要超過半數的節點存活且可互相通信，整個系統一定能達成一緻狀态。

第一階段A

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

第一階段B

Acceptor接收到Prepare（n）請求，若提議編号n比之前接收的Prepare請求都要大，則承諾将不會接收提議編号比n小的提議，并且帶上之前Accept的提議中編号小于n的最大的提議，否則不予理會。

第二階段A

Proposer得到了多數Acceptor的承諾後，如果沒有發現有一個Acceptor接受過一個值，那麼向所有的Acceptor發起自己的值和提議編号n，否則，從所有接受過的值中選擇對應的提議編号最大的，作為提議的值，提議編号仍然為n。

第二階段B

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

Paxos 例子說明

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

例子：

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

場景 1：

假設 A1 說：稅率應該是 10%。而此時隻有他一個人提這個建議。如下圖：

很完美，沒有任何人和他競争提案，他的這個提案毫無阻撓的通過了。A2 - A5 都會回應他：我們收到了你的提案，等待最終的準許。而 A1 在收到 2 份回複後，就可以釋出最終的決議：稅率定位 10%，不用再讨論了。

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

場景 2：

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

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

現在，A1 ，A2，A3 收到了 A1 的提案，A3，A4， A5 收到 A5 的提案，按照 Paxos 的協定，A1，A2，A4，A5 4個侍從将接受他們的提案，侍從拿着回複：我已收到你的提案，等待最終準許 回到提案者那裡。

而 A3 的行為将決定準許哪一個。

當 A3 同時收到了 A1 和 A5 的請求，該如何抉擇呢？不同的抉擇将會導緻不同的結果。

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

場景2：情況一

假設 A1 的提案先送到 A3 那裡，并且 A3 接受了該提案并回複了侍從。這樣，A1 加上 A2 加上 A3，構成了多數派，成功确定了稅率為 10%。而 A5 的侍從由于路上喝酒喝多了，晚到了一天，等他到了，稅率已經确定了，A3 回複 A5：兄弟，你來的太晚了，稅率已經定好了，不用折騰了，聽 A1 的吧。

如下圖：

場景2：情況二

依然假設 A1 的提案先送到 A3 處，但是這次 A5 的侍從不是放假了，隻是中途耽擱了一會。這次, A3 依然會将"接受"回複給 A1 .但是在決議成型之前它又收到了 A5 的提案。這時協定根據 A5 的身份地位有兩種處理方式，但結果相同。

•當 A5 地位很高，例如 CEO，就回複 A5：我已收到您的提案，等待最終準許，但是您之前有人提出将稅率定為10%,請明察。•當 A5 沒地位，普通碼農一個，直接不回複。等待 A1 廣播：稅率定為 10% 啦！！！

如下圖：

場景2：情況三

在這個情況中，我們将看見，根據提案的時間及提案者的權勢決定是否應答是有意義的。在這裡，時間和提案者的權勢就構成了給提案編号的依據。這樣的編号符合"任何兩個提案之間構成偏序"的要求。

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

在這種情況下，已經回答 A1 的 A2 發現有比 A1 更有權勢的 A5 提出了稅率 20% 的新提案，于是回複A5說：我已收到您的提案，等待最終準許。

而回複 A5 的 A3 發現新的提案者A1是個小人物，沒地位不予應答。

此時，A5 得到了 A2，A3 的回複，于是 A5 說：稅率定為 20%，别再讨論了。

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

這個時候，其他的議員就告訴他：哥們，已經定為 20% 了，别折騰了。洗洗繼續睡吧。

整個過程如下圖：

Paxos的死鎖情況

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

小結：

Paxos協定最終解決什麼問題？

當一個提議被多數派接受後，這個提議對應的值被Chosen（標明），一旦有一個值被Chosen，那麼隻要按照協定的規則繼續互動，後續被Chosen的值都是同一個值，也就是這個Chosen值的一緻性問題。

Paxos 的目标：保證最終有一個提案會被標明，當提案被標明後，其他議員最終也能擷取到被標明的提案。

Paxos 協定用來解決的問題可以用一句話來簡化：将所有節點都寫入同一個值，且被寫入後不再更改。

Raft一緻性算法

Raft算法是Paxos算法的一種簡化實作。

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

•follow:所有節點都以follower的狀态開始，如果沒有收到leader消息則會變成candidate狀态。•candidate：會向其他節點拉選票，如果得到大部分的票則成為leader，這個過程是Leader選舉。•leader：所有對系統的修改都會先經過leader。

其有兩個基本過程：

•Leader選舉：每個candidate随機經過一定時間都會提出選舉方案，最近階段中的票最多者被選為leader。•同步log：leader會找到系統中log（各種事件的發生記錄）最新的記錄，并強制所有的follow來重新整理到這個記錄。

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

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

http://thesecretlivesofdata.com/raft/

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

假設将軍中沒有叛軍，信使的資訊可靠但有可能被暗殺的情況下，将軍們如何達成一緻性決定？

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

2.選主 Leader Election

2.1 正常情況下選主

假設現在有如圖5個節點，5個節點一開始的狀态都是 Follower。

在一個節點倒計時結束 (Timeout) 後，這個節點的狀态變成 Candidate 開始選舉，它給其他幾個節點發送選舉請求 (RequestVote)

其他四個節點都傳回成功，這個節點的狀态由 Candidate 變成了 Leader，并在每個一小段時間後，就給所有的 Follower 發送一個 Heartbeat 以保持所有節點的狀态，Follower 收到 Leader 的 Heartbeat 後重設 Timeout。

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

2.2 Leader 出故障情況下的選主

一開始已經有一個 Leader，所有節點正常運作。

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

4個節點的選主過程和5個節點的類似，在選出一個新的 Leader 後，原來的 Leader 恢複了又重新加入了，這個時候怎麼處理？在 Raft 裡，第幾輪選舉是有記錄的，重新加入的 Leader 是第一輪選舉 (Term 1) 選出來的，而現在的 Leader 則是 Term 2，所有原來的 Leader 會自覺降級為 Follower

2.3 多個 Candidate 情況下的選主

假設一開始有4個節點，都還是 Follower。

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

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

兩個 Candidate 會分别給另外一個還沒有給自己投票的 Follower 發送投票請求。

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

這時，兩個節點的狀态是 Candidate，兩個是 Follower，但是他們的倒計時器仍然在運作，最先 Timeout 的那個節點會進行發起新一輪 Term 3 的投票。

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

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

兩個 Follower 已經投完票了，拒絕了這個 Candidate 的投票請求。

Leader 進行 Heartbeat， Candidate 收到後狀态自動轉為 Follower，完成選主。

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

3. 複制日志 Log Replication

3.1 正常情況下複制日志

Raft 在實際應用場景中的一緻性更多的是展現在不同節點之間的資料一緻性，用戶端發送請求到任何一個節點都能收到一緻的傳回，當一個節點出故障後，其他節點仍然能以已有的資料正常進行。在選主之後的複制日志就是為了達到這個目的。

一開始，Leader 和 兩個 Follower 都沒有任何資料。

用戶端發送請求給 Leader，儲存資料 “sally”，Leader 先将資料寫在本地日志，這時候資料還是 Uncommitted (還沒最終确認，紅色表示)

Leader 給兩個 Follower 發送 AppendEntries 請求，資料在 Follower 上沒有沖突，則将資料暫時寫在本地日志，Follower 的資料也還是 Uncommitted。

Follower 将資料寫到本地後，傳回 OK。Leader 收到後成功傳回，隻要收到的成功的傳回數量超過半數 (包含Leader)，Leader 将資料 “sally” 的狀态改成 Committed。( 這個時候 Leader 就可以傳回給用戶端了)

Leader 再次給 Follower 發送 AppendEntries 請求，收到請求後，Follower 将本地日志裡 Uncommitted 資料改成 Committed。這樣就完成了一整個複制日志的過程，三個節點的資料是一緻的，

3.2 Network Partition 情況下進行複制日志

在 Network Partition 的情況下，部分節點之間沒辦法互相通信，Raft 也能保證在這種情況下資料的一緻性。

一開始有 5 個節點處于同一網絡狀态下。

Network Partition 将節點分成兩邊，一邊有兩個節點，一邊三個節點。

兩個節點這邊已經有 Leader 了，來自用戶端的資料 “bob” 通過 Leader 同步到 Follower。

因為隻有兩個節點，少于3個節點，是以 “bob” 的狀态仍是 Uncommitted。是以在這裡，伺服器會傳回錯誤給用戶端

另外一個 Partition 有三個節點，進行重新選主。用戶端資料 “tom” 發到新的 Leader，通過和上節網絡狀态下相似的過程，同步到另外兩個 Follower。

因為這個 Partition 有3個節點，超過半數，是以資料 “tom” 都 Commit 了。

網絡狀态恢複，5個節點再次處于同一個網絡狀态下。但是這裡出現了資料沖突 “bob" 和 “tom"

三個節點的 Leader 廣播 AppendEntries

兩個節點 Partition 的 Leader 自動降級為 Follower，因為這個 Partition 的資料 “bob” 沒有 Commit，傳回給用戶端的是錯誤，用戶端知道請求沒有成功，是以 Follower 在收到 AppendEntries 請求時，可以把 “bob“ 删除，然後同步 ”tom”，通過這麼一個過程，就完成了在 Network Partition 情況下的複制日志，保證了資料的一緻性。

小結

Raft 是能夠實作分布式系統強一緻性的算法，每個系統節點有三種狀态 Follower，Candidate，Leader。實作 Raft 算法兩個最重要的事是：選主和複制日志。

一緻性協定之 ZAB

什麼是 ZAB 協定？ZAB 協定介紹

ZAB 協定全稱：Zookeeper Atomic Broadcast（Zookeeper 原子廣播協定）。

ZAB 協定是為分布式協調服務 Zookeeper 專門設計的一種支援 崩潰恢複 和 原子廣播 協定。

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

基于該協定，Zookeeper 實作了一種 主備模式 的系統架構來保持叢集中各個副本之間資料一緻性。其中所有用戶端寫入資料都是寫入到 主程序（稱為 Leader）中，然後，由 Leader 複制到備份程序（稱為 Follower）中。【涉及到2PC單點問題的解決，崩潰恢複】

選擇機制中的概念

1、Serverid：伺服器ID

比如有三台伺服器，編号分别是1,2,3。

編号越大在選擇算法中的權重越大。

2、Zxid：資料ID

伺服器中存放的最大資料ID。【zxid實際上是一個64位的數字，高32位是epoch（時期; 紀元; 世; 新時代）用來辨別leader是否發生改變，如果有新的leader産生出來，epoch會自增，低32位用來遞增計數。】

值越大說明資料越新，在選舉算法中資料越新權重越大。

3、Epoch：邏輯時鐘

或者叫投票的次數，同一輪投票過程中的邏輯時鐘值是相同的。每投完一次票這個資料就會增加，然後與接收到的其它伺服器傳回的投票資訊中的數值相比，根據不同的值做出不同的判斷。

4、Server狀态：選舉狀态

LOOKING，競選狀态。

FOLLOWING，随從狀态，同步leader狀态，參與投票。

OBSERVING，觀察狀态,同步leader狀态，不參與投票。

LEADING，上司者狀态。

選舉消息内容

在投票完成後，需要将投票資訊發送給叢集中的所有伺服器，它包含如下内容：伺服器ID、資料ID、邏輯時鐘、選舉狀态。

zookeeper是如何保證事務的順序一緻性的（保證消息有序） 在整個消息廣播中，Leader會将每一個事務請求轉換成對應的 proposal 來進行廣播，并且在廣播 事務Proposal 之前，Leader伺服器會首先為這個事務Proposal配置設定一個全局單遞增的唯一ID，稱之為事務ID（即zxid），由于Zab協定需要保證每一個消息的嚴格的順序關系，是以必須将每一個proposal按照其zxid的先後順序進行排序和處理。

消息廣播

1）在zookeeper叢集中，資料副本的傳遞政策就是采用消息廣播模式。zookeeper中農資料副本的同步方式與二段送出相似，但是卻又不同。二段送出要求協調者必須等到所有的參與者全部回報ACK确認消息後，再發送commit消息。要求所有的參與者要麼全部成功，要麼全部失敗。二段送出會産生嚴重的阻塞問題。

2）Zab協定中 Leader 等待 Follower 的ACK回報消息是指“隻要半數以上的Follower成功回報即可，不需要收到全部Follower回報”。

消息廣播具體步驟

1）用戶端發起一個寫操作請求。

2）Leader 伺服器将用戶端的請求轉化為事務 Proposal 提案，同時為每個 Proposal 配置設定一個全局的ID，即zxid。

3）Leader 伺服器為每個 Follower 伺服器配置設定一個單獨的隊列，然後将需要廣播的 Proposal 依次放到隊列中取，并且根據 FIFO 政策進行消息發送。

4）Follower 接收到 Proposal 後，會首先将其以事務日志的方式寫入本地磁盤中，寫入成功後向 Leader 回報一個 Ack 響應消息。

5）Leader 接收到超過半數以上 Follower 的 Ack 響應消息後，即認為消息發送成功，可以發送 commit 消息。

6）Leader 向所有 Follower 廣播 commit 消息，同時自身也會完成事務送出。Follower 接收到 commit 消息後，會将上一條事務送出。

zookeeper 采用 Zab 協定的核心，就是隻要有一台伺服器送出了 Proposal，就要確定所有的伺服器最終都能正确送出 Proposal。這也是 CAP/BASE 實作最終一緻性的一個展現。

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

崩潰恢複

崩潰恢複主要包括兩部分：Leader選舉 和 資料恢複

zookeeper是如何選取主leader的？

當leader崩潰或者leader失去大多數的follower，這時zk進入恢複模式，恢複模式需要重新選舉出一個新的leader，讓所有的Server都恢複到一個正确的狀态。

Zookeeper選主流程 選舉流程詳述

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

二、發送投票資訊

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

b、投票資訊包含 ：所選舉leader的Serverid，Zxid，Epoch。Epoch會随着選舉輪數的增加而遞增。

三、接收投票資訊

1、如果伺服器B接收到伺服器A的資料（伺服器A處于選舉狀态(LOOKING 狀态)

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

a）如果發送過來的邏輯時鐘Epoch大于目前的邏輯時鐘。首先，更新本邏輯時鐘Epoch，同時清空本輪邏輯時鐘收集到的來自其他server的選舉資料。然後，判斷是否需要更新目前自己的選舉leader Serverid。判斷規則rules judging：儲存的zxid最大值和leader Serverid來進行判斷的。先看資料zxid,資料zxid大者勝出;其次再判斷leader Serverid,leader Serverid大者勝出；然後再将自身最新的選舉結果(也就是上面提到的三種資料（leader Serverid，Zxid，Epoch）廣播給其他server)

b）如果發送過來的邏輯時鐘Epoch小于目前的邏輯時鐘。說明對方server在一個相對較早的Epoch中，這裡隻需要将本機的三種資料（leader Serverid，Zxid，Epoch）發送過去就行。

c）如果發送過來的邏輯時鐘Epoch等于目前的邏輯時鐘。再根據上述判斷規則rules judging來選舉leader ，然後再将自身最新的選舉結果(也就是上面提到的三種資料（leader Serverid，Zxid，Epoch）廣播給其他server)。

2）其次，判斷伺服器是不是已經收集到了所有伺服器的選舉狀态：若是，根據選舉結果設定自己的角色(FOLLOWING還是LEADER)，退出選舉過程就是了。

最後，若沒有收集到所有伺服器的選舉狀态：也可以判斷一下根據以上過程之後最新的選舉leader是不是得到了超過半數以上伺服器的支援,如果是,那麼嘗試在200ms内接收一下資料,如果沒有新的資料到來,說明大家都已經預設了這個結果,同樣也設定角色退出選舉過程。

2、 如果所接收伺服器A處在其它狀态（FOLLOWING或者LEADING）。

a)邏輯時鐘Epoch等于目前的邏輯時鐘，将該資料儲存到recvset。此時Server已經處于LEADING狀态，說明此時這個server已經投票選出結果。若此時這個接收伺服器宣稱自己是leader, 那麼将判斷是不是有半數以上的伺服器選舉它，如果是則設定選舉狀态退出選舉過程。

b) 否則這是一條與目前邏輯時鐘不符合的消息，那麼說明在另一個選舉過程中已經有了選舉結果，于是将該選舉結果加入到outofelection集合中，再根據outofelection來判斷是否可以結束選舉,如果可以也是儲存邏輯時鐘，設定選舉狀态，退出選舉過程。【recvset：用來記錄選票資訊，以友善後續統計;outofelection：用來記錄選舉邏輯之外的選票，例如當一個伺服器加入zookeeper叢集時，因為叢集已經存在，不用重新選舉，隻需要在滿足一定條件下加入叢集即可。】

描述Leader選擇過程中的狀态變化，這是假設全部執行個體中均沒有資料，假設伺服器啟動順序分别為：A,B,C。

Zab 協定如何保證資料一緻性

假設兩種異常情況：1、一個事務在 Leader 上送出了，并且過半的 Folower 都響應 Ack 了，但是 Leader 在 Commit 消息發出之前挂了。2、假設一個事務在 Leader 提出之後，Leader 挂了。

要確定如果發生上述兩種情況，資料還能保持一緻性，那麼 Zab 協定選舉算法必須滿足以下要求：

Zab 協定崩潰恢複要求滿足以下兩個要求：1）確定已經被 Leader 送出的 Proposal 必須最終被所有的 Follower 伺服器送出。2）確定丢棄已經被 Leader 提出的但是沒有被送出的 Proposal。

根據上述要求 Zab協定需要保證選舉出來的Leader需要滿足以下條件：1）新選舉出來的 Leader 不能包含未送出的 Proposal 。即新選舉的 Leader 必須都是已經送出了 Proposal 的 Follower 伺服器節點。2）新選舉的 Leader 節點中含有最大的 zxid 。這樣做的好處是可以避免 Leader 伺服器檢查 Proposal 的送出和丢棄工作。

Zab 如何資料同步

1）完成 Leader 選舉後（新的 Leader 具有最高的zxid），在正式開始工作之前（接收事務請求，然後提出新的 Proposal），Leader 伺服器會首先确認事務日志中的所有的 Proposal 是否已經被叢集中過半的伺服器 Commit。

2）Leader 伺服器需要確定所有的 Follower 伺服器能夠接收到每一條事務的 Proposal ，并且能将所有已經送出的事務 Proposal 應用到記憶體資料中。等到 Follower 将所有尚未同步的事務 Proposal 都從 Leader 伺服器上同步過啦并且應用到記憶體資料中以後，Leader 才會把該 Follower 加入到真正可用的 Follower 清單中。

Zab 資料同步過程中，如何處理需要丢棄的 Proposal

在 Zab 的事務編号 zxid 設計中，zxid是一個64位的數字。

其中低32位可以看成一個簡單的單增計數器，針對用戶端每一個事務請求，Leader 在産生新的 Proposal 事務時，都會對該計數器加1。而高32位則代表了 Leader 周期的 epoch 編号。

epoch 編号可以了解為目前叢集所處的年代，或者周期。每次Leader變更之後都會在 epoch 的基礎上加1，這樣舊的 Leader 崩潰恢複之後，其他Follower 也不會聽它的了，因為 Follower 隻服從epoch最高的 Leader 指令。

每當選舉産生一個新的 Leader ，就會從這個 Leader 伺服器上取出本地事務日志充最大編号 Proposal 的 zxid，并從 zxid 中解析得到對應的 epoch 編号，然後再對其加1，之後該編号就作為新的 epoch 值，并将低32位數字歸零，由0開始重新生成zxid。

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

基于以上政策:

當一個包含了上一個 Leader 周期中尚未送出過的事務 Proposal 的伺服器啟動時，當這台機器加入叢集中，以 Follower 角色連上 Leader 伺服器後，Leader 伺服器會根據自己伺服器上最後送出的 Proposal 來和 Follower 伺服器的 Proposal 進行比對，比對的結果肯定是 Leader 要求 Follower 進行一個回退操作，回退到一個确實已經被叢集中過半機器 Commit 的最新 Proposal。

小結

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

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

而支援崩潰恢複後資料準确性的就是資料同步了，資料同步基于事務的 ZXID 的唯一性來保證。通過 + 1 操作可以辨識事務的先後順序。

NWR模型

Amazon Dynamo的NWR模型。NWR模型把CAP的選擇權交給了使用者，讓使用者自己的選擇你的CAP中的哪兩個。

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

也就是說，每次讀取，都至少讀取到一個最新的版本。進而不會讀到一份舊資料。當我們需要高可寫的環境的時候，我們可以配置W = 1 如果N=3 那麼R = 3。這個時候隻要寫任何節點成功就認為成功，但是讀的時候必須從所有的節點都讀出資料。如果我們要求讀的高效率，我們可以配置 W=N R=1。這個時候任何一個節點讀成功就認為成功，但是寫的時候必須寫所有三個節點成功才認為成功。

NWR模型的一些設定會造成髒資料的問題，因為這很明顯不是像Paxos一樣是一個強一緻的東西，是以，可能每次的讀寫操作都不在同一個結點上，于是會出現一些結點上的資料并不是最新版本，但卻進行了最新的操作。

是以，Amazon Dynamo引了資料版本的設計。也就是說，如果你讀出來資料的版本是v1，當你計算完成後要回填資料後，卻發現資料的版本号已經被人更新成了v2，那麼伺服器就會拒絕你。版本這個事就像“樂觀鎖”一樣。

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

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

于是，Dynamo引入了Vector Clock（矢量鐘）這個設計。這個設計讓每個結點各自記錄自己的版本資訊，也就是說，對于同一個資料，需要記錄兩個事：1）誰更新的我，2）我的版本号是什麼。

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

1）一個寫請求，第一次被節點A處理了。節點A會增加一個版本資訊(A，1)。我們把這個時候的資料記做D1(A，1)。然後另外一個對同樣key的請求還是被A處理了于是有D2(A，2)。這個時候，D2是可以覆寫D1的，不會有沖突産生。

2）現在我們假設D2傳播到了所有節點(B和C)，B和C收到的資料不是從客戶産生的，而是别人複制給他們的，是以他們不産生新的版本資訊，是以現在B和C所持有的資料還是D2(A，2)。于是A，B，C上的資料及其版本号都是一樣的。

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

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

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

•A結點：D2(A,2)•B結點：D3(A,2; B,1);•C結點：D4(A,2; C,1)

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

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

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