讲清楚分布式系统中的这个算法，帮你从面试候选人中脱颖而出

目录

1. Paxos算法是什么？

2. 团建主席的选举过程

3. Paxos第一阶段：申请阶段

4. Paxos第二阶段：比较顺利的投票阶段

5. Paxos第二阶段：如果投票不太顺利呢？

6. 引申：Paxos算法专业名词解释

（1）Paxos算法是什么？

Paxos算法是一个非常经典的算法，在分布式系统中有非常广泛的使用，比如在大名鼎鼎的ZooKeeper中就有很核心的使用。

现在出去面试难度越来越大，尤其是一些知名的互联网公司。因为这些互联网公司的系统都会用到各种各样的技术，比如上述所说的ZooKeeper。

前几年，一个候选人出去面试大厂的Java职位，可能就让你说一下对ZooKeeper的原理的理解以及使用就可以了。

但是现在竞争越来越激烈，出去面试可能就会直接让你说一个技术底层的核心算法实现，比如Paxos算法就是现在大厂越来越多会问到的一个问题。

但是像Paxos这类算法实在是非常的枯燥难懂，很多文章讲这个都是用了一大堆的专业术语，还有很多的数学公式，而且里面很多概念都解释不清楚。

而对于工程方向的技术人来说，对Paxos算法只要从一个高层次的角度，对他核心的思想理解就已经可以了。

所以本文我们用比较通俗易懂的方式，从一个有趣的角度来描述一下Paxos算法的核心思想，帮助你在大厂面试中脱颖而出！

（2）团建主席的选举过程

假如现在一个公司的团队里有25个人，现在这25个人之间需要找一个人出来作为团建主席，也就是专门负责这个团队团建相关的组织事宜，比如组织大家出去旅游、出去吃喝玩乐。

这个团建的场景，以及团建主席这个角色大家应该很熟悉。

提示音：

其实这个场景引申到技术里，就是非常典型的一个分布式系统选举的场景。如果有25台机器，这些机器之间要选举出来某一台机器来作为一个Leader角色的节点，负责对集群进行整体上的 管控，是不是就跟一个团队选举一个团建主席一个道理。

此时肯定有人说，那还不简单，找一个人作为投票负责人，先让有兴趣担任团建主席的人自愿申请提名自己，然后大家分别对这些人进行投票 ，投票给谁都告诉那个投票负责人，由那个人统计各个候选人的票数，看哪个人的票数多最后就选择谁当团建主席就可以了。

这个方案确实是没问题的，但是Paxos算法是不认可这种方式的。

从Paxos算法的角度而言，它会觉得如果大家都依赖一个投票负责人来进行投票，那万一投票负责人突然失联了怎么办？

比如家里有人生病了去医院了，或者自己突然食物中毒去医院了，那大家不就没法选举出来一个团建主席了？

提示音：

引申到技术里，那就是25台机器挑选了其中一台机器作为投票选举的负责人，专门收集大家的投票，然后票数排序，最后选择出来一台机器，那万一那台机器突然宕机了怎么办？是不是会导致选举失败？所以Paxos算法是不接受这种方式的。

如下图所示：

所以现在大家就换一个思路了，这25个人不要通过一个投票负责人的方式来投票选举，而是互相之间发送短信，就通过互相发送短信的方式来选举一个团建主席。

这个好处在于哪怕25个人里有12个人都因为工作忙、在开会、孩子生病了，然后没法通过短信的方式参与投票，但是剩余的13个人还是有超过半数的人在这里，他们就可以完成最终的投票。

这样投票的过程就不用依赖于某个人了，哪怕将近一半的人都失联了，还是可以选举出来这个团建主席。

提示音：

引申到技术里，就是25台机器不要找一个投票负责人，它们互相之间发送消息进行通信，来尝试选举出来一个团建主席。

这样哪怕有12台机器都故障宕机了，但是剩余的已经过半数的13台机器还是能选举出来一个团建主席的，对系统容错性就有了大大的提升。

那么那25个人到底怎么通过互相发送短信来选举一个团建主席出来呢？

首先这25个人里，需要找出来其中5个人作为选举队长，这5个人负责跟所有人收发短信确定团建主席的人选，然后假设有3个候选人是要提名作为团建主席。

下图展示了这个过程：

（3）Paxos第一阶段：申请阶段

首先，除了那5个队长以外，所有人都需要在第一个阶段尝试申请跟投票队长进行沟通。

这个阶段，每个团队成员都会给每个队长发送一条短信，而且是不停的发送短信，短信内容就是我申请跟你进行沟通。

而每个队长也会不停收到每个成员发送过来的短信，对于队长来说，拿到短信就根据时间戳判断，如果一个人发送过来的短信是最新的，那么就回话说我同意跟你进行沟通。

