大名鼎鼎的 Paxos 算法可能不少人都聽說過，幾乎壟斷了一致性算法領域，在 Raft 協議誕生之前，Paxos 幾乎成了一致性協議的代名詞。但是對於大多數人來說，Paxos 算法太難以理解了，而且難以實現。因此斯坦福大學的兩位教授 Diego Ongaro 和 John Ousterhout 決定設計一種更容易理解的一致性算法，最終提出了 Raft 算法！

Raft 是一種更爲簡單方便易於理解的分佈式算法，主要解決了分佈式中的一致性問題。相比傳統的 Paxos 算法，Raft 將大量的計算問題分解成爲了一些簡單的相對獨立的子問題，並有着和 Multi-Paxos 同樣的性能，下面我們通過動圖，以後還原 Raft 內部原理。

Raft 基礎

名詞解釋

Raft 協議一共包含如下 3 類角色：

• Leader（領袖）：領袖由羣衆投票選舉得出，每次選舉，只能選出一名領袖；

• Candidate（候選人）：當沒有領袖時，某些羣衆可以成爲候選人，然後去競爭領袖的位置；

• Follower（羣衆）：這個很好理解，就不解釋了。

然後在進行選舉過程中，還有幾個重要的概念：

• Leader Election（領導人選舉）：簡稱選舉，就是從候選人中選出領袖；

• Term（任期）：它其實是個單獨遞增的連續數字，每一次任期就會重新發起一次領導人選舉；

• Election Timeout（選舉超時）：就是一個超時時間，當羣衆超時未收到領袖的心跳時，會重新進行選舉。

角色轉換

這幅圖是領袖、候選人和羣衆的角色切換圖，我先簡單總結一下：

• 羣衆 -> 候選人：當開始選舉，或者 “選舉超時” 時

• 候選人 -> 候選人：當 “選舉超時”，或者開始新的 “任期”

• 候選人 -> 領袖：獲取大多數投票時

• 候選人 -> 羣衆：其它節點成爲領袖，或者開始新的 “任期”

• 領袖 -> 羣衆：發現自己的任期 ID 比其它節點分任期 ID 小時，會自動放棄領袖位置

• 備註：後面會針對每一種情況，詳細進行講解。

選舉

情況 1：領導人選舉

爲了便於後續的講解，我畫了一副簡圖，“選舉定時器” 其實就是每個節點的 “超時時間”。成爲候選人：每個節點都有自己的 “超時時間”，因爲是隨機的，區間值爲 150~300ms，所以出現相同隨機時間的概率比較小，因爲節點 B 最先超時，這時它就成爲候選人。

選舉領導人：候選人 B 開始發起投票，羣衆 A 和 C 返回投票，當候選人 B 獲取大部分選票後，選舉成功，候選人 B 成爲領袖。

心跳探測：爲了時刻宣誓自己的領導人地位，領袖 B 需要時刻向羣衆發起心跳，當羣衆 A 和 C 收到領袖 B 的心跳後，羣衆 A 和 C 的 “超時時間” 會重置爲 0，然後重新計數，依次反覆。

這裏需要說明一下，領袖廣播心跳的週期必須要短於 “選舉定時器” 的超時時間，否則羣衆會頻繁成爲候選者，也就會出現頻繁發生選舉，切換 Leader 的情況。

情況 2：領袖掛掉情況

當領袖 B 掛掉，羣衆 A 和 C 會的 “選舉定時器” 會一直運行，當羣衆 A 先超時時，會成爲候選人，然後後續流程和 “領導人選舉” 流程一樣，即通知投票 -> 接收投票 -> 成爲領袖 -> 心跳探測。

情況 3：出現多個候選者情況

當出現多個候選者 A 和 D 時，兩個候選者會同時發起投票，如果票數不同，最先得到大部分投票的節點會成爲領袖；如果獲取的票數相同，會重新發起新一輪的投票。

當 C 成爲新的候選者，此時的任期 Term 爲 5，發起新一輪的投票，其它節點發起投票後，會更新自己的任期值，最後選擇新的領袖爲 C 節點。

日誌複製

複製狀態機

複製狀態機的基本思想是一個分佈式的狀態機，系統由多個複製單元組成，每個複製單元均是一個狀態機，它的狀態保存在操作日誌中。如下圖所示，服務器上的一致性模塊負責接收外部命令，然後追加到自己的操作日誌中，它與其他服務器上的一致性模塊進行通信，以保證每一個服務器上的操作日誌最終都以相同的順序包含相同的指令。一旦指令被正確複製，那麼每一個服務器的狀態機都將按照操作日誌的順序來處理它們，然後將輸出結果返回給客戶端。

