1. 简介

用于实现高容错性分布式系统的 Paxos 算法，一直以来总是被认为是难以理解的，或许是因为对很多人来说，初始版本就像是”希腊语 ” 一样（最初的论文是以希腊故事展开的形式）[5]。实际上，它也算是最浅显易见的分布式算法之一了。它的核心就是一个一致性算法——论文 [5] 中的“synod”算法。在下一个章节可以看到，它基本上是根据一个一致性算法所必需满足的条件自然而然地推断出来的。最后一个章节，我们通过将 Paxos 算法作为构建一个实现了状态机的分布式系统的一致性实现，来完整地描述它。这种使用状态机方法的论文 [4] 应该早已广为人知，因为它可能已经是分布式系统理论研究领域被引用最广泛的了。

2. 一致性算法

2.1 问题描述

假设有一组可以提出提案的进程集合。一个一致性算法需要保证：
在这些被提出的提案中，只有一个会被选定。
如果没有提案被提出，则不会有被选定的提案。
当一个提案被选定后，进程应该能获取被选定提案的信息。

对于一致来说，安全性（Safety）需求是这样的：
只有被提出的提案才能被选定。
只能有一个值被选中（chosen），同时
进程不能认为某个提案被选定，除非它真的是被选定的那个。

我们不会尝试去精确地描述活性（Liveness）需求。但是从总体上看，最终的目标是保证有一个提案被选定，并且当提案被选定后，进程最终也能获取到被选定提案的信息。
一个分布式算法，有两个重要的属性：Safety 和 Liveness，简单来说：
Safety 是指那些需要保证永远都不会发生的事情
Liveness 是指那些最终一定会发生的事情

在这个一致性算法中，有三个参与角色，我们分别用 Proposer，Acceptor 和 Learner 来表示。在具体实现中，一个进程可能充当不止一种角色，但是在这里我们并不关心它们之间的映射关系。

假设不同的参与者之间可以通过发消息来进行通信，我们使用普通的非拜占庭模式的异步模型：
每个参与者以任意的速度运行，可能会因停止而执行失败，也可能会重启。当一个提案被选定后，所有的参与者都有可能失败然后重启，除非这些参与者可以记录某些信息，否则是不可能存在一个解法的。
消息在传输中可能花费任意时间，可能会重复，也可能丢失，但不会被损坏（不会被篡改，即不会发生拜占庭问题）。

2.2 提案的选定

选定提案最简单的方式就是只有一个 Acceptor 存在。Proposer 发送提案给 Acceptor，Acceptor 会选择它接收到的第一个提案作为被选提案。虽然简单，这个解决方案却很难让人满意，因为当 Acceptor 出错时，整个系统就无法工作了。

因此，我们应该选择其他方式来选定提案，比如可以用多个 Acceptor 来避免一个 Acceptor 的单点问题。这样的话，Proposer 向一个 Acceptor 集合发送提案，某个 Acceptor 可能会通过（accept）这个提案。当有足够多的 Acceptor 通过它时，我们就认为这个提案被选定了。那么怎样才算是足够多呢？为了确保只一个提案被选定，我们可以让这个集合大到包含了 Acceptor 集合中的多数成员。因为任意两个多数集（majority）至少包含一个公共成员，如果我们再规定一个 Acceptor 只能通过一个提案，那么就能保证只有一个提案被选定（这是很多论文都研究过的多数集的一个普通应用[3]）。

假设没有失败和消息丢失的情况，如果我们希望在每个 Proposer 只能提出一个提案的前提下仍然可以选出一个提案来，这就意味着如下需求：

P1. 一个 Acceptor 必须通过它收到的第一个提案。

