Raft算法

Raft是一種共識算法，旨在替代Paxos。 它通過邏輯分離比Paxos更容易理解，但它也被正式證明是安全的，並提供了一些額外的功能。[1] Raft提供了一種在計算系統集群中分布狀態機的通用方法，確保集群中的每個節點都同意一系列相同的狀態轉換。 它有許多開源參考實現，具有Go，C ++，Java和Scala中的完整規範實現。

基本介紹

• 中文名：Raft算法
• 外文名：Raft algorithm

基本

Raft通過當選的領導者達成共識。筏集群中的伺服器是領導者或追隨者，並且在選舉的精確情況下可以是候選者（領導者不可用）。領導者負責將日誌複製到關注者。它通過傳送心跳訊息定期通知追隨者它的存在。每個跟隨者都有一個逾時（通常在150到300毫秒之間），它期望領導者的心跳。接收心跳時重置逾時。如果沒有收到心跳，則關注者將其狀態更改為候選人並開始領導選舉。

對Raft共識問題的探討

Raft通過領導方法實現共識。該集群只有一個當選的領導者，負責管理集群其他伺服器上的日誌複製。這意味著領導者可以決定新條目的放置和在其與其他伺服器之間建立數據流而無需諮詢其他伺服器。領導者領導，直到失敗或下線，在這種情況下，新的領導者當選。

共識問題在Raft中被分解為下面列出的兩個相對獨立的子問題。

領導人選舉

當現有領導者失敗或啟動算法時，需要選出新的領導者。

在這種情況下，新的術語在集群中開始。術語是伺服器上的任意時間段，在此期間需要選出新的領導者。每個學期都以領導者選舉開始。如果選舉成功完成（即選出一名領導人），該任期將繼續由新領導人精心策劃的正常運作。如果選舉失敗，那么新的選舉就會開始。

領導者選舉由候選伺服器啟動。如果伺服器在稱為選舉逾時的時間段內沒有收到領導者的通信，則伺服器成為候選者，因此它假定不再有代理領導者。它通過增加計數器一詞，投票給自己作為新的領導者，並向所有其他要求投票的伺服器傳送訊息來開始選舉。伺服器每個學期只會投票一次，先到先得。如果候選人收到來自另一個伺服器的訊息，該訊息的術語編號至少與候選人當前的期限一樣大，則候選人的選舉將被取消，候選人將變為追隨者並將該領導者視為合法。如果候選人獲得多數票，那么它就成為新的領導者。如果兩者都沒有發生，例如，由於分裂投票，則新的任期開始，新的選舉開始。

Raft使用隨機選舉逾時來確保快速解決分割投票問題。這應該減少分裂投票的機會，因為伺服器不會同時成為候選者：單個伺服器將逾時，贏得選舉，然後成為領導者並在任何關注者成為候選者之前向其他伺服器傳送心跳訊息。

日誌複製

領導者負責日誌複製。它接受客戶端請求。每個客戶端請求都包含一個由集群中複製的狀態機執行的命令。在作為新條目附加到領導者的日誌之後，每個請求將作為AppendEntries訊息轉發給關注者。如果關注者不可用，則領導者將無限期地重試AppendEntries訊息，直到所有關注者最終存儲日誌條目。

一旦領導者收到其大多數冬粉的確認，該條目已被複製，領導者將該條目套用於其本地狀態機，該請求被視為已提交。此事件還會提交領導者日誌中的所有先前條目。一旦關注者得知提交了日誌條目，它就會將該條目套用於其本地狀態機。它通過集群為所有伺服器之間的日誌提供一致性，確保遵守日誌匹配的安全規則。

在領導者崩潰的情況下，日誌可能會保持不一致，舊的領導者的一些日誌未通過群集完全複製。然後，新的領導者將通過強制關注者複製其自己的日誌來處理不一致。為此，對於每個關注者，領導者將其日誌與來自跟隨者的日誌進行比較，找到他們同意的最後一個條目，然後刪除跟隨者日誌中此關鍵條目之後的所有條目，並將其替換為擁有日誌條目。此機制將恢復出現故障的群集中的日誌一致性。

安全

Raft的安全規則

Raft保證每個安全屬性：

選舉安全：在一個特定的任期內，最多只能選出一名領導人。

Leader Append-Only：領導者只能在其日誌中添加新條目（它既不能覆蓋也不能刪除條目）。

日誌匹配：如果兩個日誌包含具有相同索引和術語的條目，則日誌在通過給定索引的所有條目中都是相同的。

領導者完整性：如果在給定的術語中提交了日誌條目，那么從該術語開始，它將出現在領導者的日誌中。

狀態機安全性：如果伺服器已將特定日誌條目套用於其狀態機，則其他伺服器不會對同一日誌套用不同的命令。

前四節中描述的算法的細節保證了四個第一規則。選舉過程受到限制，保證了國家機器安全。

國家機器安全

此規則通過一個簡單的限制來確保：候選人無法贏得選舉，除非其日誌包含所有已提交的條目。為了當選，候選人必須聯繫群集的大多數，並且根據要提交的日誌規則，這意味著每個提交的條目將出現在候選人聯繫的至少一個伺服器上。

通過比較日誌中最後一個條目的索引項，Raft確定兩個日誌中的哪一個（由兩個不同的伺服器承載）更新。如果日誌具有包含不同術語的最後一個條目，則具有較晚術語的日誌將更新。如果日誌以相同的術語結束，則更長的日誌更新是更新的。

在Raft中，候選人對選民的請求包括有關候選人日誌的信息。如果其自己的日誌比候選人的日誌更新，則選民拒絕其對候選人的投票。此實現確保了State Machine Safety規則。
追隨者崩潰

如果關注者崩潰，其他伺服器傳送的AppendEntries和投票請求將失敗。這些故障由伺服器無限期地嘗試到達被擊落的追隨者來處理。如果關注者重新啟動，則掛起的請求將完成。如果在失敗之前已經考慮了請求，則重新啟動的關注者將忽略它。

時間和可用性

隨著時間的推移，時間對於Raft選擇和保持穩定的領導者至關重要，以便擁有完美的群集可用性。通過遵守算法的時序要求來確保穩定性：

broadcastTime << electionTimeout << MTBF

broadcastTime是伺服器向群集中的每個伺服器傳送請求並接收回響所花費的平均時間。它與您使用的基礎架構有關。

MTBF是伺服器的平均故障間隔時間。它也與您的基礎設施有關。

electionTimeout與Leader Election部分中描述的相同。這是你必須選擇的東西。

對於broadcastTime，這些值的典型數字可以是0.5ms到20ms，這意味著您將electionTimeout設定在10ms到500ms之間。單個伺服器故障之間可能需要數周或數月，這意味著值可以使穩定集群正常工作。