分布式快照算法: Chandy-Lamport

本文涉及的产品
EMR Serverless StarRocks,5000CU*H 48000GB*H
EMR Serverless Spark 免费试用,1000 CU*H 有效期3个月
简介: Spark 的 Structured Streaming 的 Continuous Processing Mode 的容错处理使用了分布式快照(Distributed Snapshot)算法 Chandy-Lamport 算法,那么分布式快照算法可以用来解决什么问题呢?

0. 引言

上一篇文章最后说到 Spark 的 Structured Streaming 的 Continuous Processing Mode 的容错处理使用了分布式快照(Distributed Snapshot)算法 Chandy-Lamport 算法,那么分布式快照算法可以用来解决什么问题呢?

A snapshot algorithm is used to create a consistent snapshot of the global state of a distributed system. Due to the lack of globally shared memory and a global clock, this isn't trivially possible.

简单来说就是用来在缺乏类似全局时钟或者全局时钟不可靠的分布式系统中来确定一种全局状态。

那么分布式快照算法应用到流式系统中就是确定一个 Global 的 Snapshot,错误处理的时候各个节点根据上一次的 Global Snapshot 来恢复。下面就介绍一下在流式系统中广泛使用分布式快照算法:Chandy-Lamport 算法及其改进算法。Flink 使用的是 Chandy-Lamport 的改进算法。

1. Overview

Chandy-Lamport 算法以两个作者的名字命名,没错,其中 Lamport 就是分布式系统领域无人不晓的 Leslie Lamport,著名的一致性算法 Paxos 的作者。算法的论文于 1985 年发表,Distributed Snapshots: Determining Global States of a Distributed System,提到这篇论文,不得不提一下这篇论文的由来,洗个澡的时间想出来的。

The distributed snapshot algorithm described here came about when I visited Chandy, who was then at the University of Texas in Austin. He posed the problem to me over dinner, but we had both had too much wine to think about it right then. The next morning, in the shower, I came up with the solution. When I arrived at Chandy's office, he was waiting for me with the same solution. I consider the algorithm to be a straightforward application of the basic ideas from Time, Clocks and the Ordering of Events in a Distributed System.

正如 Lamport 所述,算法的思想非常的 straightforward,在描述算法之前需要先介绍一下 Global Snapshot。

2. Global Snapshot

Global Snapshot 我们也可以理解为 Global State,中文可以叫做全局状态,在系统做 Failure Recovery 的时候非常有用,也是广泛应用在分布式系统,更多是分布式计算系统中的一种容错处理理论基础。

在 Chandy-Lamport 算法中,为了定义分布式系统的全局状态,我们先将分布式系统简化成有限个进程和进程之间的 channel 组成,也就是一个有向图:节点是进程,边是 channel。因为是分布式系统,也就是说,这些进程是运行在不同的物理机器上的。那么一个分布式系统的全局状态就是有进程的状态和 channel 中的 message 组成,这个也是分布式快照算法需要记录的。

因为是有向图,所以每个进程对应着两类 channel: input channel, output channel。同时假设 Channel 是一个容量无限大的 FIFO 队列,收到的 message 都是有序且无重复的。Chandy-Lamport 分布式快照算法通过记录每个进程的 local state 和它的 input channel 中有序的 message,我们可以认为这是一个局部快照。那么全局快照就可以通过将所有的进程的局部快照合并起来得到。

3. Chandy-Lamport 算法

那么我们基于上面假设的分布式系统模型来看一下 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 信息
      • 记录 input channel Clk (l != k && l != j)收到的所有 msg
    • 否则

      • 记录在收到 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 对于这部分数据需要记录下来,比如记录在 log 里面。而 marker 后面 message 正常处理掉就可以了。

Terminating a snapshot

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

4. 例子

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

snapshot1

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

snapshot2

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

snapshot3

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

5. 总结

Chandy-Lamport 算法通过抽象分布式系统模型描述了一种简单直接但是非常有效的分布式快照算法。讨论 Chandy-Lamport 算法一定要注意算法的几个前提:网络可靠、消息有序。

Spark 的 Structured Streaming 虽然在官方博客中披露使用的 Chandy-Lamport 算法来做 Failover 处理,但是并没有更细节的披露。相比之下 Flink 在 2015 发布了一篇论文 Lightweight asynchronous snapshots for distributed dataflows 更适合在工程上实现,而且已经应用在了 Flink 项目中。核心思想是在 input source 端插入 barrier 来替代 Chandy-Lamport 算法中的 Marker,通过控制 barrier 的同步来实现 snapshot 的备份和 exactly-once 语义。如果看过 Spark Streaming 那篇论文,对于这个地方很明显的一个疑问就是如何处理 straggler(分布式系统中运行明显慢于其他节点的节点),答案是无法处理。

