Raft 一致性協(xié)議算法 《In search of an Understandable Consensus Algorithm (Extended Version)》

《In search of an Understandable Consensus Algorithm (Extended Version)》

Raft是一種用于管理日志復(fù)制的一致性算法。它能和Paxos產(chǎn)生同樣的結(jié)果，有著和Paxos同樣的性能，但是結(jié)構(gòu)卻不同于Paxos；Raft比Paxos更易于理解，并且能夠?yàn)閷?shí)際的系統(tǒng)構(gòu)建提供更好的基礎(chǔ)。為了增強(qiáng)可理解性，Raft將一致性涉及的例如leader 選舉, 日志復(fù)制及安全性等關(guān)鍵元素進(jìn)行了分離，并且提供了更強(qiáng)的一致性以減少必須考慮的狀態(tài)?；趯?shí)際的個人學(xué)習(xí)調(diào)查，Raft比Paxos更易于學(xué)生學(xué)習(xí)。Raft同時也包含了一種新的機(jī)制用于改變集群成員配置，并通過overlapping majority來保證安全性。

1. Introduction 一致性算法允許一群機(jī)器像一個整體一樣工作，即使其中的一些成員發(fā)生故障也不會出現(xiàn)問題。正是基于這一點(diǎn)，它在構(gòu)建可靠的大規(guī)模軟件系統(tǒng)的過程中起著關(guān)鍵的作用。Paxos一直主導(dǎo)著過去十年對 一致性算法的討論：許多一致性算法的實(shí)現(xiàn)都是以Paxos為基礎(chǔ)或者受到它的影響，并且Paxos已經(jīng)成為了用來教授學(xué)生關(guān)于一致性算法的主要工具。 不幸的是，Paxos太難以理解了，盡管已經(jīng)做了很多嘗試想使它變得更加平易近人。另外，為了支持實(shí)際的系統(tǒng)構(gòu)建，它的結(jié)構(gòu)也需要做出非常復(fù)雜的改變。因此，系統(tǒng)架構(gòu)師和學(xué)生都對Paxos感到很痛苦。 在我們自己和Paxos經(jīng)歷了一番痛苦掙扎之后，我們決定發(fā)明一種新的一致性算法來為系統(tǒng)的構(gòu)建和教學(xué)提供更好的基礎(chǔ)。我們的主要目標(biāo)有點(diǎn)特別，是為了讓它更加易于理解：我們要為實(shí)際的系統(tǒng)構(gòu)建定義一個比Paxos更加易于理解的一致性協(xié)議。此外，我們希望該算法能夠培養(yǎng)系統(tǒng)構(gòu)建者的開發(fā)直覺。而這對系統(tǒng)構(gòu)建者是必不可少的。能讓算法正常工作很重要，但是能讓別人清除的知道它是怎樣工作更加重要。

   這項(xiàng)工作的結(jié)果就是一個叫做Raft的一致性算法。在設(shè)計(jì)Raft的時候，我們使用了一些額外的技術(shù)用于增加可理解性，包括分割（Raft分離了leader 選舉, 日志復(fù)制及安全性）以及狀態(tài)空間的減少（和Paxos相比，Raft降低了不確定性以及sever之間能達(dá)到一致的方法）。一個由來自兩個大學(xué)的43位學(xué)生組成的用戶調(diào)查顯示Raft要比Paxos易于理解的多；在同時學(xué)習(xí)了兩種方法之后，其中的33名學(xué)生回答Raft的問題要比回答Paxos更好。 Raft在很多方面和現(xiàn)存的一致性算法類似，但是它也有以下這些獨(dú)特的特性： Strong leader：Raft有著比其他一致性算法更強(qiáng)形式的leadership。例如，日志條目只能從leader流向其他server。這簡化了對于日志復(fù)制的管理并且使Raft更加易于理解。 Leader election：Raft使用隨機(jī)的時鐘來選舉leader。這只是在一致性算法原有的心跳檢測的基礎(chǔ)上增加了少量的特殊機(jī)制。使得解決沖突變得更加簡答單快速。 Membership changes：Raft通過一種新的joint consensus的方法來實(shí)現(xiàn)server集合的改變，其中兩個不同配置下的majority在過度階段會發(fā)生重合。這能讓集群在配置改變時也能繼續(xù)正常運(yùn)行。 我們相信不論對于教學(xué)還是作為系統(tǒng)實(shí)現(xiàn)的基礎(chǔ)，Raft都要優(yōu)于Paxos和其他的一致性算法。它比其他算法更簡答也更加易于理解；它能完全滿足實(shí)際系統(tǒng)的需求；它有很多開源的實(shí)現(xiàn)并且被很多公司使用；它的安全性已經(jīng)被完全證實(shí)了；并且它的效率也完全可以和其他算法相媲美。 論文的第2章介紹了狀態(tài)機(jī)的相關(guān)問題，第3章描述了Paxos的優(yōu)缺點(diǎn)，第4章介紹了我們達(dá)成可理解性目標(biāo)的一般方法，第5到8章詳細(xì)介紹了 Raft一致性算法，第9章描述了對Raft的評估，第10章討論了于Raft相關(guān)一些成果。

2. Replicated State Machine 一致性算法是在復(fù)制狀態(tài)機(jī)的背景下提出來的。在這個方法中，一組服務(wù)器上的狀態(tài)機(jī)對同一個狀態(tài)計(jì)算產(chǎn)生多個完全相同的副本，這使得即使其中一些服務(wù)器崩潰了，這組服務(wù)器也還可以繼續(xù)正常執(zhí)行。復(fù)制狀態(tài)機(jī)通常用于解決分布式系統(tǒng)中容錯相關(guān)的一系列問題。例如，GFS，HDFS， RAMCloud，這些擁有單一集群領(lǐng)導(dǎo)者的大規(guī)模應(yīng)用系統(tǒng)，會使用一個獨(dú)立的復(fù)制狀態(tài)機(jī)來管理領(lǐng)導(dǎo)選取及存儲集群配置信息來應(yīng)對領(lǐng)導(dǎo)者的崩潰。復(fù)制狀態(tài)機(jī)典型的例子包括 Chubby 和 ZooKeeper。

如圖-1所示，復(fù)制狀態(tài)機(jī)功能時通過日志復(fù)制來實(shí)現(xiàn)。每臺服務(wù)器存儲一份包含一系列命令的日志，內(nèi)部狀態(tài)機(jī)依照日志中的命令順序執(zhí)行。因?yàn)槊颗_機(jī)器的狀態(tài)機(jī)都是確定的，所以計(jì)算將得到同樣的狀態(tài)和輸出結(jié)果。 一致性算法的任務(wù)就是保證復(fù)制日志的一致性。服務(wù)器上的一致性模塊，接收來自客戶端的命令，并追加到日志中。它和其它服務(wù)器上的一致性模塊進(jìn)行通信，確保每一個服務(wù)器上的日志都包含相同順序的相同請求。即使其中的一些服務(wù)宕機(jī)了。請求命令復(fù)制完成后，狀態(tài)機(jī)會按照日志中的命令順序進(jìn)行執(zhí)行。并將結(jié)果返回給客戶端。由此，這些服務(wù)器就構(gòu)成了表面統(tǒng)一的，高可靠性的復(fù)制狀態(tài)機(jī)。 實(shí)際應(yīng)用中的一致性算法通常具有以下特性： 確保非拜占庭（Non-Byzantine）情況下的安全性（從來不會返回一個錯誤的結(jié)果），包括網(wǎng)絡(luò)的延遲、分區(qū)及數(shù)據(jù)包的丟包、冗余和亂序情況。（Byzantine fail 分布式系統(tǒng)容錯問題） 高可用性，只要集群中的主體大多數(shù)機(jī)器能夠運(yùn)行，可以互相通信及和客戶端通信，這個集群就可用。因此，一個擁有 5 臺機(jī)器的集群最多可以容忍其中的 2 臺的宕機(jī)（fail）。 Server發(fā)生故障時，可以認(rèn)為是暫停了；它們可能稍后會恢復(fù)到存儲在stable storage中的狀態(tài)并且重新加入集群。 不依賴 timing 保證一致性，時鐘錯誤和極端情況下的消息延遲至多只會引起可用性問題。 通常情況下，一條命令能夠盡可能快的在大多數(shù)節(jié)點(diǎn)對一輪遠(yuǎn)程調(diào)用作出響應(yīng)時完成，少部分慢的機(jī)器不會影響系統(tǒng)的整體性能。