但是这个需求会引发另外的问题。如果有多个提案被不同的 Proposer 同时提出，这会导致虽然每个 Acceptor 都通过了一个提案，但是没有一个提案是由多数人通过的。甚至即使只有两个提案被提出，如果每个都被差不多一半的 Acceptor 通过了，哪怕只有一个 Acceptor 出错都可能导致无法确定该选定哪个提案。
比如有 5 个 Acceptor，其中 2 个通过了提案 a，另外 3 个通过了提案 b，此时如果通过提案 b 的 3 个当中有一个出错了，那么 a 和 b 的通过数都为 2, 这样就无法确定了。

P1 再加一个提案被选定需要由半数以上 Acceptor 通过的这个需求，暗示着一个 Acceptor 必须要能通过不止一个提案。我们为每个提案分配一个编号来记录一个 Acceptor 通过的那些提案，于是一个提案就包含一个提案编号以及它的 value 值。为了避免造成混淆，需要保证不同的提案具有不同编号。如何实现这个功能依赖于具体的实现细节，在这里我们假设已经实现了这种保证。当一个具有 value 值的提案被多数 Acceptor 通过后，我们就认为该 value 被选定了。同时我们也认为该提案被选定了。

我们允许多个提案被选定，但是我们必须保证所有被选定的提案具有相同的值 value。通过对提案编号的约定，它需要满足以下保证：
P2. 如果具有 value 值 v 的提案被选定了，那么所有比它编号高的提案的 value 值也必须是 v。

因为编号是完全有序的，所以条件 P2 就保证了只有一个 value 值被选定这一关键安全性属性。

一个提案能被选定，必须要被至少一个 Acceptor 通过，所以我们可以通过满足如下条件来满足 P2:

P2a. 如果一个具有 value 值 v 的提案被选定了，那么被 Acceptor 通过的所有编号比它高的提案的 value 值也必须是 v。

我们仍然需要 P1 来保证有提案会被选定。因为通信是异步的，一个提案可能会在某个 Acceptor c 还没收到任何提案时就被选定了。假设有个新的 Proposer 苏醒了，然后提出了一个具有不同 value 值的更高编号的提案，根据 P1, 需要 c 通过这个提案，但这是与 P2a 相矛盾的。因此为了同时满足 P1 和 P2a，需要对 P2a 进行强化：

P2b. 如果具有 value 值 v 的提案被选定了，那么所有比它编号更高的被 Proposer 提出的提案的 value 值也必须是 v。

一个提案被 Acceptor 通过之前肯定是由某个 Proposer 提出，因此 P2b 就隐含 P2a，进而隐含了 P2.

为了发现如何保证 P2b，我们来看看如何证明它成立。我们假设某个具有编号 m 和 value 值 v 的提案被选定了，需要证明任意具有编号 n（n > m）的提案都具有 value 值 v。我们可以通过对 n 使用数学归纳法来简化证明，这样我们可以在额外的假设下——即编号在 m..(n-1)之间的提案具有 value 值 v，来证明编号为 n 的提案具有 value 值 v，其中 i..j 表示从 i 到 j 的集合。因为编号为 m 的提案已经被选定了，这就意味着存在一个多数 Acceptor 组成的集合 C，C 中的每个成员都通过了这个提案。结合归纳的假设，m 被选定意味着：

 C 中的每一个 Acceptor 都通过了一个编号在 m..(n-1)之间的提案，并且每个编号在 m..(n-1)之间的被 Acceptor 通过的提案都具有 value 值 v。

由于任何包含多数 Acceptor 的集合 S 都至少包含一个 C 中的成员，我们可以通过保持如下不变性来确保编号为 n 的提案具有 value 值 v：

P2c. 对于任意 v 和 n，如果一个编号为 n，value 值为 v 的提案被提出，那么肯定存在一个由多数 Acceptor 组成的集合 S 满足以下条件中的一个：a. S 中不存在任何 Acceptor 通过了编号小于 n 的提案
    b. v 是 S 中所有 Acceptor 已经通过的编号小于 n 的具有最大编号的提案的 value 值。

通过维护 P2c 的不变性我们就可以满足 P2b 的条件了。

