分布式系统 18：ZAB 原子广播与领导者恢复

主节点已经生成两条有依赖的状态变化，第一条只来得及到达部分副本，第二条还在传输中。此时切换领导者，新主应该继承什么？仅仅选出一个进程，或者选出一份较长日志，都没有完整回答这个问题。

第 17 篇 使用官方 ZooKeeper 3.9.6 验证了 znode、session 与 Watch。本篇讨论服务内部的 ZAB：领导者怎样取得一个可继续生成状态变化的历史前缀，以及副本何时能确认自己已接受了这个前缀。正文分别使用 DSN 2011 论文的协议模型、固定 3.9.6 的实现和原创有限实验，不把三者合并成同一份规格。

课程结构继续参考 MIT ZooKeeper 讲义与 Stanford CS244B 论文研读安排。本篇 Python 实验不调用 ZooKeeper 内核，也不复用前面 Raft 的代码冒充 ZAB；真实产品三节点故障实验留到第 22 篇。

状态变化之间可以有依赖

普通原子广播要求各副本的交付历史相容。ZAB 还围绕 primary-backup 的状态增量讨论顺序：primary 生成后一个增量时，可能已经使用了前一个增量的结果。恢复必须保留这种生成与应用的先后关系。

例如，初始状态是 0，旧主先生成 A：0 → 1，随后生成 B：1 → 2。新主如果忽略 A，改为生成 C：0 → 10，就不能再把依赖状态 1 的 B 接到 C 后面。即使每个位置单独达成了一个值，拼接出的状态变化也可能没有合法的应用顺序。

flowchart TD
    S["初始状态 0"] --> A["旧主增量 A：0 → 1"]
    A --> B["旧主增量 B：1 → 2"]
    S --> C["新主增量 C：0 → 10"]
    C -."不能直接接上：前置状态不符".-> B

论文把顺序要求进一步拆开：local primary order 要求同一 primary 实例先广播的事务先交付；global primary order 要求不同 primary 实例的已交付事务遵守 primary 的顺序。primary integrity 则约束新 primary 广播之前已经交付此前必须继承的历史。这里的 Agreement 是交付历史相容的安全性要求，不能读成所有节点最终都会交付的活性保证。它不是“所有客户端操作之间都存在因果关系”，也不能简单等同一般的因果一致性。Junqueira、Reed、Serafini，Zab，DSN 2011，§III

论文 Figure 1 借独立共识实例说明上述依赖问题，不能据此推导“Paxos 不安全”。第 10 篇 已区分共识决定槽位与状态机按连续前缀执行。正确的复制状态机设计可以使用 Paxos；这里要解释的是，针对 primary 已生成的增量状态，恢复协议需要维护哪些额外约束。

故障模型与三阶段屏障

论文采用 crash-recovery 模型。进程可以停止再恢复，稳定存储中的承诺和历史仍在；协议不处理拜占庭节点、伪造消息或稳定数据无声损坏。连接按 FIFO 接收，同一次连接中后发送的消息不能任意越过前面的消息。结束迭代时，旧连接中的缓冲消息需要被排除，不能稍后混入新一轮。

安全性不要求某次超时准确区分失联与死亡。进展则需要一个多数集合和共同领导者稳定足够久，消息能够及时传达。永久失去多数、反复切主的执行可以持续不完成；有限实验里停在屏障前不等于证明活性失败，更不能将沉默当作成功。

领导者候选产生之后，ZAB 还要完成发现、同步、广播的转换。候选处于 LEADING 一类选举状态，不代表已经取得对外处理新状态变化的全部条件。

flowchart TD
    O["产生候选<br/>实现中由 FLE 等选举机制完成"] --> D["发现 Discovery<br/>新 epoch 承诺与历史信息"]
    D --> H["确定需要继承的完整前缀"]
    H --> S["同步 Synchronization<br/>接受 NEWLEADER 历史"]
    S --> Q{"收到有效的<br/>多数同步 ACK？"}
    Q -- 否 --> W["等待或放弃本轮<br/>不开放新广播"]
    Q -- 是 --> R["完成恢复并交付基础历史"]
    R --> B["广播 Broadcast<br/>PROPOSAL / ACK / COMMIT"]

本篇模型用确定性 oracle 指定候选，省略选举网络轮次；其后每个阶段仍需处理对应消息和多数门槛。候选名字由脚本决定，不等于脚本可以直接把系统设成 ready。原论文 §IV–V

三种编号分别记录什么