1. Paxos 近十年以來，Leslie Lamport 的 Paxos 算法幾乎成為了一致性算法的代名詞：它是授課中最常講授的算法，同時也是許多一致性算法實(shí)現(xiàn)的起點(diǎn)。Paxos 首先定義了一個能夠在單一決策基礎(chǔ)上達(dá)成一致的協(xié)議，例如一個單一復(fù)制的日志條目（single replicated log entry）。我們把這個子集叫做單一決策 Paxos（single-decree Paxos）。 之后Paxos可以將該協(xié)議的多個實(shí)例組合在一起去形成一系列的decision作為log（multi-Paxos）。Paxos保證了safety和liveness，并且它支持cluster membership的改變。它的正確性已經(jīng)被證明了并且在一般的情況下也被證明是高效的。 不幸的是，Paxos 有兩個明顯的缺點(diǎn)。第一個是 Paxos 太難以理解。它的完整說明更是出乎尋常的晦澀；很少有人能完全理解。 因此，已經(jīng)做了很多嘗試，試圖用一個更簡單的版本解釋Paxos。雖然它們都著力于single-decree版本，但是仍然非常具有挑戰(zhàn)性。在一項(xiàng)針對NSDI 2012與會者的調(diào)查中，我們發(fā)現(xiàn)很少有人對Paxos感到舒服，即使是那些經(jīng)驗(yàn)豐富的研究人員。我們自己也對Paxos感到非常痛苦，我們在不能理解完整的協(xié)議，直到我們閱讀了幾個簡化版的描述以及設(shè)計(jì)了我們自己的替代協(xié)議，而這整個過程持續(xù)了將近一年。 我們認(rèn)為Paxos的晦澀來源于它將single-decree subset作為自己的基礎(chǔ)。Single-decree Paxos被認(rèn)為是微妙的：它被劃分為兩個不能用直覺來顯示的階段并且不能單獨(dú)理解。因此，這就導(dǎo)致了很難對single-decree protocol是如何工作的建立起直覺。而multi-Paxos的composition rule則更加添加了復(fù)雜性。我們堅(jiān)信對于在multiple decision的情況下到達(dá)consensus這個問題肯定能以其他更直接，更明顯的方式被分解。 Paxos的第二個問題是它并沒有為實(shí)際的實(shí)現(xiàn)提供一個很好的基礎(chǔ)。一大原因是對于multi-Paxos沒有一個廣受認(rèn)可的算法。Lamport的描述主要針對的是single-decree Paxos；它為multi-Paxos提供了一個大概的框架，但是很多細(xì)節(jié)并沒有提及。對于充實(shí)以及優(yōu)化Paxos已經(jīng)做了很多努力，但是它們各自之間，以及和Lamport的概述都不相同。像Chubby這樣的系統(tǒng)已經(jīng)實(shí)現(xiàn)了類Paxos算法，但是它的很多細(xì)節(jié)并沒有公開。 另外，Paxos的架構(gòu)也不利于構(gòu)建實(shí)際系統(tǒng)；這是它按single-decree分解的另一個后果。例如，獨(dú)立地選取一系列的log entry并且將它們?nèi)诤铣梢粋€順序的log并沒有太多好處，僅僅只是增加了復(fù)雜度。相反，構(gòu)建一個圍繞按順序擴(kuò)展log的系統(tǒng)是更簡單和高效的。Paxos的另一個問題是它將對稱的peer-to-peer作為核心（雖然在最后為了優(yōu)化性能建議了一種弱形式的leadership）。這在只需要做一個decision的簡單場景中是可行的，但是很少有實(shí)際的系統(tǒng)會使用這種方法。如果要有一系列的decision要決定，那么先選擇一個leader，然后再讓leader去協(xié)調(diào)decision。 因此，實(shí)際系統(tǒng)很少和Paxos類似。各種實(shí)現(xiàn)都以Paxos開始，然后發(fā)現(xiàn)實(shí)現(xiàn)起來很困難，于是最后開發(fā)出了一個完全不同的架構(gòu)。這是極其費(fèi)時并且容易出錯的，而Paxos的難以理解則更加加劇了這個問題。Paxos的正確性理論很好證明，但是實(shí)際的實(shí)現(xiàn)和Paxos太過不同，因此這些證明就沒什么價值了。接下來這段來自Chubby的評論是非常典型的： Paxos算法的描述和現(xiàn)實(shí)世界的系統(tǒng)的需求之間有巨大的矛盾....而最終的系統(tǒng)都將建立在一個未經(jīng)證明的協(xié)議之上 因?yàn)檫@些問題的存在，我們得出這樣的結(jié)論，Paxos并沒有為實(shí)際系統(tǒng)的構(gòu)建或者是教學(xué)提供一個很好的基礎(chǔ)?；谠诖笠?guī)模軟件系統(tǒng)中consensus的重要性，我們決定嘗試能否設(shè)計(jì)出另外一種比Paxos有著更好性質(zhì)的consensus algorithm。而Raft就是我們實(shí)驗(yàn)得到的結(jié)果。

2. Designing for understandability 我們在設(shè)計(jì)Raft的時候有一下幾個目標(biāo)：它必須為系統(tǒng)構(gòu)建提供完整，實(shí)際可行的基礎(chǔ)，這將大大減少系統(tǒng)開發(fā)者的設(shè)計(jì)工作。在任何情況下都必須確保安全性，并且保證在典型應(yīng)用情境下的可用性。在通常的應(yīng)用操作中必須是高效的。另外，我們最重要的一點(diǎn)，也是最具挑戰(zhàn)性的一點(diǎn)是它必須易于理解，使我們廣大的讀者能夠很好的理解這個算法。 并且要能夠建立對這個算法的直覺，從而讓系統(tǒng)構(gòu)建者能做一些實(shí)際實(shí)現(xiàn)中必要的擴(kuò)展。 在設(shè)計(jì)Raft的很多節(jié)點(diǎn)上，我們要在很多可選方法之間做出選擇。在這些情況下，我們基于可理解性對這些方法進(jìn)行評估：對于每一個可選方案的描述是否困難（比如，它的狀態(tài)空間的復(fù)雜度是多少，以及它是否有subtle implication？）以及讀者是否能輕松地完全理解這種方法。 后來我們意識到這種分析方法具有很強(qiáng)的主觀性；于是我們使用了兩種方法讓分析變得更具通用性。第一種是關(guān)于問題分解的眾所周知的方法：是否有可能，我們可以將問題分解為可以被相對獨(dú)立地解釋，理解并且被解決的幾部分。例如，在Raft中，我們分解了leader election, log replication, safety和membership changes這幾部分。 我們的第二種方法是通過減少需要考慮的狀態(tài)數(shù)，盡量讓系統(tǒng)更一致以及盡可能地減少非確定性，來簡化state space。另外，log不允許存在hole，Raft限制了log之間存在不一致的可能。雖然在大多數(shù)情況下，我們都要減少不確定性，但是在某些情況下，不確定性確實(shí)提高了可理解性。特別地，隨機(jī)化的方法會引入不確定性，但是通過以相同的方式處理所有可能的選擇（choose any; it doesn't matter），確實(shí)減少了state space。我們就使用了隨機(jī)化來減少了Raft的leader election algorithm。
3. Raft 一致性算法 Raft是用于管理文章第二部分描述的復(fù)制日志算法。圖2是對Raft的簡要描述；圖3羅列了算法的一些重要屬性；接下來將會對圖示部分進(jìn)行分段討論。

狀態(tài)：

在所有服務(wù)器上持久存在的：（在響應(yīng)RPCs之前進(jìn)行更新）

currentTerm 服務(wù)器最后知道的任期號（服務(wù)啟動時，初始化為0，單調(diào)遞增）

votedFor 在當(dāng)前任期內(nèi)收到的選票的候選人 id（如果沒有就為 null）

log[] 日志條目；每個條目包含狀態(tài)機(jī)的要執(zhí)行命令及從leader處得到的任期號

在所有服務(wù)器上不穩(wěn)定存在的：

commitIndex 已知的被提交的最大日志條目的索引值（初始化為0，單調(diào)遞增）