为了维护 P2c 的不变性，一个 Proposer 在提出编号为 n 的提案时，如果存在一个将要或者已经被多数 Acceptor 通过的编号小于 n 的最大编号提案，Proposer 需要知道它的信息。获取那些已经被通过的提案很简单，但是预测未来会被通过的却很困难。为了避免去预测未来，Proposer 通过提出承诺不会有那样的通过情况来控制它。换句话说，Proposer 会请求那些 Acceptor 不要再通过任何编号小于 n 的提案了。这就导致了如下的提案生成算法：
Proposer 选择一个新的提案编号 n，然后向某个 Acceptor 集合中的成员发送请示，要求它作出如下回应：

（a）保证不再通过任何编号小于 n 的提案。（b）当前它已经通过的编号小于 n 的最大编号提案，如何存在的话。我们把这样的请求称为编号为 n 的 prepare 请求。

如果 Proposer 收到来自集合中多数成员的响应结果，那么它可以提出编号为 n，value 值为 v 的提案，这里 v 是所有响应中最大编号提案的 value 值，如果响应中不包含任何提案，那么这个值就由 Proposer 自由决定。

Proposer 通过向某个 Acceptor 集合发送需要被通过的提案请求来产生一个提案（这里的 Acceptor 集合不一定是响应前一个请求的集合）。这们把这个叫做 accept 请求。

目前我们描述了 Proposer 端的算法。那么 Acceptor 端是怎样的呢？它可能会收到来自 Proposer 端的两种请求：prepare 请求和 accept 请求。Acceptor 可以忽略任意请求而不用担心破坏算法的安全性。因此我们只需要说明它在什么情况下可以对一个请求作出响应。它可以在任何时候响应 prepare 请求也可以在不违反现有承诺的情况下响应 accept 请求。换句话说：

P1a. 一个 Acceptor 可以通过一个编号为 n 的提案，只要它还未响应任何编号大于 n 的 prepare 请求。

可以看出 P1a 包含了 P1。

现在我们就获得了一个满足安全性需求的提案选定算法——假设在提案编号唯一的前提下。只要再做点小优化，就能得到最终的算法了。
假设一个 Acceptor 收到了一个编号为 n 的 prepare 请求，但是它已经对编号大于 n 的 prepare 请求作出了响应，因此它肯定不会再通过任何新的编号为 n 的提案。那么它就没有必要对这个请求作出响应，因为它肯定不会通过编号为 n 的提案，于是我们会让 Acceptor 忽略这样的 prepare 请求，我们也会让它忽略那些它已经通过的提案的 prepare 请求。
通过这个优化，Acceptor 只需要记住它已经通过的提案的最大编号以及它已经响应过 prepare 请求的提案的最大编号。因为必须要在出错的情况下也保证 P2c 的不变性，所以 Acceptor 要在故障和重启的情况下也能记住这些信息。Proposer 可以随时丢弃提案以及它的所有信息——只要它可以保证不会提出具有相同编号的提案即可。

把 Proposer 和 Acceptor 的行为结合起来，我们就能得到算法的如下两阶段执行过程：
Phase 1:
Proposer 选择一个提案编号 n，然后向 Acceptor 的多数集发送编号为 n 的 prepare 请求。
如果一个 Acceptor 收到一个编号为 n 的 prepare 请示，且 n 大于它所有已响应请求的编号，那么它就会保证不会再通过任意编号小于 n 的提案，同时将它已经通过的最大编号提案（如果存在的话）一并作为响应。
Phase 2:
如果 Proposer 收到多数 Acceptor 对它 prepare 请求（编号为 n）的响应，那么它就会发送一个编号为 n，value 值为 v 的提案的 accept 请求给每个 Acceptor，这里 v 是收到的响应中最大编号提案的值，如果响应中不包含任何提案，那么它就可以是任意值。
如果 Acceptor 收到一个编号为 n 的提案的 accept 请求，只要它还未对编号大于 n 的 prepare 作出响应，它就可以通过这个提案。

