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 的定义、逻辑时钟的更新规则,都是按这张清单分别给出的。
直觉
一台机器在网络里能做的事,归根到底只有三种:自己埋头算(不碰网络),往外发一条消息,从外面收到一条消息。
一步一步看
目标:在两条时间线上认出内部、发送、接收三类事件各是哪一个。
-
画两条横线 P 和 Q,代表两台机器,时间从左往右走。
-
P 上的 a 只在本机计算,是内部事件;Q 上的 c 也是。
-
P 上的 b 发出一条消息,是发送事件。
-
这条消息沿斜箭头到了 Q 上的 d,d 是接收事件。b 和 d 是同一条消息的两头。
怎么判断
| 事件类型 | 英文 | 在时空图上长什么样 |
|---|---|---|
| 内部事件 | 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
直觉
在每条横线上各切一刀,刀左边的事算「已经发生」,刀右边的算「还没发生」。切法随你,可有一种切法会出问题:快照里某台机器已经收到了一条消息,而发这条消息的机器在快照里还没发它。现实中不可能先收后发,这样的快照就是坏的。
一步一步看
目标:对比一致割和不一致割,看哪一种快照在现实中不可能出现。
-
两台机器 A、B,A 发一条消息给 B。
-
一致割:A 那一刀切在「发」之后,B 那一刀切在「收」之前。快照里消息已经发出、还没收到,它正在路上,完全合法。
-
不一致割:A 那一刀切在「发」之前,B 那一刀切在「收」之后。快照里 B 收到了一条 A 还没发出的消息,现实中不可能存在。
-
换成银行转账:快照里 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 出发走一遍。
-
沿 p 的横线往右,走到 b:a → b。
-
顺着 a 发出的消息跨到 q 上的 c:a → c。再沿 q 往右走到 d:c → d,所以 a → d。
-
顺着 d 发出的消息到 r 上的 f:a → f。r 上的 e 在 f 左边,从 a 怎么走都到不了 e;e 也没有任何路能走到 a,所以 a ‖ e。
怎么判断
判定 e → f 的三条规则,满足任一即成立:
- 同一进程内的先后:e 和 f 在同一台机器上,e 先执行。
- 消息的收发:e 是消息 m 的发送,f 是同一条 m 的接收。
- 传递:存在 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 变不变,弄清这种先后关系记下的是哪种因果。
-
A 发消息给 B,B 收到后做了一次计算:发送 → 接收 → 计算,存在路径。
-
假设 B 的计算完全没用消息里的内容:路径还在,happens-before 照样成立。
-
所以 e → f 只能说明 e 可能导致了 f,证明不了 e 真的影响了 f。
-
逻辑时钟按 → 来编号,记下的是因果的可能性:
情形 有路径吗 能说什么 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 的三条规则;再把下面的「变式题」做一遍;最后回查两个最容易错的地方:看图上左右位置判先后、把 → 读成「导致」。三步做完再往下看答案。
必背
- 事件只有三类:内部事件、消息发送、消息接收。
- 一致割不存在从未来穿到过去的消息:某条消息的接收在割内而发送在割外,这个割就不一致;发了还没收到是合法的。
- happens-before 三条判定规则:同进程先后、消息收发、传递;判据是能不能沿时间轴和消息箭头走过去。
- happens-before 是偏序,允许互不可比的事件,也就是并发 e ‖ f。
- 逻辑时钟只度量事件的顺序,不参照物理时间;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。
提示
从每个事件出发各走一遍,记下能到的事件。i 没有任何消息连着,它只能沿 r 往右走。第 ④ 句先看 f 能不能经 m₁ 走到 h。
解答
用「走路」法:从一个事件出发,沿本进程时间轴往右、沿消息箭头跨进程,能走到的都是它的后继。
- 从 e 出发:e → f,经 m₁ 到 g,再到 h,经 m₂ 到 j。所以 e → f、e → g、e → h、e → j。
- 从 f 出发:f → g、f → h、f → j。从 g 出发:g → h、g → j。从 h 出发:h → j。
- 从 i 出发:只能沿 r 往右走到 j,所以 i → j。
- 剩下互相走不到的:i 和 e、f、g、h 都没有消息链相连,所以 e ‖ i、f ‖ i、g ‖ i、h ‖ i。
- 六句:① 真 ② 假,方向反了,是 h → j ③ 真 ④ 假,f 经 m₁ 能走到 h,所以 f → h ⑤ 真 ⑥ 真。
完整例题
题面:沿用「从零讲起」第 3 节的图(p 上 a、b;q 上 c、d;r 上 e、f;消息 a 到 c、d 到 f),列出所有 happens-before 关系和所有并发对。
- 从 a 出发:沿 p 到 b;经消息到 c,再到 d;经消息到 f。所以 a → b、a → c、a → d、a → f。
- 从 b 出发:b 后面没有事件,也没发消息,哪里都走不到。
- 从 c 出发:c → d,经 d 的消息到 f,所以 c → d、c → f。
- 从 d 出发:d → f。从 e 出发:沿 r 到 f,e → f。f 是最后一个事件,走不到别处。
- 一共 8 条 → 关系:a → b、a → c、a → d、a → f、c → d、c → f、d → f、e → f。
- 六个事件两两组合共 15 对,去掉上面 8 对,剩下 7 对就是并发:b ‖ c、b ‖ d、b ‖ e、b ‖ f、a ‖ e、c ‖ e、d ‖ e。
- 检查: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。
- 真。x1 → x2 → y1 → y2,沿 X 的时间轴再跨消息到 Y。
- 真。x2 能走到 y1、y2,走不到 Z;z1 能走到 z2、y2,走不到 X。互相走不到,并发。
- 假。z1 发的消息到 y2,可 z2 在 z1 之后,没有发消息,走不到 y2;y2 也走不到 z2,两者并发。
- 假。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 时钟:给每个事件发一个整数,保证先发生的编号小。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。