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

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

一、Raft是什么？

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

二、三種角色

在 Raft 算法 中有 Leader(領導者)，Candidate(候選人)，Follower(跟隨者) 三種角色，也可以說成三種身份或者狀態，關于它們的說明如下：

Leader(領導者)：

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

Candidate(候選人)：

• 主動發起選舉投票；
• 重置選舉超時時間；
• 獲取大多數 Follower(跟隨者)的投票后成為 Leader(領導者)；

Follower(跟隨者)：

• 響應 Leader(領導者)的 AppendEntries RPC(空消息) 心跳請求；
• 響應 Candidate(候選人)的 RequestVote RPC 投票請求；
• 響應 Leader(領導者)的 AppendEntries RPC 日志復制請求；
• 切換成 Candidate(候選人)角色，為自己發起選舉投票；

三者的關系如下圖：

三、如何選舉 Leader？

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

1. 任期

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

2. 隨機超時

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

• Follower(跟隨者)等待 Leader(領導者)心跳信息超時的時間間隔是隨機的；
• Candidate(候選人)等待選舉超時的時間間隔是隨機的，也就是在一個隨機時間間隔內，Candidate(候選人)沒有贏得 major(大多數)選票，選舉就無效，Candidate(候選人)需要發起新一輪的選舉；

3. 通信方式

Raft 算法中節點之間采用 RPC 進行通信，這里包含三種類型的 RPC：

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

4. 選舉核心流程 

Leader 選舉的核心流程圖：

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

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

5. 選舉詳解初始狀態

(1) 初始狀態

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

(2) 投票請求

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

(3) 投票響應

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

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

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

(4) 投票結束

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

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

假如 Leader選舉過程中出現異常，比如：集群中有 2個或者多個節點同時結束倒計時發起投票，整個過程會怎樣？

(5) 多個 Candidate 問題

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

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

(6) Split Vote 平票問題

上述描述的都是基于"奇數個節點的集群"，如果集群中的節點是偶數個，結果又是怎樣了，為了更好地說明問題，此處采用 4 個節點的集群進行說明：

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

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

(7) 腦裂問題

上文我們一直在強調：一個集群中最多只能有一個 Leader，假如在一個集群內部發生網絡分區，形成了 2 個小分區，會不會出現 2 個 Leader？如果有，該如何解決？

這里以[A,B,C,D,E] 5 個節點組成的集群為例，集群的 Leader(領導者)是節點A。假如集群內部出現了網絡分區，節點[A,B]成為一個分區，節點[C,D,E]成為另一個分區，節點A 為原集群 Leader，節點C 獲得[C,D,E]分區的所有選票，即原集群[A,B,C,D,E]的大對數選票，成為 Leader，因此一個集群產生了 2 個 Leader，這就是我們常說的"腦裂問題"。

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

答案：當網絡恢復正常后，兩個分區的 Leader 都會向其他節點發送心跳，當節點 A 收到 節點 C 的心跳之后，發現節點C 的任期編號比自己大，因此節點A 恢 復成 Follower，因此整個集群就恢復成只有一個 Leader 的狀態。

整體交互如下圖：

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

四、如何復制日志？

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

1. 日志條目

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

• 索引值：日志條目對應的整數索引值，它是用來標識日志條目的，是一個連續單調遞增的整數；
• 任期編號：創建這條日志條目的 Leader(領導者)的任期編號;
• 指令：客戶端請求指定的、狀態機需要執行的指令；

2. 日志復制過程

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

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

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

3. 日志一致性

Raft算法是Strong leader(強領導)形式，以領導者日志為準來實現日志的一致，具體包含 2個步驟：

• Leader(領導者) 通過日志復制 RPC 的一致性檢查，找到 Follower(跟隨者)節點上，與自己具有相同日志條目的最大 index 索引值；
• Leader(領導者) 強制 Follower(跟隨者) 更新覆蓋的不一致日志條目，實現日志的一致；

怎么理解呢？這里以一個實例來進行講解，如下圖：

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

• Leader(領導者) 當前最大日志條目索引是 10，因此 Leader(領導者) 會通過日志復制 RPC 消息將 index=9 的日志發送給 Follower(跟隨者)，Follower(跟隨者) 判斷自己沒有 index=9 的日志，因此拒絕更新日志并響應 Leader 失敗信息。
• Leader(領導者) 收到 Follower(跟隨者) 的失敗響應后，執行 index-1，將 index=8 的日志發送給 Follower(跟隨者)，Follower(跟隨者) 判斷自己 index=8 日志條目信息為 term=4,x->7，和 Leader(領導則)日志條目不相同 ，因此再次拒絕更新，響應 Leader 失敗信息。
• Leader(領導者) 收到 Follower 的失敗響應后，重復操作上述過程，直到 index=6;
• Leader(領導者) 將 index=6 的日志發送給 Follower(跟隨者)，Follower 判斷自己 index=6 日志條目中的 term 和 command 和 Leader 相同，響應日志復制成功。因此，Leader(領導者)就知道在 index=6「term=3,y->1」日志條目位置，Follower(跟隨者)的日志條目與自己相同。
• Leader(領導者) 通過日志復制 RPC 消息，強制 Follower(跟隨者)復制并更新覆蓋 index=6 之后的所有日志條目(不一致的日志條目)，達到 Follower 與 Leader 的日志保持一致；
• 集群中多個 Follower(跟隨者)，只需要重復上述過程，就能最終實現了集群各節點日志的一致。

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

