“不可靠的網(wǎng)絡(luò)”、“不穩(wěn)定的時(shí)鐘”和“節(jié)點(diǎn)的故障”都是在分布式系統(tǒng)中常見的問題，在文章開始前，我們先來看一下：如果在分布式系統(tǒng)中網(wǎng)絡(luò)不可靠會(huì)發(fā)生什么樣的問題。

有以下 3 個(gè)服務(wù)構(gòu)成的分布式集群，并在 server_1 中發(fā)生寫請(qǐng)求變更 A = 1，“正常情況下” server_1 將 A 值同步給 server_2 和 server_3，保證集群的數(shù)據(jù)一致性：

但是如果在數(shù)據(jù)變更時(shí)發(fā)生網(wǎng)絡(luò)問題（延遲、斷連和丟包等）便會(huì)出現(xiàn)以下情況：比如有兩個(gè)寫操作同時(shí)發(fā)生在 server_1 或 server_3 上，即便兩個(gè)寫操作有先后順序，但可能由于網(wǎng)絡(luò)延時(shí)導(dǎo)致各個(gè)服務(wù)中數(shù)據(jù)的不一致：

同樣地情況，如果在 server_1 上發(fā)生三次寫操作，在數(shù)據(jù)同步的過程中因?yàn)榫W(wǎng)絡(luò)延時(shí)或網(wǎng)絡(luò)丟包也可能會(huì)導(dǎo)致數(shù)據(jù)的不一致：

那么為了避免以上這些集群間數(shù)據(jù)不一致的問題，便需要分布式共識(shí)算法來協(xié)調(diào)。分布式共識(shí)算法簡(jiǎn)單來說就是如何在多個(gè)服務(wù)器間對(duì)某一個(gè)值達(dá)成一致，并且當(dāng)達(dá)成一致之后，無論之后這些機(jī)器間發(fā)生怎樣的故障，這個(gè)值能保持不變。本篇文章我們便對(duì) Raft 算法進(jìn)行介紹。

理解 Raft 算法

了解和學(xué)習(xí)過 Zookeeper 的同學(xué)可能聽說過 Zab 算法，它用來保證 Zookeeper 中數(shù)據(jù)的 順序一致性。Raft 也是一種分布式共識(shí)算法，它易于理解和實(shí)現(xiàn)，用于保證數(shù)據(jù)的 線性一致性，是最強(qiáng)一致性模型。

在遵循 Raft 算法的集群中，節(jié)點(diǎn)會(huì)有 3 種不同的角色。當(dāng)集群在初始化時(shí)，每個(gè)節(jié)點(diǎn)的角色都是 Follower 跟隨者，它們會(huì)等待來自 Leader 節(jié)點(diǎn)的心跳。因?yàn)榇藭r(shí)并沒有 Leader 節(jié)點(diǎn)，所以會(huì)等待心跳超時(shí)。等待超時(shí)的 Follower 節(jié)點(diǎn)會(huì)將角色轉(zhuǎn)變?yōu)?Candidate 候選者，觸發(fā)一次選舉，觸發(fā)選舉時(shí)會(huì)標(biāo)記 Term 任期變量，并將自己的一票投給自己，通知其他 Follower 節(jié)點(diǎn)發(fā)起投票。經(jīng)過投票后，收到超過半數(shù)節(jié)點(diǎn)票數(shù)的 Candidate 節(jié)點(diǎn)會(huì)成為 Leader 領(lǐng)導(dǎo)者節(jié)點(diǎn)，其他節(jié)點(diǎn)為 Follower 跟隨者節(jié)點(diǎn)，Leader 節(jié)點(diǎn)會(huì)不斷地發(fā)送心跳給 Follower 節(jié)點(diǎn)來維持領(lǐng)導(dǎo)地位：

如果每個(gè)節(jié)點(diǎn)每次在觸發(fā)選舉時(shí)都是同時(shí)超時(shí)，這樣是不是導(dǎo)致不能完成一次選舉，產(chǎn)生 “活鎖” 問題？的確可能，不過活鎖問題也很好解決：即節(jié)點(diǎn)超時(shí)時(shí)間在合理的范圍內(nèi)取隨機(jī)值，這樣由于它的隨機(jī)性就不太可能再同時(shí)發(fā)起競(jìng)選了，這個(gè)時(shí)候其他節(jié)點(diǎn)便有足夠的時(shí)間向其他節(jié)點(diǎn)索要選票。

寫變更請(qǐng)求

