【分布式系统百科】EPaxos 与 Flexible Paxos：打破 Leader 瓶颈的两条路

前置阅读：Raft 深度重写 讨论了基于 Leader 的共识协议的完整机制。本文假设你已经理解 Multi-Paxos 和 Raft 的基本工作流程。

Raft 和 Multi-Paxos 有一个共同的设计选择：所有客户端写请求都必须经过一个 Leader 节点，由 Leader 决定日志的全局顺序，再复制到 Follower。

这个设计很直观，也很容易理解。但它有两个结构性问题：

1. 吞吐瓶颈。所有写操作都要过 Leader 的网络和磁盘。Leader 的带宽就是系统的带宽上限。
2. 延迟下限。客户端不在 Leader 所在的数据中心时，每笔写至少要多一跳 WAN 延迟。在跨大洲部署里，这可能意味着每笔写多 100-200ms。

2013 年和 2016 年，两篇论文分别提出了两种不同的应对思路。

• EPaxos（Egalitarian Paxos，Moraru et al., 2013）：彻底去掉固定 Leader，任意节点都能直接提交命令，用依赖图（Dependency Graph）代替全序日志来处理命令之间的冲突。
• Flexible Paxos（Howard et al., 2016）：保留 Leader，但放松了 Quorum 的约束——Phase 1 和 Phase 2 的 Quorum 不必各自过半，只需要它们的交集非空。

两条路的出发点不同，适用场景不同，工程难度也差得很远。这篇文章把两者的核心机制拆开讲清楚，然后做一个横向对比。

一、EPaxos：无主共识协议

动机：为什么要去掉 Leader

先回顾一下 Multi-Paxos 的写路径。客户端发一个写请求，经过以下步骤：

1. 请求到达 Leader。
2. Leader 分配一个日志槽位（log slot），给这个命令定序。
3. Leader 把 Accept 消息发给所有 Follower。
4. 多数 Follower 回复 Accept 后，Leader 提交，回复客户端。

整个过程中，Leader 做了两件事：定序和复制。复制是必要的——多副本系统必须把数据写到多个节点上。但定序呢？如果两个命令操作的是不同的 key，它们之间根本不存在冲突，有没有必要让它们排成一个全序？

EPaxos 的核心洞察就在这里：只有冲突的命令才需要排序。不冲突的命令可以并行提交，不需要任何节点来定序。

这就是”无主”（Leaderless）的含义——不是没有 Leader 就会乱，而是把”定序”这件事从全局 Leader 的职责中拆出来，变成一个按需解决冲突的局部问题。

EPaxos 的系统模型

EPaxos 假设一个由 2F+1 个副本（Replica）组成的集群，容忍最多 F 个节点崩溃（crash-stop 模型）。没有固定 Leader。每个 Replica 都可以直接接收客户端请求，作为该命令的 Command Leader 发起提交流程。

一个关键前提：EPaxos 假设存在一个冲突检测函数（interference/conflict relation）。给定两个命令 α 和 β，这个函数能判断它们是否冲突。典型的定义是：如果两个命令访问了相同的 key，且至少一个是写操作，则冲突。不冲突的命令可以以任意顺序执行，结果相同。

依赖图（Dependency Graph）

EPaxos 不使用线性日志。每个命令提交时，会携带一个依赖集合（dependency set），记录”这个命令必须在哪些其他命令之后执行”。所有命令和它们的依赖关系构成一个有向图——依赖图。

举个例子。假设集群中有三个命令：

• α: Put(x, 1) —— 写 key x
• β: Put(x, 2) —— 写 key x
• γ: Get(y) —— 读 key y

α 和 β 冲突（都访问 key x，且都是写操作）。γ 和 α、β 都不冲突（访问不同的 key）。

在 EPaxos 中，α 和 β 提交后各自的依赖集合里会包含对方（因为冲突），而 γ 的依赖集合为空（不与任何已知命令冲突）。γ 可以和 α、β 并行执行。α 和 β 之间的执行顺序则需要通过依赖图的排序规则来确定。

这和 Raft 的方式完全不同。Raft 会把 α、β、γ 三个命令放进一个线性日志里：先 α，再 β，再 γ（或者别的顺序，取决于 Leader 收到的先后）。即使 γ 和 α、β 完全不相干，它也必须排队。

Fast Path 与 Slow Path

EPaxos 的提交分两条路径。

Fast Path（快路径）——只需 1 个 RTT：

1. Command Leader R₁ 收到客户端命令 α。
2. R₁ 计算 α 和本地已知命令的依赖关系，得到初始依赖集合 deps₁。
3. R₁ 向其他 Replica 发送 PreAccept 消息，包含命令 α 和 deps₁。
4. 每个收到 PreAccept 的 Replica R_i 检查自己本地的命令日志，看有没有和 α 冲突但不在 deps₁ 中的命令。如果有，就把它们加到依赖集合中，返回更新后的 deps_i。如果没有冲突，直接返回 deps₁。
5. R₁ 收集回复。如果足够多的 Replica 返回了相同的依赖集合，α 可以直接提交。这里”足够多”是一个 Fast Path Quorum，大小为 ⌊(3F+1)/2⌋ + 1 — 在 5 节点集群中是 4（包含 Command Leader 自己），在 3 节点集群中是 2（包含自己）。

关键点：Fast Path 能走通的前提是大家对依赖的看法一致。如果所有 Replica 看到的本地状态差不多（没有大量并发冲突），它们对 α 该依赖哪些命令的判断就会一致，Fast Path 就能在一个 RTT 内完成。

Slow Path（慢路径）——需要 2 个 RTT：

如果不同 Replica 返回的依赖集合不一致（有些 Replica 看到了额外的冲突命令，有些没有），Fast Path 失败。此时 R₁ 退化到经典 Paxos 的 Accept 阶段：