lastApplied 被狀態(tài)機(jī)執(zhí)行的最大日志條目的索引值（初始化為0，單調(diào)遞增）

在領(lǐng)導(dǎo)人服務(wù)器上不穩(wěn)定存在的：（每次選舉之后重新初始化）

nextIndex[] 對于每一個服務(wù)器，需要發(fā)給它的下一個日志條目的索引（初始化為領(lǐng)導(dǎo)人上一條日志的索引值+1）

matchIndex[] 對于每一個服務(wù)器，已復(fù)制到該服務(wù)器的日志條目的最高索引值（初始化為0，單調(diào)遞增）

日志追加 AppendEntries RPC

由leader發(fā)起日志復(fù)制（5.3節(jié)）；同時也用作心跳檢測 參數(shù)

term 領(lǐng)導(dǎo)人的任期號

leaderId leader id，為了其他服務(wù)器能夠重定向客戶端到leader

prevLogIndex 當(dāng)前日志之前的日志的索引值

prevLogTerm 當(dāng)前日志之前的日志的leader任期號

entries[] 將要存儲的日志條目（心跳檢測RPCs時為空，一條或多條）

leaderCommit 領(lǐng)導(dǎo)人提交的日志條目索引值

返回值

term 當(dāng)前的任期號，用于領(lǐng)導(dǎo)人更新自己的任期號

success 如果follower服務(wù)器包含能夠匹配上 prevLogIndex 和 prevLogTerm 的日志時返回true

接收者實(shí)現(xiàn)： 自身攜帶的任期號小于當(dāng)前任期號（term < currentTerm），則返回 false（5.1節(jié)） 沒有任期號與prevLogTerm相匹配，索引為prevLogIndex的日志條目，則返回 false（5.3節(jié)） 如果已經(jīng)存在的日志條目與新的日志條目沖突（索引：index相同但是任期號：term 不同），則刪除此日志條目及它之后所有的日志條目（5.3節(jié)） 添加任何在已有的日志中不存在的新條目 如果 leaderCommit > commitIndex，將commitIndex設(shè)置為leaderCommit和最新日志條目索引號中較小的那一個。

投票請求 RequestVote RPC

由候選人發(fā)起，收集選票（5.2節(jié)）

參數(shù)

term candidate的任期號

candidateId 請求投票的candidate id

lastLogIndex candidate最新日志條目的索引值

lastLogTerm candidate最新日志條目對應(yīng)的任期號

返回值

term 當(dāng)前的任期號，用于candidate更新自己任期號

voteGranted 如果 candidate 收到選票則返回 true

接收者需要實(shí)現(xiàn)： 自身攜帶的任期號小于當(dāng)前任期號（term < currentTerm），則返回 false（5.1節(jié)） 如果votedFor為空或者是candidateId，并且candidate的日志至少和自己的日志一樣新，則給該candidate投票（5.2節(jié) 和 5.4節(jié)）

服務(wù)器規(guī)則： 所有服務(wù)器： 如果commitIndex > lastApplied，lastApplied自增，將log[lastApplied]應(yīng)用到狀態(tài)機(jī)（5.3節(jié)） 如果 RPC 的請求或者響應(yīng)中的任期號 term T 大于 currentTerm，則將currentTerm賦值為 T，并切換狀態(tài)為追隨者（Follower）（5.1節(jié)） 追隨者（followers）: 5.2節(jié) 響應(yīng)來自候選人和領(lǐng)導(dǎo)人的 RPC 選舉超時后，未收到來自前領(lǐng)導(dǎo)人的AppendEntries RPC，或者投票給候選人，則自己轉(zhuǎn)換狀態(tài)為候選人。 候選人：5.2節(jié) 轉(zhuǎn)變?yōu)檫x舉人之后開始選舉： currentTerm自增 給自己投票 重置選舉計(jì)時器 向其他服務(wù)器發(fā)送RequestVote RPC 如果收到了來自大多數(shù)服務(wù)器的投票：則成為領(lǐng)導(dǎo)人 如果收到了來自新領(lǐng)導(dǎo)人的AppendEntries RPC（heartbeat）：轉(zhuǎn)換狀態(tài)為追隨者 如果選舉超時：開始新一輪的選舉 領(lǐng)導(dǎo)人： 選舉時：向其他服務(wù)器發(fā)送空的AppendEntries RPC（heartbeat）；在空閑時間重復(fù)發(fā)送以防止選舉超時（5.2節(jié)） 如果收到來自客戶端的請求：添加條目到本地日志，日志條目應(yīng)用到狀態(tài)機(jī)后響應(yīng)客戶端（5.3節(jié)） 如果上一次收到的追隨者的日志索引大于將要發(fā)送給追隨者的的日志索引（nextIndex）：則通過AppendEntries RPC將 nextIndex 之后的所有日志條目發(fā)送給追隨者。 發(fā)送成功：則將該追隨者的 nextIndex和matchIndex更新 如果由于日志不一致導(dǎo)致AppendEntries RPC失?。簩extIndex遞減并且重新發(fā)送（5.3節(jié)） 如果存在一個數(shù)N，滿足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，則將commitIndex賦值為 N

選舉安全性：一個任期只能有一個leader當(dāng)選

leader 只追加：leader不覆蓋或者刪除自身的日志條目，只追加新條目

日志匹配：如果兩個日志包含一個索引和任期都相同的條目，那么日志中此條目索引之后的所有條目都相同

leader 完整性：如果一個日志條目在一個任期內(nèi)被提交，那么次條目將會呈現(xiàn)在之后任期的leader的日志中。

狀態(tài)機(jī)安全性：當(dāng)一個服務(wù)器在它自己的狀態(tài)機(jī)上應(yīng)用了一個指定索引的日志條目后，其它服務(wù)器狀態(tài)機(jī)將不會出現(xiàn)應(yīng)用同樣索引的不同日志條目情況

Raft首先選舉出一個唯一的leader，并賦予完全的管理日志復(fù)制的責(zé)任。leader接收來自客戶端的日志條目并復(fù)制到其它服務(wù)器，同時將日志條目追加到自身日志，然后告知其它服務(wù)器（Append Entries RPCs with leaderCommit）可以應(yīng)用日志條目到狀態(tài)機(jī)。leader大大簡化了日志復(fù)制的管理。例如，leader可以自主決定日志條目的追加位置，數(shù)據(jù)以一種簡單的方式從leader流向其它服務(wù)器。leader可能宕機(jī)或者失聯(lián)，此時需要進(jìn)行l(wèi)eader選舉。 對于leader選舉，Raft將這一一致性問題分解為三個相對獨(dú)立的子過程進(jìn)程處理。 leader選舉：leader宕機(jī)，則進(jìn)行新的leader選舉 leader必須能夠接收客戶端的日志條目，并復(fù)制到集群中的其它服務(wù)器，強(qiáng)制其它服務(wù)器的日志與自己的日志同步。 安全性：狀態(tài)機(jī)的安全性保障，當(dāng)一個服務(wù)器在它自己的狀態(tài)機(jī)上應(yīng)用了一個指定索引的日志條目后，其它服務(wù)器狀態(tài)機(jī)將不會出現(xiàn)應(yīng)用同樣索引的不同日志條目情況，5.4描述了如何保障這一特性，

5.1 Raft basics 一個 Raft 集群包括若干個服務(wù)器；對于一個典型的 5 服務(wù)器集群來說，最多能夠容忍 2 臺服務(wù)器宕機(jī)。集群運(yùn)行期間，服務(wù)器會處于特定的三個狀態(tài)：leader 、follower、candidate。正常情況下，只有一個服務(wù)器處于leader狀態(tài)，其它的都是follower。follower是被動的：他們不發(fā)送任何請求，只是響應(yīng)來自leader和candidate的請求。leader來處理所有來自客戶端的請（如果一個客戶端與follower進(jìn)行通信，follower會將請求信息轉(zhuǎn)發(fā)給leader）。candidate是用來選取新的領(lǐng)導(dǎo)人的。圖-4 闡述了這些狀態(tài)及它們之間的轉(zhuǎn)換。

