译自 Leslie Lamport 2001, Paxos Made Simple

1. 引言

用来实现容错分布式系统的 Paxos 算法被认为是难以理解的，但实际上它是分布式算法里最简单和最显然的。其核心是一个共识算法。下一节表明，在满足几条必须具备的性质的前提下，这个算法几乎是不可避免的。通过使用状态机的方法来构建一个分布式系统，并且把共识算法应用到这个系统，可以得到完整的 Paxos 算法。这个方法很有名，因为分布式系统领域引用貌似最多的那篇文章的主题就是它。

2. 共识算法

2.1 问题

假定有一系列可以提议数值 (译者注：原文用的单词是 value，但其实可以是任何信息，比如命令) 的进程。共识算法保证提议的数值里只有一个被选中。如果没有数值被提议，则不会有数值被选中。如果有数值被选中，则那些进程能知晓选中的数值。共识的安全性要求是

只有被提议过的数值才能被选中，
只能选中单个数值，
仅当一个数值真的被选中时，进程才知晓这个值被选中了。

我们让三类代理来实施这三种角色：提议者，接受者，学习者。具体实现中，单个进程可能执行多种任务，但目前我们不需要管这种细节。

假定代理之间通过发送消息互相交流。我们使用惯常的异步、非拜占庭模型，也就是：

代理的工作速度是任意的，并且有可能停止或者重启。由于所有代理都可能在一个值被选中后挂掉然后重启，除非挂掉重启的代理能记住一些信息，否则解决方案是不可能存在的。
消息的传递可能需要任意长的时间，消息有可能会重复、丢失，但不会被损坏。

2.2 选一个数值

选取一个数值的最简单方法是只有一个接受者的情况。提议者向接受者发出提议，接受者选取第一个收到的数值。尽管简单，这个方案不令人满意，因为接受者如果挂掉，后面的事情就进行不下去了。

那么我们换一种方法。假设我们有多个接受者。提议者向接受者集合发出一个提议值。接受者可以接受提出的值。仅当足够多的接受者接受了一个值，才认为这个值被选中了。多少算足够多？为了保证只有一个数值被选中，任何由多数代理组成的集合就满足条件。由于任何两个多数集之间至少有一个公共接受者，那么只要接受者最多接受一个数值，这个方法就是可行的。

在没有机器挂掉或者信息丢失的情况下，我们要求，如果只有一个提议者提议了一个数值，这个值应当被选中。也就是说：

P1. 接受者必须接受它收到的第一个数值。

但这带来一个问题。不同的提议者可能在几乎相同的时间提出几个数值，导致每个接受者都接受了一个数值，但没有一个数值是被多数派接受的。就算只有两个提议的数值，如果每个被大约半数接受，那么单个接受者挂掉就可能会让知晓到底那个数值被选中成为不可能。

P1 以及关于仅当一个数值被多数接受者接受时才被选中的要求意味着接受者必须被允许接受不止一个数值。我们对接受者可能接受的不同的提议做记录，方法是对每个提议赋予一个编号 (自然数)，这样，一个提议就由一个提议编号和数值组成。为了避免混淆，我们要求不同的提议具有不同的编号。具体的实现方法各有不同。一个数值被选中当且仅当一个具有那个数值的提议被多数接受者接受。在那个情况下，我们说那个提议被选中了。

我们可以允许多个提议被选中，但必须保证选中的提议具有相同的数值。通过针对提议编号的归纳，只需要保证下面的条件就够了：

P2. 如果数值为 v 的提议被选中，则每个被选中的、编号更高的提议的数值也是 v。

由于编号是全序的，条件 P2 保证了关键的安全性质，也就是仅有一个数值被选中。

要被选中，提议必须被至少一个接受者接受。所以，可以通过满足下面的条件来满足 P2:

P2a. 如果数值为 v 的提议被选中，则每个被任意接受者接受的编号更高的提议的数值是 v。

