共识

一句话

共识（consensus）不是「多数投票表决」，而是让一群随时可能崩溃、消息随时可能延迟乱序的机器，对一串操作的顺序达成不可反悔的一致。本章把 Paxos、Raft、Zab 摆在一起讲，而它们最终都收敛成同一个形状：选一个领导者定序，再用多数派把他的日志钉死——所谓「难懂的共识算法」，难的不是选出一个值，是证明已经定下的值永远不会被后来者改写。

Glossary · 术语表

坐标

本章是 Part II「分布式系统」的收官，也是全书终章。上承 Ch9 故障检测（超时判死永远可能误判）、Ch10 领导者选举（选举本身并不保证唯一）、Ch11 复制与一致性、Ch13 分布式事务（2PC 要求全体同意，协调者一倒就全体持锁干等）。这一章把那些各自不完整的零件拼成一个能自证正确的协议，对应现实里 ZooKeeper、etcd、Consul、CockroachDB、TiKV 这类「集群大脑」。

这章要解决什么

前面每一章都留了个缺口：故障检测会把「慢」误判成「死」；选举可能在分区两侧各产生一个领导者；复制日志可能分叉；原子提交要求全体同意，于是一个节点失联就全线阻塞。共识要在这些缺口上给出一个同时满足三条的协议——一致性（不会有两个节点认定不同的值）、有效性（定下的值必须是某个节点真的提过的，不能凭空捏造）、可终止性（最终能定下来）。

前提很残酷：按 FLP 不可能性结论，纯异步网络里只要有一个节点可能崩溃，确定性算法就不可能同时保证安全性与活性。所以实用协议的做法都一样：安全性（不出错）无条件死守，活性（能推进）靠超时和随机化去「大概率」拿到——这就是为什么每个共识实现里都藏着一堆超时参数。

不解决会怎样？拿 Kubernetes 举例：整个集群的真相——哪个 Pod 该跑在哪台机器、Service 的后端有谁、谁持有某把锁——全部存在 3 到 5 个节点的 etcd 里。假如网络分区时两侧各自接受写入并都回「成功」，调度器就会按两份互相矛盾的真相去拉起容器：同一块云盘被两个进程同时挂载写入。共识是整个系统唯一真相的发源地，它错一次，上层所有正确性都跟着失效。

核心内容，讲透

一、换个说法：共识其实是「全序广播」

本章从广播切入，而不是直接扔出 Paxos。尽力广播（best-effort broadcast）只保证「我发出去了」，发送者中途崩溃就有人收得到、有人收不到；可靠广播（reliable broadcast）保证所有正确节点最终都收到，但顺序各不相同；原子广播 / 全序广播（atomic broadcast、total order broadcast）再加一条——所有节点收到的消息顺序完全相同。

关键洞见是：全序广播与共识是等价问题。有了全序广播，把「第一条被广播出来的值」当作被选定的值，就得到共识；反过来，对日志的每一个位置各跑一次共识，就得到全序广播。数据库真正要的从来不是「选一个值」，而是所有副本按同一顺序回放同一串写——所以共识在工程里永远以「复制一份完全一样的日志」的面目出现。ZooKeeper 的 Zab 协议就是照这个思路设计的：以 epoch（纪元号）划分领导权，分发现（新领导者找出最高的那份日志）、同步（推平给多数派）、广播（稳态逐条追加）三阶段。

二、Paxos：两个阶段，分别在干什么

Paxos 把节点分成三种角色（同一台机器可以同时扮演）：提案者（proposer）发起提议，接受者（acceptor）投票并记住状态，学习者（learner）知悉结果。一轮完整的 Basic Paxos 要两个阶段：

• 阶段一 Prepare / Promise：提案者挑一个全局唯一、单调递增的编号 n，问多数派「能接受 n 吗」。接受者若没见过更大的编号就承诺：此后拒绝一切编号小于 n 的消息，并把自己已经接受过的、编号最高的那个值一并回传。
• 阶段二 Accept / Accepted：提案者收齐多数派的承诺后才发出真正的值。但如果任何一条承诺里带回了旧值，提案者必须放弃自己的值，改提那个编号最高的旧值。多数派接受之后，这个值就被「选定（chosen）」。

所以阶段一根本不是投票，而是抢占 + 打听：抢占是给所有在飞的旧提案发一张作废通知，打听是把可能已经定下的历史捞回来。多数派交集保证了这次打听不会漏：任何两个过半数集合必有共同节点，而那个节点记得上一次接受了什么。Paxos 的全部魔法就一句话——后来者不许改写历史，只能接着喊同一句话。

代价也很具体：每定下一个值要 2 轮 RTT + 2 次磁盘持久化；更麻烦的是两个提案者会互相抢占编号，理论上可以无限循环下去（活锁，livelock）。这两条正是下面所有变体的改进动机。

三、Multi-Paxos 与变体家族：把两轮砍成一轮

Multi-Paxos 的改法朴素而有效：既然每条日志都重跑阶段一太贵，就选出一个特定提案者（distinguished proposer，即领导者），让他对整段日志只做一次阶段一，此后每条命令只剩阶段二的一轮 RTT。领导者靠租约维持身份——这是共识协议里罕见的、依赖物理时钟的地方：租约期内别人不得发起选举，所以时钟漂移必须有界，否则安全性靠的就不再是算法而是运维。

三个值得记住的变体，各自卖掉一样东西换另一样：

