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 年各自发表的论文。
直觉
一个整数只能记「我数到几了」,看不出这个数是自己数的还是从别人那里抄来的。向量把每台机器的进度分开记,收消息时只抄对方更大的那几格,谁贡献了多少一目了然。
一步一步看
目标:按四步规则把图上每个事件的向量算出来,看收消息那一步怎样把对方的进度抄进来。
沿用上一页的图:两台机器 A、B,A 上 a1、a2、a3,B 上 b1 到 b5,a2 发消息给 b4,b5 发消息给 a3。向量写成 (A, B),初值 (0,0)。
-
先算没收消息的事件,只给自己那一位加 1:a1 = (1,0),a2 = (2,0);b1 = (0,1),b2 = (0,2),b3 = (0,3)。a2 发送时带走整个向量 (2,0)。
-
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 件事。
-
b5 = (2,5),发给 A。a3 本地是 (2,0),先给 A 位加 1 得 (3,0),再和 (2,5) 逐位取 max 得 (3,5)。a3 记下了 B 的 5 件事。
怎么算
以 3 个节点为例,四步:
- 初始时,系统中所有向量时钟置零:[0, 0, 0]。
- 发生内部事件时,该进程在向量中自己那一位加 1。
- 发送消息时,把整个向量随消息一起发出。
- 接收消息时(接收本身也是一个事件):先把自己那一位加 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 判不出的那一对怎样被判成并发。
沿用上面的图,比三对事件:
- a2 = (2,0) 与 b4 = (2,4):2 ≤ 2,0 ≤ 4,且第 2 位严格小 → a2 → b4。正好是那条消息。
- b1 = (0,1) 与 a2 = (2,0):第 1 位 0 < 2,第 2 位 1 > 0,有大有小 → b1 ‖ a2。上一页 Lamport 编号 1 < 2 判不出来的那一对,这里判出了并发。
- 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 只记一个数,便宜,但信息被压扁了。向量每台机器一位,机器越多越贵,但信息完整,能判并发。
一步一步看
目标:逐项对照两种时钟,看向量时钟多花的空间换来了什么。
- 数据结构:Lamport 是一个整数,向量时钟是长度为 n 的向量。
- 先后推得出时间戳有序:两者都成立。
- 时间戳有序推得出先后:Lamport 不成立,向量时钟成立。
- 因此能否检测并发: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、只比第一位就下结论。三步做完再往下看答案。
必背
- 向量时钟四步:初值全 0;内部事件自己那一位加 1;发送时带上整个向量;接收时先给自己那一位加 1,再逐位取 max。
- 向量时钟判据:每位都 ≤ 且至少一位 < 为因果先后,有的位大有的位小为并发。
- 向量时钟能检测并发,这正是 Lamport 时钟做不到的。
- Lamport 时钟占 O(1) 空间、判不了并发;向量时钟占 O(n) 空间、能判并发。
- 接收事件也要给自己那一位加 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),课堂留题。判断每组是先后还是并发。
提示
每组都逐位比三次,记下每一位是 <、= 还是 >。全是 ≤ 且有 < 就是先后,同时出现 < 和 > 就是并发。
解答
- Case 1:1 ≤ 4、0 ≤ 1、0 ≤ 3,第 1 位严格小 ⟹ a → m。
- Case 2:0 ≤ 4、1 ≤ 1、0 ≤ 3,第 1 位严格小 ⟹ h → m。
- Case 3:第 1 位 2 < 4、第 3 位 0 < 3,但第 2 位 2 > 1 ⟹ 有大有小 ⟹ i ‖ m。
- Case 4:第 1 位 4 > 2,第 2 位 1 < 2 ⟹ 有大有小 ⟹ 并发。
- 反过来想 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 并发的事件并说明原因。
提示
沿时间轴从左到右逐个事件处理。先算不收消息的 a、b、c、f、k、l,再按 g、h、i、j、d、e 的顺序算接收和之后的事件。第 2 问拿每个事件的向量和 f = (0,1,0) 逐位比。
解答
向量写成 (P1, P2, P3)。接收时先给自己那一位加 1,再逐位取 max,两种顺序结果相同。
- P1 前三个事件:a = (1,0,0),b = (2,0,0),c = (3,0,0)。
- P3:k = (0,0,1),l = (0,0,2)。
- P2:f = (0,1,0)。g 收到 b 带来的 (2,0,0):先加 1 得 (0,2,0),再取 max,g = (2,2,0)。
- h 收到 k 带来的 (0,0,1):先加 1 得 (2,3,0),再取 max,h = (2,3,1)。接着 i = (2,4,1),j = (2,5,1)。
- d 收到 i 带来的 (2,4,1):本地 (3,0,0) 先加 1 得 (4,0,0),再取 max,d = (4,4,1)。接着 e = (5,4,1)。
- 与 f = (0,1,0) 比:a、b、c 的 P1 位比 f 大、P2 位比 f 小;k、l 的 P3 位比 f 大、P2 位比 f 小。有大有小,所以 a、b、c、k、l 与 f 并发。
- 其余事件:g、h、i、j 和 f 在同一进程且在 f 之后;d、e 的每一位都 ≥ f,经 i 到 d 的消息能从 f 走过去,所以都是 f 的后继,不并发。
完整例题
题面:三台机器 P1、P2、P3,初值全 0。P1 上依次有 x1、x2;P2 上依次有 y1、y2、y3;P3 上依次有 z1、z2。消息从 x1 发到 y2,从 y3 发到 z2。① 算出每个事件的向量;② 判断 x2 与 y3、x1 与 z2、z1 与 y1 的关系。
- P1:x1 = (1,0,0),发送时带走 (1,0,0);x2 = (2,0,0)。
- P2:y1 = (0,1,0)。y2 收到 (1,0,0):先加 1 得 (0,2,0),再取 max 得 (1,2,0)。y3 = (1,3,0),发送时带走 (1,3,0)。
- P3:z1 = (0,0,1)。z2 收到 (1,3,0):先加 1 得 (0,0,2),再取 max 得 (1,3,2)。
- x2 = (2,0,0) 与 y3 = (1,3,0):第 1 位 2 > 1,第 2 位 0 < 3,有大有小 → 并发。x2 没发消息,确实走不到 P2。
- x1 = (1,0,0) 与 z2 = (1,3,2):每位都 ≤,第 2 位严格小 → x1 → z2。路径是 x1 → y2 → y3 → z2。
- z1 = (0,0,1) 与 y1 = (0,1,0):第 2 位 0 < 1,第 3 位 1 > 0,有大有小 → 并发。
- 对照 Lamport:x1 = 1、x2 = 2、y1 = 1、y2 = 2、y3 = 3、z1 = 1、z2 = 4。x2 = 2 < y3 = 3 看着像先后,向量告诉你其实是并发。
变式题(先自己做)
改编自课件 p.22:三组新向量,逐位判关系(顺序、并发,还是别的):
- (3,2,1) 与 (3,2,4)
- (2,5,1) 与 (3,4,1)
- (0,0,2) 与 (0,0,2)
提示
前两组照规则逐位比就行。第三组先别急着套「并发」的定义,想一想:两个不同的事件,有可能拿到一模一样的向量吗?
判分点与答案
判分点:① 每一位都要比,只看第一位就下结论是主要失分方式;② 「有的位大、有的位小」才判并发;③ 第三组要答出「这是同一个事件」,直接套并发是陷阱。
- 3 ≤ 3、2 ≤ 2、1 < 4,每位都 ≤ 且第 3 位严格小 ⟹ 前者 happens-before 后者。
- 第 1 位 2 < 3,第 2 位 5 > 4 ⟹ 有大有小 ⟹ 并发。第 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,再沿可靠性和顺序两条轴往上爬,其中的因果序广播会直接用到这一页的向量时钟。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。