Chandy–Lamport 1985：标记消息怎样把全局状态收成一致割

破除误解：快照不是全员同时按下快门#

第一层误解把「分布式快照」听成「找一个全世界共用的时刻，让每台机器同时按下快门」。论文的系统定义里没有这只共用的钟。进程在空间上分开，只靠消息通信；消息延迟相对于进程内部事件不可忽略。若规格要求各进程在同一物理瞬间记录自己，系统里就必须先有真实的同时性。真实的同时性正是 1978 年那篇逻辑时钟故意撤下来的东西。本页的算法因此故意不询问墙钟。各进程记录局部状态的物理时刻可以错开；错开不是校准失败，而是装置的工作方式。把本页读成授时手册或集群停机窗口，等于把「一致的全局状态」偷换成「同一毫秒的照片」。

第二层误解看见「全局状态」就读成「计算里真正出现过的那一个瞬间」。论文写得很清楚：记录下来的全局状态不必在墙上时钟的某一刻实际发生过。它必须满足的是一致性：割在先于关系下左封闭——若接收被收进割里，对应的发送也必须在割里；等价地说，割里不能出现「消息已被接收、却尚未被发送」。这样的状态是某次与实际计算事件相同、只把若干并发事件重新排列之后可能经过的状态。观察者得到的不是发现出来的唯一历史，而是一份与潜在因果相容的可能状态。把 \(S^*\) 当成法庭上的瞬时物证，会把论文拒绝给出的物理同时性重新塞回去。

第三层误解把 1978 年的编号、后来的向量时间戳提前写进 1985 年的快照。逻辑时钟回答「事件如何排序」；快照回答「如何收齐一份可用的全局状态」。二者共享先于关系，装置不同。标量编号不能告诉你通道里还剩哪些消息；向量可以判定割是否一致，却并不自动把通道状态填出来。钱迪与兰波特给出的是标记加上先进先出：标记在每条有向通道上走一次，把发送方记录之前发出的消息与记录之后发出的消息切开。本页若开始教人维护 \(n\) 维计数器、比较乘积序，就把对象换成了菲奇与马特恩。若开始教人按逻辑时间戳排队互斥，就把对象换成了 1978 年。

第四层误解把这篇收成调试器、检查点工程或线上集群的转储步骤。论文的通道是理想化的：有向、先进先出、消息终达、不丢失不复制，进程集合固定，算法进行期间进程不崩溃。标记被假定成与普通消息可区分的一种消息，不是某次生产环境里的报文格式、落盘策略或协调者选举。终止检测是文中的说明性应用：性质一旦成立就不再翻回，于是一份一致状态足以判断它是否已经成立。那不是教人如何挂起容器、如何转储进程映像、如何在故障节点上重放日志。把标记规则读成「怎样给正在服务的集群拍照」，或读成从交错里取出可利用窗口的操作指南，类型就错了。它是观察者应当承认的切开论证，不是一份攻击步骤，也不是一份运维手册。

装置：局部状态、通道状态、标记与先进先出#

装置从全局状态的定义开始。一个分布式系统由有限个进程与有限条有向通道组成。每个进程是一台状态机，事件分成内部事件、发送与接收。每条通道的状态是已经沿它发出、尚未被对方接收的消息序列。一份全局状态因此有两块：各进程此刻的局部状态，加上各通道里仍在路上的消息。只收集第一块是不够的。消息若正在通道上，只看进程会把它算丢；若有人已经接收、发送方的记录里却还没有这次发送，拼出来的图画甚至在因果上不合法。

一致性把这幅图画钉住。用 Lamport 1978 逻辑时钟 里的先于关系来说：一条割选取每个进程的一个前沿；它一致，当且仅当它左封闭——若事件 \(b\) 在割里且 \(a \to b\)，则 \(a\) 也在割里。翻译成消息：不能记录一次接收，却不记录对应的发送。通道状态恰好补上那些「已发送、尚未接收」、因而穿过割的消息。不一致的割不是测量误差，而是观察者发明了一次系统里不可能发生的接收。论文要构造的，就是不会发明这种接收的 \(S^*\)。

标记规则是构造，不是机房配方。论文假定通道先进先出，于是同一条通道上先发出的消息先到达。发送一侧只有一句：进程一旦记下自己的局部状态，就在每条出边通道上先送出一个标记，然后再送别的消息。接收一侧也只有一句：沿通道 \(c\) 收到标记时，若自己尚未记录，则立刻记录局部状态，并把 \(c\) 的通道状态记成空序列；若自己已经记录，则把「局部状态记下之后、标记到达之前」沿 \(c\) 收到的那串消息，记成 \(c\) 的通道状态。任意一个进程都可以靠先记下自己、再发出标记来启动。FIFO 保证标记不会被它之前发出的消息追上，也不会让它之后发出的消息跑到它前面。于是标记成为通道上的一条切开线：线前的发送属于发送方记录之前的过去，线后的发送属于记录之后的未来。

