3358www.Sina.com/前文《理解 Paxos》中只含有伪代码，有助于理解但并不爽快。这次用Go语言实现了文章中的伪代码，希望能帮助大家更加直观地感受Paxos论文的详细内容。
我们需要简化算法。 有多简单呢？Talk is cheap. Show me the code.
代码地址： https://github.com/Tang wz/Pax OS/tree/naive
我们不持久化存储任何变量，并且用chan直接代替 RPC 调用。
按如下方式定义相关结构的定义属性：
typeproposerstruct//serverid int//thelargestroundnumbertheserverhasseenroundint//proposal number=(round number， 服务器id (number int//proposalvaluevaluestringacceptorsmap [ int ] boolnetnetwork )这些结构成员很容易理解。 其中，加速器主要用于存储加速器的地址。 它还用于存储加速器
加速器结构：
typeacceptorstruct//serverid int//thenumberoftheproposalthisserverwillaccept， or0ifithasneverreceivedapreparerequestpromisenumberint//thenumberofthelastproposaltheserverhasaccepted， or0ifitneveracceptedany.acceptednumberint//thevaluefromthemostrecentproposaltheserverhasaccepted，ornullifithasneveraccced 简单地说，需要记录三条信息。
promiseNumber :约定的提案编号
接受编号：接受的建议编号
接受值：接受的建议值
定义消息结构的消息结构定义了Proposer和加速器之间、加速器和Leaner之间的通信协议。 最重要的是Paxos两个阶段的四条消息。
Phase 1请求：记得切换到 naive 分支。
Phase 1回复：如果有已接受的建议，请单击提案编号和提案编号
Phase 2请求：提案值和提案编号
Phase 2响应： Accepted的提案值和提案编号
这样，我们的信息结构只需在提案编号和提案值上加上用于区分哪个阶段的信息的信息类型即可。 消息结构在message.go文件中定义。 具体情况如下：
//msgtyperepresentsthetypeofapaxosphase.typemsgtypeuint8const (prepare msgtype=iotapromiseproposeaccept ) )。 typemessagestruct { tpmsgtypefrominttointnumberint//proposalnumbervaluestring//proposal value }是网络上的选项和没错，我已经实现了Go RPC的版本。
typenetworkinterface { send (m message ) recv ) time outtime.duration (message，bool ) }然后实现网络接口。
类型网络结构{ 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 来记录每个节点的 chan，key 则是节点的 server id。
发送消息则将 Message 发送到目标节点的 chan 中，接受消息直接从 chan 中读取数据，并等待对应的超时时间。
不需要做其它网络地址、包相关的东西，所以非常简单。具体在 network.go 文件。
实现单元测试这个项目主要使用 go 单元测试来检验正确性，我们主要测试两种场景：
TestSingleProposer（单个 Proposer）
TestTwoProposers（多个 Proposer）
测试代码通过运行 Paxos 后检查 Chosen 返回的提案值是否符合预期。
实现算法流程按照角色将文件分为 proposer.go, acceptor.go 和 learner.go，每个文件都有一个 run() 函数来运行程序，run() 函数执行条件判断，并在对应的阶段执行对应的函数。
按照伪代码描述，我们很容易实现 Phase 1 和 Phase 2，把每个阶段的请求响应都作为一个函数，我们一步步来看。
第一轮 Prepare RPCs 请求阶段： // 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 请求阶段我们将 round+1 然后发送给多数派 Acceptors。
注：这里很多博客和教程都会将 Prepare RPC 发给所有的 Acceptors，6.824 的 paxos 实验就将 RPC 发送给所有 Acceptors。这里保持和论文一致，只发送给 a majority of acceptors。
第一轮 Prepare RPCs 响应阶段：接下来在 acceptor.go 文件中处理请求：
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，则承诺将不会接收编号小于 args.number的提案（即 a.promiseNumber = args.number）。如果之前有提案被 Accepted 的话，响应还应包含 a.acceptedNumber 和 a.acceptedValue。
否则忽略，返回 false。
第二轮 Accept RPCs 请求阶段： 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}当 Proposer 收到超过半数 Acceptor 的响应后，Proposer 向多数派的 Acceptor 发起请求并带上提案编号和提案值。
第二轮 Accept RPCs 响应阶段： 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() 请求，在这期间如果 Acceptor 没有对比 a.promiseNumber 更大的编号另行 Promise，则接受该提案。
别忘了：Learning a Chosen Value在 Paxos 中有一个十分容易混淆的概念：Chosen Value 和 Accepted Value，但如果你看过论文，其实已经说得非常直接了。论文的 2.3 节 Learning a Chosen Value 开头就说：
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 接受提案后，会将接受的提案广播 Leaners，一旦 Leaners 收到超过半数的 Acceptors 的 Accepted 提案，我们就知道这个提案被 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} 运行和测试代码拉下来后，直接运行：
go test 写在后面 为什么不用 mit 6.824 的课程代码？之前我曾把 mit 6.824 的 Raft 答案推到自己的 Github，直到 2020 开课的时候 mit 的坦率的白开水发邮件让我将我的代码转为 private，因为这样会导致学习课程的人直接搜到代码，而无法保证作业独立完成。
确实，实验是计算机最不可或缺的环节，用 mit 6.824 2015 的 paxos 代码会导致很多学习者不去自己解决困难，直接上网搜代码，从而导致学习效果不好，违背了 mit 的初衷。
当然，你也可以说现在网上以及很容易搜到 6.824 的各种代码了，但出于之前 mit 坦率的白开水的邮件，我不会将作业代码直接发出来。
感兴趣的同学可以到 2015 版本学习：http://nil.csail.mit.edu/6.824/2015/
未来计划实现一个完整的（包含网络和存储的） Paxos
基于 Paxos 实现一个 Paxos KV 存储
实现其它 Paxos 变种
欢迎各位朋友催更……
结语本文代码在 Github 上，如本文有什么遗漏或者不对之处，或者各位朋友有什么新的想法，欢迎提 issue 讨论。
你可能还喜欢
点击下方图片即可阅读
云原生是一种信仰 ????
扫码关注公众号
后台回复◉k8s◉获取史上最方便快捷的 Kubernetes 高可用部署工具，只需一条命令，连 ssh 都不需要！
点击 "阅读原文" 获取更好的阅读体验！
❤️给个「在看」，是对我最大的支持❤️