《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í)際的個(gè)人學(xué)習(xí)調(diào)查，Raft比Paxos更易于學(xué)生學(xué)習(xí)。Raft同時(shí)也包含了一種新的機(jī)制用于改變集群成員配置，并通過overlapping majority來保證安全性。

1. Introduction 一致性算法允許一群機(jī)器像一個(gè)整體一樣工作，即使其中的一些成員發(fā)生故障也不會(huì)出現(xiàn)問題。正是基于這一點(diǎn)，它在構(gòu)建可靠的大規(guī)模軟件系統(tǒng)的過程中起著關(guān)鍵的作用。Paxos一直主導(dǎo)著過去十年對(duì) 一致性算法的討論：許多一致性算法的實(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é)生都對(duì)Paxos感到很痛苦。 在我們自己和Paxos經(jīng)歷了一番痛苦掙扎之后，我們決定發(fā)明一種新的一致性算法來為系統(tǒng)的構(gòu)建和教學(xué)提供更好的基礎(chǔ)。我們的主要目標(biāo)有點(diǎn)特別，是為了讓它更加易于理解：我們要為實(shí)際的系統(tǒng)構(gòu)建定義一個(gè)比Paxos更加易于理解的一致性協(xié)議。此外，我們希望該算法能夠培養(yǎng)系統(tǒng)構(gòu)建者的開發(fā)直覺。而這對(duì)系統(tǒng)構(gòu)建者是必不可少的。能讓算法正常工作很重要，但是能讓別人清除的知道它是怎樣工作更加重要。

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

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

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

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

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

狀態(tài)：

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

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

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

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

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

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

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

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

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

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

日志追加 AppendEntries RPC

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

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

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

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

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

entries[] 將要存儲(chǔ)的日志條目（心跳檢測(cè)RPCs時(shí)為空，一條或多條）

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

返回值

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

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

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

投票請(qǐng)求 RequestVote RPC

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

參數(shù)

term candidate的任期號(hào)

candidateId 請(qǐng)求投票的candidate id

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

lastLogTerm candidate最新日志條目對(duì)應(yīng)的任期號(hào)

返回值

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

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

接收者需要實(shí)現(xiàn)： 自身攜帶的任期號(hào)小于當(dāng)前任期號(hào)（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 的請(qǐng)求或者響應(yīng)中的任期號(hào) term T 大于 currentTerm，則將currentTerm賦值為 T，并切換狀態(tài)為追隨者（Follower）（5.1節(jié)） 追隨者（followers）: 5.2節(jié) 響應(yīng)來自候選人和領(lǐng)導(dǎo)人的 RPC 選舉超時(shí)后，未收到來自前領(lǐng)導(dǎo)人的AppendEntries RPC，或者投票給候選人，則自己轉(zhuǎn)換狀態(tài)為候選人。 候選人：5.2節(jié) 轉(zhuǎn)變?yōu)檫x舉人之后開始選舉： currentTerm自增 給自己投票 重置選舉計(jì)時(shí)器 向其他服務(wù)器發(fā)送RequestVote RPC 如果收到了來自大多數(shù)服務(wù)器的投票：則成為領(lǐng)導(dǎo)人 如果收到了來自新領(lǐng)導(dǎo)人的AppendEntries RPC（heartbeat）：轉(zhuǎn)換狀態(tài)為追隨者 如果選舉超時(shí)：開始新一輪的選舉 領(lǐng)導(dǎo)人： 選舉時(shí)：向其他服務(wù)器發(fā)送空的AppendEntries RPC（heartbeat）；在空閑時(shí)間重復(fù)發(fā)送以防止選舉超時(shí)（5.2節(jié)） 如果收到來自客戶端的請(qǐng)求：添加條目到本地日志，日志條目應(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é)） 如果存在一個(gè)數(shù)N，滿足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，則將commitIndex賦值為 N

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

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

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

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

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

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

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

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