Raft將時間劃分為長度不同的任期（term），任期以連續(xù)的證書命名，每一個任期以leader選舉開始，一個或多個candidate競爭成為leader，當(dāng)一個candidate競選成功，那么它就轉(zhuǎn)換為leader，負(fù)責(zé)任期內(nèi)的管理。一些特殊情況下，選舉會進(jìn)入裂鬧狀態(tài)而失敗，那么這一任期就沒有l(wèi)eader，新的任期會隨即開始，Raft保證一個任期至多有一個領(lǐng)導(dǎo)者。 任期（term）作為Raft的邏輯時鐘，是的服務(wù)器能夠檢測到過期信息，如過期的leader，每個服務(wù)器都存儲著一個當(dāng)前任期數(shù)字，數(shù)字隨任期單調(diào)遞增，服務(wù)器間通信時會相互交換任期信息。如果一個服務(wù)器的任期信息比其它的服務(wù)器小，那么就更新自己的任期到當(dāng)前較大的任期。如果leader 或者 candidate發(fā)現(xiàn)自己的任期信息已經(jīng)過時，那么它們會立即轉(zhuǎn)換狀態(tài)為follower。當(dāng)一個服務(wù)器收到一個過期任期信息的請求時，會拒絕這個請求。 Raft服務(wù)器間通過RPC方式進(jìn)行通信，基礎(chǔ)的一致性協(xié)議只需要兩種請求信息：Request Vote RPCs（選舉使用），Append Entries RPCs（復(fù)制日志及心跳檢測時使用）。如果服務(wù)器收不到回復(fù)，會重新嘗試請求。服務(wù)器采用并行機(jī)制發(fā)送RPC請求。 5.2 Leader election Raft使用心跳機(jī)制（heartbeat）來觸發(fā)leader選取。服務(wù)器啟動時，處于follower狀態(tài)，并且保持這種狀態(tài)直到接收到來自leader或者candidate的合法RPCs。leader定時發(fā)送心跳RPCs給所有的follower，以保持自身leader角色。如果一個follwer在一定的時間內(nèi)未收到來自leader的心跳信息，則判定leader下線并開始新一輪的leader選舉。 開始選舉時，follower首先遞增自身的任期并將狀態(tài)切換為candidate。然后標(biāo)識voteFor為自己，并發(fā)送Request Vote RPCs到集群中所有其它的服務(wù)器。candidate會一直保持自身狀態(tài)，直到一下三種情況任何一種發(fā)生：贏得選舉，成為leader；其它c(diǎn)andidate贏得選舉；選舉超時，未能成功選出leader。以下，我們將詳細(xì)就此予以討論。 一個candidate獲得集群中同一任期內(nèi)大多數(shù)服務(wù)器的投票，則判定贏得選舉。每一個服務(wù)器至多只能投一次票。按照先到先服務(wù)（first-come-first-served），“大多數(shù)”的原則能夠保障一個任期內(nèi)只會有至多一個candidate能夠贏得選舉。一旦一個candidate贏得選舉，成為領(lǐng)導(dǎo)者，它會立即發(fā)送心跳消息到所有其它的服務(wù)器，告知自身leader狀態(tài)，阻止新一輪的leader選舉。 candidate選舉期間，會不斷收到其它候選人發(fā)送 Request Vote RPCs，如果接收到的請求中的任期號大于等于candidate的當(dāng)前任期號，則candidate認(rèn)可當(dāng)前投票，并將自身轉(zhuǎn)換為follower狀態(tài)。如果接收到的請求中的任期號小于candidate當(dāng)前的任期號，則candidate拒絕此次請求，并繼續(xù)保持candidate狀態(tài)。 第三種可能的結(jié)果，即選舉失敗：同一時間，過多follower成為candidate，啟動選舉時，投票被過分的分割，將沒有candidate能夠獲得“大多數(shù)”投票。當(dāng)這一情況發(fā)生，所有的選舉都將進(jìn)入選舉超時狀態(tài)，候選人又會重新發(fā)起新一輪選舉。然而，如果不采取額外的措施，split votes將會無限的重復(fù)發(fā)生。 Raft使用隨機(jī)的選舉超時時間來確保split votes很少發(fā)生，或者即使發(fā)生了，也能很快解決。為了在一開始就避免split votes 發(fā)生，Raft將選舉超時設(shè)定為150~300ms之間的一個隨機(jī)值。這就使得服務(wù)器能夠很好的分散開來，大多數(shù)情況下，同一時間，只會有一個服務(wù)器發(fā)生選舉超時。當(dāng)一個服務(wù)器贏得選舉，它能夠在其它服務(wù)器選舉超時之前向他們發(fā)送心跳信息。每一個candidate在選舉開始時，重置一個隨機(jī)的選舉超時時間，然后等待超時時間到來后，重新啟動下一輪選舉。這就大大減少了下一次選舉時split votes現(xiàn)象的發(fā)生。 選舉這一例子很好的展示了我們是如何根據(jù)可理解性做出設(shè)計(jì)選擇的。期初。我們計(jì)劃使用評級系統(tǒng)，每一個candidate賦予一個唯一的評級，以用于競爭選擇。當(dāng)一個candidate發(fā)現(xiàn)其它的candidate的評級比自身高，則將自己轉(zhuǎn)換為follower狀態(tài)，這樣評級較高的candidate就能更容易的贏得選舉。但是，我們發(fā)現(xiàn)這一方法，在可用性方面的一些微妙的問題（當(dāng)高評級的candidate選舉失敗后，低評級的candidate需要等待選舉超時到來后，才能開始下一輪的選舉）。我們隊(duì)算法做了很多次調(diào)整，但每一次的調(diào)整，都會伴隨著新的問題出現(xiàn)。最終，我們得出結(jié)論，隨機(jī)重試這種方法表現(xiàn)的更明確，更易于理解。 5.3 Log replication

一旦一個leader成功獲得選舉，它就開始接收處理客戶端請求，每個客戶端請求都包含一條需要狀態(tài)機(jī)執(zhí)行的命令。leader將命令最為新條目追加到自身日志中，同時發(fā)送Append Entries RPCs到其它服務(wù)器，進(jìn)行日志條目復(fù)制。當(dāng)所有的服務(wù)器復(fù)制完成日志條目后，leader自身狀態(tài)機(jī)開始執(zhí)行這一命令，并將結(jié)果返回給客戶端。如果發(fā)生follower宕機(jī)或者運(yùn)行緩慢，網(wǎng)絡(luò)包丟失等情況，leader會無限次重試發(fā)送Append Entries RPCs，直到所有的follower成功復(fù)制所有的日志條目。

日志存儲形式如上圖6，每一個日志條目都存儲著一條狀態(tài)機(jī)命令和一個任期號，任期號主要用于發(fā)現(xiàn)日志條目的不一致及其它一些圖3中說明的一些屬性。每一個日志條目都有一個整形索引屬性，標(biāo)識當(dāng)前條目在日志中的存儲位置。 leader決定什么時候讓狀態(tài)機(jī)執(zhí)行日志條目是安全的，而這一日志條目稱之為commited。Raft保障所有commited都是持久的，并且最終都會被集群中所有的狀態(tài)機(jī)所執(zhí)行。當(dāng)一個日志條目被集群的眾大多數(shù)服務(wù)器成功復(fù)制后，它就會被leader commited，這一過程同時也會將此條目之前的所有日志條目一并commited，包括之前任期leader創(chuàng)建的條目。leader 會一直跟蹤最新commited的日志條目索引，并將它包含在隨后的Append Entries RPCs（包括心跳）中，以便其它服務(wù)器識別，并應(yīng)用到自身狀態(tài)機(jī)。 Raft的日志管理機(jī)制能夠保障各個服務(wù)器間的日志的高度一致性。這不僅極大的簡化了系統(tǒng)的行為，提升了可預(yù)測性，同時也是安全機(jī)制重要的組成部分。Raft確保日志的以下特性：如果兩個日志中的日志條目的任期號和索引都相同，則他們存儲的command也相同；如果兩個日志中的日志條目的任期號和索引都相同，則之前的所有條目也都相同。這兩個特性和圖3中的日志屬性，共同組成了 Log Matching 屬性。 第一個特性說明，leader在一個日志索引位置至多只會創(chuàng)建一個日志條目，并且日志中的條目位置都是固定的。第二個特性是由Append Entries執(zhí)行一個簡單的一致性檢查老保障的。在發(fā)送Append Entries RPCs時，leader會將要發(fā)送的最新條目之前的條目索引（preLogIndex）及任期號（preLogTerm）包含進(jìn)去，如果follower在其日志中找不到匹配preLogIndex及preLogTerm的日志條目，則拒絕接受發(fā)送的新的日志條目。一致性檢查執(zhí)行符合遞進(jìn)歸納特性：初始的空日志滿足Log Matching Property，隨著每一次日志擴(kuò)充，一致性檢查都確保符合Log Matching Property。由此，leader能夠通過Append Entries RPCs返回的成功結(jié)果，判定所有的follower的當(dāng)前及后續(xù)日志都會和自己的日志保持一致。 正常情況下，leader和follower的日志能夠保持一致。所以Append Entries的一致性檢查不會返回失敗。但是。當(dāng)leader宕機(jī)時，就會引發(fā)日志的不一致（舊的leader可能會有一部分日志還沒有成功復(fù)制到follower）。日志的不一致會隨著一系列l(wèi)eader和follower的宕機(jī)變得更加嚴(yán)重。如圖7所示：

