【论文笔记】分布式数据流中的轻量异步快照算法

Global State Snapshot

流处理系统的一个基本挑战是处理潜在的失败。现有的方法是提供全局状态快照（ Global State Snapshots）来恢复失败的计算任务。但是这种方法有两个问题：

1. 降低处理性能
2. 快照中包含一些无用的信息

流式系统提供：

• 端到端的低延时保证
• 高吞吐
• 容错
• exactly-once

目前能提供 exactly-once 语义流处理引擎都依赖全局状态快照算法。然而全局快照算法需要停止计算拓扑，而且保存的状态常常超过所需。在对延时敏感的系统中并不可行。

Chandy-Lamport

在一个分布式系统中，如果保存系统的全局快照的问题，早由 Chandy 和 Lamport 提出解决方法。

Chandy-Lamport 的基本思想：

分布式系统中一个进程称为 P，连接进程进行通信的称为 C，每个进程 P 都具有 input channel 和 output channel。

基本假设：

• 程序不中断持续发送消息
• 所有的消息在 channel 中遵循 FIFO
• 任意 P 可以保存自己的状态快照

算法描述

1. Initiating a Snaphost：从 Source 节点开始，保存自己的 state 然后向 output channel 广播一个特殊的 marker
2. Propagating a snapshot
1. 任意一个 P 收到 marker，如果是次收到，则保存自己的状态并向 output channel 广播 marker，并开始记录其他 input channel 的消息
2. 否则将记录的 input channel 作为状态持久化
3. Terminating a snaphost：所有的 P 都从全部的 Input channel 收到 marker，则算法结束

中央协调节点可以根据每个局部快照构建一个全局快照

ABS （Asynchronous Barriers Snapshots）

ABS 算法是对 Chandy-Lamport 的改良，通过 Barrier 对齐的过程，避免了对 Channel 中消息的持久化。

定义一个计算图：

T 表示所有 Task ，E 表示连接 Task 之间的 channel。定义这个图的快照为：

无环图计算的快照

算法描述：

1. 一个中央 Coordinator 周期性的向 Source Task 发送 snapshot barrier。当 Source Task 收到 barrier 后，保存当前状态的快照，然后将 barrier 广播给所有下游 Task（Outputs）
2. 当一个 Non-Source Task 收到 barrier，将该 Input Channel 设置为 Blocked，直到从所有的 Input Channel 都收到 barrier（Barriers Alignment）。
3. 当一个 Non-Source Task 从所有的 Input Channel 收到 barrier，保存当前状态快照并将 barrier 广播给所有下游 Task。将所有 Input Channel 设置为 Unblock 并继续进行计算。
4. 当所有的 Task 完成快照，全局快照结束。所得的快照为：

有环图计算的快照

有环图如果按照之前的算法，有环的 Task 永远等不到所有 Inputs Channel 发过来的 barrier，进而产生死锁。我们定义 back-edges 为 L

算法描述：

1. 一个中央 Coordinator 周期性的向 Source Task 发送 snapshot barrier。当 Source Task 收到 barrier 后，保存当前状态的快照，然后将 barrier 广播给所有下游 Task（Outputs）
2. 当一个 Non-Source Task 收到 barrier，将该 Input Channel 设置为 Blocked，直到从所有的 非回环 Input Channel 都收到 barrier（Barriers Alignment）
3. 记录所有次收到 barrier 开始直到再次收到 barrier 期间从 back-edge 传来的所有消息
4. 当一个 Non-Source Task 从所有的 Input Channel 收到 barrier，保存当前状态快照并将 barrier 广播给所有下游 Task。将所有 Input Channel 设置为 Unblock 并继续进行计算。
5. 当所有的 Task 完成快照，全局快照结束。所得的快照为：

结论

这篇论文的主要贡献是优化了 Chandy-Lamport 算法，通过 barrier-alignment 的方法，避免记录 Channel 的状态从而提供 ABS 的性能。另外将该算法的实现贡献给 Flink，作为 Flink 容错的核心机制。Lightweight Asynchronous Snapshots 的算法在有环的时候几乎和 Chandy-Lamport 是一样的，但是在无环的时候不需要再关心 channel 中的数据也可以达到同样效果。

Reference

• Chandy-Lamport Snapshotting https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/P8-chandy-lamport.pdf
• Chandy–Lamport algorithm https://en.wikipedia.org/wiki/Chandy–Lamport_algorithm
• Flink Checkpointing https://ci.apache.org/projects/flink/flink-docs-release-1.8/dev/stream/state/checkpointing.html
• Lightweight Asynchronous Snapshots for Distributed Dataflows