本文转自  算法与数据结构

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

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

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

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

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

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

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

张大胖嘿嘿笑着同意。

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

刘瘦子也点头。

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

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

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

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

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

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

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

第一次游戏

1.拉票阶段

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

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

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

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

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

2.确定饭店

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

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

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

第二次游戏

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

总结

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

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

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

在BasicPaxos算法中，有两个角色最为重要:

Proposer:即张大胖和刘瘦子

Acceptor:小A,小B,小C，也包括张大胖和刘瘦子

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

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

在BasicPaxos这个两阶段的协议中，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