分布式共识算法之Paxos图解

1 分布式一致性：共识算法

对于一个分布式系统来说，保障集群中所有节点的数据完全相同（即一致性）是很重要的，随着多节点的引入，这影响的是整个分布式系统对外服务的表象一致性。也就是说，一个分布式系统想要做到完全的一致性，需要对外表现为顺序一致性，即各个节点上的操作顺序都一致。

而在现实运行情况下，节点可能故障，可能增加，甚至可能被篡改，这就给分布式一致性带来了挑战。在这种情况的干扰下，分布式系统需要通过某些机制，来就一些事情达成一致的看法，也就是共识。

但要注意的是，共识算法并不能一次性解决所有分布式的不一致问题。不同的算法能解决不同异常情况下的问题，所以共识算法也有分类：

• 崩溃容错算法（Crash Fault Tolerance）：典型代表是Paxos、Raft、ZAB等。
• 拜占庭容错算法（Byzantine Fault Tolerance）：FBFT为代表的确定性算法，PoW为代表的的概率算法那等。
• 拜占庭将军问题：Lamport曾经提出过在分布式网络下的一种节点作恶场景。描述的是拜占庭需要通过信使来在守卫边境的多个将军间传递消息，以达成一致的决定。如果此时出现叛徒，故意发送不同的消息来干扰共识的达成，应该如何让忠诚的将军们保持行动一致。映射到分布式系统中就是多个节点就消息达成共识时如果出现错误节点传递了错误的消息该怎么办。

对于拜占庭容错，往往都需要通过其他方面的激励或惩罚，来让“诚实”表达的节点利益最大化，本文描述的Paxos算法不解决拜占庭的问题，只解决崩溃容错算法条件下达成分布式共识的问题。

2 Paxos

2.1 背景

有一种说法，说所有共识算法都是Paxos。这种说法的来源，一方面是由于Paxos的第一次提出非常的早，另一方面则是因为，Paxos解决的其实是在分布式环境下，所有服务达成一次某个值的共识的过程，而这一过程，可以说每种共识算法都绕不开。

最早在1990年，Paxos的作者Leslie Lamport就提交了关于Paxos的论文《The Part-Time Parliament》，但直到2001年Lamport第三次发表简化版的相关论文，且2006年Google使用Paxos的理念实现了分布式系统，该算法才被大众所理解和追捧。

1990年的论文中，Lamport描述了一个名为Paxos的希腊城邦（算法得名于此），这个城邦是按照民主的议会制度来进行选举的，所有的居民进行提议和投票来选出决议。但是居民们不想花时间一直在选举上，大家都不定时地来提议、了解提议、投票、看进展等等，而Paxos算法的目标就是通过少数服从多数的方式来达成最终的一致意见。但是审稿人觉得这个背景太复杂了，要求删去，Lamport不乐意就没继续投稿了（真大师）。 八年后的1998年，Lamport再次整理算法进行投稿，但是大家还是不太理解，因此也没有引出多少水花。 又过了三年，2001年，Lamport再次进行了简化，发表了《Paxos Made Simple》，去掉了希腊城邦的背景，里面甚至没有一个公式。但依然直到2006年被Google实现后才开始吸引大家的眼球，而作者Lamport也才获得了2013年图灵奖。

2.2 算法过程

2.2.1 少数服从多数

首先要认识到，这是一个分布式系统下的共识算法，要解决的问题，简化一点，就是一堆机器，每一台都可能会收到客户端的一条消息，那需要将自己收到的消息，告诉其他的机器，让所有分布式系统中的机器，达到最终的一致，这就是达到共识。

Paxos采取了一个我们非常熟悉的达成共识的方法：少数服从多数。只要有超过一半的机器认可某一个消息，那么最终就所有机器都接受这条消息并将它作为本次的结论。而竞选失败的少数派消息，就会被拒绝，并由第一个从客户端处接收到该消息的机器，向客户端发送失败结果，由客户端进行重试，去尝试在下一轮竞选中胜出。

少数服从多数，说来简单，如果是一群人的话，大家碰个头一起举手表决就好了。但是放到一个分布式系统中就变复杂了。机器之间怎么传递提议，怎么表决，怎么统计多数，网络传输需要时间，在表决过程中，其他机器收到了新的消息怎么办，都需要一整套机制来解决。

下面就来逐步讲解Paxos的过程，但在讲解过程之前，先说Paxos中最常见的两种角色：

