In Search of Understandable Consensus Algorithm

摘要

Raft是一種管理復制日志的共識算法。它產生與（多）Paxos等效的結果，并且與Paxos一樣高效，但其結構與Paxos不同。這使得Raft比Paxos更易理解，也為構建實際系統提供了更好的基礎。為了增強可理解性，**Raft將共識的關鍵元素（如領導選舉，日志復制和安全性）分離，并強制執行更強的一致性以減少必須考慮的狀態數。**用戶研究的結果表明，相比于Paxos，Raft更容易學習。Raft還包括一種改變集群成員關系的新機制，它使用重疊多數來保證安全性。

一、簡介

共識算法允許一組機器作為一個協調一致的群體工作，可以在其中一些成員發生故障時仍然正常運行。因此，它們在構建可靠的大規模軟件系統中起著關鍵作用。在過去的十年中，Paxos [15, 16]主導了共識算法的討論：大多數共識的實現都基于Paxos或受其影響，并且Paxos已成為教授學生共識的主要工具。

不幸的是，盡管進行了許多努力以使Paxos更易理解，但它仍然相當難以理解。此外，它的架構需要復雜的改變來支持實際系統。因此，系統構建者和學生對Paxos感到困難。

Paxos在實際系統中較難實現

在自己努力應付 Paxos 算法后，我們決定尋找一種新的共識算法，為系統構建和教育提供更好的基礎。我們的方法與眾不同，主要目標是可理解性：我們能否定義一個適用于實際系統的共識算法，并以一種比 Paxos 更容易學習的方式描述它？此外，我們希望該算法能夠促進系統構建者必不可少的直覺發展。算法不僅在工作上至關重要，而且其工作原理也應該顯而易見。

這項工作的結果是一種稱為Raft的共識算法。在設計Raft時，我們應用了特定的技術來提高可理解性，包括分解（Raft將領導選舉、日志復制和安全性分離）和狀態空間的減少（相對于Paxos，Raft減少了非確定性程度和服務器之間可能不一致的方式）。在兩所大學進行的43名學生的用戶研究表明，Raft比Paxos更容易理解：在了解這兩種算法后，這些學生中有33名學生能夠更好地回答關于Raft的問題而不是關于Paxos的問題。

Raft在許多方面與現有的共識算法相似（尤其是Oki和Liskov的Viewstamped Replication [29, 22]），但它有幾個新穎的特點：

• 強大的領導者：Raft使用比其他共識算法更強大的領導形式。例如，**日志條目僅從領導者流向其他服務器。**這簡化了復制日志的管理，并使Raft更易于理解。
• 選舉領導者：Raft 使用隨機計時器來選舉領導者。這只為任何共識算法所需的心跳添加了一小部分機制，同時簡單且迅速地解決沖突。
• 成員變動：Raft的機制用于在集群中更改服務器集的使用新的聯合共識方法，在過渡期間兩個不同配置的多數派重疊。這使得集群在配置變化期間可以正常運行。

我們相信Raft在教育目的和作為實現基礎上都優于Paxos和其他一致性算法。它比其他算法更簡單、更易理解；它的描述足夠完整以滿足實際系統的需求；它有幾個開源實現并且被幾家公司使用；它的安全性特性已被明確規定和證明；它的效率與其他算法相當。

本文的其余部分介紹了復制狀態機問題（第2節），討論了Paxos的優點和缺點（第3節），描述了我們對可理解性的一般方法（第4節），呈現了Raft共識算法（第5-8節），評估了Raft（第9節），并討論了相關工作（第10節）。

二、復制狀態機

共識算法通常出現在復制狀態機的上下文中[37]。在這種方法中，一組服務器上的狀態機計算相同的狀態的相同副本，并且即使其中一些服務器宕機，它們也可以繼續運行。復制狀態機用于解決分布式系統中的各種容錯問題。例如，具有單個集群領導者的大規模系統，例如GFS [8]，HDFS [38]和RAMCloud [33]，通常使用單獨的復制狀態機來管理領導者選舉并存儲必須幸免于領導者崩潰的配置信息。復制狀態機的示例包括Chubby [2]和ZooKeeper [11]。

