Paxos Made Simple
Paxos Made Simple
摘要
1 简介
用于实现容错分布式系统的 Paxos 算法一直被认为难以理解，可能是因为许多读者最初看的是希腊语。事实上，它是最简单、最明显的分布式算法之一。其核心是共识算法——“synod”算法。下一节将展示这种共识算法几乎不可避免地遵循我们希望它满足的属性。最后一部分将解释完整的Paxos算法。这个算法是通过将共识算法直接应用到构建分布式系统的有限状态机方法中得到的。这种方法应该是众所周知的，因为它是分布式系统理论中被引用次数最多的文章的主题。
2 共识算法
2.1 问题
假设可以提出价值的进程集合。共识算法确保选择提出值中的一个。如果没有提出任何值，则不应选择任何值。如果已经选择了一个值，那么进程应该能够学习所选的值。共识的安全要求是：
- 只能选出已提议的值
- 只有一个值能被选出
- 进程永远不会知道某个值已被选出，除非它确实已被选出。
我们不会尝试指定精确的存活要求。但是，目标是确保最终选择某个建议值，并且如果选择了某个值，则进程最终可以学习该值。
我们让共识算法中的三个角色由三类代理来执行：proposer、acceptor和learner。在一种实现中，单个进程可以充当多个代理，但这里我们不关心从代理到进程的映射。
假设代理能通过发送消息来相互通信。我们使用惯用的异步、非拜占庭模型，其中
- 代理以任意速度运行，可能因停止而失败，也可能重新启动。由于在选择一个值然后重新启动后所有代理都可能会失败，因此除非已失败并重新启动的代理可以记住某些信息，否则解决方案是不可能的。
- 消息的传送时间可以任意长，可以重复，也可以丢失，但它们不会被破坏。
2.2 选择值
选择值的最简单方法是使用单个接受代理。提议者向接受者发送提议，接受者选择收到的第一个提议值。虽然简单，但这个解决方案并不令人满意，因为接受者的失败使得任何进一步的进展都不可能。
因此，让我们尝试另一种选择值的方法。让我们使用多个接受者代理，而不是单个接受者。提议者将提议值发送给一组接受者。接受者可以接受提议的值。当足够多的接受者接受该值时，就会选择该值。多大才算足够够？为了确保只选择一个值，我们可以让一个足够大的集合由任意大多数代理组成。因为任何两个多数都至少有一个共同的接受者，所以如果接受者最多可以接受一个值，那么这种方法就有效。（在许多论文中都观察到了大多数的明显概括，显然是从Leslie Lampor开始的）
在没有失败或消息丢失的情况下，即使单个提议者只提出一个值，我们也希望选择一个值。这表明了要求：
P1 接受者必须接受它收到的第一个提案
但这个要求带来了一个问题。不同的提议者可能会在同一时间提出多个值，从而导致每个接受者都接受了一个值，但没有一个值被大多数接受者接受的情况。即使只有两个提议的值，如果每个值都被大约一半的接受者接受，那么单个接受者的失败可能会导致无法了解选择了哪个值。
P1 以及仅当大多数接受者接受时才选择某个值的要求意味着必须允许接受者接受多个提案。我们通过为每个提案分配一个（自然）编号来跟踪接受者可能接受的不同提案，因此提案由提案编号和值组成。为了防止混淆，我们要求不同的提案有不同的编号。如何实现取决于其实现，至今为止我们只是假设。当具有该值的单个提案被大多数接受者接受时，就会选择一个值。在这种情况下，我们说该提案（及其价值）已被选择。
我们可以允许选择多个提案，但我们必须保证所有选择的提案具有相同的值。通过对提案编号进行归纳，足以保证：
P2a 如果选择了值为 v 的提案，则选择的每个编号较高的提案都具有值 v。
我们仍然维护 P1 以确保选择某些提案。由于通信是异步的，因此可以选择某个从未收到过任何提案的特定接受者的提案。假设一个新的提议者“启动”并发布了一个具有不同值的更高编号的提议。P1 要求 c 接受该提案，违反了 P2a 。维持 P1 和 P2a 需要加强 P2a 以：
P2b 如果选择了值为 v 的提案，则任何提案者发布的每个编号较高的提案都具有值 v。
由于提案必须由提案者发出才能被接受者接受，因此 P2b 意味着 P2a ，而 P2a 又意味着 P2 。
为了发现如何满足 P2b，让我们考虑如何证明它成立。我们假设选择了一些编号为 m 且值为 v 的提案，并表明任何编号为 n > m 的提案也具有值 v。为了使证明过程更简单，我们通过在 n 上使用归纳法来进行，这样我们就可以证明在额外假设下，编号为 n 的提案具有值 v，即假设在 m 到 n-1 之间的每个编号的提案都具有值 v，其中 i : :j 表示从 i 到 j 的一系列数字集合。对于要选择的编号为 m 的提案，必须存在某个由大多数接受者组成的集合 C，使得 C 中的每个接受者都接受它。将此与归纳假设相结合，选择 m 的假设意味着：
C 中的每个接受者都接受了编号为 m ~ (n - 1) 的提案，并且任何接受者接受的编号为 m ~ (n - 1) 的提案的值含有 v。
由于任何由大多数接受者组成的集合 S 至少包含 C 的一个成员，因此我们可以通过确保维持以下不变量来得出结论，编号为 n 的提案具有值 v：
P2c 对于任意的值v和编号n，如果发出了一个带有值v和编号n的提案，那么存在一个由大多数接受者组成的集合S，满足以下条件之一：
a. 集合S中的任何接受者都没有接受过编号小于n的任何提案。
b. 值v是集合S中的接受者所接受的所有编号小于n的提案中编号最高的那个提案的值。
因此，我们可以通过保持 P2c 的不变性来满足 P2b 。
为了保持 P2c 的不变性，想要发布编号为 n 的提案的提案者必须学习编号小于 n 的最高编号提案（如果有的话），该提案已经或将被每个接受者以某种多数接受。了解已经被接受的提案很容易；预测未来的接受情况却很难。提议者并不试图预测未来，而是通过做出不会发生此类接受的承诺来控制未来。换句话说，提议者要求接受者不再接受任何编号小于 n 的提案。这导致了以下发布提案的算法：
提议者选择一个新的提议编号 n，并向某个接受者集合中的每个成员发送请求，要求其做出以下回应：
- 承诺不再接受编号小于 n 的提案，并且
- 已接受的小于 n 的最大数字的提案（如果有）。
我将这样的请求称为编号为 n 的准备请求。
如果提议者从大多数接受者那里收到了请求的响应，那么它可以发出一个编号为n、值为v的提案，其中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 的第 1 阶段。然后，另一个提议者 q 完成提案编号为 n2 > n1 的第 1 阶段。提议者 p 对编号为 n1 的提案的第 2 阶段接受请求被忽略，因为接受者都承诺不接受任何编号小于 n2 的新提案。因此，提议者 p 开始并完成阶段 1，新提议编号为 n3 > n2，导致提议者 q 的第二个阶段 2 接受请求被忽略。依此类推。
为了保证进展，必须选择一位杰出的提议者作为唯一尝试发布提案的人。如果杰出的提议者能够与大多数接受者成功沟通，并且它使用的提议的数量大于任何已经使用的提议，那么它将成功发布被接受的提议。如果发现某个请求的提案编号更高，则通过放弃提案并重试，杰出的提案者最终将选择一个足够高的提案编号。
如果系统（提议者、接受者和通信网络）的大部分正常运行，那么就可以通过选举一位杰出的提议者来实现活跃性。菲舍尔（Fischer）、林奇（Lynch）和帕特森（Paterson）的著名成果意味着，选举提议者的可靠算法必须使用随机性或实时性——例如，使用超时。但无论选举成功或失败，安全都是有保障的。
2.5 实现
Paxos 算法假设一个进程网络。在其共识算法中，每个进程都扮演提议者、接受者和学习者的角色。算法选择一个领导者，该领导者扮演着杰出提议者和杰出学习者的角色。Paxos 共识算法正是上面描述的算法，其中请求和响应都作为普通消息发送。（响应消息标有相应的提案编号以避免混淆。）稳定存储用于在故障期间保存，用于维护接受器必须记住的信息。接受器在实际发送响应之前将其预期响应记录在稳定存储中。
剩下的就是描述保证不会发布两个具有相同编号的提案的机制。不同的提议者从不相交的数字集中选择他们的数字，因此两个不同的提议者永远不会提出具有相同数字的提案。每个提议者都会记住（在稳定存储中）它尝试发布的最高编号的提议，并以比它已经使用过的任何提议编号更高的提议编号开始第 1 阶段。
3 实现状态机
实现分布式系统的一个简单方法是作为向中央服务器发出命令的客户端集合。服务器可以被描述为一个按照某种顺序执行客户端命令的确定性状态机。状态机具有当前状态；它通过将命令作为输入并产生输出和新状态来执行步骤。例如，分布式银行系统的客户可能是出纳员，状态机状态可能由所有用户的账户余额组成。提款是通过执行状态机命令来执行的，当且仅当账户余额大于提款金额时，该命令才会减少账户余额，并输出新旧余额。
如果使用单个中央服务器的实现在该服务器发生故障时也会失败。因此，我们使用一组服务器，每个服务器都独立实现状态机。因为状态机是确定性的，所以如果所有服务器都执行相同的命令序列，那么所有服务器将产生相同的状态和输出序列。发出命令的客户端可以使用任何服务器为其生成的输出。
为了保证所有服务器执行相同的状态机命令序列，我们实现了 Paxos 共识算法的独立实例序列，第 i 个实例选择的值是序列中的第 i 个状态机命令。每个服务器在算法的每个实例中扮演所有角色（提议者、接受者和学习者）。目前，我假设服务器集是固定的，因此共识算法的所有实例都使用相同的代理集合。
在正常操作中，会选举出一个单独的服务器作为领导者，这个领导者在共识算法的所有实例中充当杰出的提议者（唯一尝试发出提议的一方）。客户端将命令发送给领导者，领导者决定每个命令在序列中的出现位置。如果领导者决定某个客户端命令应该是第 135 个命令，它会尝试选择该命令作为共识算法的第 135 个实例的值。这通常会成功，它可能因为宕机而失败，或者因为另一个服务器也认为自己是领导者，并且对第 135 个命令应该是什么有不同的看法。但是共识算法确保最多可以选择一个命令作为第 135 个命令。
这种方法效率的关键在于，在 Paxos 共识算法中，要提议的值直到第 2 阶段才会被选择。回想一下，在完成提议者算法的第 1 阶段后，要么确定要提议的值，要么提议者可以自由提议任何值。
现在，我将介绍 Paxos 状态机实现在正常操作期间的工作原理。稍后，我将讨论可能出错的内容。我会考虑当前任领导者刚刚失败并且选择了新的领导者时会发生什么。（系统启动是一种特殊情况，尚未提出任何命令）。
新领导者是共识算法的所有实例的学习者，应该知道已经选择的大多数命令。假设它知道命令 1-134、138 和 139，即共识算法的实例 1-134、138 和 139 中选择的值。（我们稍后将看到命令序列中的这种差距是如何出现的。然后，它执行实例 135-137 的阶段 1 以及所有大于 139 的实例。（我将在下面描述如何做到这一点。假设这些执行的结果确定了要在实例 135 和 140 中建议的值，但在所有其他实例中使建议的值不受约束。然后，领导者对实例 135 和 140 执行阶段 2，从而选择命令 135 和 140。
领导服务器以及学习领导服务器知道的所有命令的任何其他服务器现在可以执行命令 1-135。但是，它无法执行命令 138–140，它也知道这一点，因为尚未选择命令 136 和 137。领导者可以将客户端请求的接下来的两个命令视为命令 136 和 137。相反，我们让它立即填补空白，如命令 136 和 137，一个特殊的 “no-op” 命令，保持状态不变。（它通过执行共识算法的实例 136 和 137 的第 2 阶段来实现此目的。选择这些 no-op 命令后，可以执行命令 138-140。
命令 1-140 现已选定。领导者还完成了所有大于 140 个共识算法的实例的第 1 阶段，并且可以在这些实例的第 2 阶段中自由提出任何值。它将命令编号 141 分配给客户端请求的下一个命令，并将其建议作为共识算法实例 141 的第 2 阶段中的值。它建议将接收的下一个客户端命令作为命令 142，依此类推。
领导者可以在得知其建议的命令 141 已被选中之前提出命令 142。它在提议命令 141 时发送的所有消息都有可能丢失，并且命令 142 可能在任何其他服务器了解领导者提议的命令 141 之前被选择。当 leader 在实例 141 中未能收到对其第 2 阶段消息的预期响应时，它将重新传输这些消息。如果一切顺利，将选择其提议的命令。但是，它可能会首先失败，从而在所选命令的序列中留下空白。通常，假设领导者可以提前获取 α 命令，也就是说，它可以在选择命令 1 到 i 之后提出命令 i + 1 到 i+α。然后可能会出现高达 α-1 个命令的差距。
新选择的领导对共识算法的无限多个实例执行阶段 1 — 在上面的场景中，实例 135-137 和所有大于 139 的实例。对所有实例使用相同的提议编号，它可以通过向其他服务器发送一条合理的短消息来实现此目的。在阶段 1 中，仅当接受者已经收到来自某个提议者的阶段 2 消息时，接受者才会以不简单的 OK 进行响应。（在此方案中，仅实例 135 和 140 出现这种情况。因此，服务器（充当接受者）可以使用一条合理短的消息响应所有实例。因此，执行阶段 1 的这些无限多个实例不会造成问题。
由于领导者失败和新领导者的选举应该是罕见的事件，因此执行状态机命令（即就命令/值达成共识）的有效成本是仅执行共识算法的第 2 阶段的成本。可以证明，Paxos 共识算法的第 2 阶段在存在故障的情况下达成协议的成本是任何算法中最低的。因此，Paxos 算法本质上是最优的。
对系统正常运行的讨论假设始终只有一个领导者，除了当前领导者失败和新领导者选举之间的短暂时期。在异常情况下，leader 选举可能会失败。如果没有服务器充当 leader，则不会提出新命令。如果多个服务器认为他们是领导者，那么他们都可以在共识算法的同一实例中提出值，这可能会阻止选择任何值。但是，安全性得到了保留 — 两个不同的服务器永远不会在选择作为第 i 个状态机命令的值上产生分歧。选举一名领导人只是为了确保进展。
如果服务器集可以更改，那么必须有某种方法可以确定哪些服务器实现了共识算法的哪些实例。最简单的方法是通过状态机本身。当前的服务器集可以成为状态的一部分，并且可以使用常规状态机命令进行更改。我们可以允许领导者提前获得α命令，方法是让执行共识算法的实例 i + α 的服务器集在执行第 i 个状态机命令后由状态指定。这允许对任意复杂的 reconfiguration 算法进行简单实现。