引言
用于实现容错分布式系统的 Paxos 算法一直被认为难以理解，这可能是因为对许多读者来说最初的介绍是希腊语。事实上，它是最简单、最明显的分布式算法之一。 它的核心是一种共识算法—— The part-time parliament 中的“synod”算法。下一节表明，这种共识算法几乎不可避免地遵循我们希望它满足的属性。最后一部分解释了完整的 Paxos 算法，该算法是通过将共识直接应用于构建分布式系统的状态机方法而获得的——这种方法应该是众所周知的，因为它可能是最常见的主题 - 引用的关于分布式系统理论的文章 Time, clocks, and the ordering of events in a distributed system。
共识算法
问题
假设一组可以提出值的进程。共识算法可确保选择提议（purposed）值中的一个值。如果没有提议值，则不应选择任何值。如果选择了一个值，那么进程应该能够学习选择的值。共识的安全要求是：
- 只能选择一个已提议的值
- 只能选择一个值
- 除非实际上已经选择了一个值，否则一个进程永远不会学习到已经选择了一个值。
我们不会尝试指定精确的活性要求。然而，目标是确保最终选择一些提议的值，如果选择了一个值，那么过程最终可以学习该值。
我们让共识算法中的三个角色由三类代理执行：提议者、接受者和学习者。在一个实现中，单个进程可以充当多个代理，但是在这里我们并不关心从代理到进程的映射。
假设代理可以通过发送消息相互通信。我们使用惯用的异步非拜占庭模型，其中：
- 代理以任意速度运行，可能因停止而宕机，也可能重新启动。由于在选择一个值然后重新启动后所有代理都可能宕机，因此除非某些信息可以被宕机并重新启动的代理记住，否则不可能存在解决方案。
- 消息可能需要任意长的时间才能被传递，可以被复制，也可以丢失，但它们不会被破坏。
选择一个值
选择值的最简单方法是使用单个接受器代理。提议者向接受者发送提议，接受者选择它收到的第一个提议值。虽然简单，但这种解决方案并不令人满意，因为接受者的宕机使任何进一步的进展都变得不可能。
所以，让我们尝试另一种选择值的方法。让我们使用多个接受器代理，而不是单个接受器。提议者将提议的值发送给一组接受者。接受者可以接受提议的值。当有足够多的接受者接受它时，选择该值。多大才足够大？为了确保只选择一个值，我们可以让一个足够大的集合由任何大多数代理组成。因为任何两个多数都至少有一个共同的接受者，所以如果一个接受者最多可以接受一个值，这将起作用。（在许多论文中已经观察到对多数的明显概括，显然是从 The implementation of reliable distributed multiprocess systems 开始的）
在没有宕机或消息丢失的情况下，我们希望选择一个值，即使只有一个值是由单一的提议者提议的。这表明了要求：
\(P1\). 接受者必须接受它收到的第一个提议。
但是这个要求带来了一个问题。不同的提议者几乎可以同时提议多个值，从而导致每个接受者都接受了一个值，但没有一个值被大多数接受者接受的情况。即使只有两个提议的值，如果每个都被大约一半的接受者接受，单个接受者的宕机可能会导致无法了解选择了哪个值。
\(P1\) 和仅当一个值被大多数接受者接受时才被选择的要求意味着必须允许接受者接受多个提议。我们通过为每个提议分配一个编号（自然数）来跟踪接受者可能接受的不同提议，因此提议由一个提议编号和一个值组成。为了防止混淆，我们要求不同的提议有不同的编号。这是如何实现的取决于实现，所以现在我们只是假设它。当具有该值的单个提议已被大多数接受者接受时，将选择一个值。在这种情况下，我们说提议（以及它的价值）已被选中。
我们可以允许选择多个提议，但我们必须保证所有选择的提议具有相同的值。通过对提议编号的归纳，足以保证：
\(P2\). 如果一个值为 \(v\) 的提案被选中，那么每个被选中的编号更大的提案的值为 \(v\)。
由于数字是完全有序的，因此条件 \(P2\) 保证了仅选择单个值的关键安全属性。 要被选中，提案必须被至少一个接受者接受。 所以，我们可以通过满足 \(P2^a\) 来满足：
\(P2^a\). 如果选择了值为 \(v\) 的提案，则任何接受者接受的每个编号较高的提案都具有值 \(v\)。
我们仍然保持 \(P1\) 以确保选择某些提案。 因为通信是异步的，所以可以选择一个提案，而某个特定的接受者 \(c\) 从未收到任何提案。假设一个新的提议者“醒来”并发出一个具有不同值的更高编号的提议。 \(P1\) 要求 \(c\) 接受这个提议，违反了\(P2^a\)。维持 \(P1\) 和 \(P2^a\) 需要加强 \(P2^a\) 以：
\(P2^b\). 如果选择值为 \(v\) 的提案，则任何提案者发布的每个编号较高的提案都具有值 \(v\)。
由于提案必须由提议者发出才能被接受者接受，因此 \(P2^b\) 可推出 \(P2^a\)，而这又可推出 \(P2\)。为了发现如何满足 \(P2^b\)，让我们考虑如何证明它成立。我们假设某个编号为 \(m\) 且值为 \(v\) 的提案被选中，并表明任何编号为 \(n > m\) 的提案也具有值 \(v\)。我们将通过对 \(n\) 使用归纳来简化证明，因此我们可以证明编号为 \(n\) 的提案在附加假设下具有值 \(v\) ，即每个以 \(m..(n-1)\) 中的数字发布的提案值为 \(v\)。要选择编号为 \(m\) 的提案，必须有某个由大多数接受者组成的集合 \(C\)，使得 \(C\) 中的每个接受者都接受它。将此与归纳假设相结合，选择 \(m\) 的假设意味着：
\(C\) 中的每个接受者都接受了一个编号为 \(m..(n-1)\) 的提案，以及编号为 \(m..(n-1)\) 的每个被任何接受者接受的提案其值为 \(v\)。
由于任何由大多数接受者组成的集合 \(S\) 都包含 \(C\) 的至少一个成员，因此我们可以通过确保保持以下不变量来得出结论：编号为 \(n\) 的提案具有值 \(v\)：
\(P2^c\). 对于任何 \(v\) 和 \(n\)，如果一个值为 \(v\) 且编号为 \(n\) 的提案被发布，那么存在一个由大多数接受者组成的集合 \(S\)，使得
- \(S\) 中没有接受者接受任何编号小于 \(n\) 的提案，或者
- \(v\) 是 \(S\) 中接受者接受的所有编号小于 \(n\) 的提案中编号最高的提案的值。
因此，我们可以通过保持 \(P2^c\) 的不变性来满足 \(P2^b\)。为了保持 \(P2^c\) 的不变性，想要发布编号为 \(n\) 的提议的提议者必须学习编号小于 \(n\) 的最高编号提议，如果有的话，该提议已经或将被大多数接受者中的每个接受者接受。了解已经接受的提案很容易；但很难预测未来的接受。提议者不是试图预测未来，而是通过提取不会有任何此类接受的承诺来控制它。换句话说，提议者要求接受者不再接受编号小于 \(n\) 的提议。这导致了以下用于发布提案的算法。
- 提议者选择一个新的提议号 \(n\) 并向一组接受者中的每个成员发送请求，要求其响应：
- 承诺不再接受编号小于 \(n\) 的提案，并且
- 其已接受的最大数量小于 \(n\) 的提案（如果有的话） 我将这样的请求称为编号为 \(n\) 的准备请求。
- 如果提议者收到了大多数接受者的请求响应，那么它可以发出编号为 \(n\) 且值为 \(v\) 的提议，其中 \(v\) 是响应中编号最高的提议的值；如果响应者未报告任何提案，则由提案者任意提出一个值。 提议者通过向一组接受者发送提议被接受的请求来发布提议。（这不一定是响应初始请求的同一组接受者）我们称其为接受请求。 这描述了提议者的算法。接受者呢？它可以接收来自提议者的两种请求：准备请求和接受请求。接受者可以忽略任何请求而不会影响安全性。因此，我们只需要说明何时允许响应请求。它总是可以响应准备请求。它可以响应接受请求，接受提案，当且仅当它没有承诺不接受。换句话说：
\(P1^a\). 接受者可以接受编号为 \(n\) 的提案，当且仅当接受者没有响应编号大于 \(n\) 的准备请求。
观察到 \(P1^a\) 包含 \(P1\)。
我们现在有一个完整的算法来选择满足所需安全属性的值——假设唯一的提案编号。最终的算法是通过一个小的优化得到的。
假设一个接受者收到一个编号为 \(n\) 的准备请求，但它已经响应了一个编号大于 \(n\) 的准备请求，因此承诺不接受任何编号为 \(n\) 的新提案。然后接受者没有理由响应新的准备请求，因为它不会接受提议者想要发布的编号为 \(n\) 的提案。所以我们让接受者忽略这样的准备请求。我们也让它忽略它已经接受的提案的准备请求。
通过这种优化，接受者只需要记住它曾经接受过的编号最高的提案以及它已响应的编号最高的准备请求的编号。因为 \(P2^c\) 必须保持不变而不管宕机，接受者必须记住这个信息，即使它宕机然后重新启动。请注意，提议者总是可以放弃一个提议并完全忘记它——只要它永远不会尝试发布另一个具有相同编号的提议。
将提议者和接受者的动作放在一起，我们看到算法按照以下两个阶段运行：
阶段 1
- 提议者选择编号为 \(n\) 的提议并向大多数接受者发送编号为 \(n\) 的准备请求。
- 如果一个接受者收到一个编号 \(n\) 大于它已经响应的任何准备请求的准备请求，则它响应该请求并承诺不再接受任何编号小于 \(n\) 的提议，并返回已接受的编号最高的提案（如果有）。
阶段 2
- 如果提议者从大多数接受者那里收到对其准备请求（编号为 \(n\)）的响应，那么它会向这些接受者中的每一个发送一个接受请求，以获取编号为 \(n\) 且值为 \(v\) 的提议，其中 \(v\) 是所有响应中编号最高的提案的值（如果响应报告没有提案，则 \(v\) 为任何值）。
- 如果一个接受者收到一个编号为 \(n\) 的提议的接受请求，它会接受该提议，除非它已经响应了编号大于 \(n\) 的准备请求。
学习选中的值
要知道一个值已被选择，学习者必须发现一个提案已被大多数接受者接受。显而易见的算法是让每个接受者，只要它接受一个提案，就响应所有学习者，将提案发送给他们。这允许学习者尽快找到选择的值，但它要求每个接受者对每个学习者做出响应——响应的数量等于接受者数量和学习者数量的乘积。
非拜占庭失败的假设使一个学习者很容易从另一个学习者那里发现一个值已被接受。我们可以让接受者用他们的接受来回应一个杰出的学习者，当一个值被选择时，这反过来会通知其他学习者。这种方法需要额外的一轮让所有学习者发现选择的值。它也不太可靠，因为杰出的学习者可能会宕机。但它需要的响应数量仅等于接受者数量和学习者数量之和。
更一般地，接受者可以用他们的接受来回应一些杰出的学习者，然后每个学习者都可以在选择了一个值时通知所有的学习者。使用更大的杰出学习者集以更大的通信复杂性为代价提供更高的可靠性。
由于消息丢失，可以在没有学习者发现的情况下选择一个值。学习者可以询问接受者他们接受了哪些提议，但接受者的宕机可能会导致无法知道大多数人是否接受了特定的提议。在这种情况下，学习者只会在选择新提案时才知道选择了什么值。如果学习者需要知道一个值是否被选择，它可以让提议者使用上述算法发出提议。
过程
很容易构建一个场景，其中两个提议者每个人都不断地发布一系列提案，数量不断增加，但没有一个被选中。提议者 \(p\) 完成提案编号 \(n_1\) 的阶段 1。然后另一个提议者 \(q\) 完成第 1 阶段的提议编号 \(n_2 > n_1\)。提议者 \(p\) 对编号为 \(n_1\) 的提议的第 2 阶段接受请求被忽略，因为所有接受者都承诺不接受任何编号小于 \(n_2\) 的新提议。因此，提议者 \(p\) 然后开始并完成第 1 阶段的新提议编号 \(n_3 > n_2\)，导致第二个阶段 2 接受提议者 \(q\) 的请求被忽略。以此类推。
为了保证进度，必须选择一位杰出的提议者作为唯一尝试发布提议的人。如果杰出的提议者可以与大多数接受者成功通信，并且如果它使用的提议编号大于任何已经使用的提议，那么它将成功发出被接受的提议。通过放弃一个提案并在它获悉某个具有更高提案号的请求时再次尝试，杰出的提案者最终将选择一个足够高的提案号。
如果足够多的系统（提议者、接受者和通信网络）正常工作，则可以通过选举单个杰出的提议者来实现活跃性。 Fischer、Lynch 和 Patterson 的著名结果 Impossibility of distributed consensus with one faulty process 意味着选举提议者的可靠算法必须使用随机性或实时性——例如，通过使用超时。但是，无论选举成功与否，都可以确保安全。
实现状态机
实现分布式系统的一种简单方法是，向中央服务器发出命令的客户端集合。服务器可以被描述为以某种顺序执行客户端命令的确定性状态机。状态机有一个当前状态；它通过将命令作为输入并产生输出和新状态来执行步骤。例如，分布式银行系统的客户可能是出纳员，状态机状态可能包括所有用户的账户余额。提款将通过执行状态机命令来执行，当且仅当余额大于提款金额时，该命令会减少帐户的余额，并生成旧余额和新余额作为输出。
如果该服务器发生故障，则使用单个中央服务器的实现会宕机。因此，我们改为使用一组服务器，每个服务器都独立实现状态机。因为状态机是确定性的，如果所有服务器都执行相同的命令序列，它们将产生相同的状态序列和输出。然后，发出命令的客户端可以使用任何服务器为其生成的输出。
为了保证所有服务器执行相同的状态机命令序列，我们实现了 Paxos 共识算法的一系列独立实例，第 \(i\) 个实例选择的值是序列中的第 \(i\) 个状态机命令。每个服务器在算法的每个实例中扮演所有角色（提议者、接受者和学习者）。现在，我假设服务器集是固定的，因此共识算法的所有实例都使用相同的代理集。
在正常操作中，单个服务器被选为领导者，它在共识算法的所有实例中充当杰出的提议者（唯一尝试发布提议的人）。客户端向领导者发送命令，领导者决定每个命令应该出现在序列中的哪个位置。如果领导者决定某个客户端命令应该是第 135 个命令，它会尝试将该命令选为共识算法的第 135 个实例的值。它通常会成功。它可能因为宕机而失败，或者因为另一个服务器也认为自己是领导者并且对第 135 条命令应该是什么有不同的想法。但是共识算法保证最多可以选择一个命令作为第 135 个命令。
这种方法效率的关键在于，在 Paxos 共识算法中，要到阶段 2 才会选择要提议的值。回想一下，在完成提议者算法的阶段 1 之后，要提议的值要么被确定，要么提议者可以自由提议任何值。
我现在将描述 Paxos 状态机实现在正常操作期间是如何工作的。稍后，我将讨论可能出现的问题。我考虑当前任领导者刚刚宕机并选择了新领导者时会发生什么（系统启动是一种特殊情况，尚未提出任何命令）。
作为共识算法所有实例的学习者，新领导者应该知道大多数已经选择的命令。假设它知道命令 1-134、138 和 139，即在共识算法的实例 1-134、138 和 139 中选择的值（稍后我们将看到命令序列中的这种间隙是如何产生的）。然后它执行实例 135-137 和所有大于 139 的实例的阶段 1（我将在下面描述这是如何完成的）。假设这些执行决定了在实例 135 和 140 中建议的值，但在所有其他实例中使提出的值不受约束。然后领导者为实例 135 和 140 执行阶段 2，从而选择命令 135 和 140。
领导者以及学习了领导者知道的所有命令的任何其他服务器现在可以执行命令 1-135。但是，它不能执行它也知道的命令 138-140，因为尚未选择命令 136 和 137。领导者可以将客户端请求的接下来的两个命令作为命令 136 和 137。另外，我们通过提议特殊“no-op”命令，作为命令 136 和 137 来立即填补空白，使状态保持不变（它通过执行共识算法实例 136 和 137 的阶段 2 来做到这一点）。一旦选择了这些无操作命令，就可以执行命令 138-140。
现在已选择命令 1-140。领导者还完成了共识算法大于 140 的所有实例的第 1 阶段，并且可以在这些实例的第 2 阶段自由提出任何值。它将命令编号 141 分配给客户端请求的下一个命令，将其作为共识算法实例 141 的阶段 2 中的值。它建议接收到的下一个客户端命令为命令 142，依此类推。
领导者可以在得知其提议的命令 141 已被选择之前提议命令 142。它在提议命令 141 中发送的所有消息都可能丢失，并且在任何其他服务器了解领导者提议的命令 141 之前选择命令 142。当领导者未能收到对其阶段 2 的预期响应时实例 141 中的消息，它将重新传输这些消息。如果一切顺利，将选择其提议的命令。但是，它可能首先宕机，从而在所选命令序列中留下空隙。一般来说，假设一个领导者可以提前获得 \(\alpha\) 个命令——也就是说，它可以在命令 1 到 \(i\) 被选择之后提出命令 \(i + 1\) 到 \(i+\alpha\)。然后可能会出现多达 \(\alpha-1\) 个命令的间隙。
新选择的领导者为无数个共识算法实例执行阶段 1 ——在上面的场景中，实例 135-137 和所有大于 139 的实例。对所有实例使用相同的提议编号，它可以通过向其他服务器发送单个合理的短消息来做到这点。在第 1 阶段，只有当它已经收到某个提议者的第 2 阶段消息时，接受者才会以不止一个简单的 OK 来响应（在这个场景中，这仅适用于实例 135 和 140）。因此，服务器（充当接受者）可以用一条合理的短消息响应所有实例。因此，执行这些无限多的阶段 1 实例不会造成任何问题。
由于领导者的宕机和新领导者的选举应该是罕见的事件，因此执行状态机命令的有效成本（即对命令/值达成共识）是仅执行共识算法的第 2 阶段的成本。可以看出，Paxos 共识算法的第 2 阶段具有在存在故障时达成一致的任何算法的最小可能成本，参见 On the cost of fault-tolerant consensus when there are no faults—a tutorial。因此，Paxos 算法本质上是最优的。
这个关于系统正常运行的讨论假设总是有一个领导者，除了当前领导者宕机和选举新领导者之间的短暂时间。在异常情况下，领导者选举可能会宕机。如果没有服务器充当领导者，则不会提出新的命令。如果多个服务器认为他们是领导者，那么他们都可以在共识算法的同一个实例中提出值，这可能会阻止任何值被选择。然而，安全性得到了保护——两个不同的服务器永远不会在选择作为第 \(i\) 个状态机命令的值上存在分歧。只需要选举一个领导人以确保取得进展。
如果服务器集可以更改，那么必须有某种方法来确定哪些服务器实现了共识算法的哪些实例。最简单的方法是通过状态机本身。当前的服务器集可以成为状态的一部分，并且可以使用普通的状态机命令进行更改。我们可以通过让执行共识算法实例 \(i + \alpha\) 的服务器集由执行第 \(i\) 个状态机命令后的状态指定，从而允许领导者提前获得 \(\alpha\) 个命令。这允许任意复杂的重新配置算法的简单实现。