復制狀態機通常使用復制日志進行實現，如圖1所示。每個服務器存儲包含一系列命令的日志，其狀態機按順序執行這些命令。**每個日志以相同的順序包含相同的命令，因此每個狀態機處理相同的命令序列。**由于狀態機是確定性的，每個狀態機計算相同的狀態和相同的輸出序列。

保持復制日志一致是共識算法的工作。①服務器上的共識模塊接收來自客戶端的命令并將其添加到其日志中。②它與其他服務器上的共識模塊通信，以確保每個日志最終都包含相同的請求，并按相同的順序，即使某些服務器失敗。③一旦命令被正確復制，每個服務器的狀態機按照日志順序處理它們，④并將輸出返回給客戶端。結果，服務器們看起來形成了一個單一的、高度可靠的狀態機。

對于實際系統而言，共識算法通常具有以下特性：

• 在所有非拜占庭條件下，包括網絡延遲、分區、數據包丟失、復制和重排序，它們可以確保安全性（永不返回錯誤的結果）。
• 只要大多數服務器仍在運行且能夠相互之間和與客戶端通信，它們就具有完全功能（可用）。因此，一個典型的由五個服務器組成的集群能夠容忍任意兩個服務器的故障。假設服務器由于停止而發生故障；他們可以稍后從穩定存儲的狀態中恢復并重新加入集群。
• 它們并不依賴于時序來確保日志的一致性：有問題的時鐘和極端的消息延遲最多會導致可用性問題。
• 在一般情況下，只要多數節點在進行一輪遠程過程調用后作出響應，一個命令就能完成；少數較慢的服務器不會影響整體系統性能。

三、設計以增加可理解性

我們在設計Raft時有幾個目標：它必須為系統建設提供完整而實用的基礎，從而大大減少開發人員所需的設計工作量；在所有情況下都必須安全，并在典型的操作條件下可用；對于常見操作來說必須高效。但是我們最重要的目標，并且也是最困難的挑戰，是可理解性。它必須能夠讓廣大受眾輕松理解算法。此外，還必須能夠對算法產生直觀感受，以便系統構建者能夠在現實世界的實現中進行不可避免的擴展。

設計Raft時，我們在許多方面需要選擇不同的方法。在這些情況下，我們通過可理解性來評估不同的選擇：每一種選擇有多難解釋（例如，它的狀態空間有多復雜，是否存在微妙的影響？），讀者能夠完全理解這種方法及其影響力有多容易？

我們認識到這樣的分析具有很高的主觀性；盡管如此，我們使用了一種普遍適用的兩種技術。第一種技術是眾所周知的問題分解方法：只要可能，我們將問題分解成可以相對獨立地解決、解釋和理解的獨立部分。例如，在Raft中，我們將領導者選舉、日志復制、安全性和成員變更進行了分離。

我們的第二種方法是通過減少要考慮的狀態數量來簡化狀態空間，使系統更加連貫，并盡可能消除非確定性。具體而言，不允許日志有空洞，而且Raft限制了日志之間可能發生不一致的方式。盡管在大多數情況下我們試圖消除非確定性，但在一些情況下，非確定性實際上會提高可理解性。特別是，隨機化方法引入了非確定性，但它們傾向于通過以類似的方式處理所有可能的選擇來減少狀態空間（“選擇任何一個都可以，沒關系”）。我們使用隨機化來簡化Raft的領導者選舉算法。

四、Raft算法

Raft是一種用于管理復制日志的算法，其形式在第2節中進行了描述。圖2以簡潔的形式總結了該算法供參考，圖3列出了該算法的關鍵屬性；這些圖的要素在本節的其他部分逐步討論。

