1. 前言

過去, Paxos一直是分布式協(xié)議的標(biāo)準(zhǔn)，但是Paxos難于理解，更難以實現(xiàn)，Google的分布式鎖系統(tǒng)Chubby作為Paxos實現(xiàn)曾經(jīng)遭遇到很多坑。

來自Stanford的新的分布式協(xié)議研究稱為Raft，它是一個為真實世界應(yīng)用建立的協(xié)議，主要注重協(xié)議的落地性和可理解性。

在了解Raft之前，我們先了解Consensus一致性這個概念，它是指多個服務(wù)器在狀態(tài)達成一致，但是在一個分布式系統(tǒng)中，因為各種意外可能，有的服務(wù)器可能會崩潰或變得不可靠，它就不能和其他服務(wù)器達成一致狀態(tài)。這樣就需要一種Consensus協(xié)議，一致性協(xié)議是為了確保容錯性，也就是即使系統(tǒng)中有一兩個服務(wù)器當(dāng)機，也不會影響其處理過程。

為了以容錯方式達成一致，我們不可能要求所有服務(wù)器100%都達成一致狀態(tài)，只要超過半數(shù)的大多數(shù)服務(wù)器達成一致就可以了，假設(shè)有N臺服務(wù)器，N/2 +1 就超過半數(shù)，代表大多數(shù)了。

Paxos和Raft都是為了實現(xiàn)Consensus一致性這個目標(biāo)，這個過程如同選舉一樣，參選者需要說服大多數(shù)選民(服務(wù)器)投票給他，一旦選定后就跟隨其操作。Paxos和Raft的區(qū)別在于選舉的具體過程不同。

2. Paxos

Paxos是能夠基于一大堆完全不可靠的網(wǎng)絡(luò)條件下卻能可靠確定地實現(xiàn)共識一致性的算法。也就是說：它允許一組不一定可靠的處理器（服務(wù)器）在某些條件得到滿足情況下就能達成確定的安全的共識，如果條件不能滿足也確保這組處理器（服務(wù)器）保持一致。

2.1 共識

具體來說是這樣：分布式系統(tǒng)中由于網(wǎng)絡(luò)之間通訊可能會中斷，雖然概率很低，但是沒有100%完美的網(wǎng)絡(luò)因此，依靠網(wǎng)絡(luò)通訊的計算機之間要達成共識就比較困難，假設(shè)有X, Y和Z三臺計算機謀劃在周一攻擊人類世界，它們的攻擊計劃是只要所有計算機可用于戰(zhàn)斗時就一起進行攻擊，不落下任何一臺機器，但是當(dāng)他們決定具體什么時間開始攻擊時，在這個關(guān)鍵問題上往往會出錯。

一個基本問題是，每臺機器都有自己的攻擊時間建議，計算機X可以建議在08:00時間，因為這個時間正是周一早晨，而人們剛剛過完狂歡的周末休息天，但是計算機Z認(rèn)為13:00比較好，理由當(dāng)然也有一大堆，讓這三臺計算機基于某個時刻達成共識是非常困難的，因此，也給人類反擊留下了機會。

另外一個情況是，這三臺計算機是位于世界不同的位置，之間通訊或許通過電纜或者其他不太可靠的網(wǎng)絡(luò)設(shè)備通訊，如果X建議在08:00，它必須確認(rèn)它的這個建議能夠到達活著的Y和Z，以免一個人戰(zhàn)斗。

問題是：我們不能準(zhǔn)確地知道某個計算機的延遲的原因：是因為性能慢了還是已經(jīng)是徹底死機不能用？

那么，X怎么知道其他兩個計算機是可用的呢？也就是說，當(dāng)X和其他兩個計算機通訊發(fā)現(xiàn)得到響應(yīng)要過很長時間，它不能確定這兩臺計算機到底還能不能繼續(xù)活下去，也許這次通訊有延遲了，下一次它們又活過來了沒有延遲了，也許下次延遲更長了一點，也許下次延遲稍微短了一點，這些隨機概率問題使得X不能確定Y和Z到底是出了什么問題造成延遲的，是因為處理了某個特別耗費CPU的任務(wù)還是因為死鎖等原因？當(dāng)然，有些天真的設(shè)計者會說，只要我們將性能監(jiān)控到位，如果延遲超過一定時間，我們?nèi)斯そ槿敫嬖VX確切情況就可以，那么這種人工介入的分布式系統(tǒng)不是一個天然自洽的自動化系統(tǒng)了，不在我們討論范圍之內(nèi)，而且這樣的系統(tǒng)會讓人疲于奔命。

