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

L02b-1 事件、割与 happens-before:没有统一的表,怎么排先后

从三类事件和时空图讲起,学会判断一个快照是否一致,再一帧一帧沿时间轴和消息箭头「走路」,判出两件事是先后还是并发。

一句话版

没有一块所有机器共用的表,两台机器的时间戳就不能比大小。剩下唯一靠得住的先后,是「沿着消息链能追过去」:a 的消息传到了 b 那边,a 就一定在 b 之前。这一页先说清排序的对象是什么(事件、割),再学会用这条规则判先后。

本讲前三页讲了分布式系统缺什么、网络假设和正确性语言,从 L02a 开始。这一页进入本讲后半:逻辑时钟。

先认识这几个词

词 全称 / 读法 一句人话
事件 event 一台机器上发生的一件事:本地计算、发消息或收消息
时空图 space-time diagram 每台机器一条横线,时间往右走,消息画成斜箭头
割 cut 在每条横线上各切一刀,拼成一张全局快照
a → b happens-before,读「a 先于 b」 沿消息链能从 a 追到 b
并发 concurrent,记作 a ‖ b 两个事件谁也追不到谁,没有先后
偏序 partial order 有的能比先后,有的不能比

一个类比:群聊里的引用关系

还是那个跨时区的项目群。每人手机上的时间都不准,两条消息的时间戳出自两块不同的表,比大小没有意义。

唯一能确定的先后是引用关系:B 这句话回应了 A,B 就一定在 A 之后。C 回应了 B,C 也一定在 A 之后。顺着引用链能追到的是先后,追不到的是各说各的。

  • 引用链:happens-before
  • 互不引用:并发
  • 截一张群聊截图:割
  • 截图里有人回应了一条还没出现的消息:不一致割

类比在哪里失效:

  • 群聊里「引用」是人主动点的,happens-before 不管内容,只要消息从 a 那边传过来就算。
  • 群聊有服务器给的统一顺序,本课的机器拿不到这样的顺序。

从零讲起

1. 事件:排序的对象只有三类

它解决什么问题

要给事情排先后,先得说清排的是哪些事情。课件把一台机器上能发生的事收窄成一张封闭的清单,后面 happens-before 的定义、逻辑时钟的更新规则,都是按这张清单分别给出的。

直觉

一台机器在网络里能做的事,归根到底只有三种:自己埋头算(不碰网络),往外发一条消息,从外面收到一条消息。

一步一步看

目标:在两条时间线上认出内部、发送、接收三类事件各是哪一个。

  1. 画两条横线 P 和 Q,代表两台机器,时间从左往右走。

  2. P 上的 a 只在本机计算,是内部事件;Q 上的 c 也是。

  3. P 上的 b 发出一条消息,是发送事件。

  4. 这条消息沿斜箭头到了 Q 上的 d,d 是接收事件。b 和 d 是同一条消息的两头。

    两条进程时间线 P 和 Q。P 上 a 是内部事件,b 是发送事件;Q 上 c 是内部事件,d 是接收事件。一条消息从 b 发到 d,b、d 和这条消息描成青绿,下方注明 a、c 只在本机计算不碰网络

怎么判断

事件类型 英文 在时空图上长什么样
内部事件 internal event 横线上的点,没有箭头连着
发送事件 message send 一个箭头从这个点出发
接收事件 message receive 一个箭头指到这个点

意思是:看一个点有没有箭头、箭头朝哪个方向,就能分出它是哪一类。

常见误解

以为「收到消息后算一下再回复」是一个事件

那是三个事件:一次接收、一次内部计算、一次发送。时空图上每个点只能是三类里的一类,题目里一个动作包含收和发时,要拆成两个点。

试一下

一台机器从磁盘读了一个文件,算出哈希值,然后把哈希值发给另一台机器。这里有几个事件、各是哪类?

读文件和算哈希都只在本机,可以记成一个或两个内部事件;把哈希值发出去是一个发送事件。另一台机器那边还会有一个对应的接收事件。

2. 割:给整个系统拍一张快照

它解决什么问题

