01、Xline是什么

Xline 是一款開源的分布式 KV 存儲引擎，其核心目的是實現高性能的跨數據中心強一致性，提供跨數據中心的meatdata 管理。那么 Xline 是怎么實現這種高性能的跨數據中心強一致性的呢？這篇文章就將帶領大家一起來一探究竟。

02、Xline 的整體架構

我們先來看看 Xline 的整體架構，如下圖所示：

從上至下，Xline 可以大致分為三層，分別是

• 接入層：采用 gRPC 框架實現，負責接收來自客戶端的請求。
• 中間層：可以分為 CURP 共識模塊（左）和業務 Server 模塊（右），其中：

?CURP 共識模塊：實現了 CURP 共識算法，代碼上則對應了 Xline 中的 curp 這個 crate，相應的 rpc 服務定義在 curp/proto 中。

?業務 Server 模塊：負責實現 Xline 的上層業務邏輯，如負責 KV 相關請求的 Kv Server 以及負責認證請求的 AuthServer 等。代碼上則對應了 xline 這個 crate，相應的 rpc 服務定義文件保存在 xlineapi 這個 crate 中。

• 存儲層：負責持久化相關的工作，向上層提供抽象接口，代碼上對應了 engine 這個 crate

03、CURP 協議簡介

CURP 是什么？

Xline 中所使用的共識協議，即非 Paxos 而非 Raft，而是一種新的名為 Curp 的共識協議，其全稱為 “Consistent Unordered Replication Protocol”。CURP 協議來自于 NSDI 2019 的一篇 Paper 《Exploiting Commutativity For Practical Fast Replication》，其作者是來自斯坦福的博士生Seo Jin Park和John Ousterhout教授，John Ousterhout教授同時也是raft算法的作者。

為什么選擇 CURP 協議

那為什么 Xline 要使用 CURP 這樣一種新的協議，而非 Raft 或者 Multi-Paxos 來作為底層的共識協議呢？為了說明這個問題，我們不妨先來看看 Raft 以及 Multi-Paxos 都存在什么樣的問題？

下圖是 Raft 協議達成共識的一個時序流程：

在這個時序圖中，我們可以了解到 Raft 協議達成共識的流程：

1. client 需要向 leader 發起一個提案請求。
2. leader 接收到來自 client 的提案請求后，將其追加到自身狀態機日志當中，并向集群中的其他 follower 廣播 AppendEntries 請求。
3. follower 接收到來自 leader 的 AppendEntries 請求后，對其進行日志一致性檢查，判斷是否可以將其添加到自身的狀態機日志當中，是則返回成功響應，否則返回失敗響應。
4. leader 統計所收到的成功響應的數量，如果超過集群節點數量的一半以上，則認為共識已達成，提案成功，否則認為提案失敗，并將結果返回給 client。

下圖是 Multi-Paxos 協議達成共識的一個時序流程：

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

1. client 向 leader 發起一個提案請求。
2. leader 先在自己的狀態機日志上找到第一個沒有被批準的日志條目索引，然后執行 Basic Paxos 算法，對 index 位置的日志用 client 請求的提案值進行提案。
3. follower 接收到來自 leader 發起的提案值后進行決議，接受該提案值則返回成功響應，否則返回失敗。
4. leader 統計所收到的成功響應的數量，如果超過集群節點數量的一半以上，則認為共識已達成，提案成功，否則認為提案失敗，并將結果返回給 client。

從上述時序流程來看，不論是 Multi-Paxos 還是 Raft，要達成共識都必然需要經歷兩次 RTT。之所以是經歷兩次，是因為它們都基于一個核心假設，命令批準/日志提交后都需要同時滿足持久化存儲、有序，狀態機就能直接執行批準后的命令/應用提交后的日志。但由于網絡本身是異步的，無法保證有序性，因此需要 leader 先來執行，以確保不同命令的執行順序（日志索引），并通過廣播獲得過半數節點的復制來確保持久化，這無法在一個 RTT 內完成。

而這也是導致 Xline 不選擇 Raft 或者 Multi-Paxos 作為底層共識算法的根本原因。Xline 在設計之初便立足于跨數據中心的元數據管理。我們都知道，對于單數據中心而言，其內網的延遲往往都非常的小，只有幾毫秒甚至小于 1ms，而對于跨數據中心的廣域網下，其網絡延遲往往可以達到幾十甚至上百毫秒。傳統共識算法，例如 Raft 或者 Multi-Paxos，無論在何種狀態下，達成共識所需要都需要經過 2 個 RTT。在這種高延遲的網絡環境中，傳統的共識算法往往會導致嚴重的性能瓶頸。這不禁引起了我們的思考：任何情況下，兩次及以上的 RTT 是否是達成共識的必要條件嗎？

而CURP 算法是一種無序復制算法，它將達成共識的場景細分成了以下兩類：

fast path: 在無沖突的場景下，在滿足持久化存儲的前提下，放松對共識的有序性要求并不影響最終的共識的達成。由于 fast path 只要求持久化存儲，因此只需要 1 個 RTT 就可以達成共識。我們將 fast path 稱之為協議的前端

