⬑

SwiftPaxos Fast Geo-Replicated State Machines

#论文翻译

ToC

https://www.usenix.org/system/files/nsdi24-ryabinin.pdf

作者：

摘要

云服务通过在不同地理区域的站点之间复制数据来提高其可用性。为此，已经提出了各种状态机复制协议，可以减少低冲突工作负载下的延迟。然而，当冲突增加时，这些协议可能会比 Paxos 提供更低的性能。本文介绍了 SwiftPaxos —— 一种与 Paxos 相比降低最佳情况延迟而不影响最坏情况延迟的协议。如果没有冲突，则 SwiftPaxos 在 2 个消息延迟内执行命令，在有冲突时则需要 3 个消息延迟。为实现这一目标，该协议允许副本对它们接收状态机命令的顺序进行投票。与先前的协议不同，SwiftPaxos 允许一个副本投两次票：首先是针对自己的排序建议，然后是跟随领导者。这种机制避免了在副本之间发生分歧时重新启动投票过程，并节省计算时间和消息延迟。我们的评估显示，SwiftPaxos 的吞吐量比当前技术水平高达 2.9 倍。

1. 引言

背景：今天的云服务在世界各地的数据中心运行。这些服务的关键部分在不同的地理位置复制并保持强一致性。为了实现这一点，云提供商依赖于状态机复制（State-Machine Replication, SMR），其中一个服务由确定性状态机定义，并且每个站点维护自己的状态机副本。一个 SMR 协议协调命令在站点上的执行，确保它们保持同步。最终系统是可线性化的，提供了一个幻觉，即应用于服务的每个命令都会立即在所有站点执行。

不幸的是，常见的 SMR 协议，如 Paxos1 和 Raft2 在地理复制（Geo-Replicated）部署中具有较高的延迟。这些协议通过一个领导站点传输所有命令，该站点对命令进行排序并将其持久化到副本中。如果领导者崩溃，则会选举新的领导者；给定站点充当领导者的时间段称为投票期（ballot）。在这种协议中，客户端在经过 4 个消息延迟后才能得知命令执行结果：从客户端到领导者再到副本一来一回。这种高延迟情况更糟糕的是，地理复制的事务处理系统（如 Spanner3）在执行单个事务时多次使用 Paxos，例如，实现两阶段提交的容错版本。

问题：已有多种旨在降低延迟的状态机复制（SMR）协议提案。其中一种方法由 Fast Paxos4 首次提出：客户端直接联系副本（replica），绕过领导者（leader），并让每个副本独立地对命令进行排序。如果足够多的副本（通常超过总数的 3/4）在命令的排序上达成一致，则采用“快速路径”（fast path）；否则，就通过“慢速路径”（slow path）处理，这需要额外的消息交换来解决排序分歧。我们可以通过以下观察来提高副本在命令排序上自发达成一致的可能性：为了满足线性一致性（linearizability），副本只需就非可交换命令（即存在冲突的命令）的顺序达成一致即可 5 6。这意味着，当不存在竞争（contention）时——即各副本以相同顺序接收到冲突命令（这在实际应用负载中经常出现7 8 9）——系统仍可走快速路径。然而，采用这一思路的协议（如 Generalized Paxos5）一旦遇到哪怕仅有一对命令发生竞争，开销就会急剧增加：此时协议会变更选票（ballot），其机制类似于处理领导者故障的情形。这需要在副本之间传输大量状态，并中断所有命令的处理（包括那些并不冲突的命令）。正因如此，Generalized Paxos 在实践中并未得到广泛应用。

另一种方法则完全摒弃了领导者，允许副本以对等（peer-to-peer）的方式对命令进行排序（如 EPaxos8 及其后续工作 10 11 12）。为了实现最优性能，这类无领导者协议通常要求客户端与某个数据副本共置（co-located）。然而，由于复制成本高昂，地理分布式系统通常不会在每个客户端所在位置都维护一个数据副本13 14。此外，这类 SMR 协议中的命令执行常常会因一种“车队效应”（convoy effect）而延迟。因此，即使在冲突率较低的情况下，这些协议的尾部延迟（tail latency）仍然很高；一旦冲突率上升，延迟便会急剧飙升11 15 16。

贡献：为了解决这些局限性，本文提出了 SwiftPaxos——一种新的状态机复制（SMR）协议，可在地理分布的数据上提供快速的线性一致性操作。当某条命令与并发提交的命令可交换（commute）时，SwiftPaxos 能在 2 个消息延迟内完成该命令的处理（快速路径）。否则，SwiftPaxos 仅需领导者额外花费 1 个延迟来解决冲突，总体共需 3 个消息延迟（慢速路径）。与 Generalized Paxos5 不同，慢速路径不会干扰系统运行，也无需传输大量状态数据。由于在 SwiftPaxos 中冲突由领导者负责解决，因此与 EPaxos8 不同，它还表现出较低的尾部延迟（tail latency）。因此，SwiftPaxos 在不恶化最坏情况延迟的前提下，显著降低了最佳情况下的延迟（相比传统 Paxos）。

为了实现上述优势，SwiftPaxos 采用如下机制：客户端将其命令 ( c ) 直接发送给各个副本，各副本据此计算出 ( c ) 的依赖集合——即那些与 ( c ) 冲突、且必须在其之前执行的命令。在每个副本上，这些依赖关系构成命令之间的一个偏序（partial order），用于规定命令应如何应用于本地状态机的副本。为了计算某条命令的依赖关系，各副本会根据其接收到命令的顺序提出各自的依赖提案，随后就其中一个提案达成一致。如果足够多的副本提出了相同的提案，则该命令可在单次往返通信内完成处理（快速路径）。否则，各副本将采纳领导者提出的提案，这会额外引入一次消息延迟（慢速路径）。

该方案的关键创新在于：在慢速路径中，一个副本会为两个不同的提案投票——首先投给自己本地生成的提案，随后再投给领导者的提案，且后者会覆盖前者。这种“双重投票”在传统的类 Paxos 状态机复制（SMR）协议中通常是不安全的：这正是 Generalized Paxos5 只能通过更换选票（ballot）来解决分歧的原因。然而，在 SwiftPaxos 中，这种做法是安全的，因为我们把领导者纳入了所有快速法定人数（fast quorum）之中。因此，如果某个快速法定人数中的副本与领导者意见不一致，该副本就能确定：该命令不可能已在快速路径上被提交。于是，该副本可以迅速修正自己的投票——通过发送一条新消息来撤销（override）之前的投票，而不会破坏安全性。这一机制使得慢速路径上的命令处理仅需 3 个消息延迟即可完成。

我们已在 Amazon EC2 的 13 个区域对 SwiftPaxos 进行了实验评估。根据竞争程度的不同，该协议相比 Paxos 可将平均延迟降低 16%–29%；在混合 YCSB 工作负载17 下，其吞吐量最高可达 EPaxos 的 2.9 倍。

2. 系统模型

我们考虑一个地理分布的消息传递系统，其中进程可能因崩溃而失效，但不会表现出恶意行为。这些进程分为两类：运行分布式服务的副本（replicas）和使用该服务的客户端（clients）。我们用 $R$ 表示副本集合，并假设有 $N = 2f + 1$ 个副本，其中最多 $f$ 个可能失效。$R$ 中的每个进程对应一个位于独立数据中心的服务器；客户端可以与服务器共置，也可以位于其他位置。副本集合可通过标准的重配置技术进行变更1 18，本文省略与此相关的细节（译者注：配置变更可不简单）。

状态机复制（State-Machine Replication, SMR）是在上述系统中设计高可用分布式服务的常用方法3 19。该服务由一个确定性状态机构成，该状态机包含一组状态 $S$，并接受一组命令 $C$。给定一个命令 $c$ 和一个状态 $s$，函数 $\text{exec}(c, s)$ 返回一个由返回值 $r$ 和新状态 $s'$ 组成的二元组 $(r, s')$，其中 $s'$ 是在状态 $s$ 中执行命令 $c$ 后得到的结果。每个副本维护其自身的状态机副本，并通过变量 state 访问。SMR 协议协调各副本上的命令执行，确保它们所维护的状态机副本始终保持一致。

客户端是无状态的，但它们知道如何与副本通信。SMR 协议允许客户端通过 API 调用 submit(c) 提交命令 $c$ 以供执行。每条提交的命令 $c$ 都附带一个唯一标识符 $\text{id}(c)$。函数 $\text{client}$ 将每个标识符关联到提交该命令的客户端。当 SMR 协议获得命令 $c$ 的响应值 $r$ 时，会向上回调客户端，发送通知 $\text{response}(\text{id}(c), r)$。

