引言：尋求易理解的共識算法

共識算法是構建可靠的大規模分布式軟件系統的關鍵組件。它們允許多臺機器作為一個高內聚的整體協同工作，即使部分成員發生故障也能繼續提供服務。在過去的十年中，Paxos 算法一直是共識領域討論的核心，大多數共識實現都基于或受其影響。然而，Paxos 因其難以理解而臭名昭著，并且其架構需要復雜的修改才能應用于實際系統。

正是由于 Paxos 的這些挑戰，斯坦福大學的 Diego Ongaro 和 John Ousterhout 開始著手設計一種新的共識算法——Raft。Raft 的首要設計目標是 可理解性 (understandability)：不僅算法要能工作，更重要的是能讓人清楚地理解它為什么能工作。為了實現這一目標，Raft 采用了 問題分解 (problem decomposition) 和 狀態空間簡化 (state space reduction) 等方法。用戶研究也表明，學生學習 Raft 比學習 Paxos 更容易。

Raft 具備幾個新穎特性：

• 強領導者 (Strong leader) ：Raft 采用比其他共識算法更強的領導者模型。例如，日志條目只從領導者單向流向其他服務器，這簡化了復制日志的管理。
• 領導者選舉 (Leader election) ：Raft 使用隨機化定時器來選舉領導者。這種方式在任何共識算法都必需的心跳機制上僅增加了少量開銷，卻能簡單快速地解決沖突。
• 成員變更 (Membership changes) ：Raft 采用一種新的聯合共識 (joint consensus) 方法進行集群成員變更，通過重疊多數 (overlapping majorities) 來保證安全性。

Raft 被認為在教學和實現兩方面均優于 Paxos，它更簡單、描述更完整、已有多種開源實現并被多家公司采用，同時其安全性和效率也得到了保證。

復制狀態機

共識算法通常應用于 復制狀態機 (replicated state machines, RSMs) 的場景。在 RSM 模型中，一組服務器上的狀態機計算相同狀態的相同副本，并且即使某些服務器宕機也能繼續運行。例如，GFS、HDFS 和 RAMCloud 等系統使用獨立的復制狀態機來管理領導者選舉和存儲配置信息。Chubby 和 ZooKeeper 也是復制狀態機的著名例子。

復制狀態機通常通過 復制日志 (replicated log) 實現，如圖 1 (論文中的 Figure 1) 所示。每臺服務器存儲一個包含一系列命令的日志，其狀態機按順序執行這些命令。由于所有日志包含相同順序的相同命令，且狀態機是確定性的，因此它們會計算出相同的狀態和輸出序列。

圖片

共識算法的核心任務是保持復制日志的一致性。服務器上的共識模塊接收來自客戶端的命令并將其添加到本地日志，然后與其他服務器的共識模塊通信，以確保即使發生故障，每個日志最終都包含相同順序的相同請求。一旦命令被正確復制，每個服務器的狀態機就按日志順序處理它們，并將輸出返回給客戶端。

一個實用的共識算法通常具備以下特性：

• 在所有非拜占庭條件下確保 安全性 (Safety)，即永不返回錯誤結果。
• 只要集群中多數服務器正常運行且能夠相互通信及與客戶端通信，就能保證 可用性 (Availability)。一個典型的五服務器集群可以容忍任意兩臺服務器的故障。
• 不依賴時序來保證日志的一致性；錯誤的時鐘或極端的消息延遲最多導致可用性問題。
• 通常情況下，一條命令只需一輪 RPC 從領導者到多數服務器即可完成；少數慢速服務器不應影響整體系統性能。

Paxos 的問題所在

盡管 Paxos 在共識領域占據主導地位，但它存在兩個顯著缺陷。

第一個缺陷是 Paxos 異常難以理解。其完整解釋晦澀難懂，即使是簡化版本也頗具挑戰性。這種晦澀性可能源于其以 單決策 Paxos (single-decree Paxos) 為基礎的構建方式。單決策 Paxos 本身就密集且微妙，其分為兩個階段，缺乏簡單直觀的解釋且難以獨立理解。

