尋找一種易于理解的一致性算法

1、Top of FormBottom of Form尋找一種易于理解的一致性算法（擴(kuò)展版）摘要Raft 是一種為了管理復(fù)制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能，但是它的算法結(jié)構(gòu)和 Paxos 不同，使得 Raft 算法更加容易理解并且更容易構(gòu)建實(shí)際的系統(tǒng)。為了提升可理解性，Raft 將一致性算法分解成了幾個(gè)關(guān)鍵模塊，例如領(lǐng)導(dǎo)人選舉、日志復(fù)制和安全性。同時(shí)它通過實(shí)施一個(gè)更強(qiáng)的一致性來減少需要考慮的狀態(tài)的數(shù)量。從一個(gè)用戶研究的結(jié)果可以證明，對(duì)于學(xué)生而言，Raft 算法比 Paxos 算法更加容易學(xué)習(xí)。Raft 算法還包括一個(gè)新的機(jī)制來允許集群成員的動(dòng)態(tài)改變，它利用重疊的大多

2、數(shù)來保證安全性。1 介紹一致性算法允許一組機(jī)器像一個(gè)整體一樣工作，即使其中一些機(jī)器出現(xiàn)故障也能夠繼續(xù)工作下去。正因?yàn)槿绱?，一致性算法在?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

3、算法進(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 主要被分成了領(lǐng)導(dǎo)人選舉，日志復(fù)制和安全三個(gè)模塊）和減少狀態(tài)機(jī)的狀態(tài)（相對(duì)于 Paxos，Raft 減少

4、了非確定性和服務(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)者：和其他一致性算法相比，Raft 使用一種更強(qiáng)的領(lǐng)導(dǎo)能力形式。比如，日志條目只從領(lǐng)導(dǎo)者發(fā)送給其他的服務(wù)器。這種方式簡化了對(duì)復(fù)制日志的管理并且使得 Raft 算法更加易

5、于理解。· 領(lǐng)導(dǎo)選舉：Raft 算法使用一個(gè)隨機(jī)計(jì)時(shí)器來選舉領(lǐng)導(dǎo)者。這種方式只是在任何一致性算法都必須實(shí)現(xiàn)的心跳機(jī)制上增加了一點(diǎn)機(jī)制。在解決沖突的時(shí)候會(huì)更加簡單快捷。· 關(guān)系調(diào)整：Raft 使用一種共同一致的方法來處理集群成員變換的問題，在這種方法中，兩種不同的配置都要求的大多數(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)被證

6、明；它的效率和其他算法比起來也不相上下。接下來，這篇論文會(huì)介紹以下內(nèi)容：復(fù)制狀態(tài)機(jī)問題（第 2 節(jié)），討論 Paxos 的優(yōu)點(diǎn)和缺點(diǎn)（第 3 節(jié)），討論我們?yōu)榱死斫饽芰Χ褂玫姆椒ǎǖ?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

7、，十分典型的使用一個(gè)單獨(dú)的復(fù)制狀態(tài)機(jī)去管理領(lǐng)導(dǎo)選舉和存儲(chǔ)配置信息并且在領(lǐng)導(dǎo)人宕機(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ù)器

8、上，一致性模塊接收客戶端發(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)中使用的一致性算法通常含有以下特性：· 安全性保證（絕對(duì)不會(huì)返回一個(gè)錯(cuò)誤的結(jié)果）：在非拜占庭錯(cuò)誤情況下，包括網(wǎng)絡(luò)延遲、分區(qū)、丟包、冗余和亂序等錯(cuò)誤都可以保證正確。· 可用性：集群中只要有大多數(shù)的機(jī)器可運(yùn)行并且能夠相互通信、和客戶端通信，就可以保證可用。因

9、此，一個(gè)典型的包含 5 個(gè)節(jié)點(diǎn)的集群可以容忍兩個(gè)節(jié)點(diǎn)的失敗。服務(wù)器被停止就認(rèn)為是失敗。他們當(dāng)有穩(wěn)定的存儲(chǔ)的時(shí)候可以從狀態(tài)中恢復(fù)回來并重新加入集群。· 不依賴時(shí)序來保證一致性：物理時(shí)鐘錯(cuò)誤或者極端的消息延遲在可能只有在最壞情況下才會(huì)導(dǎo)致可用性問題。· 通常情況下，一條指令可以盡可能快的在集群中大多數(shù)節(jié)點(diǎn)響應(yīng)一輪遠(yuǎn)程過程調(diào)用時(shí)完成。小部分比較慢的節(jié)點(diǎn)不會(huì)影響系統(tǒng)整體的性能。3 Paxos算法的問題在過去的 10 年里，Leslie Lamport 的 Paxos 算法幾乎已經(jīng)成為一致性的代名詞：Paxos 是在課程教學(xué)中最經(jīng)常使用的算法，同時(shí)也是大多數(shù)一致性算法實(shí)現(xiàn)的起點(diǎn)。Pa

10、xos 首先定義了一個(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 的

11、會(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á)成一致性的問題（一份日志而不是單一的日志記錄）

12、能夠被分解成其他的方式并且更加直接和明顯。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ú)立的選擇一組日志條目

13、然后合并成一個(gè)序列化的日志并沒有帶來太多的好處，僅僅增加了不少復(fù)雜性。圍繞著日志來設(shè)計(jì)一個(gè)系統(tǒng)是更加簡單高效的；新日志條目以嚴(yán)格限制的順序增添到日志中去。另一個(gè)問題是，Paxos 使用了一種對(duì)等的點(diǎn)對(duì)點(diǎn)的方式作為它的核心（盡管它最終提議了一種弱領(lǐng)導(dǎo)人的方法來優(yōu)化性能）。在只有一個(gè)決策會(huì)被制定的簡化世界中是很有意義的，但是很少有現(xiàn)實(shí)的系統(tǒng)使用這種方式。如果有一系列的決策需要被制定，首先選擇一個(gè)領(lǐng)導(dǎo)人，然后讓他去協(xié)調(diào)所有的決議，會(huì)更加簡單快速。因此，實(shí)際的系統(tǒng)中很少有和 Paxos 相似的實(shí)踐。每一種實(shí)現(xiàn)都是從 Paxos 開始研究，然后發(fā)現(xiàn)很多實(shí)現(xiàn)上的難題，再然后開發(fā)了一種和 Paxos 明顯不

