一緻性協定Raft協定論文

尋找一種易于了解的一緻性算法（擴充版）

摘要

Raft 是一種為了管理複制日志的一緻性算法。它提供了和 Paxos 算法相同的功能和性能，但是它的算法結構和 Paxos 不同，使得 Raft 算法更加容易了解并且更容易建構實際的系統。為了提升可了解性，Raft 将一緻性算法分解成了幾個關鍵子產品，例如上司人選舉、日志複制和安全性。同時它通過實施一個更強的一緻性來減少需要考慮的狀态的數量。從一個使用者研究的結果可以證明，對于學生而言，Raft 算法比 Paxos 算法更加容易學習。Raft 算法還包括一個新的機制來允許叢集成員的動态改變，它利用重疊的大多數來保證安全性。

1 介紹

一緻性算法允許一組機器像一個整體一樣工作，即使其中一些機器出現故障也能夠繼續工作下去。正因為如此，一緻性算法在建構可信賴的大規模軟體系統中扮演着重要的角色。在過去的 10 年裡，Paxos 算法統治着一緻性算法這一領域：絕大多數的實作都是基于 Paxos 或者受其影響。同時 Paxos 也成為了教學領域裡講解一緻性問題時的示例。

但是不幸的是，盡管有很多工作都在嘗試降低它的複雜性，但是 Paxos 算法依然十分難以了解。并且，Paxos 自身的算法結構需要進行大幅的修改才能夠應用到實際的系統中。這些都導緻了工業界和學術界都對 Paxos 算法感到十分頭疼。

和 Paxos 算法進行過努力之後，我們開始尋找一種新的一緻性算法，可以為建構實際的系統和教學提供更好的基礎。我們的做法是不尋常的，我們的首要目标是可了解性：我們是否可以在實際系統中定義一個一緻性算法，并且能夠比 Paxos 算法以一種更加容易的方式來學習。此外，我們希望該算法友善系統建構者的直覺的發展。不僅一個算法能夠工作很重要，而且能夠顯而易見的知道為什麼能工作也很重要。

Raft 一緻性算法就是這些工作的結果。在設計 Raft 算法的時候，我們使用一些特别的技巧來提升它的可了解性，包括算法分解（Raft 主要被分成了上司人選舉，日志複制和安全三個子產品）和減少狀态機的狀态（相對于 Paxos，Raft 減少了非确定性和伺服器互相處于非一緻性的方式）。一份針對兩所大學 43 個學生的研究表明 Raft 明顯比 Paxos 算法更加容易了解。在這些學生同時學習了這兩種算法之後，和 Paxos 比起來，其中 33 個學生能夠回答有關于 Raft 的問題。

Raft 算法在許多方面和現有的一緻性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是它也有一些獨特的特性：

• 強上司者：和其他一緻性算法相比，Raft 使用一種更強的上司能力形式。比如，日志條目隻從上司者發送給其他的伺服器。這種方式簡化了對複制日志的管理并且使得 Raft 算法更加易于了解。
• 上司選舉：Raft 算法使用一個随機計時器來選舉上司者。這種方式隻是在任何一緻性算法都必須實作的心跳機制上增加了一點機制。在解決沖突的時候會更加簡單快捷。
• 成員關系調整：Raft 使用一種共同一緻的方法來處理叢集成員變換的問題，在這種方法下，處于調整過程中的兩種不同的配置叢集中大多數機器會有重疊，這就使得叢集在成員變換的時候依然可以繼續工作。

我們相信，Raft 算法不論出于教學目的還是作為實踐項目的基礎都是要比 Paxos 或者其他一緻性算法要優異的。它比其他算法更加簡單，更加容易了解；它的算法描述足以實作一個現實的系統；它有好多開源的實作并且在很多公司裡使用；它的安全性已經被證明；它的效率和其他算法比起來也不相上下。

接下來，這篇論文會介紹以下内容：複制狀态機問題（第 2 節），讨論 Paxos 的優點和缺點（第 3 節），讨論我們為了了解能力而使用的方法（第 4 節），闡述 Raft 一緻性算法（第 5-8 節），評價 Raft 算法（第 9 節），以及一些相關的工作（第 10 節）。

2 複制狀态機

一緻性算法是從複制狀态機的背景下提出的（參考英文原文引用37）。在這種方法中，一組伺服器上的狀态機産生相同狀态的副本，并且在一些機器宕掉的情況下也可以繼續運作。複制狀态機在分布式系統中被用于解決很多容錯的問題。例如，大規模的系統中通常都有一個叢集上司者，像 GFS、HDFS 和 RAMCloud，典型應用就是一個獨立的的複制狀态機去管理上司選舉和存儲配置資訊并且在上司人當機的情況下也要存活下來。比如 Chubby 和 ZooKeeper。

圖 1 ：複制狀态機的結構。一緻性算法管理着來自用戶端指令的複制日志。狀态機從日志中處理相同順序的相同指令，是以産生的結果也是相同的。

複制狀态機通常都是基于複制日志實作的，如圖 1。每一個伺服器存儲一個包含一系列指令的日志，并且按照日志的順序進行執行。每一個日志都按照相同的順序包含相同的指令，是以每一個伺服器都執行相同的指令序列。因為每個狀态機都是确定的，每一次執行操作都産生相同的狀态和同樣的序列。

保證複制日志相同就是一緻性算法的工作了。在一台伺服器上，一緻性子產品接收用戶端發送來的指令然後增加到自己的日志中去。它和其他伺服器上的一緻性子產品進行通信來保證每一個伺服器上的日志最終都以相同的順序包含相同的請求，盡管有些伺服器會當機。一旦指令被正确的複制，每一個伺服器的狀态機按照日志順序處理他們，然後輸出結果被傳回給用戶端。是以，伺服器叢集看起來形成一個高可靠的狀态機。

實際系統中使用的一緻性算法通常含有以下特性：

• 安全性保證（絕對不會傳回一個錯誤的結果）：在非拜占庭錯誤情況下，包括網絡延遲、分區、丢包、備援和亂序等錯誤都可以保證正确。
• 可用性：叢集中隻要有大多數的機器可運作并且能夠互相通信、和用戶端通信，就可以保證可用。是以，一個典型的包含 5 個節點的叢集可以容忍兩個節點的失敗。伺服器被停止就認為是失敗。他們當有穩定的存儲的時候可以從狀态中恢複回來并重新加入叢集。
• 不依賴時序來保證一緻性：實體時鐘錯誤或者極端的消息延遲在可能隻有在最壞情況下才會導緻可用性問題。
• 通常情況下，一條指令可以盡可能快的在叢集中大多數節點響應一輪遠端過程調用時完成。小部分比較慢的節點不會影響系統整體的性能。

3 Paxos算法的問題

在過去的 10 年裡，Leslie Lamport 的 Paxos 算法幾乎已經成為一緻性的代名詞：Paxos 是在課程教學中最經常使用的算法，同時也是大多數一緻性算法實作的起點。Paxos 首先定義了一個能夠達成單一決策一緻的協定，比如單條的複制日志項。我們把這一子集叫做單決策 Paxos。然後通過組合多個 Paxos 協定的執行個體來促進一系列決策的達成。Paxos 保證安全性和活性，同時也支援叢集成員關系的變更。Paxos 的正确性已經被證明，在通常情況下也很高效。

不幸的是，Paxos 有兩個明顯的缺點。第一個缺點是 Paxos 算法特别的難以了解。完整的解釋是出了名的不透明；通過極大的努力之後，也隻有少數人成功了解了這個算法。是以，有了幾次用更簡單的術語來解釋 Paxos 的嘗試。盡管這些解釋都隻關注了單決策的子集問題，但依然很具有挑戰性。在 2012 年 NSDI 的會議中的一次調查顯示，很少有人對 Paxos 算法感到滿意，甚至在經驗老道的研究者中也是如此。我們自己也嘗試去了解 Paxos；我們一直沒能了解 Paxos 直到我們讀了很多對 Paxos 的簡化解釋并且設計了我們自己的算法之後，這一過程花了近一年時間。

我們假設 Paxos 的不透明性來自它選擇單決策問題作為它的基礎。單決策 Paxos 是晦澀微妙的，它被劃分成了兩種沒有簡單直覺解釋和無法獨立了解的情景。是以，這導緻了很難建立起直覺的感受為什麼單決策 Paxos 算法能夠工作。構成多決策 Paxos 增加了很多錯綜複雜的規則。我們相信，在多決策上達成一緻性的問題（一份日志而不是單一的日志記錄）能夠被分解成其他的方式并且更加直接和明顯。

