Raft 论文翻译
目錄
1.?介紹
2.?復(fù)制狀態(tài)機(jī)
3.?Paxos算法的問題
4.?為了可理解性的設(shè)計(jì)
5.?Raft一致性算法
6.?集群成員變化
7.?日志壓縮
8.?客戶端交互
9.?算法實(shí)現(xiàn)和評(píng)估
10.?相關(guān)工作
11.?結(jié)論
In Search of an Understandable Consensus Algorithm?(Extended Version)
尋找一種易于理解的一致性算法（擴(kuò)展版）
摘要
Raft是一種為了管理復(fù)制日志的一致性算法。它提供了和 Paxos算法相同的功能和性能，但是它的算法結(jié)構(gòu)和 Paxos不同，使得Raft算法更加容易理解并且更容易構(gòu)建實(shí)際的系統(tǒng)。為了提升可理解性，Raft將一致性算法分解成了幾個(gè)關(guān)鍵模塊，例如Leader選舉、日志復(fù)制和安全性。同時(shí)它通過實(shí)施一個(gè)更強(qiáng)的一致性來減少需要考慮的狀態(tài)的數(shù)量。從一個(gè)用戶研究的結(jié)果可以證明，對(duì)于學(xué)生而言，Raft算法比 Paxos算法更加容易學(xué)習(xí)。Raft算法還包括一個(gè)新的機(jī)制來允許集群成員的動(dòng)態(tài)改變，它利用重疊的大多數(shù)來保證安全性。
?
1.?介紹
一致性算法允許一組機(jī)器像一個(gè)整體一樣工作，即使其中一些機(jī)器出現(xiàn)故障也能夠繼續(xù)工作下去。正因如此，一致性算法在構(gòu)建可信賴的大規(guī)模軟件系統(tǒng)中扮演著重要的角色。在過去的 10 年里，Paxos算法統(tǒng)治著一致性算法這一領(lǐng)域：絕大多數(shù)的實(shí)現(xiàn)都是基于 Paxos或者受其影響。同時(shí) Paxos也成為了教學(xué)領(lǐng)域里講解一致性問題時(shí)的示例。
但是不幸的是，盡管有很多工作都在嘗試降低它的復(fù)雜性，但是 Paxos算法依然十分難以理解。并且，Paxos自身的算法結(jié)構(gòu)需要進(jìn)行大幅的修改才能夠應(yīng)用到實(shí)際的系統(tǒng)中。這些都導(dǎo)致了工業(yè)界和學(xué)術(shù)界都對(duì) Paxos算法感到十分頭疼。
和 Paxos算法進(jìn)行過努力之后，我們開始尋找一種新的一致性算法，可以為構(gòu)建實(shí)際的系統(tǒng)和教學(xué)提供更好的基礎(chǔ)。我們的做法是不尋常的，我們的首要目標(biāo)是可理解性：我們是否可以在實(shí)際系統(tǒng)中定義一個(gè)一致性算法，并且能夠比 Paxos算法以一種更加容易的方式來學(xué)習(xí)。此外，我們希望該算法方便系統(tǒng)構(gòu)建者的直覺的發(fā)展。一個(gè)算法能夠工作是很重要的，而且能夠知道為什么能工作也很重要。
Raft一致性算法就是這些工作的結(jié)果。在設(shè)計(jì)Raft算法的時(shí)候，我們使用一些特別的技巧來提升它的可理解性，包括算法分解（Raft主要被分成了Leader選舉，日志復(fù)制和安全三個(gè)模塊）和減少狀態(tài)機(jī)的狀態(tài)（相對(duì)于 Paxos，Raft減少了非確定性和服務(wù)器互相處于非一致性的方式）。一份針對(duì)兩所大學(xué) 43 個(gè)學(xué)生的研究表明Raft明顯比 Paxos算法更加容易理解。在這些學(xué)生同時(shí)學(xué)習(xí)了這兩種算法之后，和 Paxos比起來，其中 33 個(gè)學(xué)生能夠回答有關(guān)于Raft的問題。
Raft算法在許多方面和現(xiàn)有的一致性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是它也有一些獨(dú)特的特性：
強(qiáng)領(lǐng)導(dǎo)者(Strong leader)：和其它一致性算法相比，Raft使用一種更強(qiáng)的領(lǐng)導(dǎo)能力形式。比如，日志條目只從領(lǐng)導(dǎo)者發(fā)送給其它的服務(wù)器。這種方式簡化了對(duì)復(fù)制日志的管理并且使得Raft算法更加易于理解。
領(lǐng)導(dǎo)選舉(Leader election)：Raft算法使用一個(gè)隨機(jī)計(jì)時(shí)器來選舉領(lǐng)導(dǎo)者。這種方式只是在任何一致性算法都必須實(shí)現(xiàn)的心跳機(jī)制上增加了一點(diǎn)機(jī)制。在解決沖突的時(shí)候會(huì)更加簡單快捷。
成員關(guān)系調(diào)整(Membership changes)：Raft使用一種共同一致的方法來處理集群成員變換的問題，在這種方法下，處于調(diào)整過程中的兩種不同的配置集群中大多數(shù)機(jī)器會(huì)有重疊，這就使得集群在成員變換的時(shí)候依然可以繼續(xù)工作。
?
我們相信，Raft算法不論出于教學(xué)目的還是作為實(shí)踐項(xiàng)目的基礎(chǔ)都是要比 Paxos或者其它一致性算法要優(yōu)異的。它比其它算法更加簡單，更加容易理解；它的算法描述足以實(shí)現(xiàn)一個(gè)現(xiàn)實(shí)的系統(tǒng)；它有好多開源的實(shí)現(xiàn)并且在很多公司里使用；它的安全性已經(jīng)被證明；它的效率和其它算法比起來也不相上下。
接下來，這篇論文會(huì)介紹以下內(nèi)容：復(fù)制狀態(tài)機(jī)問題（第 2 節(jié)），討論 Paxos的優(yōu)點(diǎn)和缺點(diǎn)（第 3 節(jié)），討論我們?yōu)榱丝衫斫庑远扇〉姆椒?#xff08;第 4 節(jié)），闡述Raft一致性算法（第 5-8 節(jié)），評(píng)價(jià)Raft算法（第 9 節(jié)），以及一些相關(guān)的工作（第 10 節(jié)）。
?
2.?復(fù)制狀態(tài)機(jī)
一致性算法是從復(fù)制狀態(tài)機(jī)的背景下提出的。在這種方法中，一組服務(wù)器上的狀態(tài)機(jī)產(chǎn)生相同狀態(tài)的副本，并且在一些機(jī)器宕掉的情況下也可以繼續(xù)運(yùn)行。復(fù)制狀態(tài)機(jī)在分布式系統(tǒng)中被用于解決很多容錯(cuò)的問題。例如，大規(guī)模的系統(tǒng)中通常都有一個(gè)集群領(lǐng)導(dǎo)者，像 GFS、HDFS 和 RAMCloud，典型應(yīng)用就是一個(gè)獨(dú)立的的復(fù)制狀態(tài)機(jī)去管理Leader選舉和存儲(chǔ)配置信息并且在Leader宕機(jī)的情況下也要存活下來。比如 Chubby 和 ZooKeeper。
圖1：復(fù)制狀態(tài)機(jī)的結(jié)構(gòu)。一致性算法管理著來自客戶端指令的復(fù)制日志。狀態(tài)機(jī)從日志中處理相同順序的相同指令，所以產(chǎn)生的結(jié)果也是相同的。
復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實(shí)現(xiàn)的，如圖 1。每一個(gè)服務(wù)器存儲(chǔ)一個(gè)包含一系列指令的日志，并且按照日志的順序進(jìn)行執(zhí)行。每一個(gè)日志都按照相同的順序包含相同的指令，所以每一個(gè)服務(wù)器都執(zhí)行相同的指令序列。因?yàn)槊總€(gè)狀態(tài)機(jī)都是確定的，每一次執(zhí)行操作都產(chǎn)生相同的狀態(tài)和同樣的序列。
保證復(fù)制日志相同就是一致性算法的工作了。在一臺(tái)服務(wù)器上，一致性模塊接收客戶端發(fā)送來的指令然后增加到自己的日志中去。它和其它服務(wù)器上的一致性模塊進(jìn)行通信來保證每一個(gè)服務(wù)器上的日志最終都以相同的順序包含相同的請(qǐng)求，盡管有些服務(wù)器會(huì)宕機(jī)。一旦指令被正確的復(fù)制，每一個(gè)服務(wù)器的狀態(tài)機(jī)按照日志順序處理它們，然后輸出結(jié)果被返回給客戶端。因此，服務(wù)器集群看起來形成一個(gè)高可靠的狀態(tài)機(jī)。
實(shí)際系統(tǒng)中使用的一致性算法通常含有以下特性：
?
3.?Paxos算法的問題
在過去的 10 年里，Leslie Lamport 的 Paxos算法幾乎已經(jīng)成為一致性的代名詞：Paxos是在課程教學(xué)中最經(jīng)常使用的算法，同時(shí)也是大多數(shù)一致性算法實(shí)現(xiàn)的起點(diǎn)。Paxos首先定義了一個(gè)能夠達(dá)成單一決策一致的協(xié)議，比如單條的復(fù)制日志項(xiàng)。我們把這一子集叫做單決策 Paxos。然后通過組合多個(gè) Paxos協(xié)議的實(shí)例來促進(jìn)一系列決策的達(dá)成。Paxos保證安全性和活性，同時(shí)也支持集群成員關(guān)系的變更。Paxos的正確性已經(jīng)被證明，在通常情況下也很高效。
不幸的是，Paxos有兩個(gè)明顯的缺點(diǎn)。第一個(gè)缺點(diǎn)是 Paxos算法特別的難以理解。完整的解釋是出了名的不透明；通過極大的努力之后，也只有少數(shù)人成功理解了這個(gè)算法。因此，有了幾次用更簡單的術(shù)語來解釋 Paxos的嘗試。盡管這些解釋都只關(guān)注了單決策的子集問題，但依然很具有挑戰(zhàn)性。在 2012 年 NSDI 的會(huì)議中的一次調(diào)查顯示，很少有人對(duì) Paxos算法感到滿意，甚至在經(jīng)驗(yàn)老道的研究者中也是如此。我們自己也嘗試去理解 Paxos；我們一直沒能理解 Paxos直到我們讀了很多對(duì) Paxos的簡化解釋并且設(shè)計(jì)了我們自己的算法之后，這一過程花了近一年時(shí)間。
我們假設(shè) Paxos的不透明性來自它選擇單決策問題作為它的基礎(chǔ)。單決策 Paxos是晦澀微妙的，它被劃分成了兩種沒有簡單直觀解釋和無法獨(dú)立理解的情景。因此，這導(dǎo)致了很難建立起直觀的感受為什么單決策 Paxos算法能夠工作。構(gòu)成多決策 Paxos增加了很多錯(cuò)綜復(fù)雜的規(guī)則。我們相信，在多決策上達(dá)成一致性的問題（一份日志而不是單一的日志記錄）能夠被分解成其它的方式并且更加直接和明顯。
Paxos算法的第二個(gè)問題就是它沒有提供一個(gè)足夠好的用來構(gòu)建一個(gè)現(xiàn)實(shí)系統(tǒng)的基礎(chǔ)。一個(gè)原因是還沒有一種被廣泛認(rèn)同的多決策問題的算法。Lamport 的描述基本上都是關(guān)于單決策 Paxos的；它簡要描述了實(shí)施多決策 Paxos的方法，但是缺乏很多細(xì)節(jié)。當(dāng)然也有很多具體化 Paxos的嘗試，但是它們都互相不一樣，和 Paxos的概述也不同。例如 Chubby 這樣的系統(tǒng)實(shí)現(xiàn)了一個(gè)類似于 Paxos的算法，但是大多數(shù)的細(xì)節(jié)并沒有被公開。
而且，Paxos算法的結(jié)構(gòu)也不是十分易于構(gòu)建實(shí)踐的系統(tǒng)；單決策分解也會(huì)產(chǎn)生其它的結(jié)果。例如，獨(dú)立的選擇一組日志條目然后合并成一個(gè)序列化的日志并沒有帶來太多的好處，僅僅增加了不少復(fù)雜性。圍繞著日志來設(shè)計(jì)一個(gè)系統(tǒng)是更加簡單高效的；新日志條目以嚴(yán)格限制的順序增添到日志中去。另一個(gè)問題是，Paxos使用了一種對(duì)等的點(diǎn)對(duì)點(diǎn)的方式作為它的核心（盡管它最終提議了一種弱Leader的方法來優(yōu)化性能）。在只有一個(gè)決策會(huì)被制定的簡化世界中是很有意義的，但是很少有現(xiàn)實(shí)的系統(tǒng)使用這種方式。如果有一系列的決策需要被制定，首先選擇一個(gè)Leader，然后讓它去協(xié)調(diào)所有的決議，會(huì)更加簡單快速。
因此，實(shí)際的系統(tǒng)中很少有和 Paxos相似的實(shí)踐。每一種實(shí)現(xiàn)都是從 Paxos開始研究，然后發(fā)現(xiàn)很多實(shí)現(xiàn)上的難題，再然后開發(fā)了一種和 Paxos明顯不一樣的結(jié)構(gòu)。這樣是非常費(fèi)時(shí)和容易出錯(cuò)的，并且理解 Paxos的難度使得這個(gè)問題更加糟糕。Paxos算法在理論上被證明是正確可行的，但是現(xiàn)實(shí)的系統(tǒng)和 Paxos差別是如此的大，以至于這些證明沒有什么太大的價(jià)值。下面來自 Chubby 實(shí)現(xiàn)非常典型：
由于以上問題，我們認(rèn)為 Paxos算法既沒有提供一個(gè)良好的基礎(chǔ)給實(shí)踐的系統(tǒng)，也沒有給教學(xué)很好的幫助。基于一致性問題在大規(guī)模軟件系統(tǒng)中的重要性，我們決定看看我們是否可以設(shè)計(jì)一個(gè)擁有更好特性的替代 Paxos的一致性算法。Raft算法就是這次實(shí)驗(yàn)的結(jié)果。
?
4.?為了可理解性的設(shè)計(jì)
設(shè)計(jì)Raft算法我們有幾個(gè)初衷：它必須提供一個(gè)完整的實(shí)際的系統(tǒng)實(shí)現(xiàn)基礎(chǔ)，這樣才能大大減少開發(fā)者的工作；它必須在任何情況下都是安全的并且在大多數(shù)的情況下都是可用的；并且它的大部分操作必須是高效的。但是我們最重要也是最大的挑戰(zhàn)是可理解性。它必須保證對(duì)于普遍的人群都可以十分容易的去理解。另外，它必須能夠讓人形成直觀的認(rèn)識(shí)，這樣系統(tǒng)的構(gòu)建者才能夠在現(xiàn)實(shí)中進(jìn)行必然的擴(kuò)展。
在設(shè)計(jì)Raft算法的時(shí)候，有很多的點(diǎn)需要我們?cè)诟鞣N備選方案中進(jìn)行選擇。在這種情況下，我們?cè)u(píng)估備選方案基于可理解性原則：解釋各個(gè)備選方案有多大的難度（例如，Raft的狀態(tài)空間有多復(fù)雜，是否有微妙的暗示）？對(duì)于一個(gè)讀者而言，完全理解這個(gè)方案和暗示是否容易？
我們意識(shí)到對(duì)這種可理解性分析上具有高度的主觀性；盡管如此，我們使用了兩種通常適用的技術(shù)來解決這個(gè)問題。第一個(gè)技術(shù)就是眾所周知的問題分解：只要有可能，我們就將問題分解成幾個(gè)相對(duì)獨(dú)立的，可被解決的、可解釋的和可理解的子問題。例如，Raft算法被我們分成Leader選舉，日志復(fù)制，安全性和角色改變幾個(gè)部分。
我們使用的第二個(gè)方法是通過減少狀態(tài)的數(shù)量來簡化需要考慮的狀態(tài)空間，使得系統(tǒng)更加連貫并且在可能的時(shí)候消除不確定性。特別的，所有的日志是不允許有空洞的，并且Raft限制了日志之間變成不一致狀態(tài)的可能。盡管在大多數(shù)情況下我們都試圖去消除不確定性，但是也有一些情況下不確定性可以提升可理解性。尤其是，隨機(jī)化方法增加了不確定性，但是它們有利于減少狀態(tài)空間數(shù)量，通過處理所有可能選擇時(shí)使用相似的方法。我們使用隨機(jī)化去簡化Raft中Leader選舉算法。
?
5.?Raft一致性算法
Raft是一種用來管理章節(jié) 2 中描述的復(fù)制日志的算法。圖 2 為了參考之用，總結(jié)這個(gè)算法的簡略版本，圖 3 列舉了這個(gè)算法的一些關(guān)鍵特性。圖中的這些元素會(huì)在剩下的章節(jié)逐一介紹。(接下來的4張圖是原論文中的圖2的內(nèi)容)
Raft通過選舉一個(gè)Leader，然后給予它全部的管理復(fù)制日志的責(zé)任來實(shí)現(xiàn)一致性。Leader從客戶端接收日志條目，把日志條目復(fù)制到其它服務(wù)器上，并且當(dāng)保證安全性的時(shí)候告訴其它的服務(wù)器應(yīng)用日志條目到它們的狀態(tài)機(jī)中。擁有一個(gè)Leader大大簡化了對(duì)復(fù)制日志的管理。例如，Leader可以決定新的日志條目需要放在日志中的什么位置而不需要和其它服務(wù)器商議，并且數(shù)據(jù)都從Leader流向其它服務(wù)器。一個(gè)Leader可以宕機(jī)，可以和其它服務(wù)器失去連接，這時(shí)一個(gè)新的Leader會(huì)被選舉出來。
通過Leader的方式，Raft將一致性問題分解成了三個(gè)相對(duì)獨(dú)立的子問題，這些問題會(huì)在接下來的子章節(jié)中進(jìn)行討論：
在展示一致性算法之后，這一章節(jié)會(huì)討論可用性的一些問題和計(jì)時(shí)在系統(tǒng)的作用。
狀態(tài)：
| currentTerm | 服務(wù)器最后一次知道的任期號(hào)（初始化為 0，持續(xù)遞增） |
| votedFor | 在當(dāng)前獲得選票的候選人的 Id |
| log[] | 日志條目集；每一個(gè)條目包含一個(gè)用戶狀態(tài)機(jī)執(zhí)行的指令，和收到時(shí)的任期號(hào) |
| commitIndex | 已知的最大的已經(jīng)被提交的日志條目的索引值 |
| lastApplied | 最后被應(yīng)用到狀態(tài)機(jī)的日志條目索引值（初始化為 0，持續(xù)遞增） |
| nextIndex[] | 對(duì)于每一個(gè)服務(wù)器，需要發(fā)送給他的下一個(gè)日志條目的索引值（初始化為領(lǐng)導(dǎo)人最后索引值加一） |
| matchIndex[] | 對(duì)于每一個(gè)服務(wù)器，已經(jīng)復(fù)制給他的日志的最高索引值 |
?
附加日志 RPC：
由Leader負(fù)責(zé)調(diào)用來復(fù)制日志指令；也會(huì)用作heartbeat
| term | 領(lǐng)導(dǎo)人的任期號(hào) |
| leaderId | 領(lǐng)導(dǎo)人的 Id，以便于跟隨者重定向請(qǐng)求 |
| prevLogIndex | 新的日志條目緊隨之前的索引值 |
| prevLogTerm | prevLogIndex 條目的任期號(hào) |
| entries[] | 準(zhǔn)備存儲(chǔ)的日志條目（表示心跳時(shí)為空；一次性發(fā)送多個(gè)是為了提高效率） |
| leaderCommit | 領(lǐng)導(dǎo)人已經(jīng)提交的日志的索引值 |
| term | 當(dāng)前的任期號(hào)，用于領(lǐng)導(dǎo)人去更新自己 |
| success | 跟隨者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志時(shí)為真 |
接收者實(shí)現(xiàn)：
1. 如果? term < currentTerm 就返回 false （5.1 節(jié)）
2. 如果日志在 prevLogIndex 位置處的日志條目的任期號(hào)和 prevLogTerm 不匹配，則返回 false （5.3 節(jié)）
3. 如果已經(jīng)存在的日志條目和新的產(chǎn)生沖突（索引值相同但是任期號(hào)不同），刪除這一條和之后所有的 （5.3 節(jié)）
4. 附加日志中尚未存在的任何新條目
5. 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志條目索引值中較小的一個(gè)
?
請(qǐng)求投票 RPC：
由候選人負(fù)責(zé)調(diào)用用來征集選票（5.2 節(jié)）
| term | 候選人的任期號(hào) |
| candidateId | 請(qǐng)求選票的候選人的 Id |
| lastLogIndex | 候選人的最后日志條目的索引值 |
| lastLogTerm | 候選人最后日志條目的任期號(hào) |
| term | 當(dāng)前任期號(hào)，以便于候選人去更新自己的任期號(hào) |
| voteGranted | 候選人贏得了此張選票時(shí)為真 |
接收者實(shí)現(xiàn)：
1. 如果? term < currentTerm? 返回 false （5.2 節(jié)）
2. 如果 votedFor 為空或者為 candidateId，并且候選人的日志至少和自己一樣新，那么就投票給它（5.2 節(jié)，5.4 節(jié)）
?
所有服務(wù)器需遵守的規(guī)則：
所有服務(wù)器：
Follower(5.2 節(jié))：
候選人(5.2 節(jié)）：
* 在轉(zhuǎn)變成候選人后就立即開始選舉過程
? ? ? ?* 自增當(dāng)前的任期號(hào)（currentTerm）
? ? ? ?* 給自己投票
? ? ? ?* 重置選舉超時(shí)計(jì)時(shí)器
? ? ? ?* 發(fā)送請(qǐng)求投票的 RPC 給其它所有服務(wù)器
* 如果接收到大多數(shù)服務(wù)器的選票，那么就變成Leader
* 如果接收到來自新的Leader的附加日志 RPC，轉(zhuǎn)變成Follower
* 如果選舉過程超時(shí)，再次發(fā)起一輪選舉
Leader：
* 一旦成為Leader：發(fā)送空的附加日志 RPC（心跳）給其它所有的服務(wù)器；在一定的空余時(shí)間之后不停的重復(fù)發(fā)送，以阻止Follower超時(shí)（5.2 節(jié)）
* ?如果接收到來自客戶端的請(qǐng)求：附加條目到本地日志中，在條目被應(yīng)用到狀態(tài)機(jī)后響應(yīng)客戶端（5.3 節(jié)）
* ?如果對(duì)于一個(gè)Follower，最后日志條目的索引值大于等于 nextIndex，那么：發(fā)送從 nextIndex 開始的所有日志條目：
? ? ? ?* 如果成功：更新相應(yīng)Follower的 nextIndex 和 matchIndex
? ? ? ?* 如果因?yàn)槿罩静灰恢露?#xff0c;減少 nextIndex 重試
* 如果存在一個(gè)滿足? N > commitIndex? 的 N，并且大多數(shù)的? matchIndex[i] ≥ N? 成立，并且? log[N].term == currentTerm? 成立，那么令 commitIndex 等于這個(gè) N （5.3 和 5.4 節(jié)）
圖2(上面4張圖)：一個(gè)關(guān)于Raft一致性算法的濃縮總結(jié)（不包括成員變換和日志壓縮）。左上框中的服務(wù)器行為描述為一組獨(dú)立且重復(fù)觸發(fā)的規(guī)則。第5.2條等章節(jié)編號(hào)表明了討論特殊特征的地方。
?
| 選舉安全特性 | 對(duì)于一個(gè)給定的任期號(hào)，最多只會(huì)有一個(gè)領(lǐng)導(dǎo)人被選舉出來（5.2 節(jié)） |
| 領(lǐng)導(dǎo)人只附加原則 | 領(lǐng)導(dǎo)人絕對(duì)不會(huì)刪除或者覆蓋自己的日志，只會(huì)增加（5.3 節(jié)） |
| 日志匹配原則 | 如果兩個(gè)日志在相同的索引位置的日志條目的任期號(hào)相同，那么我們就認(rèn)為這個(gè)日志從頭到這個(gè)索引位置之間全部完全相同（5.3 節(jié)） |
| 領(lǐng)導(dǎo)人完全特性 | 如果某個(gè)日志條目在某個(gè)任期號(hào)中已經(jīng)被提交，那么這個(gè)條目必然出現(xiàn)在更大任期號(hào)的所有領(lǐng)導(dǎo)人中（5.4 節(jié)） |
| 狀態(tài)機(jī)安全特性 | 如果一個(gè)領(lǐng)導(dǎo)人已經(jīng)在給定的索引值位置的日志條目應(yīng)用到狀態(tài)機(jī)中，那么其他任何的服務(wù)器在這個(gè)索引位置不會(huì)提交一個(gè)不同的日志（5.4.3 節(jié)） |
圖3：Raft在任何時(shí)候都保證以上的各個(gè)特性。
?
5.1?Raft基礎(chǔ)
一個(gè)Raft集群包含若干個(gè)服務(wù)器節(jié)點(diǎn)；通常是 5 個(gè)，這允許整個(gè)系統(tǒng)容忍 2 個(gè)節(jié)點(diǎn)的失效。在任何時(shí)刻，每一個(gè)服務(wù)器節(jié)點(diǎn)都處于這三個(gè)狀態(tài)之一：Leader、Follower或者Candidate。在通常情況下，系統(tǒng)中只有一個(gè)Leader并且其它的節(jié)點(diǎn)全部都是Follower。Follower都是被動(dòng)的：它們不會(huì)發(fā)送任何請(qǐng)求，只是簡單的響應(yīng)來自領(lǐng)導(dǎo)者或者Candidate的請(qǐng)求。Leader處理所有的客戶端請(qǐng)求（如果一個(gè)客戶端和Follower聯(lián)系，那么Follower會(huì)把請(qǐng)求重定向給Leader）。第三種狀態(tài)，Candidate，是用來在 5.2 節(jié)描述的選舉新Leader時(shí)使用。圖 4 展示了這些狀態(tài)和它們之間的轉(zhuǎn)換關(guān)系；這些轉(zhuǎn)換關(guān)系會(huì)在接下來進(jìn)行討論。
圖4：服務(wù)器狀態(tài)。Follower只響應(yīng)來自其它服務(wù)器的請(qǐng)求。如果Follower接收不到消息，那么它就會(huì)變成Candidate并發(fā)起一次選舉。獲得集群中大多數(shù)選票的Candidate將成為Leader。在一個(gè)任期內(nèi)，Leader一直直到自己宕機(jī)都會(huì)是領(lǐng)導(dǎo)者。
圖5：時(shí)間被劃分成一個(gè)個(gè)的任期，每個(gè)任期開始都是一次選舉。在選舉成功后，Leader會(huì)管理整個(gè)集群直到任期結(jié)束。有時(shí)候選舉會(huì)失敗，那么這個(gè)任期就會(huì)沒有Leader而結(jié)束。任期之間的切換可以在不同的時(shí)間不同的服務(wù)器上觀察到。
Raft把時(shí)間分割成任意長度的任期，如圖 5。任期用連續(xù)的整數(shù)標(biāo)記。每一段任期從一次**選舉**開始，就像章節(jié) 5.2 描述的一樣，一個(gè)或者多個(gè)候選人嘗試成為領(lǐng)導(dǎo)者。如果一個(gè)候選人贏得選舉，然后它就在接下來的任期內(nèi)充當(dāng)Leader的職責(zé)。在某些情況下，一次選舉過程會(huì)造成選票的瓜分。在這種情況下，這一任期會(huì)以沒有Leader結(jié)束；一個(gè)新的任期（和一次新的選舉）會(huì)很快重新開始。Raft保證了在一個(gè)給定的任期內(nèi)，最多只有一個(gè)領(lǐng)導(dǎo)者。
不同的服務(wù)器節(jié)點(diǎn)可能多次觀察到任期之間的轉(zhuǎn)換，但在某些情況下，一個(gè)節(jié)點(diǎn)也可能觀察不到任何一次選舉或者整個(gè)任期全程。任期在Raft算法中充當(dāng)邏輯時(shí)鐘的作用，這會(huì)允許服務(wù)器節(jié)點(diǎn)查明一些過期的信息比如陳舊的領(lǐng)導(dǎo)者。每一個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)當(dāng)前任期號(hào)，這一編號(hào)在整個(gè)時(shí)期內(nèi)單調(diào)的增長。當(dāng)服務(wù)器之間通信的時(shí)候會(huì)交換當(dāng)前任期號(hào)；如果一個(gè)服務(wù)器的當(dāng)前任期號(hào)比其它人小，那么它會(huì)更新自己的編號(hào)到較大的編號(hào)值。如果一個(gè)候選人或者領(lǐng)導(dǎo)者發(fā)現(xiàn)自己的任期號(hào)過期了，那么它會(huì)立即恢復(fù)成Follower狀態(tài)。如果一個(gè)節(jié)點(diǎn)接收到一個(gè)包含過期的任期號(hào)的請(qǐng)求，那么它會(huì)直接拒絕這個(gè)請(qǐng)求。
Raft算法中服務(wù)器節(jié)點(diǎn)之間通信使用遠(yuǎn)程過程調(diào)用（RPCs），并且基本的一致性算法只需要兩種類型的 RPCs。請(qǐng)求投票（RequestVote） RPCs 由候選人在選舉期間發(fā)起（章節(jié) ?5.2），然后附加條目（AppendEntries）RPCs 由Leader發(fā)起，用來復(fù)制日志和提供一種心跳機(jī)制（章節(jié) 5.3）。第 7 節(jié)為了在服務(wù)器之間傳輸快照增加了第三種 RPC。當(dāng)服務(wù)器沒有及時(shí)的收到 RPC 的響應(yīng)時(shí)，會(huì)進(jìn)行重試， 并且它們能夠并行的發(fā)起 RPCs 來獲得最佳的性能。
?
5.2 Leader選舉
Raft使用一種心跳機(jī)制來觸發(fā)Leader選舉。當(dāng)服務(wù)器程序啟動(dòng)時(shí)，它們都是Follower身份。一個(gè)服務(wù)器節(jié)點(diǎn)繼續(xù)保持著Follower狀態(tài)只要它從Leader或者候選者處接收到有效的 RPCs。領(lǐng)導(dǎo)者周期性的向所有Follower發(fā)送心跳包（即不包含日志項(xiàng)內(nèi)容的附加日志項(xiàng) RPCs）來維持自己的權(quán)威。如果一個(gè)Follower在一段時(shí)間里沒有接收到任何消息，也就是**選舉超時(shí)**，那么它就會(huì)認(rèn)為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者,并且發(fā)起選舉以選出新的領(lǐng)導(dǎo)者。
要開始一次選舉過程，Follower先要增加自己的當(dāng)前任期號(hào)并且轉(zhuǎn)換到候選人狀態(tài)。然后它會(huì)并行的向集群中的其它服務(wù)器節(jié)點(diǎn)發(fā)送請(qǐng)求投票的 RPCs 來給自己投票。候選人會(huì)繼續(xù)保持著當(dāng)前狀態(tài)直到以下三件事情之一發(fā)生：(a) 它自己贏得了這次的選舉，(b) 其它的服務(wù)器成為領(lǐng)導(dǎo)者，(c) 一段時(shí)間之后沒有任何一個(gè)獲勝的人。這些結(jié)果會(huì)分別的在下面的段落里進(jìn)行討論。
當(dāng)一個(gè)候選人從整個(gè)集群的大多數(shù)服務(wù)器節(jié)點(diǎn)獲得了針對(duì)同一個(gè)任期號(hào)的選票，那么它就贏得了這次選舉并成為Leader。每一個(gè)服務(wù)器最多會(huì)對(duì)一個(gè)任期號(hào)投出一張選票，按照先來先服務(wù)的原則（注意：5.4 節(jié)在投票上增加了一點(diǎn)額外的限制）。要求大多數(shù)選票的規(guī)則確保了最多只會(huì)有一個(gè)候選人贏得此次選舉（圖 3 中的選舉安全性）。一旦候選人贏得選舉，它就立即成為Leader。然后它會(huì)向其它的服務(wù)器發(fā)送心跳消息來建立自己的權(quán)威并且阻止新的Leader的產(chǎn)生。
在等待投票的時(shí)候，候選人可能會(huì)從其它的服務(wù)器接收到聲明它是Leader的附加日志項(xiàng) RPC。如果這個(gè)Leader的任期號(hào)（包含在此次的 RPC中）不小于候選人當(dāng)前的任期號(hào)，那么候選人會(huì)承認(rèn)Leader合法并回到Follower狀態(tài)。 如果此次 RPC 中的任期號(hào)比自己小，那么候選人就會(huì)拒絕這次的 RPC 并且繼續(xù)保持候選人狀態(tài)。
第三種可能的結(jié)果是候選人既沒有贏得選舉也沒有輸：如果有多個(gè)Follower同時(shí)成為候選人，那么選票可能會(huì)被瓜分以至于沒有候選人可以贏得大多數(shù)人的支持。當(dāng)這種情況發(fā)生的時(shí)候，每一個(gè)候選人都會(huì)超時(shí)，然后通過增加當(dāng)前任期號(hào)來開始一輪新的選舉。然而，沒有其它機(jī)制的話，選票可能會(huì)被無限的重復(fù)瓜分。
Raft算法使用隨機(jī)選舉超時(shí)時(shí)間的方法來確保很少會(huì)發(fā)生選票瓜分的情況，就算發(fā)生也能很快的解決。為了阻止選票起初就被瓜分，選舉超時(shí)時(shí)間是從一個(gè)固定的區(qū)間（例如 150-300 毫秒）隨機(jī)選擇。這樣可以把服務(wù)器都分散開以至于在大多數(shù)情況下只有一個(gè)服務(wù)器會(huì)選舉超時(shí)；然后它贏得選舉并在其它服務(wù)器超時(shí)之前發(fā)送心跳包。同樣的機(jī)制被用在選票瓜分的情況下。每一個(gè)候選人在開始一次選舉的時(shí)候會(huì)重置一個(gè)隨機(jī)的選舉超時(shí)時(shí)間，然后在超時(shí)時(shí)間內(nèi)等待投票的結(jié)果；這樣減少了在新的選舉中另外的選票瓜分的可能性。9.3 節(jié)展示了這種方案能夠快速的選出一個(gè)Leader。
Leader選舉這個(gè)例子，體現(xiàn)了可理解性原則是如何指導(dǎo)我們進(jìn)行方案設(shè)計(jì)的。起初我們計(jì)劃使用一種排名系統(tǒng)：每一個(gè)候選人都被賦予一個(gè)唯一的排名，供候選人之間競爭時(shí)進(jìn)行選擇。如果一個(gè)候選人發(fā)現(xiàn)另一個(gè)候選人擁有更高的排名，那么它就會(huì)回到Follower狀態(tài)，這樣高排名的候選人能夠更加容易的贏得下一次選舉。但是我們發(fā)現(xiàn)這種方法在可用性方面會(huì)有一點(diǎn)問題（如果高排名的服務(wù)器宕機(jī)了，那么低排名的服務(wù)器可能會(huì)超時(shí)并再次進(jìn)入候選人狀態(tài)。而且如果這個(gè)行為發(fā)生得足夠快，則可能會(huì)導(dǎo)致整個(gè)選舉過程都被重置掉）。我們針對(duì)算法進(jìn)行了多次調(diào)整，但是每次調(diào)整之后都會(huì)有新的問題。最終我們認(rèn)為隨機(jī)重試的方法是更加明顯和易于理解的。
?
5.3 日志復(fù)制
一旦一個(gè)Leader被選舉出來，它就開始為客戶端提供服務(wù)。客戶端的每一個(gè)請(qǐng)求都包含一條被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。Leader把這條指令作為一條新的日志條目附加到日志中去，然后并行的發(fā)起附加條目 RPCs 給其它的服務(wù)器，讓它們復(fù)制這條日志條目。當(dāng)這條日志條目被安全的復(fù)制（下面會(huì)介紹），Leader會(huì)應(yīng)用這條日志條目到它的狀態(tài)機(jī)中然后把執(zhí)行的結(jié)果返回給客戶端。如果Follower崩潰或者運(yùn)行緩慢，再或者網(wǎng)絡(luò)丟包，Leader會(huì)不斷的重復(fù)嘗試附加日志條目 RPCs （盡管已經(jīng)回復(fù)了客戶端）直到所有的Follower都最終存儲(chǔ)了所有的日志條目。
圖6：日志由有序序號(hào)標(biāo)記的條目組成。每個(gè)條目都包含創(chuàng)建時(shí)的任期號(hào)（圖中框中的數(shù)字），和一個(gè)狀態(tài)機(jī)需要執(zhí)行的指令。一個(gè)條目當(dāng)可以安全的被應(yīng)用到狀態(tài)機(jī)中去的時(shí)候，就認(rèn)為是可以提交了。
日志以圖 6 展示的方式組織。每一個(gè)日志條目存儲(chǔ)一條狀態(tài)機(jī)指令和從Leader收到這條指令時(shí)的任期號(hào)。日志中的任期號(hào)用來檢查是否出現(xiàn)不一致的情況，同時(shí)也用來保證圖 3 中的某些性質(zhì)。每一條日志條目同時(shí)也都有一個(gè)整數(shù)索引值來表明它在日志中的位置。
Leader來決定什么時(shí)候把日志條目應(yīng)用到狀態(tài)機(jī)中是安全的；這種日志條目被稱為已提交。Raft算法保證所有已提交的日志條目都是持久化的并且最終會(huì)被所有可用的狀態(tài)機(jī)執(zhí)行。在Leader將創(chuàng)建的日志條目復(fù)制到大多數(shù)的服務(wù)器上的時(shí)候，日志條目就會(huì)被提交（例如在圖 6 中的條目 7）。同時(shí)，Leader的日志中之前的所有日志條目也都會(huì)被提交，包括由其它Leader創(chuàng)建的條目。5.4 節(jié)會(huì)討論某些當(dāng)在Leader改變之后應(yīng)用這條規(guī)則的隱晦內(nèi)容，同時(shí)它也展示了這種提交的定義是安全的。Leader跟蹤了最大的將會(huì)被提交的日志項(xiàng)的索引，并且索引值會(huì)被包含在未來的所有附加日志 RPCs （包括心跳包），這樣其它的服務(wù)器才能最終知道Leader的提交位置。一旦Follower知道一條日志條目已經(jīng)被提交，那么它也會(huì)將這個(gè)日志條目應(yīng)用到本地的狀態(tài)機(jī)中（按照日志的順序）。
我們?cè)O(shè)計(jì)了Raft的日志機(jī)制來維護(hù)一個(gè)不同服務(wù)器的日志之間的高層次的一致性。這么做不僅簡化了系統(tǒng)的行為也使得更加可預(yù)計(jì)，同時(shí)它也是安全性保證的一個(gè)重要組件。Raft維護(hù)著以下的特性，這些同時(shí)也組成了圖 3 中的日志匹配特性：
第一個(gè)特性來自這樣的一個(gè)事實(shí)，Leader最多在一個(gè)任期里在指定的一個(gè)日志索引位置創(chuàng)建一條日志條目，同時(shí)日志條目在日志中的位置也從來不會(huì)改變。第二個(gè)特性由附加日志 RPC 的一個(gè)簡單的一致性檢查所保證。在發(fā)送附加日志 RPC 的時(shí)候，Leader會(huì)把新的日志條目緊接著之前的條目的索引位置和任期號(hào)包含在里面。如果Follower在它的日志中找不到包含相同索引位置和任期號(hào)的條目，那么它就會(huì)拒絕接收新的日志條目。一致性檢查就像一個(gè)歸納步驟：一開始空的日志狀態(tài)肯定是滿足日志匹配特性的，然后一致性檢查保護(hù)了日志匹配特性當(dāng)日志擴(kuò)展的時(shí)候。因此，每當(dāng)附加日志 RPC 返回成功時(shí)，Leader就知道Follower的日志一定是和自己相同的了。
在正常的操作中，Leader和Follower的日志保持一致性，所以附加日志 RPC 的一致性檢查從來不會(huì)失敗。然而，Leader崩潰的情況會(huì)使得日志處于不一致的狀態(tài)（老的Leader可能還沒有完全復(fù)制所有的日志條目）。這種不一致問題會(huì)在Leader和Follower的一系列崩潰下加劇。圖 7 展示了Follower的日志可能和新的Leader不同的方式。Follower可能會(huì)丟失一些在新的Leader中有的日志條目，它也可能擁有一些Leader沒有的日志條目，或者兩者都發(fā)生。丟失或者多出日志條目可能會(huì)持續(xù)多個(gè)任期。
圖7：當(dāng)一個(gè)Leader成功當(dāng)選時(shí)，Follower可能是任何情況（a-f）。每一個(gè)盒子表示是一個(gè)日志條目；里面的數(shù)字表示任期號(hào)。Follower可能會(huì)缺少一些日志條目（a-b），可能會(huì)有一些未被提交的日志條目（c-d），或者兩種情況都存在（e-f）。例如，場(chǎng)景 f 可能會(huì)這樣發(fā)生，某服務(wù)器在任期 2 的時(shí)候是Leader，已附加了一些日志條目到自己的日志中，但在提交之前就崩潰了；很快這個(gè)機(jī)器就被重啟了，在任期 3 重新被選為Leader，并且又增加了一些日志條目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，這個(gè)服務(wù)器又宕機(jī)了，并且在接下來的幾個(gè)任期里一直處于宕機(jī)狀態(tài)。
在Raft算法中，Leader處理不一致是通過強(qiáng)制Follower直接復(fù)制自己的日志來解決了。這意味著在Follower中的沖突的日志條目會(huì)被Leader的日志覆蓋。5.4 節(jié)會(huì)闡述如何通過增加一些限制來使得這樣的操作是安全的。
要使得Follower的日志進(jìn)入和自己一致的狀態(tài)，Leader必須找到最后兩者達(dá)成一致的地方，然后刪除從那個(gè)點(diǎn)之后的所有日志條目，發(fā)送自己的日志給Follower。所有的這些操作都在進(jìn)行附加日志 RPCs 的一致性檢查時(shí)完成。Leader針對(duì)每一個(gè)Follower維護(hù)了一個(gè) nextIndex，這表示下一個(gè)需要發(fā)送給Follower的日志條目的索引地址。當(dāng)一個(gè)Leader剛獲得權(quán)力的時(shí)候，它初始化所有的 nextIndex 值為自己的最后一條日志的index加1（圖 7 中的 11）。如果一個(gè)Follower的日志和Leader不一致，那么在下一次的附加日志 RPC 時(shí)的一致性檢查就會(huì)失敗。在被Follower拒絕之后，Leader就會(huì)減小 nextIndex 值并進(jìn)行重試。最終 nextIndex 會(huì)在某個(gè)位置使得Leader和Follower的日志達(dá)成一致。當(dāng)這種情況發(fā)生，附加日志 RPC 就會(huì)成功，這時(shí)就會(huì)把Follower沖突的日志條目全部刪除并且加上Leader的日志。一旦附加日志 RPC 成功，那么Follower的日志就會(huì)和Leader保持一致，并且在接下來的任期里一直繼續(xù)保持。
如果需要的話，算法可以通過減少被拒絕的附加日志 RPCs 的次數(shù)來優(yōu)化。例如，當(dāng)附加日志 RPC 的請(qǐng)求被拒絕的時(shí)候，Follower可以包含沖突的條目的任期號(hào)和自己存儲(chǔ)的那個(gè)任期的最早的索引地址。借助這些信息，Leader可以減小 nextIndex 越過所有那個(gè)任期沖突的所有日志條目；這樣就變成每個(gè)任期需要一次附加條目 RPC 而不是每個(gè)條目一次。在實(shí)踐中，我們十分懷疑這種優(yōu)化是否是必要的，因?yàn)槭∈呛苌侔l(fā)生的并且也不大可能會(huì)有這么多不一致的日志。
通過這種機(jī)制，Leader在獲得權(quán)力的時(shí)候就不需要任何特殊的操作來恢復(fù)一致性。它只需要進(jìn)行正常的操作，然后日志就能自動(dòng)的在回復(fù)附加日志 RPC 的一致性檢查失敗的時(shí)候自動(dòng)趨于一致。Leader從來不會(huì)覆蓋或者刪除自己的日志（圖 3 的Leader只附加特性）。
日志復(fù)制機(jī)制展示出了第 2 節(jié)中形容的一致性特性：Raft能夠接受，復(fù)制并應(yīng)用新的日志條目只要大部分的機(jī)器是工作的；在通常的情況下，新的日志條目可以在一次 RPC 中被復(fù)制給集群中的大多數(shù)機(jī)器；并且單個(gè)的緩慢的Follower不會(huì)影響整體的性能。
?
5.4 安全性
前面的章節(jié)里描述了Raft算法是如何選舉和復(fù)制日志的。然而，到目前為止描述的機(jī)制并不能充分的保證每一個(gè)狀態(tài)機(jī)會(huì)按照相同的順序執(zhí)行相同的指令。例如，一個(gè)Follower可能會(huì)進(jìn)入不可用狀態(tài)同時(shí)Leader已經(jīng)提交了若干的日志條目，然后這個(gè)Follower可能會(huì)被選舉為Leader并且覆蓋這些日志條目；因此，不同的狀態(tài)機(jī)可能會(huì)執(zhí)行不同的指令序列。
這一節(jié)通過在領(lǐng)導(dǎo)選舉的時(shí)候增加一些限制來完善Raft算法。這一限制保證了任何的Leader對(duì)于給定的任期號(hào)，都擁有了之前任期的所有被提交的日志條目（圖 3 中的Leader完整特性）。增加這一選舉時(shí)的限制，我們對(duì)于提交時(shí)的規(guī)則也更加清晰。最終，我們將展示對(duì)于Leader完整特性的簡要證明，并且說明Leader完整性特性是如何引導(dǎo)復(fù)制狀態(tài)機(jī)做出正確行為的。
?
5.4.1 選舉限制
在任何基于Leader的一致性算法中，Leader都必須存儲(chǔ)所有已經(jīng)提交的日志條目。在某些一致性算法中，例如 Viewstamped Replication，某個(gè)節(jié)點(diǎn)即使是一開始并沒有包含所有已經(jīng)提交的日志條目，它也能被選為領(lǐng)導(dǎo)者。這些算法都包含一些額外的機(jī)制來識(shí)別丟失的日志條目并把它們傳送給新的Leader，要么是在選舉階段要么在之后很快進(jìn)行。不幸的是，這種方法會(huì)導(dǎo)致相當(dāng)大的額外的機(jī)制和復(fù)雜性。Raft使用了一種更加簡單的方法，它可以保證所有之前的任期號(hào)中已經(jīng)提交的日志條目在選舉的時(shí)候都會(huì)出現(xiàn)在新的Leader中，不需要傳送這些日志條目給Leader。這意味著日志條目的傳送是單向的，只從Leader傳給Follower，并且Leader從不會(huì)覆蓋自身本地日志中已經(jīng)存在的條目。
Raft使用投票的方式來阻止一個(gè)候選人贏得選舉除非這個(gè)候選人包含了所有已經(jīng)提交的日志條目。候選人為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點(diǎn)，這意味著每一個(gè)已經(jīng)提交的日志條目在這些服務(wù)器節(jié)點(diǎn)中肯定存在于至少一個(gè)節(jié)點(diǎn)上。如果候選人的日志至少和大多數(shù)的服務(wù)器節(jié)點(diǎn)一樣新（這個(gè)新的定義會(huì)在下面討論），那么它一定持有了所有已經(jīng)提交的日志條目。請(qǐng)求投票 RPC 實(shí)現(xiàn)了這樣的限制： RPC 中包含了候選人的日志信息，然后投票人會(huì)拒絕掉那些日志沒有自己新的投票請(qǐng)求。
Raft通過比較兩份日志中最后一條日志條目的索引值和任期號(hào)定義誰的日志比較新。如果兩份日志最后的條目的任期號(hào)不同，那么任期號(hào)大的日志更加新。如果兩份日志最后的條目任期號(hào)相同，那么日志比較長的那個(gè)就更加新。
?
5.4.2 提交之前任期內(nèi)的日志條目
如同 5.3 節(jié)介紹的那樣，Leader知道一條當(dāng)前任期內(nèi)的日志記錄是可以被提交的，只要它被存儲(chǔ)到了大多數(shù)的服務(wù)器上。如果一個(gè)Leader在提交日志條目之前崩潰了，未來后續(xù)的Leader會(huì)繼續(xù)嘗試復(fù)制這條日志記錄。然而，一個(gè)Leader不能斷定一個(gè)之前任期里的日志條目被保存到大多數(shù)服務(wù)器上的時(shí)候就一定已經(jīng)提交了。圖 8 展示了一種情況，一條已經(jīng)被存儲(chǔ)到大多數(shù)節(jié)點(diǎn)上的老日志條目，也依然有可能會(huì)被未來的Leader覆蓋掉。
圖8：如圖的時(shí)間序列展示了為什么Leader無法決定對(duì)老任期號(hào)的日志條目進(jìn)行提交。在 (a) 中，S1 是領(lǐng)導(dǎo)者，部分的復(fù)制了索引位置 2 的日志條目。在 (b) 中，S1 崩潰了，然后 S5 在任期 3 里通過 S3、S4 和自己的選票贏得選舉，然后從客戶端接收了一條不一樣的日志條目放在了索引 2 處。然后到 (c)，S5 又崩潰了；S1 重新啟動(dòng)，選舉成功，開始復(fù)制日志。在這時(shí)，來自任期 2 的那條日志已經(jīng)被復(fù)制到了集群中的大多數(shù)機(jī)器上，但是還沒有被提交。如果 S1 在 (d) 中又崩潰了，S5 可以重新被選舉成功（通過來自 S2，S3 和 S4 的選票），然后覆蓋了它們?cè)谒饕?2 處的日志。反之，如果在崩潰之前，S1 把自己主導(dǎo)的新任期里產(chǎn)生的日志條目復(fù)制到了大多數(shù)機(jī)器上，就如 (e) 中那樣，那么在后面任期里面這些新的日志條目就會(huì)被提交（因?yàn)镾5 就不可能選舉成功）。 這樣在同一時(shí)刻就同時(shí)保證了，之前的所有老的日志條目就會(huì)被提交。
為了消除圖8里描述的情況，Raft永遠(yuǎn)不會(huì)通過計(jì)算副本數(shù)目的方式去提交一個(gè)之前任期內(nèi)的日志條目。只有Leader當(dāng)前任期里的日志條目通過計(jì)算副本數(shù)目可以被提交；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性，之前的日志條目也都會(huì)被間接的提交。在某些情況下，Leader可以安全的知道一個(gè)老的日志條目是否已經(jīng)被提交（例如，該條目是否存儲(chǔ)到所有服務(wù)器上），但是Raft為了簡化問題使用一種更加保守的方法。
當(dāng)Leader復(fù)制之前任期里的日志時(shí)，Raft會(huì)為所有日志保留原始的任期號(hào), 這在提交規(guī)則上產(chǎn)生了額外的復(fù)雜性。在其它的一致性算法中，如果一個(gè)新的Leader要重新復(fù)制之前的任期里的日志時(shí)，它必須使用當(dāng)前新的任期號(hào)。Raft使用的方法更加容易辨別出日志，因?yàn)樗梢噪S著時(shí)間和日志的變化對(duì)日志維護(hù)著同一個(gè)任期編號(hào)。另外，和其它的算法相比，Raft中的新Leader只需要發(fā)送更少日志條目（其它算法中必須在它們被提交之前發(fā)送更多的冗余日志條目來為它們重新編號(hào)）。
?
5.4.3 安全性論證
在給定了完整的Raft算法之后，我們現(xiàn)在可以更加精確的討論Leader完整性特性（這一討論基于 9.2 節(jié)的安全性證明）。我們假設(shè)Leader完全性特性是不存在的，然后我們推出矛盾來。假設(shè)任期 T 的Leader（Leader?T）在任期內(nèi)提交了一條日志條目，但是這條日志條目沒有被存儲(chǔ)到未來某個(gè)任期的Leader的日志中。設(shè)大于 T 的最小任期 U 的Leader?U 沒有這條日志條目。
圖9：如果 S1 （任期 T 的領(lǐng)導(dǎo)者）提交了一條新的日志在它的任期里，然后 S5 在之后的任期 U 里被選舉為Leader，然后至少會(huì)有一個(gè)機(jī)器，如 S3，既擁有來自 S1 的日志，也給 S5 投票了。
1. 在Leader?U 選舉的時(shí)候一定沒有那條被提交的日志條目（Leader從不會(huì)刪除或者覆蓋任何條目）。
2. Leader?T 復(fù)制這條日志條目給集群中的大多數(shù)節(jié)點(diǎn)，同時(shí)，LeaderU 從集群中的大多數(shù)節(jié)點(diǎn)贏得了選票。因此，至少有一個(gè)節(jié)點(diǎn)（投票者、選民）同時(shí)接受了來自LeaderT 的日志條目，并且給LeaderU 投票了，如圖 9。這個(gè)投票者是產(chǎn)生這個(gè)矛盾的關(guān)鍵。
3. 這個(gè)投票者必須在給Leader?U 投票之前先接受了從Leader?T 發(fā)來的已經(jīng)被提交的日志條目；否則它就會(huì)拒絕來自Leader?T 的附加日志請(qǐng)求（因?yàn)榇藭r(shí)它的任期號(hào)會(huì)比 T 大）。
4. 投票者在給Leader?U 投票時(shí)依然保存有這條日志條目，因?yàn)槿魏沃虚g的Leader都包含該日志條目（根據(jù)上述的假設(shè)），Leader從不會(huì)刪除條目，并且Follower只有在和Leader沖突的時(shí)候才會(huì)刪除條目。
5. 投票者把自己選票投給Leader?U 時(shí)，Leader?U 的日志必須和投票者自己一樣新。這就導(dǎo)致了兩者矛盾之一。
6. 首先，如果投票者和Leader?U 的最后一條日志的任期號(hào)相同，那么Leader?U 的日志至少和投票者一樣長，所以Leader?U 的日志一定包含所有投票者的日志。這是另一處矛盾，因?yàn)橥镀闭甙四菞l已經(jīng)被提交的日志條目，但是在上述的假設(shè)里，Leader?U 是不包含的。
7. 除此之外，Leader?U 的最后一條日志的任期號(hào)就必須比投票人大了。此外，它也比 T 大，因?yàn)橥镀比说淖詈笠粭l日志的任期號(hào)至少和 T 一樣大（它包含了來自任期 T 的已提交的日志）。創(chuàng)建了Leader?U 最后一條日志的之前Leader一定已經(jīng)包含了那條被提交的日志（根據(jù)上述假設(shè)，Leader?U 是第一個(gè)不包含該日志條目的Leader）。所以，根據(jù)日志匹配特性，Leader?U 一定也包含那條被提交的日志，這里產(chǎn)生矛盾。
8. 這里完成了矛盾。因此，所有比 T 大的Leader一定包含了所有來自 T 的已經(jīng)被提交的日志。
9. 日志匹配原則保證了未來的Leader也同時(shí)會(huì)包含被間接提交的條目，例如圖 8 (d) 中的索引 2。
通過Leader完全特性，我們就能證明圖 3 中的狀態(tài)機(jī)安全特性，即如果服務(wù)器已經(jīng)在某個(gè)給定的索引值應(yīng)用了日志條目到自己的狀態(tài)機(jī)里，那么其它的服務(wù)器不會(huì)應(yīng)用一個(gè)不一樣的日志到同一個(gè)索引值上。在一個(gè)服務(wù)器應(yīng)用一條日志條目到它自己的狀態(tài)機(jī)中時(shí)，它的日志必須和Leader的日志，在該條目和之前的條目上相同，并且已經(jīng)被提交。現(xiàn)在我們來考慮在任何一個(gè)服務(wù)器應(yīng)用一個(gè)指定索引位置的日志的最小任期；日志完全特性保證擁有更高任期號(hào)的Leader會(huì)存儲(chǔ)相同的日志條目，所以之后的任期里應(yīng)用某個(gè)索引位置的日志條目也會(huì)是相同的值。因此，狀態(tài)機(jī)安全特性是成立的。
最后，Raft要求服務(wù)器按照日志中索引位置順序應(yīng)用日志條目。和狀態(tài)機(jī)安全特性結(jié)合起來看，這就意味著所有的服務(wù)器會(huì)應(yīng)用相同的日志序列集到自己的狀態(tài)機(jī)中，并且是按照相同的順序。
?
5.5 Follower和候選人崩潰
到目前為止，我們都只關(guān)注了Leader崩潰的情況。Follower和候選人崩潰后的處理方式比Leader要簡單的多，并且它們的處理方式是相同的。如果Follower或者候選人崩潰了，那么后續(xù)發(fā)送給它們的 RPCs 都會(huì)失敗。Raft中處理這種失敗就是簡單的通過無限的重試；如果崩潰的機(jī)器重啟了，那么這些 RPC 就會(huì)完整的成功。如果一個(gè)服務(wù)器在完成了一個(gè) RPC，但是還沒有響應(yīng)的時(shí)候崩潰了，那么在它重新啟動(dòng)之后就會(huì)再次收到同樣的請(qǐng)求。Raft的 RPCs 都是冪等的，所以這樣重試不會(huì)造成任何問題。例如一個(gè)Follower如果收到附加日志請(qǐng)求但是它已經(jīng)包含了這一日志，那么它就會(huì)直接忽略這個(gè)新的請(qǐng)求。
?
5.6 時(shí)間和可用性
Raft的要求之一就是安全性不能依賴時(shí)間：整個(gè)系統(tǒng)不能因?yàn)槟承┦录\(yùn)行的比預(yù)期快一點(diǎn)或者慢一點(diǎn)就產(chǎn)生了錯(cuò)誤的結(jié)果。但是，可用性（系統(tǒng)可以及時(shí)的響應(yīng)客戶端）不可避免的要依賴于時(shí)間。例如，如果消息交換比服務(wù)器故障間隔時(shí)間長，候選人將沒有足夠長的時(shí)間來贏得選舉；沒有一個(gè)穩(wěn)定的Leader，Raft將無法工作。
Leader選舉是Raft中對(duì)時(shí)間要求最為關(guān)鍵的方面。Raft可以選舉并維持一個(gè)穩(wěn)定的Leader,只要系統(tǒng)滿足下面的時(shí)間要求：
廣播時(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í)間就是對(duì)于一臺(tái)服務(wù)器而言，兩次故障之間的平均時(shí)間。廣播時(shí)間必須比選舉超時(shí)時(shí)間小一個(gè)量級(jí)，這樣Leader才能夠發(fā)送穩(wěn)定的心跳消息來阻止Follower開始進(jìn)入選舉狀態(tài)；通過隨機(jī)化選舉超時(shí)時(shí)間的方法，這個(gè)不等式也使得選票瓜分的情況變得不可能。選舉超時(shí)時(shí)間應(yīng)該要比平均故障間隔時(shí)間小上幾個(gè)數(shù)量級(jí)，這樣整個(gè)系統(tǒng)才能穩(wěn)定的運(yùn)行。當(dāng)Leader崩潰后，整個(gè)系統(tǒng)會(huì)大約相當(dāng)于選舉超時(shí)的時(shí)間里不可用；我們希望這種情況在整個(gè)系統(tǒng)的運(yùn)行中很少出現(xiàn)。
廣播時(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ù)制級(jí)別。盡管可以通過暫停整個(gè)集群，更新所有配置，然后重啟整個(gè)集群的方式來實(shí)現(xiàn)，但是在更改的時(shí)候集群會(huì)不可用。另外，如果存在手工操作步驟，那么就會(huì)有操作失誤的風(fēng)險(xiǎn)。為了避免這樣的問題，我們決定自動(dòng)化配置改變并且將其納入到Raft一致性算法中來。
為了讓配置修改機(jī)制能夠安全，那么在轉(zhuǎn)換的過程中不能夠存在任何時(shí)間點(diǎn)使得兩個(gè)Leader同時(shí)被選舉成功在同一個(gè)任期里。不幸的是，任何服務(wù)器直接從舊的配置直接轉(zhuǎn)換到新的配置的方案都是不安全的。一次性自動(dòng)的轉(zhuǎn)換所有服務(wù)器是不可能的，所以在轉(zhuǎn)換期間整個(gè)集群存在劃分成兩個(gè)獨(dú)立的大多數(shù)群體的可能性（見圖 10）。
圖10：直接從一種配置轉(zhuǎn)到新的配置是十分不安全的，因?yàn)楦鱾€(gè)機(jī)器可能在任何的時(shí)候進(jìn)行轉(zhuǎn)換。在這個(gè)例子中，集群配額從 3 臺(tái)機(jī)器變成了 5 臺(tái)。不幸的是，存在這樣的一個(gè)時(shí)間點(diǎn)，兩個(gè)不同的Leader在同一個(gè)任期里都可以被選舉成功。一個(gè)是通過舊的配置，一個(gè)通過新的配置。
為了保證安全性，配置更改必須使用兩階段方法。目前有很多種兩階段的實(shí)現(xiàn)。例如，有些系統(tǒng)在第一階段停掉舊的配置，所以集群就不能處理客戶端請(qǐng)求；然后在第二階段在啟用新的配置。在Raft中，集群先切換到一個(gè)過渡的配置，我們稱之為共同一致；一旦共同一致已經(jīng)被提交了，那么系統(tǒng)就切換到新的配置上。共同一致是老配置和新配置的結(jié)合：
共同一致允許獨(dú)立的服務(wù)器在不影響安全性的前提下，在不同的時(shí)間進(jìn)行配置轉(zhuǎn)換過程。此外，共同一致可以讓集群在配置轉(zhuǎn)換的過程中依然響應(yīng)客戶端的請(qǐng)求。
集群配置在復(fù)制日志中以特殊的日志條目來存儲(chǔ)和通信；圖 11 展示了配置轉(zhuǎn)換的過程。當(dāng)一個(gè)Leader接收到一個(gè)改變配置從 C-old 到 C-new 的請(qǐng)求，它會(huì)為了共同一致存儲(chǔ)配置（圖中的 C-old,new），以前面描述的日志條目和副本的形式。一旦一個(gè)服務(wù)器將新的配置日志條目增加到它的日志中，它就會(huì)用這個(gè)配置來做出未來所有的決定（服務(wù)器總是使用最新的配置，無論它是否已經(jīng)被提交）。這意味著Leader要使用 ?C-old,new 的規(guī)則來決定日志條目 C-old,new 什么時(shí)候需要被提交。如果Leader崩潰了，被選出來的新Leader可能是使用 C-old 配置也可能是 C-old,new 配置，這取決于贏得選舉的候選人是否已經(jīng)接收到了 C-old,new 配置。在任何情況下， C-new 配置在這一時(shí)期都不會(huì)單方面的做出決定。
一旦 C-old,new 被提交，那么無論是 C-old 還是 C-new，在沒有經(jīng)過它人批準(zhǔn)的情況下都不可能做出決定，并且Leader完全特性保證了只有擁有 C-old,new 日志條目的服務(wù)器才有可能被選舉為Leader。這個(gè)時(shí)候，Leader創(chuàng)建一條關(guān)于 C-new 配置的日志條目并復(fù)制給集群就是安全的了。再者，每個(gè)服務(wù)器在見到新的配置的時(shí)候就會(huì)立即生效。當(dāng)新的配置在 C-new 的規(guī)則下被提交，舊的配置就變得無關(guān)緊要，同時(shí)不使用新的配置的服務(wù)器就可以被關(guān)閉了。如圖 11，C-old 和 C-new 沒有任何機(jī)會(huì)同時(shí)做出單方面的決定；這保證了安全性。
圖11：一個(gè)配置切換的時(shí)間線。虛線表示已經(jīng)被創(chuàng)建但是還沒有被提交的配置日志條目，實(shí)線表示最后被提交的配置日志條目。Leader首先創(chuàng)建了 C-old,new 的配置條目在自己的日志中，并提交到 C-old,new 中（C-old 的大多數(shù)和 ?C-new 的大多數(shù)）。然后它創(chuàng)建 C-new 條目并提交到 C-new 中的大多數(shù)。這樣就不存在 ?C-new 和 C-old 可以同時(shí)做出決定的時(shí)間點(diǎn)。
在關(guān)于重新配置還有三個(gè)問題需要提出。
第一個(gè)問題是，新的服務(wù)器可能初始化沒有存儲(chǔ)任何的日志條目。當(dāng)這些服務(wù)器以這種狀態(tài)加入到集群中，那么它們需要一段時(shí)間來更新追趕，這時(shí)還不能提交新的日志條目。為了避免這種可用性的間隔時(shí)間，Raft在配置更新之前使用了一種額外的階段，在這個(gè)階段，新的服務(wù)器以沒有投票權(quán)身份加入到集群中來（Leader復(fù)制日志給它們，但是不考慮它們是大多數(shù)）。一旦新的服務(wù)器追趕上了集群中的其它機(jī)器，重新配置可以像上面描述的一樣處理。
第二個(gè)問題是，集群的Leader可能不是新配置的一員。在這種情況下，Leader就會(huì)在提交了 C-new 日志之后退位（回到Follower狀態(tài)）。這意味著有這樣的一段時(shí)間，Leader管理著集群，但是不包括它自己；它復(fù)制日志但是不把它自己算作是大多數(shù)之一。當(dāng) C-new 被提交時(shí)，會(huì)發(fā)生Leader過渡，因?yàn)檫@時(shí)是最早新的配置可以獨(dú)立工作的時(shí)間點(diǎn)（將總是能夠在 C-new 配置下選出新的Leader）。在此之前，可能只能從 C-old 中選出Leader。
第三個(gè)問題是，移除不在 C-new 中的服務(wù)器可能會(huì)擾亂集群。這些服務(wù)器將不會(huì)再接收到心跳，所以當(dāng)選舉超時(shí)，它們就會(huì)進(jìn)行新的選舉過程。它們會(huì)發(fā)送擁有新的任期號(hào)的請(qǐng)求投票 RPCs，這樣會(huì)導(dǎo)致當(dāng)前的Leader回退成Follower狀態(tài)。新的Leader最終會(huì)被選出來，但是被移除的服務(wù)器將會(huì)再次超時(shí)，然后這個(gè)過程會(huì)再次重復(fù)，導(dǎo)致整體可用性大幅降低。
為了避免這個(gè)問題，當(dāng)服務(wù)器確認(rèn)當(dāng)前Leader存在時(shí)，服務(wù)器會(huì)忽略請(qǐng)求投票 RPCs。特別的，當(dāng)服務(wù)器在當(dāng)前最小選舉超時(shí)時(shí)間內(nèi)收到一個(gè)請(qǐng)求投票 RPC，它不會(huì)更新當(dāng)前的任期號(hào)或者投出選票。這不會(huì)影響正常的選舉，每個(gè)服務(wù)器在開始一次選舉之前，至少等待一個(gè)最小選舉超時(shí)時(shí)間。然而，這有利于避免被移除的服務(wù)器擾亂：如果Leader能夠發(fā)送心跳給集群，那么它就不會(huì)被更大的任期號(hào)廢黜。
?
7.?日志壓縮
Raft的日志在正常操作中不斷的增長，但是在實(shí)際的系統(tǒng)中，日志不能無限制的增長。隨著日志不斷增長，它會(huì)占用越來越多的空間，花費(fèi)越來越多的時(shí)間來重置。如果沒有一定的機(jī)制去清除日志里積累的陳舊的信息，那么會(huì)帶來可用性問題。
快照是最簡單的壓縮方法。在快照系統(tǒng)中，整個(gè)系統(tǒng)的狀態(tài)都以快照的形式寫入到穩(wěn)定的持久化存儲(chǔ)中，然后到那個(gè)時(shí)間點(diǎn)之前的日志全部丟棄。快照技術(shù)被使用在 Chubby 和 ZooKeeper 中，接下來的章節(jié)會(huì)介紹Raft中的快照技術(shù)。
增量壓縮的方法，例如日志清理或者日志結(jié)構(gòu)合并樹，都是可行的。這些方法每次只對(duì)一小部分?jǐn)?shù)據(jù)進(jìn)行操作，這樣就分散了壓縮的負(fù)載壓力。首先，它們先選擇一個(gè)已經(jīng)積累的大量已經(jīng)被刪除或者被覆蓋對(duì)象的區(qū)域，然后重寫那個(gè)區(qū)域還活躍的對(duì)象，之后釋放那個(gè)區(qū)域。和簡單操作整個(gè)數(shù)據(jù)集合的快照相比，需要增加復(fù)雜的機(jī)制來實(shí)現(xiàn)。狀態(tài)機(jī)可以實(shí)現(xiàn) LSM tree 使用和快照相同的接口，但是日志清除方法就需要修改Raft了。
圖12：一個(gè)服務(wù)器用新的快照替換了從 1 到 5 的條目，快照值存儲(chǔ)了當(dāng)前的狀態(tài)。快照中包含了最后的索引位置和任期號(hào)。
圖12展示了Raft中快照的基礎(chǔ)思想。每個(gè)服務(wù)器獨(dú)立的創(chuàng)建快照，只包括已經(jīng)被提交的日志。主要的工作包括將狀態(tài)機(jī)的狀態(tài)寫入到快照中。Raft也包含一些少量的元數(shù)據(jù)到快照中：最后被包含索引指的是被快照取代的最后的條目在日志中的索引值（狀態(tài)機(jī)最后應(yīng)用的日志），最后被包含的任期指的是該條目的任期號(hào)。保留這些數(shù)據(jù)是為了支持快照后緊接著的第一個(gè)條目的附加日志請(qǐng)求時(shí)的一致性檢查，因?yàn)檫@個(gè)條目需要前一日志條目的索引值和任期號(hào)。為了支持集群成員更新（第 6 節(jié)），快照中也將最后的一次配置作為最后一個(gè)條目存下來。一旦服務(wù)器完成一次快照，它就可以刪除最后索引位置之前的所有日志和快照了。
盡管通常服務(wù)器都是獨(dú)立的創(chuàng)建快照，但是Leader必須偶爾的發(fā)送快照給一些落后的Follower。這通常發(fā)生在當(dāng)Leader已經(jīng)丟棄了下一條需要發(fā)送給Follower的日志條目的時(shí)候。幸運(yùn)的是這種情況不是常規(guī)操作：一個(gè)與Leader保持同步的Follower通常都會(huì)有這個(gè)條目。然而一個(gè)運(yùn)行非常緩慢的Follower或者新加入集群的服務(wù)器（第 6 節(jié)）將不會(huì)有這個(gè)條目。這時(shí)讓這個(gè)Follower更新到最新的狀態(tài)的方式就是通過網(wǎng)絡(luò)把快照發(fā)送給它們。
?
安裝快照 RPC：
由Leader調(diào)用以將快照的分塊發(fā)送給Follower。領(lǐng)導(dǎo)者總是按順序發(fā)送分塊。
| term | 領(lǐng)導(dǎo)人的任期號(hào) |
| leaderId | 領(lǐng)導(dǎo)人的 Id，以便于跟隨者重定向請(qǐng)求 |
| lastIncludedIndex | 快照中包含的最后日志條目的索引值 |
| lastIncludedTerm | 快照中包含的最后日志條目的任期號(hào) |
| offset | 分塊在快照中的偏移量 |
| data[] | 原始數(shù)據(jù) |
| done | 如果這是最后一個(gè)分塊則為 true |
| term | 當(dāng)前任期號(hào)，便于領(lǐng)導(dǎo)人更新自己 |
接收者實(shí)現(xiàn)：
1. 如果? term < currentTerm? 就立即回復(fù)
2. 如果是第一個(gè)分塊（offset 為 0）就創(chuàng)建一個(gè)新的快照
3. 在指定偏移量寫入數(shù)據(jù)
4. 如果 done 是 false，則繼續(xù)等待更多的數(shù)據(jù)
5. 保存快照文件，丟棄具有較小索引的任何現(xiàn)有或部分快照
6. 如果現(xiàn)存的日志條目與快照中最后包含的日志條目具有相同的索引值和任期號(hào)，則保留其后的日志條目并進(jìn)行回復(fù)
7. 丟棄整個(gè)日志
8. 使用快照重置狀態(tài)機(jī)（并加載快照的集群配置）
圖13：一個(gè)關(guān)于安裝快照的簡要概述。為了便于傳輸，快照都是被分成分塊的；每個(gè)分塊都給了Follower生命的跡象，所以Follower可以重置選舉超時(shí)計(jì)時(shí)器。
在這種情況下Leader使用一種叫做安裝快照的新的 RPC 來發(fā)送快照給太落后的Follower；見圖 13。當(dāng)Follower通過這種 RPC 接收到快照時(shí)，它必須自己決定對(duì)于已經(jīng)存在的日志該如何處理。通常快照會(huì)包含沒有在接收者日志中存在的信息。在這種情況下，Follower丟棄其整個(gè)日志；它全部被快照取代，并且可能包含與快照沖突的未提交條目。如果接收到的快照是自己日志的前面部分（由于網(wǎng)絡(luò)重傳或者錯(cuò)誤），那么被快照包含的條目將會(huì)被全部刪除，但是快照后面的條目仍然有效，必須保留。
這種快照的方式背離了Raft的強(qiáng)Leader原則，因?yàn)?/span>Follower可以在不知道Leader情況下創(chuàng)建快照。但是我們認(rèn)為這種背離是值得的。Leader的存在，是為了解決在達(dá)成一致性的時(shí)候的沖突，但是在創(chuàng)建快照的時(shí)候，一致性已經(jīng)達(dá)成，這時(shí)不存在沖突了，所以沒有Leader也是可以的。數(shù)據(jù)依然是從Leader傳給Follower，只是Follower可以重新組織它們的數(shù)據(jù)了。
我們考慮過一種替代的基于Leader的快照方案，即只有Leader創(chuàng)建快照，然后發(fā)送給所有的Follower。但是這樣做有兩個(gè)缺點(diǎn)。第一，發(fā)送快照會(huì)浪費(fèi)網(wǎng)絡(luò)帶寬并且延緩了快照處理的時(shí)間。每個(gè)Follower都已經(jīng)擁有了所有產(chǎn)生快照需要的信息，而且很顯然，自己從本地的狀態(tài)中創(chuàng)建快照比通過網(wǎng)絡(luò)接收別人發(fā)來的要經(jīng)濟(jì)。第二，Leader的實(shí)現(xiàn)會(huì)更加復(fù)雜。例如，Leader需要發(fā)送快照的同時(shí)并行的將新的日志條目發(fā)送給Follower，這樣才不會(huì)阻塞新的客戶端請(qǐng)求。
還有兩個(gè)問題影響了快照的性能。首先，服務(wù)器必須決定什么時(shí)候應(yīng)該創(chuàng)建快照。如果快照創(chuàng)建的過于頻繁，那么就會(huì)浪費(fèi)大量的磁盤帶寬和其它資源；如果創(chuàng)建快照頻率太低，它就要承受耗盡存儲(chǔ)容量的風(fēng)險(xiǎn)，同時(shí)也增加了從日志重建的時(shí)間。一個(gè)簡單的策略就是當(dāng)日志大小達(dá)到一個(gè)固定大小的時(shí)候就創(chuàng)建一次快照。如果這個(gè)閾值設(shè)置的顯著大于期望的快照的大小，那么快照對(duì)磁盤壓力的影響就會(huì)很小了。
第二個(gè)影響性能的問題就是寫入快照需要花費(fèi)顯著的一段時(shí)間，并且我們還不希望影響到正常操作。解決方案是通過寫時(shí)復(fù)制的技術(shù)，這樣新的更新就可以被接收而不影響到快照。例如，具有函數(shù)式數(shù)據(jù)結(jié)構(gòu)的狀態(tài)機(jī)天然支持這樣的功能。另外，操作系統(tǒng)的寫時(shí)復(fù)制技術(shù)的支持（如 Linux 上的 fork）可以被用來創(chuàng)建完整的狀態(tài)機(jī)的內(nèi)存快照（我們的實(shí)現(xiàn)就是這樣的）。
?
8.?客戶端交互
這一節(jié)將介紹客戶端是如何和Raft進(jìn)行交互的，包括客戶端如何發(fā)現(xiàn)Leader和Raft是如何支持線性化語義的。這些問題對(duì)于所有基于一致性的系統(tǒng)都存在，并且Raft的解決方案和其它的也差不多。
Raft中的客戶端發(fā)送所有請(qǐng)求給Leader。當(dāng)客戶端啟動(dòng)的時(shí)候，它會(huì)隨機(jī)挑選一個(gè)服務(wù)器進(jìn)行通信。如果客戶端第一次挑選的服務(wù)器不是Leader，那么那個(gè)服務(wù)器會(huì)拒絕客戶端的請(qǐng)求并且提供它最近接收到的Leader的信息（附加條目請(qǐng)求包含了Leader的網(wǎng)絡(luò)地址）。如果Leader已經(jīng)崩潰了，那么客戶端的請(qǐng)求就會(huì)超時(shí)；客戶端之后會(huì)再次重試隨機(jī)挑選服務(wù)器的過程。
我們Raft的目標(biāo)是要實(shí)現(xiàn)線性化語義（每一次操作立即執(zhí)行，只執(zhí)行一次，在它調(diào)用和收到回復(fù)之間）。但是，如上述，Raft是可以執(zhí)行同一條命令多次的：例如，如果Leader在提交了這條日志之后，但是在響應(yīng)客戶端之前崩潰了，那么客戶端會(huì)和新的Leader重試這條指令，導(dǎo)致這條命令就被再次執(zhí)行了。解決方案就是客戶端對(duì)于每一條指令都賦予一個(gè)唯一的序列號(hào)。然后，狀態(tài)機(jī)跟蹤每條指令最新的序列號(hào)和相應(yīng)的響應(yīng)。如果接收到一條指令，它的序列號(hào)已經(jīng)被執(zhí)行了，那么就立即返回結(jié)果，而不重新執(zhí)行指令。
只讀的操作可以直接處理而不需要記錄日志。但是，在不增加任何限制的情況下，這么做可能會(huì)冒著返回臟數(shù)據(jù)的風(fēng)險(xiǎn)，因?yàn)?/span>Leader響應(yīng)客戶端請(qǐng)求時(shí)可能已經(jīng)被新的Leader作廢了，但是它還不知道。線性化的讀操作必須不能返回臟數(shù)據(jù)，Raft需要使用兩個(gè)額外的措施在不使用日志的情況下保證這一點(diǎn)。首先，Leader必須有關(guān)于被提交日志的最新信息。Leader完全特性保證了Leader一定擁有所有已經(jīng)被提交的日志條目，但是在它任期開始的時(shí)候，它可能不知道哪些是已經(jīng)被提交的。為了知道這些信息，它需要在它的任期里提交一條日志條目。Raft中通過Leader在任期開始的時(shí)候提交一個(gè)空白的沒有任何操作的日志條目到日志中去來實(shí)現(xiàn)。第二，Leader在處理只讀的請(qǐng)求之前必須檢查自己是否已經(jīng)被廢了（如果一個(gè)更新的Leader被選舉出來,它的信息可能已經(jīng)變臟了）。Raft中通過讓Leader在響應(yīng)只讀請(qǐng)求之前，先和集群中的大多數(shù)節(jié)點(diǎn)交換一次心跳信息來處理這個(gè)問題。可選的，Leader可以依賴心跳機(jī)制來實(shí)現(xiàn)一種租約的機(jī)制，但是這種方法依賴時(shí)間來保證安全性（假設(shè)時(shí)間誤差是有界的）。
?
9.?算法實(shí)現(xiàn)和評(píng)估
我們已經(jīng)為 RAMCloud 實(shí)現(xiàn)了Raft算法作為存儲(chǔ)配置信息的復(fù)制狀態(tài)機(jī)的一部分，并且?guī)椭?RAMCloud 協(xié)調(diào)故障轉(zhuǎn)移。這個(gè)Raft實(shí)現(xiàn)包含大約 2000 行 C++ 代碼，其中不包括測(cè)試、注釋和空行。這些代碼是開源的。同時(shí)也有大約 25 個(gè)其它獨(dú)立的第三方的基于這篇論文草稿的開源實(shí)現(xiàn)，針對(duì)不同的開發(fā)場(chǎng)景。同時(shí)，很多公司已經(jīng)部署了基于Raft的系統(tǒng)。這一節(jié)會(huì)從三個(gè)方面來評(píng)估Raft算法：可理解性、正確性和性能。
?
9.1 可理解性
為了和 Paxos比較Raft算法的可理解能力，我們針對(duì)高層次的本科生和研究生，在斯坦福大學(xué)的高級(jí)操作系統(tǒng)課程和加州大學(xué)伯克利分校的分布式計(jì)算課程上，進(jìn)行了一次學(xué)習(xí)的實(shí)驗(yàn)。我們分別拍了針對(duì)Raft和 Paxos的視頻課程，并準(zhǔn)備了相應(yīng)的小測(cè)驗(yàn)。Raft的視頻講課覆蓋了這篇論文除了日志壓縮的所有內(nèi)容；Paxos講課包含了足夠的資料來創(chuàng)建一個(gè)等價(jià)的復(fù)制狀態(tài)機(jī)，包括單決策 Paxos，多決策 Paxos，重新配置和一些實(shí)際系統(tǒng)需要的性能優(yōu)化（例如Leader選舉）。小測(cè)驗(yàn)測(cè)試一些對(duì)算法的基本理解和解釋一些邊角的示例。每個(gè)學(xué)生都是看完第一個(gè)視頻，回答相應(yīng)的測(cè)試，再看第二個(gè)視頻，回答相應(yīng)的測(cè)試。大約有一半的學(xué)生先進(jìn)行 Paxos部分，然后另一半先進(jìn)行Raft部分，這是為了說明兩者從第一部分的算法學(xué)習(xí)中獲得的表現(xiàn)和經(jīng)驗(yàn)的差異。我們計(jì)算參加人員的每一個(gè)小測(cè)驗(yàn)的得分來看參與者是否在Raft算法上更加容易理解。
我們盡可能的使得 Paxos和Raft的比較更加公平。這個(gè)實(shí)驗(yàn)偏愛 Paxos表現(xiàn)在兩個(gè)方面：43 個(gè)參加者中有 15 個(gè)人在之前有一些 ?Paxos的經(jīng)驗(yàn)，并且 Paxos的視頻要長 14%。如表格 1 總結(jié)的那樣，我們采取了一些措施來減輕這種潛在的偏見。我們所有的材料都可供審查。
| 相同的講課質(zhì)量 | 兩者使用同一個(gè)講師。Paxos 使用的是現(xiàn)在很多大學(xué)里經(jīng)常使用的。Paxos 會(huì)長 14%。 | 視頻 |
| 相同的測(cè)驗(yàn)難度 | 問題以難度分組，在兩個(gè)測(cè)驗(yàn)里成對(duì)出現(xiàn)。 | 小測(cè)驗(yàn) |
| 公平評(píng)分 | 使用紅字標(biāo)題。隨機(jī)順序打分，兩個(gè)測(cè)驗(yàn)交替進(jìn)行。 | 紅字標(biāo)題 |
表1：考慮到可能會(huì)存在的偏見，對(duì)于每種情況的解決方法，和相應(yīng)的材料。
參加者平均在Raft的測(cè)驗(yàn)中比 Paxos高 4.9 分（總分 60，那么Raft的平均得分是 25.7，而 Paxos是 20.8）；圖 14 展示了每個(gè)參與者的得分。配置t-檢驗(yàn)（又稱student‘s t-test）表明，在 95% 的可信度下，真實(shí)的Raft分?jǐn)?shù)分布至少比 Paxos高 2.5 分。
圖14：一個(gè)散點(diǎn)圖表示了 43 個(gè)學(xué)生在 Paxos和Raft的小測(cè)驗(yàn)中的成績。在對(duì)角線之上的點(diǎn)表示在Raft獲得了更高分?jǐn)?shù)的學(xué)生。
我們也建立了一個(gè)線性回歸模型來預(yù)測(cè)一個(gè)新的學(xué)生的測(cè)驗(yàn)成績，基于以下三個(gè)因素：它們使用的是哪個(gè)小測(cè)驗(yàn)，之前對(duì) Paxos的經(jīng)驗(yàn)，和學(xué)習(xí)算法的順序。模型預(yù)測(cè)，對(duì)小測(cè)驗(yàn)的選擇會(huì)產(chǎn)生 12.5 分的差別。這顯著的高于之前的 4.9 分，因?yàn)楹芏鄬W(xué)生在之前都已經(jīng)有了對(duì)于 Paxos的經(jīng)驗(yàn)，這相當(dāng)明顯的幫助 Paxos，對(duì)Raft就沒什么太大影響了。但是奇怪的是，模型預(yù)測(cè)對(duì)于先進(jìn)行 Paxos小測(cè)驗(yàn)的人而言，Raft的得分低了6.3分; 雖然我們不知道為什么，這似乎在統(tǒng)計(jì)上是有意義的。
我們同時(shí)也在測(cè)驗(yàn)之后調(diào)查了參與者，它們認(rèn)為哪個(gè)算法更加容易實(shí)現(xiàn)和解釋；這個(gè)的結(jié)果在圖 15 上。壓倒性的結(jié)果表明Raft算法更加容易實(shí)現(xiàn)和解釋（41 人中的 33個(gè)）。但是，這種自己報(bào)告的結(jié)果不如參與者的成績更加可信，并且參與者可能因?yàn)槲覀兊?/span>Raft更加易于理解的假說而產(chǎn)生偏見。
圖15：通過一個(gè) 5 分制的問題，參與者（左邊）被問哪個(gè)算法它們覺得在一個(gè)高效正確的系統(tǒng)里更容易實(shí)現(xiàn)，右邊被問哪個(gè)更容易向?qū)W生解釋。
關(guān)于Raft用戶學(xué)習(xí)有一個(gè)更加詳細(xì)的討論。
?
9.2 正確性
在第 5 節(jié)，我們已經(jīng)制定了正式的規(guī)范，和對(duì)一致性機(jī)制的安全性證明。這個(gè)正式規(guī)范使用 TLA+ 規(guī)范語言使圖 2 中總結(jié)的信息非常清晰。它長約400行，并作為證明的主題。同時(shí)對(duì)于任何想實(shí)現(xiàn)Raft的人也是十分有用的。我們通過 TLA 證明系統(tǒng)非常機(jī)械的證明了日志完全特性。然而，這個(gè)證明依賴的約束前提還沒有被機(jī)械證明（例如，我們還沒有證明規(guī)范的類型安全）。而且，我們已經(jīng)寫了一個(gè)非正式的證明關(guān)于狀態(tài)機(jī)安全性是完備的，并且是相當(dāng)清晰的（大約 3500 個(gè)詞）。
?
9.3 性能
Raft和其它一致性算法例如 Paxos有著差不多的性能。在性能方面，最重要的關(guān)注點(diǎn)是，當(dāng)Leader被選舉成功時(shí)，什么時(shí)候復(fù)制新的日志條目。Raft通過很少數(shù)量的消息包（一輪從Leader到集群大多數(shù)機(jī)器的消息）就達(dá)成了這個(gè)目的。同時(shí)，進(jìn)一步提升Raft的性能也是可行的。例如，很容易通過支持批量操作和管道操作來提高吞吐量和降低延遲。對(duì)于其它一致性算法已經(jīng)提出過很多性能優(yōu)化方案；其中有很多也可以應(yīng)用到Raft中來，但是我們暫時(shí)把這個(gè)問題放到未來的工作中去。
我們使用我們自己的Raft實(shí)現(xiàn)來衡量RaftLeader選舉的性能并且回答兩個(gè)問題。首先，Leader選舉的過程收斂是否快速？第二，在Leader宕機(jī)之后，最小的系統(tǒng)宕機(jī)時(shí)間是多久？
圖16：發(fā)現(xiàn)并替換一個(gè)已經(jīng)崩潰的Leader的時(shí)間。上面的圖考察了在選舉超時(shí)時(shí)間上的隨機(jī)化程度，下面的圖考察了最小選舉超時(shí)時(shí)間。每條線代表了 1000 次實(shí)驗(yàn)（除了 150-150 毫秒只試了 100 次），和相應(yīng)的確定的選舉超時(shí)時(shí)間。例如，150-155 毫秒意思是，選舉超時(shí)時(shí)間從這個(gè)區(qū)間范圍內(nèi)隨機(jī)選擇并確定下來。這個(gè)實(shí)驗(yàn)在一個(gè)擁有 5 個(gè)節(jié)點(diǎn)的集群上進(jìn)行，其廣播時(shí)延大約是 15 毫秒。對(duì)于 9 個(gè)節(jié)點(diǎn)的集群，結(jié)果也差不多。
為了衡量Leader選舉，我們反復(fù)的使一個(gè)擁有五個(gè)節(jié)點(diǎn)的服務(wù)器集群的Leader宕機(jī)，并計(jì)算需要多久才能發(fā)現(xiàn)Leader已經(jīng)宕機(jī)并選出一個(gè)新的Leader（見圖 16）。為了構(gòu)建一個(gè)最壞的場(chǎng)景，在每一的嘗試?yán)?#xff0c;服務(wù)器都有不同長度的日志，意味著有些候選人是沒有成為Leader的資格的。另外，為了促成選票瓜分的情況，我們的測(cè)試腳本在終止Leader之前同步的發(fā)送了一次心跳廣播（這大約和Leader在崩潰前復(fù)制一個(gè)新的日志給其它機(jī)器很像）。Leader均勻的隨機(jī)的在心跳間隔里宕機(jī)，也就是最小選舉超時(shí)時(shí)間的一半。因此，最小宕機(jī)時(shí)間大約就是最小選舉超時(shí)時(shí)間的一半。
圖 16 中上面的圖表明，只需要在選舉超時(shí)時(shí)間上使用很少的隨機(jī)化就可以大大避免選票被瓜分的情況。在沒有隨機(jī)化的情況下，在我們的測(cè)試?yán)?#xff0c;選舉過程往往都需要花費(fèi)超過 10 秒鐘由于太多的選票瓜分的情況。僅僅增加 5 毫秒的隨機(jī)化時(shí)間，就大大的改善了選舉過程，現(xiàn)在平均的宕機(jī)時(shí)間只有 287 毫秒。增加更多的隨機(jī)化時(shí)間可以大大改善最壞情況：通過增加 50 毫秒的隨機(jī)化時(shí)間，最壞的完成情況（1000 次嘗試）只要 513 毫秒。
圖 16 中下面的圖顯示，通過減少選舉超時(shí)時(shí)間可以減少系統(tǒng)的宕機(jī)時(shí)間。在選舉超時(shí)時(shí)間為 12-24 毫秒的情況下，只需要平均 35 毫秒就可以選舉出新的Leader（最長的一次花費(fèi)了 152 毫秒）。然而，進(jìn)一步降低選舉超時(shí)時(shí)間的話就會(huì)違反Raft的時(shí)間不等式需求：在選舉新Leader之前，Leader就很難發(fā)送完心跳包。這會(huì)導(dǎo)致沒有意義的Leader改變并降低了系統(tǒng)整體的可用性。我們建議使用更為保守的選舉超時(shí)時(shí)間，比如 150-300 毫秒；這樣的時(shí)間不大可能導(dǎo)致沒有意義的Leader改變，而且依然提供不錯(cuò)的可用性。
?
10.?相關(guān)工作
已經(jīng)有很多關(guān)于一致性算法的工作被發(fā)表出來，其中很多都可以歸到下面的類別中：
Raft和 Paxos最大的不同之處就在于Raft的強(qiáng)領(lǐng)導(dǎo)特性：Raft使用Leader選舉作為一致性協(xié)議里必不可少的部分，并且將盡可能多的功能集中到了Leader身上。這樣就可以使得算法更加容易理解。例如，在 Paxos中，Leader選舉和基本的一致性協(xié)議是正交的：Leader選舉僅僅是性能優(yōu)化的手段，而且不是一致性所必須要求的。但是，這樣就增加了多余的機(jī)制：Paxos同時(shí)包含了針對(duì)基本一致性要求的兩階段提交協(xié)議和針對(duì)Leader選舉的獨(dú)立的機(jī)制。相比較而言，Raft就直接將Leader選舉納入到一致性算法中，并作為兩階段一致性的第一步。這樣就減少了很多機(jī)制。
像Raft一樣，VR 和 ZooKeeper 也是基于Leader的，因此它們也擁有一些Raft的優(yōu)點(diǎn)。但是，Raft比 VR 和 ZooKeeper 擁有更少的機(jī)制因?yàn)?/span>Raft盡可能的減少了非Leader的功能。例如，Raft中日志條目都遵循著從Leader發(fā)送給其它人這一個(gè)方向：附加條目 RPC 是向外發(fā)送的。在 VR 中，日志條目的流動(dòng)是雙向的（Leader可以在選舉過程中接收日志）；這就導(dǎo)致了額外的機(jī)制和復(fù)雜性。根據(jù) ZooKeeper 公開的資料看，它的日志條目也是雙向傳輸?shù)?#xff0c;但是它的實(shí)現(xiàn)更像 Raft。
和上述我們提及的其它基于一致性的日志復(fù)制算法中，Raft的消息類型更少。例如，我們數(shù)了一下 VR 和 ZooKeeper 使用的用來基本一致性需要和成員改變的消息數(shù)（排除了日志壓縮和客戶端交互，因?yàn)檫@些都比較獨(dú)立且和算法關(guān)系不大）。VR 和 ZooKeeper 都分別定義了 10 中不同的消息類型，相對(duì)的，Raft只有 4 種消息類型（兩種 RPC 請(qǐng)求和對(duì)應(yīng)的響應(yīng)）。Raft的消息都稍微比其它算法的要信息量大，但是都很簡單。另外，VR 和 ZooKeeper 都在Leader改變時(shí)傳輸了整個(gè)日志；所以為了能夠?qū)嵺`中使用，額外的消息類型就很必要了。
Raft的強(qiáng)Leader模型簡化了整個(gè)算法，但是同時(shí)也排斥了一些性能優(yōu)化的方法。例如，平等主義 Paxos（EPaxos）在某些沒有Leader的情況下可以達(dá)到很高的性能。平等主義 Paxos充分發(fā)揮了在狀態(tài)機(jī)指令中的交換性。任何服務(wù)器都可以在一輪通信下就提交指令，除非其它指令同時(shí)被提出了。然而，如果指令都是并發(fā)的被提出，并且互相之間不通信溝通，那么 EPaxos就需要額外的一輪通信。因?yàn)槿魏畏?wù)器都可以提交指令，所以 EPaxos在服務(wù)器之間的負(fù)載均衡做的很好，并且很容易在 WAN 網(wǎng)絡(luò)環(huán)境下獲得很低的延遲。但是，它在 Paxos上增加了非常明顯的復(fù)雜性。
一些集群成員變換的方法已經(jīng)被提出或者在其它的工作中被實(shí)現(xiàn)，包括 Lamport 的原始的討論，VR 和 SMART。我們選擇使用共同一致的方法因?yàn)?/span>它對(duì)一致性協(xié)議的其它部分影響很小，這樣我們只需要很少的一些機(jī)制就可以實(shí)現(xiàn)成員變換。Lamport 的基于 α 的方法之所以沒有被Raft選擇是因?yàn)樗僭O(shè)在沒有Leader的情況下也可以達(dá)到一致性。和 VR 和 SMART 相比較，Raft的重新配置算法可以在不限制正常請(qǐng)求處理的情況下進(jìn)行；相比較的，VR 需要停止所有的處理過程，SMART 引入了一個(gè)和 α 類似的方法，限制了請(qǐng)求處理的數(shù)量。Raft的方法同時(shí)也需要更少的額外機(jī)制來實(shí)現(xiàn)，和 VR、SMART 比較而言。
?
11.?結(jié)論
算法的設(shè)計(jì)通常會(huì)把正確性，效率或者簡潔作為主要的目標(biāo)。盡管這些都是很有意義的目標(biāo)，但是我們相信，可理解性也是一樣的重要。在開發(fā)者把算法應(yīng)用到實(shí)際的系統(tǒng)中之前，這些目標(biāo)沒有一個(gè)會(huì)被實(shí)現(xiàn)，這些都會(huì)必然的偏離發(fā)表時(shí)的形式。除非開發(fā)人員對(duì)這個(gè)算法有著很深的理解并且有著直觀的感覺，否則將會(huì)對(duì)它們而言很難在實(shí)現(xiàn)的時(shí)候保持原有期望的特性。
在這篇論文中，我們嘗試解決分布式一致性問題，但是一個(gè)廣為接受但是十分令人費(fèi)解的算法 Paxos已經(jīng)困擾了無數(shù)學(xué)生和開發(fā)者很多年了。我們創(chuàng)造了一種新的算法 Raft，顯而易見的比 Paxos要容易理解。我們同時(shí)也相信，Raft也可以為實(shí)際的實(shí)現(xiàn)提供堅(jiān)實(shí)的基礎(chǔ)。把可理解性作為設(shè)計(jì)的目標(biāo)改變了我們?cè)O(shè)計(jì)Raft的方式；隨著設(shè)計(jì)的進(jìn)展，我們發(fā)現(xiàn)自己重復(fù)使用了一些技術(shù)，比如分解問題和簡化狀態(tài)空間。這些技術(shù)不僅提升了Raft的可理解性，同時(shí)也使我們堅(jiān)信其正確性。
?
12.?感謝
這項(xiàng)研究必須感謝以下人員的支持：Ali Ghodsi，David Mazie\`res，和伯克利 CS 294-91 課程、斯坦福 CS 240 課程的學(xué)生。Scott Klemmer 幫我們?cè)O(shè)計(jì)了用戶調(diào)查，Nelson Ray 建議我們進(jìn)行統(tǒng)計(jì)學(xué)的分析。在用戶調(diào)查時(shí)使用的關(guān)于 Paxos的幻燈片很大一部分是從 Lorenzo Alvisi 的幻燈片上借鑒過來的。特別的，非常感謝 DavidMazieres 和 Ezra Hoch，它們找到了Raft中一些難以發(fā)現(xiàn)的漏洞。許多人提供了關(guān)于這篇論文十分有用的反饋和用戶調(diào)查材料，包括 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 位匿名的會(huì)議審查人員（可能有重復(fù)），并且特別感謝我們的Leader?Eddie Kohler。Werner Vogels 發(fā)了一條早期草稿鏈接的推特，給Raft帶來了極大的關(guān)注。我們的工作由 Gigascale 系統(tǒng)研究中心和 Multiscale 系統(tǒng)研究中心給予支持，這兩個(gè)研究中心由關(guān)注中心研究程序資金支持，一個(gè)是半導(dǎo)體研究公司的程序，由 STARnet 支持，一個(gè)半導(dǎo)體研究公司的程序由 MARCO 和 DARPA 支持，在國家科學(xué)基金會(huì)的 0963859 號(hào)批準(zhǔn)，并且獲得了來自 Facebook，Google，Mellanox，NEC，NetApp，SAP 和 Samsung 的支持。Diego Ongaro 由 Junglee 公司，斯坦福的畢業(yè)團(tuán)體支持。
總結(jié)
- 上一篇： 跟着微信后台团队学习分布式一致性协议
- 下一篇： TCP三次握手，握的是啥？