土法炼钢兴趣小组的算法知识备份

【分布式系统百科】05 · 分布式系统的复杂性度量：消息复杂度、轮次复杂度与空间下界

2026-04-13 · distributed · #complexity #message-complexity #round-complexity #lower-bound #consensus #leader-election #distributed-systems

文章导航

分类入口
distributed
标签入口
#complexity#message-complexity#round-complexity#lower-bound#consensus#leader-election#distributed-systems

目录

你写了一个 Raft 集群，5 个节点，客户端提交一条写请求。Leader 收到请求后，把日志发给 4 个 Follower，等 2 个 ACK（加上自己，达到多数），提交，回复客户端。整个流程走完，网络上一共飞了多少条消息？如果集群扩到 7 个节点、99 个节点呢？延迟会怎么变化？

再换一个场景：你听说 PBFT 能容忍拜占庭故障，打算用它做一个 21 节点的联盟链。结果发现，每提交一笔交易，节点间要互发 O(n^2) 条消息。21 个节点就是上百条消息；扩到 100 个节点，每笔交易要近万条消息在网络上飞。这还能用吗？

顺序算法的复杂性分析已经有成熟的框架：时间复杂度（Time Complexity）衡量计算步数，空间复杂度（Space Complexity）衡量内存消耗。但分布式算法跑在多台机器上，计算不是瓶颈，通信才是。衡量一个分布式算法的”好坏”，需要另一套度量体系：

这四个维度之间存在 trade-off。减少轮次往往要增加消息数；提高容错度往往要增加轮次或消息数；压缩空间往往会牺牲精度或增加通信量。理解这些 trade-off，是设计和选型分布式协议的前提。

这是第一部分（基础模型与核心概念）的最后一篇。从下一篇开始，我们进入第二部分：时间、顺序与因果。

主要协议复杂度速查表

协议 故障模型 消息复杂度 轮次复杂度（正常路径） 空间复杂度（每节点） 容错上限
Paxos（Multi-Paxos，稳定 Leader） 崩溃 O(n) 1 轮 O(日志长度) f < n/2
Raft（稳定 Leader） 崩溃 O(n) 1 轮 O(日志长度) + O(n) Leader 状态 f < n/2
PBFT 拜占庭 O(n^2) 3 轮 O(kn) 并行请求 k f < n/3
EPaxos（无冲突快速路径） 崩溃 O(f) 1 轮 O(日志长度) + 依赖图 f < n/2
EPaxos（有冲突慢速路径） 崩溃 O(n) 2 轮 O(日志长度) + 依赖图 f < n/2

实际集群带宽估算：以一个 5 节点集群（n=5）为例，假设吞吐量为 10,000 ops/sec，每条协议消息平均大小 256 字节：

这组数字清楚地说明了为什么 O(n) 和 O(n^2) 的差距在工程上不是渐近分析的抽象问题，而是”网卡够不够用”的现实问题。

graph LR
    subgraph 轮次复杂度低
        FastPaxos["Fast Paxos<br/>1 轮 / O(n)"]
        Raft["Raft / Multi-Paxos<br/>1 轮 / O(n)"]
    end
    subgraph 轮次复杂度中等
        ClassicPaxos["Classic Paxos<br/>2 轮 / O(n)"]
        EPaxos["EPaxos 慢路径<br/>2 轮 / O(n)"]
    end
    subgraph 轮次复杂度高
        PBFT["PBFT<br/>3 轮 / O(n^2)"]
        HotStuff["HotStuff<br/>3 轮 / O(n)"]
    end

    FastPaxos -. "冲突退回" .-> ClassicPaxos
    Raft -- "同等消息量" --- ClassicPaxos
    PBFT -. "阈值签名优化" .-> HotStuff

