淺談分佈式存儲之 Raft，有點幹~~

分佈式一致性是分佈式系統中最基本的問題，用來保證分佈式系統的高可靠。業界也有很多分佈式一致性複製協議：Paxos、Zab、Viewstamped Replication、Raft 等。Raft 相比於其他共識算法簡化了協議中的狀態以及交互，更加清晰也更加容易理解實現。

1. Raft 概述

Raft 節點有 3 種角色：

Raft 信息有 3 種 RPC：

1.1 Leader 選舉

Raft 將時間劃分爲一個個的任期（Term），TermID 單調遞增，每個 Term 最多隻有一個 Leader。

Candidate 先將本地的 currentTerm++，然後向其他節點發送 RequestVote 請求。其他節點根據本地數據版本、長度和之前選主的結果判斷應答成功與否。具體處理規則如下：

currentTerm 只是用於忽略老的 Term 的 vote 請求，或者提升自己的 currentTerm，並不參與 Log 新舊的決策。Log 新舊的比較，是基於 lastLogTerm 和 lastLogIndex 進行比較，而不是基於 currentTerm 和 lastLogIndex 進行比較。

關於選舉有兩個很重要的隨機超時時間：心跳超時、選舉超時。

心跳超時要小於選舉超時一個量級，Leader 才能夠發送穩定的心跳消息來阻止 Follower 開始進入選舉狀態。可以設置：心跳超時 = peers max RTT(round-trip time)，選舉超時 = 10 * 心跳超時。

1.2 Log 複製

大致流程是：更新操作通過 Leade r 寫入 Log，複製到多數節點，變爲 Committed，再 Apply 業務狀態機。

  1. Leader 首先要把這個指令追加到 log 中形成一個新的 entry；

  2. 然後通過 AppendEntries RPC 並行地把該 entry 發給其他 servers；

  3. 其他 server 如果發現沒問題，複製成功後會給 Leader 一個表示成功的 ACK；

  4. Leader 收到大多數 ACK 後 Apply 該日誌，返回客戶端執行結果。

如果 Followers crash 或者丟包，Leader 會不斷重試 AppendEntries RPC。

每個 log entry 都存儲着一條用於狀態機的指令，同時保存着從 Leader 收到該 entry 時的 Term，此外還有 index 指明自己在 Log 中的位置。可以被 Apply 的 entry 叫做 committed，一個 log entry 一旦複製給了大多數節點就成爲 committed，committed 的 log 最終肯定會被 Apply。

如果當前待提交 entry 之前有未提交的 entry，即使是以前過時的 leader 創建的，只要滿足已存儲在大多數節點上就一次性按順序都提交。

1.3 Log 恢復

Log Recovery 分爲 currentTerm 修復和 prevTerm 修復。Log Recovery 就是要保證一定已經 Committed 的數據不會丟失，未 Committed 的數據轉變爲 Committed，但不會因爲修復過程中斷又重啓而影響節點之間一致性。

currentTerm 修復主要是解決某些 Follower 節點重啓加入集羣，或者是新增 Follower 節點加入集羣，Leader 需要向 Follower 節點傳輸漏掉的 Log Entry。如果 Follower 需要的 Log Entry 已經在 Leader 上 Log Compaction 清除掉了，Leader 需要將上一個 Snapshot 和其後的 Log Entry 傳輸給 Follower 節點。Leader-Alive 模式下，只要 Leader 將某一條 Log Entry 複製到多數節點上，Log Entry 就轉變爲 Committed。

prevTerm 修復主要是在保證 Leader 切換前後數據的一致性。通過上面 RAFT 的選主可以看出，每次選舉出來的 Leader 一定包含已經 committed 的數據（抽屜原理，選舉出來的 Leader 是多數中數據最新的，一定包含已經在多數節點上 commit 的數據）。新的 Leader 將會覆蓋其他節點上不一致的數據。雖然新選舉出來的 Leader 一定包括上一個 Term 的 Leader 已經 Committed 的 Log Entry，但是可能也包含上一個 Term 的 Leader 未 Committed 的 Log Entry。這部分 Log Entry 需要轉變爲 Committed，即通過 Noop。

