守株阁

主节点返回写入成功后立刻故障，备节点接管却读不到这次写入。副本没有同时损坏，客户端也没有误读响应；只要成功响应早于复制完成，这条时间线就可能成立。复制协议要规定的，正是哪些事件必须发生在成功之前，以及换主之后哪些结果必须保留。 上一篇：一致性模型与分区边界给出了检查读写历史的标准。本篇把标准落到主备与链式复制的确认点上。课程结构参考 MIT 6.5840 2026 的 Chain Replication 讲义，协议以 OSDI 2004 原论文为依据；PostgreSQL 18.6 只用于核对真实产品的配置语义，配套程序是独立的有限事件模型。 成功、复制与可读是三个事件 设一个寄存器初值为 x=0，客户端提交 Put(x,1)。主节点可以先更新内存、记录日志，再把变化发送给备节点。备节点收到字节、写入本地日志、刷入稳定存储和应用到查询状态，各自需要不同步骤。“已经复制”若不指明其中哪一步，就不足以解释一次故障后的结果。 异步主备允许主节点在备节点达到所需状态之前返回成功。如下时间线中，主节点本地数据甚至可以已经落盘，切换仍会丢失这次已确认写入： 123P: 写入 1 ── 返回 ...

客户端 A 写入 x=1 并收到成功，客户端 B 随后读到 x=0。这个结果是否错误，取决于存储接口承诺的一致性模型。若接口承诺线性一致，且没有其他写入，它就是反例；若只承诺顺序一致，还要检查客户端之间的程序关系；若只承诺最终收敛，仅凭这一次旧读无法判定违反承诺。 上一篇：时钟与因果偏序用 happens-before 描述事件之间的因果关系。本篇把对象的读写规格加入时间线，区分哪些观察可以由一次合法执行解释。MIT 6.5840 和 Stanford CS244B 都将一致性、复制与容错放在课程主线中；这里先建立检查读写历史的工具，下一篇再比较复制协议如何满足这些约束。 先规定一个读写对象 设一个 KV 对象初始所有键的值都是 0。Put(x,1) 把 x 改为 1，并返回 OK；Get(x) 返回当前 x 的值。单线程执行 Put(x,1); Get(x) 时，读取必须得到 1。这个规则称为顺序规格，独立于对象用内存、磁盘还是多个副本实现。 并发历史记录每个操作的调用和返回事件，也记录客户端身份、参数及返回值。W_A(x,1)[1,4] 表示 A 在事件 1 调用写，在事件 ...

单周期数据通路：一条指令怎样走完五件事 中心问题：如果一条指令必须在一个时钟周期内完成，硬件要给它准备哪些路？ 单周期 CPU 把取指、译码、执行、访存、写回放进同一个周期。它不表示真实高性能处理器都这样工作；它的价值在于把“指令语义需要的硬件路径”一次摊开。add 要读两个寄存器、进 ALU、写回寄存器；lw 还要访问数据存储器；sw 写内存但不写寄存器；分支既要比较寄存器，又要决定下一个 PC。 本篇覆盖 add/sub/and/or/addi/andi/ori/lw/sw/beq/bne/blt/bge。证据等级是“手算”和“功能执行”。功能执行指 Python 脚本生成控制表、穷举 ALU 断言并保存静态延迟算式；延迟部分不是周期仿真，也不推进阶段事件。不覆盖 jump、CSR、异常、压缩指令、流水线冒险、多周期控制或真实硬件频率。 依据和边界 RISC-V RV32I 文档给出本篇使用的指令语义：整数寄存器-寄存器指令读 rs1/rs2 并写 rd；立即数逻辑和加法读 rs1 加 sign-extended 12 位立即数；load/store 用 rs1 + offs...

