1. 什么是Raft算法？

Raft 是英文”Reliable、Replicated、Redundant、And Fault-Tolerant”（“可靠、可復(fù)制、可冗余、可容錯”）的首字母縮寫。Raft算法是一種用于在分布式系統(tǒng)中實現(xiàn)共識的一致性算法。共識的目標(biāo)是確保在分布式系統(tǒng)中的節(jié)點之間就某個值達(dá)成一致，這對于保障系統(tǒng)的可靠性和一致性至關(guān)重要。Raft算法由Diego Ongaro和John Ousterhout于2013年提出，它以簡潔易懂的設(shè)計理念和算法流程，成為分布式系統(tǒng)中共識問題的熱門解決方案。

2. 三種角色(身份/狀態(tài))

在Raft算法中，分布式系統(tǒng)的節(jié)點可以處于三種不同的角色/狀態(tài)：

1. Leader（領(lǐng)導(dǎo)者）：負(fù)責(zé)處理所有客戶端請求，并決定日志的復(fù)制和提交。一個Raft集群只能有一個Leader。
2. Follower（追隨者）：在沒有Leader的情況下，F(xiàn)ollower處于等待狀態(tài)，接受Leader的指令。
3. Candidate（候選者）：在進(jìn)行Leader選舉的階段，節(jié)點首先成為候選者，通過競選過程競爭成為新的Leader。

三者的關(guān)系如下圖：

3. 如何選舉Leader

3.1 什么是任期

Raft算法中的term(任期)一般包含 election(選舉) 和 normal operation(工作期)，每個term(任期)由單調(diào)遞增的 term counter(任期編號)標(biāo)識，工作期可長可短也可能不存在，比如下圖(摘自官網(wǎng))中 Term4 的 Split Vote(平分選票)，因而未成功選舉 Leader(領(lǐng)導(dǎo)者)，因此工作期就不存在，需要進(jìn)行下一場選舉：

3.2 隨機(jī)超時

為了選舉新的Leader，候選者需要在一個隨機(jī)超時時間范圍內(nèi)等待響應(yīng)，避免多個候選者同時發(fā)起選舉。如果在超時時間內(nèi)沒有接收到有效的Leader心跳，節(jié)點會成為候選者并發(fā)起新的選舉,避免多Candidate選舉帶來的性能問題，隨機(jī)超時包含2層含義：

1.Follower(跟隨者)等待 Leader(領(lǐng)導(dǎo)者)心跳信息超時的時間間隔是隨機(jī)的；

2.Candidate(候選人)等待選舉超時的時間間隔是隨機(jī)的，也就是在一個隨機(jī)時間間隔內(nèi)，Candidate(候選人)沒有贏得 major(大多數(shù))選票，選舉就無效，Candidate(候選人)需要發(fā)起新一輪的選舉;

3.3 通信方式

Raft中的通信是通過RPC（遠(yuǎn)程過程調(diào)用）實現(xiàn)的，節(jié)點之間通過RPC進(jìn)行消息傳遞。
這里包含三種類型的 RPC：

• RequestVote RPCs：由 Candidate(候選人) 在選舉過程中發(fā)出
• AppendEntries RPCs：由 Leader(領(lǐng)導(dǎo)者) 發(fā)出，用來做日志復(fù)制和提供心跳機(jī)制
• Snapshot RPCs：當(dāng) Follower日志落后 Leader太多，就會以 parallel(并行)的方式發(fā)送快照 RPC請求，幫助Follower快速同步日志

3.4 選舉核心流程

• 當(dāng)節(jié)點啟動時，它處于Follower狀態(tài)，等待接收來自Leader的心跳消息。
• 如果Follower在超時時間內(nèi)沒有收到心跳消息，它會轉(zhuǎn)變?yōu)镃andidate狀態(tài)，發(fā)起一次選舉。
• 在選舉中，Candidate會向其他節(jié)點發(fā)送請求投票的消息。
• 其他節(jié)點收到請求后，會對候選者進(jìn)行投票，可以投給自己，也可以投給其他候選者，但每個節(jié)點只能投一票。
• 如果有節(jié)點得到了多數(shù)投票，它將成為新的Leader，更新自己的任期，并向其他節(jié)點發(fā)送心跳消息，使它們轉(zhuǎn)變?yōu)镕ollower狀態(tài)。
• 如果沒有任何候選者在一輪選舉中獲得多數(shù)票，則進(jìn)入下一輪選舉。