如果一个成员收到超过半数（这里就是3个）的队长的回信说同意沟通，那么就可以告诉那些同意沟通的队长，自己想要投票给谁。

但是这里要注意一点，队长是会不断的收到别人发过来的短信的，所以很可能他刚刚答应跟你沟通，结果立马收到别人的短信，发现别人的短信更新，所以就同意跟别人进行沟通了，你的沟通权就会被取消。

所以如果一个成员狂发短信的过程中，突然发现自己被超过半数的队长同意沟通了，别着急高兴。

这个成员需要赶紧继续下一个阶段，告诉那些队长自己想要投票的候选人，要是发晚了，人家队长可能就在跟别人沟通了，不会理你了！

（4）Paxos第二阶段：一个比较顺利的投票阶段

这个时候一个成员获得了跟半数以上队长的沟通资格，然后就可以发送一条短信过去，说自己想要选举的人是三个候选人里的谁，这个人选可能就是成员自己拍脑袋决定的，随机选择的一个候选人而已。

这时大家考虑一下，如果3个队长都没有收到其他成员发过来的更新的申请短信，都保持着跟这个成员的沟通，那么3个队长收到他发过来的投票，比如说选举“张三 ”当做团建主席，那就直接通过了！

这个时候成员发现3个队长都回话说，就用你说的那个“张三”同学作为团建主席了，那就定了，此时团建主席就是这个“张三”了。

后续其他成员发申请短信给队长的时候，如果它们跟那三个队长获得沟通权，三个队长都会回复短信说，就是“张三”了，已经选举出来了。

这个时候，其他成员都会直接遵守这个选举结果，就认为是“张三”了。

另一种情况，此时要是某个其他成员跟 1 个知道“张三”投票结果的队长沟通，然而它跟另外 2 个知道“ 张三 ”投票结果的队长没建立上沟通，却跟剩下的2个还不知道“张三”投票结果的队长沟通，这个成员因为感知到了其中1个队长已经选择了“张三”，此时他就会尝试说，我就投票给“张三”了，通知另外2个还在茫然中的队长是“张三”。

此时另外两个茫然的队长也会选择接受“张三”的投票结果，最后5个队长都会接收“张三”这个投票结果，然后所有成员在跟队长沟通的过程中，也必然会全部接收到“张三”这个投票结果。

最后所有成员都会发现，最终的选举结果，就是：张三。这是一个非常顺利的投票阶段。

（5）Paxos第二阶段：如果投票不太顺利呢？

那么来复盘一下上面的情况，万一要是投票的过程不太顺利呢？

比如一个成员好不容易获取了跟三个队长的沟通资格，结果发送投票请求过去的时候，其中一个队长已经跟别人建立了沟通，此时就不会理睬你的投票。

那可能就只有2个队长接收了你的“张三”的投票，但是没到3个队长就不能确定选择“张三”。

这个时候怎么办？可能在这种混乱的情况下，比如5个队长里，其中2个队长接收到的投票是“张三”，1个队长是“李四”，2个队长是“王五”，没法确定选举结果。

然后所有成员继续持续不断的重复上述步骤，跟队长申请沟通，然后再尝试投票。

假如一个成员跟3个队长建立了沟通，其中2个队长告诉他自己已经接收到“张三”投票了，1个队长告诉他自己已经接收到“李四”投票了，那么这个成员会看哪个投票是最新的，比如说“李四”那个投票是最新的，那么他就会说，我就投“李四”了。

此时那2个接收到“张三”投票的队长就会改变自己的选票为“李四”，然后就会出现3个队长都接受了“李四”这个投票。

如果另外一个成员跟1个接收“李四”投票的队长以及2个接收“王五”投票的队长建立了沟通，会发现“李四“是最新选出来的，此时他会说，我就投给“李四”了。

然后那2个接收“王五”投票的队长，也会接收“李四”的投票。以此类推，大家开一下自己的脑洞，这个过程可能会持续很长时间，直到最后，所有队长都接受了“李四”的投票，所有成员也会接收“李四”的投票。

（6）引申：Paxos算法专业名词解释

其实上述过程已经用一个简单的投票选举团建主席的例子给简化的非常通俗了，虽然还是有点烧脑，但是建议大家多看几遍，肯定照着思路能大致想明白Paxos算法的一个思路。

他有两个要点：一个是超过半数的运用，一个是只用最新的投票 。

Paxos算法里，对一堆机器中扮演队长角色的机器叫做“Acceptor”，对于普通成员的角色叫做“Proposer”，互相发短信其实就是发消息进行通信，短信的时间戳就是“epoch”。

大家把上述的过程换成机器之间的通信以及选举，就能清楚这个过程了。