摘要：每個在收到的心跳信息后會重啟定時器，從而避免在正常工作時，會發(fā)生選舉的情況。日志復(fù)制當(dāng)選出后，它會開始接受客戶端請求，每個請求會帶有一個指令，可以被回放到狀態(tài)機中。

一個 Raft 集群包含若干個服務(wù)器節(jié)點；通常是 5 個，這允許整個系統(tǒng)容忍 2 個節(jié)點的失效，每個節(jié)點處于以下三種狀態(tài)之一：

follower（跟隨者） ：所有結(jié)點都以 follower 的狀態(tài)開始。如果沒收到 leader消息則會變成 candidate狀態(tài)。

candidate（候選人）：會向其他結(jié)點“拉選票”，如果得到大部分的票則成為leader。這個過程就叫做Leader選舉(Leader Election)。

leader（領(lǐng)導(dǎo)者）：所有對系統(tǒng)的修改都會先經(jīng)過leader。

Raft通過選出一個leader來簡化日志副本的管理，例如，日志項(log entry)只允許從leader流向follower。

基于leader的方法，Raft算法可以分解成三個子問題：

Leader election (領(lǐng)導(dǎo)選舉)：原來的leader掛掉后，必須選出一個新的leader

Log replication (日志復(fù)制)：leader從客戶端接收日志，并復(fù)制到整個集群中

Safety (安全性)：如果有任意的server將日志項回放到狀態(tài)機中了，那么其他的server只會回放相同的日志項

Raft 使用一種心跳機制來觸發(fā)領(lǐng)導(dǎo)人選舉。當(dāng)服務(wù)器程序啟動時，他們都是 follower(跟隨者) 身份。如果一個跟隨者在一段時間里沒有接收到任何消息，也就是選舉超時，然后他就會認為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者然后開始進行選舉以選出新的領(lǐng)導(dǎo)者。要開始一次選舉過程，follower 會給當(dāng)前term加1并且轉(zhuǎn)換成candidate狀態(tài)。

然后他會并行的向集群中的其他服務(wù)器節(jié)點發(fā)送請求投票的 RPCs 來給自己投票。候選人的狀態(tài)維持直到發(fā)生以下任何一個條件發(fā)生的時候，

他自己贏得了這次的選舉

如果這個節(jié)點贏得了半數(shù)以上的vote就會成為leader，每個節(jié)點會按照first-come-first-served的原則進行投票，并且一個term中只能投給一個節(jié)點， 這樣就保證了一個term最多有一個節(jié)點贏得半數(shù)以上的vote。

當(dāng)一個節(jié)點贏得選舉， 他會成為leader， 并且給所有節(jié)點發(fā)送這個信息， 這樣所有節(jié)點都會回退成follower。

其他的服務(wù)器成為領(lǐng)導(dǎo)者

如果在等待選舉期間，candidate接收到其他server要成為leader的RPC，分兩種情況處理：

如果leader的term大于或等于自身的term，那么改candidate 會轉(zhuǎn)成follower 狀態(tài)

如果leader的term小于自身的term，那么會拒絕該 leader，并繼續(xù)保持candidate 狀態(tài)

一段時間之后沒有任何一個獲勝的人

有可能，很多follower同時變成candidate，導(dǎo)致沒有candidate能獲得大多數(shù)的選舉，從而導(dǎo)致無法選出主。當(dāng)這個情況發(fā)生時，每個candidate會超時，然后重新發(fā)增加term，發(fā)起新一輪選舉RPC。需要注意的是，如果沒有特別處理，可能出導(dǎo)致無限地重復(fù)選主的情況。

Raft采用隨機定時器的方法來避免上述情況，每個candidate選擇一個時間間隔內(nèi)的隨機值，例如150-300ms，采用這種機制，一般只有一個server會進入candidate狀態(tài)，然后獲得大多數(shù)server的選舉，最后成為主。每個candidate在收到leader的心跳信息后會重啟定時器，從而避免在leader正常工作時，會發(fā)生選舉的情況。

當(dāng)選出 leader 后，它會開始接受客戶端請求，每個請求會帶有一個指令，可以被回放到狀態(tài)機中。leader 把指令追加成一個log entry，然后通過AppendEntries RPC并行的發(fā)送給其他的server，當(dāng)改entry被多數(shù)派server復(fù)制后，leader 會把該entry回放到狀態(tài)機中，然后把結(jié)果返回給客戶端。

當(dāng) follower 宕機或者運行較慢時，leader 會無限地重發(fā)AppendEntries給這些follower，直到所有的follower都復(fù)制了該log entry。

