码农们的聚餐，会复杂到什么程度？

作者丨刘欣

责编 | 仲培艺

本文经授权转载自码农翻身（ ID：coderising）

张大胖的部门连续加班三个月，系统终于上线了！

经理打算组织一次部门聚餐， 犒劳一下大家。至于去哪家饭店，就留给大家来讨论了。

没想到的是，这一伙人争得不可开交，谁都说不过谁，其中，争吵得最凶的是张大胖和刘瘦子，张大胖想去吃火锅， 刘瘦子想去吃烧烤， 剩下三个员工是墙头草， 也不知道听谁的。

经理看到这一群不省油的灯，突然想到一个办法，说道：“别吵了！咱们都是写程序的，用一个算法来解决这个问题吧。”

大家听到算法，一下子就来了兴致：“什么算法？”

“就是大名鼎鼎的 Paxos 啊，它有点儿复杂，大家正好学习一下。 这次咱们要出去聚餐，但是张大胖和刘瘦子的意见不统一，我们最终还是要选一家，这叫达成共识。这个共识啊只要有超过半数的人同意就可以了。”

“在开始之前，我先说几个要求， 咱们的目的是一起去吃饭，所以张大胖你不能给小 A 说去吃火锅，给小 B 说去吃烧烤，又给小 C 说去吃料理。你这样来回捣乱我可要罚你工资了！”

张大胖嘿嘿笑着同意。

“还有你，刘瘦子，如果小 A，小 B 或者小 C 已经有人同意张大胖的意见了，你就别墨迹，别再坚持你的意见，跟着去吃就好了。”

刘瘦子也点头。

“最后小 A、小 B、小 C 你们仨，同意了一个人的提议就别来回当墙头草，确定吃哪个饭店就不要改啦！”

张大胖他们五个人听到经理讲了这些要求，默默记在心里。

经理接着说：“具体的算法也不难，就两个阶段：

1. 给自己拉票阶段，这一阶段的目的是争夺“发言权”，只有多数人同意听你“发言”，才能进入下一阶段；

2. 确认阶段：确定去哪个饭店吃饭。

经理一边说，一边给出了算法具体的步骤，张大胖刘瘦子一看，很简单啊！迫不及待地就开始玩起来了。

经理心里偷偷地笑了：简单！哼！等玩起来了够你俩折腾的！

第一次游戏

拉票阶段

张大胖人比较聪明，看到小 A、小 B、小 C这三个家伙头发乱糟糟的，以及标配的格子衬衫，一想就知道还没有女朋友。

为了让这三个人听自己的，张大胖想出来一个点子：听我的提议，我给你们每人介绍一位女生！

小 A、小 B 听到了，非常高兴，张大哥解决单身问题，听张大哥的！

与此同时，他俩在小本子上记下：介绍一位女生， 我可以同意饭店提议！

张大胖乐了，自己这么轻松已经取得 3 个人的支持，小 A、小 B 加上自己（我自己不会人格分裂反对我自己）， 已经是多数派了，不管小 C 是否同意， 我都有了发言权了。

确定饭店

张大胖给小 A、小 B 说， 我给你们介绍一位女生，去吃火锅！

小 A、小 B 都表示同意，在小本子上记下： 介绍一位女生，去吃火锅。

张大胖收到结果，知道自己的 Paxos 算法已经执行完毕， 高兴地宣布：“行了，我们已经达成了共识，可以去吃火锅了! ”

第二次游戏

刘瘦子傻眼了：“张大胖你这家伙下手太快了，你这样搞，一点意思都没有啊， 不行，我们再玩一次！”

张大胖说：“没问题， 我还怕你不成？” 

话虽这么说，他赶紧和小 A、小 B、小 C 联系：给你们介绍一位女生，要支持我啊。

小 A、小 B 表示同意，在本子上记下：介绍一位女生， 我可以同意饭店提议！

结果小 C 说了句，张大胖，你不实在哈，刘瘦子说给我介绍俩女生呢！

原来小 C 由于已经听了刘瘦子的话了，本子记得是：介绍两位女生，我可以同意饭店提议！

张大胖心说，这刘瘦子也不笨嘛，也知道用这种方式来拉拢人。

不过既然有小 A、小 B 答应自己，张大胖知道自己有了多数派的同意！

自己赶快给他们说去哪吃就行，别让这几个墙头草跑了！然后哼着小曲儿去找女生联系方式了。

找到联系方式以后，张大胖进入第二阶段，准备彻底终结这次饭店之争。

小 A 顺利地同意了吃火锅的提议，记录了下来：介绍一位女生，去吃火锅。

没想到的是，小 B 已经反水了：张大胖，你不实在哈，刘瘦子说给我介绍俩女生呢！

