← COMP5567 全部讲次
L02b-3 · 第 2 周

L02b-3 向量时钟:每台机器记一位,就能判出并发

一帧一帧算向量时钟,学会逐位比较判出先后和并发,弄清它比 Lamport 时钟多花了什么、多换来了什么,最后做完课件的 Take-home 练习。

一句话版

Lamport 时钟把所有消息链的进度压成一个整数,压完就分不清「先后」和「碰巧编号小」。向量时钟改成每台机器各占一位:第 i 位记「我知道第 i 台机器已经发生了几件事」。两个向量逐位比,每位都不大就是先后,有大有小就是并发。

上一页 L02b-2 讲了 Lamport 时钟和它判不出并发的局限,这一页补上。

先认识这几个词

词 全称 / 读法 一句人话
向量时钟 vector clock 每台机器维护一个长度为 n 的数组,n 是机器数
V(e) vector of e 事件 e 拿到的那个向量
分量 component 向量里的一位,第 i 位对应第 i 台机器
逐位取 max element-by-element max 两个向量每一位各自取较大的那个
逐位比较 componentwise comparison 两个向量每一位分别比大小

一个类比:每人一张进度表

项目群里每人手上不再只有一个数,而是一张表,列出群里每个人「我知道他已经说了几句话」。自己说一句,就在自己那一格加 1。发消息时把整张表附上。收到别人的表,就逐格看,哪格对方知道得更多就抄过来,再在自己那格加 1。

比较两句话时,拿出各自附的表。一张表每格都不比另一张多,说明前者知道的事后者全知道,前者在先。两张表各有一格多出来,说明各自知道对方不知道的事,谁也没看到谁,就是并发。

  • 表里的一格:向量的一个分量
  • 收到时逐格抄大的:逐位取 max
  • 各有一格多出来:有的位大有的位小,并发

类比在哪里失效:真人可能记漏,向量时钟的每一格严格按规则更新,不会漏记也不会多记。

从零讲起

1. 向量时钟的四步规则

它解决什么问题

Lamport 时钟判不出两个事件是否并发:LC(a) < LC(b) 推不出 a → b。需要一种时间戳,大小关系能双向对应 happens-before,看到时间戳就能断定是先后还是并发。

从哪来(补充)

向量时钟在 20 世纪 80 年代初由多位作者各自独立提出,常被引用的两篇是 Colin Fidge 和 Friedemann Mattern 1988 年各自发表的论文。

出处:Wikipedia: Vector clock

直觉

一个整数只能记「我数到几了」,看不出这个数是自己数的还是从别人那里抄来的。向量把每台机器的进度分开记,收消息时只抄对方更大的那几格,谁贡献了多少一目了然。

一步一步看

目标:按四步规则把图上每个事件的向量算出来,看收消息那一步怎样把对方的进度抄进来。

沿用上一页的图:两台机器 A、B,A 上 a1、a2、a3,B 上 b1 到 b5,a2 发消息给 b4,b5 发消息给 a3。向量写成 (A, B),初值 (0,0)。

  1. 先算没收消息的事件,只给自己那一位加 1:a1 = (1,0),a2 = (2,0);b1 = (0,1),b2 = (0,2),b3 = (0,3)。a2 发送时带走整个向量 (2,0)。

    两条进程线 A 和 B,A 上 a1、a2、a3,B 上 b1 到 b5。这一步标出没收消息的事件向量:a1 是 (1,0),a2 是 (2,0),b1 到 b3 是 (0,1)、(0,2)、(0,3),a2 发出的消息带走整个向量 (2,0),描成青绿

  2. b4 收到 (2,0)。B 本地是 (0,3)。按课件顺序先给 B 位加 1 得 (0,4),再和 (2,0) 逐位取 max 得 (2,4)。图上写的是先取 max 得 (2,3) 再加 1,结果一样。第 1 位从 0 变成 2:B 现在知道 A 已经发生过 2 件事。

    同一张图,b4 标出向量 (2,4),从 a2 到 b4 的消息描成青绿,标题写 b4 收到 (2,0) 后逐位取 max 得 (2,3)、B 位加 1 得 (2,4),下方注明第 1 位从 0 变 2,B 知道了 A 已发生 2 件事

  3. b5 = (2,5),发给 A。a3 本地是 (2,0),先给 A 位加 1 得 (3,0),再和 (2,5) 逐位取 max 得 (3,5)。a3 记下了 B 的 5 件事。

    同一张图,所有事件都标出向量,b5 是 (2,5),a3 是 (3,5),从 b5 到 a3 的消息描成青绿,下方注明 a3 记下了 B 的 5 件事,而 b1 的 (0,1) 和 a2 的 (2,0) 有大有小