1. R₁ 合并所有收到的依赖集合，取并集，得到最终的 deps。
2. R₁ 向所有 Replica 发送 Accept 消息，包含 α 和 deps。
3. 多数 Replica（F+1，普通 Paxos Quorum）回复 Accept 后，α 提交。

Slow Path 本质上就是 Classic Paxos 的 Phase 2。它和 Multi-Paxos 的正常写路径延迟相当——2 个 RTT（PreAccept + Accept）。

总结：

以下流程图展示了一个命令从到达 Replica 到最终提交的完整决策路径：

flowchart TD
    A["命令 α 到达 Replica R₁"] --> B["R₁ 计算本地依赖集合 deps₁"]
    B --> C["R₁ 向其他 Replica 发送 PreAccept"]
    C --> D{"所有回复的 deps 是否一致？"}
    D -->|"是：≥ Fast Quorum 返回相同 deps"| E["Fast Path 提交（1 RTT）"]
    D -->|"否：不同 Replica 看到不同冲突"| F["合并所有 deps 取并集"]
    F --> G["R₁ 发送 Accept（经典 Paxos Phase 2）"]
    G --> H{"多数派（F+1）回复 Accept？"}
    H -->|是| I["Slow Path 提交（2 RTT）"]
    H -->|否| J["等待或重试"]
    E --> K["命令进入依赖图，等待执行排序"]
    I --> K

该流程图的核心分支在于 PreAccept 阶段各 Replica 返回的依赖集合是否一致。如果集群中没有大量并发冲突命令，各 Replica 本地状态相似，依赖判断趋于一致，命令可以在 1 个 RTT 内通过 Fast Path 提交。一旦某个 Replica 看到了其他 Replica 不知道的冲突命令（例如该命令刚到达尚未传播），依赖不一致就会迫使 Command Leader 退化到 Slow Path，额外增加一轮 Accept 通信。

Fast Path 的 Quorum 比普通多数 Quorum 更大。这是 EPaxos 的代价之一：在 5 节点集群中，Fast Path 需要 4 个节点同意（而 Raft 只需要 3 个）。但好处是只要走通，1 个 RTT 就搞定，比 Raft 的 2 个 RTT（客户端→Leader→Follower→Leader→客户端）更快。

序列号与 epoch

每个命令在 EPaxos 中除了携带依赖集合，还携带一个序列号（sequence number，简称 seq）。seq 的值取依赖集合中所有命令的 seq 的最大值加一。seq 的作用是在同一个强连通分量（SCC）内提供确定性的排序依据——后面执行排序部分会详细解释。

每个命令在集群中由一个二元组 (Replica ID, Instance ID) 唯一标识。Replica ID 标识哪个 Replica 作为 Command Leader 发起了这个命令，Instance ID 是该 Replica 本地的自增编号。

执行排序：Tarjan SCC + 确定性排序

提交（commit）和执行（execute）在 EPaxos 中是分开的。命令提交后不能立刻执行，因为它可能依赖尚未提交的其他命令。

EPaxos 的执行排序算法：

1. 等待依赖就绪：一个命令 α 只有在它依赖集合中的所有命令都已提交后，才能开始执行排序。
2. 构建子图：从 α 出发，沿着依赖关系递归地收集所有可达的命令，构建一个局部依赖子图。
3. Tarjan 算法找强连通分量（SCC）：在这个子图上运行 Tarjan 算法，找出所有 SCC。一个 SCC 就是一组命令，它们之间存在循环依赖——A 依赖 B，B 依赖 C，C 又依赖 A。
4. 拓扑排序 SCC：对 SCC 之间的有向关系做拓扑排序——如果 SCC₁ 中的命令依赖 SCC₂ 中的命令，SCC₂ 先执行。
5. SCC 内部确定性排序：同一个 SCC 内的命令，所有 Replica 必须用相同的规则排序。默认按 seq 升序，seq 相同时按 (Replica ID, Instance ID) 字典序。

关键在于第 5 步。SCC 内存在循环依赖，逻辑上它们没有”天然的先后”。但为了让所有 Replica 得到相同的执行结果，必须有一个确定性规则来打破循环。只要所有 Replica 用的规则一样，结果就一致。

Tarjan SCC 的具体工作示例

用一个具体的场景来理解 SCC 如何影响执行排序。假设集群中有五个已提交的命令：

• cmd1: Put(x, 1)，seq=1，deps={cmd2}
• cmd2: Put(x, 2)，seq=2，deps={cmd1}
• cmd3: Put(y, 1)，seq=1，deps={cmd2}
• cmd4: Put(y, 2)，seq=2，deps={cmd3}
• cmd5: Get(z)，seq=1，deps={}

graph LR
    cmd1["cmd1: Put(x,1)<br/>seq=1"] -->|依赖| cmd2["cmd2: Put(x,2)<br/>seq=2"]
    cmd2 -->|依赖| cmd1
    cmd3["cmd3: Put(y,1)<br/>seq=1"] -->|依赖| cmd2
    cmd4["cmd4: Put(y,2)<br/>seq=2"] -->|依赖| cmd3
    cmd5["cmd5: Get(z)<br/>seq=1"]

    style cmd1 fill:#f9d,stroke:#333
    style cmd2 fill:#f9d,stroke:#333
    style cmd3 fill:#bbf,stroke:#333
    style cmd4 fill:#bbf,stroke:#333
    style cmd5 fill:#bfb,stroke:#333

Tarjan 算法从任意节点出发做深度优先搜索，维护一个栈和两个编号（发现序号 dfn 和可回溯的最小序号 low）。当 dfn[v] == low[v] 时，弹栈得到一个 SCC。在上图中，算法会发现：