Raft是通過首先選舉出一位杰出的領導者，然后將完全負責管理復制日志的責任交給該領導者來實現一致性。領導者接受來自客戶端的日志條目，將其復制到其他服務器上，并告訴服務器何時安全地將日志條目應用到其狀態機上。擁有領導者簡化了復制日志的管理。例如，領導者可以決定在日志中的哪個位置放置新的條目，而無需咨詢其他服務器，數據從領導者流向其他服務器的方式也是簡單的。領導者可能會失敗或與其他服務器斷開連接，這種情況下會選舉出新的領導者。

領導者的作用：

• 日志復制
• 日志提交
• 簡化復制管理，如領導者可以決定在日志中哪個位置放置新的條目，無需咨詢其他服務器。數據從領導者流向其他服務器的方式也是簡單的。領導者失敗了，那么選出新的領導者

給定領導者的方法，Raft將一致性問題分解成三個相對獨立的子問題，這些問題在接下來的小節中進行了討論。

• 領導選舉：當現任領導者失敗時，必須選擇新的領導者（第5.2節）。
• 日志復制：領導者必須接受來自客戶端的日志條目，并將它們復制到整個集群中，迫使其他日志與其一致（第5.3節）。
• 安全性：Raft的關鍵安全屬性是圖3中的狀態機安全屬性：如果任何服務器已將特定日志項應用于其狀態機，則其他服務器不得為相同的日志索引應用不同的命令。第5.4節描述了Raft如何確保此屬性；解決方案涉及對第5.2節中描述的選舉機制的額外限制。

在介紹共識算法之后，本節討論系統的可用性問題和時間在其中的作用。

Raft基礎

Raft集群包含多個服務器，五個是典型的數量，這使系統能夠容忍兩個故障。在任何給定的時間，每個服務器處于三種狀態之一：領導者、追隨者或候選人。在正常的運行中，正好有一個領導者，所有其他服務器都是追隨者。追隨者是被動的：他們自己不發出請求，只是回應領導者和候選人的請求。領導者處理所有客戶端請求（如果客戶端聯系追隨者，追隨者將其重定向到領導者）。候選人這個狀態用于在5.2小節中描述的選舉新領導者。圖4展示了這些狀態及其轉換過程；轉換過程將在下面討論。

五個服務器，容忍2個故障。

服務器處于三種狀態之一：

• 領導人：處理所有客戶端的請求
• 追隨者：回應候選人和領導者的請求

正常的運行只有一個領導者，其余都是追隨者。

Raft 將時間分為任意長度的時期，如圖5所示。這些時期按連續整數進行編號。每個時期都從選舉開始，候選人嘗試成為領導者，如第5.2節所述。如果候選人贏得選舉，那么它將在該時期的其余時間擔任領導者。**在某些情況下，選舉會導致投票分裂。在這種情況下，該時期將在沒有領導者的情況下結束；**不久將開始一個新的時期（帶有新的選舉）。Raft 確保在給定時期內至多只有一個領導者。

不同的服務器可能在不同的時間觀察到任期之間的轉換，在某些情況下，服務器甚至可能沒有觀察到選舉或整個任期。任期在Raft中充當邏輯時鐘[14]，它們允許服務器檢測過時的信息，如陳舊的領導者。每個服務器存儲一個當前任期號碼，它隨時間單調遞增。當前任期在服務器通信時進行交換；**如果一個服務器的當前任期較小，則將其當前任期更新為較大的值。**如果候選人或領導者發現其任期已過時，則立即恢復為跟隨者狀態。如果服務器收到具有過時任期號碼的請求，則拒絕該請求。

加粗，不理解。

Raft服務器使用遠程過程調用(RPC)進行通信，基本的一致性算法只需要兩種類型的RPC。RequestVote RPC由候選人在選舉期間發起(第5.2節)，AppendEntries RPC由領導者發起以復制日志條目并提供一種心跳機制(第5.3節)。第7節增加了第三種RPC用于在服務器之間傳輸快照。如果服務器未能及時收到響應，它們會重試RPC，并并行發出RPC以獲得最佳性能。

兩種RPC：

• RequestVote RPC：候選人在選舉期間發起
• AppendEntries RPC：領導者發起，兩種用途：
  • 復制日志條目
  • 提供心跳機制

