前言

寫完【paxos 的直觀解釋】之后，網(wǎng)友都說療效甚好，但是也會(huì)對(duì)這篇教程中一些環(huán)節(jié)提出疑問（有疑問說明真的看懂了 ），例如怎么把只能確定一個(gè)值的 paxos 應(yīng)用到實(shí)際場(chǎng)景中。

既然?Talk is cheap，那么就?Show me the code，這次我們把教程中描述的內(nèi)容直接用代碼實(shí)現(xiàn)出來，希望能覆蓋到教程中的涉及的每個(gè)細(xì)節(jié)。幫助大家理解 paxos 的運(yùn)行機(jī)制。

這是一個(gè)基于 paxos，200 行代碼的 kv 存儲(chǔ)系統(tǒng)的簡(jiǎn)單實(shí)現(xiàn)，作為【paxos 的直觀解釋】這篇教程中的代碼示例部分。Paxos 的原理本文不再介紹了，本文提到的數(shù)據(jù)結(jié)構(gòu)使用【protobuf】定義，網(wǎng)絡(luò)部分使用【grpc】定義。另外 200 行 go 代碼實(shí)現(xiàn) paxos 存儲(chǔ)。

文中的代碼可能做了簡(jiǎn)化, 完整代碼實(shí)現(xiàn)在【paxoskv】這個(gè)項(xiàng)目中（naive 分支）。

運(yùn)行和使用

跑一下：

這個(gè)項(xiàng)目中除了 paxos 實(shí)現(xiàn)，用 3 個(gè) test case 描述了 3 個(gè) paxos 運(yùn)行的例子，

• 【TestCase1SingleProposer】：無沖突運(yùn)行。

• 【TestCase2DoubleProposer】：有沖突運(yùn)行。

• 【Example_setAndGetByKeyVer】作為 key-val 使用。

測(cè)試代碼描述了幾個(gè) paxos 運(yùn)行例子的行為，運(yùn)行測(cè)試可以確認(rèn) paxos 的實(shí)現(xiàn)符合預(yù)期。

本文中 protobuf 的數(shù)據(jù)結(jié)構(gòu)定義如下：

以及主要的函數(shù)實(shí)現(xiàn)：

從頭實(shí)現(xiàn) Paxoskv

Paxos 相關(guān)的數(shù)據(jù)結(jié)構(gòu)

在這個(gè)例子中我們的數(shù)據(jù)結(jié)構(gòu)和服務(wù)框架使用【protobuf】和【grpc】實(shí)現(xiàn)，首先是最底層的 paxos 數(shù)據(jù)結(jié)構(gòu)：Proposer 和 Acceptor在【slide-27】中我們介紹了 1 個(gè) Acceptor 所需的字段：

在存儲(chǔ)端（Acceptor）也有幾個(gè)概念：

• last_rnd 是 Acceptor 記住的最后一次進(jìn)行寫前讀取的 Proposer（客戶端）是誰，以此來決定誰可以在后面真正把一個(gè)值寫到存儲(chǔ)中。

• v 是最后被寫入的值。

• vrnd 跟 v 是一對(duì), 它記錄了在哪個(gè) Round 中 v 被寫入了。

原文中這些名詞是參考了【paxos made simple】中的名稱，但在【Leslie Lamport】后面的幾篇 paper 中都換了名稱，為了后續(xù)方便，在【paxoskv】的代碼實(shí)現(xiàn)中也做了相應(yīng)的替換：

Proposer 的字段也很簡(jiǎn)單，它需要記錄：

• 當(dāng)前的 ballot number：Bal，

• 以及它選擇在 Phase2 運(yùn)行的值：Val（【slide-29】）。

于是在這個(gè)項(xiàng)目中用 protobuf 定義這兩個(gè)角色的數(shù)據(jù)結(jié)構(gòu)，如代碼【paxoskv.proto】中的聲明，如下：

其中 Proposer 還需要一個(gè) PaxosInstanceId，來標(biāo)識(shí)當(dāng)前的 paxos 實(shí)例為哪個(gè) key 的哪個(gè) version 在做決定，【paxos made simple】中只描述了一個(gè) paxos 實(shí)例的算法（對(duì)應(yīng)一個(gè) key 的一次修改），要實(shí)現(xiàn)多次修改，就需要增加這個(gè)字段來區(qū)分不同的 paxos 實(shí)例：