怎么算

以 3 个节点为例,四步:

  1. 初始时,系统中所有向量时钟置零:[0, 0, 0]。
  2. 发生内部事件时,该进程在向量中自己那一位加 1。
  3. 发送消息时,把整个向量随消息一起发出。
  4. 接收消息时(接收本身也是一个事件):先把自己那一位加 1,再把收到的向量与自己的向量逐元素比较,每一位取两者中较大的值。

意思是:自己那一位只由自己加,别人的位只靠收消息时抄过来。所以第 i 位永远等于「我知道第 i 台机器已经发生了几件事」。

常见误解

接收时只做 max,忘了给自己加 1

接收本身也是一个事件,要赋时间戳,自己那一位必须加 1。b4 如果只做 max,会得到 (2,3),和 b3 的 B 位一样,等于没发生新事件。

发送时只带自己那一位的数

带走的是完整向量。a2 带走的是 (2,0),如果只带一个 2,接收方不知道这个 2 属于哪一位,也就抄不过去。

试一下

三台机器,P2 本地向量 (1,3,0),收到 (4,1,2)。接收事件的向量是多少?

先给 P2 位加 1 得 (1,4,0),再和 (4,1,2) 逐位取 max:第 1 位 4,第 2 位 4,第 3 位 2,结果是 (4,4,2)。

2. 逐位比较:先后还是并发

它解决什么问题

算出向量之后,要能一眼看出两个事件的关系。判据只有两条,记住就能做题。

直觉

V(a) 每一位都不比 V(b) 大,说明 a 知道的事 b 全知道,信息从 a 流到了 b。有一位 a 大、另一位 b 大,说明双方各知道对方不知道的事,谁也没看到谁。

一步一步看

目标:用逐位比较判三对事件,看 Lamport 判不出的那一对怎样被判成并发。

沿用上面的图,比三对事件:

  1. a2 = (2,0) 与 b4 = (2,4):2 ≤ 2,0 ≤ 4,且第 2 位严格小 → a2 → b4。正好是那条消息。
  2. b1 = (0,1) 与 a2 = (2,0):第 1 位 0 < 2,第 2 位 1 > 0,有大有小 → b1 ‖ a2。上一页 Lamport 编号 1 < 2 判不出来的那一对,这里判出了并发。
  3. a1 = (1,0) 与 a3 = (3,5):每位都 ≤ 且有严格小 → a1 → a3。
一对事件 向量 逐位 结论
a2、b4 (2,0)、(2,4) = 和 < a2 → b4
b1、a2 (0,1)、(2,0) < 和 > 并发
a1、a3 (1,0)、(3,5) < 和 < a1 → a3

怎么判断

  • V(a) ≤ V(b) 且 V(a) ≠ V(b),即每一位都 ≤、至少一位严格 < ⟹ a → b。
  • 两个方向都不成立,有的位 a 大、有的位 b 大 ⟹ a ‖ b,并发。

意思是:向量时钟的大小关系和 happens-before 双向对应,看到向量就能下结论,不用再去图上走路。

常见误解

只比第一位就下结论

(2,5,1) 与 (3,4,1) 第一位 2 < 3,看着像前者在先,可第二位 5 > 4,有大有小,是并发。每一位都要比。

把两个向量的各位加起来比总和

加总等于又压回一个整数,信息又丢了。(0,1) 总和 1、(2,0) 总和 2,比总和得出「前者在先」,实际是并发。

试一下

(1,2,0) 与 (1,3,2) 是什么关系?(3,0,1) 与 (1,2,1) 呢?

第一组:1 ≤ 1、2 ≤ 3、0 ≤ 2,且有严格小,前者 → 后者。第二组:第 1 位 3 > 1,第 2 位 0 < 2,有大有小,并发。

