Fast Paxos

摘要

正如在实践中使用的那样，传统的共识算法需要三个消息延迟，然后任何进程才能学习选择的值。 Fast Paxos 是经典 Paxos 算法的扩展，它允许在两个消息延迟中学习值。非正式地解释了该算法的工作方式和原因，该算法的 TLA+ 规范作为附录出现。

简介

共识问题需要一组过程来选择单个值。本文考虑了非拜占庭错误的异步消息传递系统中的共识问题。这个问题的解决方案绝不能允许选择两个不同的值，尽管有任意数量的故障，并且如果足够多的进程没有故障并且可以相互通信，它最终必须选择一个值。

在共识问题的传统陈述中，每个过程都提出一个值，并且选择的值必须是那些提出的值之一。不难看出，任何解决方案都需要至少两次消息延迟，然后任何进程才能了解已选择的值。许多算法在最好的情况下实现了这种延迟。经典的 Paxos 算法很受欢迎，因为它在实际系统中使用时在正常情况下实现了最佳延迟。

传统共识算法所需的明显最优消息延迟数量是虚幻的——传统问题陈述的产物，其中值由提出它们的相同进程选择。在许多应用程序中，值不是由选择值的相同进程提出的。例如，在客户端/服务器系统中，客户端提出要执行的下一个命令，服务器选择一个提议的命令。当在这样的系统中使用传统的共识算法时，在客户端提出命令和某个进程得知选择了哪个命令之间需要三个消息延迟。

快速共识算法是这样一种算法，其中一个进程可以在它被提出时的两个消息延迟内学习选择的值，即使值是由不同的进程集提出和选择的。已经表明，如果竞争提案发生冲突，即如果同时提出两个不同的值 ，没有通用共识算法可以保证在两个消息延迟内学习。因此，快速共识算法在发生冲突时并不总是很快。

Fast Paxos 是一种快速共识算法，是经典 Paxos 的变体。在正常情况下，在没有冲突的情况下，学习发生在两个消息延迟中，并且即使发生冲突，也可以保证在三个消息延迟中发生。此外，它可以使用尽可能少的进程数量来实现任何所需程度的容错。

Fast Paxos 背后的基本思想也是 Brasileiro 等人早期算法的基础。然而，他们只考虑了传统的共识问题，因此他们没有意识到他们的算法可以很容易地修改以获得快速的共识。 Pedone 和 Schiper 的 R-共识算法也可以被修改以产生一个快速的共识算法。然而，最终算法在存在冲突的情况下至少需要四个消息延迟。（他们还使用类似的算法解决了一个更普遍的问题，在共识的特殊情况下，当发生冲突时也需要至少四个消息延迟。）Zielinski 最近提出了一个快速的共识算法，可以看作是 Fast Paxos 的一种变体。

Fast Paxos 本质上是经典 Paxos 的简单扩展。如果理解了经典 Paxos 的工作原理，就很容易理解 Fast Paxos 的工作原理。因此，我从第 2 节开始解释经典的 Paxos。第 3 节然后解释如何修改经典 Paxos 以获得 Fast Paxos。这些部分的说明有些非正式。他们的目标是解释算法为何起作用；它们没有以伪代码或任何其他语言提供算法的惯常简明描述。经典 Paxos 算法的精确陈述可以在其他地方找到，附录中给出了 Fast Paxos 的正式 TLA+ 规范。 TLA+ 规范足够通用，可以涵盖此处讨论的所有变体。然而，没有一个 Fast Paxos 的单一声明充分描述了实现所有这些变体所涉及的细节。对 Fast Paxos 底层原理的透彻理解比任何算法描述（无论是伪代码还是正式语言）都为实现它做好了准备。

最后一节讨论了 Fast Paxos 的最优性，解释了 Brasileiro 等人的算法之间的关系。和 Fast Paxos，并简要提到了经典 Paxos 和 Fast Paxos 的泛化处理拜占庭式故障。

经典的 Paxos 算法

问题

共识问题最有用地用三组代理表示：可以提出值的提议者，选择单个值的接受者，以及学习选择了什么值的学习者。代理代表某个进程所扮演的角色； 一个进程可以扮演多个角色。例如，在客户端/服务器系统中，客户端可能扮演提议者和学习者的角色，而服务器可能扮演接受者和学习者的角色。

我假设惯用的异步、分布式、非拜占庭计算模型，其中：

• 代理以任意速度运行，可能因停止而失败，也可能重新启动。但是，代理可能不会执行不正确的操作。
• 代理通过发送消息进行通信，这些消息可能需要任意长的时间才能传递，可以无序传递，可以复制，也可以丢失。 但是，消息永远不会（无法检测到）损坏。