【paxoskv.proto】還定義了一個(gè) BallotNum，因?yàn)橐ＷC全系統(tǒng)內(nèi)的 BallotNum 都有序且不重復(fù)，一般的做法就是用一個(gè)本地單調(diào)遞增的整數(shù)，和一個(gè)全局唯一的 id 組合起來實(shí)現(xiàn)：

定義 RPC 消息結(jié)構(gòu)

RPC 消息定義了 Proposer 和 Acceptor 之間的通訊。

在一個(gè) paxos 系統(tǒng)中，至少要有 4 個(gè)消息：

• Phase 1 的 Prepare-request，Prepare-reply

• Phase 2 的 Accept-request，Accept-reply

如【slide-28】所描述的（原文中使用 rnd，這里使用 Bal，都是同一個(gè)概念）：

Phase- 1（Prepare）：

Phase- 2（Accept）：

在 Prepare-request 或 Accept-request 中，發(fā)送的是一部分或全部的 Proposer 的字段，因此我們?cè)诖a中：

• 直接把 Proposer 的結(jié)構(gòu)體作為 request 的結(jié)構(gòu)體

• 同樣把 Acceptor 的結(jié)構(gòu)體作為 reply 的結(jié)構(gòu)體

在使用的時(shí)候只使用其中幾個(gè)字段，對(duì)應(yīng)我們的 RPC 服務(wù)【PaxosKV】定義如下：

使用 Protobuf 和 Grpc 生成服務(wù)框架

protobuf 可以將【paxoskv.proto】直接生成 go 代碼（代碼庫(kù)中已經(jīng)包含了生成好的代碼：【paxoskv.pb.go】，只有修改【paxoskv.proto】之后才需要重新生成）

• 首先安裝 protobuf 的編譯器 protoc，可以根據(jù)【install-protoc】中的步驟安裝, 一般簡(jiǎn)單的一行命令就可以了：安裝好之后通過 protoc--version 確認(rèn)版本，至少應(yīng)該是 3.x: libprotoc 3.13.0

• Linux：apt install-y protobuf-compiler

• Mac：brew install protobuf

• 安裝 protoc 的 go 語言生成插件 protoc-gen-go：go get -u?http://github.com/golang/protobuf/protoc-gen-go

• 重新編譯 protokv.proto 文件：直接 make gen 或：

生成后的【paxoskv.pb.go】代碼中可以看到，其中主要的數(shù)據(jù)結(jié)構(gòu)例如 Acceptor 的定義：

以及 KV 服務(wù)的 client 端和 server 端的代碼，client 端是實(shí)現(xiàn)好的，server 端只有一個(gè) interface，后面我們需要來完成它的實(shí)現(xiàn)：

實(shí)現(xiàn)存儲(chǔ)的服務(wù)器端

【impl.go】是所有實(shí)現(xiàn)部分，我們定義一個(gè) KVServer 結(jié)構(gòu)體，用來實(shí)現(xiàn) grpc 服務(wù)的 interface PaxosKVServer；其中使用一個(gè)內(nèi)存里的 map 結(jié)構(gòu)模擬數(shù)據(jù)的存儲(chǔ)：

其中 Version 對(duì)應(yīng)一個(gè) key 的一次變化，也就是對(duì)應(yīng)一個(gè) paxos 實(shí)例，Versions 對(duì)應(yīng)一個(gè) key 的一系列變化，Storage 就是所有 key 的所有變化。

實(shí)現(xiàn) Acceptor 的 grpc 服務(wù) handler

Acceptor，是這個(gè)系統(tǒng)里的 server 端，監(jiān)聽一個(gè)端口，等待 Proposer 發(fā)來的請(qǐng)求并處理，然后給出應(yīng)答。

根據(jù) paxos 的定義，Acceptor 的邏輯很簡(jiǎn)單：在【slide-28】中描述：

根據(jù)教程里的描述，為 KVServer 定義 handle Prepare-request 的代碼：

這段代碼分 3 步：

• 取得 paxos 實(shí)例，

• 生成應(yīng)答：Acceptor 總是返回 LastBal，Val，VBal 這 3 個(gè)字段，所以直接把 Acceptor 賦值給 reply。

