前兩天，面試了一個在大廠工作了 8年的 Java技術(shù)專家，簡歷上寫著“精通分布式算法，包括 Raft，Paxos”，于是，先簡單地問了下：能聊聊 Raft算法中有哪幾種角色？結(jié)果，支支吾吾硬是沒有回答出來。

所以，在簡歷上慎用精通二字，除非真的是這個領(lǐng)域的專家，借此機(jī)會，一起來深入研究下 Raft算法。

一、Raft是什么？

Raft 是英文"Reliable、Replicated、Redundant、And Fault-Tolerant"（可靠、可復(fù)制、可冗余、可容錯）的首字母縮寫，它起源于 2013 年 斯坦福大學(xué) Diego Ongaro(迭戈·安加羅) 和 John Ousterhout(約翰·奧斯特豪特) 的博士論文《In Search of an Understandable Consensus Algorithm》，是一種用于替代 Paxos 的共識算法，相比于 Paxos，Raft 的目標(biāo)是更容易理解，同時安全性更高，并能提供一些額外的特性。

二、三種角色

在 Raft 算法 中有 Leader(領(lǐng)導(dǎo)者)，Candidate(候選人)，F(xiàn)ollower(跟隨者) 三種角色，也可以說成三種身份或者狀態(tài)，關(guān)于它們的說明如下：

Leader(領(lǐng)導(dǎo)者)：

• 負(fù)責(zé)處理所有外部的請求，如果不是 Leader 機(jī)器收到請求時，請求會被轉(zhuǎn)到 Leader 機(jī)器；
• 負(fù)責(zé)向 Follower(跟隨者) 同步心跳信息；
• 負(fù)責(zé)向其他節(jié)點(diǎn)同步日志復(fù)制 AppendEntries RPC 信息；
• 同一任期，最多只能有一個 Leader；

Candidate(候選人)：

• 主動發(fā)起選舉投票；
• 重置選舉超時時間；
• 獲取大多數(shù) Follower(跟隨者)的投票后成為 Leader(領(lǐng)導(dǎo)者)；

Follower(跟隨者)：

• 響應(yīng) Leader(領(lǐng)導(dǎo)者)的 AppendEntries RPC(空消息) 心跳請求；
• 響應(yīng) Candidate(候選人)的 RequestVote RPC 投票請求；
• 響應(yīng) Leader(領(lǐng)導(dǎo)者)的 AppendEntries RPC 日志復(fù)制請求；
• 切換成 Candidate(候選人)角色，為自己發(fā)起選舉投票；

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

三、如何選舉 Leader？

在講解 Leader 選舉之前，我們先了解 任期、隨機(jī)超時、通信方式 等幾個基本概念，幫助后面更好地去理解 Leader 選舉機(jī)制。

1. 任期

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

2. 隨機(jī)超時

在 Raft算法中，隨機(jī)超時是指，每個節(jié)點(diǎn)都隨機(jī)設(shè)置一個倒計(jì)時，一旦倒計(jì)時結(jié)束，節(jié)點(diǎn)就被喚醒，從而切換成 Candidate(候選人) 角色，發(fā)起選舉。Raft 算法就是巧妙地利用了隨機(jī)超時的方法，保證在大多數(shù)情況下只有一個節(jié)點(diǎn)發(fā)起選舉，避免多 Candidate 選舉帶來的性能問題，隨機(jī)超時包含 2 層含義：

• Follower(跟隨者)等待 Leader(領(lǐng)導(dǎo)者)心跳信息超時的時間間隔是隨機(jī)的；
• Candidate(候選人)等待選舉超時的時間間隔是隨機(jī)的，也就是在一個隨機(jī)時間間隔內(nèi)，Candidate(候選人)沒有贏得 major(大多數(shù))選票，選舉就無效，Candidate(候選人)需要發(fā)起新一輪的選舉；

3. 通信方式

Raft 算法中節(jié)點(diǎn)之間采用 RPC 進(jìn)行通信，這里包含三種類型的 RPC：

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