第二個缺陷是 Paxos 沒有為構建實際系統提供良好的基礎。沒有一個被廣泛認可的 多決策 Paxos (multi-Paxos) 算法；Lamport 的描述主要集中在單決策上，對多決策僅給出了大致思路，缺乏許多細節。此外，Paxos 的對等 (peer-to-peer) 核心架構不適合需要做出一系列決策的實際系統；先選舉一個領導者，再由領導者協調決策會更簡單高效。因此，實際系統往往與 Paxos 的原始描述相去甚遠，開發者需要花費大量時間和精力進行修改和擴展，這既耗時又容易出錯。正如 Chubby 的實現者所言：“Paxos 算法的描述與真實世界系統的需求之間存在巨大鴻溝……最終的系統將基于一個未經證明的協議。”

為可理解性而設計

Raft 的設計將可理解性置于首位。設計者不僅希望算法能夠正確、高效地工作，還希望廣大的開發者和學生能夠輕松理解它，并建立起對算法行為的直觀認識。

在設計過程中，Raft 采用了兩種主要技術來增強可理解性：

1. 問題分解 (Problem decomposition) ：將復雜問題分解為若干個相對獨立的子問題，這些子問題可以被獨立解決、解釋和理解。Raft 將共識問題分解為領導者選舉、日志復制、安全性和成員變更幾個部分。
2. 狀態空間簡化 (State space reduction) ：通過減少需要考慮的狀態數量，使系統行為更具一致性，并盡可能消除不確定性。例如，Raft 不允許日志中存在空洞，并限制了日志之間可能出現不一致的方式。值得一提的是，Raft 在領導者選舉中引入的隨機化，雖然是一種不確定性，但它通過以相似方式處理所有可能選擇，反而簡化了狀態空間，提升了理解性。

Raft 共識算法

圖片

Raft 算法用于管理一個復制日志，其整體機制可以參考論文中的圖 2 (Figure 2) 進行概覽，關鍵屬性總結在圖 3 (Figure 3)。Raft 通過選舉一位唯一的 領導者 (leader)，并賦予其管理復制日志的全部職責來實現共識。領導者從客戶端接收日志條目，將其復制到其他服務器上，并告知服務器何時可以安全地將日志條目應用于它們的狀態機。這種領導者模型簡化了復制日志的管理。如果當前領導者失效，則會選舉出新的領導者。

圖片

Raft 將共識問題分解為三個相對獨立的子問題：

• 領導者選舉 (Leader election) ：當現有領導者失效時，必須選舉出新的領導者 (5.2節)。
• 日志復制 (Log replication) ：領導者必須接受來自客戶端的日志條目，并在集群中進行復制，強制其他服務器的日志與自己保持一致 (5.3節)。
• 安全性 (Safety) ：Raft 的關鍵安全屬性是狀態機安全屬性 (State Machine Safety Property)：如果任一服務器已將特定日志條目應用于其狀態機，則其他服務器不能對同一日志索引應用不同的命令 (5.4節)。

Raft 基礎

一個 Raft 集群包含若干服務器，通常是5臺，這樣可以容忍兩臺服務器的故障。在任何時刻，每臺服務器都處于以下三種狀態之一：領導者 (leader)、跟隨者 (follower) 或 候選人 (candidate)。正常情況下，集群中只有一個領導者，其余所有服務器都是跟隨者。跟隨者是被動的，它們不主動發起請求，僅響應來自領導者和候選人的請求。所有客戶端請求都由領導者處理；如果客戶端聯系到跟隨者，跟隨者會將其重定向到領導者。候選人狀態則用于選舉新的領導者。

Raft 將時間劃分為連續的 任期 (terms)，每個任期用一個連續整數編號。每個任期從一次選舉開始，一個或多個候選人嘗試成為領導者。如果一個候選人贏得選舉，它將在該任期的剩余時間內擔任領導者。有時選舉可能以選票分裂告終，導致該任期沒有領導者，此時會很快開始一個新的任期（和新一輪選舉）。Raft 保證在一個給定的任期中最多只有一個領導者。

任期在 Raft 中充當 邏輯時鐘 (logical clock)，允許服務器檢測過時的信息（如陳舊的領導者）。每臺服務器都存儲一個單調遞增的當前任期號 (currentTerm)。服務器通信時會交換 currentTerm；如果一臺服務器的 currentTerm 小于另一臺，它會將自己的 currentTerm 更新為較大的值。如果候選人或領導者發現自己的任期已過時，它會立即轉變為跟隨者狀態。如果服務器收到一個帶有陳舊任期號的請求，它會拒絕該請求。

Raft 服務器之間通過 遠程過程調用 (RPCs) 進行通信。基本的共識算法只需要兩種類型的 RPC：

