文章目录

• • • Chandy-Lamport分布式快照算法
    • • Distributed Snapshot
      • The Chandy-Lamport Algorithm
      • Example

Chandy-Lamport分布式快照算法

Distributed Snapshot

分布式快照：特定时间点记录下来的分布式系统的全局状态（global state）。

分布式快照主要用途：故障恢复（即检查点）、死锁检测、垃圾收集等。

将分布式系统抽象为一张有向图：顶点称为进程（process），边称为channel。下图就示出包含3个进程和4个channel的分布式系统。

global state要包含所有进程的状态以及所有channel的状态

由于进程之间在通过channel不停地交换数据，所以以下动作都可能造成全局状态的改变：

• 进程p收到或发出一条消息M(message)；
• channel c承载了到达或离开进程p的一条消息M(message)。

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

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

The Chandy-Lamport Algorithm

普林斯顿大学Chandy-Lamport分布式快照算法的PPT

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

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

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

Chandy-Lamport 算法具体的工作流程主要包括下面三个部分：

• Initiating a snapshot: 也就是开始创建 snapshot，可以由系统中的任意一个进程发起
• Propagating a snapshot: 系统中其他进程开始逐个创建 snapshot 的过程
• Terminating a snapshot: 算法结束条件

Initiating a snapshot

• 进程 Pi 发起: 记录自己的进程状态，同时生产一个标识信息 marker，marker 和进程通信的 message 不同
• 将 marker 信息通过 ouput channel 发送给系统里面的其他进程
• 开始记录所有 input channel 接收到的 message

Propagating a snapshot

• 对于进程 Pj 从 input channel Ckj 接收到 marker 信息:

• 如果 Pj 还没有记录自己的进程状态，则

  • Pj 记录自己的进程状态，同时将 channel Ckj 置为空
  • 向 output channel 发送 marker 信息

• 否则，记录其他 channel 在收到 marker 之前的 channel 中收到所有 message

每个进程向下游发送的消息是源源不断的，所以必须得有个东西来划分“当前的消息”与“将来的消息“， marker 充当一个分隔符，分隔进程做 local snapshot （记录进程状态）的 message。比如 Pj 做完 local snapshot 之后 Ckj 中发送过来的 message 为 [a,b,c,marker,x,y,z] 那么 a, b, c 就是进程 Pk 做 local snapshot 前的数据，Pj 对于这部分数据需要记录下来。而 marker 后面 message 正常处理掉就可以了。

Terminating a snapshot

• 所有的进程都收到 marker 信息并且记录下自己的状态和 channel 的状态（包含的 message）

Example

假设系统中包含两个进程 P1 和 P2 ，P1 进程状态包括三个变量 X1，Y1 和 Z1 , P2 进程包括三个变量 X2，Y2 和 Z2。初始状态如下。

由 P1 发起全局 Snapshot 记录，P1 先记录本身的进程状态，然后向 P2 发送 marker 信息。在 marker 信息到达 P2 之前，P2 向 P1 发送 message: M。

P2 收到 P1 发送过来的 marker 信息之后，记录自己的状态。然后 P1 收到 P2 之前发送过来的 message: M。对于 P1 来说，从 P2 channel 发送过来的信息相当于是 [M, marker]，由于 P1 已经做了 local snapshot，所以 P1 需要记录 message M。

那么全局 Snapshot 就相当于下图中的蓝色部分。

参考

https://zhuanlan.zhihu.com/p/53482103?spm=a2csy.flink.0.0.7ed8b5ccaxa0Mr

https://zhuanlan.zhihu.com/p/43536305

https://www.jianshu.com/p/06fff1ffe0a7

Shylin