Paxos 问题指分布式系统中存在故障（Fault），但不存在恶意 corrupt 节点场景（消息可能丢失但不会造假）下的共识达成（Consensus）问题。Google Chubby 的作者 Mike Burrows 说过这个世界上只有一种一致性算法，那就是 Paxos，其它的算法都是残次品。

背景介绍

现在，我们来想像一个充满了民主与法制的联邦议会，有三种角色参会：

• Proposer：发起提案的提议员

• Acceptor：给每个提案投票的议员，如果大多数议员同意则通过提案

• Learner：记录员记录议员们通过的提案

当然，总有人身兼多职，例如：A 是 Proposer、Acceptor、Learner 三位一体的工具人。

在议会中，需要由 Proposer 先发起一个提议，Accptors 为该提案投票，通过提案后 Learners 进行相关的记录。而在这个过程中，交流（communication）必然是少不了的。

那么，将该议会制度代入二进制世界。首先需要我们解决的问题是议会中人们的交流问题。而对于我们的目标（实现分布式系统）来说，要解决的就是不同主机相互之间的交流问题。当然我们可以通过各式各样的方法传递数据，当然最通用也最适合分布式定义的方式当然是通过网络传输的 HTTP/TCP 协议了。

因此，我们也需要对网络的传输特性有所了解：

1. 网络传输是异步的。

   当然这不是必须的，但与此同时你也要接受你实现的系统运行速度可以与乌龟比速度的事实以及一旦出现了死锁或其他问题导致的整个系统不可用。造成的结果已经至少违反了 CAP 理论中的 AP 了。

2. 网络传输的不确定性。

   通常情况下，网络数据包会以一个比较稳定的速度到达它的目的地。但也会发生一些意外：丢包、断连、重复包。甚至会因为网络拥塞导致同时发的包到达相同目的地的时间差距很大。

当然，不仅仅要考虑网络的原因，我们还要考虑作为议会参与者对应的机器的问题：

1. 无法与其他参与者通过网络通信

2. 因各种各样的问题断电或者终止程序的运行

3. 终止后重启，重新参会的问题

4. .....

好了，万事开头难，二进制世界总是从第一个 0/1 开始，随后将不断出现的问题加以解决，画上一个看不到结尾的句号。

提出提案

一个有容错（fault-tolerant）能力的分布式系统需要满足哪些基本条件：

• 当没有提案（proposal）出现时，不会改变记录员（learner）记录的内容。

• 对于同一个提案编号（proposal number）有多个提案值（proposal value）时，最终只会选择一个唯一的值。

• 记录员应该记录被议员（Acceptors）通过的提案值。

在分布式系统中，我们不能强求其拥有像本地数据库一样的 ACID 能力。

原因是多种多样的，例如：无法避免的网络延迟、网络闪断等。

但我们可以保证其 BASE 能力，计算机的世界总是充满了权衡的味道。

注意，Paxos 只对一个值（accepted value）的提案进行了描述，即所有的提案都是针对同一个值进行改变。例如：A 发起一个提案将 accepted value 值修改为 5，随后 B 发起一个提案将 accepted value 值修改为 2。

选择唯一的提案（Choosing a Value）

单议员场景（Single Acceptor）

我们来考虑一个最简单的情况，议会中只有一个 Proposer、Acceptor 和 Learner。每个提案被 Proposer 发起后，Acceptor 直接同意提案并由 Learner 记录结果。

显然，三个角色无论哪一个不能正常运行，都会导致整个系统的不可用。这可不是我们想看到的。

多议员场景（Mutiple Acceptors）

由于多个 Acceptors 出现在我们的议会中，对于每一个 Proposer 发起的提议，每个 Acceptor 都会对提案发表自己的意见（同意、拒绝、弃权）。

当然，正常情况下 Acceptor 不会弃权，这种情况只出现在网络断连等特殊情况。

议员当然不能毫无目的的发表自己的看法，他们也需要一个共同的核心价值观：喜新厌旧。没错，这是根据数据的特性来确定的。例如，作者今年 22 岁，到了明年涨到了 23 岁，而作者用户信息栏中的 22 岁就会变得毫无意义。而对于未填写的年龄信息来说，22 岁这条信息就比未填写更新更有意义。

那么，如何在如此多的意见中公平的选出一个最终的唯一的结果呢？

结论就是选出一个大多数（majority）议员都同意的结果。也就是我们常说的少数服从多数，用数学公式来表示为 (​acceptors.size / 2) + 1 [手动向下取整]。

当然，大多数原则也还是太过的虚幻，我们还是举个例子来说明其科学性。假设我们有 5 位记录员记录通过的提案，但在将「accepted proposal number，accepted value」从「OLD，1」 修改为「NEW，2」这个提案时发生了意外，其中两位记录员由于走神没有记录下这个提案的结果，但还是有三个记录员记录成功了该提案，因此提案通过。当我们现在想知道该提案的结果时，只需要随便选三个记录员问一下他们记录的内容，选取其中 proposal number 最新的即可，假设我们的运气太不好了恰好问到了走神的两位记录员，但我们还是会从第三位记录员口中得知「NEW，2」这个最新的结果。与此相反的是，假设三位记录员都没有记录成功最新提案，但提案又被错误地通过了，随便找三位记录员询问记录结果时就会有几率询问到错误的结果（或过期的数据）。因此，我们要保证只有过半的人都成功记录了提案，才可以通过提案。

我们这里引入了 proposal number 这个概念，其作用就是以一个递增序列的形式标记提案，数字最大的就可以认为是最新的提案。

此时，我们应该将现实世界中的多议员的场景考虑的比较全面了。

多提议员场景（Multiple Proposers）