上图展示了主要共识协议在轮次复杂度和消息复杂度两个维度上的分布。横向分组体现轮次差异，节点标签包含每次操作的消息量级。可以看到，Fast Paxos 用更大的 quorum 换取了更少的轮次，而 HotStuff 则用密码学聚合将 PBFT 的消息复杂度从 O(n^2) 压缩到 O(n)，但保持了相同的 3 轮结构。

sequenceDiagram
    participant C as 客户端
    participant L as Leader
    participant R1 as 副本1
    participant R2 as 副本2
    participant R3 as 副本3

    rect rgb(230, 245, 255)
    Note over C,R3: Paxos / Raft（稳定 Leader，1 轮）
    C->>L: 请求
    L->>R1: Propose
    L->>R2: Propose
    L->>R3: Propose
    R1-->>L: ACK
    R2-->>L: ACK
    Note right of L: 收到多数 ACK，提交
    L-->>C: 响应
    end

    rect rgb(255, 235, 235)
    Note over C,R3: PBFT（3 轮）
    C->>L: 请求
    L->>R1: Pre-prepare
    L->>R2: Pre-prepare
    L->>R3: Pre-prepare
    Note over L,R3: 第1轮结束
    R1->>L: Prepare
    R1->>R2: Prepare
    R1->>R3: Prepare
    R2->>L: Prepare
    R2->>R1: Prepare
    R2->>R3: Prepare
    R3->>L: Prepare
    R3->>R1: Prepare
    R3->>R2: Prepare
    Note over L,R3: 第2轮结束（全互联 n^2 消息）
    R1->>L: Commit
    R1->>R2: Commit
    R1->>R3: Commit
    R2->>L: Commit
    R2->>R1: Commit
    R2->>R3: Commit
    Note over L,R3: 第3轮结束
    L-->>C: 响应
    end

上图直观地对比了 Paxos/Raft 和 PBFT 的消息时间线。Paxos/Raft 在稳定 Leader 下只需要 1 轮通信（Leader 广播 + 收 ACK），而 PBFT 需要 3 轮，其中 Prepare 和 Commit 阶段的全互联广播产生 O(n^2) 条消息。轮次差距直接导致延迟差距：在跨数据中心（RTT = 50ms）场景下，Paxos 的单次共识延迟约 50ms，PBFT 至少 150ms。

一、为什么顺序算法的复杂性分析不够用

顺序算法跑在一台机器上，所有操作共享同一块内存，访问任意变量的代价是 O(1)。分析复杂度时，只需数”执行了多少条指令”和”用了多少额外内存”。

分布式算法的世界不一样。几个关键差异：

没有共享内存。 节点之间的唯一通信方式是发消息。读取另一个节点的状态，不是一次内存访问，而是一个网络往返。消息可能丢失、乱序、重复。

没有全局时钟。 不存在一个所有节点都认同的”现在是第几步”。各节点独立推进，唯一的同步手段是消息交换。“算法执行了多少步”这个问题本身就需要重新定义。

部分故障。 顺序算法要么整体跑完，要么整体崩溃。分布式系统可能有些节点活着、有些死了、有些慢得像死了一样。算法必须在部分节点故障的情况下继续工作，这种容错能力本身就是复杂性的一个维度。

这三个差异催生了分布式复杂性分析的三个核心指标：消息复杂度应对”没有共享内存”，轮次复杂度应对”没有全局时钟”，容错度应对”部分故障”。

计算模型

讨论复杂度需要先明确计算模型。分布式计算理论中最常用的两个模型：

同步模型（Synchronous Model）：通信有已知的上界延迟。算法按”轮次”推进——每一轮中，每个节点发送消息、接收消息、做本地计算。轮次复杂度在这个模型里有精确定义。

异步模型（Asynchronous Model）：消息延迟没有上界，但假设消息最终会到达。没有天然的”轮次”概念，轮次复杂度需要通过消息依赖链来间接定义。

现实中的分布式系统（如 Raft、Paxos）通常工作在半同步模型（Partially Synchronous Model）下：大部分时间表现得像同步系统，但偶尔会出现任意长的延迟。这个模型下的复杂度分析要同时考虑正常情况（common case）和最坏情况（worst case）。

