分布式系统 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 生成后一个增量时，可能已经使用了前一个增量的结果。恢复必须保留这种生成与应用的先后关...
分布式系统 17：ZooKeeper 服务模型与会话边界
配置更新、服务发现和主节点选举，都需要多个进程对少量共享状态形成一致的解释。ZooKeeper 提供的接口很小：创建节点、读取数据、带版本更新、列出孩子，以及接收变化通知。但这些接口的有效范围不同。一次 TCP 断开不等于会话结束；收到 Watch 不等于拿到了新值；临时节点消失，也不能证明原进程已经停止访问外部资源。 第 16 篇 用受限搜索检查原创 Raft 核心。本篇转向实际产品的 API 合同，使用 Apache ZooKeeper 3.9.6 官方服务端和 Java 客户端完成本机 TCP 实验。第 18 篇再讨论 ZAB 如何组织更新与恢复，不能把前面实现的 Raft 机制直接套进 ZooKeeper。 课程结构参考 MIT 6.5840 的 ZooKeeper 讲义及 Stanford CS244B 的论文研读安排。2010 年原论文解释协调服务的设计取舍；本篇涉及的持久 Watch 和 Java 会话终止行为，则按 3.9.6 文档与发布源码核对。 实验的系统模型 服务端、客户端和代理都运行在同一台机器、同一个 JVM 中。故障注入只中断 A 的网络连接，B、服务...
分布式系统 16：从故障轨迹到有限状态搜索
一条测试通过，说明具体输入与调度没有触发已检查的错误。它没有回答：另一个消息先到会怎样，恢复恰好发生在两次授票之间会怎样，以及是否存在更短的失败过程。 第 15 篇 已用独立历史检查器判断有限客户端历史。本篇继续使用累计 Go Raft 核心，枚举一个明确受限的选举环境。目标是找出漏保存 votedFor 的最短反例，同时说明“穷尽”“最短”和“没有发现错误”分别依赖什么条件。 课程结构对应 MIT 6.5840 当前公开日程中的验证与 IronFleet 讨论，Stanford CS244B 则提供原始论文研讨路径。本篇的 BFS 和事件模型为原创实验，没有运行课程证明或照搬作业实现。MIT 2026 日程与验证讲义、Stanford 2024 日程 三种检查各自回答什么 确定性故障注入控制实现的一条执行轨迹：在哪一步丢消息、在哪一步重启、哪份状态保存错误。历史检查把外部调用与返回交给独立规格，判断这些结果是否能解释为合法顺序。状态搜索则枚举环境允许的不同动作，探索可达状态，再检查性质。 flowchart TB CODE["实际核心 + 受控环境"] ...
分布式系统 15：把客户端命令接到容错 KV
客户端发出 Add(x,5)。集群已经提交并应用，x 从 0 变成 5，但返回值在传输途中丢失。客户端重试时，另一位 leader 收到了相同请求。Raft 可以把两次提交都正确复制，却不会自动识别它们代表同一个业务操作。如果状态机再次相加，日志完全一致，业务结果仍然错误。 第 14 篇 已经建立读屏障与配置边界。本篇把客户端身份、状态机、快照和回复接在同一份 Raft 核心上，并使用独立顺序规范检查客户端历史。判断对象从“日志是否一致”推进到“成功返回的读写能否解释为合法的顺序执行”。 课程结构参考 MIT 6.5840 Spring 2026 的 Raft→RSM→KV→快照路径；当年课程接口使用版本化 Put/Get，本篇的 ClientID、Sequence 和 Add 是原创教学选择，不是该课程作业答案。Stanford CS244B 的论文研讨与独立项目要求提供了研究和评估形态。MIT 2026 Lab 4、MIT 2026 Lab 2、Stanford 2024 项目说明 一个逻辑操作，可以有多次尝试 逻辑请求携带 (ClientID, Sequence, Kind...
分布式系统 14：Raft 成员变更与线性化读
三个副本 A、B、C 已经能够复制日志。扩容时，把配置直接改成 A、B、C、D、E，看起来只是多加两台机器。但旧配置的多数 A、B 与新配置的多数 C、D、E 没有交集。若两组分别依据各自配置选出 leader，原先依赖多数交集的安全性论证便失去了前提。 读取也有类似的边界。一个副本的本地角色仍是 leader，并不表示它此刻还能代表集群。它可能被隔离，而另一侧已经选出新 leader、完成新的写入。成员变更决定哪些确认构成有效多数，线性化读则要使用这些确认，把一次读连接到实际时间顺序。 第 13 篇 已经接通持久化、快照与恢复。本篇继续扩展同一份 Go 核心，采用论文的 joint consensus 时序，并明确区分论文规则、etcd 的固定版本实现与教学驱动。第 14 篇的固定目录 race 二进制已通过九类本地场景；累计旧篇运行回归仍有缺口，具体范围见实验记录。 多数必须分别计算 稳定配置 C 的多数满足 |Q∩C| > |C|/2。两个 C 的多数必然相交；换成另一个集合 D 后，这个推理不能直接沿用。 joint 配置同时保存旧集合和新集合，要求同一批确认分别满...
分布式系统（24）：分片与在线迁移的归属边界
分片把不同键交给不同服务组。扩容时，计算一个新映射并不困难；困难在于旧组还有请求、新组正在接收数据、控制器可能随时停止，而客户端缓存的地址不会同时更新。迁移协议必须说明每个阶段谁能接受业务请求，以及失败后凭什么继续。 分布式系统（23）：Dynamo风格复制、Quorum与冲突版本 前篇讨论 Dynamo 风格副本选择与冲突版本。本篇切换到每个分片最多一个有效服务归属的模型：每个组可以在内部使用复制状态机，跨组迁移则把源撤权、状态传输和目标授权串成有序步骤。允许迁移窗口暂时没有可用服务者，但不允许两个组各自成功修改同一分片。 映射函数不能代替迁移协议 范围分片按排序后的键空间划分区间。相邻键通常在少量分片中，范围扫描容易定位；若新写集中在尾部区间，负载也可能集中在那里。Bigtable 的 tablet 就以行键范围为分布单元，这个组织方式服务于排序与范围访问，而不是所有场景下的负载均衡保证。Bigtable，OSDI 2006，§2 哈希分片先把键映射到散列空间，再分配给节点或逻辑分片。它可以打散具有相近前缀的键，但范围查询可能需要访问多个分片。若直接使用 hash(key) ...
分布式系统 13：Raft 持久化、快照与恢复边界
节点已经执行到日志 100，保存了一份快照，然后删除前 100 条日志。进程重启时，快照里却只有执行到 80 的状态。日志复制算法即使完全正确，也无法补回已经被本地删除、又没有进入快照的那 20 次修改。 第 12 篇 讨论了哪些日志可以提交。持久化和快照把这个结论连接到文件系统：重启时必须恢复出一组相互对应的任期、投票、日志、应用状态和进度，才能继续遵守已经作出的决定。 本篇沿用前两篇的 Go 核心，接入真实文件与子进程恢复。实验使用固定成员、非拜占庭消息和确定性状态机；网络由父进程调度，文件由节点子进程写入。进程被杀死后，操作系统仍在运行。因此观察到的是进程恢复行为，不能把它当成断电、内核崩溃或磁盘控制器故障的验证。 从稳定存储前提到保存完成 Raft 的安全性依赖稳定存储。节点一旦给某个任期投票，恢复后仍须记得这张票；一旦成功确认接收日志，恢复后不能凭空失去所确认的前缀。论文 Figure 2 把 currentTerm、votedFor 和日志列为持久状态，要求相应更新在 RPC 回复之前进入稳定存储。§5.5 的崩溃恢复讨论建立在这个前提上。Raft 扩展论文，Figu...
分布式系统（23）：Dynamo风格复制、Quorum与冲突版本
复制到多个节点并等待若干确认，可以提高故障期间成功处理请求的机会，却不能仅凭 R + W > N 推出线性一致性。参与确认的是哪些节点、读是否传播读到的版本、并发写如何比较、故障恢复后如何处理分歧，都属于协议本身。 分布式系统 22：协议、协调服务与多数派故障 前篇的 etcd 实验在失去多数派后无法完成默认读写。Dynamo 风格系统采用另一种取舍：允许部分故障期间的写入，在副本之间保留可能冲突的版本，把一部分协调工作推迟到读取、修复或业务合并时。这里的 Dynamo 指 Amazon 2007 年论文描述的内部系统；不能把论文机制直接当作今天 Amazon DynamoDB 的 API 保证。 请求协调者与全局主节点不同 Dynamo 论文讨论的是按键访问的高可用存储。系统需要在节点故障、通信延迟和临时不可达时继续处理相当一部分请求，并接受副本暂时不同。论文没有依赖一个全局领导者，为所有键的写入生成统一日志顺序；不过每次请求仍可由一个协调者收集副本响应。无主复制不等于没有请求协调者。 一致性哈希把键映射到环上的位置，preference list 决定优先存储该键的物理...
分布式系统 12：Raft 日志匹配与本任期提交
五台服务器里，三台都有同一条日志，是否就可以回复客户端“写入成功”？在 Raft 中，还要看条目产生于哪个任期，以及当前领导者凭什么判断它已经提交。 设 A 在旧任期写入 x，后来重新当选，并把 x 补到了多数节点。另一个节点可能保留着更新任期产生的冲突条目 y，仍有资格在下一轮赢得选举。此时直接提交 x，会把一个允许被覆盖的条目当成不可撤销的结果。 第 11 篇 建立了任期、投票与保存完成后的消息释放边界。本篇在同一个 Go 核心上加入实际日志，解释 AppendEntries 怎样修复分歧，以及“本任期条目获得多数确认”为什么能保护整段前缀。 模型与三个不同的位置 采用固定成员配置、崩溃恢复故障模型和非拜占庭消息行为。消息可以延迟、丢失、重复和乱序，节点不会任意伪造协议内容。多数始终按完整配置计算；五节点需要三个成员。成功确认的持久状态在恢复后仍然存在，是协议安全性的一项前提。 日志条目包含任期和命令，索引从 1 开始。leader 只在自身日志末尾追加当前任期的条目；follower 可以删除与合法领导者冲突的未提交后缀。实验中的命令是字符串，尚未接入应用状态机。 三个位置...
分布式系统 22：协议、协调服务与多数派故障
三成员 etcd 只剩一个成员时，一次写请求等待约三秒后超时。恢复第二个成员，完成新的写屏障，再读取先前请求的键，它已经存在。客户端没有收到成功回复，与系统没有执行该写，是两件不同的事。 分布式系统 21：etcd 的读、事务、Watch 与 Lease 前篇已把读、事务、Watch 与 Lease 的保证拆开。本篇将这些 API 放回协议与实现的完整关系中，对照 Paxos、Zab、Raft、ZooKeeper 和 etcd，并用真实三成员进程故障验证多数派丢失与恢复。协议比较依据原论文；产品固定 ZooKeeper 3.9.6、etcd 3.7.1。三成员实验只运行 etcd，不能把文档对照表当作两个产品都实测过。 协议正确为何仍不足以保证业务正确 Paxos、Zab、Raft 解决复制状态之间如何达成安全顺序。ZooKeeper、etcd 则还包含存储、客户端连接、读写 API、变化通知和运维接口。把五个名字直接放进“谁支持 Watch”的表格，会混淆算法与服务。 协议安全依赖实现保存承诺、任期和日志；产品 API 又决定客户端如何观察结果；业务配方最后还要处理重试、检查...