共识的安全要求如下，其中一个值只能由提议者提出。

• 非平凡性：只能学习提议的值。
• 一致性：最多可以学习一个值。

大多数共识算法，包括 Fast Paxos，都可以轻松满足非平凡的要求。因此，我将在很大程度上忽略不平凡。通过确保接受者只选择一个值并且只能学习他们选择的值来满足一致性。确保只能选择一个值是困难的部分； 很明显应该如何学习选择的值。因此，我将专注于接受者如何选择一个值。

面对任意数量的（非拜占庭式）故障，必须保持安全要求。共识算法还应满足进度要求，即如果足够多的代理无故障，则最终选择一个值。我们不想依赖提议者或学习者来取得进展，因为他们可能不可靠。例如，我们不希望客户端/服务器系统仅仅因为客户端没有响应而停止；客户可能扮演提议者和/或学习者的角色。进程应该只要求足够多的接受者是无故障的，只要有一个无故障的提议者来提出一个值，并且有一个无故障的学习者来学习一个值。然而，这样的要求是有问题的，因为经典的 Fischer、Lynch、Paterson 结果指出任何满足共识安全属性的容错异步算法都无法满足它。因此，需要一些额外的假设。不同的共识算法使用不同的假设。我将推迟对 Paxos 算法的进程属性的精确陈述，其中涉及定义“无故障”的含义，直到我描述了它如何满足安全属性。这是可能的，因为安全要求必须在没有任何无故障假设的情况下保持不变。

如果所有代理都没有故障，即使它们都失败并重新启动，也必须有可能取得进展。 由于可以在代理失败之前学习到一个值，因此代理必须有一些稳定的存储，可以在失败和重新启动后幸存下来。 我假设代理在重新启动时会从稳定的存储中恢复其状态，因此代理的故障与它的简单暂停没有区别。 因此没有必要明确地对故障进行建模。

安全

基本算法

我首先描述一个简单版本的 Paxos 共识算法，它满足共识的安全要求。 它在第 2.3 节中扩展到也满足进度属性的完整算法。

实现一致性要求不选择两个不同的值。 由于一个接受者在任何一回合中最多投票接受一个值，并且任何两个多数都包含一个共同的接受者，因此不可能在同一回合中选择两个不同的值。 但是，接受者可以在不同的回合次中投票接受不同的值。 实现一致性的难点在于确保在不同的回合次中不会选择不同的值。

实现一致性要求不选择两个不同的值。 由于一个接受者在任何一回合中最多投票接受一个值，并且任何两个多数都包含一个共同的接受者，因此不可能在同一回合中选择两个不同的值。 但是，接受者可以在不同的回合次中投票接受不同的值。 实现一致性的难点在于确保在不同的回合次中不会选择不同的值。

尽管我们根据接受者曾经投过的所有票来推断算法，但接受者不必记住这些票。 一个接受者 \(a\) 只维护以下数据：

• \(rnd[a]\)：\(a\) 参加过的编号最高的回合次，初始为 0。（由于 0 不是回合次，所以 \(rnd[a] = 0\) 表示没有参加任何回合次。）
• \(vrnd[a]\)：\(a\) 投票的编号最高的回合次，初始为 0。（因此，\(rnd[a] \le rnd[a]\) 始终为真。）
• \(vval[a]\)：\(a\) 在回合 \(vrnd[a]\) 中投票接受的值； 它的初始值（当 \(vrnd[a] = 0\) 时）无关紧要。

Paxos 假设有一组协调者代理。 协调者和接受者的角色通常由同一个进程扮演。 对于每一回合 \(i\)，一些协调者被预先分配为第 \(i\) 回合的协调者。此外，每个协调者都被指定为无限多回合的协调者。 提案人将他们的提案发送给协调者。 如下所述，第 \(i\) 回合的协调者选择一个它试图在该回合中选择的值。 每个协调者 \(c\) 维护以下数据：

• \(crnd[c]\)：\(c\) 开始的编号最高的一回合，最初为 0。
• \(cval[c]\)：\(c\) 为回合 \(crnd[c]\) 选择的值，或者如果 \(c\) 尚未为该回合选择一个值，则为特殊值 \(none\)。 它的初始值无关紧要。

如果在第 \(i\) 回合中，学习者从大多数接受者那里收到阶段 2b 的消息，宣布他们在第 \(i\) 回合中都投票给了 \(v\)，那么它就会学习到一个值 \(v\)。

第 \(i\) 回合在以下阶段进行，其中 \(c\) 是该回合的协调者。