數據同步流程

數據同步流程，借鑑了 “複製狀態機” 的思想，都是先 “提交”，再“應用”。當 Client 發起數據更新請求，請求會先到領袖節點 C，節點 C 會更新日誌數據，然後通知羣衆節點也更新日誌，當羣衆節點更新日誌成功後，會返回成功通知給領袖 C，至此完成了“提交” 操作；當領袖 C 收到通知後，會更新本地數據，並通知羣衆也更新本地數據，同時會返回成功通知給 Client，至此完成了 “應用” 操作，如果後續 Client 又有新的數據更新操作，會重複上述流程。

日誌複製原理

每一個日誌條目一般包括三個屬性：整數索引 Log Index、任期號 Term 和指令 Commond。每個條目所包含的 “整數索引” 即該條目在日誌文件中的槽位，“任期號”對應到圖中就是每個方塊中的數字，用於檢測在不同服務器上日誌的不一致問題，指令即用於被狀態機執行的外部命令，圖中就是帶箭頭的數字。

領導人決定什麼時候將日誌條目應用到狀態機是安全的，即可被提交的呢？一旦領導人創建的條目已經被複制到半數以上的節點上了，那麼這個條目就稱爲可被提交的。例如，圖中的 9 號條目在其中 4 節點（一共 7 個節點）上具有複製，所以 9 號條目是可被提交的；但條目 10 只在其中 3 個節點上有複製，因此 10 號條目不是可被提交的。

一般情況下，Leader 和 Follower 的日誌都是保存一致的，如果 Leader 節點在故障之前沒有向其它節點完全複製日誌文件之前的所有條目，會導致日誌不一致問題。在 Raft 算法中，Leader 會強制 Follower 和自己的日誌保存一致，因此 Follower 上與 Leader 的衝突日誌會被領導者的日誌強制覆寫。爲了實現上述邏輯，就需要知道 Follower 上與 Leader 日誌不一致的位置，那麼 Leader 是如何精準找到每個 Follower 日誌不一致的那個槽位呢？

Leader 爲每一個 Follower 維護了一個 nextlndex，它表示領導人將要發送給該追隨者的下一條日誌條目的索引，當一個 Leader 贏得選舉時，它會假設每個 Follower 上的日誌都與自己的保持－致，於是先將 nextlndex 初始化爲它最新的日誌條目索引數 + 1，在上圖中，由於 Leader 最新的日誌條目 index 是 10 ，所以 nextlndex 的初始值是 11。當 Leader 向 Follower 發送 AppendEntries RPC 時，它攜帶了（item_id，nextIndex - 1）二元組信息，item_id 即爲 nextIndex - 1 這個槽位的日誌條目的 term。Follower 接收到 AppendEntries RPC 消息後，會進行一致性檢查，即搜索自己的日誌文件中是否存在這樣的日誌條目，如果不存在，就像 Leader 返回 AppendEntries RPC 失敗，然後領導人會將 nextIndex 遞減，然後進行重試，直到成功爲止。之後的邏輯就比較簡單，Follower 將 nextIndex 之前的日誌全部保留，之後的全部刪除，然後將 Leader 的 nextIndex 之後的日誌全部同步過來。

上面只是講述了方法，下面舉個例子，加深一下理解，還是以上面的圖爲例。Leader 的 nextlndex 爲 11，向 b 發送 AppendEntries RPC(6,10)，發現 b 沒有，繼續發送 (6,9)(6,8) (5,7) (5,6) (4,5)，最後發送(4,4) 才找到，所以對於 b，nextlndex=4 之後的日誌全部刪除，然後將 Leader 的 nextlndex=4 的日誌全部追加過來。

腦裂情況

當網絡問題導致腦裂，出現雙 Leader 情況時，每個網絡可以理解爲一個獨立的網絡，因爲原先的 Leader 獨自在一個區，所以向他提交的數據不可能被複制到大多數節點上，所以數據永遠都不會提交，這個可以在第 4 幅圖中提現出來（SET 3 沒有提交）。

當網絡恢復之後，舊的 Leader 發現集羣中的新 Leader 的 Term 比自己大，則自動降級爲 Follower，並從新 Leader 處同步數據達成集羣數據一致，同步數據的方式可以詳見 “日誌原理”。

盡信書則不如無書，因個人能力有限，難免有疏漏和錯誤之處，如發現 bug 或者有更好的建議，歡迎批評指正，不吝感激。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OLcb0nWLp-Oa1DA6ppFbKQ