一个 Proposer 可以提出多个提案，只要它能遵循以上算法约定。它可以在任意时刻丢弃某个提案（即使针对该提案的请求或响应在提案丢弃后很久才到达，正确性依然可以保证）。如果 Proposer 已经在尝试提交更大编号的提案，那么丢弃也未尝不是一件好事。因此，如果一个 Acceptor 因为已经收到更高编号的 prepare 请求而忽略某个 prepare 或者 accept 请求，它应该通知对应的 Proposer，然后该 Proposer 可以丢弃这个提案。这是一个不影响正确性的性能优化。

2.3 获取被选定的提案值

为了获取被选定的值，一个 Learner 必须要能知道一个提案已经被多数 Acceptor 通过了。最直观的算法是，让每个 Acceptor 在通过一个提案时就通知所有 Learner，把通过的提案告知它们。这可以让 Learner 尽快找到被选定的值，但这需要每个 Acceptor 和 Learner 之间互相通信——通信次数等于二者数量的乘积。

在假设非拜占庭错误的前提下，一个 Learner 可以很容易地通过另一个 Learner 了解一个值已经被选定了。我们可以让所有 Acceptor 将它们的通过信息发送给一个特定的 Learner，当一个 value 被选定时，由它来通知其他 Learner。这种方法需要额外一个步骤才能通知到所有 Learner，而且它也不是可靠的，因为那个特定的 Learner 可能会发生一些故障。但是这种情况下的通信次数，只需要二者数量之和。

更一般地，Acceptor 可以将它们的通过信息发送给一个特写的 Learner 集合，它们中的任何一个都可以在某个 value 被选定后通知所有 Learner。这个集合中的 Learner 越多，可靠性就越好，通信复杂度也相应更高。

因为消息可能会丢失，一个 value 被选定后，可能没有 Learner 会发现。Learner 可以向 Acceptor 询问它们通过了哪些提案，但是任一 Acceptor 出错，都有可能导致无法分辨是否有多数 Acceptor 通过了某个提案。在这种情况下，只有当一个新的提案被选定时，Learner 才能发现被选定的 value。如果一个 Learner 想知道是否已经选定一个 value，它可以让 Proposer 利用上面的算法提出一个提案。

2.4 进展性

很容易可以构造出这样一种情况，两个 Proposer 持续地提出序号递增的提案，但是没有提案会被选定。Proposer p 为编号为 n1 的提案完成 Phase 1, 然后另一个 Proposer q 为编号为 n2(n2>n1)的提案完成 Phase 1。Proposer p 对于编号 n1 的 Phase 2 的 accept 请求会被忽略，因为 Acceptor 承诺不再通过任何编号小于 n2 的提案。这样 Proposer p 就会用一个新的编号 n3(n3>n2)重新开始并完成 Phase 1，这又导致了 Proposer q 对于 Phase 2 的 accept 请求被忽略，如此往复。

为了保证进度，必须选择一个特定的 Proposer 作为唯一的提案提出者。如果这个 Proposer 可以和多数 Acceptor 进行通信，并且可以使用比已用编号更大的编号来进行提案的话，那么它提出的提案就可以成功被通过。如果知道有某些编号更高的请求，它可以通过舍弃当前的提案并重新开始，这个 Proposer 最终一定会选到一个足够大的提案编号。

如果系统中有足够的组件（Proposer, Acceptor 以及网络通信）工作良好，通过选举一个特定的 Proposer，活性就能够达到。著名的 FLP 理论 [1] 指出，一个可靠的 Proposer 选举算法要么利用随时性要么利用实时性来实现——比如使用超时机制。然而无论选举是否成功，安全性都可以保证。

2.5 实现