follower可能和新的leader的日志不同，follower可能含有l(wèi)eader沒有的日志條目，也可能缺少leader已有的日志條目，或者兩種情況都有。日志條目的丟失和多余可能涉及多個日志條目。 Raft協(xié)議中，leader通過強(qiáng)制follower復(fù)制自己的日志來處理日志的不一致問題。follower中不一致的條目將會被leader中的條目覆蓋。 為了使follower的日志和自己保持一致，leader首先需要找到和follower日志中能夠保持一致的最新的日志條目索引，然后，刪除follower中此索引之后的所有條目并發(fā)送leader中此條目之后的所有條目到follower。所有這些操作都是由AppendEntries的一致性檢查引發(fā)執(zhí)行。leader對每一個follower都維護(hù)著一個nextIndex變量，nextIndex代表下一個將要發(fā)送到follower的日志條目的索引。當(dāng)一個leader最開始負(fù)責(zé)管理，leader會將所有follower的nextIndex初始化為最后一個日志條目的下一個索引。如果follower的日志不一致，AppendEntries的一致性檢查就會在下一次的Append Entries RPCs中返回失敗。一次失敗后，leader機(jī)會將此follower的nextIndex減1，然后重新發(fā)送Append Entries RPCs，以此，循環(huán)往復(fù)，直到找到一個leader和follower的日志能通過AppendEntries的一致性檢查的nextIndex值。此時AppendEntries就會刪除follower中此索引之后所有的日志條目，并復(fù)制leader此索引之后所有的日志條目到follower，從而保障leader和follower的日志一致性。并且在接下來的任期內(nèi)也一致保持。 如果愿意的話，協(xié)議還可以通過減少失敗的Append Entries RPCs次數(shù)來進(jìn)行優(yōu)化。例如，當(dāng)拒絕AppendEntries RPCs時，follower可以將沖突的條目的任期和此任期內(nèi)存儲的第一個條目返回給leader。這樣leader就可將nextIndex直接減去所有沖突的條目最早的條目。一個任期內(nèi)的日志條目沖突只需要一次AppendEntries RPCs就可以，而不需要像之前那樣每個條目一次AppendEntries RPCs。但是在實(shí)際應(yīng)用中，我們認(rèn)為此優(yōu)化時完全沒必要的。因?yàn)锳ppendEntries RPCs請求失敗并不是經(jīng)常發(fā)生，并且好像也不會有很多沖突的日志條目。 通過這種機(jī)制，當(dāng)一個leader開始負(fù)責(zé)管理時，不需要采用任何額外的措施來恢復(fù)日志的一致性。它只需要執(zhí)行正常的操作，日志自會隨著AppendEntries的一致性檢查自動收斂。leader永遠(yuǎn)不會覆蓋自身的日志條目。 這種日志復(fù)制機(jī)制展示了我們在第二部分描述的一致性屬性：Raft只要在大多數(shù)服務(wù)器正常運(yùn)行的情況下就能執(zhí)行日志條目的接收，復(fù)制和應(yīng)用。正常情況下一次RPCs就能完成一個日志條目的復(fù)制，單個follower的操作延遲不影響整體性能。 5.4 Safety 之前的章節(jié)討論了Raft算法是如何進(jìn)行領(lǐng)導(dǎo)選舉和日志復(fù)制的。但是，到目前為止所描述的機(jī)制并不能很有效的保證每一個狀態(tài)機(jī)以同樣的順序執(zhí)行執(zhí)行同樣的命令。例如，一個follower離線期間，leader提交了一些日志條目?；謴?fù)正常后，被選舉為leader，然后使用新的日志條目覆蓋掉之前l(fā)eader提交而未成功被復(fù)制的那些條目。這樣，不同服務(wù)器的狀態(tài)機(jī)就可能執(zhí)行了不同的命令序列。 這一章節(jié)對于可能會被選為leader的服務(wù)器添加了一些限制。使得特定任期內(nèi)的leader能夠包含之前任期內(nèi)提交的日志條目。通過增加這些選舉限制，我們進(jìn)一步細(xì)化了提交規(guī)則。最后，我們呈現(xiàn)了e Leader Completeness Property的證明草圖并且展示了它是如何指導(dǎo)狀態(tài)機(jī)正確的執(zhí)行的。 5.4.1 Election restriction 在任何leader-based的一致性算法中，leader最終都必須保存著所有提交的日志條目。Raft使用一種簡單的方法使得之前l(fā)eader提交的日志條目能夠在一選舉出新leader時就能完整的呈現(xiàn)在的leader上，而不需要任何的傳送。這就意味著，日志條目只會從leader流向follower，leader永遠(yuǎn)不會覆蓋已有的日志條目。 Raft控制選舉過程，只有當(dāng)candidate的日志包含所有已提交的日志條目時，它才能夠被選舉為leader。參與選舉期間，candidate需要與大多數(shù)服務(wù)器進(jìn)行通信，同時，我們知道，集群大多數(shù)原則，每一個日志條目必須存在于大多數(shù)的服務(wù)器中至少一個服務(wù)器上。這樣，當(dāng)一個candidate滿足自己的日志至少比大多數(shù)服務(wù)器中任何一個服務(wù)器的日志新時，它就存儲了及群眾所有已提交的日志條目。Request Vote RPCs實(shí)現(xiàn)了這種限制：請求中包含candidate的日志信息，如果投票服務(wù)器的日志條目比candidate的日志新，則會拒絕此次投票。 Raft通過比較兩個服務(wù)器上日志的最后一個日志條目的任期和索引來決定誰的日志時最新的。任期不同，則任期大的日志新。任期相同，則索引大的日志新。 5.4.2 Committing entries from previous terms

leader知道任期內(nèi)的日志條目一旦被大多數(shù)服務(wù)器復(fù)制存儲，就被提交了。如果一個leader在提交一個日志條目前宕機(jī)了，將來的leader會繼續(xù)嘗試完成這一日志條目的復(fù)制，提交。然而，一個leader并不能立馬識別一個被大多數(shù)服務(wù)器存儲的日志條目，是否已被之前的leader提交了。上圖8展示了一種情景，存在大多數(shù)服務(wù)器上的日志條目被新的leader覆蓋了。 為了消除這種問題，Raft從來不會通過計(jì)算備份數(shù)來決定是否提交上一個任期的日志條目。只有l(wèi)eader當(dāng)期的日志條目需要通過計(jì)算備份數(shù)來決定提交。一旦當(dāng)前任期內(nèi)的一個日志條目以這種方式被提交了，那么根據(jù) Log Matching Property 限制，所有之前的所有日志條目也就間接的被提交了。當(dāng)然也存在某些情景，leader能夠立即識別是否一個舊的日志條目被提交了（日志條目被所有的服務(wù)器復(fù)制存儲了），但是Raft為了簡潔，選擇了使用更加保守的方法。 Raft之所以會有這種問題是因?yàn)閘eader在復(fù)制之前l(fā)eader日志條目時任然保留著原始的任期號。Raft的這種方式，使得其能夠更好的對相關(guān)日志條目進(jìn)行推斷。另外，Raft復(fù)制的之前的日志條目也相對較少。 5.4.3 Safety argument 給出了完整的Raft算法后，我們可以進(jìn)一步對 Leader Completeness Property進(jìn)行論證。首先我們假設(shè)Leader Completeness Property不成立，然后退出矛盾的結(jié)論。假定任期T內(nèi)的leader提交了一個日志條目，但是這個日志條目沒有被之后任期的leader存儲?？紤]存在的沒有存儲這條日志條目的領(lǐng)導(dǎo)者的大于任期T的小任期U。