• 最后更新 Acceptor 的狀態(tài)：然后按照 paxos 算法描述，如果請(qǐng)求中的 ballot number 更大，則記錄下來，表示不在接受更小 ballot number 的 Proposer。

其中 getLockedVersion() 從 KVServer.Storage 中根據(jù) request 發(fā)來的PaxosInstanceId 中的字段 key 和 ver 獲取一個(gè)指定 Acceptor 的實(shí)例：

handle Accept-request 的處理類似，在【slide-31】中描述：

Accept() 要記錄 3 個(gè)值，

• LastBal：Acceptor 看到的最大的 ballot number；

• Val：Proposer 選擇的值，

• 以及 VBal：Proposer 的 ballot number：

Acceptor 的邏輯到此完整了，再看 Proposer：

實(shí)現(xiàn) Proposer 邏輯

Proposer 的運(yùn)行分 2 個(gè)階段，Phase1 和 Phase2，與 Prepare 和 Accept 對(duì)應(yīng)。

Phase1

在【impl.go】的實(shí)現(xiàn)中，Proposer.Phase1() 函數(shù)負(fù)責(zé) Phase1 的邏輯：

這段代碼首先通過 rpcToAll() 向所有 Acceptor 發(fā)送 Prepare-request 請(qǐng)求， 然后找出所有的成功的 reply：

• 如果發(fā)現(xiàn)一個(gè)更大的 ballot number，表示一個(gè) Prepare 失?。河懈碌腜roposer 存在；

• 否則，它是一個(gè)成功的應(yīng)答，再看它有沒有返回一個(gè)已經(jīng)被 Acceptor 接受（voted）的值。

最后，成功應(yīng)答如果達(dá)到多數(shù)派（quorum），則認(rèn)為 Phase1 完成，返回最后一個(gè)被 voted 的值，也就是 VBal 最大的那個(gè)。讓上層調(diào)用者繼續(xù) Phase2；如果沒有達(dá)到 quorum，這時(shí)可能是有多個(gè) Proposer 并發(fā)運(yùn)行而造成沖突，有更大的 ballot number，這時(shí)則把見到的最大 ballot number 返回，由上層調(diào)用者提升 ballot number 再重試。

client 與 server 端的連接

上面用到的 rpcToAll 在這個(gè)項(xiàng)目中的實(shí)現(xiàn) client 端（Proposer）到 server 端（Acceptor）的通訊，它是一個(gè)十分 簡(jiǎn)潔美觀 簡(jiǎn)陋的 grpc 客戶端實(shí)現(xiàn)：

Phase2

Proposer 運(yùn)行的 Phase2 在【slide-30】中描述，比 Phase1 更簡(jiǎn)單：

在第 2 階段 phase-2，Proposer X 將它選定的值寫入到 Acceptor 中，這個(gè)值可能是它自己要寫入的值，或者是它從某個(gè) Acceptor 上讀到的 v（修復(fù)）。

我們看到，它只需要確認(rèn)成 Phase2 的功應(yīng)答數(shù)量達(dá)到 quorum 就可以了。另外同樣它也有責(zé)任在 Phase2 失敗時(shí)返回看到的更大的 ballot number，因?yàn)樵?Phase1 和 Phase2 之間可能有其他 Proposer 使用更大的 ballot number 打斷了當(dāng)前 Proposer 的執(zhí)行，就像【slide-33】的沖突解決的例子中描述的那樣。

完整的 Paxos 邏輯

完整的 paxos 由 Proposer 負(fù)責(zé)，包括：如何選擇一個(gè)值，使得一致性得以保證。如【slide-29】中描述的：

Proposer X 收到多數(shù)（quorum）個(gè)應(yīng)答，就認(rèn)為是可以繼續(xù)運(yùn)行的。如果沒有聯(lián)系到多于半數(shù)的 acceptor，整個(gè)系統(tǒng)就 hang 住了，這也是 paxos 聲稱的只能運(yùn)行少于半數(shù)的節(jié)點(diǎn)失效。這時(shí) Proposer 面臨 2 種情況：

