1. 逻辑时钟和物理时钟

在分布式场景中,我们需要时间来判断不同节点上事件发生的先后顺序。

物理时钟可以用严格的绝对时间来表明事件的发生顺序,但是在分布式环境中,各个节点由于网络等因素无法做到完全一致的时间。即使使用NTP时间同步,也会有纳秒的误差。在这个误差时间内,可能会发生很多事件,那么这些事件的先后顺序就很难判断了。

Time, Clocks and the Ordering of Events in a Distributed System这篇论文的作者Leslie Lamport 在1978年提出逻辑时钟的概念。在分布式环境中,通过一系列规则来定义逻辑时钟的变化。从而能通过逻辑时钟来对分布式系统中的事件的先后顺序进行判断。逻辑时钟本质上定义了一种happen before关系。

2. lamport逻辑时钟

lamport时间戳原理,可以用下图来解释。A、B、C是三个进程。C1表示C进程上的1号事件。C1中的值1表示逻辑时间戳为1。其他的也可以同样来理解。

lamport逻辑时钟算法

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

lamport逻辑时钟很好的表达了事件的先后关系,但是无法表示同时发生这种关系。例如图中事件B4和事件C3没有因果关系,属于同时发生事件,但Lamport时间戳定义两者有先后顺序。lamport逻辑时钟规定:按事件的时间戳大小为时间排序,任何两个时间不可能在同一时间发生,任何消息收到的时间都应该比发送的时间晚。

3. vector逻辑时钟

上面我们提到了lamport逻辑时钟无法表示同时发生这种时间关系,因此这种vector时钟也应运而生。

Vector clock是在Lamport时间戳基础上演进的另一种逻辑时钟方法,它通过vector结构不但记录本节点的Lamport时间戳,同时也记录了其他节点的Lamport时间戳。Vector clock的原理与Lamport时间戳类似,使用原理如下:

vector时钟算法:
1.初始化所有的时钟为0
2.每一次处理内完内部事件,将自己的logic clock 加1
3.每一次发送一个消息的时候,需要将自己的向量时钟和消息一起发送
4.每一次接收到一个消息的时候,需要将自己的 logic clock +1,同时更新每一个逻辑时钟,更新的规则是取出收到 向量时钟和自己的取最大值

假设分布式系统有A、B和C这3个进程,根据上述规则其各自对应的逻辑时钟 随着时间演化情况如图所示,其数值变化规则遵循上述规则,时间线之间的边代表 进程间发送的消息。标为cause的阴影部分代表导致[A:2,B:4,C:1] 事件的原因,标为effect的阴影部分则代表[ A:2,B:4,C:1]事件影响到的后续事件, 而无阴影部分覆盖的事件则是和[ A:2, B:4, C:1]事件无逻辑上因果关系的事件,事件,比如事件[ A:1,B:2,C:1]以及[ A:4,B:5,C5],通过和[A:2, B:4,C:1]对应位置比较可知其因果关系为:, B: 2, C: 1] 为[ A: 2, B: 4, C: 1]之 因,[ A: 4, B: 5, C5] 为[ A: 2, B: 4, C: 1] 之 果。

正常情况下,向量时钟V1上的各个时间分量如果全部都小于等于V2上各个时间分量,则认为V1比V2早。

向量时钟V1上的各个时间分量有的比V2上的时间分量大,有的比其小,则认为是同时发生。

再来看看我们在lamport中的B4(左)和C3(右)对应的向量时钟为:

其中B:4大于B:3而C:1小于C:3。这样就认为两个逻辑时间是冲突的,即认为这两个事件是同时发生。

4. version vector

版本向量是本文的补充内容。 version vector借助vector clock可以用来判断分布式环境中的副本同时写入造成的冲突。

分布式系统中数据一般存在多个副本(replication),多个副本可能被同时更新,这会引起副本间数据不一致,Version vector的实现与Vector clock非常类似,目的用于发现数据冲突。下面通过一个例子说明Version vector的用法:

version vector算法:

  1. client端写入数据,该请求被Sx处理并创建相应的vector ([Sx, 1]),记为数据D1
  2. 第2次请求也被Sx处理,数据修改为D2,vector修改为([Sx, 2])
  3. 第3、第4次请求分别被Sy、Sz处理,client端先读取到D2,然后D3、D4被写入Sy、Sz
  4. 第5次更新时client端读取到D2、D3和D4 3个数据版本,通过类似Vector clock判断同时发生关系的方法可判断D3、D4存在数据冲突,最终通过一定方法解决数据冲突并写入D5

Vector clock只用于发现数据冲突,不能解决数据冲突。如何解决数据冲突因场景而异,具体方法有以最后更新为准(last write win),或将冲突的数据交给client由client端决定如何处理,或通过quorum决议事先避免数据冲突的情况发生。

5. vector过大的解决

由于记录了所有数据在所有节点上的逻辑时钟信息,Vector clock和Version vector在实际应用中可能面临的一个问题是vector过大,用于数据管理的元数据(meta data)甚至大于数据本身。

解决该问题的方法是使用server id取代client id创建vector (因为server的数量相对client稳定),或设定最大的size、如果超过该size值则淘汰最旧的vector信息。

参考资料:

  1. Time, Clocks and the Ordering of Events in a Distributed System
  2. 分布式系统理论基础 - 时间、时钟和事件顺序
  3. Vector clock
  4. 分布式一致算法 clock