3.5 選舉詳解

Raft算法中的選舉是基于多數(shù)投票原則，要求候選者獲得超過半數(shù)的票數(shù)。這樣做的目的是為了保證選出的Leader得到大多數(shù)節(jié)點的支持，從而維持系統(tǒng)的穩(wěn)定性和一致性。

初始狀態(tài)

初始狀態(tài)時，每個節(jié)點的角色都是 Follower(跟隨者)，Term任期編號為 0(假設(shè)任期編號從0開始)，并且每個節(jié)點都伴有一個隨機(jī)超時( 假設(shè)節(jié)點A：100ms，節(jié)點B：150ms，節(jié)點C：180ms)，如下圖：

投票請求

因為節(jié)點A 的倒計時是 100ms，3 個節(jié)點中最小的，所以，節(jié)點A 最先結(jié)束倒計時被喚醒，成功晉升為 Candidate(候選人)，然后將自己的 Term counter (任期編號) +1，同時為自己先投一票，再向其他的 Follower 發(fā)起 RequestVote RPC 請求投票，如下圖：

投票響應(yīng)

Follower(跟隨者) 節(jié)點B 和 C 收到 Candidate(候選人)節(jié)點A 的 RequestVote Rpc 投票請求后，會做如下處理：

if(自己在Term任期編號1的選舉中已經(jīng)投過票){
   忽略請求；
}else {
  將選票 投給 Candidate(候選人)節(jié)點A，并且將自己的任期編號設(shè)置為1，重置自己的隨機(jī)超時；
}

這里假設(shè)節(jié)點B和C在任期編號為 1 的選舉中沒有投過票，所以會把選票投給節(jié)點A，并且把自己的任期編號設(shè)置為 1，重置自己的隨機(jī)超時，交互如下圖：

投票結(jié)束

Candidate(候選人)節(jié)點A 在任期編號為 1 的選舉內(nèi)贏得了大多數(shù)的選票，成為本任期的 Leader(領(lǐng)導(dǎo)者)，為了維持自己的 Leader(領(lǐng)導(dǎo)者) 地位，Leader(領(lǐng)導(dǎo)者)節(jié)點A 需要不間斷的給 Follower(跟隨者) 節(jié)點B和C 發(fā)送心跳，告訴他們自己還存活，讓 節(jié)點B和C 重置 隨機(jī)超時，防止節(jié)點B和C重新發(fā)起投票，整體交互如下圖：

到此，一個完整的 Leader選舉過程描述結(jié)束，該流程是不是和我們讀書時代的選班長有異曲同工之妙？

看完上面的選舉描述，不知道你會不會產(chǎn)生這樣的疑問：假如集群中有 2個或者多個節(jié)點同時發(fā)起投票，整個過程會怎樣了？

多個 Candidate問題

在上述 Leader選舉的描述中我們可以發(fā)現(xiàn)，每個節(jié)點都有一個隨機(jī)超時，因此節(jié)點被喚醒是隨機(jī)的，這樣大大降低了多個節(jié)點在同一時刻被喚醒成為 Candidate(候選人) 的概率， 但是小概率的事件不代表不發(fā)生，假如有 2個節(jié)點同時被喚醒，整個 Leader選舉流程會怎樣？

這里我們假設(shè)節(jié)點A和B的隨機(jī)超時都是 100ms，這樣兩個節(jié)點就會同時被喚醒，成為 Candidate(候選人)，首先 節(jié)點 A 和 B 會分別為自己投一票，然后向其他節(jié)點發(fā)起投票請求，如果節(jié)點A的投票請求先于節(jié)點B到達(dá)節(jié)點C， 最終，節(jié)點A 獲取 2張選票，節(jié)點B 獲取 1張選票，因此，節(jié)點A 獲取大多數(shù)選票成為 Leader(領(lǐng)導(dǎo)者)，節(jié)點B 的角色會從 Candidate 恢復(fù)成 Follower，整個交互如下圖：

Split Vote 平票問題

上述描述的都是基于”奇數(shù)個節(jié)點的集群”，如果集群中的節(jié)點是偶數(shù)個，結(jié)果又是怎樣了，為了更好的說明問題，此處采用 4個節(jié)點的集群進(jìn)行說明：