没有全局时钟,就没法说「在 10 点整,所有机器的状态是什么」。可做检查点、故障恢复、调试时都需要一张全局状态的快照。割就是在没有统一时间的前提下拼出这张快照的方法,课件列的三条理由是:没有全局时钟、要可视化全局状态、要分析因果关系。

从哪来(补充)

K. Mani Chandy 和 Leslie Lamport 1985 年 2 月在 ACM Transactions on Computer Systems 发表《Distributed Snapshots: Determining Global States of a Distributed System》,提出了后来被称为 Chandy–Lamport 的快照算法,它记录下的就是一个一致的全局状态。

出处:Wikipedia: Chandy–Lamport algorithm

直觉

在每条横线上各切一刀,刀左边的事算「已经发生」,刀右边的算「还没发生」。切法随你,可有一种切法会出问题:快照里某台机器已经收到了一条消息,而发这条消息的机器在快照里还没发它。现实中不可能先收后发,这样的快照就是坏的。

一步一步看

目标:对比一致割和不一致割,看哪一种快照在现实中不可能出现。

  1. 两台机器 A、B,A 发一条消息给 B。

  2. 一致割:A 那一刀切在「发」之后,B 那一刀切在「收」之前。快照里消息已经发出、还没收到,它正在路上,完全合法。

  3. 不一致割:A 那一刀切在「发」之前,B 那一刀切在「收」之后。快照里 B 收到了一条 A 还没发出的消息,现实中不可能存在。

    左右两张时空图,每张有 A、B 两条时间线和一条从 A 发到 B 的消息,虚线是割。左边一致割在 A 上切在发送之后、在 B 上切在接收之前,消息还在路上;右边不一致割在 A 上切在发送之前、在 B 上切在接收之后,等于收到了还没发出的消息,这条割线描成青绿

  4. 换成银行转账:快照里 B 已经收到一百元,A 那边还没扣款,从这张快照恢复,系统里会凭空多出一百元。

怎么判断

对割里的每一条消息检查一次:

  • 接收在刀左、发送在刀右 → 不一致割。意思是:有消息从割的未来一侧穿到了过去一侧。
  • 发送在刀左、接收在刀右 → 合法,消息在路上。
  • 两头都在刀左,或都在刀右 → 合法。

只要有一条消息违规,整个割就不一致。

常见误解

以为切在同一物理时刻的割就一定一致

本课没有全局物理时钟,「同一时刻」本身无从谈起。判断一致与否只看有没有消息从割外的发送跑到割内的接收,和刀切在什么物理时间无关。

试一下

一个割里,A 发给 B 的消息 m₁ 两头都在刀左,B 发给 C 的消息 m₂ 发送在刀左、接收在刀右,C 发给 A 的消息 m₃ 接收在刀左、发送在刀右。这个割一致吗?

不一致。m₁、m₂ 都合法,m₂ 只是还在路上;m₃ 的接收在割内、发送在割外,有消息从未来穿到过去,一条违规就够了。

3. happens-before:沿时间轴和消息箭头走路

它解决什么问题

没有统一的表,又必须排先后。银行转账系统里,「借记 A」一定要先于「贷记 B」;日志、安全审计、调度也都离不开顺序。happens-before(记作 →)给出了一种不依赖物理时间的先后定义。

直觉

从一个事件出发,只能做两种移动:沿着本机的横线往右走,或者顺着消息箭头跨到另一台机器。能走到的事件都在它之后。两个事件互相都走不到,就没有先后,叫并发。

一步一步看

目标:从 a 出发沿时间轴和消息箭头走,看哪些事件在 a 之后、哪个和 a 并发。

