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

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

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

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

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

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

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

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

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

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

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

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

他自己贏得了這次的選舉

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

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

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

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

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

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

一段時(shí)間之后沒有任何一個(gè)獲勝的人

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

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

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

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

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

如果兩個(gè)log entry有相同的index和term，那么它們存儲(chǔ)相同的指令

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

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

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

log entry不會(huì)改變它們在日志中的位置

特性二通過以下保證：

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

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

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

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

領(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)提交了。下圖展示了一種情況，一條已經(jīng)被存儲(chǔ)到大多數(shù)節(jié)點(diǎn)上的老日志條目，也依然有可能會(huì)被未來的領(lǐng)導(dǎo)人覆蓋掉。

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

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

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

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

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

為了上圖描述的情況，Raft 永遠(yuǎn)不會(huì)通過計(jì)算副本數(shù)目的方式去提交一個(gè)之前任期內(nèi)的日志條目。只有領(lǐng)導(dǎo)人當(dāng)前任期里的日志條目通過計(jì)算副本數(shù)目可以被提交；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性，之前的日志條目也都會(huì)被間接的提交。例如，圖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)提交了一條日志條目，但是這條日志條目沒有被存儲(chǔ)到未來某個(gè)任期的領(lǐng)導(dǎo)人的日志中。設(shè)大于 T 的最小任期 U 的領(lǐng)導(dǎo)人 U 沒有這條日志條目。

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

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

領(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 投票了，這個(gè)投票者是產(chǎn)生這個(gè)矛盾的關(guān)鍵。

這個(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 大）。

投票者在給領(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ì)刪除條目。

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

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

除此之外，領(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)生矛盾。

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

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

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

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

領(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）

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

選舉超時(shí)時(shí)間就是選舉的超時(shí)時(shí)間限制

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

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

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

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

http://thesecretlivesofdata.c...