• RequestVote RPC：由候選人在選舉期間發起 (5.2節)。
• AppendEntries RPC：由領導者發起，用于復制日志條目和作為心跳 (5.3節)。

領導者選舉

Raft 使用心跳機制來觸發領導者選舉。服務器啟動時是跟隨者狀態。只要能從領導者或候選人那里收到有效的 RPC，服務器就保持跟隨者狀態。領導者會向所有跟隨者發送周期性的心跳（不攜帶日志條目的 AppendEntries RPC）以維持其權威。如果一個跟隨者在一段時間（稱為 選舉超時 (election timeout)）內沒有收到任何通信，它就假定當前沒有可行的領導者，并開始一次選舉以選出新的領導者。

開始選舉時，跟隨者會：

1. 增加其本地的 currentTerm。
2. 轉變為候選人狀態。
3. 為自己投票。
4. 并行地向集群中的其他所有服務器發送 RequestVote RPC。

候選人會保持此狀態，直到發生以下三種情況之一：(a) 它贏得選舉；(b) 另一臺服務器確立自己為領導者；(c) 一段時間過去后沒有贏家。

• 贏得選舉 ：候選人從整個集群中超過半數的服務器那里獲得了針對同一任期的選票。每臺服務器在給定的任期內最多只能為一名候選人投票（基于先到先得的原則，并受5.4節中額外限制的約束）。多數決規則確保了在一個特定任期內最多只能有一個候選人贏得選舉（即選舉安全屬性）。一旦候選人獲勝，它就成為領導者，并向所有其他服務器發送心跳消息以建立其權威并阻止新的選舉。
• 發現其他領導者 ：在等待選票期間，候選人可能會收到來自另一臺聲稱是領導者的服務器的 AppendEntries RPC。如果該領導者的任期（包含在其 RPC 中）大于或等于候選人的當前任期，則候選人承認該領導者的合法性并轉換回跟隨者狀態。如果 RPC 中的任期小于候選人的當前任期，則候選人拒絕該 RPC 并繼續保持候選人狀態。
• 沒有贏家（選票分裂） ：如果許多跟隨者同時成為候選人，選票可能會被瓜分，導致沒有候選人獲得多數票。發生這種情況時，每個候選人都會超時，并通過增加其任期號和發起另一輪 RequestVote RPC 來開始新的選舉。

為了確保選票分裂很少發生并且能夠迅速解決，Raft 使用了 隨機化選舉超時 (randomized election timeouts)。選舉超時時間從一個固定的區間內隨機選擇（例如 150-300 毫秒）。這使得服務器的超時時間分散開，在大多數情況下，只有一個服務器會首先超時并發起選舉；它贏得選舉并在其他服務器超時之前發送心跳。處理選票分裂也使用相同的機制：每個候選人在開始選舉時重新啟動其隨機化選舉超時，并等待該超時結束后才開始下一次選舉，這減少了在新選舉中再次發生選票分裂的可能性。

日志復制

一旦選出領導者，它就開始處理客戶端請求。每個客戶端請求都包含一個由復制狀態機執行的命令。領導者將該命令作為新條目追加到其日志中，然后并行地向其他所有服務器發送 AppendEntries RPC 以復制該條目。當條目被安全復制后（如下所述），領導者將該條目應用于其狀態機，并將執行結果返回給客戶端。如果跟隨者崩潰、運行緩慢或網絡丟包，領導者會無限期地重試 AppendEntries RPC（即使在響應客戶端之后），直到所有跟隨者最終都存儲了所有日志條目。

日志條目 (log entries) 包含狀態機命令以及領導者收到該條目時的任期號。每個日志條目還有一個整數索引，標識其在日志中的位置。

圖片

一個日志條目被認為是 已提交的 (committed) 時，意味著它可以安全地應用于狀態機了。Raft 保證已提交的條目是持久的，并且最終會被所有可用的狀態機執行。當創建條目的領導者已在多數服務器上復制了該條目時，該條目即被提交（例如論文圖 6 中的條目 7）。這也同時提交了領導者日志中所有在它之前的條目，包括由先前領導者創建的條目。領導者會跟蹤它所知道的最高已提交條目的索引 (commitIndex)，并在未來的 AppendEntries RPC（包括心跳）中包含該索引，以便其他服務器最終得知。一旦跟隨者得知某個日志條目已提交，它就會按日志順序將該條目應用于其本地狀態機。

