← COMP5567 全部讲次
L03b-3 · 第 2 周

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 和因果序都只约束「每个节点自己看着合理」。两个节点完全可以排出不同的顺序。

这对一类应用是致命的:几台机器各存一份数据,靠执行同一串命令保持一致。命令顺序一不同,结果就不同。比如一台先「余额乘二」再「加十」,另一台反过来,余额就对不上了。全序广播把这个口子堵上。

直觉

全序广播的性质有四条:

  1. Validity:正确进程广播 m,它最终交付 m。
  2. Agreement:某个正确进程交付了 m,所有正确进程最终交付 m。
  3. Integrity:每条消息至多交付一次,且之前确实被广播过。
  4. Total order:两个正确进程都交付了 m 和 m′,它们交付这两条的先后相同。

前三条和可靠广播一样,新东西只在第四条。它只说「要么都 m 先,要么都 m′ 先」,没说哪个该先。

一步一步看

目标:看全序只要求 P₃、P₄ 的交付顺序一致,不管 M₁ 和 M₂ 哪个在前。

最小的例子:P₁ 广播 M₁,P₂ 广播 M₂,看正确节点 P₃、P₄ 怎么交付。

  1. P₃、P₄ 都先 M₁ 后 M₂:两者一样,合法。

  2. P₃、P₄ 都先 M₂ 后 M₁:两者也一样,同样合法。

  3. P₃ 先 M₁、P₄ 先 M₂:两者不一样,违反全序。

    全序的三种交付组合表格:P₃ 和 P₄ 都先 M₁ 后 M₂ 合法,都先 M₂ 后 M₁ 也合法,P₃ 先 M₁ 而 P₄ 先 M₂ 违反全序,违反那一格被标出

这个例子的价值是说明两种顺序都合法。全序不挑方向,只挑一致。

怎么判断

判断一组交付记录是否满足全序,逐对比较:

  1. 任取两条消息 m、m′。
  2. 找出所有交付了这两条的正确节点。
  3. 看它们是否全部 m 在前,或者全部 m′ 在前。
  4. 有一个节点方向不同,就违反全序。

用状态机的话说,意思是:同样的初态 + 同样的命令序列 = 同样的终态。全序保证的正是「同样的命令序列」这一半。

常见误解

以为全序就是按发送时间排

全序不规定哪个顺序对,只要求一致。M₂ 发得晚,也可以全体排在 M₁ 前面。

以为全序自动守因果

普通全序只要求排列一样,不管箭头方向,可能全体一致地把回复排在原话前面。全序和因果序的关系放在下一页讲。

试一下

有三条消息、两个正确节点。节点甲交付 X Y Z,节点乙交付 X Z Y。违反全序吗?

违反。Y 和 Z 这一对,甲是 Y 先,乙是 Z 先。

2. 定序器:一个人说了算

它解决什么问题

全序要求所有人一致,可每个节点收到消息的先后不同。最直接的办法是找一个节点替大家排。

FIFO TOB 在全序之外还要求同一发送方保序。下面两种实现都是为 FIFO TOB 设计的。

直觉

指定一个 leader 当定序器。所有消息先交给它,它给每条消息一个单调递增的全局序号,再发给大家。各节点只按序号交付,序号连着才放。

这样排出来的顺序天然一致,因为只有一个人在排。代价也明显:leader 是单点,它崩了,整个系统要停下来重新选举。

一步一步看

目标:看定序器统一编号后,各节点为什么都按同一个顺序交付。

P₁ 广播 A,P₂ 广播 C,L 是定序器。

  1. P₁、P₂ 把消息发给 L。

    定序器第 1 步:四条时间线 P₁、P₂、定序器 L、P₃。P₁ 广播 A、P₂ 广播 C,两条箭头指向定序器 L,被标出

  2. L 按自己收到的先后编号,A 是 1 号、C 是 2 号,带着编号发给所有节点。

    定序器第 2 步:定序器 L 给 A 编 1 号、给 C 编 2 号,被标出,再从 L 发出三条箭头到 P₁、P₂、P₃

  3. 每个节点按号交付,全体都是 A、C。

    定序器第 3 步:P₁、P₂、P₃ 三个节点都按号交付 A 再交付 C,被标出;右栏三行都写 A, C,定序器那一行写着单点