• Proposer：提案者。也就是在选举中提出提案的人，放到分布式系统里，就是接收到客户端写操作的人。一切行为都由Proposer提出提案开始，Paxos会将提案想要进行的操作，抽象为一个“value”，去在多台机器中传递，最后被所有机器接受。
• Acceptor：批准者。Acceptor 从含义上来说就是除了当前Proposer以外的其他机器，他们之间完全平等和独立，Proposer需要争取超过半数（N/2 1）的 Acceptor 批准后，其提案才能通过，它倡导的“value”操作才能被所有机器所接受。

除了以上两种角色，实际上Paxos还会提到Learner，即学习者这个角色，该角色是在达成决议时，对结论的学习者，也即是从其他节点“学习”最终提案内容，比较简单。需要注意，这些角色只是在不同时间下，逻辑上的划分，实际上任何一台机器都可以充当这三个角色之一。

2.2.2 一个简单的提案

先描述最简单的情况，假设现在有四台机器，其中一台收到了来自客户端的写操作请求，需要同步给其他机器。

此时这台收到请求的机器，我们称它为Proposer，因为它将要开始将收到的请求，作为一个提案，提给其他的机器。这里为了方便，我们假设这个请求是要将一个地址设置为“深圳”，那么如下图所示：

此时，其他的Acceptor都闲着呢，也没其他人找，所以当它们收到Proposer的提案时，就直接投票了，说可以可以，我是空的，赞成提案（同意提议）：

到这里，就还是一个简单的同步的故事，但需要注意的是，这里Proposer实际上是经历了两步的。

在这个简单的提案过程中，Proposer其实也经历了两个阶段：

1. Prepare阶段：Proposer告诉所有其他机器，我这里有一个提案（操作），想要你们投投票支持一下，想听听大家的意见。Acceptor看自己是NULL，也就是目前还没有接受过其他的提案，就说我肯定支持。
2. Accept阶段：Proposer收到其他机器的回复，说他们都是空的，也就是都可以支持接受Proposer的提案（操作），于是正式通知大家这个提案被集体通过了，可以生效了，操作就会被同步到所有机器正式生效。

2.2.3 两个提案并发进行

现在考虑一个更复杂的场景，因为我们处于一个分布式的场景，每台机器都可能会收到请求，那如果有两台机器同时收到了两个客户端的不同请求，该怎么处理呢？大家听谁的呢？最后的共识以谁的为准呢？如下图

在这种情况下，由于网络传输的时间问题，两个Proposer的提案到达各个机器，是会存在先后顺序的。假设Proposer 1 的提案先达到了 Acceptor 1 和 Acceptor 2，而Proposer 2 的提案先达到了 Acceptor 3，其达到 Acceptor 1 和 Acceptor 2 时，由于机器已经投票给Proposer 1 了，所以Proposer 2 的提案遭到拒绝，Proposer 1 达到 Acceptor 3 的时候同样被拒。

Acceptor们迷了，Proposer们也迷了，到底应该接受谁？此时，还是遵循自由民主的法则——少数服从多数。

Proposer 1 发现超过半数的Acceptor都接受了自己，所以放心大胆地发起要求，让所有Acceptor都按照自己的值来操作。而Proposer 2 发现只有不到半数的Acceptor支持自己，而有超过半数是支持Proposer 1 的值的，因此只能拒绝Client 2，并将自己也改为Proposer 1 的操作：

到此为止，看起来没有问题，但是，这是因为恰好Acceptor的数量是单数，可以选出“大多数”，但是因为同时成为Proposer的机器数量是不确定的，因此是无法保证Acceptor的数量一定是单数的，如下面这种情况就无法选出“大多数”了：

这时，两个Proposer有可能总是先抢到一个Acceptor的支持，然后在另一个Acceptor处折戟沉沙，算法就一直循环死锁下去了。为了解决这种情况，Paxos给提案加了一个编号。

2.2.4 给提案加上编号

之前我们Proposer的提案都是只有操作内容的，现在我们给他加一个编号，即：

• Proposer 1 的提案为：[n1, v1]
• Proposer 2 的提案为：[n2, v2]

假设Proposer 1 接到Clint 1 的消息稍微早一点，那么它的编号就是1，Proposer 2 的编号就是2，那么他们的提案实际就是：

• Proposer 1 的提案为：[1, { Set Addr = "深圳"}]
• Proposer 2 的提案为：[2, { Set Addr = "北京"}]

此时，Paxos加上一条规则：

• Acceptor如果还没有正式通过提案（即还没有Accept使操作生效），就可以接受编号更大的Prepare请求。

所以，回到上面的困境