14、一樣的結(jié)構(gòu)。這樣非常費(fèi)時(shí)和容易出錯(cuò)的，并且理解 Paxos 的難度是的這個(gè)問題更加糟糕。Paxos 算法在理論上被證明是正確可行的，但是現(xiàn)實(shí)的系統(tǒng)和 Paxos 差別是如此的大，以至于這些證明沒有什么太大的價(jià)值。下面來自 Chubby 實(shí)現(xiàn)非常典型：在Paxos算法描述和實(shí)現(xiàn)現(xiàn)實(shí)系統(tǒng)中間有者巨大的鴻溝。最終的系統(tǒng)建立在一種沒有經(jīng)過證明的算法之上。由于以上問題，我們認(rèn)為 Paxos 算法既沒有提供一個(gè)良好的基礎(chǔ)給實(shí)踐的系統(tǒng)，也沒有給教學(xué)很好的幫助。基于一致性問題在大規(guī)模軟件系統(tǒng)中的重要性，我們決定看看我們是否可以設(shè)計(jì)一個(gè)擁有更好特性的替代 Paxos 的一致性算法。Raft算法就是這次實(shí)驗(yàn)的結(jié)果

15、。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ù)雜，是否有微妙的暗示）？

16、對(duì)于一個(gè)讀者而言，完全理解這個(gè)方案和暗示是否容易？我們意識(shí)到對(duì)這種可理解性分析上具有高度的主觀性；盡管如此，我們使用了兩種通常適用的技術(shù)來解決這個(gè)問題。第一個(gè)技術(shù)就是眾所周知的問題分解：只要有可能，我們就將問題分解成幾個(gè)相對(duì)獨(dú)立的，可被解決的、可解釋的和可理解的子問題。例如，Raft 算法被我們分成領(lǐng)導(dǎo)人選舉，日志復(fù)制，安全性和角色改變幾個(gè)部分。我們使用的第二個(gè)方法是通過減少狀態(tài)的數(shù)量來簡化需要考慮的狀態(tài)空間，使得系統(tǒng)更加連貫并且在可能的時(shí)候消除不確定性。特別的，所有的日志是不允許有空洞的，并且 Raft 限制了日志之間變成不一致狀態(tài)的可能。盡管在大多數(shù)情況下我們都試圖去消除不確定性，但是也有

17、一些情況下不確定性可以提升可理解性。尤其是，隨機(jī)化方法增加了不確定性，但是他們有利于減少狀態(tài)空間數(shù)量，通過處理所有可能選擇時(shí)使用相似的方法。我們使用隨機(jī)化去簡化 Raft 中領(lǐng)導(dǎo)人選舉算法。5 Raft 一致性算法Raft 是一種用來管理章節(jié) 2 中描述的復(fù)制日志的算法。圖 2 為了參考之用，總結(jié)這個(gè)算法的簡略版本，圖 3 列舉了這個(gè)算法的一些關(guān)鍵特性。圖中的這些元素會(huì)在剩下的章節(jié)逐一介紹。Raft 通過選舉一個(gè)高貴的領(lǐng)導(dǎo)人，然后給予他全部的管理復(fù)制日志的責(zé)任來實(shí)現(xiàn)一致性。領(lǐng)導(dǎo)人從客戶端接收日志條目，把日志條目復(fù)制到其他服務(wù)器上，并且當(dāng)保證安全性的時(shí)候告訴其他的服務(wù)器應(yīng)用日志條目到他們的狀態(tài)機(jī)

18、中。擁有一個(gè)領(lǐng)導(dǎo)人大大簡化了對(duì)復(fù)制日志的管理。例如，領(lǐng)導(dǎo)人可以決定新的日志條目需要放在日志中的什么位置而不需要和其他服務(wù)器商議，并且數(shù)據(jù)都從領(lǐng)導(dǎo)人流向其他服務(wù)器。一個(gè)領(lǐng)導(dǎo)人可以宕機(jī)，可以和其他服務(wù)器失去連接，這時(shí)一個(gè)新的領(lǐng)導(dǎo)人會(huì)被選舉出來。通過領(lǐng)導(dǎo)人的方式，Raft 將一致性問題分解成了三個(gè)相對(duì)獨(dú)立的子問題，這些問題會(huì)在接下來的子章節(jié)中進(jìn)行討論：· 領(lǐng)導(dǎo)選舉：一個(gè)新的領(lǐng)導(dǎo)人需要被選舉出來，當(dāng)先存的領(lǐng)導(dǎo)人宕機(jī)的時(shí)候（章節(jié) 5.2）· 日志復(fù)制：領(lǐng)導(dǎo)人必須從客戶端接收日志然后復(fù)制到集群中的其他節(jié)點(diǎn)，并且強(qiáng)制要求其他節(jié)點(diǎn)的日志保持和自己相同。· 安全性：在 Raft 中

19、安全性的關(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)用一個(gè)不同的指令。章節(jié) 5.4 闡述了 Raft 算法是如何保證這個(gè)特性的；這個(gè)解決方案涉及到一個(gè)額外的選舉機(jī)制（5.2 節(jié)）上的限制。在展示一致性算法之后，這一章節(jié)會(huì)討論可用性的一些問題和系統(tǒng)中的候選人角色的問題。狀態(tài)：狀態(tài)所有服務(wù)器上持久存在的currentTerm服務(wù)器最后一次知道的任期號(hào)（初始化為 0，持續(xù)遞增）votedFor在當(dāng)前獲得選票的候選人的 Idlog日志條目集；每一個(gè)條目包含一個(gè)用戶狀態(tài)機(jī)執(zhí)行的指令，和收到時(shí)的任期號(hào)狀態(tài)