二、消息复杂度

定义

消息复杂度衡量的是：完成一次协议操作（比如一次共识决议、一次选主），所有节点之间总共需要交换多少条消息。通常用节点数 n 的函数来表示。

这里的”消息”是逻辑层面的。一条消息可能包含一个字节，也可能包含几兆字节的日志数据。如果消息大小差异显著，还需要结合比特复杂度（Bit Complexity）来分析——但多数协议分析中，按”条”计数已经足够说明问题。

选主问题：从 O(n^2) 到 O(n log n)

选主（Leader Election）是最简单的分布式协调问题之一：n 个节点中选出一个公认的 Leader。它的消息复杂度因算法设计而差异很大。

朴素方案：全互联广播。 每个节点把自己的 ID 广播给所有其他节点，每个节点选 ID 最大的作为 Leader。每个节点发 n-1 条消息，总共 n(n-1) = O(n^2) 条消息。简单粗暴，但扩展性差。

环上的 LCR 算法。 LeLann-Chang-Roberts 算法假设节点组成一个单向环。每个节点把自己的 ID 沿环传递；收到一个 ID 时，如果比自己大就继续转发，否则丢弃。最大 ID 的消息会绕环一圈回到发起者，该节点宣布自己是 Leader。

LCR 的消息复杂度：最坏情况下 O(n^2)。考虑 ID 按从小到大顺序排列在环上的情况——最小的 ID 走 1 步被丢弃，第二小的走 2 步……最大的走 n 步。总消息数是 1 + 2 + … + n = n(n+1)/2。

Hirschberg-Sinclair 算法。 HS 算法把搜索范围按 2 的幂次扩展：第 k 轮中，每个节点向两个方向各发送探测消息，最远到达 2^k 跳。如果探测范围内自己的 ID 最大，进入下一轮；否则退出竞选。

HS 的消息复杂度：O(n log n)。每轮中，存活的候选者数量至少减半（因为每 2^k 个节点中最多一个存活），所以最多 O(log n) 轮。每轮中每个候选者发送 O(2^k) 条消息，但候选者数量是 O(n/2^k)，所以每轮的总消息数是 O(n)。O(log n) 轮乘以每轮 O(n)，得到 O(n log n)。

这个结果是最优的：Attiya 和 Welch 在 Distributed Computing: Fundamentals, Simulations, and Advanced Topics 中给出了证明——在匿名环（节点不知道环大小）的比较模型下，选主的消息复杂度下界是 Omega(n log n)。HS 算法达到了这个下界。

共识问题的消息复杂度

共识（Consensus）比选主复杂得多：所有正确的节点要就某个值达成一致，且一旦决定不可更改。

Paxos / Raft 的正常路径：O(n)。 在有稳定 Leader 的情况下，一次共识操作的消息流如下：

  1. Leader 向 n-1 个 Follower 发送 Propose / AppendEntries：n-1 条消息
  2. 每个 Follower 回复 ACK：n-1 条消息

总计 2(n-1) = O(n) 条消息。Leader 等到多数 ACK（即 f+1 个，其中 f = (n-1)/2）就可以提交。

注意：这是 stable leader 下的 common case。如果发生 Leader 选举，Raft 还要额外消耗 O(n) 条消息（RequestVote + 回复）。如果发生多轮选举失败（split vote），选举消息会叠加，但每轮仍是 O(n)。

下界：Omega(n)。 Dolev 和 Reischuk 在 1985 年的论文 Bounds on Information Exchange for Byzantine Agreement 中证明了：在 n 个节点中有 f 个可能发生拜占庭故障的情况下，达成共识至少需要 Omega(n + f^2) 条消息。当 f = O(1) 时下界就是 Omega(n)；当 f = Theta(n) 时下界是 Omega(n^2)。