增加了一種RPC用以在服務器之間傳輸快照。服務器未能及時響應，那么并行發出RPC以獲得最佳性能。

領導人選舉

Raft使用心跳機制來觸發領導者選舉。當服務器啟動時，它們作為跟隨者開始。只要服務器從領導者或候選人接收到有效的RPC（遠程過程調用），它就保持在跟隨者狀態。領導者定期發送心跳（不攜帶日志條目的AppendEntries RPC）給所有跟隨者，以維持其權威性。如果一個跟隨者在一段被稱為選舉超時的時間內沒有通信，那么它就會假定沒有可行的領導者，并開始進行選舉以選擇一個新的領導者。

心跳機制觸發領導人選舉：心跳過期，那么開始選舉

開始選舉，追隨者增加其當前任期并轉換為候選人狀態。然后，它為自己投票并并行向集群中的每個其他服務器發出請求選票的RPC。候選人將保持在這個狀態，直到以下三種情況發生之一：（a）它贏得選舉，（b）另一個服務器建立為領導者，或者（c）一段時間過去沒有獲勝者。這些結果在下面的段落中分別討論。

開始選舉的動作：

• 追隨者：追加任期，轉換為候選人狀態【所有的追隨者都要追加任期嗎？還是僅僅發起投票的追隨者追加任期】
• 候選人：為自己投票，向集群中的其他每個服務器發出請求選票RPC RequestVote RPC，候選人將保持這個狀態，直到：
  • 贏得選舉
  • 另一個服務器成為領導者
  • 一段時間過去了，但沒有獲勝者

一名候選人如果獲得整個集群中大多數服務器在同一屆中的選票，則贏得選舉。每個服務器在給定屆中最多只能為一個候選人投票，按照先到先得的原則（注：第5.4節增加了對投票的額外限制）。多數規則確保在特定屆中最多只能有一個候選人獲勝（圖3中的選舉安全特性）。一旦候選人贏得選舉，它將成為領導者。然后，它向其他所有服務器發送心跳消息，以確立其權威并防止新的選舉。

贏得選舉的情況：獲得大多數選票，確保只有一個候選人獲勝

選舉規則：先到先得（額外限制）【似乎是對日志條目有要求】

贏得選舉后：

• 成為領導者
• 向其他所有服務器發送心跳信息，確立權威，防止新的選舉

Note：會不會出現一次選舉結束，還沒來得及樹立權威（RPC需要一定時間），另一個服務器心跳才剛剛過期，然后立馬又開啟選舉的情況？

在等待投票時，候選人可能會收到一條來自另一臺聲稱自己是領導者的服務器的AppendEntries RPC。如果領導者的任期（包含在其RPC中）至少與候選人當前的任期一樣大，則候選人將承認領導者的合法性，并返回到follower狀態。如果RPC中的任期小于候選人當前的任期，則候選人拒絕該RPC，并繼續處于候選人狀態。

另一個服務器成為領導者的情況：

解決了上述問題，發起選舉要加任期，可以根據收到的選舉請求RequestVote的RPC請求中的任期進行操作。

• 任期>=自己的任期：新的領導人已經出現，放棄選舉
• 任期小：可能是過期的消息，拒絕RPC，繼續候選人。

第三種可能的結果是候選人既不贏得選舉，也不輸掉選舉：如果許多追隨者同時成為候選人，選票可能被分割，以至于沒有候選人獲得多數票。當出現這種情況時，每個候選人將超時并通過增加其任期并啟動另一輪RequestVote RPCs來開始新的選舉。然而，如果沒有額外措施，分割的選票可能會無限重復。

無獲勝領導人：原因是多個候選人一起發起投票，選票瓜分

動作：

• 每個候選人超時，并啟動新一輪選舉

沒有額外機制保障，分割選票的可能會無限重復

