Lamport 逻辑时钟(Lamport Timestamp)和 Vector Clock 简单理解

Lamport 逻辑时钟(Lamport Timestamp)

Lamport Timestamp 是一种衡量时间和因果关系的方法。现实生活中,很多程序都有着因果(causality)关系,比如执行完事件 A 后才能执行事件 B。

int main {
  create_photos(6);
  view_photos(6);
  return 0;
}

比如上面的代码,我只有创建完照片 6 才能访问照片 6,这就是因果关系。但是在分布式系统中,我们如何衡量事件的因果顺序呢?

如下图,比如我有 A,B,日志服务器 三台机器,用户发起一个购买操作,首先第一个请求在 Server A 上面创建了订单,之后支付操作在 Server B 上进行。然后为了记录用户操作,Server A 和 Server B 异步发送日志写入请求到达日志服务器。假设两条日志同时到达,那么日志服务器该如何区分先后顺序呢?

2020-05-03-FQRWHv

我们首先想到的就是使用时间戳(timestamp)的方式,根据时间戳的大小来判断事情发生的先后。但是在分布式系统中,不同的机器的时间可能不一样,这样导致这种方法会产生误差。也许你会说让机器定期进行 NTP 时间同步,但是在一个集群中,不同机器内部时间计算也会产生误差,可能有些机器时间前进的快点,有些机器会慢点,这种现象也叫 Clock Drift

Logic Clock

所以我们要引入逻辑上面的时间,其中 Logic Clock 中最出名的就是 Lamport Timestamp。通过逻辑时间,我们可以判断不同事件的因果顺序关系。

算法实现

Lamport Timestamp 算法的实现遵循以下规则:

  • 每一台机器内部都有一个时间戳(Timestamp),初始值为 0。
  • 机器执行一个事件(event)之后,该机器的 timestamp + 1。
  • 当机器发送信息(message)给另一台机器,它会附带上自己的时间戳,如
  • 当机器接受到一条 message,它会将本机的 timestamp 和 message 的 timestamp 进行对比,选取大的 timestamp 并 +1。

有些会说计数器叫 counter,也有些会说叫 timestamp,反正都代表一种计数方式。

Lamport Timestamp 伪代码如下:

发送信息

void sendMessage() {
  do_one_event();
  timestamp = timestamp + 1;
  send(message, timestamp);
}

接收信息

void receiveMessage() {
  (message, remote_timestamp) = receive();
  counter = max(timestamp, remote_timestamp) + 1;
}

思考

2020-05-01-BHuFXF

首先规定一个事件 A 的逻辑时间戳表示方式为 $C(A)$ 。下面所有的时间戳都为逻辑时间戳,不是机器真实时间。

如果事件 A 在事件 B 之前发生,(叫做 happened-before,表示为 $A\rightarrow B$),那么事件 A 的时间戳一定小于事件 B。即表达为:

$$
A\rightarrow B \Rightarrow C(A)<C(B)
$$

但是我们要注意这种推导关系是不能反过来的。

$$
C(A)1$ 但是它们之间没有因果关系,它们是并行 (concurrent) 的(或者是独立的,independent)。

我们还可以知道,如果 $C(A) <= C(B)$ ,那么事件 B 是绝对不可能发生在事件 A 之前。
$$
C(A)<=C(B)\Rightarrow B\nrightarrow A
$$
当然,如果事件 A 和 事件 B 的时间戳相同,则它们是并行独立的,即
$$
C(A)=C(B)\Rightarrow A \nleftrightarrow B
$$
大家可以参考下下面的图,加深下理解。

2020-05-01-PSQ3s2

Vector Clock

但是 Lamport Timestamp 不能很好的满足分布式系统,比如你不能区分两个事件是否有关联,或者在一个多点读的 key-value 数据库中,你无法确定保存哪一份副本(通常保存最新的那份副本)。

如下图所示,你其实无法单纯的通过 logic clock 比较来判断 Process 1 中的事件 3 和 Process 2 中的事件 8 是否有关系。

