L03b-3 交付顺序(三):全序广播,所有人排成同一个序列
全序只要求全体一致、不规定哪种顺序;FIFO TOB 的两种实现,定序器和 Lamport 时钟,以及怎样分两步验证一个交付序列。
一句话版
全序广播要求所有正确节点按同一个排列交付全部消息。它只管一致,不规定哪种排列才对;排法有两条路,找一个定序器统一编号,或者让每个节点用 Lamport 时钟按同一规则各自排。
读之前最好先懂 L03b-2 的因果序,以及 L02b-2 的 Lamport 时钟。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| TOB | Total Order Broadcast,全序广播,也叫原子广播(atomic broadcast) | 所有节点交付的排列完全一样 |
| FIFO TOB | 带 FIFO 的全序广播 | 排列一样,且同一发送方保序 |
| 复制状态机 | replicated state machine | 几台机器执行同一串命令,保持状态相同 |
| sequencer | 定序器,单一 leader | 由一个领头节点给每条消息编全局序号 |
| LC | Lamport clock,Lamport 逻辑时钟 | 每个进程手里一个只增不减的计数器 |
| 打破平局 | tie-breaking | 时间戳相同时,用所有人都看得到的字段分先后 |
一个类比:全楼信箱排列必须一样
传达室的规矩升到最严一档:全楼每个信箱里的信,排列必须一模一样。至于按什么排,传达室自己定规则就行,没人规定哪种才对。
做法有两种。一种是设一位总管,所有信先交给他,他在信封上写编号,各信箱按编号放。另一种不设总管,每封信出门时盖一个计数章,各信箱按章上的数排,数一样就按寄信人姓名的字母顺序排。
类比在哪里失效:
- 总管病了,全楼的信都停在他桌上。网络里这个节点崩了要重新选,选的过程本身就不简单。
- 盖章的办法看似人人自己排,可信箱得知道「比这个数更小的信不会再来了」才敢放。这需要额外的等待和确认。
从零讲起
1. 全序:所有人一致,不管哪种顺序
它解决什么问题
前两页的 FIFO 和因果序都只约束「每个节点自己看着合理」。两个节点完全可以排出不同的顺序。
这对一类应用是致命的:几台机器各存一份数据,靠执行同一串命令保持一致。命令顺序一不同,结果就不同。比如一台先「余额乘二」再「加十」,另一台反过来,余额就对不上了。全序广播把这个口子堵上。
直觉
全序广播的性质有四条:
- Validity:正确进程广播 m,它最终交付 m。
- Agreement:某个正确进程交付了 m,所有正确进程最终交付 m。
- Integrity:每条消息至多交付一次,且之前确实被广播过。
- Total order:两个正确进程都交付了 m 和 m′,它们交付这两条的先后相同。
前三条和可靠广播一样,新东西只在第四条。它只说「要么都 m 先,要么都 m′ 先」,没说哪个该先。
一步一步看
目标:看全序只要求 P₃、P₄ 的交付顺序一致,不管 M₁ 和 M₂ 哪个在前。
最小的例子:P₁ 广播 M₁,P₂ 广播 M₂,看正确节点 P₃、P₄ 怎么交付。
-
P₃、P₄ 都先 M₁ 后 M₂:两者一样,合法。
-
P₃、P₄ 都先 M₂ 后 M₁:两者也一样,同样合法。
-
P₃ 先 M₁、P₄ 先 M₂:两者不一样,违反全序。
这个例子的价值是说明两种顺序都合法。全序不挑方向,只挑一致。
怎么判断
判断一组交付记录是否满足全序,逐对比较:
- 任取两条消息 m、m′。
- 找出所有交付了这两条的正确节点。
- 看它们是否全部 m 在前,或者全部 m′ 在前。
- 有一个节点方向不同,就违反全序。
用状态机的话说,意思是:同样的初态 + 同样的命令序列 = 同样的终态。全序保证的正是「同样的命令序列」这一半。
常见误解
以为全序就是按发送时间排
全序不规定哪个顺序对,只要求一致。M₂ 发得晚,也可以全体排在 M₁ 前面。
以为全序自动守因果
普通全序只要求排列一样,不管箭头方向,可能全体一致地把回复排在原话前面。全序和因果序的关系放在下一页讲。
试一下
有三条消息、两个正确节点。节点甲交付 X Y Z,节点乙交付 X Z Y。违反全序吗?
违反。Y 和 Z 这一对,甲是 Y 先,乙是 Z 先。
2. 定序器:一个人说了算
它解决什么问题
全序要求所有人一致,可每个节点收到消息的先后不同。最直接的办法是找一个节点替大家排。
FIFO TOB 在全序之外还要求同一发送方保序。下面两种实现都是为 FIFO TOB 设计的。
直觉
指定一个 leader 当定序器。所有消息先交给它,它给每条消息一个单调递增的全局序号,再发给大家。各节点只按序号交付,序号连着才放。
这样排出来的顺序天然一致,因为只有一个人在排。代价也明显:leader 是单点,它崩了,整个系统要停下来重新选举。
一步一步看
目标:看定序器统一编号后,各节点为什么都按同一个顺序交付。
P₁ 广播 A,P₂ 广播 C,L 是定序器。
-
P₁、P₂ 把消息发给 L。
-
L 按自己收到的先后编号,A 是 1 号、C 是 2 号,带着编号发给所有节点。
-
每个节点按号交付,全体都是 A、C。
怎么判断
定序器方案要回答两个问题:
- 一致性从哪来?全序号只有一个来源,所有人按同一串号交付。
- FIFO 从哪来?定序器给同一发送方的消息编号时保持它们的发送次序,各节点按号交付就保住了。
意思是:定序器把「大家商量顺序」变成了「听一个人的」,省掉了商量,换来了单点。
常见误解
以为定序器按消息的发送时间编号
它按自己收到的先后编号。没有全局时钟,发送时间无从比较。
以为定序器崩了也没关系,换一个就行
换人要重新选举,选举期间不能出新序号;新 leader 还得弄清旧 leader 已经发出去哪些号。这正是单点的代价。
试一下
区块链里谁扮演定序器的角色?
出块者。谁被选中出块,谁就决定这一批交易的顺序。中本聪共识、PBFT 的 primary、Raft 的 leader 都在干这件事。
3. Lamport 时钟:不设总管,各自按同一规则排
它解决什么问题
定序器有单点。换个思路:每个节点自己排,只要规则一样、输入一样,排出来就一样。
从哪来(补充)
逻辑时钟由 Leslie Lamport 在 1978 年发表于 Communications of the ACM 的论文《Time, clocks, and the ordering of events in a distributed system》中提出。时间戳相同时用任意固定规则打破平局,常用进程 ID。出处:Lamport timestamp(Wikipedia)。
直觉
每个进程维护一个计数器 LC,三条规则:
- 本地规则:本地事件发生或发送消息时,LC 加一。
- 消息规则:发送时把当前 LC 附在消息上。
- 接收规则:收到消息时,LC 取本地值和消息里的值中较大的那个,再加一。
排全序的规则:LC 小的排前面;LC 相同,按发送方 ID 这类确定性规则排。
打破平局必须用确定性规则。各节点独立排,必须得到同一个结果,所以只能用消息里自带、人人看得到的字段。「谁先到算谁前面」依赖本地观察,各节点会排出不同结果。
一步一步看
目标:看各节点用 Lamport 时钟加发送方 ID,怎样各自排出同一个全序。
-
P₁ 一次本地事件,LC 从 0 到 1;发送 m₁,LC 到 2,附在 m₁ 上。
-
P₂ 同样一次本地事件再发送 m₂,m₂ 也带着 2。
-
P₃ 收到 m₁,按接收规则 max(0, 2) + 1,LC 变成 3。
-
m₁ 和 m₂ 的 LC 都是 2,平局。按发送方 ID,P₁ 小于 P₂,m₁ 排第一。
怎么算
排序键 = (LC, 发送方 ID),先比 LC,再比 ID。
意思是:每条消息带着一对数,所有节点拿同一对数、同一个比较方法,排出的全序必然相同。
Lamport 时钟和因果的关系是单向的:m → m′ ⟹ LC(m) < LC(m′)。所以按 LC 排出来的全序自动兼容因果序。反过来,LC(m) < LC(m′) 推不出 m → m′。
全序用 Lamport、因果序用向量,各取所需。标量能排出一个全序,却丢了并发信息;向量能判因果和并发,却排不出唯一全序。
常见误解
以为 Lamport 时钟能判断两条消息是否并发
不能。LC 小推不出因果先于,判并发得用上一页的向量。
以为 Lamport 法没有任何代价
它没有单点,但节点得确认之后不会再来时间戳更小的消息,才敢交付眼前这条。这需要额外的等待或确认机制。
试一下
P₃ 当前 LC 是 5,收到一条带着 3 的消息,LC 变成多少?
max(5, 3) + 1 = 6。
4. 验证 FIFO TOB:两步走
它解决什么问题
拿到一个交付序列,怎么判断它是否同时满足全序和 FIFO?两条性质看的东西不同,分开验最不容易漏。
直觉
第一步看全序:所有进程的序列是否一模一样。第二步看 FIFO:对每个发送方单独看,它的消息在序列里的相对次序是否和发送次序一致。
FIFO 只管相对次序,不要求连续,别人的消息插在中间不影响。
一步一步看
目标:分两步查三个候选序列,看哪个全体一致却违反 FIFO。
P₁ 先广播 A 再广播 B,P₂ 广播 C,P₃ 广播 D。三个候选序列:
-
A C B D:全体相同;A 在 B 前。合法。
-
A C D B:全体相同;A 仍在 B 前。合法。
-
C B A D:全体相同;可 B 跑到了 A 前面,违反 FIFO。
只有 P₁ 发了不止一条,C、D 各自的发送方只发一条,FIFO 那一步不用查它们。
怎么判断
- 把各进程的交付序列并排,逐位比较,有一位不同就违反全序。
- 列出发了多条消息的发送方。
- 对每个这样的发送方,抽出它的消息,看在序列中的先后是否和发送先后一致。
- 两步都过,才是 FIFO TOB。
意思是:全序管「大家一样」,FIFO 管「每个人自己的不颠倒」,缺一条都不行。
常见误解
以为全体一致就够了
C B A D 全体一致,仍然不是 FIFO TOB。全序和 FIFO 是两条独立的性质。
以为 A 和 B 之间不能插别人的消息
可以插。FIFO 只要求 A 在 B 前,A C B D 里中间夹着 C 完全合法。
试一下
D A C B 是合法的 FIFO TOB 序列吗?(假设全体相同)
是。全体相同,P₁ 的 A 仍在 B 前。
把它们串起来
全序把要求从「各自合理」提到「全体一致」。它的第四条性质只说先后相同,不说谁先,所以两种方向都合法。复制状态机需要的正是这一点:同一串命令,同一个结果。
排出全序有两条路。定序器简单,一致性来自只有一个人在排,代价是单点。Lamport 时钟不设总管,每条消息带着时间戳和发送方 ID,各节点用同一个比较方法排,代价是要等确认。
两种实现都是 FIFO TOB,除了全体一致还要同一发送方保序。拿到一个序列验证时,就照这两条分两步查。
时钟的分工也在这里定下来:全序用标量,因果用向量。下一页把全序和因果序、gossip 放在同一张强弱图上比较。
课件里的坑
- [课件留白] p.44 的 Agreement 写的是可靠广播版,前件是「正确进程」。uniform 版本只在 p.45 的对照表里用「Uniformity: Yes (usually)」一笔带过,答题要写 uniform 时注意把前件改成「任何进程」。
- [课件留白] p.47 只说 Lamport 法「无单点」,没讲它的代价:节点要确认之后不会再来更小时间戳的消息,才能交付,需要额外的等待或确认机制。
- [概念区分] p.47 的平局规则必须是确定性的。答题写「先到先排」会被扣分,因为各节点到达顺序不同,排不出同一个结果。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写全序的四条性质,再写出 Lamport 时钟的三条规则和排序键。然后做课件例题,重点是 p.49 的两步验证。最后回查两个最容易错的地方:以为全序规定了某个特定顺序、以为平局可以按到达先后排。
必背
- Total order 只要求「所有人一致」,不要求「哪个顺序才对」
- 全序广播是复制状态机和区块链账本的必需品:同样的初态 + 同样的命令序列 = 同样的终态
- FIFO TOB 两种实现:sequencer(单 leader 定序,有单点)和 Lamport clock(逻辑时间戳 + 确定性打破平局)
- Lamport 时钟三条规则:本地事件/发送时 LC++;发送附带 LC;接收时 LC ← max(本地, 收到) + 1;平局按 sender ID 等确定性规则排
- 标量时钟能排全序但丢并发信息,向量时钟能判因果但排不出唯一全序
- 验证 FIFO TOB 分两步:各进程序列是否相同,再看每个发送方的消息相对次序是否与发送次序一致,允许中间插别人的消息
课件例题
例 1(课件 p.45):P1 广播 M1、P2 广播 M2,正确节点 P3、P4 怎么交付
题面:在全序广播下,写出 P3、P4 合法的交付情况。
提示
全序只要求两者一样,不规定哪条在前。
解答
P3、P4 都先 M1 后 M2,或者都先 M2 后 M1。两种都合法,只要两者相同。一个先 M1、另一个先 M2 就违反全序。
例 2(课件 p.48):两条消息 Lamport 时间戳相同,谁在前
题面:m1 的 LC = 2,发送方 P1;m2 的 LC = 2,发送方 P2。按全序规则谁排在前面?
提示
LC 打平之后,看消息里还有哪个字段是人人都看得到的。
解答
LC 相同,按发送方 ID 这类确定性规则打破平局。P1 的 ID 小于 P2,所以 m1 在 m2 之前。关键在于每个节点用同一条规则,算出的结果就一样。
例 3(课件 p.49,Example FIFO TOB):系统按 A、C、B、D 交付,每个进程看到什么
题面:P1 先后广播 A、B;P2 广播 C;P3 广播 D。系统给所有正确进程的交付顺序是 A、C、B、D。填空:在每个进程(P1、P2、P3)上 ____。
提示
分两步说:全序成立吗?P1 的两条消息次序对吗?
解答
- 每个进程都按 A、C、B、D 交付。
- 全序成立:三个进程排列相同。
- FIFO 成立:P1 的 A 在 B 前,中间插了 C 不影响。C 和 D 的发送方各只发一条,不用查。
- 换成 A、C、D、B 也合法;换成 C、B、A、D 就违反 FIFO,因为 B 跑到了 A 前面。
完整例题
用 Lamport 时钟把 p.49 的四条消息排出全序,看它是否正好得到 A、C、B、D。
设定:三个进程 LC 初值都是 0。P1 广播 A,紧接着广播 B;P2 广播 C;P3 先有一次本地事件,再广播 D。消息在途中,发送前谁也没收到别人的消息。
第一步,给每条消息算时间戳(发送时 LC 加一,再附上):
- A:P1 的 LC 从 0 到 1,A 带 1。
- B:P1 的 LC 从 1 到 2,B 带 2。
- C:P2 的 LC 从 0 到 1,C 带 1。
- D:P3 本地事件到 1,发送时到 2,D 带 2。
第二步,按排序键 (LC, 发送方 ID) 排:
| 消息 | LC | 发送方 | 排序键 |
|---|---|---|---|
| A | 1 | P1 | (1, P1) |
| C | 1 | P2 | (1, P2) |
| B | 2 | P1 | (2, P1) |
| D | 2 | P3 | (2, P3) |
LC = 1 的两条 A、C 打平,按 ID,P1 < P2,A 在前。LC = 2 的 B、D 打平,P1 < P3,B 在前。结果是 A、C、B、D。
第三步,验证两条性质。所有节点拿同样四对数、同样的比较方法,排出的序列相同,全序成立。P1 的 A 带 1、B 带 2,同一进程的时间戳严格递增,A 一定在 B 前,FIFO 成立。
再多想一层:同一发送方的时间戳一定递增,这就是 Lamport 法自动满足 FIFO 的原因。真正麻烦的是「何时敢交付」:P2 收到 B 时,它得确认不会再有 LC 小于 2 的消息还在路上,才能放出 B。
变式题(先自己做)
变式|自编情境:P1 广播 X(发送前没有其他事件)。P2 先收到 X,再广播 Y。P3 有两次本地事件后广播 Z。三个进程 LC 初值都是 0。
(1) 写出 X、Y、Z 的时间戳。(2) 按 Lamport 规则排出全序。(3) 这个全序守因果吗?
提示
P2 收到 X 时用接收规则,之后发送 Y 再加一。P3 两次本地事件各加一,发送再加一。
判分点与答案
(1) X:P1 发送时 0 → 1,X 带 1。Y:P2 收到 X,max(0, 1) + 1 = 2;发送 Y 时 2 → 3,Y 带 3。Z:P3 两次本地事件到 2,发送时到 3,Z 带 3。
(2) 排序键 X (1, P1)、Y (3, P2)、Z (3, P3)。Y、Z 打平,P2 < P3,Y 在前。全序是 X、Y、Z。
(3) 守。唯一的因果边是 X → Y,X 带 1 小于 Y 带 3,X 在前。m → m′ ⟹ LC(m) < LC(m′),按 LC 排出来的全序自动兼容因果。
判分点:接收规则写成 max 再加一;发送也要加一;平局写明按 ID;第 (3) 问指出因果边并用单向蕴含说明。
闪卡自测
1. 全序广播的四条性质是什么?
Validity、Agreement、Integrity(不重复、不凭空造)、Total order:任意两个正确进程交付 m 和 m′ 的先后相同。
2. 全序规定哪个顺序才对吗?
不规定,只要求所有正确进程一致。
3. 为什么复制状态机需要全序,因果序不够?
因果序允许并发消息在不同副本上顺序不同,执行结果就会分叉。全序保证同一串命令。
4. FIFO TOB 有哪两种实现?各自的弱点?
定序器:单个 leader 编号,有单点。Lamport 时钟:没有单点,但要等确认不会再来更小时间戳的消息。
5. Lamport 时钟的接收规则是什么?
LC ← max(本地 LC, 收到的 LC) + 1。
6. 平局为什么不能按到达先后排?
到达先后各节点不同,排出来就不一致。只能用消息里人人看得到的字段,比如发送方 ID。
7. 为什么全序用标量时钟,因果用向量时钟?
标量能排出唯一全序但丢了并发信息;向量能判因果,却排不出唯一全序。
8. 验证一个 FIFO TOB 交付序列要看哪两点?
各进程的序列是否相同;每个发送方的消息相对次序是否和发送次序一致,中间允许插别人的消息。
下一讲
下一页 L03b-4 走向另一头:gossip 放弃确定性换规模;再把本讲所有广播放到一张强弱图上,看全序和因果序为什么互不包含、全序为什么和共识等价。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。