1. 当Proposer 1 想要向Acceptor 2 寻求支持时，Acceptor 2 一看你的编号（1）比我已经支持的编号（2）要小，拒绝拒绝。此时Proposer 1 由于没有得到过半数的支持，会重新寻求支持。
2. 而当Proposer 2 想要向Acceptor 1 寻求支持时，Acceptor 1 一看你的编号（2）比我已经支持的编号（1）要大，好的你是老大我听你的。此时Proposer 2 已经得到了超过半数的支持，可以进入正式生效的Accept阶段了。

这里需要补充一下，Proposer 1 这里支持提案失败，他是怎么让自己也接受Proposer 2 的提案的呢？

所以这里的后续会发生的事情是：

1. Proposer 2 发现得到了过半数的支持，开始向所有Acceptor发送Accept请求。
2. 所有Acceptor接收到Accept请求后，按照之前Prepare时收到的信息与承诺，去生效Proposer 2 的提案内容（即Set Addr = “北京”的操作）。
3. Proposer 1 之前已经收到了所有Acceptor的回复，发现没有得到过半数的支持，直接回复Client 1 请求失败，并变成一个Acceptor（或者说Learner），接受Proposer 2 的Accept请求。

这里再想多一点，考虑另一种场景：假设Proposer 2 的Accept请求先达到了Acceptor 2，然后Proposer 1 向Acceptor 2 发送的Prepare请求才到达 Acceptor 2，会发生什么呢？

最直观的处理是， Acceptor 2 直接拒绝，然后Proposer 1 走上面的流程，但Paxos为了效率，又增加了另一条规则：

• 如果一个Prepare请求，到达Acceptor时，发现该Acceptor已经接受生效了另一个提案，那么它除了回复提案被拒绝外，还会带上Acceptor已经通过的编号最大的那个提案的内容回到Proposer。Proposer收到带内容的拒绝后，需要修改自己的提案为返回的内容。

此时会发生的事情就变成了：

1. 此时Acceptor 2 除了会拒绝它的请求，还会告诉Proposer 1，说我已经通过并生效了另一个编号为2的提案，内容是Set Addr = “北京”。
2. 然后Proposer 1 查看回复时，发现已经有Acceptor生效提案了，于是就修改自己的提案，也改为Set Addr = “北京”，并告知Client 1 你的请求失败了。
3. 接着Proposer 1 开始充当Proposer 2 的小帮手，帮他一起传播 Proposer 2 的提案，加快达成共识的过程。

PS：这里需要注意，编号是需要保证全局唯一的，而且是全局递增的，否则在比较编号大小的时候就会出现问题，怎么保证编号唯一且递增有很多方法，比如都向一个统一的编号生成器请求新编号；又比如每个机器的编号用机器ID拼接一个数字，该数字按一个比总机器数更大的数字间隔递增。

2.2.5 一些异常情况

上面的规则是不是就能保证整个算法解决所有问题了呢？恐怕不是，这里再看看一些异常情况。

异常情况一：假设现在有三个Proposer同时收到客户端的请求，那么他们会生成全局唯一的不同编号，带着各自接收到的请求提案，去寻求Acceptor的支持。但假设他们都分别争取到了一个Acceptor的支持，此时由于Prepare阶段只会接受编号更大的提案，所以正常情况下只有Proposer 3 的提案会得到所有Acceptor的支持。但假设这时候Proposer 3 机器挂了，无法进行下一步的Accept了，怎么办呢？那么所有Acceptor就会陷入持续的等待，而其他的Proposer也会一直重试然后一直失败。

为了解决这个问题，Paxos决定，允许Proposer在提案遭到过半数的拒绝时，更新自己的提案编号，用新的更大的提案编号，去发起新的Prepare请求。

那么此时Proposer 1 和Proposer 2 就会更新自己的编号，从【1】与【2】，改为比如【4】和【5】，重新尝试提案。这时即使Proposer 3 机器挂了，没有完成Accept，Acceptor也会由于接收到了编号更大的提案，从而覆盖掉Proposer 3 的提案，进入新的投票支持阶段。

异常情况二：虽然更新编号是解决了上面的问题，但却又引入了活锁的问题。由于可以更新编号，那么有概率出现这种情况，即每个Proposer都在被拒绝时，增大自己的编号，然后每个Proposer在新的编号下又争取到了小于半数的Acceptor，都无法进入Accept，又重新加大编号发起提案，一直这样往复循环，就成了活锁（和死锁的区别是，他们的状态一直在变化，尝试解锁，但还是被锁住了）。

要解决活锁的问题，有几种常见的方法：

