分布式系統必須知道的一個共識算法：Raft

作者：悟空聊架構 2023-04-05 10:00:00

人工智能新聞

本篇通過動圖的方式來講解 Raft 算法如何選舉領導者，更容易理解和消化。

一、Raft 概述

??Raft 算法???是分布式系統開發首選的??共識算法??。比如現在流行 Etcd、Consul。

如果??掌握???了這個算法，就可以較容易地處理絕大部分場景的??容錯???和??一致性??需求。比如分布式配置系統、分布式 NoSQL 存儲等等，輕松突破系統的單機限制。

Raft 算法是通過一切以領導者為準的方式，實現一系列值的共識和各節點日志的一致。

二、Raft 角色

2.1 角色

跟隨者（Follower）：??普通群眾??，默默接收和來自領導者的消息，當領導者心跳信息超時的時候，就主動站出來，推薦自己當候選人。

候選人（Candidate）：??候選人??將向其他節點請求投票 RPC 消息，通知其他節點來投票，如果贏得了大多數投票選票，就晉升當領導者。

領導者（Leader）：??霸道總裁??，一切以我為準。處理寫請求、管理日志復制和不斷地發送心跳信息，通知其他節點“我是領導者，我還活著，你們不要”發起新的選舉，不用找新領導來替代我。

如下圖所示，分別用三種圖代表跟隨者、候選人和領導者。

角色

三、單節點系統

3.1 數據庫服務器

現在我們想象一下，有一個單節點系統，這個節點作為數據庫服務器，且存儲了一個值為 X。

數據庫服務器

3.2 客戶端

左邊綠色的實心圈就是客戶端，右邊的藍色實心圈就是節點 a（Node a）。Term 代表任期，后面會講到。

客戶端

3.3 客戶端向服務器發送數據

客戶端向單節點服務器發送了一條更新操作，設置數據庫中存的值為 8。單機環境下（單個服務器節點），客戶端從服務器拿到的值也是 8。一致性非常容易保證。

客戶端向服務器發送數據

3.4 多節點如何保證一致性？

但如果有多個服務器節點，怎么保證一致性呢？比如有三個節點：a，b，c。如下圖所示。這三個節點組成一個數據庫集群。客戶端對這三個節點進行更新操作，如何保證三個節點中存的值一致？這個就是分布式一致性問題。Raft 算法就是來解決這個問題的。當然還有其他協議也可以保證，本篇只針對 Raft 算法。

在多節點集群中，在節點故障、分區錯誤等異常情況下，Raft 算法如何保證在同一個時間，集群中只有一個領導者呢？下面就開始講解 Raft 算法選舉領導者的過程。

四、選舉領導過程

4.1 初始狀態

初始狀態下，集群中所有節點都是跟隨者的狀態。

如下圖所示，有三個節點(Node) a、b、c，任期（Term）都為 0。

初始狀態

4.2 成為候選者

Raft 算法實現了隨機超時時間的特性，每個節點等待領導者節點心跳信息的超時時間間隔是隨機的。比如 A 節點等待超時的時間間隔 150 ms，B 節點 200 ms，C 節點 300 ms。那么 a 先超時，最先因為沒有等到領導者的心跳信息，發生超時。如下圖所示，三個節點的超時計時器開始運行。

超時時間

當 A 節點的超時時間到了后，A 節點成為候選者，并增加自己的任期編號，Term 值從 0 更新為 1，并給自己投了一票。

Node A：Term = 1, Vote Count = 1。
Node B：Term = 0。
Node C：Term = 0。

成為候選者

4.3 投票

我們來看下候選者如何成為領導者的。

Leader 選舉

第一步：節點 A 成為候選者后，向其他節點發送請求投票 RPC 信息，請它們選舉自己為領導者。
第二步：節點 B 和節點 C 接收到節點 A 發送的請求投票信息后，在編號為 1 的這屆任期內，還沒有進行過投票，就把選票投給節點 A，并增加自己的任期編號。
第三步：節點 A 收到 3 次投票，得到了大多數節點的投票，從候選者成為本屆任期內的新的領導者。
第四步：節點 A 作為領導者，固定的時間間隔給節點 B 和節點 C 發送心跳信息，告訴節點 B 和 C，我是領導者，組織其他跟隨者發起新的選舉。
第五步：節點 B 和節點 C 發送響應信息給節點 A，告訴節點 A 我是正常的。

4.4 任期

英文單詞是 term，領導者是有任期的。

自動增加：跟隨者在等待領導者心跳信息超時后，推薦自己為候選人，會增加自己的任期號，如上圖所示，節點 A 任期為 0，推舉自己為候選人時，任期編號增加為 1。
更新為較大值：當節點發現自己的任期編號比其他節點小時，會更新到較大的編號值。比如節點 A 的任期為 1，請求投票，投票消息中包含了節點 A 的任期編號，且編號為 1，節點 B 收到消息后，會將自己的任期編號更新為 1。
恢復為跟隨者：如果一個候選人或者領導者，發現自己的任期編號比其他節點小，那么它會立即恢復成跟隨者狀態。這種場景出現在分區錯誤恢復后，任期為 3 的領導者受到任期編號為 4 的心跳消息，那么前者將立即恢復成跟隨者狀態。
拒絕消息：如果一個節點接收到較小的任期編號值的請求，那么它會直接拒絕這個請求，比如任期編號為 6 的節點 A，收到任期編號為 5 的節點 B 的請求投票 RPC 消息，那么節點 A 會拒絕這個消息。

4.5 選舉規則

一個任期內，領導者一直都會領導者，直到自身出現問題（如宕機），或者網絡問題（延遲），其他節點發起一輪新的選舉。
在一次選舉中，每一個服務器節點最多會對一個任期編號投出一張選票，投完了就沒了。

4.6 大多數

假設一個集群由 N 個節點組成，那么大多數就是至少 N/2+1。例如：3 個節點的集群，大多數就是 2。

4.7 心跳超時

為了防止多個節點同時發起投票，會給每個節點分配一個隨機的選舉超時時間。這個時間內，節點不能成為候選者，只能等到超時。比如上述例子，節點 A 先超時，先成為了候選者。這種巧妙的設計，在大多數情況下只有一個服務器節點先發起選舉，而不是同時發起選舉，減少了因選票瓜分導致選舉失敗的情況。