最近读了一篇 Paper, 提出了一种 Bloom Clock 的方法, 用来解决分布式系统中, 两个事件的因果关系的判断问题.

为什么判断因果 “没那么简单”

我们经常想知道两个事件哪个发生在前, 比如 A 和 B 有一个公共账户, A 和 B 各自从账户取走了 100 元. 如果账户余额不到 200 元, 那么谁先取就很重要了. 这看上去是个很简单的问题, 看一下表就好了. 然而事情并不简单. 俗话说得好,

A man with a watch knows what time it is. A man with two watches is never sure.

在分布式系统中, 每台机器都有一个自己的时钟, 有的快有的慢, 但看时间戳, 谁也说不清哪个先哪个后, 你说难办不难办.

在尝试解决这个先后判断问题之前, 我们先想一想, 先后到底重要吗? 能判断先后当然好, 如果能有一个事件的严格的全序关系, 实际上我们就能做到 consensus 或者说 strong consistency (这个证明这里就不做了). 但是在不需要强一致的情况下, 有时候谁先谁后不一定重要, 就比如 A 从自己账户取走 100 元, B 也从自己的账户取走 100 元, 我们没比较分清谁先谁后. 所以, 只有在某些情况下, 我们才需要判断出来. 而这种场景大部分都是需要判断两个有因果关系的事件的先后关系. 如果两个事件没有因果关系, 实际上不存在所谓的先后. 这句话有点绕, 之后尝试解释一下.

光锥是什么

在解释之前我们再用(我仅有的)物理学知识分析一下因果关系. 物理学中有个概念: 光锥. 以下是来自中文维基百科的解释:

光锥是 … 时空下能够与一个单一事件通过光速存在因果联系的所有点的集合

光锥

在掌握的物理知识很少的情况下, 我觉得这光锥还是比较好理解的. 光锥就是一个四维的锥体, 随着时间不断扩大. 举个例子, 如果在时间点 *t1地点 *l1*发生了事件 A, 在时间点t2(>t1)地点l2*发生了事件 B, 并且两个地点之间的距离大于光速 * 时间差, 那么 A 和 B 是没有因果关系的, 即 *(t_2, l2)*这个时空坐标不在 *(t1, l_1)*的光锥内. 为什么一定没有因果关系呢? 因为信息传播的最大速度是光速, 连光都来不及到, 事件 B 一定对事件 A 一无所知, 更别提因果关系了.

向量钟, i.e. Vector Clock

上面讲了这么多, 我相信大家都能发现, 因果关系是一种偏序关系 (虽然我觉得不讲上面那么多, 大家也能发现). 那么现在回到今天的主题. 为了在分布式系统中确定两个事件的因果关系, 已经有很多工作了, 最广为人知的应该就是 Vector Clock 了吧. 以下是来自维基百科的图片.

Vector

A, B, C 三台机器都本地维护了一个从机器 ID 到一个整数的 Map, 这个整数是一个逻辑事件戳, 它遵循以下规则:

  1. 每台机器初始化之后, Map 只包含一个 entry, key 是自己的 ID, value 是 0, 如上图最左边. 每当自己本地发生一个事件 (发出/收到一个消息), 就把自己 ID 增加 1.
  2. 当发送消息的时候, 机器会把自己本地的 Map 发送给别人, 比如 C 发送自己的 {c: 1} 给了 B.
  3. 当受到消息的时候, 机器会把自己本地的 Map 和受到的 Map 作 merge. Merge 的逻辑是对每一个 key, 取两个 Map 中较大的很多值.

有了这个 Map 之后, 比较两个事件的因果关系就很简单, 只要比较两个事件发生时的 Map 就可以了. 如果一个 Map 的每一个 key 对应的 value 都大于等于另一个 Map 对应的 value, 则我们说第一个 Map 对应的事件是第二个 Map 对应事件的”果” (有点佛学的意思了…). 如果 “互有胜负”, 说明没有因果关系.

向量钟的问题

向量钟这个算法简洁优美, 但是在机器数量很多的情况下会一个很大的额外开销. 要是一个集群 1000 台机器, 那么这个 Map 就要有 1000 个 entry. 假设不做任何压缩, 然后用 4 个字节保存 key, 4 个字节保存 value, 那么每个 RPC 会有 8K 的 overhead. 而大部分 RPC 本身的 payload 才多少. 带宽作为稀缺资源, 怎么能浪费在这种事上!

Bloom Clock

俗话说的好

人生就是各种 Trade Off

我们不想用这么多带宽, 那就牺牲点什么东西. 牺牲什么呢, Bloom Clock 提议牺牲一下精度好了. 它的思想实际上非常简单, 就是利用 Bloom Filter 的特性. 它维护了一个 Counting Bloom Filter, 每个事件被 hash 之后会增加对应 bucket 的 counter. 这个 counter 的列表就相当于 Vector Clock 中的 Map. 但是这个 counter 列表的大小会比 Map 小很多.

使用了 Bloom Filter 之后, 很显然, 只会有 false positive. 而发生 false positive 的概率是可以通过调节参数控制的.

没有因果关系就无所谓先后?

上面挖的坑还是要埋一下

如果两个事件没有因果关系, 实际上不存在所谓的先后. 这句话有点绕, 之后尝试解释一下

假设有一个 git 项目, 其中有一个文件 .gitignore. 最开始只有一行. 现在有两个人分别在不知情的情况下各自在下面加了一行不一样的内容. 那么问题来了, merge conflict! 很明显, 两个修改行为是没有因果关系的, 但是会有先后关系 (我们可以看 commit log). 那么这个先后关系到底重不重要内, it depends. 在我们这个情况下, 我感觉哪个在前都没有关系.

上面这个例子如果没能说服你的话, 我建议你读一读 Dynamo DB 的论文中关于如何 resolve conflict 的部分.