分布式系统:向量时钟

在上一篇文章 分布式系统:Lamport 逻辑时钟 中我们知道Lamport 逻辑时钟帮助我们得到了分布式系统中的事件全序关系,但是对于同时发生的关系却不能很好的描述,导致无法描述事件的因果关系。向量时钟是在 Lamport 时间戳基础上演进的另一种逻辑时钟方法,它通过向量结构不但记录本节点的 Lamport 时间戳,同时也记录了其他节点的 Lamport 时间戳,因此能够很好描述同时发生关系以及事件的因果关系。

 

注意:

本文中的因果关系指的是时序关系,即时间的前后,并不是逻辑上的原因和结果
本文中提及的时间戳如无特别说明,都指的是Lamport 逻辑时钟的时间戳,不是物理时钟的时间戳

为什幺需要向量时钟

 

首先我们来回顾一下 Lamport 逻辑时钟算法,它提供了一种判断分布式系统中事件全序关系的方法:如果 a -> b,那幺 C(a) < C(b),但是 C(a) < C(b) 并不能说明 a -> b。也就是说** C(a) < C(b) 是 a -> b 的必要不充分条件,我们不能通过 Lamport 时间戳对事件 a、b 的因果关系进行判断。** 下面我们举一个例子来说明。

假设有三个进程在发消息,Ts(mi)表示消息mi的发送时间戳,Tr(mi)表示消息mi的接受时间戳,显然 Ts(mi) < Tr(mi),但是这个能说明什幺呢?

 

我们可以发现在进程 P2 中,Tr(m1) < Ts(m3),说明 m3 是在 m1 被接收之后发送的,也就是说 m3 的发送跟 m1 的接收有关系。难道通过 Lamport 时间戳就能区分事件的因果的关系了吗?答案是 No,我们仔细看可以发现,虽然 Tr(m1) < Ts(m2),但实际上 m2 的发送跟 m1 并没有关系。

 

综上所述,我们可以发现 Lamport 逻辑时钟算法中每个进程只拥有自己的本地时间,没有其他进程的时间,导致无法描述事件的因果关系。如果每个进程都能够知道其他所有进程的时间,是否就能够得到事件的因果关系了呢?为此,有人提出了向量时钟算法,在 Lamport 逻辑时钟的基础上进行了改良,提出了一种在分布式系统中描述事件因果关系的算法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注