和现实世界不同的是，二进制世界还有一个颇为常见的场景：并行场景。即在一种极端情况下，两个 Proposers 同一时间提出了自己的提案，由于多个 Proposers 不会共享他们的 proposal number，因此 Acceptor 可能会或快或慢的接收到两个相同 proposal number 的提案。

对于 Acceptor 来说，最先接收到的提案根据喜新厌旧的原则是必然会被同意的，而后面紧随其后的相同提案编号（proposal number）的提案由于不是最新的数据，所以会拒绝该提案。

需要注意的是，对于 Acceptor 来说，是否是新的数据完全取决于 proposal number，与 proposal value 毫无关系。

因此，到这一步来说可以分为两种情况进行讨论：Acceptors 个数为奇数、Acceptors 个数为偶数。

如果是奇数，无论如何接收提案，总会有过半的 Acceptors 同意某一提案，而拒绝另一提案。

但如果是偶数，有一半的 Acceptors 同意了 A 提案，另一半同意了 B 提案。两者都没有过半，因此都会被拒绝。

此时我们发现，在设备正常运转的情况下，同样的输入但造成的结果却是不确定的，这显然无法满足算法的基本特性：确定性。

当然，保证两个 proposal number 在 Proposals 不相互通信的情况下不同还是比较简单的，例如可以通过 timestamp-serverId-counter 的数据格式来保证。这里不是重点，感兴趣的读者可以参考《分布式系统 分布式ID生成方案》的几种核心思想。

过期数据场景（Expiration Data）

在网络分区或其他场景影响下，也会造成这样一种情况（情况很多），Acceptor 会接收到的 proposal number 比在自身中记录的 accepted proposal number 低的提案。这显然是因为其他 Acceptor 存在旧数据造成的。

解决方案当然是将已经记录的相对更新的数据记录传播到其他的 Learner 中并记录。当一个提案被 Proposer 提出，传播到多个 Acceptors 时，Acceptor 会发现接收到的 proposal number 比在自身中记录的 accepted proposal number 低的提案。这显然是因为其他 Acceptors 存在旧数据造成的。因此我们只需要将已经通过的最新提案返回到 Proposer，Proposer 根据返回的记录中最新提案重新修改 proposal 的内容，并再次 issue proposal 即可将全部节点更新为最新提案。

因此我们将整个提交过程分为两个阶段：prepare 阶段和 accept 阶段。

并且基于上述思想，我们还可以在不影响数据正确性的前提下做进一步优化：Acceptor 会分别记录 prepare 和 accept 两阶段所接收的最新 proposal number，并直接忽略低于对应阶段 proposal number 的网络包。

具体的操作流程如下图：

以下是上图的详细描述：

第一阶段

提议员（Proposer）选择一个提议编号 pn，并向所有议员（Acceptor）广播一个编号 pn 的 Prepare(n) 请求。

如果议员（Acceptor）收到的准备请求的编号 n 大于其已答复的任何准备 Prepare 请求的编号，则议员（Acceptor）对该请求作出答复，并承诺 Promised(pn) 不接受任何编号小于 pn 且其已接受的编号最高的提案。

第二阶段

如果提议员（Proposer）从大多数议员（Acceptor）处收到对其准备请求（编号 pn）的响应，则它向这些接受人中的每一个发送一个接受请求，请求编号 pn 的提案，其值为 pv。如果没有发现有一个议员（Acceptor）接受过一个 pv，那么向所有的议员（Acceptor）发起自己的值和提议编号 pn，否则，从所有接受过的值中选择对应的提议编号最大的，作为提议的值。

如果议员（Acceptor）收到编号为 pn 的提案的接受请求，则除非议员（Acceptor）已对编号大于 pn 的准备请求作出响应，否则接受该提案。

记录通过的提案（Learning a Chosen Value）

在 N 个 Acceptors​ 及 M 个 Learners​ 的场景下，网络中一次 learn 操作会造成 N * M​ 量级的数据包 request & response。

而选取 Learner Leader 可以将网络中数据包量级压缩到 N + M​。但一旦 Learner Leader 宕机，整个系统也会不可用。

这时我们可以选取多个 Learner Leader 来补充系统的可用性，但会对系统复杂度造成进一步的提升。

FIX

FIX Leader机制

现在，我们将上面描述中讲的问题总结一下：

1. 在多提议员的场景下，我们要保证每个提议员发出的议案编号全局唯一。

   避免数据混乱，维持算法确定性。

2. 在多议员和多记录员的场景下，我们最好保证记录员有 Leader 负责从 Acceptor 接收通过的提案以及将该提案传播给其他 Learner。

   优化网络中网络包的数量。

另外，过期数据场景中提到的方案也会造成新的问题——活锁（Live Lock）。

Paxos 算法可能形成活锁而永远不会结束，如下图实例所示：

回顾两个承诺之一，Acceptor 不再应答 proposal number 小于等于当前请求的 prepare 请求。意味着需要应答 proposal number 大于当前请求的 prepare 请求。两个 Proposers 交替 Prepare 成功，而 Accept 失败，形成活锁。

当然，选举一个 Proposer Leader 是可以解决活锁的问题的，顺便也能把上述 proposal number 全局号唯一的问题解决了。

针对上述问题且依据上文描述，Paxos 系统时需要拥有以下特性：

• Proposers 需要 Leader

• Learners 需要 Leader

• 引入对上述两种 Leader 实施的可用性方案

• 实现两阶段提交的议题选择方案

引入 Proposal Leader 和 Learner Leader，我们再来看看当前 Paxos 系统的结构吧。

Proposer Leader 的出现实现了 request 的序列化，它让每个接收到的 command 以队列的形式进行 issue proposal 的操作并保证了大多数 command 的正确执行。但也只是大多数，请求仍然会因为网络故障以及“Split Brain“的问题提交失败。