分享好友

×
取消 复制
【论文笔记】分布式数据流中的轻量异步快照算法
2020-06-24 17:30:25

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 中消息的持久化。

定义一个计算图:

G=(T, E)

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

G^* = (T^, E^)

无环图计算的快照


算法描述:

  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 完成快照,全局快照结束。所得的快照为:

G^* = (T^,E^), E = \phi

有环图计算的快照


有环图如果按照之前的算法,有环的 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 完成快照,全局快照结束。所得的快照为:

G^=(T^,L^*), L \subset E

结论

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

Reference

分享好友

分享这个小栈给你的朋友们,一起进步吧。

Flink专区
创建时间:2020-06-19 13:29:19
Apache Flink是由Apache软件基金会开发的开源流处理框架,其核心是用Java和Scala编写的分布式流数据流引擎。Flink以数据并行和流水线方式执行任意流数据程序,Flink的流水线运行时系统可以执行批处理和流处理程序。此外,Flink的运行时本身也支持迭代算法的执行
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

技术专家

查看更多
  • ☀️
    专家
戳我,来吐槽~