Raft利用隨機的選舉超時來確保分裂投票是罕見的，并且盡快解決它們。為了防止分裂投票，在第一次選舉時，選舉超時是從一個固定的時間間隔中隨機選擇的（例如，150-300毫秒）。這樣分散了服務器，以至于在大多數情況下，只有一個服務器會超時；它贏得選舉并在其他任何服務器超時之前發送心跳。同樣的機制用于處理分裂投票。每個候選者在選舉開始時重新啟動其隨機化的選舉超時，并且在開始下一次選舉之前等待超時的過去；這減少了新選舉中發生另一次分裂投票的可能性。第9.3節顯示了這種方法能夠迅速選出一位領導者。

選票被瓜分，等待一段時間再啟動新的一輪RequestRPC

每個進程設置的等待時間是隨機分散在150-300ms之間的，以分散服務器

大多數情況下只有一個服務器會超時

超時后會啟動新的RPC，他的任期增加，比其他的follower任期都要大。其他的follower收到任期比他還大的任期，那么放棄選舉。

Note：放棄選舉的方式是什么？什么都不做？還是要投票？

選舉是一個例子，說明了我們在設計選擇之間是如何根據可理解性來做出選擇的。最初，我們計劃使用一個排名系統：每個候選人被分配一個唯一的排名，然后用該排名來選擇競爭的候選人。如果一個候選人發現了一個排名更高的候選人，它將回到追隨者狀態，以便排名更高的候選人可以更容易地贏得下一次選舉。我們發現這種方法在可用性方面存在一些微妙的問題（如果一個排名較低的服務器需要超時并再次成為候選人，但如果它這樣做得太快，會重置選舉領導者的進度）。我們對算法進行了幾次調整，但每次調整后都出現了新的特殊情況。最終，我們得出結論，隨機重試的方法更加明顯和可理解。

日志復制

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

領導者復制日志的動作：

• 追加客戶請求到日志條目
• 并行發出AppendEntries RPC以復制日志條目到客戶端
• 安全復制（什么是安全復制？）后，領導者將條目應用于狀態機
• 執行結果返回客戶端
• 如果出現追隨者崩潰等情況，領導者無限次嘗試AppendEntries RPC，直到所有追隨者最終存儲所有的日志條目

日志按照圖6所示進行組織。每個日志條目存儲了在其被領導者接收時的狀態機命令以及任期號。日志條目中的任期號用于檢測日志之間的不一致，并確保圖3中的某些屬性。每個日志條目還有一個整數索引，用于標識其在日志中的位置。

日志條目內容：

• 狀態機命令
• 任期號碼：檢測日志之間的不一致
• 整數索引：標識日志的位置

領導者決定何時安全地將日志項應用到狀態機；這樣的項被稱為已提交。 Raft算法保證已提交的項是持久的，并且最終會被所有可用的狀態機執行。一旦創建該項的領導者在大多數服務器上復制了該項（例如，在圖6中的項7中），則日志項被提交。這還會提交領導者日志中的所有先前項，包括之前的領導者創建的項。第5.4節討論了在領導者更改后應用此規則時的一些細微之處，并且還表明了這種承諾定義的安全性。領導者跟蹤其已知的最高索引已被提交，并將該索引包括在以后的AppendEntries RPC中（包括心跳），以便其他服務器最終找出。一旦跟隨者了解到日志項已提交，它將按日志順序將該項應用于其本地狀態機。

提交：將日志項應用到狀態機

安全地復制：大多數服務器復制了該項，日志被提交。還會提交領導者日志中的所有先前項，包括之前領導者創建的項。

日志被提交后：被提交的最高索引將包括在以后的AppendEntriesRPC中（包括心跳），保證被跟隨者捕捉到日志提交信息。

• 提交之前的領導者的項==【會不會重復提交？】==

我們設計了Raft日志機制，以保持不同服務器上日志的高度一致性。這不僅簡化了系統的行為，使其更加可預測，而且還是確保安全性的重要組成部分。Raft具有以下特性，這些特性共同構成圖3中的日志匹配屬性。

• 如果兩個不同的日志中的條目具有相同的索引和任期，那么它們存儲的是相同的命令。
• 如果兩個不同日志中的條目具有相同的索引和任期，則在所有之前的條目中，這兩個日志是相同的。

