Chandy-Lamport分布式快照算法

分析&回答

Distributed Snapshot

所谓分布式快照，实际上就是特定时间点记录下来的分布式系统的全局状态（global state）。分布式快照的主要用途有故障恢复（即检查点）、死锁检测、垃圾收集等。

为了方便理解，我们仍然沿用原论文中的方法，将分布式系统抽象为一张有向图：顶点称为进程（process），边称为链路（channel）。下图就示出包含3个进程和4个链路的分布式系统。

那么，全局状态就要包含所有进程的状态以及所有链路的状态。由于进程之间在通过链路不停地交换数据，所以以下动作都可能造成全局状态的改变：

进程p收到或发出一条消息M；
链路c承载了到达或离开进程p的一条消息M。

论文中将使分布式系统状态发生变化的因素叫做事件（event），并给出了它的形式化定义，即e=<p, s, s', M, c>。p、M、c的定义上面已经提到了，而s和s'分别是进程p在事件e发生之前及发生之后的状态。

可见，进程对自己的状态是有感知的，而链路本身只负责传递消息，它们的状态不容易记录。并且我们无法让时间静止，各个进程的时钟也很有可能不同步，故不能在一瞬间同时捕获所有进程和链路的状态。所以必须要曲线救国，通过每个进程记录的与自己相关的状态合并出全局状态，这也是Chandy-Lamport算法的核心思想所在。

下面具体介绍算法的细节。

The Chandy-Lamport Algorithm

Chandy-Lamport算法基于如下前提：在每对进程pi、pj之间都存在两条单向的链路cij和cji，即对于pi来讲，cij是出边，cji是入边。链路的网络可靠，缓存无限大，并且先进先出，即链路上的消息会不重不漏地按序到达。

算法要达到如下的终极目标：

最终产生的快照必须保证一致性；
快照过程不能影响系统正常运行，更不能stop the world。

为了保证成功取得全局快照，Chandy-Lamport算法分为3个阶段，即初始化快照、扩散快照与完成快照，并且借助一种与正常消息不同的特殊消息作为标记，英文称为marker。这3个阶段并没有直接体现在论文中，而是出自普林斯顿大学相关课程的PPT，但算法实际流程则是严格一致的。下面叙述3个阶段的流程。

Initiating a Snapshot

假设进程pi发起快照：

pi记录自己的状态；
pi通过所有出边链路cij向其他进程pj发送marker消息；
pi通过所有入边链路cji开始监听所有流向自己的消息。

Propagating a Snapshot

对于任意一个进程pj（包含发起快照的那个进程），考虑它的所有入边链路ckj。当在ckj上收到了marker消息时，有两种情况。

如果pj还没有记录自己的状态——

pj记录自己的状态，并将ckj标记为空；
pj通过所有出边链路向其他进程发送marker消息；
通过所有入边链路开始监听所有流向自己的消息。

如果pj已经记录过自己的状态——
记下入边链路上监听到的消息，直到收到marker消息为止。

Terminating a Snapshot

若所有进程都成功地：

收到了marker消息；
记录下了自己的状态；
记录下了入边链路的状态（就是链路上的消息）

则快照成功，算法流程结束。然后就可以将所有这些状态传输到一个稳定的分布式存储中心，全局快照就产生了。

Understanding the Algorithm

全局快照的难点在于，因为系统不能停止，每个进程向下游发送的消息是源源不断的，所以必须得有个东西来划分“当前的消息”与“将来的消息”，让它们不会混淆，而marker消息就是这个界限。对进程pj的入边链路ckj而言，如果收到的消息序列是[a, b, c, marker, d, e, f]，那么就说明a/b/c三条消息属于当前快照，而d/e/f三条消息属于下一个快照。

另外，因为每个进程都记录自己收到的消息，所以进程最终都能持有入边链路的状态。为什么要用接收进程来记录？用两句大白话来解释：