vlambda博客
学习文章列表

一个分布式系统，经常需要面对同一份数据在不同时间的更改，这个更改可能来自不同节点间数据的同步，也可能来自系统对于客户端写请求的处理，那么这样的更改就可能出现冲突问题。而 基于事件发生顺序的冲突问题 的解决，是很多分布式系统，在一致性方面，都必须要仔细考虑和妥善处理的问题。

下面我来通过简单的例子介绍这类问题的产生，以及应对的思路。

往右的箭头表示在一个分布式系统中，A、B、C 三个节点上，实际时间流逝的时间轴。

1. 节点 A 在 3:00 的时候给 x 赋值 0，并将赋值事件发送给 C；
2. 一分钟后 A 上的另一个事件被触发并发送给 B，并在 3:02 的时候，它进一步产生将 x 赋值为 1 的事件，并发送给 C；
3. 很明显这个赋值 x 为 1 的事件实际上是在赋值 x 为 0 的事件之后产生的。由于网络的不稳定等原因，赋值 0 较赋值 1 后同步到节点 C，于是在 C 中 x 的最终值是 0，而不是 1。

1. 物理时钟

解决这个问题，最直接的思路显然是采用物理时钟，也就是利用绝对时间。

1. 给对 x 的赋值事件，增加一个时间戳，3:00 的时候，节点 A 产生了赋值为 0 的事件；
2. 3:02 的时候，节点 B 产生了赋值为 1 的事件。后者先到达 C 的时候，赋值事件生效；
3. 但是在前者到达 C 的时候，节点 C 检测到上一次的数据变更时间戳是 3:02，比后抵达的事件（时间戳是 3:00）后发生，因此丢弃该赋值事件，这样就保证了最终 C 的数据的最终正确性。

这种方式可以简单称为 物理时钟，即分布式系统中所有的节点都遵循同样的时间，即 “绝对” 时间，但是无论采用怎样的时间同步机制，不但要保证时间同步机制始终生效，还要知道，这样的绝对时间精度总有上限的。

两次数据变更，间隔时间可能非常小，比如就是来源于邻近两行代码的执行而已，这样的时间间隔，即便是最精密的物理时钟，可能都无法感知。

2. 逻辑时钟

逻辑时钟和物理时钟最大的区别是，它不再关心绝对的 “时间” 是多少，转而 关心事件之间的发生顺序，即它们的发生先后这一依赖关系。

逻辑时钟 的规则很简单，每个节点都维护一个永远递增的 “时间戳”，为了和前面的物理时间戳区分，我把它称为版本号，事件的传播必须携带版本号。每当有事件产生和发送，版本号就自增 1；如果有事件到达，如果事件版本号比当前版本号还小就抛弃，否则就接纳事件，并更新当前的版本号为当前版本号和事件所携带的版本号二者的最大值。

你看图示，这个过程简单描述如下：

1. 最开始 A、B、C 三个节点的版本号都是 0；
2. 在节点 A 产生了给 x 赋值 0 的事件，版本号更新为 1，这个事件被发送给 C；
3. 接着版本号为 2 的事件传递给了 B，B 的版本号就更新为自己的当前版本号（为 0）和接收事件的版本号（为 2）二者的最大值 2，由此触发产生给 x 赋值 1 的事件并发送给 C，这时的版本号为 3；
4. C 首先收到了版本号为 3 的事件，比当前版本号 0 要大，因此接纳事件，赋值 x 为 1，并更新当前版本号为 3；
5. C 接着又收到了版本号为 1 的事件，比当前版本号 3 要小，因此丢弃该事件。

不同事件源头带来的冲突问题

逻辑时钟版本号也有局限性，且看下面的例子，描述了单纯应用它的时候出现的问题：

这个过程如下：

1. 节点 B 先发生某事件，版本号更新为 1，接着产生数据变更事件，赋值 x 为 0，版本号为 2，此事件需要同步到 C；
2. 接着 A 上产生赋值 x 为 1 的事件，版本号为 1，同步到 C；
3. B 发送过来的同步事件被 C 接纳，C 上版本号为 2，x 被赋值为 0；
4. A 发送过来的同步事件被 C 丢弃，因此此时 C 的版本号已经是 2 了，大于 B 同步过来的版本号 1。

这里的问题是，实际这个赋值为 0 的事件，要比赋值为 1 的事件 ，从绝对时间的角度来说，要更早发生，可是最终在 C 上这个值却是 0，也就是说，后发生的赋值事件反而被丢弃了。

疑问：即便我们能够实现一种机制，解决这个问题，即冲突的时候让这个绝对时间较晚发生的变更生效，就一定正确吗？