第一個屬性源于一個事實：在給定的任期和給定的日志索引中，一個領導者最多創建一個條目。日志條目永遠不會改變它們在日志中的位置。第二個屬性通過AppendEntries執行的簡單一致性檢查保證。在發送AppendEntries RPC時，領導者在其日志中的新條目包含了有關條目之前的索引（preLogIndex）和任期（preLogTerm）的信息。如果跟隨者在其日志中找不到具有相同索引和任期的條目，則拒絕新的條目。一致性檢查作為歸納步驟：日志的初始空狀態滿足日志匹配屬性，并且每當日志被擴展時，一致性檢查都保持日志匹配屬性。因此，每當AppendEntries成功返回時，領導者都知道跟隨者的日志與其自身的日志一致，直到新條目。

拒絕新的條目會補發嗎？【已解決】

如果兩個日志中的條目在索引和任期上相同，則在所有先前條目中，這兩個日志相同。在正常操作期間，領導者和跟隨者的日志保持一致，因此AppendEntries一致性檢查永遠不會失敗。然而，領導者崩潰可能會導致日志不一致（舊的領導者可能沒有完全復制其日志中的所有條目）。這些不一致性可能會在一系列領導者和跟隨者的崩潰中累積。圖7說明了跟隨者的日志可能與新領導者的日志不同的方式。跟隨者可能會缺少領導者存在的條目，可能會有領導者不存在的額外條目，或者兩者都可能存在。日志中缺少和多余的條目可以跨越多個任期。

不一致的原因：舊的領導者沒有完全復制其日志

不一致情形：

• 日志多了
• 日志少了

可能跨越多個任期

在Raft中，領導者通過強制追隨者的日志復制自己的日志來處理不一致。這意味著追隨者日志中的沖突條目將被領導者日志中的條目覆蓋。第5.4節將證明，當與一項額外限制相結合時，這是安全的。

解決方案：強制追隨者的日志復制自己的日志

額外限制：領導者自己具有最新的日志條目

為了使跟隨者的日志與自己的一致，領導者必須找到兩個日志達成一致的最新日志條目，刪除該點之后跟隨者日志中的任何條目，并將該點之后領導者的所有條目發送給跟隨者。所有這些操作都是作為AppendEntries RPC執行的一致性檢查的響應而發生的。**領導者為每個跟隨者維護一個nextIndex，它是領導者將發送給該跟隨者的下一個日志條目的索引。**當領導者首次獲得權力時，它初始化所有的nextIndex值為其日志中最后一個索引之后的索引（在圖7中為11）。如果一個跟隨者的日志與領導者的日志不一致，在下一個AppendEntries RPC中，AppendEntries一致性檢查將失敗。在被拒絕之后，領導者會減小nextIndex并重試AppendEntries RPC。最終，nextIndex將達到一個領導者和跟隨者日志匹配的點。當發生這種情況時，AppendEntries將成功，它會移除跟隨者日志中的任何沖突條目，并追加來自領導者日志的條目（如果有）。一旦AppendEntries成功，跟隨者的日志將與領導者保持一致，并且在該任期的剩余時間內保持一致。

如果需要的話，可以對協議進行優化，以減少被拒絕的AppendEntries RPC的數量。例如，在拒絕一個AppendEntries請求時，追隨者可以包含沖突條目的任期和其存儲的第一個索引。有了這些信息，領導者可以遞減nextIndex以繞過所有該任期中的沖突條目；每個有沖突條目的任期只需要一個AppendEntries RPC，而不是每個條目一個RPC。實際上，我們懷疑這種優化是不必要的，因為故障發生得很少，而且不太可能存在許多不一致的條目。

AppendEntries一致性檢查達成一致的方式：

• 找到兩個日志達成一致的最新日志條目
• 刪除該點之后跟隨者日志中的任何條目
• 領導者的所有條目發給跟隨者

領導者為每個跟隨者維護一個nextIndex，該值初始化為領導者最后一個日志的下一個日志的索引。

AppendEntries失敗的情況：

