判断因果关系的向量时钟算法( 二 ) _向量时钟算法

如果仔细观察这条链的话会发现它并不能真实反映事件发生的顺序，会存在不公平的情况。但至少因果关系可以保证。

以上这个算法被称为是逻辑时钟算法，它相当于重新定义了一个逻辑上的时间来代替真实物理世界的时间。由于它是Lamport大神提出的，所以也被称为是Lamport逻辑时钟算法。

向量时钟
在上面的文章当中我们也分析了，逻辑时钟算法有一个问题是虽然保证了因果顺序，但也牺牲了公平。比如上图当中B3和A2发生在同一时间，但是B3排在A2的前面。也就是说我们通过比较 C(A) 和 C(B)无法得出真实的发生顺序。

为了解决这个问题，大神们在Lamport的逻辑时钟上做了改进，提出了向量时钟算法。

向量时钟和逻辑时钟的原理几乎一样，只不过对于每个节点或者进程而言，它维护的不再是一个单个的时间戳，而是一个时间戳构成的向量。向量的维度就等于进程的数量，也就是说每个进程不止记录自己的时间戳，而且还会记录其他进程的时间戳，这些时间戳组合在一起，就构成了一个时间向量。

在事件的处理上，向量时钟算法和逻辑时钟基本一致。

在进程i发生事件（接收、发送或者是内部事件）的时候，，这时候C是一个时间戳向量，i是进程i的下标。
当进程i发送消息的时候，会将消息和自己的时钟向量一同发出。
当进程i收到进程j发送来的消息时，会根据一起发送来的时钟向量更新自己的时钟向量：

同样，由于单个时间戳换成了向量时钟，所以我们判断因果顺序的方式也需要变化。在向量时钟算法当中，我们定义如果事件A在事件B之前，那么需要满足两个条件：

对于所有的下标K，都有
存在下标，使得

也就是说至少需要一个维度存在严格小于，其他维度全部小于等于，才可以看做是因果关系。原因也很简单，因为如果存在消息传递，那么至少有一个维度会带来增加。如果两个事件的向量时钟相等，说明两者是没有发生过信息传递的，自然也就不符合我们定义的因果关系。

我们回顾一下之前的例子，将节点改写成向量时钟之后，得到的结果如下图：

文章插图
【判断因果关系的向量时钟算法】
将逻辑时钟优化成向量时钟之后，就可以严格判断因果关系了。如果两个节点的时钟向量没有大小关系，那么可以说明这两个事件之间没有联系。

实际应用
和我们之前介绍的一样，向量时钟算法主要用在分布式系统的因果关系的检测上。而因果关系之所以需要检测，往往是因为我们面临多个副本同时更新，我们需要检测这些副本的冲突。
我们来一起看一个例子，这个例子是亚马逊的Dynamo系统，它是一个KV的存储系统，类似于redis，可以简单理解成缓存。为了高可用，Dynamo保证即使在出现网络分区或者机器宕机的时候，仍然可读可写。但是这会导致一个问题，当网络分区恢复之后，多个副本的数据可能会出现不一致的情况，这个时候我们就需要通过向量时钟算法来检测冲突了。

文章插图

假设一开始的时候客户端W创建了一个记录X，这个记录是由机器 Sx 来负责的。那么则形成了数据 D1
和它对应的向量时钟 [Sx, 1] 。

之后，客户端继续更新记录X，同样由机器 Sx 执行，形成了新数据 D2，它的向量时钟变成 [Sx, 2]，它和 D1 存在因果关系。所以我们可以知道 D2 是最新的数据。

再之后，客户端继续更新X，这次由 Sy 执行，产生了D3，同样，可以知道操作结束之后它的向量时钟为 [Sx, 2], [Sy, 1] 。

与此同时，另一个客户端读入了 D2 之后，在机器 Sz 上更新产生了 D4 ，此时的向量时钟是 [Sx, 2], [Sz, 1] 。

我们来分析一下，如果这时候有客户端同时读到 D2 和 D3 ，那么通过向量时钟可以判断出来，D3 是最新的数据。如果同时读到 D3 和 D4 ，由于这两者的向量时钟并没有因果关系，所以无法判断谁是最新的数据，这就产生了冲突。

但是必须要说明的是，向量时钟算法只能检测冲突，并不能解决冲突，冲突需要客户端自己解决。如果客户端判断，决定应该以 Sx 的节点为准，那么最后的数据就会变成 D5 ，此时的向量时钟为[Sx, 3], [Sy, 1], [Sz, 1] 。