社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
最近在学习Flink的Fault Tolerance，了解到Flink在Chandy Lamport Algorithm的基础上扩展实现了一套分布式Checkpointing机制，这个机制在论文"Lightweight Asynchronous Snapshots for Distributed Dataflows"中进行了详尽的描述。怀着对Lamport大神的敬仰，我分别下载研读了两篇论文，在这里把一些阅读的收获记录下来，希望能对学习Flink/Blink的同学能有些帮助。
我们先来看看Chandy Lamport Algorithm，“Distributed Snapshots: Determining Global States of a Distributed System”，此文应该是分布式SnapShot的开山之作，发布于1985年（很多同学还没有出生-_-），按照Lamport自己的说法，这篇文章是这么来的：
“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.”
所以说，大神的世界我们不懂，一言不合就写一篇论文。我们言归正传，开始介绍论文中描述的算法。
分布式系统是一个包含有限进程和有限消息通道的系统，这些进程和通道可以用一个有向图描述，其中节点表示进程，边表示通道。如下图所示：p、q分别是进程，c, c'则是消息通道。
另外为了问题描述的简洁，对上述模型还做了假设：消息通道只包含有限的buffer、消息保序、通道可靠等
所谓的Distributed Snapshot，就是为了保存分布式系统的State，那么首先我们需要定义清楚什么是分布式系统的State。考虑到上述分布式模型的定义，分布式系统State同样是由“进程状态”和“通道状态”组成的。
在某一个时刻的某分布式系统的所有进程和所有通道状态的组合，就是这个分布式系统的全局状态。基于上述的双进程双通道的最简分布式系统，为了描述算法，作者设计了一个“单令牌状态”转换系统，两个进程通过接收和发出令牌，会在S0、S1两个State之间转换，整个分布式系统则会在如下所示的4种全局状态（Global State）之间转换。
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
