Chandy-Lamport分布式快照算法小记

Prologue

前面陆陆续续写了几篇关于Flink的浅显的小文章，其中多次提到了“异步屏障快照（asychronous barrier snapshot, ABS）算法”这个词，并指出它是Flink检查点机制的基础。而ABS算法的渊源就是本文要说的Chandy-Lamport算法，它是目前在流式系统中广泛使用的分布式快照算法。

这个算法在论文《Distributed Snapshots: Determining Global States of Distributed Systems》中提出，并以作者的名字命名，即得州大学奥斯汀分校的K. Mani Chandy与斯坦福的Leslie Lamport（这位也是鼎鼎大名的Paxos算法的作者）。算法产生的背景有点意思，据Leslie Lamport自己说：

The distributed snapshot algorithm described here came about when I visited Chandy, who was then at the University of Texas in Austin. He posed the problem to me over dinner, but we had both had too much wine to think about it right then. The next morning, in the shower, I came up with the solution. When I arrived at Chandy's office, he was waiting for me with the same solution.

下面先介绍一些分布式系统中快照的前置知识，然后正式介绍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算法基于如下前提：在每对进程p_i、p_j之间都存在两条单向的链路c_ij和c_ji，即对于p_i来讲，c_ij是出边，c_ji是入边。链路的网络可靠，缓存无限大，并且先进先出，即链路上的消息会不重不漏地按序到达。

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

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

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

Initiating a Snapshot

假设进程p_i发起快照：

1. p_i记录自己的状态；
2. p_i通过所有出边链路c_ij向其他进程p_j发送marker消息；
3. p_i通过所有入边链路c_ji开始监听所有流向自己的消息。

Propagating a Snapshot

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

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

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

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

Terminating a Snapshot

若所有进程都成功地：

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

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

Understanding the Algorithm

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

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

• 只有发送了数据，下游才会（按序）接收到数据；
• 发送者无法知道数据在下游的接收情况。

如果不这样设计，而采用简单的单令牌系统的话，就会有问题。仍然借用论文中给出的一个例子：

进程p和q以令牌（token）的传送来标定状态，s1表示持有令牌，s0表示未持有令牌。假设在“token in C”全局状态下保存快照，而q的时间戳比p早，那么就会造成两个进程都处于s0状态，而q认为令牌不在链路C中，p也认为令牌不在链路C'中，因此快照里令牌就会丢失，造成不一致。

Example

下面的图示出有两个进程的分布式系统根据Chandy-Lamport算法生成快照的过程，其中蓝色的部分表示状态已经被保存，并且进程P₁发起快照。

The End

天气是真的凉了哈。

晚安晚安。