29

从物理时钟到逻辑时钟

 4 years ago
source link: https://www.raychase.net/5768
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

mQZR7zf.jpg!web 一个分布式系统，经常需要面对同一份数据在不同时间的更改，这个更改可能来自不同节点间数据的同步，也可能来自系统对于客户端写请求的处理，那么这样的更改就可能出现冲突问题。而基于事件发生顺序的冲突问题的解决，是很多分布式系统，在一致性方面，都必须要仔细考虑和妥善处理的问题。我曾经阅读过一些互联网上的材料，但是没有发现哪个能比较系统且简洁地把这个问题和解决描述清楚的，我觉得我也许能够做得更好，于是有了本文。下面我来通过简单的例子介绍这类问题的产生，以及应对的思路。

我来举一个简单例子：

fmUFrui.png!web

你可以看到，往右的箭头表示在一个分布式系统中，A、B、C 三个节点上，实际时间流逝的时间轴。节点 A 在 3:00 的时候给 x 赋值 0，并将赋值事件发送给 C；一分钟后 A 上的另一个事件被触发并发送给 B，并在 3:02 的时候，它进一步产生将 x 赋值为 1 的事件，并发送给 C。很明显这个赋值 x 为 1 的事件实际上是在赋值 x 为 0 的事件之后产生的。

可是呢，由于网络的不稳定等原因，赋值 0 较赋值 1 后同步到节点 C，于是在 C 中 x 的最终值是 0，而不是 1。这显然不是我们期望的。你也许会说，这里举的例子非常极端，网络传输通常不会有那么长的耗时，可是，这个造成数据不一致的原理却是一样的。

物理时钟

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

zayaq27.png!web

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

这种方式可以简单称为物理时钟，即分布式系统中所有的节点都遵循同样的时间，即 “绝对” 时间，但是无论采用怎样的时间同步机制，不但要保证时间同步机制始终生效，还要知道，这样的绝对时间精度总有上限的。 两次数据变更，间隔时间可能非常小，比如就是来源于邻近两行代码的执行而已，这样的时间间隔，即便是最精密的物理时钟，可能都无法感知。

遗憾的是，据我所知，有一些大厂著名的分布式存储系统中，依然在采用这样的方式，可是正如你所见，这样的设计其实就是有问题的。

Lamport 逻辑时钟

Leslie Lamport 在他的论文 Time, Clocks, and the Ordering of Events in a Distributed System 中介绍了逻辑时钟的概念。 逻辑时钟和物理时钟最大的区别是，它不再关心绝对的 “时间” 是多少，转而关心事件之间的发生顺序，即它们的发生先后这一依赖关系。

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

q2iUzyZ.png!web

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

  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 要小，因此丢弃该事件。

冲突识别的问题

很快，人们发现 Lamport 时钟也有局限性，且看下面的例子，描述了单纯应用它的时候出现的问题：

ZZf2mmB.png!web

这个过程如下：

  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 的事件，是很难判断的——即便我们能够以某种方式知道它们谁先发生。举一个具体的例子，公司只有一个免费旅游的名额，员工小明和小王都分别提出申请，那么到底谁的请求被通过？是根据请求到达时间的时间戳，是请求发送的时间戳判断，还是根据小明和小王谁曾经给公司做过的贡献大来判断，这就是应用场景的约束了。有了应用场景，对于这样没有互相依赖关系的事件，我们才能合理地定出冲突处理的策略。不同的分布式系统中也是这样，有根据不同的标准来处理冲突的，甚至也有直接交给用户来处理冲突的（五年前我曾经写过自己对于 Dynamo 的论文的学习笔记，它也在向量时钟冲突的时候也提供了两种解决方式）。

可见，无论我们应该采取哪一种冲突处理的策略，单纯应用 Lamport 时钟存在这样这样一个局限性：并不能很好地识别出 “缺乏事件发生先后的依赖关系而造成冲突” 的情形。

向量时钟

采用向量（Vector）时钟的方式时，前面提到的单纯版本号，就会变成一个版本号数组，上面记录了每一个节点当前的版本号：

YviIR3y.png!web

你看上面的图示，每次版本号变更，都会对于这个版本号向量中相应的那一维自增。当 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]， 这个版本号的每一维，都小于或等于当时的版本号，因此，丢弃该事件 。

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

QjYBryv.png!web

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

最后，就如同任何软件上的解决方案都有两面性一样，向量时钟也不是完美的，比方说，在节点数量巨大的情况下，你可以想象这个版本号的向量维度会非常高，那么传递一个简单的信息，得携带大得多的版本信息这样的 overhead。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK