深入浅出 PAXOS

原文：Paxos Made Simple
作者：Leslie Lamport
发表日期：2001 年 11 月 01 日
译者：ou@https://ouonline.net/

摘要

Paxos 算法，如果用简明的语言来描述，其实很简单。

目录

• 1 引言
• 2 共识算法
  • 2.1 问题描述
  • 2.2 选定一个值
  • 2.3 获得被选定的值
  • 2.4 推进
  • 2.5 实现
• 3 实现一个状态机
• 参考文献

1 引言

Paxos 是一个用来实现具有容错特性的分布式系统的算法。很多人认为 Paxos 晦涩难懂，可能是因为原始的论文 [5] 让很多人难以理解。实际上，Paxos 可能是最简单和直观的分布式算法之一。它的核心是在 [5] 中被称为 synod 的共识算法。下一章将证明 Paxos 几乎满足了我们想要的特性。最后一章描述了完整的 Paxos 算法，这个算法是通过将共识直接应用在构建分布式系统的状态机中获得的。这个方法很多人应该都知道，因为它可能是在分布式系统理论中被引用最多的论文 [4] 的主题。

2 共识算法

2.1 问题描述

假设有一组进程，每个进程都可以提出一个值。共识算法保证在这些值中有一个会被选定。如果没有进程提出值，就不会有新的值被选定。如果某个值被选定，那么所有的进程都会收到这个值的通知。达成共识的安全性要求有¹：

• 只有进程提出的值才能被选定；
• 只能选定一个值；
• 进程直到某个值被选定后才会知道这个值被选定。

这里我们不去尝试指定精确的能让算法执行下去的条件²。然而，我们的目标是保证某些已发布的值最终会被选定，并且某个值被选定后，每个进程最终都能获知这个值。

我们使用 proposer，acceptor，learner 这三种代理来扮演在共识算法中的三种角色。在某些实现中，一个进程可能会充当其中的一个或多个代理，不过我们不需要关心进程和代理的对应关系。

假设这些代理之间可以通过互相发送消息来通信。我们使用的非“拜占庭”异步模型是这样的³：

• 每个代理都会以任意速度执行，可能会因为停止而导致出错，可能会重启。由于所有代理都可能在某个值被选定后出错然后重启，因此有些信息需要被这些出错或重启的进程记录下来；
• 消息长度不限，可以在进程间传递或复制，也有可能丢失，但是消息内容不会被修改。

2.2 选定一个值

最容易选定一个值的方法是只允许有一个 acceptor 代理。每个 proposer 都发送提案给这个 acceptor，然后 acceptor 选定收到的第一个提案。尽管这个方法很简单，但是 acceptor 的出错会导致接下来的工作都无法进行。

所以让我们来尝试使用另一种方法。我们使用多个 acceptor 来代替上面提到的单个 acceptor。每个 proposer 可以把自己提出的值发送给一组 acceptor。acceptor 可能会接受已经提出的值。如果某个值被一个足够大的 acceptor 集合接受后，它就被选定了。这里的“足够大”到底是多大呢？为了确保仅有一个值被选定，我们构造一个包含大多数代理的足够大的集合。因为任意两个“大多数”的集合至少有一个共同的 acceptor，如果每个 acceptor 最多只能接受一个值的话，这个方法是可行的。（这是在许多论文中已经观察到的多数的直观总结，显然是从 [3] 开始的。⁴）

在没有丢失消息和不会出错的情况下，即使只有一个 proposer 发布了一个值，我们也希望这个值会被选定。这需要一个条件：

P1. 一个 acceptor 必须接受它收到的第一个提案。

但是这个条件引起了一个问题。不同的 proposer 可能会在差不多同一时间提出几个值，这样就会出现同时出现多个值的情况。这会导致一个问题：每个 acceptor 都接受了一个值，但是并没有哪个值被大多数 acceptor 接受。即使只有两个值被提出，如果每个值都被差不多半数的 acceptor 接受，那么某个 acceptor 出错都可能导致不知道哪个值该被选定。

从 P1 和“当且仅当大多数 acceptor 接受了某个值，这个值才是最终被选定的”这两个条件可以推出，必须允许 acceptor 接受多个提案。我们为 acceptor 可能收到的每个不同的提案分配一个自然数作为编号，这样每个提案包括一个提案编号和一个值。为了防止歧义，我们要求不同提案的编号是唯一的。编号的获取依赖具体的实现，所以这里我们仅仅是假设这个条件成立。当某个提案被大多数 acceptor 接受，这个提案中的值就被选定了。在这种情况下，我们可以说这个提案（以及提案中的值）被选定了。

