理解 RAFT 分布式共識算法——第 1 部分

為什么我們需要共識

我們大多數(shù)人在我們的編程生涯中至少使用過一次關系數(shù)據(jù)庫，如 MySQL、Oracle。當您INSERT或UPDATE一個值然后對其執(zhí)行 SELECT時，您會得到最新的值——這通常是因為我們使用一臺機器來管理我們的數(shù)據(jù)。

現(xiàn)在想象一下，您有大量數(shù)據(jù)分布在 10 臺機器上。為了更好地提供數(shù)據(jù)，您已啟用數(shù)據(jù)復制。假設一條數(shù)據(jù)在 3 臺機器上復制，應用程序是全球性的，然后想從世界任何地方查詢準確的數(shù)據(jù)，為了解決這個問題，我們需要一種機制，通過該機制，多個服務器可以就一個值達成一致，并且無論哪臺機器為您的SELECT請求提供服務，每次都會得到相同的結果。

簡而言之，您需要對分布式系統(tǒng)有一個連貫的視圖，這樣它的行為就好像只有一臺機器在為所有請求提供服務，這就是我們需要達成共識的地方。

如果你想構建一個強一致的分布式系統(tǒng)（CAP定理中的CP系統(tǒng)），需要有共識。

Raft

Raft（復制和容錯）是解決這個問題的算法/協(xié)議。它來自于 2014 年斯坦福大學 Diego Ongaro 和 John Ousterhout 的博士論文。 Raft 的設計易于理解，前身算法如 Paxos 和 Multi-Paxos 是眾所周知的共識算法，已知很難理解理解，只有少數(shù)人能正確理解它們。

Raft 沒有標準的實現(xiàn)，它只是定義了幾個步驟以容錯的方式達成共識。目前已經(jīng)有數(shù)百種 Raft 實現(xiàn)，大多數(shù)工程師在他們的一生中不需要實現(xiàn)任何共識算法，但是理解分布式系統(tǒng)的核心并沒有什么壞處。

Q. Raft 是如何實現(xiàn)的？A. Raft 通常被實現(xiàn)為服務內(nèi)部的一個模塊，如分布式數(shù)據(jù)庫或分布式鍵值存儲如 etcd等。Raft 本身不是作為服務或微服務實現(xiàn)的。它就像系統(tǒng)中的后臺進程一樣工作。

前提條件概念

在我們深入了解 Raft 之前，請先了解以下概念。

法定人數(shù)

如果你的分布式系統(tǒng)有N節(jié)點，你至少需要(N/2) + 1節(jié)點來就一個值達成一致——基本上你需要多數(shù)票（超過 50%）來達成共識，就像任何國家的憲法選舉一樣。多數(shù)投票確保當(N/2) + 1節(jié)點運行和響應時，即使存在網(wǎng)絡分區(qū)或系統(tǒng)中的其他故障，至少一個節(jié)點包含讀取和寫入請求中給定數(shù)據(jù)的最新值。

問：當我們有一個基于仲裁的節(jié)點系統(tǒng)時，我們可以容忍多少個節(jié)點故障N？A.如果N是奇數(shù)，我們可以忍受N/2節(jié)點故障。如果N是偶數(shù)，我們可以忍受(N/2)-1節(jié)點故障。

下面是一個簡單的表格來說明這個事實：

Q. 生產(chǎn)時應該選擇偶數(shù)還是奇數(shù)N？A.考慮一下N = 4，根據(jù)上表，所需的多數(shù)是3& 你只能容忍1節(jié)點故障。對于N = 5，大多數(shù)仍然是3但可以容忍2節(jié)點故障。

問：生產(chǎn)中 N 的最差值是多少？A.如果N = 1or N = 2，如果丟失了一個節(jié)點，將丟失整個系統(tǒng)，因為您實際上根本無法容忍任何節(jié)點故障。事實上N = 2，您實際上已經(jīng)使系統(tǒng)中的單點故障翻了一番——如果任何一個節(jié)點出現(xiàn)故障，您的整個系統(tǒng)就會出現(xiàn)故障。所以在生產(chǎn)中選擇一個奇數(shù)值N 3。

問：在生產(chǎn)中什么是好的合理N？A.這個數(shù)字顯然取決于您對數(shù)據(jù)、帶寬、吞吐量和成本要求的估計。但是，5是一個不錯的數(shù)字，因為2節(jié)點總數(shù)停機，而3節(jié)點仍在運行。

問：如果大多數(shù)節(jié)點不可用會怎樣？

理想情況下，系統(tǒng)可能會完全停止響應，具體取決如何配置讀寫用例。通常寫入完全停止，但如果您將讀取請求設計為最終一致，則可用節(jié)點仍可能為讀取請求提供服務。

節(jié)點狀態(tài)

Raft 節(jié)點可以處于三種狀態(tài)：Leader, Follower& Candidate。我們將在后面的部分看到節(jié)點轉換是如何發(fā)生的?，F(xiàn)在只需要記住Raft 是一個基于領導者的共識協(xié)議，日志總是從領導者流向追隨者。

