CURP 協議簡介

什麼是 Xline

Xline 是一個開源的分佈式 KV 存儲引擎，其核心目的是實現跨數據中心的高性能強一致性，提供跨數據中心的元數據管理。那麼 Xline 是如何實現這種跨數據中心的高性能強一致性呢？本文將帶領您一探究竟。

Xline 整體架構

我們先看一下 Xline 的整體架構，如下圖：

從上到下，Xline 大致可以分爲三層，即

• 接入層：使用 gRPC 框架實現，負責接收客戶端的請求。

• 中間層：可分爲 CURP 共識模塊（左）和業務服務器模塊（右），其中：

• CURP 共識模塊：實現 CURP 共識算法，代碼對應 Xline 中的 curp crate，而對應的 RPC 服務定義在 curp/proto 中。

• 業務服務器模塊：負責實現 Xline 的上層業務邏輯，比如 KV 相關請求的 KvServer、認證請求的 AuthServer 等。代碼對應 xline crate，而對應的 RPC 服務定義在 xlineapi 箱。

• 存儲層：負責 Xline 內部數據和元數據的持久化，向上層提供抽象接口，代碼對應引擎 crate。

CURP 協議簡介

什麼是 CURP？

Xline 中使用的共識協議不是 Paxos 或 Raft，而是一種名爲 CURP 的新共識協議，它被稱爲 “一致無序複製協議（CURP）”。它起源於 NSDI 2019 的論文《Exploiting Commutativity For Practical Fast Replication》，該論文的作者是斯坦福大學博士生 Seo Jin Park 和 Raft 算法的作者 John Ousterhout 教授。

爲什麼選擇 CURP 協議？

爲什麼 Xline 使用 CURP 這樣的新協議而不是 Raft 或 Multi-Paxos 作爲底層共識協議？爲了說明這一點，我們來看一下 Raft 和 Multi-Paxos 的問題。

下圖展示了 Raft 的共識流程：

在這個時序圖中，我們可以看到 Raft 協議是如何達成共識的：

1. 客戶向領導提出建議請求。

2. 領導者接收來自客戶端的提議請求，將其附加到其狀態機日誌中，並將 AppendEntries 請求廣播給集羣中的其他追隨者。

3. follower 收到 leader 的 AppendEntries 請求後，會進行日誌一致性檢查，以確定是否可以添加到自己的狀態機日誌中。如果檢查成功，則返回成功消息；如果檢查失敗，則返回失敗消息。

4. Leader 統計收到的成功響應的數量，如果超過集羣節點數的一半，則認爲達成共識，提案成功，否則認爲提案失敗，並將結果返回給客戶端。

下圖展示了 Multi-Paxos 協議達成共識的流程：

在這個時序圖中，我們可以瞭解 Multi-Paxos 協議達成共識的流程：

1. 客戶向領導提出建議請求。

2. 領導者在其狀態機日誌中找到第一個未批准的日誌條目的索引，然後執行 Basic Paxos 算法以客戶端請求的建議值提議索引處的日誌。

3. follower 接收 leader 發送的 proposal 值，並決定是接受 proposal 值並返回成功的響應，還是返回失敗的響應。

4. Leader 統計收到的成功響應的數量，如果超過集羣節點數的一半，則認爲已達成共識，提案成功，否則認爲提案失敗，返回結果給客戶。

5. 無論是 Multi-Paxos 還是 Raft，達成共識都不可避免地需要 2 個 RTT。兩者都基於一個核心假設：在命令批准或日誌提交後必須滿足持久存儲和排序的標準。因此，狀態機可以直接執行批准的命令或應用提交的日誌。由於網絡固有的異步性，確保有序性具有挑戰性。因此，領導者需要強制執行不同命令的執行順序，並通過廣播獲得多數人的複製來實現持久化。此過程無法在單個 RTT 內完成。

這就是爲什麼 Xline 沒有選擇 Raft 或者 Multi-Paxos 作爲底層共識算法。Xline 主要設計用於管理跨數據中心的元數據。衆所周知，對於單個數據中心來說，其內網的延遲往往很低，只有幾毫秒甚至不到 1 毫秒，而對於跨數據中心的廣域網來說，網絡延遲可以達到幾十毫秒或幾十毫秒。甚至數百毫秒。傳統共識算法，如 Raft 或 Multi-Paxos，無論共識狀態如何，都需要 2 個 RTT 才能達成共識，這在此類高延遲網絡環境中往往會導致嚴重的性能瓶頸。這讓我們想知道是否需要兩次或多次 RTT 才能在任何情況下達成共識。

CURP 算法是一種無序複製算法，將共識場景分爲以下兩類：

• 快速路徑：在不衝突的場景下，在持久化存儲的前提下，放寬共識的排序要求，不影響最終的共識。由於快速路徑只需要存儲持久性，因此只需要 1 個 RTT 即可達成共識。我們將快速路徑稱爲協議的前端。