对于崩溃故障（Crash Failure）模型，共识的消息复杂度下界是 Omega(n)。Paxos 和 Raft 的 O(n) 已经达到了这个下界。

PBFT：O(n^2)。 PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错）要容忍拜占庭故障——节点可能发送恶意消息。PBFT 的正常路径分三个阶段：

  1. Pre-prepare：Leader 向所有 Replica 广播提案，O(n) 条消息
  2. Prepare：每个 Replica 向所有其他 Replica 广播 Prepare 消息，O(n^2) 条消息
  3. Commit：每个 Replica 向所有其他 Replica 广播 Commit 消息，O(n^2) 条消息

总计 O(n^2)。Prepare 和 Commit 阶段的全互联广播是 PBFT 消息复杂度的瓶颈。这也是 PBFT 难以扩展到大规模网络的根本原因。

为什么 PBFT 需要全互联广播？因为在拜占庭模型中，Leader 本身可能是恶意的。节点不能仅靠 Leader 的消息来确认提案——它们需要直接听到其他节点的声音，确认”大家收到的提案是同一个”。这种互相确认的需求天然导致 O(n^2) 的消息量。

HotStuff：O(n)。 HotStuff（Yin 等人，2019）的关键创新是用阈值签名（Threshold Signature）把全互联广播变成了星型通信。每个节点把投票（带签名）发给 Leader，Leader 收集到足够多的签名后，聚合成一个聚合签名（Aggregate Signature），再广播给所有节点。每个阶段的通信模式是 n 条消息（n-1 条投票到 Leader + 1 条聚合结果广播），而不是 n^2 条全互联消息。

HotStuff 用三轮投票（Prepare、Pre-commit、Commit）完成一次共识，每轮 O(n) 消息，总计 O(n)。代价是引入了密码学运算（阈值签名的生成和验证），以及对 Leader 的更强依赖——Leader 成为通信瓶颈。

消息复杂度汇总

协议 故障模型 消息复杂度（每次操作） 说明
LCR 选主 崩溃 O(n^2) 最坏 环上单向传递
HS 选主 崩溃 O(n log n) 双向探测，倍增范围
Paxos / Raft 崩溃 O(n) 稳定 Leader 下
PBFT 拜占庭 O(n^2) 全互联广播
HotStuff 拜占庭 O(n) 阈值签名聚合

三、轮次复杂度

定义

轮次复杂度（Round Complexity）衡量的是：从协议发起到结束，需要经过多少个”通信轮次”。在同步模型中，一个轮次就是一次全局的”发送-接收”步骤。在异步模型中，轮次通常定义为消息因果链的最长长度。

轮次复杂度直接影响延迟。如果每个轮次的网络延迟是 d，那么 k 轮的协议延迟至少是 k * d。注意，这里的 d 不等于单次 RTT——一个轮次可能涉及多条消息的发送和接收。

Paxos 的两轮与 Fast Paxos 的一轮

Classic Paxos：2 轮。 一次正常的 Paxos 共识操作分两个阶段：

Phase 1（Prepare）：Proposer 发送 Prepare(n) 给多数 Acceptor，Acceptor 回复 Promise。这是一个轮次。

Phase 2（Accept）：Proposer 收到多数 Promise 后，发送 Accept(n, v) 给多数 Acceptor，Acceptor 回复 Accepted。又一个轮次。

总计 2 轮。在有稳定 Leader 的 Multi-Paxos 中，Phase 1 可以预先执行一次然后复用，后续操作只需要 Phase 2 的 1 轮。这就是 Multi-Paxos（以及 Raft）在稳定状态下的延迟：1 轮（Leader 发日志 + 收 ACK）。

但严格来说，从客户端的视角，一次完整操作是：客户端发请求给 Leader（半个 RTT）+ Leader 发日志给 Follower 并等 ACK（1 RTT）+ Leader 回复客户端（半个 RTT）= 2 个半 RTT。实际工程中通常说”一次 Raft 写操作需要 1 个 RTT”，指的是 Leader 与 Follower 之间的通信轮次。

