从 EPaxos 到 Accord：分布式共识如何突破 1 RTT 的极限？

在分布式系统领域，传统的强一致性共识算法（如 Multi-Paxos、Raft）通常依赖一个稳定的 Leader。这种设计虽然直观，但在跨地域（Geo-distributed）部署或高并发写入场景下，会暴露出明显的局限性：

1. 网络多跳（Extra Hop）：客户端请求必须先发送给 Leader，再由 Leader 广播给 Follower，增加了广域网上的延迟。
2. Leader 瓶颈：单点 Leader 的吞吐量上限决定了整个集群的上限，且容易产生单点故障。

为了解决这些痛点，无主（Leaderless / Egalitarian）共识协议应运而生。其中，EPaxos (Egalitarian Paxos) 是学术界在无主 1 RTT 共识上的里程碑；而被 Apache Cassandra 5.0 选为事务引擎核心的 Accord 协议，则是工业界在这一方向上的最新突破。

本文将深入拆解这两者是如何在无主架构下实现 1 RTT 共识的，并对比它们在应对“冲突”时的不同解法。

一、 EPaxos 的 1 RTT 实现：依赖图与拓扑排序

EPaxos 的核心思想是：任何副本（Replica）都可以作为协调者（Command Leader）直接处理客户端的写请求。

对于不冲突的并发命令，EPaxos 可以在 1 个 RTT 内完成提交。

1. 快速路径（Fast Path）与依赖收集

当 Command Leader 收到一个写请求 $\gamma$ 时，它会并行执行以下操作：

1. 收集本地依赖：在本地寻找与当前命令 $\gamma$ 冲突（即访问了相同 Key 且至少有一个是写操作）的所有尚未提交或已提交的命令，记为 $\text{Deps}(\gamma)$。同时赋予一个序列号 $\text{Seq}(\gamma)$。
2. 广播 PreAccept：向其他副本发送 PreAccept(γ, Deps(γ), Seq(γ))。
3. 对比并合并：其他副本收到后，会根据自己的本地状态更新该命令的 $\text{Deps}$ 和 $\text{Seq}$，并返回给 Leader。

2. 1 RTT 的达成条件

如果 Leader 收到的响应中，所有副本返回的 $\text{Deps}$ 和 $\text{Seq}$ 完全一致，且这些副本构成了快速法定人数（Fast Quorum），那么该命令就可以直接进入 Commit 状态。

• EPaxos 的 Fast Quorum 大小为 $F = f + \lfloor \frac{f+1}{2} \rfloor$（其中 $f$ 为容错数，集群总数为 $2f+1$）。例如在 5 节点集群中，Fast Quorum 需要 4 个节点达成一致。

此时，Leader 只需要 1 个 RTT（PreAccept 的往返）即可向客户端返回成功，后续的 Commit 消息是异步广播的。

Client      Leader (Replica A)       Replica B        Replica C
  |                 |                    |                |
  |--- Propose ---->|                    |                |
  |                 |--- PreAccept ----->|                |
  |                 |--- PreAccept ---------------------->|
  |                 |<-- Deps/Seq OK ----|                |
  |                 |<-- Deps/Seq OK ---------------------|
  |<-- Success -----| (1 RTT Finished)
  |                 |--- Commit (Async)->|                |

3. 冲突时的代价：慢速路径（Slow Path）

如果副本返回的 $\text{Deps}$ 或 $\text{Seq}$ 不一致（说明存在并发冲突），Leader 就无法在 1 RTT 内提交。它必须**合并（Merge）**所有的依赖关系，然后发起一轮传统的 Paxos 协商：

1. 广播 Accept(γ, MergedDeps, MaxSeq) 到标准 Quorum（$f+1$ 个节点）。
2. 收到多数派确认后，再广播 Commit。
   这需要 2 RTT 才能完成。

4. 致命软肋：执行时的拓扑排序与活锁风险

EPaxos 最受诟病的是其执行阶段的复杂度。
由于每个副本只记录了直接依赖（Deps），在执行命令时，必须将这些依赖关系构建成一个有向图，并进行拓扑排序。

• 如果图中存在环（例如 $A \rightarrow B \rightarrow C \rightarrow A$），则需要找出强连通分量（SCC），并按照特定的规则（如 Seq 大小、TxnId 大小）打破循环。
• 在高冲突率场景下，依赖图会变得无限庞大，导致 Deferred Execution（延迟执行） 严重。每个节点为了执行一个命令，不得不等待它依赖的所有前置命令全部 Commit。这会导致严重的性能塌缩和内存暴涨。

二、 Accord 的 1 RTT 实现：时间戳升级与执行时间解耦

Accord 协议同样是一个无主、支持跨行分布式事务的共识协议。但它的设计理念深受新一代分布式数据库（如 Spanner、CockroachDB）的影响，试图在提供 1 RTT 共识的同时，彻底解决 EPaxos 的依赖图恶梦。

1. 核心概念：TxnId、Deps 与 ExecuteAt

在 Accord 中，每个事务被赋予三个关键属性：

• $\text{TxnId}$：事务发起时的逻辑时间戳（通常由本地物理时钟加上协调者 ID 构成）。
• $\text{Deps}$：该事务依赖的其他事务 ID 集合。
• $\text{ExecuteAt}$：事务实际执行的时间戳（$\ge \text{TxnId}$）。这是 Accord 的关键创新。