假設(shè)節(jié)點 A 和 B 的隨機(jī)超時都是 100ms，這樣兩個節(jié)點就會同時被喚醒成為 Candidate(候選人)，首先節(jié)點 A 和 B 會分別為自己投一票，然后再向其他節(jié)點請求投票，因為節(jié)點 A 和 B 已為自己投票， 根據(jù)同一任期內(nèi)最多投 1票的約束，節(jié)點 A 和 B 會拒絕給對方投票， 最終 節(jié)點 A 和 B 各自只能獲取 2票，這里出現(xiàn)了一個經(jīng)典的問題：Split Vote(平分票數(shù))，該如何處理呢？

在這種”平分選票”未選出 Leader(領(lǐng)導(dǎo)者)的情況下，所有節(jié)點會全部恢復(fù)成 Follower(跟隨者) 狀態(tài)，重新設(shè)置隨機(jī)超時時間，準(zhǔn)備下一輪的選舉。不過需要提醒的是選舉的過程越長越增加了集群不可用的時長，因此要盡量避免 Split Vote問題。整個交互如下圖：

腦裂問題

上文我們一直在強(qiáng)調(diào)：一個集群中最多只能有一個 Leader，假如在一個集群內(nèi)部發(fā)生網(wǎng)絡(luò)分區(qū)，形成了 2個小分區(qū)，會不會出現(xiàn) 2個Leader？如果有，該如何解決？

這里以[A,B,C,D,E] 5個節(jié)點組成的集群為例，假如原集群的Leader是節(jié)點A，如果內(nèi)部出現(xiàn)了網(wǎng)絡(luò)問題，節(jié)點[A,B]為一個分區(qū)，節(jié)點[C,D,E]為一個分區(qū)，節(jié)點A為原來的 Leader，節(jié)點C獲得[C,D,E]分區(qū)的所有選票也成為 Leader，因此一個集群產(chǎn)生了 2個Leader，這就是我們常說的”腦裂問題”。

Raft是如何解決這種腦裂問題？

答案：當(dāng)網(wǎng)絡(luò)恢復(fù)正常后，兩個分區(qū)的 Leader都會向其他節(jié)點發(fā)送心跳，當(dāng)節(jié)點A 收到 節(jié)點C的心跳之后，發(fā)現(xiàn)C的任期比自己大，因此節(jié)點A恢復(fù)成Follower，因此整個集群就恢復(fù)成只有一個 Leader的狀態(tài)。

整體交互如下圖：

上文在對任期的描述時講到，任期通常包含 Leader選舉和 normal operation(工作期)兩部分，Leader選舉過程已分析完成，接下來分析 normal operation(工作期)。

4. 如何復(fù)制日志

4.1 什么是日志條目

在Raft算法中，每個節(jié)點維護(hù)著一份日志，其中包含了系統(tǒng)中所有狀態(tài)變更的記錄。每一次狀態(tài)變更被稱為一個日志條目。

• 索引值：日志條目對應(yīng)的整數(shù)索引值，它是用來標(biāo)識日志條目的，是一個連續(xù)單調(diào)遞增的整數(shù)；
• 任期編號：創(chuàng)建這條日志條目的 Leader(領(lǐng)導(dǎo)者)的任期編號;
• 指令：客戶端請求指定的、狀態(tài)機(jī)需要執(zhí)行的指令；

4.2 日志復(fù)制過程

Raft算法通過日志的復(fù)制來實現(xiàn)共識。Leader接收客戶端的請求，并將請求轉(zhuǎn)換為日志條目，然后將這些日志條目復(fù)制到其他節(jié)點。當(dāng)大多數(shù)節(jié)點都成功地復(fù)制了這些日志條目后，Leader可以提交這些日志條目，并向客戶端返回成功響應(yīng)。