4. 選舉核心流程 

Leader 選舉的核心流程圖：

Leader 選舉的核心流程為：Candidate 發(fā)起選舉，任期編號+1，向其他節(jié)點(diǎn)發(fā)起 RequestVote RPC 投票請求，若獲得大多數(shù)投票后成為 Leader；若收到 Leader 的心跳包，則 Candidate 恢復(fù)成 Follower 角色。

有了上面幾個基本概念的鋪墊，為了更情景化地說明 Leader 的選舉過程，本文將以節(jié)點(diǎn) A、節(jié)點(diǎn) B、節(jié)點(diǎn) C 組成的集群來進(jìn)行演示。

5. 選舉詳解初始狀態(tài)

(1) 初始狀態(tài)

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

(2) 投票請求

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

(3) 投票響應(yīng)

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

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

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

(4) 投票結(jié)束

Candidate(候選人)節(jié)點(diǎn) A 在任期編號為 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ī)超時，防止節(jié)點(diǎn) B 和 C 重新發(fā)起投票，整體交互如下圖：

到此，一個沒有出現(xiàn)異常情況的 Leader 選舉過程描述結(jié)束，該流程是不是和我們讀書時代的選班長有異曲同工之妙？

假如 Leader選舉過程中出現(xiàn)異常，比如：集群中有 2個或者多個節(jié)點(diǎn)同時結(jié)束倒計(jì)時發(fā)起投票，整個過程會怎樣？

(5) 多個 Candidate 問題

在上述 Leader選舉的描述中我們可以發(fā)現(xiàn)，每個節(jié)點(diǎn)都有一個隨機(jī)超時機(jī)制，因此節(jié)點(diǎn)被喚醒是隨機(jī)的，這樣大大降低了多個節(jié)點(diǎn)在同一時刻被喚醒成為 Candidate(候選人) 的概率，但是小概率的事件不代表不發(fā)生，這里我們以節(jié)點(diǎn) A 和 B同時發(fā)起投票為例：

假設(shè)節(jié)點(diǎn) A 和 B 的隨機(jī)超時都是 100ms，這樣兩個節(jié)點(diǎn)就會同時被喚醒，成為 Candidate(候選人)，首先，節(jié)點(diǎn) A 和 B 會分別為自己投上一票，然后再向其他節(jié)點(diǎn)發(fā)起投票請求，如果節(jié)點(diǎn) A 的投票請求先于節(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 的角色會從 Candidate 恢復(fù)成 Follower，整個交互如下圖：

(6) Split Vote 平票問題

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

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

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

(7) 腦裂問題

上文我們一直在強(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é)點(diǎn)組成的集群為例，集群的 Leader(領(lǐng)導(dǎo)者)是節(jié)點(diǎn)A。假如集群內(nèi)部出現(xiàn)了網(wǎng)絡(luò)分區(qū)，節(jié)點(diǎn)[A,B]成為一個分區(qū)，節(jié)點(diǎn)[C,D,E]成為另一個分區(qū)，節(jié)點(diǎn)A 為原集群 Leader，節(jié)點(diǎn)C 獲得[C,D,E]分區(qū)的所有選票，即原集群[A,B,C,D,E]的大對數(shù)選票，成為 Leader，因此一個集群產(chǎn)生了 2 個 Leader，這就是我們常說的"腦裂問題"。

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

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

整體交互如下圖：

上文在描述 Leader的選舉過程中提到 3種 RPCs，那么它們是什么呢？接下來我們就來分析 Raft的另外一個重要知識點(diǎn)：日志復(fù)制。

四、如何復(fù)制日志？

在講解 log replication(復(fù)制日志)之前，我們需要先看看 log entry(日志條目):

1. 日志條目

日志條目實(shí)際上是一種數(shù)據(jù)格式，主要包含索引值(Log index)、任期編號(Term)、指令(Command) 三部分，如下圖(摘自官方)：

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

2. 日志復(fù)制過程

Leader(領(lǐng)導(dǎo)者)一旦被選舉出來，就要為客戶端的請求提供服務(wù)，每一個客戶端請求都包含一條將被復(fù)制狀態(tài)機(jī)執(zhí)行的命令，而這些指令就是通過日志復(fù)制的方式得到執(zhí)行。為了更好地理解復(fù)制過程，這里給出了一張日志復(fù)制過程的簡要圖：

• 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)崩潰、運(yùn)行緩慢、網(wǎng)絡(luò)丟包，Leader(領(lǐng)導(dǎo)者)會不斷地重試 AppendEntries RPCs（即使已經(jīng)對客戶端作出了響應(yīng)）直到所有的 Follower(跟隨者)成功存儲了所有的日志條目；

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

