Distributed Snapshots（分布式快照）

一句话

Chandy–Lamport 快照算法：任一进程可自发记录自身状态，并在此后发出任何普通消息之前，向每条出边发一枚 marker（标记消息）；其余进程首次收到 marker 时立即记录自身状态并同样转发。靠通道的 FIFO（先进先出）性质，marker 在每条通道上划出「拍照前 / 拍照后」的分界线，各进程把「记完自身之后、收到该通道 marker 之前」收到的消息记为通道状态。系统不停机、不加锁、不需要全局时钟，就拼出一张因果一致的全局状态——它未必是系统真正经历过的某个瞬间，但足以判定一切稳定性质（死锁、终止、垃圾对象）。

Glossary · 术语表

坐标

作者是 K. Mani Chandy（当时在德州大学奥斯汀分校）与 Leslie Lamport（当时在 SRI International），论文《Distributed Snapshots: Determining Global States of Distributed Systems》发表于 ACM Transactions on Computer Systems，1985 年 2 月。它直接建在 Lamport 自己 1978 年的《Time, Clocks, and the Ordering of Events》之上——happens-before 是这篇的全部地基；往下则接出了一致全局状态的理论（Mattern、Fidge 的向量时钟）、免 FIFO 的变体（Lai–Yang），以及工业界的分布式 checkpoint。Lamport 自述这个问题是 Chandy 在一次晚饭时抛给他的，他第二天早上在淋浴时想出了解法，赶到 Chandy 办公室时发现对方已经有了同样的答案。

问题与动机

动机不是「我想要一张照片」，而是一类很实际的问题：怎么判断系统进入了某种全局状态？死锁检测、终止检测、分布式垃圾回收，表面上八竿子打不着，本质是同一件事——站在系统外面看一眼当前全局状态，判断某个谓词成不成立。

可「看一眼」恰恰是分布式系统里做不到的事。两条硬约束：没有共享内存（谁也看不见别人的内存，只能靠消息问），没有全局时钟（各机器的表对不齐，也没法约好「3 点整一起记」）。于是只能挨个问，而挨个问必然跨越一段时间，期间系统还在跑——科普版那个账本例子就是后果。论文开篇的自况是：一群摄影师要拍一片迁徙鸟群铺满的天空，景太大，只能分头拍再拼；可鸟在飞、快门又不同步，拼出来很可能有的鸟拍了两次、有的一次没拍到。难点从来不是拍，是让拼出来的东西有意义。

还有半截容易被漏掉：全局状态不只是各进程状态之和，还包括所有通道里的在途消息。只记进程、忘了路上的东西，「钱凭空少了 50」正是这么丢的。这半截是这篇论文一半的功劳。

核心思想 / 方法

第一步：把目标从「同时」换成「一致」

既然「同一瞬间」拿不到，论文换了个判据：一张照片（一个割）只要不出现因果倒错就算合格。所谓因果倒错，就是照片里收到了一条还没被发出的消息——收方记了「我收到了」，发方却记着「我还没发」。这样的割叫不一致割，反之叫一致割（consistent cut）。

用 happens-before 说就是：一致割是一个对因果封闭的前缀——若事件 b 在割里、且 a 先于 b 发生，那 a 也必须在割里。注意这里的不对称：「已发未收」完全合法（它就是在途消息，如实记下即可），「已收未发」才是不可能存在的世界，必须杜绝。算法要做的正是保证后者不发生。

第二步：两条规则，没有第三条

算法引入一种特殊消息 marker（标记）。它不参与业务计算，唯一作用是在每条通道上划一道线。全文的算法就是下面两条规则：

• marker 发送规则：进程 p 先记录自身状态；然后在沿通道 c 发出任何后继普通消息之前，沿每条出边各发一枚 marker。（「先记录、再 marker、最后才是普通消息」这个次序是全部的关键。）
• marker 接收规则：进程 q 沿通道 c 收到一枚 marker 时——若 q 尚未记录自身状态：立即记录自身状态，并把通道 c 的状态记为空序列，随后执行上面的发送规则；若 q 已经记录过自身状态：把通道 c 的状态记为「q 记录自身状态之后、收到这枚 marker 之前，从 c 上收到的消息序列」。

拍照由任意进程自发发起（直接执行发送规则即可），无需谁批准；多个进程同时发起也不出错——每个进程只在第一次收到 marker 时记录自己，后到的 marker 只用来封掉它那条通道。

第三步：为什么这样就一定一致

把「记录自身状态」想成进程由白变红：记录之前发出的是白消息（拍照前发出），之后发出的是红消息。两条规则合起来保证了一件事——任意一条通道上，白消息全排在 marker 前面，红消息全排在后面。

凭什么？靠两个条件咬合：发送规则规定「先记录、再发 marker、然后才可能发红消息」，故 marker 一定排在该通道所有红消息之前；而通道 FIFO，次序不会被打乱，收方看到的就是发方发出的次序。于是 marker 成了通道上一把干净的剪刀：