• Leader(領(lǐng)導(dǎo)者) 接收到客戶端請求后，創(chuàng)建一個 new entry(新日志條目)，并 appends(追加)到本地日志中(Leader的日志條目為uncommitted狀態(tài))；
• Leader(領(lǐng)導(dǎo)者) 以同步的方式向所有 Follower(跟隨者) 發(fā)送 AppendEntries RPC 日志條目復(fù)制請求(Follower的日志條目為uncommitted狀態(tài))；
• Leader(領(lǐng)導(dǎo)者) 得到 major(大多數(shù)) Follower(跟隨者)的復(fù)制成功的響應(yīng)后，Leader(領(lǐng)導(dǎo)者)將日志條目應(yīng)用到它的狀態(tài)機(jī)中(Leader的日志條目為committed狀態(tài))；
• Leader(領(lǐng)導(dǎo)者) 將執(zhí)行的結(jié)果返回給客戶端；
• Leader(領(lǐng)導(dǎo)者) 通過心跳或新的 AppendEntries RPC 將提交了某條日志條目的狀態(tài)同步給Follower(跟隨者)，F(xiàn)ollower(跟隨者)將日志條目狀態(tài)同步到本地狀態(tài)機(jī)中(Follower的日志條目為committed狀態(tài))；
• 如果 Follower(跟隨者)出現(xiàn)崩潰、運行緩慢、網(wǎng)絡(luò)丟包，Leader(領(lǐng)導(dǎo)者)會不斷地重試 AppendEntries RPCs（即使已經(jīng)對客戶端作出了響應(yīng)）直到所有的 Follower(跟隨者)成功存儲了所有的日志條目；

通過上述日志的復(fù)制過程可以看出日志的提交過程有點類似兩階段提交(2PC)，不過與2PC的區(qū)別在于，Leader只需要 majority(大多數(shù))節(jié)點的回復(fù)即可，只要過半節(jié)點處于工作狀態(tài)則系統(tǒng)就是可用的。 然而，這種是一種比較理想的狀態(tài)，假如在復(fù)制日志的過程中，出現(xiàn)了進(jìn)程崩潰、服務(wù)器宕機(jī)等問題，就可能導(dǎo)致日志不一致，Raft 會如何處理呢？

4.3 日志的一致性

在Raft算法中，所有節(jié)點的日志必須保持一致。這意味著，如果一個日志條目在某個節(jié)點被提交，那么這個日志條目也必須在所有節(jié)點上被提交。通過使用多數(shù)投票的方式選出Leader，并確保Leader復(fù)制的日志達(dá)到大多數(shù)節(jié)點，Raft算法保證了日志的一致性。

圖中包含了 1個 Leader 和 1個 Follower的所有日志條目，整個復(fù)制過程分以下幾個步驟(步驟1-4是一致性檢查機(jī)制)：

1.Leader(領(lǐng)導(dǎo)者) 當(dāng)前最大日志條目索引是 10，因此 Leader(領(lǐng)導(dǎo)者) 會通過日志復(fù)制 RPC 消息將 index=9 的日志發(fā)送給 Follower(跟隨者)，F(xiàn)ollower(跟隨者) 判斷自己沒有index=9的日志，因此拒絕更新日志并響應(yīng) Leader 失敗信息。

2.Leader(領(lǐng)導(dǎo)者) 收到 Follower(跟隨者) 的失敗響應(yīng)后，執(zhí)行index-1，將 index=8的日志發(fā)送給 Follower(跟隨者)，F(xiàn)ollower(跟隨者) 判斷自己index=8日志條目信息為term=4,x->7，和 Leader(領(lǐng)導(dǎo)則)日志條目不相同 ，因此再次拒絕更新，響應(yīng) Leader失敗信息。

3.Leader(領(lǐng)導(dǎo)者) 收到 Follower 的失敗響應(yīng)后，重復(fù)操作上述過程，直到 index=6;

4.Leader(領(lǐng)導(dǎo)者) 將 index=6的日志發(fā)送給 Follower(跟隨者)，F(xiàn)ollower判斷自己 index=6 日志條目中的 term和command 和 Leader相同，響應(yīng)日志復(fù)制成功。因此，Leader(領(lǐng)導(dǎo)者)就知道在 index=6「term=3,y->1」日志條目位置，F(xiàn)ollower(跟隨者)的日志條目與自己相同。

5.Leader(領(lǐng)導(dǎo)者) 通過日志復(fù)制 RPC消息，強(qiáng)制 Follower(跟隨者)復(fù)制并更新覆蓋 index=6之后的所有日志條目(不一致的日志條目)，達(dá)到 Follower 與 Leader的日志保持一致；

6.集群中多個 Follower(跟隨者)，只需要重復(fù)上述過程，就能最終實現(xiàn)了集群各節(jié)點日志的一致。