Fast Paxos：快速路径 1 轮。 Lamport 在 2006 年的论文 Fast Paxos 中提出了一种优化：在没有冲突的情况下，客户端直接把提案发给所有 Acceptor，Acceptor 直接 Accept，不需要 Prepare 阶段。一轮就能完成。

代价是什么？

  1. 需要更大的 quorum。 Classic Paxos 的 quorum 大小是 floor(n/2) + 1。Fast Paxos 的快速轮次需要的 quorum 大小是 floor(2n/3) + 1（即至少 2/3 的节点回复）。这意味着容错度从 f < n/2 降低到 f < n/3。
  2. 冲突时退回两轮。 如果多个客户端同时提交了不同的值，Acceptor 会收到冲突的提案。此时需要一个 Coordinator 介入，回到经典的两阶段协议来解决冲突。冲突越频繁，Fast Paxos 的优势越小。

这是轮次复杂度与容错度之间的一个经典 trade-off：减少一轮通信延迟，必须接受更低的容错能力或更大的 quorum。

轮次下界

在崩溃故障模型下，达成共识至少需要多少轮？

同步模型中的下界。 Fischer 和 Lynch 在 1982 年证明了：在同步模型中，如果最多有 f 个节点可能崩溃，达成共识至少需要 f+1 轮。直觉是：每轮中最多”暴露”一个故障节点的信息，要确认 f 个节点都没故障，至少需要 f+1 轮。

对于实际系统：如果 n=5, f=2，理论下界是 3 轮。但 Paxos/Raft 在稳定 Leader 下只需要 1 轮——这不矛盾吗？因为 Fischer-Lynch 的下界针对的是最坏情况（可能不断有节点崩溃），而实际系统的 common case 是没有故障、有稳定 Leader。在有故障发生时（Leader 崩溃、重新选举），轮次确实会增加。

异步模型中的不可能性。 FLP 不可能定理（Fischer, Lynch, Paterson, 1985）表明：在纯异步模型中，即使只有一个节点可能崩溃，也不存在确定性算法能在有限轮次内保证终止。所以异步模型中的共识协议（如 Paxos）只能保证 Safety，不能保证在最坏情况下 Liveness——它可能需要无限轮才能终止。工程实践中靠随机化超时和 Leader 机制来打破这个不可能性。

延迟不只是 RTT

一个常见的误解是”分布式系统的延迟就是 RTT”。实际的端到端延迟包括：

在跨数据中心的部署中，单次 RTT 可能是几十到上百毫秒。此时一轮和两轮的差距就不是理论兴趣，而是直接影响用户体验的工程问题。Google Spanner 选择在全球部署中使用 TrueTime + 2PC 而不是经典 Paxos，正是因为对跨洲 RTT 非常敏感。

四、空间复杂度与状态膨胀

定义

分布式算法的空间复杂度衡量每个节点需要维护多少本地状态。与顺序算法不同，分布式系统的空间使用有两个特殊关切：

  1. 随节点数增长的状态：某些元数据的大小与集群中的节点数 n 成比例。
  2. 随操作历史增长的状态：某些协议需要保留历史信息来解决冲突或保证正确性，状态会随时间不断膨胀。

共识协议的空间需求

Raft 的状态。 每个 Raft 节点需要维护的核心状态：

持久化状态（每次更新需写盘）：
  currentTerm    — 当前任期号          O(1)
  votedFor       — 本 term 投给谁      O(1)
  log[]          — 日志条目数组         O(日志总数)

易失状态（所有节点）：
  commitIndex    — 已提交的最大 index   O(1)
  lastApplied    — 已应用的最大 index   O(1)

易失状态（仅 Leader）：
  nextIndex[]    — 每个 Follower 的下次发送 index  O(n)
  matchIndex[]   — 每个 Follower 已匹配的 index    O(n)

