L03a-1 可靠广播(一):收到和交付是两回事,可靠性分三级
从时空图的读法讲起,分清 send、receive、deliver,再一级一级看 best-effort、RB、URB 各保证什么、漏洞在哪、差别落在哪一个词上。
一句话版
一个节点想让所有节点都收到同一条消息,这件事叫广播。消息到了手里和消息交给应用是两步,两步之间可以先扣住,协议的全部本事都在这段时间差里。
这一页只回答一个问题:消息最终会不会被大家都交付。答案分三级,一级比一级多要一条保证。协议具体怎么写,留给下一页 L03a-2。
先认识这几个词
读之前最好先懂 happens-before(事件先后),见 L02b-1。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 进程 / 节点 | process / node | 网络里一台各自干活的机器,本讲两个词混用 |
| 时空图 | space-time diagram | 横线代表进程、箭头代表消息的示意图 |
| receive / deliver | 接收 / 交付 | 消息到手叫 receive,协议放行给应用叫 deliver |
| 正确进程 / 故障进程 | correct / faulty process | 全程不崩溃的叫正确进程,中途崩了的叫故障进程 |
| best-effort | 尽力而为广播 | 能送就送,送不到没人负责补 |
| RB | Reliable Broadcast,可靠广播 | 有正确进程交付,所有正确进程都交付 |
| URB | Uniform Reliable Broadcast,一致可靠广播 | 有任何进程交付,所有正确进程都交付 |
一个类比:楼下那间传达室
写字楼楼下有间传达室。快递员什么时候把信送到,由外面的世界决定,你插不上手。传达室什么时候把信放进你的信箱,由传达室的规矩决定。
两步之间有段时间差。传达室可以先把一封信扣在架子上,等另一封到了再一起放。协议的全部本事就在这段时间差里。
传达室的规矩可以一级级加严。最松的一档是能送就送,送不到算了。严一点的一档是只要有一个住户拿到了,就保证楼里所有还在的住户都能拿到。再严一档,哪怕拿到信的那个住户当天就搬走了,这条保证也照样成立。
类比在哪里失效:
- 传达室是一个中心,网络里每个节点自己就是自己的传达室。所以发送方也得先把消息发给自己,走和别人一样的交付流程。
- 楼里谁搬走了大家看得见,网络里节点崩了别人看不见。「正确进程」和「任何进程」这一字之差,正是 RB 和 URB 的全部区别。
- 楼里的信基本不会丢。网络里的消息会半路丢,best-effort 那一档对别人收不收得到没有任何承诺。
从零讲起
1. 先补一块:时空图怎么读(补充)
它解决什么问题
这一讲几乎每道题都给一张图,问谁交付了什么、违不违反某条性质。图读不懂,后面的性质再熟也答不出来。时空图就是把「谁在什么时候做了什么、消息从谁飞到谁」画在一张纸上的办法。
直觉
把每个进程想成一条从左往右流的时间河。河上的一个点是这个进程做的一件事,叫事件(event)。两条河之间的斜箭头是一条消息:箭尾是发出去的那一刻,箭头是到达的那一刻。
箭头是斜的,因为消息在网络上要走一段时间。箭头半路打叉,表示这份消息丢了。一条河在某处打叉、后面变成虚线,表示这个进程在那一刻崩溃,之后什么也不做。
一步一步看
目标:学会按横线、圆点、箭头的顺序读一张时空图,看出谁交付了 m。
-
先数横线:有几条横线就有几个进程,这张图里是 P、Q、R。
-
再看圆点:P 的线上先是 broadcast(m),后面是 deliver(m)。同一条线上越靠右越晚发生。
-
再看箭头:从 P 的广播点出发有两条斜箭头,一条落到 Q,一条落到 R。被标出的那条就是消息 m 在路上。
-
最后看落点之后:Q、R 收到 m 之后各自 deliver(m)。右侧一栏写着每个进程最后的状态。
怎么判断
拿到一张时空图,按这个顺序读:横线是谁 → 每条线上有哪些点、先后如何 → 哪些箭头到了、哪些打叉 → 哪条线中途打叉崩溃。
判断「某进程交付过 m 没有」,只看它自己那条线上有没有 deliver(m) 这个点。箭头到了只说明收到了,交付要另画一个点。
常见误解
以为同一条竖线上的点是「同时」发生的
不同进程之间没有共同的钟,图上上下对齐只是画的位置,不代表同一时刻。能确定先后的只有两种情况:同一条线上的左右,和一条箭头的两端(发出一定早于到达)。
试一下
一张图里 R 的线上没有 deliver(m) 的点,但有一条从 P 来的箭头落在 R 上。R 交付了 m 吗?
不能算交付。箭头落下只说明 R 收到(receive)了 m,交付要看 R 的线上有没有 deliver(m) 这个事件。下一个概念讲的就是这两者的差别。
2. send / receive / deliver 与那段时间差
它解决什么问题
如果消息一到就交给应用,协议就没有任何插手的余地:网络送什么顺序,应用就看到什么顺序;网络丢了谁,谁就看不到。把「到手」和「交给应用」拆成两步,协议才能在中间做事。
直觉
课件特意强调四个词各是一件事,每个词都不能混:
- broadcast:应用对协议说「把这条消息发给所有人」。
- send:协议真的往某条链路上塞一个包。
- receive:协议从网络收到一个包,还没给应用看。
- deliver:协议决定「现在可以让应用看到这条消息了」。
receive 的先后由网络决定,协议管不着。deliver 的先后由协议决定。协议手里唯一的工具是收到之后先扣住不交,扣住消息的地方叫缓冲区(buffer)。
一步一步看
目标:看网络打乱到达顺序后,协议怎样用 buffer 把交付顺序摆回来。
-
发送方 p₁ 先 broadcast 出 m₁,再 broadcast 出 m₂。
-
网络把顺序弄乱了:p₂ 先 receive 到 m₂,后 receive 到 m₁。
-
协议看到 m₂ 先到,但它想按发送的先后交付,于是把 m₂ 扣在 buffer 里。
-
m₁ 到了,先交付 m₁,再把 m₂ 从 buffer 放出来交付。
怎么判断
看一条性质约束的是谁,只问一句:它说的是 deliver 还是 receive?本讲后面所有性质,Validity、Agreement、No Duplication、No Creation、FIFO、Causal、Total,全部只约束 deliver。
再看发送方:它也要走一遍 deliver。课件对 deliver 的定义里写明,交付的对象包括发送方自己。否则「自己广播的自己一定交付」这句话在它身上没法说。
常见误解
把 receive 和 deliver 当同一件事
混了这两个词,后面的三个排序算法就全看不懂了。那三个算法只做一件事:把已经 receive 的消息暂时不 deliver,等条件满足再放。
以为发送方知道自己发了什么,可以跳过交付
发送方也得和别人一样走一遍 deliver。下一页的协议里,广播的第一步就是把消息发给自己,理由就在这里。
试一下
p₂ 先收到 m₂ 后收到 m₁,最后的交付顺序是 m₁、m₂。这一过程里 m₂ 在哪待过?
在 p₂ 的缓冲区里。它已经被 receive,但协议没有立刻 deliver,等 m₁ 交付之后才放出来。
3. 最弱一档:best-effort
它解决什么问题
先回答最低的要求:至少别乱来。消息不能重复交付,不能凭空捏造,正确的发送方自己要能交付。best-effort 就是满足这三条、别的一概不管的一档。
直觉
三条性质,每条一句话:
- 有效性(Validity):正确进程 p 广播 m,则 p 最终把 m 交付给自己。
- 不重复(No Duplication):每条消息只交付一次。
- 不捏造(No Creation):交付了一条声称来自 p 的消息,那它确实是 p 之前广播的。
它缺的是一致性(Agreement)。Validity 只管发送方自己,别人收不收得到,它一个字都没说。所以几个节点可以对「有没有 m」看法不一样。
一步一步看
目标:看 best-effort 的三条性质都没违反时,几个进程对「有没有 m」仍可以看法不一。
课件用两张时空图演示这种不一致,两张图失败的对象正好反过来。
-
第一种:P 广播 m 并交付给自己,发给 Q 的那份送到,Q 交付了。
-
发给 R 的那份半路丢了,R 什么也没收到。协议不补发,三个进程看法不一致。
-
第二种更极端:P 广播完立刻崩溃,自己都没来得及交付。
-
发给 Q 的那份丢了,发给 R 的那份送到,R 交付了 m。最后只有 R 有这条消息。
怎么判断
判断一个场景违不违反 best-effort,只查三条:
- 有没有正确的发送方最后没交付自己的消息?有就违反 Validity。
- 有没有谁把同一条消息交付了两次?有就违反 No Duplication。
- 有没有谁交付了一条没人广播过的消息?有就违反 No Creation。
三条都没有,就不违反。别人收没收到不在检查范围里。
常见误解
以为 Validity 保证所有人都收到
它只管正确的发送方自己。第二张图里的发送方崩了,它连自己交付都不受 Validity 约束,别人收没收到更没人负责。
把两张图记反
第一张是 Q 成功、R 失败,发送方自己交付了。第二张是 Q 失败、R 成功,发送方广播完就崩,自己没交付。
试一下
P 正确,广播 m 后自己交付了 m;Q 交付了 m 两次;R 没收到。违反 best-effort 吗?违反哪条?
违反,违反的是 No Duplication:Q 把同一条消息交付了两次。R 没收到不违反任何一条,best-effort 没有 Agreement。
4. 补上一致性:RB
它解决什么问题
best-effort 允许正确的节点之间看法不一。可靠广播(RB)补一条 Agreement,把正确进程之间拉齐:只要有一个正确进程交付了,所有正确进程都得交付。
直觉
RB 有四条性质,前面三条和 best-effort 一样,多出来的是:
Agreement:若 m 被某个正确进程交付,则每个正确进程都最终交付 m。
这句话有两个限定词要抠。前半句(前件)说的是「某个正确进程交付了」,如果只有故障进程交付过,这条性质不触发。后半句(后件)说的是「每个正确进程都交付」,对故障进程没有要求。
所以 RB 只在正确进程内部保证一致。故障进程崩之前知道什么,它不管。
一步一步看
目标:看只有故障进程交付过 m 时,Q、R 一直没有 m 为什么也不违反 RB。
课件用一张反例图说明 RB 的漏洞。
-
P 广播 m,先把 m 交付给自己。
-
发给 Q 和 R 的两份都半路丢了。
-
P 随后崩溃。
-
唯一交付过 m 的是 P,而 P 是故障进程。Agreement 的前件不成立,Q、R 一直没有 m 也不违反 RB。
怎么判断
判断 RB 的 Agreement 有没有被违反,按三步走:
- 圈出所有正确进程。
- 看有没有哪个正确进程交付了 m。没有,性质不触发,直接判不违反。
- 有的话,再看是不是每个正确进程都交付了 m。缺一个就违反。
常见误解
以为「P 交付了、别人没有」一定违反 RB
要先看 P 是不是正确进程。P 后来崩了,就是故障进程,它的交付不触发 Agreement。
以为这个漏洞无关紧要
交付是有外部后果的。P 在崩之前如果已经按 m 做了事,比如写了数据库、给用户回了执,系统就出现「有人按 m 行动过,但没人知道 m 存在」的状态。课件的说法是把消息带进了坟墓。
试一下
Q 是正确进程,交付了 m;P、R 也正确,但 R 永远没交付 m。违反 RB 吗?
违反。前件成立(正确进程 Q 交付了 m),后件要求每个正确进程都交付,R 是正确进程却没交付。
5. 把故障进程也算上:URB
它解决什么问题
RB 的漏洞来自前件只看正确进程。一致可靠广播(URB)只改一个词,把前件里的「正确进程」换成「任何进程」,交付完就崩的进程也会触发保证。
从哪来(补充)
best-effort、RB、URB 这一套「性质逐条叠加」的写法,常被追溯到 Vassos Hadzilacos 和 Sam Toueg 在 1994 年写的一份技术报告。报告题目是 A modular approach to the specification and implementation of fault-tolerant broadcasts,作者把广播按性质拆成一个个模块,各种广播由不同模块组合而成。
直觉
两句话放在一起对比:
- RB:正确进程交付 ⟹ 所有正确进程交付。
- URB:任何进程交付 ⟹ 所有正确进程交付。
只有前件变了,后件一个字没动。后件还是只要求正确进程交付,因为没法要求一个已经崩掉的进程再去做什么。Uniform 这个词的意思就是对所有进程一视同仁,不管它后来崩不崩。
一步一步看
目标:看同一个场景换成 URB 后,正确进程 Q、R 为什么必须交付 m。
把 RB 漏洞那个场景换成 URB 再走一遍。
-
P 广播 m,先交付给自己。按协议,进程总会交付自己广播的消息。
-
P 随后崩溃。崩之前那次交付已经发生,不能撤销。
-
代入 URB:任何进程交付过 m,前件成立。
-
所以正确进程 Q、R 都必须最终交付 m。图上多出来的就是这两次交付。
把 RB 和 URB 对这个场景的要求摆成表:
| 只有 P1 交付了 M 然后崩溃 | RB | URB |
|---|---|---|
| P2 交付 M? | 不要求 | 要求 |
| P3 交付 M? | 不要求 | 要求 |
怎么判断
判断 URB 的 Uniform Agreement,和 RB 只差第二步:
- 圈出所有正确进程。
- 看有没有任何进程(正确的、崩了的都算)交付了 m。没有,性质不触发。
- 有的话,看是不是每个正确进程都交付了 m。缺一个就违反。
常见误解
以为 URB 要求所有进程都交付
后件没变,崩溃的进程不在要求范围里。
以为广播出去的消息 URB 保证一定有人交付
不保证。URB 只承诺「有一个进程交付了,所有正确进程都交付」。如果谁都没交付,前件不成立,零交付也合法。下一页的四节点例子里就有这样的消息。
试一下
P 广播 m 后、交付前就崩了;Q 收到并交付了 m,随后也崩了;R 正确,还没收到 m。URB 下 R 必须交付 m 吗?
必须。Q 交付过 m,前件「任何进程交付」成立,R 是正确进程,必须最终交付。换成 RB 就不必须,因为交付过 m 的 Q 是故障进程。
把它们串起来
这一讲分两半:可靠性解决「消息会不会被交付」,顺序解决「按什么次序交付」。本页和下一页是前一半。
读题先读图。时空图上,进程是横线,消息是斜箭头,交付是线上的一个点。箭头到了只算收到,交付要另看。
起点是把 receive 和 deliver 分开。所有性质只约束 deliver,协议的本事全在「收到了先不交」。
在这个前提下,可靠性一级比一级多要一点。best-effort 只保证不重复、不捏造、正确的发送方自己交付。RB 加上 Agreement,把正确进程之间拉齐。URB 只改前件里的一个词,把交付完就崩的故障进程也算进来。
怎么用一个很短的协议实现 URB,留给 L03a-2。
课件里的坑
- [课件留白] 开头点名了四种消息顺序,包括 absolute order(按真实物理时间排序),但后面只展开了 FIFO / causal / total 三种。异步系统没有全局时钟,absolute order 实现不了,所以课件只提名字。
- [概念区分] best-effort 的两张图(p.7、p.8)失败对象是反过来的:p.7 是 Q 成功、R 失败;p.8 是 Q 失败、R 成功,且发送方 P 广播完就崩、自己都没交付。
- [概念区分] p.15 的第二步「P1 交付 M」来自 Validity:进程总是交付自己广播的消息。考题问「P1 明明崩了为什么算交付过」,答案就是这一步在崩之前已经合法发生。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写三条:send / receive / deliver 三个动作、三级可靠性各有哪几条性质、RB 和 URB 差在哪个词。再把下面的「变式题」做一遍。最后回查两个最容易错的地方:把 receive 和 deliver 当同一件事、以为 URB 要求所有进程都交付。
必背
- send / receive / deliver 是三件事,所有性质只约束 deliver;receive 由网络说了算,协议唯一的手段是收到后先扣住不交。
- 三级可靠性:best-effort = Validity + No Duplication + No Creation;Reliable 再加 Agreement;Uniform 把 Agreement 前件的「正确进程」换成「任何进程」。
- best-effort 缺 Agreement,节点之间可以出现不一致的世界观;Validity 只管发送方自己。
- RB 的漏洞:故障进程可以交付完就崩,把消息带进坟墓。
- URB 的 Agreement 后件不变,仍只要求正确进程交付;RB 和 URB 的全部差别在前件。
课件例题
例 1(课件 p.7):best-effort 下,P、Q 交付了而 R 没有
题面:三个进程 P、Q、R。P 执行 Broadcast(m) 并交付 m;发给 Q 的那份送到,Q 交付 m;发给 R 的那份标着 Delivery failed。图右侧写着 Inconsistent:P delivered、Q delivered、R failed。问:这违反 best-effort 吗?
提示
把 best-effort 的三条性质逐条代进去,看哪一条管得到 R。
解答
不违反。best-effort 只有 Validity、No Duplication、No Creation 三条:P 自己交付了 m,Validity 成立;没人重复交付、没人交付捏造的消息。它没有 Agreement,所以 R 没收到不算违规,结果就是三个节点对「有没有 m」看法不一致。
例 2(课件 p.8):发送方广播完就崩了
题面:P 执行 Broadcast(m) 后立刻崩溃,自己没有交付 m。发给 Q 的那份 Delivery failed,发给 R 的那份送到,R 交付了 m。问:发送方失败时会发生什么?
提示
先判断 P 是正确进程还是故障进程,再看 Validity 管不管得到它。
解答
出现不一致:R 交付了 m,P 和 Q 没有。这仍然不违反 best-effort。P 是故障进程,Validity 只约束正确进程广播的消息,所以 P 自己没交付也不算违规;Q 没收到同样没有性质去管。和例 1 对照,两张图失败的对象正好反过来。
例 3(课件 p.11):RB 下发送方交付完再崩
题面:P 执行 Broadcast(m),先交付给自己,之后崩溃。发给 Q 和 R 的两份都是 Delivery failed。图右侧:P delivered、Q failed、R failed。问:p 交付了 m 然后崩溃,会怎样?
提示
RB 的 Agreement 前件写的是「正确进程交付」。交付过 m 的是谁?它正确吗?
解答
发送方和接收方的状态不一致:P 交付过,Q、R 都没有。RB 的 Agreement 前件是「正确进程交付」,唯一交付过的 P 是故障进程,前件不成立,所以 RB 不被违反。这就是 RB 的漏洞:故障进程交付完就崩,把消息带进了坟墓。
例 4(课件 p.13):URB 下同一个场景该是什么样
题面:P 执行 Broadcast(m),交付给自己,之后崩溃。这次 Q 和 R 都画了 Deliver(p,m)。图下注明:p 既可以是正确进程,也可以是故障进程。问:为什么这张图里 Q、R 必须交付?
提示
和例 3 比,前件里换了哪个词?
解答
URB 的前件是「任何进程交付」。P 崩之前交付过 m,前件成立,所以所有正确进程 Q、R 都必须最终交付 m。和例 3 对照,图上只多了两个交付点,差别就是前件里「正确」换成「任何」这一个词。
例 5(课件 p.14–15):只有 P1 交付后崩溃,RB 和 URB 各要求什么
题面和逐步解法见下方「完整例题」。
提示
先分清谁正确、谁交付过,再分别代入两条 Agreement。
解答
RB 下 P2、P3 都不要求交付;URB 下 P2、P3 都必须最终交付。推导见完整例题。
完整例题
这题就是课件的 Concrete Example,课件还配了一张对照表。
题面:P1 广播 M;P1 交付 M 后崩溃,此时 P2、P3 都还没收到 M;P2、P3 是正确进程,仍在运行。问:在 RB 和 URB 下,P2、P3 是否必须交付 M?
- 先确认谁是正确进程:P1 崩了,是故障进程;P2、P3 是正确进程。
- 再确认谁交付过:只有 P1。按协议,进程总会交付自己广播的消息,所以 P1 崩之前交付了 M。
- 代入 RB 的 Agreement:「正确进程交付 ⟹ 所有正确进程交付」。交付过 M 的只有故障进程 P1,前件不成立,RB 不要求 P2、P3 交付。它们可能永远收不到 M,这是允许的。
- 代入 URB 的 Uniform Agreement:「任何进程交付 ⟹ 所有正确进程交付」。P1 交付过,前件成立,P2、P3 必须最终交付 M。
- 对照表:P2 交付 M?RB 不要求,URB 要求。P3 交付 M?RB 不要求,URB 要求。
变式题(先自己做)
自编情境:P1 广播 M 后、交付前就崩溃;P2 收到并交付了 M,随后也崩溃;P3 是正确进程,还没收到 M。在 best-effort、RB、URB 三级下,P3 是否必须交付 M?
提示
先列出谁是正确进程、谁交付过 M。再把三级的性质逐条代进去,注意 Validity 管的是谁、Agreement 前件写的是「正确」还是「任何」。
判分点与答案
判分点:① 指出 P1、P2 都是故障进程,只有 P3 正确;② best-effort 和 RB 都不要求,理由要落在 Validity 只管正确的发送方、RB 前件要求正确进程交付;③ URB 要求,理由是 P2 交付过且前件是任何进程。
- best-effort:不要求。Validity 只约束正确进程广播的消息,P1 是故障进程;也没有 Agreement。
- RB:不要求。交付过 M 的只有 P2,P2 是故障进程,前件不成立。
- URB:要求。P2 交付过 M,前件「任何进程交付」成立,正确进程 P3 必须最终交付 M。
闪卡自测
1. broadcast、send、receive、deliver 各是谁做的?哪些性质约束哪一个?
broadcast 是应用层向协议提的请求,send 是协议往链路塞包,receive 是协议收到包,deliver 是协议决定让应用看到(p.3)。所有性质只约束 deliver,receive 的顺序永远由网络决定。
2. 为什么发送方也要把消息交付给自己?
p.4 的 Deliver 定义明写包括交付给它自己。它必须走和别人一样的 deliver 流程,否则 Validity 这条性质在它身上没法陈述,这也是 URB 协议「先发给自己」的理由(p.4、p.16)。
3. best-effort 有哪三条性质?缺的那条带来什么后果?
Validity、No Duplication、No Creation(p.5)。缺 Agreement,所以节点之间可以出现不一致的世界观;而且 Validity 只管发送方自己,别人收不收得到没有承诺。
4. best-effort 的两张图,失败的对象有什么不同?
第一张是 Q 成功、R 失败;第二张是 Q 失败、R 成功,而且发送方 P 广播完就崩、自己都没交付(p.7、p.8)。
5. RB 和 URB 的差别到底在哪一个词上?RB 的漏洞是什么?
Agreement 的前件:RB 写「正确进程交付 ⟹ 所有正确进程交付」,URB 换成「任何进程交付 ⟹ 所有正确进程交付」,后件不变(p.12、p.14)。RB 的漏洞是故障进程可以交付完就崩,把消息带进坟墓(p.11)。
6. P1 广播 M、交付 M 后崩溃,P2、P3 正确且还没交付。RB 和 URB 下 P2、P3 必须交付 M 吗?
RB 下不必须:唯一交付过 M 的 P1 是故障进程,前件不成立。URB 下必须:P1 崩之前确实交付过 M,任何进程交付就触发(p.14、p.15)。
7. URB 要求崩溃的进程也交付吗?
不要求。后件仍是「所有正确进程交付」,崩溃的进程不在要求范围里(p.12)。
8. 广播出去的消息,URB 保证一定有人交付吗?
不保证。URB 只承诺「有一个进程交付了,所有正确进程都交付」;如果谁都没交付,前件不成立,零交付也合法(p.17)。
下一讲
L03a-2 接着讲 URB 协议本身:先发给自己、先转发再交付、用 MJ 去重,以及课件那道四节点时空图里哪些消息没人交付。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。