我们仍然保留 P1 来保证有提议被选中。由于通讯是异步的，一个提议可能在某个接受者 c 从未收到任何提议的情况下被选中。假设一个新的提议者“醒来”并且发出一个编号大且数值不同的提议，P1 要求 c 接受这个提议，这就违背了 P2a。要想保留 P1 和 P2a，需要强化 P2a:

P2b. 如果一个数值为 v 的提议被选中，那么由任何提议者发出的任何编号更高的提议的数值都是 v。

由于提议必须先被提出才能被接受，P2b 蕴含了 P2a，而 P2a 蕴含了 P2。

为了知道如何满足 P2b，我们来考虑如何证明它成立。我们假定，某个编号为 m 而数值为 v 的提议被选中，然后证明任何编号为 n > m 的提议的数值也是 v。证明可以通过对 n 的归纳实现，也就是说，在已知编号在闭区间 [m, n-1] 内的提议的数值都是 v 的前提下，证明编号为 n 的提议的数值也是 v。要让编号为 m 的提议被选中，必须存在多数集合 C 使得其中每个接受者都接受这个提议。结合归纳假设，m 被选中这个前提意味着：C 里的每个接受者接受了编号在 [m, n-1] 内的提议，并且编号在 [m, n-1] 内且被任意一个接受者接受的提议具有数值 v。

由于任何包含多数接受者的集合 S 至少包含 C 的一个元素，我们可以在下述不变量得到保证的情况下得出结论说编号为 n 的提议的数值为 v：

P2c. 对任何 v 和 n，如果发布过数值为 v 而编号为 n 的提议，则存在由多数派组成的集合 S 满足条件：要么 (a) S 内的接受者没有接受过任何编号小于 n 的提议，要么 (b) S 内的接受者接受过的编号低于 n 的所有提议里编号最大的那个对应的数值是 v。

于是，我们可以通过保证 P2c 来满足 P2b。

为了保证 P2c，提议者在准备发布编号为 n 的提议时必须知道已经或者即将被某个多数派接受者集合接受的、编号低于 n 的提议里编号最高的那个提议 (如果存在的话)。了解已经被接受的提议的相关信息不难，难的是预测未来的接受情况。与其去预测未来，提议者通过获取关于不会存在这样的接受事件的承诺来控制。换句话说，提议者要求接受者不再接受任何编号低于 n 的提议。这引出下面的发布提议的算法。

提议者选择新的编号 n 并发送给某个接受者集合的每个成员，请求接受者回复下述内容：
1. 承诺不再接受任何编号低于 n 的提议，以及
2. 接受者接受过的编号低于 n 的提议里编号最大的那个提议 (如果存在的话)。

准备

如果提议者从多数接受者那里收到了所请求的回复，则发布一个编号为 n 数值为 v 的提议，这里 v 是收到的回复里编号最高的提议的数值，或者，在收到的回复不包含任何提议的情况下，提议者自己选取的任意值。

提议者向某个接受者集合的成员发送请求，要求对方接受提议。(这个接受者集合不必与之前响应初始请求的集合相同。) 我们把这个请求称为接受请求。

这描述了一个提议者算法。接受者呢？它接受两类来自提议者的请求：准备请求，以及接受请求。接受者可以无视任何请求而不影响安全性。所以，我们只需要描述何时允许它响应一个请求。它总是可以响应一个准备请求。当且仅当它还没承诺不接受一个提议时，它可以响应一个接受请求并接受这个提议。换句话说：

P1a. 当且仅当一个接受者还没响应过编号大于 n 的准备请求时，接受者可以接受编号为 n 的提议。

注意到 P1a 蕴含了 P1。

现在我们有了选出满足安全性质的数值的方法 —— 假定提议编号是唯一的。最终的算法只需要一点额外的优化。

假设一个接受者收到编号为 n 的准备请求，但之前已经响应过编号大于 n 的准备请求 (因此承诺不再接受编号为 n 的新提议)。于是，这个接受者没有理由去响应这个新的请求，因为它不会接受提议者想要发布的编号为 n 的提议。于是我们让接受者无视这样的准备请求。我们也让它无视针对它已经接受过的提议的准备请求。

