Raft 一致性算法论文译文
本篇博客為著名的 RAFT 一致性算法論文的中文翻譯，論文名為《In search of an Understandable Consensus Algorithm (Extended Version)》(尋找一種易于理解的一致性算法)。
Raft 是一種用來管理日志復制的一致性算法。它和 Paxos 的性能和功能是一樣的，但是它和 Paxos 的結構不一樣；這使得 Raft 更容易理解并且更易于建立實際的系統。為了提高理解性，Raft 將一致性算法分為了幾個部分，例如領導選取（leader selection），日志復制（log replication）和安全性（safety），同時它使用了更強的一致性來減少了必須需要考慮的狀態。從用戶學習的結果來看，Raft 比 Paxos 更容易學會。Raft 還包括了一種新的機制來使得動態改變集群成員，它使用重疊大多數（overlapping majorities）來保證安全。
1. 引言
一致性算法允許一組機器像一個整體一樣工作，即使其中的一些機器出了錯誤也能正常工作。正因為此，他們扮演著建立大規模可靠的軟件系統的關鍵角色。在過去的十年中 Paxos 一直都主導著有關一致性算法的討論：大多數一致性算法的實現都基于它或者受它影響，并且 Paxos 也成為了教學生關于一致性知識的主要工具。
不幸的是，盡管在降低它的復雜性方面做了許多努力，Paxos 依舊很難理解。并且，Paxos 需要經過復雜的修改才能應用于實際中。這些導致了系統構構建者和學生都十分頭疼。
在被 Paxos 折磨之后，我們開始尋找一種在系統構建和教學上更好的新的一致性算法。我們的首要目標是讓它易于理解：我們能不能定義一種面向實際系統的一致性算法并且比 Paxos 更容易學習呢？并且，我們希望這種算法能憑直覺就能明白，這對于一個系統構建者來說是十分必要的。對于一個算法，不僅僅是讓它工作起來很重要，知道它是如何工作的更重要。
我們工作的結果是一種新的一致性算法，叫做 Raft。在設計 Raft 的過程中我們應用了許多專門的技巧來提升理解性，包括算法分解（分為領導選取（leader selection），日志復制（log replication）和安全性（safety））和減少狀態（state space reduction）（相對于 Paxos，Raft 減少了非確定性的程度和服務器互相不一致的方式）。在兩所學校的43個學生的研究中發現，Raft 比 Paxos 要更容易理解：在學習了兩種算法之后，其中的33個學生回答 Raft 的問題要比回答 Paxos 的問題要好。
Raft 算法和現在一些已經有的算法在一些地方很相似（主要是?Oki 和 Liskov 的 Viewstamped Replication。但是 Raft 有幾個新的特性：
- 強領導者（Strong Leader）：Raft 使用一種比其他算法更強的領導形式。例如，日志條目只從領導者發送向其他服務器。這樣就簡化了對日志復制的管理，使得 Raft 更易于理解。
- 領導選取（Leader Selection）：Raft 使用隨機定時器來選取領導者。這種方式僅僅是在所有算法都需要實現的心跳機制上增加了一點變化，它使得在解決沖突時更簡單和快速。
- 成員變化（Membership Change）：Raft 為了調整集群中成員關系使用了新的聯合一致性（joint consensus）的方法，這種方法中大多數不同配置的機器在轉換關系的時候會交迭（overlap）。這使得在配置改變的時候，集群能夠繼續操作。
我們認為，Raft 在教學方面和實際實現方面比 Paxos 和其他算法更出眾。它比其他算法更簡單、更容易理解；它能滿足一個實際系統的需求；它擁有許多開源的實現并且被許多公司所使用；它的安全特性已經被證明；并且它的效率和其他算法相比也具有競爭力。
這篇論文剩下的部分會講如下內容：復制狀態機（replicated state machine）問題（第2節），討論 Paxos 的優缺點（第3節），討論我們用的為了達到提升理解性的方法（第4節），陳述 Raft 一致性算法（第5~8節），評價 Raft 算法（第9節），對相關工作的討論（第10節）。
2. 復制狀態機（Replicated State Machine）
一致性算法是在復制狀態機的背景下提出來的。在這個方法中，在一組服務器的狀態機產生同樣的狀態的副本因此即使有一些服務器崩潰了這組服務器也還能繼續執行。復制狀態機在分布式系統中被用于解決許多有關容錯的問題。例如，GFS，HDFS還有 RAMCloud 這些大規模的系統都是用一個單獨的集群領導者，使用一個單獨的復制狀態機來進行領導選取和存儲配置信息來應對領導者的崩潰。使用復制狀態機的例子有 Chubby 和 ZooKeeper。
?
?
圖-1：復制狀態機的架構。一致性算法管理來自客戶端狀態命令的復制日志。狀態機處理的日志中的命令的順序都是一致的，因此會得到相同的執行結果。如圖-1所示，復制狀態機是通過復制日志來實現的。每一臺服務器保存著一份日志，日志中包含一系列的命令，狀態機會按順序執行這些命令。因為每一臺計算機的狀態機都是確定的，所以每個狀態機的狀態都是相同的，執行的命令是相同的，最后的執行結果也就是一樣的了。
如何保證復制日志一致就是一致性算法的工作了。在一臺服務器上，一致性模塊接受客戶端的命令并且把命令加入到它的日志中。它和其他服務器上的一致性模塊進行通信來確保每一個日志最終包含相同序列的請求，即使有一些服務器宕機了。一旦這些命令被正確的復制了，每一個服務器的狀態機都會按同樣的順序去執行它們，然后將結果返回給客戶端。最終，這些服務器看起來就像一臺可靠的狀態機。
應用于實際系統的一致性算法一般有以下特性：
-
確保安全性（從來不會返回一個錯誤的結果），即使在所有的非拜占庭（Non-Byzantine）情況下，包括網絡延遲、分區、丟包、冗余和亂序的情況下。
-
高可用性，只要集群中的大部分機器都能運行，可以互相通信并且可以和客戶端通信，這個集群就可用。因此，一般來說，一個擁有 5 臺機器的集群可以容忍其中的 2 臺的失敗（fail）。服務器停止工作了我們就認為它失敗（fail）了，沒準一會當它們擁有穩定的存儲時就能從中恢復過來，重新加入到集群中。
-
不依賴時序保證一致性，時鐘錯誤和極端情況下的消息延遲在最壞的情況下才會引起可用性問題。
-
通常情況下，一條命令能夠盡可能快的在大多數節點對一輪遠程調用作出相應時完成，一少部分慢的機器不會影響系統的整體性能。
3. Paxos 算法的不足
在過去的10年中，Leslie Lamport 的 Paxos 算法幾乎已經成為了一致性算法的代名詞：它是授課中最常見的算法，同時也是許多一致性算法實現的起點。Paxos 首先定義了一個能夠達成單一決策一致的協議，例如一個單一復制日志條目（single replicated log entry）。我們把這個子集叫做單一決策 Paxos（single-decree Paxos）。之后 Paxos通過組合多個這種協議來完成一系列的決策，例如一個日志（multi-Paxos）。Paxos 確保安全性和活躍性（liveness），并且它支持集群成員的變更。它的正確性已經被證明，通常情況下也很高效。
不幸的是，Paxos 有兩個致命的缺點。第一個是 Paxos 太難以理解。它的完整的解釋晦澀難懂；很少有人能完全理解，只有少數人成功的讀懂了它。并且大家做了許多努力來用一些簡單的術語來描述它。盡管這些解釋都關注于單一決策子集問題，但仍具有挑戰性。在 NSDI 2012 會議上的一次非正式調查顯示，我們發現大家對 Paxos 都感到不滿意，其中甚至包括一些有經驗的研究員。我們自己也曾深陷其中，我們在讀過幾篇簡化它的文章并且設計了我們自己的算法之后才完全理解了 Paxos，而整個過程花費了將近一年的時間。
我們假定 Paxos 的晦澀來源于它將單決策子集作為它的基礎。單決策（Single-decree）Paxos 是晦澀且微妙的：它被劃分為兩個沒有簡單直觀解釋的階段，并且難以獨立理解。正因為如此，它不能很直觀的讓我們知道為什么單一決策協議能夠工作。為多決策 Paxos 設計的規則又添加了額外的復雜性和精巧性。我們相信多決策問題能夠分解為其它更直觀的方式。
Paxos 的第二個缺點是它難以在實際環境中實現。其中一個原因是，對于多決策 Paxos （multi-Paxos） ，大家還沒有一個一致同意的算法。Lamport 的描述大部分都是有關于單決策 Paxos （single-decree Paxos）；他僅僅描述了實現多決策的可能的方法，缺少許多細節。有許多實現 Paxos 和優化 Paxos 的嘗試，但是他們都和 Lamport 的描述有些出入。例如，Chubby 實現的是一個類似 Paxos 的算法，但是在許多情況下的細節沒有公開。
另外，Paxos 的結構也是不容易在一個實際系統中進行實現的，這是單決策問題分解帶來的又一個問題。例如，從許多日志條目中選出條目然后把它們融合到一個序列化的日志中并沒有帶來什么好處，它僅僅增加了復雜性。圍繞著日志來設計一個系統是更簡單、更高效的：新日志按照嚴格的順序添加到日志中去。另一個問題是，Paxos 使用對等的點對點的實現作為它的核心（盡管它最終提出了一種弱領導者的形式來優化性能）。這種方法在只有一個決策被制定的情況下才顯得有效，但是很少有現實中的系統使用它。如果要做許多的決策，選擇一個領導人，由領帶人來協調是更簡單有效的方法。
因此，在實際的系統應用中和 Paxos 算法都相差很大。所有開始于 Paxos 的實現都會遇到很多問題，然后由此衍生出了許多與 Paxos 有很大不同的架構。這是既費時又容易出錯的，并且理解 Paxos 的難度又非常大。Paxos 算法在它正確性的理論證明上是很好的，但是在實現上的價值就遠遠不足了。來自 Chubby 的實現的一條評論就能夠說明：
Paxos 算法的描述與實際實現之間存在巨大的鴻溝…最終的系統往往建立在一個沒有被證明的算法之上。
正因為存在這些問題，我們認為 Paxos 不僅對于系統的構建者來說不友好，同時也不利于教學。鑒于一致性算法對于大規模軟件系統的重要性，我們決定試著來設計一種另外的比 Paxos 更好的一致性算法。Raft 就是這樣的一個算法。
4. 易于理解的設計
設計 Raft 的目標有如下幾個：
-
它必須提供一個完整的、實際的基礎來進行系統構建，為的是減少開發者的工作；
-
它必須在所有情況下都能保證安全可用；
-
它對于常規操作必須高效；
-
最重要的目標是：易于理解，它必須使得大多數人能夠很容易的理解；
-
另外，它必須能讓開發者有一個直觀的認識，這樣才能使系統構建者們去對它進行擴展。
在設計 Raft 的過程中，我們不得不在許多種方法中做出選擇。當面臨這種情況時，我們通常會權衡可理解性：每種方法的可理解性是如何的？（例如，它的狀態空間有多復雜？它是不是有很細微的含義？）它的可讀性如何？讀者能不能輕易地理解這個方法和它的含義？
我們意識到對這種可理解性的分析具有高度的主觀性；盡管如此，我們使用了兩種適用的方式。第一種是眾所周知的問題分解：我們盡可能將問題分解成為若干個可解決的、可被理解的小問題。例如，在 Raft 中，我們把問題分解成為了領導選取（leader election）、日志復制（log replication）、安全（safety）和成員變化（membership changes）。
我們采用的第二個方法是通過減少需要考慮的狀態的數量將狀態空間簡化，這能夠使得整個系統更加一致并且盡可能消除不確定性。特別地，日志之間不允許出現空洞，并且 Raft 限制了限制了日志不一致的可能性。盡管在大多數情況下，我們都都在試圖消除不確定性，但是有時候有些情況下，不確定性使得算法更易理解。尤其是，隨機化方法使得不確定性增加，但是它減少了狀態空間。我們使用隨機化來簡化了 Raft 中的領導選取算法。
5. Raft 一致性算法
Raft 是一種用來管理第 2 章中提到的復制日志的算法。表-2 為了方便參考是一個算法的總結版本，表-3 列舉了算法中的關鍵性質；表格中的這些元素將會在這一章剩下的部分中分別進行討論。
狀態：
在所有服務器上持久存在的：（在響應遠程過程調用 RPC 之前穩定存儲的）
| 名稱 | 描述 |
| currentTerm | 服務器最后知道的任期號（從0開始遞增） |
| votedFor | 在當前任期內收到選票的候選人 id（如果沒有就為 null） |
| log[] | 日志條目；每個條目包含狀態機的要執行命令和從領導人處收到時的任期號 |
在所有服務器上不穩定存在的：
| 名稱 | 描述 |
| commitIndex | 已知的被提交的最大日志條目的索引值（從0開始遞增） |
| lastApplied | 被狀態機執行的最大日志條目的索引值（從0開始遞增） |
在領導人服務器上不穩定存在的：（在選舉之后初始化的）
| 名稱 | 描述 |
| nextIndex[] | 對于每一個服務器，記錄需要發給它的下一個日志條目的索引（初始化為領導人上一條日志的索引值+1） |
| matchIndex[] | 對于每一個服務器，記錄已經復制到該服務器的日志的最高索引值（從0開始遞增） |
?
附加日志遠程過程調用 （AppendEntries RPC）
由領導人來調用復制日志（5.3節）；也會用作heartbeat
| 參數 | 描述 |
| term | 領導人的任期號 |
| leaderId | 領導人的 id，為了其他服務器能重定向到客戶端 |
| prevLogIndex | 最新日志之前的日志的索引值 |
| prevLogTerm | 最新日志之前的日志的領導人任期號 |
| entries[] | 將要存儲的日志條目（表示 heartbeat 時為空，有時會為了效率發送超過一條） |
| leaderCommit | 領導人提交的日志條目索引值 |
| 返回值 | 描述 |
| term | 當前的任期號，用于領導人更新自己的任期號 |
| success | 如果其它服務器包含能夠匹配上 prevLogIndex 和 prevLogTerm 的日志時為真 |
接受者需要實現：
?
投票請求 RPC（RequestVote RPC）
由候選人發起收集選票（5.2節）
| 參數 | 描述 |
| term | 候選人的任期號 |
| candidateId | 請求投票的候選人 id |
| lastLogIndex | 候選人最新日志條目的索引值 |
| lastLogTerm | 候選人最新日志條目對應的任期號 |
| 返回值 | 描述 |
| term | 目前的任期號，用于候選人更新自己 |
| voteGranted | 如果候選人收到選票為 true |
接受者需要實現：
?
服務器需要遵守的規則：
所有服務器：
- 如果commitIndex > lastApplied，lastApplied自增，將log[lastApplied]應用到狀態機（5.3節）
- 如果 RPC 的請求或者響應中包含一個 term T 大于?currentTerm，則currentTerm賦值為 T，并切換狀態為追隨者（Follower）（5.1節）
追隨者（followers）: 5.2節
- 響應來自候選人和領導人的 RPC
- 如果在超過選取領導人時間之前沒有收到來自當前領導人的AppendEntries RPC或者沒有收到候選人的投票請求，則自己轉換狀態為候選人
候選人：5.2節
- 轉變為選舉人之后開始選舉：
- currentTerm自增
- 給自己投票
- 重置選舉計時器
- 向其他服務器發送RequestVote RPC
- 如果收到了來自大多數服務器的投票：成為領導人
- 如果收到了來自新領導人的AppendEntries RPC（heartbeat）：轉換狀態為追隨者
- 如果選舉超時：開始新一輪的選舉
領導人：
- 一旦成為領導人：向其他所有服務器發送空的AppendEntries RPC（heartbeat）;在空閑時間重復發送以防止選舉超時（5.2節）
- 如果收到來自客戶端的請求：向本地日志增加條目，在該條目應用到狀態機后響應客戶端（5.3節）
- 對于一個追隨者來說，如果上一次收到的日志索引大于將要收到的日志索引（nextIndex）：通過AppendEntries RPC將 nextIndex 之后的所有日志條目發送出去
- 如果發送成功：將該追隨者的?nextIndex和matchIndex更新
- 如果由于日志不一致導致AppendEntries RPC失敗：nextIndex遞減并且重新發送（5.3節）
- 如果存在一個滿足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，則將commitIndex賦值為 N
?
?
| 性質 | 描述 |
| 選舉安全原則（Election Safety） | 一個任期（term）內最多允許有一個領導人被選上（5.2節） |
| 領導人只增加原則（Leader Append-Only） | 領導人永遠不會覆蓋或者刪除自己的日志，它只會增加條目 |
| 日志匹配原則（Log Matching） | 如果兩個日志在相同的索引位置上的日志條目的任期號相同，那么我們就認為這個日志從頭到這個索引位置之間的條目完全相同（5.3 節） |
| 領導人完全原則（Leader Completeness) | 如果一個日志條目在一個給定任期內被提交，那么這個條目一定會出現在所有任期號更大的領導人中 |
| 狀態機安全原則（State Machine Safety） | 如果一個服務器已經將給定索引位置的日志條目應用到狀態機中，則所有其他服務器不會在該索引位置應用不同的條目（5.4.3節） |
Raft 通過首先選出一個領導人來實現一致性，然后給予領導人完全管理復制日志（replicated log）的責任。領導人接收來自客戶端的日志條目，并把它們復制到其他的服務器上，領帶人還要告訴服務器們什么時候將日志條目應用到它們的狀態機是安全的。通過選出領導人能夠簡化復制日志的管理工作。例如，領導人能夠決定將新的日志條目放到哪，而并不需要和其他的服務器商議，數據流被簡化成從領導人流向其他服務器。如果領導人宕機或者和其他服務器失去連接，就可以選取下一個領導人。
通過選出領導人，Raft 將一致性問題分解成為三個相對獨立的子問題：
- 領導人選取（Leader election）：?在一個領導人宕機之后必須要選取一個新的領導人（5.2節）
- 日志復制（Log replication）：?領導人必須從客戶端接收日志然后復制到集群中的其他服務器，并且強制要求其他服務器的日志保持和自己相同
- 安全性（Safety）：?Raft 的關鍵的安全特性是 表-3 中提到的狀態機安全原則（State Machine Safety）:如果一個服務器已經將給定索引位置的日志條目應用到狀態機中，則所有其他服務器不會在該索引位置應用不同的條目。5.4節闡述了 Raft 是如何保證這條原則的，解決方案涉及到一個對于選舉機制另外的限制，這一部分會在 5.2節 中說明。
在說明了一致性算法之后，本章會討論有關可用性（availability）的問題和系統中時序（timing）的問題。
5.1 Raft 基礎
一個 Raft 集群包括若干服務器；對于一個典型的 5 服務器集群，該集群能夠容忍 2 臺機器不能正常工作，而整個系統保持正常。在任意的時間，每一個服務器一定會處于以下三種狀態中的一個：領導人、候選人、追隨者。在正常情況下，只有一個服務器是領導人，剩下的服務器是追隨者。追隨者們是被動的：他們不會發送任何請求，只是響應來自領導人和候選人的請求。領導人來處理所有來自客戶端的請求（如果一個客戶端與追隨者進行通信，追隨者會將信息發送給領導人）。候選人是用來選取一個新的領導人的，這一部分會在 5.2節 進行闡釋。圖-4 闡述了這些狀態，和它們之間的轉換；它們的轉換會在下邊進行討論。
?
?
圖-4：服務器的狀態。追隨者只響應其他服務器的請求。如果追隨者沒有收到任何消息，它會成為一個候選人并且開始一次選舉。收到大多數服務器投票的候選人會成為新的領導人。領導人在它們宕機之前會一直保持領導人的狀態。?
?
?
圖-5：時間被分為一個個的任期（term），每一個任期的開始都是領導人選舉。在成功選舉之后，一個領導人會在任期內管理整個集群。如果選舉失敗，該任期就會因為沒有領帶人而結束。這個轉變會在不同的時間的不同服務器上觀察到。?
?
如 圖-5 所示，Raft 算法將時間劃分成為任意不同長度的任期（term）。任期用連續的數字進行表示。每一個任期的開始都是一次選舉（election），就像 5.2節 所描述的那樣，一個或多個候選人會試圖成為領導人。如果一個候選人贏得了選舉，它就會在該任期的剩余時間擔任領導人。在某些情況下，選票會被瓜分，有可能沒有選出領導人，那么，將會開始另一個任期，并且立刻開始下一次選舉。Raft 算法保證在給定的一個任期最少要有一個領導人。
不同的服務器可能會在任期內觀察到多次不同的狀態轉換，在某些情況下，一臺服務器可能看不到一次選舉或者一個完整的任期。任期在 Raft 中充當邏輯時鐘的角色，并且它們允許服務器檢測過期的信息，比如過時的領導人。每一臺服務器都存儲著一個當前任期的數字，這個數字會單調的增加。當服務器之間進行通信時，會互相交換當前任期號；如果一臺服務器的當前任期號比其它服務器的小，則更新為較大的任期號。如果一個候選人或者領導人意識到它的任期號過時了，它會立刻轉換為追隨者狀態。如果一臺服務器收到的請求的任期號是過時的，那么它會拒絕此次請求。
Raft 中的服務器通過遠程過程調用（RPC）來通信，基本的 Raft 一致性算法僅需要 2 種 RPC。RequestVote RPC 是候選人在選舉過程中觸發的（5.2節），AppendEntries RPC 是領導人觸發的，為的是復制日志條目和提供一種心跳（heartbeat）機制（5.3節）。第7章加入了第三種 RPC 來在各個服務器之間傳輸快照（snapshot）。如果服務器沒有及時收到 RPC 的響應，它們會重試，并且它們能夠并行的發出 RPC 來獲得最好的性能。
5.2 領導人選取
Raft 使用一種心跳機制（heartbeat）來觸發領導人的選取。當服務器啟動時，它們會初始化為追隨者。一太服務器會一直保持追隨者的狀態只要它們能夠收到來自領導人或者候選人的有效 RPC。領導人會向所有追隨者周期性發送心跳（heartbeat，不帶有任何日志條目的 AppendEntries RPC）來保證它們的領導人地位。如果一個追隨者在一個周期內沒有收到心跳信息，就叫做選舉超時（election timeout）,然后它就會假定沒有可用的領導人并且開始一次選舉來選出一個新的領導人。
為了開始選舉，一個追隨者會自增它的當前任期并且轉換狀態為候選人。然后，它會給自己投票并且給集群中的其他服務器發送 RequestVote RPC。一個候選人會一直處于該狀態，直到下列三種情形之一發生：
- 它贏得了選舉；
- 另一臺服務器贏得了選舉；
- 一段時間后沒有任何一臺服務器贏得了選舉
這些情形會在下面的章節中分別討論。
一個候選人如果在一個任期內收到了來自集群中大多數服務器的投票就會贏得選舉。在一個任期內，一臺服務器最多能給一個候選人投票，按照先到先服務原則（first-come-first-served）（注意：在 5.4節 針對投票添加了一個額外的限制）。大多數原則使得在一個任期內最多有一個候選人能贏得選舉（表-3 中提到的選舉安全原則）。一旦有一個候選人贏得了選舉，它就會成為領導人。然后它會像其他服務器發送心跳信息來建立自己的領導地位并且組織新的選舉。
當一個候選人等待別人的選票時，它有可能會收到來自其他服務器發來的聲明其為領導人的 AppendEntries RPC。如果這個領導人的任期（包含在它的 RPC 中）比當前候選人的當前任期要大，則候選人認為該領導人合法，并且轉換自己的狀態為追隨者。如果在這個 RPC 中的任期小于候選人的當前任期，則候選人會拒絕此次 RPC， 繼續保持候選人狀態。
第三種情形是一個候選人既沒有贏得選舉也沒有輸掉選舉：如果許多追隨者在同一時刻都成為了候選人，選票會被分散，可能沒有候選人能獲得大多數的選票。當這種情形發生時，每一個候選人都會超時，并且通過自增任期號和發起另一輪 RequestVote RPC 來開始新的選舉。然而，如果沒有其它手段來分配選票的話，這種情形可能會無限的重復下去。
Raft 使用隨機的選舉超時時間來確保第三種情形很少發生，并且能夠快速解決。為了防止在一開始是選票就被瓜分，選舉超時時間是在一個固定的間隔內隨機選出來的（例如，150~300ms）。這種機制使得在大多數情況下只有一個服務器會率先超時，它會在其它服務器超時之前贏得選舉并且向其它服務器發送心跳信息。同樣的機制被用于選票一開始被瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個隨機的選舉超時時間，在超時進行下一次選舉之前一直等待。這能夠減小在新的選舉中一開始選票就被瓜分的可能性。9.3節 展示了這種方法能夠快速的選出一個領導人。
選舉是一個理解性引導我們設計替代算法的一個例子。最開始時，我們計劃使用一種排名系統：給每一個候選人分配一個唯一的排名，用于在競爭的候選人之中選擇領導人。如果一個候選人發現了另一個比它排名高的候選人，那么它會回到追隨者的狀態，這樣排名高的候選人會很容易地贏得選舉。但是我們發現這種方法在可用性方面有一點問題（一個低排名的服務器在高排名的服務器宕機后，需要等待超時才能再次成為候選人，但是如果它這么做的太快，它能重置選舉領帶人的過程）。我們對這個算法做了多次調整，但是每次調整后都會出現一些新的問題。最終我們認為隨機重試的方法是更明確并且更易于理解的。
5.3 日志復制
一旦選出了領導人，它就開始接收客戶端的請求。每一個客戶端請求都包含一條需要被復制狀態機（replicated state machine）執行的命令。領導人把這條命令作為新的日志條目加入到它的日志中去，然后并行的向其他服務器發起 AppendEntries RPC ，要求其它服務器復制這個條目。當這個條目被安全的復制之后（下面的部分會詳細闡述），領導人會將這個條目應用到它的狀態機中并且會向客戶端返回執行結果。如果追隨者崩潰了或者運行緩慢或者是網絡丟包了，領導人會無限的重試 AppendEntries RPC（甚至在它向客戶端響應之后）知道所有的追隨者最終存儲了所有的日志條目。
?
圖-6：日志由有序編號的日志條目組成。每個日志條目包含它被創建時的任期號（每個方塊中的數字），并且包含用于狀態機執行的命令。如果一個條目能夠被狀態機安全執行，就被認為可以提交了。日志就像 圖-6 所示那樣組織的。每個日志條目存儲著一條被狀態機執行的命令和當這條日志條目被領導人接收時的任期號。日志條目中的任期號用來檢測在不同服務器上日志的不一致性，并且能確保 圖-3 中的一些特性。每個日志條目也包含一個整數索引來表示它在日志中的位置。
領導人決定什么時候將日志條目應用到狀態機是安全的；這種條目被稱為可被提交（commited）。Raft 保證可被提交（commited）的日志條目是持久化的并且最終會被所有可用的狀態機執行。一旦被領導人創建的條目已經復制到了大多數的服務器上，這個條目就稱為可被提交的（例如，圖-6中的7號條目）。領導人日志中之前的條目都是可被提交的（commited），包括由之前的領導人創建的條目。5.4節將會討論當領導人更替之后這條規則的應用問題的細節，并且也討論了這種提交方式是安全的。領導人跟蹤記錄它所知道的被提交條目的最大索引值，并且這個索引值會包含在之后的 AppendEntries RPC 中（包括心跳 heartbeat 中），為的是讓其他服務器都知道這條條目已經提交。一旦一個追隨者知道了一個日志條目已經被提交，它會將該條目應用至本地的狀態機（按照日志順序）。
我們設計了 Raft 日志機制來保證不同服務器上日志的一致性。這樣做不僅簡化了系統的行為使得它更可預測，并且也是保證安全性不可或缺的一部分。Raft 保證以下特性，并且也保證了 表-3 中的日志匹配原則（Log Matching Property）:
- 如果在不同日志中的兩個條目有著相同的索引和任期號，則它們所存儲的命令是相同的。
- 如果在不同日志中的兩個條目有著相同的索引和任期號，則它們之間的所有條目都是完全一樣的。
第一條特性源于領導人在一個任期里在給定的一個日志索引位置最多創建一條日志條目，同時該條目在日志中的位置也從來不會改變。第二條特性源于 AppendEntries 的一個簡單的一致性檢查。當發送一個 AppendEntries RPC 時，領導人會把新日志條目緊接著之前的條目的索引位置和任期號都包含在里面。如果追隨者沒有在它的日志中找到相同索引和任期號的日志，它就會拒絕新的日志條目。這個一致性檢查就像一個歸納步驟：一開始空的日志的狀態一定是滿足日志匹配原則的，一致性檢查保證了當日志添加時的日志匹配原則。因此，只要 AppendEntries 返回成功的時候，領導人就知道追隨者們的日志和它的是一致的了。
?
?
圖-7：當最上邊的領導人掌權之后，追隨者日志可能有以下情況（a~f）。一個格子表示一個日志條目；格子中的數字是它的任期。一個追隨者可能會丟失一些條目（a, b）；可能多出來一些未提交的條目（c, d）；或者兩種情況都有（e, f）。例如，場景 f 在如下情況下就會發生：如果一臺服務器在任期2時是領導人并且往它的日志中添加了一些條目，然后在將它們提交之前就宕機了，之后它很快重啟了，成為了任期3的領導人，又往它的日志中添加了一些條目，然后在任期2和任期3中的條目提交之前它又宕機了并且幾個任期內都一直處于宕機狀態。?
?
在一般情況下，領導人和追隨者們的日志保持一致，因此 AppendEntries 一致性檢查通常不會失敗。然而，領導人的崩潰會導致日志不一致（舊的領導人可能沒有完全復制完日志中的所有條目）。這些不一致會導致一系列領導人和追隨者崩潰。圖-7 闡述了一些追隨者可能和新的領導人日志不同的情況。一個追隨者可能會丟失掉領導人上的一些條目，也有可能包含一些領導人沒有的條目，也有可能兩者都會發生。丟失的或者多出來的條目可能會持續多個任期。
在 Raft 算法中，領導人通過強制追隨者們復制它的日志來處理日志的不一致。這就意味著，在追隨者上的沖突日志會被領導者的日志覆蓋。5.4節會說明當添加了一個額外的限制之后這是安全的。
為了使得追隨者的日志同自己的一致，領導人需要找到追隨者同它的日志一致的地方，然后刪除追隨者在該位置之后的條目，然后將自己在該位置之后的條目發送給追隨者。這些操作都在 AppendEntries RPC 進行一致性檢查時完成。領導人給每一個追隨者維護了一個nextIndex，它表示領導人將要發送給該追隨者的下一條日志條目的索引。當一個領導人開始掌權時，它會將nextIndex初始化為它的最新的日志條目索引數+1（圖-7 中的 11）。如果一個追隨者的日志和領導者的不一致，AppendEntries 一致性檢查會在下一次 AppendEntries RPC 時返回失敗。在失敗之后，領導人會將nextIndex遞減然后重試 AppendEntries RPC。最終nextIndex會達到一個領導人和追隨者日志一致的地方。這時，AppendEntries 會返回成功，追隨者中沖突的日志條目都被移除了，并且添加所缺少的上了領導人的日志條目。一旦 AppendEntries 返回成功，追隨者和領導人的日志就一致了，這樣的狀態會保持到該任期結束。
如果需要的話，算法還可以進行優化來減少 AppendEntries RPC 失敗的次數。例如，當拒絕了一個 AppendEntries 請求，追隨者可以記錄下沖突日志條目的任期號和自己存儲那個任期的最早的索引。通過這些信息，領導人能夠直接遞減nextIndex跨過那個任期內所有的沖突條目；這樣的話，一個沖突的任期需要一次 AppendEntries RPC，而不是每一個沖突條目需要一次 AppendEntries RPC。在實踐中，我們懷疑這種優化是否是必要的，因為AppendEntries 一致性檢查很少失敗并且也不太可能出現大量的日志條目不一致的情況。
通過這種機制，一個領導人在掌權時不需要采取另外特殊的方式來恢復日志的一致性。它只需要使用一些常規的操作，通過響應 AppendEntries 一致性檢查的失敗能使得日志自動的趨于一致。一個領導人從來不會覆蓋或者刪除自己的日志（表-3 中的領導人只增加原則）。
這個日志復制機制展示了在第2章中闡述的所希望的一致性特性：Raft 能夠接受，復制并且應用新的日志條目只要大部分的服務器是正常的。在通常情況下，一條新的日志條目可以在一輪 RPC 內完成在集群的大多數服務器上的復制；并且一個速度很慢的追隨者并不會影響整體的性能。
5.4 安全性
之前的章節中討論了 Raft 算法是如何進行領導選取和復制日志的。然而，到目前為止這個機制還不能保證每一個狀態機能按照相同的順序執行同樣的指令。例如，當領導人提交了若干日志條目的同時一個追隨者可能宕機了，之后它又被選為了領導人然后用新的日志條目覆蓋掉了舊的那些，最后，不同的狀態機可能執行不同的命令序列。
這一節通過在領帶人選取部分加入了一個限制來完善了 Raft 算法。這個限制能夠保證對于固定的任期，任何的領導人都擁有之前任期提交的全部日志條目（表-3 中的領導人完全原則）。有了這一限制，日志提交的規則就更清晰了。最后，我們提出了對于領導人完全原則的簡單證明并且展示了它是如何修正復制狀態機的行為的。
5.4.1 選舉限制
在所有的以領導人為基礎的一致性算法中，領導人最終必須要存儲全部已經提交的日志條目。在一些一致性算法中，例如：Viewstamped Replication，即使一開始沒有包含全部已提交的條目也可以被選為領導人。這些算法都有一些另外的機制來保證找到丟失的條目并將它們傳輸給新的領導人，這個過程要么在選舉過程中完成，要么在選舉之后立即開始。不幸的是，這種方式大大增加了復雜性。Raft 使用了一種更簡單的方式來保證在新的領導人開始選舉的時候在之前任期的所有已提交的日志條目都會出現在上邊，而不需要將這些條目傳送給領導人。這就意味著日志條目只有一個流向：從領導人流向追隨者。領導人永遠不會覆蓋已經存在的日志條目。
Raft 使用投票的方式來阻止沒有包含全部日志條目的服務器贏得選舉。一個候選人為了贏得選舉必須要和集群中的大多數進行通信，這就意味著每一條已經提交的日志條目最少在其中一臺服務器上出現。如果候選人的日志至少和大多數服務器上的日志一樣新（up-to-date，這個概念會在下邊有詳細介紹），那么它一定包含有全部的已經提交的日志條目。RequestVote RPC 實現了這個限制：這個 RPC（遠程過程調用）包括候選人的日志信息，如果它自己的日志比候選人的日志要新，那么它會拒絕候選人的投票請求。
Raft 通過比較日志中最后一個條目的索引和任期號來決定兩個日志哪一個更新。如果兩個日志的任期號不同，任期號大的更新；如果任期號相同，更長的日志更新。
5.4.2 提交之前任期的日志條目
?
圖-8：如圖的時間序列說明了為什么領導人不能通過之前任期的日志條目判斷它的提交狀態。（a）中的 S1 是領導人并且部分復制了索引2上的日志條目。（b）中 S1 崩潰了；S5 通過 S3，S4 和自己的選票贏得了選舉，并且在索引2上接收了另一條日志條目。（c）中 S5 崩潰了，S1 重啟了，通過 S2，S3 和自己的選票贏得了選舉，并且繼續索引2處的復制，這時任期2的日志條目已經在大部分服務器上完成了復制，但是還并沒有提交。如果在（d）時刻 S1 崩潰了，S5 會通過 S2，S3，S4 的選票成為領導人，然后用它自己在任期3的日志條目覆蓋掉其他服務器的日志條目。然而，如果在崩潰之前，S1 在它的當前任期在大多數服務器上復制了一條日志條目，就像在（e）中那樣，那么這條條目就會被提交（S5就不會贏得選舉）。在這時，之前的日志條目就會正常被提交。正如 5.3節 中描述的那樣，只要一個日志條目被存在了在多數的服務器上，領導人就知道當前任期就可以提交該條目了。如果領導人在提交之前就崩潰了，之后的領導人會試著繼續完成對日志的復制。然而，領導人并不能斷定存儲在大多數服務器上的日志條目一定在之前的任期中被提交了。圖-8 說明了一種情況，一條存儲在了大多數服務器上的日志條目仍然被新上任的領導人覆蓋了。
為了消除 圖-8 中描述的問題，Raft 從來不會通過計算復制的數目來提交之前人氣的日志條目。只有領導人當前任期的日志條目才能通過計算數目來進行提交。一旦當前任期的日志條目以這種方式被提交，那么由于日志匹配原則（Log Matching Property），之前的日志條目也都會被間接的提交。在某些情況下，領導人可以安全的知道一個老的日志條目是否已經被提交（例如，通過觀察該條目是否存儲到所有服務器上），但是 Raft 為了簡化問題使用了一種更加保守的方法。
因為當領導人從之前任期復制日志條目時日志條目保留了它們最開始的任期號，所以這使得 Raft 在提交規則中增加了額外的復雜性。在其他的一致性算法中，如果一個新的領導人要從之前的任期中復制日志條目，它必須要使用當前的新任期號。Raft 的方法使得判斷日志更加容易，因為它們全程都保持著同樣的任期號。另外，和其它的一致性算法相比，Raft 算法中的新領導人會發送更少的之前任期的日志條目（其他算法必須要發送冗余的日志條目并且在它們被提交之前來重新排序）。
5.4.3 安全性論證
圖-9：如果 S1（任期 T 的領導人）在它的任期提交了一條日志條目，并且 S5 在之后的任期 U 成為了領導人，那么最少會有一臺服務器（S3）接收了這條日志條目并且會給 S5 投票。
給出了完整的 Raft 算法，現在我們能夠更精確的論證領導人完全原則（Leader Completeness)（這基于 9.2節 提出的安全性證明）。我們假定領導人完全原則是不成立的，然后推導出矛盾。假定任期 T 的領導人 leaderT在它的任期提交了一個日志條目，但是這條日志條目并沒有存儲在之后的任期中的領導人上。我們設大于 T 的最小的任期 U 的領導人（leaderU） 沒有存儲這條日志條目。
在 leaderU?選舉時一定沒有那條被提交的日志條目（領導人從來不會刪除或者覆蓋日志條目）。
leaderT?復制了這個條目到集群的大多數的服務器上。因此，只是有一臺服務器（投票者）即接收了來自 leaderT?的日志條目并且給 leaderU?投票，就像 圖-9 中所示那樣。這個投票者是產生矛盾的關鍵。
投票者必須在給 leaderU?投票之前接收來自 leaderT?的日志條目；否則它會拒絕來自 leaderT?的 AppendEntries 請求（它的當前任期會比 T 要大）。
投票者會在它給 leaderU?投票時存儲那個條目，因為任何中間的領導人都保有該條目（基于假設），領導人從來不會移除這個條目，并且追隨者也只會在和領導人沖突時才會移除日志條目。
投票者給 leaderU?投票了，所以 leaderU?的日志必須和投票者的一樣新。這就導致了一個矛盾。
首先，如果投票者和 leaderU?最后一條日志條目的任期號相同，那么 leaderU?的日志一定和投票者的一樣長，因此它的日志包含全部投票者的日志條目。這是矛盾的，因為在假設中投票者和 leaderU?包含的已提交條目是不同的。
除此之外， leaderU?的最后一條日志的任期號一定比投票者的大。另外，它也比 T 要大，因為投票者的最后一條日志條目的任期號最小也要是 T（它包含了所有任期 T 提交的日志條目）。創建 leaderU?最后一條日志條目的上一任領導人必須包含已經提交的日志條目（基于假設）。那么，根據日志匹配原則（Log Matching），leaderU?也一定包含那條提交的日志條目，這也是矛盾的。
這時就完成了矛盾推導。因此，所有比任期 T 大的領導人一定包含所有在任期 T 提交的日志條目。
日志匹配原則（Log Matching）保證了未來的領導人也會包含被間接提交的日志條目，就像 圖-8 中（d）時刻索引為2的條目。
通過給出了 領導人完全原則（Leader Completeness)，我們能夠證明 表-3 中的狀態機安全原則（State Machine Safety），狀態機安全原則（State Machine Safety）講的是如果一臺服務器將給定索引上的日志條目應用到了它自己的狀態機上，其它服務器的同一索引位置不可能應用的是其它條目。在一個服務器應用一條日志條目到它自己的狀態機中時，它的日志必須和領導人的日志在該條目和之前的條目上相同，并且已經被提交。現在我們來考慮在任何一個服務器應用一個指定索引位置的日志的最小任期；日志完全特性（Log Completeness Property）保證擁有更高任期號的領導人會存儲相同的日志條目，所以之后的任期里應用某個索引位置的日志條目也會是相同的值。因此，狀態機安全特性是成立的。
最后，Raft 算法需要服務器按照日志中索引位置順序應用日志條目。和狀態機安全特性結合起來看，這就意味著所有的服務器會應用相同的日志序列集到自己的狀態機中，并且是按照相同的順序。
5.5 追隨者和候選人崩潰
截止到目前，我們只討論了領導人崩潰的問題。追隨者和候選人崩潰的問題解決起來要比領導人崩潰要簡單得多，這兩者崩潰的處理方式是一樣的。如果一個追隨者或者候選人崩潰了，那么之后的發送給它的 RequestVote RPC 和 AppendEntries RPC 會失敗。Raft 通過無限的重試來處理這些失敗；如果崩潰的服務器重啟了，RPC 就會成功完成。如果一個服務器在收到了 RPC 之后但是在響應之前崩潰了，那么它會在重啟之后再次收到同一個 RPC。因為 Raft 中的 RPC 都是冪等的，因此不會有什么問題。例如，如果一個追隨者收到了一個已經包含在它的日志中的 AppendEntries 請求，它會忽視這個新的請求。
5.6 時序和可用性
我們對于 Raft 的要求之一就是安全性不依賴于時序（timing）：系統不能僅僅因為一些事件發生的比預想的快一些或慢一些就產生錯誤。然而，可用性（系統可以及時響應客戶端的特性）不可避免的要依賴時序。例如，如果消息交換在服務器崩潰時花費更多的時間，候選人不會等待太長的時間來贏得選舉；沒有一個穩定的領導人，Raft 將無法工作。
領導人選取是 Raft 中對時序要求最關鍵的地方。Raft 會選出并且保持一個穩定的領導人只有系統滿足下列時序要求（timing requirement）：
?
broadcastTime << electionTimeout << MTBF?
在這個不等式中，broadcastTime指的是一臺服務器并行的向集群中的其他服務器發送 RPC 并且收到它們的響應的平均時間；electionTimeout指的就是在 5.2節 描述的選舉超時時間；MTBF指的是單個服務器發生故障的間隔時間的平均數。broadcastTime應該比electionTimeout小一個數量級，為的是使領導人能夠持續發送心跳信息（heartbeat）來阻止追隨者們開始選舉；根據已經給出的隨機化選舉超時時間方法，這個不等式也使得瓜分選票的情況變成不可能。electionTimeout也要比MTBF小幾個數量級，為的是使得系統穩定運行。當領導人崩潰時，整個大約會在electionTimeout的時間內不可用；我們希望這種情況僅占全部時間的很小的一部分。
broadcastTime和MTBF是由系統決定的性質，但是electionTimeout是我們必須做出選擇的。Raft 的 RPC 需要接收方將信息持久化的保存到穩定存儲中去，所以廣播時間大約是 0.5 毫秒到 20 毫秒，這取決于存儲的技術。因此，electionTimeout一般在 10ms 到 500ms 之間。大多數的服務器的MTBF都在幾個月甚至更長，很容易滿足這個時序需求。
6. 集群成員變化
截止到目前，我們都假定集群的配置（加入到一致性算法的服務器集合）是固定的。在實際中，我們會經常更改配置，例如，替換掉那些崩潰的機器或者更改復制級別。雖然通過關閉整個集群，升級配置文件，然后重啟整個集群也可以解決這個問題，但是這回導致在更改配置的過程中，整個集群不可用。另外，如果存在需要手工操作，那么就會有操作失誤的風險。為了避免這些問題，我們決定采用自動改變配置并且把這部分加入到了 Raft 一致性算法中。
為了讓配置修改機制能夠安全，那么在轉換的過程中在任何時間點兩個領導人不能再同一個任期被同時選為領導人。不幸的是，服務器集群從舊的配置直接升級到新的配置的任何方法都是不安全的，一次性自動的轉換所有服務器是不可能的，所以集群可以在轉換的過程中劃分成兩個單獨的組（如 圖-10 所示）。
?
?
圖-10：從一個配置切換到另一個配置是不安全的因為不同的服務器會在不同的時間點進行切換。在這個例子中，集群數量從三臺轉換成五臺。不幸的是，在一個時間點有兩個服務器能被選舉成為領導人，一個是在使用舊的配置的機器中（Cold）選出的領導人，另一個領導人是通過新的配置（Cnew）選出來的。為了保證安全性，集群配置的調整必須使用兩階段（two-phase）方法。有許多種實現兩階段方法的實現。例如，一些系統在第一個階段先把舊的配置設為無效使得它無法處理客戶端請求，然后在第二階段啟用新的配置。在 Raft 中，集群先切換到一個過渡配置，我們稱其為共同一致（joint consensus）；一旦共同一致被提交了，然后系統再切換到新的配置。共同一致是舊的配置和新的配置的組合：
-
日志條目被復制給集群中新、老配置的所有服務器。
-
新、老配置的服務器都能成為領導人。
-
需要分別在兩種配置上獲得大多數的支持才能達成一致（針對選舉和提交）
共同一致允許獨立的服務器在不影響安全性的前提下，在不同的時間進行配置轉換過程。此外，共同一致可以讓集群在配置轉換的過程中依然能夠響應服務器請求。
?
?
圖-11：集群配置變更的時間線。虛線表示的是已經被創建但是還沒提交的配置條目，實線表示的是最新提交的配置條目。領導人首先在它的日志中創建 Cold,new配置條目并且將它提交到Cold,new（使用舊配置的大部分服務器和使用新配置的大部分服務器）。然后創建它創建Cnew配置條目并且將它提交到使用新配置的大部分機器上。這樣就不存在Cold和Cnew能夠分別同時做出決定的時刻。集群配置在復制日志中用特殊的日志條目來存儲和通信；圖-11 展示了配置變更的過程。當一個領導人接收到一個改變配置 Cold?為 Cnew?的請求，它會為了共同一致以前面描述的日志條目和副本的形式將配置存儲起來（圖中的 Cold,new）。一旦一個服務器將新的配置日志條目增加到它的日志中，它就會用這個配置來做出未來所有的決定（服務器總是使用最新的配置，無論它是否已經被提交）。這意味著領導人要使用 Cold,new?的規則來決定日志條目 Cold,new?什么時候需要被提交。如果領導人崩潰了，被選出來的新領導人可能是使用 Cold?配置也可能是 Cold,new?配置，這取決于贏得選舉的候選人是否已經接收到了 Cold,new?配置。在任何情況下， Cnew?配置在這一時期都不會單方面的做出決定。
一旦 Cold,new?被提交，那么無論是 Cold?還是 Cnew，在沒有經過他人批準的情況下都不可能做出決定，并且領導人完全特性（Leader Completeness Property）保證了只有擁有 Cold,new?日志條目的服務器才有可能被選舉為領導人。這個時候，領導人創建一條關于 Cnew?配置的日志條目并復制給集群就是安全的了。另外，每個服務器在收到新的配置的時候就會立即生效。當新的配置在 Cnew的規則下被提交，舊的配置就變得無關緊要，同時不使用新的配置的服務器就可以被關閉了。如 圖-11，Cold?和 Cnew?沒有任何機會同時做出單方面的決定；這就保證了安全性。
針對重新配置提出了三個問題。第一個問題是一開始的時候新的服務器可能沒有任何日志條目。如果它們在這個狀態下加入到集群中，那么它們需要一段時間來更新追趕，在這個階段它們還不能提交新的日志條目。為了避免這種可用性的間隔時間，Raft 在配置更新的時候使用了一種額外的階段，在這個階段，新的服務器以沒有投票權的身份加入到集群中來（領導人復制日志給他們，但是不把它們考慮到大多數中）。一旦新的服務器追趕上了集群中的其它機器，重新配置可以像上面描述的一樣處理。
第二個問題是，集群的領導人可能不是新配置的一員。在這種情況下，領導人就會在提交了 Cnew日志之后退位（回到跟隨者狀態）。這意味著有這樣的一段時間，領導人管理著集群，但是不包括自己；它復制日志但是不把它自己看作是大多數之一。當 Cnew?被提交時，會發生領導人過渡，因為這時是新的配置可以獨立工作的最早的時間點（總是能夠在 Cnew?配置下選出新的領導人）。在此之前，可能只能從 Cold?中選出領導人。
第三個問題是，移除不在 Cnew?中的服務器可能會擾亂集群。這些服務器將不會再接收到心跳（heartbeat），所以當選舉超時時，它們就會進行新的選舉過程。它們會發送帶有新的任期號的 RequestVote RPC，這樣會導致當前的領導人回退成跟隨者狀態。新的領導人最終會被選出來，但是被移除的服務器將會再次超時，然后這個過程會再次重復，導致整體可用性大幅降低。
為了避免這個問題，當服務器確認當前領導人存在時，服務器會忽略 RequestVote RPC。特別的，當服務器在當前最小選舉超時時間內收到一個 RequestVote RPC，它不會更新當前的任期號或者投出選票。這不會影響正常的選舉，每個服務器在開始一次選舉之前，至少等待一個最小選舉超時時間。然而，這有利于避免被移除的服務器擾亂：如果領導人能夠發送心跳給集群，那么它就不會被更大的任期號廢除。
7. 日志壓縮
Raft 產生的日志在持續的正常操作中不斷增長，但是在實際的系統中，它不會無限的增長下去。隨著日志的不斷增長，它會占據越來越多的空間并且花費更多的時間重置。如果沒有一個機制使得它能夠廢棄在日志中不斷累積的過時的信息就會引起可用性問題。
快照（snapshot）是最簡單的壓縮方式。在快照中，全部的當前系統狀態都被寫入到快照中，存儲到持久化的存儲中，然后在那個時刻之前的全部日志都可以被丟棄。在 Chubby 和 ZooKeeper 中都使用了快照技術，這一章的剩下的部分會介紹 Raft 中使用的快照技術。
增量壓縮（incremental approaches）的方法，例如日志清理（log cleaning）或者日志結構合并樹（log-structured merge trees），都是可行的。這些方法每次只對一小部分數據進行操作，這樣就分散了壓縮的負載壓力。首先，他們先選擇一個已經積累的大量已經被刪除或者被覆蓋對象的區域，然后重寫那個區域還活躍的對象，之后釋放那個區域。和簡單操作整個數據集合的快照相比，需要增加復雜的機制來實現。狀態機可以使用和快照相同的接口來實現 LSM tree ，但是日志清除方法就需要修改 Raft 了。
?
?
圖-12：一個服務器用新的快照替換了從 1 到 5 的條目，快照值存儲了當前的狀態。快照中包含了最后的索引位置和任期號。圖-12 展示了 Raft 中快照的基礎思想。每個服務器獨立的創建快照，只包括已經被提交的日志。主要的工作包括將狀態機的狀態寫入到快照中。Raft 也將一些少量的元數據包含到快照中：最后被包含的索引（last included index）指的是被快照取代的最后的條目在日志中的索引值（狀態機最后應用的日志），最后被包含的任期（last included term）指的是該條目的任期號。保留這些數據是為了支持快照前的第一個條目的附加日志請求時的一致性檢查，因為這個條目需要最后的索引值和任期號。為了支持集群成員更新（第 6 章），快照中也將最后的一次配置作為最后一個條目存下來。一旦服務器完成一次快照，他就可以刪除最后索引位置之前的所有日志和快照了。
盡管通常服務器都是獨立的創建快照，但是領導人必須偶爾的發送快照給一些落后的跟隨者。這通常發生在當領導人已經丟棄了下一條需要發送給跟隨者的日志條目的時候。幸運的是這種情況不是常規操作：一個與領導人保持同步的跟隨者通常都會有這個條目。然而一個運行非常緩慢的跟隨者或者新加入集群的服務器（第 6 章）將不會有這個條目。這時讓這個跟隨者更新到最新的狀態的方式就是通過網絡把快照發送給它們。
* 安裝快照 RPC（InstallSnapshot RPC）*
在領導人發送快照給跟隨者時使用調用。領導人總是按順序發送。
| term | 領導人的任期 |
| leaderId | 為了追隨者能重定向到客戶端 |
| lastIncludedIndex | 快照中包含的最后日志條目的索引值 |
| lastIncludedTerm | 快照中包含的最后日志條目的任期號 |
| offset | 分塊在快照中的偏移量 |
| data[] | 快照塊的原始數據 |
| done | 如果是最后一塊數據則為真 |
| 返回值 | 描述 |
| term | currentTerm，用于領導人更新自己 |
接受者需要實現：
如果term < currentTerm立刻回復
如果是第一個分塊（offset 為 0）則創建新的快照
在指定的偏移量寫入數據
如果?done為 false，則回復并繼續等待之后的數據
保存快照文件，丟棄所有存在的或者部分有著更小索引號的快照
如果現存的日志擁有相同的最后任期號和索引值，則后面的數據繼續保留并且回復
丟棄全部日志
能夠使用快照來恢復狀態機（并且裝載快照中的集群配置）
在這種情況下領導人使用一種叫做安裝快照（InstallSnapshot）的新的 RPC 來發送快照給太落后的跟隨者；見 表-13。當跟隨者通過這種 RPC 接收到快照時，它必須自己決定對于已經存在的日志該如何處理。通常快照會包含沒有在接收者日志中存在的信息。在這種情況下，跟隨者直接丟棄它所有的日志；這些會被快照所取代，但是可能會和沒有提交的日志產生沖突。如果接收到的快照是自己日志的前面部分（由于網絡重傳或者錯誤），那么被快照包含的條目將會被全部刪除，但是快照之后的條目必須是正確的和并且被保留下來。
這種快照的方式背離了 Raft 的強領導人原則（strong leader principle），因為跟隨者可以在不知道領導人情況下創建快照。但是我們認為這種背離是值得的。領導人的存在，是為了解決在達成一致性的時候的沖突，但是在創建快照的時候，一致性已經達成，這時不存在沖突了，所以沒有領導人也是可以的。數據依然是從領導人傳給跟隨者，只是跟隨者可以重新組織它們的數據了。
我們考慮過一種替代的基于領導人的快照方案，即只有領導人創建快照，然后發送給所有的跟隨者。但是這樣做有兩個缺點。第一，發送快照會浪費網絡帶寬并且延緩了快照處理的時間。每個跟隨者都已經擁有了所有產生快照需要的信息，而且很顯然，自己從本地的狀態中創建快照比通過網絡接收別人發來的要經濟。第二，領導人的實現會更加復雜。例如，領導人需要發送快照的同時并行的將新的日志條目發送給跟隨者，這樣才不會阻塞新的客戶端請求。
還有兩個問題影響了快照的性能。首先，服務器必須決定什么時候應該創建快照。如果快照創建的過于頻繁，那么就會浪費大量的磁盤帶寬和其他資源；如果創建快照頻率太低，它就要承受耗盡存儲容量的風險，同時也增加了從日志重建的時間。一個簡單的策略就是當日志大小達到一個固定大小的時候就創建一次快照。如果這個閾值設置的顯著大于期望的快照的大小，那么快照對磁盤壓力的影響就會很小了。
第二個影響性能的問題就是寫入快照需要花費顯著的一段時間，并且我們還不希望影響到正常操作。解決方案是通過寫時復制（copy-on-write）的技術，這樣新的更新就可以被接收而不影響到快照。例如，具有函數式數據結構的狀態機天然支持這樣的功能。另外，操作系統的寫時復制技術的支持（如 Linux 上的 fork）可以被用來創建完整的狀態機的內存快照（我們的實現就是這樣的）。
8. 客戶端交互
這一節將介紹客戶端是如何和 Raft 進行交互的，包括客戶端是如何發現領導人的和 Raft 是如何支持線性化語義（linearizable semantics）的。這些問題對于所有基于一致性的系統都存在，并且 Raft 的解決方案和其他的也差不多。
Raft 中的客戶端將所有請求發送給領導人。當客戶端啟動的時候，它會隨機挑選一個服務器進行通信。如果客戶端第一次挑選的服務器不是領導人，那么那個服務器會拒絕客戶端的請求并且提供它最近接收到的領導人的信息（附加條目請求包含了領導人的網絡地址）。如果領導人已經崩潰了，那么客戶端的請求就會超時；客戶端之后會再次重試隨機挑選服務器的過程。
我們 Raft 的目標是要實現線性化語義（linearizable semantics）（每一次操作立即執行，在它調用和收到回復之間只執行一次）。但是，如上述所說，Raft 是可以多次執行同一條命令的：例如，如果領導人在提交了這條日志之后，但是在響應客戶端之前崩潰了，那么客戶端會和新的領導人重試這條指令，導致這條命令就被再次執行了。解決方案就是客戶端對于每一條指令都賦予一個唯一的序列號。然后，狀態機跟蹤每條指令最新的序列號和相應的響應。如果接收到一條指令，它的序列號已經被執行了，那么就立即返回結果，而不重新執行指令。
只讀（read-only）的操作可以直接處理而不需要記錄日志。但是，在不增加任何限制的情況下，這么做可能會冒著返回過期數據(stale data)的風險，因為領導人響應客戶端請求時可能已經被新的領導人作廢了，但是它還不知道。線性化的讀操作必須不能返回過期數據，Raft 需要使用兩個額外的措施在不使用日志的情況下保證這一點。首先，領導人必須有關于被提交日志的最新信息。領導人完全原則（Leader Completeness Property）保證了領導人一定擁有所有已經被提交的日志條目，但是在它任期開始的時候，它可能不知道哪些是已經被提交的。為了知道這些信息，它需要在它的任期里提交一條日志條目。Raft 中通過領導人在任期開始的時候提交一個空白的沒有任何操作的日志條目到日志中去來進行實現。第二，領導人在處理只讀的請求之前必須檢查自己是否已經被廢除了（如果一個更新的領導人被選舉出來，它自己的信息就已經過期了）。Raft 中通過讓領導人在響應只讀請求之前，先和集群中的大多數節點交換一次心跳（heartbeat）信息來處理這個問題。另外，領導人可以依賴心跳機制來實現一種租約的機制，但是這種方法依賴時序來保證安全性（它假設時間誤差是有界的）。
9. 實現和評價
我們已經為 RAMCloud 實現了 Raft 算法作為存儲配置信息的復制狀態機的一部分，并且幫助 RAMCloud 協調故障轉移。這個 Raft 實現包含大約 2000 行 C++ 代碼，其中不包括測試、注釋和空行。這些代碼是開源的。同時也有大約 25 個其他獨立的第三方的基于這篇論文草稿的開源實現，針對不同的開發場景。同時，很多公司已經部署了基于 Raft 的系統。
這一章會從三個方面來評估 Raft 算法：可理解性、正確性和性能。
9.1 可理解性
為了比較 Paxos 和 Raft 算法的可理解性，我們針對高層次的本科生和研究生，在斯坦福大學的高級操作系統課程和加州大學伯克利分校的分布式計算課程上，進行了一次學習的實驗。我們分別拍了針對 Raft 和 Paxos 的視頻課程，并準備了相應的小測驗。Raft 的視頻講課覆蓋了這篇論文除了日志壓縮之外的所有內容；Paxos 課程包含了足夠的資料來創建一個等價的復制狀態機，包括單決策 Paxos，多決策 Paxos，重新配置和一些實際系統需要的性能優化（例如領導人選舉）。小測驗測試一些對算法的基本理解和解釋一些示例。每個學生都是看完第一個視頻，回答相應的測試，再看第二個視頻，回答相應的測試。大約有一半的學生先進行 Paxos 部分，然后另一半先進行 Raft 部分，這是為了說明兩者獨立的區別從第一個算法處學來的經驗。我們計算參加人員的每一個小測驗的得分來看參與者是否對 Raft 的理解更好。
| 相同的講課質量 | 使用相同的講師。Paxos 的講義是基于之前在幾所大學中使用的材料的并且做了改進。Paxos 的講義要長 14% | 視頻 |
| 相同的測試難度 | 用難度給問題分組，在測試中成對出現 | 測驗 |
| 公平的打分 | 使用紅字標題。隨機順序打分，兩個測驗交替進行。 | 紅字標題 |
我們盡可能的使得 Paxos 和 Raft 的比較更加公平。這個實驗偏愛 Paxos 表現在兩個方面：43 個參加者中有 15 個人在之前有一些 Paxos 的經驗，并且 Paxos 的視頻要長 14%。如表-1 總結的那樣，我們采取了一些措施來減輕這種潛在的偏見。我們所有的材料都可供審查。
?
圖-14：表示了 43 個學生在 Paxos 和 Raft 的小測驗中的成績的散點圖。在對角線之上的點表示在 Raft 獲得了更高分數的學生。
參加者平均在 Raft 的測驗中比 Paxos 高 4.9 分（總分 60，那么 Raft 的平均得分是 25.7，而 Paxos 是 20.8）；圖-14 展示了每個參與者的得分。一對 t -測試表明，擁有 95% 的可信度，真實的 Raft 分數分布至少比 Paxos 高 2.5 分。
我們也建立了一個線性回歸模型來預測一個新的學生的測驗成績，基于以下三個因素：他們使用的是哪個小測驗，之前對 Paxos 的經驗，和學習算法的順序。模型顯示，對小測驗的選擇會產生 12.5 分的差別在對 Raft 的好感度上。這顯著的高于之前的 4.9 分，因為很多學生在之前都已經有了對于 Paxos 的經驗，這相當明顯的幫助 Paxos，對 Raft 就沒什么太大影響了。但是奇怪的是，模型預測對于先進行 Paxos 小測驗的人而言，Raft 的小測驗得分會比 Paxos 低 6.3 分；我們不知道為什么，但這在統計學上是這樣的。
?
圖-15：通過一個 5 分制的問題，參與者（左邊）被問哪個算法他們覺得在一個高效正確的系統里更容易實現，右邊被問哪個更容易向學生解釋。
我們同時也在測驗之后調查了參與者，他們認為哪個算法更加容易實現和解釋；這個的結果在圖-15 上。壓倒性的結果表明 Raft 算法更加容易實現和解釋（41 人中的 33個）。但是，這種自己報告的結果不如參與者的成績更加可信，并且參與者可能因為我們的 Raft 更加易于理解的假說而產生偏見。
關于 Raft 用戶學習有一個更加詳細的討論，詳見http://ramcloud.stanford.edu/ ?ongaro/thesis.pdf
9.2 正確性
在第5章，我們已經進行了一個正式的說明，和對一致性機制的安全性證明。這個正式說明通過?TLA+?讓 表-2 中的信息非常清晰。它大約有 400 行并且充當了證明的主題。同時對于任何想實現的人也是十分有用的。我們非常機械的通過 TLA 證明系統證明了日志完全特性（Log Completeness Property）。然而，這個證明依賴的約束前提還沒有被機械證明（例如，我們還沒有證明這個說明中的類型安全 type safety）。而且，我們已經寫了一個非正式的證明關于狀態機安全性質是完備的，并且是相當清晰的（大約 3500 個詞）。
9.3 性能
Raft 和其他一致性算法例如 Paxos 有著差不多的性能。在性能方面，最重要的關注點是，當領導人被選舉成功時，什么時候復制新的日志條目。Raft 通過很少數量的消息包（一輪從領導人到集群大多數機器的消息）就達成了這個目的。同時，進一步提升 Raft 的性能也是可行的。例如，很容易通過支持批量操作和管道操作來提高吞吐量和降低延遲。對于其他一致性算法已經提出過很多性能優化方案；其中有很多也可以應用到 Raft 中來，但是我們暫時把這個問題放到未來的工作中去。
我們使用我們自己的 Raft 實現來衡量 Raft 領導人選舉的性能并且回答以下兩個問題。首先，領導人選舉的過程收斂是否快速？第二，在領導人宕機之后，最小的系統宕機時間是多久？
?
?
圖-16：發現并替換一個已經崩潰的領導人的時間。上面的圖考察了在選舉超時時間上的隨機化程度，下面的圖考察了最小超時時間。每條線代表了 1000 次實驗（除了 150-150 毫秒只試了 100 次），和相應的確定的選舉超時時間。例如，150-155 毫秒意思是，選舉超時時間從這個區間范圍內隨機選擇并確定下來。這個實驗在一個擁有 5 個節點的集群上進行，其廣播時延大約是 15 毫秒。對于 9 個節點的集群，結果也差不多。為了衡量領導人選舉，我們反復的使一個擁有五個節點的服務器集群的領導人宕機，并計算需要多久才能發現領導人已經宕機并選出一個新的領導人（見圖-16）。為了構建一個最壞的場景，在每一的嘗試里，服務器都有不同長度的日志，意味著有些候選人是沒有成為領導人的資格的。另外，為了促成選票瓜分的情況，我們的測試腳本在終止領導人之前同步的發送了一次心跳廣播（這大約和領導人在崩潰前復制一個新的日志給其他機器很像）。領導人均勻的隨機的在心跳間隔里宕機，也就是最小選舉超時時間的一半。因此，最小宕機時間大約就是最小選舉超時時間的一半。
圖-16 上面的圖表表明，只需要在選舉超時時間上使用很少的隨機化就可以大大避免選票被瓜分的情況。在沒有隨機化的情況下，在我們的測試里，選舉過程由于太多的選票瓜分的情況往往都需要花費超過 10 秒鐘。僅僅增加 5 毫秒的隨機化時間，就大大的改善了選舉過程，現在平均的宕機時間只有 287 毫秒。增加更多的隨機化時間可以大大改善最壞情況：通過增加 50 毫秒的隨機化時間，最壞的完成情況（1000 次嘗試）只要 513 毫秒。
圖-16 中下面的圖顯示，通過減少選舉超時時間可以減少系統的宕機時間。在選舉超時時間為 12-24 毫秒的情況下，只需要平均 35 毫秒就可以選舉出新的領導人（最長的一次花費了 152 毫秒）。然而，進一步降低選舉超時時間的話就會違反 Raft 的時間不等式需求：在選舉新領導人之前，領導人就很難發送完心跳包。這會導致沒有意義的領導人改變并降低了系統整體的可用性。我們建議使用更為保守的選舉超時時間，比如 150-300 毫秒；這樣的時間不大可能導致沒有意義的領導人改變，而且依然提供不錯的可用性。
10. 相關工作
已經有很多關于一致性算法的工作被發表出來，其中很多都可以歸到下面的類別中：
- Lamport 關于 Paxos 的原始描述，和嘗試描述的更清晰的論文。
- 關于 Paxos 的更詳盡的描述，補充遺漏的細節并修改算法，使得可以提供更加容易的實現基礎。
- 實現一致性算法的系統，例如 Chubby，ZooKeeper 和 Spanner。對于 Chubby 和 Spanner 的算法并沒有公開發表其技術細節，盡管他們都聲稱是基于 Paxos 的。ZooKeeper 的算法細節已經發表，但是和 Paxos 有著很大的差別。
- Paxos 可以應用的性能優化。
- Oki 和 Liskov 的 Viewstamped Replication（VR），一種和 Paxos 差不多的替代算法。原始的算法描述和分布式傳輸協議耦合在了一起，但是核心的一致性算法在最近的更新里被分離了出來。VR 使用了一種基于領導人的方法，和 Raft 有很多相似之處。
Raft 和 Paxos 最大的不同之處就在于 Raft 的強領導特性：Raft 使用領導人選舉作為一致性協議里必不可少的部分，并且將盡可能多的功能集中到了領導人身上。這樣就可以使得算法更加容易理解。例如，在 Paxos 中，領導人選舉和基本的一致性協議是正交的：領導人選舉僅僅是性能優化的手段，而且不是一致性所必須要求的。但是，這樣就增加了多余的機制：Paxos 同時包含了針對基本一致性要求的兩階段提交協議和針對領導人選舉的獨立的機制。相比較而言，Raft 就直接將領導人選舉納入到一致性算法中，并作為兩階段一致性的第一步。這樣就減少了很多機制。
像 Raft 一樣，VR 和 ZooKeeper 也是基于領導人的，因此他們也擁有一些 Raft 的優點。但是，Raft 比 VR 和 ZooKeeper 擁有更少的機制因為 Raft 盡可能的減少了非領導人的功能。例如，Raft 中日志條目都遵循著從領導人發送給其他人這一個方向：附加條目 RPC 是向外發送的。在 VR 中，日志條目的流動是雙向的（領導人可以在選舉過程中接收日志）；這就導致了額外的機制和復雜性。根據 ZooKeeper 公開的資料看，它的日志條目也是雙向傳輸的，但是它的實現更像 Raft。
和上述我們提及的其他基于一致性的日志復制算法中，Raft 的消息類型更少。例如，我們數了一下 VR 和 ZooKeeper 使用的用來基本一致性需要和成員改變的消息數（排除了日志壓縮和客戶端交互，因為這些都比較獨立且和算法關系不大）。VR 和 ZooKeeper 都分別定義了 10 中不同的消息類型，相對的，Raft 只有 4 中消息類型（兩種 RPC 請求和對應的響應）。Raft 的消息都稍微比其他算法的要信息量大，但是都很簡單。另外，VR 和 ZooKeeper 都在領導人改變時傳輸了整個日志；所以為了能夠實踐中使用，額外的消息類型就很必要了。
Raft 的強領導人模型簡化了整個算法，但是同時也排斥了一些性能優化的方法。例如，平等主義 Paxos （EPaxos）在某些沒有領導人的情況下可以達到很高的性能。平等主義 Paxos 充分發揮了在狀態機指令中的交換性。任何服務器都可以在一輪通信下就提交指令，除非其他指令同時被提出了。然而，如果指令都是并發的被提出，并且互相之間不通信溝通，那么 EPaxos 就需要額外的一輪通信。因為任何服務器都可以提交指令，所以 EPaxos 在服務器之間的負載均衡做的很好，并且很容易在 WAN 網絡環境下獲得很低的延遲。但是，他在 Paxos 上增加了非常明顯的復雜性。
一些集群成員變換的方法已經被提出或者在其他的工作中被實現，包括 Lamport 的原始的討論，VR 和 SMART。我們選擇使用共同一致（joint consensus）的方法因為它對一致性協議的其他部分影響很小，這樣我們只需要很少的一些機制就可以實現成員變換。Raft 沒有采用 Lamport 的基于 α 的方法是因為它假設在沒有領導人的情況下也可以達到一致性。和 VR 和 SMART 相比較，Raft 的重新配置算法可以在不限制正常請求處理的情況下進行；相比較而言，VR 需要停止所有的處理過程，SMART 引入了一個和 α 類似的方法，限制了請求處理的數量。和 VR、SMART 比較而言，Raft 的方法同時需要更少的額外機制來實現。
11. 總結
算法的設計通常會把正確性，效率或者簡潔作為主要的目標。盡管這些都是很有意義的目標，但是我們相信，可理解性也是一樣的重要。在開發者把算法應用到實際的系統中之前，這些目標沒有一個會被實現，這些都會必然的偏離發表時的形式。除非開發人員對這個算法有著很深的理解并且有著直觀的感覺，否則將會對他們而言很難在實現的時候保持原有期望的特性。
在這篇論文中，我們嘗試解決分布式一致性問題，但是一個廣為接受但是十分令人費解的算法 Paxos 已經困擾了無數學生和開發者很多年了。我們創造了一種新的算法 Raft，顯而易見的比 Paxos 要容易理解。我們同時也相信，Raft 也可以為實際的實現提供堅實的基礎。把可理解性作為設計的目標改變了我們設計 Raft 的方式；這個過程是我們發現我們最終很少有技術上的重復，例如問題分解和簡化狀態空間。這些技術不僅提升了 Raft 的可理解性，同時也使我們堅信其正確性。
12. 鳴謝
這項研究必須感謝以下人員的支持：Ali Ghodsi，David Mazie res，和伯克利 CS 294-91 課程、斯坦福 CS 240 課程的學生。Scott Klemmer 幫我們設計了用戶調查，Nelson Ray 建議我們進行統計學的分析。在用戶調查時使用的關于 Paxos 的幻燈片很大一部分是從 Lorenzo Alvisi 的幻燈片上借鑒過來的。特別的，非常感謝 DavidMazieres 和 Ezra Hoch，他們找到了 Raft 中一些難以發現的漏洞。許多人提供了關于這篇論文十分有用的反饋和用戶調查材料，包括 Ed Bugnion，Michael Chan，Hugues Evrard，Daniel Giffin，Arjun Gopalan，Jon Howell，Vimalkumar Jeyakumar，Ankita Kejriwal，Aleksandar Kracun，Amit Levy，Joel Martin，Satoshi Matsushita，Oleg Pesok，David Ramos，Robbert van Renesse，Mendel Rosenblum，Nicolas Schiper，Deian Stefan，Andrew Stone，Ryan Stutsman，David Terei，Stephen Yang，Matei Zaharia 以及 24 位匿名的會議審查人員（可能有重復），并且特別感謝我們的領導人 Eddie Kohler。Werner Vogels 發了一條早期草稿鏈接的推特，給 Raft 帶來了極大的關注。我們的工作由 Gigascale 系統研究中心和 Multiscale 系統研究中心給予支持，這兩個研究中心由關注中心研究程序資金支持，一個是半導體研究公司的程序，由 STARnet 支持，一個半導體研究公司的程序由 MARCO 和 DARPA 支持，在國家科學基金會的 0963859 號批準，并且獲得了來自 Facebook，Google，Mellanox，NEC，NetApp，SAP 和 Samsung 的支持。Diego Ongaro 由 Junglee 公司，斯坦福的畢業團體支持。
?
引用
本文的版權歸作者?羅遠航?所有，采用?Attribution-NonCommercial 3.0 License。任何人可以進行轉載、分享，但不可在未經允許的情況下用于商業用途；轉載請注明出處。感謝配合！
總結
以上是生活随笔為你收集整理的Raft 一致性算法论文译文的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： android jni开发方式
- 下一篇： 编程语言代码编写指南