• SCC-A = {cmd1, cmd2}：cmd1 依赖 cmd2，cmd2 依赖 cmd1，构成循环。
• SCC-B = {cmd3}：cmd3 依赖 cmd2（属于 SCC-A），但没有被 SCC-A 中的命令反向依赖。
• SCC-C = {cmd4}：cmd4 依赖 cmd3。
• SCC-D = {cmd5}：无依赖，独立节点。

拓扑排序的结果是：SCC-A 最先执行（被其他 SCC 依赖），然后是 SCC-B，然后是 SCC-C。SCC-D 与其他 SCC 无依赖关系，可以在任何位置执行。

SCC-A 内部的排序规则：按 seq 升序，seq 相同时按 (Replica ID, Instance ID) 字典序。所以 cmd1（seq=1）先于 cmd2（seq=2）。最终的全局执行顺序为：cmd1 -> cmd2 -> cmd3 -> cmd4，cmd5 可在任意位置并行执行。

所有 Replica 用完全相同的 Tarjan 算法和相同的 SCC 内部排序规则，因此即使它们看到命令的到达顺序不同，最终计算出的执行顺序也完全一致。

这个排序算法比 Raft 的”按日志索引执行”复杂得多。Raft 的执行顺序是天然的——日志索引就是执行顺序。EPaxos 需要在执行时重建顺序，代价是更高的计算复杂度和更长的执行延迟。

隐含假设与实现难度

EPaxos 论文中有一些隐含假设，在工程实现时容易出问题。

假设 1：冲突检测函数的正确性与完备性

EPaxos 的正确性依赖于冲突检测的准确性。如果两个命令实际上冲突（交换执行顺序会产生不同结果），但冲突检测函数没有报告冲突，EPaxos 就不会建立依赖关系，两个 Replica 可能以不同顺序执行这两个命令，导致状态不一致。

在 KV 存储中，“访问同一个 key 且至少一个是写”是清晰的冲突定义。但在更复杂的状态机中——比如涉及范围查询、二级索引、触发器——准确地定义冲突就没那么容易了。

假设 2：命令的确定性

EPaxos 假设每个命令的执行是确定性的。给定同样的初始状态和同样的命令序列，所有 Replica 必须产生完全相同的结果。这和所有复制状态机（RSM）的要求一致，但在 EPaxos 中更加重要：因为不同 Replica 可能以不同的全局顺序执行命令（只要不冲突的命令可以任意排序），任何非确定性都可能被放大。

假设 3：恢复协议的复杂性

当一个 Command Leader 在发出 PreAccept 后崩溃，其他 Replica 需要运行恢复协议来完成这个命令的提交。EPaxos 的恢复协议是整个算法中最复杂的部分。它需要处理多种情况：

• Command Leader 只发出了部分 PreAccept 就崩溃了。
• 有些 Replica 收到了 PreAccept，有些没有。
• 恢复过程中又有新的并发命令到达。

恢复协议需要正确地重建或确定依赖集合和 seq，然后通过 Paxos Accept 完成提交。这个过程的正确性证明在原始论文中非常复杂，实际实现也容易出错。

以下伪代码展示了恢复协议的核心逻辑。当一个 Replica 发现某个命令实例处于未完成状态（Command Leader 可能已崩溃）时，它作为 Recovery Leader 发起恢复：

def recover(instance_id):
    """恢复一个未完成的命令实例"""
    # Phase 1: 用更高的 ballot 发起 Prepare，抢占原 Command Leader
    new_ballot = next_ballot()
    responses = []
    for replica in all_replicas:
        resp = send_prepare(replica, instance_id, new_ballot)
        if resp is not None:
            responses.append(resp)

    if len(responses) < F + 1:
        return FAIL  # 无法联系到多数派

    # Phase 2: 根据收集到的状态决定如何完成
    accepted = [r for r in responses if r.status == ACCEPTED]
    pre_accepted = [r for r in responses if r.status == PRE_ACCEPTED]

    if any(accepted):
        # 已有 Replica 在 Accept 阶段：使用已接受的 deps 和 seq
        best = max(accepted, key=lambda r: r.ballot)
        final_deps = best.deps
        final_seq = best.seq
    elif len(pre_accepted) >= fast_quorum_size():
        # 足够多的 Replica 在 PreAccept 阶段且 deps 一致
        if all_deps_equal(pre_accepted):
            final_deps = pre_accepted[0].deps
            final_seq = pre_accepted[0].seq
        else:
            # deps 不一致，取并集
            final_deps = union_all_deps(pre_accepted)
            final_seq = max(r.seq for r in pre_accepted)
    elif any(pre_accepted):
        # 部分 Replica 有 PreAccept 记录
        final_deps = union_all_deps(pre_accepted)
        final_seq = max(r.seq for r in pre_accepted)
    else:
        # 没有任何 Replica 见过这个命令：提交 no-op
        final_deps = []
        final_seq = 0
        submit_noop(instance_id, new_ballot)
        return OK

    # Phase 3: 用确定的 deps 和 seq 走 Paxos Accept
    ack_count = 0
    for replica in all_replicas:
        if send_accept(replica, instance_id, new_ballot, final_deps, final_seq):
            ack_count += 1
    if ack_count >= F + 1:
        commit(instance_id, final_deps, final_seq)
        return OK
    return FAIL

恢复协议的复杂性在于它需要区分多种中间状态：命令可能只被部分 Replica PreAccept、可能已被部分 Accept、甚至可能从未被任何 Replica 看到。每种情况的处理逻辑不同，且必须保证与正常路径的提交结果不冲突。

已知 Bug 与修复

EPaxos 论文和原始实现中存在已知的正确性问题。

Bug 1：执行排序中的活锁

Sutra（2020）在论文 On the correctness of Egalitarian Paxos 中指出，EPaxos 原始论文中描述的执行算法在某些边界条件下可能导致活锁（livelock）。具体来说，如果两个 Replica 同时尝试执行依赖相互纠缠的命令集合，它们可能会反复等待对方的命令先提交，导致死循环。