日志

這不是常規(guī)日志文件，是基于磁盤的文件，通常稱為日志條目的對象以二進制數(shù)據(jù)的形式順序添加。

已提交和未提交的日志

• 只有當集群中的多數(shù)節(jié)點復制日志條目時，才會提交日志條目。提交的日志永遠不會被覆蓋。提交的日志是持久的，最終會被 Raft 集群中的所有節(jié)點執(zhí)行。
• 如果客戶端命令/日志條目尚未復制到大多數(shù)集群節(jié)點，則稱為未提交日志。未提交的日志可以在追隨者節(jié)點中被覆蓋。

狀態(tài)機

狀態(tài)機本質上可能非常復雜。通常這意味著——根據(jù)輸入到系統(tǒng)的輸入，數(shù)據(jù)（鍵）的狀態(tài)會發(fā)生變化。在 Raft 上下文中，認為這就像一個存儲密鑰最終商定值的模塊。每個節(jié)點都有自己的狀態(tài)機。Raft 必須確保無論提交什么日志條目，它們最終都會應用于狀態(tài)機，該狀態(tài)機作為內(nèi)存中數(shù)據(jù)的真實來源。對于容錯，狀態(tài)機也可以持久化。

學期

表示節(jié)點充當領導者的時間段，該概念基于邏輯時間（不是全局時間） -它只是由每個節(jié)點單獨管理的計數(shù)器。一旦一個任期結束，另一個任期就會從一個新的領導者開始。即使在給定的時間點，節(jié)點之間的學期可能會有所不同，但 Raft 有一種機制可以將它們同步并收斂到相同的值。

也稱為租約或領導租約，只是它的另一個名稱。

RPC

像 Facebook 移動應用程序通過 HTTP 之上的 REST API 與 Facebook 服務器通信一樣，參與 Raft 的節(jié)點之間使用 TCP 之上的遠程過程調用 (RPC) 進行通信。該協(xié)議適用于跨數(shù)據(jù)中心、內(nèi)部系統(tǒng)和服務（不是面向用戶的產(chǎn)品或服務）的通信。

Raft 使用兩個不同的 RPC 請求。在高水平：

• RequestVote (RV)：當一個節(jié)點想成為領導者時，它通過發(fā)送這個請求來請求其他節(jié)點為它投票。
• AppendEntries (AE)：通過此消息，領導者要求追隨者將條目添加到他們的日志文件中。領導者可以發(fā)送空消息以及向追隨者指示它還活著的心跳。

Q. 基于領導者的系統(tǒng)的主要優(yōu)勢是什么？A.當抽象基于領導者時，系統(tǒng)變得易于理解和操作?？蛻敉ǔＭㄟ^領導者進行交互，領導者負責重要的決策制定、系統(tǒng)的元數(shù)據(jù)狀態(tài)。

問：基于領導的系統(tǒng)的主要缺點是什么？一個。領導者成為單點故障。因此，系統(tǒng)應該能夠在當前領導者失敗時快速做出反應以選擇另一個領導者。此外，由于所有客戶端交互都通過領導者進行，因此系統(tǒng)可能會在規(guī)模上變得更慢。

隨機超時

Raft 使用隨機選舉超時的概念——跟隨者等待成為候選者的時間量（有關狀態(tài)轉換的更多詳細信息，請參見圖 3）。當集群啟動時，每個節(jié)點都會為自己選擇一個介于150-300毫秒之間的隨機超時，并開始倒計時?，F(xiàn)在有2種可能：

• 在節(jié)點超時之前，它會收到來自另一個節(jié)點的消息——它可能是來自領導者的心跳或日志復制消息或來自另一個對等方的投票請求。在這種情況下，超時被重置并且倒計時再次開始。
• 超時期間節(jié)點根本沒有收到任何消息。

Q. 為什么選擇隨機超時？A.假設所有節(jié)點都有固定的超時時間。因此，在沒有領導者的情況下，它們同時超時并且無法保證領導者選舉，因為該過程可以重復多次或無限期地并且所有節(jié)點再次開始倒計時相同的超時值。所以隨機化在這里有幫助。如果領導者仍未確定，則該過程會以跨節(jié)點的一組新的隨機超時重新開始，最終我們將擁有一個領導者。經(jīng)過一兩次試驗，我們不太可能沒有選擇領導者。

終生期限

當集群中沒有領導者并且節(jié)點X超時時，它會啟動一個新的選舉期限，T通過添加1上一個任期的值來增加其任期。提醒您一下——術語是由所有節(jié)點管理的本地計數(shù)器。這里又有2個案例：

• 如果X被選為新的領導者，任期T繼續(xù)，即；添加到領導者X和此后的所有新日志條目都使用 term 傳播給追隨者T。
• X輸?shù)暨x舉，新的選舉開始于新的任期Uwhere U > T。

因此，從圖形上看，術語圖如下所示：