Paxos分布式系统共识算法？我愿称其为点歌算法… _生活百科

原创：微信公众号 码农参上，欢迎分享，转载请保留出处。

哈喽大家好啊，我是Hydra 。
分布式系统共识算法Paxos相信大家都不陌生，它被称为最难理解的算法不是没有道理的，首先，它的发表之路就充满了坎坷。
1990年，莱斯利·兰伯特大佬写了一篇论文，举了一个城邦选举的例子来介绍Paxos算法，然而大佬的幽默感并未得到审稿人的认可，论文未发表成功…
1998年，兰伯特重新发表论文《The Part-Time Parliament》描述算法，然而众多学者并不买账，直呼看不懂…
2001年，兰伯特对算法的描述进行简化，再次发表《Paxos Made Simple》，这次Paxos成为了世界公认最优秀的分布式系统共识算法…

文章插图
其实说白了，Paxos算法要解决的问题是一个分布式系统如何就某个值决议达成一致。比如说，一组进程现在正在提议某个数据的值，需要通过消息传递的方式使这个值达成一致，也就是最终仅能有一个值被选定。
但毕竟是大佬写出来的东西，且不说逻辑推理部分，就算单拎出来论文中对两个核心阶段的描述来说，我等凡人理解起来也还是有些困难。
不信？那就让英语六级的我先来简单地翻译一下。

文章插图
阶段1a、提案者选择一个提案号n，发送一个提案号为n的prepare请求给大多数接受者。
b、如果一个接受者收到的编号为n的prepare请求，并且编号比它已经响应过的任何prepare请求的编号都大，那它就回应这个请求，承诺不再接受任何编号小于n的提案，并回复它已经接受的编号最大的提案（如果存在的话）。
阶段2a、如果提案者收到大多数接受者关于它编号为n的prepare请求的回应，它就给这些接受者发送一个编号为n，值为v的accept请求，v是收到的回应中编号最大的提案值。如果之前不存在任何一个提案的回复时，那么v可以是任意值，也就是可以由自己指定。
b、接受者收到编号为n的accept请求时，只要它还没有响应编号比n更高的prepare请求，那么它将接受该提案。

文章插图
是不是还看不懂？那就对了，下面我们通过一个简单的例子来描述这个过程。
记得小时候，有不少广播电台可以通过电话点歌，打电话给话务员告诉她你要点的歌，接下来就会播放。当然了，这个过程不是免费的，肯定有不少小伙伴在月末父母交话费的时候，惨遭过社会的毒打。
既然是电台热线，那么肯定不只有一个话务员了，我们假定这个电台同时存在3个话务员，并且她们之间是相互没有交流的，那么当短时间内打进来很多电话时，要怎么决定放哪首歌呢？

文章插图
首先，话务员之间遵从少数服从多数，那么为了获得更多话务员的支持，你可以不断给更多的话务员打电话。
其次，前面我们说过，这个过程是收费的，假定存在一条潜规则，电台会更偏向于接受出价高的人的点歌请求，那么也就好办了，你可以使了劲地加钱。
在这种环境下，听众想要点歌成功的话，就得靠上面两个办法。
这时，第一个听众打进来电话了，在第一个阶段听众只能进行报价，还不能提出自己想要听什么歌，这个报价就可以理解为算法中的编号