• 当Proposer接收到回复，发现支持它的Acceptor小于半数时，可以不立即更新编号重试，而是随机延迟一小段时间，来错开彼此的冲突。
• 可以设置一个Proposer的Leader，全部由它来进行提案，这即使共识算法的常见套路，选择一个Leader。这需要进行Leader的选举，以及解决存活性检查以及换届的问题。实际上就已经演变成Multi-Paxos了。

异常情况三：由于在提案时，Proposer都是根据是否得到超过半数的Acceptor的支持，来作为是否进入Accept阶段的依据，那如果在算法进行中新增或下线了机器呢？如果此时一些Proposer知道机器数变了，一些Proposer不知道，那么大家对半数的判断就会不一致，导致算法出错。

因此在实际运行中，机器节点数的变动，也需要作为一条要达成共识的请求提案，通过Paxos算法本身，传达到所有机器节点上。

为了使Paxos运行得更稳定，不需要时刻担心是否有节点数变化，可以固定一个周期，要求只有在达到固定周期时才允许变更节点数，比如只有在经过十次客户端请求的提案与接受后，才处理一次机器节点数变化的提案。

那如果这个间隔设置地相对过久，导致现在想要修改节点数时，一直要苦等提案数，怎么办呢？毕竟有时候机器坏了是等不了的。那么可以支持主动填充空的提案数，来让节点变更的提案尽早生效。

2.2.6 Paxos协议的两阶段

抽象和完善一下这个过程，就是：

1. Prepare准备阶段：在该阶段，Proposer会尝试告诉所有的其他机器，我现在有一个提案（操作），请告诉我你们是否支持（是否能接受）。其他机器会看看自己是否已经支持其他提案了（是否接受过其他操作请求），并回复给Proposer（如果曾经接受过其他值，就告诉Proposer接受过什么值/操作）。
   1. Acceptor如果已经支持了编号N的提案，那么不会再支持编号小于N的提案，但可以支持编号更大的提案；
   2. Acceptor如果生效了编号为N的提案，那么不会再接受编号小于N的提案，且会在回复时告知当前已生效的提案编号与内容。
2. Accept提交阶段：在该阶段，Proposer根据上一阶段接收到的回复，来决定行为：
   1. 如果上一阶段超过半数的机器回复说接受提案，那么Proposer就正式通知所有机器去生效这个操作；
   2. 如果上一阶段超过半数的机器回复说他们已经先接受了其他编号更大的提案，那么Proposer会更新一个更大的编号去重试（随机延时）；
   3. 如果上一阶段的机器回复说他们已经生效了其他编号的提案，那么Proposer就也只能接受这个其他人的提案，并告知所有机器直接接受这个新的提案；
   4. 如果上一阶段都没收到半数的机器回复，那么提案取消。
   5. PS：接受其他提案，以及提案取消的情况下，Proposer就要直接告诉客户端该次请求失败了，等待客户端重试即可。

这里可以看到，超过半数以上的机器是个很重要的决定结果走向的条件。

至此，已经描述完了针对一次达成共识的过程，这被称为Basic-Paxos。

那如果有多个值需要达成共识呢？

2.2.7 Multi-Paxos

如果有多个值要不断地去针对一次次请求达成共识，使用Basic-Paxos也是可以的，无非就是一遍遍地执行算法取得共识并生效嘛，但在分布式系统下，容易由于多次的通信协程造成响应过慢的问题，何况还有活锁问题存在。因此Lamport给出的解法是：

1. 先选择一个Leader来担当Proposer的角色，取消多Proposer，只有一个Leader来提交提案，这样就没有了竞争（也没有了活锁）。同时，由于无需协商判断，有了Leader后就可以取消Prepare阶段，两阶段变一阶段，提高效率。
2. 对于每一次要确定的值/操作，使用唯一的一个标识来区分，保证其单调递增即可。

对于选择Leader的过程，简单的做法很多，复杂的也只需要进行一次Basic-Paxos即可。选出Leader后，直到Leader挂掉或者到期，都可以保持由它来进行简化的Paxos协议。

如果有多个机器节点都由于某些问题自认为自己是Leader，从而都提交了提案，也没关系，可以令其退化成Basic-Paxos，也可以在发现后再次选择Leader即可。

3 其他共识算法

这里也顺便对比一下另外两种常见的共识算法：ZAB和Raft。

3.1 ZAB

ZAB全称是Zookeeper Atomic Broadcast，也就是Zookeeper的原子广播，顾名思义是用于Zookeeper的。

ZAB理解起来很简单，在协议中有两种角色：