Leader 的 nextIndex[] 和 matchIndex[] 大小是 O(n)，随节点数线性增长。但在实际的 Raft 集群中 n 通常是 3、5、7，这部分开销可以忽略。

真正的空间瓶颈是日志本身。日志会随操作不断增长，Raft 通过快照（Snapshot）机制来截断历史日志：当日志长度超过阈值时，把当前状态机状态持久化为快照，然后丢弃快照之前的日志。快照机制把空间复杂度从 O(操作总数) 降低到 O(状态大小 + 增量日志)。

PBFT 的状态。 PBFT 节点需要维护额外的状态来支持视图变更（View Change）：

这意味着每个待处理的请求，节点要存储 O(n) 条签名消息。如果并行处理 k 个请求，空间是 O(kn)。

向量时钟的 O(n) 问题

向量时钟（Vector Clock）是追踪因果关系的经典机制。每个节点维护一个长度为 n 的向量，记录它知道的每个节点的逻辑时间。每条消息都需要携带完整的向量。

当 n 很大时，这个开销不可接受。100 个节点的集群，每条消息要附带 100 个时间戳。1000 个节点就是 1000 个。这是向量时钟在大规模系统中不实用的根本原因。

实际系统的应对策略：

CRDT 的元数据膨胀

CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）的空间问题更为严重。以 OR-Set（Observed-Remove Set，可观测删除集合）为例：

每次添加一个元素，需要生成一个全局唯一的标签（通常是节点 ID + 本地计数器）。删除一个元素时，不是真正删除，而是把它的标签标记为”墓碑”（Tombstone）。如果不做 GC，墓碑会无限积累。

OR-Set 的空间复杂度：O(添加操作总数)，而不是 O(集合当前大小)。一个元素被添加、删除、再添加 1000 次，OR-Set 会保留 1000 个标签的历史。

Delta-state CRDT 通过只传输增量变化来减少通信量，但本地状态的膨胀问题依然存在。GC 需要全局协调（确认所有节点都已经收到某个状态之后才能安全丢弃），而全局协调又违背了 CRDT “不需要协调”的初衷。这是 CRDT 工程化中最棘手的问题之一，后续 CRDT 系列文章会详细讨论。

五、下界：不可突破的理论底线

下界（Lower Bound）告诉我们：无论算法怎么设计，某些成本是无法避免的。理解下界能防止我们在不可能的方向上浪费精力。

共识的消息下界

崩溃模型下的 Omega(n)。 直觉上，要让 n 个节点达成共识，至少需要让所有正确的节点知道决定的值。即使用树形广播（Leader 告诉几个节点，它们再转告其他节点），总消息数也至少是 n-1 = Omega(n)。

更严格的论证来自 Attiya 和 Welch 的教材：在可能有 f 个崩溃故障的模型中，达成共识至少需要 n-1 条消息（如果不允许任何故障）或更多（如果要容忍故障）。Paxos 和 Raft 在 stable leader 下达到了 O(n)，已经是最优的。

拜占庭模型下的 Omega(n + f^2)。 Dolev 和 Reischuk（1985）证明的这个下界意味着：如果要容忍 f = Theta(n) 个拜占庭故障（如 f = n/3 - 1），消息复杂度的下界就是 Omega(n^2)。PBFT 的 O(n^2) 在这个意义上也是最优的。

HotStuff 看起来打破了这个下界——它只需要 O(n) 条消息就能容忍拜占庭故障。矛盾吗？不矛盾。HotStuff 使用了阈值签名，这是一种密码学工具。Dolev-Reischuk 下界的前提是”原始的点对点消息”模型——每条消息只能由发送者签名。阈值签名允许把 n 个签名聚合成一个，相当于用计算换通信。下界被”绕过”而不是被”打破”。

广播的消息下界

可靠广播（Reliable Broadcast）：一个节点要把一个值发给所有其他节点，保证所有正确的节点要么都收到，要么都不收到。

在无故障的情况下，最优方案是树形广播，总消息数 n-1。

