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

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。

  1. 先算没收消息的事件,各自从 0 往上加 1:a1 = 1,a2 = 2;b1 = 1,b2 = 2,b3 = 3。a2 是发送事件,消息带走 2。

    两条进程线 A 和 B,A 上 a1、a2、a3,B 上 b1 到 b5,消息从 a2 发到 b4、从 b5 发到 a3。这一步只标出没收消息的事件编号:a1 是 1,a2 是 2,b1 到 b3 是 1、2、3,a2 发出的消息带走值 2,描成青绿

  2. b4 收到 a2 带来的 2。B 本地已经是 3,取 Max(3, 2) + 1 = 4。本地比收到的大,保留本地再加 1。

    同一张图,b4 标出编号 4,从 a2 到 b4 的消息描成青绿,下方注明本地 3 比收到的 2 大,取本地的 3 再加 1

  3. b5 = 5,发消息给 A。a3 收到 5,A 本地是 2,取 Max(2, 5) + 1 = 6。A 的编号一下跳到 6。

    同一张图,b5 标出编号 5,从 b5 到 a3 的消息描成青绿,a3 标出编号 6,下方注明收到的 5 比本地 2 大,A 取 5 再加 1 跳到 6

怎么算

四条规则:

  1. 每个进程维护一个本地计数器,初值为 0。
  2. 进程上每发生一个事件,计数器加 1。
  3. 发送消息时,把当前计数器的值随消息带上。
  4. 收到消息时,把计数器设为 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:找一对编号更小却并发的事件。

  1. 沿用上面的图,看 b1 = 1 和 a2 = 2。

  2. 编号上 1 < 2。

  3. 用上一页的「走路」法:b1 只能往右走到 b5,再经消息到 a3,到不了 a2;a2 经消息到 b4,也走不回 b1。

  4. 两者互相走不到,b1 ‖ a2。编号小于只是碰巧。

    同一张 A、B 时空图,b1 编号 1 和 a2 编号 2 描成青绿,标题写 LC(b1) = 1 小于 LC(a2) = 2,但两者之间没有路,下方说明 b1 只能走到 b5 再到 a3、a2 也走不到 b1,两者并发

怎么判断

记 LC(e) 为事件 e 的 Lamport 编号,两条性质成对出现:

  1. 若 a → b,则 LC(a) < LC(b)。这就是时钟条件:∀a, b: a → b ⟹ LC(a) < LC(b)。
  2. 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 裁决,把全部事件排成一个全序。

  1. 沿用上面的图,把每个事件写成(编号, 进程):(A, 1)、(A, 2)、(A, 6)、(B, 1) 到 (B, 5)。

  2. 先比编号,小的排前面。

  3. 编号 1 撞了两个:(A, 1) 和 (B, 1)。约定 A < B,(A, 1) 排前面。

  4. 排完:(A, 1)、(B, 1)、(A, 2)、(B, 2)、(B, 3)、(B, 4)、(B, 5)、(A, 6)。

    八个事件按编号和进程排成一行:(A,1)、(B,1)、(A,2)、(B,2)、(B,3)、(B,4)、(B,5)、(A,6),开头编号相同的 (A,1) 和 (B,1) 描成青绿,注明编号相同再比进程、约定 A 小于 B;下方说明 (B,1) 排在 (A,2) 前面只是规定,两者其实并发

怎么判断

比较 (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、看到编号小就说先发生。三步做完再往下看答案。

必背

  1. Lamport 时钟四条规则:计数器初值 0;每发生一个事件加 1;发消息时带上当前值;收消息时设为 Max(local, received) + 1。
  2. 时钟条件:a → b ⟹ LC(a) < LC(b)。
  3. Lamport 时钟收消息时取 Max(local, received) + 1;a → b ⟹ LC(a) < LC(b) 成立,反向不成立,因此判不出并发。
  4. Lamport 时钟附上进程 ID 打破平局,得到人为的全序,但仍然判不出两个事件是否并发。
  5. 课件列的两个问题:两个事件可能有相同的时间戳;没有全局顺序。

课件例题

例 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,要求填出全局顺序。

三条水平时间线 P、Q、R,时间向右。P 上有 (P, 1)、(P, 2) 两个事件,(P, 2) 发一条斜箭头到 Q 上的 (Q, 3);Q 之后有 (Q, 4),发箭头到 R 上的 (R, 5);R 在 (R, 5) 之前有一个内部事件 (R, 1),画在 (P, 2) 右侧、(Q, 4) 左侧
图片来源:COMP5567 Lecture_2-Distributed-system.pdf, p.21
提示

先按规则 4 核对 Q 和 R 的接收编号对不对,再按「先比编号、再比进程」排。

解答
  1. 先核对编号:Q 收到 P 发来的 2,本地是 0,取 Max(0, 2) + 1 = 3;R 收到 Q 发来的 4,本地是 1,取 Max(1, 4) + 1 = 5。图上的编号都对。
  2. 排序规则:先比编号,编号相同再比进程 ID。
  3. 编号 1 有两个,(P, 1) 和 (R, 1),P < R,所以 (P, 1) 在前。
  4. 全局顺序:(P, 1) → (R, 1) → (P, 2) → (Q, 3) → (Q, 4) → (R, 5)。
  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 编号;② 检查时钟条件;③ 找出一对编号有大小但其实并发的事件。

  1. p:a = 1,a 是发送,带走 1;b = 2。
  2. q:c 收到 1,本地 0,取 Max(0, 1) + 1 = 2;d = 3,d 是发送,带走 3。
  3. r:e = 1;f 收到 3,本地 1,取 Max(1, 3) + 1 = 4。
  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),全部满足。
  5. 反例:e = 1 < b = 2,可上一页已经判过 b ‖ e。再如 e = 1 < c = 2,c ‖ e。编号小不等于先发生。
  6. 排全序(约定 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 排;③ 并发的判断要用「走路」说明,不能只看编号。

  1. x1 = 1(带走 1),x2 = 2;y1 = 1(带走 1);y2 收到 1,本地 1,取 Max(1, 1) + 1 = 2;x3 收到 1,本地 2,取 Max(2, 1) + 1 = 3。
  2. 全序:(X, 1)=x1、(Y, 1)=y1、(X, 2)=x2、(Y, 2)=y2、(X, 3)=x3。
  3. 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 向量时钟:把一个整数换成每台机器一位的向量,换来判断并发的能力。

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

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