raft的log replication保證以下性質(zhì)(Log Matching Property)：

如果兩個log entry有相同的index和term，那么它們存儲相同的指令

如果兩個log entry在兩份不同的日志中，并且有相同的index和term，那么它們之前的log entry是完全相同的

其中特性一通過以下保證：

leader在一個特定的term和index下，只會創(chuàng)建一個log entry

log entry不會改變它們在日志中的位置

特性二通過以下保證：

AppendEntries會做log entry的一致性檢查，當(dāng)發(fā)送一個AppendEntriesRPC時，leader會帶上需要復(fù)制的log entry前一個log entry的(index, iterm)

如果follower沒有發(fā)現(xiàn)與它一樣的log entry，那么它會拒絕接受新的log entry 這樣就能保證特性二得以滿足。

在一些一致性算法中，即使一臺server沒有包含所有之前已提交的log entry，也能被選為主，這些算法需要把leader上缺失的日志從其他的server拷貝到leader上，這種方法會導(dǎo)致額外的復(fù)雜度。相對而言，raft使用一種更簡單的方法，即它保證所有已提交的log entry都會在當(dāng)前選舉的leader上，因此，在raft算法中，日志只會從leader流向follower。

為了實現(xiàn)上述目標(biāo)，raft在選舉中會保證，一個candidate只有得到大多數(shù)的server的選票之后，才能被選為主。得到大多數(shù)的選票表明，選舉它的server中至少有一個server是擁有所有已經(jīng)提交的log entry的，而leader的日志至少和follower的一樣新，這樣就保證了leader肯定有所有已提交的log entry。

領(lǐng)導(dǎo)人知道一條當(dāng)前任期內(nèi)的日志記錄是可以被提交的，只要它被存儲到了大多數(shù)的服務(wù)器上。如果一個領(lǐng)導(dǎo)人在提交日志條目之前崩潰了，未來后續(xù)的領(lǐng)導(dǎo)人會繼續(xù)嘗試復(fù)制這條日志記錄。然而，一個領(lǐng)導(dǎo)人不能斷定一個之前任期里的日志條目被保存到大多數(shù)服務(wù)器上的時候就一定已經(jīng)提交了。下圖展示了一種情況，一條已經(jīng)被存儲到大多數(shù)節(jié)點上的老日志條目，也依然有可能會被未來的領(lǐng)導(dǎo)人覆蓋掉。

如上圖的例子，圖（c）就發(fā)生了一個log entry雖然已經(jīng)復(fù)制到大多數(shù)的服務(wù)器，但是仍然有可能被覆蓋掉的可能，如圖（d），整個發(fā)生的時序如下：

圖a中，S1被選為主，然后復(fù)制到log index為2的log entry到S2上

圖b中，S1掛掉，然后S5獲得了S3，S4和自身的選舉，成為leader，然后，其從客戶端收到了一個新的log entry(3)

圖c中，S5掛掉，S1重新正常工作，又被選為主，繼續(xù)復(fù)制log entry(2)，在log entry(2)被提交前，S1又掛掉

圖d中，S5又重新被選為領(lǐng)導(dǎo)者，然后，會把term 3的log entry覆蓋到其他log index為2的log entry

為了上圖描述的情況，Raft 永遠不會通過計算副本數(shù)目的方式去提交一個之前任期內(nèi)的日志條目。只有領(lǐng)導(dǎo)人當(dāng)前任期里的日志條目通過計算副本數(shù)目可以被提交；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性，之前的日志條目也都會被間接的提交。例如，圖e中，如果S1在掛掉前把log entry(4)復(fù)制到了大多數(shù)的server后，就能保證之前的log entry（2）被提交了，之后S5也就不可能被選為領(lǐng)導(dǎo)者了。

以反證法來證明，假設(shè)任期 T 的領(lǐng)導(dǎo)人（領(lǐng)導(dǎo)人 T）在任期內(nèi)提交了一條日志條目，但是這條日志條目沒有被存儲到未來某個任期的領(lǐng)導(dǎo)人的日志中。設(shè)大于 T 的最小任期 U 的領(lǐng)導(dǎo)人 U 沒有這條日志條目。

如果 S1 （任期 T 的領(lǐng)導(dǎo)者）提交了一條新的日志在它的任期里，然后 S5 在之后的任期 U 里被選舉為領(lǐng)導(dǎo)人，然后至少會有一個機器，如 S3，既擁有來自 S1 的日志，也給 S5 投票了。

在領(lǐng)導(dǎo)人 U 選舉的時候一定沒有那條被提交的日志條目（領(lǐng)導(dǎo)人從不會刪除或者覆蓋任何條目）。