3. 日志一致性

Raft算法是Strong leader(強(qiáng)領(lǐng)導(dǎo))形式，以領(lǐng)導(dǎo)者日志為準(zhǔn)來實(shí)現(xiàn)日志的一致，具體包含 2個步驟：

• Leader(領(lǐng)導(dǎo)者) 通過日志復(fù)制 RPC 的一致性檢查，找到 Follower(跟隨者)節(jié)點(diǎn)上，與自己具有相同日志條目的最大 index 索引值；
• Leader(領(lǐng)導(dǎo)者) 強(qiáng)制 Follower(跟隨者) 更新覆蓋的不一致日志條目，實(shí)現(xiàn)日志的一致；

怎么理解呢？這里以一個實(shí)例來進(jìn)行講解，如下圖：

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

• 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 失敗信息。
• 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 失敗信息。
• Leader(領(lǐng)導(dǎo)者) 收到 Follower 的失敗響應(yīng)后，重復(fù)操作上述過程，直到 index=6;
• 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(跟隨者)的日志條目與自己相同。
• Leader(領(lǐng)導(dǎo)者) 通過日志復(fù)制 RPC 消息，強(qiáng)制 Follower(跟隨者)復(fù)制并更新覆蓋 index=6 之后的所有日志條目(不一致的日志條目)，達(dá)到 Follower 與 Leader 的日志保持一致；
• 集群中多個 Follower(跟隨者)，只需要重復(fù)上述過程，就能最終實(shí)現(xiàn)了集群各節(jié)點(diǎn)日志的一致。

問題：為什么 Follower(跟隨者) 不直接告訴 Leader(領(lǐng)導(dǎo)者) 從哪個 index 開始日志缺頁了，而需要 Leader(領(lǐng)導(dǎo)者)一個一個去嘗試，重復(fù) RPC 操作，消耗網(wǎng)絡(luò)資源？

答案：因?yàn)橄嗤膇ndex索引，可能來自不同的 term任期，所以 Leader(領(lǐng)導(dǎo)者)需要從最大的index 往前一個個比較相同 index 的 Follower的日志條目，直到找到第一「term和command」相同的日志條目，然后將后面的日志全部覆蓋更新。

五、節(jié)點(diǎn)變更問題   

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

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

那么，Raft 是如何在成員變更時保持集群的穩(wěn)定性并且不出現(xiàn) 2 個 Leader(領(lǐng)導(dǎo)者)？

最暴力的方式就是先將舊配置集群關(guān)閉再開啟新配置集群，但是這種方式有個致命的問題就是會出現(xiàn)一段時間內(nèi)集群不可用，而 Raft 算法為了安全考慮，采用了 Joint Consensus(聯(lián)合共識) 和 single-server changes(單服務(wù)器變更) 兩種方式。

1. 聯(lián)合共識

joint consensus(聯(lián)合共識)是指 集群從舊配置變更成新配置的過程中使用了一個過渡的中間配置，聯(lián)合共識配置是新舊配置的并集，此方法允許一次性向集群中插入多個節(jié)點(diǎn)而不會出現(xiàn)腦裂等 (safety) 問題，并且整個集群在配置轉(zhuǎn)換的過程中依然能夠接收用戶請求，從而實(shí)現(xiàn)配置切換對集群調(diào)用方無感知，因?yàn)樵诼?lián)合共識階段，集群會出現(xiàn)新舊兩種配置，為了更好的工作，聯(lián)合共識做了如下的約束：

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

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