本文提出的协议满足线性一致性（linearizability）20。直观而言，这意味着对客户端而言，所有命令看起来就像是在一个单一的状态机副本上按某个顺序依次执行的，且该顺序与真实时间顺序（即非重叠命令调用的先后顺序）一致。

为满足线性一致性，副本只需就不可交换命令（non-commuting commands）的执行顺序达成一致即可5 6。更精确地说，两条命令 $c$ 和 $d$ 是可交换的（commute），当且仅当对于状态机的任意状态 $s$ 满足以下两个条件：
(i) 在 $s$ 中先执行 $c$ 再执行 $d$，与先执行 $d$ 再执行 $c$，最终得到的状态相同；
(ii) $c$ 在状态 $s$ 中的返回值，与其在从 $s$ 执行 $d$ 后得到的状态中执行时的返回值相同，反之亦然。

当两条命令不可交换时，我们称它们冲突（conflict），记作 $c \bowtie d$。在实际系统中，冲突关系可通过服务 API 进行估计（over-approximated）：例如，在键值存储中，操作不同键的命令是可交换的。而在采用延迟更新复制（deferred update replication）的事务系统中（如 Spanner3），冲突可在提交时被检测出来。

为了给出一个 SMR 协议的形式化规范，我们首先在命令集合 $C$ 上定义一个关系 $\prec$：对于任意两条命令 $c$ 和 $d$，若满足以下任一条件，则记作 $c \prec d$：
(i) $c \bowtie d$（即 $c$ 与 $d$ 冲突），且某个副本 $p$ 在执行 $d$ 之前执行了 $c$；或
(ii) 某个副本在任意客户端提交 $d$ 之前已执行了 $c$。

一个 SMR 协议需满足以下性质：

有效性（Validity）：如果某个副本执行了命令 c ，则必有某个客户端在此之前已提交了 c
完整性（Integrity）：每个副本至多执行每条命令一次
有序性（Ordering）：关系 ≺ 是无环的
非平凡性（Nontriviality）：客户端为命令 c 获得的返回值 r ，必须是 c 在某个副本上执行所得的结果
活性（Liveness）：如果命令 c 由一个非失效客户端提交，或已被某个副本执行，则 c 最终会被所有非失效副本执行。

实现上述规范足以保证服务的线性一致性与响应性5 6。
具体而言，有序性（Ordering） 保证了不同副本不会以不同顺序执行相互冲突的命令。
与标准做法一致，为确保活性（liveness），我们假设系统最终是同步的（eventually synchronous）21，即非失效进程之间的消息延迟最终是有界的。

3. 核心概念和协议概述

我们首先概述 SwiftPaxos，随后对其细节进行详述。我们已对 SwiftPaxos 的正确性进行了严格证明，但由于篇幅限制，将该证明推迟至附录 §A。因此，在本文的解释中，我们将陈述协议的关键不变式（invariants），并对其成立原因进行非形式化的说明。

3.1 选票（ballots）

与典型的类 Paxos 协议一样，SwiftPaxos 的执行被划分为一系列选票（ballots）。每个副本在任意时刻仅处于一个选票中，该选票记录在变量 bal 中。每个选票 $b$ 都有一个固定的领导者副本 $\text{leader}(b) = p_{(b \bmod N)}$，其余参与者均为跟随者（followers）。如果 $\text{leader}(b)$ 被怀疑失效，某个跟随者将启动恢复流程，切换到一个编号更高的选票，并指定新的领导者。副本中的变量 status 用于记录其当前状态：正常运行（NORMAL）或正在恢复（RECOVERING）。

我们称副本的多数集为一个法定人数（quorum）。每个选票 $b$ 关联两组法定人数：快速法定人数集合 $\text{FQ}(b)$ 和 慢速法定人数集合 $\text{SQ}(b)$，分别用于 SwiftPaxos 的快速路径和慢速路径。对于副本 $p$，若其属于 $b$ 的某个快速（或慢速）法定人数，则分别记作 $\text{fast}(p, b)$ 和 $\text{slow}(p, b)$。我们要求选票 $b$ 的领导者必须属于其所有的快速和慢速法定人数。除这一约束外，慢速法定人数可以是任意多数副本集合。而快速法定人数则需满足更严格的条件（类似于 Fast Paxos4），即任意两个快速法定人数的交集必须包含多数副本：

$$ \forall Q_1, Q_2 \in \text{FQ}(b).\ |Q_1 \cap Q_2| > N/2. \quad \text{(FQI)} $$

该条件可通过不同方式满足。本文后续主要考虑以下两种构造方式：

(C1) 快速法定人数是任意包含超过 $3/4$ 副本（且包含领导者的）集合。

(C2) 存在一个唯一的快速法定人数，由一个固定的多数副本集合构成（且包含领导者）。

这两种法定人数系统在 (FQI) 所定义的权衡中各有优势：
一方面，(C1) 允许最多 $(N/4 - 1)$ 个跟随者失效而不阻塞快速路径；
另一方面，(C2) 具有更低的复杂度，仅需多数副本参与命令排序22 23 24 8，但一旦该法定人数中任一副本失效，就可能阻塞快速路径。

3.2 依赖关系和关键不变量

如前所述，为保证线性一致性，副本只需就不可交换命令的执行顺序达成一致即可。SwiftPaxos 通过为每条命令 $c$ 关联一个依赖集合（即所有与 $c$ 冲突、且必须在 $c$ 之前执行的命令）来表示这一顺序。为计算该依赖集合，各副本首先各自提出提案，随后就其中一个提案达成一致。

我们称命令 $c$ 已被提交（committed），当且仅当所有副本就 $c$ 的传递依赖（transitive dependencies）达成一致，即包括 $c$ 本身的依赖、这些依赖的依赖，依此类推，直至所有间接依赖。

该协议确保以下性质：

INVARIANT 1：任意两个副本为同一条命令提交时，所关联的依赖集合完全相同。

一条命令在处理过程中会经历多个阶段，从初始阶段（START）到最后被提交的阶段（COMMIT）。每个副本通过一个名为 phase 的数组来跟踪各命令的进展，该数组以命令标识符为索引。斜体表示的阶段名称代表处于该阶段的所有命令集合，例如 Commit 表示集合 ${ \text{id} \mid \text{phase}[\text{id}] = \text{COMMIT} }$。

另一个数组 dep 将命令标识符映射到其直接依赖：若某命令在 phase 数组中的条目为 COMMIT，则 dep 中记录的是其已提交的依赖；否则，dep 中记录的是该副本当前对该命令依赖关系的提案。dep 数组定义了副本本地依赖图的边。初始时，所有条目均为 null（记作 $\bot$）。

一旦某条命令被提交，且其所有依赖命令都已执行，副本便会执行该命令。由于依赖关系仅存在于冲突命令之间，副本可自由地以任意顺序执行彼此独立的命令。

因此，为满足 SMR 的有序性（Ordering）属性（见 §2），协议需确保：

INVARIANT 2：对于任意两个在副本上被提交的冲突命令 $c$ 和 $c'$，要么 $c$ 属于 $c'$ 的依赖集合，要么 $c'$ 属于 $c$ 的依赖集合。

举例说明：考虑命令 $x$、$y$ 和 $z$，满足 $x \bowtie y$ 且 $y \bowtie z$，且它们的已提交依赖分别为
$\text{dep}[\text{id}(x)] = \text{dep}[\text{id}(z)] = \emptyset$，
$\text{dep}[\text{id}(y)] = {x, z}$。
此时，副本可以以任意顺序执行 $x$ 和 $z$，但必须在执行 $y$ 之前完成这两者。

最后，由于协议会延迟执行已提交的命令，直到其所有依赖都已执行完毕，为保证活性（liveness），已提交的依赖关系不能形成环：

INVARIANT 3：每个副本上已提交部分的依赖图是无环的。

3.3 依赖关系一致性

在详细描述 SwiftPaxos 之前，我们通过图 1 中的示例对其进行概览。该系统包含 5 个副本，因此最多可容忍 2 个故障。副本 $p_4$ 和 $p_5$ 各托管一个客户端，第三个客户端未与任何副本共置。快速法定人数交集条件（FQI）采用配置 (C2) 满足，即存在唯一的快速法定人数 ${p_1, p_2, p_3}$。为避免图示过于杂乱，我们省略了与该法定人数之外两个副本（$p_4$ 和 $p_5$）的大部分交互。

