Golang 實(shí)現(xiàn) Paxos 分布式共識(shí)算法
前文《理解 Paxos》只包含偽代碼，幫助了理解但又不夠爽，既然現(xiàn)在都講究?Talk is cheap. Show me the code.?這次就把文章中的偽代碼用 Go 語(yǔ)言實(shí)現(xiàn)出來(lái)，希望能幫助各位朋友更直觀的感受 Paxos 論文中的細(xì)節(jié)。
但我們需要對(duì)算法做一些簡(jiǎn)化，有多簡(jiǎn)單呢？我們不持久化存儲(chǔ)任何變量，并且用?chan?直接代替 RPC 調(diào)用。
代碼地址：https://github.com/tangwz/paxos/tree/naive
記得切換到 naive 分支。
定義相關(guān)結(jié)構(gòu)體
我們定義 Proposer 如下：
type proposer struct {
// server id
id int
// the largest round number the server has seen
round int
// proposal number = (round number, serverID)
number int
// proposal value
value string
acceptors map[int]bool
net network
}
這些結(jié)構(gòu)體成員都很容易理解，其中?acceptors?我們主要用來(lái)存儲(chǔ) Acceptors 的地址，以及記錄我們收到 Acceptor 的成功/失敗響應(yīng)。
Acceptor 的結(jié)構(gòu)體：
type acceptor struct {
// server id
id int
// the number of the proposal this server will accept, or 0 if it has never received a Prepare request
promiseNumber int
// the number of the last proposal the server has accepted, or 0 if it never accepted any.
acceptedNumber int
// the value from the most recent proposal the server has accepted, or null if it has never accepted a proposal
acceptedValue string
learners []int
net network
}
主要成員解釋都有注釋?zhuān)?jiǎn)單來(lái)說(shuō)我們需要記錄三個(gè)信息：
promiseNumber：承諾的提案編號(hào)acceptedNumber：接受的提案編號(hào)acceptedValue：接受的提案值
定義消息結(jié)構(gòu)體
消息結(jié)構(gòu)體定義了 Proposer 和 Acceptor 之間、Acceptor 和 Leaner 之間的通訊協(xié)議。最主要的還是 Paxos 的兩階段的四個(gè)消息。
Phase 1 請(qǐng)求：提案編號(hào)
Phase 1 響應(yīng)：如果有被 Accepted 的提案，返回提案編號(hào)和提案值
Phase 2 請(qǐng)求：提案編號(hào)和提案值
Phase 2 響應(yīng)：Accepted 的提案編號(hào)和提案值
這樣看，我們的消息結(jié)構(gòu)體只需要提案編號(hào)和提案值，加上一個(gè)消息類(lèi)型，用來(lái)區(qū)分是哪個(gè)階段的消息。消息結(jié)構(gòu)體定義在 message.go 文件，具體如下：
// MsgType represents the type of a paxos phase.
type MsgType uint8
const (
Prepare MsgType = iota
Promise
Propose
Accept
)
type message struct {
tp MsgType
from int
to int
number int // proposal number
value string // proposal value
}
實(shí)現(xiàn)網(wǎng)絡(luò)
網(wǎng)絡(luò)上可以做的選擇和優(yōu)化很多，但這里為了保持簡(jiǎn)單的原則，我們將網(wǎng)絡(luò)定義成?interface。后面完全可以改成 RPC 或 API 等其它通信方式來(lái)實(shí)現(xiàn)（沒(méi)錯(cuò)，我已經(jīng)實(shí)現(xiàn)了一個(gè) Go RPC 的版本了）。
type network interface {
send(m message)
recv(timeout time.Duration) (message, bool)
}
接下里我們?nèi)?shí)現(xiàn) network 接口：
type Network struct {
queue map[int]chan message
}
func newNetwork(nodes ...int) *Network {
pn := &Network{
queue: make(map[int]chan message, 0),
}
for _, a := range nodes {
pn.queue[a] = make(chan message, 1024)
}
return pn
}
func (net *Network) send(m message) {
log.Printf("net: send %+v", m)
net.queue[m.to] <- m
}
func (net *Network) recvFrom(from int, timeout time.Duration) (message, bool) {
select {
case m := <-net.queue[from]:
log.Printf("net: recv %+v", m)
return m, true
case <-time.After(timeout):
return message{}, false
}
}
就是用?queue?來(lái)記錄每個(gè)節(jié)點(diǎn)的?chan，key 則是節(jié)點(diǎn)的 server id。
發(fā)送消息則將?Message?發(fā)送到目標(biāo)節(jié)點(diǎn)的?chan?中，接受消息直接從?chan?中讀取數(shù)據(jù)，并等待對(duì)應(yīng)的超時(shí)時(shí)間。
不需要做其它網(wǎng)絡(luò)地址、包相關(guān)的東西，所以非常簡(jiǎn)單。具體在?network.go?文件。
實(shí)現(xiàn)單元測(cè)試
這個(gè)項(xiàng)目主要使用 go 單元測(cè)試來(lái)檢驗(yàn)正確性，我們主要測(cè)試兩種場(chǎng)景：
TestSingleProposer（單個(gè) Proposer）
TestTwoProposers（多個(gè) Proposer）
測(cè)試代碼通過(guò)運(yùn)行 Paxos 后檢查 Chosen 返回的提案值是否符合預(yù)期。
實(shí)現(xiàn)算法流程
按照角色將文件分為 proposer.go, acceptor.go 和 learner.go，每個(gè)文件都有一個(gè)?run()?函數(shù)來(lái)運(yùn)行程序，run()?函數(shù)執(zhí)行條件判斷，并在對(duì)應(yīng)的階段執(zhí)行對(duì)應(yīng)的函數(shù)。
按照偽代碼描述，我們很容易實(shí)現(xiàn) Phase 1 和 Phase 2，把每個(gè)階段的請(qǐng)求響應(yīng)都作為一個(gè)函數(shù)，我們一步步來(lái)看。
第一輪 Prepare RPCs 請(qǐng)求階段：
// Phase 1. (a) A proposer selects a proposal number n
// and sends a prepare request with number n to
// a majority of acceptors.func (p *proposer) prepare() []message {
p.round++
p.number = p.proposalNumber()
msg := make([]message, p.majority())
i := 0
for to := range p.acceptors {
msg[i] = message{
tp: Prepare,
from: p.id,
to: to,
number: p.number,
}
i++
if i == p.majority() {
break
}
}
return msg
}
// proposal number = (round number, serverID)
func (p *proposer) proposalNumber() int {
return p.round<< 16 | p.id
}
Prepare 請(qǐng)求階段我們將 round+1 然后發(fā)送給多數(shù)派 Acceptors。
注：這里很多博客和教程都會(huì)將 Prepare RPC 發(fā)給所有的?Acceptors，6.824 的 paxos 實(shí)驗(yàn)就將 RPC 發(fā)送給所有 Acceptors。這里保持和論文一致，只發(fā)送給 a majority of acceptors。
第一輪 Prepare RPCs 響應(yīng)階段：
接下來(lái)在?acceptor.go?文件中處理請(qǐng)求：
func (a *acceptor) handlePrepare(args message) (message, bool) {
if a.promiseNumber >= args.number {
return message{}, false
}
a.promiseNumber = args.number
msg := message{
tp: Promise,
from: a.id,
to: args.from,
number: a.acceptedNumber,
value: a.acceptedValue,
}
return msg, true
}
如果?
args.number?大于?acceptor.promiseNumber，則承諾將不會(huì)接收編號(hào)小于?args.number的提案（即?a.promiseNumber = args.number）。如果之前有提案被 Accepted 的話，響應(yīng)還應(yīng)包含 a.acceptedNumber 和 a.acceptedValue。否則忽略，返回?
false。
第二輪 Accept RPCs 請(qǐng)求階段：
func (p *proposer) accept() []message {
msg := make([]message, p.majority())
i := 0
for to, ok := range p.acceptors {
if ok {
msg[i] = message{
tp: Propose,
from: p.id,
to: to,
number: p.number,
value: p.value,
}
i++
}
if i == p.majority() {
break
}
}
return msg
}
當(dāng) Proposer 收到超過(guò)半數(shù) Acceptor 的響應(yīng)后，Proposer 向多數(shù)派的 Acceptor 發(fā)起請(qǐng)求并帶上提案編號(hào)和提案值。
第二輪 Accept RPCs 響應(yīng)階段：
func (a *acceptor) handleAccept(args message) bool {
number := args.number
if number >= a.promiseNumber {
a.acceptedNumber = number
a.acceptedValue = args.value
a.promiseNumber = number
return true
}
return false
}
Acceptor 收到?Accept()?請(qǐng)求，在這期間如果 Acceptor 沒(méi)有對(duì)比 a.promiseNumber 更大的編號(hào)另行 Promise，則接受該提案。
別忘了：Learning a Chosen Value
在 Paxos 中有一個(gè)十分容易混淆的概念：Chosen Value 和 Accepted Value，但如果你看過(guò)論文，其實(shí)已經(jīng)說(shuō)得非常直接了。論文的 2.3 節(jié) Learning a Chosen Value 開(kāi)頭就說(shuō)：
To learn that a value has been chosen, a learner must find out that a proposal has been accepted by a majority of acceptors.?
所以 Acceptor 接受提案后，會(huì)將接受的提案廣播 Leaners，一旦 Leaners 收到超過(guò)半數(shù)的 Acceptors 的 Accepted 提案，我們就知道這個(gè)提案被 Chosen 了。
func (l *learner) chosen() (message, bool) {
acceptCounts := make(map[int]int)
acceptMsg := make(map[int]message)
for _, accepted := range l.acceptors {
if accepted.number != 0 {
acceptCounts[accepted.number]++
acceptMsg[accepted.number] = accepted
}
}
for n, count := range acceptCounts {
if count >= l.majority() {
return acceptMsg[n], true
}
}
return message{}, false
}
運(yùn)行和測(cè)試
代碼拉下來(lái)后，直接運(yùn)行：
go test
寫(xiě)在后面
為什么不用 mit 6.824 的課程代碼？
之前我曾把 mit 6.824 的 Raft 答案推到自己的 Github，直到 2020 開(kāi)課的時(shí)候 mit 的助教發(fā)郵件讓我將我的代碼轉(zhuǎn)為 private，因?yàn)檫@樣會(huì)導(dǎo)致學(xué)習(xí)課程的人直接搜到代碼，而無(wú)法保證作業(yè)獨(dú)立完成。
確實(shí)，實(shí)驗(yàn)是計(jì)算機(jī)最不可或缺的環(huán)節(jié)，用 mit 6.824 2015 的 paxos 代碼會(huì)導(dǎo)致很多學(xué)習(xí)者不去自己解決困難，直接上網(wǎng)搜代碼，從而導(dǎo)致學(xué)習(xí)效果不好，違背了 mit 的初衷。
當(dāng)然，你也可以說(shuō)現(xiàn)在網(wǎng)上以及很容易搜到 6.824 的各種代碼了，但出于之前 mit 助教的郵件，我不會(huì)將作業(yè)代碼直接發(fā)出來(lái)。
感興趣的同學(xué)可以到 2015 版本學(xué)習(xí)：http://nil.csail.mit.edu/6.824/2015/
未來(lái)計(jì)劃
實(shí)現(xiàn)一個(gè)完整的（包含網(wǎng)絡(luò)和存儲(chǔ)的） Paxos
基于 Paxos 實(shí)現(xiàn)一個(gè) Paxos KV 存儲(chǔ)
實(shí)現(xiàn)其它 Paxos 變種
歡迎各位朋友催更……
結(jié)語(yǔ)
本文代碼在 Github 上，如本文有什么遺漏或者不對(duì)之處，或者各位朋友有什么新的想法，歡迎提 issue 討論。
推薦閱讀