目錄
1 介紹... 3
2 複制狀态機... 4
3 Raft算法産生的背景... 6
4 為了可了解性的設計... 7
5 Raft設計原理... 8
5.1 Raft基礎... 9
5.2 上司人選舉... 11
5.3 日志複制... 12
5.4 安全性... 16
5.4.1 選舉限制.... 17
5.4.2 送出之前任期内的日志條目.... 17
5.4.3 安全性論證.... 19
5.5 跟随者和候選人崩潰... 21
5.6 時間和可用性... 21
6 叢集成員變化... 22
7 日志壓縮... 26
8 Hyperledger Fabric為何選擇Raft 27
8.1 Raft排序和kafka排序的對比... 27
1 介紹
Raft算法是一種為了管理複制日志的一緻性算法。它提供了和Paxos算法相同的功能和性能，但是它的算法結構和Paxos不同，使得Raft算法更加容易了解并且更容易建構實際的系統。為了提升可了解性，Raft将一緻性算法分解成了幾個關鍵子產品，例如上司人選舉、日志複制和安全性。同時它通過實施一個更強的一緻性來減少需要考慮的狀态的數量。Raft算法比Paxos 算法更加容易學習。Raft 算法還包括一個新的機制來允許叢集成員的動态改變，它利用重疊的大多數來保證安全性。
一緻性算法就是允許一組機器像一個整體一樣工作，即使其中一些機器出現故障也能夠繼續工作下去。其中，Paxos算法統治着一緻性算法這一領域：絕大多數的實作都是基于 Paxos 或者受其影響。
但不幸的是，盡管有很多工作都在嘗試降低它的複雜性，但是 Paxos 算法依然十分難以了解。并且，Paxos 自身的算法結構需要進行大幅的修改才能夠應用到實際的系統中。
對Paxos算法進行深入研究之後，我們開始尋找一種新的一緻性算法，可以為建構實際的系統提供更好的基礎，于是Raft一緻性算法應運而生。
Raft一緻性算法就是其中一個比較優異的選擇，Raft是一種為了管理複制日志的一緻性算法。它提供了和Paxos算法相同的功能和性能，但是它的算法結構和Paxos不同，使得Raft算法更加容易了解并且更容易建構實際的系統。為了提升可了解性，Raft将一緻性算法分解成了幾個關鍵子產品，例如上司人選舉、日志複制和安全性。同時它通過實施一個更強的一緻性來減少需要考慮的狀态的數量。從一個使用者研究的結果可以證明，對于學生而言，Raft算法比Paxos算法更加容易學習。Raft算法還包括一個新的機制來允許叢集成員的動态改變，它利用重疊的大多數來保證安全性。在設計Raft算法的時候，使用一些特别的技巧來提升它的可了解性，包括算法分解（Raft 主要被分成了上司人選舉，日志複制和安全三個子產品）和減少狀态機的狀态（相對于Paxos，Raft減少了非确定性和伺服器互相處于非一緻性的方式）。
Raft算法在許多方面和現有的一緻性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是它也有一些獨特的特性：
- 強上司者：和其他一緻性算法相比，Raft使用一種更強的上司能力形式。比如，日志條目隻從上司者發送給其他的伺服器。這種方式簡化了對複制日志的管理并且使得Raft算法更加易于了解。
- 上司選舉：Raft算法使用一個随機計時器來選舉上司者。這種方式隻是在任何一緻性算法都必須實作的心跳機制上增加了一點機制。在解決沖突的時候會更加簡單快捷。
- 成員關系調整：Raft使用一種共同一緻的方法來處理叢集成員變換的問題，在這種方法下，處于調整過程中的兩種不同的配置叢集中大多數機器會有重疊，這就使得叢集在成員變換的時候依然可以繼續工作。
Raft算法不論是作為實踐項目的基礎都是要比Paxos 或者其他一緻性算法要優異的。它比其他算法更加簡單，更加容易了解；它的算法描述足以實作一個現實的系統；它有好多開源的實作并且在很多公司裡使用；它的安全性已經被證明；它的效率和其他算法比起來也不相上下。
2 複制狀态機
一緻性算法是從複制狀态機的背景下提出的。在這種方法中，一組伺服器上的狀态機産生相同狀态的副本，并且在一些機器宕掉的情況下也可以繼續運作。複制狀态機在分布式系統中被用于解決很多容錯的問題。例如，大規模的系統中通常都有一個叢集上司者，像 GFS、HDFS 和 RAMCloud，典型應用就是一個獨立的的複制狀态機去管理上司選舉和存儲配置資訊并且在上司人當機的情況下也要存活下來。比如 Chubby 和 ZooKeeper。
複制狀态機的結構：一緻性算法管理着來自用戶端指令的複制日志。狀态機從日志中處理相同順序的相同指令，是以産生的結果也是相同的。如下圖1：
圖1
複制狀态機通常都是基于複制日志實作的。每一個伺服器存儲一個包含一系列指令的日志，并且按照日志的順序進行執行。每一個日志都按照相同的順序包含相同的指令，是以每一個伺服器都執行相同的指令序列。因為每個狀态機都是确定的，每一次執行操作都産生相同的狀态和同樣的序列。
保證複制日志相同就是一緻性算法的工作了。在一台伺服器上，一緻性子產品接收用戶端發送來的指令然後增加到自己的日志中去。它和其他伺服器上的一緻性子產品進行通信來保證每一個伺服器上的日志最終都以相同的順序包含相同的請求，盡管有些伺服器會當機。一旦指令被正确的複制，每一個伺服器的狀态機按照日志順序處理他們，然後輸出結果被傳回給用戶端。是以，伺服器叢集看起來形成一個高可靠的狀态機。
實際系統中使用的一緻性算法通常含有以下特性：
- 安全性保證（絕對不會傳回一個錯誤的結果）：在非拜占庭錯誤情況下，包括網絡延遲、分區、丢包、備援和亂序等錯誤都可以保證正确。
- 可用性：叢集中隻要有大多數的機器可運作并且能夠互相通信、和用戶端通信，就可以保證可用。是以，一個典型的包含5個節點的叢集可以容忍兩個節點的失敗。伺服器被停止就認為是失敗。他們當有穩定的存儲的時候可以從狀态中恢複回來并重新加入叢集。
- 不依賴時序來保證一緻性：實體時鐘錯誤或者極端的消息延遲隻有在最壞情況下才會導緻可用性問題。
- 通常情況下，一條指令可以盡可能快的在叢集中大多數節點響應一輪遠端過程調用時完成。小部分比較慢的節點不會影響系統整體的性能。
3 Raft算法産生的背景
在過去的 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算法通過選舉一個高貴的上司人，然後給予他全部的管理複制日志的責任來實作一緻性。上司人從用戶端接收日志條目，把日志條目複制到其他伺服器上，并且當保證安全性的時候告訴其他的伺服器應用日志條目到他們的狀态機中。擁有一個上司人大大簡化了對複制日志的管理。例如，上司人可以決定新的日志條目需要放在日志中的什麼位置而不需要和其他伺服器商議，并且資料都從上司人流向其他伺服器。一個上司人可以當機，可以和其他伺服器失去連接配接，這時一個新的上司人會被選舉出來。
通過上司人的方式，Raft 将一緻性問題分解成了三個相對獨立的子問題，這些問題會在接下來的子章節中進行讨論：
- 上司選舉：一個新的上司人需要被選舉出來，當現存的上司人當機的時候。
- 日志複制：上司人必須從用戶端接收日志然後複制到叢集中的其他節點，并且強制要求其他節點的日志保持和自己相同。
- 安全性：在 Raft 中安全性的關鍵是狀态機安全：如果有任何的伺服器節點已經應用了一個确定的日志條目到它的狀态機中，那麼其他伺服器節點不能在同一個日志索引位置應用一個不同的指令。
5.1 Raft基礎
一個Raft叢集包含若幹個伺服器節點；通常是5個，這允許整個系統容忍 2 個節點的失效。在任何時刻，每一個伺服器節點都處于這三個狀态之一：上司人、跟随者或者候選人。在通常情況下，系統中隻有一個上司人并且其他的節點全部都是跟随者。跟随者都是被動的：他們不會發送任何請求，隻是簡單的響應來自上司者或者候選人的請求。上司人處理所有的用戶端請求（如果一個用戶端和跟随者聯系，那麼跟随者會把請求重定向給上司人）。第三種狀态，候選人，是用來選舉新上司人時使用。
圖 2
圖2：伺服器狀态。跟随者隻響應來自其他伺服器的請求。如果跟随者接收不到消息，那麼他就會變成候選人并發起一次選舉。獲得叢集中大多數選票的候選人将成為上司者。在一個任期内，上司人一直都會是上司人直到自己當機了。
圖3
圖 3：時間被劃分成一個個的任期，每個任期開始都是一次選舉。在選舉成功後，上司人會管理整個叢集直到任期結束。有時候選舉會失敗，那麼這個任期就會沒有上司人而結束。任期之間的切換可以在不同的時間不同的伺服器上觀察到。
Raft把時間分割成任意長度的任期，如圖3。任期用連續的整數标記。每一段任期從一次選舉開始，一個或者多個候選人嘗試成為上司者。如果一個候選人赢得選舉，然後他就在接下來的任期内充當上司人的職責。在某些情況下，一次選舉過程會造成選票的瓜分。在這種情況下，這一任期會以沒有上司人結束；一個新的任期（和一次新的選舉）會很快重新開始。Raft保證了在一個給定的任期内，最多隻有一個上司者。
不同的伺服器節點可能多次觀察到任期之間的轉換，但在某些情況下，一個節點也可能觀察不到任何一次選舉或者整個任期全程。任期在Raft算法中充當邏輯時鐘的作用，這會允許伺服器節點查明一些過期的資訊比如陳舊的上司者。每一個節點存儲一個目前任期号，這一編号在整個時期内單調的增長。當伺服器之間通信的時候會交換目前任期号；如果一個伺服器的目前任期号比其他人小，那麼他會更新自己的編号到較大的編号值。如果一個候選人或者上司者發現自己的任期号過期了，那麼他會立即恢複成跟随者狀态。如果一個節點接收到一個包含過期的任期号的請求，那麼他會直接拒絕這個請求。
Raft算法中伺服器節點之間通信使用遠端過程調用（RPCs），并且基本的一緻性算法隻需要兩種類型的 RPCs。請求投票（RequestVote） RPCs 由候選人在選舉期間發起，然後附加條目（AppendEntries）RPCs 由上司人發起，用來複制日志和提供一種心跳機制。當伺服器沒有及時的收到 RPC 的響應時，會進行重試，并且他們能夠并行的發起 RPCs 來獲得最佳的性能。
5.2 上司人選舉
Raft使用一種心跳機制來觸發上司人選舉。當伺服器程式啟動時，他們都是跟随者身份。一個伺服器節點繼續保持着跟随者狀态隻要他從上司人或者候選者處接收到有效的 RPCs。上司者周期性的向所有跟随者發送心跳包（即不包含日志項内容的附加日志項 RPCs）來維持自己的權威。如果一個跟随者在一段時間裡沒有接收到任何消息，也就是選舉逾時，那麼他就會認為系統中沒有可用的上司者,并且發起選舉以選出新的上司者。
要開始一次選舉過程，跟随者先要增加自己的目前任期号并且轉換到候選人狀态。然後他會并行的向叢集中的其他伺服器節點發送請求投票的 RPCs 來給自己投票。候選人會繼續保持着目前狀态直到以下三件事情之一發生：
(a) 他自己赢得了這次的選舉；
(b) 其他的伺服器成為上司者；
(c) 一段時間之後沒有任何一個獲勝的人。
當一個候選人從整個叢集的大多數伺服器節點獲得了針對同一個任期号的選票，那麼他就赢得了這次選舉并成為上司人。每一個伺服器最多會對一個任期号投出一張選票，按照先來先服務的原則。要求大多數選票的規則確定了最多隻會有一個候選人赢得此次選舉。一旦候選人赢得選舉，他就立即成為上司人。然後他會向其他的伺服器發送心跳消息來建立自己的權威并且阻止新的上司人的産生。
在等待投票的時候，候選人可能會從其他的伺服器接收到聲明它是上司人的附加日志項 RPC。如果這個上司人的任期号（包含在此次的 RPC中）不小于候選人目前的任期号，那麼候選人會承認上司人合法并回到跟随者狀态。 如果此次 RPC 中的任期号比自己小，那麼候選人就會拒絕這次的 RPC 并且繼續保持候選人狀态。
第三種事情的結果是候選人既沒有赢得選舉也沒有輸：如果有多個跟随者同時成為候選人，那麼選票可能會被瓜分以至于沒有候選人可以赢得大多數人的支援。當這種情況發生的時候，每一個候選人都會逾時，然後通過增加目前任期号來開始一輪新的選舉。然而，沒有其他機制的話，選票可能會被無限的重複瓜分。
Raft算法使用随機選舉逾時時間的方法來確定很少會發生選票瓜分的情況，就算發生也能很快的解決。為了阻止選票起初就被瓜分，選舉逾時時間是從一個固定的區間（例如 150-300 毫秒）随機選擇。這樣可以把伺服器都分散開以至于在大多數情況下隻有一個伺服器會選舉逾時；然後他赢得選舉并在其他伺服器逾時之前發送心跳包。同樣的機制被用在選票瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個随機的選舉逾時時間，然後在逾時時間内等待投票的結果；這樣減少了在新的選舉中另外的選票瓜分的可能性。
上司人選舉這個例子，展現了可了解性原則是如何指導我們進行方案設計的。起初我們計劃使用一種排名系統：每一個候選人都被賦予一個唯一的排名，供候選人之間競争時進行選擇。如果一個候選人發現另一個候選人擁有更高的排名，那麼他就會回到跟随者狀态，這樣高排名的候選人能夠更加容易的赢得下一次選舉。但是我們發現這種方法在可用性方面會有一點問題（如果高排名的伺服器當機了，那麼低排名的伺服器可能會逾時并再次進入候選人狀态。而且如果這個行為發生得足夠快，則可能會導緻整個選舉過程都被重置掉）。我們針對算法進行了多次調整，但是每次調整之後都會有新的問題。最終我們認為随機重試的方法是更加明顯和易于了解的。
5.3 日志複制
一旦一個上司人被選舉出來，他就開始為用戶端提供服務。用戶端的每一個請求都包含一條被複制狀态機執行的指令。上司人把這條指令作為一條新的日志條目附加到日志中去，然後并行的發起附加條目 RPCs 給其他的伺服器，讓他們複制這條日志條目。當這條日志條目被安全的複制（下面會介紹），上司人會應用這條日志條目到它的狀态機中然後把執行的結果傳回給用戶端。如果跟随者崩潰或者運作緩慢，再或者網絡丢包，上司人會不斷的重複嘗試附加日志條目 RPCs （盡管已經回複了用戶端）直到所有的跟随者都最終存儲了所有的日志條目。
圖4
圖 4：日志由有序序号标記的條目組成。每個條目都包含建立時的任期号（圖中框中的數字），和一個狀态機需要執行的指令。一個條目當可以安全的被應用到狀态機中去的時候，就認為是可以送出了。
日志以圖 4 展示的方式組織。每一個日志條目存儲一條狀态機指令和從上司人收到這條指令時的任期号。日志中的任期号用來檢查是否出現不一緻的情況。每一條日志條目同時也都有一個整數索引值來表明它在日志中的位置。
上司人來決定什麼時候把日志條目應用到狀态機中是安全的；這種日志條目被稱為已送出。Raft 算法保證所有已送出的日志條目都是持久化的并且最終會被所有可用的狀态機執行。在上司人将建立的日志條目複制到大多數的伺服器上的時候，日志條目就會被送出。同時，上司人的日志中之前的所有日志條目也都會被送出，包括由其他上司人建立的條目，同時他也展示了這種送出的定義是安全的。上司人跟蹤了最大的将會被送出的日志項的索引，并且索引值會被包含在未來的所有附加日志 RPCs （包括心跳包），這樣其他的伺服器才能最終知道上司人的送出位置。一旦跟随者知道一條日志條目已經被送出，那麼他也會将這個日志條目應用到本地的狀态機中（按照日志的順序）。
我們設計了 Raft 的日志機制來維護一個不同伺服器的日志之間的高層次的一緻性。這麼做不僅簡化了系統的行為也使得更加可預計，同時他也是安全性保證的一個重要元件。Raft 維護着以下的特性：
- 如果在不同的日志中的兩個條目擁有相同的索引和任期号，那麼他們存儲了相同的指令。
- 如果在不同的日志中的兩個條目擁有相同的索引和任期号，那麼他們之前的所有日志條目也全部相同。
第一個特性來自這樣的一個事實，上司人最多在一個任期裡在指定的一個日志索引位置建立一條日志條目，同時日志條目在日志中的位置也從來不會改變。第二個特性由附加日志 RPC 的一個簡單的一緻性檢查所保證。在發送附加日志 RPC 的時候，上司人會把新的日志條目緊接着之前的條目的索引位置和任期号包含在裡面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的條目，那麼他就會拒絕接收新的日志條目。一緻性檢查就像一個歸納步驟：一開始空的日志狀态肯定是滿足日志比對特性的，然後一緻性檢查保護了日志比對特性當日志擴充的時候。是以，每當附加日志 RPC 傳回成功時，上司人就知道跟随者的日志一定是和自己相同的了。
在正常的操作中，上司人和跟随者的日志保持一緻性，是以附加日志 RPC 的一緻性檢查從來不會失敗。然而，上司人崩潰的情況會使得日志處于不一緻的狀态（老的上司人可能還沒有完全複制所有的日志條目）。這種不一緻問題會在上司人和跟随者的一系列崩潰下加劇。圖 7 展示了跟随者的日志可能和新的上司人不同的方式。跟随者可能會丢失一些在新的上司人中有的日志條目，他也可能擁有一些上司人沒有的日志條目，或者兩者都發生。丢失或者多出日志條目可能會持續多個任期。
圖5
圖 5：當一個上司人成功當選時，跟随者可能是任何情況（a-f）。每一個盒子表示是一個日志條目；裡面的數字表示任期号。跟随者可能會缺少一些日志條目（a-b），可能會有一些未被送出的日志條目（c-d），或者兩種情況都存在（e-f）。例如，場景 f 可能會這樣發生，某伺服器在任期 2 的時候是上司人，已附加了一些日志條目到自己的日志中，但在送出之前就崩潰了；很快這個機器就被重新開機了，在任期 3 重新被選為上司人，并且又增加了一些日志條目到自己的日志中；在任期 2 和任期 3 的日志被送出之前，這個伺服器又當機了，并且在接下來的幾個任期裡一直處于當機狀态。
在 Raft 算法中，上司人處理不一緻是通過強制跟随者直接複制自己的日志來解決了。這意味着在跟随者中的沖突的日志條目會被上司人的日志覆寫。
要使得跟随者的日志進入和自己一緻的狀态，上司人必須找到最後兩者達成一緻的地方，然後删除從那個點之後的所有日志條目，發送自己的日志給跟随者。所有的這些操作都在進行附加日志 RPCs 的一緻性檢查時完成。上司人針對每一個跟随者維護了一個 nextIndex，這表示下一個需要發送給跟随者的日志條目的索引位址。當一個上司人剛獲得權力的時候，他初始化所有nextIndex 值為自己的最後一條日志的index加1。如果一個跟随者的日志和上司人不一緻，那麼在下一次的附加日志 RPC 時的一緻性檢查就會失敗。在被跟随者拒絕之後，上司人就會減小 nextIndex 值并進行重試。最終 nextIndex 會在某個位置使得上司人和跟随者的日志達成一緻。當這種情況發生，附加日志 RPC 就會成功，這時就會把跟随者沖突的日志條目全部删除并且加上上司人的日志。一旦附加日志 RPC 成功，那麼跟随者的日志就會和上司人保持一緻，并且在接下來的任期裡一直繼續保持。
如果需要的話，算法可以通過減少被拒絕的附加日志 RPCs 的次數來優化。例如，當附加日志 RPC 的請求被拒絕的時候，跟随者可以包含沖突的條目的任期号和自己存儲的那個任期的最早的索引位址。借助這些資訊，上司人可以減小 nextIndex 越過所有那個任期沖突的所有日志條目；這樣就變成每個任期需要一次附加條目 RPC 而不是每個條目一次。在實踐中，我們十分懷疑這種優化是否是必要的，因為失敗是很少發生的并且也不大可能會有這麼多不一緻的日志。
通過這種機制，上司人在獲得權力的時候就不需要任何特殊的操作來恢複一緻性。他隻需要進行正常的操作，然後日志就能自動的在回複附加日志 RPC 的一緻性檢查失敗的時候自動趨于一緻。上司人從來不會覆寫或者删除自己的日志。
日志複制機制展示出了Raft算法的一緻性特性：Raft 能夠接受，複制并應用新的日志條目隻要大部分的機器是工作的；在通常的情況下，新的日志條目可以在一次 RPC 中被複制給叢集中的大多數機器；并且單個的緩慢的跟随者不會影響整體的性能。
5.4 安全性
前面的章節裡描述了 Raft 算法是如何選舉和複制日志的。然而，到目前為止描述的機制并不能充分的保證每一個狀态機會按照相同的順序執行相同的指令。例如，一個跟随者可能會進入不可用狀态同時上司人已經送出了若幹的日志條目，然後這個跟随者可能會被選舉為上司人并且覆寫這些日志條目；是以，不同的狀态機可能會執行不同的指令序列。
這一節通過在上司選舉的時候增加一些限制來完善 Raft 算法。這一限制保證了任何的上司人對于給定的任期号，都擁有了之前任期的所有被送出的日志條目。增加這一選舉時的限制，我們對于送出時的規則也更加清晰。最終，我們将展示對于上司人完整特性的簡要證明，并且說明上司人是如何上司複制狀态機的做出正确行為的。
5.4.1 選舉限制
在任何基于上司人的一緻性算法中，上司人都必須存儲所有已經送出的日志條目。在某些一緻性算法中，例如 Viewstamped Replication，某個節點即使是一開始并沒有包含所有已經送出的日志條目，它也能被選為上司者。這些算法都包含一些額外的機制來識别丢失的日志條目并把他們傳送給新的上司人，要麼是在選舉階段要麼在之後很快進行。不幸的是，這種方法會導緻相當大的額外的機制和複雜性。Raft 使用了一種更加簡單的方法，它可以保證所有之前的任期号中已經送出的日志條目在選舉的時候都會出現在新的上司人中，不需要傳送這些日志條目給上司人。這意味着日志條目的傳送是單向的，隻從上司人傳給跟随者，并且上司人從不會覆寫自身本地日志中已經存在的條目。
Raft 使用投票的方式來阻止一個候選人赢得選舉除非這個候選人包含了所有已經送出的日志條目。候選人為了赢得選舉必須聯系叢集中的大部分節點，這意味着每一個已經送出的日志條目在這些伺服器節點中肯定存在于至少一個節點上。如果候選人的日志至少和大多數的伺服器節點一樣新（這個新的定義會在下面讨論），那麼他一定持有了所有已經送出的日志條目。請求投票 RPC 實作了這樣的限制： RPC 中包含了候選人的日志資訊，然後投票人會拒絕掉那些日志沒有自己新的投票請求。
Raft 通過比較兩份日志中最後一條日志條目的索引值和任期号定義誰的日志比較新。如果兩份日志最後的條目的任期号不同，那麼任期号大的日志更加新。如果兩份日志最後的條目任期号相同，那麼日志比較長的那個就更加新。
5.4.2 送出之前任期内的日志條目
如同 5.3 節介紹的那樣，上司人知道一條目前任期内的日志記錄是可以被送出的，隻要它被存儲到了大多數的伺服器上。如果一個上司人在送出日志條目之前崩潰了，未來後續的上司人會繼續嘗試複制這條日志記錄。然而，一個上司人不能斷定一個之前任期裡的日志條目被儲存到大多數伺服器上的時候就一定已經送出了。圖 6 展示了一種情況，一條已經被存儲到大多數節點上的老日志條目，也依然有可能會被未來的上司人覆寫掉。
圖6
圖 6：如圖的時間序列展示了為什麼上司人無法決定對老任期号的日志條目進行送出。在 (a) 中，S1 是上司者，部分的複制了索引位置 2 的日志條目。在 (b) 中，S1 崩潰了，然後 S5 在任期 3 裡通過 S3、S4 和自己的選票赢得選舉，然後從用戶端接收了一條不一樣的日志條目放在了索引 2 處。然後到 (c)，S5 又崩潰了；S1 重新啟動，選舉成功，開始複制日志。在這時，來自任期 2 的那條日志已經被複制到了叢集中的大多數機器上，但是還沒有被送出。如果 S1 在 (d) 中又崩潰了，S5 可以重新被選舉成功（通過來自 S2，S3 和 S4 的選票），然後覆寫了他們在索引 2 處的日志。反之，如果在崩潰之前，S1 把自己主導的新任期裡産生的日志條目複制到了大多數機器上，就如 (e) 中那樣，那麼在後面任期裡面這些新的日志條目就會被送出（因為S5 就不可能選舉成功）。 這樣在同一時刻就同時保證了，之前的所有老的日志條目就會被送出。
為了消除圖6裡描述的情況，Raft 永遠不會通過計算副本數目的方式去送出一個之前任期内的日志條目。隻有上司人目前任期裡的日志條目通過計算副本數目可以被送出；一旦目前任期的日志條目以這種方式被送出，那麼由于日志比對特性，之前的日志條目也都會被間接的送出。在某些情況下，上司人可以安全的知道一個老的日志條目是否已經被送出（例如，該條目是否存儲到所有伺服器上），但是 Raft 為了簡化問題使用一種更加保守的方法。
當上司人複制之前任期裡的日志時，Raft 會為所有日志保留原始的任期号, 這在送出規則上産生了額外的複雜性。在其他的一緻性算法中，如果一個新的上司人要重新複制之前的任期裡的日志時，它必須使用目前新的任期号。Raft 使用的方法更加容易辨識出日志，因為它可以随着時間和日志的變化對日志維護着同一個任期編号。另外，和其他的算法相比，Raft 中的新上司人隻需要發送更少日志條目（其他算法中必須在他們被送出之前發送更多的備援日志條目來為他們重新編号）。
5.4.3 安全性論證
在給定了完整的Raft 算法之後，我們現在可以更加精确的讨論上司人完整性特性。我們假設上司人完全性特性是不存在的，然後我們推出沖突來。假設任期T的上司人（上司人T）在任期内送出了一條日志條目，但是這條日志條目沒有被存儲到未來某個任期的上司人的日志中。設大于T的最小任期U的上司人U沒有這條日志條目。
圖 7
圖 7：如果 S1 （任期 T 的上司者）送出了一條新的日志在它的任期裡，然後 S5 在之後的任期 U 裡被選舉為上司人，然後至少會有一個機器，如 S3，既擁有來自 S1 的日志，也給 S5 投票了。
- 在上司人 U 選舉的時候一定沒有那條被送出的日志條目（上司人從不會删除或者覆寫任何條目）。
- 上司人 T 複制這條日志條目給叢集中的大多數節點，同時，上司人U 從叢集中的大多數節點赢得了選票。是以，至少有一個節點（投票者、選民）同時接受了來自上司人T 的日志條目，并且給上司人U 投票了，如圖 7。這個投票者是産生這個沖突的關鍵。
- 這個投票者必須在給上司人 U 投票之前先接受了從上司人 T 發來的已經被送出的日志條目；否則他就會拒絕來自上司人 T 的附加日志請求（因為此時他的任期号會比 T 大）。
- 投票者在給上司人 U 投票時依然儲存有這條日志條目，因為任何中間的上司人都包含該日志條目（根據上述的假設），上司人從不會删除條目，并且跟随者隻有在和上司人沖突的時候才會删除條目。
- 投票者把自己選票投給上司人 U 時，上司人 U 的日志必須和投票者自己一樣新。這就導緻了兩者沖突之一。
- 首先，如果投票者和上司人 U 的最後一條日志的任期号相同，那麼上司人 U 的日志至少和投票者一樣長，是以上司人 U 的日志一定包含所有投票者的日志。這是另一處沖突，因為投票者包含了那條已經被送出的日志條目，但是在上述的假設裡，上司人 U 是不包含的。
- 除此之外，上司人 U 的最後一條日志的任期号就必須比投票人大了。此外，他也比 T 大，因為投票人的最後一條日志的任期号至少和 T 一樣大（他包含了來自任期 T 的已送出的日志）。建立了上司人 U 最後一條日志的之前上司人一定已經包含了那條被送出的日志（根據上述假設，上司人 U 是第一個不包含該日志條目的上司人）。是以，根據日志比對特性，上司人 U 一定也包含那條被送出的日志，這裡産生沖突。
- 這裡完成了沖突。是以，所有比 T 大的上司人一定包含了所有來自 T 的已經被送出的日志。
- 日志比對原則保證了未來的上司人也同時會包含被間接送出的條目，例如圖6 (d) 中的索引 2。
根據上司人完全特性，可知如果伺服器已經在某個給定的索引值應用了日志條目到自己的狀态機裡，那麼其他的伺服器不會應用一個不一樣的日志到同一個索引值上。在一個伺服器應用一條日志條目到他自己的狀态機中時，他的日志必須和上司人的日志，在該條目和之前的條目上相同，并且已經被送出。現在我們來考慮在任何一個伺服器應用一個指定索引位置的日志的最小任期；日志完全特性保證擁有更高任期号的上司人會存儲相同的日志條目，是以之後的任期裡應用某個索引位置的日志條目也會是相同的值。是以，狀态機安全特性是成立的。
最後，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 一緻性算法中來。
為了讓配置修改機制能夠安全，那麼在轉換的過程中不能夠存在任何時間點使得兩個上司人同時被選舉成功在同一個任期裡。不幸的是，任何伺服器直接從舊的配置直接轉換到新的配置的方案都是不安全的。一次性自動的轉換所有伺服器是不可能的，是以在轉換期間整個叢集存在劃分成兩個獨立的大多數群體的可能性（見圖 8）。
圖 8
圖 8：直接從一種配置轉到新的配置是十分不安全的，因為各個機器可能在任何的時候進行轉換。在這個例子中，叢集配額從 3 台機器變成了 5 台。不幸的是，存在這樣的一個時間點，兩個不同的上司人在同一個任期裡都可以被選舉成功。一個是通過舊的配置，一個通過新的配置。
為了保證安全性，配置更改必須使用兩階段方法。目前有很多種兩階段的實作。例如，有些系統在第一階段停掉舊的配置是以叢集就不能處理用戶端請求；然後在第二階段在啟用新的配置。在 Raft 中，叢集先切換到一個過渡的配置，我們稱之為共同一緻；一旦共同一緻已經被送出了，那麼系統就切換到新的配置上。共同一緻是老配置和新配置的結合：
- 日志條目被複制給叢集中新、老配置的所有伺服器。
- 新、舊配置的伺服器都可以成為上司人。
- 達成一緻（針對選舉和送出）需要分别在兩種配置上獲得大多數的支援。
共同一緻允許獨立的伺服器在不影響安全性的前提下，在不同的時間進行配置轉換過程。此外，共同一緻可以讓叢集在配置轉換的過程人依然響應用戶端的請求。
叢集配置在複制日志中以特殊的日志條目來存儲和通信；圖 9 展示了配置轉換的過程。當一個上司人接收到一個改變配置從 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 的規則下被送出，舊的配置就變得無關緊要，同時不使用新的配置的伺服器就可以被關閉了。如圖 9，C-old 和 C-new 沒有任何機會同時做出單方面的決定；這保證了安全性。
圖 9
圖 9：一個配置切換的時間線。虛線表示已經被建立但是還沒有被送出的條目，實線表示最後被送出的日志條目。上司人首先建立了 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 了。
圖 10
圖 10：一個伺服器用新的快照替換了從 1 到 5 的條目，快照值存儲了目前的狀态。快照中包含了最後的索引位置和任期号。
圖 10 展示了 Raft 中快照的基礎思想。每個伺服器獨立的建立快照，隻包括已經被送出的日志。主要的工作包括将狀态機的狀态寫入到快照中。Raft 也包含一些少量的中繼資料到快照中：最後被包含索引指的是被快照取代的最後的條目在日志中的索引值（狀态機最後應用的日志），最後被包含的任期指的是該條目的任期号。保留這些資料是為了支援快照後緊接着的第一個條目的附加日志請求時的一緻性檢查，因為這個條目需要前一日志條目的索引值和任期号。為了支援叢集成員更新，快照中也将最後的一次配置作為最後一個條目存下來。一旦伺服器完成一次快照，他就可以删除最後索引位置之前的所有日志和快照了。
盡管通常伺服器都是獨立的建立快照，但是上司人必須偶爾的發送快照給一些落後的跟随者。這通常發生在當上司人已經丢棄了下一條需要發送給跟随者的日志條目的時候。幸運的是這種情況不是正常操作：一個與上司人保持同步的跟随者通常都會有這個條目。然而一個運作非常緩慢的跟随者或者新加入叢集的伺服器将不會有這個條目。這時讓這個跟随者更新到最新的狀态的方式就是通過網絡把快照發送給他們。
8 Hyperledger Fabric為何選擇Raft
Hyperledger Fabric在1.4.1版本以前，Hyperledger Fabric的核心共識算法通過kafka叢集實作，簡單來說，就是通過kafka對所有交易資訊進行排序（如果系統存在多個channel，則對每個channel分别排序），Hyperledger Fabric為何選擇Raft主要從以下說明：
8.1 Raft排序和kafka排序的對比
從提供服務的視角來看，基于Raft和kafka的排序服務是類似的，他們都是基于CFT（crash fault tolerant）模型的排序服務，并且都使用了主從節點的設定。但是Raft比kafka有以下優勢：
- kafka和zookeeper的設計不适用于大型網絡。它們的設計是CFT模型，但局限于運作的比較緊密的主機上。也就是說，需要有一個組織專門運作kafka叢集。鑒于此，當有多個組織使用基于kafka排序服務的時候，其實沒有實作去中心化，因為所有的節點連接配接的都是由一個組織單獨控制的kafka叢集。如果使用Raft算法，每個組織可以貢獻排序節點，共同組成排序服務，可以更好的去中心化。
- Raft是原生支援的，而kafka需要經過複雜的步驟部署，并且需要單獨學習成本。而且kafka和zookeeper的支援相關的issue要通過apache來處理，而不是Hyperledger Fabric。Raft的實作是包含在Fabric社群的，開發支援更加便利。
- 系統架構不同
- kafka共識
在kafka共識模式中，orderer與orderer之間不會互相直接建立連接配接，而是與kafka連接配接。這種共識模式中，依賴于外部的kafka叢集系統和zookeeper叢集系統。每個orderer會把自己的交易發送給kafka叢集，交易在kafka對應的topic中排序後，kafka把排序後的交易推送給orderer節點。Orderer節點收到交易後對交易打包，然後發給peer，具體如下圖：
圖11
- Raft共識
在Raft共識模式中，orderer與orderer之間直接建立連接配接，不依賴外部系統。在orderer節點中，會建立Raft的協程來處理與其他orderer的通信，具體如下圖：
圖12
- Raft排序服務的目的
Raft排序是Fabric實作拜占庭容錯排序服務的第一步，如我們所見，開發Raft排序服務的決定也是基于此的。