爲什麼 Raft 算法是分佈式系統的首選？

背景

當今的數據中心和應用程序在高度動態的環境中運行，爲了應對高度動態的環境，它們通過額外的服務器進行橫向擴展，並且根據需求進行擴展和收縮。同時，服務器和網絡故障也很常見。

因此，系統必須在正常操作期間處理服務器的上下線。它們必須對變故做出反應並在幾秒鐘內自動適應；對客戶來說的話，明顯的中斷通常是不可接受的。

幸運的是，分佈式共識可以幫助應對這些挑戰。

拜占庭將軍

在介紹共識算法之前，先介紹一個簡化版拜占庭將軍的例子來幫助理解共識算法。

假設多位拜占庭將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們如何達成是否要進攻的一致性決定？

解決方案大致可以理解成：先在所有的將軍中選出一個大將軍，用來做出所有的決定。

舉例如下：假如現在一共有 3 個將軍 A，B 和 C，每個將軍都有一個隨機時間的倒計時器，倒計時一結束，這個將軍就把自己當成大將軍候選人，然後派信使傳遞選舉投票的信息給將軍 B 和 C，如果將軍 B 和 C 還沒有把自己當作候選人（自己的倒計時還沒有結束），並且沒有把選舉票投給其他人，它們就會把票投給將軍 A，信使回到將軍 A 時，將軍 A 知道自己收到了足夠的票數，成爲大將軍。在有了大將軍之後，是否需要進攻就由大將軍 A 決定，然後再去派信使通知另外兩個將軍，自己已經成爲了大將軍。如果一段時間還沒收到將軍 B 和 C 的回覆（信使可能會被暗殺），那就再重派一個信使，直到收到回覆。

共識算法

共識是可容錯系統中的一個基本問題：即使面對故障，服務器也可以在共享狀態上達成一致。

共識算法允許一組節點像一個整體一樣一起工作，即使其中的一些節點出現故障也能夠繼續工作下去，其正確性主要是源於複製狀態機的性質：一組 Server 的狀態機計算相同狀態的副本，即使有一部分的 Server 宕機了它們仍然能夠繼續運行。

一般通過使用複製日誌來實現複製狀態機。每個 Server 存儲着一份包括命令序列的日誌文件，狀態機會按順序執行這些命令。因爲每個日誌包含相同的命令，並且順序也相同，所以每個狀態機處理相同的命令序列。由於狀態機是確定性的，所以處理相同的狀態，得到相同的輸出。

因此共識算法的工作就是保持複製日誌的一致性。服務器上的共識模塊從客戶端接收命令並將它們添加到日誌中。它與其他服務器上的共識模塊通信，以確保即使某些服務器發生故障。每個日誌最終包含相同順序的請求。一旦命令被正確地複製，它們就被稱爲已提交。每個服務器的狀態機按照日誌順序處理已提交的命令，並將輸出返回給客戶端，因此，這些服務器形成了一個單一的、高度可靠的狀態機。

適用於實際系統的共識算法通常具有以下特性：

• 安全。確保在非拜占庭條件（也就是上文中提到的簡易版拜占庭）下的安全性，包括網絡延遲、分區、包丟失、複製和重新排序。

• 高可用。只要大多數服務器都是可操作的，並且可以相互通信，也可以與客戶端進行通信，那麼這些服務器就可以看作完全功能可用的。因此，一個典型的由五臺服務器組成的集羣可以容忍任何兩臺服務器端故障。假設服務器因停止而發生故障；它們稍後可能會從穩定存儲上的狀態中恢復並重新加入集羣。

• 一致性不依賴時序。錯誤的時鐘和極端的消息延遲，在最壞的情況下也只會造成可用性問題，而不會產生一致性問題。

• 在集羣中大多數服務器響應，命令就可以完成，不會被少數運行緩慢的服務器來影響整體系統性能。

Raft 算法是什麼？

Raft 也是一個 一致性算法，和 Paxos 目標相同。但它還有另一個名字 - 易於理解的一致性算法。Paxos 和 Raft 都是爲了實現 一致性 產生的。不同於 Paxos 算法直接從分佈式一致性問題出發推導出來，Raft 算法則是從多副本狀態機的角度提出，用於管理多副本狀態機的日誌複製。

Raft 實現了和 Paxos 相同的功能，它將一致性分解爲多個子問題: Leader 選舉 (Leader election)、日誌同步(Log replication)、安全性(Safety)、日誌壓縮(Log compaction)、成員變更(Membership change) 等。同時，Raft 算法使用了更強的假設來減少了需要考慮的狀態，使之變的易於理解和實現。

