21.12 共识算法对比
一句话
所有共识算法都在解同一道题——多数派 + 提案编号/任期 + 日志匹配；差别在谁当 leader、日志是否连续、读怎么走、成员变更怎么做，选型看运维与生态，不只看论文里的延迟数字。
共识要解决什么问题、要满足哪三条性质，见 21.1 共识问题定义；这些算法假设的故障类型见 22.1 故障类型。
一张表看全
| 算法 | 角色 | 日志形态 | 提交条件 | 读路径 | 成员变更 | 典型实现 |
|---|---|---|---|---|---|---|
| Basic Paxos | 提议者/接受者/学习者（可重叠） | 单值，无日志 | 多数派接受 | 再做一轮读（或读已决定值） | 未定义 | 教学、Chubby 的底层 |
| Multi-Paxos | 选出稳定 leader 后重复 Paxos | 每个 slot 独立 | 多数派 | leader 读 + 租约 | 复杂（需自行设计） | Spanner、Megastore |
| Raft | leader / follower / candidate | 连续日志（无洞） | 多数派持久化 | ReadIndex / 租约 / 从 leader 读 | 单次变更或联合共识 | etcd、TiKV、CockroachDB |
| ZAB | leader / follower / observer | 连续日志，zxid（epoch+counter） | 多数派 | 从 leader 读（FIFO 客户端顺序） | 需停机或滚动 | ZooKeeper |
| EPaxos | 无固定 leader | 依赖图 + 提交 | 快速路径（无冲突）1 RTT；冲突则 2 RTT | 需解析依赖 | 支持 | 研究原型、部分新系统 |
| PBFT | primary + backup | 序号 + 视图号，三阶段（pre-prepare/prepare/commit） | 2f+1 个 prepare/commit 确认 | 等 commit 后读主副本 | 视图切换 + 成员变更协议 | 联盟链、BFT-SMaRt、Tendermint |
共同点（记住这三条，面试就不会答偏）：
- 只能靠多数派：任何决定必须被
⌊N/2⌋+1个节点持久化，否则会出现两个决定； - 提案必须带编号/任期：编号单调递增，旧 leader 的提案会被拒绝（否则旧提案可能覆盖新提案）；
- 日志匹配/前缀性质：如果两个日志在某个位置相同，那么它们之前的所有位置都相同——这是“已提交不可改”的基础。
Raft 与 Paxos：可理解性不是小事
| 维度 | Multi-Paxos | Raft |
|---|---|---|
| leader 选举 | 论文未规定，工程实现各异 | 任期 + 随机超时，规则明确 |
| 日志 | 允许有洞（slot 可以空） | 必须连续，先补齐再提交 |
| 成员变更 | 未定义，需自己设计 | 单节点变更 / 联合共识，有明确安全性证明 |
| 快照 | 未定义 | InstallSnapshot RPC |
| 客户端交互 | 需要自己处理重复提案 | 线性一致读（ReadIndex/租约）有标准做法 |
| 实现难度 | 高（“Paxos 很难”主要难在这） | 中（论文给全了状态机与 RPC） |
🔑 Multi-Paxos 与 Raft 的安全性等价（都满足共识三性质），差别在工程完备度：Paxos 是“一个可证明的骨架”，Raft 是“一份可直接实现的规范”。这也是 etcd/TiKV 选 Raft 的原因——不是它更快，而是它更不容易实现错。
ZAB 与 Raft：一个容易忽略的差异
ZAB（ZooKeeper Atomic Broadcast）与 Raft 都是“leader 主导 + 多数派 + 连续日志”，但：
| 维度 | ZAB | Raft |
|---|---|---|
| 事务编号 | zxid = (epoch, counter)，全局单调 | (term, index) |
| 恢复阶段 | 选主后要同步（diff/trunc/snap），保证 leader 的日志是最终真相 | 新 leader 通过“日志匹配”隐式压制旧日志 |
| 读 | 客户端 FIFO，读可能陈旧（除非 sync()） | ReadIndex/租约可做线性一致读 |
| 顺序保证 | 全局全序广播（primary order） | 日志全序 |
实践差异：ZooKeeper 的 get 默认可能读到旧值（它保证的是“写线性一致 + 客户端 FIFO”），所以需要强读时要 sync()；这一点常被误读成“ZooKeeper 是强一致的”（48.6 产品 (etcd / Consul / ZooKeeper / Nacos) 有同样的提醒）。
性能：不是“谁快”，而是“RTT 除以批大小”
单 leader 串行提交时，吞吐上限 = 批大小 / RTT，单条延迟 ≈ RTT（批内第一条还要排队）：
package main
import "fmt"
// 单 leader 串行提交：每批要等一次多数派往返
// 吞吐 = 批大小 / RTT；单条延迟 ≈ RTT
func main() {
rtts := []struct {
name string
ms float64
}{
{"同 AZ", 0.5},
{"同城跨 AZ", 1},
{"北京–上海", 30},
{"中美", 180},
}
batches := []int{1, 10, 100, 1000}
fmt.Println("=== 单 leader 串行提交的吞吐上限（ops/s）===")
fmt.Printf("%-14s", "RTT")
for _, b := range batches {
fmt.Printf("%10s", fmt.Sprintf("批=%d", b))
}
fmt.Println()
for _, r := range rtts {
fmt.Printf("%-14s", fmt.Sprintf("%s(%.1fms)", r.name, r.ms))
for _, b := range batches {
fmt.Printf("%10.0f", float64(b)/(r.ms/1000))
}
fmt.Println()
}
fmt.Println("\n=== 单条写入的延迟不会因为批而下降 ===")
for _, r := range rtts {
fmt.Printf("%-14s 提交延迟 ≈ %5.1fms，串行上限 %.0f ops/s\n", r.name, r.ms, 1000/r.ms)
}
}
本机实测（模型计算，RTT 取常见量级）：
=== 单 leader 串行提交的吞吐上限（ops/s）===
RTT 批=1 批=10 批=100 批=1000
同 AZ(0.5ms) 2000 20000 200000 2000000
同城跨 AZ(1.0ms) 1000 10000 100000 1000000
北京–上海(30.0ms) 33 333 3333 33333
中美(180.0ms) 6 56 556 5556
=== 单条写入的延迟不会因为批而下降 ===
同 AZ 提交延迟 ≈ 0.5ms，串行上限 2000 ops/s
同城跨 AZ 提交延迟 ≈ 1.0ms，串行上限 1000 ops/s
北京–上海 提交延迟 ≈ 30.0ms，串行上限 33 ops/s
中美 提交延迟 ≈ 180.0ms，串行上限 6 ops/s
三个结论：
| 结论 | 数字 |
|---|---|
| 跨城单 key 串行提交只有 33 ops/s | 30ms RTT、不批量 |
| 批量是唯一出路 | 批=100 → 3333 ops/s（同样的 RTT） |
| 跨洲做共识几乎必须“分区 + 本地批” | 180ms RTT、批=1000 也只有 5556 ops/s |
⚠️ 这张表解释了一个常见困惑：“为什么 etcd 集群跨城部署后写吞吐掉得这么厉害？”——不是 etcd 慢，是物理 RTT 除以批大小，也就是 PACELC 的 EC 代价（17.4 PACELC）。
拜占庭共识：PBFT 补上那一行
前面的算法都假设“节点只会停，不会撒谎”。PBFT 假设节点可以任意作恶：伪造消息、对不同的副本说不同的话、选择性不发。代价是副本数从 2f+1 跳到 3f+1，消息量从 O(N) 跳到 O(N²)。
| 阶段 | 谁发起 | 收到什么才算过 | 作用 |
|---|---|---|---|
| pre-prepare | primary | 备份接受序号与视图号 | 定序（这一请求在日志的哪个位置） |
| prepare | 每个备份 | 收到 2f 个其他副本的 prepare（含自己共 2f+1） | 确认“多数派看到了同一个序号” |
| commit | 每个副本 | 收到 2f+1 个 commit | 确认“多数派准备执行”，可以回复客户端 |
| view-change | 任一怀疑 primary 的副本 | 收到 2f+1 个 view-change | primary 作恶/失联时换主，保证安全 |
三个数字决定它能不能用：
| 指标 | PBFT | Raft |
|---|---|---|
| 副本数 | 3f+1（f=1 → 4 个） | 2f+1（f=1 → 3 个） |
| quorum | 2f+1 | f+1 |
| 每请求消息 | 约 2n²：n=4 → 32 条，n=7 → 98 条 | 约 2n：n=4 → 8 条 |
| 每请求延迟 | 约 3 个 RTT（pre-prepare / prepare / commit） | 1 个 RTT |
| 30ms RTT 下的写延迟 | 约 90ms | 约 30ms |
为什么公司内部系统几乎不用它：内部节点是“自己的”，故障模型是崩溃而不是拜占庭；用 PBFT 等于为“不存在的敌人”付 3 倍副本 + O(N²) 消息 + 视图切换的复杂度。它真正的主场是跨组织、互不信任的场景（联盟链），那里“节点可能作恶”是前提而不是假设。
⚠️ PBFT 的
O(N²)不是实现问题，是算法结构：每个副本都要向所有副本广播 prepare 与 commit。所以它的集群规模通常只有 4–16 个节点，靠“少而可信的共识组”而不是“多副本”来扩展。
读路径：三种读法，三种一致性
| 读法 | 额外开销 | 保证 | 适合 |
|---|---|---|---|
| 从 leader 直接读 | 0 | 不保证（可能是旧值，甚至脏读） | 只读监控、近似值 |
| ReadIndex | 一次多数派往返（1 RTT） | 线性一致 | 余额、配置、锁 |
| 租约读（lease） | 0（租约内） | 线性一致（依赖时钟假设 ≤ 租约） | 高频强一致读 |
| follower 读（ReadIndex 转发） | 1 RTT（可本地处理） | 线性一致（需向 leader 确认） | 读扩展 |
选型决策表
| 场景 | 推荐 | 理由 |
|---|---|---|
| K8s / 配置 / 服务发现 | etcd（Raft） | 生态成熟，运维工具齐全 |
| 协调、临时节点、watch | ZooKeeper（ZAB） | 会话与 watch 语义成熟 |
| 跨地域强一致数据库 | Spanner 类（Multi-Paxos + TrueTime） | 需要外部一致性，接受延迟 |
| 高吞吐日志复制 | Raft + 批量 | 批大小是吞吐杠杆 |
| 多地写、低冲突 | EPaxos 类 | 无 leader，快速路径 1 RTT |
| 只需要“选一个主” | Raft 选主即可 | 不需要完整日志（选主细节见 48.4 Leader 选举） |
| 数据库主从复制 | 单主 + 日志复制 | 与共识的区别见 44.13 主从复制与读写分离 |
为什么表里没有 PoW
PoW 经常被当成“共识算法之一”，但它解决的是另一个问题：谁有资格参与（Sybil 抵抗），而不是“参与者之间怎么定序”。
| 维度 | PoW 的世界 | Raft / PBFT 的世界 |
|---|---|---|
| 成员 | 开放、匿名、可任意加入 | 已知、可控、有身份 |
| 定序依据 | 算力（最长链） | 任期/视图 + 多数派投票 |
| 最终性 | 概率的：k 个确认后仍可能回滚 | 确定的：提交即终局 |
| 代价 | 能耗、低 TPS、分叉 | 延迟、副本数、协调 |
| 典型场景 | 公链 | 公司内部、联盟链 |
把 PoW 放进这张对比表会让读者误以为“内部系统也能用 PoW 换高可用”——实际上它连“提交即终局”都不保证，和 Raft/PBFT 不是同一类工具。它只在“开放公网 + 无身份 + 需要 Sybil 抵抗”时才是正确答案；而企业里这类需求通常落在联盟链，用的是 PBFT/Tendermint，不是 PoW。故障模型的前提见 22.1 故障类型。
反模式
| 反模式 | 后果 |
|---|---|
| 3 节点跨 3 城部署 | 每次提交 30ms+，任两地抖动就选不出主 |
| 用共识存高频流水 | 单 key 33 ops/s 上限，批量也救不了跨洲 |
| 从 leader 直接读却宣称线性一致 | 新 leader 未提交 no-op 时读到旧值 |
| 自己实现 Multi-Paxos 的成员变更 | 安全性证明缺失，扩容时双主 |
把 ZooKeeper 的 get 当强一致读 | 读到旧值；需要 sync() |
| 忽略日志连续性（Raft 有洞） | 提交位置错乱，状态机不一致 |
| 5 节点全同步、不开批量 | 吞吐与延迟双输 |
自检
Q1 Raft、Multi-Paxos、ZAB 在“安全性”上有什么区别？为什么工程上还选 Raft？
▸ 答案：安全性等价——三者都满足共识三性质（一致性、有效性、终止性），都能保证“已提交的日志不丢、不出现两个决定”。差别在工程完备度：Multi-Paxos 只给了骨架（leader 选举、成员变更、快照、客户端去重都要自己设计），ZAB 绑定 ZooKeeper 的会话/watch 模型，Raft 把状态机、RPC、成员变更、快照、线性一致读都写成了规范。选 Raft 是因为“实现错的概率低、生态与工具成熟”，不是因为它数学上更强。
Q2 跨城 30ms RTT 的三节点 etcd 集群，单 key 写入吞吐上限大约是多少？怎么提高？
▸ 答案：不批量时约 33 ops/s（1 / 0.03s），因为每次提交都要等一次多数派往返，且同一 key 必须串行。提高办法：① 批量（批=100 → 3333 ops/s），把多个写合并进一次往返；② 按 key 分片（不同 key 走不同 Raft group，互不排队）；③ 缩短 RTT（同城部署，把跨城复制交给异步/上层）。加节点没用——延迟由 RTT 决定，不由副本数决定。
Q3 为什么“从 leader 直接读”不能保证线性一致？ReadIndex 做了什么？
▸ 答案：leader 可能在一次网络分区中已经被新 leader 取代，但它自己还不知道，此时直接读会返回旧值（甚至脏读）。ReadIndex 的做法是：读之前先向多数派确认“我仍是 leader”（收集一轮心跳/确认，记录当前 commit index），等本地状态机应用到该 index 后再返回。这样读也付一次多数派往返，换来线性一致。租约读是它的优化：在租约有效期内免掉这次往返，但依赖时钟漂移有上界。
Q4 EPaxos 与 Raft 的核心差别是什么？什么场景值得用它？
▸ 答案：Raft 有固定 leader，所有写都要经过它，跨地域时每次写至少 1 个 RTT 到 leader；EPaxos 无固定 leader，每个副本都能提议，无冲突时快速路径只需 1 个 RTT（就近多数派），有冲突时用依赖图排序、退化为 2 个 RTT。适合多地写、冲突率低的场景（如多地副本各自处理本地 key）；如果写集中在少数热点 key，冲突会让它退化，反而不如 Raft 简单可靠。
Q5 4 个副本的 PBFT 与 4 个副本的 Raft，每请求各需要多少条消息、几个 RTT？为什么公司内部几乎不用 PBFT？
▸ 答案：PBFT 每请求约 2n² = 32 条消息、约 3 个 RTT（pre-prepare / prepare / commit），quorum 是 2f+1 = 3；Raft 每请求约 2n = 8 条消息、1 个 RTT，quorum 是 f+1 = 2。PBFT 多出来的成本是为“节点可能作恶”付的保险费：内部节点是可信的，故障模型是崩溃而非拜占庭，用 PBFT 等于为不存在的敌人付 3 倍副本、O(N²) 消息与视图切换的复杂度。它只在跨组织、互不信任（联盟链）时才值得。