Sutra 提出了修正方案：在执行排序算法中引入更严格的等待条件，确保至少一个 Replica 能取得进展。

Bug 2：依赖集合的非传递性

原始论文假设依赖关系可以安全地通过传递性推导。但 Sutra 指出在某些并发场景下，依赖集合的合并方式可能导致不同 Replica 看到不一致的依赖图结构，即使每个 Replica 本地的操作都正确。

修复方案涉及在 PreAccept 阶段更严格地合并依赖集合，并在 Slow Path 中使用合并后的完整依赖集合。

Bug 3：原始实现的工程问题

EPaxos 作者公开的 Go 实现（github.com/efficient/epaxos）在社区测试中被发现有多处 bug，包括竞态条件、不正确的依赖追踪、恢复路径的逻辑错误等。这不是算法本身的问题，而是实现的正确性验证极其困难——EPaxos 的状态空间比 Raft 大得多，穷举测试很难覆盖所有 corner case。

截至目前，没有一个广泛使用的生产级 EPaxos 实现。相比之下，Raft 的生产实现有 etcd/raft、HashiCorp Raft、Dragonboat 等多个成熟选项。这本身就说明了 EPaxos 的工程实现难度。

EPaxos 的性能特征

EPaxos 论文的 benchmark 显示，在低冲突（命令间冲突率低于 2%）的工作负载下，EPaxos 的吞吐量可以比 Multi-Paxos 高 2 倍以上。原因是：

1. 没有 Leader 瓶颈：写负载均匀分布在所有 Replica 上，网络带宽利用率更高。
2. Fast Path 省一个 RTT：在低冲突时大部分命令走 Fast Path，只需 1 RTT 提交。
3. 无需转发：客户端可以直接连最近的 Replica，不需要先转发到 Leader。

但在高冲突工作负载下（例如大量命令集中在少数热点 key 上），EPaxos 的优势大幅缩减甚至反转：

1. Slow Path 频率上升：高冲突导致依赖集合不一致，更多命令走 Slow Path。
2. 依赖图膨胀：大量冲突命令构成复杂的依赖图，执行排序的计算开销增大。
3. SCC 变大：高冲突导致更大的 SCC，SCC 内部的排序和执行延迟增加。

这在实际系统中是一个重要的取舍：如果你的工作负载是大量独立 key 的并发操作（比如用户之间互不干扰的操作），EPaxos 有明显优势。如果你的工作负载是大量操作集中在少数共享状态上（比如全局计数器、共享锁），EPaxos 的优势会被 Slow Path 和复杂的执行排序吃掉。

二、Flexible Paxos：重新定义 Quorum

核心洞察

Classic Paxos 的标准教科书要求：Phase 1（Prepare）和 Phase 2（Accept）都使用多数 Quorum（即至少 ⌊N/2⌋ + 1 个节点）。在一个 5 节点集群中，两个阶段各自都需要 3 个节点参与。

Heidi Howard 等人在 2016 年的论文 Flexible Paxos: Quorum intersection revisited 中提出了一个简单但影响深远的观察：

Phase 1 和 Phase 2 的 Quorum 不需要各自过半。它们只需要满足一个条件：Q1 ∩ Q2 ≠ ∅（两个 Quorum 有交集）。

换成数学语言：Q1 + Q2 > N。

为什么这个条件就够了？回顾 Paxos 的安全性论证：

• Phase 1（Prepare）的作用是发现当前系统中是否已经有被接受的值。一个新的 Proposer 发送 Prepare(n) 消息，收到 Q1 个 Acceptor 的回复。如果之前已经有值通过了 Phase 2 的 Accept，那么至少有一个 Acceptor 同时出现在 Q1 和 Q2 中——它会告诉新 Proposer 那个已经被接受的值。
• Phase 2（Accept）的作用是让足够多的 Acceptor 接受一个值。Q2 个 Acceptor 接受了值 v。

安全性的保证来自一个不变量：任意两轮 Phase 1 和 Phase 2 的参与者至少有一个重叠。只要这个重叠存在，新的 Proposer 就一定能发现已经被接受的值，从而不会覆盖它。

flowchart TD
    subgraph 经典 Paxos
        A1["Phase 1 (Prepare)<br/>Q1 = 多数派 = 3/5"] --- A2["Phase 2 (Accept)<br/>Q2 = 多数派 = 3/5"]
        A2 --- A3["Q1 ∩ Q2 ≥ 1<br/>（两个多数派必有交集）"]
    end

    subgraph Flexible Paxos
        B1["Phase 1 (Prepare)<br/>Q1 = 4/5（更大）"] --- B2["Phase 2 (Accept)<br/>Q2 = 2/5（更小）"]
        B2 --- B3["Q1 + Q2 = 6 > N=5<br/>（交集仍然非空）"]
    end

    subgraph 安全性保证
        C1["新 Proposer 的 Prepare<br/>联系 Q1 个节点"] --> C2{"Q1 ∩ Q2 ≠ ∅ ?"}
        C2 -->|是| C3["至少一个节点同时参与了<br/>旧的 Accept 和新的 Prepare"]
        C3 --> C4["新 Proposer 发现已接受的值<br/>不会覆盖，安全性成立"]
        C2 -->|否| C5["可能覆盖已接受的值<br/>安全性被违反"]
    end

上图展示了 Flexible Paxos 的核心安全性论证。经典 Paxos 用”两个 Quorum 都是多数”来保证交集非空，这是最简单但不是唯一的方式。Flexible Paxos 放松了这个约束：只要 Q1 + Q2 > N，两个集合就一定存在交集，新的 Proposer 在 Prepare 阶段一定能从交集中的节点得知已被接受的值。这个放松使得 Phase 2（高频操作）的 Quorum 可以更小，而 Phase 1（低频操作）的 Quorum 相应增大。