Paxos算法的第二個問題就是它沒有提供一個足夠好的用來建構一個現實系統的基礎。一個原因是還沒有一種被廣泛認同的多決策問題的算法。Lamport 的描述基本上都是關于單決策 Paxos 的；他簡要描述了實施多決策 Paxos 的方法，但是缺乏很多細節。當然也有很多具體化 Paxos 的嘗試，但是他們都互相不一樣，和 Paxos 的概述也不同。例如 Chubby 這樣的系統實作了一個類似于 Paxos 的算法，但是大多數的細節并沒有被公開。

而且，Paxos 算法的結構也不是十分易于建構實踐的系統；單決策分解也會産生其他的結果。例如，獨立的選擇一組日志條目然後合并成一個序列化的日志并沒有帶來太多的好處，僅僅增加了不少複雜性。圍繞着日志來設計一個系統是更加簡單高效的；新日志條目以嚴格限制的順序增添到日志中去。另一個問題是，Paxos 使用了一種對等的點對點的方式作為它的核心（盡管它最終提議了一種弱上司人的方法來優化性能）。在隻有一個決策會被制定的簡化世界中是很有意義的，但是很少有現實的系統使用這種方式。如果有一系列的決策需要被制定，首先選擇一個上司人，然後讓他去協調所有的決議，會更加簡單快速。

是以，實際的系統中很少有和 Paxos 相似的實踐。每一種實作都是從 Paxos 開始研究，然後發現很多實作上的難題，再然後開發了一種和 Paxos 明顯不一樣的結構。這樣是非常費時和容易出錯的，并且了解 Paxos 的難度使得這個問題更加糟糕。Paxos 算法在理論上被證明是正确可行的，但是現實的系統和 Paxos 差别是如此的大，以至于這些證明沒有什麼太大的價值。下面來自 Chubby 實作非常典型：

在Paxos算法描述和實作現實系統中間有着巨大的鴻溝。最終的系統建立在一種沒有經過證明的算法之上。

由于以上問題，我們認為 Paxos 算法既沒有提供一個良好的基礎給實踐的系統，也沒有給教學很好的幫助。基于一緻性問題在大規模軟體系統中的重要性，我們決定看看我們是否可以設計一個擁有更好特性的替代 Paxos 的一緻性算法。Raft算法就是這次實驗的結果。

4 為了可了解性的設計

設計 Raft 算法我們有幾個初衷：它必須提供一個完整的實際的系統實作基礎，這樣才能大大減少開發者的工作；它必須在任何情況下都是安全的并且在大多數的情況下都是可用的；并且它的大部分操作必須是高效的。但是我們最重要也是最大的挑戰是可了解性。它必須保證對于普遍的人群都可以十分容易的去了解。另外，它必須能夠讓人形成直覺的認識，這樣系統的建構者才能夠在現實中進行必然的擴充。

在設計 Raft 算法的時候，有很多的點需要我們在各種備選方案中進行選擇。在這種情況下，我們評估備選方案基于可了解性原則：解釋各個備選方案有多大的難度（例如，Raft 的狀态空間有多複雜，是否有微妙的暗示）？對于一個讀者而言，完全了解這個方案和暗示是否容易？

我們意識到對這種可了解性分析上具有高度的主觀性；盡管如此，我們使用了兩種通常适用的技術來解決這個問題。第一個技術就是衆所周知的問題分解：隻要有可能，我們就将問題分解成幾個相對獨立的，可被解決的、可解釋的和可了解的子問題。例如，Raft 算法被我們分成上司人選舉，日志複制，安全性和角色改變幾個部分。

我們使用的第二個方法是通過減少狀态的數量來簡化需要考慮的狀态空間，使得系統更加連貫并且在可能的時候消除不确定性。特别的，所有的日志是不允許有空洞的，并且 Raft 限制了日志之間變成不一緻狀态的可能。盡管在大多數情況下我們都試圖去消除不确定性，但是也有一些情況下不确定性可以提升可了解性。尤其是，随機化方法增加了不确定性，但是他們有利于減少狀态空間數量，通過處理所有可能選擇時使用相似的方法。我們使用随機化去簡化 Raft 中上司人選舉算法。

5 Raft 一緻性算法

Raft 是一種用來管理章節 2 中描述的複制日志的算法。圖 2 為了參考之用，總結這個算法的簡略版本，圖 3 列舉了這個算法的一些關鍵特性。圖中的這些元素會在剩下的章節逐一介紹。

Raft 通過選舉一個高貴的上司人，然後給予他全部的管理複制日志的責任來實作一緻性。上司人從用戶端接收日志條目，把日志條目複制到其他伺服器上，并且當保證安全性的時候告訴其他的伺服器應用日志條目到他們的狀态機中。擁有一個上司人大大簡化了對複制日志的管理。例如，上司人可以決定新的日志條目需要放在日志中的什麼位置而不需要和其他伺服器商議，并且資料都從上司人流向其他伺服器。一個上司人可以當機，可以和其他伺服器失去連接配接，這時一個新的上司人會被選舉出來。

通過上司人的方式，Raft 将一緻性問題分解成了三個相對獨立的子問題，這些問題會在接下來的子章節中進行讨論：

• 上司選舉：一個新的上司人需要被選舉出來，當現存的上司人當機的時候（章節 5.2）
• 日志複制：上司人必須從用戶端接收日志然後複制到叢集中的其他節點，并且強制要求其他節點的日志保持和自己相同。
• 安全性：在 Raft 中安全性的關鍵是在圖 3 中展示的狀态機安全：如果有任何的伺服器節點已經應用了一個确定的日志條目到它的狀态機中，那麼其他伺服器節點不能在同一個日志索引位置應用一個不同的指令。章節 5.4 闡述了 Raft 算法是如何保證這個特性的；這個解決方案涉及到一個額外的選舉機制（5.2 節）上的限制。

在展示一緻性算法之後，這一章節會讨論可用性的一些問題和系統中的候選人角色的問題。

狀态：

狀态	所有伺服器上持久存在的
currentTerm	伺服器最後一次知道的任期号（初始化為 0，持續遞增）
votedFor	在目前獲得選票的候選人的 Id
log[]	日志條目集；每一個條目包含一個使用者狀态機執行的指令，和收到時的任期号

狀态	所有伺服器上經常變的
commitIndex	已知的最大的已經被送出的日志條目的索引值
lastApplied	最後被應用到狀态機的日志條目索引值（初始化為 0，持續遞增）

狀态	在上司人裡經常改變的 （選舉後重新初始化）
nextIndex[]	對于每一個伺服器，需要發送給他的下一個日志條目的索引值（初始化為上司人最後索引值加一）
matchIndex[]	對于每一個伺服器，已經複制給他的日志的最高索引值

附加日志 RPC：

由上司人負責調用來複制日志指令；也會用作heartbeat

參數	解釋
term	上司人的任期号
leaderId	上司人的 Id，以便于跟随者重定向請求
prevLogIndex	新的日志條目緊随之前的索引值
prevLogTerm	prevLogIndex 條目的任期号
entries[]	準備存儲的日志條目（表示心跳時為空；一次性發送多個是為了提高效率）
leaderCommit	上司人已經送出的日志的索引值

傳回值	解釋
term	目前的任期号，用于上司人去更新自己
success	跟随者包含了比對上 prevLogIndex 和 prevLogTerm 的日志時為真

接收者實作：

1. 如果

   term < currentTerm

   就傳回 false （5.1 節）
2. 如果日志在 prevLogIndex 位置處的日志條目的任期号和 prevLogTerm 不比對，則傳回 false （5.3 節）
3. 如果已經存在的日志條目和新的産生沖突（索引值相同但是任期号不同），删除這一條和之後所有的 （5.3 節）
4. 附加任何在已有的日志中不存在的條目
5. 如果

   leaderCommit > commitIndex

   ，令 commitIndex 等于 leaderCommit 和 新日志條目索引值中較小的一個

請求投票 RPC：

由候選人負責調用用來征集選票（5.2 節）

參數	解釋
term	候選人的任期号
candidateId	請求選票的候選人的 Id
lastLogIndex	候選人的最後日志條目的索引值
lastLogTerm	候選人最後日志條目的任期号

