OPED 是 (我自己发起的) One Paper Each Day 挑战, 即每天读一篇 Paper, 领域不限.

这是 OPED 挑战的第一篇, 论文为 Distributed Snapshots: Determining Global States of Distributed Systems

在一个分布式的系统里, 由于存在时钟的问题, 我们很难获得一个有意义的全局的状态. 论文里就举了一个很好的例子. 假设我们有 100 个摄像师, 各自都被分配了天空的一块区域. 现在我们需要他们拍摄整块天空的状态, 那么就需要他们在 8:00 拍摄, 然后将所有人的照片合并起来. 因为没法做到同时拍摄, 那么照片之间的时间戳就会不一样, 这样就会出现同一只小鸟出现在多张照片中的情况.

为了解决分布式系统中如何产生分布式快照的问题, 这篇论文提出了一种很有意思的方法, 这里先卖个关子.

概念

在介绍这个方法之前, 我们先明确一下, 一个分布式快照需要包含哪些信息.

一个分布式系统, 自然包含了很多个节点, 每个节点都有自己的状态, 那么显然, Node State 自然是分布式快照必须包含的信息. 那还需要什么东西吗? 答案自然是肯定的. 考虑这种情况:

有两个节点, 和一个 Token. 这两个节点都有两种状态: 占有 Token 和不占有 Token. 每个节点的

由此我们可以发现, 我们还需要各个节点之间还在传输中的数据, 才能获得完整的状态信息. 这个传输中的数据构成一个有序的序列, 我们管它叫 Channel State. 有了这两部分数据, 一个分布式快照就完整了.

算法

概念我都懂了, 那么到底怎么生成状态快照呢?

为了解决这个问题, 实际上之前已经有很多方式了. 但是很多方式都有一些限制, 要么会侵入业务逻辑, 要么会 block 实际的数据处理. 这篇论文提出了一种新的方法, 完全不会阻塞数据处理. 这个算法要求定期的在信道中发送一个 marker, 节点收到 marker 之后会按照定义的规则执行一定的操作. 这些规则很简单, 如下:

  1. 如果一个节点收到 marker 时, 还没有记录自己的状态, 那么它就会记录自己当前的状态, 即 node state.
  2. 如果一个节点收到 marker 时已经记录了自己的状态, 那么从自己记录状态到现在所有收到的消息, 都是发送消息的信道的状态, 即 channel state.

在每个节点和信道的状态都记录完之后, 整个快照就是所有这些状态的合集.

第一个规则实际上很好理解, 你可以想象为一个 record 走完数据处理链路的每个节点, 就记录下自己的状态, 这些记录下来的状态合并之后就是整个系统处理完这个记录之后的整体状态.

那么为什么一个节点收到 marker 的时候已经记录了自己的状态呢? 以为数据处理的链路可能有环, 一个 marker 可能又会回到之前经过的某个节点. 因为这个节点已经记录过自己的状态了, 那么在”第一次收到 marker 并记录了自己状态的那个瞬间”到”再一次收到 marker” 之间收到的消息怎么体现在快照中内? 第二条规则要求我们把这些作为信道的状态记录.