分布式快照算法: Chandy-Lamport

主要用于在分布式系统中确定一个全局状态，一般用在分布式系统的状态恢复上。

Filnk中的Snapshot使用的是这个算法的改进版；Duird的KafkaIndex中也应用了相似的算法

算法流程

主要参考Flink的实现，从Source开始记录Mark

1. 从最上游进程开始记录当前进程状态，并将Mark消息广播到直接的下游节点；同时开始记录Mark之后的所有消息
2. 下游节点收到Mark消息之后做一样的操作，并记录Mark之后的所有消息
3. 当所有节点完成一遍操作，合并每个节点当时的局部快照，合并后则获得一个全局快照

优缺点

• 优点是简单，有效
• 缺点是算法前提：网络可靠、消息有序。当遇到 straggler（分布式系统中运行明显慢于其他节点的节点）的时候无法处理