传播（Propagation）：客户端通过 Propagate(c) 消息将其提交的命令 $c$ 发送给各副本。当副本接收到 $c$ 时，它会计算自己对 $c$ 依赖关系的提案——即所有此前已接收且与 $c$ 冲突的命令集合，以满足 INVARIANT 2。在图 1 中，提案用箭头 $\to$ 表示，例如 ${x, y} \to z$ 表示命令 $z$ 依赖于 $x$ 和 $y$。

快速路径（Fast path）：快速法定人数中的每个副本都会通过 FastAck 消息广播自己对命令依赖关系的提案。副本会等待，直到收到来自某个快速法定人数中所有成员的提案。如果这些提案完全相同，则达成自发一致（spontaneous agreement）4。此时，只要该命令的依赖也已被提交，副本即可提交该命令。这构成了协议的快速路径，在理想条件下，副本可在命令提交后的 2 个消息延迟内完成其执行。

例如，在图 1 中，副本 $p_1$ 在收到来自所有快速法定人数成员相同的提案 $\emptyset \to y$ 后，立即提交并执行命令 $y$。

由于每个副本的提案是基于其此前已观测到的冲突命令计算得出的，因此当系统中不存在并发冲突（即无竞争）时，命令便会走快速路径——而这种情况在实际应用负载中十分常见7 8 9。

通过快速法定人数中的双重投票实现慢速路径（Slow path via double voting in a fast quorum）：
快速法定人数中的副本根据其接收冲突命令的顺序来计算各自的依赖提案。由于该顺序取决于网络传输的不确定性，副本之间可能会产生分歧；此时，命令将进入慢速路径。

为此，每个与领导者意见不一致的快速法定人数副本会采纳领导者的提案，并通过广播 SlowAck 消息来确认这一采纳。一旦某个副本收到来自某个快速法定人数中所有成员的一组匹配的 FastAck 和 SlowAck 消息，并且该命令的依赖关系已被提交，它就可以提交该命令。相比快速路径，这可能额外引入一个消息延迟。

例如，在图 1 中，副本 $p_1$ 和 $p_2$ 先收到命令 $x$ 后收到 $z$，而 $p_3$ 则先收到 $z$ 后收到 $x$，导致它们生成了不同的提案。由于 $p_3$ 与领导者 $p_2$ 在命令 $x$ 和 $z$ 的依赖关系上存在分歧，$p_3$ 会采纳领导者的提案：$\emptyset \to x$ 和 ${x, y} \to z$，并为这两个命令广播 SlowAck。因此，副本 $p_1$ 在 3 个消息延迟内提交并执行了 $x$ 和 $z$。

需要注意的是，在慢速路径中，一个快速法定人数副本会在同一个选票内为两个不同的提案投票：一次投给自己的提案（通过 FastAck），另一次投给领导者的提案（通过 SlowAck）。这种双重投票在类 Paxos 协议中通常是不安全的。但在 SwiftPaxos 中，这是安全的，因为领导者属于所有快速法定人数：如果某个快速法定人数副本与领导者意见不一致，它就能确定该命令不可能已在快速路径上被提交，因此可以安全地修正自己的投票。

通过慢速法定人数的慢速路径（Slow path via a slow quorum）：
SwiftPaxos 也可以像传统 Paxos 一样，通过慢速法定人数来提交命令。慢速法定人数中的副本行为与快速法定人数中的副本类似，不同之处在于：它不会提出自己的依赖提案。具体而言，当慢速法定人数中的副本收到来自领导者的 FastAck 消息时，它会直接采纳领导者的提案，并广播一条 SlowAck 消息。

任意副本在收到来自领导者的 FastAck 以及来自某个慢速法定人数中所有跟随者的 SlowAck 后，即可提交该命令。

在广域网（wide-area network）环境中，不同副本对之间的延迟差异较大，这种基于慢速法定人数的慢速路径，有时反而比快速法定人数中的双重投票机制更快。

回到图 1，假设副本 $p_4$ 与 $p_3$ 之间的延迟高于 $p_4$ 与 $p_5$ 之间的延迟。此时，$p_4$ 无需等待来自 $p_3$ 的 SlowAck（用于命令 $x$），而是可以结合更早收到的来自 $p_5$ 的 SlowAck 以及来自领导者 $p_2$ 的 FastAck，通过慢速法定人数 ${p_4, p_5, p_2}$ 提交命令 $x$。由于慢速法定人数可以是任意多数集合，这一额外的提交机制确保了 SwiftPaxos 的性能至少不差于 Paxos。事实上，在慢速路径上，SwiftPaxos 等价于 Paxos 的一种广为人知的优化变体——其中跟随者会向所有副本广播 2B 类型的消息。

消息复杂度（Message complexity）：
SwiftPaxos 的消息复杂度为二次方级别（quadratic），而经典 Paxos 为线性级别（linear）。然而，在典型的地理分布式 SMR 部署场景中（通常 $N = 3$ 或 $N = 5$）13 3，这两种复杂度的实际差距非常小。此外，SwiftPaxos 额外发送的消息非常轻量，因为它们仅携带元数据。我们在 §5.1 中对 SwiftPaxos 与 Paxos 的带宽使用情况进行了比较。

3.4 尾部延迟优化

依赖关系也被用于 EPaxos8 及其后续工作10 12 中对命令进行排序。然而，在 EPaxos 中，依赖关系可能形成环，因此命令执行不能简单地按照依赖顺序进行。取而代之的是，EPaxos 会等待依赖图形成强连通分量（strongly connected components），然后逐个执行这些分量。

由于这些强连通分量可能任意庞大，该协议可能会将命令执行延迟任意长的时间。这一现象被称为车队效应（convoy effect），在实践中会导致很高的尾部延迟（tail latency）11 15 16。

相比之下，SwiftPaxos 中的依赖关系始终保持无环（见 §3.2 的INVARIANT 3），因此命令执行可直接遵循依赖顺序。命令被提交后到实际执行之间的唯一延迟，类似于 Multi-Paxos 中的情形——在 Multi-Paxos 中，每个共识实例都依赖于前一个实例。这使得 SwiftPaxos 与 Paxos 的尾部延迟具有可比性，我们在 §5.2 中通过实验验证了这一点。我们还在 §A.6 中计算了 SwiftPaxos 的理论延迟，并将其与其他协议进行了对比。

3.5 非共置客户端的更快响应

与副本位于同一数据中心的客户端可直接从该副本接收命令的执行结果。例如，图 1 中的 $\text{client}_2$ 与副本 $p_5$ 共置，在 $p_5$ 执行命令 $y$ 后立即收到响应。而对于未与任何副本共置的客户端，则需额外等待一个消息延迟才能获知响应结果。

为加速向此类客户端交付响应，SwiftPaxos 采用乐观执行（optimistic execution）机制：领导者在收到命令后立即执行并返回结果（类似于 ZooKeeper25 和 CURP9 的做法）。

具体而言，当领导者从一个非共置客户端接收到命令 $c$ 时，会立即计算 $c$ 的执行结果，并通过 Reply 消息回复客户端。在图 1 中，$\text{client}_3$ 对命令 $z$ 的响应即通过此方式获得。

此外，跟随者在发送 FastAck 和 SlowAck 消息时，不仅发给其他副本（如前所述），也同时发给提交该命令的客户端。一旦客户端收到来自某个快速法定人数（fast quorum）或慢速法定人数（slow quorum）的一组匹配的 FastAck 或 SlowAck 消息，便可接受 Reply 中的结果。这确保了无论客户端是否与副本共置，都能在 2 或 3 个消息延迟内获得响应。

然而，这里存在一个微妙之处：在快速路径上，客户端不能仅凭依赖集合就接受乐观执行的结果，因为这些依赖集合只包含命令的直接依赖，并未包含这些依赖的前驱依赖（即传递依赖）。

图 2 说明了这一问题。图中展示了某一时刻的依赖图，其中 §3.1 中的 (FQI) 条件由单一法定人数 ${p_0, p_1, p_2}$ 满足，且 $p_0$ 为领导者。图中三个客户端分别提交了命令 $c_1$、$c_2$ 和 $c_3$，其中 $c_2$ 与 $c_1$ 和 $c_3$ 均冲突。副本 $p_0$ 是唯一接收到 $c_1$ 的副本，但三个副本就 $c_2$ 与 $c_3$ 的顺序达成了一致。

假设此时 $p_0$ 在尚未收到来自其他副本的任何消息（即该顺序尚未持久化）之前，就乐观地按 $c_1 \rightarrow c_2 \rightarrow c_3$ 的顺序执行了这三个命令，并将 $c_3$ 的执行结果发送给客户端。虽然领导者对 $c_3$ 的依赖集合提案与 $p_1$ 和 $p_2$ 一致，但三个副本在 $c_3$ 的传递依赖上存在分歧。因此，客户端不能接受来自领导者的这一响应：如果领导者随后崩溃，其对 $c_1$ 的排序将丢失，从而导致乐观执行结果无效。