1、該committed entry在leaderU選舉期間一定不存在于它的log中（leader從不刪除或者覆寫entry）。 2、leaderT將entry備份到了集群的majority中，并且leaderU獲取了來自集群的majority的投票，如Figure 9所示。而voter是達(dá)到矛盾的關(guān)鍵。 3、voter一定在投票給leaderU之前已經(jīng)接受了來自leaderT的committed entry；否則它將拒絕來自leaderT的AppendEntry request（因?yàn)樗腸urrent term高于T）。 4、當(dāng)voter投票給leaderU的時候它依然保有該entry，因?yàn)槊總€intervening leader都包含該entry(根據(jù)假設(shè))，leader從不刪除entry，而follower只刪除它們和leader矛盾的entry。 5、voter投票給leaderU，因此leaderU的log一定和voter的log一樣up-to-date。這就導(dǎo)致了兩個矛盾中的其中一個矛盾。 6、首先，如果voter和leaderU共享同一個last log term，那么leaderu的log至少要和voter的log一樣長，因此它的log包含了voter的log中的每一個entry。這是一個矛盾，因?yàn)関oter包含了committed entry而leaderU假設(shè)是不包含的。 7、除非，leaderU的last log term必須比voter的大。進(jìn)一步說，它必須大于T，因?yàn)関oter的last log term至少是T（它包含了term T的committed entry）。之前創(chuàng)建leaderU的last log entry的leader必須在它的log中包含了committed entry（根據(jù)假設(shè)）。那么，根據(jù)Log Matching Property，leaderU的log必須包含committed entry，這也是一個矛盾。 8、這完成了矛盾。因此，所有term大于T的leader必須包含所有來自于T并且在term T提交的entry。 9、Log Matching Property確保了future leader也會包含那些間接committed的entry，例如Figure 8(d)中的index 2。 給定Leader Completeness Property，證明Figure 3中的State Machine Safety Property就比較容易，即讓所有的state machine以相同的順序執(zhí)行同樣的log entry。 5.5 Follower and candidate crashes 到目前為止，我們的關(guān)注點(diǎn)都在leader失敗上。follower和candidate的失敗相對來說，更容易處理，處理機(jī)制同leader相同。當(dāng)follower和candidate失敗時，所有發(fā)送到他們的Request Vote RPCs和AppendEntries RPCs都會失敗。Raft通過無限次重試來處理這種狀況。當(dāng)失敗服務(wù)器重新恢復(fù)時，RPC請求完成請求。當(dāng)服務(wù)器接收處理完RPC請求，但是在回復(fù)之前宕機(jī)。那么在它恢復(fù)時，會接收到相同的RPC請求。因?yàn)镽aft的RPCs是冪等的，所以這種情況并不會引發(fā)任何問題，例如，當(dāng)一個follower接收到的AppendEntrie請求包含自身已存在的日志條目時，它會忽視這此請求。 5.6 Timing and availability 我們對Raft的要求之一就是安全性不依賴于時間因素：系統(tǒng)不會因?yàn)橐恍┦录l(fā)生的比預(yù)期的快或慢而產(chǎn)生錯誤的結(jié)果。然而，可用性不可避免的要依賴于時間因素。例如， 因?yàn)閟erver崩潰造成的信息交換的時間比通常情況下來得長，candidate就不能停留足夠長的時間來贏得選舉。如果沒有一個穩(wěn)定的leader，Raft就不能正常的執(zhí)行。 leader選舉是Raft中時間因素影響比較大的方面。當(dāng)系統(tǒng)滿足 broadcastTime ? electionTimeout ? MTBF 時，Raft才能夠維持一個穩(wěn)定的Leader。在上面的不等式中，broadcastTime代表一個服務(wù)器并行的向所有的其它服務(wù)器發(fā)送RPCs并收到回復(fù)的平均時間；electionTimeout代表選舉超時時間；MTBF代表單個服務(wù)器的故障發(fā)生間隔。broadcastTime應(yīng)該比electricTimeout小一個數(shù)量級，這樣leader就能可能的發(fā)送心跳信息到follower以阻止新的領(lǐng)導(dǎo)選舉。通過隨機(jī)的 electionTimeout 使用，使得split votes更加不可能出現(xiàn)。 electionTimeout應(yīng)該比MTBF小幾個數(shù)量級，這樣系統(tǒng)就能夠正常運(yùn)行。當(dāng)leader宕機(jī)時，系統(tǒng)會在 electionTimeout 內(nèi)變的不可用。我們希望這種情景出現(xiàn)的盡量少。 electionTimeout和MTBF是系統(tǒng)固有的時間屬性，electionTimeout則需要我們自己進(jìn)行設(shè)置，Raft的RPCs需要接收者執(zhí)行相關(guān)的持久化操作，所以broadcastTime會根據(jù)存儲技術(shù)的差異在0.5ms和20ms之間變動。這樣electionTimeout的變動范圍就可能在10ms到500ms之間。通常的MTBF在幾個月，甚至更多，完全滿足系統(tǒng)的時間因素要求。

1. Cluster membership changes 到目前為止，我們都假定集群的配置（參與一致性算法的服務(wù)器）是固定的。但是，在實(shí)際應(yīng)用中，配置時常也需要做相應(yīng)的變動，例如，替換宕機(jī)的服務(wù)器，改變復(fù)制的等級。我們可以將系統(tǒng)下線，修改配置，然后重啟系統(tǒng)，但是這不可避免的會引起系統(tǒng)下線期間的不可用。另外，人為操作因素也更容易引發(fā)系統(tǒng)錯誤。為了解決這些問題，我們決定實(shí)現(xiàn)配置變更的自動化，并將其融合進(jìn)一致性算法中。 為了保障配置變更機(jī)制的安全，在配置轉(zhuǎn)換期間，不能存在同一任期內(nèi)選舉出現(xiàn)兩個leader的現(xiàn)象。不幸的是，沒有任何方法能夠使得集群能夠安全的實(shí)現(xiàn)配置轉(zhuǎn)換。自動的轉(zhuǎn)換全部的服務(wù)器是不可能的，所有集群在轉(zhuǎn)換期間極有可能出現(xiàn)裂腦現(xiàn)象。如圖10：

為了確保安全，配置變更必須采用兩階段法。有很多種方法來實(shí)現(xiàn)這種算法。Raft中，集群首先切換到過渡配置狀態(tài)，我們稱之為 joint consensus ，一旦 joint consensus 被提交，系統(tǒng)切換到新的配置狀態(tài)。聯(lián)合一致性狀態(tài)既包括舊的配置，也包括新的配置： 日志條目在集群中被復(fù)制到兩種配置下所有的服務(wù)器。 新舊配置中的服務(wù)器都有可能選舉成為leader 關(guān)于選舉和日志條目的提交的協(xié)定同時需要新舊配置中的大多數(shù)服務(wù)器原則要求。 joint consensus允許單個服務(wù)器在不影響安全性的基礎(chǔ)上，在不同的特定時刻進(jìn)行不同配置的轉(zhuǎn)換。此外， joint consensus允許集群在配置轉(zhuǎn)換期間繼續(xù)處理客戶端的請求。