基礎

節點類型

一個 Raft 集羣包括若干服務器，以典型的 5 服務器集羣舉例。在任意的時間，每個服務器一定會處於以下三個狀態中的一個：

• Leader：負責發起心跳，響應客戶端，創建日誌，同步日誌。

• Candidate：Leader 選舉過程中的臨時角色，由 Follower 轉化而來，發起投票參與競選。

• Follower：接受 Leader 的心跳和日誌同步數據，投票給 Candidate。

在正常的情況下，只有一個服務器是 Leader，剩下的服務器是 Follower。Follower 是被動的，它們不會發送任何請求，只是響應來自 Leader 和 Candidate 的請求。

任期

如圖所示，raft 算法將時間劃分爲任意長度的任期（term），任期用連續的數字表示，看作當前 term 號。每一個任期的開始都是一次選舉，在選舉開始時，一個或多個 Candidate 會嘗試成爲 Leader。如果一個 Candidate 贏得了選舉，它就會在該任期內擔任 Leader。如果沒有選出 Leader，將會開啓另一個任期，並立刻開始下一次選舉。raft 算法保證在給定的一個任期最少要有一個 Leader。

每個節點都會存儲當前的 term 號，當服務器之間進行通信時會交換當前的 term 號；如果有服務器發現自己的 term 號比其他人小，那麼他會更新到較大的 term 值。如果一個 Candidate 或者 Leader 發現自己的 term 過期了，他會立即退回成 Follower。如果一臺服務器收到的請求的 term 號是過期的，那麼它會拒絕此次請求。

三類角色的變遷圖如下：

日誌

• entry：每一個事件成爲 entry，只有 Leader 可以創建 entry。entry 的內容爲 <term,index,cmd> 其中 cmd 是可以應用到狀態機的操作。

• log：由 entry 構成的數組，每一個 entry 都有一個表明自己在 log 中的 index。只有 Leader 纔可以改變其他節點的 log。entry 總是先被 Leader 添加到自己的 log 數組中，然後再發起共識請求，獲得同意後纔會被 Leader 提交給狀態機。Follower 只能從 Leader 獲取新日誌和當前的 commitIndex，然後把對應的 entry 應用到自己的狀態機中。

Raft 算法子問題

Raft 實現了和 Paxos 相同的功能，它將一致性分解爲多個子問題:

• Leader 選舉 (Leader election)

• 日誌同步 (Log replication)

• 安全性 (Safety)

• 日誌壓縮 (Log compaction)

• 成員變更 (Membership change)

領導人選舉

raft 使用心跳機制來觸發 Leader 的選舉。當 Server 啓動時，初始化爲 Follower。Leader 向所有 Followers 週期性發送 heartbeat。如果 Follower 在選舉超時時間內沒有收到 Leader 的 heartbeat，就會等待一段隨機的時間後發起一次 Leader 選舉。 Follower 將其當前 term 加一然後轉換爲 Candidate。它首先給自己投票並且給集羣中的其他服務器發送 RequestVote RPC 。結果有以下三種情況：

• 贏得了多數（超過 1/2）的選票，成功選舉爲 Leader；

• 收到了 Leader 的消息，表示有其它服務器已經搶先當選了 Leader；

• 沒有 Server 贏得多數的選票，Leader 選舉失敗，等待選舉時間超時（Election Timeout）後發起下一次選舉。

在 Candidate 等待選票的時候，它可能收到其他節點聲明自己是 Leader 的心跳，此時有兩種情況：

• 該 Leader 的 term 號大於等於自己的 term 號，說明對方已經成爲 Leader，則自己回退爲 Follower。

• 該 Leader 的 term 號小於自己的 term 號，那麼會拒絕該請求並讓該節點更新 term。

如果一臺服務器能夠收到來自 Leader 或者 Candidate 的有效信息，那麼它會一直保持爲 Follower 狀態，並且刷新自己的 electionElapsed，重新計時。

Leader 會向所有的 Follower 週期性發送心跳來保證自己的 Leader 地位。如果一個 Follower 在一個週期內沒有收到心跳信息，就叫做選舉超時，然後它就會認爲此時沒有可用的 Leader，並且開始進行一次選舉以選出一個新的 Leader。

