分散式系統必須知道的共識演算法：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 先超時，先成為了候選者。這種巧妙的設計，在大多數情況下只有一個伺服器節點先發起選舉，而不是同時發起選舉，減少了因選票瓜分導致選舉失敗的情況。

成為候選者

五、領導者故障

如果領導節點故障，則會觸發新的一輪選舉。如下圖所示，領導者節點 A 發生故障，節點 B 和 節點 C 就會重新選出 Leader。

領導故障

• 第一步 ：節點A 發生故障，節點B和節點C 沒有收到領導者節點A 的心跳訊息，等待逾時。
• 第二步：節點 C 先發生逾時，節點 C 成為候選人。
• 第三步：節點 C 向節點 A 和節點 B 發起請求投票資訊。
• 第四步：節點 C 回應投票，將票投給了 C，而節點 A 因為發生故障了，無法回應 C 的投票請求。
• 第五步：節點 C 收到兩票（大多數票數），成為領導者。
• 第六步：節點 C 向節點 A 和 B 發送心跳訊息，節點 B 回應心跳訊息，節點 A 不回應心跳訊息，因為 A 故障了。

總結

Raft 演算法透過以下幾種方式來進行領導選舉，保證了一個任期只有一位領導，極大減少了選舉失敗的情況。

• 任期
• 領導者心跳資訊
• 隨機選舉超時時間
• 先來先服務的投票原則
• #大多數票原則

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

以上是分散式系統必須知道的共識演算法：Raft的詳細內容。更多資訊請關注PHP中文網其他相關文章！