因為X不能確定Y或Z是否可用，所以X僅僅只能和Y與Z中一臺基于攻擊時間達成共識，就無法完全三臺機器全部投入戰(zhàn)斗的計劃。注意的是，X Y Z三臺中任何一臺都可能會出現(xiàn)延遲，這就造成了三臺機器之間任何通訊都是無法確認(rèn)可靠的，比如X發(fā)出消息給Z，Z確認(rèn)后回執(zhí)給X，但是這段時間X突然死機了，那么Z要等待X多長時間才能知道它收到確認(rèn)呢？還是再次等待X回復(fù)確認(rèn)的確認(rèn)，這樣無限循環(huán)下去也不能解決它們之間通訊可能出現(xiàn)隨機不可靠的問題。

所有關(guān)鍵問題在于：由于這三臺機器之間通訊是無法保證100%可靠，它們就不能就任何事情達成共識。

下面以分布式拍賣案例說明這種情況以及Paxos的基本原理：

在傳統(tǒng)拍賣場景中，價高者先得，這些拍賣者都是在同一個房間，彼此能夠直接看得到對方的報價，如果我們假設(shè)分布式拍賣是將這些拍賣者分離到不同的地方，這樣我們可以用拍賣者之間的聯(lián)系模擬分布式計算機之間的通訊。

假設(shè)拍賣者各自在自己家里拍賣，通過郵局信件發(fā)出自己的拍賣信息，拍賣者之間除非等到郵局投遞人告訴他們彼此之間的報價，否則是無法知道對方報價的。如果郵局信件投遞這個環(huán)節(jié)出了問題，投遞速度慢了甚至無法投遞了，那么整個拍賣程序就無法繼續(xù)進行下去。

2.2 Paxos解決共識思路

Paxos是一個解決共識問題的算法，現(xiàn)實中Paxos的實現(xiàn)以及成為一些世界級軟件的心臟，如Cassandra, Google的 Spanner數(shù)據(jù)庫, 分布式鎖服務(wù)Chubby. 一個被Paxos管理的系統(tǒng)實際上談?wù)摰氖侵?狀態(tài)和跟蹤等問題，其目標(biāo)是建造更高可用性和強一致性的分布式系統(tǒng)。

Paxos完成一次寫操作需要兩次來回，分別是prepare/promise, 和 propose/accept：

寫操作

第一次由提交者Leader向所有其他服務(wù)器發(fā)出prepare消息請求準(zhǔn)備，所有服務(wù)器中大多數(shù)如果回復(fù)諾言承諾就表示準(zhǔn)備好了，可以接受寫入；第二次提交者向所有服務(wù)器發(fā)出正式建議propose，所有服務(wù)器中大多數(shù)如果回復(fù)已經(jīng)接收就表示成功了。

為了詳細(xì)描述這個兩段過程，首先讓我們定義一下我們將使用的一些名詞術(shù)語：

• 一個流程是系統(tǒng)中計算機的一個人們使用有關(guān)復(fù)制或節(jié)點等詞語表達，都差不多。
• 一個客戶端是屬于系統(tǒng)中一個成員的計算機，但是詢問系統(tǒng)值是什么或者要求系統(tǒng)獲取一個新的值。

Paxos構(gòu)建分布式數(shù)據(jù)庫的小片段: 它僅僅實現(xiàn)流程將一個新的東西精確地寫入系統(tǒng)中，流程是由Paxos的一個實例管治，可以失敗或者不知道任何東西、或者大多數(shù)流程都知道一個同樣的值，這就是共識，Paxos并不真的告訴我們?nèi)绾斡盟鼇順?gòu)建數(shù)據(jù)庫或類似的東西，它只是負(fù)責(zé)獨立節(jié)點之間通訊的流程， 這些流程服務(wù)器會基于一個新值執(zhí)行決定，Paxos會存儲一個值數(shù)據(jù)，只是一次性的，一旦你第一次設(shè)置以后就不能再改變它。

2.3 Paxos讀操作

其實Paxos精華是在寫操作，將讀操作放在寫操作前面講解，是著重Paxos以大多數(shù)服務(wù)器達成共識為重要標(biāo)志，通過讀取判斷是否達成共識這一狀態(tài)。

為了從Paxos系統(tǒng)中讀取一個值數(shù)據(jù)，客戶端會請求讀取所有流程中存儲的當(dāng)前值，然后從大多數(shù)流程服務(wù)器中獲得這個值，如果數(shù)量湊不夠大多數(shù)或者沒有足夠的客戶端響應(yīng)，讀取操作失敗，下面圖示你會看到一個客戶端詢問其他節(jié)點他們的值是多少，這些節(jié)點返回值給客戶端，當(dāng)客戶端獲得了大多數(shù)節(jié)點的響應(yīng)，返回的值都是同樣的，它就算成功地讀操作了，并順便保存讀結(jié)果。