5. 節(jié)點變更問題

節(jié)點變更是分布式系統(tǒng)很常見的問題，比如，服務(wù)器擴(kuò)容需要增加機(jī)器，服務(wù)器縮容需要減少機(jī)器，出現(xiàn)節(jié)點故障需要變更機(jī)器等等。 在Raft算法中，為了描述節(jié)點變更，作者使用 Configuration(配置) 這個重要的概念，可以把”配置”理解為集群中所有節(jié)點地址信息的集合。比如節(jié)點 A、B、C 組成的集群，那么集群的配置就是[A, B, C]集合。

集群節(jié)點的變更可能會導(dǎo)致集群分裂，出現(xiàn) 2個 Leader(領(lǐng)導(dǎo)者)，如下圖，集群[A,B,C] 增加節(jié)點D和E，如果發(fā)生網(wǎng)絡(luò)分區(qū)，形成 [A,B] 和 [C,D,E] 兩個小分區(qū)， 節(jié)點A 獲取原配置的大多數(shù)的選票成為 Leader(領(lǐng)導(dǎo)者)，節(jié)點E 獲取新配置的大多數(shù)選票成為 Leader(領(lǐng)導(dǎo)者)，出現(xiàn)了 2個 Leader(領(lǐng)導(dǎo)者)，違背了Raft算法最多一個 Leader(領(lǐng)導(dǎo)者)的原則。如下圖：

5.1 聯(lián)合共識

在Raft算法中，當(dāng)節(jié)點需要進(jìn)行變更時，比如加入新節(jié)點或移除現(xiàn)有節(jié)點，可以通過聯(lián)合共識來保證變更的一致性。新節(jié)點必須和大多數(shù)節(jié)點達(dá)成共識，才能成為集群的一部分。
joint consensus(聯(lián)合共識)是指 集群從舊配置變更成新配置的過程中使用了一個過渡的中間配置，聯(lián)合共識配置是新舊配置的并集，此方法允許一次性向集群中插入多個節(jié)點而不會出現(xiàn)腦裂等 (safety) 問題，并且整個集群在配置轉(zhuǎn)換的過程中依然能夠接收用戶請求，從而實現(xiàn)配置切換對集群調(diào)用方無感知， 因為在聯(lián)合共識階段，集群會出現(xiàn)新舊兩種配置，為了更好的工作，聯(lián)合共識做了如下的約束：

• 約束1. 新舊配置的日志會復(fù)制給新、舊配置的所有節(jié)點；
• 約束2. 新、舊配置的任何節(jié)點都可能成為 Leader(領(lǐng)導(dǎo)者)；
• 約束3. 選舉和日志復(fù)制階段需要在新老配置上面都超多半數(shù)才能被提交生效；

下面摘取了Raft官方關(guān)于聯(lián)合共識階段配置變更的時間線描述圖：

其中，虛線代表已創(chuàng)建但是未提交的配置項，實線代表最新的已提交的配置項。

首先，Leader(領(lǐng)導(dǎo)者) 創(chuàng)建 Cold,new 日志條目，并復(fù)制到新舊配置中的大多數(shù)，此時所有的日志條目都需要被聯(lián)合共識。

然后，Leader(領(lǐng)導(dǎo)者) 創(chuàng)建 Cnew 日志條目，并復(fù)制到 Cnew(新配置)中的大多數(shù)。因此，舊配置和新配置不會存在可以同時做出決策的時間點。

鑒于此圖比較晦澀難懂，因此我們以一個實例來進(jìn)行講述，假設(shè)集群有A、B、C三個節(jié)點，需要往集群中添加 D、E兩個節(jié)點，看看聯(lián)合共識是如何工作的。

首先， Leader(領(lǐng)導(dǎo)者) 向所有 Follower發(fā)送一條配置變更日志 Cold,new[A,B,C,D,E]，告知集群要新增兩個節(jié)點[D,E]。根據(jù)約束1，日志會被復(fù)制到新舊配置的所有節(jié)點。如下圖：

其次，根據(jù)約束3，配置變更日志Cold,new[A,B,C,D,E] 在新舊配置中都需要大多數(shù)節(jié)點復(fù)制成功，才能被成功應(yīng)用。換句話說，假設(shè)舊配置的大多數(shù)為[A,B]、新配置的大多數(shù)為[A,B,D]， 那么這些節(jié)點都需要復(fù)制成功，如下圖：

