摘要
分布式共识是分布式系统最重要的构建块之一。 Fast Paxos 是用于分布式共识的 Paxos 算法的最新变体之一。 Fast Paxos 允许接受者在快速回合次中单方面对其选择的值进行投票，从而消除了达成共识的沟通步骤。作为权衡，协调者必须建立一个大于 Classic Paxos 中使用的简单多数的法定人数。本文介绍了 Fast Paxos 算法的理论、实现和综合性能评估。与 Lamport 的原始文章相比，该理论以更易于理解的方式描述。特别是，导出了一个易于实现的协调器取值规则。在实现状态机复制的 Fast Paxos 时，开发了许多附加机制来应对实际场景。此外，实验表明 Fast Paxos 最适合在单客户端配置中使用。即使在局域网中存在两个或多个并发客户端也会导致频繁的冲突，这将降低系统吞吐量并增加客户端所经历的平均响应时间。由于频繁的冲突，Fast Paxos 在存在中到大量并发客户端的情况下实际上比 Classic Paxos 表现更差。
关键词：分布式共识、端到端延迟、容错、概率密度函数、仲裁要求、状态机复制、系统吞吐量
概论
分布式共识是分布式系统最重要的组成部分之一。例如，如果不使用一些分布式共识算法来确保所有副本保持一致，就不可能构建高可用性云服务。Fast Paxos 是用于分布式共识的原始 Paxos 算法（简称 Classic Paxos）的最新变体之一。Classic Paxos 非常适合状态机复制，它已被用于许多实际的容错系统中。 Fast Paxos 旨在通过使用更大的仲裁规模来进一步减少达成共识的延迟。与 Classic Paxos 类似，Fast Paxos 以回合次运行，每回合有两个阶段。如果一回合内没有达成共识，将启动新一回合的活跃度。在 Fast Paxos 中，可以有两种不同类型的回合：快速回合和经典回合。经典回合次的运行方式与经典 Paxos 中的回合次相同，只是协调器处的值选择规则不同，这将在后面的部分中解释。在 Lamport 于 2006 年发表的原始文章中，法定人数要求以及值选择规则取决于对该文中中称为 \(O4(v)\) 的以下观察结果的评估：
只有当存在一个 \(k-quorum R\) 使得 RTQ 中的每个接受者 a 的 \(vr(a) = k\) 和 \(vv(a) = v\) 时，才在第 \(k\) 回合中选择了一个值。
这里 \(Q\) 指的是当前回合的法定人数，\(k\) 是最近一回合的接受者 \(a\) 投票的回合数，\(k-quorum\) 是指在第 \(k\) 回合中使用的法定人数，\(vr(a)\) 是指接受者 \(a\) 已投票的回合的回合数，而 \(vv(a)\) 指的是该投票中包含的值\(O4(v)\) 为真当且仅当上述观察对于值 \(v\) 的某回合 \(k\) 为真。
正如我们所见，要评估这一观察结果，必须检查之前的每一回合 \(k\)，并确定回合 \(k\) 是否存在满足对 \(v\) 的特定约束的 \(k-quorum\)。这意味着协调器要评估是否一个值 \(v\) 满足 \(O4(v)\)，它必须在每一回合中从系统的每个接受者那里收集投票，这在异步环境中根本不实用。
在本文中，我们为协调者介绍了一个更易于实现的值选择规则，并提供了对仲裁要求的更直观推理，两者都无需评估 \(O4(v)\)。为了证明所提出的值选择规则的实用性，我们提出了一个用于状态机复制的 Fast Paxos 实现。我们表明，需要许多额外的机制来应对实际情况。此外，我们使用我们的研究原型对 Fast Paxos 进行了全面评估。我们的实验表明，Fast Paxos 最适合在单客户端配置中使用。即使在局域网中存在两个或多个并发客户端也会导致频繁的冲突，这将降低系统吞吐量并增加客户端所经历的平均响应时间。由于频繁的冲突，Fast Paxos 在存在中到大量并发客户端的情况下实际上比 Classic Paxos 表现更差。
本文的其余部分组织如下。第 2 节描述了 Fast Paxos 以及 Classic Paxos 及其变体中使用的系统模型。第 3 节定义了分布式共识解决方案的安全性和活跃性要求。第 4 节和第 5 节介绍 Classic Paxos 及其在状态机复制（称为 Multi-Paxos）中的应用，作为 Fast Paxos 的基础。在第 6 节中，我们描述了 Fast Paxos 和我们的理论贡献。在第 7 节和第 8 节中，我们报告了 Fast Paxos 的实施和性能评估的细节。我们以关于相关工作和结束语的最后两节来结束这篇文章。
系统模型
我们考虑一个具有多个进程的分布式系统，其中任何一个都可能提出一个值。一个进程可以以三个角色之一参与分布式共识算法（例如 Classic Paxos 和 Fast Paxos）：提议者，接受者，或学习者。提议者是提出要被他人选择和学习的值的人。接受者参与对提议的值的协议谈判。学习者是学习已选择的值的人。请注意，角色是逻辑分类的，一个进程可以承担多个角色，例如，一个进程可以同时充当提议者和接受者。
在客户端-服务器系统中，客户端将他们的请求发送到服务器进行处理，并期望收到相应的回复。当使用服务器的状态机复制时，必须确保所有副本以相同的总顺序传递和执行请求。对于每个请求，其总顺序构成了需要在副本之间达成分布式共识的值。为了确定每个请求的总顺序，通常将其中一个副本指定为主副本，并负责确定总顺序。因此，要达成一致的值通常由客户端和主节点共同贡献（即，他们共同作为提议者）。主节点也称为协调节点。
我们假设系统和共识算法在只有崩溃故障（即没有拜占庭故障）的异步环境中运行。异步环境意味着一个进程可能需要任意长的时间来完成一个本地任务，并且一条消息可能需要任意长的时间才能在预期的目标进程中传递，可能需要多次重传。此外，进程可能会失败，失败的进程会停止参与共识算法，即崩溃。
分布式共识的正确性标准
一个完善的共识算法应该确保下面定义的安全属性和活性属性：
- 安全性：共识算法应保证：
- (S.a)：如果一个值被一个进程选择，那么相同的值必须被任何其他选择了该值的进程选择
- (S.b)：选择的值必须是由系统中的进程之一提出的
- (S.c)：只有被某个进程选择的值才能被进程学习
- 活性：最终选择了一些值。此外，如果选择了一个值，那么系统中的一个进程最终可以学习该值。
安全要求 (S.a) 确保所有流程都选择相同的值。要求 (S.b) 和 (S.c) 排除了琐碎的解决方案，例如，所有流程都选择一个预定义的值。只有在系统同步期间才能满足活性特性。
Classic Paxos
Classic Paxos 分为两个阶段，分别是准备阶段（即第一阶段）和接受阶段（即第二阶段），如图 1 所示。准备阶段由提议者发起，向系统中的接受者发送一个准备请求，称为 \(P1a(n)\)，其中 n 是提议者选择的提议编号。在这个阶段，准备请求中不包含任何值。这可能看起来违反直觉，但限制提议者在提议的价值方面的自由至关重要，因为一些接受者可能已经接受了竞争提议者提出的值。允许提议者始终提出任意值可能会导致接受多个值（正如我们将看到的，在 Fast Paxos 中取消了此限制，并且定义了机制，以便在 Fast Paxos 中选择最多一个冲突值）。
在准备阶段，当接受者收到 P1a(n) 消息时，它会执行以下操作：
- 如果接受者没有对任何 \(P1a(n)\) 消息做出响应，则记录提议编号 \(n\)，并向提议者发送确认，记为\(P1b(n)\)
- 如果接受者已经回复了另一个 \(P1a(m)\) 的提议编号为 m 的消息，并且 \(m < n\)，则有两种情况：
- 接受者没有收到任何接受在接受阶段由提议者发送的请求，称为 \(P2a\) 消息，它记录较高的提议编号 \(n\)，并将其 \(P1b(n)\) 消息发送给提议者
- 接受者已经收到带有提议编号 \(k\) 的 \(P2a(k)\) 消息，它一定已经收到了某个提议者过去提出的值。这个完整的提案 \([k, v]\) 包含在给提案人的 \(P1b(n, [k, v])\) 中。显然，\(k\) 必须小于 \(n\)。
第二阶段（即接受阶段）从提议者可以设法收集大多数接受者的响应时开始。提议者通过以下方式确定要包含在 \(P2a\) 消息中的值：
- 如果提议者收到一条或多条带有完整提议的 \(P1b\) 消息。它在具有最高提案编号的提案中选择值 \(v\)；
- 如果提议者收到的 \(P1b\) 消息中没有一个包含完整的提议，则提议者可以自由提议任何值。 选择值后，提议者向接受者多播一条 \(P2a(n, v)\) 消息。当一个接受者收到一条 \(P2a(n,v)\) 消息时，只有当它已经响应了相应的 \(P1a(n)\) 消息时，它才会接受提议 \([n,v]\)。然后，它发送一个确认消息，称为 \(P2b(n)\)。
一旦选择了值，提议者就会向接受者多播一条 \(P2a(n, v)\) 消息。当一个接受者收到一条 \(P2a(n, v)\) 消息时，只有当它已经响应了相应的 \(P1a(n)\) 消息时，它才会接受提议 \([n,v]\)。然后，它发送一个确认 消息，称为 \(P2b(n)\)。
注意，当一个接受者接受一条 \(P2a\) 消息时，并不意味着 \(P2a\) 中包含的提议中包含的值已经被选中。只有在大多数接受者都接受了相同的 \(P2a\) 之后，才认为该值已被选中。在少数接受者接受 \(P2a\) 消息后，可能没有选择任何值或最终选择了另一个值。
学习者可以通过多种方式找出已选择的值。最直接的方法是让一个接受者将 \(P2b\) 多播给所有学习者，如图 1 所示。当一个学习者从大多数接受者那里收集到相同提议的 \(P2b\) 消息时，就可以放心，该值已被选择。作为替代方案，如果学习者的数量很大，可以选择一小部分学习者来接收来自接受者的多播，然后他们可以将接受的值转发给剩余的学习者。另一种选择是让每个学习者定期回合询接受者，看看他们是否接受了一个值。
如果一个学习者想要确保它学到的值确实是被选择的值，它可以要求一个提议者发出一个新的提议。该提议的结果将确认是否选择了该值。
Multi-Paxos
Classic Paxos 算法的一个直接应用是启用状态机复制。如前所述，服务器副本（即接受者）要同意的值是客户端发送的请求的总顺序。请求序列的总排序是通过运行 Classic Paxos 算法的一系列实例来完成的。每个实例都分配有一个序列号，表示所选请求的总排序。对于每个实例，要选择的值是应该分配给该实例的特定请求。
每个实例中的提议者被称为协调者（coordinator）、领导者（leader），或者简称为主要者（primary）。充当提议者的副本也充当接受者。在一个简单的实现中，主节点将选择的值传播到剩余的副本（通常称为备份），以便它们也可以学习该值。显然，主节点是第一个知道为 Classic Paxos 算法的每个实例选择了一个值的节点，并且通常是第一个向客户端发送回复的节点。备份可以抑制他们的回复，除非他们怀疑主服务器，因为客户端对于它的每个请求只需要一个回复。还可以通过将每个副本的 \(P2b\) 消息多播到所有副本（而不是只发送到主副本）来使备份更快地学习所选值。这种方法的一个折衷是在系统中发送更多的多播消息。此外，备份可能会在主节点之前学习选择的值。
通常，在系统部署开始时，其中一个服务器副本被指定为主服务器。只有当主节点出现故障时，这种情况很少见，或者被其他副本怀疑有故障时，才会选举另一个副本作为新的主节点。只要系统中存在唯一的主节点，就可以保证没有副本报告已接受主节点的任何提议，这将使主节点能够选择任何值（即，将任何请求分配给当前实例）。因此，在正常操作期间（即系统中只有一个主节点时）可以省略第一个阶段（即准备阶段）。
需要完整的 Classic Paxos 算法来选举一个新的主节点。此外，只要当前主节点运行正常，此运行将有效地执行所有经典 Paxos 实例的第一阶段。
上述将经典 Paxos 算法应用于状态机复制的方案最早是在 Paxos Made Simple 中提出的，而“Multi-Paxos”一词最早是在 (Chandra, Griesemer, Redstone, 2007) 中引入的。正常操作期间的 Multi-Paxos 算法如图 2 所示。请注意，主节点可以在收到来自法定人数副本的 \(P2b\) 消息后立即执行请求。
Fast Paxos
Fast Paxos 的目标是在客户端负责提议接受者选择的值的情况下减少达成共识的端到端延迟。在 Multi-Paxos 中，我们展示了 Classic Paxos 的第一阶段可以为算法的所有实例运行一次，前提是最初只有一个领导者。因此，在 Multi-Paxos 中，达成协议的成本是 Classic Paxos 算法的第二阶段。Fast Paxos 旨在通过在状态机复制中为所有 Fast Paxos 实例运行一条 P2a 消息来进一步降低达成共识的成本。这将使接受者能够单方面选择一个值（由客户端提供）并立即将 P2b 消息发送给领导者，从而减少端到端延迟。
因为 Classic Paxos 算法被证明是最优的，为了减少延迟，我们必须牺牲一些其他的东西。在 Fast Paxos 中，要容忍 \(f\) 个故障副本，需要 \(2f + 1\) 个以上的副本。我们将制定关于允许 Fast Paxos 工作的最小副本数的标准。此外，由于接受者（即服务器副本）单方面选择一个值（即客户端发送的请求消息），不同的接受者可能选择不同的值。这种情况被称为碰撞（在选择值时）。碰撞避免和碰撞恢复是 Fast Paxos 中出现的新问题。
我们首先描述 Fast Paxos 算法的基本步骤，然后讨论协调器的仲裁要求和值选择规则。我们通过提供 Fast Paxos 的正确性证明以及我们的修改来结束本节。
基本步骤
与 Classic Paxos 类似，Fast Paxos 也是逐回合运行（回合数对应 Classic Paxos 中的提案编号），每回合有两个阶段，如图 3 所示。第一个阶段是准备阶段，使协调者能够请求接受者的状态和承诺。 第二阶段是协调者选择一个值并由接受者投票。 当一个接受者在第 \(i\) 回合中响应了 P1a 消息时，就说接受者已经参与了第 \(i\) 回合。 当一个接受者向协调者发送一个 P2b 消息以响应来自协调者的 P2a 消息时，就说接受者已经对该回合投票。 当协调者在该回合中从法定人数的接受者中收集到具有相同值的 P2b 消息时，就说该值已被选中。
但是，Fast Paxos 与 Classic Paxos 有许多不同之处：
- 在 Fast Paxos 中，一回合可以是快速回合，也可以是经典回合。 快速回合次可能使用与经典回合次不同大小的法定人数。 我们将快速回合次中使用的法定人数称为快速法定人数，将经典回合次中使用的法定人数称为经典法定人数；
- 协调者的取值规则与经典 Paxos 不同，因为存在快速回合；
- 在经典回合次中，协调者选择要投票的值，类似于经典 Paxos；
- 在快速回合中，如果值选择规则允许协调者选择自己的值，它可能会在没有选择任何值的情况下向接受者发送特殊的 P2a 消息。这种特殊的 P2a 消息（也称为 any 消息）使接受者能够选择自己的值（由客户提出）进行投票。
学习者可以使用我们为 Classic Paxos 概括的任何学习机制学习已选择的值，只需进行一个修改：不是从大多数接受者那里收集来学习已选择的值，而是学习者必须在经典回合中从经典法定人数的接受者中收集，以及在快速回合中从快速法定人数的接受者中收集。
假设自从服务器开始运行以来有一个唯一的协调器，第一次运行快速回合时将始终允许协调器在阶段 2 发送任何消息。在典型的状态机复制系统中，这将允许为所有 Fast Paxos 实例发送一条 P2a 消息，这将消除一个通信步骤，如图 4 所示。这是 Fast Paxos 的唯一优势。 因此，只要有可能，就会运行快速回合，并且仅当由于协调器失败或由于冲突而无法在快速回合中达成共识时才使用经典回合。
冲突恢复、法定人数要求和价值选择规则
在快速回合中，如果协调者发出任何 P2a 消息，接受者将可以自由选择其唯一值。 如果有多个客户端同时提出不同的值（即它们同时向服务器副本发出请求），则不同的接受者可能会选择不同的值，这将导致冲突。 发生这种情况时，协调员可能会在其收集的法定人数中看到不同的值，这将阻止在此快速回合次中达成共识。
请注意，协调器不能阻止等待，直到它从法定人数的接受者那里收集到具有相同价值的投票，因为如果少于法定人数的接受者投票支持相同的价值，它可能永远无法建立法定人数 . 因此，在检测到碰撞时，协调器应该通过开始一个新的经典回合来启动恢复。 在这个新的经典回合次中，很明显协调员会在新回合次的第一阶段从法定人数的接受者那里收到相同或相似的信息。 因此，可以省略第一阶段，协调器可以继续确定要在第二阶段投票的值。
由于法定人数包含不同的值，协调者必须小心选择在前一回合中已选择或可能被选择的值。 就像 Classic Paxos 一样，Fast Paxos 不会终止，因此，一旦选择了一个值，在未来的任何一回合中也必须选择相同的值。 如果法定人数的接受者投票了相同的值，则选择或可能选择一个值。 选择任何其他值可能会导致选择两个或多个值，这将违反共识的安全属性。 然而，协调者要确定投票法定人数中的一个值是否已被选择或可能被选择，这并不简单。
在我们进一步研究值选择规则之前，我们首先证明 Classic Paxos 中基于简单多数的仲裁形成在 Fast Paxos 中不再有效。在经典 Paxos 中，要容忍 \(f\) 个错误的接受者，总共需要 \(2f + 1\) 个接受者，并且法定人数为简单多数 (\(f + 1\))。使用 \(f + 1\) 的 quorum 大小，两个 quorum 相交的数量可能只有一个接受者。因此，通过这种 quorum 形成，协调者不能排除可能已经选择了一个值的可能性，即使它已经收集了一个具有该值的投票。因此，如果协调器在其收集的投票法定人数中看到不同的值，它将无法确定选择哪个值。请注意，只能选择不同的值中的一个，因为即使法定人数是由简单多数形成的，接受者也不可能在同一回合中形成两个具有不同值的法定人数。然后问题变成确定哪些值是最有可能的候选值，以便如果在前一回合中选择了一个值，则保证选择该值。
