25.5 分布式快照 (Chandy-Lamport)
一句话
Chandy-Lamport 用一个 marker 把 “瞬间拍照” 变成 “各节点各拍各的 + 记下通道里的在途消息”：收到第一个 marker 就记录本地状态，并沿 FIFO 通道转发——最终拼出一个一致的全局快照，哪怕它不对应任何真实时刻。
算法（每个进程）
| 步 | 动作 |
|---|---|
| ① | 发起者：记录本地状态，向所有出边发 marker |
| ② | 收到第一个 marker（且自己还没记录）：立即记录本地状态，记录该入边为 “空”，向所有出边转发 marker |
| ③ | 收到其他入边的 marker：把该入边在 “记录本地状态之后、收到此 marker 之前” 收到的消息，记为通道状态 |
| ④ | 所有入边都收到 marker → 本进程完成 |
拼起来（本地状态 + 各通道状态）就是一致快照。
性质与前提
| 性质 | 说明 |
|---|---|
| 一致性 | 快照满足 “所有消息要么都在、要么都不在”，可线性化到某个时刻 |
| 不对应真实时刻 | 它是 “某个可能的全局状态”，不是物理瞬间 |
| 前提 | 通道可靠且 FIFO（marker 与消息不超车） |
| 消息量 | O(E)（每条边至少一个 marker） |
与流处理的关系
Flink 的异步屏障快照（ABS） 就是它的工程化：
| 概念 | 对应 |
|---|---|
| Barrier | marker |
| 算子状态 | 本地状态 |
| 通道状态 | 缓冲的在途记录（对齐时暂存） |
| 对齐（alignment） | 等所有入边的 barrier 到齐再快照 |
| 非对齐（unaligned） | 不等待，把在途数据也写进快照（避免反压放大） |
“对齐” 的代价是反压：一条慢入边会阻塞整个算子；所以高吞吐场景常用非对齐快照（代价是快照更大）。
实测：快照里的 “消息总数” 必须对得上
本机 Python 3.14 模拟（3 进程、FIFO 通道、5 条消息、P0 发 5 条后 P1 消费 2 条时发起快照）：
| 量 | 值 |
|---|---|
| 快照内进程状态 | [0, 2, 0]（P1 已处理 2 条） |
| 快照内通道在途 | [[1,1,1]]（P0→P1 还剩 3 条） |
| 快照内消息总数 | 5 |
| 全局已发消息数 | 5 |
断言：状态之和 + 在途消息数 == 全局已发数。若漏记通道状态，快照总数会是 2——恢复后就丢了 3 条消息。这就是 “只记本地状态一定不一致” 的实证。
# 收到第一个 marker：记录本地状态 + 把“此后收到的消息”记进通道状态
if not recorded and first_marker(in_edge):
snapshot.state = copy(state); recorded = True
for e in out_edges: send(e, MARKER)
elif recorded and marker(in_edge):
snapshot.channels[(in_edge, self)] = buffer[in_edge] # 通道状态
反模式
| 反模式 | 后果 |
|---|---|
| 在非 FIFO 通道上用 marker | 快照可能包含 “晚于 marker 的消息”，不一致 |
| 快照期间做状态变更却不纳入 | 恢复后状态错 |
| 快照阻塞业务线程 | 抖动，吞吐下降 |
| 只存快照不存日志 | 无法做 “从快照 + 增量” 的精确恢复 |
三条铁律
🔑 快照 = 本地状态 + 在途消息；只记本地状态一定不一致。
🔑 前提是可靠 FIFO 通道；否则 marker 语义失效。
🔑 快照要配增量日志，才能恢复到任意点。
自检
Q1 为什么 Chandy-Lamport 的快照可能不对应 “某一真实时刻”？
▸ 答案：因为各进程记录状态的时间点不同（收到 marker 的先后不同），中间有消息在飞。快照拼出来的是 “一个可能的全局状态”——它满足一致性（消息不丢不重），但不等于 “某个物理瞬间的所有节点状态”。
Q2 通道状态为什么要单独记录？
▸ 答案：因为 “A 记录了状态之后发出、B 还没记录状态之前收到” 的消息，属于跨快照边界的消息：不记录它，恢复时就会丢；记录它，才能保证 “发出去的都在快照里”。
Q3 “对齐” 为什么会造成反压？
▸ 答案：因为算子必须等所有入边的 barrier 到齐才能做快照；慢入边没到，快算子就要暂停处理并缓冲数据，反压沿链路向上传播。非对齐快照把这些在途数据直接写进快照，避免等待，但快照更大、恢复更慢。
Q4 这个算法能用于 “备份数据库” 吗？
▸ 答案：思路可以借鉴（一致性快照），但数据库有自己的 WAL/checkpoint 机制，直接用 CL 算法没有意义。它的真正用武之地是流处理/分布式计算的状态快照，以及理解 “为什么 marker 能拼出全局一致状态”。
Q5 如果某个进程在快照过程中崩溃了怎么办？
▸ 答案：本轮快照作废（不完整），需要在恢复后重新发起。工程实现（如 Flink）会把快照与 checkpoint 协调器绑定：任一节点失败即整体回滚到上一个成功的 checkpoint，而不是 “修补半个快照”。
Q7 为什么实验中 “状态之和 + 在途” 恰好等于全局已发，而不是 “某一时刻的真实值”？
▸ 答案：因为它对应的确实是 “P0 发完 5 条、P1 处理了 2 条” 的那个时刻——在单通道、顺序执行的例子里，快照正好落在一个真实点上。只有在多进程并发、消息在多个通道同时飞时，快照才可能拼出 “不对应任何真实时刻” 的一致状态；本例只是验证 “账要算平”。