傳回值	解釋
term	目前任期号，以便于候選人去更新自己的任期号
voteGranted	候選人赢得了此張選票時為真

接收者實作：

1. 如果

   term < currentTerm

   傳回 false （5.2 節）
2. 如果 votedFor 為空或者就是 candidateId，并且候選人的日志至少和自己一樣新，那麼就投票給他（5.2 節，5.4 節）

所有伺服器需遵守的規則：

所有伺服器：

• 如果

  commitIndex > lastApplied

  ，那麼就 lastApplied 加一，并把

  log[lastApplied]

  應用到狀态機中（5.3 節）
• 如果接收到的 RPC 請求或響應中，任期号

  T > currentTerm

  ，那麼就令 currentTerm 等于 T，并切換狀态為跟随者（5.1 節）

跟随者（5.2 節）：

• 響應來自候選人和上司者的請求
• 如果在超過選舉逾時時間的情況之前都沒有收到上司人的心跳，或者是候選人請求投票的，就自己變成候選人

候選人（5.2 節）：

• 在轉變成候選人後就立即開始選舉過程
  • 自增目前的任期号（currentTerm）
  • 給自己投票
  • 重置選舉逾時計時器
  • 發送請求投票的 RPC 給其他所有伺服器
• 如果接收到大多數伺服器的選票，那麼就變成上司人
• 如果接收到來自新的上司人的附加日志 RPC，轉變成跟随者
• 如果選舉過程逾時，再次發起一輪選舉

上司人：

• 一旦成為上司人：發送空的附加日志 RPC（心跳）給其他所有的伺服器；在一定的空餘時間之後不停的重複發送，以阻止跟随者逾時（5.2 節）
• 如果接收到來自用戶端的請求：附加條目到本地日志中，在條目被應用到狀态機後響應用戶端（5.3 節）
• 如果對于一個跟随者，最後日志條目的索引值大于等于 nextIndex，那麼：發送從 nextIndex 開始的所有日志條目：
  • 如果成功：更新相應跟随者的 nextIndex 和 matchIndex
  • 如果因為日志不一緻而失敗，減少 nextIndex 重試
• 如果存在一個滿足

  N > commitIndex

  的 N，并且大多數的

  matchIndex[i] ≥ N

  成立，并且

  log[N].term == currentTerm

  成立，那麼令 commitIndex 等于這個 N （5.3 和 5.4 節）

圖 2：一個關于 Raft 一緻性算法的濃縮總結（不包括成員變換和日志壓縮）。

特性	解釋
選舉安全特性	對于一個給定的任期号，最多隻會有一個上司人被選舉出來（5.2 節）
上司人隻附加原則	上司人絕對不會删除或者覆寫自己的日志，隻會增加（5.3 節）
日志比對原則	如果兩個日志在相同的索引位置的日志條目的任期号相同，那麼我們就認為這個日志從頭到這個索引位置之間全部完全相同（5.3 節）
上司人完全特性	如果某個日志條目在某個任期号中已經被送出，那麼這個條目必然出現在更大任期号的所有上司人中（5.4 節）
狀态機安全特性	如果一個上司人已經在給定的索引值位置的日志條目應用到狀态機中，那麼其他任何的伺服器在這個索引位置不會送出一個不同的日志（5.4.3 節）

圖 3：Raft 在任何時候都保證以上的各個特性。

5.1 Raft 基礎

一個 Raft 叢集包含若幹個伺服器節點；通常是 5 個，這允許整個系統容忍 2 個節點的失效。在任何時刻，每一個伺服器節點都處于這三個狀态之一：上司人、跟随者或者候選人。在通常情況下，系統中隻有一個上司人并且其他的節點全部都是跟随者。跟随者都是被動的：他們不會發送任何請求，隻是簡單的響應來自上司者或者候選人的請求。上司人處理所有的用戶端請求（如果一個用戶端和跟随者聯系，那麼跟随者會把請求重定向給上司人）。第三種狀态，候選人，是用來在 5.2 節描述的選舉新上司人時使用。圖 4 展示了這些狀态和他們之間的轉換關系；這些轉換關系會在接下來進行讨論。

圖 4：伺服器狀态。跟随者隻響應來自其他伺服器的請求。如果跟随者接收不到消息，那麼他就會變成候選人并發起一次選舉。獲得叢集中大多數選票的候選人将成為上司者。在一個任期内，上司人一直都會是上司人直到自己當機了。

圖 5：時間被劃分成一個個的任期，每個任期開始都是一次選舉。在選舉成功後，上司人會管理整個叢集直到任期結束。有時候選舉會失敗，那麼這個任期就會沒有上司人而結束。任期之間的切換可以在不同的時間不同的伺服器上觀察到。

Raft 把時間分割成任意長度的任期，如圖 5。任期用連續的整數标記。每一段任期從一次選舉開始，就像章節 5.2 描述的一樣，一個或者多個候選人嘗試成為上司者。如果一個候選人赢得選舉，然後他就在接下來的任期内充當上司人的職責。在某些情況下，一次選舉過程會造成選票的瓜分。在這種情況下，這一任期會以沒有上司人結束；一個新的任期（和一次新的選舉）會很快重新開始。Raft 保證了在一個給定的任期内，最多隻有一個上司者。

不同的伺服器節點可能多次觀察到任期之間的轉換，但在某些情況下，一個節點也可能觀察不到任何一次選舉或者整個任期全程。任期在 Raft 算法中充當邏輯時鐘的作用，這會允許伺服器節點查明一些過期的資訊比如陳舊的上司者。每一個節點存儲一個目前任期号，這一編号在整個時期内單調的增長。當伺服器之間通信的時候會交換目前任期号；如果一個伺服器的目前任期号比其他人小，那麼他會更新自己的編号到較大的編号值。如果一個候選人或者上司者發現自己的任期号過期了，那麼他會立即恢複成跟随者狀态。如果一個節點接收到一個包含過期的任期号的請求，那麼他會直接拒絕這個請求。

Raft 算法中伺服器節點之間通信使用遠端過程調用（RPCs），并且基本的一緻性算法隻需要兩種類型的 RPCs。請求投票（RequestVote） RPCs 由候選人在選舉期間發起（章節 5.2），然後附加條目（AppendEntries）RPCs 由上司人發起，用來複制日志和提供一種心跳機制（章節 5.3）。第 7 節為了在伺服器之間傳輸快照增加了第三種 RPC。當伺服器沒有及時的收到 RPC 的響應時，會進行重試， 并且他們能夠并行的發起 RPCs 來獲得最佳的性能。

5.2 上司人選舉

Raft 使用一種心跳機制來觸發上司人選舉。當伺服器程式啟動時，他們都是跟随者身份。一個伺服器節點繼續保持着跟随者狀态直到他從上司人或者候選者處接收到有效的 RPCs。上司者周期性的向所有跟随者發送心跳包（即不包含日志項内容的附加日志項 RPCs）來維持自己的權威。如果一個跟随者在一段時間裡沒有接收到任何消息，也就是選舉逾時，那麼他就會認為系統中沒有可用的上司者,并且發起選舉以選出新的上司者。

要開始一次選舉過程，跟随者先要增加自己的目前任期号并且轉換到候選人狀态。然後他會并行的向叢集中的其他伺服器節點發送請求投票的 RPCs 來給自己投票。候選人會繼續保持着目前狀态直到以下三件事情之一發生：(a) 他自己赢得了這次的選舉，(b) 其他的伺服器成為上司者，(c) 一段時間之後沒有任何一個獲勝的人。這些結果會分别的在下面的段落裡進行讨論。

當一個候選人從整個叢集的大多數伺服器節點獲得了針對同一個任期号的選票，那麼他就赢得了這次選舉并成為上司人。每一個伺服器最多會對一個任期号投出一張選票，按照先來先服務的原則（注意：5.4 節在投票上增加了一點額外的限制）。要求大多數選票的規則確定了最多隻會有一個候選人赢得此次選舉（圖 3 中的選舉安全性）。一旦候選人赢得選舉，他就立即成為上司人。然後他會向其他的伺服器發送心跳消息來建立自己的權威并且阻止新的上司人的産生。

在等待投票的時候，候選人可能會從其他的伺服器接收到聲明它是上司人的附加日志項 RPC。如果這個上司人的任期号（包含在此次的 RPC中）不小于候選人目前的任期号，那麼候選人會承認上司人合法并回到跟随者狀态。 如果此次 RPC 中的任期号比自己小，那麼候選人就會拒絕這次的 RPC 并且繼續保持候選人狀态。