2020-05-01-w3C9Kq

如果事件 3 执行时间延迟几秒,这不会影响到事件 8。所以两个事件互不干涉,为了判断两个事件是否为这种情况,我们引入了 Vector Clock(向量逻辑时间)。

算法实现

Vector Clock 是通过向量(数组)包含了一组 Logic Clock,里面每一个元素都是一个 Logic Clock。如上图,我们有 3 台机器,那么 Vector Clock 就包含三个元素,每一个元素的索引(index)指向自己机器的索引。我们遵循以下规则:

  • 每一台机器都初始化所有的 timestamp 为 0。例如上面的例子,每一台机器初始的 Vector Clock 均为 [0, 0, 0]
  • 当机器处理一个 event,它会在向量中将和自己索引相同的元素的 timestamp + 1。例如 1 号 机器处理了一个 event,那么 1 号机器的 Vector Clock 变为 [1, 0, 0]
  • 每当发送 message 时,它会将向量中自己的 timestamp + 1,并附带在 message 中进行发送。如
  • 当一台机器接收到 message 时,它会把自己的 Vector Clock 和 message 中的 Vector Clock 进行逐一对比(每一个 timestamp 逐一对比),并将 timestamp 更新为更大的那个(类似于 Lamport Timestamp 的操作)。然后它会对代表自己的 timestamp + 1。

如下图所示:

2020-05-01-8ndGfw

由此我们也可以知道,如果 $A\rightarrow B$ ,那么 $A$ 的 Vector Clock 中的每一个元素都会小于 $B$ 中的每一个元素。

判断两个事件是否并行或独立

回到刚刚判断两个事件是不是有关联,我们可以看到 Process 1 中的 [3, 0, 0] 和 Process 2 中的 [2, 4, 2] ,其中 3 > 2 而 0 < 4,0 < 2 。有些 timestamp 大于对方,而有些 timestamp 又小于对方,由此我们可以得知这两个事件是互不相干的。

K/V 数据库中的应用

传统的分布式数据库存在一个 leader,leader 接收写入请求后,会将写入数据同步到集群一半以上的节点上面。一半以上节点反馈写入成功后,leader 再返回给客户端写入成功,有点类似于 Raft ,是单点写的。

如果我们引入了 Vector Clock,我们可以实现多点写,如 Dynamo 论文中所示。

假设 Key K 有三个副本 k1, k2, k3(目前是一样的),分别位于 M1, M2, M3 三台服务器上面,现在因为某种故障,导致了网络分区,三台机器均不能互相通信,但是每台机器仍然能够和客户端保持通讯。

其中 k1 副本被 client 1 持续更新,k2 副本被 client 2 持续更新。当三台机器之间互相通讯恢复的时候,进行副本同步时,应该保留哪个版本?如果只保留 k2,即采用 last write win 机制,那么同步后,client 1 会发现它写的数据丢了。

这个时候就需要 Vector Clock,更确切的说是 Version Clock(Dynamo 中是这么说的)。

为了处理这种场景,Dynamo 使用 Version Clock 来捕获同一份数据(Object) 的不同版本之间的因果关系(causality)。每个 Object 的每个版本会有一个相关联的 Version Clock , 形如 [(serverA, counter), (serverB, counter),...], 通过检查同一个 Object 不同版本的 Version Clock,可以决定是否可以完全丢弃一个版本,仅保留另外一个版本,还是需要将两个版本进行合并(merge)。如果 Object 的版本 A 的 Version Clock 中的每项 (server, counter) 在版本 B 的 Version Clock 中都有对应项,并且 counter 小于等于版本 B 中对应项的 counter,那么这个 Object 的版本 A 可以被丢弃,否则需要对两个版本进行 merge。