我们可以允许多个提案被选定，但是需要保证被选定的提案中的值都是相同的。结合提案编号，我们可以保证：

P2. 如果某个值为 v 的提案被选定，那么所有被选定的编号比它大的提案中的值也是 v。

由于提案编号是有序的，因此条件 P2 保证了满足“仅有一个值被选定”这个关键的安全属性。

为了能被选定，某个提案要被至少一个 acceptor 接受。因此我们可以通过满足以下条件来满足 P2：

P2a. 如果某个值为 v 的提案被选定，那么任意一个 acceptor 已经接受的所有编号比它大的提案，它们的值也是 v。

我们依然需要 P1 来保证一定会有提案被选定。因为通信是异步的，某个提案可能会被某个在此之前没收到任何提案的 acceptor c 接受。假设一个新的 proposer “醒来”并发布了一个编号更大的提案，这个提案包含了一个不同的值，P1 要求 c 必须接受这个提案，但是这样就违反了条件 P2a。为了保证两者都成立，我们将 P2a 加强一下：

P2b. 如果某个值为 v 的提案被选定，那么任意 proposer 提出的所有编号比它大的提案，它们的值也是 v。

由于被 acceptor 接受的提案都是由 proposer 提出的，因此从 P2b 能够推导出 P2a，从而推导出 P2。

为了明白怎样才能满足 P2b，让我们先来看下怎么证明它。假设某个编号为 m，值 为 v 的提案被选定了，接下来将证明任意编号为 n（n > m）的提案的值也是 v。通过对 n 使用归纳法，证明过程可以变得容易一点。我们假设编号从 m 到 n-1 的提案的值都是 v，在这个假设条件下我们可以证明编号为 n 的提案的值也是 v。如果被选定的提案编号为 m，那么必然有一个包含大多数 acceptor 的集合 C，C 中的每个 acceptor 都接受了它。结合上面的归纳假设，从 m 被选定这个假设可以推出：

集合 C 中的每个 acceptor 都接受了编号从 m 到 n-1 中的某个提案，并且这些被接受了的提案的值都是 v。

如果一个集合 S 包含大多数 acceptor，那么它和集合 C 至少有一个共同的成员。我们通过确保以下条件的不变性，就可以保证编号为 n 的提案的值是 v：

P2c. 对任意的 v 和 n，如果一个编号为 n，值为 v 的提案被发布了，那么存在一个包含大多数 acceptor 的集合 S，使得以下条件中的一个成立：
    a）S 中没有一个 acceptor 接受的提案编号小于 n；
    b）v 是 S 接受的所有编号小于 n 的提案中，编号最大的那个提案的值。

因此我们可以通过确保 P2c 的不变性来满足 P2b。

为了确保 P2c 的不变性，如果某个 proposer 要发布编号为 n 的提案，那么它必须知道在所有编号小于 n 的提案中编号最大的那个提案的值，并且这个编号最大的提案必须将要或已经被大多数 acceptor 接受。获取已经被接受的提案很简单，预测将要被接受的提案却很难⁵。为了避免对未来进行预测，proposer 承诺将来不会出现这样的情况。也就是说，proposer 要求 acceptor 不要接受任何编号小于 n 的提案。因此得到以下发布提案的算法：

1. 某个 proposer 选择一个提案编号 n 然后发送一个请求给某个集合中的每个 acceptor，请求它们回复：
   • a）承诺不再接受编号小于 n 的提案；
   • b）在已经接受的编号小于 n 的提案中编号最大的提案（如果有的话）。

   这样的一个请求被称为编号为 n 的 prepare 请求。

2. 如果某个 proposer 收到了大多数 acceptor 的上述回复，它就可以发布一个编号为 n，值为 v 的提案。如果回复中没有提案，那么 proposer 可以选择任意的 v 值，否则 v 必须是收到的回复中编号最大的提案的值。

proposer 通过向一组 acceptor 发送接受该提案的请求来发布提案。（这些 acceptor 不一定是响应初始请求的那些 acceptor。）我们把这一步称为 accept 请求。

上面介绍的是 proposer 的算法。那么 acceptor 呢？acceptor 可以接收来自 proposer 的两种请求：prepare 请求和 accept 请求。acceptor 可以忽略任何请求而不影响安全性，因此，我们仅考虑它什么时候才可以回复请求。acceptor 可以回复任何 prepare 请求；但是仅当 acceptor 接受某个提案，才可以回复对应的 accept 请求。也就是说：

P1a. 当且仅当某个 acceptor 没有回复过任何编号大于 n 的 prepare 请求，它才可以接受编号为 n 的提案。