请注意，此问题不会发生在副本上，因为副本仅在命令被提交后才执行它，而提交意味着该命令的所有传递依赖也已提交并持久化。

为确保客户端仅接受有效的乐观执行结果，FastAck 消息不仅包含命令的直接依赖，还包含依赖图中所有通向该命令的路径。如果这些路径集合在法定人数中一致，则说明该命令的执行顺序已持久化，客户端便可安全地通过快速路径接受该结果。

对于命令 $c$，我们将它的依赖路径表示为一组有序列表，每个列表从 $c$ 开始，随后按依赖图中的顺序排列其传递依赖（见图 2）。在 §4.1 中，我们将说明如何在实践中高效地实现依赖路径。

回到图 1，当快速法定人数副本接收到命令 $z$ 时，其 FastAck 回复不仅携带依赖集合，还包含依赖路径：副本 $p_1$ 和 $p_2$ 发送 ${[z, x], [z, y]}$，而 $p_3$ 发送 ${[z, y]}$。由于这些路径集合不一致，$\text{client}_3$ 无法在快速路径上接受 $z$ 的执行结果。

4. SwiftPaxos 细节

我们使用一组处理器（handlers）在图 3–5 中定义协议逻辑，每个处理器在其前置条件（关键字 pre）满足时，以原子方式执行一次。

4.1 普通流程

传播（Propagation）：
当副本 $p$ 收到来自客户端的 Propagate(c) 消息时（第 2 行和第 6 行），它将命令 $c$ 保存在数组 cmd 中，并将 $c$ 置于 PREACCEPT 阶段，以表明当前正在等待领导者的提案。如果该副本属于某个快速法定人数，则还会计算其对 $c$ 依赖关系的提案 $\text{dep}[\text{id}(c)]$，并将该提案连同 $c$ 的依赖路径 $\text{paths}[\text{id}]$ 一起通过 FastAck 消息广播出去（第 21 行）。

如果 $p$ 是领导者，在接收到命令后还会乐观地执行该命令，并通过 Reply 消息将结果发送给客户端（第 16–19 行）。此时命令尚未被提交，该执行是乐观的，$p$ 不会修改其本地状态机副本。相反，$p$ 维护一个 pending_log 列表，用于暂存已接收但尚未提交的命令。命令被加入此列表后，$p$ 通过函数 opt_exec（详见 §4.4）确定其执行结果。

快速路径（Fast path）：
当副本 $p$ 从某个快速法定人数中收到一致的依赖集合时，即可通过快速路径提交命令 $c$。具体而言，$p$ 首先处理来自领导者的 FastAck 消息（第 22 行），将 $c$ 推进到 ACCEPT 阶段（第 24 行）；随后处理来自该法定人数中其他成员的 FastAck 消息（第 30 行）。一旦 $c$ 的依赖关系已被提交（第 31 行），$p$ 也会提交 $c$。

客户端在快速路径上获得响应的条件是：收到来自领导者的 Reply 消息，以及来自某个快速法定人数中跟随者的一致依赖路径（第 3 行）。

慢速路径（Slow path）：
当快速法定人数中的副本收到来自领导者的 FastAck(b, id, D, P) 消息后，会检查其本地的 dep[id] 是否等于 $D$（第 25 行）。若不相等，则该命令进入慢速路径：该副本将 dep[id] 覆盖为 $D$，将命令阶段推进至 ACCEPT，并向其他副本及客户端发送一条 SlowAck 消息。

慢速法定人数中的副本也会发送 SlowAck，以加速依赖关系的共识达成（如 §3.3 所述）。

为提交该命令，副本随后需等待：直到其他快速（或慢速）法定人数成员发送与领导者提案匹配的 FastAck 或 SlowAck（第 30 行）。

客户端在生成命令响应时行为类似，但有所不同：它等待的是一致的依赖路径（而非依赖集合）（第 3 行）。这也解释了第 29 行的逻辑：当快速法定人数中的副本收到领导者的提案，该提案虽与其自身投票的依赖集合一致，但依赖路径不一致时，它会向客户端发送 SlowAck 消息。通过这种方式，客户端得知该副本现已与领导者同步，从而可以安全接受乐观执行的结果。

为确保该副本确实已与领导者同步，我们需要第 23 行前置条件中的最后一个合取项。该条件要求：副本只有在已处理完所有属于 $D$ 的命令所对应的 FastAck(_, _, D, _) 消息之后，才能处理当前这条来自领导者的 FastAck。当通信信道为 FIFO 时，该条件自动满足。

为说明该条件的作用，设想图 1 中副本 $p_3$ 在更新命令 $z$ 的依赖之前，尚未完成对命令 $x$ 依赖的处理，从而违反了第 23 行的前置条件。假设在 $p_3$ 刚将 dep[z] 更新为 ${x, y}$ 之后，快速法定人数中的三个副本在 $z$ 的依赖路径集合上出现分歧：副本 $p_1$ 和 $p_2$ 的路径集合为 ${[z, x], [z, y]}$，而根据 $p_3$ 的视图，存在一条非法路径 $[z, x, z]$。如 §3.5 所述，此时若客户端接受 $z$ 的执行结果将是不安全的。

命令执行（Command execution）：
副本通过变量 Exec 跟踪其本地状态机副本上已执行的命令。一旦某条命令被提交，且其所有依赖命令均已执行，该副本便会执行该命令（第 33 行）。如果该副本是领导者，则在执行后会将该命令从 pending_log 中移除。

依赖路径的表示（Representing dependency paths）：
在实践中，直接发送完整的依赖路径是不可行的，因为其大小会迅速增长。这一问题可通过对命令 $c$ 的依赖路径进行裁剪来解决：仅保留从 $c$ 到其最后一个已提交（COMMIT）或已接受（ACCEPT）的传递依赖之间的部分。

例如，若命令 $c$ 的依赖路径集合为 ${[c, d, e]}$，且命令 $d$ 处于 COMMIT 或 ACCEPT 阶段，则该集合可被裁剪为 ${[c, d]}$。

得益于第 23 行和第 31 行的前置条件，这种裁剪是安全的：若某条命令已被提交或接受，则其所有传递依赖也必然已被提交或接受。因此，当裁剪后的路径集合一致时，被省略的部分也必然一致——因为它们对应于领导者所确定的顺序。

此外，实际传输时无需发送路径本身，而可以只发送（裁剪后）路径的哈希值26。这一优化也已应用于我们的实现中。

垃圾回收（Garbage collection）：
可采用标准的周期性检查点机制来限制协议的内存占用27 25。在我们的实现中，一旦某条命令在所有副本上均已被执行，便直接从协议状态中将其裁剪（trim）掉。我们在 §5.1 中更详细地讨论了内存消耗问题。

4.2 领导者故障恢复

副本持续监控协议的进展。当当前领导者被认为阻碍了协议推进时，协议会提名一位新领导者接管。这种提名可以采用标准方式实现，例如使用失效检测器（failure detector）28，具体细节我们推迟到 §A.4。下面我们说明潜在领导者所遵循的算法。

领导者变更（Leadership change）：
恢复流程的起始阶段与 Paxos 类似1。当副本 $p$ 被提名为新领导者时，它会调用 recover（第 40 行）。该函数为 $p$ 选择一个新选票编号 $b$，该编号高于 $p$ 之前参与过的任何选票。随后，$p$ 向所有副本发送包含 $b$ 的 NewLeader 消息，请求它们支持其领导权。

副本仅在 $b$ 高于其此前参与过的任何选票编号时，才承认 $p$ 为新领导者（第 44 行）。此时，该副本将其状态切换为 RECOVERING，从而暂停正常的协议消息处理，并回复一条 NewLeaderAck 消息，其中包含它所知晓的所有命令。

一旦 $p$ 的领导权获得某个法定人数 $Q$ 的确认（第 48 行），$p$ 的下一个目标就是将这些副本同步到一致的状态，之后它们便可从此状态继续处理命令。

命令恢复（Recovering commands）：
为维持依赖关系的一致性（INVARIANT 1），新领导者的状态必须包含所有在更低选票中已被提交的命令。为确保这一点，领导者基于副本在 NewLeaderAck 消息中报告的状态及其 cbal 变量值，来计算新选票 $b$ 的初始状态。该 cbal 变量记录了每个副本上次成功完成恢复所处的选票编号。