在 f 个崩溃故障的情况下，可靠广播至少需要 2f + (n-f-1) = n + f - 1 条消息。直觉是：需要额外的消息来检测和应对发送者的崩溃。

选主的消息下界

在比较模型（Comparison Model）下的异步环上，选主的消息复杂度下界是 Omega(n log n)，由 Burns 在 1980 年证明。HS 算法达到了这个下界。

这个下界只在特定模型下成立。如果允许使用节点 ID 的数值信息（而不仅仅是比较大小），或者网络拓扑不是环，可能有更高效的算法。

容错的节点数下界

容忍 f 个崩溃故障至少需要 2f + 1 个节点。这是因为需要在故障节点不参与的情况下仍然能形成多数派，而多数派之间必须有交集（至少一个正确节点同时参与了两次决议）。

容忍 f 个拜占庭故障至少需要 3f + 1 个节点。额外的 f 个节点是用来”中和”拜占庭节点的恶意投票——即使 f 个节点投了恶意票，另外 f 个正确节点的票加上第三组 f+1 个正确节点的票仍然能形成多数。

这两个下界是分布式容错理论中最基本的结果，分别由 Lamport 等人在 1982 年的论文 The Byzantine Generals Problem 中给出严格证明。

六、实际系统的复杂度分析

理论分析给出的是渐近复杂度。工程实践中更关心的是具体的常数和实际瓶颈。

Raft 的实际消息开销

以一个 5 节点 Raft 集群为例，分析一次正常写操作的消息数：

稳定状态下一次写操作：
  Leader → 4 Followers: AppendEntries   = 4 条消息
  2 Followers → Leader: ACK（达到多数即可） = 2 条消息（最少）到 4 条（全部回复）
  总计：6 到 8 条消息

心跳（空 AppendEntries），假设 100ms 一次：
  Leader → 4 Followers: 4 条消息
  4 Followers → Leader: 4 条消息
  每秒心跳消息：80 条

Leader 选举（一次）：
  Candidate → 4 节点: RequestVote  = 4 条消息
  回复:                            = 4 条消息
  新 Leader 心跳宣告:               = 4 条消息
  总计：约 12 条消息

注意：实际实现中，Raft 通常做批处理（Batching）——把多个客户端请求打包到一个 AppendEntries 中发送。批处理不改变消息条数，但大幅提高吞吐量（每条消息承载更多有效载荷）。

PBFT 的消息爆炸

同样 5 节点（n=5, f=1），PBFT 一次正常操作：

Pre-prepare:  Leader → 4 Replicas  = 4 条消息
Prepare:      每个节点 → 其他 4 个   = 5 × 4 = 20 条消息
Commit:       每个节点 → 其他 4 个   = 5 × 4 = 20 条消息
总计：44 条消息

对比 Raft 的 6~8 条，多了近 6 倍。而且 PBFT 的消息数按 O(n^2) 增长：

n=5:   44 条
n=7:   82 条
n=13:  316 条
n=21:  820 条
n=101: 20,200 条

这就是为什么传统 PBFT 实际部署很少超过几十个节点。

HotStuff 的改进

同样 5 节点（n=5, f=1），HotStuff 一次正常操作：

每轮（共 3 轮，Prepare / Pre-commit / Commit）：
  4 Replicas → Leader: 投票（带签名） = 4 条消息
  Leader → 4 Replicas: 聚合签名       = 4 条消息
  每轮：8 条消息

3 轮总计：24 条消息

虽然轮次比 PBFT 多（3 轮 vs PBFT 正常路径的 3 轮），但每轮的消息数从 O(n^2) 降到了 O(n)。扩展到 n=101 时：

HotStuff: 3 × 2 × 100 = 600 条消息
PBFT:     约 20,200 条消息

差距在大规模集群中极为显著。

协议对比总览

主要分布式协议复杂度对比

上图汇总了本文讨论的主要协议在消息复杂度、轮次和容错能力上的对比。几个关键观察：