最后，Cold,new 被成功應(yīng)用后，Leader(領(lǐng)導(dǎo)者)再發(fā)送一條新的 Cnew RPC日志復(fù)制請求，通知集群Follower(跟隨者)可以使用新配置。Follower(跟隨者)收到日志復(fù)制RPC后，在 Raft一致性檢查機(jī)制保證下切換成新配置，Leader(領(lǐng)導(dǎo)者)因為已經(jīng)處于新配置狀態(tài)，所以不需要聯(lián)合共識，到此，舊配置就平穩(wěn)過渡到新配置，如下圖：

對于新的節(jié)點D、E，Raft 會通過日志一致性檢查來復(fù)制領(lǐng)導(dǎo)者的所有日志條目，從而保證它們同樣能夠保持日志完整性。

上文我們分析了往集群中新增2節(jié)點的流程，接下來分析上述流程為什么不會產(chǎn)生腦裂。我們依然假設(shè)集群產(chǎn)生了網(wǎng)絡(luò)分區(qū)，形成了[A,B] 和 [C,D,E] 兩個小分區(qū)：

1.假如 Leader(領(lǐng)導(dǎo)者)節(jié)點A 未發(fā)送 Cold,new RPC變更日志請求，[A,B] 分區(qū)依然是舊配置，節(jié)點A 是領(lǐng)導(dǎo)者；而[C,D,E]分區(qū)，當(dāng)節(jié)點C 發(fā)起選舉時，因為不知道節(jié)點D、E 的存在，無法獲取到大多數(shù)節(jié)點的投票。因此兩個分區(qū)只有一個 Leader(領(lǐng)導(dǎo)者) 節(jié)點A，符合預(yù)期。

2.假如 Leader(領(lǐng)導(dǎo)者)節(jié)點A 已發(fā)送 Cold,new RPC變更日志請求，此時發(fā)生了網(wǎng)絡(luò)分區(qū)，會出現(xiàn)下面兩種情情況：

3.如果 Cold,new 沒有被大多數(shù)節(jié)點確認(rèn)，那么 Leader(領(lǐng)導(dǎo)者)節(jié)點A 無法應(yīng)用該配置，[A,B] 依然是舊配置對外提供服務(wù)，[C,D,E]分區(qū)，C任然是舊配置，感知不到D,E的存在嗎，所以不可能成為 Leader，D或E任何一個節(jié)點獲取不到大多數(shù)選票也無法成為Leader(領(lǐng)導(dǎo)者)，符合預(yù)期；

4.如果 Cold,new 已經(jīng)被大多數(shù)節(jié)點復(fù)制，那么 Leader(領(lǐng)導(dǎo)者)節(jié)點A 會應(yīng)用該配，并向所有 Follower(跟隨者)發(fā)送 Cnew RPC復(fù)制日志請求，因為網(wǎng)絡(luò)分區(qū)導(dǎo)致 Cnew無法被聯(lián)合共識，領(lǐng)導(dǎo)者 A 后續(xù)不會提交任何日志（在一些實現(xiàn)中會自動退位為跟隨者）；對于分區(qū) [C,D,E] 無法 Cnew RPC復(fù)制日志請求，C 任然是舊配置無法獲取到大多數(shù)選票，節(jié)點D，E無法獲取到大多數(shù)選票，該分區(qū)也無法選舉出 Leader(領(lǐng)導(dǎo)者)。符合預(yù)期。

5.假如 Cnew 階段產(chǎn)生了分區(qū)，因為 Cold,new 已經(jīng)生效，[A,B] 和 [C,D,E] 兩個小分區(qū)都拿到了新配置[A,B,C,D,E]，因此[A,B]分區(qū)無法獲取新配置的大多數(shù)選票，無法選出新 Leader(領(lǐng)導(dǎo)者)，也就不可能發(fā)生腦裂，符合預(yù)期。

盡管 joint consensus(聯(lián)合共識)允許一次性向集群中插入多個節(jié)點且不會出現(xiàn)腦裂等問題，但由于該方法理解和實現(xiàn)都比較難，所以 Raft作者提出了一種改進(jìn)的方法：single-server changes(單服務(wù)器變更)。