回到刚才的例子,k1 被更新,Version Clock (注:此处假设 k1/k2/k3 三个副本之前一模一样) 为[(M1, 1), (M2, 0), (M3, 0)],k2 被更新,Version Clock 为[(M1, 0), (M2,1), (M3, 0)],随后 k1 和 k2 网络通了,他们通过比较两个 Version Clock 发现两个 Version Clock 存在冲突,且不存在对方每一项 Logic Clock 小于自己的 Logic Clock,那么就两个版本都保留,当客户端来读 Key=K 的时候,两个版本的数据和对应的 Version Clock 都返回给客户端,由客户端进行冲突合并,客户端进行冲突合并后写入Key K的时候,带着合并后的 Version Clock [(M1, 1), (M2, 1), (M3, 0)] 发到M1 和 M2 两台机器,覆盖服务器版本,冲突解决。

Vector Clock 缺陷

系统伸缩(Scale)缺陷

其实 Vector Clock 对资源的伸缩支持并不是很好,因为对于一个 key 来说,随着服务器数量的增加,Vector Clock 中向量的元素也同样增长。假设集群有 1000 台机器,每次传递信息时都要携带这个长度为 1000 的 Vector,这个性能不太好接受。

非唯一缺陷

在正常的系统下面,假设所有的消息都是有序的(即同一台机器发送 消息 1 和 2 到另一台机器,另一台机器也会先接收到消息 1 再接收消息 2)。那么我们可以根据每一台机器的 Vector Clock 来恢复它们之间的计算(computation)关系,也就是每一种计算都有着对应自己独一无二的 Vector Clock。

但是,如果消息不是有序的,消息之间会‘超车‘(overtaking),那么问题就来了,看下图:

2020-05-02-uJrKNN

大家看看左右两张图,两种不一样的计算方式,但是最终 $p$ 和 $q$ 上面产生了相同的 Vector Clock。也就是说,相同的 Vector Clock 并不代表唯一的 computation。

2020-05-02-ugBzFk

这张图中,我们可以看看 $r$ 节点中的 $j$,我们无法判断这个 $j$ 是从 $p$ 那边的 $e$ 传递过来还是 $r$ 自己处理了一个事件,在自己 $i$ 的基础上面 +1 。

解决办法 1

在 Vector Clock 中添加事件类型,例如用内部(internal),发送(send),接收(receive)3 种事件表明 Vector Clock。但是这样的话还是有问题,

2020-05-02-ajHByN

我们标明了 send 和 receive 两种事件,但是结果还是不同的 computation 产生了相同的 Vector Clock。

解决办法 2

将 Vector Clock 改为既包含接收到消息的时间和本地时间。例如下面这个图:

2020-05-02-ajHByN

将左边图改为 $h:(<3,0>,<3,1>),i:(<1,0>,<3,2>,j:(<2,0>),<3,3>)$ ,右边图中变为 $h:(<3,0>,<3,1>),i:(<2,0>,<3,2>,j:(<1,0>),<3,3>)$ 。

通过这种方法,我们能够确定每一种 computation 有着唯一的 Vector Clock。虽然这种会导致 Vector Clock 体积增长了一倍。

当然这种方法也不一定完全需要,因为只要我们能够保证消息发送到达的有序,即不产生消息超车(Overtaking)的情况下,原来的 Vector Clock 也够用了。你可以在发送的消息上面再携带上本机的 timestamp,然后对方接受的时候,根据 timestamp 的先后顺序对消息进行排序(因为就是两个节点,点对点,可以使用这种时间戳的方式),这样就保证了消息不会发生超车。参考 TCP 对消息顺序的控制。

参考资料

https://en.wikipedia.org/wiki/Lamport_timestamps

https://jameshfisher.com/2017/02/12/what-are-lamport-timestamps/

https://towardsdatascience.com/understanding-lamport-timestamps-with-pythons-multiprocessing-library-12a6427881c6

https://www.zhihu.com/question/19994133

https://www.cnblogs.com/foxmailed/p/4985848.html

https://dl.acm.org/doi/10.1016/S0020-0190%2898%2900143-4

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/lamport-timestamp-vector-clock

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2023年3月2日
下一篇 2020年10月13日

相关推荐

发表回复

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