理解 RAFT 分布式共識(shí)算法——第 1 部分
為什么我們需要共識(shí)
我們大多數(shù)人在我們的編程生涯中至少使用過(guò)一次關(guān)系數(shù)據(jù)庫(kù)，如 MySQL、Oracle。當(dāng)您INSERT或UPDATE一個(gè)值然后對(duì)其執(zhí)行 SELECT時(shí)，您會(huì)得到最新的值——這通常是因?yàn)槲覀兪褂靡慌_(tái)機(jī)器來(lái)管理我們的數(shù)據(jù)。
現(xiàn)在想象一下，您有大量數(shù)據(jù)分布在 10 臺(tái)機(jī)器上。為了更好地提供數(shù)據(jù)，您已啟用數(shù)據(jù)復(fù)制。假設(shè)一條數(shù)據(jù)在 3 臺(tái)機(jī)器上復(fù)制，應(yīng)用程序是全球性的，然后想從世界任何地方查詢(xún)準(zhǔn)確的數(shù)據(jù)，為了解決這個(gè)問(wèn)題，我們需要一種機(jī)制，通過(guò)該機(jī)制，多個(gè)服務(wù)器可以就一個(gè)值達(dá)成一致，并且無(wú)論哪臺(tái)機(jī)器為您的SELECT請(qǐng)求提供服務(wù)，每次都會(huì)得到相同的結(jié)果。
簡(jiǎn)而言之，您需要對(duì)分布式系統(tǒng)有一個(gè)連貫的視圖，這樣它的行為就好像只有一臺(tái)機(jī)器在為所有請(qǐng)求提供服務(wù)，這就是我們需要達(dá)成共識(shí)的地方。
如果你想構(gòu)建一個(gè)強(qiáng)一致的分布式系統(tǒng)（CAP定理中的CP系統(tǒng)），需要有共識(shí)。
Raft
Raft（復(fù)制和容錯(cuò)）是解決這個(gè)問(wèn)題的算法/協(xié)議。它來(lái)自于 2014 年斯坦福大學(xué) Diego Ongaro 和 John Ousterhout 的博士論文。 Raft 的設(shè)計(jì)易于理解，前身算法如 Paxos 和 Multi-Paxos 是眾所周知的共識(shí)算法，已知很難理解理解，只有少數(shù)人能正確理解它們。
Raft 沒(méi)有標(biāo)準(zhǔn)的實(shí)現(xiàn)，它只是定義了幾個(gè)步驟以容錯(cuò)的方式達(dá)成共識(shí)。目前已經(jīng)有數(shù)百種 Raft 實(shí)現(xiàn)，大多數(shù)工程師在他們的一生中不需要實(shí)現(xiàn)任何共識(shí)算法，但是理解分布式系統(tǒng)的核心并沒(méi)有什么壞處。
Q. Raft 是如何實(shí)現(xiàn)的？A. Raft 通常被實(shí)現(xiàn)為服務(wù)內(nèi)部的一個(gè)模塊，如分布式數(shù)據(jù)庫(kù)或分布式鍵值存儲(chǔ)如 etcd等。Raft 本身不是作為服務(wù)或微服務(wù)實(shí)現(xiàn)的。它就像系統(tǒng)中的后臺(tái)進(jìn)程一樣工作。
前提條件概念
在我們深入了解 Raft 之前，請(qǐng)先了解以下概念。
法定人數(shù)
如果你的分布式系統(tǒng)有N節(jié)點(diǎn)，你至少需要(N/2) + 1節(jié)點(diǎn)來(lái)就一個(gè)值達(dá)成一致——基本上你需要多數(shù)票（超過(guò) 50%）來(lái)達(dá)成共識(shí)，就像任何國(guó)家的憲法選舉一樣。多數(shù)投票確保當(dāng)(N/2) + 1節(jié)點(diǎn)運(yùn)行和響應(yīng)時(shí)，即使存在網(wǎng)絡(luò)分區(qū)或系統(tǒng)中的其他故障，至少一個(gè)節(jié)點(diǎn)包含讀取和寫(xiě)入請(qǐng)求中給定數(shù)據(jù)的最新值。
問(wèn)：當(dāng)我們有一個(gè)基于仲裁的節(jié)點(diǎn)系統(tǒng)時(shí)，我們可以容忍多少個(gè)節(jié)點(diǎn)故障N？A.如果N是奇數(shù)，我們可以忍受N/2節(jié)點(diǎn)故障。如果N是偶數(shù)，我們可以忍受(N/2)-1節(jié)點(diǎn)故障。
下面是一個(gè)簡(jiǎn)單的表格來(lái)說(shuō)明這個(gè)事實(shí)：
Q. 生產(chǎn)時(shí)應(yīng)該選擇偶數(shù)還是奇數(shù)N？A.考慮一下N = 4，根據(jù)上表，所需的多數(shù)是3& 你只能容忍1節(jié)點(diǎn)故障。對(duì)于N = 5，大多數(shù)仍然是3但可以容忍2節(jié)點(diǎn)故障。
問(wèn)：生產(chǎn)中 N 的最差值是多少？A.如果N = 1or N = 2，如果丟失了一個(gè)節(jié)點(diǎn)，將丟失整個(gè)系統(tǒng)，因?yàn)槟鷮?shí)際上根本無(wú)法容忍任何節(jié)點(diǎn)故障。事實(shí)上N = 2，您實(shí)際上已經(jīng)使系統(tǒng)中的單點(diǎn)故障翻了一番——如果任何一個(gè)節(jié)點(diǎn)出現(xiàn)故障，您的整個(gè)系統(tǒng)就會(huì)出現(xiàn)故障。所以在生產(chǎn)中選擇一個(gè)奇數(shù)值N 3。
問(wèn)：在生產(chǎn)中什么是好的合理N？A.這個(gè)數(shù)字顯然取決于您對(duì)數(shù)據(jù)、帶寬、吞吐量和成本要求的估計(jì)。但是，5是一個(gè)不錯(cuò)的數(shù)字，因?yàn)?節(jié)點(diǎn)總數(shù)停機(jī)，而3節(jié)點(diǎn)仍在運(yùn)行。
問(wèn)：如果大多數(shù)節(jié)點(diǎn)不可用會(huì)怎樣？
理想情況下，系統(tǒng)可能會(huì)完全停止響應(yīng)，具體取決如何配置讀寫(xiě)用例。通常寫(xiě)入完全停止，但如果您將讀取請(qǐng)求設(shè)計(jì)為最終一致，則可用節(jié)點(diǎn)仍可能為讀取請(qǐng)求提供服務(wù)。
節(jié)點(diǎn)狀態(tài)
Raft 節(jié)點(diǎn)可以處于三種狀態(tài)：Leader, Follower& Candidate。我們將在后面的部分看到節(jié)點(diǎn)轉(zhuǎn)換是如何發(fā)生的?，F(xiàn)在只需要記住Raft 是一個(gè)基于領(lǐng)導(dǎo)者的共識(shí)協(xié)議，日志總是從領(lǐng)導(dǎo)者流向追隨者。
日志
這不是常規(guī)日志文件，是基于磁盤(pán)的文件，通常稱(chēng)為日志條目的對(duì)象以二進(jìn)制數(shù)據(jù)的形式順序添加。
已提交和未提交的日志
- 只有當(dāng)集群中的多數(shù)節(jié)點(diǎn)復(fù)制日志條目時(shí)，才會(huì)提交日志條目。提交的日志永遠(yuǎn)不會(huì)被覆蓋。提交的日志是持久的，最終會(huì)被 Raft 集群中的所有節(jié)點(diǎn)執(zhí)行。
- 如果客戶(hù)端命令/日志條目尚未復(fù)制到大多數(shù)集群節(jié)點(diǎn)，則稱(chēng)為未提交日志。未提交的日志可以在追隨者節(jié)點(diǎn)中被覆蓋。
狀態(tài)機(jī)
狀態(tài)機(jī)本質(zhì)上可能非常復(fù)雜。通常這意味著——根據(jù)輸入到系統(tǒng)的輸入，數(shù)據(jù)（鍵）的狀態(tài)會(huì)發(fā)生變化。在 Raft 上下文中，認(rèn)為這就像一個(gè)存儲(chǔ)密鑰最終商定值的模塊。每個(gè)節(jié)點(diǎn)都有自己的狀態(tài)機(jī)。Raft 必須確保無(wú)論提交什么日志條目，它們最終都會(huì)應(yīng)用于狀態(tài)機(jī)，該狀態(tài)機(jī)作為內(nèi)存中數(shù)據(jù)的真實(shí)來(lái)源。對(duì)于容錯(cuò)，狀態(tài)機(jī)也可以持久化。
學(xué)期
表示節(jié)點(diǎn)充當(dāng)領(lǐng)導(dǎo)者的時(shí)間段，該概念基于邏輯時(shí)間（不是全局時(shí)間） -它只是由每個(gè)節(jié)點(diǎn)單獨(dú)管理的計(jì)數(shù)器。一旦一個(gè)任期結(jié)束，另一個(gè)任期就會(huì)從一個(gè)新的領(lǐng)導(dǎo)者開(kāi)始。即使在給定的時(shí)間點(diǎn)，節(jié)點(diǎn)之間的學(xué)期可能會(huì)有所不同，但 Raft 有一種機(jī)制可以將它們同步并收斂到相同的值。
也稱(chēng)為租約或領(lǐng)導(dǎo)租約，只是它的另一個(gè)名稱(chēng)。
RPC
像 Facebook 移動(dòng)應(yīng)用程序通過(guò) HTTP 之上的 REST API 與 Facebook 服務(wù)器通信一樣，參與 Raft 的節(jié)點(diǎn)之間使用 TCP 之上的遠(yuǎn)程過(guò)程調(diào)用 (RPC) 進(jìn)行通信。該協(xié)議適用于跨數(shù)據(jù)中心、內(nèi)部系統(tǒng)和服務(wù)（不是面向用戶(hù)的產(chǎn)品或服務(wù)）的通信。
Raft 使用兩個(gè)不同的 RPC 請(qǐng)求。在高水平：
- RequestVote (RV)：當(dāng)一個(gè)節(jié)點(diǎn)想成為領(lǐng)導(dǎo)者時(shí)，它通過(guò)發(fā)送這個(gè)請(qǐng)求來(lái)請(qǐng)求其他節(jié)點(diǎn)為它投票。
- AppendEntries (AE)：通過(guò)此消息，領(lǐng)導(dǎo)者要求追隨者將條目添加到他們的日志文件中。領(lǐng)導(dǎo)者可以發(fā)送空消息以及向追隨者指示它還活著的心跳。
Q. 基于領(lǐng)導(dǎo)者的系統(tǒng)的主要優(yōu)勢(shì)是什么？A.當(dāng)抽象基于領(lǐng)導(dǎo)者時(shí)，系統(tǒng)變得易于理解和操作。客戶(hù)通常通過(guò)領(lǐng)導(dǎo)者進(jìn)行交互，領(lǐng)導(dǎo)者負(fù)責(zé)重要的決策制定、系統(tǒng)的元數(shù)據(jù)狀態(tài)。
問(wèn)：基于領(lǐng)導(dǎo)的系統(tǒng)的主要缺點(diǎn)是什么？一個(gè)。領(lǐng)導(dǎo)者成為單點(diǎn)故障。因此，系統(tǒng)應(yīng)該能夠在當(dāng)前領(lǐng)導(dǎo)者失敗時(shí)快速做出反應(yīng)以選擇另一個(gè)領(lǐng)導(dǎo)者。此外，由于所有客戶(hù)端交互都通過(guò)領(lǐng)導(dǎo)者進(jìn)行，因此系統(tǒng)可能會(huì)在規(guī)模上變得更慢。
隨機(jī)超時(shí)
Raft 使用隨機(jī)選舉超時(shí)的概念——跟隨者等待成為候選者的時(shí)間量（有關(guān)狀態(tài)轉(zhuǎn)換的更多詳細(xì)信息，請(qǐng)參見(jiàn)圖 3）。當(dāng)集群?jiǎn)?dòng)時(shí)，每個(gè)節(jié)點(diǎn)都會(huì)為自己選擇一個(gè)介于150-300毫秒之間的隨機(jī)超時(shí)，并開(kāi)始倒計(jì)時(shí)?，F(xiàn)在有2種可能：
- 在節(jié)點(diǎn)超時(shí)之前，它會(huì)收到來(lái)自另一個(gè)節(jié)點(diǎn)的消息——它可能是來(lái)自領(lǐng)導(dǎo)者的心跳或日志復(fù)制消息或來(lái)自另一個(gè)對(duì)等方的投票請(qǐng)求。在這種情況下，超時(shí)被重置并且倒計(jì)時(shí)再次開(kāi)始。
- 超時(shí)期間節(jié)點(diǎn)根本沒(méi)有收到任何消息。
Q. 為什么選擇隨機(jī)超時(shí)？A.假設(shè)所有節(jié)點(diǎn)都有固定的超時(shí)時(shí)間。因此，在沒(méi)有領(lǐng)導(dǎo)者的情況下，它們同時(shí)超時(shí)并且無(wú)法保證領(lǐng)導(dǎo)者選舉，因?yàn)樵撨^(guò)程可以重復(fù)多次或無(wú)限期地并且所有節(jié)點(diǎn)再次開(kāi)始倒計(jì)時(shí)相同的超時(shí)值。所以隨機(jī)化在這里有幫助。如果領(lǐng)導(dǎo)者仍未確定，則該過(guò)程會(huì)以跨節(jié)點(diǎn)的一組新的隨機(jī)超時(shí)重新開(kāi)始，最終我們將擁有一個(gè)領(lǐng)導(dǎo)者。經(jīng)過(guò)一兩次試驗(yàn)，我們不太可能沒(méi)有選擇領(lǐng)導(dǎo)者。
終生期限
當(dāng)集群中沒(méi)有領(lǐng)導(dǎo)者并且節(jié)點(diǎn)X超時(shí)時(shí)，它會(huì)啟動(dòng)一個(gè)新的選舉期限，T通過(guò)添加1上一個(gè)任期的值來(lái)增加其任期。提醒您一下——術(shù)語(yǔ)是由所有節(jié)點(diǎn)管理的本地計(jì)數(shù)器。這里又有2個(gè)案例：
- 如果X被選為新的領(lǐng)導(dǎo)者，任期T繼續(xù)，即；添加到領(lǐng)導(dǎo)者X和此后的所有新日志條目都使用 term 傳播給追隨者T。
- X輸?shù)暨x舉，新的選舉開(kāi)始于新的任期Uwhere U > T。
因此，從圖形上看，術(shù)語(yǔ)圖如下所示：