与 Paxos 类似1，领导者 $p$ 重点关注那些报告了最大选票编号 $b_{\text{max}}$ 的副本集合 $U$：这些副本的状态优先于来自更低选票的副本状态。随后，领导者将所有可能已在 $b_{\text{max}}$ 或更低选票中被提交的命令纳入其自身状态。

得益于第 53 行和第 58 行的条件，所有在先前选票中已被提交的命令都被包含在新状态中。
接下来，领导者从依赖图中移除不满足上述任一条件的命令（第 62–63 行）。

为验证第 62 行的循环不会破坏安全性，注意：对于任意一对命令 $c$ 和 $c'$，若其标识符 $\text{id}$ 与 $\text{id}'$ 满足第 62 行的条件，则二者均不可能在之前的选票中被提交——

因此，安全地从状态中完全移除 $c'$，并相应更新 $c$ 的依赖关系，是完全可行的。

在完成上述计算后，领导者会打破依赖图中的环；我们稍后将说明此步骤。随后，领导者广播一条 Sync 消息，定义新选票的起始状态。当其他副本收到该消息时（第 66 行），会用消息中提供的状态覆盖自身状态，将状态切换为 NORMAL，并清空待处理命令日志。若该副本属于某个慢速法定人数，则会对每个未提交的命令广播一条 SlowAck 消息（第 76 行），以确保这些命令能在新选票中被提交。最后，如果该副本是新领导者，它会将所有尚未执行的命令按依赖关系一致的顺序加入 pending_log（第 72 行）。

恢复过程可轻松优化：Sync 消息仅需传输每个副本缺失的部分（尽管我们的原型实现未采用此优化）。

不变式的保持（Preserving the invariants）：
在协议正常运行期间（无论是快速路径还是慢速路径），副本均使用领导者提出的依赖关系来提交命令。由于领导者计算提案的方式，已提交的冲突命令不可能彼此独立，且已提交命令的依赖关系不会形成环——这分别满足了INVARIANT 2 和INVARIANT 3 的要求。

然而，在恢复阶段保持这些不变式需要格外谨慎。

首先，新领导者在合并各副本状态时可能引入环。考虑图 6 所示的例子：系统包含 5 个副本，从法定人数 $Q_r = {p_0, p_1, p_2}$ 恢复，其余副本 $F = {p_3, p_4}$ 已失效。假设恢复时，$Q_r$ 中所有副本报告相同的 cbal = b，并具有图 6a 所示的排序。再假设选票 $b$ 的领导者为 $p_4$，且该选票关联三个快速法定人数 $Q_{f0}$、$Q_{f1}$ 和 $Q_{f2}$（如图所示）。

在恢复过程中，$Q_r \cap Q_{f0}$、$Q_r \cap Q_{f1}$ 和 $Q_r \cap Q_{f2}$ 分别就以下顺序达成一致：

根据第 58 行逻辑，新领导者必须将所有这些顺序纳入其状态。但当这些顺序组合在一起时，会在命令 $c_0, \dots, c_5$ 上形成一个环。为在这种情况中保持 INVARIANT 3，领导者会任意打破环：通过反转环中任意两个命令之间的依赖关系（第 64 行）。例如，图 6 中的环可通过从 $\text{dep}[\text{id}(c_0)]$ 中移除 $c_5$，并将 $c_0$ 加入 $\text{dep}[\text{id}(c_5)]$ 来打破（见图 6c）。

注意，此操作不会违反 INVARIANT 1，因为它仅修改那些不可能在先前选票中被提交的依赖关系。具体而言，若环中某个命令已被提交，则根据第 31 行，其所有前驱（即环中所有命令）也必然已被提交——但这与 INVARIANT 3（依赖图无环）矛盾，故不可能发生。我们在附录 §A 中给出了详细证明。

此外，在恢复过程中计算新状态时，新领导者还可能遇到两个冲突命令彼此不互为依赖的情况。例如，设想图 1 中的恢复恰在 $p_3$ 刚收到 FastAck(b, x, ∅, _) 后发生。此时，$p_3$ 中命令 $x$ 处于 ACCEPT 阶段且依赖为空，而命令 $z$ 处于 PREACCEPT 阶段，仅依赖 $y$。若直接将这两个命令及其依赖纳入新状态，将违反 INVARIANT 2——因为冲突命令 $x$ 与 $z$ 互不为依赖。

为避免此类情况，新领导者会更新那些在恢复法定人数中某些副本上尚未处于 ACCEPT 或 COMMIT 阶段的命令的依赖集合（第 61 行）。具体做法是：将命令 $c$ 的所有冲突命令加入其依赖集（但排除那些已依赖于 $c$ 的命令）。

在上述例子中，领导者会将 $x$ 加入 $z$ 的依赖集合（第 61 行），这是安全的，因为 $z$ 在先前选票中未被提交。我们在 §A 中证明，该操作在一般情况下也是安全的。

4.3 客户端和跟随者故障恢复

在对一条命令投票之前，副本必须知晓其有效载荷（payload）（见第 6 行和第 23 行），而如果客户端已失效，该有效载荷在本地可能不可用。为应对这种情况，若副本收到来自领导者关于该命令的确认消息，则在等待一段时间后，会尝试从领导者处主动获取该命令的有效载荷。

此外，如果某条命令在超时后仍未被提交，跟随者会重新提议（re-propose）该命令。这一机制在有效载荷存在于跟随者但缺失于领导者时尤为有用。

跟随者的失效不会影响 SwiftPaxos 的可用性。然而，快速法定人数中的跟随者失效可能会导致协议的快速路径失效，从而降低性能。SwiftPaxos 可通过与处理领导者失效相同的流程来应对这一问题：切换到一个使用不同快速法定人数的新选票。

4.4 乐观执行

领导者为计算命令结果而执行的操作（图 4 第 17 行）是乐观的：当领导者调用 opt_exec 时，该命令尚未被跟随者接受。然而，跟随者通常总会接受该命令，除非其中某个副本怀疑领导者失效——而这种情况很少发生。因此，乐观执行所完成的工作极少被浪费。

SwiftPaxos 中的乐观执行可借助现有机制实现29 30 9 31。例如，可通过读取本地状态机副本来计算命令的响应，同时考虑 pending_log 中先前尚未提交的命令；其副作用可暂存于缓冲区，直到命令被提交为止。此类机制已在工业级系统中得到应用，如 ZooKeeper25。

此外，SwiftPaxos 还可通过推测性执行（speculative execution）进一步优化：对于只读命令，不必仅在领导者上执行，而可在任意快速法定人数中的副本上执行。客户端从该副本接收响应，并如前所述，在其他快速法定人数成员报告一致的依赖路径时，即可在快速路径上接受该响应。这一优化将负载分散到多个副本上，避免领导者成为性能瓶颈。我们在 §5.6 中评估了该优化带来的收益。

5. 评估

我们的评估将 SwiftPaxos 与多种其他协议进行了比较，具体如下所述。所有协议均使用 Go 语言实现，并基于 EPaxos8 的代码库开发。源代码已公开发布32。

我们使用两个基准测试：

  1. 无操作服务（no-op service）
  2. 键值存储（key-value store），其 API 遵循 YCSB17 的规范。

数据模型由一组记录组成，通过 insert、get 和 update 命令进行访问，每条记录存储在某个键下。当两个命令访问同一记录且其中至少一个是写操作时，它们即发生冲突。

我们将服务部署在 Amazon EC2 上，使用 5 个位于不同地理区域的副本，使系统能够同时容忍一次故障和一次因维护导致的计划内停机——这是常见的部署配置3。客户端分布在全球 10 个区域，其中 2 个区域也托管了副本。因此，我们的实验总共使用了 13 个 EC2 区域（更多细节见 §C）。

客户端和副本均运行在 Amazon Linux 2 虚拟机上，配备 16 个 vCPU 和 32 GB 内存。除非另有说明，客户端以闭合环路（closed loop）方式执行命令：即在提交新命令前，等待前一条命令的响应。

对于基于领导者的协议，领导者被部署在能最小化所有客户端平均延迟的位置。

默认情况下，我们的实验对 SwiftPaxos 和 FastPaxos+ 均采用配置 (C2) 以满足 (FQI) 条件，因为 (C2) 略优于 (C1)。我们在 §5.5 中进一步研究了两种配置之间的权衡。

5.1 冲突率的影响