集群配置是通過特殊的日志條目通過日志復(fù)制進(jìn)行存儲和傳輸通訊的，圖11展示了配置的轉(zhuǎn)換過程。當(dāng)leader收到配置從 Cold 到 Cnew變更的的請求時，它首先將配置作為日志條目存儲為 Cold,new 并復(fù)制到其它服務(wù)器，一旦某個服務(wù)器將收到的 Cold,new 配置日志條目添加到自身的日志，那么之后其所有的決策都將以此配置 Cold,new 為依據(jù)（服務(wù)器總是以日志中最新的配置為依據(jù)進(jìn)行決策，無論配置條目是否已提交）。這就意味著，leader將使用 Cold,new 配置，來決定配置條目 Cold,new 什么時候提交。當(dāng)leader宕機(jī)時，新的leader將在舊配置 Cold或者聯(lián)合配置 Cold,new 的機(jī)器中選舉出來。這取決于獲得選舉的candidate是否已經(jīng)收到聯(lián)合配置 Cold,new 。任何情況下，具有新配置 Cnew 的服務(wù)器在這段時間內(nèi)都不能做出片面的決定。 一旦 Cold,new被提交后，具有Cold或者Cnew的服務(wù)器將不能再沒有其它服務(wù)器允許的情況下做出任何決策， Leader Completeness Property確保了只有具有Cold,new的服務(wù)器才能當(dāng)選為leader。此時，leader將能夠安全的創(chuàng)建Cnew的配置條目并將其復(fù)制到集群其它服務(wù)器。同樣，當(dāng)復(fù)制的服務(wù)器收到配置條目后就開始使用它。當(dāng)新的配置被提交后，擁有舊配置的服務(wù)器將可以被關(guān)閉。 在配置轉(zhuǎn)換期間存在著三方面的問題，第一個就是新的服務(wù)器初始化啟動的時候不包含任何日志條目，當(dāng)他們加入集群中時，需要花費(fèi)相當(dāng)?shù)臅r間同步到最新的狀態(tài)，在此期間，它將不能提交任何日志條目。為了避免可用性斷層，Raft設(shè)定新加入進(jìn)群的服務(wù)器狀態(tài)為none-voting（leader向他們復(fù)制日志，但是不講他們納入大多數(shù)范圍）。當(dāng)新的服務(wù)器同步到最新的狀態(tài)后，就可以執(zhí)行正常的配置轉(zhuǎn)換過程了。 第二個問題是集群leader處在舊的配置中，這種情況下，leader在將Cnew類目提交后就降級轉(zhuǎn)換為follower狀態(tài)。這就意味著在leader提交配置類目的這段時間了，它在管理者一個不包括自己的集群。它復(fù)制日志條目，但是卻將自身排除在被分計(jì)數(shù)外。leader的身份狀態(tài)轉(zhuǎn)換發(fā)生在Cnew條目提交的時候，這也是新的配置第一次能夠獨(dú)立決策執(zhí)行的時刻。在此之前，只有處于Cold的服務(wù)器才可以被選舉為leader。 第三個問題是，無關(guān)的服務(wù)器（處在Cold的服務(wù)器）會擾亂集群運(yùn)行。因?yàn)檫@些服務(wù)器不會收到心跳請求，所以他們就會產(chǎn)生超時并啟動新一輪的選舉。他們發(fā)送的Request Vote RPCs包含了新的任期號，這就會導(dǎo)致當(dāng)前的leader接收到請求后轉(zhuǎn)換為follower狀態(tài)，并最終在Cold下的某個服務(wù)器當(dāng)選為新的leader。但是那些無關(guān)的的服務(wù)器會無限次的不斷產(chǎn)生超時，啟動選舉，最終到會系統(tǒng)可用性的大大降低。 為了避免這樣的問題發(fā)生，服務(wù)器設(shè)定當(dāng)明確認(rèn)定當(dāng)前l(fā)eader存在的情況下，會選擇忽略此類的Request Vote RPCs。特別的，當(dāng)服務(wù)器在當(dāng)前最小選舉超時時間內(nèi)收到一個 RequestVote RPC，它不會更新當(dāng)前的任期號或者投出選票。這不會影響正常的選舉，每個服務(wù)器在開始一次選舉之前，至少等待一個最小選舉超時時間。然而，這有利于避免無關(guān)服務(wù)器的擾亂：如果領(lǐng)導(dǎo)人能夠發(fā)送心跳給集群，那么它就不會被更大的任期號廢除。

1. Log compaction Raft日志會伴隨著系統(tǒng)的日常運(yùn)行持續(xù)增長。但在實(shí)際應(yīng)用中，我們不能讓它無限制的增長下去。日志越長，占用的存儲空間越多，也將耗費(fèi)狀態(tài)機(jī)更多時間去重新應(yīng)用日志條目。我們需要適當(dāng)?shù)臋C(jī)制來處理掉日志中的過期的信息，避免其影響系統(tǒng)的可用性。 快照是壓縮的最簡單的方式，通過快照將某一時刻系統(tǒng)的當(dāng)前狀態(tài)寫入快照文件，保存到磁盤，然后將這一時刻之前的所有日志丟棄。例如chubby，zookeeper的快照機(jī)制。

圖12展示了快照的基本思想。各個服務(wù)器獨(dú)立的對已提交的日志條目進(jìn)行日志快照。主要的工作是由狀態(tài)機(jī)將它當(dāng)前的狀態(tài)寫入快照文件來完成。Raft也保留了一些元數(shù)據(jù)在快照中，例如，last included index代表狀態(tài)機(jī)最后應(yīng)用的日志條目索引。last included term則是指這一條目的任期。因?yàn)槿罩緱l目需要包含preLogIndex和preLogTerm這兩個屬性以應(yīng)對AppendEntries的一致性檢查。為了支持集群配置變更，快照文件也在last included index之前包含了最新的配置條目。一旦某個服務(wù)器完成快照寫入，他就會將last include index之前的所有日志條目都刪除掉。 雖然，正常情況下，各個服務(wù)器各自完成各自的快照。但是，偶爾也需要leader向落后的follower發(fā)送自身的快照。這一情況通常發(fā)生在leader丟棄掉了需要發(fā)送到follower的日志條目的時候。當(dāng)然，這種情況很少發(fā)生。和leader保持同步的follower擁有l(wèi)eader的所有日志，但是，落后比較大的follower或者剛加入集群的服務(wù)器卻并非如此。處理此類follower的機(jī)制就是leader發(fā)送日志快照來進(jìn)行同步。

leader需要使用一種新的RPC請求：InstallSnapshot來向落后的follower發(fā)送快照。如圖13所示，當(dāng)follower接收到此類請求時，需要判斷怎么對其進(jìn)行處理。通常來說，快照包含最新的日志條目（包含接收者不存在的日志條目），這樣接收服務(wù)器就可以丟棄自身所有的日志條目（可能包含未提交的和和快照中有沖突的條目），然后替換為快照中的日志條目。相反，如果接收者受到的快照包含的日志條目時其自身日志之前部分的條目（因?yàn)橹貍骰蛘咂渌e誤），那么就會將快照覆蓋的自身日志條目刪除掉，但是這之后的日志條目仍然有效，需要保留下來。 follower未經(jīng)leader允許，接收快照，違背了Raft的強(qiáng)領(lǐng)導(dǎo)準(zhǔn)則。然而，這是事出有因的，leader是為了處理達(dá)到一致性狀態(tài)過程中的沖突的，但是，在進(jìn)行快照的時候，就已經(jīng)達(dá)成一致性的目的了。數(shù)據(jù)仍然是從leader流向follower，只是follower可以重新整理他們自己的數(shù)據(jù)。 讓我們來思考另外一種leader-based的一致性算法。只有l(wèi)eader可以創(chuàng)建快照，然后發(fā)送到follower。這種方式有兩個缺點(diǎn)，首先是發(fā)送快照造成的帶寬浪費(fèi)，及整個快照進(jìn)程的拖慢。每個服務(wù)器都已經(jīng)包含了創(chuàng)建子什么快照的數(shù)據(jù)，因此本地化的快照創(chuàng)建成本更低。其次是，leader的實(shí)現(xiàn)會變得更加復(fù)雜，例如，leader發(fā)送快照的時候，同時需要并行的發(fā)送新的日志條目，并且不能阻塞客戶端請求。 另外兩個影響快照性能的因素是什么時候創(chuàng)建快照及不能影響系統(tǒng)的正常運(yùn)行。關(guān)于創(chuàng)建快照的時機(jī)，如果創(chuàng)建的太頻繁就會造成磁盤，帶寬和能量的浪費(fèi)，并且也增大了重啟狀態(tài)恢復(fù)的時間耗費(fèi)。因?yàn)槲覀冃枰O(shè)定一個合適的日志大小作為觸發(fā)快照的閾值。對于第二個問題，因?yàn)閯?chuàng)建快照會耗費(fèi)一定的時間，為了避免影響正常的系統(tǒng)運(yùn)行，我們可以采用copy-on-write機(jī)制，這樣新的請求，日志條目的更新不會影響快照的創(chuàng)建。例如，基于功能性結(jié)構(gòu)數(shù)據(jù)的狀態(tài)機(jī)就天然的支持這種特性?；蛘呶覀兛梢允褂貌僮飨到y(tǒng)的copy-on-write機(jī)制來創(chuàng)建狀態(tài)機(jī)的in-memory快照。