第三種可能的結果是候選人既沒有赢得選舉也沒有輸：如果有多個跟随者同時成為候選人，那麼選票可能會被瓜分以至于沒有候選人可以赢得大多數人的支援。當這種情況發生的時候，每一個候選人都會逾時，然後通過增加目前任期号來開始一輪新的選舉。然而，沒有其他機制的話，選票可能會被無限的重複瓜分。

Raft 算法使用随機選舉逾時時間的方法來確定很少會發生選票瓜分的情況，就算發生也能很快的解決。為了阻止選票起初就被瓜分，選舉逾時時間是從一個固定的區間（例如 150-300 毫秒）随機選擇。這樣可以把伺服器都分散開以至于在大多數情況下隻有一個伺服器會選舉逾時；然後他赢得選舉并在其他伺服器逾時之前發送心跳包。同樣的機制被用在選票瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個随機的選舉逾時時間，然後在逾時時間内等待投票的結果；這樣減少了在新的選舉中另外的選票瓜分的可能性。9.3 節展示了這種方案能夠快速的選出一個上司人。

上司人選舉這個例子，展現了可了解性原則是如何指導我們進行方案設計的。起初我們計劃使用一種排名系統：每一個候選人都被賦予一個唯一的排名，供候選人之間競争時進行選擇。如果一個候選人發現另一個候選人擁有更高的排名，那麼他就會回到跟随者狀态，這樣高排名的候選人能夠更加容易的赢得下一次選舉。但是我們發現這種方法在可用性方面會有一點問題（如果高排名的伺服器當機了，那麼低排名的伺服器可能會逾時并再次進入候選人狀态。而且如果這個行為發生得足夠快，則可能會導緻整個選舉過程都被重置掉）。我們針對算法進行了多次調整，但是每次調整之後都會有新的問題。最終我們認為随機重試的方法是更加明顯和易于了解的。

5.3 日志複制

一旦一個上司人被選舉出來，他就開始為用戶端提供服務。用戶端的每一個請求都包含一條被複制狀态機執行的指令。上司人把這條指令作為一條新的日志條目附加到日志中去，然後并行的發起附加條目 RPCs 給其他的伺服器，讓他們複制這條日志條目。當這條日志條目被安全的複制（下面會介紹），上司人會應用這條日志條目到它的狀态機中然後把執行的結果傳回給用戶端。如果跟随者崩潰或者運作緩慢，再或者網絡丢包，上司人會不斷的重複嘗試附加日志條目 RPCs （盡管已經回複了用戶端）直到所有的跟随者都最終存儲了所有的日志條目。

圖 6：日志由有序序号标記的條目組成。每個條目都包含建立時的任期号（圖中框中的數字），和一個狀态機需要執行的指令。一個條目當可以安全的被應用到狀态機中去的時候，就認為是可以送出了。

日志以圖 6 展示的方式組織。每一個日志條目存儲一條狀态機指令和從上司人收到這條指令時的任期号。日志中的任期号用來檢查是否出現不一緻的情況，同時也用來保證圖 3 中的某些性質。每一條日志條目同時也都有一個整數索引值來表明它在日志中的位置。

上司人來決定什麼時候把日志條目應用到狀态機中是安全的；這種日志條目被稱為已送出。Raft 算法保證所有已送出的日志條目都是持久化的并且最終會被所有可用的狀态機執行。在上司人将建立的日志條目複制到大多數的伺服器上的時候，日志條目就會被送出（例如在圖 6 中的條目 7）。同時，上司人的日志中之前的所有日志條目也都會被送出，包括由其他上司人建立的條目。5.4 節會讨論某些當在上司人改變之後應用這條規則的隐晦内容，同時他也展示了這種送出的定義是安全的。上司人跟蹤了最大的将會被送出的日志項的索引，并且索引值會被包含在未來的所有附加日志 RPCs （包括心跳包），這樣其他的伺服器才能最終知道上司人的送出位置。一旦跟随者知道一條日志條目已經被送出，那麼他也會将這個日志條目應用到本地的狀态機中（按照日志的順序）。

我們設計了 Raft 的日志機制來維護一個不同伺服器的日志之間的高層次的一緻性。這麼做不僅簡化了系統的行為也使得更加可預計，同時他也是安全性保證的一個重要元件。Raft 維護着以下的特性，這些同時也組成了圖 3 中的日志比對特性：

• 如果在不同的日志中的兩個條目擁有相同的索引和任期号，那麼他們存儲了相同的指令。
• 如果在不同的日志中的兩個條目擁有相同的索引和任期号，那麼他們之前的所有日志條目也全部相同。

第一個特性來自這樣的一個事實，上司人最多在一個任期裡在指定的一個日志索引位置建立一條日志條目，同時日志條目在日志中的位置也從來不會改變。第二個特性由附加日志 RPC 的一個簡單的一緻性檢查所保證。在發送附加日志 RPC 的時候，上司人會把新的日志條目緊接着之前的條目的索引位置和任期号包含在裡面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的條目，那麼他就會拒絕接收新的日志條目。一緻性檢查就像一個歸納步驟：一開始空的日志狀态肯定是滿足日志比對特性的，然後一緻性檢查保護了日志比對特性當日志擴充的時候。是以，每當附加日志 RPC 傳回成功時，上司人就知道跟随者的日志一定是和自己相同的了。

在正常的操作中，上司人和跟随者的日志保持一緻性，是以附加日志 RPC 的一緻性檢查從來不會失敗。然而，上司人崩潰的情況會使得日志處于不一緻的狀态（老的上司人可能還沒有完全複制所有的日志條目）。這種不一緻問題會在上司人和跟随者的一系列崩潰下加劇。圖 7 展示了跟随者的日志可能和新的上司人不同的方式。跟随者可能會丢失一些在新的上司人中有的日志條目，他也可能擁有一些上司人沒有的日志條目，或者兩者都發生。丢失或者多出日志條目可能會持續多個任期。

圖 7：當一個上司人成功當選時，跟随者可能是任何情況（a-f）。每一個盒子表示是一個日志條目；裡面的數字表示任期号。跟随者可能會缺少一些日志條目（a-b），可能會有一些未被送出的日志條目（c-d），或者兩種情況都存在（e-f）。例如，場景 f 可能會這樣發生，某伺服器在任期 2 的時候是上司人，已附加了一些日志條目到自己的日志中，但在送出之前就崩潰了；很快這個機器就被重新開機了，在任期 3 重新被選為上司人，并且又增加了一些日志條目到自己的日志中；在任期 2 和任期 3 的日志被送出之前，這個伺服器又當機了，并且在接下來的幾個任期裡一直處于當機狀态。

在 Raft 算法中，上司人處理不一緻是通過強制跟随者直接複制自己的日志來解決了。這意味着在跟随者中的沖突的日志條目會被上司人的日志覆寫。5.4 節會闡述如何通過增加一些限制來使得這樣的操作是安全的。

要使得跟随者的日志進入和自己一緻的狀态，上司人必須找到最後兩者達成一緻的地方，然後删除從那個點之後的所有日志條目，發送自己的日志給跟随者。所有的這些操作都在進行附加日志 RPCs 的一緻性檢查時完成。上司人針對每一個跟随者維護了一個 nextIndex，這表示下一個需要發送給跟随者的日志條目的索引位址。當一個上司人剛獲得權力的時候，他初始化所有的 nextIndex 值為自己的最後一條日志的index加1（圖 7 中的 11）。如果一個跟随者的日志和上司人不一緻，那麼在下一次的附加日志 RPC 時的一緻性檢查就會失敗。在被跟随者拒絕之後，上司人就會減小 nextIndex 值并進行重試。最終 nextIndex 會在某個位置使得上司人和跟随者的日志達成一緻。當這種情況發生，附加日志 RPC 就會成功，這時就會把跟随者沖突的日志條目全部删除并且加上上司人的日志。一旦附加日志 RPC 成功，那麼跟随者的日志就會和上司人保持一緻，并且在接下來的任期裡一直繼續保持。

如果需要的話，算法可以通過減少被拒絕的附加日志 RPCs 的次數來優化。例如，當附加日志 RPC 的請求被拒絕的時候，跟随者可以包含沖突的條目的任期号和自己存儲的那個任期的最早的索引位址。借助這些資訊，上司人可以減小 nextIndex 越過所有那個任期沖突的所有日志條目；這樣就變成每個任期需要一次附加條目 RPC 而不是每個條目一次。在實踐中，我們十分懷疑這種優化是否是必要的，因為失敗是很少發生的并且也不大可能會有這麼多不一緻的日志。

