Chandy-Lamport 快照算法

概述

Chandy-Lamport 算法由 K. Mani Chandy 与 Leslie Lamport 于 1985 年提出，解决"如何在分布式系统运行过程中拍摄一张全局一致的状态快照"的问题，而无需停止整个系统。

原理

发起进程记录自身状态后向所有出边通道发送特殊标记（marker）；任何进程首次收到 marker 时记录自身状态并向所有出边转发 marker，同时开始记录其他入边通道上 marker 到达之前的在途消息。当所有通道都收到 marker，快照完成。算法要求通道满足 FIFO，得到的快照是一个一致割（consistent cut）。

应用

该算法是分布式系统检测稳定性质（死锁、终止）与故障恢复的基础；Apache Flink 的分布式检查点（异步屏障快照）即是其变体，用 barrier 对齐实现流计算的精确一次语义。