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

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

但是如果在數據變更時發(fā)生網絡問題（延遲、斷連和丟包等）便會出現以下情況：比如有兩個寫操作同時發(fā)生在 server_1 或 server_3 上，即便兩個寫操作有先后順序，但可能由于網絡延時導致各個服務中數據的不一致：

同樣地情況，如果在 server_1 上發(fā)生三次寫操作，在數據同步的過程中因為網絡延時或網絡丟包也可能會導致數據的不一致：

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

理解 Raft 算法

了解和學習過 Zookeeper 的同學可能聽說過 Zab 算法，它用來保證 Zookeeper 中數據的 順序一致性。Raft 也是一種分布式共識算法，它易于理解和實現，用于保證數據的 線性一致性，是最強一致性模型。

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

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

寫變更請求

當發(fā)生寫變更請求時，由 Leader 節(jié)點負責處理，即使是請求到 Follower 節(jié)點，也需要轉發(fā)給 Leader 節(jié)點處理。當 Leader 節(jié)點接收到寫請求時，它并不立即對這個請求進行處理，而是先將請求信息 按順序追加到日志文件中（WAL: write-ahead-log），如圖中標記的 log_index 表示追加到的最新一條日志的序號：

在這個過程中，日志必須持久化存儲。隨后，Leader 節(jié)點通過 RPC 請求將日志同步到各個 Follower 節(jié)點，當超過半數節(jié)點成功將日志記錄時，便認為同步成功。在這里可知 Raft 算法采用的是單主復制的模型，所以它也就會存在以下缺點：

面對大量寫請求負載時系統比較難擴展，因為系統只有一個主節(jié)點，寫請求的性能瓶頸由單個節(jié)點決定

當主節(jié)點宕機時，從節(jié)點提升為主節(jié)點不是即時的，可能會造成一些停機時間

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

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

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

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

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

返回執(zhí)行結果

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

在這個過程中，我一直在強調 “按順序”，不論是日志的追加還是日志的被應用都是按順序來的，因此才能保證數據的線性一致性。

讀請求

Raft 集群處理讀請求會保證讀請求的線性一致性，所謂線性一致性讀就是在 t1 的時間寫入了一個值，那么在 t1 之后，讀一定能讀到這個值，不可能讀到 t1 之前的值，在 Raft 算法中實現線性一致性讀有以下兩種方式：

ReadIndex Read

在這種方式下，當 Leader 節(jié)點處理讀請求時：

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

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

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

Leader 執(zhí)行 read 請求，將結果返回

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

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

Lease Read

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

lease_end = current_time() + election_timeout / clock_drift_bound

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

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

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

一致性

一致性 通常指的就是數據一致性，在分布式系統中的讀寫請求，表現得像在單機系統上一樣，符合直覺和預期。一致性模型有很多種，在這里我們只談以下常見的幾種：

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

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

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

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

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

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

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

接下來我們再來談談腦裂問題：

腦裂問題

當集群中發(fā)生網絡通訊問題時，讀、寫請求只能在超過半數節(jié)點的集群內生效，過半數機制 在數學上保證不可能同時存在兩個Leader：

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

Term機制：時間上保證舊Leader會自動讓位給新Leader

主動stepDown：Leader無法聯系到過半數節(jié)點時主動放棄領導權

嚴格的投票規(guī)則：每個term每個節(jié)點只能投票給一個候選人

當網絡問題恢復時，Follower 節(jié)點能通過 Leader 節(jié)點的日志同步重新追回期間錯過的數據。此外，一般采用 Raft 算法的集群在部署的時都是 “奇數個節(jié)點”，而不是偶數個節(jié)點，這其實是數學的體現，性價比更高：

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

以上我們基本了解了 Raft 算法的內容，如果想使用 Raft 算法，對系統模型有以下要求：

服務可能宕機、停止運行，但過段時間能夠恢復，但不能存在 拜占庭故障

消息可能丟失、延遲亂序或重復；可能有網絡分區(qū)，并在一段時間之后恢復

巨人的肩膀

SOFAJRaft

The Raft Consensus Algorithm

TiKV 功能介紹 – Lease Read

《深入理解分布式系統》

審核編輯 黃宇