由於可能同一時刻出現多個 Candidate，導致沒有 Candidate 獲得大多數選票，如果沒有其他手段來重新分配選票的話，那麼可能會無限重複下去。

日誌複製

一旦選出了 Leader，它就開始接受客戶端的請求。每一個客戶端的請求都包含一條需要被複制狀態機（Replicated State Machine）執行的命令。

Leader 收到客戶端請求後，會生成一個 entry，包含 <index,term,cmd>，再將這個 entry 添加到自己的日誌末尾後，向所有的節點廣播該 entry，要求其他服務器複製這條 entry。

如果 Follower 接受該 entry，則會將 entry 添加到自己的日誌後面，同時返回給 Leader 同意。

如果 Leader 收到了多數的成功響應，Leader 會將這個 entry 應用到自己的狀態機中，之後可以成爲這個 entry 是 committed 的，並且向客戶端返回執行結果。

raft 保證以下兩個性質：

• 在兩個日誌裏，有兩個 entry 擁有相同的 index 和 term，那麼它們一定有相同的 cmd，即所存儲的命令是相同的。

• 在兩個日誌裏，有兩個 entry 擁有相同的 index 和 term，那麼它們前面的 entry 也一定相同

第一條特性源於 Leader 在一個 term 內在給定的一個 log index 最多創建一條日誌條目，同時該條目在日誌中的位置也從來不會改變。

第二條特性源於 AppendEntries 的一個簡單的一致性檢查。當發送一個 AppendEntries RPC 時，Leader 會把新日誌條目緊接着之前的條目的 log index 和 term 都包含在裏面。如果 Follower 沒有在它的日誌中找到 log index 和 term 都相同的日誌，它就會拒絕新的日誌條目。

一般情況下，Leader 和 Followers 的日誌保持一致，因此 AppendEntries 一致性檢查通常不會失敗。然而，Leader 崩潰可能會導致日誌不一致: 舊的 Leader 可能沒有完全複製完日誌中的所有條目。Leader 通過強制 Follower 複製自己的日誌來處理日誌的不一致。這就意味着，在 Follower 上的衝突日誌會被領導者的日誌覆蓋。

爲了使得 Follower 的日誌和自己的日誌一致，Leader 需要找到 Follower 與它日誌一致的地方，然後刪除 Follower 在該位置之後的日誌，接着把這之後的日誌發送給 Follower。

Leader 給每一個 Follower 維護了一個 nextIndex，它表示 Leader 將要發送給該追隨者的下一條日誌條目的索引。當一個 Leader 開始掌權時，它會將 nextIndex 初始化爲它的最新的日誌條目索引數 + 1。如果一個 Follower 的日誌和 Leader 的不一致，AppendEntries 一致性檢查會在下一次 AppendEntries RPC 時返回失敗。在失敗之後，Leader 會將 nextIndex 遞減然後重試 AppendEntries RPC。最終 nextIndex 會達到一個 Leader 和 Follower 日誌一致的地方。這時，AppendEntries 會返回成功，Follower 中衝突的日誌條目都被移除了，並且添加所缺少的上了 Leader 的日誌條目。一旦 AppendEntries 返回成功，Follower 和 Leader 的日誌就一致了，這樣的狀態會保持到該任期結束。

安全性

選舉限制

Leader 需要保證自己存儲全部已經提交的日誌條目。這樣纔可以使日誌條目只有一個流向：從 Leader 流向 Follower，Leader 永遠不會覆蓋已經存在的日誌條目。

每個 Candidate 發送 RequestVoteRPC 時，都會帶上最後一個 entry 的信息。所有節點收到投票信息時，會對該 entry 進行比較，如果發現自己的更新，則拒絕投票給該 Candidate。

判斷日誌新舊的方式：如果兩個日誌的 term 不同，term 大的更新；如果 term 相同，更長的 index 更新。

節點崩潰

如果 Leader 崩潰，集羣中的節點在 electionTimeout 時間內沒有收到 Leader 的心跳信息就會觸發新一輪的選主，在選主期間整個集羣對外是不可用的。

如果 Follower 和 Candidate 崩潰，處理方式會簡單很多。之後發送給它的 RequestVoteRPC 和 AppendEntriesRPC 會失敗。由於 raft 的所有請求都是冪等的，所以失敗的話會無限的重試。如果崩潰恢復後，就可以收到新的請求，然後選擇追加或者拒絕 entry。

時間與可用性