从逻辑到状态：一块 ALU 为什么还需要时钟 中心问题：只靠一张真值表能不能得到一台会执行程序的机器？ 答案是否定的。真值表和组合逻辑能说明“给定输入会产生什么输出”，但程序执行还需要“什么时候保存这个输出”。组合逻辑负责计算，寄存器负责记住，时钟把“旧状态参与计算”和“新状态进入机器”分成两个时刻。没有这个分界，CPU 里的寄存器、PC、内存写回都会变成一团互相追赶的信号。 本篇只讨论一条最短的桥：布尔函数怎样变成小型 ALU，ALU 输出怎样进入寄存器，为什么最长组合路径决定时钟周期。证据等级是“手算”和“功能执行”。功能执行指 Python 脚本对 4 位 ALU 穷举断言并保存输出；时序部分只是静态延迟手算，不是周期仿真。这里没有 RTL、综合报告、FPGA 上板或真实 CPU 测量。 边界与依据 RISC-V 官方 ISA Specifications 20260120 的 RV32I 章节说明：RV32I 有 32 个 32 位 x 寄存器，x0 恒为 0，另有 pc 保存当前指令地址；R 型指令从 rs1、rs2 读数并向 rd 写结果，ADD/SUB/AND/OR...

服务 P 修改一条记录，再发消息通知服务 Q；Q 收到通知后更新索引。两份日志的墙上时间却显示，索引更新比记录修改早了五毫秒。这个排序能证明系统违反了业务顺序吗？不能。机器时钟可能有偏差，但消息接收必须晚于相应发送，这条约束来自通信过程。 上一篇的网络 KV 与持久化恢复处理单机服务的请求顺序和故障恢复。跨越进程之后，一条本地日志不再包含全部事件，恢复出来的记录也未必足以比较另一台机器的操作。本篇从事件和消息定义因果偏序，用 Lamport 时钟保持这个偏序，再用向量时钟识别模型内的并发。物理时间仍有用途，只是它需要另一组假设。 顺序从哪些事实产生 假定系统有固定的三个进程 P、Q、R。每个进程内部的事件按一个顺序执行，跨进程的影响全部通过显式消息传递；发送和接收是不同事件。消息可以延迟和乱序，讨论到的接收事件都有对应发送。进程不重启回退计数器，不复用身份，整数不溢出。若应用通过共享数据库等其他途径通信，也必须把那条路径纳入模型。 在这个模型中，a → b 表示 a happens-before b，定义来自三条规则：同一进程上先发生的事件在后发生事件之前；消息发送在相应接收之前...

服务端已经把 x=two 写入文件，并完成同步。返回客户端的连接随即关闭，客户端收到错误。服务进程被终止以后，新的进程应该恢复出什么值？客户端用原来的请求 ID 重试，应该重新写一遍，还是取回上次结果？ 第 01 篇的内存去重在重启后会丢失。本篇把业务修改、请求身份和返回结果放进同一条追加日志，再用真实 HTTP 连接和子进程终止验证恢复行为。第 03 篇 讨论 GFS 写入路径中的多个副本；这里暂时收窄到一台机器上的一个服务进程，把单副本自身必须兑现的承诺讲清楚。 网络接口需要先定义可观察语义 这个 KV 服务提供两类请求。GET /kv?key=x 查询当前值；POST /kv 接收包含 ID、Key、Value 的 JSON，将一个键设为指定字符串。写入返回原请求与全局递增的 Revision。首次成功修改获得一个新 revision，同 ID 同参数重试返回第一次的记录，不推进 revision。 revision 在这里仅是单个日志中的序号。它既不是物理时间，也不是跨节点一致性协议里的任期，更不能当作全局分布式事务版本。GET 返回当前值与存储的全局 revision。...

多个工作者可以重做同一份计算，保存计算结果的文件系统却必须回答另一组问题：数据放在哪些机器上，谁决定并发写入的先后，一次写入只有部分副本完成时能否读取，以及客户端收到成功究竟意味着什么。 上一篇：MapReduce 任务重试与输出提交区分了执行与发布。GFS 把这种区分推进到存储层：网络已经传完数据、某个副本已经改动文件、整个请求已经得到成功响应，是三个不同的时刻。混淆它们，会把失败后的残留内容当成已提交结果。 讨论对象是 Ghemawat、Gobioff 和 Leung 在 SOSP 2003 发表的 GFS。MIT 6.5840 Spring 2026 把它放在 MapReduce、RPC 之后，用它连接分片、复制与故障恢复。本篇的 Go 程序只执行有限内存时间线，不提供 GFS API，也没有真实的磁盘复制、租约时钟或网络传输。 从工作负载确定系统模型 2003 年 GFS 面向大型数据处理。文件较大，追加和顺序读取常见，系统需要聚合带宽，并把机器故障视为日常条件。这与任意程序都能直接使用的通用文件系统有距离。应用可以配合存储接口，接受校验记录、过滤重复等额外责任。原论文 ...