當(dāng)發(fā)生寫變更請(qǐng)求時(shí)，由 Leader 節(jié)點(diǎn)負(fù)責(zé)處理，即使是請(qǐng)求到 Follower 節(jié)點(diǎn)，也需要轉(zhuǎn)發(fā)給 Leader 節(jié)點(diǎn)處理。當(dāng) Leader 節(jié)點(diǎn)接收到寫請(qǐng)求時(shí)，它并不立即對(duì)這個(gè)請(qǐng)求進(jìn)行處理，而是先將請(qǐng)求信息 按順序追加到日志文件中（WAL: write-ahead-log），如圖中標(biāo)記的 log_index 表示追加到的最新一條日志的序號(hào)：

在這個(gè)過程中，日志必須持久化存儲(chǔ)。隨后，Leader 節(jié)點(diǎn)通過 RPC 請(qǐng)求將日志同步到各個(gè) Follower 節(jié)點(diǎn)，當(dāng)超過半數(shù)節(jié)點(diǎn)成功將日志記錄時(shí)，便認(rèn)為同步成功。在這里可知 Raft 算法采用的是單主復(fù)制的模型，所以它也就會(huì)存在以下缺點(diǎn)：

面對(duì)大量寫請(qǐng)求負(fù)載時(shí)系統(tǒng)比較難擴(kuò)展，因?yàn)橄到y(tǒng)只有一個(gè)主節(jié)點(diǎn)，寫請(qǐng)求的性能瓶頸由單個(gè)節(jié)點(diǎn)決定

當(dāng)主節(jié)點(diǎn)宕機(jī)時(shí)，從節(jié)點(diǎn)提升為主節(jié)點(diǎn)不是即時(shí)的，可能會(huì)造成一些停機(jī)時(shí)間

隨后，Leader 節(jié)點(diǎn)會(huì)更新最新同步日志的索引 commit_index 為 1，并通過心跳下發(fā)給各個(gè) Follower 節(jié)點(diǎn)：

在這個(gè)過程中可以發(fā)現(xiàn) Follower 節(jié)點(diǎn)只是聽從并響應(yīng) Leader 節(jié)點(diǎn)，沒有任何主動(dòng)性。現(xiàn)在，已經(jīng)完成了日志在集群間的同步，但是請(qǐng)求對(duì)變量 A 的修改還沒有被應(yīng)用（Apply）。Apply 是在 Raft 算法中經(jīng)常出現(xiàn)的一個(gè)名詞，在多數(shù)與 Raft 算法相關(guān)的文章中經(jīng)常會(huì)看到 “將已提交的日志條目應(yīng)用到狀態(tài)機(jī)” 等類似的表述。其實(shí) “狀態(tài)機(jī)” 理解起來并不復(fù)雜，通俗的理解是 業(yè)務(wù)邏輯的載體 或 業(yè)務(wù)邏輯的執(zhí)行者，它的職責(zé)包括：

接收來自日志文件中有序的命令

執(zhí)行具體的業(yè)務(wù)邏輯，在本次寫請(qǐng)求中，業(yè)務(wù)邏輯指的便是變更 A 的值

變更應(yīng)用程序的狀態(tài)

返回執(zhí)行結(jié)果

更加通俗的講就是 讓請(qǐng)求生效。將已經(jīng)提交的日志應(yīng)用到狀態(tài)機(jī)是比較簡(jiǎn)單且自主的過程，各個(gè)服務(wù)實(shí)例會(huì)記錄 apply_index 來標(biāo)記應(yīng)用索引，當(dāng) apply_index 小于 commit_index 時(shí)，那么證明日志文件中記錄的請(qǐng)求信息還有部分沒生效，所以需要按順序應(yīng)用，直到 apply_index = commit_index：

在這個(gè)過程中，我一直在強(qiáng)調(diào) “按順序”，不論是日志的追加還是日志的被應(yīng)用都是按順序來的，因此才能保證數(shù)據(jù)的線性一致性。

讀請(qǐng)求

Raft 集群處理讀請(qǐng)求會(huì)保證讀請(qǐng)求的線性一致性，所謂線性一致性讀就是在 t1 的時(shí)間寫入了一個(gè)值，那么在 t1 之后，讀一定能讀到這個(gè)值，不可能讀到 t1 之前的值，在 Raft 算法中實(shí)現(xiàn)線性一致性讀有以下兩種方式：

ReadIndex Read

在這種方式下，當(dāng) Leader 節(jié)點(diǎn)處理讀請(qǐng)求時(shí)：

首先將 commit_index 記錄到本地的 read_index 變量里

