您的位置:  首页 > 技术杂谈 > 正文

向量时钟的本质

2021-10-25 12:00 https://my.oschina.net/oneflow/blog/5286655 OneFlow深度学习框架 次阅读 条评论

fe89005e01fdbe9f26055d3069426b57.png

撰文 | 陈清扬

读到一篇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 顺序。可以总结如下:

af9c9c54b3106c45b85141f34f90b134.png

d20c142caa2e5fb6e4302d0bd9ba11f6.png

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

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

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

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

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

560052509935a4e7b61c1bb1750eb6d8.png

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

17e49e5021895cad4d4c0df1fc8f8c2d.png

即,根据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可以总结如下:

bed7fb7776171d173858a46896c12bc4.png

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一个名字,然后加入到集合中。每次发送消息则发送自己的集合,每次接收消息则合并消息的集合。下图是一个例子:

5a8a02615480f9ccd5fe59ad6a1fbc79.png

此时,要知道两个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) < V(f) => e -> f。

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

其他人都在看

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

a00a3378ea3391bbf3267bb73a93a8b0.png

  • 0
    感动
  • 0
    路过
  • 0
    高兴
  • 0
    难过
  • 0
    搞笑
  • 0
    无聊
  • 0
    愤怒
  • 0
    同情
热度排行
友情链接