张大胖心想，真是墙头草，看来只好从第一阶段的拉票重新开始了。

加大筹码！给他们每人介绍三位女生！果然，小 A、小 B 这两个墙头草再次反水，欢天喜地支持自己了。

与此同时， 刘瘦子美滋滋地以为，自己用“介绍两位女生”获得了多数派的支持，可以进入第二阶段，去确定饭店。

可是他和小 B 联系的时候，悲催地发现，张大胖已经提高了筹码（3 位女生）。又把小 B 给拉走了！

刘瘦子赶紧查找通信录，准备找出更多联系方式，给他们介绍 4 位女生。

张大胖可没有闲着，马上进入第二阶段，成功地确定了饭店。

至此，张大胖的 Paxos 算法执行完毕，他知道大多数人已经同意去吃火锅了。

刘瘦子再次发起拉票，试图重新占据优势，可是他发现小 A 和小 B 已经接受了吃火锅的提议。

他们说：“刘瘦子，我们很想答应你，可是，我们已经答应吃火锅的建议了，不能再变了，但是，为了表示对您的尊重，我们以后就认定确定吃火锅是得给我们介绍 4 位女生。”

刘瘦子想到经理之前定的规则：“如果已经有人接受过了饭店的提议，不能再墨迹了，跟着去吃就行了！”

他叹了口气，进入了第二阶段，确定饭店，不过他确定的也是“吃火锅”

刘瘦子的 Paxos 算法也执行完了， 最终达成了一致，去吃火锅。

总结

我发现对于这个 Basic Paxos 算法，你要是理解了，会发现很简单，但是想把脑子中的东西描述出来，却很难，因为每个参与者的状态都在不断地变化中，细节太多，分支太多。

所以就通过这个小游戏讲述了 Basic Paxos 算法，说实话，不太严谨，比如小 A、小 B、小 C 如果收到了带着更多“贿赂”的 Accept，虽然已经确定了饭店，还是可以修改的，这一点在游戏中就没提。

这个游戏展示了执行过程遇到的典型情况。 完整的算法参见文章的最后部分。

在 Basic Paxos 算法中，有两个角色最为重要：

• Proposer：即张大胖和刘瘦子

• Acceptor：小 A、小 B、小 C， 也包括张大胖和刘瘦子

一个人可以身兼多个角色。

游戏中的“介绍 n 位女生”，在 Paxos 算法中，就是一个数字 n。

在 Basic Paxos 这个两阶段的协议中，Proposer 在第一阶段发送 Prepare(n) 给其他人，试图获取“发言权”。 这里的 Prepare(n) 就相当于“介绍 n 位女生”。

在第二阶段发送 Accept(n,v) 来试图确定结果，这里的 n 还是“介绍n位女生”，v 是吃火锅或者吃烧烤。

由于有多个 Proposer 可以发送 Prepare(n)。这时候 Acceptor 就需要根据 n 的大小来确定听谁的。所以就会出现像小 B 这样的墙头草，来回摇摆。

Proposer 在第一阶段得到大多数人支持以后，会进入第二阶段，发出 Accept(n,v) 的消息给其他人。

某个 Acceptor，例如小 B，收到了张大胖的 Accept(3,火锅)，已经记录下了吃火锅， 这时候即使收到的消息中是 Prepare(4) ，数字更大也不行。他就告诉刘瘦子，我已经确定选火锅了。 

这时候的关键点就是刘瘦子要跟随，不要坚持自己的烧烤了。

一个有趣的问题

聪明的你估计已经看出：如果张大胖和刘瘦子交替着争夺发言权，例如：

张大胖介绍 1 位女生，争取了小 A、小 B

刘瘦子介绍 2 位女生，争取了小 B、小 C

张大胖介绍 3 位女生，又争取了小 A、小 B

刘瘦子介绍 4 位女生，又争取了小 B、小 C

……

这样一来，无论是谁都无法进入第二阶段，算法永远无法完成。

一种解决办法就是，可以让他们开始新一轮争取的时候，等待一个随机的时间。让其他人有机会去完成这个算法。

算法

贴一张详细的算法，有兴趣的可以仔细研究一下。

算法来自于：https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx

作者：王卓是北京邮电大学硕士，研究方向为区块链技术、共识算法及零知识证明，对区块链技术底层有较深的理解。

声明：本文经授权转载自码农翻身，如需转载请联系原作者。

 热 文 推 荐 

System.out.println("点个在看吧！");
console.log("点个在看吧！");
print("点个在看吧！");
printf("点个在看吧！\n");
cout << "点个在看吧！" << endl;
Console.WriteLine("点个在看吧！");
Response.Write("点个在看吧！");
alert("点个在看吧！")
echo "点个在看吧！"

你点的每个“在看”，我都认真当成了喜欢