一旦一個(gè)leader成功獲得選舉，它就開始接收處理客戶端請(qǐng)求，每個(gè)客戶端請(qǐng)求都包含一條需要狀態(tài)機(jī)執(zhí)行的命令。leader將命令最為新條目追加到自身日志中，同時(shí)發(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會(huì)無限次重試發(fā)送Append Entries RPCs，直到所有的follower成功復(fù)制所有的日志條目。

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

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

leader知道任期內(nèi)的日志條目一旦被大多數(shù)服務(wù)器復(fù)制存儲(chǔ)，就被提交了。如果一個(gè)leader在提交一個(gè)日志條目前宕機(jī)了，將來的leader會(huì)繼續(xù)嘗試完成這一日志條目的復(fù)制，提交。然而，一個(gè)leader并不能立馬識(shí)別一個(gè)被大多數(shù)服務(wù)器存儲(chǔ)的日志條目，是否已被之前的leader提交了。上圖8展示了一種情景，存在大多數(shù)服務(wù)器上的日志條目被新的leader覆蓋了。 為了消除這種問題，Raft從來不會(huì)通過計(jì)算備份數(shù)來決定是否提交上一個(gè)任期的日志條目。只有l(wèi)eader當(dāng)期的日志條目需要通過計(jì)算備份數(shù)來決定提交。一旦當(dāng)前任期內(nèi)的一個(gè)日志條目以這種方式被提交了，那么根據(jù) Log Matching Property 限制，所有之前的所有日志條目也就間接的被提交了。當(dāng)然也存在某些情景，leader能夠立即識(shí)別是否一個(gè)舊的日志條目被提交了（日志條目被所有的服務(wù)器復(fù)制存儲(chǔ)了），但是Raft為了簡(jiǎn)潔，選擇了使用更加保守的方法。 Raft之所以會(huì)有這種問題是因?yàn)閘eader在復(fù)制之前l(fā)eader日志條目時(shí)任然保留著原始的任期號(hào)。Raft的這種方式，使得其能夠更好的對(duì)相關(guān)日志條目進(jìn)行推斷。另外，Raft復(fù)制的之前的日志條目也相對(duì)較少。 5.4.3 Safety argument 給出了完整的Raft算法后，我們可以進(jìn)一步對(duì) Leader Completeness Property進(jìn)行論證。首先我們假設(shè)Leader Completeness Property不成立，然后退出矛盾的結(jié)論。假定任期T內(nèi)的leader提交了一個(gè)日志條目，但是這個(gè)日志條目沒有被之后任期的leader存儲(chǔ)?？紤]存在的沒有存儲(chǔ)這條日志條目的領(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的時(shí)候它依然保有該entry，因?yàn)槊總€(gè)intervening leader都包含該entry(根據(jù)假設(shè))，leader從不刪除entry，而follower只刪除它們和leader矛盾的entry。 5、voter投票給leaderU，因此leaderU的log一定和voter的log一樣up-to-date。這就導(dǎo)致了兩個(gè)矛盾中的其中一個(gè)矛盾。 6、首先，如果voter和leaderU共享同一個(gè)last log term，那么leaderu的log至少要和voter的log一樣長(zhǎng)，因此它的log包含了voter的log中的每一個(gè)entry。這是一個(gè)矛盾，因?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，這也是一個(gè)矛盾。 8、這完成了矛盾。因此，所有term大于T的leader必須包含所有來自于T并且在term T提交的entry。 9、Log Matching Property確保了future leader也會(huì)包含那些間接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的失敗相對(duì)來說，更容易處理，處理機(jī)制同leader相同。當(dāng)follower和candidate失敗時(shí)，所有發(fā)送到他們的Request Vote RPCs和AppendEntries RPCs都會(huì)失敗。Raft通過無限次重試來處理這種狀況。當(dāng)失敗服務(wù)器重新恢復(fù)時(shí)，RPC請(qǐng)求完成請(qǐng)求。當(dāng)服務(wù)器接收處理完RPC請(qǐng)求，但是在回復(fù)之前宕機(jī)。那么在它恢復(fù)時(shí)，會(huì)接收到相同的RPC請(qǐng)求。因?yàn)镽aft的RPCs是冪等的，所以這種情況并不會(huì)引發(fā)任何問題，例如，當(dāng)一個(gè)follower接收到的AppendEntrie請(qǐng)求包含自身已存在的日志條目時(shí)，它會(huì)忽視這此請(qǐng)求。 5.6 Timing and availability 我們對(duì)Raft的要求之一就是安全性不依賴于時(shí)間因素：系統(tǒng)不會(huì)因?yàn)橐恍┦录l(fā)生的比預(yù)期的快或慢而產(chǎn)生錯(cuò)誤的結(jié)果。然而，可用性不可避免的要依賴于時(shí)間因素。例如， 因?yàn)閟erver崩潰造成的信息交換的時(shí)間比通常情況下來得長(zhǎng)，candidate就不能停留足夠長(zhǎng)的時(shí)間來贏得選舉。如果沒有一個(gè)穩(wěn)定的leader，Raft就不能正常的執(zhí)行。 leader選舉是Raft中時(shí)間因素影響比較大的方面。當(dāng)系統(tǒng)滿足 broadcastTime ? electionTimeout ? MTBF 時(shí)，Raft才能夠維持一個(gè)穩(wěn)定的Leader。在上面的不等式中，broadcastTime代表一個(gè)服務(wù)器并行的向所有的其它服務(wù)器發(fā)送RPCs并收到回復(fù)的平均時(shí)間；electionTimeout代表選舉超時(shí)時(shí)間；MTBF代表單個(gè)服務(wù)器的故障發(fā)生間隔。broadcastTime應(yīng)該比electricTimeout小一個(gè)數(shù)量級(jí)，這樣leader就能可能的發(fā)送心跳信息到follower以阻止新的領(lǐng)導(dǎo)選舉。通過隨機(jī)的 electionTimeout 使用，使得split votes更加不可能出現(xiàn)。 electionTimeout應(yīng)該比MTBF小幾個(gè)數(shù)量級(jí)，這樣系統(tǒng)就能夠正常運(yùn)行。當(dāng)leader宕機(jī)時(shí)，系統(tǒng)會(huì)在 electionTimeout 內(nèi)變的不可用。我們希望這種情景出現(xiàn)的盡量少。 electionTimeout和MTBF是系統(tǒng)固有的時(shí)間屬性，electionTimeout則需要我們自己進(jìn)行設(shè)置，Raft的RPCs需要接收者執(zhí)行相關(guān)的持久化操作，所以broadcastTime會(huì)根據(jù)存儲(chǔ)技術(shù)的差異在0.5ms和20ms之間變動(dòng)。這樣electionTimeout的變動(dòng)范圍就可能在10ms到500ms之間。通常的MTBF在幾個(gè)月，甚至更多，完全滿足系統(tǒng)的時(shí)間因素要求。

