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

有以下 3 個服務構成的分佈式集羣，並在 server\_1 中發生寫請求變更 A = 1，“正常情況下” server\_1 將 A 值同步給 server\_2 和 server\_3，保證集羣的數據一致性：

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

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

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

理解 Raft 算法

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

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

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

寫變更請求

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

在這個過程中，日誌必須持久化存儲。隨後，Leader 節點通過 RPC 請求將日誌同步到各個 Follower 節點，當超過半數節點成功將日誌記錄時，便認為同步成功。在這裏可知 Raft 算法採用的是單主複製的模型，所以它也就會存在以下缺點：

1. 面對大量寫請求負載時系統比較難擴展，因為系統只有一個主節點，寫請求的性能瓶頸由單個節點決定
2. 當主節點宕機時，從節點提升為主節點不是即時的，可能會造成一些停機時間

隨後，Leader 節點會更新最新同步日誌的索引 commit\_index 為 1，並通過心跳下發給各個 Follower 節點：

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

1. 接收來自日誌文件中有序的命令
2. 執行具體的業務邏輯，在本次寫請求中，業務邏輯指的便是變更 A 的值
3. 變更應用程序的狀態
4. 返回執行結果

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

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

讀請求

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

ReadIndex Read

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

1. 首先將 commit\_index 記錄到本地的 read\_index 變量裏
2. 向其他節點發送一次 Heartbeat，確認自己仍然是 Leader 角色
3. Leader 節點等待自己的狀態機執行，直到 apply\_index 超過了 read\_index，這樣就能夠安全的提供線性一致性讀了
4. Leader 執行 read 請求，將結果返回

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

如果是 Follower 節點處理讀請求也和以上過程類似，當 Follower 節點收到讀請求後，直接給 Leader 發送一個獲取此時 read\_index 的請求，Leader 節點仍然處理以上流程然後將 read\_index 返回，此時 Follower 節點等到當前的狀態機 apply\_index 超過 read\_index 後，就可以返回結果了。

Lease Read

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

lease_end = current_time() + election_timeout / clock_drift_bound

其中 election\_timeout 為選舉的超時時間，clock\_drift\_bound 表示時鐘漂移，指的是在分佈式系統中，兩個或多個節點上的時鐘以不同的速率運行，導致它們之間的時間差隨時間不斷累積和變化（也就是分佈式系統中不穩定的時鐘問題）。

舉個簡單的例子，假如選舉過期時間是 10s，時鐘漂移為 1.1，那麼租約過期時間為：lease\_end = current\_time() + 10s / 1.1 ≈ current\_time() + 9s，如果在處理讀請求時，在租約時間內，則無需發送 Heartbeat 來明確 Leader 身份，直接等待 apply\_index >= commit\_index 後返回請求結果。

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

一致性

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

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

1. 順序記錄中的任何一次讀必須讀到最近一次寫入的數據
2. 順序記錄要跟全局時鐘下的順序保持一致

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

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

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

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

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

腦裂問題

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

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

1. Term機制：時間上保證舊Leader會自動讓位給新Leader
2. 主動stepDown：Leader無法聯繫到過半數節點時主動放棄領導權
3. 嚴格的投票規則：每個term每個節點只能投票給一個候選人

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

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

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

1. 服務可能宕機、停止運行，但過段時間能夠恢復，但不能存在 拜占庭故障
2. 消息可能丟失、延遲亂序或重複；可能有網絡分區，並在一段時間之後恢復

巨人的肩膀

• SOFAJRaft
• The Raft Consensus Algorithm
• TiKV 功能介紹 – Lease Read
• 《深入理解分佈式系統》