有了这个优化，接受者只需要记忆它接受过的编号最高的提议，以及它响应过的编号最高的准备请求。由于即便在挂掉的情况下 P2c 也必须被遵守，接受者必须记住这个信息 (即便挂掉并重启)。注意，提议者总是可以抛弃并忘记一个提议 —— 只要它不试图重新发布编号相同的新提议。

把提议者和接受者的行为放到一起，我们看到这个算法的执行分两个阶段。

第一阶段. (a) 提议者选取一个编号 n 并且向多数派接受者发出编号为 n 的准备请求。 (b) 如果接受者收到的准备请求的编号 n 大于其响应过的任何准备请求的编号，则它对请求的回应是，承诺不再接受任何编号小于 n 的提议，同时返回其接受过的提议的最高编号 (如果有的话)。

第二阶段. (a) 如果提议者从多数接受者收到其编号为 n 的准备请求的响应，则它向这些接受者发出一个编号为 n 而数值为 v 的接受请求，这里 v 是它收到的响应里编号最高的提议的数值，或者 —— 在没有收到响应提议的情况下 —— 这个提议者指定的任何数值。(b) 如果一个接受者收到编号为 n 的接受请求，它会接受这个请求，除非它已经响应过编号大于 n 的准备请求。

提议者可以发出多个提议，前提是每个都满足上面的描述。它可以在任何时候抛弃一个提议。(正确性是得到保证的，即便针对一个提议的请求和/或响应可能在提议被抛弃之后很久才收到。) 当一个提议者开始发布更高编号的提议时，抛弃一个提议可能是正确的做法。因此，如果一个接受者由于自身已经收到过编号更高的准备请求而无视一个准备或接受请求，那么它最好告知提议者，而这个提议者应该抛弃当前的提议。这只是一个性能优化，不影响正确性。

2.3 知晓一个选中的数值

为了知晓一个数值已被选中，学习者必须知晓一个提议已被多数接受者接受。明显的算法是，让每个接受者在接受提议的时候，向所有学习者发送提议的内容。这让学习者尽早地知道了选中的数值，但需要每个接受者响应每个学习者 —— 响应的个数等于接受者的个数乘以学习者的个数。

关于非拜占庭故障的假定让一个学习者能够容易地从另一个学习者那里知道一个数值已经被选中了。我们可以让各接受者向一个特别的学习者告知自己接受提议的信息，而当一个数值被选中时，这个特别的学习者再把这个消息告诉别的学习者。这个方法需要额外的工作来让所有学习者发现选中的数值，并且不够可靠，因为那个特别的学习者可能挂掉。但这个方法要求的响应数量仅仅等于接受者和学习者数量之和。

更一般地，接受者可以把它们的接受事件告知一个学习者集合，当一个数值被选中后，这个集合中的每个再告知所有学习者。较大的特别学习者集合会可靠些，只是通讯复杂度也高些。

由于消息会丢失，选中的数值可能没有学习者知道。学习者可以询问接受者接受过什么提议，但接受者故障可能会让知道是否某个提议被多数派接受成为不可能。在那种情况下，仅当新提议被选中的时候学习者会知道选中的数值是什么。如果一个学习者想要知道是否某个数值已被选中，它可以让一个提议者发出一个提议，使用上面描述的算法。

2.4 保证进展

容易构造一个场景，其中两个提议者不断发布一系列编号不断增长的提议，而没有一个被选中。提议者 p 完成编号 n1 的提议的第一阶段，然后另一个提议者 q 完成编号为 n2 > n1 的提议的第一阶段。提议者 p 的第二阶段的编号为 n1 的接受请求都被无视了，因为所有接受者都承诺不再接受编号小于 n2 的提议。于是，提议者 p 开始并且完成编号为 n3 > n2 的提议的第一阶段，导致 q 的第二阶段的接受请求被无视。如此进行下去。