• Fast Paxos：让客户端直接把值发给接受者，省掉「先经领导者」那一跳。代价是快速路径的法定人数更大（约 ⌈3N/4⌉ 而非过半），且两个客户端撞车时要回退经典路径重跑一轮——净收益只在冲突率低时成立。
• EPaxos（Egalitarian Paxos）：干脆不要固定领导者，每条命令携带它依赖的命令集合；改不同键的命令互不冲突，可以乱序执行，只有真冲突的才需要排序。好处是没有单点瓶颈、跨地域可就近提交；代价是依赖图与恢复路径相当复杂，冲突一多反而更慢。
• Flexible Paxos（FPaxos）：Howard 等人 2016 年的观察——Paxos 真正需要的并不是「每个法定人数都过半」，而只是阶段一的集合与阶段二的集合必须相交，即 |Q1| + |Q2| > N。于是 N=4 时可取 Q1=3、Q2=2：稳态写只等 2 个节点确认，把成本挪到了「很少发生」的选举那一次上。

四、Raft：把共识写成能照着实现的说明书

Raft 的设计目标不是更快，而是可理解——作者明说，Paxos 的描述与一个真正能跑的系统之间差距太大，以至于每个团队都在各自发明细节。Raft 用三件事把这些细节钉死：

• 任期（term）是逻辑时钟：单调递增，每个任期至多一个领导者。所有消息都带任期号，任何节点一看到更大的任期号就立刻退位成跟随者——老领导者只要一开口，就会被告知自己已经下台。
• 只有三种状态与一条数据流向：跟随者 / 候选人 / 领导者；选举超时随机化（论文建议在 150–300ms 区间内随机取值）以打破平票，典型故障切换在几百毫秒级完成。日志只从领导者单向流向跟随者，跟随者冲突的尾巴直接截断重写——没有「互相合并」这回事。
• 选举限制：候选人的日志若比投票者旧，投票者就拒绝投票。于是只有「日志至少和多数派一样新」的节点才能当选，已提交的条目必然在新领导者手里。Paxos 里最烧脑的「把可能已选定的旧值打听回来」，被 Raft 挪到选举这一刻一次性解决了。

五、拜占庭共识：当节点开始说谎

前面所有协议都假设崩溃-停止：节点要么正确，要么沉默。拜占庭故障则允许节点发出任意、互相矛盾的消息——被入侵、固件错误，或根本就是敌对参与方。PBFT 的代价直观可见：要容忍 f 个叛徒需要 3f+1 个节点（崩溃模型只要 2f+1），三阶段消息 pre-prepare / prepare / commit，消息量随节点数呈 O(N²) 增长。结论也很清楚：在自家机房、同一组织内运维的集群里，拜占庭假设通常不划算；它真正的舞台是互不信任的参与方，区块链即是其工业化版本。

关键权衡与选型

所有方案的安全性保证是一样的（不会出现两个互相矛盾的已提交值），差别全在谁定序、稳态要几轮、以及实现有多难写对。

集群要几个节点？多一倍节点并不等于多一倍好——写延迟取决于「第几快的那个节点」。

跨地域部署时这张表会变得很刺眼：三个可用区之间 RTT 约 1–3ms，共识写还能接受；一旦把副本摊到跨大洲（RTT 70–150ms），每次写都要等一个跨洋往返——这正是 Spanner 要用 TrueTime、EPaxos 要做「就近提交」的原因。

为什么重要 / 落到真实系统

共识在工程里的正确用法，可以浓缩成一句：让它管「小而贵」的东西，别让它管「大而多」的东西。小而贵指的是元数据与领导权——谁是分片的主、配置是什么、锁被谁持有。Kubernetes 把整个集群的真相放进 etcd，但那通常只有几十 MB 到几 GB，业务数据走的是另一条复制路径。一旦把每个业务写都塞进一个共识组，吞吐就被领导者的落盘速度加一次多数派 RTT 死死卡住。

工业界的标准解法是分组：CockroachDB 与 TiKV 把数据切成大量范围（CockroachDB 默认每个范围约 64MB），每个范围跑一个独立的 Raft 组，成千上万个组并行推进，于是集群吞吐随节点数增长，而每个组内部仍是教科书式的 Raft。另一个常见优化是租约读：持租副本本地应答读请求，不必为每次读再跑一轮共识。

易错点与争议

• 「共识就是多数投票的民主」——最常见的误解。多数派在这里的作用是集合交集而不是民意；Paxos 的提案者经常被迫放弃自己的值、改提别人的值，这恰恰是算法正确的来源。
• 「Raft 比 Paxos 快」——两者的安全性保证和稳态消息轮数基本相同，Raft 的卖点是可理解性与可实现性，不是性能。拿它去赢性能辩论属于张冠李戴。
• 「选出了领导者就不会脑裂」——共识只保证新领导者合法，不保证旧领导者立刻知道自己已下台。一次长 GC 停顿或网络分区，就足以让老领导者带着过期租约继续写。所以存储层必须认fencing token（带任期号的单调递增凭证），拒绝任期更小的写——这一条在生产事故里反复出现。
• 低估成员变更——Google 在《Paxos Made Live — An Engineering Perspective》（Chandra 等，PODC 2007）里直言，从算法论文到可用系统之间还隔着大量论文没写的工程问题：磁盘损坏、日志压缩、成员变更、以及如何测试。Raft 的单节点变更与 joint consensus 也是早期实现踩坑最多的地方。
• 时代局限——本章成书于 2019 年；此后 multi-raft、只投票不存数据的 witness 副本、Flexible Paxos 的生产化都有推进，但本章的骨架至今没变。

要点