2. 1 RTT 的达成：更宽容的 Fast Path

与 EPaxos 遇到任何差异就退化到 2 RTT 不同，Accord 引入了 ExecuteAt 升级机制（Timestamp Bumping），使得它在部分冲突场景下依然能保持 1 RTT。

1. PreAccept 阶段：协调者生成 $\text{TxnId}$，向 Fast Quorum 发送 PreAccept(Txn, TxnId)。
2. 依赖与时间戳计算：每个副本在本地计算该事务所触及的 Key，找出与之冲突的、已知的最大时间戳，并提议一个本地的 $\text{ExecuteAt}$（必须大于所有冲突事务的 $\text{TxnId}$ 和 $\text{ExecuteAt}$）。
3. 协调者决策：
   • 如果所有副本返回的 $\text{Deps}$ 一致，且提议的 $\text{ExecuteAt}$ 相同（等于 $\text{TxnId}$），则以 1 RTT 提交。
   • 即使不一致：如果协调者发现虽然副本提议的 $\text{ExecuteAt}$ 被调大了（说明有冲突），但只要在 Fast Quorum 返回的范围内能够计算出一个确定性的、足够大的 $\text{ExecuteAt}$ 使得所有冲突事务都在其之前或之后，协调者可以直接单方面做出 Commit 决策，并将最终的 $\text{ExecuteAt}$ 和合并后的 $\text{Deps}$ 广播出去。
   • 这依然只需要 1 RTT！ 只有在极其严重的并发冲突，导致协调者无法在一个 Fast Quorum 内安全地推导出一个一致的 $\text{ExecuteAt}$ 范围时，才会退化到 2 RTT（Accept 阶段）。

Client         Coordinator           Replica B        Replica C
  |                 |                    |                |
  |--- Propose ---->|                    |                |
  |                 |--- PreAccept ----->|                |
  |                 |--- PreAccept ---------------------->|
  |                 |<-- LocalDeps/BumpedExecuteAt -------|
  |                 |<-- LocalDeps/BumpedExecuteAt -------|
  |                 | (Coordinator resolves ExecuteAt and Deps internally)
  |<-- Success -----| (1 RTT Finished)
  |                 |--- Commit (Async)->|                |

3. 执行机制的颠覆：无需拓扑排序

Accord 彻底抛弃了 EPaxos 的有向图拓扑排序。
在 Accord 中，事务的执行顺序完全由 $\text{ExecuteAt}$ 的大小决定。

• 每个节点本地维护一个简单的队列，按照 $\text{ExecuteAt}$ 的字面大小线性执行事务。
• 如果两个事务有依赖关系，它们必定拥有不同的 $\text{ExecuteAt}$。
• 这意味着，Accord 不需要去寻找强连通分量，不需要解决“环”的问题。由于消除了图计算开销，其执行管道的吞吐量呈线性增长，极大地降低了高并发冲突下的尾延迟（Tail Latency）。

三、 EPaxos 与 Accord 深度对比

关键差异剖析：为什么 Accord 比 EPaxos 更适合工业界？

1. 冲突解决哲学的转变

EPaxos 的设计带有学术界对“极简依赖”的偏执。它试图精确记录“谁在谁之前发生”，导致每个副本都在拼凑一张巨大的全局拼图。一旦并发量上升，拼图碎片（Deps）对不上，就会引发大量的 Slow Path。

Accord 则引入了实用的妥协。它利用逻辑时钟（TxnId / ExecuteAt）对执行顺序进行了“数字化”。当发生冲突时，Accord 的做法不是去记录错综复杂的因果网络，而是简单粗暴地**“把冲突事务的执行时间往后推”**（Bump Timestamp）。只要大家都承认这个新的时间戳，顺序就自然确定了。这种设计不仅保住了 1 RTT，还大大简化了状态机的实现。

2. 恢复机制（Recovery）的鲁棒性

在无主协议中，如果 Coordinator 在中途挂掉，其他节点必须接管并尝试提交或终止（Abort）该事务。

• EPaxos 的恢复：接管节点需要重建依赖图，如果在接管期间又发生了并发冲突，恢复过程会变得异常复杂，甚至可能导致活锁（Livelock）。
• Accord 的恢复：由于每个事务的生命周期都有明确的 Epoch 划分，且每个事务都锚定在一个具体的 $\text{ExecuteAt}$ 上，接管节点只需要查询 Fast Quorum，确定该事务是否已经有了确定的 $\text{ExecuteAt}$。如果没有，则安全地将其 Bump 到一个足够大的时间戳然后提交，或者直接将其标记为 Invalidated。整个过程是确定性且线性的。

四、 总结

• EPaxos 证明了在无主架构下通过依赖收集实现 1 RTT 共识的可行性，但其依赖图的设计在真实的高负载生产环境中表现出严重的性能不稳定性。
• Accord 则是在汲取了 EPaxos 的教训后，做出的工程化最优解。它通过**执行时间戳（ExecuteAt）**将“共识”与“执行”解耦，在冲突时通过时间戳升级保留了 1 RTT 的可能性，彻底解决了拓扑排序带来的性能灾难。

对于需要高吞吐、低延迟、多活部署的现代分布式数据库而言，Accord 代表了当前无主共识协议演进的一个极具前景的方向。