L02b-2 Lamport 时钟:给每个事件发一个号
一帧一帧算 Lamport 时钟的四条规则,看清时钟条件为什么只单向成立,以及加上进程 ID 之后得到的全序能做什么、不能做什么。
一句话版
Lamport 时钟给每个事件发一个整数编号:本机每发生一件事加 1,收到消息时先追上对方的编号再加 1。这样只要 a 先于 b,a 的编号一定更小。反过来不成立:编号小的不一定先发生,所以它判不出并发。
上一页 L02b-1 讲了 happens-before 怎么靠「走路」判。这一页让数字替你走路。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| Lamport 时钟 | Lamport clock | 每台机器各自维护的一个整数计数器 |
| LC(e) | Lamport clock of e | 事件 e 拿到的编号 |
| 时钟条件 | clock condition | 先发生的事件编号一定更小 |
| 单向蕴含 | one-way implication | A 推得出 B,B 推不出 A |
| 打破平局 | tie-breaking | 编号相同时再比进程 ID |
| 全序 | total order | 所有事件排成一条线,任意两个都能比 |
一个类比:排队叫号
还是那个跨时区的项目群,每人手里只有一个记数本。自己每说一句话,就把本子上的数加 1,写在这句话后面。看到别人的消息时,先看那条消息后面的数,如果比自己本子上的大,就把本子翻到那个数,再加 1 写在自己的回复后面。
这样一来,一句回复的编号永远比它回应的那句大。可两个人各自说话、互不回应时,编号谁大谁小纯属碰巧。
- 本子上的数:本地计数器
- 回复前先追上对方的数:Max(local, received) + 1
- 编号碰巧一样:时间戳相同
- 互不回应的两句话:并发事件
类比在哪里失效:群聊里的人可能故意看了消息却不回,Lamport 时钟里只要收到消息就一定取 max,没有「看了不算」这回事。
从零讲起
1. Lamport 时钟的四条规则
它解决什么问题
上一页判 happens-before 要在图上找路,事件一多就很慢,机器也没法「看图」。需要一个每台机器在本地就能算的数字,并且保证先发生的事件数字小。
从哪来(补充)
Leslie Lamport 1978 年在 Communications of the ACM 发表《Time, Clocks, and the Ordering of Events in a Distributed System》,提出了这种逻辑时钟。它只用来给事件定序,不对应物理时间。
出处:Wikipedia: Lamport timestamp
直觉
每台机器各数各的,本地每做一件事加 1。消息就像一张便条,上面写着发送方当时数到几。接收方读到便条时,如果自己数得比便条少,说明自己落后了,先追上再加 1;如果自己数得比便条多,保持自己的再加 1。这样接收事件的编号一定比发送事件大。
一步一步看
目标:按四条规则给两台机器上的事件逐个编号,看收消息时编号怎么取。
两台机器 A、B。A 上依次有 a1、a2、a3;B 上依次有 b1 到 b5。a2 发消息给 b4,b5 发消息给 a3。
-
先算没收消息的事件,各自从 0 往上加 1:a1 = 1,a2 = 2;b1 = 1,b2 = 2,b3 = 3。a2 是发送事件,消息带走 2。
-
b4 收到 a2 带来的 2。B 本地已经是 3,取 Max(3, 2) + 1 = 4。本地比收到的大,保留本地再加 1。
-
b5 = 5,发消息给 A。a3 收到 5,A 本地是 2,取 Max(2, 5) + 1 = 6。A 的编号一下跳到 6。
怎么算
四条规则:
- 每个进程维护一个本地计数器,初值为 0。
- 进程上每发生一个事件,计数器加 1。
- 发送消息时,把当前计数器的值随消息带上。
- 收到消息时,把计数器设为 Max(local, received) + 1。
意思是:第 4 条是全部的精髓,取本地和收到的两个值中较大的那个再加 1,保证接收事件的编号一定大于发送事件的编号。
常见误解
收消息时直接写 received + 1
上面第 2 步就是反例:B 本地已经是 3,收到的是 2,写 received + 1 会得到 3,和 b3 撞号,还让 B 的计数器倒退。必须先取 max,本地进度不能往回走。
以为发送事件不用加 1
发送本身也是一个事件,要先按第 2 条加 1,再把加完后的值带走。a2 就是先加到 2,再带着 2 发出去。
试一下
B 本地计数器是 7,收到一条带着 4 的消息,这个接收事件的编号是多少?如果带的是 9 呢?
带 4 时取 Max(7, 4) + 1 = 8;带 9 时取 Max(7, 9) + 1 = 10。
2. 时钟条件只单向成立
它解决什么问题
有了编号,就想反过来用:看到 LC(a) < LC(b),能不能断定 a 先于 b?课件的回答是不能。这一条决定了 Lamport 时钟能用在哪、不能用在哪。
直觉
规则保证了「沿消息链往后走,编号一定变大」。可两条互不相连的链各数各的,A 数到 2、B 数到 1,只说明 A 那边事情多,跟谁先谁后没关系。
一步一步看
目标:验证 LC(a) < LC(b) 推不出 a 先于 b:找一对编号更小却并发的事件。
-
沿用上面的图,看 b1 = 1 和 a2 = 2。
-
编号上 1 < 2。
-
用上一页的「走路」法:b1 只能往右走到 b5,再经消息到 a3,到不了 a2;a2 经消息到 b4,也走不回 b1。
-
两者互相走不到,b1 ‖ a2。编号小于只是碰巧。
怎么判断
记 LC(e) 为事件 e 的 Lamport 编号,两条性质成对出现:
- 若 a → b,则 LC(a) < LC(b)。这就是时钟条件:∀a, b: a → b ⟹ LC(a) < LC(b)。
- LC(a) < LC(b) 并不意味着 a → b。
意思是:可以用编号排除先后(LC(a) ≥ LC(b) 时 a 一定不先于 b),不能用编号证明先后,更判不出两件事是不是并发。
常见误解
看到编号小就说「先发生」
这是把单向蕴含当成了充要条件。课件原话:LC(a) < LC(b) 并不意味着 a → b。考题让你判 a、b 关系时,Lamport 编号只能当排除工具。
试一下
已知 LC(x) = 5,LC(y) = 3。能说出 x 和 y 的什么关系?
只能说 x 一定不先于 y(若 x → y 应有 LC(x) < LC(y),与 5 > 3 矛盾)。至于是 y → x 还是 y ‖ x,从编号看不出来。
3. 加上进程 ID:人为造一个全序
它解决什么问题
课件列了 Lamport 时钟的两个问题:两个事件可能有相同的时间戳;没有全局顺序。有些场景需要所有机器对全部事件排出同一个顺序,比如大家按同一顺序执行操作,编号撞了就排不下去。
直觉
编号相同时,找一个所有机器都同意的规则来裁决:比进程 ID。只要 ID 不重复,任意两个事件都能分出前后。
一步一步看
目标:看编号撞车时怎样用进程 ID 裁决,把全部事件排成一个全序。
-
沿用上面的图,把每个事件写成(编号, 进程):(A, 1)、(A, 2)、(A, 6)、(B, 1) 到 (B, 5)。
-
先比编号,小的排前面。
-
编号 1 撞了两个:(A, 1) 和 (B, 1)。约定 A < B,(A, 1) 排前面。
-
排完:(A, 1)、(B, 1)、(A, 2)、(B, 2)、(B, 3)、(B, 4)、(B, 5)、(A, 6)。
怎么判断
比较 (LC(a), a 的进程) 和 (LC(b), b 的进程):
- 编号不同 → 编号小的在前。
- 编号相同 → 进程 ID 小的在前。
意思是:这样得到的是一个任意但确定的全序。它和真实因果不矛盾,因为平局只出现在并发事件之间;它也不代表真实因果,排在前面的不一定真的先发生。
常见误解
以为加了进程 ID 就能判并发了
课件写明,加了进程 ID 也解决不了:Lamport 时钟无法判断两个事件是否并发。打破平局只是把并发事件随便排了个先后,并发信息本身还是丢了。这个局限直接引出下一页的向量时钟。
试一下
三个事件 (Q, 3)、(P, 4)、(R, 3),约定 P < Q < R,排出全序。
先比编号:两个 3 在前,4 在后。两个 3 再比进程,Q < R。结果是 (Q, 3)、(R, 3)、(P, 4)。
把它们串起来
Lamport 时钟把「走路」压成了一个本地就能算的整数。四条规则里只有收消息那条需要动脑:取 max 再加 1,保证接收一定比发送大。
由此得到时钟条件:先发生的编号一定小。反过来不成立,编号小的可能只是另一条链上事情多。所以 Lamport 编号能排除先后,不能证明先后。
编号撞了就再比进程 ID,得到一个所有机器都认可的全序。这个全序是人为规定的,并发事件之间的先后没有意义。要分辨两件事是不是并发,一个整数不够,下一页换成一个向量。
课件里的坑
- [课件留空] p.21 的
Global order: _______是课堂填空,课件上没有答案。按「先比编号、再比进程 ID」自己填,见下面例 2。 - [单向蕴含] p.20 的两条性质必须成对记:a → b ⟹ LC(a) < LC(b) 成立,反向不成立。只背前一条会在判断题上失分。
- [局限没解决] p.21 的进程 ID 只解决了「时间戳相同」,没解决「判不出并发」。问「加了进程 ID 还有什么局限」时答后者。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写四条规则和两条性质;再把下面的「变式题」做一遍;最后回查两个最容易错的地方:收消息写成 received + 1、看到编号小就说先发生。三步做完再往下看答案。
必背
- Lamport 时钟四条规则:计数器初值 0;每发生一个事件加 1;发消息时带上当前值;收消息时设为 Max(local, received) + 1。
- 时钟条件:a → b ⟹ LC(a) < LC(b)。
- Lamport 时钟收消息时取 Max(local, received) + 1;a → b ⟹ LC(a) < LC(b) 成立,反向不成立,因此判不出并发。
- Lamport 时钟附上进程 ID 打破平局,得到人为的全序,但仍然判不出两个事件是否并发。
- 课件列的两个问题:两个事件可能有相同的时间戳;没有全局顺序。
课件例题
例 2(课件 p.20–21):给 Lamport 时钟例子排一个全局顺序
题面:三个进程 P、Q、R。P 上两个事件,编号 1、2,编号 2 的事件发一条消息给 Q。Q 收到后的事件编号 3,之后又有一个事件编号 4,它发消息给 R。R 先有一个内部事件编号 1,之后收到 Q 的消息,事件编号 5。p.20 指出 P 的 1 和 R 的 1 编号相同,排不出全局顺序;p.21 改用(进程, 编号)表示,并假设进程 ID 排序为 P < Q < R,要求填出全局顺序。
提示
先按规则 4 核对 Q 和 R 的接收编号对不对,再按「先比编号、再比进程」排。
解答
- 先核对编号:Q 收到 P 发来的 2,本地是 0,取 Max(0, 2) + 1 = 3;R 收到 Q 发来的 4,本地是 1,取 Max(1, 4) + 1 = 5。图上的编号都对。
- 排序规则:先比编号,编号相同再比进程 ID。
- 编号 1 有两个,(P, 1) 和 (R, 1),P < R,所以 (P, 1) 在前。
- 全局顺序:(P, 1) → (R, 1) → (P, 2) → (Q, 3) → (Q, 4) → (R, 5)。
- 注意 (R, 1) 排在 (P, 2) 前面只是按编号规定的,两者其实并发。这就是 p.21 下方的局限:Lamport 时钟判不出并发。
完整例题
题面:沿用上一页的走路图。三个进程 p、q、r,p 上依次有 a、b;q 上依次有 c、d;r 上依次有 e、f。消息从 a 发到 c,从 d 发到 f。① 算出每个事件的 Lamport 编号;② 检查时钟条件;③ 找出一对编号有大小但其实并发的事件。
- p:a = 1,a 是发送,带走 1;b = 2。
- q:c 收到 1,本地 0,取 Max(0, 1) + 1 = 2;d = 3,d 是发送,带走 3。
- r:e = 1;f 收到 3,本地 1,取 Max(1, 3) + 1 = 4。
- 检查时钟条件:上一页列出的 8 条先后关系里,a → b(1 < 2)、a → c(1 < 2)、a → d(1 < 3)、a → f(1 < 4)、c → d(2 < 3)、c → f(2 < 4)、d → f(3 < 4)、e → f(1 < 4),全部满足。
- 反例:e = 1 < b = 2,可上一页已经判过 b ‖ e。再如 e = 1 < c = 2,c ‖ e。编号小不等于先发生。
- 排全序(约定 p < q < r):(p, 1)=a、(r, 1)=e、(p, 2)=b、(q, 2)=c、(q, 3)=d、(r, 4)=f。
变式题(先自己做)
自编情境:两个进程 X、Y。X 上依次有 x1、x2、x3;Y 上依次有 y1、y2。消息从 x1 发到 y2,从 y1 发到 x3。① 算出每个事件的 Lamport 编号;② 约定 X < Y 排出全序;③ 指出全序里哪一对相邻事件其实并发。
提示
y1 不收消息,从 0 加 1。x3 收到的是 y1 带来的值,不是 y2 的。
判分点与答案
判分点:① 两个接收事件都要写出 Max 的两个参数;② 编号相同时按进程 ID 排;③ 并发的判断要用「走路」说明,不能只看编号。
- x1 = 1(带走 1),x2 = 2;y1 = 1(带走 1);y2 收到 1,本地 1,取 Max(1, 1) + 1 = 2;x3 收到 1,本地 2,取 Max(2, 1) + 1 = 3。
- 全序:(X, 1)=x1、(Y, 1)=y1、(X, 2)=x2、(Y, 2)=y2、(X, 3)=x3。
- x1 和 y1 相邻且编号都是 1:x1 只能走到 x2、x3 和 y2,走不到 y1;y1 只能走到 y2 和 x3,走不到 x1,并发。x2 和 y2 也相邻且互相走不到,同样并发。
闪卡自测
1. 写出 Lamport 时钟的四条规则。收消息时为什么不能只写 received + 1?
计数器初值 0;每发生一个事件加 1;发消息时带上当前值;收消息时设为 Max(local, received) + 1(p.19)。取 max 是为了保证接收事件的时间戳一定大于发送事件的时间戳,同时不能把本地已经走得更远的进度倒退回去。
2. 时钟条件怎么写?
∀a, b: a → b ⟹ LC(a) < LC(b)(p.20)。
3. LC(a) < LC(b) 能推出 a → b 吗?举一个反例。
不能(p.20)。课件例子里 R 的内部事件编号 1、P 的第二个事件编号 2,1 < 2,但两者之间没有消息链,是并发。
4. 课件列了 Lamport 时钟的哪两个问题?
两个事件(P1、R1)有相同的时间戳;没有全局顺序(p.20)。
5. 附上进程 ID 之后,Lamport 时钟解决了什么、没解决什么?
解决了编号相同排不出全局顺序的问题,得到一个确定的全序;没解决判断并发的问题,排在前面的不一定真的先发生(p.21)。
下一讲
L02b-3 向量时钟:把一个整数换成每台机器一位的向量,换来判断并发的能力。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。