七、Trade-off 的本质

分布式系统的复杂性度量之间不是独立的，它们相互制约。

消息 vs 轮次

减少轮次往往需要增加每轮的消息数。Fast Paxos 把轮次从 2 减到 1，方法是让客户端直接把提案广播给所有 Acceptor——这增加了每个客户端的消息发送量。在冲突时回退到两轮路径，消息总量反而更多。

轮次 vs 容错

Fast Paxos 的快速路径需要 2n/3 + 1 的 quorum，比经典 Paxos 的 n/2 + 1 更大。这意味着同样的集群规模下，Fast Paxos 能容忍的故障数更少。

更一般地：Dutta 等人在 2005 年的论文 Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks 中给出了轮次和容错之间的精确 trade-off 关系。

消息 vs 空间

一些协议通过缓存更多状态来减少消息。Multi-Paxos 的 Leader 缓存 Prepare 阶段的结果，后续操作跳过 Prepare，把两轮变成一轮——代价是 Leader 需要维护更多的本地状态，并且 Leader 更换时需要执行完整的两阶段协议来恢复状态。

选择的依据

在实际选型中，复杂度分析提供的判断框架：

场景 关注重点 推荐方向
跨数据中心部署 轮次复杂度（RTT 很大） 减少轮次，接受更高的消息量或更强的硬件
大规模节点（100+） 消息复杂度 避免 O(n^2) 协议，选择 O(n) 方案
高容错需求 容错度 接受更多轮次或更多消息的 trade-off
资源受限环境 空间复杂度 避免向量时钟，使用 HLC 或其他压缩方案
拜占庭环境 消息 + 轮次 HotStuff 优于 PBFT（如果能接受密码学开销）

八、结语

分布式算法的”好坏”不是一个单一的评分，而是一个多维度的 trade-off 空间。消息复杂度、轮次复杂度、空间复杂度和容错度四个维度相互制约，没有一个协议在所有维度上都最优。

理论下界告诉我们哪些成本是无法避免的：崩溃模型下共识至少 O(n) 条消息，拜占庭模型下至少 O(n^2) 条（在点对点通信模型中），比较模型的环上选主至少 O(n log n) 条消息，同步模型下 f 容错的共识至少 f+1 轮。这些下界是协议设计的物理定律——不是当前技术水平的限制，而是信息论层面的根本约束。

工程实践中，渐近复杂度只是起点。批处理、流水线、预计算、密码学聚合等技术手段可以大幅改善实际性能的常数因子，甚至绕过某些下界的前提条件。选择协议时，要结合具体的部署规模、网络延迟、容错需求和计算资源来做权衡。

本篇是”基础模型与核心概念”部分的最后一篇。从下一篇开始，进入第二部分”时间、顺序与因果”——分布式系统中最反直觉的话题。第一个问题：你以为墙上的钟是可靠的？

参考资料

论文 / 书

相关阅读

导航

上一篇：端到端论证

下一篇：物理时钟的谎言

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-04-13 · distributed

【分布式系统百科】Raft 深度重写：从论文的 18 页到 etcd 的 15000 行

Raft 论文 18 页就能读完，但 etcd/raft 用了 15000 行 Go 才把它变成能在生产环境跑的代码。这篇文章从论文的每一个核心机制出发，逐一拆解工程实现中论文没说的东西：PreVote、ReadIndex、LeaderTransfer、ConfChange V2、流水线复制、Async Apply，以及 TiKV 的 Multi-Raft 实践。最后做一次精确的 Paxos 对比，并坦诚讨论 Raft 的已知缺陷。

2026-04-01 · distributed

Raft：让共识算法不再是黑魔法

Paxos 被引用了几千次，能正确实现它的人不超过几十个。Raft 用可理解性换工程落地，它的 Leader Election、Log Replication 和 Safety 三板斧，撑起了 etcd、TiKV 和大半个云原生基础设施。

By .