01、Xline是什么

Xline 是一款開源的分布式 KV 存儲(chǔ)引擎，其核心目的是實(shí)現(xiàn)高性能的跨數(shù)據(jù)中心強(qiáng)一致性，提供跨數(shù)據(jù)中心的meatdata 管理。那么 Xline 是怎么實(shí)現(xiàn)這種高性能的跨數(shù)據(jù)中心強(qiáng)一致性的呢？這篇文章就將帶領(lǐng)大家一起來一探究竟。

02、Xline 的整體架構(gòu)

我們先來看看 Xline 的整體架構(gòu)，如下圖所示：

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

• 接入層：采用 gRPC 框架實(shí)現(xiàn)，負(fù)責(zé)接收來自客戶端的請(qǐng)求。
• 中間層：可以分為 CURP 共識(shí)模塊（左）和業(yè)務(wù) Server 模塊（右），其中：

?CURP 共識(shí)模塊：實(shí)現(xiàn)了 CURP 共識(shí)算法，代碼上則對(duì)應(yīng)了 Xline 中的 curp 這個(gè) crate，相應(yīng)的 rpc 服務(wù)定義在 curp/proto 中。

?業(yè)務(wù) Server 模塊：負(fù)責(zé)實(shí)現(xiàn) Xline 的上層業(yè)務(wù)邏輯，如負(fù)責(zé) KV 相關(guān)請(qǐng)求的 Kv Server 以及負(fù)責(zé)認(rèn)證請(qǐng)求的 AuthServer 等。代碼上則對(duì)應(yīng)了 xline 這個(gè) crate，相應(yīng)的 rpc 服務(wù)定義文件保存在 xlineapi 這個(gè) crate 中。

• 存儲(chǔ)層：負(fù)責(zé)持久化相關(guān)的工作，向上層提供抽象接口，代碼上對(duì)應(yīng)了 engine 這個(gè) crate

03、CURP 協(xié)議簡(jiǎn)介

CURP 是什么？

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

為什么選擇 CURP 協(xié)議

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

下圖是 Raft 協(xié)議達(dá)成共識(shí)的一個(gè)時(shí)序流程：

在這個(gè)時(shí)序圖中，我們可以了解到 Raft 協(xié)議達(dá)成共識(shí)的流程：

1. client 需要向 leader 發(fā)起一個(gè)提案請(qǐng)求。
2. leader 接收到來自 client 的提案請(qǐng)求后，將其追加到自身狀態(tài)機(jī)日志當(dāng)中，并向集群中的其他 follower 廣播 AppendEntries 請(qǐng)求。
3. follower 接收到來自 leader 的 AppendEntries 請(qǐng)求后，對(duì)其進(jìn)行日志一致性檢查，判斷是否可以將其添加到自身的狀態(tài)機(jī)日志當(dāng)中，是則返回成功響應(yīng)，否則返回失敗響應(yīng)。
4. leader 統(tǒng)計(jì)所收到的成功響應(yīng)的數(shù)量，如果超過集群節(jié)點(diǎn)數(shù)量的一半以上，則認(rèn)為共識(shí)已達(dá)成，提案成功，否則認(rèn)為提案失敗，并將結(jié)果返回給 client。

下圖是 Multi-Paxos 協(xié)議達(dá)成共識(shí)的一個(gè)時(shí)序流程：

在這個(gè)時(shí)序圖中，我們可以了解到 Multi-Paxos 協(xié)議達(dá)成共識(shí)的流程：

1. client 向 leader 發(fā)起一個(gè)提案請(qǐng)求。
2. leader 先在自己的狀態(tài)機(jī)日志上找到第一個(gè)沒有被批準(zhǔn)的日志條目索引，然后執(zhí)行 Basic Paxos 算法，對(duì) index 位置的日志用 client 請(qǐng)求的提案值進(jìn)行提案。
3. follower 接收到來自 leader 發(fā)起的提案值后進(jìn)行決議，接受該提案值則返回成功響應(yīng)，否則返回失敗。
4. leader 統(tǒng)計(jì)所收到的成功響應(yīng)的數(shù)量，如果超過集群節(jié)點(diǎn)數(shù)量的一半以上，則認(rèn)為共識(shí)已達(dá)成，提案成功，否則認(rèn)為提案失敗，并將結(jié)果返回給 client。