acceptedEpoch 保存对新 epoch 的承诺，对应论文中的 f.p。节点承诺更高 epoch 后，不能再接受旧 epoch 的提议。currentEpoch 对应 f.a，记录已经接受 NEWLEADER 历史的 epoch；它必须与相应历史的持久化关系一起理解。

选举机制自己的轮次编号又是另一件事。3.9.6 FastLeaderElection 的 logicalclock/electionEpoch 用于选举轮次，不能与上述持久字段混写。选举候选排序比较 peerEpoch、lastLoggedZxid，最后比较 serverId；排序本身还不等于收齐了有效选票。固定版 FastLeaderElection.java

zxid 则标识事务，编码为高 32 位 epoch、低 32 位 counter。(e,0) 用于 NEWLEADER 标记，不是普通用户更新。它也有有限整数表示边界，不能说成无限递增的数学整数。固定版 ZxidUtils.java

flowchart TD
    A["接受新 epoch 承诺"] --> P["acceptedEpoch = e<br/>拒绝旧 epoch 提议"]
    P --> H["接受并稳定保存恢复历史 H"]
    H --> C["currentEpoch = e<br/>与 H 的持久关系必须成立"]
    C --> Z["广播事务 zxid = e,1；e,2；…"]
    E["FLE 选举轮次"] -."不同计数，不可互换".-> P

发现阶段的新 epoch 来自参与者报告的 acceptedEpoch，不能描述为领导者读取了全系统、包括不可达节点在内的最大值。收到更高 epoch 的节点先保存承诺，再报告当前已接受历史。两个同 epoch 的有效建立过程若都需要多数确认，其确认集合必有交点；交点不能对同一个 epoch 提供两次相互冲突的有效承诺。

历史选择也不能只比较长度。论文依据 ACK-E 中已接受历史的 epoch，再比较该历史的末尾 zxid，选择后续同步的前缀。一个较新 epoch 的历史具有优先意义，前提是此前同步阶段确实履行了持久化合同。后面的错误实验正是破坏这个前提。

保存历史以后才能回复 ACK

发现阶段得到一个前缀后，新主必须让多数节点接受它。论文 Phase 2 把历史与已接受历史的 epoch 作为原子持久步骤处理，再发送同步 ACK。只把数据放进内存或异步写队列，尚未满足这一前提。

sequenceDiagram
    participant L as 新主
    participant F as follower
    participant D as follower 稳定存储
    L->>F: NEWLEADER(e, H)
    F->>D: 保存 H 与已接受 epoch e
    D-->>F: 原子持久步骤完成
    F-->>L: ACK NEWLEADER
    Note over L: 收到多数有效同步 ACK
    L-->>F: 激活本轮并完成恢复交付
    Note over L,F: 才进入可生成新状态变化的阶段

为什么多数交集还不够？旧事务 X 被一个多数接受，新发现集合与它相交，只能说明某个交点曾经接受 X。还需要交点保存历史、承诺不再接受旧 epoch，以及新多数确实保存选定历史，才能把这一事实归纳到再下一次领导者切换。若同步 ACK 可以早于历史保存，某个节点就可能带着更高 currentEpoch、却带着更旧的数据重启，历史比较规则会据此作出错误选择。

广播阶段同样区分三个事实：事务已被足够多节点接受，领导者收到了足够多 ACK，以及 COMMIT 已到达某个副本并交付。论文的 chosen 根据多数实际接受定义，不以领导者是否看到了 ACK 或客户端是否收到答复为条件。

这允许事务流水线。领导者可以连续发出 A、B，副本按顺序保存并确认，领导者再按前缀顺序提交。新主产生第一条自己的增量之前必须恢复旧历史，但同 epoch 的下一条增量不必等待上一条 COMMIT 已经交付。把这两条约束混在一起，会错误地禁止合法流水线。

未确认尾部可能保留，也可能丢弃

旧主已经保存 Y、但尚未获得多数时，Y 的命运由后续选定历史决定。假设 A、B、C 都已交付 X，只有旧主 A 多保存了 Y。A 失联后，由 B/C 发现并同步，选定历史可以只有 X；A 返回时，其少数尾部需要修复。

另一条合法轨迹中，A 停止并恢复后参与新的发现。它的 X、Y 仍在稳定历史中，且在本轮比较中被选中，Y 就可以随同步保留并交付。应用不能把“没收到成功答复”解释为“下一个 leader 一定删除了这条操作”。

