Paxos 追本溯源

Paxos 算法是莱斯利兰伯特（Leslie Lamport）于 1990 年提出的一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。在常见的分布式系统中，总会发生诸如机器宕机或网络异常等情况。Paxos 算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，且保证不论发生任何异常，都不会破坏整个系统的一致性。

1982年，Lamport 与另两人共同发表了论文 The Byzantine Generals Problem，提出了一种计算机容错理论。在理论描述过程中，为了将所要描述的问题形象的表达出来，Lamport 设想出了下面这样一个场景：

拜占庭帝国有许多支军队，不同军队的将军之间必须制订一个统一的行动计划，从而做出进攻或者撒退的决定，同时，各个将军在地理上都是被分隔开来的，只能依靠军队的通讯员来进行通讯。然而，在所有的通讯员中可能会存在叛徒，这些叛徒可以任意篡改消息，从而达到欺骗将军的目的。

这就是著名的“拜占延将军问题”。从理论上来说，在分布式计算领城，试图在异步系统和不可靠的通道上来达到一致性状态是不可能的，因此在对一致性的研究过程中，都往往假设信道是可靠的。而事实上，大多数系统都是部署在同一个局城网中的，因此消息被篡改的情况非常罕见，另一方面，由于硬件和网络原因而造成的消息不完整问题，只需一套简单的校验算法即可避免。因此，在实际工程实战中，可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。那么，在这种情况下需要什么样的算法来保证一致性呢？

Lamport 在 1990 年提出了一个理论上的一致性解决方案，同时给出了严格的数学证明。鉴于之前采用故事类比的方式成功的闻述了拜占廷将军问题，因此这次 Lamport 同样用心良苦地设想出了一个场景来描述这种一致性算法需要解决的问题及其具体的解决过程：

在古希腊有一个叫做 Paxos 的小岛，岛上采用议会的形式来通过法令，议会中的议员通过信使进行消息的传递。值得注意的是，议员和信使都是兼职的，他们随时有可能会离开议会厅，并且信使可能会重复的传递消息，也可能一去不复返。因此，议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。

Paxos 算法名称的由来就是取自论文中提到的 Paxos 小岛。

Paxos 算法详解

兰伯特提出的 Paxos 算法包含 2 个部分：

• 一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识；
• 另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。

1. Basic Paxos

假设我们要实现一个分布式集群，这个集群是由节点 A、B、C 组成，提供只读 KV 存储服务。你应该知道，创建只读变量时，必须要对它进行赋值，而且这个值后续没法修改。因此所有节点必须要先对只读变量的值达成共识，然后所有节点再一起创建这个只读变量。

假设，当有多个客户端（比如客户端 1、2）试图创建同一个只读变量（比如 X）时，客户端 1 试图创建值为 3 的 X，客户端 2 试图创建值为 7 的 X，这样要如何达成共识，实现各节点上 X 值的一致呢？

为了帮助人们更好地理解 Basic Paxos 算法，兰伯特在讲解时使用了一些独有而且比较重要的概念，提案、准备（Prepare）请求、接受（Accept）请求、角色等等，其中最重要的就是角色。因为角色是对 Basic Paxos 中最核心的三个功能的抽象，比如，由接受者（Acceptor）对提议的值进行投票，并存储接受的值。

1.1 Paxos 中的三种角色

在 Basic Paxos 中，有提议者（Proposer）、接受者（Acceptor）、学习者（Learner）三种角色，他们之间的关系如下：

提议者（Proposer）
提议一个值，用于投票表决。通常情况下，集群中收到客户端请求的那个节点就是提议者。

接受者（Acceptor）
对每个提议的值进行投票，并存储接受的值。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商并接受和存储数据。可以看到，一个节点是可以身兼多个角色的。

学习者（Learner）
被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。通常，学习者是数据备份节点。

其实，这三种角色，在本质上代表的是三种功能：

• 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；
• 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；
• 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。

1.2 Paxos 如何达成共识

在 Basic Paxos 中，兰伯特使用提案代表一个提议。在一个提案中，除了提议值，还包含提案编号，提案编号相当于全局唯一标识（该标识的生成并不是 Paxos 算法关注的地方）。假设使用 [n, v] 表示一个提案，其中 n 为提案编号，v 为提议值。整个共识协商分为两个阶段进行，具体协商过程如下：

回到开头的那个例子，我们假设客户端 1 的提案编号为 1，客户端 2 的提案编号为 5，并假设节点 A、B 先收到来自客户端 1 的准备请求，节点 C 先收到来自客户端 2 的准备请求。注意，这里的客户端实际为收到客户端请求的集群节点。

准备（Prepare）阶段

先来看第一个阶段，首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求：

注意，在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了。接着，当节点 A、B 收到提案编号为 1 的准备请求，节点 C 收到提案编号为 5 的准备请求后，进行如下处理：

• 由于之前没有通过任何提案，所以节点 A、B 将返回一个尚无提案的响应。也就是说节点 A 和 B 在告诉提议者，我之前没有通过任何提案，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。

• 节点 C 也是如此，它将返回一个尚无提案的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。

当节点 A、B 收到提案编号为 5 的准备请求，和节点 C 收到提案编号为 1 的准备请求时，进行如下处理：

• 当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个尚无提案的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。

• 当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。