3. 和 Lamport 时钟的取舍

它解决什么问题

两种时钟都能用,要知道各自花多少、换来什么,才能在题目和实际场景里选对。

直觉

Lamport 只记一个数,便宜,但信息被压扁了。向量每台机器一位,机器越多越贵,但信息完整,能判并发。

一步一步看

目标:逐项对照两种时钟,看向量时钟多花的空间换来了什么。

  1. 数据结构:Lamport 是一个整数,向量时钟是长度为 n 的向量。
  2. 先后推得出时间戳有序:两者都成立。
  3. 时间戳有序推得出先后:Lamport 不成立,向量时钟成立。
  4. 因此能否检测并发:Lamport 不能,向量时钟能。
Lamport 时钟 向量时钟
数据结构 一个整数 长度为 n 的向量
a → b ⟹ 时间戳有序 成立 成立
时间戳有序 ⟹ a → b 不成立 成立
能否检测并发 不能 能
空间开销 O(1) O(n)

怎么判断

需要判并发 → 用向量时钟。只要一个所有机器一致的全序、不关心并发 → Lamport 加进程 ID 就够,开销更小。

意思是:向量时钟用 O(n) 的空间代价,换来了判定并发的能力,这个取舍就是它存在的理由。

常见误解

以为向量时钟能给出全序

向量时钟如实反映偏序:并发的两个事件,向量就是有大有小,排不出先后。要全序还是得另加规则。

试一下

一个系统有 100 台机器,每条消息都要带时间戳。换成向量时钟后,每条消息多带多少个整数?

Lamport 带 1 个整数,向量时钟带 100 个,每条消息多带 99 个。

把它们串起来

Lamport 时钟把进度压成一个整数,保住了「先发生的编号小」,丢掉了「编号小的是不是先发生」。向量时钟让每台机器各占一位,自己那一位只由自己加,别人的位只在收消息时抄过来,所以每个向量都准确记下「我知道每台机器发生过几件事」。

于是比较变成逐位的:每位都不大就是先后,有大有小就是并发,和 happens-before 双向对应。代价是每条消息要带 n 个整数。

下一讲的因果序广播就用向量时钟判断一条消息能不能交付,这一页的算法要练到能闭眼手算。

课件里的坑

  • [顺序之争] p.22 写的是接收时先给自己那一位加 1,再逐位取 max。不少资料写成先 max 再加 1。标准向量时钟没有重置时,消息里的接收方分量不会超过本地,两种顺序结果相同;答题按课件顺序写。
  • [课堂留题] p.22 的 Case 4,(4,1,0) 与 (2,2,0) 标的是「?」,课件上没有答案。第 1 位 4 > 2、第 2 位 1 < 2,有大有小,答并发。
  • [必做练习] p.30 的 Take-home Exercise-1 最容易错两处:接收事件也要给自己那一位加 1;发送时带走的是完整向量,不是单个数。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写四步规则和两条判据;再把下面的「变式题」做一遍;最后回查两个最容易错的地方:接收时忘了给自己加 1、只比第一位就下结论。三步做完再往下看答案。

必背

  1. 向量时钟四步:初值全 0;内部事件自己那一位加 1;发送时带上整个向量;接收时先给自己那一位加 1,再逐位取 max。
  2. 向量时钟判据:每位都 ≤ 且至少一位 < 为因果先后,有的位大有的位小为并发。
  3. 向量时钟能检测并发,这正是 Lamport 时钟做不到的。
  4. Lamport 时钟占 O(1) 空间、判不了并发;向量时钟占 O(n) 空间、能判并发。
  5. 接收事件也要给自己那一位加 1,不能只做 max;发送时带走的是完整向量,不是单个数。

课件例题

例 3(课件 p.22):用向量时钟判四组事件的关系

题面:课件给出四组向量:Case 1 (1,0,0) 与 (4,1,3);Case 2 (0,1,0) 与 (4,1,3);Case 3 (2,2,0) 与 (4,1,3);Case 4 (4,1,0) 与 (2,2,0),课堂留题。判断每组是先后还是并发。

提示

每组都逐位比三次,记下每一位是 <、= 还是 >。全是 ≤ 且有 < 就是先后,同时出现 < 和 > 就是并发。