20、所有服務(wù)器上經(jīng)常變的commitIndex已知的最大的已經(jīng)被提交的日志條目的索引值lastApplied最后被應(yīng)用到狀態(tài)機(jī)的日志條目索引值（初始化為 0，持續(xù)遞增）狀態(tài)在領(lǐng)導(dǎo)人里經(jīng)常改變的 （選舉后重新初始化）nextIndex對(duì)于每一個(gè)服務(wù)器，需要發(fā)送給他的下一個(gè)日志條目的索引值（初始化為領(lǐng)導(dǎo)人最后索引值加一）matchIndex對(duì)于每一個(gè)服務(wù)器，已經(jīng)復(fù)制給他的日志的最高索引值附加日志 RPC：由領(lǐng)導(dǎo)人負(fù)責(zé)調(diào)用來復(fù)制日志指令；也會(huì)用作heartbeat參數(shù)解釋term領(lǐng)導(dǎo)人的任期號(hào)leaderId領(lǐng)導(dǎo)人的 Id，以便于跟隨者重定向請(qǐng)求prevLogIndex新的日志條目緊隨之前的索引值pre

21、vLogTermprevLogIndex 條目的任期號(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

22、. 如果已經(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é)）參數(shù)解釋term候選人的任期號(hào)candidateId請(qǐng)求選票的候選人的 IdlastLogIndex候選人的最后日志條目的索引值lastLogTerm候選人最后日志條目的任期號(hào)返回值解釋term當(dāng)前任期號(hào)，以便于候選人

23、去更新自己的任期號(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ù)器：· 如果commitIndex > lastApplied，那么就 lastApplied 加一，并把loglastApplied應(yīng)用到狀態(tài)機(jī)中（5.3 節(jié)）· 如果接收到的 RPC 請(qǐng)求中，任期號(hào)T > currentTerm，

24、那么就令 currentTerm 等于 T，并切換狀態(tài)為跟隨者（5.1 節(jié)）跟隨者（5.2 節(jié)）：· 響應(yīng)來自候選人和領(lǐng)導(dǎo)者的請(qǐng)求· 如果在超過選舉超時(shí)時(shí)間的情況之前都沒有收到領(lǐng)導(dǎo)人的心跳，或者是候選人請(qǐng)求投票的，就自己變成候選人候選人（5.2 節(jié)）：· 在轉(zhuǎn)變成候選人后就立即開始選舉過程o 自增當(dāng)前的任期號(hào)（currentTerm）o 給自己投票o 重置選舉超時(shí)計(jì)時(shí)器o 發(fā)送請(qǐng)求投票的 RPC 給其他所有服務(wù)器· 如果接收到大多數(shù)服務(wù)器的選票，那么就變成領(lǐng)導(dǎo)人· 如果接收到來自新的領(lǐng)導(dǎo)人的附加日志 RPC，轉(zhuǎn)變成跟隨者· 如果選舉過

25、程超時(shí)，再次發(fā)起一輪選舉領(lǐng)導(dǎo)人：· 一旦成為領(lǐng)導(dǎo)人：發(fā)送空的附加日志 RPC（心跳）給其他所有的服務(wù)器；在一定的空余時(shí)間之后不停的重復(fù)發(fā)送，以阻止跟隨者超時(shí)（5.2 節(jié)）· 如果接收到來自客戶端的請(qǐng)求：附加條目到本地日志中，在條目被應(yīng)用到狀態(tài)機(jī)后響應(yīng)客戶端（5.3 節(jié)）· 如果對(duì)于一個(gè)跟隨者，最后日志條目的索引值大于等于 nextIndex，那么：發(fā)送從 nextIndex 開始的所有日志條目：o 如果成功：更新相應(yīng)跟隨者的 nextIndex 和 matchIndexo 如果因?yàn)槿罩静灰恢露?，減少 nextIndex 重試· 如果存在一個(gè)滿足N &

26、gt; commitIndex的 N，并且大多數(shù)的matchIndexi N成立，并且logN.term = currentTerm成立，那么令 commitIndex 等于這個(gè) N （5.3 和 5.4 節(jié)）圖 2：一個(gè)關(guān)于 Raft 一致性算法的濃縮總結(jié)（不包括成員變換和日志壓縮）。特性解釋選舉安全特性對(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)人完全特性如

27、果某個(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)之一：領(lǐng)導(dǎo)人、跟隨者或者候選人。在通常情況下，系統(tǒng)中只有一個(gè)領(lǐng)導(dǎo)人并且其他的節(jié)點(diǎn)全部都是跟隨者。跟隨者都是被動(dòng)的：他們不會(huì)發(fā)送任何請(qǐng)求，只

28、是簡單的響應(yīng)來自領(lǐng)導(dǎo)者或者候選人的請(qǐng)求。領(lǐng)導(dǎo)人處理所有的客戶端請(qǐng)求（如果一個(gè)客戶端和跟隨者聯(lián)系，那么跟隨者會(huì)把請(qǐng)求重定向給領(lǐng)導(dǎo)人）。第三種狀態(tài)，候選人，是用來在 5.2 節(jié)描述的選舉新領(lǐng)導(dǎo)人時(shí)使用。圖 4 展示了這些狀態(tài)和他們之前轉(zhuǎn)換關(guān)系；這些轉(zhuǎn)換關(guān)系會(huì)在接下來進(jìn)行討論。圖 4：服務(wù)器狀態(tài)。跟隨者只響應(yīng)來自其他服務(wù)器的請(qǐng)求。如果跟隨者接收不到消息，那么他就會(huì)變成候選人并發(fā)起一次選舉。獲得集群中大多數(shù)選票的候選人將成為領(lǐng)導(dǎo)者。領(lǐng)導(dǎo)人一直都會(huì)是領(lǐng)導(dǎo)人直到自己宕機(jī)了。圖 5：時(shí)間被劃分成一個(gè)個(gè)的任期，每個(gè)任期開始都是一次選舉。在選舉成功后，領(lǐng)導(dǎo)人會(huì)管理整個(gè)集群直到任期結(jié)束。有時(shí)候選舉會(huì)失敗，那么這個(gè)