Leader 爲每個 Follower 維護一個 nextId，標識下一個要發送的 logIndex。Leader 通過回溯尋找 Follower 上最後一個 CommittedId，然後 Leader 發送其後的 LogEntry。

重新選取 Leader 之後，新的 Leader 沒有之前內存中維護的 nextId，以本地 lastLogIndex+1 作爲每個節點的 nextId。這樣根據節點的 AppendEntries 應答可以調整 nextId：

local.nextIndex = max(min(local.nextIndex-1, resp.LastLogIndex+1), 1)

1.4 Log 壓縮

在實際系統中，Log 會無限制增長，導致 Log 佔用太多的磁盤空間，需要更長的啓動時間來加載，將會導致系統不可用。需要對日誌做壓縮。

Snapshot 是 Log Compaction 的常用方法，將系統的全部狀態寫入一個 Snapshot 中，並持久化到一個可靠存儲系統中，完成 Snapshot 之後這個點之前的 Log 就可以被刪除了。

1.5 成員變更

當 Raft 集羣進行節點變更時，新加入的節點可能會因爲需要花費很長時間同步 Log 而降低集羣的可用性，導致集羣無法 commit 新的請求。

假設原來集羣有 3 個節點，可以容忍 3 - (3/2+1) = 11 個節點出錯，這時由於機器維修、增加副本解決熱點讀等原因又新加入了一個節點，這時也是可以容忍 4 - (4/2+1) = 11 個節點出錯，恰好原來的一個節點出錯了，此時雖然可以 commit 但是得等到新的節點完全追上 Leader 的日誌纔可以，而新節點追上 Leader 日誌花費的時間比較長，在這期間就沒法 commit，會降低系統的可用性。

爲了避免這個問題，引入了節點的 Learner 狀態，當集羣成員變更時，新加入的節點爲 Learner 狀態，Learner 狀態的節點不算在 Quorum 節點內，不能參與投票；只有 Leader 確定這個 Learner 節點接收完了 Snapshot，可以正常同步 Log 了，纔可能將其變成可以正常的節點。

1.6 安全性

2. 功能完善

2.1 預選舉

預選舉（Pre-Vote）主要避免了網絡分區節點加入集羣時，引起集羣中斷服務的問題。

Follower 在轉變爲 Candidate 之前，先與集羣節點通信，獲得集羣 Leader 是否存活的信息。如果當前集羣有 Leader 存活，Follower 就不會轉變爲 Candidate，也不會增加 Term，就不會引起 Leader StepDown，從而不會導致集羣選主中斷服務。

2.2 Leader 轉移

Leader 轉移可以把當前 Raft Group 中的 Leader 轉換給另一個 Follower，可用於負載均衡、重啓機器等。

在進行 transfer leadership 時，先 block 當前 Leader 的寫入，然後使 Transferee 節點日誌達到 Leader 的最新狀態，進而發送 TimeoutNow 請求，觸發 Transferee 節點立即選主。

但是不能無限制的 block Leader 的寫入，會影響線上服務。通常可以爲 transfer leadership 設置一個超時時間。超時之後如果發現 Transferee 節點 Term 沒有發生變化，說明 Transferee 節點沒有追上數據，沒有選主成功，transfer leadership 就失敗了。

2.3 網絡分區

網絡分區主要包含對稱網絡分區（Symmetric network partitioning）和非對稱網絡分區（Asymmetric network partitioning）。

對稱網絡分區

S1 爲當前 Leader，網絡分區造成 S2 和 S1、S3 心跳中斷。S2 既不會被選成 Leader，也不會收到 Leader 的消息，而是會一直不斷地發起選舉。Term 會不斷增大。爲了避免網絡恢復後，S2 發起選舉導致正在工作的 Leader step-down，從而導致整個集羣重新發起選舉，可以使用 pre-vote 來阻止對稱網絡分區節點在重新加入時，會中斷集羣的問題。因爲發生對稱網絡分區後的節點，pre-vote 不會成功，也就不會導致集羣一段時間內無法正常提供服務的問題。

非對稱網絡分區