Paxos讀操作

與單節(jié)點系統(tǒng)(只有一臺服務(wù)器)相比這有些奇怪，這兩個系統(tǒng)中，客戶端都需要觀察系統(tǒng)已決定狀態(tài)，但是在非分布式系統(tǒng)中像MySQL或一個memcached服務(wù)器中, 客戶端只需直接向標(biāo)準(zhǔn)的狀態(tài)存儲的服務(wù)器地址獲取狀態(tài)即可，在簡單的Paxos中, 客戶端也是同樣的方式觀察狀態(tài)，但是因為并沒有標(biāo)準(zhǔn)的狀態(tài)存儲的服務(wù)器地址，它需要詢問所有的成員，以便能夠確定僅有一個會報告值數(shù)據(jù)，實際上是大多數(shù)節(jié)點都持有的值數(shù)據(jù)，如果客戶端詢問一個節(jié)點，有可能這個節(jié)點流程已經(jīng)過期，得到了錯誤的值數(shù)據(jù)，流程失效過期的原因有很多：由于不可靠的網(wǎng)絡(luò)導(dǎo)致本應(yīng)送達到它們的消息丟失了；或者他們也許當(dāng)機然后使用了一個過期狀態(tài)恢復(fù)；或者算法還在運行計算中，流程并沒有正好得到消息等等。在現(xiàn)實中使用Paxos實現(xiàn)時，其實不需要每個節(jié)點都進行一次讀取，會有更好的讀取方式，但是他們都是拓展的原始 Paxos 算法。

2.4 Paxos寫操作

當(dāng)一個客戶端要求寫入系統(tǒng)一個新值時，讓我們看看Paxos讓我們集群的流程都做了什么？下面的過程都是只有一個值的寫入，最終我們能用這個流程作為原始數(shù)據(jù)，允許值數(shù)據(jù)在彼此之間一個個設(shè)置，但是基本的Paxos算法管治了一個新值數(shù)據(jù)的寫操作流程， 然后做重復(fù)的事情。

Paxos寫操作

首先Paxos管理的系統(tǒng)中一個客戶端要求寫入一個新值，客戶端這里如圖所示是紅圈，其它流程是藍圈， Paxos能保證客戶端發(fā)送它們的寫請求到Paxos集群中任何成員, 這里演示中客戶端隨機挑選流程中任意一個，這種方式是重要且巧妙的，意味著沒有任何單點風(fēng)險，意味著我們的Paxos管治系統(tǒng)能繼續(xù)保持在線可用，無論任何一個節(jié)點當(dāng)機或其他不可用原因無響應(yīng)。如果我們設(shè)計一個特定節(jié)點作為“推薦人proposer”或者 "the master" 等, 如果這個主節(jié)點死機，那么整個系統(tǒng)就崩潰了。

當(dāng)寫請求被接受后，Paxos流程會接受這個寫新值到系統(tǒng)中請求“建議”， “建議”是Paxos中一個正式概念: 向一個Paxos管治的系統(tǒng)建議可能會成功或失敗，需要步驟來確保共識能夠達成維系，這個建議以準(zhǔn)備消息從那些與客戶端連接的流程節(jié)點們被發(fā)往整個系統(tǒng)。

2.5 序列號

這個準(zhǔn)備消息保存在被建議的值數(shù)據(jù)中，它們也稱為序列號sequence number，序列號是由建議流程產(chǎn)生的，它定義了接受流程應(yīng)該準(zhǔn)備接受帶有序列號的建議，這個序列號是關(guān)鍵: 它用于表明新舊建議之間的區(qū)別，如果兩個流程試圖獲得需要設(shè)置一個值，Paxos認(rèn)為最后一個流程應(yīng)該有優(yōu)先權(quán)，這樣讓流程分辨哪個是最后一個，這樣它就能設(shè)置最新的值。

這些接受的流程能夠進行在系統(tǒng)中關(guān)鍵的檢查：這個在到來的準(zhǔn)備消息中序列號是我見過的最高級別嗎？如果是，那就很cool, 我能準(zhǔn)備好接受將要到來的值數(shù)據(jù)，那就不要管之前聽到的任何其他值數(shù)據(jù)了，如下圖所示：客戶端每隔一段向一個流程建議一個新值，這個流程發(fā)送準(zhǔn)備消息給其他流程，然后那些流程注意到這是一個成功的更高的超過舊的新序列號，然后就放手那些舊建議。