29、任期就會(huì)沒有領(lǐng)導(dǎo)人而結(jié)束。任期之間的切換可以在不同的時(shí)間不同的服務(wù)器上觀察到。Raft 把時(shí)間分割成任意長度的任期，如圖 5。任期用連續(xù)的整數(shù)標(biāo)記。每一段任期從一次選舉開始，就像章節(jié) 5.2 描述的一樣，一個(gè)或者多個(gè)候選人嘗試成為領(lǐng)導(dǎo)者。如果一個(gè)候選人贏得選舉，然后他就在接下來的任期內(nèi)充當(dāng)領(lǐng)導(dǎo)人的職責(zé)。在某些情況下，一次選舉過程會(huì)造成選票的瓜分。在這種情況下，這一任期會(huì)以沒有領(lǐng)導(dǎo)人結(jié)束；一個(gè)新的任期（和一次新的選舉）會(huì)很快重新開始。Raft 保證了在一個(gè)給定的任期內(nèi)，最多只有一個(gè)領(lǐng)導(dǎo)者。不同的服務(wù)器節(jié)點(diǎn)可能多次觀察到任期之間的轉(zhuǎn)換，但在某些情況下，一個(gè)節(jié)點(diǎn)也可能觀察不到任何一次選舉或者整個(gè)任期

30、全程。任期在 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ù)成跟隨者狀態(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 由候選人在

31、選舉期間發(fā)起（章節(jié) 5.2），然后附加條目（AppendEntries）RPCs 由領(lǐng)導(dǎo)人發(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 領(lǐng)導(dǎo)人選舉Raft 使用一種心跳機(jī)制來觸發(fā)領(lǐng)導(dǎo)人選舉。當(dāng)服務(wù)器程序啟動(dòng)時(shí)，他們都是跟隨者身份。一個(gè)服務(wù)器節(jié)點(diǎn)要想繼續(xù)保持著跟隨者狀態(tài)除非他從領(lǐng)導(dǎo)人或者候選者處接收到有效的 RPCs。領(lǐng)導(dǎo)者周期性的向所有跟隨者發(fā)送心跳包（不包含日志項(xiàng)內(nèi)容的附加日志項(xiàng) RPCs）來維持自己的權(quán)威。如果一

32、個(gè)跟隨者在一段時(shí)間里沒有接收到任何消息，也就是選舉超時(shí)，然后他就會(huì)認(rèn)為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者然后開始進(jìn)行選舉以選出新的領(lǐng)導(dǎo)者。要開始一次選舉過程，跟隨者先要增加自己的當(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)的選票，那么他就贏得了這次選舉并成為領(lǐng)導(dǎo)人。每一個(gè)服務(wù)器最多會(huì)對(duì)

33、一個(gè)任期號(hào)投出一張選票，按照先來先服務(wù)的原則（注意：5.4 節(jié)在投票上增加了一點(diǎn)額外的限制）。要求大多數(shù)選票的規(guī)則確保了最多只會(huì)有一個(gè)候選人贏得此次選舉（圖 3 中的選舉安全性）。一旦候選人贏得選舉，他就立即成為領(lǐng)導(dǎo)人。然后他會(huì)向其他的服務(wù)器發(fā)送心跳消息來建立自己的權(quán)威并且阻止新的領(lǐng)導(dǎo)人的產(chǎn)生。在等待投票的時(shí)候，候選人可能會(huì)從其他的服務(wù)器接收到聲明它是領(lǐng)導(dǎo)人的附加日志項(xiàng) RPC。如果這個(gè)領(lǐng)導(dǎo)人的任期號(hào)（包含在此次的 RPC中）不小于候選人當(dāng)前的任期號(hào)，那么候選人會(huì)承認(rèn)領(lǐng)導(dǎo)人合法并回到跟隨者狀態(tài)。 如果此次 RPC 中的任期號(hào)比自己小，那么候選人就會(huì)拒絕這次的 RPC 并且繼續(xù)保持候選人狀態(tài)。第

34、三種可能的結(jié)果是候選人既沒有贏得選舉也沒有輸：如果有多個(gè)跟隨者同時(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ī)制被用在

35、選票瓜分的情況下。每一個(gè)候選人在開始一次選舉的時(shí)候會(huì)重置一個(gè)隨機(jī)的選舉超時(shí)時(shí)間，然后在下次選舉之前一直等待；這樣減少了在新的選舉中另外的選票瓜分的可能性。9.3 節(jié)展示了這種方案能夠快速的選出一個(gè)領(lǐng)導(dǎo)人。選舉是一個(gè)用來展示在選擇設(shè)計(jì)替代方案的時(shí)候可理解性是如何指導(dǎo)我們的例子。起初我們計(jì)劃使用一種排名系統(tǒng)：每一個(gè)候選人都被賦予一個(gè)唯一的排名，排名用來在候選人之間競(jìng)爭時(shí)進(jìn)行選擇。如果一個(gè)候選人發(fā)現(xiàn)另一個(gè)候選人擁有更高的排名，那么他就會(huì)回到跟隨者狀態(tài)，這樣高排名的候選人能夠更加容易的贏得下一次選舉。但是我們發(fā)現(xiàn)這種方法在可用性方面會(huì)有一點(diǎn)問題（一個(gè)低排名的服務(wù)器可能會(huì)再次的超時(shí)并成為候選人當(dāng)高排名的

36、服務(wù)器宕機(jī)時(shí)，但是如果他這么做太快，他會(huì)重置掉一個(gè)選舉過程）。我們針對(duì)算法進(jìn)行了多次調(diào)整，但是每次調(diào)整之后都會(huì)有新的問題。最終我們認(rèn)為隨機(jī)重試的方法是更加明顯和易于理解的。5.3 日志復(fù)制一旦一個(gè)領(lǐng)導(dǎo)人被選舉出來，他就開始為客戶端提供服務(wù)?？蛻舳说拿恳粋€(gè)請(qǐng)求都包含一條被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。領(lǐng)導(dǎo)人把這條指令作為一條新的日志條目附加到日志中去，然后并行的發(fā)起附加條目 RPCs 給其他的服務(wù)器，讓他們復(fù)制這條日志條目。當(dāng)這條日志條目被安全的復(fù)制（下面會(huì)介紹），領(lǐng)導(dǎo)人會(huì)應(yīng)用這條日志條目到它的狀態(tài)機(jī)中然后把執(zhí)行的結(jié)果返回給客戶端。如果跟隨者崩潰或者運(yùn)行緩慢，再或者網(wǎng)絡(luò)丟包，領(lǐng)導(dǎo)人會(huì)不斷的重復(fù)嘗試附加日

37、志條目 RPCs （盡管已經(jīng)回復(fù)了客戶端）直到所有的跟隨者都最終存儲(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ī)指令和從領(lǐng)導(dǎo)人收到這條指令時(shí)的任期號(hào)。在日志中的任期號(hào)是用來檢查不一致情況，同時(shí)也用來保證圖 3 中的某些性質(zhì)。每一條日志條目同時(shí)也都有一個(gè)整數(shù)索引值來表明它在日志中的位置。領(lǐng)導(dǎo)人來決定什么時(shí)候把日志條目應(yīng)用到狀態(tài)機(jī)中是安全的；這種日志條目被稱為已提交。Raft 算法保證所有

38、已提交的日志條目都是持久化的并且最終會(huì)被所有可用的狀態(tài)機(jī)執(zhí)行。在領(lǐng)導(dǎo)人將創(chuàng)建的日志條目復(fù)制到大多數(shù)的服務(wù)器上的時(shí)候，日志條目就會(huì)被提交（例如在圖 6 中的條目 7）。同時(shí)，領(lǐng)導(dǎo)人的日志中之前的所有日志條目也都會(huì)被提交，包括由其他領(lǐng)導(dǎo)人創(chuàng)建的條目。5.4 節(jié)會(huì)討論某些當(dāng)在領(lǐng)導(dǎo)人改變之后應(yīng)用這條規(guī)則的隱晦內(nèi)容，同時(shí)他也展示了這種提交的定義是安全的。領(lǐng)導(dǎo)人跟蹤了最大的將會(huì)被提交的日志項(xiàng)的索引，并且索引值會(huì)被包含在未來的所有附加日志 RPCs （包括心跳包），這樣其他的服務(wù)器才能最終知道領(lǐng)導(dǎo)人的提交位置。一旦跟隨者知道一條日志條目已經(jīng)被提交，那么他也會(huì)將這個(gè)日志條目應(yīng)用到本地的狀態(tài)機(jī)中（按照日志的順序

39、）。我們?cè)O(shè)計(jì)了 Raft 的日志機(jī)制來維護(hù)一個(gè)不同服務(wù)器的日志之間的高層次的一致性。這么做不僅簡化了系統(tǒng)的行為也使得更加可預(yù)計(jì)，同時(shí)他也是安全性保證的一個(gè)重要組件。Raft 維護(hù)著以下的特性，這些同時(shí)也組成了圖 3 中的日志匹配特性：· 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)，那么他們存儲(chǔ)了相同的指令。· 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)，那么他們之前的所有日志條目也全部相同。第一個(gè)特性來自這樣的一個(gè)事實(shí)，領(lǐng)導(dǎo)人最多在一個(gè)任期里在指定的一個(gè)日志索引位置創(chuàng)建一條日志條目，同時(shí)日志條目在日志中的位置也從來不會(huì)改變。第二個(gè)特性由附加日志 RPC 的一