S1、S2、S3 分別位於三個 IDC，其中 S1 和 S2 之間網絡不通，其他之間可以聯通。這樣一旦 S1 或者是 S2 搶到了 Leader，另外一方在超時之後就會觸發選主，例如 S1 爲 Leader，S2 不斷超時觸發選主，S3 提升 Term 打斷當前 Lease，從而拒絕 Leader 的更新。

可以增加一個 trick 的檢查，每個 Follower 維護一個時間戳記錄收到 Leader 上數據更新的時間，只有超過 ElectionTimeout 之後才允許接受 Vote 請求。這個類似 ZooKeeper 中只有 Candidate 才能發起和接受投票，就可以保證 S1 和 S3 能夠一直維持穩定的 quorum 集合，S2 不能選主成功。

2.4 SetPeer

Raft 只能在多數節點存活的情況下才可以正常工作，在實際環境中可能會存在多數節點故障只存活一個節點的情況，這個時候需要提供服務並修復數據。因爲已經不能達到多數，不能寫入數據，也不能做正常的節點變更。Raft 庫需要提供一個 SetPeer 的接口，設置每個節點的複製組節點列表，便於故障恢復。

假設只有一個節點 S1 存活的情況下，SetPeer 設置節點列表爲 {S1}，這樣形成一個只有 S1 的節點列表，讓 S1 繼續提供讀寫服務，後續再調度其他節點進行 AddPeer。通過強制修改節點列表，可以實現最大可用模式。

2.5 Noop

在分佈式系統中，對於一個請求都有三種返回結果：成功、失敗、超時。

在 failover 時，新的 Leader 由於沒有持久化 commitIndex，所以並不清楚當前日誌的 commitIndex 在哪，也即不清楚 log entry 是 committed 還是 uncommitted 狀態。通常在成爲新 Leader 時提交一條空的 log entry 來提交之前所有的 entry。

RAFT 中增加了一個約束：對於之前 Term 的未 Committed 數據，修復到多數節點，且在新的 Term 下至少有一條新的 Log Entry 被複制或修復到多數節點之後，才能認爲之前未 Committed 的 Log Entry 轉爲 Committed。即最大化 commit 原則：Leader 在當選後立即追加一條 Noop 並同步到多數節點，實現之前 Term uncommitted 的 entry 隱式 commit。

2.6 MultiRaft

元數據相比數據來說整體數據量要小的多，通常單臺機器就可以存儲。我們也通常藉助於 Etcd 等使用單個 Raft Group 來進行元數據的複製和管理。但是單個 Raft Group，存在以下兩點弊端：

對於集羣元數據來說使用單個 Raft Group 是夠了，但是如果想讓 Raft 用於數據的複製，那麼必須得使用 MultiRaft，也即有多個複製組，類似於 Ceph 的 PG，每個 PG、Raft Group 是一個複製組。

但是 Raft Group 的每個副本間都會建立鏈接來保持心跳，如果多個 Raft Group 裏的副本都建立鏈接的話，那麼物理節點上的鏈接數就太多了，需要複用物理節點的鏈接。如下圖 cockroachdb multi raft 所示：

MultiRaft 還需要解決以下問題：

3. 性能優化

3.1 Batch

Batch 並不會對請求做延遲來達到批量處理的目的，對單個請求的延遲沒有影響。

3.2 PipeLine

Raft 依賴 Leader 來保持集羣的數據一致性，數據的複製都是從 Leader 到 Follower。一個簡單的寫入流程如下，性能是完全不行的：

  1. Leader 收到 Client 請求；

  2. Leader 將數據 Append 到自己的 Log；

  3. Leader 將數據發送給其他的 Follower；

  4. Leader 等待 Follower ACK，大多數節點提交了 Log，則 Apply；

  5. Leader 返回 Client 結果；

  6. 重複步驟 1。

Leader 跟其他節點之間的 Log 同步是串行 Batch 的方式，如果單純使用 Batch，每個 Batch 發送之後 Leader 依舊需要等待該 Batch 同步完成之後才能繼續發送下一個 Batch，這樣會導致較長的延遲。可以通過 Leader 跟其他節點之間的 PipeLine 複製來改進，會有效降低延遲。

3.3 並行

順序提交

