全局快照与状态

全局快照在不冻结系统的情况下，捕获分布式计算状态的一致性视图——包括每个进程的本地状态以及传输中的消息。

Definition

一致性全局状态是本地进程状态和通道内容（对应于一致性割集）的集合。一致性割集是指，对于每个记录的消息接收，相应的发送也被记录，因此即使没有观察到全局瞬间，该状态也可能在计算过程中出现。

Scope

本主题涵盖了一致性全局状态的概念及其定义所用的“割集”（cut），Chandy-Lamport 基于标记的快照算法及其假设（FIFO通道、可靠交付），以及快照在稳定属性检测（如终止和死锁检测）和分布式检查点与恢复中的应用。

Core questions

• 是什么让记录的全局状态一致而非不可能？
• 在计算持续运行时，如何记录这样的状态？
• 如何从快照中检测终止和死锁等稳定属性？

Key theories

一致性割集

全局状态对应于跨进程事件序列的割集；当割集在“先发生”（happened-before）关系下是封闭的，即确保在记录的状态中没有消息在发送之前被接收时，该割集才是一致的。

Chandy-Lamport 快照算法

发起者记录其状态并向每个出站通道发送一个标记；每个进程在首次接收到标记时，记录其状态，然后记录其他通道上的入站消息，直到它们的标记到达，从而捕获通道内容。

稳定属性检测

由于快照捕获的是系统可能处于的某个状态，任何在快照中检测到的稳定属性（一旦成立就保持为真的属性，如终止或死锁）都是真实存在的，这使得快照成为一种通用的检测工具。

Clinical relevance

快照算法为故障恢复提供了分布式检查点/重启功能，包括现代流处理引擎为提供“恰好一次”保证而使用的异步快照，以及长时间运行计算中的死锁和终止检测。

History

Chandy和Lamport于1985年提出的算法首次提供了一种在不停止系统的情况下记录一致性全局状态的实用方法；Mattern及其他研究者推广了其底层的割集理论，该技术后来成为容错流处理的基础。

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

拍摄快照是否需要暂停系统？

不需要。Chandy-Lamport 算法通过沿通道传播标记，在计算持续进行的同时记录一致的全局状态；记录的状态是系统可能处于的状态，即使它从未被全局暂停过。