flowchart TD
    T["A：X,Y<br/>B：X<br/>C：X<br/>Y 仅 A 保存"] --> L["A 暂不可达<br/>发现集合 B,C"]
    T --> R["A 从稳定历史恢复<br/>发现集合 A,B"]
    L --> S["选择 X<br/>同步形成新多数"]
    S --> D["A 返回后删除少数尾部 Y"]
    R --> K["选择 X,Y<br/>同步确认后交付 Y"]

已经被多数持久接受、但 ACK 或 COMMIT 尚在路上的事务还有更强约束。本篇 chosen-before-commit 场景让 X 在 A/B 保存，旧主尚未收到任何 ACK 就停止；新发现集合 B/C 仍继承 X，并在生成 Y 前交付 X。输出的持久接受证书与领导者已观察 ACK 的记录分开保存。

这些轨迹并不授权系统丢弃已经交付的前缀。没有确认与确认丢失是应用侧的不确定性，协议恢复仍要守住已经成立的选择与交付事实。

论文步骤与 3.9.6 实现的对应

产品使用了更多消息和恢复优化。下面只列与证明边界相关的对应，不能把每一行当作逐语句等价映射。

论文中的职责	ZooKeeper 3.9.6 对照	边界
提出新 epoch、交换状态	FOLLOWERINFO、LEADERINFO、ACKEPOCH	acceptedEpoch 与 currentEpoch 分开传递和保存
选择合适历史	FLE 候选排序及 waitForEpochAck 检查	更先进 follower 会使建立过程失败；该方法不会自动拉取它的全历史继续
同步前缀	DIFF、TRUNC、SNAP 与后续事务流	根据历史范围、分支和可用日志选择，不能只看长度
确认新历史与开放服务	NEWLEADER ACK、UPTODATE	单节点 ACK 不足以证明已形成多数
正常广播	PROPOSAL、ACK、COMMIT	ACK 前有持久链路，提交保留顺序

Leader.waitForEpochAck 如果发现 follower 的 StateSummary 比 leader 更新，会抛异常并中止本次建立。论文通用算法的“从回复中选择历史”与这一依赖选举前置条件的优化必须分别说明。固定版 Leader.java

同步也不是“短日志用 DIFF，长日志用 TRUNC”这样单一的长度判断。实际实现会检查共同事务范围、已提交缓存、可用磁盘日志，以及能否连续覆盖所需区间；无法完成合适的增量同步时可能退回快照。

flowchart TD
    H["目标：与选定历史一致"] --> C["检查共同位置、历史分支<br/>及可用事务范围"]
    C --> D["DIFF<br/>发送缺少的连续事务"]
    C --> T["TRUNC<br/>删除不属于目标历史的尾部"]
    C --> S["SNAP<br/>传递状态并接续事务"]
    D --> P["保存恢复所需状态与历史"]
    T --> P
    S --> P
    P --> A["达到正确持久边界后确认"]

3.9.6 Learner.syncWithLeader 的 NEWLEADER 分支先处理同步事务、调用数据库 commit()，随后 setCurrentEpoch，再发送 ACK。正常提议的 SyncRequestProcessor.flush 也先调用数据库提交，再由后续处理器生成 ACK。FileTxnLog 默认 forceSync 开启时调用 channel.force(false)；关闭这条路径或者底层硬件不履行持久性承诺，会改变证明的前提。Learner.java、SyncRequestProcessor.java

这条顺序有实际修订背景。ZOOKEEPER-3911 涉及 DIFF 同步的未提交日志；ZOOKEEPER-4646 指向恢复确认早于事务持久化的问题，其状态为 Duplicate，不能虚构一个独立修复版本；ZOOKEEPER-4785 记录相关 currentEpoch 与事务保存竞态，修复版本包括 3.9.2。固定 3.9.6 源码已有相应顺序，下面的教学变异不等于声称当前产品仍含这些缺陷。

一个先确认、后丢历史的反例

examples/distributed-systems/zab18/model.py 只使用 Python 标准库。稳定映像是模型数据结构，restart 从该映像恢复；没有执行磁盘 fsync，也没有启动 ZooKeeper。FIFO 队列带连接代次，旧连接中的封套被丢弃；事件等待与活性分析没有被替换成随机睡眠。

唯一错误模式发生在节点 3 的第二个 epoch：处理 NEWLEADER 时只把 currentEpoch 改成 2，内存里有 X，稳定历史却仍为空，随后照常回复 ACK。其余规则和正确模式相同。后续 crash 清除内存，把这个错误变成可观察的恢复结果。