通過這種機制，上司人在獲得權力的時候就不需要任何特殊的操作來恢複一緻性。他隻需要進行正常的操作，然後日志就能自動的在回複附加日志 RPC 的一緻性檢查失敗的時候自動趨于一緻。上司人從來不會覆寫或者删除自己的日志（圖 3 的上司人隻附加特性）。

日志複制機制展示出了第 2 節中形容的一緻性特性：Raft 能夠接受，複制并應用新的日志條目隻要大部分的機器是工作的；在通常的情況下，新的日志條目可以在一次 RPC 中被複制給叢集中的大多數機器；并且單個的緩慢的跟随者不會影響整體的性能。

5.4 安全性

前面的章節裡描述了 Raft 算法是如何選舉和複制日志的。然而，到目前為止描述的機制并不能充分的保證每一個狀态機會按照相同的順序執行相同的指令。例如，一個跟随者可能會進入不可用狀态同時上司人已經送出了若幹的日志條目，然後這個跟随者可能會被選舉為上司人并且覆寫這些日志條目；是以，不同的狀态機可能會執行不同的指令序列。

這一節通過在上司選舉的時候增加一些限制來完善 Raft 算法。這一限制保證了任何的上司人對于給定的任期号，都擁有了之前任期的所有被送出的日志條目（圖 3 中的上司人完整特性）。增加這一選舉時的限制，我們對于送出時的規則也更加清晰。最終，我們将展示對于上司人完整特性的簡要證明，并且說明上司人是如何上司複制狀态機的做出正确行為的。

5.4.1 選舉限制

在任何基于上司人的一緻性算法中，上司人都必須存儲所有已經送出的日志條目。在某些一緻性算法中，例如 Viewstamped Replication，某個節點即使是一開始并沒有包含所有已經送出的日志條目，它也能被選為上司者。這些算法都包含一些額外的機制來識别丢失的日志條目并把他們傳送給新的上司人，要麼是在選舉階段要麼在之後很快進行。不幸的是，這種方法會導緻相當大的額外的機制和複雜性。Raft 使用了一種更加簡單的方法，它可以保證所有之前的任期号中已經送出的日志條目在選舉的時候都會出現在新的上司人中，不需要傳送這些日志條目給上司人。這意味着日志條目的傳送是單向的，隻從上司人傳給跟随者，并且上司人從不會覆寫自身本地日志中已經存在的條目。

Raft 使用投票的方式來阻止一個候選人赢得選舉除非這個候選人包含了所有已經送出的日志條目。候選人為了赢得選舉必須聯系叢集中的大部分節點，這意味着每一個已經送出的日志條目在這些伺服器節點中肯定存在于至少一個節點上。如果候選人的日志至少和大多數的伺服器節點一樣新（這個新的定義會在下面讨論），那麼他一定持有了所有已經送出的日志條目。請求投票 RPC 實作了這樣的限制： RPC 中包含了候選人的日志資訊，然後投票人會拒絕掉那些日志沒有自己新的投票請求。

Raft 通過比較兩份日志中最後一條日志條目的索引值和任期号定義誰的日志比較新。如果兩份日志最後的條目的任期号不同，那麼任期号大的日志更加新。如果兩份日志最後的條目任期号相同，那麼日志比較長的那個就更加新。

5.4.2 送出之前任期内的日志條目

如同 5.3 節介紹的那樣，上司人知道一條目前任期内的日志記錄是可以被送出的，隻要它被存儲到了大多數的伺服器上。如果一個上司人在送出日志條目之前崩潰了，未來後續的上司人會繼續嘗試複制這條日志記錄。然而，一個上司人不能斷定一個之前任期裡的日志條目被儲存到大多數伺服器上的時候就一定已經送出了。圖 8 展示了一種情況，一條已經被存儲到大多數節點上的老日志條目，也依然有可能會被未來的上司人覆寫掉。

圖 8：如圖的時間序列展示了為什麼上司人無法決定對老任期号的日志條目進行送出。在 (a) 中，S1 是上司者，部分的複制了索引位置 2 的日志條目。在 (b) 中，S1 崩潰了，然後 S5 在任期 3 裡通過 S3、S4 和自己的選票赢得選舉，然後從用戶端接收了一條不一樣的日志條目放在了索引 2 處。然後到 (c)，S5 又崩潰了；S1 重新啟動，選舉成功，開始複制日志。在這時，來自任期 2 的那條日志已經被複制到了叢集中的大多數機器上，但是還沒有被送出。如果 S1 在 (d) 中又崩潰了，S5 可以重新被選舉成功（通過來自 S2，S3 和 S4 的選票），然後覆寫了他們在索引 2 處的日志。反之，如果在崩潰之前，S1 把自己主導的新任期裡産生的日志條目複制到了大多數機器上，就如 (e) 中那樣，那麼在後面任期裡面這些新的日志條目就會被送出（因為S5 就不可能選舉成功）。 這樣在同一時刻就同時保證了，之前的所有老的日志條目就會被送出。

為了消除圖 8 裡描述的情況，Raft 永遠不會通過計算副本數目的方式去送出一個之前任期内的日志條目。隻有上司人目前任期裡的日志條目通過計算副本數目可以被送出；一旦目前任期的日志條目以這種方式被送出，那麼由于日志比對特性，之前的日志條目也都會被間接的送出。在某些情況下，上司人可以安全的知道一個老的日志條目是否已經被送出（例如，該條目是否存儲到所有伺服器上），但是 Raft 為了簡化問題使用一種更加保守的方法。

當上司人複制之前任期裡的日志時，Raft 會為所有日志保留原始的任期号, 這在送出規則上産生了額外的複雜性。在其他的一緻性算法中，如果一個新的上司人要重新複制之前的任期裡的日志時，它必須使用目前新的任期号。Raft 使用的方法更加容易辨識出日志，因為它可以随着時間和日志的變化對日志維護着同一個任期編号。另外，和其他的算法相比，Raft 中的新上司人隻需要發送更少日志條目（其他算法中必須在他們被送出之前發送更多的備援日志條目來為他們重新編号）。

5.4.3 安全性論證

在給定了完整的 Raft 算法之後，我們現在可以更加精确的讨論上司人完整性特性（這一讨論基于 9.2 節的安全性證明）。我們假設上司人完全性特性是不存在的，然後我們推出沖突來。假設任期 T 的上司人（上司人 T）在任期内送出了一條日志條目，但是這條日志條目沒有被存儲到未來某個任期的上司人的日志中。設大于 T 的最小任期 U 的上司人 U 沒有這條日志條目。

圖 9：如果 S1 （任期 T 的上司者）送出了一條新的日志在它的任期裡，然後 S5 在之後的任期 U 裡被選舉為上司人，然後至少會有一個機器，如 S3，既擁有來自 S1 的日志，也給 S5 投票了。

1. 在上司人 U 選舉的時候一定沒有那條被送出的日志條目（上司人從不會删除或者覆寫任何條目）。
2. 上司人 T 複制這條日志條目給叢集中的大多數節點，同時，上司人U 從叢集中的大多數節點赢得了選票。是以，至少有一個節點（投票者、選民）同時接受了來自上司人T 的日志條目，并且給上司人U 投票了，如圖 9。這個投票者是産生這個沖突的關鍵。
3. 這個投票者必須在給上司人 U 投票之前先接受了從上司人 T 發來的已經被送出的日志條目；否則他就會拒絕來自上司人 T 的附加日志請求（因為此時他的任期号會比 T 大）。
4. 投票者在給上司人 U 投票時依然保有這條日志條目，因為任何中間的上司人都包含該日志條目（根據上述的假設），上司人從不會删除條目，并且跟随者隻有和上司人沖突的時候才會删除條目。
5. 投票者把自己選票投給上司人 U 時，上司人 U 的日志必須和投票者自己一樣新。這就導緻了兩者沖突之一。
6. 首先，如果投票者和上司人 U 的最後一條日志的任期号相同，那麼上司人 U 的日志至少和投票者一樣長，是以上司人 U 的日志一定包含所有投票者的日志。這是另一處沖突，因為投票者包含了那條已經被送出的日志條目，但是在上述的假設裡，上司人 U 是不包含的。
7. 除此之外，上司人 U 的最後一條日志的任期号就必須比投票人大了。此外，他也比 T 大，因為投票人的最後一條日志的任期号至少和 T 一樣大（他包含了來自任期 T 的已送出的日志）。建立了上司人 U 最後一條日志的之前上司人一定已經包含了那條被送出的日志（根據上述假設，上司人 U 是第一個不包含該日志條目的上司人）。是以，根據日志比對特性，上司人 U 一定也包含那條被送出當然日志，這裡産生沖突。
8. 這裡完成了沖突。是以，所有比 T 大的上司人一定包含了所有來自 T 的已經被送出的日志。
9. 日志比對原則保證了未來的上司人也同時會包含被間接送出的條目，例如圖 8 (d) 中的索引 2。

