向量时钟的本质

撰文 | 陈清扬

读到一篇ACM Queue上好文章（https://queue.acm.org/detail.cfm?id=2917756），与诸君分享。

分布式系统中有两大问题：一没有全局时钟，二没有共享内存。很多时候我们都需要引入时间的概念，譬如来确定事件之间的顺序和因果关系。那分布式系统中既然没有全局的时钟，我们又该如何确定事件的顺序呢？

PS：不需要背景介绍的读者可以直接跳到后面讲因果历史的部分。

1

逻辑时间与Lamport Timestamp

Leslie Lamport在其1978年著名的论文《Time, clocks, and the ordering of events in a distributed system》中提出了逻辑时间，即用一个整数来表示一个事件的逻辑时间，以及happened-before 顺序。可以总结如下：

简而言之，每个线程都用一个integer来simulate它自己的时间，对于本地事件或者消息的发送和接收按照以下规则来更新时间。

• 每一次发生本地事件，该线程的时间+=1

• 每一次发送消息，发送的线程的时间先+=1，然后再发送。发送的消息中会包含它的时间

• 每一次接收消息，接收的线程先获取消息中带有的时间，再和它自己的local时间对比，取最大值后，再+=1作为自己新的local时间

这种更新时间的方式称为Lamport timestamp或者Lamport clock。它的确为整个系统定义了一个全序（total order），但是它没有说明事件是否concurrent，根据Lamport的论文，concurrent的定义是：

即事件a和b的时间戳没有happened-before关系，无法比较。这就是一个偏序（partial order），但是上述的Lamport timestamp算法没有办法表示偏序，即（引用维基百科一段话）

即，根据C(a) < C(b)，我们并不能完全infer出a和b的happened-before关系。

2

向量时钟

向量时钟（Vector Clock）其实是Lamport clock的一种很自然的extension了，其定义的是偏序而不是全序，于是可以表示concurrent的关系，据考证类似概念最早由Rivka Ladin和Babara Liskov于1986年提出，vector clock由Colin Fidge和Friedemann Mattern于1988年左右首次使用。Vector Clock可以总结如下：

Vector clock的更新方法和Lamport clock类似，区别在于现在每个线程需要维护一个vector来记录它眼中每一个线程（包括它自己）的时间。然后发送消息的时候，整个vector都要包含在消息里。接收消息的时候，把自己的local时间+=1，然后对于vector中的其他每一个项都需要用上述max的办法更新，以获取其他线程最新的时间。

这里的重点在于上面图片中的等价符号，=>的部分是显然的（根据VC更新的规则），但是<=的部分是如何证明的呢？即，是否存在当V(e) < V(f)的时候，e和f之间并没有happened-before关系？

这个证明我个人觉得并没有那么显然，需要一番思考，但是假如我们从Causal history的角度来看就明显多了。

3

因果历史（Causal History）

因果历史是检查因果关系的一个直观的方法。每个线程维护一个集合，然后每次碰到local event，给这个event一个名字，然后加入到集合中。每次发送消息则发送自己的集合，每次接收消息则合并消息的集合。下图是一个例子：

此时，要知道两个event之间的因果关系或者happened-before关系，只需要看他们对应的集合是否一个包含另一个，即set inclusion test。

这样集合的表示虽然直观，但是并不compact，我们可以看到可以优化的地方。譬如当node B向node C发送{a1,a2,b1,b2,b3}的时候其实只需要发送最近的events，即{a2, b3}就行了。因为a2发生已经暗含了a2之前的A上的事件也已经发生了。b3也是同理，也暗含了b1, b2一定已经发生了。所以这里其实本质上对于每一个线程，我们只需要发送和记录一个数字就行了，这样优化以后得到的结果便是Vector Clock！所以从这个角度，VC其实就是Causal History的一种压缩表示，一种编码。

现在我们再来想想前面的证明，是否存在当V(e) < V(f)的时候，e和f之间并没有happened-before关系？从Causal History的角度，这个证明就很简单了，如果V(e) < V(f)，即相当于f包括了e的集合，而f要知道e的那些事件，必须要通过消息的发送，即构成了happened-before关系。

如果纯从VC的角度证明，可以这样想。假设e和f分别是线程E和F上的事件。happened-before可以理解成一种图上的路径，两种happens-before关系构成了有向边，如果e没有路径到f，那F最多只能知道上次E给他发消息的时候E的时间（在e之前）。而当E的状态达到e的时候，E的local time已经超过上次给F发消息的时候的时间了，所以V(e)绝不可能< V(f)。同理也可证，假如f没有路径到e，V(f)也绝不可能 < V(e)。于是我们证明了Definition 3中<=的部分，即V(e) e -> f。

本文获得授权后发布。原文：https://zhuanlan.zhihu.com/p/419944615

其他人都在看

• OneFlow v0.5.0正式上线

• GPU架构演进十年，从费米到安培

• 玩转大模型，是时候展示你真正的技术了

• 动态调度的“诅咒”| 原有深度学习框架的缺陷③

• OneFlow框架添加算子实践：expand和repeat

• 计算机架构史上的一次伟大失败，多数人都不知道

点击“阅读原文”，欢迎下载体验OneFlow新一代开源深度学习框架