40、個(gè)簡單的一致性檢查所保證。在發(fā)送附加日志 RPC 的時(shí)候，領(lǐng)導(dǎo)人會(huì)把新的日志條目緊接著之前的條目的索引位置和任期號(hào)包含在里面。如果跟隨者在它的日志中找不到包含相同索引位置和任期號(hào)的條目，那么他就會(huì)拒絕接收新的日志條目。一致性檢查就像一個(gè)歸納步驟：一開始空的日志狀態(tài)肯定是滿足日志匹配特性的，然后一致性檢查保護(hù)了日志匹配特性當(dāng)日志擴(kuò)展的時(shí)候。因此，每當(dāng)附加日志 RPC 返回成功時(shí)，領(lǐng)導(dǎo)人就知道跟隨者的日志一定是和自己相同的了。圖 7：當(dāng)一個(gè)領(lǐng)導(dǎo)人成功當(dāng)選時(shí)，跟隨者可能是任何情況（a-f）。每一個(gè)盒子表示是一個(gè)日志條目；里面的數(shù)字表示任期號(hào)。跟隨者可能會(huì)缺少一些日志條目（a-b），可能會(huì)有一些未被提

41、交的日志條目（c-d），或者兩種情況都存在（e-f）。例如，場(chǎng)景 f 可能這樣發(fā)生，那個(gè)服務(wù)器在任期 2 的時(shí)候是領(lǐng)導(dǎo)人，附加了一些日志條目到自己的日志中，在提交之前就崩潰了；很快這個(gè)機(jī)器就重啟了，在任期 3 重新被選為領(lǐng)導(dǎo)人，并且又增加了一些日志條目到自己的日志中；在這些任期 2 和任期 3 重點(diǎn)日志被提交之前，這個(gè)服務(wù)器又宕機(jī)了，然后的幾個(gè)任期里一直處于宕機(jī)狀態(tài)。在正常的操作中，領(lǐng)導(dǎo)人和跟隨者的日志保持一致性，所以附加日志 RPC 的一致性檢查從來不會(huì)失敗。然而，領(lǐng)導(dǎo)人崩潰的情況會(huì)使得日志處于不一致的狀態(tài)（老的領(lǐng)導(dǎo)人可能還沒有完全復(fù)制所有的日志條目）。這種不一致問題會(huì)在一系列的領(lǐng)導(dǎo)人和跟隨