1. 1. 如果 \(crnd[c] < i\)，则 \(c\) 通过将 \(crnd[c]\) 设置为 \(i\)，将 \(cval[c]\) 设置为 \(none\) 来开始第 \(i\) 回合，并向每个接受者 \(a\) 发送消息，请求 \(a\) 参与第 \(i\) 回合。
   2. 如果接受者 \(a\) 收到参与第 \(i\) 回合的请求并且 \(i > rnd[a]\)，则 \(a\) 将 \(rnd[a]\) 设置为 \(i\)，并向协调者 \(c\) 发送包含回合数 \(i\) 和 \(vrnd[a]\) 和 \(vval[a]\) 的当前值的消息。如果 \(i \le rnd[a]\)（因此 \(a\) 已经开始第 \(i\) 回合或更高编号的回合），则 \(a\) 忽略该请求。
2. 1. 如果 \(crnd[c] = i\)（所以 \(c\) 还没有开始更高编号的一回合），\(cval[c] = none\)（所以 \(c\) 还没有执行这一回合的阶段 2a），并且 \(c\) 已经收到阶段来自大多数接受者的第 \(i\) 回合的 1b 消息；然后根据下面描述的规则，\(c\) 使用这些消息的内容来选择一个值 \(v\)，将 \(cval[c]\) 设置为 \(v\)，并向接受者发送一条消息，要求他们在第 \(i\) 回合投票接受 \(v\)。
   2. 如果一个接受者 \(a\) 在第 \(i\) 回合收到一个投票接受一个值 \(v\) 的请求，并且 \(i \ge rnd[a]\)并且 \(vrnd[a] \ne i\)；然后 \(a\) 在第 \(i\) 回合投票接受 \(v\)，将 \(vrnd[a]\) 和 \(rnd[a]\) 设置为 \(i\)，将 \(cval[a]\) 设置为 \(v\)，并向所有学习者发送消息，宣布其第 \(i\) 回合投票。 如果 \(i < rnd[a]\) 或 \(vrnd[a] = i\)（因此 \(a\) 已开始更高编号的一回合或已在此回合中投票），则 \(a\) 忽略该请求。

协调者可以随时为新的回合数执行阶段 1a 动作。 但是，该操作的启用条件会阻止协调者开始一个比它已经开始的数字低的一回合。 不同的回合次可以同时执行，但是如果接受者收到（并采取行动）更高编号回合次的消息，它将停止参与回合次。 请求接受不同值的阶段 2a 消息可以在不同的回合次中发送。 但是，阶段 2a 动作的启用条件和回合次对协调者的唯一分配确保了在同一回合次中不能发送具有不同值的阶段 2a 消息。

在阶段 2a 中选择一个值

进展

Progress 属性

完整算法

我现在扩展上述算法，使其满足进度属性。首先，协调者和接受者的动作修改如下：

• CA1. 如果接受者 \(a\) 收到第 \(i\) 回合的阶段 1a 或 2a 消息，且 \(i < rnd[a]\) 并且第 \(rnd[a]\) 回合的协调者不是第 \(i\) 回合的协调者，则 \(a\) 向第 \(i\) 回合的协调者发送一条特殊消息，指示那一回合 \(rnd[a]\) 开始了。(如果 \(i < rnd[a]\) 并且回合 \(i\) 和 \(rnd[a]\) 具有相同的协调者，则回合 \(i\) 消息已过时并被忽略。)
• CA2. 只有当协调者 \(c\) 认为自己是当前的领导者时，它才会执行一个动作。只有当 \(crnd[c] = 0\) 或者它已经知道已经开始了一回合 \(j\) 时，它才开始新一回合 \(i\)，对于 \(crnd[c] < j < i\) 的某些 \(j\)。

由于任何消息都可能丢失，因此代理可能必须重新传输消息以确保它们最终被传递。我修改算法：

• CA3. 每个接受者不断地重新发送它发送的最后一个阶段 1b 或 2b 消息；任何认为自己是领导者的协调者不断向每个接受者重新发送它发送的最后一个阶段 1a 或 2a 消息；并且每个提出了值的提议者不断地将该提议重新发送给每个协调者。

CA3 要求代理发送无限的消息序列。第 2.4 节解释了如何停止这种无休止的消息重传。到目前为止描述的动作说明了代理应该尝试执行的动作。我们不能指望一个失败的代理成功地做任何事情。我们所能期待的是：

• CA4. 一个无故障的代理最终会执行它应该执行的任何操作。

例如，CA3 和 CA4 意味着当接受者 a 没有故障时，它最终必须重新发送它发送的最后一个阶段 1b 或 2b 消息。 CA4 不禁止有缺陷的代理执行操作。

过程证明

实施注意事项

减少消息数量

经典 Paxos 的成本

Paxos 加速