接受（Accept）阶段

首先客户端 1、2 在收到大多数节点的准备响应后，会分别发送接受请求：

当客户端 1 收到大多数的接受者（节点 A、B）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空（即尚无提案），所以就把自己的提议值 3 作为提案的值，发送接受请求 [1, 3]。

同理，当客户端 2 收到大多数的接受者（节点 A、B、C）的准备响应后，由于准备响应中的提案值为空，所以就把自己的提议值 7 作为提案的值，发送接受请求 [5, 7]。

当三个节点收到 2 个客户端的接受请求时，会进行这样的处理：

当节点 A、B、C 收到接受请求 [1, 3] 时，由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5，所以提案 [1, 3] 将被拒绝。当节点 A、B、C 收到接受请求 [5, 7] 时，由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5，所以就通过提案 [5, 7]，也就是接受了值 7，三个节点就 X 的值为 7 达成了共识。之后，如果集群中有学习者，当接受者通过了一个提案时，就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么它也通过该提案，接受该提案的值。

假如，节点 A、B 已经通过了提案 [5, 7]，节点 C 未通过任何提案，那么当客户端 3 提案编号为 9 时，通过 Basic Paxos 执行“SET X = 6”，最终三个节点上 X 值是多少呢？

准备阶段：当节点 A、B 收到提案编号为 9 的准备请求时，因为提案编号 9 大于它们之前响应的准备请求的提案编号 5，但这两个节点之前通过了提案 [5, 7]，因此接受者 A、B 会在准备请求的响应中，包含已经通过的最大编号的提案信息 [5, 7]，并承诺以后不再响应提案编号小于等于 9 的准备请求，不会通过编号小于 9 的提案；由于节点 C 之前没有通过任何提案，所以返回一个尚无提案的响应。并承诺以后不再响应提案编号小于等于 9 的准备请求，不会通过编号小于 9 的提案。

接受阶段：当客户端 3 收到大多数的接受者的准备响应后（节点 A、B、C），根据响应中提案编号最大的提案的值来设置接受请求中的值。因为来自节点 A、B 的准备响应中为 [5, 7] 和 C 的准备响应为空，所以就把节点 A、B 的响应值 7 作为提案值，发送接受请求 [9, 7]。当节点 A、B、C 收到接受请求 [9, 7] 时，由于提案的提案编号 9 不小于三个节点承诺能通过的提案的最小提案编号 9，所以就通过提案 [9, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识。

总结一下：Basic Paxos 只能就单个值达成共识，属于一个基础算法，具体是通过二阶段提交的方式来达成共识的。除了共识之外，Basic Paxos 还实现了容错，在集群中少于一半的节点出现故障时，集群也能工作。

2. Multi-Paxos

兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法。上面说过，Basic Paxos 是通过二阶段提交来达成共识的。在准备阶段，接收到大多数准备响应的提议者，才能发起接受请求进入接受阶段：

而如果我们直接通过多次执行 Basic Paxos 实例，来实现一系列值的共识，会存在这样几个问题：

• 如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，导致协商失败，需要重新协商。想象一下，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。

• 2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。

那么如何解决上面的 2 个问题呢？可以通过引入领导者和优化 Basic Paxos 执行来解决。

2.1 领导者（Leader）

我们可以通过引入领导者节点，也就是说，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了：

实际上，在兰伯特的论文中，没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby 中，主节点（也就是领导者节点）是通过执行 Basic Paxos 算法进行投票选举产生的。

那么，如何解决第二个问题，也就是如何优化 Basic Paxos 执行呢？

2.2 优化 Basic Paxos 执行

我们可以采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，优化 Basic Paxos 执行。即领导者节点上的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入到接受阶段：

什么是稳定状态？
准备阶段的意义，是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶段就没有意义了，也就是可以省掉了。

和重复执行 Basic Paxos 相比，Multi-Paxos 引入领导者节点后，因为只有领导者节点一个提议者，只有它说了算，所以就不存在提案冲突。另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。

3. Chubby 的 Multi-Paxos 实现

下面，我们以 Chubby 的 Multi-Paxos 实现为例，具体讲解一下 Multi-Paxos 的具体实现。

首先，它通过引入主节点，实现了兰伯特提到的领导者（Leader）节点的特性。也就是说，主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。另外，在 Chubby 中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。比如在实际场景中，几天内都是同一个节点作为主节点。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。

其次，在 Chubby 中实现了兰伯特提到的“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制。最后，在 Chubby 中，为了实现了强一致性，读操作也只能在主节点上执行。 也就是说，只要数据写入成功，之后所有的客户端读到的数据都是一致的。具体过程如下：

• 所有的读请求和写请求都由主节点来处理。当主节点从客户端接收到写请求后，作为提议者，执行 Basic Paxos，将数据发给所有节点，并且在大多数的服务器接受了这个写请求后，再响应给客户端成功：

• 当主节点接收到读请求后，只需要查询本地数据，然后返回给客户端就可以了：

由于 Chubby 的所有写请求都在主节点处理，限制了集群处理写请求的并发能力，约等于单机。因为在 Chubby 的 Multi-Paxos 实现中，也约定了“大多数原则”，即只要大多数节点正常运行，集群就能正常工作，所以 Chubby 能容错 (n-1)/2 个节点的故障。