“凭什么说你比我先？”——没有上帝时钟，如何判断“谁先谁后”？

物理时钟在分布式系统中难以完美同步，导致无法仅凭物理时间戳来精确判断事件的因果顺序。逻辑时钟为此而生。

兰伯特逻辑时钟

兰伯特逻辑时钟（Lamport Logical Clock）为系统中的每个事件分配一个单调递增的数字（时间戳），用于捕捉事件间的偏序关系（Happened-Before Relationship）。

假设每个进程 Pi 维护一个本地计数器Ci 。

1）进程内事件发生：Pi 在执行一个内部事件或发送消息前，Ci = Ci +1。

2）消息发送：Pi 发送消息m时，附带当前Ci 值作为消息时间戳 ts(m)。

3）消息接收：Pj 接收到消息m后，更新其本地计数器 Cj = max(Cj, ts(m) )+ 1。

如果事件A发生在事件B之前（A -> B），则 C(A) < C(B)。但反之不成立，即 C(A) < C(B)并不一定意味着 A -> B，A和B可能是并发的。

兰伯特时钟虽然解决了存在依赖关系的事件时序，但无法区分两个具有相同逻辑时间戳的事件的真实顺序，也无法判断两个时间戳不同但无因果关系的事件是否为并发。

向量时钟

向量时钟（Vector clock）是逻辑时钟的一种扩展，能够更精确地捕捉事件间的因果关系，并能识别并发事件。

假设有事件A、B分别在节点p、q上发生，向量时钟分别为TA、TB。

如果TqB > TqA并且TpB >= TpA，则A发生于 B之前，记作A -> B，此时说明事件A、B有因果关系。

如果TqB > TqA并且TpB < TpA，则认为A、B同时发生，记作A <-> B，此时说明事件A、B不存在因果关系。

例如下图节点B上的第4个事件（A=2 B =4 C=1）与节点C上的第2个事件 （B=3 C=2）没有因果关系，在逻辑上判定为同时发生事件。

而C节点第1个事件（C=1）与B节点第1个事件（B=1 C=1）有因果关系，所以C节点第1个事件 （C=1） 先于B节点第1个事件 （B=1 C=1）发生，后者依赖前者，有先后关系。

版本向量

向量时钟最常见的应用是发现数据冲突（Detect conflict）。分布式系统中数据一般存在多个副本，多个副本可能被同时更新，这会引起副本间数据不一致，版本向量（Version vector）的实现与向量时钟非常类似，目的用于发现数据冲突。

版本向量用一个counter nodes对表示。其中，nodes表示节点，counter是一个计数器，初始为0，每次更新操作加1。

假设在一个“去中心化”的分布式系统中，有副本数N=3，R=2，W=2，初始3个副本（A B C）上的数据为（1 1 1），版本向量都为空（ ）。

1）首先，某次更新操作由节点A主导，执行+1操作，节点A更新自己及节点C成功。此时三个节点上的副本数据为（2 1 2），版本向量为（(1, A) (1, A)），A、C的版本向量表示数据版本号为1，更新由节点A主导。

2）接着，更新操作由节点B主导，执行+2 操作，节点B更新自己及节点C成功。此时三个节点上的副本数据分别为(2 3 3)，版本向量为（(1, A) (1, B)）。

3）接着，更新操作再由节点A主导，执行+3操作，节点A更新自己及节点C成功。此时三个节点上的数据为（5 3 5），版本向量为（(2, A) (1, A) (2, A) (1, A)）。

4）最后，假设用户读取节点A及节点B上的数据，得到两个不一致的数据5与 3，及这两个数据的版本信息(2, A) (1, A)。假设用户判断出，其实这些加法操作可以合并，那么最终的数据应该是7，另外用户也可以选择保留一个数据例如5作为自己的数据。

由于提供了版本向量信息，不一致的数据其实成为了多版本数据，用户可以通过自定义策略选择合并这些多版本数据。最常见的冲突解决方法有两种：一种是通过客户端逻辑来解决，比如购物车应用；另外一种常见的策略“Last write win”，即选择时间戳最新的副本。

未完待续

很高兴与你相遇！如果你喜欢本文内容，记得关注哦！！！