注意，P1a 包含 P1。

在提案编号唯一的假设前提下，我们有了一个完整的选择满足所需安全属性的值的算法。我们通过进行一个小优化来获得最终的算法。

假设某个 acceptor 收到一个编号为 n 的 prepare 请求。但是在此之前它已经回复过某个编号大于 n 的 prepare 请求，承诺不再接受任何编号为 n 的新提案。acceptor 没有理由回复新的 prepare 请求，因为它不会接受该 proposer 要发布的编号为 n 的提案。因此我们让 acceptor 忽略这样的 prepare 请求。我们也可以让 acceptor 忽略已接受的提案的 prepare 请求。

通过这个优化，一个 acceptor 只需要记录它接受过的编号最大的提案，以及已回复的编号最大的 prepare 请求的编号。因为在出错的情况下也需要保证 P2c 的不变性，即使 acceptor 出错后重启也必须记录这些信息。注意到 proposer 可以完全忽略某个提案——只要它永远不会发布和这个提案编号相同的另一个提案。

把 proposer 和 acceptor 的行为组合起来，我们得到下面的 2 阶段算法：

• 阶段 1
  • （a）某个 proposer 选择一个编号为 n 的提案并发送一个编号为 n 的 prepare 请求给大多数 acceptor；
  • （b）如果某个 acceptor 收到一个编号为 n 的 prepare 请求，n 比它已回复的任何 prepare 请求的编号都大，那么它回复该请求的内容包括：承诺不会接受任何编号小于 n 的提案，以及它已经接受的编号最大的提案（如果有的话）。
• 阶段 2
  • （a）如果某个 proposer 收到大多数 acceptor 对于它编号为 n 的 prepare 请求的回复，那么它会发送一个 accept 请求给这些 acceptor。这个 accept 请求的内容是一个编号为 n，值为 v 的提案，其中 v 是在收到的回复中编号最大的提案的值。如果收到的回复中没有提案，则 v 可以为任意值；
  • （b）如果某个 acceptor 收到包含编号为 n 的 accept 请求，它会接受该提案——除非它已经回复过另一个编号大于 n 的 prepare 请求。

一个 proposer 只要遵循发布提案的算法，就可以发布多个提案。它也可以在协议期间随时放弃提案。即使提案的请求或回复可能在它被放弃了很久之后才到达，算法也能保证正确性。当其它 proposer 已经在尝试提出编号更大的提案时，放弃自己编号较小的提案是一个好主意。因此，如果一个 acceptor 因为已经收到了编号更大的 prepare 请求而忽略编号较小的 prepare 或者 accept 请求时，它最好通知被丢弃的请求的发出者。这是一个性能优化，不会影响正确性。

2.3 获得被选定的值

为了获得已被选定的值，learner 需要知道被大多数 acceptor 选定的提案。一个直观的算法是，让每个 acceptor 在接受提案的时候把提案发送给所有的 learner。这个方法能让 learner 尽早得知被选定的值，不过这要求每个 acceptor 给每个 learner 发送回复——总的回复数量是 acceptor 数量和 learner 数量的乘积。

在不会出现“拜占庭”错误的假设下，一个 learner 很容易从另一个 learner 那里得知被选定的值。我们可以让 acceptor 把各自接受的提案发送给一个特殊的 learner，然后由这个 learner 告知其它 learner 被选定的值是什么。这个方法使得所有的 learner 都需要一个额外的步骤才能知道被选定的值是什么。另外这个方法也不是那么可靠，因为这个特殊的 learner 可能会出错。但是这个方法需要的回复数量是 acceptor 数量和 learner 数量之和。

更一般的方法是，acceptor 把各自接受的提案发送给一组特殊的 learner。当某个值被选定时，这些 learner 中的每一个都可以通知所有的 learner。使用一个更大的特殊 learner 集合能提供更好的可靠性，代价是更大的通信复杂度。

因为消息可能会丢失，learner 可能永远不会知道某个值被选定。learner 可以询问 acceptor 已经接受的提案，但是如果某个 acceptor 的出错可能会使我们无法知道大多数 acceptor 是否接受了某个特定的提案。在这种情况下，learner 只有在新的提案被选定的时候才能知道被选定的值是什么。如果某个 learner 需要知道某个值是否被选定，它可以让某个 proposer 使用上述算法发布一个提案。

2.4 推进