为了保证进展，必须选出一个特别的提议者，仅仅它可以发布提议。如果这个特别提议者能与多数接受者成功通讯，并且它采用的提议的编号大于所有已经使用过的编号，那么它将会成功发布一个被接受的提议。如果它知道存在编号更大的请求，则它可以抛弃一个提议然后重试，这样它最终能找出足够大的编号值。

如果这个系统 (提议者、接受者、通讯网络) 工作正常，则可以通过选出一个特别的提议者来达成共识。Fischer, Lynch, 以及 Patterson 等人的著名结果表明，选择提议者的可靠算法必须要么使用随机性，要么使用实时性 —— 比如，使用超时机制。但是，不管提议者的选择是否成功，安全性都是得到保证的。

2.5 实现

Paxos 算法假定了一个进程网络。在其共识算法中，每个进程执行了提议者、接受者、学习者的角色。算法选出一个领导者，执行特别提议者和特别学习者的角色。Paxos 共识算法就是上面描述的那样，其中请求和响应都是作为普通消息发送的，响应消息带有提议号以避免混淆。接受者必须记忆的信息保存在稳定存储设备里，接受者在发出响应之前保存这些内容。

唯一剩下的是保证没有两个提议有相同编号的机制。不同的提议者从不相交的集合选取编号，所以不同的提议者永远不会发出相同的编号。每个提议者在稳定存储里记忆其试图发布过的编号最大的提议，然后在第一阶段使用比其曾用过的编号都大的数作为编号。

3. 实现一个状态机

实现分布式系统的一个简单方法是把系统作为一个客户端集合，它们往中心服务器发命令。服务器可被描述为决定性状态机，按某种顺序执行客户端命令。状态机有一个当前状态，每一步它以一个命令作为输入，生成输出和新的状态。比如，分布式银行系统的客户端可能是柜员，而状态机的状态可能是所有用户的账户余额。取款通过减小账户余额实现 (当且仅当余额不小于取款金额)，输出是旧的和新的余额。

使用单个中心服务器的实现会在这个服务器挂掉时跟着挂掉。于是可以使用一个服务器集合，每个独立实现了状态机。由于状态机是决定性的，所有服务器在执行相同的指令序列后会生成相同的状态和输出序列。发布命令的客户端然后就可以使用任何服务器产生的输出。

为了保证所有服务器执行相同的状态机命令序列，我们来实现一个由 Paxos 共识算法的独立实例组成的序列，其中，第 i 个实例选中的数值是序列中的第 i 个状态机命令。每个服务器执行每个算法实例的所有角色 (提议者、接受者、学习者)。当前，假定服务器集合是固定的，也就是所有共识算法实例使用相同的代理人集合。

在正常操作中，单个服务器被选为领导，在所有共识算法实例中作为特别的提议者 (即唯一能发布提议的)。客户端向领导发送指令，领导决定每个命令应该处于命令序列的什么位置。如果领导认为某个客户端命令应该排在第 135 位，它会让那个命令作为共识算法的第 135 个实例的数值。通常会成功。故障会导致失败，或者另外的服务器认为它自己是领导并且对第 135 个命令应该是什么有不同意见也会导致失败。共识算法保证至多一个命令被选中作为第 135 个命令。

这个办法的效率之关键在于，在 Paxos 共识算法中，提议的数值在第二阶段之前是未定的。回忆起，在提议者的第一阶段完成后，提议的数值要么已经决定，要么提议者可以自由提议任何数值。

下面先描述 Paxos 的状态机实现在正常运行中如何工作，然后描述会有什么样的故障。我们会考虑之前的领导出故障而新领导被选出后会发生什么。(系统启动是特殊情况，此时还没有命令被提议。)