1. Client interaction 這一章介紹了客戶端和Raft的交互，包括客戶單如何識別集群leader，以及Raft是如何支持線性化。這些問題是所有一致性算法的共性問題，Raft的實(shí)現(xiàn)也大體相同。 集群leader負(fù)責(zé)處理客戶端所有的請求?？蛻舳藛訒r，它隨機(jī)的連接集群中的一臺服務(wù)器。如果連接的服務(wù)器不是leader，服務(wù)器會拒絕客戶端的連接，并提供集群最新leader的信息（AppendEntries請求包含leader的網(wǎng)絡(luò)地址信息）。如果leader宕機(jī)，客戶端的請求就會超時，需要重新向集群嘗試連接。 Raft的目標(biāo)是實(shí)現(xiàn)線性化（每一次操作都是即刻執(zhí)行的，并且只執(zhí)行一次），然而，就像前面描述的，Raft也存在可能會多次執(zhí)行同一個命令的情景：例如，leader 在提交完日志條目后及回復(fù)客戶端之前宕機(jī)，客戶端就會重新向新的leader發(fā)起同樣的命令請求。這將會導(dǎo)致同一命令被再次執(zhí)行。解決方案是，客戶端給每一次的請求命令添加一個唯一的序列碼，這樣服務(wù)器狀態(tài)機(jī)就可以根據(jù)請求的序列碼追蹤相應(yīng)的回復(fù)。當(dāng)服務(wù)器收到一個和之前序列碼相同的命令請求時，服務(wù)器就可以不必重新執(zhí)行命令，而獲取響應(yīng)返回給客戶端。 只讀操作可以直接處理而不需要寫入日志，但是可能會返回過期數(shù)據(jù)，因?yàn)轫憫?yīng)的leader可能已經(jīng)被新的leader所替代。線性特性不允許返回過期數(shù)據(jù)，Raft在不記錄日志的情況下需要兩個額外的預(yù)防措施來避免這一情況的發(fā)生。第一，leader必須擁有最新的日志條目。 Leader Completeness Property能夠保證leader擁有所有已提交的日志條目。但是在任期之初，leader并不知道那些條目時所有已提交的條目。為了解決這個問題，在任期開始的時候，leader需要提交一個空的 no-op條目。第二，leader在處理只讀請求之前必須先檢測一下自己是否已經(jīng)被替代。Raft通過讓leader在處理只讀請求之前向集群大多數(shù)服務(wù)器發(fā)送心跳信息來完成檢測。領(lǐng)導(dǎo)人可以依賴心跳機(jī)制來實(shí)現(xiàn)一種租約的機(jī)制，但是這種方法依賴時序來保證安全性
2. Implementation and evaluation ... ...
3. Related work 已經(jīng)有許多關(guān)于一致性算法的文章被發(fā)表出來，他們答題可以歸納為以下幾類： 對Lamport Paxos 協(xié)議的原始描述及解析。 Paxos的改進(jìn)算法，包括對 Paxos的查遺補(bǔ)缺及改進(jìn)，以為實(shí)際應(yīng)用提供更好的基礎(chǔ)。 實(shí)現(xiàn)一致性算法的系統(tǒng)，例如 Chubby，ZooKeeper 和 Spanner。Chubby 和 Spanner 的實(shí)現(xiàn)算法還沒有詳細(xì)的公開，但他們都聲稱是基于 Paxos。ZooKeeper 的算法細(xì)節(jié)已經(jīng)公開，但是卻和 Paxos 有著很大的差別。 Paxos 算法的性能優(yōu)化。 Oki 和 Liskov 的 Viewstamped Replication（VR），一種和 Paxos 差不多的替代算法。最初的算法和分布式傳輸協(xié)議耦合在了一起，但是在最近的更新中，算法核心的一致性協(xié)議被分離了出來。VR 使用了一種leader-based的方法，和 Raft 有許多相似之處。 Raft 和 Paxos 最大的不同之處就在于 Raft 的強(qiáng)領(lǐng)導(dǎo)特性：Raft 使用leader選舉作為一致性協(xié)議里必不可少的部分，并且將盡可能多的功能集中到了leader身上。這樣就使得算法更加簡單，易于理解。例如，在 Paxos 中，leader選舉和基本的一致性協(xié)議是正交的：leader選舉僅僅是作為性能優(yōu)化的手段，而且不是一致性所必須的。然而，這樣就給算法增加了多余的機(jī)制：Paxos 同時包含了針對基本一致性要求的兩階段提交協(xié)議和針對領(lǐng)導(dǎo)人選舉的機(jī)制。相比較而言，Raft 就直接將leader選舉納入到一致性算法中，并作為一致性算法兩階段的第一步。這樣就減少了不必要的算法機(jī)制。 像 Raft 一樣，VR 和 ZooKeeper 也是leader-based的，因此他們也擁有一些 Raft 的優(yōu)點(diǎn)。但是，Raft 比 VR 和 ZooKeeper 擁有更少的機(jī)制，因?yàn)?Raft 盡可能的減少了 non-leaders 的功能。例如，Raft 中日志條目只會從leader流向follower。在 VR 中，日志條目的流動是雙向的（領(lǐng)導(dǎo)人可以在選舉過程中接收日志）；這就導(dǎo)致了額外的機(jī)制和復(fù)雜性。根據(jù) ZooKeeper 公開的資料看，它的日志條目也是雙向傳輸?shù)?，但是它的?shí)現(xiàn)更像 Raft。 相比較于上述我們提及的其他服務(wù)于日志復(fù)制的一致性算法的算法，Raft 擁有更少的消息類型。例如，我們統(tǒng)計(jì)了一下VR 和 ZooKeeper 使用的用于基本一致性需要和成員變更的消息類型數(shù)（除了日志壓縮及客戶端交互，因?yàn)檫@些都是完全獨(dú)立于算法的）。VR 和 ZooKeeper 都分別定義了 10 中不同的消息類型，相對的，Raft 只有 4 種消息類型（兩種 RPC 請求和對應(yīng)的響應(yīng)）。Raft 的消息都稍微比其他算法的要信息量大，但是都很簡單。另外，VR 和 ZooKeeper 都在領(lǐng)導(dǎo)人變更時傳輸了整個日志；所以為了能夠?qū)嵺`中使用，額外的消息類型就很必要了。 Raft 的強(qiáng)領(lǐng)導(dǎo)人方法簡化了整個算法，但是同時也妨礙了一些性能優(yōu)化的方法。例如， Egalitarian Paxos （EPaxos）在某些沒有領(lǐng)導(dǎo)人的情況下可以達(dá)到很高的性能。EPaxos 充分發(fā)揮了在狀態(tài)機(jī)指令中的交換性。任何服務(wù)器都可以在一輪通信下就提交指令，只要其他同時被提交的指令和它進(jìn)行溝通。然而，如果并發(fā)被提交的指令，互相之間沒有進(jìn)行通信溝通，那么 EPaxos 就需要額外的一輪通信。因?yàn)槿魏畏?wù)器都可能提交指令，EPaxos 在服務(wù)器之間的負(fù)載均衡做的很好，并且很容易在 WAN 網(wǎng)絡(luò)環(huán)境下獲得很低的延遲。但同時，它也在 Paxos 上增加了許多重要的復(fù)雜度。 一些處理集群成員變換的方法已經(jīng)被提出或者在其他的成果中被實(shí)現(xiàn)，包括 Lamport 最初的討論，VR 和 SMART。我們選擇使用joint consensus方法，是因?yàn)槔昧艘恢滦詤f(xié)議，這樣我們就只需要增加很少一部分機(jī)制就可以實(shí)現(xiàn)成員變更。 Lamport 的基于 α 的方法對于Raft并不適用，因?yàn)樗俣ㄒ恢滦钥梢圆恍枰猯eader就可以達(dá)到。和 VR 和 SMART 相比較，Raft 的重配置算法可以在不影響正常請求處理的情況下進(jìn)行；相比較而言，VR 需要停止所有的處理請求。SMART 則引入了一個和 α 類似的方法，限制了請求處理的數(shù)量。同時，Raft 的方法需要更少的額外機(jī)制來實(shí)現(xiàn)。
4. Conclusion ... ...
5. Acknowledgments ... ...