• 逐漸少nextIndex的值，直到和領導者匹配==（nextIndex和preLogIndex難道不是發送一個就行了嗎？為什么要發送兩個？）==
• AppendEntries：匹配到一致的日志條目后，刪除之后的條目，追加自己的條目。
• 一旦一致，那么剩余任期內一致。

使用該機制，當權力更替發生時，領導者不需要采取任何特殊行動來恢復日志的一致性。它只需開始正常運行，日志會自動在附加條目一致性檢查失敗的情況下收斂。領導者永遠不會覆蓋或刪除其自己日志中的條目（圖 3 中的領導者僅附加屬性）。

該日志復制機制展現了第 2 節中描述的理想共識屬性：只要大多數服務器可用，Raft 就可以接受、復制和應用新的日志條目；在正常情況下，新條目可以通過向大多數集群進行一輪 RPC 復制；單個緩慢的跟隨者不會影響性能。

安全

前面的章節描述了Raft如何選舉領導者并復制日志條目。然而，迄今為止描述的機制還不足以確保每個狀態機以相同的順序執行完全相同的命令。例如，一個追隨者在領導者提交多個日志條目時可能不可用，然后它可能會被選為領導者并用新的條目覆蓋這些條目；結果，不同的狀態機可能會執行不同的命令序列。

“不可用”日志的概念

1. 領導者選舉和日志復制的不一致：Raft算法通過復制日志條目來確保一致性。如果一個領導者在它的任期內沒有將一個日志條目成功復制到大多數節點上**（即AppendEntries失敗），那么這個條目就被認為是"不可用"**的。如果此時發生選舉，并且另一個節點成為新的領導者，新領導者可能不知道之前未復制成功的日志條目。
   1. ——這種情況難道不是用領導者的日志直接覆蓋這些日志嗎？
2. 新的領導者覆蓋日志條目：在沒有安全措施的情況下，新的領導者可能會在自己的日志中添加新條目，并強制其他節點接受這些新條目，從而覆蓋了舊的、未復制成功的條目。這就導致了狀態機在不同節點上執行不同的命令序列。

本部分通過對哪些服務器可以被選為領導者的限制，完成了Raft算法。該限制確保了給定任期的領導者包含在之前任期中已經被提交的所有條目（來自第3圖的領導者完全性屬性）。在給出選舉限制之后，我們進一步將提交規則描述得更加精確。最后，我們提供了領導者完全性屬性的證明概要，并展示了它如何導致復制狀態機的正確行為。

選舉限制

在任何以領導者為基礎的共識算法中，領導者最終必須存儲所有已提交的日志條目。在某些共識算法中，如Viewstamped Replication [22]，即使最初不包含所有已提交的條目，也可以選舉出領導者。這些算法包含額外的機制，以識別缺失的條目并將其傳輸給新領導者，可以在選舉過程中或之后的短時間內完成。不幸的是，這導致了相當大的附加機制和復雜性。Raft使用了一種更簡單的方法，它保證了上一任期的所有已提交的條目在每個新領導者的選舉時刻都可以找到，而不需要將這些條目傳輸給領導者。這意味著日志條目只從領導者流向追隨者，領導者從不覆蓋其日志中的現有條目。

領導者的日志具有完整性——包含所有已經提交的日志條目

Raft保證上一任期所有已經提交的條目在每個領導者的選舉時刻都可以找到，而不需要將這些條目傳輸給領導者。

Raft使用投票過程來防止候選人在選舉中獲勝，除非它的日志包含所有已提交的條目。候選人必須與大多數集群聯系，才能當選，這意味著每個已提交的條目必須至少存在于這些服務器中的一個。如果候選人的日志至少與大多數其他日志一樣更新（其中“更新”在下面被準確地定義），**那么它將包含所有已提交的條目。**RequestVote RPC實現了這一限制：RPC包括有關候選人日志的信息，如果投票者自己的日志比候選人的日志更新，則投票者將否決其投票。

這里使用的是“已經提交”，但是不是未完成復制的日志也可能會造成不一致的狀態機嗎？為何只要求領導者具有完整的已經提交的日志，而不要求他有目前最新的日志（該日志可以沒被提交）。