解答
  1. Case 1:1 ≤ 4、0 ≤ 1、0 ≤ 3,第 1 位严格小 ⟹ a → m。
  2. Case 2:0 ≤ 4、1 ≤ 1、0 ≤ 3,第 1 位严格小 ⟹ h → m。
  3. Case 3:第 1 位 2 < 4、第 3 位 0 < 3,但第 2 位 2 > 1 ⟹ 有大有小 ⟹ i ‖ m。
  4. Case 4:第 1 位 4 > 2,第 2 位 1 < 2 ⟹ 有大有小 ⟹ 并发。

四个例子按三个分量逐位比对:(1,0,0) 与 (4,1,3) 每位都小于等于且有严格小于,判 a 先于 m;(0,1,0) 与 (4,1,3) 同理判 h 先于 m;(2,2,0) 与 (4,1,3) 的第 2 位 2 大于 1,有大有小判并发;(4,1,0) 与 (2,2,0) 的第 1 位 4 大于 2、第 2 位 1 小于 2,同样判并发

  1. 反过来想 Lamport 为什么做不到:它把整个向量压成一个整数,压完之后「有的位大有的位小」这个信息就没了,只剩下两个数谁大谁小,而大小关系推不出因果。

例 4(课件 p.30,Take-home Exercise-1):给整张图标向量时钟,并找出与 f 并发的事件

题面:三个进程 P1、P2、P3,逻辑时钟初值全为 0。P1 上依次有 a、b、c、d、e;P2 上依次有 f、g、h、i、j;P3 上依次有 k、l。图上三条消息:b 发出、g 接收;k 发出、h 接收;i 发出、d 接收。要求:① 列出每个事件的向量时钟;② 列出与 f 并发的事件并说明原因。

课件 Figure 1:三条进程线 P1、P2、P3,时间从左向右。P1 上依次是 a、b、c、d、e,P2 上依次是 f、g、h、i、j,P3 上依次是 k、l;三条消息箭头分别从 b 指向 g、从 k 指向 h、从 i 指向 d
图片来源:COMP5567 Lecture_2-Distributed-system.pdf, p.30
提示

沿时间轴从左到右逐个事件处理。先算不收消息的 a、b、c、f、k、l,再按 g、h、i、j、d、e 的顺序算接收和之后的事件。第 2 问拿每个事件的向量和 f = (0,1,0) 逐位比。

解答

向量写成 (P1, P2, P3)。接收时先给自己那一位加 1,再逐位取 max,两种顺序结果相同。

  1. P1 前三个事件:a = (1,0,0),b = (2,0,0),c = (3,0,0)。
  2. P3:k = (0,0,1),l = (0,0,2)。
  3. P2:f = (0,1,0)。g 收到 b 带来的 (2,0,0):先加 1 得 (0,2,0),再取 max,g = (2,2,0)。
  4. h 收到 k 带来的 (0,0,1):先加 1 得 (2,3,0),再取 max,h = (2,3,1)。接着 i = (2,4,1),j = (2,5,1)。
  5. d 收到 i 带来的 (2,4,1):本地 (3,0,0) 先加 1 得 (4,0,0),再取 max,d = (4,4,1)。接着 e = (5,4,1)。
  6. 与 f = (0,1,0) 比:a、b、c 的 P1 位比 f 大、P2 位比 f 小;k、l 的 P3 位比 f 大、P2 位比 f 小。有大有小,所以 a、b、c、k、l 与 f 并发。
  7. 其余事件:g、h、i、j 和 f 在同一进程且在 f 之后;d、e 的每一位都 ≥ f,经 i 到 d 的消息能从 f 走过去,所以都是 f 的后继,不并发。

三条进程线 P1、P2、P3 上每个事件标出答案向量:P1 上 a 到 e 依次是 (1,0,0)、(2,0,0)、(3,0,0)、(4,4,1)、(5,4,1),P2 上 f 到 j 依次是 (0,1,0)、(2,2,0)、(2,3,1)、(2,4,1)、(2,5,1),P3 上 k、l 是 (0,0,1)、(0,0,2);与 f 并发的 a、b、c、k、l 描成青绿

完整例题

