概述

在分布式场景下,因为存在多个运行的实例,每个实例都有可能处于不同的环境,所以要在这些前提下取得一致性很多时候都是非常困难的。例如有两个更新操作,一个来自实例 A,一个来自实例 B,而且这个更新操作是互斥的,当实例 C 收到这两个更新操作的时候,是先执行 A 还是执行 B 是个好问题。

可能一般代码的实现都是先收到那个更新就先执行那个更新,因为先收到就意味着先 “发出” 嘛。然而,在分布式场景下,网络因素是个重要的话题,很可能 A 比 B 先发出,但是 C 却先收到 B,因为 A-C 之间的网络没有 B-C 之间的那么好。所以这个时候,就需要引入一个时钟的问题,假设 A/B 和 C 三台机器的时钟都是一致的话,那么 A 和 B 把自己发出的时间戳带上就可以了,这样 C 对比一下时间戳就可以了,但是,同样的,要想在分布式环境下保持时钟一致性几乎是不可能的。

于是,就回到了本文的话题,分布式环境下的时钟。

什么是 Lamport Clock

Lamport Clock 的目标就是要解决非物理时钟下,确认两个事件的先后顺序的。实现的方式也很简单,可以这么概述:

就是这么简单的一个原理,所以 Lamport Clock 能保证一个事情,如果事件 A 在事件 B 之前发生,那么肯定有(计数器A < 计数器B);但是,如果有一个(计数器 A < 计数器B),却无法反推出来事件 A 在事件 B 之前发生,这是不可逆的,因为,可能事件 A 和事件 B 无法比较。

显然,对于真实场景来说,Lamport Clock 的实用性还是不行,于是,Lamport 又提出了一个改进版本 Vector Clock。

什么是 Vector Clock

Vector Clock 是在 Lamport Clock 的基础上演进的,和 Lamport Clock 只用一个逻辑时钟不一样,Vector Clock 是使用多个逻辑时钟,有几个实例参与者,就有几个逻辑时钟,整体流程为:

这样,如果存在两个事件,所有的向量都 Vector A < Vector B,那么就可以认为事件A 肯定比事件 B 早发生,如果部分小于,部分大于,那么他们就没有先后顺序,可以认为 同时发生

有哪些应用

在我的以前文章中,我曾经介绍过 RAFT 一致性算法,其中就有一个情形是如果有部分节点和其他节点失联了,当这个节点回来的时候,就需要比对自己和其他复制集的状态,那么怎么比对?肯定不能比对事件戳,那么 Vector Clock 就是一个很不错的选择了。

Ref