切开线把通道状态说清楚了。若接收方比发送方更早记录，那么在标记到达之前沿该通道收到的消息，正是发送方在自己记录之前已经发出、接收方在自己记录之后才看到的那些——它们构成通道状态。若发送方先记录，标记会先于后续数据到达尚未记录的接收方，接收方随即记录，并把该通道记成空：没有「穿过割仍在路上」的消息需要补记。两种情形都禁止「接收进了割、发送还在割外」。改变寄存器、发出标记本身如何在操作系统里落地，论文并不写；写出的是这条切开与左封闭之间的关系。

记录下来的 \(S^\) 仍可能从未在某一物理瞬间出现。证明走的是重排，不是授时。实际计算里，有些进程早记录、有些晚记录；晚记录的那些进程，在别人已经记下之后仍在执行与割无关的并发事件。把这些与割无因果的事件「推」到记录完成之后，得到另一次事件集合相同的计算。在那次计算里，\(S^\) 会作为真实的全局状态出现一次。先于关系没有被破坏，因为被移动的只是互不能影响的事件。观察者因此不必声称「我拍到了当时」；他只需要声称「我得到了一份计算本来就可能经过的状态」。这一句把快照从物理学的同时面里救出来，放回事件的偏序里。

稳定性质是这份可能状态能做什么的界限。谓词 \(\varphi\) 稳定，意思是：一旦在某个全局状态上为真，则沿任何后续计算它继续为真。终止（全体被动且通道皆空）、死锁、令牌已经丢失，都是这一类。论文证明一条夹逼。算法开始时的实际状态 \(S0\) 能够到达 \(S^\)，\(S^\) 能够到达算法结束时的实际状态 \(S1\)。若 \(\varphi(S^)\) 成立，稳定性把它传到 \(S_1\)：结束之后性质已经为真。若 \(\varphi(S^)\) 不成立，则 \(S0\) 上它也不能成立，否则稳定性会强迫它在 \(S^*\) 上为真。终止检测被用来说明：你不必抓住「恰好终止的那一毫秒」；你只需要一份一致状态，问通道是否已空、进程是否已被动。非稳定的性质没有这套夹逼——「令牌此刻在谁手里」可以在 \(S0\)、\(S^*\)、\(S_1\) 上给出三个不同答案，快照不负责指出哪一个是墙上的现在。

装置的假设也写在纸面上。通道必须保序；乱序到达会让标记失去切开能力，后来莱与杨把颜色打在普通消息上，那是 1987 年的另一份装置。消息必须终达，进程集合必须固定，算法进行期间没有崩溃。缺一条，「尚未到达的标记」与「进程已经停机」就无法区分——那正是同年 FLP 在共识问题上写严、而本页明确不处理的失败。多次启动需要区分不同次的标记；论文的对象是一次快照。通道状态是消息序列，不是字节流切片，也不是磁盘检查点格式。这些句子把装置钉在理想化的消息图上，而不是钉在某次集群的运行手册上。

它证明了什么，以及它没有证明什么#

它证明：在先进先出、消息终达、进程不崩溃的模型里，标记规则收成的 \(S^\) 是一致全局状态——左封闭，因而不含「未发送却已接收」。它证明 \(S^\) 是某次事件重排后真实出现过的状态，因此与实际计算共享同一偏序闭包。它证明稳定性质可以被夹在算法起止之间：真则事后为真，假则事先为假。它表明许多检测问题不必先发明一只全局钟，只要会收齐进程状态与通道状态。终止检测是这条推论的课堂尺度说明，不是另一套协议。

它没有证明存在唯一的全局时刻，也没有证明 \(S^*\) 曾经被墙上时钟量到。它没有给出 向量时钟，没有判定任意两条割谁先谁后的格论坐标；马特恩 1989 年把一致割写成格，那是后文。它没有给出崩溃后仍能选定单一值的共识算法，因而既不是 Paxos，也不是虚拟同步里的视图更换，更不是把 分布式系统 里某次超时怎么设。它没有取消先进先出：乱序通道上的正确快照是另一篇文章的对象。它没有把线性化点安装进消息传递——线性化 的对象是并发对象的历史，不是通道序列。互斥、复制组、日志提交，全部超出本次切开。本页因此停在割本身：先看见不一致意味着什么，再看见标记如何借用 FIFO 把它禁止掉，最后看见稳定性质为什么只需要可能状态、不需要同时性。

跨域连接#

