专业书籍精读 · Database Internals · 第 10 章
Database Internals · Ch 10 · Alex Petrov · 2019
一个小组要合作办事，如果每件小事都全组开会表决，那什么也办不成。于是大家推一个人拍板——有事找他，他说了算。你转账、发消息、存照片，背后那几十台机器每天都在干同一件事：推举一台机器当头儿。《Database Internals》第 10 章讲的就是这个动作，以及它为什么比听起来难得多。
最常见的换头儿，不是因为那台机器真坏了，而是它的硬盘忙了一下、回话慢了半秒。别人听不到它吭声，以为它没了，就张罗着重选——它自己毫不知情，还在正常上班。换头儿多半是被误会触发的，不是被故障触发的。
没有头儿，事情办不下去——但坏得很明显，喊一声就有人来修。真正的灾难是同时冒出两个头儿：老的没真死、只是没人听见，新的已经上任。两人同时在同一本账上记账，你那笔钱可能被算两遍，事后还没人知道该信哪一本——两份记录都言之有理。这是整章要防的头号事故。
这一章摊开了几种老办法，一层层递进——
但全章最该记住的不是上面任何一种推举法，而是那枚公章：给每一任头儿刻一枚带届数的章，所有文件只认届数最新的那一枚。于是老头儿睡醒了照样发号施令也没关系——他手里那枚是上一届的，盖出来一律作废。
真正的取舍不是「哪种推举法更聪明」，而是两件事：别老换（换一次全场都要停下来等交接），以及换了之后老头儿必须真的失效。前者靠「没真出事就别动」，后者靠那枚带届数的公章。
诚实的代价是：没有一种推举法能保证「全场永远只有一个头儿」——能做到的只是「乱一阵之后最终只剩一个」。安全网从来不在推举那一步，而在盖章那一步。
推举头儿不难，难的是让上一任彻底作废。所以别指望选举本身选得又快又准——要让每一任都带上届数，让所有人只认最新的那一届；这样即使误会了、一时冒出两个头儿，账也不会被写坏。
想看具体算法、消息开销与示意图？ → 切到精读版
你以为领导者选举（leader election）是「把最合适的那台挑出来」，其实这一章真正的命题是：选举本身根本无法保证「同一时刻只有一个主」。选主是共识（consensus）问题的一个实例，而工程上用的都是比共识更弱、更便宜的算法——它们只承诺「最终收敛到一个主」。于是真正的安全边界被推到了两个地方：稳定性（没真出事就别改选）与世代号（让上一任的写入失效）。
2f+1 台最多容忍 f 台失效；多数派只可能存在于一个分区，这是防双主的根。Part II「分布式系统」的第三章。上承第 9 章故障检测——选举的触发器就是「认定老主死了」，所以检测器的误判率直接等于改选率；下启第 11 章复制（有主才有单点定序）与第 14 章共识（Raft / Multi-Paxos 把选主吃进算法内部）。现实里对应：ZooKeeper 的 leader、etcd 的 Raft leader、Kafka 的 controller 与分区 leader、Kubernetes 控制器的 Lease 抢锁、MySQL 的自动 failover。
先问为什么非要有个主。因为「让 n 个节点对每个操作协商」和「让一个节点直接定序」的成本差一个量级：无主设计里每个写都要跑一轮投票、等多数派回音，同机房两三个来回；有主时客户端一次往返就拿到定序结果。顺序、唯一性、冲突消解全从「要协商的事」退化成「查一下主的记录」。
不解决会怎样？两个方向的代价完全不对称。
没有主：坏得很响。3 节点强一致集群主挂了又选不出来，整个集群直接不可写——不是慢，是彻底停摆。改选空窗就是可用性账单上最直观的一笔：etcd 默认选举超时 1 秒，从「主没了」到「新主能干活」至少几百毫秒到一两秒，期间所有写请求都在排队或报错。
两个主：坏得很静。老主只是被误判（一次长 GC 停顿、一段跨机架抖动），不知道自己已被免职，还在接受写入；新主也在写。两份历史各自自洽，事后无法自动判定谁对——这不是恢复慢，是永久性数据损坏，往往要人工比对账本才能收尾。
所以这一章的真问题不是「哪个算法选得快」，而是：既然触发选举的信号本身就不可靠（第 9 章已证明「慢」与「死」分不开），一个必然会误判的选举机制，怎么才能不把数据写坏？
严格说，「大家一致认为 X 是主」就是一次共识（consensus）——一组节点对某个值达成不可推翻的一致。共识有代价：至少两轮消息、必须凑到多数派、还要持久化。本章的经典算法几乎都刻意绕开这个代价：不凑多数派，只靠「谁编号大」这类局部规则，于是只承诺最终收敛到一个主，不承诺过程中不出现两个。记住这句，后面所有算法就好评价了——它们不是在比谁更正确，而是在比要多少条消息、换主要多久、乱的时候能乱到什么程度。
Bully（霸道算法）是所有变体的起点：每个节点有一个全局可比大小的唯一编号（rank），活着的里面编号最大的当主。谁发现主没了，就向所有比自己大的节点发 ELECTION；有人回话说明还有更大的活着，自己退出；没人回话就广播「我是主」。
为什么这样设计？因为它不需要任何共享状态也不需要持久化——只要编号能比大小、消息能送到就能跑。代价是三个盲点：
O(n²)。二十节点还好，两百节点时一次误判就能掀起几万条消息。Next-In-Line Failover（继任名单）：主在心跳里顺带下发一份按优先级排好的备选名单。主一挂，第一位直接接位，整轮选举被省掉——换主时间从「一轮选举」压缩成「一个超时」。代价很直白：名单是主活着时写的，可能已过期，所以必须允许沿名单往下退，退到底才回落到完整选举。
Candidate / Ordinary（候选人与群众）：只有候选人有资格当主，其余节点只负责发现问题并通知候选人。消息量从全体 O(n²) 降成候选人间 O(k²)——两百节点里设 5 个候选人，一次选举的消息量少两个数量级。代价是候选人集合成了新的单点：5 个全不可用，剩下 195 台健康机器谁也当不了主。
Ring（环算法）：节点排成逻辑环，每个只认自己的后继。选举消息沿环传递，每过一个活节点就追加它的编号；转回起点时名单已齐，取其中最大的当主。优点是消息量线性，且只需「认识下一个」这点拓扑知识。
Invitation（邀请算法）是本章最值得记住的思想转向。前面几种都在保证「全局只有一个主」，它索性承认可以存在多个组：每个进程起初都是自己单人组的主，互相「邀请」加入，组可合并，合并后由其中一个原组主继续当主。于是网络分区不再是异常——两边各自成组照常干活，恢复后再合并。
代价是难题从「选举」搬到了「合并」——两组各有一段独立历史，谁来裁决冲突？这正是 Ch11 里 CRDT 与最终一致性要处理的。取舍一句话：要么牺牲可用性保唯一主，要么牺牲唯一主保可用性、把账留到合并时算。
书里评价每种算法时都回到同一个追问：它会不会导致频繁改选。这是账本问题——每次改选都要停写、等新主补齐日志、等客户端重连重试，一次几百毫秒到数秒；检测器每分钟误判一次，集群就长期半瘫。所以工程第一原则是：老主还在正常干活就绝不改选（稳定领导者，stable leader）。
这也解释了 Bully 那个盲点为什么致命：规则是「最大编号者必须当主」，于是那台最大编号的破机器每次复活都强制触发改选。真实系统一律反过来：现任只要还能续租就继续干。
另一个减震手法是随机化超时：若所有节点同时超时、同时发起选举，票被瓜分谁也拿不到多数，只好重来——这就是活锁。给每个节点的等待时间加一点随机抖动，「谁先发起」就自然错开了。
前面所有算法都无法排除这一幕：老主只是看起来死了（一次 5 秒的 Full GC 就够），新主已上任，老主醒来仍以为自己是主，继续写。既然选举防不住，就换个地方防——给每一任主配一个只增不减的世代号（epoch），随每个写请求带到存储层，存储层只接受见过的最大世代号。
这一步把「保证不出现两个主」这个做不到的要求，换成了「允许两个主，但只有一个改得动数据」这个做得到的要求。老主的写会拿到拒绝，由此知道自己已被免职并主动退位。选举负责活性，世代号负责安全性。书里对世代号的完整处理留到第 14 章——那里 Paxos 的提案编号、Raft 的任期号干的就是这件事。
先横着比。真正区分它们的是分区下会不会出双主，不是快不快。
表 1 · 五种选举思路的代价对照
| 机制 | 消息量 | 换主速度 | 分区下会出双主吗 | 代价 / 适合谁 |
|---|---|---|---|---|
| Bully | O(n²) 最坏 | 一整轮选举 | 会：各分区各选最大者 | 最简单、无需共享状态；但不看能力，最大编号者反复复活会活锁。仅适合小集群 |
| Next-In-Line | 近似 0（名单随心跳带） | 最快，一个超时即接位 | 会 | 名单会过期，要能沿名单下退。适合主从对明确、要压 RTO |
| Candidate / Ordinary | O(k²)，k 为候选人数 | 一轮（仅候选人间） | 会 | 候选人集合成了新单点，全挂就无人可选。适合上百节点 |
| Ring | O(n) 一圈 | 一圈传递，随 n 线性变慢 | 会：切成两个环各选一主 | 环要能修（跳过死节点），拓扑维护是额外负担。适合成员稳定的场景 |
| Invitation | 合并时较高 | 无需全局收敛，本组立即可用 | 刻意允许 | 难题移到合并冲突上。适合可用性优先、能接受最终一致 |
| 共识内建（Raft / Zab） | 一轮多数派投票 | 选举超时量级，etcd 默认 1s | 不会：多数派只存在于一个分区 | 少数派分区完全不可写；需 2f+1 台并持久化状态。绝大多数强一致系统的实际选择 |
落到架构决策上，问题通常不是「用哪个算法」，而是「主放在哪一层」——大多数团队根本不该自己实现选举。
表 2 · 「谁来选主」的三种工程路线
| 路线 | 怎么做 | 能拿到什么 | 要付什么 |
|---|---|---|---|
| 自己实现选举 | Bully / Ring 之类，靠心跳加编号 | 零外部依赖、代码短 | 安全性全靠自己兜：必须自建世代号与 fencing，否则一次分区即数据损坏 |
| 外部租约抢锁 | 在 ZooKeeper / etcd / K8s Lease 上抢一个带 TTL 的键，抢到的当主并持续续租 | 几十行代码，唯一性由外部集群的共识保证；到期自动失效，不必宣判他人死亡 | 多一个必须高可用的依赖；换主时间被租约长度锁死（典型 10–15 秒）；仍不免 fencing |
| 共识算法内建选主 | 直接用 Raft / Multi-Paxos / Zab 的库或产品 | 选举与复制共用一套任期号，安全性可证；可加「日志够新才可当选」这类约束 | 实现与运维复杂度最高；写路径必须过多数派，跨区延迟明显 |
一条能直接带走的经验：任何不可撤销的动作都必须带着世代号去执行——切流量、删数据、扣款。选举给你的只是「我大概是主」，世代号才是「我确实是现任」。
任何「怎么做高可用」的评审或面试题，第二刀必落在这里（第一刀是故障检测）。把「主挂了就重新选一个」答成「现任续租优先、随机化超时避免瓜分选票、候选人要日志够新、执行端带世代号 fencing」，档次立刻不同。
点名几个真家伙：ZooKeeper 用 Zab，靠事务 ID 保证新主的历史不比任何人旧；etcd 用 Raft，默认心跳 100 毫秒、选举超时 1000 毫秒；Kafka 的 controller 早年由 ZooKeeper 选出，KRaft 后改用自带 Raft，分区 leader 切换还要求新主在 ISR（同步副本集）里；Kubernetes 多副本控制器靠抢一个 Lease 对象当主。
100ms heartbeat interval.」、「By default, etcd uses a 1000ms election timeout.」，并把心跳周期锚在网络往返上——「normally around 0.5-1.5x the round-trip time」；跨洲部署时「The upper limit of election timeout is 50000ms (50s)」。选举超时不是随便调的旋钮，它同时是你的 RTO 下限和误判率上限。etcd Documentation · Tuning · tuning.mdwal_fsync_duration_seconds 的 p99 压在 10 毫秒内，并指出「If monitoring of the machine's CPU usage shows heavy utilization, there may not be enough compute capacity for etcd.」换主的真实诱因往往是一块共享 SSD，不是一次宕机。etcd Documentation · FAQ · faq.md① 核心命题：选主本质是共识（把「n 个节点逐个操作协商」换成「一个节点定序」），但工程上用的都是更弱更便宜的算法——只承诺「最终收敛到一个主」，不承诺过程中不出现两个。
② 两种失败的代价严重不对称：没有主是响亮的停摆（可恢复），两个主是安静的数据分叉（往往不可自动恢复）。
③ Bully：活着的里编号最大者当主，无需共享状态；三个盲点——不看能力、最大编号者反复复活会活锁、消息量 O(n²)。
④ 两种省钱优化：继任名单（换主只需一个超时）与候选人制（消息量降到 O(k²)，代价是候选人成了新单点）。
⑤ Ring 沿环收名单，消息量线性但要维护环；Invitation 索性允许多组共存、事后合并——用唯一主换可用性，把账留到合并时算。
⑥ 稳定性是主线：改选要停写、补日志、重连，一次几百毫秒到数秒。原则是现任还能续租就绝不改选，并用随机化超时避免瓜分选票。
⑦ 安全边界不在选举里：给每任主一个只增的世代号（epoch）并在存储层 fencing，把「不能有两个主」换成「可以有两个主，但只有一个写得进去」。
⑧ 真实系统：etcd / Kafka KRaft 用 Raft（心跳 100ms、选举超时 1s），ZooKeeper 用 Zab，K8s 用 Lease 抢锁且自己声明不做 fencing；现实中改选多由慢磁盘与 CPU 争抢触发，不是宕机。