Raft算法：保障分布式系統(tǒng)共識(shí)的穩(wěn)健之道
1. 什么是Raft算法？
Raft 是英文”Reliable、Replicated、Redundant、And Fault-Tolerant”（“可靠、可復(fù)制、可冗余、可容錯(cuò)”）的首字母縮寫(xiě)。Raft算法是一種用于在分布式系統(tǒng)中實(shí)現(xiàn)共識(shí)的一致性算法。共識(shí)的目標(biāo)是確保在分布式系統(tǒng)中的節(jié)點(diǎn)之間就某個(gè)值達(dá)成一致，這對(duì)于保障系統(tǒng)的可靠性和一致性至關(guān)重要。Raft算法由Diego Ongaro和John Ousterhout于2013年提出，它以簡(jiǎn)潔易懂的設(shè)計(jì)理念和算法流程，成為分布式系統(tǒng)中共識(shí)問(wèn)題的熱門(mén)解決方案。
2. 三種角色(身份/狀態(tài))
在Raft算法中，分布式系統(tǒng)的節(jié)點(diǎn)可以處于三種不同的角色/狀態(tài)：
- Leader（領(lǐng)導(dǎo)者）：負(fù)責(zé)處理所有客戶端請(qǐng)求，并決定日志的復(fù)制和提交。一個(gè)Raft集群只能有一個(gè)Leader。
- Follower（追隨者）：在沒(méi)有Leader的情況下，F(xiàn)ollower處于等待狀態(tài)，接受Leader的指令。
- Candidate（候選者）：在進(jìn)行Leader選舉的階段，節(jié)點(diǎn)首先成為候選者，通過(guò)競(jìng)選過(guò)程競(jìng)爭(zhēng)成為新的Leader。
三者的關(guān)系如下圖：
3. 如何選舉Leader
3.1 什么是任期
Raft算法中的term(任期)一般包含 election(選舉) 和 normal operation(工作期)，每個(gè)term(任期)由單調(diào)遞增的 term counter(任期編號(hào))標(biāo)識(shí)，工作期可長(zhǎng)可短也可能不存在，比如下圖(摘自官網(wǎng))中 Term4 的 Split Vote(平分選票)，因而未成功選舉 Leader(領(lǐng)導(dǎo)者)，因此工作期就不存在，需要進(jìn)行下一場(chǎng)選舉：
3.2 隨機(jī)超時(shí)
為了選舉新的Leader，候選者需要在一個(gè)隨機(jī)超時(shí)時(shí)間范圍內(nèi)等待響應(yīng)，避免多個(gè)候選者同時(shí)發(fā)起選舉。如果在超時(shí)時(shí)間內(nèi)沒(méi)有接收到有效的Leader心跳，節(jié)點(diǎn)會(huì)成為候選者并發(fā)起新的選舉,避免多Candidate選舉帶來(lái)的性能問(wèn)題，隨機(jī)超時(shí)包含2層含義：
1.Follower(跟隨者)等待 Leader(領(lǐng)導(dǎo)者)心跳信息超時(shí)的時(shí)間間隔是隨機(jī)的；
2.Candidate(候選人)等待選舉超時(shí)的時(shí)間間隔是隨機(jī)的，也就是在一個(gè)隨機(jī)時(shí)間間隔內(nèi)，Candidate(候選人)沒(méi)有贏得 major(大多數(shù))選票，選舉就無(wú)效，Candidate(候選人)需要發(fā)起新一輪的選舉;
3.3 通信方式
Raft中的通信是通過(guò)RPC（遠(yuǎn)程過(guò)程調(diào)用）實(shí)現(xiàn)的，節(jié)點(diǎn)之間通過(guò)RPC進(jìn)行消息傳遞。
這里包含三種類型的 RPC：
- RequestVote RPCs：由 Candidate(候選人) 在選舉過(guò)程中發(fā)出
- AppendEntries RPCs：由 Leader(領(lǐng)導(dǎo)者) 發(fā)出，用來(lái)做日志復(fù)制和提供心跳機(jī)制
- Snapshot RPCs：當(dāng) Follower日志落后 Leader太多，就會(huì)以 parallel(并行)的方式發(fā)送快照 RPC請(qǐng)求，幫助Follower快速同步日志
3.4 選舉核心流程
- 當(dāng)節(jié)點(diǎn)啟動(dòng)時(shí)，它處于Follower狀態(tài)，等待接收來(lái)自Leader的心跳消息。
- 如果Follower在超時(shí)時(shí)間內(nèi)沒(méi)有收到心跳消息，它會(huì)轉(zhuǎn)變?yōu)镃andidate狀態(tài)，發(fā)起一次選舉。
- 在選舉中，Candidate會(huì)向其他節(jié)點(diǎn)發(fā)送請(qǐng)求投票的消息。
- 其他節(jié)點(diǎn)收到請(qǐng)求后，會(huì)對(duì)候選者進(jìn)行投票，可以投給自己，也可以投給其他候選者，但每個(gè)節(jié)點(diǎn)只能投一票。
- 如果有節(jié)點(diǎn)得到了多數(shù)投票，它將成為新的Leader，更新自己的任期，并向其他節(jié)點(diǎn)發(fā)送心跳消息，使它們轉(zhuǎn)變?yōu)镕ollower狀態(tài)。
- 如果沒(méi)有任何候選者在一輪選舉中獲得多數(shù)票，則進(jìn)入下一輪選舉。
3.5 選舉詳解
Raft算法中的選舉是基于多數(shù)投票原則，要求候選者獲得超過(guò)半數(shù)的票數(shù)。這樣做的目的是為了保證選出的Leader得到大多數(shù)節(jié)點(diǎn)的支持，從而維持系統(tǒng)的穩(wěn)定性和一致性。
初始狀態(tài)
初始狀態(tài)時(shí)，每個(gè)節(jié)點(diǎn)的角色都是 Follower(跟隨者)，Term任期編號(hào)為 0(假設(shè)任期編號(hào)從0開(kāi)始)，并且每個(gè)節(jié)點(diǎn)都伴有一個(gè)隨機(jī)超時(shí)( 假設(shè)節(jié)點(diǎn)A：100ms，節(jié)點(diǎn)B：150ms，節(jié)點(diǎn)C：180ms)，如下圖：
投票請(qǐng)求
因?yàn)楣?jié)點(diǎn)A 的倒計(jì)時(shí)是 100ms，3 個(gè)節(jié)點(diǎn)中最小的，所以，節(jié)點(diǎn)A 最先結(jié)束倒計(jì)時(shí)被喚醒，成功晉升為 Candidate(候選人)，然后將自己的 Term counter (任期編號(hào)) +1，同時(shí)為自己先投一票，再向其他的 Follower 發(fā)起 RequestVote RPC 請(qǐng)求投票，如下圖：
投票響應(yīng)
Follower(跟隨者) 節(jié)點(diǎn)B 和 C 收到 Candidate(候選人)節(jié)點(diǎn)A 的 RequestVote Rpc 投票請(qǐng)求后，會(huì)做如下處理：
if(自己在Term任期編號(hào)1的選舉中已經(jīng)投過(guò)票){
忽略請(qǐng)求；
}else {
將選票 投給 Candidate(候選人)節(jié)點(diǎn)A，并且將自己的任期編號(hào)設(shè)置為1，重置自己的隨機(jī)超時(shí)；
}這里假設(shè)節(jié)點(diǎn)B和C在任期編號(hào)為 1 的選舉中沒(méi)有投過(guò)票，所以會(huì)把選票投給節(jié)點(diǎn)A，并且把自己的任期編號(hào)設(shè)置為 1，重置自己的隨機(jī)超時(shí)，交互如下圖：
投票結(jié)束
Candidate(候選人)節(jié)點(diǎn)A 在任期編號(hào)為 1 的選舉內(nèi)贏得了大多數(shù)的選票，成為本任期的 Leader(領(lǐng)導(dǎo)者)，為了維持自己的 Leader(領(lǐng)導(dǎo)者) 地位，Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 需要不間斷的給 Follower(跟隨者) 節(jié)點(diǎn)B和C 發(fā)送心跳，告訴他們自己還存活，讓 節(jié)點(diǎn)B和C 重置 隨機(jī)超時(shí)，防止節(jié)點(diǎn)B和C重新發(fā)起投票，整體交互如下圖：
到此，一個(gè)完整的 Leader選舉過(guò)程描述結(jié)束，該流程是不是和我們讀書(shū)時(shí)代的選班長(zhǎng)有異曲同工之妙？
看完上面的選舉描述，不知道你會(huì)不會(huì)產(chǎn)生這樣的疑問(wèn)：假如集群中有 2個(gè)或者多個(gè)節(jié)點(diǎn)同時(shí)發(fā)起投票，整個(gè)過(guò)程會(huì)怎樣了？
多個(gè) Candidate問(wèn)題
在上述 Leader選舉的描述中我們可以發(fā)現(xiàn)，每個(gè)節(jié)點(diǎn)都有一個(gè)隨機(jī)超時(shí)，因此節(jié)點(diǎn)被喚醒是隨機(jī)的，這樣大大降低了多個(gè)節(jié)點(diǎn)在同一時(shí)刻被喚醒成為 Candidate(候選人) 的概率， 但是小概率的事件不代表不發(fā)生，假如有 2個(gè)節(jié)點(diǎn)同時(shí)被喚醒，整個(gè) Leader選舉流程會(huì)怎樣？
這里我們假設(shè)節(jié)點(diǎn)A和B的隨機(jī)超時(shí)都是 100ms，這樣兩個(gè)節(jié)點(diǎn)就會(huì)同時(shí)被喚醒，成為 Candidate(候選人)，首先 節(jié)點(diǎn) A 和 B 會(huì)分別為自己投一票，然后向其他節(jié)點(diǎn)發(fā)起投票請(qǐng)求，如果節(jié)點(diǎn)A的投票請(qǐng)求先于節(jié)點(diǎn)B到達(dá)節(jié)點(diǎn)C， 最終，節(jié)點(diǎn)A 獲取 2張選票，節(jié)點(diǎn)B 獲取 1張選票，因此，節(jié)點(diǎn)A 獲取大多數(shù)選票成為 Leader(領(lǐng)導(dǎo)者)，節(jié)點(diǎn)B 的角色會(huì)從 Candidate 恢復(fù)成 Follower，整個(gè)交互如下圖：
Split Vote 平票問(wèn)題
上述描述的都是基于”奇數(shù)個(gè)節(jié)點(diǎn)的集群”，如果集群中的節(jié)點(diǎn)是偶數(shù)個(gè)，結(jié)果又是怎樣了，為了更好的說(shuō)明問(wèn)題，此處采用 4個(gè)節(jié)點(diǎn)的集群進(jìn)行說(shuō)明：
假設(shè)節(jié)點(diǎn) A 和 B 的隨機(jī)超時(shí)都是 100ms，這樣兩個(gè)節(jié)點(diǎn)就會(huì)同時(shí)被喚醒成為 Candidate(候選人)，首先節(jié)點(diǎn) A 和 B 會(huì)分別為自己投一票，然后再向其他節(jié)點(diǎn)請(qǐng)求投票，因?yàn)楣?jié)點(diǎn) A 和 B 已為自己投票， 根據(jù)同一任期內(nèi)最多投 1票的約束，節(jié)點(diǎn) A 和 B 會(huì)拒絕給對(duì)方投票， 最終 節(jié)點(diǎn) A 和 B 各自只能獲取 2票，這里出現(xiàn)了一個(gè)經(jīng)典的問(wèn)題：Split Vote(平分票數(shù))，該如何處理呢？
在這種”平分選票”未選出 Leader(領(lǐng)導(dǎo)者)的情況下，所有節(jié)點(diǎn)會(huì)全部恢復(fù)成 Follower(跟隨者) 狀態(tài)，重新設(shè)置隨機(jī)超時(shí)時(shí)間，準(zhǔn)備下一輪的選舉。不過(guò)需要提醒的是選舉的過(guò)程越長(zhǎng)越增加了集群不可用的時(shí)長(zhǎng)，因此要盡量避免 Split Vote問(wèn)題。整個(gè)交互如下圖：
腦裂問(wèn)題
上文我們一直在強(qiáng)調(diào)：一個(gè)集群中最多只能有一個(gè) Leader，假如在一個(gè)集群內(nèi)部發(fā)生網(wǎng)絡(luò)分區(qū)，形成了 2個(gè)小分區(qū)，會(huì)不會(huì)出現(xiàn) 2個(gè)Leader？如果有，該如何解決？
這里以[A,B,C,D,E] 5個(gè)節(jié)點(diǎn)組成的集群為例，假如原集群的Leader是節(jié)點(diǎn)A，如果內(nèi)部出現(xiàn)了網(wǎng)絡(luò)問(wèn)題，節(jié)點(diǎn)[A,B]為一個(gè)分區(qū)，節(jié)點(diǎn)[C,D,E]為一個(gè)分區(qū)，節(jié)點(diǎn)A為原來(lái)的 Leader，節(jié)點(diǎn)C獲得[C,D,E]分區(qū)的所有選票也成為 Leader，因此一個(gè)集群產(chǎn)生了 2個(gè)Leader，這就是我們常說(shuō)的”腦裂問(wèn)題”。
Raft是如何解決這種腦裂問(wèn)題？
答案：當(dāng)網(wǎng)絡(luò)恢復(fù)正常后，兩個(gè)分區(qū)的 Leader都會(huì)向其他節(jié)點(diǎn)發(fā)送心跳，當(dāng)節(jié)點(diǎn)A 收到 節(jié)點(diǎn)C的心跳之后，發(fā)現(xiàn)C的任期比自己大，因此節(jié)點(diǎn)A恢復(fù)成Follower，因此整個(gè)集群就恢復(fù)成只有一個(gè) Leader的狀態(tài)。
整體交互如下圖：
上文在對(duì)任期的描述時(shí)講到，任期通常包含 Leader選舉和 normal operation(工作期)兩部分，Leader選舉過(guò)程已分析完成，接下來(lái)分析 normal operation(工作期)。
4. 如何復(fù)制日志
4.1 什么是日志條目
在Raft算法中，每個(gè)節(jié)點(diǎn)維護(hù)著一份日志，其中包含了系統(tǒng)中所有狀態(tài)變更的記錄。每一次狀態(tài)變更被稱為一個(gè)日志條目。
- 索引值：日志條目對(duì)應(yīng)的整數(shù)索引值，它是用來(lái)標(biāo)識(shí)日志條目的，是一個(gè)連續(xù)單調(diào)遞增的整數(shù)；
- 任期編號(hào)：創(chuàng)建這條日志條目的 Leader(領(lǐng)導(dǎo)者)的任期編號(hào);
- 指令：客戶端請(qǐng)求指定的、狀態(tài)機(jī)需要執(zhí)行的指令；
4.2 日志復(fù)制過(guò)程
Raft算法通過(guò)日志的復(fù)制來(lái)實(shí)現(xiàn)共識(shí)。Leader接收客戶端的請(qǐng)求，并將請(qǐng)求轉(zhuǎn)換為日志條目，然后將這些日志條目復(fù)制到其他節(jié)點(diǎn)。當(dāng)大多數(shù)節(jié)點(diǎn)都成功地復(fù)制了這些日志條目后，Leader可以提交這些日志條目，并向客戶端返回成功響應(yīng)。
- Leader(領(lǐng)導(dǎo)者) 接收到客戶端請(qǐng)求后，創(chuàng)建一個(gè) new entry(新日志條目)，并 appends(追加)到本地日志中(Leader的日志條目為uncommitted狀態(tài))；
- Leader(領(lǐng)導(dǎo)者) 以同步的方式向所有 Follower(跟隨者) 發(fā)送 AppendEntries RPC 日志條目復(fù)制請(qǐng)求(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)者) 通過(guò)心跳或新的 AppendEntries RPC 將提交了某條日志條目的狀態(tài)同步給Follower(跟隨者)，F(xiàn)ollower(跟隨者)將日志條目狀態(tài)同步到本地狀態(tài)機(jī)中(Follower的日志條目為committed狀態(tài))；
- 如果 Follower(跟隨者)出現(xiàn)崩潰、運(yùn)行緩慢、網(wǎng)絡(luò)丟包，Leader(領(lǐng)導(dǎo)者)會(huì)不斷地重試 AppendEntries RPCs（即使已經(jīng)對(duì)客戶端作出了響應(yīng)）直到所有的 Follower(跟隨者)成功存儲(chǔ)了所有的日志條目；
通過(guò)上述日志的復(fù)制過(guò)程可以看出日志的提交過(guò)程有點(diǎn)類似兩階段提交(2PC)，不過(guò)與2PC的區(qū)別在于，Leader只需要 majority(大多數(shù))節(jié)點(diǎn)的回復(fù)即可，只要過(guò)半節(jié)點(diǎn)處于工作狀態(tài)則系統(tǒng)就是可用的。 然而，這種是一種比較理想的狀態(tài)，假如在復(fù)制日志的過(guò)程中，出現(xiàn)了進(jìn)程崩潰、服務(wù)器宕機(jī)等問(wèn)題，就可能導(dǎo)致日志不一致，Raft 會(huì)如何處理呢？
4.3 日志的一致性
在Raft算法中，所有節(jié)點(diǎn)的日志必須保持一致。這意味著，如果一個(gè)日志條目在某個(gè)節(jié)點(diǎn)被提交，那么這個(gè)日志條目也必須在所有節(jié)點(diǎn)上被提交。通過(guò)使用多數(shù)投票的方式選出Leader，并確保Leader復(fù)制的日志達(dá)到大多數(shù)節(jié)點(diǎn)，Raft算法保證了日志的一致性。
圖中包含了 1個(gè) Leader 和 1個(gè) Follower的所有日志條目，整個(gè)復(fù)制過(guò)程分以下幾個(gè)步驟(步驟1-4是一致性檢查機(jī)制)：
1.Leader(領(lǐng)導(dǎo)者) 當(dāng)前最大日志條目索引是 10，因此 Leader(領(lǐng)導(dǎo)者) 會(huì)通過(guò)日志復(fù)制 RPC 消息將 index=9 的日志發(fā)送給 Follower(跟隨者)，F(xiàn)ollower(跟隨者) 判斷自己沒(méi)有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ù)操作上述過(guò)程，直到 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)者) 通過(guò)日志復(fù)制 RPC消息，強(qiáng)制 Follower(跟隨者)復(fù)制并更新覆蓋 index=6之后的所有日志條目(不一致的日志條目)，達(dá)到 Follower 與 Leader的日志保持一致；
6.集群中多個(gè) Follower(跟隨者)，只需要重復(fù)上述過(guò)程，就能最終實(shí)現(xiàn)了集群各節(jié)點(diǎn)日志的一致。
5. 節(jié)點(diǎn)變更問(wèn)題
節(jié)點(diǎn)變更是分布式系統(tǒng)很常見(jiàn)的問(wèn)題，比如，服務(wù)器擴(kuò)容需要增加機(jī)器，服務(wù)器縮容需要減少機(jī)器，出現(xiàn)節(jié)點(diǎn)故障需要變更機(jī)器等等。 在Raft算法中，為了描述節(jié)點(diǎn)變更，作者使用 Configuration(配置) 這個(gè)重要的概念，可以把”配置”理解為集群中所有節(jié)點(diǎn)地址信息的集合。比如節(jié)點(diǎn) A、B、C 組成的集群，那么集群的配置就是[A, B, C]集合。
集群節(jié)點(diǎn)的變更可能會(huì)導(dǎo)致集群分裂，出現(xiàn) 2個(gè) Leader(領(lǐng)導(dǎo)者)，如下圖，集群[A,B,C] 增加節(jié)點(diǎn)D和E，如果發(fā)生網(wǎng)絡(luò)分區(qū)，形成 [A,B] 和 [C,D,E] 兩個(gè)小分區(qū)， 節(jié)點(diǎn)A 獲取原配置的大多數(shù)的選票成為 Leader(領(lǐng)導(dǎo)者)，節(jié)點(diǎn)E 獲取新配置的大多數(shù)選票成為 Leader(領(lǐng)導(dǎo)者)，出現(xiàn)了 2個(gè) Leader(領(lǐng)導(dǎo)者)，違背了Raft算法最多一個(gè) Leader(領(lǐng)導(dǎo)者)的原則。如下圖：
5.1 聯(lián)合共識(shí)
在Raft算法中，當(dāng)節(jié)點(diǎn)需要進(jìn)行變更時(shí)，比如加入新節(jié)點(diǎn)或移除現(xiàn)有節(jié)點(diǎn)，可以通過(guò)聯(lián)合共識(shí)來(lái)保證變更的一致性。新節(jié)點(diǎn)必須和大多數(shù)節(jié)點(diǎn)達(dá)成共識(shí)，才能成為集群的一部分。
joint consensus(聯(lián)合共識(shí))是指 集群從舊配置變更成新配置的過(guò)程中使用了一個(gè)過(guò)渡的中間配置，聯(lián)合共識(shí)配置是新舊配置的并集，此方法允許一次性向集群中插入多個(gè)節(jié)點(diǎn)而不會(huì)出現(xiàn)腦裂等 (safety) 問(wèn)題，并且整個(gè)集群在配置轉(zhuǎn)換的過(guò)程中依然能夠接收用戶請(qǐng)求，從而實(shí)現(xiàn)配置切換對(duì)集群調(diào)用方無(wú)感知， 因?yàn)樵诼?lián)合共識(shí)階段，集群會(huì)出現(xiàn)新舊兩種配置，為了更好的工作，聯(lián)合共識(shí)做了如下的約束：
- 約束1. 新舊配置的日志會(huì)復(fù)制給新、舊配置的所有節(jié)點(diǎn)；
- 約束2. 新、舊配置的任何節(jié)點(diǎn)都可能成為 Leader(領(lǐng)導(dǎo)者)；
- 約束3. 選舉和日志復(fù)制階段需要在新老配置上面都超多半數(shù)才能被提交生效；
下面摘取了Raft官方關(guān)于聯(lián)合共識(shí)階段配置變更的時(shí)間線描述圖：
其中，虛線代表已創(chuàng)建但是未提交的配置項(xiàng)，實(shí)線代表最新的已提交的配置項(xiàng)。
首先，Leader(領(lǐng)導(dǎo)者) 創(chuàng)建 Cold,new 日志條目，并復(fù)制到新舊配置中的大多數(shù)，此時(shí)所有的日志條目都需要被聯(lián)合共識(shí)。
然后，Leader(領(lǐng)導(dǎo)者) 創(chuàng)建 Cnew 日志條目，并復(fù)制到 Cnew(新配置)中的大多數(shù)。因此，舊配置和新配置不會(huì)存在可以同時(shí)做出決策的時(shí)間點(diǎn)。
鑒于此圖比較晦澀難懂，因此我們以一個(gè)實(shí)例來(lái)進(jìn)行講述，假設(shè)集群有A、B、C三個(gè)節(jié)點(diǎn)，需要往集群中添加 D、E兩個(gè)節(jié)點(diǎn)，看看聯(lián)合共識(shí)是如何工作的。
首先， Leader(領(lǐng)導(dǎo)者) 向所有 Follower發(fā)送一條配置變更日志 Cold,new[A,B,C,D,E]，告知集群要新增兩個(gè)節(jié)點(diǎn)[D,E]。根據(jù)約束1，日志會(huì)被復(fù)制到新舊配置的所有節(jié)點(diǎn)。如下圖：
其次，根據(jù)約束3，配置變更日志Cold,new[A,B,C,D,E] 在新舊配置中都需要大多數(shù)節(jié)點(diǎn)復(fù)制成功，才能被成功應(yīng)用。換句話說(shuō)，假設(shè)舊配置的大多數(shù)為[A,B]、新配置的大多數(shù)為[A,B,D]， 那么這些節(jié)點(diǎn)都需要復(fù)制成功，如下圖：
最后，Cold,new 被成功應(yīng)用后，Leader(領(lǐng)導(dǎo)者)再發(fā)送一條新的 Cnew RPC日志復(fù)制請(qǐng)求，通知集群Follower(跟隨者)可以使用新配置。Follower(跟隨者)收到日志復(fù)制RPC后，在 Raft一致性檢查機(jī)制保證下切換成新配置，Leader(領(lǐng)導(dǎo)者)因?yàn)橐呀?jīng)處于新配置狀態(tài)，所以不需要聯(lián)合共識(shí)，到此，舊配置就平穩(wěn)過(guò)渡到新配置，如下圖：
對(duì)于新的節(jié)點(diǎn)D、E，Raft 會(huì)通過(guò)日志一致性檢查來(lái)復(fù)制領(lǐng)導(dǎo)者的所有日志條目，從而保證它們同樣能夠保持日志完整性。
上文我們分析了往集群中新增2節(jié)點(diǎn)的流程，接下來(lái)分析上述流程為什么不會(huì)產(chǎn)生腦裂。我們依然假設(shè)集群產(chǎn)生了網(wǎng)絡(luò)分區(qū)，形成了[A,B] 和 [C,D,E] 兩個(gè)小分區(qū)：
1.假如 Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 未發(fā)送 Cold,new RPC變更日志請(qǐng)求，[A,B] 分區(qū)依然是舊配置，節(jié)點(diǎn)A 是領(lǐng)導(dǎo)者；而[C,D,E]分區(qū)，當(dāng)節(jié)點(diǎn)C 發(fā)起選舉時(shí)，因?yàn)椴恢拦?jié)點(diǎn)D、E 的存在，無(wú)法獲取到大多數(shù)節(jié)點(diǎn)的投票。因此兩個(gè)分區(qū)只有一個(gè) Leader(領(lǐng)導(dǎo)者) 節(jié)點(diǎn)A，符合預(yù)期。
2.假如 Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 已發(fā)送 Cold,new RPC變更日志請(qǐng)求，此時(shí)發(fā)生了網(wǎng)絡(luò)分區(qū)，會(huì)出現(xiàn)下面兩種情情況：
3.如果 Cold,new 沒(méi)有被大多數(shù)節(jié)點(diǎn)確認(rèn)，那么 Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 無(wú)法應(yīng)用該配置，[A,B] 依然是舊配置對(duì)外提供服務(wù)，[C,D,E]分區(qū)，C任然是舊配置，感知不到D,E的存在嗎，所以不可能成為 Leader，D或E任何一個(gè)節(jié)點(diǎn)獲取不到大多數(shù)選票也無(wú)法成為L(zhǎng)eader(領(lǐng)導(dǎo)者)，符合預(yù)期；
4.如果 Cold,new 已經(jīng)被大多數(shù)節(jié)點(diǎn)復(fù)制，那么 Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 會(huì)應(yīng)用該配，并向所有 Follower(跟隨者)發(fā)送 Cnew RPC復(fù)制日志請(qǐng)求，因?yàn)榫W(wǎng)絡(luò)分區(qū)導(dǎo)致 Cnew無(wú)法被聯(lián)合共識(shí)，領(lǐng)導(dǎo)者 A 后續(xù)不會(huì)提交任何日志（在一些實(shí)現(xiàn)中會(huì)自動(dòng)退位為跟隨者）；對(duì)于分區(qū) [C,D,E] 無(wú)法 Cnew RPC復(fù)制日志請(qǐng)求，C 任然是舊配置無(wú)法獲取到大多數(shù)選票，節(jié)點(diǎn)D，E無(wú)法獲取到大多數(shù)選票，該分區(qū)也無(wú)法選舉出 Leader(領(lǐng)導(dǎo)者)。符合預(yù)期。
5.假如 Cnew 階段產(chǎn)生了分區(qū)，因?yàn)?Cold,new 已經(jīng)生效，[A,B] 和 [C,D,E] 兩個(gè)小分區(qū)都拿到了新配置[A,B,C,D,E]，因此[A,B]分區(qū)無(wú)法獲取新配置的大多數(shù)選票，無(wú)法選出新 Leader(領(lǐng)導(dǎo)者)，也就不可能發(fā)生腦裂，符合預(yù)期。
盡管 joint consensus(聯(lián)合共識(shí))允許一次性向集群中插入多個(gè)節(jié)點(diǎn)且不會(huì)出現(xiàn)腦裂等問(wèn)題，但由于該方法理解和實(shí)現(xiàn)都比較難，所以 Raft作者提出了一種改進(jìn)的方法：single-server changes(單服務(wù)器變更)。
5.2 單服務(wù)器變更
單服務(wù)器變更，就是每次只能有一個(gè)節(jié)點(diǎn)服務(wù)器成員變更。如果需要變更多個(gè)服務(wù)器節(jié)點(diǎn)，則需要執(zhí)行多次單服務(wù)器變更。 我們還是以圖文的方式來(lái)進(jìn)行解釋：
假如 集群有節(jié)點(diǎn)A、節(jié)點(diǎn)B、節(jié)點(diǎn)C，現(xiàn)在需要增加 2個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)D，節(jié)點(diǎn)E)，增加的方式是先增加節(jié)點(diǎn)D
- 第一步，Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 向新節(jié)點(diǎn)D 同步數(shù)據(jù)；
- 第二步，Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 將新配置[A, B, C, D]作為一個(gè)日志條目，復(fù)制到新配置中所有節(jié)點(diǎn)(節(jié)點(diǎn) A、B、C、D)上，然后將新配置的日志條目應(yīng)用（Apply）到本地狀態(tài)機(jī)，完成單節(jié)點(diǎn)變更。
同理再增加節(jié)點(diǎn)E：
- 第一步，Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 向新節(jié)點(diǎn)E 同步數(shù)據(jù)；
- 第二步，Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 將新配置[A, B, C, D, E]作為一個(gè)日志條目，復(fù)制到新配置中所有節(jié)點(diǎn)(節(jié)點(diǎn) A、B、C、D、E)上，然后將新配置的日志條目應(yīng)用（Apply）到本地狀態(tài)機(jī)，完成單節(jié)點(diǎn)變更。
刪除節(jié)點(diǎn)E:
- 第一步，先刪除 節(jié)點(diǎn) E；
- 第二步，Leader(領(lǐng)導(dǎo)者)節(jié)點(diǎn)A 將新配置[A, B, C, D]作為一個(gè)日志條目，復(fù)制到新配置中所有節(jié)點(diǎn)(節(jié)點(diǎn) A、B、C、D)上，然后將新配置的日志條目應(yīng)用(Apply)到本地狀態(tài)機(jī)，完成單節(jié)點(diǎn)變更。
通過(guò)上述對(duì)單服務(wù)器的增加和刪除可以看出，每次單服務(wù)器節(jié)點(diǎn)的增減，可以保證新舊集群至少存在一個(gè)交集服務(wù)器節(jié)點(diǎn)，這樣就不會(huì)在新舊配置同時(shí)存在 2個(gè)“大多數(shù)”，從而保證集群只能有一個(gè) Leader(領(lǐng)導(dǎo)者)。
特別注意
在作者Diego Ongaro(迭戈·安加羅) bug in single-server membership changes 的文章中特別說(shuō)明了，單服務(wù)器變更的方式在串行化的方式下可以保證一個(gè)集群 只能有一個(gè) Leader，但是在并發(fā)的、競(jìng)爭(zhēng)可能導(dǎo)致多個(gè) Leader，從而導(dǎo)致安全違規(guī)（腦裂）。
6. Safety
前面章節(jié)描述了 Raft 如何做 Leader Election(Leader選舉) 和 Log Replication(日志復(fù)制)。然而，到目前為止所討論的機(jī)制并不能充分地保證每一個(gè)狀態(tài)機(jī)會(huì)按相同的順序執(zhí)行相同的指令。比如說(shuō)，一個(gè) Follower(跟隨者) 可能會(huì)進(jìn)入不可用狀態(tài)，在此期間，Leader 可能提交了若干的日志條目，然后這個(gè) Follower 可能被選舉為新Leader 并且用新的日志條目去覆蓋這些日志條目。這樣就會(huì)造成不同的狀態(tài)機(jī)執(zhí)行不同的指令的情況。 對(duì)于上述問(wèn)題，Raft 如何保證安全？
6.1 選舉約束
- 同一任期內(nèi)每個(gè)節(jié)點(diǎn)最多只能投票 1次，并且按照 first-come-first-served(先來(lái)先服務(wù)) 的原則
- 日志條目的傳送只能從 Leader 到 Follower，Leader 從來(lái)不會(huì)覆蓋本地日志中已有的日志
- Candidate(候選人) 只有獲得集群中大多數(shù)選票才能成為 Leader(領(lǐng)導(dǎo)者)
- 日志完整性高的 Follower(跟隨者)拒絕投票給日志完整性低的 Candidate(候選人)，這里的日志指的是已復(fù)制未commit狀態(tài)。也就是說(shuō)，即便 Candidate(候選人)的 term 大于 Follower(跟隨者)的 term，假如 Candidate(候選人) 向 Follower(跟隨者)發(fā)送了一條投票RPC，如果當(dāng)前消息中的term 小于 Follower(跟隨者)最后一條消息的 term，則 Follower(跟隨者) 拒絕給 Candidate(候選人)投票
6.2 Leader只能提交任期內(nèi)的日志條目
首先我們以圖文的方式來(lái)展示一個(gè)已經(jīng)被存儲(chǔ)到大多數(shù)節(jié)點(diǎn)的日志條目，仍然有可能會(huì)被新 Leader覆蓋的場(chǎng)景：
- 在圖A中，S1是 Leader，將index=2的日志復(fù)制給了S2，此時(shí)S1的數(shù)據(jù)還沒(méi)有復(fù)制大多數(shù)節(jié)點(diǎn)
- 在圖B中，S1宕機(jī)了，S5 從 [S2,S3,S4,S5] 獲得大多數(shù)選票成為 Leader，任期編號(hào)為3，然后收到客戶端的指令，將日志存放在 index=2 位置上
- 在圖C中，S5宕機(jī)了，S1重啟，假如S1當(dāng)選為 Leader，然后S1繼續(xù)將它在任期2的日志條目復(fù)制給[S2,S3,S4]成功，但是還未被提交
- 情況1：在圖D中，假設(shè)S1在提交日志之前宕機(jī)，S5重啟，因?yàn)镾5最后日志條目上的任期為3，大于[S2,S3,S4]的任期編號(hào)2，所以S5可以得到[S2,S3,S4]大多數(shù)選票成為 Leader，然后 S5繼續(xù)將它在任期3的日志條目復(fù)制到大多數(shù)節(jié)點(diǎn)[S2,s3,S4]，因此覆蓋了S1復(fù)制給[S2,S3]中 index=2處的日志
- 情況2：在圖E中，S1在宕機(jī)之前把任期3的日志復(fù)制到大多數(shù)節(jié)點(diǎn)的index=3處，那么 S5就不可能成為 Leader，這種情況下，之前所有的日志被提交了
為了解決上圖中日志被覆蓋的問(wèn)題，Raft 規(guī)定 Leader只能提交任期內(nèi)的日志條目。
7. 實(shí)際使用
Raft算法已經(jīng)在許多分布式系統(tǒng)中得到了廣泛的應(yīng)用，其中包括分布式數(shù)據(jù)庫(kù)、分布式存儲(chǔ)系統(tǒng)、分布式文件系統(tǒng)等。以下是一些實(shí)際應(yīng)用場(chǎng)景：
- 分布式數(shù)據(jù)庫(kù)：在數(shù)據(jù)庫(kù)集群中，Raft算法可以用于實(shí)現(xiàn)數(shù)據(jù)的復(fù)制和一致性，確保所有節(jié)點(diǎn)的數(shù)據(jù)保持一致。
- 分布式存儲(chǔ)系統(tǒng)：在分布式存儲(chǔ)系統(tǒng)中，Raft算法可以用于實(shí)現(xiàn)數(shù)據(jù)的復(fù)制和數(shù)據(jù)一致性，確保數(shù)據(jù)的可靠性和高可用性。
- 分布式文件系統(tǒng)：在分布式文件系統(tǒng)中，Raft算法可以用于實(shí)現(xiàn)元數(shù)據(jù)的復(fù)制和一致性，確保文件系統(tǒng)的正確運(yùn)行。
- 分布式計(jì)算平臺(tái)：在分布式計(jì)算平臺(tái)中，Raft算法可以用于協(xié)調(diào)不同的計(jì)算節(jié)點(diǎn)，確保任務(wù)的分發(fā)和執(zhí)行的一致性。
- 分布式消息隊(duì)列：在分布式消息隊(duì)列中，Raft算法可以用于實(shí)現(xiàn)消息的復(fù)制和分發(fā)，確保消息隊(duì)列的可靠性和高可用性。
8. 總結(jié)
Raft算法是一種簡(jiǎn)潔而高效的分布式一致性算法，通過(guò)引入Leader選舉和日志復(fù)制的機(jī)制，確保了分布式系統(tǒng)的共識(shí)和一致性。它具有易于理解和實(shí)現(xiàn)的優(yōu)點(diǎn)，被廣泛應(yīng)用于各種分布式系統(tǒng)中。
Raft算法的核心思想是將分布式系統(tǒng)的復(fù)雜問(wèn)題簡(jiǎn)化為幾個(gè)簡(jiǎn)單的步驟，通過(guò)選舉Leader和復(fù)制日志的方式來(lái)實(shí)現(xiàn)共識(shí)。這種簡(jiǎn)單而有效的設(shè)計(jì)理念，使得Raft算法成為了分布式系統(tǒng)中一種受歡迎的共識(shí)算法。
然而，值得注意的是，Raft算法并不是解決分布式系統(tǒng)共識(shí)問(wèn)題的唯一方案。在實(shí)際應(yīng)用中，根據(jù)具體的場(chǎng)景和需求，還可以考慮其他的一致性算法，如Paxos算法等。