所有應(yīng)答中都沒有任何非空的 v，這表示系統(tǒng)之前是干凈的，沒有任何值已經(jīng)被其他 paxos 客戶端完成了寫入（因?yàn)橐粋€(gè)多數(shù)派讀一定會(huì)看到一個(gè)多數(shù)派寫的結(jié)果），這時(shí) Proposer X 繼續(xù)將它要寫的值在 phase-2 中真正寫入到多于半數(shù)的 Acceptor 中。

如果收到了某個(gè)應(yīng)答包含被寫入的 v 和 vrnd，這時(shí)，Proposer X 必須假設(shè)有其他客戶端（Proposer）正在運(yùn)行，雖然 X 不知道對(duì)方是否已經(jīng)成功結(jié)束，但任何已經(jīng)寫入的值都不能被修改！所以 X 必須保持原有的值。于是 X 將看到的最大 vrnd 對(duì)應(yīng)的 v 作為 X 的 phase-2 將要寫入的值。

這時(shí)實(shí)際上可以認(rèn)為 X 執(zhí)行了一次（不知是否已經(jīng)中斷的）其他客戶端（Proposer）的修復(fù)。

基于 Acceptor 的服務(wù)端和 Proposer 2 個(gè) Phase 的實(shí)現(xiàn)，最后把這些環(huán)節(jié)組合到一起組成一個(gè)完整的 paxos，在我們的代碼【RunPaxos】這個(gè)函數(shù)中完成這些事情：

這段代碼完成了幾件事：運(yùn)行 Phase1，有 voted 的值就選它，沒有就選自己要寫的值 val，然后運(yùn)行 Phase2。

就像 Phase1 Phase2 中描述的一樣，任何一個(gè)階段，如果沒達(dá)到 quorum，就需要提升遇到的更大的 ballot number，重試去解決遇到的 ballot number 沖突。這個(gè)函數(shù)接受 2 個(gè)參數(shù)：

• 所有 Acceptor 的列表（用一個(gè)整數(shù)的 id 表示一個(gè) Acceptor），

• 以及要提交的值。

其中，按照 paxos 的描述，這個(gè)值 val 不一定能提交：如果 paxos 在 Phase1 完成后看到了其他已經(jīng)接受的值（voted value），那就要選擇已接收的值，放棄 val。遇到這種情況，在我們的系統(tǒng)中，例如要寫入 key=foo，ver=3 的值為 bar，如果沒能選擇 bar，就要選擇下一個(gè)版本 key=foo，ver=4 再嘗試寫入。

這樣不斷的重試循環(huán), 寫操作最終都能成功寫入一個(gè)值（voted value）。

實(shí)現(xiàn)讀操作

在我們這個(gè) NB（naive and basic）的系統(tǒng)中，讀和寫一樣都要通過一次 paxos 算法來完成。因?yàn)閷懭脒^程就是一次 paxos 執(zhí)行，而 paxos 只保證在一個(gè) quorum 中寫入確定的值，不保證所有節(jié)點(diǎn)都有這個(gè)值。因此一次讀操作如果要讀到最后寫入的值，至少要進(jìn)行一次多數(shù)派讀。

但多數(shù)派讀還不夠：它可能讀到一個(gè)未完成的 paxos 寫入，如【slide-11】中描述的臟讀問題，讀取到的最大 VBal 的值，可能不是確定的值（寫入到多數(shù)派）。

例如下面的狀態(tài)：

如果 Proposer 試圖讀，在 Phase1 聯(lián)系到 A0 A1 這 2 個(gè) Acceptor，那么 foo 和 bar 這 2 個(gè)值哪個(gè)是確定下來的，要取決于 A2 的狀態(tài)。所以這時(shí)要再把最大VBal 的值跑完一次 Phase2，讓它被確定下來，然后才能把結(jié)果返回給上層（否則另一個(gè) Proposer 可能聯(lián)系到 A1 和 A2，然后認(rèn)為 Val=bar 是被確定的值）。

當(dāng)然如果 Proposer 在讀取流程的 Phase1 成功后沒有看到任何已經(jīng) voted 的值（例如沒有看到 foo 或 bar）， 就不用跑 Phase2 了。

所以在這個(gè)版本的實(shí)現(xiàn)中，讀操作也是一次【RunPaxos】函數(shù)的調(diào)用，除了它并不 propose 任何新的值，為了支持讀操作，所以在上面的代碼中 Phase2 之前加入一個(gè)判斷，如果傳入的 val 和已 voted 的值都為空，則直接返回：