42、者崩潰的情況下加劇。圖 7 展示了跟隨者的日志可能和新的領(lǐng)導(dǎo)人不同的方式。跟隨者可能會(huì)丟失一些在新的領(lǐng)導(dǎo)人中有的日志條目，他也可能擁有一些領(lǐng)導(dǎo)人沒有的日志條目，或者兩者都發(fā)生。丟失或者多出日志條目可能會(huì)持續(xù)多個(gè)任期。在 Raft 算法中，領(lǐng)導(dǎo)人處理不一致是通過強(qiáng)制跟隨者直接復(fù)制自己的日志來解決了。這意味著在跟隨者中的沖突的日志條目會(huì)被領(lǐng)導(dǎo)人的日志覆蓋。5.4 節(jié)會(huì)闡述如何通過增加一些限制來使得這樣的操作是安全的。要使得跟隨者的日志進(jìn)入和自己一致的狀態(tài)，領(lǐng)導(dǎo)人必須找到最后兩者達(dá)成一致的地方，然后刪除從那個(gè)點(diǎn)之后的所有日志條目，發(fā)送自己的日志給跟隨者。所有的這些操作都在進(jìn)行附加日志 RPCs 的一

43、致性檢查時(shí)完成。領(lǐng)導(dǎo)人針對(duì)每一個(gè)跟隨者維護(hù)了一個(gè) nextIndex，這表示下一個(gè)需要發(fā)送給跟隨者的日志條目的索引地址。當(dāng)一個(gè)領(lǐng)導(dǎo)人剛獲得權(quán)力的時(shí)候，他初始化所有的 nextIndex 值為自己的最后一條日志的index加1（圖 7 中的 11）。如果一個(gè)跟隨者的日志和領(lǐng)導(dǎo)人不一致，那么在下一次的附加日志 RPC 時(shí)的一致性檢查就會(huì)失敗。在被跟隨者拒絕之后，領(lǐng)導(dǎo)人就會(huì)減小 nextIndex 值并進(jìn)行重試。最終 nextIndex 會(huì)在某個(gè)位置使得領(lǐng)導(dǎo)人和跟隨者的日志達(dá)成一致。當(dāng)這種情況發(fā)生，附加日志 RPC 就會(huì)成功，這時(shí)就會(huì)把跟隨者沖突的日志條目全部刪除并且加上領(lǐng)導(dǎo)人的日志。一旦

44、附加日志 RPC 成功，那么跟隨者的日志就會(huì)和領(lǐng)導(dǎo)人保持一致，并且在接下來的任期里一直繼續(xù)保持。如果需要的話，算法可以通過減少被拒絕的附加日志 RPCs 的次數(shù)來優(yōu)化。例如，當(dāng)附加日志 RPC 的請(qǐng)求被拒絕的時(shí)候，跟隨者可以包含沖突的條目的任期號(hào)和自己存儲(chǔ)的那個(gè)任期的最早的索引地址。借助這些信息，領(lǐng)導(dǎo)人可以減小 nextIndex 越過所有那個(gè)任期沖突的所有日志條目；這樣就變成每個(gè)任期需要一次附加條目 RPC 而不是每個(gè)條目一次。在實(shí)踐中，我們十分懷疑這種優(yōu)化是否是必要的，因?yàn)槭∈呛苌侔l(fā)生的并且也不大可能會(huì)有這么多不一致的日志。通過這種機(jī)制，領(lǐng)導(dǎo)人在獲得權(quán)力的時(shí)候就不需要任何特殊的操作來恢復(fù)

45、一致性。他只需要進(jìn)行正常的操作，然后日志就能自動(dòng)的在回復(fù)附加日志 RPC 的一致性檢查失敗的時(shí)候自動(dòng)趨于一致。領(lǐng)導(dǎo)人從來不會(huì)覆蓋或者刪除自己的日志（圖 3 的領(lǐng)導(dǎo)人只附加特性）。日志復(fù)制機(jī)制展示出了第 2 節(jié)中形容的一致性特性：Raft 能夠接受，復(fù)制并應(yīng)用新的日志條目只要大部分的機(jī)器是工作的；在通常的情況下，新的日志條目可以在一次 RPC 中被復(fù)制給集群中的大多數(shù)機(jī)器；并且單個(gè)的緩慢的跟隨者不會(huì)影響整體的性能。5.4 安全性前面的章節(jié)里描述了 Raft 算法是如何選舉和復(fù)制日志的。然而，到目前為止描述的機(jī)制并不能充分的保證每一個(gè)狀態(tài)機(jī)會(huì)按照相同的順序執(zhí)行相同的指令。例如，一個(gè)跟隨者可能會(huì)進(jìn)入

46、不可用狀態(tài)同時(shí)領(lǐng)導(dǎo)人已經(jīng)提交了若干的日志條目，然后這個(gè)跟隨者可能會(huì)被選舉為領(lǐng)導(dǎo)人并且覆蓋這些日志條目；因此，不同的狀態(tài)機(jī)可能會(huì)執(zhí)行不同的指令序列。這一節(jié)通過在領(lǐng)導(dǎo)選舉的時(shí)候增加一些限制來完善了 Raft 算法。這一限制保證了任何的領(lǐng)導(dǎo)人對(duì)于給定的任期號(hào)，都擁有了之前任期的所有被提交的日志條目（圖 3 中的領(lǐng)導(dǎo)人完整特性）。增加這一選舉時(shí)的限制，我們對(duì)于提交時(shí)的規(guī)則也更加清晰。最終，我們展示對(duì)于領(lǐng)導(dǎo)人完整特性的簡要證明并且說明領(lǐng)導(dǎo)人是如何領(lǐng)導(dǎo)復(fù)制狀態(tài)機(jī)的正確行為的。5.4.1 選舉限制在任何基于領(lǐng)導(dǎo)人的一致性算法中，領(lǐng)導(dǎo)人都必須存儲(chǔ)所有已經(jīng)提交的日志條目。在某些一致性算法中，例如 Viewsta

47、mped Replication，一個(gè)人可以被選舉為領(lǐng)導(dǎo)人即使他一開始并沒有包含所有已經(jīng)提交的日志條目。這種算法包含一些額外的機(jī)制來識(shí)別丟失的日志條目并把他們傳送給新的領(lǐng)導(dǎo)人，要么是在選舉階段要么在之后很快進(jìn)行。不幸的是，這種方法會(huì)導(dǎo)致相當(dāng)大的額外的機(jī)制和復(fù)雜性。Raft 使用了一種更加簡單的方法，它可以保證所有之前的任期號(hào)中已經(jīng)提交的日志條目在選舉的時(shí)候都會(huì)出現(xiàn)在新的領(lǐng)導(dǎo)人中，不需要傳送這些日志條目給領(lǐng)導(dǎo)人。這意味著日志條目的傳送是單向的，只從領(lǐng)導(dǎo)人傳給跟隨者，并且領(lǐng)導(dǎo)人從不會(huì)覆蓋本地日志中已經(jīng)存在的條目。Raft 使用投票的方式來阻止候選人贏得選舉除非這個(gè)候選人包含了所有已經(jīng)提交的日志條目