• 时间哲学：麦塔加特的 B 系列是「先于 / 后于」的固定关系，A 系列才是过去—现在—未来的流逝。分布式快照拒绝生产一个全体共享的「现在」：各进程记录的物理时刻可以错开，\(S^*\) 仍可以是一致的。奥古斯丁问「现在」有没有厚度；这里的现在甚至不必是横切世界的那一层同时面，它只是观察者用标记收成的一条左封闭前沿。把快照听成「终于拍到了那一毫秒」，是把 B 系列里的相容割重新填成 A 系列里的此刻。滴答线可以被扳直，同时性仍是作图选择。本页的时间是事件能否互相影响，不是钟面。
• 狭义相对论：相对论里没有全体共用的同时性，事件的序由信号能否连接来定义。兰波特 1978 年已经提醒读者去看不变的时空表述，并划开「可能发出的信号」与「实际发出的消息」。1985 年的快照把这张图的横切问题写进算法：你不能用一张同时面去切消息图，否则会切出接收而无发送。标记并不恢复牛顿式的绝对同时，它只保证切出来的那条割与实际消息的因果相容。光锥给出物理上的不可能影响；FIFO 通道上的标记给出这次运行里一条可计算的切开。把全体进程的局部状态在墙钟上对齐，等于强行选一张同时面，再把类空两侧的事件投影到面上假装发生在一起。
• 因果：先于是潜在因果，不是休谟要你在接球瞬间看见的那根力。你看见的是进程内部的排列，加上一条已经送达的消息。一致割说的是：观察者不得把结果写进原因尚未发生的图画里。通道状态不是隐藏的力，而是已经发出、尚未送达、因而仍属于「正在影响」的那些边。标记不创造因果，只禁止漏记。系统外的电话仍然无效：没进入消息集合的先后，不会因为多一次快照就变成割里的边。把 \(S^*\) 读成必须在日志里找到的瞬时物证，会把潜在因果误当成已经留下痕迹的传递物。
• 认识论：单个进程在收到标记之前，至多知道自己的局部历史，不知道别人已经记录了什么、通道上还剩什么。快照是一次被设计出来的知识收集，不是发现一个外在的全局事实。收集完成之后，观察者持有的是一份可能状态，不是每个参与者都已经核验的公共知识。进程 \(p\) 记下自己，并不因此知道 \(S^*\) 的其余分量；那些分量要等标记走完、通道状态被补齐。把「我这边已经拍过」当成「系统的全局状态已经为人所知」，是把私人证据提升为公共知识。装置拒绝这一跃：一致性是观察者对拼图的约束，不是每个进程在每个时刻都持有的抄本。
• 同一性：\(S^*\) 可能从未作为实际计算的瞬时状态出现，却仍被认作「该系统的一份全局状态」。同一性在这里不依赖与某一物理瞬间重合，而依赖外延：同一组事件、同一偏序、通道里同一批尚未送达的消息。换一种并发交错，对象仍是那次计算，只要先于关系不被发明或抹掉。这与持存问题结构相似：变化中的个体凭什么还是它。快照给出的答案是规格性的——合法的全局状态是左封闭的那一类，不是墙钟偶然切到的那一帧。规格若改成「必须物理同时」，对象就不再是这篇论文里的系统。

参考文献#

• K. Mani Chandy & Leslie Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems 3(1), 1985, pp. 63–75. DOI: 10.1145/214451.214456. —— 本文对象：标记消息、FIFO 通道、一致全局状态与稳定性质的检测。
• Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM 21(7), 1978, pp. 558–565. DOI: 10.1145/359545.359563. —— 先于偏序；本页用它说明一致割的左封闭，并不靠逻辑编号去收集状态。
• Edsger W. Dijkstra & C. S. Scholten, "Termination Detection for Diffusing Computations", Information Processing Letters 11(1), 1980, pp. 1–4. DOI: 10.1016/0020-0190(80)90021-6. —— 终止作为稳定性质的先声；1985 年论文用快照说明同一类检测。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 同年把失败放进完全异步模型；用以标明本页假定进程在算法期间不崩溃。

延伸阅读#

• Friedemann Mattern, "Virtual Time and Global States of Distributed Systems", in M. Cosnard et al. (eds.), Parallel and Distributed Algorithms, North-Holland, 1989, pp. 215–226. —— 用向量时间给一致割一个格上的坐标；判定而非构造，与本页标记装置相邻。
• Ten-Hwang Lai & Tao-Heng Yang, "On Distributed Snapshots", Information Processing Letters 25(3), 1987, pp. 153–158. DOI: 10.1016/0020-0190(87)90121-2. —— 去掉 FIFO 假设的着色消息快照；用来标明本页切开论证依赖保序通道。
• Colin J. Fidge, "Timestamps in Message-Passing Systems That Preserve the Partial Ordering", Proceedings of the 11th Australian Computer Science Conference, 1988, pp. 56–66. —— 保持偏序的向量时间戳；与快照分工：一个刻画并发，一个收集全局状态。
• Kenneth P. Birman, "Replication and Fault-Tolerance in the ISIS System", Proceedings of the 10th ACM Symposium on Operating Systems Principles, 1985, pp. 79–86. DOI: 10.1145/323627.323636. —— 同年进程组与后来所谓虚拟同步；对象是复制与视图，不是标记割。