1. Cluster membership changes 到目前為止，我們都假定集群的配置（參與一致性算法的服務(wù)器）是固定的。但是，在實(shí)際應(yīng)用中，配置時(shí)常也需要做相應(yīng)的變動(dòng)，例如，替換宕機(jī)的服務(wù)器，改變復(fù)制的等級(jí)。我們可以將系統(tǒng)下線，修改配置，然后重啟系統(tǒng)，但是這不可避免的會(huì)引起系統(tǒng)下線期間的不可用。另外，人為操作因素也更容易引發(fā)系統(tǒng)錯(cuò)誤。為了解決這些問題，我們決定實(shí)現(xiàn)配置變更的自動(dòng)化，并將其融合進(jìn)一致性算法中。 為了保障配置變更機(jī)制的安全，在配置轉(zhuǎn)換期間，不能存在同一任期內(nèi)選舉出現(xiàn)兩個(gè)leader的現(xiàn)象。不幸的是，沒有任何方法能夠使得集群能夠安全的實(shí)現(xiàn)配置轉(zhuǎn)換。自動(dòng)的轉(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í)需要新舊配置中的大多數(shù)服務(wù)器原則要求。 joint consensus允許單個(gè)服務(wù)器在不影響安全性的基礎(chǔ)上，在不同的特定時(shí)刻進(jìn)行不同配置的轉(zhuǎn)換。此外， joint consensus允許集群在配置轉(zhuǎn)換期間繼續(xù)處理客戶端的請(qǐng)求。

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

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