raft 的要求之一就是安全性不依賴於時間：系統不能僅僅因爲一些事件發生的比預想的快一些或者慢一些就產生錯誤。爲了保證上述要求，最好能滿足以下的時間條件：

broadcastTime << electionTimeout << MTBF

• broadcastTime：向其他節點併發發送消息的平均響應時間；

• electionTimeout：選舉超時時間；

• MTBF(mean time between failures)：單臺機器的平均健康時間；

broadcastTime 應該比 electionTimeout 小一個數量級，爲的是使 Leader 能夠持續發送心跳信息（heartbeat）來阻止 Follower 開始選舉；

electionTimeout 也要比 MTBF 小几個數量級，爲的是使得系統穩定運行。當 Leader 崩潰時，大約會在整個 electionTimeout 的時間內不可用；我們希望這種情況僅佔全部時間的很小一部分。

由於 broadcastTime 和 MTBF 是由系統決定的屬性，因此需要決定 electionTimeout 的時間。

一般來說，broadcastTime 一般爲 0.5～20ms，electionTimeout 可以設置爲 10～500ms，MTBF 一般爲一兩個月。

日誌壓縮

在實際的系統中，不能讓日誌無限增長，否則系統重啓時需要花很長的時間進行回放，從而影響可用性。Raft 採用對整個系統進行 snapshot 來解決，snapshot 之前的日誌都可以丟棄。

每個副本獨立的對自己的系統狀態進行 snapshot，並且只能對已經提交的日誌記錄進行 snapshot。

Snapshot 中包含以下內容:

• 日誌元數據。最後一條已提交的 log entry 的 log index 和 term。這兩個值在 snapshot 之後的第一條 log entry 的 AppendEntries RPC 的完整性檢查的時候會被用上。

• 系統當前狀態。

當 Leader 要發給某個日誌落後太多的 Follower 的 log entry 被丟棄，Leader 會將 snapshot 發給 Follower。或者當新加進一臺機器時，也會發送 snapshot 給它。發送 snapshot 使用 InstalledSnapshot RPC。

做 snapshot 既不要做的太頻繁，否則消耗磁盤帶寬， 也不要做的太不頻繁，否則一旦節點重啓需要回放大量日誌，影響可用性。推薦當日志達到某個固定的大小做一次 snapshot。

做一次 snapshot 可能耗時過長，會影響正常日誌同步。可以通過使用 copy-on-write 技術避免 snapshot 過程影響正常日誌同步。

成員變更

成員變更是在集羣運行過程中副本發生變化，如增加 / 減少副本數、節點替換等。

成員變更也是一個分佈式一致性問題，既所有服務器對新成員達成一致。但是成員變更又有其特殊性，因爲在成員變更的一致性達成的過程中，參與投票的進程會發生變化。

如果將成員變更當成一般的一致性問題，直接向 Leader 發送成員變更請求，Leader 複製成員變更日誌，達成多數派之後提交，各服務器提交成員變更日誌後從舊成員配置 (Cold) 切換到新成員配置(Cnew)。

因爲各個服務器提交成員變更日誌的時刻可能不同，造成各個服務器從舊成員配置 (Cold) 切換到新成員配置 (Cnew) 的時刻不同。

成員變更不能影響服務的可用性，但是成員變更過程的某一時刻，可能出現在 Cold 和 Cnew 中同時存在兩個不相交的多數派，進而可能選出兩個 Leader，形成不同的決議，破壞安全性。

由於成員變更的這一特殊性，成員變更不能當成一般的一致性問題去解決。

爲了解決這一問題，Raft 提出了兩階段的成員變更方法。集羣先從舊成員配置 Cold 切換到一個過渡成員配置，稱爲共同一致 (joint consensus)，共同一致是舊成員配置 Cold 和新成員配置 Cnew 的組合 Cold U Cnew，一旦共同一致 Cold U Cnew 被提交，系統再切換到新成員配置 Cnew。

Raft 兩階段成員變更過程如下:

1. Leader 收到成員變更請求從 Cold 切成 Cnew；

2. Leader 在本地生成一個新的 log entry，其內容是 Cold∪Cnew，代表當前時刻新舊成員配置共存，寫入本地日誌，同時將該 log entry 複製至 Cold∪Cnew 中的所有副本。在此之後新的日誌同步需要保證得到 Cold 和 Cnew 兩個多數派的確認；

3. Follower 收到 Cold∪Cnew 的 log entry 後更新本地日誌，並且此時就以該配置作爲自己的成員配置；