题面:三台机器 P1、P2、P3,初值全 0。P1 上依次有 x1、x2;P2 上依次有 y1、y2、y3;P3 上依次有 z1、z2。消息从 x1 发到 y2,从 y3 发到 z2。① 算出每个事件的向量;② 判断 x2 与 y3、x1 与 z2、z1 与 y1 的关系。

  1. P1:x1 = (1,0,0),发送时带走 (1,0,0);x2 = (2,0,0)。
  2. P2:y1 = (0,1,0)。y2 收到 (1,0,0):先加 1 得 (0,2,0),再取 max 得 (1,2,0)。y3 = (1,3,0),发送时带走 (1,3,0)。
  3. P3:z1 = (0,0,1)。z2 收到 (1,3,0):先加 1 得 (0,0,2),再取 max 得 (1,3,2)。
  4. x2 = (2,0,0) 与 y3 = (1,3,0):第 1 位 2 > 1,第 2 位 0 < 3,有大有小 → 并发。x2 没发消息,确实走不到 P2。
  5. x1 = (1,0,0) 与 z2 = (1,3,2):每位都 ≤,第 2 位严格小 → x1 → z2。路径是 x1 → y2 → y3 → z2。
  6. z1 = (0,0,1) 与 y1 = (0,1,0):第 2 位 0 < 1,第 3 位 1 > 0,有大有小 → 并发。
  7. 对照 Lamport:x1 = 1、x2 = 2、y1 = 1、y2 = 2、y3 = 3、z1 = 1、z2 = 4。x2 = 2 < y3 = 3 看着像先后,向量告诉你其实是并发。

变式题(先自己做)

改编自课件 p.22:三组新向量,逐位判关系(顺序、并发,还是别的):

  1. (3,2,1) 与 (3,2,4)
  2. (2,5,1) 与 (3,4,1)
  3. (0,0,2) 与 (0,0,2)
提示

前两组照规则逐位比就行。第三组先别急着套「并发」的定义,想一想:两个不同的事件,有可能拿到一模一样的向量吗?

判分点与答案

判分点:① 每一位都要比,只看第一位就下结论是主要失分方式;② 「有的位大、有的位小」才判并发;③ 第三组要答出「这是同一个事件」,直接套并发是陷阱。

  1. 3 ≤ 3、2 ≤ 2、1 < 4,每位都 ≤ 且第 3 位严格小 ⟹ 前者 happens-before 后者。
  2. 第 1 位 2 < 3,第 2 位 5 > 4 ⟹ 有大有小 ⟹ 并发。第 3 位相等不影响判定。
  3. 两个向量完全相等。按字面套「两个方向都不严格成立」会判成并发,但这是陷阱:每发生一个事件,本地分量必定加一,所以不同事件不可能拥有相同的向量。相等只说明这是同一个事件的时间戳被写了两遍。

闪卡自测

1. 向量时钟接收事件的两步,顺序能不能反?发送时带走什么?

课件写的是先给自己那一位加 1,再逐位取 max(p.22)。标准向量时钟下与「先 max 再加 1」结果相同,但不能只做 max。发送时带走的是完整向量,不是单个数。

2. 向量时钟怎么判先后、怎么判并发?

每位都 ≤ 且至少一位严格 < ⟹ 先后;有的位大、有的位小 ⟹ 并发(p.22)。

3. (4,1,0) 与 (2,2,0) 是什么关系?

第 1 位 4 > 2,第 2 位 1 < 2,有大有小,并发(p.22)。

4. Lamport 时钟和向量时钟在空间与能力上各是什么取舍?

Lamport 占 O(1) 空间,判不了并发;向量时钟占 O(n) 空间,n 是进程数,能判并发。向量时钟用多出来的空间换判断并发的能力。

5. Take-home 里与 f 并发的是哪些事件?

a、b、c、k、l(p.30)。它们和 f = (0,1,0) 比都是有的位大、有的位小。

下一讲

L03a-1 可靠广播(一):先区分 receive 和 deliver,再沿可靠性和顺序两条轴往上爬,其中的因果序广播会直接用到这一页的向量时钟。

下一讲 →
L03a-1 L03a-1 可靠广播(一):收到和交付是两回事,可靠性分三级

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。