Raft 的日志機制旨在維護不同服務器日志之間的高度一致性，這構成了 日志匹配特性 (Log Matching Property)：

1. 如果在不同日志中的兩個條目具有相同的索引和任期，那么它們存儲相同的命令。這是因為領導者在給定的任期內，對于一個給定的日志索引最多只創建一個條目，并且日志條目在日志中的位置永遠不會改變。
2. 如果在不同日志中的兩個條目具有相同的索引和任期，那么這些日志在直到該索引（包括該索引）之前的所有條目上都是相同的。這通過 AppendEntries RPC 執行的一個簡單的一致性檢查來保證：領導者在發送 AppendEntries RPC 時，會包含其日志中緊接在新條目之前的那個條目的索引和任期。如果跟隨者在其日志中找不到具有相同索引和任期的條目，它就會拒絕新的條目。

圖片

正常操作期間，領導者和跟隨者的日志保持一致，因此 AppendEntries 的一致性檢查永遠不會失敗。然而，領導者崩潰可能會導致日志不一致（舊領導者可能沒有完全復制其日志中的所有條目）。這些不一致性可能在一系列領導者和跟隨者崩潰中累積（如論文圖 7 所示）。

Raft 中，領導者通過強制跟隨者的日志復制自己的日志來處理不一致性。這意味著跟隨者日志中沖突的條目將被領導者日志中的條目覆蓋。為了使跟隨者的日志與自己的日志一致，領導者必須找到兩個日志一致的最新日志條目，刪除該點之后跟隨者日志中的所有條目，并向跟隨者發送該點之后領導者日志中的所有條目。這些操作都是響應 AppendEntries RPC 的一致性檢查而發生的。

領導者為每個跟隨者維護一個 nextIndex，即領導者將要發送給該跟隨者的下一個日志條目的索引。當領導者剛上任時，它會將所有 nextIndex 值初始化為其日志中最后一個條目之后的索引。如果跟隨者的日志與領導者的不一致，下一次 AppendEntries RPC 中的一致性檢查將會失敗。在被拒絕后，領導者會遞減 nextIndex 并重試 AppendEntries RPC。最終 nextIndex 會達到一個領導者和跟隨者日志匹配的點。此時 AppendEntries 將成功，它會移除跟隨者日志中任何沖突的條目，并追加來自領導者日志的條目（如果有）。一旦 AppendEntries 成功，跟隨者的日志就與領導者的日志一致了，并且在該任期的剩余時間里都將保持這種狀態。

通過這種機制，領導者上任時無需采取任何特殊操作來恢復日志一致性。它只需開始正常操作，日志就會在 AppendEntries 一致性檢查失敗時自動趨于一致。領導者從不覆蓋或刪除其自身日志中的條目（領導者只追加屬性）。

安全性

前面描述的領導者選舉和日志復制機制尚不足以確保每個狀態機以完全相同的順序執行完全相同的命令。例如，一個跟隨者可能在領導者提交若干日志條目時不可用，然后它可能被選為領導者并用新的條目覆蓋這些已提交的條目。本節通過增加一個關于哪些服務器可以被選舉為領導者的限制來完善 Raft 算法。這個限制確保了任何給定任期的領導者都包含先前任期中所有已提交的條目（領導者完整性屬性）。

選舉限制 (Election restriction)

在任何基于領導者的共識算法中，領導者最終必須存儲所有已提交的日志條目。Raft 采用一種更簡單的方法，它保證從選舉的那一刻起，每個新領導者都擁有先前任期中所有已提交的條目，而無需將這些條目傳輸給領導者。這意味著日志條目只從領導者單向流向跟隨者，并且領導者從不覆蓋其日志中的現有條目。

Raft 利用投票過程來阻止一個候選人贏得選舉，除非其日志包含了所有已提交的條目。候選人為了當選必須聯系集群中的多數服務器，這意味著每個已提交的條目必須存在于該多數服務器中的至少一個服務器上。如果候選人的日志至少與該多數服務器中任何其他日志一樣“最新”（“最新”的定義如下），那么它將持有所有已提交的條目。RequestVote RPC 實現了這一限制：RPC 中包含了關于候選人日志的信息，如果投票者自己的日志比候選人的日志更新，則它會拒絕投票。