有时候不得不承认,在大多数情况下,所谓系统架构都是在做 trade-off。

Refer

  1. Chandy K M, Lamport L. Distributed snapshots: Determining global states of distributed systems[J]. ACM Transactions on Computer Systems (TOCS), 1985, 3(1): 63-75.
  2. Carbone P, Fóra G, Ewen S, et al. Lightweight asynchronous snapshots for distributed dataflows[J]. arXiv preprint arXiv:1506.08603, 2015.
  3. Time, Clocks and the Ordering of Events in a Distributed System
  4. Leslie Lamport Homepage
  5. http://tele.informatik.uni-freiburg.de/lehre/ws01/dsys/Lectures/Lecture10.pdf
  6. https://people.cs.umass.edu/~arun/590CC/lectures/Snapshots.pdf
  7. https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/P8-chandy-lamport.pdf
相关文章
|
5月前
|
消息中间件 运维 Kafka
直播预告|Kafka+Flink双引擎实战:手把手带你搭建分布式实时分析平台!
在数字化转型中,企业亟需从海量数据中快速提取价值并转化为业务增长动力。5月15日19:00-21:00,阿里云三位技术专家将讲解Kafka与Flink的强强联合方案,帮助企业零门槛构建分布式实时分析平台。此组合广泛应用于实时风控、用户行为追踪等场景,具备高吞吐、弹性扩缩容及亚秒级响应优势。直播适合初学者、开发者和数据工程师,参与还有机会领取定制好礼!扫描海报二维码或点击链接预约直播:[https://developer.aliyun.com/live/255088](https://developer.aliyun.com/live/255088)
358 35
直播预告|Kafka+Flink双引擎实战:手把手带你搭建分布式实时分析平台!
|
6月前
|
JSON 算法 API
一文掌握 1688 商品详情 API 接口:从入门到实战
1688是国内领先的综合电商批发平台,提供海量商品资源。其商品详情API助力开发者与企业获取商品的详细信息(如属性、价格、库存等),广泛应用于电商数据分析、比价系统及采购场景。API支持GET/POST请求,需传入通用参数(app_key、timestamp等)与业务参数(如product_id)。返回JSON格式数据,包含商品标题、价格、图片链接等详情,提升业务效率与决策精准度。
|
JSON NoSQL MongoDB
MongoDB Compass的安装及使用图文说明(非常详细)
MongoDB Compass的安装及使用图文说明(非常详细)
4279 2
|
安全 测试技术 数据库
测试流程规范--准入准出规则
为了加强测试部软件测试的质量控制及与测试相关部门、人员更好理解测试各阶段的准入/准出条件而建立的准入/准出规范。
2814 0
测试流程规范--准入准出规则
|
5月前
|
机器学习/深度学习 数据采集 人工智能
别让“大数据”变成“大忽悠”——聊聊机器学习的真本事
别让“大数据”变成“大忽悠”——聊聊机器学习的真本事
123 9
|
10月前
|
弹性计算 运维 监控
EMR管控平台全面升级:智能化助力客户实现在离线混部和降本增效
本次介绍EMR开源大数据平台2.0的最新特性,基于微服务架构,提供更稳定高效的服务。平台升级主要体现在智能化和Serverless两个方面。智能化功能利用大语言模型提升运维效率,推出一键诊断和根因分析,缩短问题定位时间。全托管弹性伸缩根据业务动态自动调整资源,提高资源利用率。即将推出的EMR on ACS产品形态支持离在线业务混部,进一步优化资源使用,帮助用户实现降本增效。
|
消息中间件 存储 供应链
数据仓库介绍与实时数仓案例
1.数据仓库简介 数据仓库是一个面向主题的(Subject Oriented)、集成的(Integrate)、相对稳定的(Non-Volatile)、反映历史变化(Time Variant)的数据集合,用于支持管理决策。
43554 86
|
安全 Unix 网络安全
你真的理解ssh吗?5分钟ssh入门到精通
这篇文章提供了SSH的基础知识、基础使用、高级配置方法,以及如何实现SSH的免密登录,帮助用户从入门到精通SSH。
1501 2
|
对象存储 存储 分布式计算
JindoFS: 云上大数据的高性能数据湖存储方案
JindoFS 是EMR打造的高性能大数据存储服务,可以为不同的计算引擎提供不同的存储服务,可以根据应用的场景来选择不同的存储模式。在2019杭州云栖大会大数据生态专场,阿里巴巴计算平台事业部EMR团队技术专家殳鑫鑫和Intel大数据团队软件开发经理徐铖共同向大家分享了云上大数据的高性能数据湖存储方案JindoFS的产生背景、架构以及与Intel DCPM的性能评测。
16680 58
JindoFS: 云上大数据的高性能数据湖存储方案