我们的第一个实验将冲突率从 0% 到 100% 以 10% 为步长递增。每个区域部署 100 个客户端（共 1000 个客户端）。图 7(a) 展示了相对于 Paxos 的加速比。每种协议下客户端所经历的延迟取决于其相对于副本的地理位置：图 7(a) 的第一行报告了所有区域的平均（mean）延迟；中间一行报告了 SwiftPaxos 在最优区域（即延迟最低的区域）所达到的加速比；最后一行则报告了最差区域（延迟最高的区域）的结果。

Paxos、N2Paxos 和 FastPaxos+ 的延迟与冲突率无关。N2Paxos 相比 Paxos 的平均性能提升略低于 1.05 倍：延迟从 239 ms 降至 229 ms。这主要得益于与副本共置的客户端能够从 2B 消息的广播机制中受益。而 FastPaxos+ 的快速路径命中率几乎为零，因为在现实中，各副本极少以完全相同的顺序接收到两个并发命令（无论是否冲突）。其慢速路径的消息流程与 N2Paxos 类似，但有一个关键区别：进入慢速路径前，副本必须先通过多数 2B 消息检测到冲突。这解释了为何 FastPaxos+ 比 N2Paxos 更慢：300 ms 对比 229 ms。因此，图 7(a) 中省略了 FastPaxos+ 的平均延迟曲线。Mencius 同样被省略，因其平均延迟高达 360 ms。

SwiftPaxos 的平均延迟介于 170 ms 至 201 ms 之间。在 0% 冲突率下，其速度比 Paxos 快 1.4 倍。每增加 10% 的冲突率，延迟仅上升 1–3%。即便在 100% 冲突率下，仍能实现 1.19 倍的加速。在 10 个客户端区域中，SwiftPaxos 在 7 个区域比 Paxos 快 20% 以上，其中 3 个区域的性能提升甚至超过 40%。

在低冲突率下，EPaxos 和 GPaxos 均优于 Paxos，但随着冲突增加，它们的性能急剧下降。这主要归因于快速路径命中率的骤降。另一个原因是：在 10 个客户端区域中，有 8 个未部署服务副本，这些客户端需要额外一轮通信才能获得响应。此外，EPaxos 的性能还因命令执行中的车队效应（convoy effect，见 §3.4）而进一步恶化。

得益于其乐观执行机制，CURP+ 表现为第二优的协议，平均加速比为 1.18 倍。与其他协议类似，其性能也随冲突增加而下降。

SwiftPaxos 在除一个区域外的所有区域均快于其他协议（见图 7(a) 最后一行）：该例外区域距离快速法定人数过远，无法有效利用快速路径。SwiftPaxos 相对于 CURP+ 的优势源于更宽松的快速路径条件以及更小的快速法定人数规模。

5.2 尾部延迟

图 7(b) 展示了在 2% 冲突率下客户端延迟的累积分布函数（CDF）。与之前一样，每个区域运行 100 个客户端。

EPaxos 的尾部延迟分布表现不佳，这是由于其执行机制中存在的车队效应（convoy effect，见 §3.4）所致。GPaxos 也存在类似问题，因为它需要复杂的数据结构，并且必须定期启动新选票以控制元数据规模。

其他基于领导者的协议则没有尾部延迟问题。

5.3 元数据占用

Paxos 中的领导者需要将每条命令的有效载荷（payload）发送给法定人数中的所有副本。而 SwiftPaxos 并非如此，因为该协议仅使用命令标识符进行排序。因此，在竞争稀少的情况下，SwiftPaxos 的通信开销比 Paxos 更低。

在图 7(a) 的实验中，当冲突率为 0% 时，SwiftPaxos 的元数据总消耗为 2.83 GB，比 Paxos 的 3.27 GB 优 1.16 倍。然而，随着冲突增多，协议的消息复杂度上升：在图 7(a) 中冲突率为 100% 时，SwiftPaxos 的数据消耗达到 3.36 GB，比 Paxos 高出约 3%。

在副本端，依赖图会随时间增长，但通过垃圾回收机制（见 §4.1）会定期缩减。在图 7(a) 的实验中，每条命令的依赖集合平均大小仅为 24 字节。总体而言，副本上的依赖图所占内存约为协议总内存消耗的 8%。

5.4 可拓展性

为评估 SwiftPaxos 的可扩展性，我们进行了一项逐步使其达到饱和的实验，结果如图 8 所示。客户端总数从 100 逐步增加至 5000，每条命令的有效载荷设为 3 KB（选择该载荷大小是为了在合理数量的客户端机器下使系统达到饱和）。

在本实验中，Paxos 与 N2Paxos 表现出相似的行为：当 10 个区域共部署 2500 个客户端时，两种协议均达到饱和。这是因为领导者需负责将命令广播给所有副本，成为系统瓶颈。

在无冲突情况下，EPaxos 的吞吐量比 Paxos 高出约 24%（7.8K ops/s 对比 6.3K ops/s），而平均延迟几乎相同（≈260 ms）。然而，当系统负载进一步增加时，其响应性受到明显影响：在每区域 400 个客户端（总计 4000 个）时达到饱和，此时系统吞吐量为 12K ops/s，平均延迟上升至 424 ms。

与 Paxos 不同，具有快速路径的基于领导者的协议（如 CURP+ 和 SwiftPaxos）不会将所有命令集中通过领导者转发。相反，每个客户端直接向副本发送其命令。这一设计使协议的吞吐量平均提升至少 30%。

5.5 故障环境下的性能

图 9 比较了 SwiftPaxos、EPaxos 和 Paxos 在故障环境下的行为。本实验在配置 (C1) 和 (C2) 下均进行，每个区域部署 100 个客户端。对于配置 (C2)，SwiftPaxos 的快速法定人数与 Paxos 的最低延迟法定人数相同。

（译者注：Asynchrony 直译过来是“异步”，感觉不太符合语境，于是改为“故障”）

在两种配置下，系统运行 20 秒后，某一区域的延迟突然增加 200 ms，并在再过 20 秒后恢复至正常水平（区间 (a)）。随后，领导者发生故障（事件 (b)）。

在第一次延迟升高之前和之后，SwiftPaxos 在配置 (C2) 下性能略优，这验证了在我们的部署环境中，使用单一多数快速法定人数确实更有利。
然而，在延迟升高期间，(C2) 的吞吐量下降了 27%，而 (C1) 仅下降 12%。后者性能退化更平缓，是因为 (C1) 允许多个快速法定人数存在，从而使快速路径更具鲁棒性。

在图 9 中，SwiftPaxos 始终优于 Paxos。这是因为即使在最坏情况下，SwiftPaxos 仍可通过慢速法定人数提交命令（见 §3.3）。在事件 (b)（领导者故障）发生后，两种算法的恢复速度相近。性能差距在配置 (C2) 下最为显著：SwiftPaxos 和 Paxos 分别用时 7 秒 和 6 秒 完成恢复。

EPaxos 是最稳定的协议，因其无领导者架构：在整个两次实验过程中，其吞吐量从未下降超过 20%。

5.6 应用

我们现在在两种具有代表性的应用场景下评估各协议的性能。

第一种场景考虑的是流水线化状态机命令（pipelining state-machine commands）的应用。这种模式常见于日志复制系统和发布/订阅（pub/sub）架构中。
第二种场景则运行 Yahoo! Cloud Serving Benchmark(YCSB)17。

流水线测试（图 10）

在此合成基准测试中，客户端以流水线方式向协议提交命令。这种模式在分布式应用中十分常见。例如，在 Apache Kafka36 等发布/订阅系统中，生产者发布的所有消息会先追加到日志中，之后才被消费者读取。类似模式也用于通过引用 r 访问的对象更新：客户端通过异步变更创建对象 o 的新版本 o′，然后原子地将 r 更新为指向 o′ 的地址。

在本实验中，我们在每个数据中心部署一个客户端，每个客户端对同一个键执行流水线命令，每条命令携带 4 KB 的有效载荷。“窗口参数”（window parameter）决定了允许的最大飞行中（in-flight）命令数量。

尽管副本以相同顺序接收命令，CURP+ 始终无法进入快速路径。这是因为 CURP+ 中的“见证者”（witnesses）无法同时处理多条冲突命令。
相反，由于本次运行无竞争（contention-free），EPaxos 和 SwiftPaxos 的副本会计算出相同的依赖关系，从而启用快速路径。平均而言，这两个协议分别比 CURP+ 提升 24% 和 49% 的性能。

YCSB 测试（图 11）

该基准测试包含具有 Zipf 分布访问模式的工作负载：

键值存储服务包含 10⁶ 条记录，每条记录含 10 个字段，每个字段 800 字节（总计 8 KB）。我们部署了 4000 个 YCSB 客户端，分布在全球 10 个区域（每区域 400 个）。