48、。候選人為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點(diǎn)，這意味著每一個(gè)已經(jīng)提交的日志條目肯定在這些服務(wù)器節(jié)點(diǎn)中至少存在一個(gè)上面。如果候選人的日志至少和大多數(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)的日志條目如

49、同 5.3 節(jié)介紹的那樣，領(lǐng)導(dǎo)人知道一條當(dāng)前任期內(nèi)的日志記錄是可以被提交的，只要它被存儲(chǔ)到了大多數(shù)的服務(wù)器上。如果一個(gè)領(lǐng)導(dǎo)人在提交日志條目之前崩潰了，未來后續(xù)的領(lǐng)導(dǎo)人會(huì)繼續(xù)嘗試復(fù)制這條日志記錄。然而，一個(gè)領(lǐng)導(dǎo)人不能斷定一個(gè)之前任期里的日志條目被保存到大多數(shù)服務(wù)器上的時(shí)候就一定已經(jīng)提交了。圖 8 展示了一種情況，一條已經(jīng)被存儲(chǔ)到大多數(shù)節(jié)點(diǎn)上的老日志條目，也依然有可能會(huì)被未來的領(lǐng)導(dǎo)人覆蓋掉。圖 8：如圖的時(shí)間序列展示了為什么領(lǐng)導(dǎo)人無法通過老的日志的任期號(hào)來判斷其提交狀態(tài)。在 (a) 中，S1 是領(lǐng)導(dǎo)者，部分的復(fù)制了索引位置 2 的日志條目。在 (b) 中，S1 崩潰了，然后 S5 在任期 3 里通

50、過 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 在自己的任期里復(fù)制了日志條目到大多數(shù)機(jī)器上，如 (e) 中，然后這個(gè)條目就會(huì)被提交（S5 就不可能選舉成功）。 在這個(gè)時(shí)候，之前的所有日志就會(huì)被正常提交處理。為了消除圖 8 里

51、描述的情況，Raft 通過計(jì)算副本數(shù)目的方式，使得永遠(yuǎn)不會(huì)提交一個(gè)之前任期內(nèi)的日志條目。通過計(jì)算副本數(shù)目，只有領(lǐng)導(dǎo)人當(dāng)前任期里的日志條目可以被提交；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性，之前的日志條目也都會(huì)被間接的提交。在某些情況下，領(lǐng)導(dǎo)人可以安全的知道一個(gè)老的日志條目是否已經(jīng)被提交（例如，該條目是否存儲(chǔ)到所有服務(wù)器上），但是 Raft 為了簡化問題使用一種更加保守的方法。當(dāng)領(lǐng)導(dǎo)人復(fù)制之前任期里的日志時(shí)，Raft 會(huì)在提交規(guī)則上產(chǎn)生額外的復(fù)雜性是因?yàn)樗械娜罩緱l目都保留原始的任期號(hào)。在其他的一致性算法中，如果一個(gè)新的領(lǐng)導(dǎo)人要重新復(fù)制之前的任期里的日志時(shí)，它必須使用當(dāng)前新

52、的任期號(hào)。Raft 使用的方法更加容易判斷出日志，因?yàn)樗麄內(nèi)潭际褂猛粋€(gè)任期號(hào)。另外，和其他的算法相比，Raft 中的新領(lǐng)導(dǎo)人只需要發(fā)送更少日志條目（其他算法中必須在他們被提交之前發(fā)送更多的冗余日志條目來給他們重新編號(hào)）。5.4.3 安全性論證在給定了完整的 Raft 算法之后，我們現(xiàn)在可以更加精確的討論領(lǐng)導(dǎo)人完整性特性（這一討論基于 9.2 節(jié)的安全性證明）。我們假設(shè)領(lǐng)導(dǎo)人完全性特性是不存在的，然后我們推出矛盾來。假設(shè)任期 T 的領(lǐng)導(dǎo)人（領(lǐng)導(dǎo)人 T）在任期內(nèi)提交了一條日志條目，但是這條日志條目沒有被存儲(chǔ)到該領(lǐng)導(dǎo)人未來某個(gè)任期的日志中。設(shè)大于 T 的最小任期 U 的領(lǐng)導(dǎo)人 U 沒有這條日志條

53、目。圖 9：如果 S1 （任期 T 的領(lǐng)導(dǎo)者）提交了一條新的日志在它的任期里，然后 S5 在之后的任期 U 里被選舉為領(lǐng)導(dǎo)人，然后至少會(huì)有一個(gè)機(jī)器，如 S3，既擁有來自 S1 的日志，也給 S5 投票了。1. 在領(lǐng)導(dǎo)人 U 選舉的時(shí)候一定沒有那條被提交的日志條目（領(lǐng)導(dǎo)人從不會(huì)刪除或者覆蓋任何條目）。2. 領(lǐng)導(dǎo)人 T 復(fù)制這條日志條目給集群中的大多數(shù)節(jié)點(diǎn)，同時(shí)，領(lǐng)導(dǎo)人U 從集群中的大多數(shù)節(jié)點(diǎn)贏得了選票。因此，至少有一個(gè)節(jié)點(diǎn)（投票者、選民）同時(shí)接受了來自領(lǐng)導(dǎo)人T 的日志條目，并且給領(lǐng)導(dǎo)人U 投票了，如圖 9。這個(gè)投票者是產(chǎn)生這個(gè)矛盾的關(guān)鍵。3. 這個(gè)投票者必須在給領(lǐng)導(dǎo)人 U 投票之前先接受了從領(lǐng)導(dǎo)