通過上司人完全特性，我們就能證明圖 3 中的狀态機安全特性，即如果已經伺服器已經在某個給定的索引值應用了日志條目到自己的狀态機裡，那麼其他的伺服器不會應用一個不一樣的日志到同一個索引值上。在一個伺服器應用一條日志條目到他自己的狀态機中時，他的日志必須和上司人的日志，在該條目和之前的條目上相同，并且已經被送出。現在我們來考慮在任何一個伺服器應用一個指定索引位置的日志的最小任期；日志完全特性保證擁有更高任期号的上司人會存儲相同的日志條目，是以之後的任期裡應用某個索引位置的日志條目也會是相同的值。是以，狀态機安全特性是成立的。

最後，Raft 要求伺服器按照日志中索引位置順序應用日志條目。和狀态機安全特性結合起來看，這就意味着所有的伺服器會應用相同的日志序列集到自己的狀态機中，并且是按照相同的順序。

5.5 跟随者和候選人崩潰

到目前為止，我們都隻關注了上司人崩潰的情況。跟随者和候選人崩潰後的處理方式比上司人要簡單的多，并且他們的處理方式是相同的。如果跟随者或者候選人崩潰了，那麼後續發送給他們的 RPCs 都會失敗。Raft 中處理這種失敗就是簡單的通過無限的重試；如果崩潰的機器重新開機了，那麼這些 RPC 就會完整的成功。如果一個伺服器在完成了一個 RPC，但是還沒有響應的時候崩潰了，那麼在他重新啟動之後就會再次收到同樣的請求。Raft 的 RPCs 都是幂等的，是以這樣重試不會造成任何問題。例如一個跟随者如果收到附加日志請求但是他已經包含了這一日志，那麼他就會直接忽略這個新的請求。

5.6 時間和可用性

Raft 的要求之一就是安全性不能依賴時間：整個系統不能因為某些事件運作的比預期快一點或者慢一點就産生了錯誤的結果。但是，可用性（系統可以及時的響應用戶端）不可避免的要依賴于時間。例如，如果消息交換在伺服器崩潰時花費更多的時間，候選人将不會等待太長的時間來赢得選舉；沒有一個穩定的上司人，Raft 将無法工作。

上司人選舉是 Raft 中對時間要求最為關鍵的方面。Raft 可以選舉并維持一個穩定的上司人,隻要系統滿足下面的時間要求：

廣播時間（broadcastTime） << 選舉逾時時間（electionTimeout） << 平均故障間隔時間（MTBF）

在這個不等式中，廣播時間指的是從一個伺服器并行的發送 RPCs 給叢集中的其他伺服器并接收響應的平均時間；選舉逾時時間就是在 5.2 節中介紹的選舉的逾時時間限制；然後平均故障間隔時間就是對于一台伺服器而言，兩次故障之間的平均時間。廣播時間必須比選舉逾時時間小一個量級，這樣上司人才能夠發送穩定的心跳消息來阻止跟随者開始進入選舉狀态；通過随機化選舉逾時時間的方法，這個不等式也使得選票瓜分的情況變得不可能。選舉逾時時間應該要比平均故障間隔時間小上幾個數量級，這樣整個系統才能穩定的運作。當上司人崩潰後，整個系統會大約相當于選舉逾時的時間裡不可用；我們希望這種情況在整個系統的運作中很少出現。

廣播時間和平均故障間隔時間是由系統決定的，但是選舉逾時時間是我們自己選擇的。Raft 的 RPCs 需要接收方将資訊持久化的儲存到穩定存儲中去，是以廣播時間大約是 0.5 毫秒到 20 毫秒，取決于存儲的技術。是以，選舉逾時時間可能需要在 10 毫秒到 500 毫秒之間。大多數的伺服器的平均故障間隔時間都在幾個月甚至更長，很容易滿足時間的需求。

6 叢集成員變化

到目前為止，我們都假設叢集的配置（加入到一緻性算法的伺服器集合）是固定不變的。但是在實踐中，偶爾是會改變叢集的配置的，例如替換那些當機的機器或者改變複制級别。盡管可以通過暫停整個叢集，更新所有配置，然後重新開機整個叢集的方式來實作，但是在更改的時候叢集會不可用。另外，如果存在手工操作步驟，那麼就會有操作失誤的風險。為了避免這樣的問題，我們決定自動化配置改變并且将其納入到 Raft 一緻性算法中來。

為了讓配置修改機制能夠安全，那麼在轉換的過程中不能夠存在任何時間點使得兩個上司人同時被選舉成功在同一個任期裡。不幸的是，任何伺服器直接從舊的配置直接轉換到新的配置的方案都是不安全的。一次性自動的轉換所有伺服器是不可能的，是以在轉換期間整個叢集存在劃分成兩個獨立的大多數群體的可能性（見圖 10）。

圖 10：直接從一種配置轉到新的配置是十分不安全的，因為各個機器可能在任何的時候進行轉換。在這個例子中，叢集配額從 3 台機器變成了 5 台。不幸的是，存在這樣的一個時間點，兩個不同的上司人在同一個任期裡都可以被選舉成功。一個是通過舊的配置，一個通過新的配置。

為了保證安全性，配置更改必須使用兩階段方法。目前有很多種兩階段的實作。例如，有些系統在第一階段停掉舊的配置是以叢集就不能處理用戶端請求；然後在第二階段在啟用新的配置。在 Raft 中，叢集先切換到一個過渡的配置，我們稱之為共同一緻；一旦共同一緻已經被送出了，那麼系統就切換到新的配置上。共同一緻是老配置和新配置的結合：

• 日志條目被複制給叢集中新、老配置的所有伺服器。
• 新、舊配置的伺服器都可以成為上司人。
• 達成一緻（針對選舉和送出）需要分别在兩種配置上獲得大多數的支援。

共同一緻允許獨立的伺服器在不影響安全性的前提下，在不同的時間進行配置轉換過程。此外，共同一緻可以讓叢集在配置轉換的過程人依然響應伺服器請求。

叢集配置在複制日志中以特殊的日志條目來存儲和通信；圖 11 展示了配置轉換的過程。當一個上司人接收到一個改變配置從 C-old 到 C-new 的請求，他會為了共同一緻存儲配置（圖中的 C-old,new），以前面描述的日志條目和副本的形式。一旦一個伺服器将新的配置日志條目增加到它的日志中，他就會用這個配置來做出未來所有的決定（伺服器總是使用最新的配置，無論他是否已經被送出）。這意味着上司人要使用 C-old,new 的規則來決定日志條目 C-old,new 什麼時候需要被送出。如果上司人崩潰了，被選出來的新上司人可能是使用 C-old 配置也可能是 C-old,new 配置，這取決于赢得選舉的候選人是否已經接收到了 C-old,new 配置。在任何情況下， C-new 配置在這一時期都不會單方面的做出決定。

一旦 C-old,new 被送出，那麼無論是 C-old 還是 C-new，在沒有經過他人準許的情況下都不可能做出決定，并且上司人完全特性保證了隻有擁有 C-old,new 日志條目的伺服器才有可能被選舉為上司人。這個時候，上司人建立一條關于 C-new 配置的日志條目并複制給叢集就是安全的了。再者，每個伺服器在見到新的配置的時候就會立即生效。當新的配置在 C-new 的規則下被送出，舊的配置就變得無關緊要，同時不使用新的配置的伺服器就可以被關閉了。如圖 11，C-old 和 C-new 沒有任何機會同時做出單方面的決定；這保證了安全性。