領(lǐng)導(dǎo)人 T 復(fù)制這條日志條目給集群中的大多數(shù)節(jié)點，同時，領(lǐng)導(dǎo)人U 從集群中的大多數(shù)節(jié)點贏得了選票。因此，至少有一個節(jié)點（投票者、選民）同時接受了來自領(lǐng)導(dǎo)人T 的日志條目，并且給領(lǐng)導(dǎo)人U 投票了，這個投票者是產(chǎn)生這個矛盾的關(guān)鍵。

這個投票者必須在給領(lǐng)導(dǎo)人 U 投票之前先接受了從領(lǐng)導(dǎo)人 T 發(fā)來的已經(jīng)被提交的日志條目；否則他就會拒絕來自領(lǐng)導(dǎo)人 T 的附加日志請求（因為此時他的任期號會比 T 大）。

投票者在給領(lǐng)導(dǎo)人 U 投票時依然保有這條日志條目，因為任何中間的領(lǐng)導(dǎo)人都包含該日志條目（根據(jù)上述的假設(shè)），領(lǐng)導(dǎo)人從不會刪除條目，并且跟隨者只有和領(lǐng)導(dǎo)人沖突的時候才會刪除條目。

投票者把自己選票投給領(lǐng)導(dǎo)人 U 時，領(lǐng)導(dǎo)人 U 的日志必須和投票者自己一樣新。這就導(dǎo)致了兩者矛盾之一。

首先，如果投票者和領(lǐng)導(dǎo)人 U 的最后一條日志的任期號相同，那么領(lǐng)導(dǎo)人 U 的日志至少和投票者一樣長，所以領(lǐng)導(dǎo)人 U 的日志一定包含所有投票者的日志。這是另一處矛盾，因為投票者包含了那條已經(jīng)被提交的日志條目，但是在上述的假設(shè)里，領(lǐng)導(dǎo)人 U 是不包含的。

除此之外，領(lǐng)導(dǎo)人 U 的最后一條日志的任期號就必須比投票人大了。此外，他也比 T 大，因為投票人的最后一條日志的任期號至少和 T 一樣大（他包含了來自任期 T 的已提交的日志）。創(chuàng)建了領(lǐng)導(dǎo)人 U 最后一條日志的之前領(lǐng)導(dǎo)人一定已經(jīng)包含了那條被提交的日志（根據(jù)上述假設(shè)，領(lǐng)導(dǎo)人 U 是第一個不包含該日志條目的領(lǐng)導(dǎo)人）。所以，根據(jù)日志匹配特性，領(lǐng)導(dǎo)人 U 一定也包含那條被提交當(dāng)然日志，這里產(chǎn)生矛盾。

因此，假設(shè)不成立，所有比 T 大的領(lǐng)導(dǎo)人一定包含了所有來自 T 的已經(jīng)被提交的日志。日志匹配原則保證了未來的領(lǐng)導(dǎo)人也同時會包含被間接提交的條目

跟隨者或者候選人崩潰，會按如下處理：

領(lǐng)導(dǎo)者會不斷給它發(fā)送選舉和追加日志的RPC，直到成功

跟隨者會忽略它已經(jīng)處理過的追加日志的RPC

領(lǐng)導(dǎo)人選舉是 Raft 中對時間要求最為關(guān)鍵的方面。Raft 可以選舉并維持一個穩(wěn)定的領(lǐng)導(dǎo)人,只要系統(tǒng)滿足下面的時間要求：

廣播時間（broadcastTime） << 選舉超時時間（electionTimeout） << 平均故障間隔時間（MTBF）

廣播時間指的是從一個服務(wù)器并行的發(fā)送 RPCs 給集群中的其他服務(wù)器并接收響應(yīng)的平均時間；

選舉超時時間就是選舉的超時時間限制

平均故障間隔時間就是對于一臺服務(wù)器而言，兩次故障之間的平均時間。

選舉超時時間要大于廣播時間的原因是，防止跟隨者因為還沒收到領(lǐng)導(dǎo)者的心跳，而重新選主。

選舉超時時間要小于MTBF的原因是，防止選舉時，能正常工作的server沒有達到大多數(shù)。

對于廣播時間，一般在[0.5ms,20ms]之間，而平均故障間隔時間一般非常大，至少是按照月為單位。因此，一般選舉超時時間一般選擇范圍為[10ms,500ms]。因此，當(dāng)領(lǐng)導(dǎo)者掛掉后，能在較短時間內(nèi)重新選主。

http://thesecretlivesofdata.c...