將 Leader Append 持久化日誌和向 Followers 發送日誌並行處理。Leader 只需要在內存中保存未 Committed 的 Log Entry，在多數節點已經應答的情況下，無需等待 Leader 本地 IO 完成，直接將內存中的 Log Entry 直接 Apply 給狀態機即可。

亂序提交

亂序提交要滿足以下兩點：

上層不同的應用場景限制了提交的方式：

不同的分佈式存儲需要的提交方式：

簡單分析

單個 Raft Group 只能順序提交日誌，多個 Raft Group 之間雖然可以做到並行提交日誌，但是受限於上層應用（數據庫等）的跨 Group 分佈式事物，可能導致其他不相關的分佈式事物不能並行提交，只能順序提交。

上層應用比如數據庫的分佈式事物是跨 Group(A、B、C) 的，Group A 被阻塞了，分佈式事務不能提交， 那麼所有的參與者 Group(B、C) 就不能解鎖，進而不能提交其他不相關的分佈式事物，從而引發多個 Group 的鏈式反應。

Raft 不適用於多連接的高併發環境中。Leader 和 Follower 維持多條連接的情況在生產環境也很常見，單條連接是有序的，多條連接並不能保證有序，有可能發送次序靠後的 Log Entry 先於發送次序靠前的 Log Entry 達到 Follower。但是 Raft 規定 Follower 必須按次序接受 Log Entry，就意味着即使發送次序靠後的 Log Entry 已經寫入磁盤了（實際上不能落盤得等之前的 Log Entry 達到）也必須等到前面所有缺失的 Log Entry 達到後才能返回。如果這些 Log Entry 是業務邏輯順序無關的，那麼等待之前未到達的 Log Entry 將會增加整體的延遲。

其實 Raft 的日誌複製和 Ceph 基於 PG Log 的複製一樣，都是順序提交的，雖然可以通過 Batch、PipeLine 優化，但是在併發量大的情況下延遲和吞吐量仍然上不去。

具體 Raft 亂序提交的實現可參考：PolarFS: ParallelRaft

http://www.vldb.org/pvldb/vol11/p1849-cao.pdf

3.4 異步

我們知道被 committed 的日誌肯定是可以被 Apply 的，在什麼時候 Apply 都不會影響數據的一致性。所以在 Log Entry 被 committed 之後，可以異步的去 Apply 到業務狀態機，這樣就可以並行的 Append Log 和 Apply Log 了，提升系統的吞吐量。

其實就和 Ceph BlueStore 的 kv_sync_thread 和 kv_finalize_thread 一樣，每個線程都有其隊列。kv_sync_thread 去寫入元數據到 RocksDB（請求到此已經成功），kv_finalize_thread 去異步的回調上層應用通知請求成功。

3.5 ReadIndex

Raft 的寫入流程會走一遍 Raft，保證了數據的一致性。爲了實現線性一致性讀，讀流程也可以走一遍 Raft，但是會產生磁盤 IO，性能不好。Leader 具有最新的數據，理論上 Leader 可以讀取到最新的數據。但是在網絡分區的情況下，無法確定當前的 Leader 是不是真的 Leader，有可能當前 Leader 與其他節點發生了網絡分區，其他節點形成了一個 Group 選舉了新的 Leader 並更新了一些數據，此時如果 Client 還從老的 Leader 讀取數據，便會產生 Stale Read。

讀流程走一遍 Raft、ReadIndex、Lease Read 都是用來實現線性一致性讀，避免 Stale Read。

  1. 當收到讀請求時，Leader 先檢查自己是否在當前 Term commit 過 entry，沒有否則直接返回；

  2. 然後，Leader 將自己當前的 commitIndex 記錄到變量 ReadIndex 裏面；

  3. 向 Follower 發起 Heartbeat，收到大多數 ACK 說明自己還是 Leader；

  4. Leader 等待 applyIndex >= ReadIndex，就可以提供線性一致性讀；

  5. 返回給狀態機，執行讀操作返回結果給 Client。

線性一致性讀：在 T1 時刻寫入的值，在 T1 時刻之後肯定可以讀到。也即讀的數據必須是讀開始之後的某個值，不能是讀開始之前的某個值。不要求返回最新的值，返回時間大於讀開始的值就可以。