解析：前面三个图的例子中，赋值事件事件传递链中，依赖关系的源头都在 A 上面，这样这两个源头在 A 上的先后顺序是非常清晰的——谁先发生，谁后发生，就好比是两行不同位置的代码，谁先执行都是很明确的。可是，这第四个图就不是这样的了，一个赋值事件在 A 上生成，另一个在 B 上，且二者的传递链并没有交集。虽说我画的是分布式系统中的两个物理节点，可即便在同一个节点的不同线程或进程中，这样的情况也是可能发生的。

因此，不给出明确的应用场景，在缺乏事件依赖关系的情况下，到底应该丢弃哪一个赋值 x 的事件，是很难判断的——即便我们能够以某种方式知道它们谁先发生。是根据请求到达时间的时间戳，是请求发送的时间戳判断，还是根据小明和小王谁曾经给公司做过的贡献大来判断，这就是应用场景的约束了。有了应用场景，对于这样没有互相依赖关系的事件，我们才能合理地定出冲突处理的策略。

3. 向量时钟

版本号逻辑时钟存在不同事件源头冲突问题，因为版本号的维度其实是事件维度的，向量时钟的引入其实是对事件维度的版本号的扩充，做到了事件和节点维度的版本号，形成一个向量。

每次版本号变更，都会对于这个版本号向量中相应的那一维自增。当 C 收到事件的时候，根据这个向量版本号的大小就可以做出应该接纳还是拒绝的决定了：

1. C 的初始版本号是 [A:0, B:0, C:0]，它先收到了 x 赋值为 1 的事件，其版本号是 [A:2, B:1, C:0]，这个版本号的每一维，都等于或大于初始版本号，因此，接纳该事件；
2. 之后收到了 x 赋值为 0 的事件，其版本号是 [A:1, B:0, C:0]，这个版本号的每一维，都小于或等于当时的版本号，因此，丢弃该事件。

相应地，我们再来看看前面那个 “冲突识别” 的例子：

如图所示，在 C 上比较这两个事件的时候，一个事件的向量是 [A:0, B:2, C:0]，另一个则是 [A:1, B:0, C:0]。前者在向量 B 上更大，而后者则在向量 A 上更大，这样的矛盾就意味着冲突的发生。既然冲突能够被识别出来，我们就可以根据系统的预定义来选择冲突处理策略了。

弊端：就如同任何软件上的解决方案都有两面性一样，向量时钟也不是完美的，比方说，在节点数量巨大的情况下，你可以想象这个版本号的向量维度会非常高，那么传递一个简单的信息，就要携带一个巨大的版本信息，甚至于版本信息已经远远大于事件需要传递的信息本身了。

4. Lamport 逻辑时钟

1978年Lamport在《Time, Clocks and the Ordering of Events in a Distributed System》中提出了逻辑时钟的概念，来解决分布式系统中区分事件发生的时序问题。

逻辑时钟是为了区分现实中的物理时钟提出来的概念，一般情况下我们提到的时间都是指物理时间，但实际上很多应用中，只要所有机器有相同的时间就够了，这个时间不一定要跟实际时间相同。更进一步，如果两个节点之间不进行交互，那么它们的时间甚至都不需要同步。因此问题的关键点在于节点间的交互要在事件的发生顺序上达成一致，而不是对于时间达成一致。

Lamport 逻辑时钟中提出的时间戳概念其实就是类似于版本号，具体的分析过程参考第2节。

Lamport 逻辑时钟原理如下：

1. 每个事件对应一个Lamport时间戳，初始值为0；
2. 如果事件在节点内发生，本地进程中的时间戳加1；
3. 如果事件属于发送事件，本地进程中的时间戳加1并在消息中带上该时间戳；
4. 如果事件属于接收事件，本地进程中的时间戳 = Max(本地时间戳，消息中的时间戳) + 1

假设有事件a、b，C(a)、C(b)分别表示事件a、b对应的Lamport时间戳，如果a发生在b之前(happened before)，记作 a -> b，则有C(a) < C(b)，例如图1中有 C1 -> B1，那么 C(C1) < C(B1)。通过该定义，事件集中Lamport时间戳不等的事件可进行比较，我们获得事件的偏序关系(partial order)。注意：如果C(a) < C(b)，并不能说明a -> b，也就是说C(a) < C(b)是a -> b的必要不充分条件。

如果C(a) = C(b)，那a、b事件的顺序又是怎样的？值得注意的是当C(a) = C(b)的时候，它们肯定不是因果关系，所以它们之间的先后其实并不会影响结果，我们这里只需要给出一种确定的方式来定义它们之间的先后就能得到全序关系。注意：Lamport逻辑时钟只保证因果关系（偏序）的正确性，不保证绝对时序的正确性。