经典 Paxos 用”两个 Quorum 都是多数”来保证重叠。但实际上，多数只是保证重叠的一种方式——不是唯一的方式。只要 Q1 + Q2 > N，两个集合就一定有交集。

Phase 1 / Phase 2 的不对称性

这个放松看起来简单，但实际意义取决于 Phase 1 和 Phase 2 在系统中的使用频率差异。

在一个稳态运行的 Multi-Paxos 系统中：

• Phase 1（Leader 选举 / Prepare）：只在 Leader 发生变更时运行。如果系统稳定，可能几小时甚至几天才运行一次。
• Phase 2（Accept / 日志复制）：每一笔写操作都要运行。

频率差异巨大。Phase 1 是低频操作，Phase 2 是高频操作。

Flexible Paxos 允许把 Phase 2 的 Quorum 设小（减少写延迟），代价是 Phase 1 的 Quorum 要设大。这在实际中是划算的，因为 Phase 1 本来就不频繁。

具体来看。一个 5 节点集群：

“写优化”配置下，Phase 2 只需要 2 个节点确认（包括 Leader 自己的话，只需要 1 个 Follower 回复），写延迟大幅降低。代价是 Leader 选举需要 4 个节点参与——如果 2 个节点同时挂了，选不出新 Leader。但稳态下这没关系。

“极端写优化”配置下，Phase 2 的 Quorum 为 1——Leader 自己写完就算提交。这意味着 Leader 的本地磁盘故障就会丢数据。这种配置不适用于需要持久性保证的场景，但在某些临时性或可重建的数据场景下（例如缓存预热），延迟极低。

容错能力的变化

需要注意：Flexible Paxos 改变了容错能力的计算方式。

Classic Paxos（N=5, Q1=Q2=3）：最多容忍 2 个节点故障（Phase 1 和 Phase 2 都只需要 3 个，5 - 3 = 2）。

Flexible Paxos（N=5, Q1=4, Q2=2）：

• Phase 2（写）：最多容忍 3 个节点故障（5 - 2 = 3）。稳态下的容错能力实际上提高了。
• Phase 1（选举）：最多容忍 1 个节点故障（5 - 4 = 1）。选举时的容错能力降低了。

这是一个权衡。如果 Leader 很少变更，降低 Phase 1 的容错能力是可以接受的。但如果系统频繁发生 Leader 切换（例如在不稳定的网络环境中），Q1 变大意味着选举更难成功，系统可用性反而下降。

跨数据中心应用

Flexible Paxos 最直接的应用场景是跨数据中心部署。

假设你有两个数据中心：DC-A 部署 3 个节点，DC-B 部署 2 个节点，总共 N=5。DC-A 和 DC-B 之间的 WAN 延迟是 50ms。

用经典 Paxos（Q2=3）：每笔写至少需要一个节点的 Accept 跨 WAN 传输。即使 Leader 在 DC-A，它也需要 3 个 Accept 回复，DC-A 只有 3 个节点（包括 Leader），如果其中一个暂时不可用，就必须等 DC-B 的回复。

用 Flexible Paxos（Q1=4, Q2=2）：Leader 在 DC-A 时，Phase 2 只需要 2 个节点——Leader 自己加 DC-A 的另一个节点。写操作完全不需要跨 WAN。只有 Leader 选举（Phase 1）需要跨 WAN 联系 DC-B。

在稳态下，这意味着写延迟从”LAN + WAN”降到”纯 LAN”。这是一个数量级的改善。

WPaxos（Ailijiang et al., 2017）是 Flexible Paxos 思想的一个具体应用。它在多数据中心场景下使用不对称 Quorum，让写操作在本地数据中心完成，同时用大 Quorum 的 Phase 1 保证跨数据中心的安全性。

Flexible Paxos 与 Raft 的关系

Raft 的 Leader 选举和日志复制分别对应 Paxos 的 Phase 1 和 Phase 2。理论上，Flexible Paxos 的思想可以直接应用到 Raft 上：选举时要求更多节点投票，复制时只需要更少的节点确认。

但实际上，Raft 的设计中有一些细节使得直接应用 Flexible Quorum 比较复杂：

1. Safety 证明。Raft 的安全性论证依赖于”多数 Quorum”这个条件。改用不对称 Quorum 后，需要重新验证所有安全性属性（Election Safety、Leader Completeness 等）。
2. Membership Change。Raft 的成员变更（joint consensus 或 single-server change）假设了固定的 Quorum 大小。引入 Flexible Quorum 后，成员变更的安全性需要额外论证。
3. ReadIndex / LeaseRead。Raft 的线性化读依赖于 Leader 确认自己仍是 Leader，这通常通过向多数节点发送心跳来实现。如果写 Quorum 变小，Leader 的”多数心跳”可能无法保证它看到了最新的数据。

这些问题不是不可解，但需要仔细处理。目前主流的 Raft 实现（etcd/raft、HashiCorp Raft）都没有原生支持 Flexible Quorum。

三、Go 模拟：EPaxos Fast Path

下面用 Go 实现一个简化的 EPaxos Fast Path 模拟。这不是生产代码——它跳过了持久化、恢复协议、网络传输等工程细节——但能展示依赖追踪和 Fast Path 判定的核心逻辑。

package main

import (
    "fmt"
    "sort"
    "strings"
    "sync"
)

// Command 表示一个客户端命令
type Command struct {
    Op  string // "Put" 或 "Get"
    Key string
    Val string
}

func (c Command) String() string {
    if c.Op == "Get" {
        return fmt.Sprintf("Get(%s)", c.Key)
    }
    return fmt.Sprintf("Put(%s,%s)", c.Key, c.Val)
}