從上述時(shí)序流程來看，不論是 Multi-Paxos 還是 Raft，要達(dá)成共識(shí)都必然需要經(jīng)歷兩次 RTT。之所以是經(jīng)歷兩次，是因?yàn)樗鼈兌蓟谝粋€(gè)核心假設(shè)，命令批準(zhǔn)/日志提交后都需要同時(shí)滿足持久化存儲(chǔ)、有序，狀態(tài)機(jī)就能直接執(zhí)行批準(zhǔn)后的命令/應(yīng)用提交后的日志。但由于網(wǎng)絡(luò)本身是異步的，無法保證有序性，因此需要 leader 先來執(zhí)行，以確保不同命令的執(zhí)行順序（日志索引），并通過廣播獲得過半數(shù)節(jié)點(diǎn)的復(fù)制來確保持久化，這無法在一個(gè) RTT 內(nèi)完成。

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

而CURP 算法是一種無序復(fù)制算法，它將達(dá)成共識(shí)的場(chǎng)景細(xì)分成了以下兩類：

fast path: 在無沖突的場(chǎng)景下，在滿足持久化存儲(chǔ)的前提下，放松對(duì)共識(shí)的有序性要求并不影響最終的共識(shí)的達(dá)成。由于 fast path 只要求持久化存儲(chǔ)，因此只需要 1 個(gè) RTT 就可以達(dá)成共識(shí)。我們將 fast path 稱之為協(xié)議的前端

slow path：在有沖突的場(chǎng)景下，則需要同時(shí)保證并發(fā)請(qǐng)求的有序性，及持久化存儲(chǔ)這兩個(gè)前提條件，因此需要 2 個(gè) RTT 來達(dá)成共識(shí)，我們將 slow path 稱之為協(xié)議的后端。

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

fast path 與 slow path

那么 CURP 是如何實(shí)現(xiàn) fast path 和 slow path 的呢？下圖是 CURP 算法中集群拓?fù)涞囊粋€(gè)簡(jiǎn)圖

讓我們先來看看這張圖中都有哪些內(nèi)容：

1. Client：向集群發(fā)起請(qǐng)求的 client。
2. Master：對(duì)應(yīng)了集群中的 leader 節(jié)點(diǎn)。Master 節(jié)點(diǎn)中保存了狀態(tài)機(jī)的日志，其中綠色部分代表的是已經(jīng)持久化到磁盤當(dāng)中的日志，而藍(lán)色部分則代表的是保存在內(nèi)存當(dāng)中的日志。
3. Follower 節(jié)點(diǎn)：對(duì)應(yīng)了上圖中黃色虛線框的部分，每個(gè) follower 都包含了一下兩個(gè)部分：

a. Witness：本質(zhì)上可以近似地看成是一個(gè)基于內(nèi)存的 HashMap，一方面負(fù)責(zé)記錄當(dāng)前集群中處在 fast path 流程中的請(qǐng)求，另一方面，CURP 也會(huì)通過 Witness 來判斷當(dāng)前的請(qǐng)求是否存在沖突。Witness 中所保存的所有記錄都是無序的。

b. Backup：保存持久化到磁盤中的狀態(tài)機(jī)日志。

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

1. client 向集群中所有節(jié)點(diǎn)廣播 PUT z=7 的請(qǐng)求；
2. 集群當(dāng)中的節(jié)點(diǎn)接受到該請(qǐng)求后，根據(jù)角色的不同會(huì)執(zhí)行不同的邏輯：

a. leader 接收到請(qǐng)求后，會(huì)立刻將數(shù)據(jù) z = 7 寫入到本地（也就是狀態(tài)機(jī)日志中的藍(lán)色部分）然后立刻返回 OK。

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

3. client 收集并統(tǒng)計(jì)所接收到的成功響應(yīng)的數(shù)量。對(duì)于一個(gè)節(jié)點(diǎn)數(shù)量為 2f + 1 的集群，當(dāng)接收到的成功響應(yīng)達(dá)到 f+f/2+1 個(gè)時(shí)，則確認(rèn)該操作已經(jīng)持久化到集群當(dāng)中，整個(gè)過程耗時(shí) 1 個(gè) RTT。

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

1. client 向集群中所有節(jié)點(diǎn)廣播 PUT z=9 的請(qǐng)求；
2. 集群當(dāng)中的節(jié)點(diǎn)接受到該請(qǐng)求后，根據(jù)角色的不同會(huì)執(zhí)行不同的邏輯：

a. leader 接收到請(qǐng)求后，將 z = 9 寫入到狀態(tài)機(jī)日志中。由于 z = 9 與 z = 7 相沖突，向 client 返回 KeyConflict 響應(yīng)，并異步發(fā)起 AppendEntries 請(qǐng)求將狀態(tài)機(jī)日志同步到集群的其他節(jié)點(diǎn)上。

b. follower 接收到請(qǐng)求后，由于 z = 9 與 witness 中的 z = 7 相沖突，因此會(huì)拒絕保存這個(gè)提案。

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

04、Summary

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