新的领导，作为共识算法所有实例中的学习者，需要知道已被选中的命令的多数。假设它知道命令 1-134, 138, 139 —— 也就是，共识算法在实例 1-134, 138, 139 中选中的数值。(我们将会知道命令序列中间隙如何出现。) 然后它执行实例 135-137 的第一阶段以及所有编号大于 139 的实例的第一阶段。假设这些执行的后果决定了实例 135 和 140 所要提议的数值，但不影响其它实例的数值。领导者然后执行实例 135 和 140 的第二阶段，由此选中了编号为 135 和 140 的命令。

领导者和其它知道领导者知道的所有命令的服务器现在可以执行命令 1-135 了。然而，它不能执行命令 138-140 (虽然它也知道这些命令)，因为命令 136-137 还没被选中。领导者可以把客户端请求的接下来两个命令作为命令 136 和 137。但我们不这么做，我们让它立即以一个特殊的无操作命令来填充这两个空位。(通过执行实例 136 和 137 的第二阶段实现。) 当这些无操作命令被选中后，命令 138-140 就可被执行了。

命令 1-140 现在已被选中。领导者也完成了编号大于 140 的所有实例的第一阶段，并且对这些实例的第二阶段它可以提议任何数值。它为客户端请求的下一个命令赋予编号 141，提议以这个命令作为实例 141 的第二阶段的数值。然后提议下一个客户端命令为 142 号命令，如此进行下去。

领导者可以在知道其提议的 141 号命令被选中之前提议命令 142。有可能它在提议命令 141 时发出的所有消息都丢失了，也有可能其它服务器在知道命令 141 的内容之前命令 142 已经被选中。当领导者未能收到其期待的对实例 141 第二阶段的响应，它会重新发布这些消息。如果一切正常，它提议的命令会被选中。但它可能出故障，导致选中的命令序列里出现间隙。一般，假设领导者可以提前提议 \(\alpha\) 个命令 —— 也就是说，它可以在命令 1 到 \(i\) 被选中后提议命令 \(i+1\) 到 \(i+\alpha\)，那么宽度大到 \(\alpha-1\) 的缺口就有可能出现。

新选出的领导者可以为无限多个实例执行第一阶段 —— 在上面的场景中，为实例 135-137 以及所有大于 139 的实例执行第一阶段。它可以通过发送足够短的消息给别的服务器并且对所有实例采用相同的编号来实现。在第一阶段，除非一个接受者已经收到某个提议者的第二阶段消息，否则它只会回应一个 OK。(在上面的场景，这只适用于实例 135 和 140。) 于是，作为接受者的服务器可以以足够短的消息响应所有实例。为无限多个实例执行第一阶段因此不造成问题。

由于领导者故障以及重新选领导应该是稀有事件，状态机命令的实际执行成本 —— 也就是达成关于命令/数值的共识的成本 —— 是执行共识算法的第二阶段的成本。在可能有故障的情况下，可以证明，Paxos 共识算法是的第二阶段是任何能达成共识的算法里成本最小的。因此，Paxos 算法实质上是最优的。

上面关于正常运作的讨论假定了单个领导者的存在 (除了领导者故障以及重新选领导的短暂期间)。在反常情景，领导者选举可能失败。如果没有领导者，就没有新命令被提出。如果多个服务器认为自己是领导者，则它们都会在同一个共识算法实例中提议数值，这可能导致没有数值被选中。但是，安全性仍然是得到保证的 —— 两个不同的服务器永远不会在第 i 个状态机命令是什么这件事情上持不同意见。选举单个领导者只是为了保证进展。

如果服务器集合会变化，那么必须要有方法来知道哪些服务器实现了共识算法的哪些实例。做这件事的最简单方法是使用状态机自身。当前的服务器集合可以作为状态的一部分，并且可以通过通常的状态机命令改变。我们可以允许领导者提前 \(\alpha\) 个命令，也就是说，在第 \(i\) 个状态机命令执行后，执行共识算法的第 \(i+\alpha\) 个实例的服务器集合被确定。这就给出了一个任意复杂的重配置算法的简单实现。