這里有一個順序的設(shè)計(先發(fā)送準(zhǔn)備消息)，這是為避免單點風(fēng)險，如果沒有這個順序，Paxos中成員就無法分辨哪個建議是他們可以有信心地準(zhǔn)備接受的。

我們不能想象有不是按照如下步驟的，另外不同的共識算法：首先發(fā)送第一個消息詢問其他流程，以確保將設(shè)置的新值是最新的值，盡管方式可以再簡單些。如果兩個流程正好同時建議不同的值，那么可能就不能滿足共識算法安全的需求了。

如果一半的流程相信它們接受的也許是正確也許是錯誤的值，那么系統(tǒng)將進入一個僵局，存在兩個相同數(shù)量的組卻有不同的值，那么就無法確定大多數(shù)這個概念了，這個僵局能夠被第一個Paxos消息避免，因為Paxos的序列號，那些有問題的建議將有被其他更低的序列號，這樣序列號更高的建議就會毫不含糊地被大多數(shù)流程接收，它們也首先獲得了更高的序列號，然后如果接受到更低的序列號就會拒絕，Paxos 就是這樣通過用序列號控制整個系統(tǒng)的時間節(jié)奏。

注意：保證沒有兩個建議使用相同的序列號是很重要的，這是確保他們的順序，這樣每個序列號只有一個建議，這樣才能比較兩個建議，實現(xiàn)Paxos時，全局唯一有序的序列號實際是精確系統(tǒng)時間和集群中節(jié)點數(shù)量的拷貝，隨著時間不斷增加，從來不會重復(fù)。

2.6 Paxos流程

2.6.1 Paxos第一階段：準(zhǔn)備Perpare/諾言Promises

Paxos的第一階段是prepare/promise，準(zhǔn)備階段就是將建議值發(fā)送到各個目標(biāo)節(jié)點。

當(dāng)建議被發(fā)到目標(biāo)節(jié)點后，流程會會檢查建議中的序列號，是否是它們見到過的最高級，如果是最高級，它們會發(fā)出一個promise不再接受比這個新序列號更舊的建議了，這個promise作為消息，發(fā)到提交建議新值的流程服務(wù)器，這個promise消息給提交建議的流程后，提交建議的流程需要自己統(tǒng)計一下有多少其他流程已經(jīng)發(fā)回它們的promise了，如果判斷數(shù)量上是否達到大多數(shù)？如果大多數(shù)流程已經(jīng)同意接受這個建議或者更高級序列號的建議，這個提交建議的流程就能知道它獲得了發(fā)言權(quán)(因為有大多數(shù)支持)，這樣就開始講話，算法中的下一步處理將可能進行；如果回復(fù)promise的節(jié)點數(shù)量沒有達到大多數(shù)，也就是共識沒有達成，這樣這個節(jié)點提交的建議將退出，客戶端要求的寫操作失敗。

為了決定一個建議是否已經(jīng)有足夠的promises, 提交建議者只是統(tǒng)計一下它接受到的 promise 消息數(shù)量，然后和整個系統(tǒng)中節(jié)點服務(wù)器數(shù)量比較一下，“足夠”意味著大多數(shù)(N/2 + 1)個流程服務(wù)器在某段時間內(nèi)都回復(fù)了promises。如果超過一半的流程服務(wù)器沒有返回promises，這意味著這個建議沒有被大多數(shù)通過，那么在前面描述的讀算法中就不能滿足大多數(shù)的要求，也就不能達成共識，這個建議就退出。其他包括網(wǎng)絡(luò)分區(qū)錯誤也可能會阻止大多數(shù)達成共識。

2.6.2 第二階段：Paoxs接納Acceptance

當(dāng)完成prepare/promise階段，進入了 propose/accept階段。

一旦建議提交者已經(jīng)從大多數(shù)其他流程服務(wù)器獲得了promise，它會要求promise的流程服務(wù)器接收它們之前承諾接受的新值數(shù)據(jù)，這是一個“確認(rèn)commit”階段，如果沒有沖突建議失敗或分區(qū)錯誤，那么這個新建議將被所有其他節(jié)點接受，那么Paxos過程就完成了。

