基於 Jepsen 來發現幾個 Raft 實現中的一致性問題(2)

2020 年 4 月 15 日
筆記
開發日誌, 技術長文

Nebula Graph 是一個高性能、高可用、強一致的分散式圖資料庫。由於 Nebula Graph 採用的是存儲計算分離架構，在存儲層實際只是暴露了簡單的 kv 介面，採用 RocksDB 作為狀態機，通過 Raft 一致性協議來保證多副本數據一致的問題。Raft 協議雖然比 Paxos 更加容易理解，但在工程實現上還是有很多需要注意和優化的地方。

另外，如何測試基於 Raft 的分散式系統也是困擾業界的問題，目前 Nebula 主要採用了 Jepsen 作為一致性驗證工具。之前我的小夥伴已經在《Jepsen 測試框架在圖資料庫 Nebula Graph 中的實踐》中做了詳細的介紹，對 Jepsen 不太了解的同學可以先移步這篇文章。

在這篇文章中將著重介紹如何通過 Jepsen 來對 Nebula Graph 的分散式 kv 進行一致性驗證。

強一致的定義

首先，我們需要什麼了解叫強一致，它實際就是 Linearizability，也被稱為線性一致性。引用《Designing Data-Intensive Applications》里一書里的定義：

In a linearizable system, as soon as one client successfully completes a write, all clients reading from the database must be able to see the value just written.

也就是說，強一致的分散式系統雖然其內部可能有多個副本，但對外暴露的就好像只有一個副本一樣，客戶端的任何讀請求獲取到的都是最新寫入的數據。

Jepsen 如何檢查系統是否滿足強一致

以一個 Jepsen 測試的 timeline 為例，採用的模型為 single-register，也就是整個系統只有一個暫存器（初始值為空），客戶端只能對該暫存器進行 read 或者 write 操作（所有操作均為滿足原子性，不存在中間狀態）。同時有 4 個客戶端對這個系統發出請求，圖中每一個方框的上沿和下沿代表發出請求的時間和收到響應的時間。

從客戶端的角度來看，對於任何一次請求，服務端處理這個請求可能發生在從客戶端發出請求到接收到對應的結果這段時間的任何一個時間點。可以看到在時間上，客戶端 1/3/4 的三個操作 write 1/write 4/read 1 在時間上實際上是存在 overlap 的，但我們可以通過不同客戶端所收到的響應，確定系統真正的狀態。

由於初始值為空，客戶端 4 的讀請求卻獲取到了 1，說明客戶端 4 的 read 操作一定在客戶端 1 的 write 1 之後，且 write 4 發生在 write 1 之前（否則會讀出 4），則可以確認三個操作實際發生的順序為 write 4 -> write 1 -> read 1。儘管從全局角度看，read 1 的請求最先發出，但實際卻是最後被處理的。後面的幾個操作在時間上是不存在 overlap，是依次發生的，最終客戶端 2 最後讀到了最後一次寫入的 4，整個過程中沒有違反強一致的定義，驗證通過。

如果客戶端 3 的那次 read 獲取到的值是 4，那麼整個系統就不是強一致的了，因為根據之前的分析，最後一次成功寫入的值為 1，而客戶端 3 卻讀到了 4，是一個過期的值，也就違背了線性一致性。事實上，Jepsen 也是通過類似的演算法來驗證分散式系統是否滿足強一致的。

通過 Jepsen 的一致性驗證找到對應問題

我們先簡單介紹一下 Nebula Raft 裡面處理一個請求的流程（以三副本為例），以便更好地理解後面的問題。讀請求相對簡單，由於客戶端只會將請求發送給 leader，leader 節點只需要在確保自己是 leader 的前提下，直接從狀態機獲取對應結果返回給客戶端即可。

寫請求的流程則複雜一些，如 Raft Group 圖所示：

Leader（圖中綠色圈）收到 client 發送的 request，寫入到自己的 wal（write ahead log）中。
Leader將 wal 中對應的 log entry 發送給 follower，並進入等待。
Follower 收到 log entry 後寫入自己的 wal 中(不等待應用到狀態機)，並返回成功。
Leader 接收到至少一個 follower 返回成功後，應用到狀態機，向 client 發送 response。

下面我將用示例來說明通過 Jepsen 測試在之前的Raft實現中發現的一致性問題：

如上圖所示，ABC 組成一個三副本 raft group，圓圈為狀態機（為了簡化，假設其為一個 single-register），方框中則是保存的相應 log entry。

在初始狀態，三個副本中的狀態機中都為 1，Leader 為 A，term為 1
客戶端發送了 write 2 的請求，Leader 根據上面的流程進行處理，在向 client 告知寫入成功後被 kill。（step 4 完成後）
此後 C 被選為 term 2 的 leader，但由於 C 此時有可能還沒有將之前 write 2 的 log entry 應用到狀態機（此時狀態機中仍為1）。如果此時 C 接受到客戶端的讀請求，那麼 C 會直接返回 1。這違背了強一致的定義，之前已經成功寫入 2，卻讀到了過期的結果。

這個問題是出在 C 被選為 term 2 的 leader 後，需要發送心跳來保證之前 term 的 log entry 被大多數節點接受，在這個心跳成功之前是不能對外提供讀（否則可能會讀到過期數據）。有興趣的同學可以參考 raft parer 中的 Figure 8 以及 5.4.2 小節。

從上一個問題出發，通過 Jepsen 我們又發現了一個相關的問題：leader 如何確保自己還是 leader？這個問題經常出現在網路分區的時候，當 leader 因為網路問題無法和其他節點通訊從而被隔離後，此時如果仍然允許處理讀請求，有可能讀到的就是過期的值。為此我們引入了 leader lease 的概念。

當某個節點被選為 leader 之後，該節點需要定期向其他節點發送心跳，如果心跳確認大多數節點已經收到，則獲取一段時間的租約，並確保在這段時間內不會出現新的 leader，也就保證該節點的數據一定是最新的，從而在這段時間內可以正常處理讀請求。

和 TiKV 的處理方法不同的是，我們沒有採取心跳間隔乘以係數作為租約時間，主要是考慮到不同機器的時鐘漂移不同的問題。而是保存了上一次成功的 heartbeat 或者 appendLog 所消耗的時間 cost，用心跳間隔減去 cost 即為租約時間長度。

當發生網路分區時， leader 儘管被隔離，但是在這個租約時間仍然可以處理讀請求（對於寫請求，由於被隔離，都會告知客戶端寫入失敗），超出租約時間後則會返回失敗。當 follower 在至少一個心跳間隔時間以上沒有收到 leader 的消息，會發起選舉，選出新 leader 處理後續的客戶端請求。

結語

對於一個分散式系統，很多問題需要長時間的壓力測試和故障模擬才能發現，通過 Jepsen 能夠在不同注入故障的情況下驗證分散式系統。之後我們也會考慮採用其他混沌工程工具來驗證 Nebula Graph，在保證數據高可靠的前提下不斷提高性能。

本文中如有錯誤或疏漏歡迎去 GitHub：//github.com/vesoft-inc/nebula issue 區向我們提 issue 或者前往官方論壇：//discuss.nebula-graph.com.cn/ 的 建議回饋 分類下提建議 👏；加入 Nebula Graph 交流群，請聯繫 Nebula Graph 官方小助手微訊號：NebulaGraphbot