如上文第 2.4.2 节所述，Paxos 共识算法中正常情况下的通信模式为：

\[ 提议者 \to 领导者 \to 接受者 \to 学习者 \]

在 Fast Paxos 中，提议者绕过领导者直接将其提议发送给接受者。这可以节省一条消息延迟（和一条消息）。我现在解释它是如何工作的。但首先，我需要以一种小而重要的方式概括 Paxos 算法。

Paxos 算法在上面根据多数集进行了说明，其中多数集包含大多数接受者。如果在第 \(i\) 回合中有多数接受者投票接受 \(v\)，则在第 \(i\) 回合中选择值 \(v\)。多数集所需的唯一属性是任何两个多数集都具有非空交集。该算法通过假设任意两个称为法定人数的集合的集合来简单概括，这样任何两个法定人数都具有非空交集，并在第 2 节中简单地将“majority set”替换为“法定人数”。

我们可以通过允许法定人数集取决于回合数来进一步推广该算法。也就是说，我们假设对于每个回合数 \(i\)，有一组称为 i-quorum 的接受者集合。如果某个 i-quorum 中的所有接受者在第 \(i\) 回合中投票接受 \(v\)，则在第 \(i\) 回合中选择值 \(v\)。同样，保持一致性所需的唯一要求是任何两个仲裁都具有非空交集。这意味着对于任何整数 \(i\) 和 j，任何 i-quorum 和任何 j-quorum 都有非空交集。对算法的必要更改是显而易见的。例如，在图 1 中，Q 应该是 i-quorum，而不是多数集。我不会费心明确地重写算法。

在第 2.3 节的进度属性中，“多数集”应该替换为什么并不明显。这将在下面的第 3.3 节中讨论。

基本算法

我现在描述第 2.2 节的基本 Paxos 算法对 Fast Paxos 的推广。它只保证安全。稍后会考虑进度和成本。在 Fast Paxos 中，回合编号分为快速回合编号和经典回合编号。一回合被称为快速或经典，取决于它的编号。与以前一样，回合分两个阶段进行，但有两个不同之处：

• 协调者在阶段 2a 中选择值的规则被修改如下所述。
• 在一个快速的第 \(i\) 回合中，如果协调者可以在阶段 2a 中选择任何提议的值，那么它可以代替选择单个值，而是向接受者发送一个称为 \(any\) 消息的特殊阶段 2a 消息。当接受者收到阶段 2a 任何消息时，它可以将任何提议者的提议值的消息视为具有该值的普通第 \(i\) 阶段 2a 消息。（但是，对于单个值，它可能只执行一次第 \(i\) 阶段 2b 动作。）

回想一下，在正常情况下，协调者 \(c\) 收到的所有阶段 1b 消息都表明在该回合中没有接受者投票，因此 \(c\) 可以选择阶段 2a 中的任何提议值。因此，快速回合的正常情况是 \(c\) 发送阶段 2a \(any\) 消息。这通常在为该算法实例提出任何值之前，选择 \(c\) 作为领导者时完成。然后，接受者等待来自提议者的提议消息，并将其接收到的第一个消息视为来自 \(c\) 的普通阶段 2a 消息。

经典回合的工作方式与经典 Paxos 中的相同。协调者选择接受者可以投票的值，因此不同的接受者不能在同一回合中投票接受不同的值。在快速回合中情况并非如此。如果协调者在快速回合中发送阶段 2a \(any\) 消息，则每个接受者独立决定将哪个提议消息作为阶段 2a 消息。因此，不同的接受者可以在快速回合次中投票接受不同的值。

协调者在阶段 2a 中选择值的规则不再保证一致性，即使对于经典回合也是如此。事实上，这条规则根本不再适用。图 1 中的规则声明断言，如果 \(k \ne 0\)，则 \(V\) 包含单个元素。如果 \(k\) 是一个快速整数，这就不再适用了。必须修改在阶段 2a 中选择值 \(v\) 的规则。

冲突恢复

在经典 Paxos 中，如果 i-quorum 的接受者在接收到更高编号轮的消息之前收到该轮的第 2a 阶段消息，则第 i 轮成功选择一个值。 如果 i 是协调器发送阶段 2a 任何消息的快速轮次，则这不适用于 Fast Paxos。 在这种情况下，不同的接受者可以在该轮中投票接受不同的值，从而导致没有值被选择。 在正常情况下，接受者首先收到阶段 2a 的任何消息，然后投票接受它收到的第一个提议值。 如果两个或多个不同的提议者几乎同时发送提议，并且这些提议被接受者以不同的顺序接收，则该轮可能会失败。 我现在考虑该算法如何从竞争提案的这种冲突中恢复。