向其他節(jié)點(diǎn)發(fā)送一次 Heartbeat，確認(rèn)自己仍然是 Leader 角色

Leader 節(jié)點(diǎn)等待自己的狀態(tài)機(jī)執(zhí)行，直到 apply_index 超過了 read_index，這樣就能夠安全的提供線性一致性讀了

Leader 執(zhí)行 read 請(qǐng)求，將結(jié)果返回

在第三步中，保證 apply_index >= read_index 是為了保證所有小于等于 read_index 的請(qǐng)求都已經(jīng)生效。

如果是 Follower 節(jié)點(diǎn)處理讀請(qǐng)求也和以上過程類似，當(dāng) Follower 節(jié)點(diǎn)收到讀請(qǐng)求后，直接給 Leader 發(fā)送一個(gè)獲取此時(shí) read_index 的請(qǐng)求，Leader 節(jié)點(diǎn)仍然處理以上流程然后將 read_index 返回，此時(shí) Follower 節(jié)點(diǎn)等到當(dāng)前的狀態(tài)機(jī) apply_index 超過 read_index 后，就可以返回結(jié)果了。

Lease Read

因?yàn)?ReadIndex Read 需要發(fā)送一次 Heartbeat 來確認(rèn) Leader 身份，存在 RPC 請(qǐng)求的開銷，為了進(jìn)一步優(yōu)化，便可以采用租約（Lease）讀。租約其實(shí)指的是 Leader 節(jié)點(diǎn)身份的過期約定時(shí)間，所以這種讀請(qǐng)求只針對(duì) Leader 節(jié)點(diǎn)，F(xiàn)ollower 節(jié)點(diǎn)沒有租約的概念，它通過以下公式計(jì)算：

lease_end = current_time() + election_timeout / clock_drift_bound

其中 election_timeout 為選舉的超時(shí)時(shí)間，clock_drift_bound 表示時(shí)鐘漂移，指的是在分布式系統(tǒng)中，兩個(gè)或多個(gè)節(jié)點(diǎn)上的時(shí)鐘以不同的速率運(yùn)行，導(dǎo)致它們之間的時(shí)間差隨時(shí)間不斷累積和變化（也就是分布式系統(tǒng)中不穩(wěn)定的時(shí)鐘問題）。

舉個(gè)簡(jiǎn)單的例子，假如選舉過期時(shí)間是 10s，時(shí)鐘漂移為 1.1，那么租約過期時(shí)間為：lease_end = current_time() + 10s / 1.1 ≈ current_time() + 9s，如果在處理讀請(qǐng)求時(shí)，在租約時(shí)間內(nèi)，則無需發(fā)送 Heartbeat 來明確 Leader 身份，直接等待 apply_index >= commit_index 后返回請(qǐng)求結(jié)果。

在以上讀寫流程中，Raft 分布式共識(shí)算法能讓每個(gè)節(jié)點(diǎn)對(duì)日志的值和順序達(dá)成共識(shí)，每個(gè)節(jié)點(diǎn)都存儲(chǔ)相同的日志副本，使整個(gè)系統(tǒng)中的每個(gè)節(jié)點(diǎn)都能有一致的狀態(tài)和輸出，使得這些節(jié)點(diǎn)看起來就像一個(gè)單獨(dú)的，高可用的狀態(tài)機(jī)。在上文中我們提到過 Zookeeper 使用的 Zab 共識(shí)算法保證的是順序一致性，Raft 算法保證的是線性一致性，所以借著這個(gè)引子也來談?wù)勎覍?duì)一致性的理解。

一致性

一致性 通常指的就是數(shù)據(jù)一致性，在分布式系統(tǒng)中的讀寫請(qǐng)求，表現(xiàn)得像在單機(jī)系統(tǒng)上一樣，符合直覺和預(yù)期。一致性模型有很多種，在這里我們只談以下常見的幾種：

線性一致性 是最強(qiáng)的一致性模型，也被稱為強(qiáng)一致性，在 CAP 定理中的 C 表達(dá)的一致性含義便是線性一致性。這種一致性模型要求系統(tǒng)要像單一節(jié)點(diǎn)一樣工作，并且所有操作是原子的，它有兩個(gè)約束條件：

順序記錄中的任何一次讀必須讀到最近一次寫入的數(shù)據(jù)

順序記錄要跟全局時(shí)鐘下的順序保持一致