【Example_setAndGetByKeyVer】這個(gè)測(cè)試用例展示了如何使用 paxos 實(shí)現(xiàn)一個(gè) kv 存儲(chǔ)，實(shí)現(xiàn)讀和寫的代碼大概這樣：

到現(xiàn)在為止，本文中涉及到的功能都實(shí)現(xiàn)完了，完整實(shí)現(xiàn)在【impl.go】中。

接著我們用測(cè)試用例實(shí)現(xiàn) 1 下【paxos的直觀解釋】中列出的 2 個(gè)例子, 從代碼看 poxos 的運(yùn)行：

文中例子

第1個(gè)例子是 paxos 無沖突的運(yùn)行【slide-32】：

把它寫成 test case，確認(rèn)教程中每步操作之后的結(jié)果都如預(yù)期

【TestCase1SingleProposer】：

第 2 個(gè)例子對(duì)應(yīng) 2 個(gè) Proposer 遇到?jīng)_突并解決沖突的例子，略長(zhǎng)不貼在文中了，代碼可以在 【TestCase2DoubleProposer】看到。

工程

Paxos 的出色之處在于它將分布式一致性問題簡(jiǎn)化到最核心的部分，沒有任何多余的設(shè)計(jì)。

工程實(shí)現(xiàn)上我們多數(shù)時(shí)候會(huì)用一個(gè) paxos 的變體，它需要對(duì) paxos 中的實(shí)例擴(kuò)展為一系列多值的操作日志，支持完整的狀態(tài)機(jī)，以及對(duì)運(yùn)維提供支持成員變更，所以 raft 在工程上更受歡迎：

https://github.com/datafuselabs/openraft創(chuàng)建 openraft 這個(gè)項(xiàng)目的目的是：

• 優(yōu)化和改良 raft 算法本身的問題：

• 例如一個(gè) term 內(nèi)無法選出多個(gè) leader，造成選舉沖突過多的問題，

• 例如不必要的 pre-vote 階段的引入，

• 例如 raft 作為一個(gè)一致性算法對(duì)外部時(shí)鐘的依賴，

• 例如強(qiáng)制的 leader/candidate 階段的拆分使得換 leader 要經(jīng)歷一個(gè)無法服務(wù)的 candidate-state 的階段。

openraft 正在解決的這些問題，使之不僅僅是一個(gè)為了性能和安全用 rust 重寫的項(xiàng)目。

• 其次在用戶接口上，提供一組語義明確的 async API。

參考鏈接

本文用到的代碼在 paxoskv 項(xiàng)目的 naive 分支上：

【https://github.com/openacid/paxoskv/tree/naive】

• 【paxos made simple】：http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple

• 【Leslie Lamport】：http://www.lamport.org/

• 【protobuf】：https://developers.google.com/protocol-buffers

• 【install-protoc】：https://grpc.io/docs/protoc-installation/

• 【grpc】：https://grpc.io/

• 【paxos的直觀解釋】：https://blog.openacid.com/algo/paxos

• 【issue】：https://github.com/openacid/paxoskv/issues/new/choose

• 【paxoskv】：https://github.com/openacid/paxoskv/tree/naive

• 【TestCase1SinglePropose】：https://github.com/openacid/paxoskv/blob/naive/paxoskv/paxos_slides_case_test.go#L11

• 【TestCase2DoubleProposer】：https://github.com/openacid/paxoskv/blob/naive/paxoskv/paxos_slides_case_test.go#L57

• 【Example_setAndGetByKeyVer】：https://github.com/openacid/paxoskv/blob/naive/paxoskv/example_set_get_test.go

• 【Openraft】:?https://github.com/datafuselabs/openraft

關(guān)于 Databend

Databend 是一款開源、彈性、低成本，基于對(duì)象存儲(chǔ)也可以做實(shí)時(shí)分析的新式數(shù)倉(cāng)。期待您的關(guān)注，一起探索云原生數(shù)倉(cāng)解決方案，打造新一代開源 Data Cloud。

• Databend 文檔：https://databend.rs/

• Twitter：https://Twitter.com/Datafuse_Labs

• Slack：https://datafusecloud.slack.com/

• Wechat：Databend

• GitHub ：https://github.com/datafuselabs/databend