// Conflicts 判断两个命令是否冲突
// 规则：访问相同 key 且至少一个是写操作
func Conflicts(a, b Command) bool {
    if a.Key != b.Key {
        return false
    }
    return a.Op == "Put" || b.Op == "Put"
}

// InstanceID 唯一标识一个命令实例
type InstanceID struct {
    Replica  int
    Instance int
}

func (id InstanceID) String() string {
    return fmt.Sprintf("R%d.%d", id.Replica, id.Instance)
}

// InstanceState 记录每个命令实例的状态
type InstanceState struct {
    Cmd  Command
    Deps []InstanceID // 依赖集合
    Seq  int          // 序列号
}

// Replica 是一个 EPaxos 副本
type Replica struct {
    mu        sync.Mutex
    id        int
    instances map[InstanceID]*InstanceState
    nextInst  int
}

func NewReplica(id int) *Replica {
    return &Replica{
        id:        id,
        instances: make(map[InstanceID]*InstanceState),
    }
}

// findConflicts 查找与给定命令冲突的所有已知实例
func (r *Replica) findConflicts(cmd Command, exclude InstanceID) ([]InstanceID, int) {
    r.mu.Lock()
    defer r.mu.Unlock()

    var deps []InstanceID
    maxSeq := 0
    for id, inst := range r.instances {
        if id == exclude {
            continue
        }
        if Conflicts(cmd, inst.Cmd) {
            deps = append(deps, id)
            if inst.Seq > maxSeq {
                maxSeq = inst.Seq
            }
        }
    }
    // 确定性排序
    sort.Slice(deps, func(i, j int) bool {
        if deps[i].Replica != deps[j].Replica {
            return deps[i].Replica < deps[j].Replica
        }
        return deps[i].Instance < deps[j].Instance
    })
    return deps, maxSeq
}

// handlePreAccept 处理 PreAccept 请求
// 返回该 Replica 计算出的依赖集合和 seq
func (r *Replica) handlePreAccept(id InstanceID, cmd Command, leaderDeps []InstanceID, leaderSeq int) ([]InstanceID, int) {
    localDeps, localMaxSeq := r.findConflicts(cmd, id)

    // 合并 Leader 的依赖和本地依赖
    merged := mergeDeps(leaderDeps, localDeps)
    seq := leaderSeq
    if localMaxSeq+1 > seq {
        seq = localMaxSeq + 1
    }

    // 记录到本地
    r.mu.Lock()
    r.instances[id] = &InstanceState{Cmd: cmd, Deps: merged, Seq: seq}
    r.mu.Unlock()

    return merged, seq
}

// mergeDeps 合并两个依赖集合（去重）
func mergeDeps(a, b []InstanceID) []InstanceID {
    seen := make(map[InstanceID]bool)
    for _, d := range a {
        seen[d] = true
    }
    for _, d := range b {
        seen[d] = true
    }
    result := make([]InstanceID, 0, len(seen))
    for d := range seen {
        result = append(result, d)
    }
    sort.Slice(result, func(i, j int) bool {
        if result[i].Replica != result[j].Replica {
            return result[i].Replica < result[j].Replica
        }
        return result[i].Instance < result[j].Instance
    })
    return result
}