怎么判断

定序器方案要回答两个问题:

  1. 一致性从哪来?全序号只有一个来源,所有人按同一串号交付。
  2. 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,三条规则:

  1. 本地规则:本地事件发生或发送消息时,LC 加一。
  2. 消息规则:发送时把当前 LC 附在消息上。
  3. 接收规则:收到消息时,LC 取本地值和消息里的值中较大的那个,再加一。

排全序的规则:LC 小的排前面;LC 相同,按发送方 ID 这类确定性规则排。

打破平局必须用确定性规则。各节点独立排,必须得到同一个结果,所以只能用消息里自带、人人看得到的字段。「谁先到算谁前面」依赖本地观察,各节点会排出不同结果。

一步一步看

目标:看各节点用 Lamport 时钟加发送方 ID,怎样各自排出同一个全序。

  1. P₁ 一次本地事件,LC 从 0 到 1;发送 m₁,LC 到 2,附在 m₁ 上。

  2. P₂ 同样一次本地事件再发送 m₂,m₂ 也带着 2。

  3. P₃ 收到 m₁,按接收规则 max(0, 2) + 1,LC 变成 3。

    Lamport 时钟逐事件表格:P₁ 本地事件 LC 从 0 到 1、发送 m₁ 到 2;P₂ 同样到 2 发送 m₂;P₃ 收到带 2 的 m₁,按 max(0, 2) + 1 变成 3,这一格被标出

  4. m₁ 和 m₂ 的 LC 都是 2,平局。按发送方 ID,P₁ 小于 P₂,m₁ 排第一。

    Lamport 排全序表格:m₁ 和 m₂ 的 LC 都是 2,发送方分别是 P₁ 和 P₂,按 ID 打破平局,m₁ 排第 1 被标出,m₂ 排第 2

怎么算

排序键 = (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。三个候选序列:

  1. A C B D:全体相同;A 在 B 前。合法。

  2. A C D B:全体相同;A 仍在 B 前。合法。

  3. C B A D:全体相同;可 B 跑到了 A 前面,违反 FIFO。

    验证 FIFO TOB 的两步表格:A C B D 和 A C D B 全体相同且 A 在 B 前,合法;C B A D 全体相同但 B 跑到 A 前,违反 FIFO,这一格被标出

只有 P₁ 发了不止一条,C、D 各自的发送方只发一条,FIFO 那一步不用查它们。

怎么判断

  1. 把各进程的交付序列并排,逐位比较,有一位不同就违反全序。
  2. 列出发了多条消息的发送方。
  3. 对每个这样的发送方,抽出它的消息,看在序列中的先后是否和发送先后一致。
  4. 两步都过,才是 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 的两步验证。最后回查两个最容易错的地方:以为全序规定了某个特定顺序、以为平局可以按到达先后排。

必背

  1. Total order 只要求「所有人一致」,不要求「哪个顺序才对」
  2. 全序广播是复制状态机和区块链账本的必需品:同样的初态 + 同样的命令序列 = 同样的终态
  3. FIFO TOB 两种实现:sequencer(单 leader 定序,有单点)和 Lamport clock(逻辑时间戳 + 确定性打破平局)
  4. Lamport 时钟三条规则:本地事件/发送时 LC++;发送附带 LC;接收时 LC ← max(本地, 收到) + 1;平局按 sender ID 等确定性规则排
  5. 标量时钟能排全序但丢并发信息,向量时钟能判因果但排不出唯一全序
  6. 验证 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 的两条消息次序对吗?

解答
  1. 每个进程都按 A、C、B、D 交付。
  2. 全序成立:三个进程排列相同。
  3. FIFO 成立:P1 的 A 在 B 前,中间插了 C 不影响。C 和 D 的发送方各只发一条,不用查。
  4. 换成 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 加一,再附上):

  1. A:P1 的 LC 从 0 到 1,A 带 1。
  2. B:P1 的 LC 从 1 到 2,B 带 2。
  3. C:P2 的 LC 从 0 到 1,C 带 1。
  4. 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 放弃确定性换规模;再把本讲所有广播放到一张强弱图上,看全序和因果序为什么互不包含、全序为什么和共识等价。

下一讲 →
L03b-4 L03b-4 交付顺序(四):gossip,以及各档广播的强弱

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