• 红消息绝不会进照片——收方记录通道状态的窗口在 marker 到达时就关上了，而红消息全在 marker 后面。（「钱不会凭空多」，即杜绝因果倒错。）
• 每条白消息都有着落——要么在收方记录自身状态之前就已被收到、体现在收方局部状态里；要么落在「收方记完自己」到「marker 到达」这段窗口里，被记成通道状态。（「钱不会凭空少」。）

白红消息的分界正好就是那个割，而第一条说明了它是一致的。整个论证不需要任何全局协调：每个进程只看自己收到了什么，全局一致性是 FIFO 加规则次序自动挤出来的。

第四步：代价与终止

每条通道恰好流过一枚 marker，消息开销是 |E|（通道总数），与业务流量无关。正常计算全程不停：记录自身状态是本地的瞬时动作，之后照常收发。只要有一个进程发起、且拓扑能连通到所有进程，算法在有限时间内结束（消息延迟有限）。最后还需把各处记录的碎片汇总到一处才成完整快照——这步论文留给具体应用。

第五步：那张照片可能从未真的出现过

这是全文最容易被误解、也最值得记住的一点：记录下来的全局状态 S* 未必是系统实际经历过的任何一个瞬间——它由各进程在不同物理时刻记录的片段拼成。

论文证明的是一个更弱、却恰好够用的结论：设 S_i 是算法启动时的实际状态、S_φ 是结束时的实际状态，则 S* 从 S_i 可达，且 S_φ 从 S* 可达。也就是说，存在一个与实际执行因果等价的重排（把并发事件换个顺序），在那条路径上 S* 确实出现过。白话讲：照片拍到的是一个「本来完全可能发生」的世界，只是碰巧不是实际发生的那个。

这正好够判定稳定性质 y：若 y(S*) 为真，由 S* 可达 S_φ 知系统现在确实已经 y 了；若 y(S*) 为假，由 S_i 可达 S* 且 y 稳定，知算法启动时系统还没 y。两头都给出了对真实系统有意义的结论。

关键结果

这是一篇理论论文，没有实验表格、没有 benchmark 数字——诚实地说，它的「结果」是算法、正确性证明和一个应用框架，而非性能曲线。可量化的结论有三条：

• 开销：每条通道恰好一枚 marker，总计 |E| 条额外消息，与业务消息量无关；每个进程一次本地状态记录。
• 不侵扰：与底层计算完全并发——不暂停进程、不冻结通道、不要求时钟同步。
• 正确性：S* 满足「S_i → S* → S_φ 可达链」，据此得到稳定性质检测两个方向的推论。论文把死锁检测、终止检测统一成「拍一张照片，再在照片上跑集中式判定」——这个归约本身就是结果的一部分。

为什么重要 / 影响

它把「分布式系统的全局状态」从含糊的直觉变成了可计算、可推理的对象。在这之前，「系统现在是什么样」几乎没法严肃讨论；这之后，一致割、一致全局快照成了分布式系统的通用词汇。

• 理论上：它与 Lamport 1978 的 happens-before 一起，构成了「分布式系统里可观察什么」的基础；后来的向量时钟（Mattern、Fidge 1988）正是为刻画一致全局状态而生，分布式调试与谓词检测整条线都从这里长出来。
• 问题的统一：死锁检测、终止检测、分布式垃圾回收这些曾各自为战的算法，被收编成「稳定性质检测」的同一套模板。
• 工业落地：最直接的后代是 Apache Flink 的异步屏障快照（Asynchronous Barrier Snapshotting）——数据流里周期插入的 barrier 就是 marker，算子在多条输入上「对齐」barrier 就是 marker 接收规则，由此支撑 exactly-once 与故障恢复。更广义地说，「不停机地给一个跑着的分布式系统存个档」，今天的做法都在这篇的射程内。

局限与批评

• 强依赖 FIFO 通道：marker 能当剪刀用全靠「不超车」，通道若非 FIFO 算法直接失效。Lai–Yang（1987）等给出免 FIFO 的变体，代价是改用消息染色并记录收发历史——用额外信息换掉了对顺序的依赖。
• 不容错：论文假设进程不崩溃、消息不丢失。可一旦有进程崩在拍照中途，marker 传不下去，快照就悬在那里——而「容错」恰恰是人们最想拿快照解决的事。真实的 checkpoint 系统必须另加超时、重试与协调。
• 只对稳定性质有效：S* 可能从未真实出现，所以「此刻队列长度」「此刻有没有违反不变量」这类非稳定谓词，在照片上得到的结论对真实系统没有保证。
• 需要改造每个进程：每个参与者都得懂 marker 规则、都得能暂存通道状态。在由别人写的异构组件拼起来的系统里，这个「全员配合」的前提并不便宜。
• 状态与通道可能很大：论文不关心记录一次状态要花多少钱，而工程上这正是主要成本——高吞吐通道的在途消息可能极多，大状态算子的快照可以是 GB 级。Flink 后来的增量快照与 unaligned checkpoint（放弃 barrier 对齐、把在途数据一并记下）都是在偿还这笔账。
• 拓扑假设：要求 marker 能沿边到达所有进程（论文按强连通图讨论）；成员动态进出的现代系统里，这个前提要额外维护。

要点