Chandy-Lamport算法

定义

Chandy-Lamport 算法是 K. Mani Chandy 与 Leslie Lamport 于 1985 年在论文《Distributed Snapshots: Determining Global States of Distributed Systems》中提出的分布式快照算法,用于在不暂停系统的情况下记录分布式系统的全局一致状态。

原理

算法假设进程间通过先进先出的可靠通道通信。发起快照的进程先记录自身状态,然后向所有出边通道发送标记(marker)消息;任何进程首次收到标记时记录自身状态并向所有出边转发标记;对每条入边通道,进程记录从自己拍快照到收到该通道标记之间到达的消息,作为通道状态。所有进程与通道状态合起来构成一个一致的全局快照。

意义

该算法证明了无需全局时钟、不冻结系统也能获得一致切面,可用于死锁检测、垃圾回收和故障恢复。

应用

Apache Flink 的检查点机制采用其变体——异步屏障快照(asynchronous barrier snapshotting),用屏障对齐替代通道消息记录,实现流处理的精确一次状态一致性。