注意：在新 Leader 剛剛選舉出來 Noop 的 Entry 還沒有提交成功之前，是不能夠處理讀請求的，可以處理寫請求。也即需要步驟 1 來防止 Stale Read。

原因：在新 Leader 剛剛選舉出來 Noop 的 Entry 還沒有提交成功之前，這時候的 commitIndex 並不能夠保證是當前整個系統最新的 commitIndex。

考慮這個情況：

因爲 commitIndex 之後可能還有 Log Entry 對該值更新，只要 w1Apply 到業務狀態機就可以滿足 applyIndex >= ReadIndex，此時就可以返回 w1 的值。但是此時 w2、w3 還未 Apply 到業務狀態機，就沒法返回 w3，就會產生 Stale Read。必須等到 Noop 執行完纔可以執行讀，纔可以避免 Stale Read。

3.6 Follower Read

如果是熱點數據麼可以通過提供 Follower Read 來減輕 Leader 的讀壓力，可用非常方便的通過 ReadIndex 實現。

  1. Follower 向 Leader 請求 ReadIndex；

  2. Leader 執行完 ReadIndex 章節的前 4 步（用來確定 Leader 是真正的 Leader）；

  3. Leader 返回 commitIndex 給 Follower 作爲 ReadIndex；

  4. Follower 等待 applyIndex >= ReadIndex，就可以提供線性一致性讀；

  5. 返回給狀態機，執行讀操作返回結果給 Client。

3.7 Lease Read

Lease Read 相比 ReadIndex 更進一步，不僅省去了 Log  的磁盤開銷，還省去了 Heartbeat 的網絡開銷，提升讀的性能。

基本思路

Leader 獲取一個比 election timeout 小的租期（Lease）。因爲 Follower 至少在 election timeout 時間之後纔會發送選舉，那麼在 Lease 內是不會進行 Leader 選舉。就可以跳過 ReadIndex 心跳的環節，直接從 Leader 上讀取。但是 Lease Read 的正確性是和時間掛鉤的，如果時鐘漂移比較嚴重，那麼 Lease Read 就會產生問題。

  1. Leader 定時發送（心跳超時時間）Heartbeat 給 Follower， 並記錄時間點 start；

  2. 如果大多數迴應，那麼新的 Lease 到期時間爲 start + Lease(<election timeout)；

  3. Leader 確認自己是 Leader 後，等待 applyIndex >= ReadIndex，就可以提供線性一致性讀；

  4. 返回給狀態機，執行讀操作返回結果給 Client。

3.8 Double Write-Store

我們知道 Raft 把數據 Append 到自己的 Log 的同時發送請求給 Follower，多數回覆 ACK 就認爲 commit，就可以 Apply 到業務狀態機了。如果業務狀態機（分佈式 KV、分佈式對象存儲等）也把數據持久化存儲，那麼數據便 Double Write-Store，集羣中存在兩份相同的數據。如果是三副本，那麼就會有 6 份。

接下來主要思考元數據、數據做的一點點優化。

通常的一個優化方式就是先把數據寫入 Journal（環形隊列、大小固定、空間連續、使用 3D XPoint、NVME），然後再把數據寫入內存即可返回，最後異步的把數據刷入 HDD（最好帶有 NVME 緩存）。

元數據

元數據通常使用分佈式 KV 存儲，數據量比較小，Double Write-Store 影響不是很大，即使存儲兩份也不會浪費太多空間，而且以下改進也相比數據方面的改進更容易實現。

可以擼一個簡單的 Append-Only 的單機存儲引擎 WAL 來替代 RocksDB 作爲 Raft Log 的存儲引擎，Apply 業務狀態機層的存儲引擎可以使用 RocksDB，但是可以關閉 RocksDB 的 WAL，因爲數據已經存儲在 Append-Only 的 Raft Log 了，細節仍需考慮。

數據

這裏的數據通常指非結構化數據：圖片、文檔、音視頻等。非結構化數據通常使用分佈式對象存儲、塊存儲、文件存儲等來存儲，由於數據量比較大，Double Store 是不可接受的，大致有兩種思路去優化：

參考資源

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/5pzk4ltA6YrgObUgX9RCHg

猜你喜歡