我们很容易构造这样的一个场景：两个 proposer 各自发布一系列编号递增的提案，但是没有一个提案被选定。proposer p 完成了编号为 n1 的提案的阶段 1，接着另一个 proposer q 也完成了编号为 n2（n2>n1）的提案的阶段 1。p 的阶段 2 的编号为 n1 的 accept 请求被忽略了，因为所有 acceptor 都承诺了不再接受任何编号小于 n2 的新提案。因此，p 开始了一个编号为 n3（n3>n2）的新提案的阶段 1，导致 q 的阶段 2 的 accept 请求被忽略了。依此类推。

为了保证算法可以继续执行，一个特殊的 proposer 被选出来作为唯一可以发布提案的发布者。如果这个特殊的 proposer 可以成功地和大多数 acceptor 进行通信，并且发布了一个编号比已经使用过的编号都要大的提案，那么它就可以成功发布一个能被接受的提案。它如果发现某些请求中的提案编号更大，可以丢弃当前提案并重试，最后一定能够找到一个足够大的提案编号。

如果系统（proposer，acceptor，以及通信网络）中足够多的部分都正常工作，通过选择一个特殊的 proposer，算法就一定能够执行下去。[1] 中的著名的结论表明，一个可靠的选择 proposer 算法一定是通过随机性或实时性来实现——例如使用超时机制。然而，无论选举是否成功，安全性都可以保证。

2.5 实现

Paxos 假设有若干进程组成一个网络。在它的共识算法里，每个进程扮演着 proposer，acceptor 和 learner 中的角色。算法会选择一个 leader 作为特殊的 proposer 和 learner。Paxos 共识算法正如上面描述的那样，请求和回复都被当做普通的消息发送。（回复的消息会用对应的提案编号来标记以防止混淆。）acceptor 在出错期间需要用可靠的存储设备来保存必须记录的信息。acceptor 需要在发送回复之前把要发送的内容记录在可靠的存储设备中。

剩下的就是介绍一种机制，以确保不会发布两个具有相同编号的提案。不同的 proposer 从不相交的集合中选择他们的编号，因此两个不同的 proposer 永远不会发布具有相同编号的提案。每个 proposer 把它将要发布的编号最大的提案记录在可靠的存储设备中，然后用比已经使用的编号更大的提案编号，从阶段 1 开始执行。

3 实现一个状态机

一个向单一中央服务器发出指令的客户端的集合，就是一个简单的分布式系统实现。其中的服务器可以被看作是一个确定性状态机，它以某种顺序执行客户端的指令。状态机有一个当前状态，它通过将指令作为输入来执行一个操作，然后生成一个输出和一个新的状态。举个例子，一个分布式银行系统的客户端可能是出纳员，状态机的状态可能是所有客户的账户余额。当且仅当账户余额大于取款时，状态机通过执行一条减少账户余额的指令来实现提款的操作，同时将取款前后的余额作为输出。

在使用单独中央服务器的实现方案中，如果这个服务器出错了，那么整个服务都失败了。因此我们改为使用一组服务器，其中的每个服务器都独立实现了这个状态机。因为这个状态机是确定性的，只要执行相同顺序的指令，所有的服务器都会生成相同的状态和输出序列。发出指令的客户端可以使用任意服务器生成的输出。

为了保证所有的服务器都执行相同顺序的状态机指令，我们实现了一系列独立的 Paxos 共识算法实例，其中第 i 号实例选定的值作为第 i 个状态机指令。每个服务器在每个算法实例里扮演所有的角色（proposer，acceptor，learner）。假设这组服务器是固定的，所以所有共识算法的实例都使用相同的代理集合。

在正常的操作中，一个服务器被选为 leader，即在共识算法中的所有实例中作为特殊的 proposer（唯一可以发布提案的服务器）。客户端向 leader 发送指令，leader 决定该指令在执行序列中的位置。如果 leader 决定某条客户端指令应该是第 135 条指令，它会尝试使这条指令成为共识算法的第 135 号实例选定的值。通常情况下这都会成功。但也有可能失败，原因可能是服务器出错，或者另一个服务器认为它自己才是 leader，对第 135 条指令有异议。但是共识算法会保证最多只有一条指令会被选定为第 135 条指令。

这种方法有效的关键在于，在 Paxos 共识算法中，在阶段 2 之前，被提出的值还没有被选定。之前提到的，在 proposer 算法的阶段 1 完成之后，要么将要被提出的值已经确定下来，或者 proposer 可以自由提出任何值。

接下来将要介绍 Paxos 状态机在正常运行时是怎样工作的，之后会讨论可能出问题的地方。考虑下在前一个 leader 出错了然后选出了新 leader 的时候会发生什么。（系统重启是一个特例，在这种情况下还没有提出任何指令。）