Paxos 算法 [5] 假设了一组进程网络。在它的一致性算法中，每个进程都扮演着 Proposer, Acceptor 以及 Learner 的角色。该算法选择了一个 Leader 来扮演那个特定的 Proposer 和 Learner。Paxos 一致性算法就是上面描述的那个，请求和响应都以普通消息的方式发送（响应消息通过对应的提案编号来标识以避免混淆）。使用可靠的存储设备存储 Acceptor 需要记住的信息来防止出错。Acceptor 在真正发送响应之前，会将它记录到可靠的存储设备中。

剩下的就是描述如果保证不会用到重复编号的机制了。不同的 Proposer 从不相交的编号集合中选择自己的编号，这样任何两个 Proposer 就不会用到相同的编号了。每个 Proposer 都记录（在可靠存储设备中）它使用过的最大编号，然后用比这更大编号的提案开始 Phase 1。

3. 状态机实现

有一种实现分布式系统的简单方式，就是使用一组客户端集合向中央服务器发送命令。服务器可以看成一个以某种顺序执行客户端命令的确定性状态机。这个状态机有个当前状态，通过接收一个命令当作输入来产生一个输出和新状态。比如，分布式银行系统的客户端可能是一些出纳员，状态机的状态则由所有用户的账户余额组成。一个取款操作，通过执行一个减少账户余额的状态机命令（当且仅当余额大于取款数目时）实现，然后将新旧余额作为输出。

使用单点中央服务器的系统在该服务器故障的情况下，整个系统都将运行失败。因此我们用一组服务器来代替它，每个服务器都独立实现了该状态机。因为这个状态机是确定性的，如果所有服务器都以同样的顺序执行命令，那么它们将产生相同的状态机状态和输出。一个提出命令的客户端，可以使用任意服务器为它产生的输出。

为了保证所有服务器都能执行相同的状态机命令序列，我们需要实现一系列独立的 Paxos 一致性算法实例，第 i 个实例选定的值作为序列中的第 i 个状态机命令。在算法的每个实例中，每个服务器担任所有角色（Proposer，Acceptor 和 Learner）。现在，我们假设服务器的集合是固定的，这样所有的一致性算法实例都具有相同的参与者集合。

在正常执行中，一个服务器被选举成为 Leader，它会在所有一致性算法实例当中扮演特定的 Proposer（唯一的提案提出者）。客户端给 Leader 发送命令，它来决定每条命令出现在序列当中的位置。如果 Leader 决定某个客户端命令应该是第 135 个，它会尝试让该命令成为第 135 个一致性算法实例选定的 value 值。这通常都会成功，但是在一些故障或者有另外的服务器也认为自己是 Leader 并且对第 135 个命令持有异议时，它可能会失败。但是一致性算法可以保证，最多只有一条命令会被选定为第 135 条。

这个方法的关键在于，在 Paxos 一致性算法中，被提出的 value 值只在 Phase 2 才会被选定。回忆一下，在 Proposer 完成 Phase 1 时，要么提案的 value 值被确定了，要么 Proposer 可以自由提出任意值。

我们现在描述了 Paxos 状态机实现是怎样在正常情况下运行的，接下来我们看看会有哪些出错的情况，看下之前的 Leader 故障以及新的 Leader 被选举出来后会发生什么（系统启动是一种特殊情况，此时还没有命令被提出）。

新的 Leader 被选举出来后，首先要成为所有一致性算法实例的 Learner，需要知道目前已经选定的大部分命令。假设它知道命令 1 -134，138 以及 139——也就是一致性算法实例 1 -134，138 以及 139 选定的值（后面我们会看到这样的命令缺口是如何产生的）。接下来它会执行 135-137 以及 139 以后的算法实例的 Phase 1（下面会描述如何来做）。假设执行结果表明，实例 135 和 140 的提案值已被确定，但是其他执行实例的提案值是没有限制的。那么 Leader 可以执行实例 135 和 140 的 Phase 2，进而选定第 135 和 140 条命令。