一批输入有十八条记录。某个工作者写出半个结果文件后退出，调度器把同一份输入交给另一个进程。第二个进程成功了，最终结果能否保证每条记录只出现一次？如果第一个进程没有退出，只是回复得晚，它又该如何处理自己的结果？ 上一篇的 RPC 重试与请求去重讨论了一次调用可能执行多次。批处理框架面对相同的不确定性，却有一个有利条件：许多任务可以从固定输入重新计算。代价是框架必须规定哪一次执行的输出能进入下游，不能把工作者留下的所有文件直接拼起来。 MapReduce 把这件事与任务切分、数据分组、调度放进一个计算框架。本文沿用 2004 年论文的模型讨论保证，再用独立 Go 实验检查进程被杀和旧 attempt 晚到的发布边界。实验有真实子进程和文件操作，不连接分布式存储，不模拟成生产集群。 先确定计算结果是什么 输入记录为 (ID, key)，ID 从 0 到 17，key 表示 ID 的奇偶性。目标是按 key 收集 ID，并在每组内排序。正确结果只有两组：偶数组包含 0,2,...,16，奇数组包含 1,3,...,17。这个任务很小，但能检查重试后是否多算、漏算或分错组。 将输入按 ID...

计数器最初为 0。客户端调用 Add(1)，服务端把计数器改成 1，回复却在返回途中丢失。客户端等待超时，再调用一次，计数器变成 2。网络只丢了一条回复，业务却多执行了一次。 第 00 篇 已经区分“执行失败”与“没有观察到结果”。RPC 将这个区别带进接口设计：同一项业务操作可以对应多次网络尝试，接口必须说明如何识别它们，以及服务重启之后还保留什么证据。 RPC 隐藏了传输，没有消除失败 一次远程调用通常经过参数编码、请求传输、服务端解码与分发、业务执行、结果编码、回复传输和客户端解码。正常路径看起来接近函数调用，失败路径却多了两个独立进程和两个消息方向。 如果本地进程中的普通函数返回，调用者通常可以直接使用返回值。远程请求还可能卡在消息队列、连接缓冲区或服务端执行队列里；客户端停止等待时，服务端未必停止工作。客户端看到的超时，不能反推出业务修改已经回滚。MIT 2026 RPC 讲义把这种“不知道请求是否到达或执行”的情况作为 RPC 故障语义的起点。 TCP 提供的连接内字节流可靠性也不足以解决这个问题。服务端可以先提交业务，再在回复到达客户端之前崩溃；客户端重连之后，即使...

11 篇的线段树更新一个位置时，只修改从根到叶的一条路径。如果需要保留旧数组，复制整棵树会把一次更新的空间成本扩大到线性。路径复制保留未变子树，只为这条路径分配新节点，并把新根登记为一个版本。 这里的“持久化”指旧版本仍可访问。它不表示数据已经写入磁盘，也不提供崩溃恢复、事务提交或跨进程读取能力。 版本成为接口的一部分 输入是长度 n 的整数数组，初始化产生版本 0。沿用 11 篇的点增量和半开区间和，但每个操作都指定版本： 操作 输入与输出 add(version,i,delta) 从指定版本派生新版本，只把位置 i 增加 delta；返回新版本号 sum(version,l,r) 返回该版本 [l,r) 的整数和 版本号从 0 开始连续增加，不复用。任何已有版本都能作为更新起点，因此版本之间形成分叉关系，而不是只允许不断修改最新版本。非法版本、位置或区间抛出 IndexError；空区间返回 0。空数组可以建立版本 0，但没有合法更新位置。 规模变量除 n 外还包括成功更新次数 q。所有版本根都保留在 roots 中。调用者通过公开方法操作对象，不直接...