// depsEqual 比较两个依赖集合是否相同
func depsEqual(a, b []InstanceID) bool {
    if len(a) != len(b) {
        return false
    }
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

func depsString(deps []InstanceID) string {
    if len(deps) == 0 {
        return "∅"
    }
    parts := make([]string, len(deps))
    for i, d := range deps {
        parts[i] = d.String()
    }
    return "{" + strings.Join(parts, ", ") + "}"
}

// FastPathResult 表示 Fast Path 的判定结果
type FastPathResult struct {
    ID       InstanceID
    Cmd      Command
    Deps     []InstanceID
    Seq      int
    FastPath bool
    Reason   string
}

// runFastPath 模拟 Command Leader 发起 Fast Path
// N=5, F=2, Fast Quorum = floor((3*2+1)/2) + 1 = 4
func runFastPath(replicas []*Replica, leaderIdx int, cmd Command) FastPathResult {
    leader := replicas[leaderIdx]

    // 分配 InstanceID
    leader.mu.Lock()
    instID := InstanceID{Replica: leader.id, Instance: leader.nextInst}
    leader.nextInst++
    leader.mu.Unlock()

    // Leader 自己先计算依赖
    leaderDeps, maxSeq := leader.findConflicts(cmd, instID)
    leaderSeq := maxSeq + 1

    // 记录到本地
    leader.mu.Lock()
    leader.instances[instID] = &InstanceState{Cmd: cmd, Deps: leaderDeps, Seq: leaderSeq}
    leader.mu.Unlock()

    fmt.Printf("  Leader R%d: deps=%s seq=%d\n", leader.id, depsString(leaderDeps), leaderSeq)

    // 发送 PreAccept 到其他 Replica，收集回复
    type reply struct {
        replica int
        deps    []InstanceID
        seq     int
    }
    var replies []reply

    for i, r := range replicas {
        if i == leaderIdx {
            continue
        }
        deps, seq := r.handlePreAccept(instID, cmd, leaderDeps, leaderSeq)
        replies = append(replies, reply{replica: r.id, deps: deps, seq: seq})
        fmt.Printf("  R%d reply: deps=%s seq=%d\n", r.id, depsString(deps), seq)
    }

    // 判定 Fast Path
    // Fast Quorum = floor((3F+1)/2) + 1，F=2 时为 4
    // Leader 自己算一票，所以需要 3 个 Replica 返回相同的 deps 和 seq
    N := len(replicas)
    F := (N - 1) / 2
    fastQuorum := (3*F+1)/2 + 1
    needed := fastQuorum - 1 // Leader 自己是一票

    matchCount := 0
    for _, r := range replies {
        if depsEqual(r.deps, leaderDeps) && r.seq == leaderSeq {
            matchCount++
        }
    }

    result := FastPathResult{
        ID:  instID,
        Cmd: cmd,
    }

    if matchCount >= needed {
        result.FastPath = true
        result.Deps = leaderDeps
        result.Seq = leaderSeq
        result.Reason = fmt.Sprintf("一致回复 %d/%d (需 %d)", matchCount+1, N, fastQuorum)
    } else {
        // Slow Path: 合并所有依赖
        allDeps := leaderDeps
        maxS := leaderSeq
        for _, r := range replies {
            allDeps = mergeDeps(allDeps, r.deps)
            if r.seq > maxS {
                maxS = r.seq
            }
        }
        result.FastPath = false
        result.Deps = allDeps
        result.Seq = maxS
        result.Reason = fmt.Sprintf("一致回复 %d/%d (需 %d), 退化 Slow Path",
            matchCount+1, N, fastQuorum)
    }

    return result
}

func main() {
    // 5 个 Replica，F=2
    replicas := make([]*Replica, 5)
    for i := range replicas {
        replicas[i] = NewReplica(i)
    }

    fmt.Println("=== 场景 1：无冲突命令 ===")
    fmt.Println("提交 Put(x,1) 到 R0：")
    r1 := runFastPath(replicas, 0, Command{Op: "Put", Key: "x", Val: "1"})
    printResult(r1)

    fmt.Println("\n提交 Get(y) 到 R2（与 Put(x,1) 不冲突）：")
    r2 := runFastPath(replicas, 2, Command{Op: "Get", Key: "y"})
    printResult(r2)

    fmt.Println("\n=== 场景 2：有冲突命令 ===")
    fmt.Println("提交 Put(x,2) 到 R1（与 Put(x,1) 冲突）：")
    r3 := runFastPath(replicas, 1, Command{Op: "Put", Key: "x", Val: "2"})
    printResult(r3)

    fmt.Println("\n=== 场景 3：制造 Slow Path ===")
    fmt.Println("先向 R3 单独注入一个命令（模拟部分 Replica 看到额外状态）：")
    extraID := InstanceID{Replica: 3, Instance: 99}
    replicas[3].mu.Lock()
    replicas[3].instances[extraID] = &InstanceState{
        Cmd: Command{Op: "Put", Key: "z", Val: "secret"},
        Seq: 10,
    }
    replicas[3].mu.Unlock()
    fmt.Println("  R3 本地有额外命令: Put(z,secret)")
    fmt.Println("\n提交 Put(z,3) 到 R0（R3 看到额外冲突，其他 Replica 看不到）：")
    r4 := runFastPath(replicas, 0, Command{Op: "Put", Key: "z", Val: "3"})
    printResult(r4)
}

func printResult(r FastPathResult) {
    path := "Fast Path ✓"
    if !r.FastPath {
        path = "Slow Path ✗"
    }
    fmt.Printf("  → %s [%s] cmd=%s deps=%s seq=%d\n",
        r.ID, path, r.Cmd, depsString(r.Deps), r.Seq)
    fmt.Printf("    原因: %s\n", r.Reason)
}

运行这段代码的预期行为：

• 场景 1：两个不冲突的命令分别走 Fast Path 提交，因为所有 Replica 对依赖的判断一致。
• 场景 2：Put(x,2) 与已提交的 Put(x,1) 冲突，但只要所有 Replica 一致地识别出这个冲突，依然可以走 Fast Path——只是依赖集合不再是空集。
• 场景 3：R3 本地有一个其他 Replica 没见过的命令。当提交 Put(z,3) 时，R3 的依赖集合比其他 Replica 多一个条目，依赖不一致，被迫走 Slow Path。

这个模拟清楚地展示了 EPaxos Fast Path 的核心判定逻辑：不是看命令有没有冲突，而是看所有 Replica 是否对冲突的判断达成一致。

四、对比分析：Raft vs Multi-Paxos vs EPaxos vs Flexible Paxos

消息复杂度

Raft 和 Multi-Paxos 的正常路径消息复杂度相同：Leader 向 N-1 个节点发送消息，等 F 个回复（多数 Quorum 减去自己），总共 2(N-1) 条消息。EPaxos 的 Fast Path 消息数量相同（PreAccept 发给所有节点），但 Quorum 更大。Flexible Paxos 消息数量相同，但 Phase 2 的 Quorum 可以更小。

从消息数量看，几个协议差别不大。真正的差别在延迟和吞吐。

延迟

EPaxos 的 Fast Path 在客户端直连最近 Replica 时有延迟优势——客户端发请求到最近的 Replica，该 Replica 直接作为 Command Leader 发起 PreAccept，1 个 RTT 后提交。不需要先转发到远端的 Leader。

Flexible Paxos 的优势不同：它不减少 RTT 数量，但减少了每个 RTT 中需要等待的节点数。在跨数据中心场景下，如果 Phase 2 的 Quorum 可以完全在本地数据中心内完成，那么写延迟就只有本地 LAN 的延迟，而不是 WAN 延迟。

吞吐量

EPaxos 是唯一在吞吐量上有结构性优势的协议。因为没有固定 Leader，写负载均匀分布在所有 Replica 上，系统吞吐量是所有 Replica 带宽之和，而不是单个 Leader 的带宽。

但这个优势有前提：工作负载中冲突率低。高冲突工作负载下，EPaxos 的 Slow Path 和复杂的执行排序会成为瓶颈。

容错能力

EPaxos 的 Fast Path Quorum 更大，因此 Fast Path 能容忍的故障数更少。5 节点集群中，Fast Path 需要 4 个节点，只能容忍 1 个故障。Slow Path 退化到标准 Paxos，容忍 2 个故障。

Flexible Paxos 的容错能力取决于配置。写优化配置（Q2=2）下，Phase 2 可以容忍 3 个节点故障，但 Phase 1 只能容忍 1 个。

实现复杂度

这是最容易被忽视、但在工程中最重要的维度。

EPaxos 的实现复杂度比 Raft 高一个数量级。原因：

1. 状态空间大。每个命令有独立的依赖集合和 seq，Replica 之间的状态组合数量远超线性日志。
2. 恢复协议复杂。Raft 的 Leader 选举和日志修复相对简单——新 Leader 把自己的日志强制覆盖到 Follower 上。EPaxos 的恢复需要重建依赖关系，处理多种中间状态。
3. 执行排序非平凡。Tarjan SCC + 拓扑排序 + 确定性排序，比 Raft 的”按索引执行”复杂得多。
4. 测试困难。EPaxos 的 bug 往往隐藏在特定的并发场景中，需要精心设计的对抗性测试用例才能触发。

Flexible Paxos 相比之下改动很小——只是放松了 Quorum 大小的约束。如果你已经有一个正确的 Paxos 实现，改成 Flexible Paxos 主要是配置变更，代码改动量很小。

什么时候该用哪个

Raft / Multi-Paxos：通用选择。如果你的工作负载没有明显的 Leader 瓶颈问题（大多数系统都没有），Raft 是最安全的选择。实现成熟、调试工具丰富、社区支持好。

EPaxos：理论上适合高吞吐、低冲突、地理分布式的工作负载。实际上因为没有成熟的生产实现，目前更适合学术研究和原型验证。如果你的系统确实受限于 Leader 的吞吐瓶颈，可以考虑 Multi-Raft（分区后每个分区一个 Raft 组）作为更实际的替代方案。

Flexible Paxos：适合跨数据中心部署、写延迟敏感的场景。改动量小，风险可控。如果你已经有 Paxos 基础的系统，Flexible Quorum 是一个低风险的优化手段。

五、EPaxos 的后续发展

EPaxos 提出后，学术界在这个方向上有一些后续工作。

Mencius（2008，实际上早于 EPaxos）：另一种无主共识协议。它的思路不同于 EPaxos——Mencius 预先把日志槽位轮流分配给各个 Replica（类似轮转 Leader），每个 Replica 负责自己的槽位。好处是没有依赖图的复杂性，坏处是如果某个 Replica 暂时没有命令要提交，它需要显式地”跳过”自己的槽位，带来额外的延迟。

Atlas（Enes et al., 2020）：可以看作 EPaxos 的简化变体。Atlas 简化了 EPaxos 的执行排序规则，用更严格的依赖追踪换取更简单的实现。但 Atlas 也没有广泛的生产使用。

Tempo（Enes et al., 2021）：在 EPaxos 的基础上引入时钟信息（类似 HLC），用物理时间戳辅助排序，减少依赖图的复杂性。

Compartmentalized Paxos（Whittaker et al., 2020）：不是去掉 Leader，而是把 Leader 的职责拆分到多个组件中（Proxy、Acceptor、Learner 分离），让每个组件可以独立扩展。这是另一种打破 Leader 瓶颈的思路。

这些后续工作反映了一个现实：EPaxos 的核心洞察（冲突命令才需要排序）是正确的，但把这个洞察工程化的代价比预期的大得多。学术界仍在寻找更好的平衡点。

六、总结

Multi-Paxos 和 Raft 用 Leader 换来了简单性：一个节点负责定序，其他节点跟随。代价是 Leader 成为吞吐瓶颈和延迟下限。

EPaxos 去掉了 Leader，让任意节点直接提交命令，用依赖图追踪冲突，用 Tarjan SCC 排序执行。理论性能在低冲突工作负载下比 Multi-Paxos 好得多。但依赖图、Fast/Slow Path 判定、恢复协议、执行排序的实现复杂度极高，已知存在原始论文描述的算法 bug，至今没有成熟的生产实现。

Flexible Paxos 保留了 Leader，但放松了 Quorum 约束：Phase 1 和 Phase 2 的 Quorum 只需要交集非空（Q1 + Q2 > N）。这个改动概念简单、实现代价小，在跨数据中心场景下效果明显——写路径可以完全在本地数据中心完成。

两条路各有取舍。选择哪条路，取决于你的系统瓶颈在哪里：如果瓶颈是单 Leader 的吞吐，EPaxos 方向值得研究，但工程落地要谨慎；如果瓶颈是跨数据中心的写延迟，Flexible Paxos 是一个更务实的选择。

参考资料

论文

• Moraru, I., Andersen, D. G., & Kaminsky, M. (2013). There is more consensus in Egalitarian Parliaments. SOSP ’13. — EPaxos 的原始论文，提出无主依赖图机制。
• Howard, H., Malkhi, D., & Spiegelman, A. (2016). Flexible Paxos: Quorum intersection revisited. OPODIS ’16. — 提出 Q1 + Q2 > N 的 Quorum 放松条件。
• Sutra, P. (2020). On the correctness of Egalitarian Paxos. Information Processing Letters, 156. — 指出 EPaxos 原始论文中的执行排序 bug 并给出修复。
• Ailijiang, A., Charapko, A., Demirbas, M., & Kober, T. (2017). WPaxos: Wide area network flexible consensus. — Flexible Paxos 在跨数据中心场景的应用。
• Enes, V., Baquero, C., Rezende, T. F., Gotsman, A., Perrin, M., & Sutra, P. (2020). State machine replication with high throughput and low latency (Atlas). — EPaxos 的简化变体。
• Whittaker, M., Hellerstein, J. M., & Stoica, I. (2020). Compartmentalized Paxos. — 通过组件拆分打破 Leader 瓶颈。

相关阅读

• Lamport, L. (1998). The Part-Time Parliament. ACM TOCS. — Paxos 的原始论文。
• Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm (Raft). USENIX ATC ’14.

上一篇：Raft 深度重写 ｜ 下一篇：VR 与 PBFT