Time-3-向量时钟

在Lamport逻辑时钟里，对于任意两个事件a和b，我们介绍过对于任意两个事件a和b，如果 a → b，那么 C (a) < C (b)，但是反向并不成立，C(a) < C(b)推不出来a→b。本文介绍的向量时钟（Vector Clocks）可以保证反向也能成立，也即充分条件变成了充分必要条件。

向量时钟算法

向量时钟是1988年由Colin Fidge和Friedemann Mattern提出的，比Lamport老爷子晚了刚好十年。Lamport逻辑时钟存在的问题是不能描述事件的因果关系，C(a) < C(b)推不出来a → b，这样导致即使知道了两个逻辑时钟值，但却不能确定这两个事件的因果关系。

向量时钟可以解决这个问题，它的思想是进程间通信的时候，不光同步本进程的时钟值，还同步自己知道的其他进程的时钟值，算法如下：

分布式系统中每个进程Pi保存一个本地逻辑时钟向量值VCi，向量的长度是分布式系统中进程的总个数。VCi[j]表示进程Pi知道的进程Pj的本地逻辑时钟值，VCi的更新算法如下：

初始化VCi的值全为0，VCi = [0,0,…,0]；
进程Pi每发生一次事件，VCi[i]加一；
进程Pi给进程Pj发送消息，需要带上自己的向量时钟VCi；
进程Pj接收消息，需要做两步操作：

4.1 对于VCj向量中的每个值VCj[k]，更新为max(VCi[k], VCj[k])；

4.2 将VCj中自己对应的时钟值加1，即VCj[j]加1。

向量时钟举例：

图1

向量时钟里的向量是一种偏序关系：

如果向量VCi中的每个元素VCi[k]都小于VCj中的对应元素VCj[k]，则VCi ≤ VCj。
如果VCi中的每个元素VCi[k]都和VCj中的对应元素VCj[k]相等，则VCi = VCj。
如果VCi和VCj不能比较大小，则称两个向量是并发的，VCi || VCj。

从以上两个结论又可以得出：

同一个进程内的两个事件a和b，如果a → b，那么VCi(a) < VCj(b)。
a是Pi进程的消息发送事件，b是Pj进程该消息的接收事件，那么VCi(a) < VCj(b)。

由以上两个结论又可以得出，对于任意两个事件a和b，如果a → b，那么VC(a) < VC(b)。

那么，怎么证明VC(a) < VC(b)可以推导a → b呢？

如果事件a和b在同一个进程内，很显然a → b。

如果事件a和b在不同进程内，比如Pa和Pb。

设VCa = [m, n]，VCb = [s, t]。

因为VCa < VCb，所以m ≤ s，所以必然不早于a之前和不晚于b之后的时间内，Pa向Pb发送了消息，否则Pb对Pa的计数器得不到及时刷新，s就不会小于m。

图2

实际上，可以分为以下图3中的4种情况：

图3

当a = c且d = b，易得a → b。
当a = c且d → b，由c → d ，得到a → b。
当a = c且d → b，由c → d，得到a → b。
当a → c且d → b，由c → d，得到a → b。

综上，VCa < VCb可以推导出a → b。

向量时钟将Lamport逻辑时钟的全序时钟值改成了向量时钟的偏序关系，可以准确刻画事件的顺序。

因果关系与光锥

向量时钟可以反应事件之间的因果关系，图4中对于中间的B4事件，左边蓝色区域内的事件都是B4事件的“因”，右边红色区域内的事件都是B4事件的“果”。而上下白色区域内的事件则属于和B4事件没有因果关系的平行事件。

图4

这有点像狭义相对论中的光锥。光锥是闵可夫斯基时空下能够与一个单一事件通过光速存在因果联系的所有点的集合，简单来说就是事件所能影响的时空范围，它的图形如图5所示：

图5

时空是由三维空间和一维时间构成的，由于人类是三维空间中的生物，没办法感受四维时空，所以光锥图中把三维的时间简化为了二维xy平面。空间平面中的每一个纬度都可以向正负两个方向移动，而时间不可能倒退，只能向正方向移动。

以当前观测点为原点，因为任何物体的运动速度都不可能超过光速，所以它产生的事件造成的影响也不可能超过光速，所以它产生的事件造成的影响也不可能超过光速。这个事件每秒钟在二维空间平面中的传播范围，也不可能超过光每秒钟走过的地方。所以光锥呈现一个圆锥的形状。光锥分为未来光锥和过去光锥，未来光锥指当前发生的事件对未来造成影响的范围，而过去光锥指过去多大时空范围的事件能对现在造成影响。