順序一致性 要比線性一致性弱，它只要求 同一客戶端或進(jìn)程的操作在排序后保持先后順序不變，但 不同客戶端之間的先后順序是可以任意改變的，順序一致性與線性一致性的主要區(qū)別在于 沒有全局時(shí)間的限制。比如在社交網(wǎng)絡(luò)場(chǎng)景下，一個(gè)人通常不關(guān)注他看到的所有朋友的帖子的順序，但是對(duì)于某個(gè)具體朋友，仍然以正確的順序顯示帖子的順序。

因果一致性 則是比 順序一致性 更弱的一致性模型，因果一致性要求必須以相同的順序看到因果相關(guān)的操作，而沒有因果關(guān)系的并發(fā)操作可以被不同的進(jìn)程以不同的順序觀察到。典型的例子就是社交網(wǎng)絡(luò)中發(fā)帖和評(píng)論的關(guān)系：必須先有發(fā)帖才能對(duì)該帖子進(jìn)行評(píng)論，所以發(fā)帖操作必須在評(píng)論操作之前。

最終一致性 是常見的最弱的一致性模型，所謂最終表達(dá)的含義是“對(duì)于系統(tǒng)到達(dá)穩(wěn)定狀態(tài)并沒有硬性要求”，即便這聽起來很不靠譜，但是在業(yè)務(wù)中被應(yīng)用的很多也很好，而且這種一致性模型能使系統(tǒng)的性能很高。

CAP 定理：C 代表一致性，當(dāng)客戶端訪問所有節(jié)點(diǎn)時(shí)，返回的都是同一份最新的數(shù)據(jù)；A 代表可用性，指每次請(qǐng)求都能獲取到非錯(cuò)誤的響應(yīng)，但不保證獲取的數(shù)據(jù)是最新的；P 代表分區(qū)容錯(cuò)性，節(jié)點(diǎn)之間由于網(wǎng)絡(luò)分區(qū)而導(dǎo)致消息丟失的情況下，系統(tǒng)仍能正常運(yùn)行。

接下來我們?cè)賮碚務(wù)勀X裂問題：

腦裂問題

當(dāng)集群中發(fā)生網(wǎng)絡(luò)通訊問題時(shí)，讀、寫請(qǐng)求只能在超過半數(shù)節(jié)點(diǎn)的集群內(nèi)生效，過半數(shù)機(jī)制 在數(shù)學(xué)上保證不可能同時(shí)存在兩個(gè)Leader：

除此之外還有以下機(jī)制來避免腦裂問題：

Term機(jī)制：時(shí)間上保證舊Leader會(huì)自動(dòng)讓位給新Leader

主動(dòng)stepDown：Leader無法聯(lián)系到過半數(shù)節(jié)點(diǎn)時(shí)主動(dòng)放棄領(lǐng)導(dǎo)權(quán)

嚴(yán)格的投票規(guī)則：每個(gè)term每個(gè)節(jié)點(diǎn)只能投票給一個(gè)候選人

當(dāng)網(wǎng)絡(luò)問題恢復(fù)時(shí)，F(xiàn)ollower 節(jié)點(diǎn)能通過 Leader 節(jié)點(diǎn)的日志同步重新追回期間錯(cuò)過的數(shù)據(jù)。此外，一般采用 Raft 算法的集群在部署的時(shí)都是 “奇數(shù)個(gè)節(jié)點(diǎn)”，而不是偶數(shù)個(gè)節(jié)點(diǎn)，這其實(shí)是數(shù)學(xué)的體現(xiàn)，性價(jià)比更高：

如上圖所示，雖然部署 4 個(gè)節(jié)點(diǎn)多出一個(gè)節(jié)點(diǎn)，但是和 3 節(jié)點(diǎn)集群相比，容錯(cuò)能力是相同的：只能容忍 1 個(gè)節(jié)點(diǎn)故障。在容錯(cuò)能力沒有被提高的情況下又花費(fèi)了更多的服務(wù)器成本和運(yùn)維管理成本。

以上我們基本了解了 Raft 算法的內(nèi)容，如果想使用 Raft 算法，對(duì)系統(tǒng)模型有以下要求：

服務(wù)可能宕機(jī)、停止運(yùn)行，但過段時(shí)間能夠恢復(fù)，但不能存在 拜占庭故障

消息可能丟失、延遲亂序或重復(fù)；可能有網(wǎng)絡(luò)分區(qū)，并在一段時(shí)間之后恢復(fù)

巨人的肩膀

SOFAJRaft

The Raft Consensus Algorithm

TiKV 功能介紹 – Lease Read

《深入理解分布式系統(tǒng)》

審核編輯 黃宇