Leader 以及其他已经获取 Leader 所有已知命令的服务器，现在可以执行命令 1 -135。然而它还不能执行命令 138-140，因为命令 136 和 137 还未被选定。Leader 可以将接下来两条客户端请求的命令当作命令 136 和 137。同时我们也可以提出一个特殊的“noop”指令来立即填补这个空缺但保持状态不变（通过执行一致性算法实例 136 和 137 的 Phase 2 来完成）。一旦该 no-op 指令被选定，命令 138-140 就可以被执行了。

命令 1 -140 目前已经被选定了。Leader 也已经完成了所有大于 140 的一致性算法实例的 Phase 1，而且它可以在 Phase 2 中自由地为这些实例指定任意值。它为下一个从客户端接收的命令分配序号 141，并在 Phase 2 中将它作为第 141 个一致性算法实例的 value 值。它将接收到的下一个客户端命令作为命令 142, 并以此类推。

Leader 可以在它提出的命令 141 被选定前提出命令 142。它发送的关于命令 141 的提案信息可能全部丢失，因此在所有其他服务器获知 Leader 选定的命令 141 之前，命令 142 就可能已被选定。当 Leader 无法收到实例 141 的 Phase 2 的期望回应时，它会重传这些信息。如果一切顺利的话，它的提案命令将被选定。但是仍然可能会失败，造成在选定的命令序列中出现缺口。一般来说，假设 Leader 可以提前确定 a 个命令，这意味着命令 i 被选定之后，它就可以提出 i + 1 到 i + a 的命令了。这样就可能形成长达 a - 1 的命令缺口。

一个新选定的 Leader 需要为无数个一致性算法实例执行 Phase 1——在上面的场景中，就是 135-137 以及所有大于 139 的执行实例。通过向其他服务器发送一条合适的消息，就可以让所有执行实例使用同一个提案编号（计数器）。在 Phase 1 中，只要一个 Acceptor 已经收到来自某 Proposer 的 Phase 2 消息，那么它就可以为不止一个实例作出通过回应（在上面的场景中，就是针对 135 和 140 的情况）。因此一个服务器（作为 Acceptor 时）可以用一条适当的短消息对所有实例作出回应。执行这样无限多的实例的 Phase 1 也不会有问题。
这里应该是指稳定的 Paxos 模型，Phase 1 可以被省略，只要编号计数器是唯一的。

由于 Leader 的故障和新 Leader 的选举是很少见的情况，那么执行一条状态机命令的主要开销，即在命令值上达成一致性的开销，就是执行一致性算法中 Phase 2 的开销。可以证明，在允许失效的情况下，Paxos 一致性算法的 Phase 2 在所有一致性算法中具有最小可能的时间复杂度[2]。因此 Paxos 算法基本上是最优的。

在系统正常运行的情况下，我们假设总是只有一个 Leader，只有在当前 Leader 故障及选举出新 Leader 之间的短时间内才会违背这个假设。在特殊情况下，Leader 选举可能失败。如果没有服务器扮演 Leader，那么就没有新命令被提出。如果同时有多个服务器认为自己是 Leader，它们在一个一致性算法执行实例中可能提出不同 value 值，这可能导致没有任何值能被选定。但是安全性是可以保证的——不可能有两个不同的值被选定为第 i 条状态机命令。单个 Leader 的选举只是为了保证流程能往下进行。

如果服务器的集合是变化的，那么必须有某种方法可以决定哪些服务器来实现哪一些一致性算法实例。最简单的方式就是通过状态机本身来完成。当前的服务器集合可以是状态的一部分，同时也可以通过状态机命令来改变。通过用执行完第 i 条状态机命令后的状态来描述执行一致性算法 i + a 的服务器集合，我们就能让 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] (1,
2, 3, 4) Leslie Lamport. The part-time parliament. ACM Transactions on
Computer Systems, 16(2):133–169, May 1998.