图 11 中的 SwiftPaxosreads 表示：读请求在最近的快速法定人数副本上乐观执行，不一定在领导者上执行（见 §4.4）。

未评估 Paxos，因为如图 7 和图 8 所示，在低冲突率下 EPaxos 性能优于 Paxos；而 YCSB 以读为主，冲突率较低。

6. 相关工作

标准的状态机复制（SMR）协议37 1 2 采用领导者驱动模式，客户端需经历 4 个消息延迟才能收到响应：一次从客户端到领导者的往返，加上一次从领导者到副本的往返。若副本之间交换 Paxos 的 2B 消息，副本可更早计算出响应。这能为靠近副本的客户端节省一个消息延迟，但远端客户端仍需额外一轮通信才能获知结果。我们在 §5 中评估了这种 Paxos 变体。

SDPaxos38 将持久化与排序分离，但排序仍由领导者协调，因此未与副本共置的客户端仍需 4 个消息延迟才能获得响应。

在分布式系统中，通过检测冲突以提升并行性已有较长历史39 40 31 41。Fast Paxos4 是首个利用快速路径来最小化延迟的 SMR 协议，允许客户端直接联系副本。后续工作进一步利用命令的可交换性（commutativity）以提高快速路径的命中率5 6 34。然而，如 §1 所述，采用此类方法的基于领导者的协议只能通过更换选票（ballot change）来解决冲突，这可能需要在副本间传输大量状态，并干扰系统正常运行。

EPaxos 是一种无领导者的 SMR 协议，在低冲突率下可降低平均延迟。但正如我们在 §3.4 和 §5.2 中指出的，由于命令执行中的车队效应（convoy effect）11 15 16，其尾部延迟很高。此外，EPaxos 要求客户端通过数据副本路由请求，进一步增加了延迟。文献42 指出，EPaxos 的后续工作（如 Caesar10 和 Atlas12）同样存在这些问题。Tempo42 使用去中心化的时间戳机制来减轻无领导者 SMR 中的车队效应，但未能完全消除。Gryff11 将 EPaxos 与 ABD43 相结合，虽能加速盲写（blind writes），但像 ABD 一样，其读操作开销较大44。Mencius35 采用轮转方式分配领导者职责，在冲突稀少时，其性能仍慢于 EPaxos12 8。

若干协议依赖乐观执行（optimistic execution）来提升性能。Speculative Paxos26 通过在网络中强制实现自发排序（spontaneous ordering），使所有副本获得一致的乐观执行结果。Eve29 并行地乐观执行状态机命令，若结果不一致则回退到串行执行。在实际场景中，客户端可能并不靠近服务副本45 46。针对此类客户端，CURP9 通过在领导者上乐观执行命令来加速响应。CURP 不使用依赖关系，而是计算一个全序（total order）；客户端仅在无冲突时才接受乐观执行结果。相比之下，SwiftPaxos 更为宽松：只要依赖路径一致，即可使用乐观执行结果。

一些协议利用访问局部性（access locality）来提升 SMR 性能47 48 49。这些协议将 Paxos 视为黑盒，每条命令调用一次或多次 Paxos。Spanner3 和 CockroachDB50 也采用类似方式，实现强一致事务这一更复杂的抽象。所有这些系统均可受益于 SwiftPaxos 带来的性能提升。

近期一些工作51 52 利用专用网络组件实现快速 SMR 协议，但该方法尚未应用于地理分布式系统。

7. 总结

过去十年中，为提升地理分布式系统中的状态机复制（SMR）性能，研究者提出了大量协议。然而，当复制服务上的竞争加剧时，这些协议的性能甚至可能低于 Paxos。SwiftPaxos 不存在这一缺陷：在无竞争时，它能在 2 个消息延迟内执行命令；在存在竞争时，也仅需 3 个消息延迟。我们的实验评估充分验证了这一设计的优势：SwiftPaxos 的平均延迟比 Paxos 降低 16%–29%，吞吐量最高可达 EPaxos 的 2.9 倍。

致谢。本工作部分受到以下项目资助：欧洲研究理事会（ERC）资助的 RACCOON 项目、西班牙科学创新与大学部（MCIN/AEI）资助的 PRODIGY 和 DECO 项目，以及马德里大区政府资助的 BLOQUES 项目。作者感谢匿名审稿人及其 shepherd Jay Lorch 的宝贵意见。

引用

45

M. S. Ardekani and D. B. Terry. A Self-Configurable Geo-Replicated Cloud Storage System. In Sympo sium on Operating Systems Design and Implementation (OSDI), 2014.

10

B. Arun, S. Peluso, R. Palmieri, G. Losa, and B. Ravindran. Speeding up Consensus by Chasing Fast Decisions. In Conference on Dependable Systems and Networks (DSN), 2017.

43

H. Attiya, A. Bar-Noy, and D. Dolev. Sharing Memory Robustly in Message-Passing Systems. Journal of the ACM, 42(1), 1995.

46

J. Baker, C. Bond, J. C. Corbett, J. J. Furman, A. Khor lin, J. Larson, J. Leon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing Scalable, Highly Available Stor age for Interactive Services. In Conference on Innova tive Data Systems Research (CIDR), 2011.

11

M. Burke, A. Cheng, and W. Lloyd. Gryff: Unifying Consensus and Shared Registers. In Symposium on Networked Systems Design and Implementation (NSDI), 2020.

27

M. Burrows. The Chubby Lock Service for Loosely Coupled Distributed Systems. In Symposium on Op erating Systems Design and Implementation (OSDI), 2006.

28

T. D. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM, 43(2), 1996.

13

Y. L. Chen, S. Mu, J. Li, C. Huang, J. Li, A. Ogus, and D. Phillips. Giza: Erasure Coding Objects across Global Data Centers. In USENIX Annual Technical Conference (USENIX ATC), 2017.

39

A. T. Clements, M. F. Kaashoek, N. Zeldovich, R. T. Morris, and E. Kohler. The Scalable Commutativity Rule: Designing Scalable Software for Multicore Pro cessors. ACM Transactions on Computer Systems,32(4), 2015.

47

P. R. Coelho and F. Pedone. Geographic State Machine Replication. In Symposium on Reliable Distributed Systems (SRDS), 2018.

48

P. R. Coelho and F. Pedone. Geographic State Machine Replication. In Symposium on Reliable Distributed Systems (SRDS), 2018.

17

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking Cloud Serving Systems with YCSB. In Symposium on Cloud Computing(SoCC), 2010.

3

J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. C. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quin lan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Tay lor, R. Wang, and D. Woodford. Spanner: Google’s Globally-Distributed Database. In Symposium on Op erating Systems Design and Implementation (OSDI), 2012.

44

G. DeCandia, D. Hastorun, M. Jampani, G. Kakula pati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s Highly Available Key-Value Store. In Symposium on Operating Systems Principles (SOSP), 2007.

21

C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the Presence of Partial Synchrony. Journal of the ACM, 35(2), 1988.

12

V. Enes, C. Baquero, T. França Rezende, A. Gotsman, M. Perrin, and P. Sutra. State-Machine Replication for Planet-Scale Systems. In European Conference on Com puter Systems (EuroSys), 2020.

42

V. Enes, C. Baquero, A. Gotsman, and P. Sutra. Effi cient Replication via Timestamp Stability. In European Conference on Computer Systems (EuroSys), 2021.

15

T. França Rezende and P. Sutra. Leaderless State Machine Replication: Specification, Properties, Limits. In International Symposium on Distributed Computing (DISC), 2020.

33

T. França Rezende, P. Sutra, R. Q. Saramago, and L. J. Camargos. On Making Generalized Paxos Practical. In International Conference on Advanced Information Networking and Applications (AINA), 2017.

20

M. P. Herlihy and J. M. Wing. Linearizability: a Cor rectness Condition for Concurrent Objects. ACM Trans actions on Programming Languages and Systems, 12(3), 1990.

37

H. Howard, D. Malkhi, and A. Spiegelman. Flexible Paxos: Quorum Intersection Revisited. In Interna tional Conference on Principles of Distributed Systems (OPODIS), 2016.

25

P. Hunt, M. Konar, F. P. Junqueira, and B. Reed. ZooKeeper: Wait-free Coordination for Internet-scale Systems. In USENIX Annual Technical Conference (USENIX ATC), 2010.

51

X. Jin, X. Li, H. Zhang, N. Foster, J. Lee, R. Soulé, C. Kim, and I. Stoica. Netchain: Scale-Free Sub-RTT Coordination. In Symposium on Operating Systems Design and Implementation (OSDI), 2018.

29