5.2 單服務(wù)器變更

單服務(wù)器變更，就是每次只能有一個節(jié)點服務(wù)器成員變更。如果需要變更多個服務(wù)器節(jié)點，則需要執(zhí)行多次單服務(wù)器變更。 我們還是以圖文的方式來進(jìn)行解釋：

假如 集群有節(jié)點A、節(jié)點B、節(jié)點C，現(xiàn)在需要增加 2個節(jié)點(節(jié)點D，節(jié)點E)，增加的方式是先增加節(jié)點D

• 第一步，Leader(領(lǐng)導(dǎo)者)節(jié)點A 向新節(jié)點D 同步數(shù)據(jù)；
• 第二步，Leader(領(lǐng)導(dǎo)者)節(jié)點A 將新配置[A, B, C, D]作為一個日志條目，復(fù)制到新配置中所有節(jié)點(節(jié)點 A、B、C、D)上，然后將新配置的日志條目應(yīng)用（Apply）到本地狀態(tài)機(jī)，完成單節(jié)點變更。

同理再增加節(jié)點E：

• 第一步，Leader(領(lǐng)導(dǎo)者)節(jié)點A 向新節(jié)點E 同步數(shù)據(jù)；
• 第二步，Leader(領(lǐng)導(dǎo)者)節(jié)點A 將新配置[A, B, C, D, E]作為一個日志條目，復(fù)制到新配置中所有節(jié)點(節(jié)點 A、B、C、D、E)上，然后將新配置的日志條目應(yīng)用（Apply）到本地狀態(tài)機(jī)，完成單節(jié)點變更。

刪除節(jié)點E:

• 第一步，先刪除 節(jié)點 E；
• 第二步，Leader(領(lǐng)導(dǎo)者)節(jié)點A 將新配置[A, B, C, D]作為一個日志條目，復(fù)制到新配置中所有節(jié)點(節(jié)點 A、B、C、D)上，然后將新配置的日志條目應(yīng)用(Apply)到本地狀態(tài)機(jī)，完成單節(jié)點變更。

通過上述對單服務(wù)器的增加和刪除可以看出，每次單服務(wù)器節(jié)點的增減，可以保證新舊集群至少存在一個交集服務(wù)器節(jié)點，這樣就不會在新舊配置同時存在 2個“大多數(shù)”，從而保證集群只能有一個 Leader(領(lǐng)導(dǎo)者)。

特別注意

在作者Diego Ongaro(迭戈·安加羅) bug in single-server membership changes 的文章中特別說明了，單服務(wù)器變更的方式在串行化的方式下可以保證一個集群 只能有一個 Leader，但是在并發(fā)的、競爭可能導(dǎo)致多個 Leader，從而導(dǎo)致安全違規(guī)（腦裂）。

6. Safety

前面章節(jié)描述了 Raft 如何做 Leader Election(Leader選舉) 和 Log Replication(日志復(fù)制)。然而，到目前為止所討論的機(jī)制并不能充分地保證每一個狀態(tài)機(jī)會按相同的順序執(zhí)行相同的指令。比如說，一個 Follower(跟隨者) 可能會進(jìn)入不可用狀態(tài)，在此期間，Leader 可能提交了若干的日志條目，然后這個 Follower 可能被選舉為新Leader 并且用新的日志條目去覆蓋這些日志條目。這樣就會造成不同的狀態(tài)機(jī)執(zhí)行不同的指令的情況。 對于上述問題，Raft 如何保證安全？

6.1 選舉約束

1. 同一任期內(nèi)每個節(jié)點最多只能投票 1次，并且按照 first-come-first-served(先來先服務(wù)) 的原則
2. 日志條目的傳送只能從 Leader 到 Follower，Leader 從來不會覆蓋本地日志中已有的日志
3. Candidate(候選人) 只有獲得集群中大多數(shù)選票才能成為 Leader(領(lǐng)導(dǎo)者)
4. 日志完整性高的 Follower(跟隨者)拒絕投票給日志完整性低的 Candidate(候選人)，這里的日志指的是已復(fù)制未commit狀態(tài)。也就是說，即便 Candidate(候選人)的 term 大于 Follower(跟隨者)的 term，假如 Candidate(候選人) 向 Follower(跟隨者)發(fā)送了一條投票RPC，如果當(dāng)前消息中的term 小于 Follower(跟隨者)最后一條消息的 term，則 Follower(跟隨者) 拒絕給 Candidate(候選人)投票