答案：因為相同的index索引，可能來自不同的 term任期，所以 Leader(領導者)需要從最大的index 往前一個個比較相同 index 的 Follower的日志條目，直到找到第一「term和command」相同的日志條目，然后將后面的日志全部覆蓋更新。

五、節點變更問題   

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

集群節點的變更可能會導致集群分裂，出現 2 個 Leader(領導者)，如下圖，集群[A,B,C] 增加節點 D 和 E，如果發生網絡分區，形成 [A,B] 和 [C,D,E] 兩個小分區，節點 A 獲取原配置的大多數的選票成為 Leader(領導者)，節點 E 獲取新配置的大多數選票成為 Leader(領導者)，出現了 2 個 Leader(領導者)，違背了 Raft 算法最多一個 Leader(領導者)的原則。如下圖：

那么，Raft 是如何在成員變更時保持集群的穩定性并且不出現 2 個 Leader(領導者)？

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

1. 聯合共識

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

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

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

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

首先，Leader(領導者) 創建 Cold,new 日志條目，并復制到新舊配置中的大多數，此時所有的日志條目都需要被聯合共識。

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

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

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

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

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

對于新的節點 D、E，Raft 會通過日志一致性檢查來復制領導者的所有日志條目，從而保證它們同樣能夠保持日志完整性。

上文我們分析了集群中新增 2個節點的全流程，為什么整個流程不會產生腦裂？我們依然假設集群產生了網絡分區，形成了[A,B] 和 [C,D,E] 兩個小分區：

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

(2) 假如 Leader(領導者)節點A 已發送 Cold,new RPC 變更日志請求，此時發生了網絡分區，會出現下面兩種情情況：

• 如果 Cold,new 沒有被大多數節點確認，那么 Leader(領導者)節點 A 無法應用該配置，[A,B] 依然是舊配置對外提供服務，[C,D,E]分區，C 任然是舊配置，感知不到 D,E 的存在嗎，所以不可能成為 Leader，D 或 E 任何一個節點獲取不到大多數選票也無法成為 Leader(領導者)，符合預期；
• 如果 Cold,new 已經被大多數節點復制，那么 Leader(領導者)節點 A 會應用該配，并向所有 Follower(跟隨者)發送 Cnew RPC 復制日志請求，因為網絡分區導致 Cnew 無法被聯合共識，領導者 A 后續不會提交任何日志（在一些實現中會自動退位為跟隨者）；對于分區 [C,D,E] 無法 Cnew RPC 復制日志請求，C 任然是舊配置無法獲取到大多數選票，節點 D，E 無法獲取到大多數選票，該分區也無法選舉出 Leader(領導者)。符合預期。

假如 Cnew 階段產生了分區，因為 Cold,new 已經生效，[A,B] 和 [C,D,E] 兩個小分區都拿到了新配置[A,B,C,D,E]，因此[A,B]分區無法獲取新配置的大多數選票，無法選出新 Leader(領導者)，也就不可能發生腦裂，符合預期。

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

2. 單服務器變更

單服務器變更，就是每次只能有一個節點服務器成員變更。如果需要變更多個服務器節點，則需要執行多次單服務器變更。我們還是以圖文的方式來進行解釋：

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

• 第一步，Leader(領導者)節點 A 向新節點 D 同步數據；
• 第二步，Leader(領導者)節點 A 將新配置[A, B, C, D]作為一個日志條目，復制到新配置中所有節點(節點 A、B、C、D)上，然后將新配置的日志條目應用（Apply）到本地狀態機，完成單節點變更。

同理再增加節點 E：

• 第一步，Leader(領導者)節點 A 向新節點 E 同步數據；
• 第二步，Leader(領導者)節點 A 將新配置[A, B, C, D, E]作為一個日志條目，復制到新配置中所有節點(節點 A、B、C、D、E)上，然后將新配置的日志條目應用（Apply）到本地狀態機，完成單節點變更。

刪除節點 E:

• 第一步，先刪除 節點 E；
• 第二步，Leader(領導者)節點 A 將新配置[A, B, C, D]作為一個日志條目，復制到新配置中所有節點(節點 A、B、C、D)上，然后將新配置的日志條目應用(Apply)到本地狀態機，完成單節點變更。

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

特別注意：

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

六、Safety  

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

1. 選舉約束

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

2. 只能提交任期內的日志

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

在圖 A 中，S1 是 Leader，將 index=2 的日志復制給了 S2，此時 S1 的數據還沒有復制大多數節點

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

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

七、實際使用 

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

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

八、總結  

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

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