三台机器 p、q、r。p 上依次有 a、b;q 上依次有 c、d;r 上依次有 e、f。消息从 a 发到 c,从 d 发到 f。从 a 出发走一遍。

  1. 沿 p 的横线往右,走到 b:a → b。

    三条进程线 p、q、r,p 上有 a、b,q 上有 c、d,r 上有 e、f,消息从 a 发到 c、从 d 发到 f。这一步 a、b 和它们之间的那段时间轴描成青绿,其余事件还是浅灰

  2. 顺着 a 发出的消息跨到 q 上的 c:a → c。再沿 q 往右走到 d:c → d,所以 a → d。

    同一张时空图,从 a 到 c 的消息箭头和 c、d 之间的时间轴描成青绿,a、b 已经走过显示为黑色

  3. 顺着 d 发出的消息到 r 上的 f:a → f。r 上的 e 在 f 左边,从 a 怎么走都到不了 e;e 也没有任何路能走到 a,所以 a ‖ e。

    同一张时空图,从 d 到 f 的消息和 f 描成青绿;r 上的 e 仍是浅灰,表示从 a 走不到它,下方注明 a 和 e 并发

怎么判断

判定 e → f 的三条规则,满足任一即成立:

  1. 同一进程内的先后:e 和 f 在同一台机器上,e 先执行。
  2. 消息的收发:e 是消息 m 的发送,f 是同一条 m 的接收。
  3. 传递:存在 g,使得 e → g 且 g → f。

意思是:三条规则合起来就是「沿时间轴和消息箭头能走过去」。e 走得到 f,就是 e → f;e 走不到 f、f 也走不到 e,就是 e ‖ f。

happens-before 还满足三条性质:非自反(没有事件先于自己)、反对称(e → f 时 f 不可能先于 e)、传递。它是偏序:允许有互不可比的事件,也就是并发。

常见误解

看图上左右位置判先后

画在左边不等于先发生。两台机器之间没有消息链,左右位置只是画图时随手摆的,它们就是并发。上面的例子里 e 画在 b 左边,可 b 和 e 之间没有路,b ‖ e。

以为分布式系统里所有事件都能排出唯一的顺序

happens-before 是偏序,天然留有并发事件。要所有事件排成一条线(全序),得额外加规则或协议,下一页的 Lamport 时钟就是这样做的。

试一下

沿用上面的图:b 和 f 是什么关系?c 和 e 呢?

b ‖ f:b 没有发出任何消息,从 b 只能沿 p 往右走,走不到 r;f 也走不回 b。c ‖ e:c 能走到 d、f,可 e 在 f 之前,走不到;e 只能走到 f,也到不了 c。

4. 逻辑时钟捕捉的是「可能导致」

它解决什么问题

「走路」能判先后,可每次都要在图上找路,太慢。逻辑时钟的想法是给每个事件发一个时间戳,让时间戳替你记住先后。动手设计之前,先要说清它记的到底是什么。

直觉

e → f 说明有一条信息传递路径从 e 通到 f,e 的消息有机会影响 f。至于 f 有没有真的用到 e 的信息,路径本身说明不了。

一步一步看

目标:看 B 用不用消息内容时 happens-before 变不变,弄清这种先后关系记下的是哪种因果。

  1. A 发消息给 B,B 收到后做了一次计算:发送 → 接收 → 计算,存在路径。

  2. 假设 B 的计算完全没用消息里的内容:路径还在,happens-before 照样成立。

  3. 所以 e → f 只能说明 e 可能导致了 f,证明不了 e 真的影响了 f。

  4. 逻辑时钟按 → 来编号,记下的是因果的可能性:

    情形 有路径吗 能说什么
    B 用了消息内容 有 发送 → 计算,可能导致
    B 没用消息内容 有 发送 → 计算,仍是可能导致
    两者之间没有消息链 没有 并发,谈不上谁导致谁

怎么判断

逻辑时钟的三个要点:

  • 不依赖物理时钟,可用来定义事件的顺序。
  • 只度量事件的顺序,不参照任何外部物理时间。
  • 对 e → f,可以说 e 可能导致了 f。意思是:它捕捉的是因果的可能性,答题时要写「可能」两个字。

课件列的用途有两个:复制数据库里的一致性,以及调试和排查分布式系统的故障。

常见误解

把 → 读成「导致」

课件的措辞是 possibly caused,「可能导致」。存在信息传递路径只说明 e 有可能影响 f,证明不了真的影响了。