圖12展示了快照的基本思想。各個(gè)服務(wù)器獨(dú)立的對(duì)已提交的日志條目進(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這兩個(gè)屬性以應(yīng)對(duì)AppendEntries的一致性檢查。為了支持集群配置變更，快照文件也在last included index之前包含了最新的配置條目。一旦某個(gè)服務(wù)器完成快照寫入，他就會(huì)將last include index之前的所有日志條目都刪除掉。 雖然，正常情況下，各個(gè)服務(wù)器各自完成各自的快照。但是，偶爾也需要leader向落后的follower發(fā)送自身的快照。這一情況通常發(fā)生在leader丟棄掉了需要發(fā)送到follower的日志條目的時(shí)候。當(dāng)然，這種情況很少發(fā)生。和leader保持同步的follower擁有l(wèi)eader的所有日志，但是，落后比較大的follower或者剛加入集群的服務(wù)器卻并非如此。處理此類follower的機(jī)制就是leader發(fā)送日志快照來進(jìn)行同步。

leader需要使用一種新的RPC請(qǐng)求：InstallSnapshot來向落后的follower發(fā)送快照。如圖13所示，當(dāng)follower接收到此類請(qǐng)求時(shí)，需要判斷怎么對(duì)其進(jìn)行處理。通常來說，快照包含最新的日志條目（包含接收者不存在的日志條目），這樣接收服務(wù)器就可以丟棄自身所有的日志條目（可能包含未提交的和和快照中有沖突的條目），然后替換為快照中的日志條目。相反，如果接收者受到的快照包含的日志條目時(shí)其自身日志之前部分的條目（因?yàn)橹貍骰蛘咂渌e(cuò)誤），那么就會(huì)將快照覆蓋的自身日志條目刪除掉，但是這之后的日志條目仍然有效，需要保留下來。 follower未經(jīng)leader允許，接收快照，違背了Raft的強(qiáng)領(lǐng)導(dǎo)準(zhǔn)則。然而，這是事出有因的，leader是為了處理達(dá)到一致性狀態(tài)過程中的沖突的，但是，在進(jìn)行快照的時(shí)候，就已經(jīng)達(dá)成一致性的目的了。數(shù)據(jù)仍然是從leader流向follower，只是follower可以重新整理他們自己的數(shù)據(jù)。 讓我們來思考另外一種leader-based的一致性算法。只有l(wèi)eader可以創(chuàng)建快照，然后發(fā)送到follower。這種方式有兩個(gè)缺點(diǎn)，首先是發(fā)送快照造成的帶寬浪費(fèi)，及整個(gè)快照進(jìn)程的拖慢。每個(gè)服務(wù)器都已經(jīng)包含了創(chuàng)建子什么快照的數(shù)據(jù)，因此本地化的快照創(chuàng)建成本更低。其次是，leader的實(shí)現(xiàn)會(huì)變得更加復(fù)雜，例如，leader發(fā)送快照的時(shí)候，同時(shí)需要并行的發(fā)送新的日志條目，并且不能阻塞客戶端請(qǐng)求。 另外兩個(gè)影響快照性能的因素是什么時(shí)候創(chuàng)建快照及不能影響系統(tǒng)的正常運(yùn)行。關(guān)于創(chuàng)建快照的時(shí)機(jī)，如果創(chuàng)建的太頻繁就會(huì)造成磁盤，帶寬和能量的浪費(fèi)，并且也增大了重啟狀態(tài)恢復(fù)的時(shí)間耗費(fèi)。因?yàn)槲覀冃枰O(shè)定一個(gè)合適的日志大小作為觸發(fā)快照的閾值。對(duì)于第二個(gè)問題，因?yàn)閯?chuàng)建快照會(huì)耗費(fèi)一定的時(shí)間，為了避免影響正常的系統(tǒng)運(yùn)行，我們可以采用copy-on-write機(jī)制，這樣新的請(qǐng)求，日志條目的更新不會(huì)影響快照的創(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的交互，包括客戶單如何識(shí)別集群leader，以及Raft是如何支持線性化。這些問題是所有一致性算法的共性問題，Raft的實(shí)現(xiàn)也大體相同。 集群leader負(fù)責(zé)處理客戶端所有的請(qǐng)求?？蛻舳藛?dòng)時(shí)，它隨機(jī)的連接集群中的一臺(tái)服務(wù)器。如果連接的服務(wù)器不是leader，服務(wù)器會(huì)拒絕客戶端的連接，并提供集群最新leader的信息（AppendEntries請(qǐng)求包含leader的網(wǎng)絡(luò)地址信息）。如果leader宕機(jī)，客戶端的請(qǐng)求就會(huì)超時(shí)，需要重新向集群嘗試連接。 Raft的目標(biāo)是實(shí)現(xiàn)線性化（每一次操作都是即刻執(zhí)行的，并且只執(zhí)行一次），然而，就像前面描述的，Raft也存在可能會(huì)多次執(zhí)行同一個(gè)命令的情景：例如，leader 在提交完日志條目后及回復(fù)客戶端之前宕機(jī)，客戶端就會(huì)重新向新的leader發(fā)起同樣的命令請(qǐng)求。這將會(huì)導(dǎo)致同一命令被再次執(zhí)行。解決方案是，客戶端給每一次的請(qǐng)求命令添加一個(gè)唯一的序列碼，這樣服務(wù)器狀態(tài)機(jī)就可以根據(jù)請(qǐng)求的序列碼追蹤相應(yīng)的回復(fù)。當(dāng)服務(wù)器收到一個(gè)和之前序列碼相同的命令請(qǐng)求時(shí)，服務(wù)器就可以不必重新執(zhí)行命令，而獲取響應(yīng)返回給客戶端。 只讀操作可以直接處理而不需要寫入日志，但是可能會(huì)返回過期數(shù)據(jù)，因?yàn)轫憫?yīng)的leader可能已經(jīng)被新的leader所替代。線性特性不允許返回過期數(shù)據(jù)，Raft在不記錄日志的情況下需要兩個(gè)額外的預(yù)防措施來避免這一情況的發(fā)生。第一，leader必須擁有最新的日志條目。 Leader Completeness Property能夠保證leader擁有所有已提交的日志條目。但是在任期之初，leader并不知道那些條目時(shí)所有已提交的條目。為了解決這個(gè)問題，在任期開始的時(shí)候，leader需要提交一個(gè)空的 no-op條目。第二，leader在處理只讀請(qǐng)求之前必須先檢測(cè)一下自己是否已經(jīng)被替代。Raft通過讓leader在處理只讀請(qǐng)求之前向集群大多數(shù)服務(wù)器發(fā)送心跳信息來完成檢測(cè)。領(lǐng)導(dǎo)人可以依賴心跳機(jī)制來實(shí)現(xiàn)一種租約的機(jī)制，但是這種方法依賴時(shí)序來保證安全性
2. Implementation and evaluation ... ...
3. Related work 已經(jīng)有許多關(guān)于一致性算法的文章被發(fā)表出來，他們答題可以歸納為以下幾類： 對(duì)Lamport Paxos 協(xié)議的原始描述及解析。 Paxos的改進(jìn)算法，包括對(duì) 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身上。這樣就使得算法更加簡(jiǎn)單，易于理解。例如，在 Paxos 中，leader選舉和基本的一致性協(xié)議是正交的：leader選舉僅僅是作為性能優(yōu)化的手段，而且不是一致性所必須的。然而，這樣就給算法增加了多余的機(jī)制：Paxos 同時(shí)包含了針對(duì)基本一致性要求的兩階段提交協(xié)議和針對(duì)領(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 中日志條目只會(huì)從leader流向follower。在 VR 中，日志條目的流動(dòng)是雙向的（領(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 中不同的消息類型，相對(duì)的，Raft 只有 4 種消息類型（兩種 RPC 請(qǐng)求和對(duì)應(yīng)的響應(yīng)）。Raft 的消息都稍微比其他算法的要信息量大，但是都很簡(jiǎn)單。另外，VR 和 ZooKeeper 都在領(lǐng)導(dǎo)人變更時(shí)傳輸了整個(gè)日志；所以為了能夠?qū)嵺`中使用，額外的消息類型就很必要了。 Raft 的強(qiáng)領(lǐng)導(dǎo)人方法簡(jiǎn)化了整個(gè)算法，但是同時(shí)也妨礙了一些性能優(yōu)化的方法。例如， Egalitarian Paxos （EPaxos）在某些沒有領(lǐng)導(dǎo)人的情況下可以達(dá)到很高的性能。EPaxos 充分發(fā)揮了在狀態(tài)機(jī)指令中的交換性。任何服務(wù)器都可以在一輪通信下就提交指令，只要其他同時(shí)被提交的指令和它進(jìn)行溝通。然而，如果并發(fā)被提交的指令，互相之間沒有進(jìn)行通信溝通，那么 EPaxos 就需要額外的一輪通信。因?yàn)槿魏畏?wù)器都可能提交指令，EPaxos 在服務(wù)器之間的負(fù)載均衡做的很好，并且很容易在 WAN 網(wǎng)絡(luò)環(huán)境下獲得很低的延遲。但同時(shí)，它也在 Paxos 上增加了許多重要的復(fù)雜度。 一些處理集群成員變換的方法已經(jīng)被提出或者在其他的成果中被實(shí)現(xiàn)，包括 Lamport 最初的討論，VR 和 SMART。我們選擇使用joint consensus方法，是因?yàn)槔昧艘恢滦詤f(xié)議，這樣我們就只需要增加很少一部分機(jī)制就可以實(shí)現(xiàn)成員變更。 Lamport 的基于 α 的方法對(duì)于Raft并不適用，因?yàn)樗俣ㄒ恢滦钥梢圆恍枰猯eader就可以達(dá)到。和 VR 和 SMART 相比較，Raft 的重配置算法可以在不影響正常請(qǐng)求處理的情況下進(jìn)行；相比較而言，VR 需要停止所有的處理請(qǐng)求。SMART 則引入了一個(gè)和 α 類似的方法，限制了請(qǐng)求處理的數(shù)量。同時(shí)，Raft 的方法需要更少的額外機(jī)制來實(shí)現(xiàn)。
4. Conclusion ... ...
5. Acknowledgments ... ...