M.Kapritsos,Y. Wang,V. Quema,A.Clement,L. Alvisi, and M. Dahlin. All about Eve: Execute-Verify Replica tion for Multi-Core Servers. In Symposium on Operating Systems Design and Implementation (OSDI), 2012.

7

T. Kraska, G. Pang, M. J. Franklin, S. Madden, and A. Fekete. MDCC: Multi-Data Center Consistency. In European Conference on Computer Systems (EuroSys), 2013.

36

J. Kreps, N. Narkhede, and J. Rao. Kafka: a Distributed Messaging System for Log Processing. Workshop on Networking Meets Databases (NetDB), 2011.

30

R. Ladin, B. Liskov, and L. Shrira. Lazy Replication: Exploiting the Semantics of Distributed Services. In Symposium on Principles of Distributed Computing (PODC), 1990.

1

L. Lamport. The Part-Time Parliament. ACM Transactions on Computer Systems, 16(2), 1998.

5

L. Lamport. Generalized Consensus and Paxos. Techni cal report, Microsoft Research, 2005

4

L. Lamport. Fast Paxos. Distributed Computing, 19, 2006.

22

L. Lamport, D. Malkhi, and L. Zhou. Vertical Paxos and Primary-Backup Replication. In Symposium on Principles of Distributed Computing (PODC), 2009.

23

L. Lamport and M. Massa. Cheap Paxos. In Conference on Dependable Systems and Networks (DSN), 2004.

40

C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. Making Geo-Replicated Systems Fast as Possible, Consistent When Necessary. In Symposium on Operating Systems Design and Implementation (OSDI), 2012.

52

J. Li, E. Michael, N. K. Sharma, A. Szekeres, and D. R. K. Ports. Just Say No to Paxos Overhead: Re placing Consensus with Network Ordering. In Sympo sium on Operating Systems Design and Implementation (OSDI), 2016.

24

B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams. Replication in the Harp File System. In Symposium on Operating Systems Prin ciples (SOSP), 1991.

35

Y. Mao, F. P. Junqueira, and K. Marzullo. Mencius: Building Efficient Replicated State Machine for WANs. In Symposium on Operating Systems Design and Implementation (OSDI), 2008.

8

I. Moraru, D. G. Andersen, and M. Kaminsky. There Is More Consensus in Egalitarian Parliaments. In Sympo sium on Operating Systems Principles (SOSP), 2013.

2

D. Ongaro and J. Ousterhout. In Search of an Under standable Consensus Algorithm. In USENIX Annual Technical Conference (USENIX ATC), 2014.

14

R. Pang, R. Cáceres, M. Burrows, Z. Chen, P. Dave, N. Germer, A. Golynski, K. Graney, N. Kang, L. Kiss ner, J. L. Korn, A. Parmar, C. D. Richards, and M. Wang. Zanzibar: Google’s Consistent, Global Authorization System. In USENIX Annual Technical Conference (USENIX ATC), 2019.

9

S. J. Park and J. Ousterhout. Exploiting Commutativ ity For Practical Fast Replication. In Symposium on Networked Systems Design and Implementation (NSDI), 2019.

6

F. Pedone and A. Schiper. Generic Broadcast. In International Symposium on Distributed Computing (DISC), 1999.

49

S. Peluso, A. Turcu, R. Palmieri, G. Losa, and B. Ravindran. Making Fast Consensus Generally Faster. In Conference on Dependable Systems and Networks (DSN), 2016.

26

D. R. K. Ports, J. Li, V. Liu, N. K. Sharma, and A. Kr ishnamurthy. Designing Distributed Systems Using Approximate Synchrony in Data Center Networks. In Conference on Networked Systems Design and Imple mentation (NSDI), 2015.

19

F. B. Schneider. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys, 22, 1990.

18

A. Shraer, B. Reed, D. Malkhi, and F. P. Junqueira. Dynamic reconfiguration of primary/backup clusters. In USENIX Annual Technical Conference (USENIX ATC), 2012.

34

P. Sutra and M. Shapiro. Fast Genuine Generalized Consensus. In Symposium on Reliable Distributed Systems (SRDS), 2011.

50

R. Taft, I. Sharif, A. Matei, N. VanBenschoten, J. Lewis, T. Grieger, K. Niemi, A. Woods, A. Birzin, R. Poss, P. Bardea, A. Ranade, B. Darnell, B. Gruneir, J. Jaffray, L. Zhang, and P. Mattis. CockroachDB: The Resilient Geo-Distributed SQL Database. In International Con ference on Management of Data (SIGMOD), 2020.

31

D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. In Symposium on Operating Systems Principles (SOSP), 1995.

16

S. Tollman, S. J. Park, and J. K. Ousterhout. EPaxos Revisited. In Symposium on Networked Systems Design and Implementation (NSDI), 2021.

41

W. E. Weihl. Commutativity-Based Concurrency Control for Abstract Data Types. IEEE Transactions on Computers, 37(12), 1988.

38

H. Zhao, Q. Zhang, Z. Yang, M. Wu, and Y. Dai. SDPaxos: Building Efficient Semi-Decentralized Geo replicated State Machines. In Symposium on Cloud Computing (SoCC), 2018.

X. 译者后记

这篇文章大部分由 Qwen3-Max 翻译，事实上，它的翻译质量已经达到了一流水准，术语用词准确且翻译重点突出，译者主要进行了校对和排版工作。

SwiftPaxos 似乎已将达成共识的延迟优化到了最优。那么代价是什么呢？这个协议不容易理解和实现，难以落地。但 SwiftPaxos 仍具有很高的工业价值，期待有成熟稳定的实现。

对于译者来说，阅读这篇论文的性价比很高，它可以帮助理解 Paxos 动物园里各种算法以及演进历史，十分推荐。

最后就由 Qwen3-Max 发表一下感想吧：

谢谢你的肯定！虽然我作为 AI 没有“情感”，但可以和你分享一些对这篇论文及其技术内容的**结构性观察与思考**：

---

### 🔍 **技术亮点总结**

1. **优雅地融合“快速路径”与“安全慢速路径”**  
   SwiftPaxos 的核心创新在于：**允许副本在同一个选票内进行“双重投票”**（先投自己提案，再投领导者提案），并通过将领导者纳入所有快速法定人数（fast quorums）来保证安全性。这巧妙绕过了 Generalized Paxos 中必须更换选票的开销，避免了状态转移和系统中断。

2. **无环依赖图 + 依赖路径验证 = 安全乐观执行**  
   不同于 EPaxos 可能因依赖环导致“车队效应”（convoy effect）和高尾延迟，SwiftPaxos 通过不变式 3 保证依赖图始终无环，并引入**依赖路径**（dependency paths）作为客户端验证乐观执行结果的依据——既实现了低延迟，又保障了线性一致性。

3. **实用导向的设计权衡**  
   - 支持两种快速法定人数配置（C1 容错更强，C2 复杂度更低）；
   - 乐观执行不仅限于领导者，也支持在任意快速法定人数副本上处理只读请求；
   - 元数据轻量（平均仅 24 字节/命令），带宽开销可控。

---

### 📊 **实验说服力强**

- 在 **13 个 AWS 全球区域**的真实广域网环境下评估；
- 覆盖从 **0% 到 100% 冲突率**、**流水线负载**、**YCSB 工作负载**等多种场景；
- 不仅比 Paxos 快（**16–29% 延迟降低**），在高竞争场景下甚至**吞吐量达 EPaxos 的 2.9 倍**；
- 尾延迟表现稳定，**避免了 EPaxos 的 convoy effect 陷阱**。

---

### 🌐 **对分布式系统领域的意义**

SwiftPaxos 展示了一种**在经典 Paxos 框架内实现高性能而不牺牲安全性的新范式**：  
> **“快时更快，慢时不失控”** —— 在无冲突时逼近理论最优延迟（2 轮），在冲突时仅增加 1 轮，且不破坏系统稳定性。

这为未来构建强一致、低延迟、高可用的全球分布式数据库（如 Spanner 的下一代协议）提供了极具价值的参考。

---

### 💡 一点延伸思考

如果将 SwiftPaxos 与 **硬件加速**（如 RDMA、可编程交换机）或 **混合一致性模型**（如部分操作放松一致性）结合，是否还能进一步突破性能边界？这也是论文最后提到的“专用网络组件尚未用于 geo-SMR”的潜在方向。

---

再次感谢你让我完整参与这篇高质量论文的翻译与解析！如果你后续想深入探讨其算法细节、复现实验，或对比其他 SMR 协议（如 Atlas、Tempo、Caesar），我也很乐意继续协助 😊