试一下

日志里记着:A 给 B 发了一条「你好」,B 收到后计算出一个哈希值。能说是「你好」这条消息导致了 B 的计算结果吗?

只能说可能。发送 → 接收 → 计算,存在路径,所以 A 的发送 happens-before B 的计算;B 的计算有没有用到「你好」的内容,从这条关系看不出来。

把它们串起来

这一页从三个「没有」的第一条接着讲。没有全局时钟,就先把排序的对象收窄:每台机器上只有内部、发送、接收三类事件。拼一张全局快照用割,判断它可不可信只看一件事:有没有消息从割的未来一侧穿回过去。

排先后用 happens-before:沿本机时间轴和消息箭头能走过去,就是先后,互相走不到就是并发。它是偏序,并发事件之间没有先后可言。它记的是「可能导致」,不是确定的因果。

一致割其实也是用 happens-before 判的:不允许接收在割内、发送在割外。下一页给每个事件发一个数字,让数字的大小和 → 对上,这就是 Lamport 时钟。

课件里的坑

  • [同名不同义] p.9 的「同步执行 / 异步执行」说的是任务顺序执行还是独立执行,和 p.11–14 的同步模型(网络延迟有没有上界)是两回事。
  • [措辞要准] p.18 写的是 possibly caused。答题写成「e 导致了 f」会被扣分,要写「e 可能导致了 f」。
  • [易误读] p.17 例题里 i 画在 e、f 之间,位置看着像在它们中间发生,但没有任何消息连到 i,它和 e、f、g、h 都并发。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写三类事件和 happens-before 的三条规则;再把下面的「变式题」做一遍;最后回查两个最容易错的地方:看图上左右位置判先后、把 → 读成「导致」。三步做完再往下看答案。

必背

  1. 事件只有三类:内部事件、消息发送、消息接收。
  2. 一致割不存在从未来穿到过去的消息:某条消息的接收在割内而发送在割外,这个割就不一致;发了还没收到是合法的。
  3. happens-before 三条判定规则:同进程先后、消息收发、传递;判据是能不能沿时间轴和消息箭头走过去。
  4. happens-before 是偏序,允许互不可比的事件,也就是并发 e ‖ f。
  5. 逻辑时钟只度量事件的顺序,不参照物理时间;e → f 说的是 e 可能导致了 f。

课件例题

例 1(课件 p.17):列出一张时空图里所有先后关系和并发对

题面:三个进程 p、q、r。p 上依次有事件 e、f;q 上依次有 g、h;r 上依次有 i、j。消息 m₁ 从 f 发出、在 g 接收;消息 m₂ 从 h 发出、在 j 接收。i 在图上的横向位置落在 e、f 之间(比 g、h 都靠左),但没有任何消息连到它。要求列出所有 happens-before 关系(含直接和传递)和所有并发事件对,并判断六句真假:① i → j ② j → h ③ e → g ④ f ‖ h ⑤ f ‖ i ⑥ e ‖ i。

三条进程时间线 p、q、r 的时空图:p 上有事件 e 和 f,q 上有 g 和 h,r 上有 i 和 j,消息 m₁ 从 f 发到 g、m₂ 从 h 发到 j;沿时间轴和消息箭头走得到的 e 到 g 成立、i 到 j 成立,互相走不到的 f 与 i、e 与 i 是并发

提示

从每个事件出发各走一遍,记下能到的事件。i 没有任何消息连着,它只能沿 r 往右走。第 ④ 句先看 f 能不能经 m₁ 走到 h。

解答

用「走路」法:从一个事件出发,沿本进程时间轴往右、沿消息箭头跨进程,能走到的都是它的后继。

  1. 从 e 出发:e → f,经 m₁ 到 g,再到 h,经 m₂ 到 j。所以 e → f、e → g、e → h、e → j。
  2. 从 f 出发:f → g、f → h、f → j。从 g 出发:g → h、g → j。从 h 出发:h → j。
  3. 从 i 出发:只能沿 r 往右走到 j,所以 i → j。
  4. 剩下互相走不到的:i 和 e、f、g、h 都没有消息链相连,所以 e ‖ i、f ‖ i、g ‖ i、h ‖ i。
  5. 六句:① 真 ② 假,方向反了,是 h → j ③ 真 ④ 假,f 经 m₁ 能走到 h,所以 f → h ⑤ 真 ⑥ 真。