54、人 T 發(fā)來的已經(jīng)被提交的日志條目；否則他就會(huì)拒絕來自領(lǐng)導(dǎo)人 T 的附加日志請(qǐng)求（因?yàn)榇藭r(shí)他的任期號(hào)會(huì)比 T 大）。4. 投票者在給領(lǐng)導(dǎo)人 U 投票時(shí)依然保有這條日志條目，因?yàn)槿魏沃虚g的領(lǐng)導(dǎo)人都包含該日志條目（根據(jù)上述的假設(shè)），領(lǐng)導(dǎo)人從不會(huì)刪除條目，并且跟隨者只有和領(lǐng)導(dǎo)人沖突的時(shí)候才會(huì)刪除條目。5. 投票者把自己選票投給領(lǐng)導(dǎo)人 U 時(shí)，領(lǐng)導(dǎo)人 U 的日志必須和投票者自己一樣新。這就導(dǎo)致了兩者矛盾之一。6. 首先，如果投票者和領(lǐng)導(dǎo)人 U 的最后一條日志的任期號(hào)相同，那么領(lǐng)導(dǎo)人 U 的日志至少和投票者一樣長，所以領(lǐng)導(dǎo)人 U 的日志一定包含所有投票者的日志。這是另一處矛盾，因?yàn)橥镀闭甙四菞l已經(jīng)被

55、提交的日志條目，但是在上述的假設(shè)里，領(lǐng)導(dǎo)人 U 是不包含的。7. 除此之外，領(lǐng)導(dǎo)人 U 的最后一條日志的任期號(hào)就必須比投票人大了。此外，他也比 T 大，因?yàn)橥镀比说淖詈笠粭l日志的任期號(hào)至少和 T 一樣大（他包含了來自任期 T 的已提交的日志）。創(chuàng)建了領(lǐng)導(dǎo)人 U 最后一條日志的之前領(lǐng)導(dǎo)人一定已經(jīng)包含了那條被提交的日志（根據(jù)上述假設(shè)，領(lǐng)導(dǎo)人 U 是第一個(gè)不包含該日志條目的領(lǐng)導(dǎo)人）。所以，根據(jù)日志匹配特性，領(lǐng)導(dǎo)人 U 一定也包含那條被提交當(dāng)然日志，這里產(chǎn)生矛盾。8. 這里完成了矛盾。因此，所有比 T 大的領(lǐng)導(dǎo)人一定包含了所有來自 T 的已經(jīng)被提交的日志。9. 日志匹配原則保證了未來的領(lǐng)導(dǎo)人也同時(shí)會(huì)包

56、含被間接提交的條目，例如圖 8 (d) 中的索引 2。通過領(lǐng)導(dǎo)人完全特性，我們就能證明圖 3 中的狀態(tài)機(jī)安全特性，即如果已經(jīng)服務(wù)器已經(jīng)在某個(gè)給定的索引值應(yīng)用了日志條目到自己的狀態(tài)機(jī)里，那么其他的服務(wù)器不會(huì)應(yīng)用一個(gè)不一樣的日志到同一個(gè)索引值上。在一個(gè)服務(wù)器應(yīng)用一條日志條目到他自己的狀態(tài)機(jī)中時(shí)，他的日志必須和領(lǐng)導(dǎo)人的日志，在該條目和之前的條目上相同，并且已經(jīng)被提交?，F(xiàn)在我們來考慮在任何一個(gè)服務(wù)器應(yīng)用一個(gè)指定索引位置的日志的最小任期；日志完全特性保證擁有更高任期號(hào)的領(lǐng)導(dǎo)人會(huì)存儲(chǔ)相同的日志條目，所以之后的任期里應(yīng)用某個(gè)索引位置的日志條目也會(huì)是相同的值。因此，狀態(tài)機(jī)安全特性是成立的。最后，Raft 要求

57、服務(wù)器按照日志中索引位置順序應(yīng)用日志條目。和狀態(tài)機(jī)安全特性結(jié)合起來看，這就意味著所有的服務(wù)器會(huì)應(yīng)用相同的日志序列集到自己的狀態(tài)機(jī)中，并且是按照相同的順序。5.5 跟隨者和候選人崩潰到目前為止，我們都只關(guān)注了領(lǐng)導(dǎo)人崩潰的情況。跟隨者和候選人崩潰后的處理方式比領(lǐng)導(dǎo)人要簡單的多，并且他們的處理方式是相同的。如果跟隨者或者候選人崩潰了，那么后續(xù)發(fā)送給他們的 RPCs 都會(huì)失敗。Raft 中處理這種失敗就是簡單的通過無限的重試；如果崩潰的機(jī)器重啟了，那么這些 RPC 就會(huì)完整的成功。如果一個(gè)服務(wù)器在完成了一個(gè) RPC，但是還沒有響應(yīng)的時(shí)候崩潰了，那么在他重新啟動(dòng)之后就會(huì)再次收到同樣的請(qǐng)求。Raft 的

58、RPCs 都是冪等的，所以這樣重試不會(huì)造成任何問題。例如一個(gè)跟隨者如果收到附加日志請(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í)花費(fèi)更多的時(shí)間，候選人將不會(huì)等待太長的時(shí)間來贏得選舉；沒有一個(gè)穩(wěn)定的領(lǐng)導(dǎo)人，Raft 將無法工作。領(lǐng)導(dǎo)人選舉是 Raft 中對(duì)時(shí)間要求最為關(guān)鍵的方面。Raft 可以選舉出并維持一個(gè)穩(wěn)定的領(lǐng)導(dǎo)人除非整個(gè)系統(tǒng)滿足下面的時(shí)間要求：

59、廣播時(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í)，這樣領(lǐng)導(dǎo)人才能夠發(fā)送穩(wěn)定的心跳消息來阻止跟隨者開始進(jìn)入選舉狀態(tài)；通過隨機(jī)化選舉超時(shí)時(shí)間的方法，這個(gè)不等式也使得選票瓜分的情況變得不可能。選舉超時(shí)時(shí)間應(yīng)該要比平均故障間隔時(shí)間小上幾個(gè)數(shù)量級(jí)，這樣整個(gè)系統(tǒng)