上次我們分享 CAP 定理時，我們了解到，在網路分割槽的情況下，我們必須在一致性和可適應性之間做出選擇，更具體地說，我們實際上是在強一致性和最終一致性之間做出選擇。 在最終一致性方面，我們通常會聽到很多東西，比如讀修復、寫修復、反熵等等。 不過，在強一致性方面，我們經常聽到某**發布的強一致性演算法，原因是強一致性必須有合理的數學證明，大家都會相信，另外，還需要經過大規模的落地驗證才能讓大家認可，所以在商業上廣泛應用的強一致性演算法很少， 如Paxos、Zookeeper's Zab、Raft等。 由於在某些場景下必須保證強一致性，如金融支付、票務系統等，本文將介紹強一致性系列的演算法。
如果要談共識演算法，就不得不提 Paxos，因為 Paxos 在剛開始提出的時候缺乏工程實現細節，更像是乙個理論框架，導致實現細節看起來像 Paxos 的演算法，甚至有人會說世界上只有一種共識演算法， 那就是Paxos。這裡暫且不贅述 Paxos 的細節，因為 Paxos 演算法是出了名的難，導致作者 Lamport 甚至發表了《Paxos Made **》來解釋他的演算法，但這裡提到 Paxos 是因為 Paxos 的重要性在於它有嚴謹的數學證明，如果你真的想了解 Paxos， 建議先了解 Paxos 家族的其他演算法，比如本文要提到的 Raft，最後如果對 Paxos 在工程端的實現感興趣，可以參考 Google 團隊對 Paxos 的實用總結“Paxos Made Live — An Engineering Perspective”。
從所解決的問題型別來看，有兩種型別的共識演算法，即：拜占庭容錯演算法（Bezantine Fault Tolerance，BFT）和容錯演算法（crash fault tolerance, cft）。拜占庭容錯演算法主要用於求解 if節點作惡在如何同步集群狀態的情況下，常見的拜占庭容錯演算法有pbft; 容錯演算法主要在處理它們節點故障或遇到網路問題如何保持整個集群的狀態一致，常見的容錯演算法有zab、筏子等。
雖然拜占庭將軍問題和拜占庭容錯演算法PBFT很早就被提出來了，但可以說，直到區塊鏈的出現，才發現了大規模的應用場景，企業內部的大部分應用仍然屬於容錯演算法，比如谷歌的分布式鎖系統通過Paxos達成共識——Chubby， 而今天我們就要介紹一下企業中常見的共識機制——筏子。
Raft是史丹福大學Diego Ongaro的博士生，2013年與他的導師John Ousterhout合著了《尋找一種可理解的共識演算法》，並獲得了2014年Usenix年度技術會議最佳**獎。
通俗易懂的演算法最大的優點就是在工程上不容易出錯，這也導致了2013年以後的新系統如果需要強一致性，通常會優先選擇筏子，比如2013年的etcd，2015年的influxdb、ipfs和cockroachdb等; 理解的另乙個好處是實現相當多，所以可以找到相當多的參考實現，如果在 GitHub 上搜尋 paxos 和 raft，會發現有近 3 倍的轉發數量相差。
接下來，我將詳細介紹 raft 演算法，從節點記錄的內容（狀態、術語、日誌和狀態機）開始，然後是兩個模組——領導者選舉和日誌複製。
在 raft 中，節點有三種狀態，分別是 leader、candidate 和 follower。 木筏屬於強大的領導者模型，所以乙個 Raft 集群中只能有乙個 Leader，其他節點會尊重 Leader，Leader 說什麼就做什麼，這也導致了 Raft 只能做容錯（CFT），而不能處理拜占庭容錯（BFT）的事實。
節點狀態任期聽起來像是只有 leader 才需要的東西，是的，但為了容錯，集群中的任何節點都可能在 leader 失敗後成為候選節點並參與 leader 選舉，因此每個節點都需要知道當前術語。
任期是乙個嚴格遞增的數字，而木筏是強勢領導模式，所以乙個任期內最多只能有乙個領導者，只有當領導者在場時，他才能為外部世界提供服務。如下圖為例，每屆任期從領導人選舉開始（深藍色間隔），然後是集群可以對外服務的時間（淺藍色間隔），每屆任期只有在領導人失敗後才會啟動下一次選舉，因此每個任期的長度不固定， 而且在領導人選舉中也可能有任期失敗（如第3任期），這意味著任期內沒有領導人，因此將直接進行下一輪領導人選舉。
術語日誌由索引、術語和命令組成，索引是乙個嚴格遞增的數字，這裡的術語表示在哪個術語期間記錄的日誌，指令表示要執行哪些操作。 在下圖中，紅色框表示日誌索引 4 出現在項 2 處，指令是將 x 設定為 2。
log 狀態機的中文翻譯應該是狀態機，但這裡我們用資料狀態機來區分它與節點狀態。 Raft 記錄了使用者通過日誌傳送的指令，但寫入日誌只是乙個記錄，並不意味著資料的狀態真的發生了變化，在日誌複製一節中，我會解釋從新增日誌到改變資料狀態的條件，但這裡我們先知道新增日誌與更改資料狀態不是一回事
在上一篇文章中提到，CP 模型通常使用兩階段提交（2pc），這就是為什麼 raft 將日誌與資料狀態機分開，寫入日誌是第一階段，更改資料狀態機是第二階段。 例如，如果每次新增新日誌時都滿足更改資料狀態的條件，則資料狀態也會隨著日誌中的說明而更改。 
日誌和資料狀態機的關係我們上面提到節點有三種狀態——follower、candidate 和 leader，所以讓我們根據不同的節點狀態和每個狀態可能遇到的事件來了解 Raft Leader 選舉的機制。
每個節點在剛開始的時候都是乙個跟隨者，跟隨者會為領導者的心跳資訊維護乙個計時器，根據計時器的結果，有兩種可能：
繼續成為追隨者：在計時器倒計時到 0 之前，節點在收到來自領導者的心跳訊息或候選人投票請求訊息 （RequestVote RPC） 時，會重置計時器以繼續作為追隨者。 成為候選人：當計時器倒計時到0時，沒有收到leader心跳訊息，也沒有收到其他候選人訊息，follower認為集群中沒有leader，發起選舉，成為候選人。 當乙個節點從追隨者變為候選者時，它會增加乙個任期並投票給自己（下圖中的節點 a）。 上面提到，乙個任期內最多只能有乙個領導者，所以當節點發起選舉時，任期增加乙個，這意味著節點認為上一任期已經結束，進入下一任期。
關注者不會收到心跳訊息，不會成為候選人，也不會傳送投票請求
一旦節點成為候選節點，它就會向每個節點傳送乙個 RequestVote RPC，並維護乙個選舉超時計時器，這可以通過以下三種方式之一發生：
成為領導者：只要候選人獲得超過半數的選票，候選節點將狀態更改為 leader（下圖中的節點 A），並開始向其他節點傳送心跳訊息。 回退到追隨者：當候選人在選舉期間發現他們已經有相同任期的領導人或更高任期的領導人時，他們會將其狀態改回追隨者。 選舉超時：當候選人的倒計時時鐘為0時，他或她沒有辦法成為領導者，並且他沒有收到其他領導者的心跳訊息，此時節點會判斷選舉失敗，開始下一次選舉，候選人的任期加一， 代表新學期的開始，並將他的投票數重置為 1，最後再次向其他節點傳送投票請求。
當候選人獲得多數選票時，他將成為領導者並傳送心跳資訊
在節點是 leader 的期間，它會繼續向其他節點傳送心跳訊息，以防止其他節點舉行選舉，但集群也可能因為分割槽的原因有兩個 leader，當分割槽恢復時，其中乙個 leader 發現另乙個 leader 的任期比他高， 而任期較低的領導者將返回給追隨者，這樣集群就會回到只有乙個領導者的狀態。
leader不斷傳送心跳，阻止其他節點發起選舉以上是某個節點在三種狀態下可能遇到的三種情況，接下來是節點遇到投票請求時會如何投票（RequestVote RPC）：
高任期的節點不會被投票為低任期，高日誌索引的節點不會被投票給低日誌索引的節點只有日誌最完整的節點才能成為領導者。如果候選者滿足上一點，則節點將優先考慮傳送第乙個投票請求的候選人。每個節點在乙個任期內只能投一票。 如上所述，有乙個從日誌中更改資料狀態機的條件，本節將解釋 raft 如何複製日誌並更改資料狀態機。 由於 raft 是乙個強 leader 模型，只有 leader 才能接收到來自客戶端的寫入請求進行處理，並且在收到客戶端的請求後，leader 會將客戶端的指令寫入日誌中，然後將日誌複製請求（appendentries rpc）傳送到其他節點，只要 leader 收到超過一半的答覆是成功的，領導者將執行 log 命令，更改其資料狀態機，並回覆客戶端。
以上情況是理想情況，但實際上，由於各種問題，每個追隨者的日誌可能會不一致（如下圖所示）。 Raft 專為 appendentries RPC 設計不允許直接複製最新的日誌，並跳過中間未複製的日誌。如下圖所示，如果 leader 向第乙個跟隨者傳送索引 8 的日誌複製請求，則該跟隨者的最新日誌最多只有索引 5，因此 leader 的請求將被拒絕，並且 leader 會繼續向第乙個跟隨者傳送索引 7 的日誌複製請求， 並且 follower 會拒絕，直到 leader 將索引 6 的日誌複製請求傳送給第乙個 follower，follower 會接受它，並從索引 6 重新同步到索引 8。
因此，如果 raft 集群想要對外服務，至少一半的節點必須有完整的日誌記錄才能對外服務，因為沒有完整日誌記錄的節點無法成功回覆最新的日誌輸入請求。
追隨者並沒有完全複製領導者的記錄，現在我們已經討論了 Raft 是如何工作的，讓我們回到兩個 Raft 設計理念——隨機選舉超時、兩階段提交優化和分割槽容錯。
從追隨者到候選人的**，可以發現每個節點的計時器倒計時時間都不一樣，所以有些節點成為候選人的速度比較快，而有些節點還在倒計時，這種設計是為了避免節點同時發起投票，導致選票分散，進而造成選舉失敗， 大家還記得上面說過，每個選舉任期只有在有領導之後才能對外任職，所以 RAFT 要盡量保證選舉能夠成功，為了避免節點頻繁發起選舉，Raft **建議將超時時間設定在 150 到 300ms 之間。
如上文所述，兩階段提交應該只有在集群完成提交階段後才會回覆客戶端，但在 raft 中，只有 leader 會在執行階段完成後回覆客戶端，因此等於省略了一半的資訊傳播，這是對 raft 的優化。 但你一定想知道，追隨者如何知道他們什麼時候可以進入執行階段？ 你還記得我們之前提到的心跳訊息嗎？ 其實心跳資訊也是日誌拷貝請求資訊（appendentries rpc），日誌請求資訊也會被包括在內leadercommit，代表 leader 最新進入執行階段的日誌索引，所以 leader 在傳播心跳訊息時，不僅通知關注者不要發起選舉，還會複製日誌並同步資料狀態機的狀態，以減少資訊量。
在上一篇文章之後，大家會好奇 raft 是如何處理分割槽容錯問題的，以下面這個 ** 為例，在 raft 集群再次分割槽後，確實可能會產生兩個 leader，導致裂腦的問題，但是我們上面提到，日誌複製只有在大多數節點響應成功後才會成功傳送回客戶端， 所以無論分割槽如何切割，最多只有乙個分割槽，節點超過一半因此，只有乙個領導者可以繼續對外服務，而其他領導者即使收到客戶的請求也只能回覆失敗。
在分割槽的情況下，最多只能使用乙個分割槽對外服務如上文所述，兩階段提交可以保持集群中大部分節點的狀態一致，實現強一致性。 在拜占庭容錯演算法PBFT中，將兩階段提交公升級為三階段提交，並改變流程以避免某些節點作惡，導致無法達成共識。
希望讀完這篇文章，讀者能夠理解 raft 演算法是如何工作的，Raft 之所以在 2014 年發布後被很多系統迅速採用的原因之一是它易於理解，另乙個原因是 raft 在實現中與系統完美解耦，從而可以基於 raft 開發系統， 其他共識機制，如Zookeeper的ZAB，在發布之初是針對Zookeeper的。因此，其他系統更難在zab之上開發。
各種語言的 raft 教材和實現版本很多，如果想了解更多，建議直接閱讀 **如果覺得直接閱讀太難，也可以觀看 raft 作者在伊利諾大學親自講解 raft** 最後，如果想深入研究原始碼研究， 您可以研究 HashiCorp 的版本，因為此版本已在 Consul、IPFS 和 InfluxDB 等主要系統中使用。