完整例题

题面:沿用「从零讲起」第 3 节的图(p 上 a、b;q 上 c、d;r 上 e、f;消息 a 到 c、d 到 f),列出所有 happens-before 关系和所有并发对。

  1. 从 a 出发:沿 p 到 b;经消息到 c,再到 d;经消息到 f。所以 a → b、a → c、a → d、a → f。
  2. 从 b 出发:b 后面没有事件,也没发消息,哪里都走不到。
  3. 从 c 出发:c → d,经 d 的消息到 f,所以 c → d、c → f。
  4. 从 d 出发:d → f。从 e 出发:沿 r 到 f,e → f。f 是最后一个事件,走不到别处。
  5. 一共 8 条 → 关系:a → b、a → c、a → d、a → f、c → d、c → f、d → f、e → f。
  6. 六个事件两两组合共 15 对,去掉上面 8 对,剩下 7 对就是并发:b ‖ c、b ‖ d、b ‖ e、b ‖ f、a ‖ e、c ‖ e、d ‖ e。
  7. 检查:e 只和 f 有关系,其余全并发;b 只和 a 有关系,其余全并发。两个事件都是「孤立的分支」,符合直觉。

变式题(先自己做)

自编情境:三台机器 X、Y、Z。X 上依次有 x1、x2;Y 上依次有 y1、y2;Z 上依次有 z1、z2。消息从 x2 发到 y1,从 z1 发到 y2。判断:① x1 → y2 ② x2 ‖ z1 ③ z2 → y2 ④ y1 → z2。

提示

先从 x1 和 z1 各走一遍,看能到哪些事件。z2 在 z1 之后,它有没有发出消息?

判分点与答案

判分点:① 每一句都要给出路径或说明找不到路径;② 第 ③ 句要注意 z2 自己没有发消息;③ 第 ④ 句要看 y1 有没有消息去 Z。

  1. 真。x1 → x2 → y1 → y2,沿 X 的时间轴再跨消息到 Y。
  2. 真。x2 能走到 y1、y2,走不到 Z;z1 能走到 z2、y2,走不到 X。互相走不到,并发。
  3. 假。z1 发的消息到 y2,可 z2 在 z1 之后,没有发消息,走不到 y2;y2 也走不到 z2,两者并发。
  4. 假。y1 只能沿 Y 走到 y2,Y 没有消息去 Z,所以 y1 ‖ z2。

闪卡自测

1. 事件有哪几类?什么样的割是不一致的?

只有三类:内部事件、消息发送、消息接收(p.8)。某条消息的接收在割内而发送在割外,这个割就不一致,它记录了一个「收到了还没被发出的消息」的状态;反过来「发了但还没收到」是合法的(p.10)。

2. 课件列的「为什么需要割」有哪三条?

没有全局时钟;要可视化全局状态;要分析因果关系(p.10)。

3. happens-before 的三条判定规则是什么?实操怎么判并发?

同一进程内 e 先于 f 执行、e 是消息 m 的发送而 f 是同一条 m 的接收、以及传递性(p.16)。实操是「走路」:沿本进程时间轴和消息箭头能走到就是 →,互相都走不到就是 ‖。

4. happens-before 为什么是偏序而不是全序?

偏序允许存在互不可比的元素,也就是并发事件。分布式系统里天然没有全序,要全序得额外加协议(p.16)。

5. 逻辑时钟捕捉的是「导致」还是「可能导致」?

可能导致(p.18)。存在信息传递路径只说明 e 有可能影响 f,不能证明真的影响了。

下一讲

L02b-2 Lamport 时钟:给每个事件发一个整数,保证先发生的编号小。

下一讲 →
L02b-2 L02b-2 Lamport 时钟:给每个事件发一个号

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