本系列文章链接如下：

本系列文章主要介绍计算机系统中时钟的处理。主要内容包含NTP，Lamport逻辑时钟，向量时钟，TrueTime等。本文是第三篇，介绍向量时钟。

在《计算机的时钟（二）：Lamport逻辑时钟》中，我们介绍过对于任意两个事件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]
进程Pi每发生一次事件，VCi[i]加1。
进程Pi给进程Pj发送消息，需要带上自己的向量时钟VCi。
进程Pj接收消息，需要做两步操作。

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

4.2 将VCj中自己对应的时钟值加1，即VCj[j]加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) < VCi (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。

实际上，可以分为以下几种情况：

当a = c且d = b，易得a → b。
当a = c且d → b，由传递性，得a → b。
同样对于d = b且a → c的情况。
当a → c且d → b，根据进程内的算法逻辑性和传递性，也很容易得出结论。

综上: VCa < VCb 推导出 a → b 得证。

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

因果关系与光锥

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

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

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

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