其中，虛線代表已創(chuàng)建但是未提交的配置項(xiàng)，實(shí)線代表最新的已提交的配置項(xià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ù)。因此，舊配置和新配置不會存在可以同時做出決策的時間點(diǎn)。

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

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

其次，根據(jù)約束 3，配置變更日志 Cold,new[A,B,C,D,E] 在新舊配置中都需要大多數(shù)節(jié)點(diǎn)復(fù)制成功，才能被成功應(yīng)用。換句話說，假設(shè)舊配置[A,B,C]的大多數(shù)為[A,B]、新配置[A,B,C,D,E]的大多數(shù)為[A,B,D]， 那么這些節(jié)點(diǎn)都需要復(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)者)因?yàn)橐呀?jīng)處于新配置狀態(tài)，所以不需要聯(lián)合共識，到此，舊配置就平穩(wěn)過渡到新配置，如下圖：

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

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

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

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

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

假如 Cnew 階段產(chǎn)生了分區(qū)，因?yàn)?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é)點(diǎn)且不會出現(xiàn)腦裂等問題，但由于該方法理解和實(shí)現(xiàn)都比較難，所以 Raft 作者提出了一種改進(jìn)的方法：single-server changes(單服務(wù)器變更)。

2. 單服務(wù)器變更

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

假如 集群有節(jié)點(diǎn) A、節(jié)點(diǎn) B、節(jié)點(diǎn) C，現(xiàn)在需要增加 2 個節(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]作為一個日志條目，復(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]作為一個日志條目，復(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]作為一個日志條目，復(fù)制到新配置中所有節(jié)點(diǎn)(節(jié)點(diǎn) A、B、C、D)上，然后將新配置的日志條目應(yīng)用(Apply)到本地狀態(tài)機(jī)，完成單節(jié)點(diǎn)變更。

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

特別注意：

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

六、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 如何保證安全？

1. 選舉約束

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

2. 只能提交任期內(nèi)的日志

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

在圖 A 中，S1 是 Leader，將 index=2 的日志復(fù)制給了 S2，此時 S1 的數(shù)據(jù)還沒有復(fù)制大多數(shù)節(jié)點(diǎn)

• 在圖 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 重啟，因?yàn)?S5 最后日志條目上的任期為 3，大于[S2,S3,S4]的任期編號 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，這種情況下，之前所有的日志被提交了

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

七、實(shí)際使用 

Raft是現(xiàn)在很多分布式框架常用的一種算法，掌握這個算法，可以得心應(yīng)手地處理絕大部分場景的容錯和一致性需求，比如分布式配置系統(tǒng)、分布式 NoSQL 存儲等等，輕松突破系統(tǒng)的單機(jī)限制。下面列舉了幾款使用 Raft算法的經(jīng)典框架：

• Etcd、Consul、CockroachDB 使用了 Raft 算法
• Redis 哨兵 Leader 選舉 使用了 Raft
• 百度開源的 RPC 框架 Braft 是基于 Raft 協(xié)議

八、總結(jié)  

本文主要從 Leader 選舉，日志復(fù)制，集群成員變更 講述了 Raft 的工作機(jī)制；

• Raft 算法要求每個任期最多只能有一個 Leader；
• Raft 算法是以 Leader 的日志為準(zhǔn)來進(jìn)行日志復(fù)制，而且日志必須是連續(xù)的；
• Raft 算法可以通過 Joint Consensus(聯(lián)合共識) 和 single-server changes(單服務(wù)器變更) 兩種方式，保證集群成員變更時最多只有一個 Leader；
• Raft 算法能實(shí)現(xiàn)強(qiáng)一致性，也就是線性一致性（Linearizability），但需要客戶端協(xié)議的配合；