Raft 通過比較日志中最后條目的索引和任期來判斷兩個日志哪個更新：

• 如果日志的最后條目具有不同的任期，則具有較晚任期的日志更新。
• 如果日志以相同的任期結束，則較長的日志更新。

提交先前任期的條目 (Committing entries from previous terms)

如 5.3 節所述，領導者知道其當前任期的一個條目一旦存儲在多數服務器上就被提交了。如果領導者在提交一個條目之前崩潰，未來的領導者將嘗試完成該條目的復制。然而，領導者不能僅僅因為一個先前任期的條目存儲在多數服務器上，就立即斷定該條目已提交。論文中的圖 8 展示了一種情況：一個舊的日志條目存儲在多數服務器上，但仍可能被未來的領導者覆蓋。

圖片

為了消除如圖 8 所示的問題，Raft 規定：從不通過計算副本數來提交先前任期的日志條目 。只有領導者當前任期的日志條目才通過計算副本數來提交。一旦當前任期的某個條目以這種方式提交，那么所有先前的條目都會因為日志匹配特性而間接提交。Raft 采取這種更保守的方法是為了簡化設計。

這種提交規則的復雜性源于當領導者復制先前任期的條目時，日志條目會保留其原始任期號。Raft 的這種方法使得推理日志條目更容易，因為它們在不同時間和不同日志中保持相同的任期號。此外，與其他算法相比，Raft 中的新領導者發送的先前任期的日志條目更少。

安全性論證 (Safety argument)

有了完整的 Raft 算法，現在可以更精確地論證 領導者完整性屬性 (Leader Completeness Property) 成立。該論證采用反證法。

假設 T 任期的領導者 leaderT 提交了其任期內的一個日志條目，但該條目未被某個未來任期 U (U > T) 的領導者 leaderU 存儲。

圖片

1. 該已提交條目在 leaderU 當選時必然不在其日志中（領導者從不刪除或覆蓋條目）。
2. leaderT 在集群的多數服務器上復制了該條目，而 leaderU 從集群的多數服務器獲得了選票。因此，至少有一個服務器（稱為“投票者”）既接受了來自 leaderT 的條目，也投票給了 leaderU （如圖 9 所示）。
3. 投票者必須在投票給 leaderU 之前就接受了來自 leaderT 的已提交條目；否則，它會拒絕來自 leaderT 的 AppendEntries 請求（因為它的當前任期會高于 T）。
4. 投票者在投票給 leaderU 時仍然存儲著該條目，因為所有中間的領導者都包含該條目（根據假設），領導者從不移除條目，而跟隨者只有在與領導者沖突時才移除條目。
5. 投票者將選票投給了 leaderU，因此 leaderU 的日志必須至少與投票者的日志一樣新。這將導致以下兩種矛盾之一：

如果投票者和 leaderU 的最后日志任期相同，那么 leaderU 的日志必須至少與投票者的日志一樣長，因此其日志包含了投票者日志中的每個條目。這與假設（leaderU 不包含該已提交條目，而投票者包含）相矛盾。

否則，leaderU 的最后日志任期必須大于投票者的最后日志任期。而且，它也大于 T，因為投票者的最后日志任期至少是 T（它包含來自 T 任期的已提交條目）。創建 leaderU 最后日志條目的先前領導者在其日志中必須包含該已提交條目（根據假設）。那么，根據日志匹配特性，leaderU 的日志也必須包含該已提交條目，這又是一個矛盾。

6. 至此，矛盾論證完畢。因此，所有大于 T 的任期的領導者都必須包含 T 任期中在該任期提交的所有條目。

圖片

有了領導者完整性屬性，就可以證明論文圖 3 中的 狀態機安全屬性 (State Machine Safety Property)：如果一臺服務器已將某個給定索引的日志條目應用于其狀態機，則其他服務器永遠不會對同一索引應用不同的日志條目。當服務器將日志條目應用于其狀態機時，其日志必須與領導者的日志在該條目之前（包括該條目）完全相同，并且該條目必須是已提交的。現在考慮任何服務器應用給定日志索引的最低任期；領導者完整性屬性保證所有更高任期的領導者都將存儲相同的日志條目，因此在后續任期中應用該索引的服務器將應用相同的值。

最后，Raft 要求服務器按日志索引順序應用條目。結合狀態機安全屬性，這意味著所有服務器都將以相同的順序將完全相同的日志條目集應用于其狀態機。