如何判斷包含所有的已提交條目？

• 如果其日志至少與其他日志一樣更新，那么它將包含所有已提交的條目。

如何保障該機制？

• RequestVote RPC實現，RPC中包含候選人日志的信息，如果投票者自己的日志比候選人的日志更新，那么將否則其投票。

上述實現是保障選舉出的領導者的日志與大多數其他日志是一樣新的。

（但是似乎還是不能避免第一個例子的情況？存在某個領導人他還沒來得及復制完這些日志，比如5個機器，他只復制了1個，那么剩下四個機器選舉，還是能得到三個選票而勝出，勝出后，是不是還是可能導致領導者強制復制日志）

Raft通過比較日志中最后條目的索引和任期來確定哪個日志更為最新。如果日志的最后條目具有不同的任期，則具有較晚任期的日志更為最新。如果日志以相同的任期結束，則較長的日志更為最新。

更長的日志為最新是什么機制？

• 這里的更長指的就是index更大。

即，更新的判斷機制：

• 任期越大越新
• 任期相同，看索引號

提交過去任期的條目

根據第5.3節的描述，領導者知道只要其當前任期的條目在大多數服務器上存儲，就會提交該條目。**如果領導者在提交條目之前崩潰，將來的領導者將嘗試完成復制該條目的過程。**然而，領導者不能立即得出結論，即一條來自先前任期的條目一旦在大多數服務器上存儲，就已經提交。圖8闡明了這樣一種情況，即舊的日志條目雖然存儲在大多數服務器上，但仍然可以被將來的領導者覆蓋。

圖8：一個時間序列顯示了為什么領導者無法使用舊任期的日志條目來確定承諾。在（a）中，S1是領導者，并且部分復制了索引2處的日志條目。在（b）中，S1崩潰；S5被選為第三個任期的領導者，獲得了S3、S4和自己的選票，并接受了索引2處的不同條目。在（c）中，S5崩潰；S1重新啟動，被選為領導者，并繼續復制。此時，第2個任期的日志條目已在大多數服務器上復制，但尚未提交。如果S1像（d）中那樣崩潰，S5可以被選為領導者（獲得S2、S3和S4的選票），并用自己在第3個任期的條目覆蓋該條目。然而，如果S1在崩潰之前在大多數服務器上復制了當前任期的條目，如（e）中的情況，那么該條目被提交（S5無法贏得選舉）。此時，日志中的所有前面的條目也都被提交了。

只保證大多數機器正常的時候是成功的，如果大多數失敗了，那么協議并不能保證一致性。

為了消除類似于圖8中的問題，Raft通過計數副本的方式不會提交來自先前任期的日志條目。**只有來自領導者當前任期的日志條目被計數副本提交；****一旦通過這種方式提交了當前任期中的條目，那么之前的所有條目都間接地因為日志匹配特性而被提交。**在某些情況下，領導者可以安全地得出一個較老的日志條目被提交的結論（例如，如果該條目存儲在每個服務器上），但是為了簡化Raft采取了更加保守的方法。

Raft在提交規則中面臨額外復雜性，因為日志條目在領導者從之前任期復制條目時保留其原始任期號。在其他共識算法中，如果新領導者復制以前 “任期” 的條目，它必須使用新的“任期號” 進行復制。Raft的方法使得對日志條目進行推理更容易，因為它們隨著時間的推移和跨日志保持相同的任期號。此外，Raft中的新領導者發送的來自以前任期的日志條目比其他算法少（其他算法必須發送冗余的日志條目來重新編號，使它們能夠被承諾）。

安全論據

給定完整的Raft算法，我們現在可以更準確地論證Leader Completeness Property成立（這個論證基于安全證明；參見第9.2節）。我們假設Leader Completeness Property不成立，然后證明一個矛盾。假設在任期T下，領導者（leaderT）提交了一個來自其任期的日志條目，但該日志條目未被某個未來任期的領導者存儲。考慮最小的任期U > T，其領導者（leaderU）未存儲該條目。