slow path：在有沖突的場景下，則需要同時保證并發請求的有序性，及持久化存儲這兩個前提條件，因此需要 2 個 RTT 來達成共識，我們將 slow path 稱之為協議的后端。

那讀者可能就會有疑問了，這里面的沖突究竟指的是什么呢？讓我們用簡單的 KV 操作來舉個例子。在分布式系統的節點上，我們對狀態機所做的操作無非就是讀和寫，在考慮對狀態機的并發操作的情況下，總共可以有讀后讀，讀后寫，寫后讀，寫后寫四種場景。顯然，對于讀后讀這種無副作用的只讀操作而言，任何情況下都不存在沖突，無論是先讀還是后讀，最終讀出來的結果總是一致的。當操作不同的 Key 時，例如 PUT A=1， PUT B=2，那么對于狀態機的最終狀態而言，不論是先執行 PUT A=1，再執行 PUT B=2，還是反過來，最終從狀態機上讀出來的結果都是 A=1，B=2。讀寫混合的場景也是同理，因此當對狀態機并發執行的多個操作之間的 key 不存在交集時，我們稱這些操作都是無沖突的。反之，如果并發多個操作之間包含了至少一個寫操作，同時其操作的 Key 存在交集，這些操作都是沖突的。

fast path 與 slow path

那么 CURP 是如何實現 fast path 和 slow path 的呢？下圖是 CURP 算法中集群拓撲的一個簡圖

讓我們先來看看這張圖中都有哪些內容：

1. Client：向集群發起請求的 client。
2. Master：對應了集群中的 leader 節點。Master 節點中保存了狀態機的日志，其中綠色部分代表的是已經持久化到磁盤當中的日志，而藍色部分則代表的是保存在內存當中的日志。
3. Follower 節點：對應了上圖中黃色虛線框的部分，每個 follower 都包含了一下兩個部分：

a. Witness：本質上可以近似地看成是一個基于內存的 HashMap，一方面負責記錄當前集群中處在 fast path 流程中的請求，另一方面，CURP 也會通過 Witness 來判斷當前的請求是否存在沖突。Witness 中所保存的所有記錄都是無序的。

b. Backup：保存持久化到磁盤中的狀態機日志。

接著，讓我們以圖中的例子 PUT z=7 為例，來看看 fast path 的執行流程：

1. client 向集群中所有節點廣播 PUT z=7 的請求；
2. 集群當中的節點接受到該請求后，根據角色的不同會執行不同的邏輯：

a. leader 接收到請求后，會立刻將數據 z = 7 寫入到本地（也就是狀態機日志中的藍色部分）然后立刻返回 OK。

b. follower 接收到請求后，會通過 witness 判斷請求是否沖突。由于此次 z = 7 并不和 witness 中僅有的 y = 5 沖突，因此 follower 會將 z = 7 保存到 witness 中，并向 client 返回 OK。

3. client 收集并統計所接收到的成功響應的數量。對于一個節點數量為 2f + 1 的集群，當接收到的成功響應達到 f+f/2+1 個時，則確認該操作已經持久化到集群當中，整個過程耗時 1 個 RTT。

接下來，在前面 fast path 例子的基礎上，讓我們以 PUT z = 9 為例，來看看 slow path 的執行流程。由于 z = 9 和前面的 z = 7 相沖突，因此 client 所發起的 fast path 會以失敗告終，并最終執行 slow path，流程如下：

1. client 向集群中所有節點廣播 PUT z=9 的請求；
2. 集群當中的節點接受到該請求后，根據角色的不同會執行不同的邏輯：

a. leader 接收到請求后，將 z = 9 寫入到狀態機日志中。由于 z = 9 與 z = 7 相沖突，向 client 返回 KeyConflict 響應，并異步發起 AppendEntries 請求將狀態機日志同步到集群的其他節點上。

b. follower 接收到請求后，由于 z = 9 與 witness 中的 z = 7 相沖突，因此會拒絕保存這個提案。

3. client 收集并統計所接收到的成功響應的數量，由于接收到的拒絕響應的數量超過了 f/2，client 需要等待 slow path 的完成。
4. 當步驟 2 中 AppendEntries 執行成功，follower 將 leader 的三條狀態機日志（y = 5, z = 7, z=9）都追加到 Backup 后，將 witness 中的相關記錄移除，并向 leader 返回成功響應。
5. leader 統計所收到的成功響應的數量，如果超過集群節點數量的一半以上，則認為共識已達成，提案成功，否則認為提案失敗，并將結果返回給 client。

04、Summary

Xline 是一款提供跨數據中心強一致性的分布式 KV 存儲，其核心問題之一便是如何在跨數據中心這種高延遲的廣域網環境中提供高性能的強一致性保證。傳統的分布式共識算法，如 Raft 和 Multi-Paxos，通過讓所有操作都滿足持久化存儲和有序性前提來保證狀態機一致性。而 CURP 協議則是對達成共識的場景做了更細粒度的劃分，將協議分割成了前端（fast path）和后端（slow path），前端只保證了提案會被持久化到集群當中，而后端不僅保證了持久化，也保證了所有保存了該提案的節點會按照相同的順序執行命令，保證了狀態機的一致性。