4. 如果 Cold 和 Cnew 中的兩個多數派確認了 Cold U Cnew 這條日誌，Leader 就提交這條 log entry；

5. 接下來 Leader 生成一條新的 log entry，其內容是新成員配置 Cnew，同樣將該 log entry 寫入本地日誌，同時複製到 Follower 上；

6. Follower 收到新成員配置 Cnew 後，將其寫入日誌，並且從此刻起，就以該配置作爲自己的成員配置，並且如果發現自己不在 Cnew 這個成員配置中會自動退出；

7. Leader 收到 Cnew 的多數派確認後，表示成員變更成功，後續的日誌只要得到 Cnew 多數派確認即可。Leader 給客戶端回覆成員變更執行成功。

異常分析:

• 如果 Leader 的 Cold U Cnew 尚未推送到 Follower，Leader 就掛了，此後選出的新 Leader 並不包含這條日誌，此時新 Leader 依然使用 Cold 作爲自己的成員配置。

• 如果 Leader 的 Cold U Cnew 推送到大部分的 Follower 後就掛了，此後選出的新 Leader 可能是 Cold 也可能是 Cnew 中的某個 Follower。

• 如果 Leader 在推送 Cnew 配置的過程中掛了，那麼同樣，新選出來的 Leader 可能是 Cold 也可能是 Cnew 中的某一個，此後客戶端繼續執行一次改變配置的命令即可。

• 如果大多數的 Follower 確認了 Cnew 這個消息後，那麼接下來即使 Leader 掛了，新選出來的 Leader 肯定位於 Cnew 中。

• 兩階段成員變更比較通用且容易理解，但是實現比較複雜，同時兩階段的變更協議也會在一定程度上影響變更過程中的服務可用性，因此我們期望增強成員變更的限制，以簡化操作流程。

兩階段成員變更，之所以分爲兩個階段，是因爲對 Cold 與 Cnew 的關係沒有做任何假設，爲了避免 Cold 和 Cnew 各自形成不相交的多數派選出兩個 Leader，才引入了兩階段方案。

如果增強成員變更的限制，假設 Cold 與 Cnew 任意的多數派交集不爲空，這兩個成員配置就無法各自形成多數派，那麼成員變更方案就可能簡化爲一階段。

那麼如何限制 Cold 與 Cnew，使之任意的多數派交集不爲空呢? 方法就是每次成員變更只允許增加或刪除一個成員。

可從數學上嚴格證明，只要每次只允許增加或刪除一個成員，Cold 與 Cnew 不可能形成兩個不相交的多數派。

一階段成員變更:

• 成員變更限制每次只能增加或刪除一個成員 (如果要變更多個成員，連續變更多次)。

• 成員變更由 Leader 發起，Cnew 得到多數派確認後，返回客戶端成員變更成功。

• 一次成員變更成功前不允許開始下一次成員變更，因此新任 Leader 在開始提供服務前要將自己本地保存的最新成員配置重新投票形成多數派確認。

• Leader 只要開始同步新成員配置，即可開始使用新的成員配置進行日誌同步。

Multi Paxos 、Raft 、ZAB 的關係與區別

以上這種把共識問題分解爲 “Leader Election”、“Entity Replication” 和“Safety”三個問題來思考、解決的解題思路，即“Raft 算法”

**ZooKeeper 的 ZAB 算法與 Raft 的思路也非常類似，**這些算法都被認爲是 Multi Paxos 的等價派生實現。

核心原理都是一樣：

• 通過隨機超時來實現無活鎖的選主過程

• 通過主節點來發起寫操作

• 通過心跳來檢測存活性

• 通過 Quorum 機制來保證一致性

具體細節上可以有差異：

• 是全部節點都能參與選主，還是部分節點能參與（ZAB 分爲 Leader Follower Observer 只有 Follower 能選 Leader）

• Quorum 中是衆生平等還是各自帶有權重

• 怎樣表示值的方式

Paxos 像民主制： 人人平等可提議， 需要反覆協商， 決策過程複雜。 代表作：MySQL MGR 組複製，多主模式下多個節點都可以寫入（需衝突檢測）。

Raft 像獨裁製： 有明確的負責人（班長）， 命令執行簡單直接， 容易理解和執行。 代表作：MongoDB 副本集，只有 Primary 節點可以接收寫入請求。

學習 raft 算法，一定要看的兩個網站：

• https://raft.github.io

• http://www.kailing.pub/raft/index.html

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