6.2 Leader只能提交任期內(nèi)的日志條目

首先我們以圖文的方式來展示一個已經(jīng)被存儲到大多數(shù)節(jié)點的日志條目，仍然有可能會被新 Leader覆蓋的場景：

• 在圖A中，S1是 Leader，將index=2的日志復(fù)制給了S2，此時S1的數(shù)據(jù)還沒有復(fù)制大多數(shù)節(jié)點
• 在圖B中，S1宕機(jī)了，S5 從 [S2,S3,S4,S5] 獲得大多數(shù)選票成為 Leader，任期編號為3，然后收到客戶端的指令，將日志存放在 index=2 位置上
• 在圖C中，S5宕機(jī)了，S1重啟，假如S1當(dāng)選為 Leader，然后S1繼續(xù)將它在任期2的日志條目復(fù)制給[S2,S3,S4]成功，但是還未被提交
• 情況1：在圖D中，假設(shè)S1在提交日志之前宕機(jī)，S5重啟，因為S5最后日志條目上的任期為3，大于[S2,S3,S4]的任期編號2，所以S5可以得到[S2,S3,S4]大多數(shù)選票成為 Leader，然后 S5繼續(xù)將它在任期3的日志條目復(fù)制到大多數(shù)節(jié)點[S2,s3,S4]，因此覆蓋了S1復(fù)制給[S2,S3]中 index=2處的日志
• 情況2：在圖E中，S1在宕機(jī)之前把任期3的日志復(fù)制到大多數(shù)節(jié)點的index=3處，那么 S5就不可能成為 Leader，這種情況下，之前所有的日志被提交了

為了解決上圖中日志被覆蓋的問題，Raft 規(guī)定 Leader只能提交任期內(nèi)的日志條目。

7. 實際使用

Raft算法已經(jīng)在許多分布式系統(tǒng)中得到了廣泛的應(yīng)用，其中包括分布式數(shù)據(jù)庫、分布式存儲系統(tǒng)、分布式文件系統(tǒng)等。以下是一些實際應(yīng)用場景：

1. 分布式數(shù)據(jù)庫：在數(shù)據(jù)庫集群中，Raft算法可以用于實現(xiàn)數(shù)據(jù)的復(fù)制和一致性，確保所有節(jié)點的數(shù)據(jù)保持一致。
2. 分布式存儲系統(tǒng)：在分布式存儲系統(tǒng)中，Raft算法可以用于實現(xiàn)數(shù)據(jù)的復(fù)制和數(shù)據(jù)一致性，確保數(shù)據(jù)的可靠性和高可用性。
3. 分布式文件系統(tǒng)：在分布式文件系統(tǒng)中，Raft算法可以用于實現(xiàn)元數(shù)據(jù)的復(fù)制和一致性，確保文件系統(tǒng)的正確運行。
4. 分布式計算平臺：在分布式計算平臺中，Raft算法可以用于協(xié)調(diào)不同的計算節(jié)點，確保任務(wù)的分發(fā)和執(zhí)行的一致性。
5. 分布式消息隊列：在分布式消息隊列中，Raft算法可以用于實現(xiàn)消息的復(fù)制和分發(fā)，確保消息隊列的可靠性和高可用性。

8. 總結(jié)

Raft算法是一種簡潔而高效的分布式一致性算法，通過引入Leader選舉和日志復(fù)制的機(jī)制，確保了分布式系統(tǒng)的共識和一致性。它具有易于理解和實現(xiàn)的優(yōu)點，被廣泛應(yīng)用于各種分布式系統(tǒng)中。

Raft算法的核心思想是將分布式系統(tǒng)的復(fù)雜問題簡化為幾個簡單的步驟，通過選舉Leader和復(fù)制日志的方式來實現(xiàn)共識。這種簡單而有效的設(shè)計理念，使得Raft算法成為了分布式系統(tǒng)中一種受歡迎的共識算法。

然而，值得注意的是，Raft算法并不是解決分布式系統(tǒng)共識問題的唯一方案。在實際應(yīng)用中，根據(jù)具體的場景和需求，還可以考慮其他的一致性算法，如Paxos算法等。