接受的過程也許可能會發(fā)生失敗，在回復(fù)了promise消息以后，在接受到Accept消息之前，如果有足夠多的服務(wù)器正好在這個時間段失敗，那么接受行為只能是少數(shù)服務(wù)器，那么Paxos進入了厄運狀態(tài)：一些流程服務(wù)器接受了新值，而不是全部的，這種不一致已經(jīng)在前面讀操作中描述：一個客戶端試圖從系統(tǒng)中大多數(shù)節(jié)點服務(wù)器讀取它們同意接受的值，它發(fā)現(xiàn)一些節(jié)點服務(wù)器報告有不同的值數(shù)據(jù)，這會引起讀失敗，但是Paxos還保持一致性，不允許在沒有達成共識情況下任何寫操作發(fā)生，這種壞的情況在實踐中經(jīng)常通過重復(fù)接受階段來讓大多數(shù)節(jié)點最終接受。

3. Raft

3.1 角色

在Raft中，任何時候一個服務(wù)器可以扮演下面角色之一：

1. Leader: 處理所有客戶端交互，日志復(fù)制等，一般一次只有一個Leader;
2. Follower: 類似選民，完全被動;
3. Candidate候選人: 類似Proposer律師，可以被選為一個新的領(lǐng)導(dǎo)人;

3.2 選舉流程

Raft階段分為兩個，首先是選舉過程，然后在選舉出來的領(lǐng)導(dǎo)人帶領(lǐng)進行正常操作，比如日志復(fù)制等。下面用圖示展示這個過程：

1. 任何一個服務(wù)器都可以成為一個候選者Candidate，它向其他服務(wù)器Follower發(fā)出要求選舉自己的請求：

   
   
   投票

2. 其他服務(wù)器同意了，發(fā)出OK，注意如果在這個過程中，有一個Follower當(dāng)機，沒有收到請求選舉的要求，因此候選者可以自己選自己，只要達到N/2 + 1 的大多數(shù)票，候選人還是可以成為Leader的:
   

   同意

3. 這樣這個候選者就成為了Leader領(lǐng)導(dǎo)人，它可以向選民也就是Follower們發(fā)出指令，比如進行日志復(fù)制

   
   
   選舉成功

4.以后通過心跳進行日志復(fù)制的通知

日志復(fù)制

5.如果一旦這個Leader宕機崩潰了，那么Follower中有一個成為候選者，發(fā)出邀票選舉

選舉

6.Follower同意后，其成為Leader，繼續(xù)承擔(dān)日志復(fù)制等指導(dǎo)工作

完成選舉

值得注意的是，整個選舉過程是有一個時間限制的，如下圖：

Splite Vote是因為如果同時有兩個候選人向大家邀票，這時通過類似加時賽來解決，兩個候選者在一段timeout比如300ms互相不服氣的等待以后，因為雙方得到的票數(shù)是一樣的，一半對一半，那么在300ms以后，再由這兩個候選者發(fā)出邀票，這時同時的概率大大降低，那么首先發(fā)出邀票的的候選者得到了大多數(shù)同意，成為領(lǐng)導(dǎo)者Leader，而另外一個候選者后來發(fā)出邀票時，那些Follower選民已經(jīng)投票給第一個候選者，不能再投票給它，它就成為落選者了，最后這個落選者也成為普通Follower一員了。

3.3 日志復(fù)制

下面以日志復(fù)制為例子說明Raft算法，假設(shè)Leader領(lǐng)導(dǎo)人已經(jīng)選出，這時客戶端發(fā)出增加一個日志的要求，比如日志是"sally"：

1. Leader接到請求，寫入sally：

   
   

2. Leader要求Followe遵從他的指令，都將這個新的日志內(nèi)容追加到他們各自日志中：

   
   

3. 大多數(shù)follower服務(wù)器將日志寫入磁盤文件后，確認(rèn)追加成功，發(fā)出Commited Ok:

   
   

4. 在下一個心跳heartbeat中，Leader會通知所有Follwer更新commited 項目：
   對于每個新的日志記錄，重復(fù)上述過程

如果在這一過程中，發(fā)生了網(wǎng)絡(luò)分區(qū)或者網(wǎng)絡(luò)通信故障，使得Leader不能訪問大多數(shù)Follwers了，那么Leader只能正常更新它能訪問的那些Follower服務(wù)器，而大多數(shù)的服務(wù)器Follower因為沒有了Leader，他們重新選舉一個候選者作為Leader，然后這個Leader作為代表于外界打交道，如果外界要求其添加新的日志，這個新的Leader就按上述步驟通知大多數(shù)Followers，如果這時網(wǎng)絡(luò)故障修復(fù)了，那么原先的Leader就變成Follower，在失聯(lián)階段這個老Leader的任何更新都不能算commit，都回滾，接受新的Leader的新的更新。

最后，附上raft協(xié)議演示地址：http://thesecretlivesofdata.com/raft/