flink的snapshot的算法在这篇论文，本文讲述也是基于这部分内容，如果有兴趣可以自行参考原文。

介绍

  目前已知的能够保证只执行一次（exactly once）语义，依赖于全局、一致性运行状态的快照。但是这么做有两个明显的缺点：

1. 同步的快照需要停止当前所有正在计算的任务

2. 需要保存很多计算无关的状态和记录，需要占用很多额外的空间。

实现方式

一种简单的实现方案可以分三步来进行：

1. 挂起所有正在执行的计算

2. 快照

3. 快照结束后，继续执行任务

这种实现方案最大的问题是对吞吐量和存储空间都有很大的影响，而且会依赖于上游发送方的数据备份。

Flink的ABS

Flink采用的是ABS（Asynchronous Barrier Snapshotting）算法。ABS只保存节点的状态，而不保存channel的状态。

无环图

无环图

1. 由中心调度节点（JobManager）向所有的source注入barrier。当source收到barrier，会对其当前状态做快照，并且广播到所有的output（如图a）

2. 当一个非source节点，收到barrier，那么其会阻塞当前的input，直到收到所有input的barrier（如图b）

3. 收到所有barrier之后，会保存当前的快照，并向所有的output广播barrier（如图c）

4. 快照结束后，解除input的阻塞，继续计算。全局的快照是所有的节点快照

环状图

环状图

环状图的快照和无环图不完全一致：

1. 首先环状可能会无限的收到某个input的barrier

2. 数据在环状随意流动，可能会丢失数据。

为了解决以上问题，Flink对之前的算法做了一些扩展

1. 通过深度优先查找，首先得到所有的back-edge（就是回路）

2. 运算过程中，当收到所有的barrier时候（不包括回路的barrier），开始备份所有从back-edge发过来的记录，直到收到back-edge的barrier（如图b）

3. 这样在循环里的记录会被记录到本次的快照，如图c