判断因果关系的向量时钟算法

今天的文章来聊聊向量时钟，在前文介绍分布式系统一致性的时候，曾经介绍过，在弱一致性模型当中会有一个因果性的问题。向量时钟算法正是设计出来解决因果关系问题的。

我们来回顾一下因果问题，在实际日常的网页行为当中，部分行为存在因果关系。比方说知乎里面回答问题，显然得先有一个同学提出问题，然后才能有各路大V谢邀解答问题。但是由于是分布式系统，有可能问题和回答并不是存放在同一台机器，导致有可能它们更新的顺序不一致，所以就有可能会出现用户在访问知乎的时候，发现自己关注的大V回答了某个问题，但是点进去问题却是空的。这种幽灵情况不是灵异事件，只是单纯的分布式系统设计没过关，没有考虑因果问题。

有的同学可以会说，这个不难啊，我们加入时间戳啊。时间戳的确可以解决一部分问题，但是并不能解决所有问题。有了时间戳之后，我们可以获得事件发生的时间，但是仍然不知道不同的数据之间的因果关系。由于分布式系统存在延迟，也不能简单地通过时间戳来做过滤或者筛选。不过，虽然单纯的时间戳不行，但已经非常接近了。

我们日常生活当中用事件发生的时间来反应事物发生的顺序，我们说的先后顺序，其实是以客观上的时间作为参考系参考得到的结果。问题来了，我们能不能找到或者构造出其他的参考系来反应事物发生的顺序呢？

当然是可以的，不然也没有这篇文章了，这就是大名鼎鼎的逻辑时钟算法。多说一句，逻辑时钟算法和许多其他分布式算法一样，同样源于大神Lamport的发明。

逻辑时钟

我们还用之前的例子来思考一下，一个人在知乎提交了问题，另一个人回答了问题，这是两个事件。我们第一反应自然是通过两个事件发生的时间来反应因果顺序，但我们仔细分析一下这个场景。后面那个人既然能回答问题，说明他一定是看到了问题。也就是说回答问题和看到问题之间发生了交互，所以很自然地可以想到，我们是不是可以用两个系统或者是两个事件之间有没有发生过信息交互来反应因果顺序呢？

于是基于这个思想，Lamport大神提出了逻辑时钟的概念。逻辑时钟概念的核心就是刚才我们说的，两个事件之间建立因果关系的前提是，两个事件之间发生过信息传递。

我们梳理一下可能发生的事件的种类，可以分成三种。第一种是发生在某个节点内部，也就是说没有和其他任何节点发生联系。第二种是发送事件，是事件的发送方。第三种是接收事件，和第二种对应，是事件的接收方。明确了这三点之后，我们就可以用时间戳来表示这三种情况了。首先，我们假设每个节点内部都会维护一个时间戳，记录当下节点的状态。

针对上面说是三种时序关系呢，我们设定三种策略。

首先是内部事件，对于节点内部发生事件呢，很简单，我们只需要将它的时间戳增大1，表示发生过了某件事情。

其次是发送事件，节点内部的时间戳自增1，并且在发送消息当中加上这个时间戳。

最后是接收事件，由于会额外接收到一个时间戳，所以我们需要利用这个时间戳来更新节点内部的时间戳。更新的方法也很简单，假设节点内部的时间戳是t，跟着消息传递而来的时间戳是t', 那么: t_new = max(t + 1, t') 。

我们分析一下上面这个关系，假设当下有事件A和B，如果事件A是事件B发生的前提。那么显然事件A的时间戳小于事件B。如果反过来，事件A的时间戳小于B，能说明事件A是事件B的前提吗？并不能，所以时间戳较小是因果关系的必要条件，但不是充分条件。

由于会存在多个节点或者进程时间戳相等的情况，所以我们把进程id也作为比较的银子。我们用C表示一个事件的时间戳，P表示事件的进程pid。如果事件A排在事件B前面，只有两种可能：

1. C(A) < C(B)
2. C(A) = C(B) and P(A) < P(B)

我们来看一个例子：

上图当中有A、B和C三个进程，其中P(A) < P(B) < P(C)。图中每一个箭头都代表传递的消息。

我们根据重新定义的时序关系，可以得到这些点的先后顺序是：

C1⇒B1⇒B2⇒A1⇒B3⇒A2⇒C2⇒B4⇒C3⇒A3⇒B5⇒C4⇒C5⇒A4

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

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

向量时钟

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

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

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

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

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

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

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

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

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

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

实际应用

和我们之前介绍的一样，向量时钟算法主要用在分布式系统的因果关系的检测上。而因果关系之所以需要检测，往往是因为我们面临多个副本同时更新，我们需要检测这些副本的冲突。

我们来一起看一个例子，这个例子是亚马逊的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]。

除了知乎之外，其实还有很多场景下的一致性问题都需要考虑因果关系。因此向量时钟算法在分布式领域可以说是鼎鼎大名，使用非常广泛。在刚听到这个名字的时候，往往会觉得它非常晦涩难懂，但实际深入了解之后，会发现其实并不困难，反而非常有趣，这也算是学习的乐趣之一吧。

今天的文章就到这里，如果觉得有所收获，请顺手点关注或转发个吧，你们的支持是我最大的动力。