• Leader节点：有任期的领导节点，负责作为与客户端的连接点接受读写操作，然后将其广播到其他节点去。
• Follower节点：主要是跟随领导节点的广播消息进行同步，并关注领导节点的健康状态，好随时取而代之。

既然有Leader节点，就必然有Leader的选举过程，ZAB的选举，会先看各个节点所记录的消息的时间戳（数据ID），时间戳（数据ID）越大，节点上的数据越新，就会优先被投票，如果数据ID比较不出来，就再看事先定义的节点的优先级（节点ID）。当大家根据上述优先级投票，超过半数去支持一个节点时，该节点就成为Leader节点了。

通过心跳算法可以共同检查Leader节点的健康度，如果出现问题（比如机器下线、网络分区、延迟过高等），就会考虑重新选举。

可以看出，这种选举方式相对Paxos是比较方便高效的，而且选出Leader节点后，就可以直接通过Leader节点接受消息进行广播，而不需要进行两阶段提交。

其实ZAB就很像选出了Leader的Multi-Paxos，两者的差异主要在选Leader的流程上。

3.2 Raft

Raft的应用比Paxos要多，有人认为Raft是Multi-Paxos的改进，因为Raft的作者也曾研究过Paxos。既然Paxos是前辈，为什么应用的反而要少呢？这是因为Basic-Paxos相对比较耗时，而Multi-Paxos，作者并没有给出具体的实现细节，这虽然给了开发者发挥的空间，但同样可能会在实现的过程中由于开发者不同的实现方式带来不同的问题，对于一个分布式共识算法，谁也不知道潜在的问题会不会就影响到一致性了。而Raft算法给出了大量实现细节，简单说就是，实现起来更不容易出错。

Raft协议同样是需要选举出Leader的，从这里也能看到，共识算法大都会走向选举出一个Leader的方向，来提升效率和稳定性。不同之处可能只在于选举的方式，以及消息同步的方式。

Raft的选举，会在上一任Leader失去联系时发起，每个Follower便有机会成为Candidate，参与选举。之所以说有机会，是因为每个Follower都会先等一会，看是否有其他候选人过来拉票，避免人人都跑去凑热闹参与选举浪费通信，这个等待的时间是在一个范围内随机的。

候选者参与选举时会产生一个term概念，每个候选者会先投自己一票，然后带着自己的term和自己的日志信息（代表着数据的新旧）去拉票，其他的Follower先看候选者的term是否大于等于当前自己的term，再看其日志信息是否比自己新，如果都满足就会投票。候选者收到超过半数的投票的话，就会成为新的Leader了。

在这个过程中投票的Follower也会更新自己的term为自己投票的候选者的term，这样就可以拒绝低于它的term的候选者了。而候选者如果被拒绝，也会回去更新自己的term以获得支持。

选出Leader后，Leader会把自己的日志发给大家做同步，以保持大家和自己的日志是一样的，然后就进行后续的接收客户端请求的环节。

可以看到Raft和Multi-Paxos也都要选举出一个Leader节点来，不同之处在于，Raft选举的Leader节点上的日志信息是最新最全的，这一方面可以不丢失日志信息的顺序，另一方面也可以让选举过程简化（日志信息的顺序总是好比较的），而Multi-Paxos选Leader的过程偏随机，就是看谁先拉拢更多节点的支持并快速落定，这一方面会使其日志不连续，另一方面也会使得其实现变得复杂和相对不可控。

但实际上不连续也不完全是缺点，它也可以提高写入的并发性能，所以虽然Raft实现相对更简单，但微信的PaxosStore还是选择了Paxos，甚至它都没有选择Multi-Paxos，而是Basic-Paxos，就是为了进一步避免单点依赖和切换Leader时的拒绝服务，来提高可用性。

可以看到，共识算法基本都需要解决两个基本问题：

1. 如何提出一个需要达成共识的提案（选举Leader、随机投票...）
2. 如何让多个节点对提案达成共识（广播、复制、投票...）

在这两个问题的处理方案上选择不同，就会导致性能、可用性等指标的不同，所以其实，兵器各有利弊，还是要看使用场景和使用的人。

参考文档

• 理解这两点，也就理解了paxos协议的精髓
• Paxos 的诞生
• Paxos 协议简单介绍
• 【超详细】分布式一致性协议 - Paxos
• Paxos算法 - 维基百科
• 分布式系统的一致性与共识算法-基础理论
• Paxos和Raft的前世今生
• raft算法与paxos算法相比有什么优势，使用场景有什么差异
• 共识算法：一次性说清楚 Paxos、Raft 等算法的区别