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

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

兰伯特逻辑时钟

兰伯特逻辑时钟（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 上发生，向量时钟分别为 T[A]、T[B]。如果 Tq[B] > Tq[A]并且 Tp[B] >= Tp[A]，则 A 发生于 B 之前，记作 A -> B，此时说明事件 A、B 有因果关系。如果 Tq[B] > Tq[A]并且 Tp[B] < Tp[A]，则认为 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)] [(1, B)]）。3）接着，更新操作再由节点 A 主导，执行+3 操作，节点 A 更新自己及节点 C 成功。此时三个节点上的数据为（5 3 5），版本向量为（[(2, A) (1, A)] [(1, B)] [(2, A) (1, A)]）。4）最后，假设用户读取节点 A 及节点 B 上的数据，得到两个不一致的数据 5 与 3，及这两个数据的版本信息[(2, A) (1, A)] [(1, B)]。假设用户判断出，其实这些加法操作可以合并，那么最终的数据应该是 7，另外用户也可以选择保留一个数据例如 5 作为自己的数据。由于提供了版本向量信息，不一致的数据其实成为了多版本数据，用户可以通过自定义策略选择合并这些多版本数据。最常见的冲突解决方法有两种：一种是通过客户端逻辑来解决，比如购物车应用；另外一种常见的策略“Last write win”，即选择时间戳最新的副本。

未完待续

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