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
