Raft是一種更為簡(jiǎn)單方便易于理解的分布式算法，主要解決了分布式中的一致性問題。相比傳統(tǒng)的Paxos算法，Raft將大量的計(jì)算問題分解成為了一些簡(jiǎn)單的相對(duì)獨(dú)立的子問題。
簡(jiǎn)述
相比于傳統(tǒng)的一致性算法Paxos，Raft有一些自己的獨(dú)特的特性。比如增加了強(qiáng)領(lǐng)導(dǎo)性，優(yōu)化了領(lǐng)導(dǎo)的選舉過程，在成員發(fā)生變化之后依然能夠很好的進(jìn)行工作。
以下是文章部分內(nèi)容的翻譯，來自GitHub。由于字?jǐn)?shù)限制只摘取了算法的核心部分。建議閱讀原文。
尋找一種易于理解的一致性算法（擴(kuò)展版）
具體內(nèi)容
一致性算法允許一組機(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 算法進(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 減少了非確定性和服務(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 DNA復(fù)制），但是它也有一些獨(dú)特的特性：
??強(qiáng)領(lǐng)導(dǎo)者：和其他一致性算法相比，Raft 使用一種更強(qiáng)的領(lǐng)導(dǎo)能力形式。比如，日志條目只從領(lǐng)導(dǎo)者發(fā)送給其他的服務(wù)器。這種方式簡(jiǎn)化了對(duì)復(fù)制日志的管理并且使得 Raft 算法更加易于理解。
??領(lǐng)導(dǎo)選舉：Raft 算法使用一個(gè)隨機(jī)計(jì)時(shí)器來選舉領(lǐng)導(dǎo)者。這種方式只是在任何一致性算法都必須實(shí)現(xiàn)的心跳機(jī)制上增加了一點(diǎn)機(jī)制。在解決沖突的時(shí)候會(huì)更加簡(jiǎn)單快捷。
??成員關(guān)系調(diào)整：Raft 使用一種共同一致的方法來處理集群成員變換的問題，在這種方法下，處于調(diào)整過程中的兩種不同的配置集群中大多數(shù)機(jī)器會(huì)有重疊，這就使得集群在成員變換的時(shí)候依然可以繼續(xù)工作。
我們相信，Raft 算法不論出于教學(xué)目的還是作為實(shí)踐項(xiàng)目的基礎(chǔ)都是要比 Paxos 或者其他一致性算法要優(yōu)異的。它比其他算法更加簡(jiǎn)單，更加容易理解；它的算法描述足以實(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)榱死斫饽芰Χ褂玫姆椒ǎǖ?4 節(jié)），闡述 Raft 一致性算法（第 5-8 節(jié)），評(píng)價(jià) Raft 算法（第 9 節(jié)），以及一些相關(guān)的工作（第 10 節(jié)）。
一致性算法
Raft 是一種用來管理章節(jié) 2 中描述的復(fù)制日志的算法。圖 2 為了參考之用，總結(jié)這個(gè)算法的簡(jiǎn)略版本，圖 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ī)中。擁有一個(gè)領(lǐng)導(dǎo)人大大簡(jiǎn)化了對(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)現(xiàn)存的領(lǐng)導(dǎo)人宕機(jī)的時(shí)候（章節(jié) 5.2）
??日志復(fù)制：領(lǐng)導(dǎo)人必須從客戶端接收日志然后復(fù)制到集群中的其他節(jié)點(diǎn)，并且強(qiáng)制要求其他節(jié)點(diǎn)的日志保持和自己相同。
??安全性：在 Raft 中安全性的關(guān)鍵是在圖 3 中展示的狀態(tài)機(jī)安全：如果有任何的服務(wù)器節(jié)點(diǎn)已經(jīng)應(yīng)用了一個(gè)確定的日志條目到它的狀態(tài)機(jī)中，那么其他服務(wù)器節(jié)點(diǎn)不能在同一個(gè)日志索引位置應(yīng)用一個(gè)不同的指令。章節(jié) 5.4 闡述了 Raft 算法是如何保證這個(gè)特性的；這個(gè)解決方案涉及到一個(gè)額外的選舉機(jī)制（5.2 節(jié)）上的限制。
在展示一致性算法之后，這一章節(jié)會(huì)討論可用性的一些問題和系統(tǒng)中的候選人角色的問題。
狀態(tài)：
附加日志 RPC：
由領(lǐng)導(dǎo)人負(fù)責(zé)調(diào)用來復(fù)制日志指令；也會(huì)用作heartbeat
接收者實(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é)）
接收者實(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 加一，并把log[lastApplied]應(yīng)用到狀態(tài)機(jī)中（5.3 節(jié)）
??如果接收到的 RPC 請(qǐng)求或響應(yīng)中，任期號(hào)T > currentTerm，那么就令 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)變成候選人后就立即開始選舉過程
??自增當(dāng)前的任期號(hào)（currentTerm）
??給自己投票
??重置選舉超時(shí)計(jì)時(shí)器
??發(fā)送請(qǐng)求投票的 RPC 給其他所有服務(wù)器
??如果接收到大多數(shù)服務(wù)器的選票，那么就變成領(lǐng)導(dǎo)人
??如果接收到來自新的領(lǐng)導(dǎo)人的附加日志 RPC，轉(zhuǎn)變成跟隨者
??如果選舉過程超時(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 開始的所有日志條目：
??如果成功：更新相應(yīng)跟隨者的 nextIndex 和 matchIndex
??如果因?yàn)槿罩静灰恢露。瑴p少 nextIndex 重試
??如果存在一個(gè)滿足N > commitIndex的 N，并且大多數(shù)的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex 等于這個(gè) N （5.3 和 5.4 節(jié)）
圖 2：一個(gè)關(guān)于 Raft 一致性算法的濃縮總結(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)求，只是簡(jiǎn)單的響應(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)者。在一個(gè)任期內(nèi)，領(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è)任期就會(huì)沒有領(lǐng)導(dǎo)人而結(jié)束。任期之間的切換可以在不同的時(shí)間不同的服務(wù)器上觀察到。
Raft 把時(shí)間分割成任意長(zhǎng)度的任期，如圖 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è)任期全程。任期在 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)的增長(zhǎng)。當(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 由候選人在選舉期間發(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)威。如果一個(gè)跟隨者在一段時(shí)間里沒有接收到任何消息，也就是選舉超時(shí)，那么他就會(huì)認(rèn)為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者，并且發(fā)起選舉以選出新的領(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ì)一個(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)。
第三種可能的結(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ī)制被用在選票瓜分的情況下。每一個(gè)候選人在開始一次選舉的時(shí)候會(huì)重置一個(gè)隨機(jī)的選舉超時(shí)時(shí)間，然后在超時(shí)時(shí)間內(nèi)等待投票的結(jié)果；這樣減少了在新的選舉中另外的選票瓜分的可能性。9.3 節(jié)展示了這種方案能夠快速的選出一個(gè)領(lǐng)導(dǎo)人。
領(lǐng)導(dǎo)人選舉這個(gè)例子，體現(xiàn)了可理解性原則是如何指導(dǎo)我們進(jìn)行方案設(shè)計(jì)的。起初我們計(jì)劃使用一種排名系統(tǒng)：每一個(gè)候選人都被賦予一個(gè)唯一的排名，供候選人之間競(jìng)爭(zhēng)時(shí)進(jìn)行選擇。如果一個(gè)候選人發(fā)現(xiàn)另一個(gè)候選人擁有更高的排名，那么他就會(huì)回到跟隨者狀態(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è)領(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ù)嘗試附加日志條目 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)用來檢查是否出現(xiàn)不一致的情況，同時(shí)也用來保證圖 3 中的某些性質(zhì)。每一條日志條目同時(shí)也都有一個(gè)整數(shù)索引值來表明它在日志中的位置。
領(lǐng)導(dǎo)人來決定什么時(shí)候把日志條目應(yīng)用到狀態(tài)機(jī)中是安全的；這種日志條目被稱為已提交。Raft 算法保證所有已提交的日志條目都是持久化的并且最終會(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ī)中（按照日志的順序）。
我們?cè)O(shè)計(jì)了 Raft 的日志機(jī)制來維護(hù)一個(gè)不同服務(wù)器的日志之間的高層次的一致性。這么做不僅簡(jiǎn)化了系統(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 的一個(gè)簡(jiǎn)單的一致性檢查所保證。在發(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)人就知道跟隨者的日志一定是和自己相同的了。
在正常的操作中，領(lǐng)導(dǎo)人和跟隨者的日志保持一致性，所以附加日志 RPC 的一致性檢查從來不會(huì)失敗。然而，領(lǐng)導(dǎo)人崩潰的情況會(huì)使得日志處于不一致的狀態(tài)（老的領(lǐng)導(dǎo)人可能還沒有完全復(fù)制所有的日志條目）。這種不一致問題會(huì)在領(lǐng)導(dǎo)人和跟隨者的一系列崩潰下加劇。圖 7 展示了跟隨者的日志可能和新的領(lǐng)導(dǎo)人不同的方式。跟隨者可能會(huì)丟失一些在新的領(lǐng)導(dǎo)人中有的日志條目，他也可能擁有一些領(lǐng)導(dǎo)人沒有的日志條目，或者兩者都發(fā)生。丟失或者多出日志條目可能會(huì)持續(xù)多個(gè)任期。
圖 7：當(dāng)一個(gè)領(lǐng)導(dǎo)人成功當(dāng)選時(shí)，跟隨者可能是任何情況（a-f）。每一個(gè)盒子表示是一個(gè)日志條目；里面的數(shù)字表示任期號(hào)。跟隨者可能會(huì)缺少一些日志條目（a-b），可能會(huì)有一些未被提交的日志條目（c-d），或者兩種情況都存在（e-f）。例如，場(chǎng)景 f 可能會(huì)這樣發(fā)生，某服務(wù)器在任期 2 的時(shí)候是領(lǐng)導(dǎo)人，已附加了一些日志條目到自己的日志中，但在提交之前就崩潰了；很快這個(gè)機(jī)器就被重啟了，在任期 3 重新被選為領(lǐng)導(dǎo)人，并且又增加了一些日志條目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，這個(gè)服務(wù)器又宕機(jī)了，并且在接下來的幾個(gè)任期里一直處于宕機(jī)狀態(tài)。
在 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 的一致性檢查時(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)人的日志。一旦附加日志 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ù)一致性。他只需要進(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)入不可用狀態(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)人完整特性的簡(jiǎn)要證明，并且說明領(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)提交的日志條目。在某些一致性算法中，例如 Viewstamped Replication，某個(gè)節(jié)點(diǎn)即使是一開始并沒有包含所有已經(jīng)提交的日志條目，它也能被選為領(lǐng)導(dǎo)者。這些算法都包含一些額外的機(jī)制來識(shí)別丟失的日志條目并把他們傳送給新的領(lǐng)導(dǎo)人，要么是在選舉階段要么在之后很快進(jìn)行。不幸的是，這種方法會(huì)導(dǎo)致相當(dāng)大的額外的機(jī)制和復(fù)雜性。Raft 使用了一種更加簡(jiǎn)單的方法，它可以保證所有之前的任期號(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è)候選人贏得選舉除非這個(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)相同，那么日志比較長(zhǎng)的那個(gè)就更加新。
5.4.2 提交之前任期內(nèi)的日志條目
如同 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)人無法決定對(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è)?a href="/hebeideji/5527083834876297305.html">索引 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)的日志條目。只有領(lǐng)導(dǎo)人當(dāng)前任期里的日志條目通過計(jì)算副本數(shù)目可以被提交；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性，之前的日志條目也都會(huì)被間接的提交。在某些情況下，領(lǐng)導(dǎo)人可以安全的知道一個(gè)老的日志條目是否已經(jīng)被提交（例如，該條目是否存儲(chǔ)到所有服務(wù)器上），但是 Raft 為了簡(jiǎn)化問題使用一種更加保守的方法。
當(dāng)領(lǐng)導(dǎo)人復(fù)制之前任期里的日志時(shí)，Raft 會(huì)為所有日志保留原始的任期號(hào), 這在提交規(guī)則上產(chǎn)生了額外的復(fù)雜性。在其他的一致性算法中，如果一個(gè)新的領(lǐng)導(dǎo)人要重新復(fù)制之前的任期里的日志時(shí)，它必須使用當(dāng)前新的任期號(hào)。Raft 使用的方法更加容易辨別出日志，因?yàn)樗梢噪S著時(shí)間和日志的變化對(duì)日志維護(hù)著同一個(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ǔ)到未來某個(gè)任期的領(lǐng)導(dǎo)人的日志中。設(shè)大于 T 的最小任期 U 的領(lǐng)導(dǎo)人 U 沒有這條日志條目。
圖 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)人 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 的日志至少和投票者一樣長(zhǎng)，所以領(lǐng)導(dǎo)人 U 的日志一定包含所有投票者的日志。這是另一處矛盾，因?yàn)橥镀闭甙四菞l已經(jīng)被提交的日志條目，但是在上述的假設(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ì)包含被間接提交的條目，例如圖 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)被提交。現(xiàn)在我們來考慮在任何一個(gè)服務(wù)器應(yīng)用一個(gè)指定索引位置的日志的最小任期；日志完全特性保證擁有更高任期號(hào)的領(lǐng)導(dǎo)人會(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 跟隨者和候選人崩潰
到目前為止，我們都只關(guān)注了領(lǐng)導(dǎo)人崩潰的情況。跟隨者和候選人崩潰后的處理方式比領(lǐng)導(dǎo)人要簡(jiǎn)單的多，并且他們的處理方式是相同的。如果跟隨者或者候選人崩潰了，那么后續(xù)發(fā)送給他們的 RPCs 都會(huì)失敗。Raft 中處理這種失敗就是簡(jiǎn)單的通過無限的重試；如果崩潰的機(jī)器重啟了，那么這些 RPC 就會(huì)完整的成功。如果一個(gè)服務(wù)器在完成了一個(gè) RPC，但是還沒有響應(yīng)的時(shí)候崩潰了，那么在他重新啟動(dòng)之后就會(huì)再次收到同樣的請(qǐng)求。Raft 的 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í)間長(zhǎng)，候選人將沒有足夠長(zhǎng)的時(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)人，只要系統(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í)，這樣領(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)才能穩(wěn)定的運(yùn)行。當(dāng)領(lǐng)導(dǎo)人崩潰后，整個(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è)月甚至更長(zhǎng)，很容易滿足時(shí)間的需求。
參考資料 >
Raft論文中文翻譯.Github.2019-01-14