sequenceDiagram
    participant A as 节点 A
    participant B as 节点 B
    participant C as 节点 C
    Note over A,B: epoch 1：多数保存 X，A/B 已交付 X
    Note over A: A 停止
    B->>C: epoch 2 同步 X
    Note over C: 错误：只保存 currentEpoch=2<br/>稳定 history 仍为空
    C-->>B: 错误 ACK
    Note over B,C: epoch 2 完成建立
    Note over B: B 停止
    Note over C: C 停止并恢复，丢失内存 X
    Note over A: A 恢复：epoch 1，历史 X
    A->>C: epoch 3 发现回复：旧 epoch，X
    Note over A,C: C 的较新 currentEpoch 优先<br/>错误地选择空历史
    C->>A: 同步空历史，再广播 Y：0 → 10
    Note over A,C: 交付 Y，与先前已交付的 X 不相容

审计器独立保留各节点曾经对外交付的历史，重启不会删除这些观察事实。被测协议不能读取审计器去阻止错误，否则只能得到“程序提前拒绝了测试”，而不是协议在坏持久前提下的实际后果。错误分支确实继续生成并交付 Y，审计报告稳定 ACK 不成立、节点遗忘已交付前缀，以及交付历史不相容。

正确分支执行相同的三轮调度。C 在 epoch 2 保存 X 与 currentEpoch 后才 ACK，重启仍带着 X；epoch 3 继承 X，再产生依赖 X 的 Y。因此差异来自被刻意破坏的存储合同，而非测试脚本直接填写期望的最后日志。

运行方式如下，所有输出均保存在仓库固定目录：

cd examples/distributed-systems
mkdir -p .build/zab18
PYTHONDONTWRITEBYTECODE=1 python3 zab18/model.py \
  --output .build/zab18/results
PYTHONDONTWRITEBYTECODE=1 python3 zab18/model.py \
  --scenario broken-phase2 --output .build/zab18/broken-results

2026-09-20 作者与独立复核使用同一源码运行七个场景，全部按预期通过：正常流水线、ACK 未达时恢复 chosen 事务、少数尾部丢弃、少数尾部继承、阶段与旧连接门槛、正确持久恢复，以及唯一错误模式。帮助退出 0，未知场景和多余位置参数退出 2。PASS broken-phase2 表示成功检出了错误，不表示错误模式满足安全性。

每个 JSON 输出包含全部发送、接收、稳定映像变化、历史选择和交付记录。普通 proposal 的 chosen 证据按提议 epoch 与事务分组，由实际稳定接受者达到多数得出，不把跨 epoch 的零散证据相加，也不把 leader 已收到 ACK 当作唯一判断。JSON 是本轮观察记录，程序不接受它作为导入回放脚本；重新执行相同确定性调度会生成相同结果。

模型还主动拒绝 ready 前广播。一个 promise 不够建立发现多数，一个或重复的同步 ACK 不够开放广播，旧 epoch 的提议与旧连接代次的封套也不能进入新历史。返回节点的 join 仅抽象为完整历史原子安装，用来检查少数尾部修复；它没有实现产品的完整重入协议，也不把该节点加入当前参与集合。

原始输出、完整错误轨迹和核验范围见 验证记录、错误分支 JSON 与 论断证据表。这些是有限调度的安全性检查，不是最短反例搜索、全状态穷尽、活性证明或当前 ZooKeeper 的完整正确性证明。

两道练习

练习一：ACK 丢失后还有没有 X？ 三个节点中，A、B 已经稳定接受 X，B 的 ACK 没有到达旧主 A，A 随即停止。新的发现集合是 B/C。如果客户端未收到答复，能否让新主直接从空历史生成 Y？若 X 只保存在 A，答案为什么不同？

答案要点：前一种情况已有多数实际接受，ACK 丢失改变旧主的知识，不撤销持久接受事实。发现与同步必须保留需要继承的 X。后一种只有少数保存，B/C 可以选不含 X 的历史；若带 X 的合格历史参与并被选择，X 也可能保留。客户端的未知结果不能决定日志命运。

练习二：只有 epoch 保存得更可靠。 同步时把 currentEpoch 先保存，并立刻 ACK，后台再慢慢写入历史。这个优化减少了等待，是否仍能凭多数交集证明恢复安全？

答案要点：不能。节点重启后可能携带较新 currentEpoch 和较旧历史，后继发现按照协议比较信息时会优先选择这份不完整历史。实验中的 epoch 2 → epoch 3 已给出具体轨迹。修复需要恢复历史与 epoch 的正确持久关系，再发送有效确认；改变审计器或隐藏旧交付记录都不能修复协议。

第 19 篇回到应用层一致性：内部广播维护了更新顺序，普通读、跨客户端观察和外部资源的 fencing 还分别需要哪些条件。