圖 11：一個配置切換的時間線。虛線表示已經被建立但是還沒有被送出的條目，實線表示最後被送出的日志條目。上司人首先建立了 C-old,new 的配置條目在自己的日志中，并送出到 C-old,new 中（C-old 的大多數和 C-new 的大多數）。然後他建立 C-new 條目并送出到 C-new 中的大多數。這樣就不存在 C-new 和 C-old 可以同時做出決定的時間點。

在關于重新配置還有三個問題需要提出。第一個問題是，新的伺服器可能初始化沒有存儲任何的日志條目。當這些伺服器以這種狀态加入到叢集中，那麼他們需要一段時間來更新追趕，這時還不能送出新的日志條目。為了避免這種可用性的間隔時間，Raft 在配置更新的時候使用了一種額外的階段，在這個階段，新的伺服器以沒有投票權身份加入到叢集中來（上司人複制日志給他們，但是不考慮他們是大多數）。一旦新的伺服器追趕上了叢集中的其他機器，重新配置可以像上面描述的一樣處理。

第二個問題是，叢集的上司人可能不是新配置的一員。在這種情況下，上司人就會在送出了 C-new 日志之後退位（回到跟随者狀态）。這意味着有這樣的一段時間，上司人管理着叢集，但是不包括他自己；他複制日志但是不把他自己算作是大多數之一。當 C-new 被送出時，會發生上司人過渡，因為這時是最早新的配置可以獨立工作的時間點（将總是能夠在 C-new 配置下選出新的上司人）。在此之前，可能隻能從 C-old 中選出上司人。

第三個問題是，移除不在 C-new 中的伺服器可能會擾亂叢集。這些伺服器将不會再接收到心跳，是以當選舉逾時，他們就會進行新的選舉過程。他們會發送擁有新的任期号的請求投票 RPCs，這樣會導緻目前的上司人回退成跟随者狀态。新的上司人最終會被選出來，但是被移除的伺服器将會再次逾時，然後這個過程會再次重複，導緻整體可用性大幅降低。

為了避免這個問題，當伺服器确認目前上司人存在時，伺服器會忽略請求投票 RPCs。特别的，當伺服器在目前最小選舉逾時時間内收到一個請求投票 RPC，他不會更新目前的任期号或者投出選票。這不會影響正常的選舉，每個伺服器在開始一次選舉之前，至少等待一個最小選舉逾時時間。然而，這有利于避免被移除的伺服器擾亂：如果上司人能夠發送心跳給叢集，那麼他就不會被更大的任期号廢黜。

7 日志壓縮

Raft 的日志在正常操作中不斷的增長，但是在實際的系統中，日志不能無限制的增長。随着日志不斷增長，他會占用越來越多的空間，花費越來越多的時間來重置。如果沒有一定的機制去清除日志裡積累的陳舊的資訊，那麼會帶來可用性問題。

快照是最簡單的壓縮方法。在快照系統中，整個系統的狀态都以快照的形式寫入到穩定的持久化存儲中，然後到那個時間點之前的日志全部丢棄。快照技術被使用在 Chubby 和 ZooKeeper 中，接下來的章節會介紹 Raft 中的快照技術。

增量壓縮的方法，例如日志清理或者日志結構合并樹，都是可行的。這些方法每次隻對一小部分資料進行操作，這樣就分散了壓縮的負載壓力。首先，他們先選擇一個已經積累的大量已經被删除或者被覆寫對象的區域，然後重寫那個區域還活躍的對象，之後釋放那個區域。和簡單操作整個資料集合的快照相比，需要增加複雜的機制來實作。狀态機可以實作 LSM tree 使用和快照相同的接口，但是日志清除方法就需要修改 Raft 了。

圖 12：一個伺服器用新的快照替換了從 1 到 5 的條目，快照值存儲了目前的狀态。快照中包含了最後的索引位置和任期号。

圖 12 展示了 Raft 中快照的基礎思想。每個伺服器獨立的建立快照，隻包括已經被送出的日志。主要的工作包括将狀态機的狀态寫入到快照中。Raft 也包含一些少量的中繼資料到快照中：最後被包含索引指的是被快照取代的最後的條目在日志中的索引值（狀态機最後應用的日志），最後被包含的任期指的是該條目的任期号。保留這些資料是為了支援快照前的第一個條目的附加日志請求時的一緻性檢查，因為這個條目需要最後的索引值和任期号。為了支援叢集成員更新（第 6 節），快照中也将最後的一次配置作為最後一個條目存下來。一旦伺服器完成一次快照，他就可以删除最後索引位置之前的所有日志和快照了。

盡管通常伺服器都是獨立的建立快照，但是上司人必須偶爾的發送快照給一些落後的跟随者。這通常發生在當上司人已經丢棄了下一條需要發送給跟随者的日志條目的時候。幸運的是這種情況不是正常操作：一個與上司人保持同步的跟随者通常都會有這個條目。然而一個運作非常緩慢的跟随者或者新加入叢集的伺服器（第 6 節）将不會有這個條目。這時讓這個跟随者更新到最新的狀态的方式就是通過網絡把快照發送給他們。

安裝快照 RPC：

在上司人發送快照給跟随者時使用到。上司人總是按順序發送。

參數	解釋
term	上司人的任期号
leaderId	上司人的 Id，以便于跟随者重定向請求
lastIncludedIndex	快照中包含的最後日志條目的索引值
lastIncludedTerm	快照中包含的最後日志條目的任期号
offset	分塊在快照中的偏移量
data[]	原始資料
done	如果這是最後一個分塊則為 true

結果	解釋
term	目前任期号，便于上司人更新自己

接收者實作：

1. 如果

   term < currentTerm

   就立即回複
2. 如果是第一個分塊（offset 為 0）就建立一個新的快照
3. 在指定偏移量寫入資料
4. 如果 done 是 false，則繼續等待更多的資料
5. 儲存快照檔案，丢棄索引值小于快照的日志
6. 如果現存的日志擁有相同的最後任期号和索引值，則後面的資料繼續保持
7. 丢棄整個日志
8. 使用快照重置狀态機

圖 13：一個關于安裝快照的簡要概述。為了便于傳輸，快照都是被分成分塊的；每個分塊都給了跟随者生命的迹象，是以跟随者可以重置選舉逾時計時器。

在這種情況下上司人使用一種叫做安裝快照的新的 RPC 來發送快照給太落後的跟随者；見圖 13。當跟随者通過這種 RPC 接收到快照時，他必須自己決定對于已經存在的日志該如何處理。通常快照會包含沒有在接收者日志中存在的資訊。在這種情況下，跟随者直接丢棄他所有的日志；這些會被快照所取代，但是可能會和沒有送出的日志産生沖突。如果接收到的快照是自己日志的前面部分（由于網絡重傳或者錯誤），那麼被快照包含的條目将會被全部删除，但是快照之後的條目必須正确和保留。

這種快照的方式背離了 Raft 的強上司人原則，因為跟随者可以在不知道上司人情況下建立快照。但是我們認為這種背離是值得的。上司人的存在，是為了解決在達成一緻性的時候的沖突，但是在建立快照的時候，一緻性已經達成，這時不存在沖突了，是以沒有上司人也是可以的。資料依然是從上司人傳給跟随者，隻是跟随者可以重新組織他們的資料了。

我們考慮過一種替代的基于上司人的快照方案，即隻有上司人建立快照，然後發送給所有的跟随者。但是這樣做有兩個缺點。第一，發送快照會浪費網絡帶寬并且延緩了快照處理的時間。每個跟随者都已經擁有了所有産生快照需要的資訊，而且很顯然，自己從本地的狀态中建立快照比通過網絡接收别人發來的要經濟。第二，上司人的實作會更加複雜。例如，上司人需要發送快照的同時并行的将新的日志條目發送給跟随者，這樣才不會阻塞新的用戶端請求。

還有兩個問題影響了快照的性能。首先，伺服器必須決定什麼時候應該建立快照。如果快照建立的過于頻繁，那麼就會浪費大量的磁盤帶寬和其他資源；如果建立快照頻率太低，他就要承受耗盡存儲容量的風險，同時也增加了從日志重建的時間。一個簡單的政策就是當日志大小達到一個固定大小的時候就建立一次快照。如果這個門檻值設定的顯著大于期望的快照的大小，那麼快照對磁盤壓力的影響就會很小了。

第二個影響性能的問題就是寫入快照需要花費顯著的一段時間，并且我們還不希望影響到正常操作。解決方案是通過寫時複制的技術，這樣新的更新就可以被接收而不影響到快照。例如，具有函數式資料結構的狀态機天然支援這樣的功能。另外，作業系統的寫時複制技術的支援（如 Linux 上的 fork）可以被用來建立完整的狀态機的記憶體快照（我們的實作就是這樣的）。