• 慢路徑：衝突場景下，需要同時滿足有序併發請求和持久化存儲的需求，需要 2 個 RTT 才能達成共識。我們將慢速路徑稱爲協議的後端。

那麼讀者可能會想，這裏到底有什麼衝突呢？我們以一個簡單的 KV 操作爲例。在分佈式系統的節點中，我們對狀態機進行的操作只是讀寫，而對狀態機進行併發操作的情況下，有四種場景：read-after-read、read-after-write 、先讀後寫和先寫後寫。顯然，對於 read-after-read 這種只讀操作，沒有任何副作用，在任何情況下都不會發生衝突，而且無論是先讀還是後讀，最終的結果總是相同的。當對不同的按鍵進行操作時，例如 PUT A=1，PUT B=2，那麼對於狀態機的最終狀態，無論是先執行 PUT A=1，再執行 PUT B=2，還是反之亦然，從狀態機讀取的最終結果是 A=1，B=2。對於讀寫混合的場景也是如此。因此，當一個狀態機上同時執行的多個操作的鍵之間不存在交集時，我們說這些操作是不衝突的。相反，如果併發操作包括至少一個寫操作，並且這些操作的鍵相交，則這些操作是衝突的。

快速路徑與慢速路徑

CURP 如何實現快路徑和慢路徑？下面是 CURP 算法中集羣拓撲的草圖。

讓我們看看這張圖中發生了什麼：

1. Client：向集羣發出請求的客戶端。

2. Master：對應集羣中的 Leader 節點，保存着狀態機日誌，其中綠色部分代表已經持久化到磁盤的日誌，藍色部分代表存儲在內存中的日誌。

3. Follower 節點：對應上圖中黃色虛線框，每個 follower 包含以下兩個組件。

• A. Witness：可以近似爲一個基於內存的 HashMap，一方面負責在快速路徑過程中記錄集羣中當前的請求，另一方面 CURP 也會利用 Witness 來判斷是否存在當前請求中存在衝突。Witness 中保存的所有記錄都是無序的。

• B. 備份：將狀態機日誌保存到磁盤。

接下來我們以圖中 PUT z=7 爲例，看看快速路徑的執行流程：

1. 客戶端向集羣中的所有節點廣播 PUT z=7 的請求。

2. 當集羣中的節點收到請求時，它會根據自己的角色執行不同的邏輯。

• A.Leader 收到請求，立即將數據 z=7 寫入本地（即狀態機日誌中的藍色部分），並立即返回 OK。

• B. 當 follower 收到請求時，會使用 witness 來判斷該請求是否存在衝突。由於 z = 7 與見證人中唯一的 y = 5 不衝突，因此 follower 將 z = 7 保存到見證人中，並向客戶端返回 OK。

3. 客戶端收集並計算收到的成功響應的數量。對於 2f+1 個節點的集羣，當收到的成功響應數量達到 f+f/2+1 時，該操作被確認持久化到集羣中，整個過程需要 1 個 RTT。

接下來，在前面的快速路徑示例的基礎上，我們以 PUT z = 9 爲例來看看慢速路徑的執行流程。由於 z=9 與 z=7 衝突，客戶端發起的快路徑將會失敗，而執行慢路徑：

1. 客戶端向集羣中的所有節點廣播 PUT z=9 請求。

2. 集羣中的節點接收請求並根據各自的角色執行不同的邏輯。

• 領導者收到請求並將 z = 9 寫入狀態機日誌。由於 z = 9 與 z = 7 衝突，因此向客戶端返回 KeyConflict 響應，並異步發起 AppendEntries 請求，將狀態機日誌同步到集羣中的其他節點。

• follower 收到請求並拒絕保存提案，因爲 z = 9 與見證人中的 z = 7 衝突。

3. 客戶端收集並計算收到的成功響應的數量。由於收到的拒絕響應數量超過 f/2，客戶端需要等待慢速路徑完成。

4. 當步驟 2 中的 AppendEntries 執行成功後，follower 將 leader 的所有三個狀態機日誌（y = 5, z = 7, z = 9）追加到 Backup 中，並從 witness 中刪除相關日誌，並返回成功給領導的答覆。

5. 領導者計算收到的成功響應的數量。如果超過集羣節點數的一半，則認爲達成共識，提案成功。否則，提案失敗，結果返回給客戶端。

概括

Xline 是一種分佈式 KV 存儲，可提供跨數據中心的強一致性。其核心問題之一是如何在跨數據中心的高延遲廣域網環境中提供高性能強一致性。傳統的分佈式共識算法，例如 Raft 和 Multi-Paxos，通過使所有操作滿足存儲持久性和排序前提來保證狀態機一致性。CURP 協議，對共識場景進行了更細粒度的劃分，將協議分爲前端（快路徑）和後端（慢路徑），其中前端僅保證提案會持久化到集羣，而後端不僅保證持久化，還保證所有保存了提案的節點都會按照相同的順序執行命令，CURP 協議的介紹到此結束。更多詳情請參考 GitHub 鏈接：

https://github.com/xline-kv/Xline

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