大家好，我是Hydra。分布式系统共识算法Paxos相信大家都不陌生。它被称为最难理解的算法并不是没有道理的。首先，它的出版之路充满坎坷。1990年，LeslieLambert先生写了一篇论文，引用了一个城邦选举的例子来介绍Paxos算法。然而，他的幽默感并没有得到审稿人的认可，论文也没有成功发表……1998年，2001年，Lambert重新发表了一篇描述算法的论文《The Part-Time Parliament》。然而，很多学者并不买账，表示看不懂……2001年，兰伯特简化了算法的描述，再次发表了《Paxos Made Simple》。这次Paxos成为了全世界公认的最好的分布式系统共识算法……其实说白了，Paxos算法要解决的问题就是分布式系统如何对某个值达成共识解决。比如一组进程当前正在提议某个数据的值，而这个值需要通过消息传递来约定，即最后只能选择一个值。但毕竟是老大写的东西，别说逻辑推理部分了，就是把论文中两个核心阶段的描述拿出来，我等普通人还是很难看懂。不相信？那么就让我这个六级的学生先做一个简单的翻译吧。阶段1a。提议者选择一个提议编号n，并向大多数接受者发送一个提议编号为n的准备请求。b.如果接收方收到编号为n的准备请求，并且该编号大于它已响应的任何准备请求，则它响应该请求并承诺不接受任何小于n的准备请求。提案，并回复它已接受的编号最高的提案（如果存在）。阶段2a。如果提议者收到大多数接受者关于其编号为n的准备请求的响应，则它向这些接受者发送编号为n和值v的接受请求，其中v是收到的响应中编号最高的提议值。如果之前没有回复过任何proposal，那么v可以是任意值，也就是可以自己指定。b.当acceptor收到编号为n的accept请求时，只要它还没有响应编号大于n的prepare请求，就会接受这个proposal。还是不明白？没错，我们通过一个简单的例子来描述这个过程。记得小时候，有很多电台可以电话点歌，打电话给接线员，告诉她你要听的歌，接下来就会播放。当然，这个过程不是免费的。想必有很多朋友在月底父母交话费的时候被社会毒打过。既然是无线电热线，接线员肯定不止一个。我们假设这个电台同时有3个操作员，他们之间互不通信。那么当短时间内有很多电话打进来的时候，你怎么决定打哪一个呢？这首歌在哪里？首先，运营商服从少数，服从多数，所以为了得到更多运营商的支持，可以不断地呼唤更多的运营商。其次，我们前面说了，这个过程是收费的。假设有个潜规则，电台会更倾向于接受出价高的人的点歌请求，那就好办了，你可以硬着头皮加钱。在这种环境下，听众要想成功点歌，就不得不依赖以上两种方式。这时候第一个听众打进来，第一阶段听众只能报价，不能提出自己想听哪首歌。这个引用可以理解为算法中的数字n。由于听众1是第一个拨打热线电话的，在他之前没有任何报价，所以这里的接线员会无条件接受第一个听众的报价并记录下来，然后给听众1返回一条回复信息。在回复信息中，运营商不仅要告诉观众他的报价是目前最高的，已经通过了，还要说明他之前没有接受过任何其他观众的点歌。这时，听众1看到自己得到了超过半数的接线员的认可，于是进入阶段2，告诉接线员他想听什么歌。当然，在这个过程中，你要告诉运营商你前一阶段的报价是多少。于是，听众1又拨通了热线，先是单独向接线员2提出选歌。运营商2收到听众1的点歌请求后，看到听众1在请求中携带的之前报价为1元，满足大于等于自己记录的最大报价的条件，于是果断接受听众1的点歌请求，在接受点歌请求后，操作员2要记录的东西又会增加，她不仅会记住接受的请求的报价金额，还会记住点播的歌曲已接受请求。然后给听众1回复，表示我已经接受你的点歌请求。当然，在听众1努力点歌的时候，其他听众也不会闲着吧？听众2虽然打来的晚了点，但还是直接激活了钞票能力，将报价提高到两块钱，上门和接线员通话。由于两元的报价高于本地记录的最高报价，运营商1和运营商2都会认同这个报价，所以他们会先将本地最高报价更新为两元。但随后，由于本地记录的信息不同，他们会给出不同的答案。如果此时另一个听众3打进来，试图以两元以下的价格向前两个接线员报价，他的报价将不会被接线员认可。这是因为，正如我们之前所说，运营商遵循拜金主义的潜规则，因此他们不会接受低于记录最高报价的报价。拒绝听众3后，我们回到前两个听众。接下来，我们根据听众1和2最先调用的时间线将时间线分为两个平行宇宙。平行宇宙1在平行宇宙1的时间轴上，我们假设听众1最先打进来。此时只有话务员2接受了听众1的点歌请求，于是听众1继续给其他话务员打电话，告诉他们想听的歌曲。对于运营商3来说，她记录的最高报价仍然比听众1早1元，所以不出意外的话，运营商3会接受听众1的歌曲请求，并更新本地记录信息。但是运算符1不同。她认可的报价已经涨到2了，所以1元的旧报价不能再向她点歌，所以运营商1会拒绝听众1的点歌请求。虽然请求没有被operator1接受，但是前面我们说过，operator必须遵循少数服从多数的原则，而listener1的请求已经被超过一半的operators接受了，所以listener1确认已选择他订购的歌曲《东风破》。平行宇宙2让我们回到平行宇宙的分叉点，回顾一下之前的情况。此时，听众2已经向接线员1和接线员2发送了报价单，并从接线员2处得知她已经以1元的报价接受了歌曲?的提议。所以在这个时间线中，我们让观众2先呼叫接线员1和2。听众2此时会在心里想，我们粉丝都是有才华的人。虽然我想听的是《简单爱》，但听完《简单爱》似乎还不错，所以我只支持听众1的选择。。于是，报价通过后，他又拿起电话，拨通了两家运营商的电话，发起点歌请求。运营商1和运营商2再次对比听众2之前携带的报价，均大于等于本地记录的最高报价，于是接受他的点歌请求。更新本地记录的信息后，将信息回复给听众2。因此，听众2的点歌请求也得到了超过半数的运营商的认可，所以听众2确认自己点的歌已被选中.看到这里，是不是好像世界线已经走到了尽头，之后的每一个结果都是《东风破》会被选中？其实Paxos算法最精彩的地方在于它更像是一场游戏，游戏中的每一步都可能影响最终的结果。平行宇宙β可以让我们稍微回到分叉点的时间，回到下一个时间点的状态。此时话务员2刚刚接受了听众1的点歌请求，听众2还没有开始呼叫。热线。这一次，站在上帝的角度，我们请观众2改变他们的选择。既然运营商2已经被别人收购了，我们应该避开，直接给运营商1和运营商3报价。可以想象，观众2的报价会得到双方运营商的认可。听众2在收到运营商半数以上的报价认可后，首先向运营商1发起点歌请求，运营商1比对报价，嗯，没问题，更新本地记录，接受他的点歌请求。按理说，现在的情况对听众2来说确实不错，只要再给接线员3打电话，就可以成功点歌。可就在这时候，观众2的室友给他打电话说：听歌好无聊，一起打一局dota吧。听众2觉得，没什么问题，暂时不点歌。但此时，听众1回过神来，他在之前的报价阶段已经获得了一半以上的认可，于是他打电话来用之前认可的报价来点歌。但在两家运营商的合作下，记录的最高报价已经涨到2元，所以听众1的点歌请求将被拒绝。到此为止，让我们整理一下。听众1的点歌请求被1接受并被2拒绝，这意味着他的提议没有被超过一半的运营商接受。无奈，观众1只能回到第一阶段，从报价单开始，重新走流程。而这一次，他将报价提高到了3元。三个运营商收到新的报价请求后，都会表示同意，并返回本地记录的信息。听众1此次收到的3个报价认可中，有2个带有之前接受的点歌信息。那么新的问题来了，他应该选择哪首歌作为他接下来要点的歌呢？在这里，监听器必须遵循与操作员相同的规则。他需要在返回的语录和歌曲信息中选择语录最高的歌曲作为他下一步选歌的依据，所以他最终会选择《简单爱》。最终，三个接线员都会接受听众1的点歌请求，而不会受到中途其他听众呼叫的干扰。最终，听众1的点歌请求被超过半数的运营商接受，于是他确定会选择《简单爱》这首歌。最后，如前所述，Paxos算法中的选举过程就像一场比赛，场上形势瞬息万变。回顾上面三个不同的时间线，来电的顺序不同，选择的运营商不同，最终可能会导致不同的结果。Paxos算法本身并不关注最终选择了哪个结果，而是关注无论如何最终达成共识。当然也有可能会遇到下面这种无法解决的情况……这种情况下，可能有两个听众交替offer成功，但是proposal歌曲失败，形成livelock的情况。这样下去，说不定一整天都没有一首歌最终入选成功。因此，在某些情况下，需要选出一个主要提议者，并且只有主要提议者才能与半数以上的接受者进行沟通，从而做出提议。说白了，就是我们常说的人。好吧，让我们做一个最后的总结。其实在我看来，Paxos算法的关键在于后者必须和前者一致，避免无休止的争论。本文只说明了resolution部分的两阶段通过示例，忽略了算法中另一个角色learner的内容。如果有兴趣，不妨阅读论文原文。毕竟Lambert老师都说了：论文原文：http://lamport.azurewebsites.net/pubs/paxos-simple.pdf
