[数据结构与算法]Paxos算法帮你选媳妇，不信你还不懂

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

听起来牛逼哄哄的是不是，现实也确实挺牛逼的，后来的Raft算法，也是基于Paxos演变而来的。我们常用的Redis的哨兵模式选举，Zookeeper的Zab协议其实都是Raft算法的落地实现。可以说Paxos算法是现在绝大多数一致性算法的基石。

那Paxos算法具体是怎样的呢？都说Paxos算法难懂，其实听完这个故事你就明白了。

你是个在北京漂泊多年的苦逼程序员，单身多年， 一直找不到媳妇。如今接近年底，听说你快回家过年了，村里的媒婆们个个都兴奋不已，终日奔走乡里帮忙找漂亮姑娘，希望可以挣上这一笔媒人钱。

乡里有个规矩，凡是找到的漂亮姑娘，都先得通知你的七大姑八大姨看看，七大姑八大姨中大多数人认可了，这姑娘就定下来了，最后媒婆会通知你和你的朋友们：“孩子，隔壁村的如花是你的了！”。

Paxos算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。（简单说：即七大姑八大姨就“对给你选的某个媳妇”达成一致）。Paxos将系统中的角色分为提议者 (Proposer，即媒婆)，决策者 (Acceptor，即七大姑八大姨)，和最终决策学习者 (Learner， 即你和朋友们)。

乡里漂亮的姑娘特别的多，为了作区分呢，媒人们会给姑娘们一个个进行编号，例如：“1号，2号，3号......”。一般来说，号码越大的姑娘越漂亮，比如3号一定比2号漂亮......

通常你的选亲活动分为3个阶段：

第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。

1.? ?Prepare（准备）阶段，媒婆会给你的七大姑八大姨发一张姑娘的照片和编号。七大姑八大姨们收到照片后，需要给予回应。如果觉得姑娘可以的话，那么他们需要做出两个承诺和一个回应。

两个承诺：

• 不再接受编号小于等于（注意：这里是<= ）当前介绍的姑娘编号的候选人（简单来说， 没现在这姑娘漂亮的不考虑了）。

• 不再接受编号小于当前介绍的姑娘的其他候选人的最终确认。（之前准备接受的姑娘，因为现在有更漂亮的，也绝不接受了）。

（对，亲戚们懂你，就是这么渣！）

一个回应：

• 不违背以前作出的承诺下，回复已经确认的姑娘信息，比如编号和照片（简单来说，就是告知媒婆已经确定接受的姑娘信息，不考虑其他的了）

?第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

2.? Accept阶段，媒婆收到多数七大姑八大姨的回应以后，向所有的七大姑八大姨发出一个Propose请求，跟大家确认，是不是真的选这个姑娘了？七大姑八大姨针对收到的Propose请求进行Accept处理，做出最终确认。

第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

?3.? Learn阶段，媒婆在收到大多数七大姑八大姨的Accept的回应以后，意味着你的媳妇就已经选成功了！这时候媒婆会拿着村里的大喇叭在村里喊：“王二狗要娶如花啦！！！”。这样你和你的朋友们就被告知了。

过程是不是很简单啊。

Paxos算法有一个很经典的缺陷，就是活锁问题。什么活锁问题呢？我们知道在Prepare阶段时，一旦亲戚们被其他媒婆介绍了更漂亮的姑娘时，他们就会承诺不会对之前回应的编号更低（没那么漂亮）的姑娘给出最终确认。

简单来说，就是这个过程：

Prepare阶段，王媒婆拿来一张照片，发给七大姑八大姨看的时候，他们告诉王媒婆这姑娘行啊。

王媒婆很开心，刚想进入Accept阶段对姑娘进行最终确认，结果半路杀出来个李媒婆进入Prepare阶段，给了个更漂亮的姑娘照片，七大姑八大姨一看，哇塞，这个姑娘更美啊，可以可以，给出回应了。这个时候王媒婆想确认之前那个姑娘，七大姑八大姨不认了，纷纷说：“不要这个了......，有更漂亮的了”。

于是，王媒婆给你选媳妇失败了......

那李媒婆一定能成功吗？当然不一定啦，半路可能又杀出个周媒婆，又搅糊了......

这就造成全村每天都轰轰烈烈给你选媳妇，但是可能永远没有结果。然后，你就变成老光棍了！

要解决这个问题也很简单，就是一旦有人给你介绍媳妇了，在一段时间内，就禁止其他人发出提议给你介绍其他姑娘。这样你的婚事在这段时间内就可能已经撮合成功了。

以上内容仅希望帮助大家理解算法过程，深入了解可寻找其他专业文章对照学习！谢谢大家支持

原创不易，请勿随意抄袭和引用，侵权必究！?