新 leader，作为这个共识算法所有实例中的 learner，应该知道大部分被选定的指令。假设它知道第 1-134，138 还有 139 条指令——也就是共识算法中的第 1-134，138 还有 139 号实例选定的值。（我们后面会看到这些命令间隙是怎样产生的。）然后它对第 135-137 号，以及所有大于 139 号的实例执行阶段 1。（接下来会说明这是怎么做到的。）假设这些执行的结果决定了第 135 和 140 号实例将要提出的值，但是在其它实例中并没有限制可被提出的值。leader 然后对第 135 和 140 号实例执行阶段 2，从而选定了第 135 和 140 条指令。

leader，以及其它也获知了 leader 所知道的所有指令的服务器，现在可以执行 1-135 号指令了。然而 leader 现在还不能执行它已经知道的第 138-140 号指令，因为第 136 和 137 号指令还没被选定。leader 也可以将接下来客户端发送过来的两条指令作为第 136 和 137 号指令。然而，我们提出一条特殊的“no-op”指令作为第 136 和 137 号指令来立刻填充指令中间的间隙，并保持状态不变。（通过对共识算法中的第 136 和 137 号实例执行阶段 2 来完成。）一旦这些“no-op”指令被选定，第 138-140 号指令就可以被执行了。

第 1-140 号指令现在已经被选定了。leader 已经对共识算法中所有编号大于 140 的实例执行完了阶段 1，现在可以在这些实例的阶段 2 提出任何值。它把收到的客户端的下一条指令作为第 141 号指令，并将这条指令作为共识算法中第 141 号实例在阶段 2 提出的值。它把收到的客户端的下一条指令作为第 142 号指令，依此类推。

leader 可以在确定它提出的第 141 号指令被选定之前就提出第 142 号指令。所有它发出的提出第 141 号指令的信息可能会丢失，因此在其它服务器知道 leader 提出第 141 号指令之前第 142 号指令可能就被选定了。当 leader 没有收到对第 141 号实例执行阶段 2 的消息的预期回复时，它将会重新传输这些消息。如果一切顺利，它提出的指令将会被选定。然而，这可能第一个出错，在选定的指令序列中间造成间隙。一般来说，假设 leader 可以提前获取 a 条指令——也就是说，当第 i 条指令被选定时，它可以提出从第 i+1 到 i+a 条指令，这会造成最多 a-1 条指令的间隙。

新选定的 leader 需要对共识算法中的无限多个实例执行阶段 1——在上面的情景中，也就是第 135-137 号，以及所有大于 139 号的执行实例。如果对所有实例使用相同的提案编号，它只需发送一条合理的短消息给其它服务器就能完成。在阶段 1，acceptor 仅在已经从某个 proposer 那里收到阶段 2 的消息的情况下，才用简单的“OK”做出响应。（在这个例子中，第 135 和 140 号实例就是这种情况。）这样，一个作为 acceptor 的服务器可以给所有实例回复一条合理的短信息。因此，对无限多个实例执行阶段 1 不会带来任何问题。

由于 leader 出错和选举新 leader 应该很少发生，执行一条状态机指令（即在指令/值上达成一致）的耗时，就是执行共识算法中阶段 2 的耗时。可以证明，在出现故障时能够最终达成一致的算法中，Paxos 共识算法的阶段 2 有最小可能耗时。因此，Paxos 算法本质上是最优的。

这里关于系统正常运行的讨论，是建立在总是只有一个 leader 的前提下，不包括当前 leader 出错以及选举新 leader 时的情况。在异常环境下，选举 leader 也可能失败。如果没有服务器充当 leader，也就不会有新指令被提出。如果多个服务器都认为自己是 leader，它们都可以在共识算法的同一个实例中提出各自的值，这有可能导致无法选定一个值。然而，安全性被保留了——两个不同的服务器永远不会在第 i 个状态机指令的选择上选定不同的值。选择单个 leader 只是为了保证算法能够执行下去。

如果服务器的集合可以被改变，那么需要有某种方法来确定哪些服务器来实现共识算法中的哪些实例。一个最简单的方法是通过状态机本身。当前服务器的集合可以被看成是状态机的某个状态，并且可以使用普通的状态机指令来修改。我们可以把执行共识算法中第 i+a 个实例的服务器集合，指定为执行了第 i 条状态机指令之后的状态，这样就可以实现 leader 提前获取 a 条指令。这为任意复杂的重新配置算法提供了一个简单的实现。

参考文献

[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.

[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).

[3] Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978.

[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.

[5] Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, May 1998.

译者注