可進(jìn)入我的博客查看原文。
Raft 算法是可以用來替代 Paxos 算法的分布式一致性算法，而且 raft 算法比 Paxos 算法更易懂且更容易實(shí)現(xiàn)。本文對 raft 論文進(jìn)行翻譯，希望能有助于讀者更方便地理解 raft 的思想。如果對 Paxos 算法感興趣，可以看我的另一篇文章：分布式系列文章——Paxos算法原理與推導(dǎo)
摘要
Raft 是用來管理復(fù)制日志（replicated log）的一致性協(xié)議。它跟 multi-Paxos 作用相同，效率也相當(dāng)，但是它的組織結(jié)構(gòu)跟 Paxos 不同。這使得 Raft 比 Paxos 更容易理解并且更容易在工程實(shí)踐中實(shí)現(xiàn)。為了使 Raft 協(xié)議更易懂，Raft將一致性的關(guān)鍵元素分開，如 leader 選舉、日志復(fù)制和安全性，并且它實(shí)施更強(qiáng)的一致性以減少必須考慮的狀態(tài)的數(shù)量。用戶研究的結(jié)果表明，Raft 比 Paxos 更容易學(xué)習(xí)。 Raft 還包括一個(gè)用于變更集群成員的新機(jī)制，它使用重疊的大多數(shù)（overlapping majorities）來保證安全性。
1 介紹
一致性算法允許多臺機(jī)器作為一個(gè)集群協(xié)同工作，并且在其中的某幾臺機(jī)器出故障時(shí)集群仍然能正常工作。 正因?yàn)槿绱?，一致性算法在建立可靠的大?guī)模軟件系統(tǒng)方面發(fā)揮了關(guān)鍵作用。 在過去十年中，Paxos [15,16] 主導(dǎo)了關(guān)于一致性算法的討論：大多數(shù)一致性的實(shí)現(xiàn)都是基于 Paxos 或受其影響，Paxos 已成為用于教授學(xué)生一致性相關(guān)知識的主要工具。
不幸的是，Paxos 實(shí)在是太難以理解，盡管許多人一直在努力嘗試使其更易懂。 此外，其架構(gòu)需要復(fù)雜的改變來支持實(shí)際系統(tǒng)。 結(jié)果是，系統(tǒng)開發(fā)者和學(xué)生都在與 Paxos 斗爭。
在我們自己與 Paxos 斗爭之后，我們開始著手尋找一個(gè)新的一致性算法，可以為系統(tǒng)開發(fā)和教學(xué)提供更好的基礎(chǔ)。 我們的方法是不尋常的，因?yàn)槲覀兊闹饕繕?biāo)是可理解性：我們可以為實(shí)際系統(tǒng)定義一個(gè)一致性算法，并以比 Paxos 更容易學(xué)習(xí)的方式描述它嗎？在該算法的設(shè)計(jì)過程中，重要的不僅是如何讓該算法起作用，還有清晰地知道該算法為什么會(huì)起作用。
這項(xiàng)工作的結(jié)果是一個(gè)稱為 Raft 的一致性算法。 在設(shè)計(jì) Raft 時(shí)，我們使用了特定的技術(shù)來提高可理解性，包括分解（Raft 分離 leader 選舉，日志復(fù)制和安全）和狀態(tài)空間減少（相對于 Paxos ，Raft 減少了不確定性程度和服務(wù)器之間彼此不一致的方式 ）。 一項(xiàng)針對兩個(gè)大學(xué)的 43 名學(xué)生的用戶研究表明，Raft 比 Paxos 更容易理解：在學(xué)習(xí)兩種算法后，其中 33 名學(xué)生能夠更好地回答關(guān)于 Raft 的問題。
Raft 在許多方面類似于現(xiàn)有的一致性算法（尤其是 Oki 和 Liskov 的 Viewstamped Replication [29,22]），但它有幾個(gè)新特性：
- Strong leader：在 Raft 中，日志條目（log entries）只從 leader 流向其他服務(wù)器。 這簡化了復(fù)制日志的管理，使得 raft 更容易理解。
- Leader 選舉：Raft 使用隨機(jī)計(jì)時(shí)器進(jìn)行 leader 選舉。 這只需在任何一致性算法都需要的心跳（heartbeats）上增加少量機(jī)制，同時(shí)能夠簡單快速地解決沖突。
- 成員變更：Raft 使用了一種新的聯(lián)合一致性方法，其中兩個(gè)不同配置的大多數(shù)在過渡期間重疊。 這允許集群在配置更改期間繼續(xù)正常運(yùn)行。
我們認(rèn)為，Raft 優(yōu)于 Paxos 和其他一致性算法，不僅在教學(xué)方面，在工程實(shí)現(xiàn)方面也是。 它比其他算法更簡單且更易于理解; 它被描述得十分詳細(xì)足以滿足實(shí)際系統(tǒng)的需要; 它有多個(gè)開源實(shí)現(xiàn)，并被多家公司使用; 它的安全性已被正式規(guī)定和驗(yàn)證; 它的效率與其他算法相當(dāng)。
本文的剩余部分介紹了復(fù)制狀態(tài)機(jī)問題（第 2 節(jié)），討論了 Paxos 的優(yōu)點(diǎn)和缺點(diǎn)（第3節(jié)），描述了我們實(shí)現(xiàn)易理解性的方法（第 4 節(jié)），提出了Raft一致性算法（第 5-8 節(jié)），評估Raft（第 9 節(jié)），并討論了相關(guān)工作（第 10 節(jié)）。
2 復(fù)制狀態(tài)機(jī)（Replicated state machines）
一致性算法是在復(fù)制狀態(tài)機(jī)[37]的背景下產(chǎn)生的。 在這種方法中，一組服務(wù)器上的狀態(tài)機(jī)計(jì)算相同狀態(tài)的相同副本，并且即使某些服務(wù)器宕機(jī)，也可以繼續(xù)運(yùn)行。
復(fù)制狀態(tài)機(jī)用于解決分布式系統(tǒng)中的各種容錯(cuò)問題。 例如，具有單個(gè) leader 的大規(guī)模系統(tǒng)，如 GFS [8]，HDFS [38] 和 RAMCloud [33] ，通常使用單獨(dú)的復(fù)制狀態(tài)機(jī)來進(jìn)行 leader 選舉和存儲(chǔ) leader 崩潰后重新選舉需要的配置信息。Chubby [2] 和 ZooKeeper [11] 都是復(fù)制狀態(tài)機(jī)。
復(fù)制狀態(tài)機(jī)通常使用復(fù)制日志實(shí)現(xiàn)，如圖1所示。每個(gè)服務(wù)器存儲(chǔ)一個(gè)包含一系列命令的日志，其狀態(tài)機(jī)按順序執(zhí)行日志中的命令。 每個(gè)日志中命令都相同并且順序也一樣，因此每個(gè)狀態(tài)機(jī)處理相同的命令序列。 這樣就能得到相同的狀態(tài)和相同的輸出序列。
一致性算法的工作就是保證復(fù)制日志的一致性。 每臺服務(wù)器上的一致性模塊接收來自客戶端的命令，并將它們添加到其日志中。 它與其他服務(wù)器上的一致性模塊通信，以確保每個(gè)日志最終以相同的順序包含相同的命令，即使有一些服務(wù)器失敗。 一旦命令被正確復(fù)制，每個(gè)服務(wù)器上的狀態(tài)機(jī)按日志順序處理它們，并將輸出返回給客戶端。 這樣就形成了高可用的復(fù)制狀態(tài)機(jī)。
實(shí)際系統(tǒng)中的一致性算法通常具有以下屬性：
它們確保在所有非拜占庭條件下（包括網(wǎng)絡(luò)延遲，分區(qū)和數(shù)據(jù)包丟失，重復(fù)和亂序）的安全性（不會(huì)返回不正確的結(jié)果）。
只要任何大多數(shù)（過半）服務(wù)器都可以運(yùn)行，并且可以相互通信和與客戶通信，一致性算法就可用。 因此，五臺服務(wù)器的典型集群可以容忍任何兩臺服務(wù)器的故障。 假設(shè)服務(wù)器突然宕機(jī); 它們可以稍后從狀態(tài)恢復(fù)并重新加入群集。
它們不依賴于時(shí)序來確保日志的一致性：錯(cuò)誤的時(shí)鐘和極端消息延遲可能在最壞的情況下導(dǎo)致可用性問題。
在通常情況下，只要集群的大部分（過半服務(wù)器）已經(jīng)響應(yīng)了單輪遠(yuǎn)程過程調(diào)用，命令就可以完成; 少數(shù)（一半以下）慢服務(wù)器不需要影響整個(gè)系統(tǒng)性能。
3 Paxos 存在的問題
在過去十年里，Leslie Lamport 的 Paxos 協(xié)議[15]幾乎成為一致性的同義詞：它是課堂上教授最多的一致性協(xié)議，并且大多數(shù)一致性的實(shí)現(xiàn)也以它為起點(diǎn)。 Paxos 首先定義了能夠在單個(gè)決策（例如單個(gè)復(fù)制日志條目）上達(dá)成一致的協(xié)議。 我們將這個(gè)子集稱為 single-decree Paxos。 然后 Paxos 組合該協(xié)議的多個(gè)實(shí)例以促進(jìn)一系列決策，例如日志（multi-Paxos）。 Paxos能夠確保安全性和活性，并且支持集群成員的變更。它的正確性已被證明，并且在正常情況下是高效的。
不幸的是，Paxos 有兩個(gè)顯著的缺點(diǎn)。 第一個(gè)缺點(diǎn)是 Paxos 非常難以理解。 Paxos 的描述晦澀難懂，臭名昭著（譯者注：《The Part-time Parliament》比較晦澀難懂，但是《Paxos Made Simple》就比較容易理解）; 很少有人成功地理解它，即使能理解也必須付出巨大的努力。 因此，已有幾個(gè)嘗試以更簡單的方式來描述 Paxos [16,20,21] 。 這些描述集中在 single-degree Paxos ，但它們?nèi)匀痪哂刑魬?zhàn)性。 在對 NSDI 2012 參會(huì)者的非正式調(diào)查中，我們發(fā)現(xiàn)很少有人喜歡 Paxos ，即使是經(jīng)驗(yàn)豐富的研究人員。 我們自己也跟 Paxos 進(jìn)行了艱苦的斗爭; 我們也無法完全理解整個(gè)協(xié)議，直到閱讀了幾個(gè)更簡單的描述和自己設(shè)計(jì)替代 Paxos 的協(xié)議，整個(gè)過程花了將近一年。
Paxos 晦澀難懂的原因是作者選擇了single-degree Paxos作為基礎(chǔ)。Single-decree Paxos 分成兩個(gè)階段，這兩個(gè)階段沒有簡單直觀的說明，并且不能被單獨(dú)理解。因此，很難理解為什么該算法能起作用。Multi-Paxos 的合成規(guī)則又增加了許多復(fù)雜性。我們相信，對多個(gè)決定（日志而不是單個(gè)日志條目）達(dá)成一致的總體問題可以用其他更直接和更明顯的方式進(jìn)行分解。
Paxos的第二個(gè)問題是它不能為構(gòu)建實(shí)際的實(shí)現(xiàn)提供良好的基礎(chǔ)。 一個(gè)原因是沒有針對 multi-Paxos 的廣泛同意的算法。 Lamport的描述主要是關(guān)于 single-decree Paxos; 他描述了 multi-Paxos 的可能方法，但缺少許多細(xì)節(jié)。 已經(jīng)有幾個(gè)嘗試來具體化和優(yōu)化 Paxos ，例如[26]，[39]和[13]，但這些彼此各不相同并且跟 Lamport 描述的也不同。 像Chubby [4] 這樣的系統(tǒng)已經(jīng)實(shí)現(xiàn)了類 Paxos（Paxos-like）算法，但大多數(shù)情況下，它們的細(xì)節(jié)并沒有公布。
此外，Paxos 的架構(gòu)對于構(gòu)建實(shí)際系統(tǒng)來說是一個(gè)糟糕的設(shè)計(jì)，這是 single-decree 分解的另一個(gè)結(jié)果。 例如，獨(dú)立地選擇日志條目集合，然后再將它們合并到順序日志中幾乎沒有任何好處，這只會(huì)增加復(fù)雜性。 圍繞日志設(shè)計(jì)系統(tǒng)是更簡單和有效的方法，新日志條目按照約束順序地添加到日志中。 Paxos 的做法適用于只需要做一次決策的情況，如果需要做一系列決策，更簡單和快速的方法是先選擇一個(gè) leader ，然后讓該 leader 協(xié)調(diào)這些決策。
因此，實(shí)際的系統(tǒng)跟 Paxos 相差很大。幾乎所有的實(shí)現(xiàn)都是從 Paxos 開始，然后發(fā)現(xiàn)很多實(shí)現(xiàn)上的難題，接著就開發(fā)了一種和 Paxos 完全不一樣的架構(gòu)。這樣既費(fèi)時(shí)又容易出錯(cuò)，而且 Paxos 本身晦澀難懂使得該問題更加嚴(yán)重。Paxos 的公式可能可以很好地證明它的正確性，但是現(xiàn)實(shí)的系統(tǒng)和 Paxos 差別是如此之大，以至于這些證明并沒有什么太大的價(jià)值。下面來自 Chubby 作者的評論非常典型：
在Paxos算法描述和實(shí)現(xiàn)現(xiàn)實(shí)系統(tǒng)中間有著巨大的鴻溝。最終的系統(tǒng)往往建立在一個(gè)還未被證明的協(xié)議之上。
由于以上問題，我們得出的結(jié)論是 Paxos 算法沒有為系統(tǒng)實(shí)踐和教學(xué)提供一個(gè)良好的基礎(chǔ)?？紤]到一致性問題在大規(guī)模軟件系統(tǒng)中的重要性，我們決定嘗試設(shè)計(jì)一個(gè)能夠替代 Paxos 并且具有更好特性的一致性算法。Raft算法就是這次實(shí)驗(yàn)的結(jié)果。
4 為可理解性而設(shè)計(jì)
在設(shè)計(jì) Raft 算法過程中我們有幾個(gè)目標(biāo)：它必須提供一個(gè)完整的實(shí)際的系統(tǒng)實(shí)現(xiàn)基礎(chǔ)，這樣才能大大減少開發(fā)者的工作；它必須在任何情況下都是安全的并且在典型的應(yīng)用條件下是可用的；并且在正常情況下是高效的。但是我們最重要的目標(biāo)也是最大的挑戰(zhàn)是可理解性。它必須保證能夠被大多數(shù)人容易地理解。另外，它必須能夠讓人形成直觀的認(rèn)識，這樣系統(tǒng)的構(gòu)建者才能夠在現(xiàn)實(shí)中進(jìn)行擴(kuò)展。
在設(shè)計(jì) Raft 算法的時(shí)候，很多情況下我們需要在多個(gè)備選方案中進(jìn)行選擇。在這種情況下，我們基于可理解性來評估備選方案：解釋各個(gè)備選方案的難道有多大（例如，Raft 的狀態(tài)空間有多復(fù)雜，是否有微妙的含義）？對于一個(gè)讀者而言，完全理解這個(gè)方案和含義是否容易？
我們意識到這樣的分析具有高度的主觀性；但是我們使用了兩種通用的技術(shù)來解決這個(gè)問題。第一個(gè)技術(shù)就是眾所周知的問題分解：只要有可能，我們就將問題分解成幾個(gè)相對獨(dú)立的，可被解決的、可解釋的和可理解的子問題。例如，Raft 算法被我們分成 leader 選舉，日志復(fù)制，安全性和成員變更幾個(gè)部分。
我們使用的第二個(gè)方法是通過減少狀態(tài)的數(shù)量來簡化狀態(tài)空間，使得系統(tǒng)更加連貫并且盡可能消除不確定性。特別的，所有的日志是不允許有空洞的，并且 Raft 限制了使日志之間不一致的方式。盡管在大多數(shù)情況下我們都試圖去消除不確定性，但是在某些情況下不確定性可以提高可理解性。特別是，隨機(jī)化方法雖然引入了不確定性，但是他們往往能夠通過使用相近的方法處理可能的選擇來減少狀態(tài)空間。我們使用隨機(jī)化來簡化 Raft 中的 leader 選舉算法。
5 Raft 一致性算法
Raft 是一種用來管理第 2 節(jié)中描述的復(fù)制日志的算法。圖 2 是該算法的濃縮，可用作參考，圖 3 列舉了該算法的一些關(guān)鍵特性。圖中的這些內(nèi)容將在剩下的章節(jié)中逐一介紹。
Raft 通過首先選舉一個(gè) distinguished leader，然后讓它全權(quán)負(fù)責(zé)管理復(fù)制日志來實(shí)現(xiàn)一致性。Leader 從客戶端接收日志條目，把日志條目復(fù)制到其他服務(wù)器上，并且在保證安全性的時(shí)候通知其他服務(wù)器將日志條目應(yīng)用到他們的狀態(tài)機(jī)中。擁有一個(gè) leader 大大簡化了對復(fù)制日志的管理。例如，領(lǐng)導(dǎo)人可以決定新的日志條目需要放在日志中的什么位置而不需要和其他服務(wù)器商議，并且數(shù)據(jù)都是從 leader 流向其他服務(wù)器。leader 可能宕機(jī)，也可能和其他服務(wù)器斷開連接，這時(shí)一個(gè)新的 leader 會(huì)被選舉出來。
通過選舉一個(gè) leader 的方式，Raft 將一致性問題分解成了三個(gè)相對獨(dú)立的子問題，這些問題將會(huì)在接下來的子章節(jié)中進(jìn)行討論：
- Leader 選舉：當(dāng)前的 leader 宕機(jī)時(shí)，一個(gè)新的 leader 必須被選舉出來。（章節(jié) 5.2）
- 日志復(fù)制：Leader 必須從客戶端接收日志條目然后復(fù)制到集群中的其他節(jié)點(diǎn)，并且強(qiáng)制要求其他節(jié)點(diǎn)的日志和自己的保持一致。
- 安全性：Raft 中安全性的關(guān)鍵是圖 3 中狀態(tài)機(jī)的安全性：如果有任何的服務(wù)器節(jié)點(diǎn)已經(jīng)應(yīng)用了一個(gè)特定的日志條目到它的狀態(tài)機(jī)中，那么其他服務(wù)器節(jié)點(diǎn)不能在同一個(gè)日志索引位置應(yīng)用一條不同的指令。章節(jié) 5.4 闡述了 Raft 算法是如何保證這個(gè)特性的；該解決方案在選舉機(jī)制（5.2 節(jié)）上增加了額外的限制。
在展示一致性算法之后，本章節(jié)將討論可用性的一些問題以及時(shí)序在系統(tǒng)中的作用。
5.1 Raft 基礎(chǔ)
一個(gè) Raft 集群包含若干個(gè)服務(wù)器節(jié)點(diǎn)；通常是 5 個(gè)，這樣的系統(tǒng)可以容忍 2 個(gè)節(jié)點(diǎn)的失效。在任何時(shí)刻，每一個(gè)服務(wù)器節(jié)點(diǎn)都處于這三個(gè)狀態(tài)之一：leader、follower 或者 candidate 。在正常情況下，集群中只有一個(gè) leader 并且其他的節(jié)點(diǎn)全部都是 follower 。Follower 都是被動(dòng)的：他們不會(huì)發(fā)送任何請求，只是簡單的響應(yīng)來自 leader 和 candidate 的請求。Leader 處理所有的客戶端請求（如果一個(gè)客戶端和 follower 通信，follower 會(huì)將請求重定向給 leader）。第三種狀態(tài)，candidate ，是用來選舉一個(gè)新的 leader（章節(jié) 5.2）。圖 4 展示了這些狀態(tài)和他們之間的轉(zhuǎn)換關(guān)系；這些轉(zhuǎn)換關(guān)系在接下來會(huì)進(jìn)行討論。
Raft 把時(shí)間分割成任意長度的任期（term），如圖 5 所示。任期用連續(xù)的整數(shù)標(biāo)記。每一段任期從一次選舉開始，一個(gè)或者多個(gè) candidate 嘗試成為 leader 。如果一個(gè) candidate 贏得選舉，然后他就在該任期剩下的時(shí)間里充當(dāng) leader 。在某些情況下，一次選舉無法選出 leader 。在這種情況下，這一任期會(huì)以沒有 leader 結(jié)束；一個(gè)新的任期（包含一次新的選舉）會(huì)很快重新開始。Raft 保證了在任意一個(gè)任期內(nèi)，最多只有一個(gè) leader 。
不同的服務(wù)器節(jié)點(diǎn)觀察到的任期轉(zhuǎn)換的次數(shù)可能不同，在某些情況下，一個(gè)服務(wù)器節(jié)點(diǎn)可能沒有看到 leader 選舉過程或者甚至整個(gè)任期全程。任期在 Raft 算法中充當(dāng)邏輯時(shí)鐘的作用，這使得服務(wù)器節(jié)點(diǎn)可以發(fā)現(xiàn)一些過期的信息比如過時(shí)的 leader 。每一個(gè)服務(wù)器節(jié)點(diǎn)存儲(chǔ)一個(gè)當(dāng)前任期號，該編號隨著時(shí)間單調(diào)遞增。服務(wù)器之間通信的時(shí)候會(huì)交換當(dāng)前任期號；如果一個(gè)服務(wù)器的當(dāng)前任期號比其他的小，該服務(wù)器會(huì)將自己的任期號更新為較大的那個(gè)值。如果一個(gè) candidate 或者 leader 發(fā)現(xiàn)自己的任期號過期了，它會(huì)立即回到 follower 狀態(tài)。如果一個(gè)節(jié)點(diǎn)接收到一個(gè)包含過期的任期號的請求，它會(huì)直接拒絕這個(gè)請求。
Raft 算法中服務(wù)器節(jié)點(diǎn)之間使用 RPC 進(jìn)行通信，并且基本的一致性算法只需要兩種類型的 RPC。請求投票（RequestVote） RPC 由 candidate 在選舉期間發(fā)起（章節(jié) 5.2），追加條目（AppendEntries）RPC 由 leader 發(fā)起，用來復(fù)制日志和提供一種心跳機(jī)制（章節(jié) 5.3）。第 7 節(jié)為了在服務(wù)器之間傳輸快照增加了第三種 RPC。當(dāng)服務(wù)器沒有及時(shí)的收到 RPC 的響應(yīng)時(shí)，會(huì)進(jìn)行重試， 并且他們能夠并行的發(fā)起 RPC 來獲得最佳的性能。
5.2 Leader 選舉
Raft 使用一種心跳機(jī)制來觸發(fā) leader 選舉。當(dāng)服務(wù)器程序啟動(dòng)時(shí)，他們都是 follower 。一個(gè)服務(wù)器節(jié)點(diǎn)只要能從 leader 或 candidate 處接收到有效的 RPC 就一直保持 follower 狀態(tài)。Leader 周期性地向所有 follower 發(fā)送心跳（不包含日志條目的 AppendEntries RPC）來維持自己的地位。如果一個(gè) follower 在一段選舉超時(shí)時(shí)間內(nèi)沒有接收到任何消息，它就假設(shè)系統(tǒng)中沒有可用的 leader ，然后開始進(jìn)行選舉以選出新的leader。
要開始一次選舉過程，follower 先增加自己的當(dāng)前任期號并且轉(zhuǎn)換到 candidate 狀態(tài)。然后投票給自己并且并行地向集群中的其他服務(wù)器節(jié)點(diǎn)發(fā)送 RequestVote RPC（讓其他服務(wù)器節(jié)點(diǎn)投票給它）。Candidate 會(huì)一直保持當(dāng)前狀態(tài)直到以下三件事情之一發(fā)生：(a) 它自己贏得了這次的選舉（收到過半的投票），(b) 其他的服務(wù)器節(jié)點(diǎn)成為 leader ，(c) 一段時(shí)間之后沒有任何獲勝者。這些結(jié)果會(huì)在下面的章節(jié)里分別討論。
當(dāng)一個(gè) candidate 獲得集群中過半服務(wù)器節(jié)點(diǎn)針對同一個(gè)任期的投票，它就贏得了這次選舉并成為 leader 。對于同一個(gè)任期，每個(gè)服務(wù)器節(jié)點(diǎn)只會(huì)投給一個(gè) candidate ，按照先來先服務(wù)（first-come-first-served）的原則（注意：5.4 節(jié)在投票上增加了額外的限制）。要求獲得過半投票的規(guī)則確保了最多只有一個(gè) candidate 贏得此次選舉（圖 3 中的選舉安全性）。一旦 candidate 贏得選舉，就立即成為 leader 。然后它會(huì)向其他的服務(wù)器節(jié)點(diǎn)發(fā)送心跳消息來確定自己的地位并阻止新的選舉。
在等待投票期間，candidate 可能會(huì)收到另一個(gè)聲稱自己是 leader 的服務(wù)器節(jié)點(diǎn)發(fā)來的 AppendEntries RPC 。如果這個(gè) leader 的任期號（包含在RPC中）不小于 candidate 當(dāng)前的任期號，那么 candidate 會(huì)承認(rèn)該 leader 的合法地位并回到 follower 狀態(tài)。 如果 RPC 中的任期號比自己的小，那么 candidate 就會(huì)拒絕這次的 RPC 并且繼續(xù)保持 candidate 狀態(tài)。
第三種可能的結(jié)果是 candidate 既沒有贏得選舉也沒有輸：如果有多個(gè) follower 同時(shí)成為 candidate ，那么選票可能會(huì)被瓜分以至于沒有 candidate 贏得過半的投票。當(dāng)這種情況發(fā)生時(shí)，每一個(gè)候選人都會(huì)超時(shí)，然后通過增加當(dāng)前任期號來開始一輪新的選舉。然而，如果沒有其他機(jī)制的話，該情況可能會(huì)無限重復(fù)。
Raft 算法使用隨機(jī)選舉超時(shí)時(shí)間的方法來確保很少發(fā)生選票瓜分的情況，就算發(fā)生也能很快地解決。為了阻止選票一開始就被瓜分，選舉超時(shí)時(shí)間是從一個(gè)固定的區(qū)間（例如 150-300 毫秒）隨機(jī)選擇。這樣可以把服務(wù)器都分散開以至于在大多數(shù)情況下只有一個(gè)服務(wù)器會(huì)選舉超時(shí)；然后該服務(wù)器贏得選舉并在其他服務(wù)器超時(shí)之前發(fā)送心跳。同樣的機(jī)制被用來解決選票被瓜分的情況。每個(gè) candidate 在開始一次選舉的時(shí)候會(huì)重置一個(gè)隨機(jī)的選舉超時(shí)時(shí)間，然后一直等待直到選舉超時(shí)；這樣減小了在新的選舉中再次發(fā)生選票瓜分情況的可能性。9.3 節(jié)展示了該方案能夠快速地選出一個(gè) leader 。
選舉的例子可以很好地展示可理解性是如何指導(dǎo)我們選擇設(shè)計(jì)方案的。起初我們打算使用一種等級系統(tǒng)（ranking system）：每一個(gè) candidate 都被賦予一個(gè)唯一的等級（rank），等級用來在競爭的 candidate 之間進(jìn)行選擇。如果一個(gè) candidate 發(fā)現(xiàn)另一個(gè) candidate 擁有更高的等級，它就會(huì)回到 follower 狀態(tài)，這樣高等級的 candidate 能夠更加容易地贏得下一次選舉。但是我們發(fā)現(xiàn)這種方法在可用性方面會(huì)有一下小問題。我們對該算法進(jìn)行了多次調(diào)整，但是每次調(diào)整之后都會(huì)有新的小問題。最終我們認(rèn)為隨機(jī)重試的方法更加顯然且易于理解。
5.3 日志復(fù)制
Leader 一旦被選舉出來，就開始為客戶端請求提供服務(wù)?？蛻舳说拿恳粋€(gè)請求都包含一條將被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。Leader 把該指令作為一個(gè)新的條目追加到日志中去，然后并行的發(fā)起 AppendEntries RPC 給其他的服務(wù)器，讓它們復(fù)制該條目。當(dāng)該條目被安全地復(fù)制（下面會(huì)介紹），leader 會(huì)應(yīng)用該條目到它的狀態(tài)機(jī)中（狀態(tài)機(jī)執(zhí)行該指令）然后把執(zhí)行的結(jié)果返回給客戶端。如果 follower 崩潰或者運(yùn)行緩慢，或者網(wǎng)絡(luò)丟包，領(lǐng)導(dǎo)人會(huì)不斷地重試 AppendEntries RPC（即使已經(jīng)回復(fù)了客戶端）直到所有的 follower 最終都存儲(chǔ)了所有的日志條目。
日志以圖 6 展示的方式組織。每個(gè)日志條目存儲(chǔ)一條狀態(tài)機(jī)指令和 leader 收到該指令時(shí)的任期號。任期號用來檢測多個(gè)日志副本之間的不一致情況，同時(shí)也用來保證圖 3 中的某些性質(zhì)。每個(gè)日志條目都有一個(gè)整數(shù)索引值來表明它在日志中的位置。
Leader 決定什么時(shí)候把日志條目應(yīng)用到狀態(tài)機(jī)中是安全的；這種日志條目被稱為已提交的。Raft 算法保證所有已提交的日志條目都是持久化的并且最終會(huì)被所有可用的狀態(tài)機(jī)執(zhí)行。一旦創(chuàng)建該日志條目的 leader 將它復(fù)制到過半的服務(wù)器上，該日志條目就會(huì)被提交（例如在圖 6 中的條目 7）。同時(shí)，leader 日志中該日志條目之前的所有日志條目也都會(huì)被提交，包括由其他 leader 創(chuàng)建的條目。5.4 節(jié)討論在 leader 變更之后應(yīng)用該規(guī)則的一些細(xì)節(jié)，并且證明了這種提交的規(guī)則是安全的。Leader 追蹤將會(huì)被提交的日志條目的最大索引，未來的所有 AppendEntries RPC 都會(huì)包含該索引，這樣其他的服務(wù)器才能最終知道哪些日志條目需要被提交。Follower 一旦知道某個(gè)日志條目已經(jīng)被提交就會(huì)將該日志條目應(yīng)用到自己的本地狀態(tài)機(jī)中（按照日志的順序）。
我們設(shè)計(jì)了 Raft 的日志機(jī)制來維持不同服務(wù)器之間日志高層次的一致性。這么做不僅簡化了系統(tǒng)的行為也使得系統(tǒng)行為更加可預(yù)測，同時(shí)該機(jī)制也是保證安全性的重要組成部分。Raft 維護(hù)著以下特性，這些同時(shí)也構(gòu)成了圖 3 中的日志匹配特性：
- 如果不同日志中的兩個(gè)條目擁有相同的索引和任期號，那么他們存儲(chǔ)了相同的指令。
- 如果不同日志中的兩個(gè)條目擁有相同的索引和任期號，那么他們之前的所有日志條目也都相同。
Leader 在特定的任期號內(nèi)的一個(gè)日志索引處最多創(chuàng)建一個(gè)日志條目，同時(shí)日志條目在日志中的位置也從來不會(huì)改變。該點(diǎn)保證了上面的第一條特性。第二個(gè)特性是由 AppendEntries RPC 執(zhí)行一個(gè)簡單的一致性檢查所保證的。在發(fā)送 AppendEntries RPC 的時(shí)候，leader 會(huì)將前一個(gè)日志條目的索引位置和任期號包含在里面。如果 follower 在它的日志中找不到包含相同索引位置和任期號的條目，那么他就會(huì)拒絕該新的日志條目。一致性檢查就像一個(gè)歸納步驟：一開始空的日志狀態(tài)肯定是滿足 Log Matching Property（日志匹配特性） 的，然后一致性檢查保證了日志擴(kuò)展時(shí)的日志匹配特性。因此，每當(dāng) AppendEntries RPC 返回成功時(shí)，leader 就知道 follower 的日志一定和自己相同（從第一個(gè)日志條目到最新條目）。
正常操作期間，leader 和 follower 的日志保持一致，所以 AppendEntries RPC 的一致性檢查從來不會(huì)失敗。然而，leader 崩潰的情況會(huì)使日志處于不一致的狀態(tài)（老的 leader 可能還沒有完全復(fù)制它日志里的所有條目）。這種不一致會(huì)在一系列的 leader 和 follower 崩潰的情況下加劇。圖 7 展示了在什么情況下 follower 的日志可能和新的 leader 的日志不同。Follower 可能缺少一些在新 leader 中有的日志條目，也可能擁有一些新 leader 沒有的日志條目，或者同時(shí)發(fā)生。缺失或多出日志條目的情況可能會(huì)涉及到多個(gè)任期。
圖 7：當(dāng)一個(gè) leader 成功當(dāng)選時(shí)（最上面那條日志），follower 可能是（a-f）中的任何情況。每一個(gè)盒子表示一個(gè)日志條目；里面的數(shù)字表示任期號。Follower 可能會(huì)缺少一些日志條目（a-b），可能會(huì)有一些未被提交的日志條目（c-d），或者兩種情況都存在（e-f）。例如，場景 f 可能這樣發(fā)生，f 對應(yīng)的服務(wù)器在任期 2 的時(shí)候是 leader ，追加了一些日志條目到自己的日志中，一條都還沒提交（commit）就崩潰了；該服務(wù)器很快重啟，在任期 3 重新被選為 leader，又追加了一些日志條目到自己的日志中；在這些任期 2 和任期 3 中的日志都還沒被提交之前，該服務(wù)器又宕機(jī)了，并且在接下來的幾個(gè)任期里一直處于宕機(jī)狀態(tài)。
在 Raft 算法中，leader 通過強(qiáng)制 follower 復(fù)制它的日志來解決不一致的問題。這意味著 follower 中跟 leader 沖突的日志條目會(huì)被 leader 的日志條目覆蓋。5.4 節(jié)會(huì)證明通過增加一個(gè)限制可以保證安全性。
要使得 follower 的日志跟自己一致，leader 必須找到兩者達(dá)成一致的最大的日志條目（索引最大），刪除 follower 日志中從那個(gè)點(diǎn)之后的所有日志條目，并且將自己從那個(gè)點(diǎn)之后的所有日志條目發(fā)送給 follower 。所有的這些操作都發(fā)生在對 AppendEntries RPCs 中一致性檢查的回復(fù)中。Leader 針對每一個(gè) follower 都維護(hù)了一個(gè) nextIndex ，表示 leader 要發(fā)送給 follower 的下一個(gè)日志條目的索引。當(dāng)選出一個(gè)新 leader 時(shí)，該 leader 將所有 nextIndex 的值都初始化為自己最后一個(gè)日志條目的 index 加1（圖 7 中的 11）。如果 follower 的日志和 leader 的不一致，那么下一次 AppendEntries RPC 中的一致性檢查就會(huì)失敗。在被 follower 拒絕之后，leaer 就會(huì)減小 nextIndex 值并重試 AppendEntries RPC 。最終 nextIndex 會(huì)在某個(gè)位置使得 leader 和 follower 的日志達(dá)成一致。此時(shí)，AppendEntries RPC 就會(huì)成功，將 follower 中跟 leader 沖突的日志條目全部刪除然后追加 leader 中的日志條目（如果有需要追加的日志條目的話）。一旦 AppendEntries RPC 成功，follower 的日志就和 leader 一致，并且在該任期接下來的時(shí)間里保持一致。
如果想要的話，該協(xié)議可以被優(yōu)化來減少被拒絕的 AppendEntries RPC 的個(gè)數(shù)。例如，當(dāng)拒絕一個(gè) AppendEntries RPC 的請求的時(shí)候，follower 可以包含沖突條目的任期號和自己存儲(chǔ)的那個(gè)任期的第一個(gè) index 。借助這些信息，leader 可以跳過那個(gè)任期內(nèi)所有沖突的日志條目來減小 nextIndex；這樣就變成每個(gè)有沖突日志條目的任期需要一個(gè) AppendEntries RPC 而不是每個(gè)條目一次。在實(shí)踐中，我們認(rèn)為這種優(yōu)化是沒有必要的，因?yàn)槭〔唤?jīng)常發(fā)生并且也不可能有很多不一致的日志條目。
通過這種機(jī)制，leader 在當(dāng)權(quán)之后就不需要任何特殊的操作來使日志恢復(fù)到一致狀態(tài)。Leader 只需要進(jìn)行正常的操作，然后日志就能在回復(fù) AppendEntries 一致性檢查失敗的時(shí)候自動(dòng)趨于一致。Leader 從來不會(huì)覆蓋或者刪除自己的日志條目（圖 3 的 Leader Append-Only 屬性）。
這樣的日志復(fù)制機(jī)制展示了第 2 節(jié)中描述的一致性特性：只要過半的服務(wù)器能正常運(yùn)行，Raft 就能夠接受，復(fù)制并應(yīng)用新的日志條目；在正常情況下，新的日志條目可以在一個(gè) RPC 來回中被復(fù)制給集群中的過半機(jī)器；并且單個(gè)運(yùn)行慢的 follower 不會(huì)影響整體的性能。
5.4 安全性
前面的章節(jié)里描述了 Raft 算法是如何進(jìn)行 leader 選舉和日志復(fù)制的。然而，到目前為止描述的機(jī)制并不能充分地保證每一個(gè)狀態(tài)機(jī)會(huì)按照相同的順序執(zhí)行相同的指令。例如，一個(gè) follower 可能會(huì)進(jìn)入不可用狀態(tài)，在此期間，leader 可能提交了若干的日志條目，然后這個(gè) follower 可能會(huì)被選舉為 leader 并且用新的日志條目覆蓋這些日志條目；結(jié)果，不同的狀態(tài)機(jī)可能會(huì)執(zhí)行不同的指令序列。
這節(jié)通過對 leader 選舉增加一個(gè)限制來完善 Raft 算法。這一限制保證了對于給定的任意任期號， leader 都包含了之前各個(gè)任期所有被提交的日志條目（圖 3 中的 Leader Completeness 性質(zhì)）。有了這一 leader 選舉的限制，我們也使得提交規(guī)則更加清晰。最后，我們展示了對于 Leader Completeness 性質(zhì)的簡要證明并且說明該性質(zhì)是如何領(lǐng)導(dǎo)復(fù)制狀態(tài)機(jī)執(zhí)行正確的行為的。
5.4.1 選舉限制
在任何基于 leader 的一致性算法中，leader 最終都必須存儲(chǔ)所有已經(jīng)提交的日志條目。在某些一致性算法中，例如 Viewstamped Replication[22]，一開始并沒有包含所有已經(jīng)提交的日志條目的服務(wù)器也可能被選為 leader 。這種算法包含一些額外的機(jī)制來識別丟失的日志條目并將它們傳送給新的 leader ，要么是在選舉階段要么在之后很快進(jìn)行。不幸的是，這種方法會(huì)導(dǎo)致相當(dāng)大的額外的機(jī)制和復(fù)雜性。Raft 使用了一種更加簡單的方法，它可以保證新 leader 在當(dāng)選時(shí)就包含了之前所有任期號中已經(jīng)提交的日志條目，不需要再傳送這些日志條目給新 leader 。這意味著日志條目的傳送是單向的，只從 leader 到 follower，并且 leader 從不會(huì)覆蓋本地日志中已經(jīng)存在的條目。
Raft 使用投票的方式來阻止 candidate 贏得選舉除非該 candidate 包含了所有已經(jīng)提交的日志條目。候選人為了贏得選舉必須與集群中的過半節(jié)點(diǎn)通信，這意味著至少其中一個(gè)服務(wù)器節(jié)點(diǎn)包含了所有已提交的日志條目。如果 candidate 的日志至少和過半的服務(wù)器節(jié)點(diǎn)一樣新（接下來會(huì)精確地定義“新”），那么他一定包含了所有已經(jīng)提交的日志條目。RequestVote RPC 執(zhí)行了這樣的限制： RPC 中包含了 candidate 的日志信息，如果投票者自己的日志比 candidate 的還新，它會(huì)拒絕掉該投票請求。
Raft 通過比較兩份日志中最后一條日志條目的索引值和任期號來定義誰的日志比較新。如果兩份日志最后條目的任期號不同，那么任期號大的日志更新。如果兩份日志最后條目的任期號相同，那么日志較長的那個(gè)更新。
5.4.2 提交之前任期內(nèi)的日志條目
如同 5.3 節(jié)描述的那樣，一旦當(dāng)前任期內(nèi)的某個(gè)日志條目已經(jīng)存儲(chǔ)到過半的服務(wù)器節(jié)點(diǎn)上，leader 就知道該日志條目已經(jīng)被提交了。如果某個(gè) leader 在提交某個(gè)日志條目之前崩潰了，以后的 leader 會(huì)試圖完成該日志條目的復(fù)制。然而，如果是之前任期內(nèi)的某個(gè)日志條目已經(jīng)存儲(chǔ)到過半的服務(wù)器節(jié)點(diǎn)上，leader 也無法立即斷定該日志條目已經(jīng)被提交了。圖 8 展示了一種情況，一個(gè)已經(jīng)被存儲(chǔ)到過半節(jié)點(diǎn)上的老日志條目，仍然有可能會(huì)被未來的 leader 覆蓋掉。
圖 8：如圖的時(shí)間序列展示了為什么 leader 無法判斷老的任期號內(nèi)的日志是否已經(jīng)被提交。在 (a) 中，S1 是 leader ，部分地復(fù)制了索引位置 2 的日志條目。在 (b) 中，S1 崩潰了，然后 S5 在任期 3 中通過 S3、S4 和自己的選票贏得選舉，然后從客戶端接收了一條不一樣的日志條目放在了索引 2 處。然后到 (c)，S5 又崩潰了；S1 重新啟動(dòng)，選舉成功，繼續(xù)復(fù)制日志。此時(shí)，來自任期 2 的那條日志已經(jīng)被復(fù)制到了集群中的大多數(shù)機(jī)器上，但是還沒有被提交。如果 S1 在 (d) 中又崩潰了，S5 可以重新被選舉成功（通過來自 S2，S3 和 S4 的選票），然后覆蓋了他們在索引 2 處的日志。但是，在崩潰之前，如果 S1 在自己的任期里復(fù)制了日志條目到大多數(shù)機(jī)器上，如 (e) 中，然后這個(gè)條目就會(huì)被提交（S5 就不可能選舉成功）。 在這種情況下，之前的所有日志也被提交了。
為了消除圖 8 中描述的問題，Raft 永遠(yuǎn)不會(huì)通過計(jì)算副本數(shù)目的方式來提交之前任期內(nèi)的日志條目。只有 leader 當(dāng)前任期內(nèi)的日志條目才通過計(jì)算副本數(shù)目的方式來提交；一旦當(dāng)前任期的某個(gè)日志條目以這種方式被提交，那么由于日志匹配特性，之前的所有日志條目也都會(huì)被間接地提交。在某些情況下，領(lǐng)導(dǎo)人可以安全地?cái)喽ㄒ粋€(gè)老的日志條目已經(jīng)被提交（例如，如果該條目已經(jīng)存儲(chǔ)到所有服務(wù)器上），但是 Raft 為了簡化問題使用了一種更加保守的方法。
Raft 會(huì)在提交規(guī)則上增加額外的復(fù)雜性是因?yàn)楫?dāng) leader 復(fù)制之前任期內(nèi)的日志條目時(shí)，這些日志條目都保留原來的任期號。在其他的一致性算法中，如果一個(gè)新的 leader 要重新復(fù)制之前的任期里的日志時(shí)，它必須使用當(dāng)前新的任期號。Raft 的做法使得更加容易推導(dǎo)出（reason about）日志條目，因?yàn)樗麄冏允贾两K都使用同一個(gè)任期號。另外，和其他的算法相比，Raft 中的新 leader 只需要發(fā)送更少的日志條目（其他算法中必須在它們被提交之前發(fā)送更多的冗余日志條目來給它們重新編號）。
5.4.3 安全性論證
在給出了完整的 Raft 算法之后，我們現(xiàn)在可以更加精確的討論領(lǐng)導(dǎo)人完整性特性（Leader Completeness Prop-erty）（這一討論基于 9.2 節(jié)的安全性證明）。我們假設(shè)領(lǐng)導(dǎo)人完全性特性是不滿足的，然后我們推出矛盾來。假設(shè)任期 T 的 leader（leader T）在任期內(nèi)提交了一個(gè)日志條目，但是該日志條目沒有被存儲(chǔ)到未來某些任期的 leader 中。假設(shè) U 是大于 T 的沒有存儲(chǔ)該日志條目的最小任期號。
圖 9：如果 S1 （任期 T 的 leader）在它的任期里提交了一個(gè)新的日志條目，然后 S5 在之后的任期 U 里被選舉為 leader ，那么肯定至少會(huì)有一個(gè)節(jié)點(diǎn)，如 S3，既接收了來自 S1 的日志條目，也給 S5 投票了。
U 一定在剛成為 leader 的時(shí)候就沒有那條被提交的日志條目了（leader 從不會(huì)刪除或者覆蓋任何條目）。
Leader T 復(fù)制該日志條目給集群中的過半節(jié)點(diǎn)，同時(shí)，leader U 從集群中的過半節(jié)點(diǎn)贏得了選票。因此，至少有一個(gè)節(jié)點(diǎn)（投票者）同時(shí)接受了來自 leader T 的日志條目和給 leader U 投票了，如圖 9。該投票者是產(chǎn)生矛盾的關(guān)鍵。
該投票者必須在給 leader U 投票之前先接受了從 leader T 發(fā)來的已經(jīng)被提交的日志條目；否則它就會(huì)拒絕來自 leader T 的 AppendEntries 請求（因?yàn)榇藭r(shí)它的任期號會(huì)比 T 大）。
該投票者在給 leader U 投票時(shí)依然保有這該日志條目，因?yàn)槿魏?U 、T 之間的 leader 都包含該日志條目（根據(jù)上述的假設(shè)），leader 從不會(huì)刪除條目，并且 follower 只有跟 leader 沖突的時(shí)候才會(huì)刪除條目。
該投票者把自己選票投給 leader U 時(shí)，leader U 的日志必須至少和投票者的一樣新。這就導(dǎo)致了以下兩個(gè)矛盾之一。
首先，如果該投票者和 leader U 的最后一個(gè)日志條目的任期號相同，那么 leader U 的日志至少和該投票者的一樣長，所以 leader U 的日志一定包含該投票者日志中的所有日志條目。這是一個(gè)矛盾，因?yàn)樵撏镀闭甙嗽撘驯惶峤坏娜罩緱l目，但是在上述的假設(shè)里，leader U 是不包含的。
否則，leader U 的最后一個(gè)日志條目的任期號就必須比該投票者的大了。此外，該任期號也比 T 大，因?yàn)樵撏镀闭叩淖詈笠粋€(gè)日志條目的任期號至少和 T 一樣大（他包含了來自任期 T 的已提交的日志）。創(chuàng)建了 leader U 最后一個(gè)日志條目的之前的 leader 一定已經(jīng)包含了該已被提交的日志條目（根據(jù)上述假設(shè)，leader U 是第一個(gè)不包含該日志條目的 leader）。所以，根據(jù)日志匹配特性，leader U 一定也包含該已被提交的日志條目，這里產(chǎn)生了矛盾。
因此，所有比 T 大的任期的 leader 一定都包含了任期 T 中提交的所有日志條目。
日志匹配特性保證了未來的 leader 也會(huì)包含被間接提交的日志條目，例如圖 8 (d) 中的索引 2。
通過 Leader Completeness 特性，我們就能證明圖 3 中的狀態(tài)機(jī)安全特性，即如果某個(gè)服務(wù)器已經(jīng)將某個(gè)給定的索引處的日志條目應(yīng)用到自己的狀態(tài)機(jī)里了，那么其他的服務(wù)器就不會(huì)在相同的索引處應(yīng)用一個(gè)不同的日志條目。在一個(gè)服務(wù)器應(yīng)用一個(gè)日志條目到自己的狀態(tài)機(jī)中時(shí)，它的日志和 leader 的日志從開始到該日志條目都相同，并且該日志條目必須被提交?，F(xiàn)在考慮如下最小任期號：某服務(wù)器在該任期號中某個(gè)特定的索引處應(yīng)用了一個(gè)日志條目；日志完整性特性保證擁有更高任期號的 leader 會(huì)存儲(chǔ)相同的日志條目，所以之后任期里服務(wù)器應(yīng)用該索引處的日志條目也會(huì)是相同的值。因此，狀態(tài)機(jī)安全特性是成立的。
最后，Raft 要求服務(wù)器按照日志索引順序應(yīng)用日志條目。再加上狀態(tài)機(jī)安全特性，這就意味著所有的服務(wù)器都會(huì)按照相同的順序應(yīng)用相同的日志條目到自己的狀態(tài)機(jī)中。
5.5 Follower 和 candidate 崩潰
到目前為止，我們只關(guān)注了 leader 崩潰的情況。Follower 和 candidate 崩潰后的處理方式比 leader 崩潰要簡單的多，并且兩者的處理方式是相同的。如果 follower 或者 candidate 崩潰了，那么后續(xù)發(fā)送給他們的 RequestVote 和 AppendEntries RPCs 都會(huì)失敗。Raft 通過無限的重試來處理這種失敗；如果崩潰的機(jī)器重啟了，那么這些 RPC 就會(huì)成功地完成。如果一個(gè)服務(wù)器在完成了一個(gè) RPC，但是還沒有響應(yīng)的時(shí)候崩潰了，那么在它重啟之后就會(huì)再次收到同樣的請求。Raft 的 RPCs 都是冪等的，所以這樣的重試不會(huì)造成任何傷害。例如，一個(gè) follower 如果收到 AppendEntries 請求但是它的日志中已經(jīng)包含了這些日志條目，它就會(huì)直接忽略這個(gè)新的請求中的這些日志條目。
5.6 定時(shí)（timing）和可用性
Raft 的要求之一就是安全性不能依賴定時(shí)：整個(gè)系統(tǒng)不能因?yàn)槟承┦录\(yùn)行得比預(yù)期快一點(diǎn)或者慢一點(diǎn)就產(chǎn)生錯(cuò)誤的結(jié)果。但是，可用性（系統(tǒng)能夠及時(shí)響應(yīng)客戶端）不可避免的要依賴于定時(shí)。例如，當(dāng)有服務(wù)器崩潰時(shí)，消息交換的時(shí)間就會(huì)比正常情況下長，candidate 將不會(huì)等待太長的時(shí)間來贏得選舉；沒有一個(gè)穩(wěn)定的 leader ，Raft 將無法工作。
Leader 選舉是 Raft 中定時(shí)最為關(guān)鍵的方面。 只要整個(gè)系統(tǒng)滿足下面的時(shí)間要求，Raft 就可以選舉出并維持一個(gè)穩(wěn)定的 leader：
廣播時(shí)間（broadcastTime） << 選舉超時(shí)時(shí)間（electionTimeout） << 平均故障間隔時(shí)間（MTBF）
在這個(gè)不等式中，廣播時(shí)間指的是一個(gè)服務(wù)器并行地發(fā)送 RPCs 給集群中所有的其他服務(wù)器并接收到響應(yīng)的平均時(shí)間；選舉超時(shí)時(shí)間就是在 5.2 節(jié)中介紹的選舉超時(shí)時(shí)間；平均故障間隔時(shí)間就是對于一臺服務(wù)器而言，兩次故障間隔時(shí)間的平均值。廣播時(shí)間必須比選舉超時(shí)時(shí)間小一個(gè)量級，這樣 leader 才能夠可靠地發(fā)送心跳消息來阻止 follower 開始進(jìn)入選舉狀態(tài)；再加上隨機(jī)化選舉超時(shí)時(shí)間的方法，這個(gè)不等式也使得選票瓜分的情況變得不可能。選舉超時(shí)時(shí)間需要比平均故障間隔時(shí)間小上幾個(gè)數(shù)量級，這樣整個(gè)系統(tǒng)才能穩(wěn)定地運(yùn)行。當(dāng) leader 崩潰后，整個(gè)系統(tǒng)會(huì)有大約選舉超時(shí)時(shí)間不可用；我們希望該情況在整個(gè)時(shí)間里只占一小部分。
廣播時(shí)間和平均故障間隔時(shí)間是由系統(tǒng)決定的，但是選舉超時(shí)時(shí)間是我們自己選擇的。Raft 的 RPCs 需要接收方將信息持久化地保存到穩(wěn)定存儲(chǔ)中去，所以廣播時(shí)間大約是 0.5 毫秒到 20 毫秒之間，取決于存儲(chǔ)的技術(shù)。因此，選舉超時(shí)時(shí)間可能需要在 10 毫秒到 500 毫秒之間。大多數(shù)的服務(wù)器的平均故障間隔時(shí)間都在幾個(gè)月甚至更長，很容易滿足時(shí)間的要求。
6 集群成員變更
到目前為止，我們都假設(shè)集群的配置（參與一致性算法的服務(wù)器集合）是固定不變的。但是在實(shí)踐中，偶爾會(huì)改變集群的配置的，例如替換那些宕機(jī)的機(jī)器或者改變復(fù)制程度。盡管可以通過使整個(gè)集群下線，更新所有配置，然后重啟整個(gè)集群的方式來實(shí)現(xiàn)，但是在更改期間集群會(huì)不可用。另外，如果存在手工操作步驟，那么就會(huì)有操作失誤的風(fēng)險(xiǎn)。為了避免這樣的問題，我們決定將配置變更自動(dòng)化并將其納入到 Raft 一致性算法中來。
為了使配置變更機(jī)制能夠安全，在轉(zhuǎn)換的過程中不能夠存在任何時(shí)間點(diǎn)使得同一個(gè)任期里可能選出兩個(gè) leader 。不幸的是，任何服務(wù)器直接從舊的配置轉(zhuǎn)換到新的配置的方案都是不安全的。一次性自動(dòng)地轉(zhuǎn)換所有服務(wù)器是不可能的，所以在轉(zhuǎn)換期間整個(gè)集群可能劃分成兩個(gè)獨(dú)立的大多數(shù)（見圖 10）。
圖 10：直接從一種配置轉(zhuǎn)到另一種配置是不安全的，因?yàn)楦鱾€(gè)機(jī)器會(huì)在不同的時(shí)候進(jìn)行轉(zhuǎn)換。在這個(gè)例子中，集群從 3 臺機(jī)器變成了 5 臺。不幸的是，存在這樣的一個(gè)時(shí)間點(diǎn)，同一個(gè)任期里兩個(gè)不同的 leader 會(huì)被選出。一個(gè)獲得舊配置里過半機(jī)器的投票，一個(gè)獲得新配置里過半機(jī)器的投票。
為了保證安全性，配置變更必須采用一種兩階段方法。目前有很多種兩階段的實(shí)現(xiàn)。例如，有些系統(tǒng)（比如，[22]）在第一階段停掉舊的配置所以不能處理客戶端請求；然后在第二階段在啟用新的配置。在 Raft 中，集群先切換到一個(gè)過渡的配置，我們稱之為聯(lián)合一致（joint consensus）；一旦聯(lián)合一致已經(jīng)被提交了，那么系統(tǒng)就切換到新的配置上。聯(lián)合一致結(jié)合了老配置和新配置：
- 日志條目被復(fù)制給集群中新、老配置的所有服務(wù)器。
- 新、舊配置的服務(wù)器都可以成為 leader 。
- 達(dá)成一致（針對選舉和提交）需要分別在兩種配置上獲得過半的支持。
聯(lián)合一致允許獨(dú)立的服務(wù)器在不妥協(xié)安全性的前提下，在不同的時(shí)刻進(jìn)行配置轉(zhuǎn)換過程。此外，聯(lián)合一致允許集群在配置變更期間依然響應(yīng)客戶端請求。
集群配置在復(fù)制日志中以特殊的日志條目來存儲(chǔ)和通信；圖 11 展示了配置變更過程。當(dāng)一個(gè) leader 接收到一個(gè)改變配置從 C-old 到 C-new 的請求，它就為聯(lián)合一致將該配置（圖中的 C-old,new）存儲(chǔ)為一個(gè)日志條目，并以前面描述的方式復(fù)制該條目。一旦某個(gè)服務(wù)器將該新配置日志條目增加到自己的日志中，它就會(huì)用該配置來做出未來所有的決策（服務(wù)器總是使用它日志中最新的配置，無論該配置日志是否已經(jīng)被提交）。這就意味著 leader 會(huì)使用 C-old,new 的規(guī)則來決定 C-old,new 的日志條目是什么時(shí)候被提交的。如果 leader 崩潰了，新 leader 可能是在 C-old 配置也可能是在 C-old,new 配置下選出來的，這取決于贏得選舉的 candidate 是否已經(jīng)接收到了 C-old,new 配置。在任何情況下， C-new 在這一時(shí)期都不能做出單方面決定。
一旦 C-old,new 被提交，那么 C-old 和 C-new 都不能在沒有得到對方認(rèn)可的情況下做出決定，并且 leader 完整性特性保證了只有擁有 C-old,new 日志條目的服務(wù)器才能被選舉為 leader ?，F(xiàn)在 leader 創(chuàng)建一個(gè)描述 C-new 配置的日志條目并復(fù)制到集群其他節(jié)點(diǎn)就是安全的了。此外，新的配置被服務(wù)器收到后就會(huì)立即生效。當(dāng)新的配置在 C-new 的規(guī)則下被提交，舊的配置就變得無關(guān)緊要，同時(shí)不使用新配置的服務(wù)器就可以被關(guān)閉了。如圖 11 所示，任何時(shí)刻 C-old 和 C-new 都不能單方面做出決定；這保證了安全性。
在關(guān)于配置變更還有三個(gè)問題需要解決。第一個(gè)問題是，新的服務(wù)器開始時(shí)可能沒有存儲(chǔ)任何的日志條目。當(dāng)這些服務(wù)器以這種狀態(tài)加入到集群中，它們需要一段時(shí)間來更新來趕上其他服務(wù)器，這段它們無法提交新的日志條目。為了避免因此而造成的系統(tǒng)短時(shí)間的不可用，Raft 在配置變更前引入了一個(gè)額外的階段，在該階段，新的服務(wù)器以沒有投票權(quán)身份加入到集群中來（leader 也復(fù)制日志給它們，但是考慮過半的時(shí)候不用考慮它們）。一旦該新的服務(wù)器追趕上了集群中的其他機(jī)器，配置變更就可以按上面描述的方式進(jìn)行。
第二個(gè)問題是，集群的 leader 可能不是新配置中的一員。在這種情況下，leader 一旦提交了 C-new 日志條目就會(huì)退位（回到 follower 狀態(tài)）。這意味著有這樣的一段時(shí)間（leader 提交 C-new 期間），leader 管理著一個(gè)不包括自己的集群；它復(fù)制著日志但不把自己算在過半里面。Leader 轉(zhuǎn)換發(fā)生在 C-new 被提交的時(shí)候，因?yàn)檫@是新配置可以獨(dú)立運(yùn)轉(zhuǎn)的最早時(shí)刻（將總是能夠在 C-new 配置下選出新的領(lǐng)導(dǎo)人）。在此之前，可能只能從 C-old 中選出領(lǐng)導(dǎo)人。
第三個(gè)問題是，那些被移除的服務(wù)器（不在 C-new 中）可能會(huì)擾亂集群。這些服務(wù)器將不會(huì)再接收到心跳，所以當(dāng)選舉超時(shí)，它們就會(huì)進(jìn)行新的選舉過程。它們會(huì)發(fā)送帶有新任期號的 RequestVote RPCs ，這樣會(huì)導(dǎo)致當(dāng)前的 leader 回到 follower 狀態(tài)。新的 leader 最終會(huì)被選出來，但是被移除的服務(wù)器將會(huì)再次超時(shí)，然后這個(gè)過程會(huì)再次重復(fù)，導(dǎo)致系統(tǒng)可用性很差。
為了防止這種問題，當(dāng)服務(wù)器認(rèn)為當(dāng)前 leader 存在時(shí)，服務(wù)器會(huì)忽略RequestVote RPCs 。特別的，當(dāng)服務(wù)器在最小選舉超時(shí)時(shí)間內(nèi)收到一個(gè) RequestVote RPC，它不會(huì)更新任期號或者投票。這不會(huì)影響正常的選舉，每個(gè)服務(wù)器在開始一次選舉之前，至少等待最小選舉超時(shí)時(shí)間。相反，這有利于避免被移除的服務(wù)器的擾亂：如果 leader 能夠發(fā)送心跳給集群，那它就不會(huì)被更大的任期號廢黜。
7 日志壓縮
Raft 的日志在正常操作中隨著包含更多的客戶端請求不斷地增長，但是在實(shí)際的系統(tǒng)中，日志不能無限制地增長。隨著日志越來越長，它會(huì)占用越來越多的空間，并且需要花更多的時(shí)間來回放。如果沒有一定的機(jī)制來清除日志中積累的過期的信息，最終就會(huì)帶來可用性問題。
快照技術(shù)是日志壓縮最簡單的方法。在快照技術(shù)中，整個(gè)當(dāng)前系統(tǒng)的狀態(tài)都以快照的形式持久化到穩(wěn)定的存儲(chǔ)中，該時(shí)間點(diǎn)之前的日志全部丟棄。快照技術(shù)被使用在 Chubby 和 ZooKeeper 中，接下來的章節(jié)會(huì)介紹 Raft 中的快照技術(shù)。
增量壓縮方法，例如日志清理或者日志結(jié)構(gòu)合并樹（log-structured merge trees，LSM 樹），都是可行的。這些方法每次只對一小部分?jǐn)?shù)據(jù)進(jìn)行操作，這樣就分散了壓縮的負(fù)載壓力。首先，它們先選擇一個(gè)積累了大量已經(jīng)被刪除或者被覆蓋的對象的數(shù)據(jù)區(qū)域，然后重寫該區(qū)域還活著的對象，之后釋放該區(qū)域。和快照技術(shù)相比，它們需要大量額外的機(jī)制和復(fù)雜性，快照技術(shù)通過操作整個(gè)數(shù)據(jù)集來簡化該問題。狀態(tài)機(jī)可以用和快照技術(shù)相同的接口來實(shí)現(xiàn) LSM 樹，但是日志清除方法就需要修改 Raft 了。
一臺服務(wù)器用一個(gè)新快照替代了它日志中已經(jīng)提交了的條目（索引 1 到 5），該快照只存儲(chǔ)了當(dāng)前的狀態(tài)（變量 x 和 y 的值）?？煺盏?last included index 和 last included term 被保存來定位日志中條目 6 之前的快照
圖 12 展示了 Raft 中快照的基本思想。每個(gè)服務(wù)器獨(dú)立地創(chuàng)建快照，快照只包括自己日志中已經(jīng)被提交的條目。主要的工作是狀態(tài)機(jī)將自己的狀態(tài)寫入快照中。Raft 快照中也包含了少量的元數(shù)據(jù)：the last included index 指的是最后一個(gè)被快照取代的日志條目的索引值（狀態(tài)機(jī)最后應(yīng)用的日志條目），the last included term 是該條目的任期號。保留這些元數(shù)據(jù)是為了支持快照后第一個(gè)條目的 AppendEntries 一致性檢查，因?yàn)樵摋l目需要之前的索引值和任期號。為了支持集群成員變更（第 6 節(jié)），快照中也包括日志中最新的配置作為 last included index 。一旦服務(wù)器完成寫快照，他就可以刪除 last included index 之前的所有日志條目，包括之前的快照。
盡管通常服務(wù)器都是獨(dú)立地創(chuàng)建快照，但是 leader 必須偶爾發(fā)送快照給一些落后的跟隨者。這通常發(fā)生在 leader 已經(jīng)丟棄了需要發(fā)送給 follower 的下一條日志條目的時(shí)候。幸運(yùn)的是這種情況在常規(guī)操作中是不可能的：一個(gè)與 leader 保持同步的 follower 通常都會(huì)有該日志條目。然而一個(gè)例外的運(yùn)行緩慢的 follower 或者新加入集群的服務(wù)器（第 6 節(jié)）將不會(huì)有這個(gè)條目。這時(shí)讓該 follower 更新到最新的狀態(tài)的方式就是通過網(wǎng)絡(luò)把快照發(fā)送給它。
Leader 使用 InstallSnapshot RPC 來發(fā)送快照給太落后的 follower ；見圖 13。當(dāng) follower 收到帶有這種 RPC 的快照時(shí)，它必須決定如何處理已經(jīng)存在的日志條目。通常該快照會(huì)包含接收者日志中沒有的信息。在這種情況下，follower 丟棄它所有的日志；這些會(huì)被該快照所取代，并且可能一些沒有提交的條目會(huì)和該快照產(chǎn)生沖突。如果接收到的快照是自己日志的前面部分（由于網(wǎng)絡(luò)重傳或者錯(cuò)誤），那么被快照包含的條目將會(huì)被全部刪除，但是快照之后的條目仍然有用并保留。
這種快照的方式違反了 Raft 的 strong leader 原則，因?yàn)?follower 可以在不知道 leader 狀態(tài)的情況下創(chuàng)建快照。但是我們認(rèn)為這種違背是合乎情理的。Leader 的存在，是為了防止在達(dá)成一致性的時(shí)候的沖突，但是在創(chuàng)建快照的時(shí)候，一致性已經(jīng)達(dá)成，因此沒有決策會(huì)沖突。數(shù)據(jù)依然只能從 leader 流到 follower ，只是 follower 可以重新組織它們的數(shù)據(jù)了。
我們考慮過一種可替代的基于 leader 的快照方案，在該方案中，只有l(wèi)eader 會(huì)創(chuàng)建快照，然后 leader 會(huì)發(fā)送它的快照給所有的 follower 。但是這樣做有兩個(gè)缺點(diǎn)。第一，發(fā)送快照會(huì)浪費(fèi)網(wǎng)絡(luò)帶寬并且延緩了快照過程。每個(gè) follower 都已經(jīng)擁有了創(chuàng)建自己的快照所需要的信息，而且很顯然，follower 從本地的狀態(tài)中創(chuàng)建快照遠(yuǎn)比通過網(wǎng)絡(luò)接收別人發(fā)來的要來得經(jīng)濟(jì)。第二，leader 的實(shí)現(xiàn)會(huì)更加復(fù)雜。例如，leader 發(fā)送快照給 follower 的同時(shí)也要并行地將新的日志條目發(fā)送給它們，這樣才不會(huì)阻塞新的客戶端請求。
還有兩個(gè)問題會(huì)影響快照的性能。首先，服務(wù)器必須決定什么時(shí)候創(chuàng)建快照。如果快照創(chuàng)建過于頻繁，那么就會(huì)浪費(fèi)大量的磁盤帶寬和其他資源；如果創(chuàng)建快照頻率太低，就要承擔(dān)耗盡存儲(chǔ)容量的風(fēng)險(xiǎn)，同時(shí)也增加了重啟時(shí)日志回放的時(shí)間。一個(gè)簡單的策略就是當(dāng)日志大小達(dá)到一個(gè)固定大小的時(shí)候就創(chuàng)建一次快照。如果這個(gè)閾值設(shè)置得顯著大于期望的快照的大小，那么快照的磁盤帶寬負(fù)載就會(huì)很小。
第二個(gè)性能問題就是寫入快照需要花費(fèi)一段時(shí)間，并且我們不希望它影響到正常的操作。解決方案是通過寫時(shí)復(fù)制的技術(shù)，這樣新的更新就可以在不影響正在寫的快照的情況下被接收。例如，具有泛函數(shù)據(jù)結(jié)構(gòu)的狀態(tài)機(jī)天然支持這樣的功能。另外，操作系統(tǒng)對寫時(shí)復(fù)制技術(shù)的支持（如 Linux 上的 fork）可以被用來創(chuàng)建整個(gè)狀態(tài)機(jī)的內(nèi)存快照（我們的實(shí)現(xiàn)用的就是這種方法）。
8 客戶端交互
本節(jié)介紹客戶端如何和 Raft 進(jìn)行交互，包括客戶端如何找到 leader 和 Raft 是如何支持線性化語義的。這些問題對于所有基于一致性的系統(tǒng)都存在，并且 Raft 的解決方案和其他的也差不多。
Raft 的客戶端發(fā)送所有的請求給 leader 。當(dāng)客戶端第一次啟動(dòng)的時(shí)候，它會(huì)隨機(jī)挑選一個(gè)服務(wù)器進(jìn)行通信。如果客戶端第一次挑選的服務(wù)器不是 leader ，那么該服務(wù)器會(huì)拒絕客戶端的請求并且提供關(guān)于它最近接收到的領(lǐng)導(dǎo)人的信息（AppendEntries 請求包含了 leader 的網(wǎng)絡(luò)地址）。如果 leader 已經(jīng)崩潰了，客戶端請求就會(huì)超時(shí)；客戶端之后會(huì)再次隨機(jī)挑選服務(wù)器進(jìn)行重試。
我們 Raft 的目標(biāo)是要實(shí)現(xiàn)線性化語義（每一次操作立即執(zhí)行，只執(zhí)行一次，在它的調(diào)用和回復(fù)之間）。但是，如上述，Raft 可能執(zhí)行同一條命令多次：例如，如果 leader 在提交了該日志條目之后，響應(yīng)客戶端之前崩潰了，那么客戶端會(huì)和新的 leader 重試這條指令，導(dǎo)致這條命令被再次執(zhí)行。解決方案就是客戶端對于每一條指令都賦予一個(gè)唯一的序列號。然后，狀態(tài)機(jī)跟蹤每個(gè)客戶端已經(jīng)處理的最新的序列號以及相關(guān)聯(lián)的回復(fù)。如果接收到一條指令，該指令的序列號已經(jīng)被執(zhí)行過了，就立即返回結(jié)果，而不重新執(zhí)行該請求。
只讀的操作可以直接處理而不需要記錄日志。但是，如果不采取任何其他措施，這么做可能會(huì)有返回過時(shí)數(shù)據(jù)（stale data）的風(fēng)險(xiǎn)，因?yàn)?leader 響應(yīng)客戶端請求時(shí)可能已經(jīng)被新的 leader 替代了，但是它還不知道自己已經(jīng)不是最新的 leader 了。線性化的讀操作肯定不會(huì)返回過時(shí)數(shù)據(jù)，Raft 需要使用兩個(gè)額外的預(yù)防措施來在不使用日志的情況下保證這一點(diǎn)。首先，leader 必須有關(guān)于哪些日志條目被提交了的最新信息。Leader 完整性特性保證了 leader 一定擁有所有已經(jīng)被提交的日志條目，但是在它任期開始的時(shí)候，它可能不知道哪些是已經(jīng)被提交的。為了知道這些信息，它需要在它的任期里提交一個(gè)日志條目。Raft 通過讓 leader 在任期開始的時(shí)候提交一個(gè)空的沒有任何操作的日志條目到日志中來處理該問題。第二，leader 在處理只讀請求之前必須檢查自己是否已經(jīng)被替代了（如果一個(gè)更新的 leader 被選舉出來了，它的信息就是過時(shí)的了）。Raft 通過讓 leader 在響應(yīng)只讀請求之前，先和集群中的過半節(jié)點(diǎn)交換一次心跳信息來處理該問題。另一種可選的方案，leader 可以依賴心跳機(jī)制來實(shí)現(xiàn)一種租約的形式，但是這種方法依賴 timing 來保證安全性（假設(shè)時(shí)間誤差是有界的）。
可進(jìn)入我的博客查看原文。
