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