8 用戶端互動

這一節将介紹用戶端是如何和 Raft 進行互動的，包括用戶端如何發現上司人和 Raft 是如何支援線性化語義的。這些問題對于所有基于一緻性的系統都存在，并且 Raft 的解決方案和其他的也差不多。

Raft 中的用戶端發送所有請求給上司人。當用戶端啟動的時候，他會随機挑選一個伺服器進行通信。如果用戶端第一次挑選的伺服器不是上司人，那麼那個伺服器會拒絕用戶端的請求并且提供他最近接收到的上司人的資訊（附加條目請求包含了上司人的網絡位址）。如果上司人已經崩潰了，那麼用戶端的請求就會逾時；用戶端之後會再次重試随機挑選伺服器的過程。

我們 Raft 的目标是要實作線性化語義（每一次操作立即執行，隻執行一次，在他調用和收到回複之間）。但是，如上述，Raft 是可以執行同一條指令多次的：例如，如果上司人在送出了這條日志之後，但是在響應用戶端之前崩潰了，那麼用戶端會和新的上司人重試這條指令，導緻這條指令就被再次執行了。解決方案就是用戶端對于每一條指令都賦予一個唯一的序列号。然後，狀态機跟蹤每條指令最新的序列号和相應的響應。如果接收到一條指令，它的序列号已經被執行了，那麼就立即傳回結果，而不重新執行指令。

隻讀的操作可以直接處理而不需要記錄日志。但是，在不增加任何限制的情況下，這麼做可能會冒着傳回髒資料的風險，因為上司人響應用戶端請求時可能已經被新的上司人廢棄了，但是他還不知道。線性化的讀操作必須不能傳回髒資料，Raft 需要使用兩個額外的措施在不使用日志的情況下保證這一點。首先，上司人必須有關于被送出日志的最新資訊。上司人完全特性保證了上司人一定擁有所有已經被送出的日志條目，但是在他任期開始的時候，他可能不知道那些是已經被送出的。為了知道這些資訊，他需要在他的任期裡送出一條日志條目。Raft 中通過上司人在任期開始的時候送出一個空白的沒有任何操作的日志條目到日志中去來實作。第二，上司人在處理隻讀的請求之前必須檢查自己是否已經被廢黜了（他自己的資訊已經變髒了如果一個更新的上司人被選舉出來）。Raft 中通過讓上司人在響應隻讀請求之前，先和叢集中的大多數節點交換一次心跳資訊來處理這個問題。可選的，上司人可以依賴心跳機制來實作一種租約的機制，但是這種方法依賴時間來保證安全性（假設時間誤差是有界的）。

9 算法實作和評估

我們已經為 RAMCloud 實作了 Raft 算法作為存儲配置資訊的複制狀态機的一部分，并且幫助 RAMCloud 協調故障轉移。這個 Raft 實作包含大約 2000 行 C++ 代碼，其中不包括測試、注釋和空行。這些代碼是開源的。同時也有大約 25 個其他獨立的第三方的基于這篇論文草稿的開源實作，針對不同的開發場景。同時，很多公司已經部署了基于 Raft 的系統。

這一節會從三個方面來評估 Raft 算法：可了解性、正确性和性能。

9.1 可了解性

為了和 Paxos 比較 Raft 算法的可了解能力，我們針對高層次的大學生和研究所學生，在斯坦福大學的進階作業系統課程和加州大學伯克利分校的分布式計算課程上，進行了一次學習的實驗。我們分别拍了針對 Raft 和 Paxos 的視訊課程，并準備了相應的小測驗。Raft 的視訊講課覆寫了這篇論文的所有内容除了日志壓縮；Paxos 講課包含了足夠的資料來建立一個等價的複制狀态機，包括單決策 Paxos，多決策 Paxos，重新配置和一些實際系統需要的性能優化（例如上司人選舉）。小測驗測試一些對算法的基本了解和解釋一些邊角的示例。每個學生都是看完第一個視訊，回答相應的測試，再看第二個視訊，回答相應的測試。大約有一半的學生先進行 Paxos 部分，然後另一半先進行 Raft 部分，這是為了說明兩者獨立的差別從第一個算法處學來的經驗。我們計算參加人員的每一個小測驗的得分來看參與者是否在 Raft 算法上更加容易了解。

我們盡可能的使得 Paxos 和 Raft 的比較更加公平。這個實驗偏愛 Paxos 表現在兩個方面：43 個參加者中有 15 個人在之前有一些 Paxos 的經驗，并且 Paxos 的視訊要長 14%。如表格 1 總結的那樣，我們采取了一些措施來減輕這種潛在的偏見。我們所有的材料都可供審查。

關心	緩和偏見采取的手段	可供檢視的材料
相同的講課品質	兩者使用同一個講師。Paxos 使用的是現在很多大學裡經常使用的。Paxos 會長 14%。	視訊
相同的測驗難度	問題以難度分組，在兩個測驗裡成對出現。	小測驗
公平評分	使用紅字标題。随機順序打分，兩個測驗交替進行。	紅字标題

表 1：考慮到可能會存在的偏見，對于每種情況的解決方法，和相應的材料。

參加者平均在 Raft 的測驗中比 Paxos 高 4.9 分（總分 60，那麼 Raft 的平均得分是 25.7，而 Paxos 是 20.8）；圖 14 展示了每個參與者的得分。一對 t -測試表明，擁有 95% 的可信度，真實的 Raft 分數分布至少比 Paxos 高 2.5 分。

圖 14：一個散點圖表示了 43 個學生在 Paxos 和 Raft 的小測驗中的成績。在對角線之上的點表示在 Raft 獲得了更高分數的學生。

我們也建立了一個線性回歸模型來預測一個新的學生的測驗成績，基于以下三個因素：他們使用的是哪個小測驗，之前對 Paxos 的經驗，和學習算法的順序。模型顯示，對小測驗的選擇會産生 12.5 分的差别在對 Raft 的好感度上。這顯著的高于之前的 4.9 分，因為很多學生在之前都已經有了對于 Paxos 的經驗，這相當明顯的幫助 Paxos，對 Raft 就沒什麼太大影響了。但是奇怪的是，模型預測對于先進性 Paxos 小測驗的人而言，Raft 的小測驗得分會比 Paxos 低 6.3 分；我們不知道為什麼，但這在統計學上是這樣的。

我們同時也在測驗之後調查了參與者，他們認為哪個算法更加容易實作和解釋；這個的結果在圖 15 上。壓倒性的結果表明 Raft 算法更加容易實作和解釋（41 人中的 33個）。但是，這種自己報告的結果不如參與者的成績更加可信，并且參與者可能因為我們的 Raft 更加易于了解的假說而産生偏見。

圖 15：通過一個 5 分制的問題，參與者（左邊）被問哪個算法他們覺得在一個高效正确的系統裡更容易實作，右邊被問哪個更容易向學生解釋。

關于 Raft 使用者學習有一個更加詳細的讨論。

9.2 正确性

在第 5 節，我們已經進行了一個正式的說明，和對一緻性機制的安全性證明。這個正式說明讓圖 2 中的資訊非常清晰通過 TLA+ 說明語言。大約 400 行說明充當了證明的主題。同時對于任何想實作的人也是十分有用的。我們非常機械的證明了日志完全特性通過 TLA 證明系統。然而，這個證明依賴的限制前提還沒有被機械證明（例如，我們還沒有證明這個說明中的類型安全）。而且，我們已經寫了一個非正式的證明關于狀态機安全性質是完備的，并且是相當清晰的（大約 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。我們選擇使用共同一緻的方法因為他對一緻性協定的其他部分影響很小，這樣我們隻需要很少的一些機制就可以實作成員變換。Lamport 的基于 α 的方法之是以沒有被 Raft 選擇是因為它假設在沒有上司人的情況下也可以達到一緻性。和 VR 和 SMART 相比較，Raft 的重新配置算法可以在不限制正常請求處理的情況下進行；相比較的，VR 需要停止所有的處理過程，SMART 引入了一個和 α 類似的方法，限制了請求處理的數量。Raft 的方法同時也需要更少的額外機制來實作，和 VR、SMART 比較而言。

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 公司，斯坦福的畢業團體支援。

轉載位址

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md