分布式快照算法: Chandy-Lamport

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

上一篇文章最后说到 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 的改进算法。

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。

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,我们可以认为这是一个局部快照。那么全局快照就可以通过将所有的进程的局部快照合并起来得到。

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)

例子

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

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

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

image.png

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

image.png

总结

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。

目录
相关文章
|
5天前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
18 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
3月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
16天前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
17天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
1月前
|
算法
基于粒子群算法的分布式电源配电网重构优化matlab仿真
本研究利用粒子群算法(PSO)优化分布式电源配电网重构,通过Matlab仿真验证优化效果,对比重构前后的节点电压、网损、负荷均衡度、电压偏离及线路传输功率,并记录开关状态变化。PSO算法通过迭代更新粒子位置寻找最优解,旨在最小化网络损耗并提升供电可靠性。仿真结果显示优化后各项指标均有显著改善。
|
3月前
|
存储 算法 NoSQL
(七)漫谈分布式之一致性算法下篇:一文从根上儿理解大名鼎鼎的Raft共识算法!
Raft通过一致性检查,能在一定程度上保证集群的一致性,但无法保证所有情况下的一致性,毕竟分布式系统各种故障层出不穷,如何在有可能发生各类故障的分布式系统保证集群一致性,这才是Raft等一致性算法要真正解决的问题。
112 11
|
3月前
|
存储 Java 流计算
Flink 分布式快照,神秘机制背后究竟隐藏着怎样的惊人奥秘?快来一探究竟!
【8月更文挑战第26天】Flink是一款开源框架,支持有状态流处理与批处理任务。其核心功能之一为分布式快照,通过“检查点(Checkpoint)”机制确保系统能在故障发生时从最近的一致性状态恢复,实现可靠容错。Flink通过JobManager触发检查点,各节点暂停接收新数据并保存当前状态至稳定存储(如HDFS)。采用“异步屏障快照(Asynchronous Barrier Snapshotting)”技术,插入特殊标记“屏障(Barrier)”随数据流传播,在不影响整体流程的同时高效完成状态保存。例如可在Flink中设置每1000毫秒进行一次检查点并指定存储位置。
63 0
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。

热门文章

最新文章