← COMP5567 全部讲次
L02a-2 · 第 2 周

L02a-2 同步模型与 FLP:消息要多久才能到

从「对方是挂了还是只是慢」这个问题讲起,一帧一帧看同步、异步、部分同步三种假设下超时还能不能判故障,以及 FLP 划下的那条边界。

一句话版

你给另一台机器发了消息,一直没等到回复:它是挂了,还是只是慢?能不能回答这个问题,取决于你事先假设网络延迟有多守规矩。这一页讲三种假设,以及在最宽松的那种假设下,共识问题碰到的天花板 FLP。

上一页讲了分布式系统的三个「没有」,见 L02a。这一页只追问其中一件事:消息要多久才能到。

先认识这几个词

词 全称 / 读法 一句人话
同步模型 synchrony model 对「消息最慢多久到」做的假设
Δ 读「delta」 消息延迟的上界:最多等这么久
超时 timeout 等满约定的时间还没回音,就下判断
共识 consensus 一群机器对同一个值达成一致
FLP Fischer、Lynch、Paterson 三位作者的首字母 纯异步下只要可能崩一台,确定性共识就保证不全
GST Global Stabilization Time,全局稳定时间 从这一刻起网络开始守规矩,一定会到,但不知道何时

一个类比:等外卖

点完外卖,平台说「30 分钟内送达,超时赔付」。这时过了 30 分钟还没到,你可以确定出问题了,这是同步模型。

换一家小店,老板只说「做好就送」,不给任何时间。等了一小时,你没法判断是骑手出了事,还是只是路上堵。这是异步模型。

第三家说「午高峰过后保证 30 分钟内送达」,但不告诉你高峰几点结束。高峰期间超时不算数,高峰过后超时就能下结论。这是部分同步,那个「高峰结束的时刻」就是 GST。

类比在哪里失效:

  • 外卖到了你一眼就看见,分布式系统里收到消息的只是一台机器,它还得再发消息告诉别人,这一来一回又是延迟。
  • 外卖迟到你只损失一顿饭;共识协议判错一次「对方挂了」,可能让两台机器各自以为自己是领导者,后果严重得多。

从零讲起

1. 同步模型是一种假设

它解决什么问题

上一页说过,机器会各自独立失败,而且别人不会立刻知道。要容错,就得先判断「它挂了没有」。唯一的线索是它有没有按时回消息,可「按时」是多久?这个问题没有标准答案,只能由设计者事先做一个假设。同步模型就是这个假设。

直觉

延迟在分布式系统里几乎躲不掉,来源有两类:系统固有的异步性,以及机器五花八门带来的异构性。慢链路、慢处理器都会拖延消息。设计协议前,你得先说清楚:我假设这些拖延最多有多长。

一步一步看

目标:分清三种延迟假设,看它们差在延迟有没有上界、上界从什么时候生效。

  1. 同步:假设任何消息都在一个已知的固定时间 Δ 内送达。

  2. 异步:不做任何假设,消息可以晚到任意久。

  3. 部分同步:假设网络在某个时刻 GST 之后变得守规矩,GST 之前不保证。

  4. 把三条时间轴放在一起,差别只在延迟有没有上界、上界从什么时候开始生效。

    三条时间轴对比:同步模型的消息在已知的 Δ 内必到,等了 Δ 还没消息就能判定对方崩溃;异步模型不设上界,消息多晚到都合法;部分同步模型存在一个一定会到但时刻未知的 GST,GST 之后上界是 x + Δ,超时判故障重新可用

怎么判断

模型 消息延迟上界 能否用超时判故障 典型协议
同步 已知固定上界 Δ 能 理论模型为主
异步 无上界 不能 受 FLP 限制
部分同步 GST 之后有界 GST 之后能 PBFT、HotStuff、Raft

意思是:拿到一道题,先找题目对延迟说了什么。给了固定上界就是同步,什么都没说就是异步,说「最终会稳定」就是部分同步。

常见误解

以为同步模型描述的是网络的真实情况

同步模型是设计者选的假设,不是对网络的测量结果。选哪种,决定了协议能做什么,也决定了假设不成立时协议会怎样出错。所以课件说它是设计分布式协议的第一个决策点。

把「同步执行」和「同步模型」混为一谈

两个词撞了名。「同步执行 / 异步执行」说的是任务是否按顺序一个接一个执行;同步模型说的是消息延迟有没有上界。本讲只讲后者。

试一下

一道题写着「网络可能任意延迟,但最终会恢复正常」,它在假设哪种模型?

部分同步。「最终会恢复正常」对应 GST 一定会到;「之前可能任意延迟」对应 GST 之前没有上界。

2. 同步模型:等满 Δ 就能下结论

它解决什么问题

在同步模型下,「它挂了还是只是慢」有确定的答案。这一节看清它为什么能回答,以及这份确定性有什么前提。

直觉

既然每条消息最慢也会在 Δ 内到,心跳过去最多 Δ,回复回来最多 Δ,那么等满一来一回还没收到,就只剩一种解释:对方出了故障。慢的可能性被假设排除了。

一步一步看

目标:看同步模型下,A 为什么等满 2Δ 就能确定 B 是活着还是崩了。

A 给 B 发一条心跳,问「你还在吗」,然后开始计时。这里假设 B 处理心跳的时间可以忽略,一来一回最多 2Δ。

  1. B 活着:B 收到心跳立刻回复,回复在 2Δ 之内回到 A,A 判定 B 活着。

    A 和 B 两条时间线,上方标出最多等 2Δ 的时间窗。A 发心跳给 B,B 的青绿回复箭头在窗口结束前回到 A,所以 A 判定 B 活着

  2. B 崩了:心跳到了 B,B 已经停止工作,不会回复。A 等到窗口右边界还没收到,判定 B 崩溃。

    A 给 B 发心跳后 B 崩溃,用叉标出;2Δ 窗口的右边界描成青绿,到点没有回复,因为同步模型保证每条消息 Δ 内必到,A 可以确定 B 崩溃

  3. 两种情况在窗口结束时就分开了,A 不用再等。

怎么算

设 A 在时刻 t 发出心跳,单程延迟上界是 Δ,B 的处理时间忽略不计:

  • 截止时刻 = t + Δ + Δ = t + 2Δ。意思是:心跳过去最多 Δ,回复回来最多 Δ,过了这个时刻还没收到回复,就判定对方崩溃。
  • 要让这个判断可靠,消息延迟、对方处理消息的时间、心跳的间隔都得有已知上界,任何一项没有上界,等多久都可能误判。

课件举的同步系统例子是片上系统和嵌入式系统,它们的线路短、环境可控,延迟上界真能保证。

常见误解

以为互联网上的服务也可以按同步模型设计

同步是理想情况,实践中消息有时会被延迟。互联网上的链路拥塞、机器卡顿都没有可靠的上界,按同步模型设计的协议一旦碰到超过 Δ 的延迟,就会把活着的机器当成死的。

试一下

同步模型下 Δ = 5,B 的处理时间忽略不计。A 在时刻 3 发心跳,到时刻 11 还没收到回复,能判定 B 崩了吗?

不能。截止时刻是 3 + 2 × 5 = 13,时刻 11 还在窗口里,回复可能正在路上。要等到时刻 13 仍没收到,才能判定。

3. 异步模型与 FLP

它解决什么问题

如果什么延迟假设都不做,协议就不怕网络有多糟,听上去最稳妥。这一节看这份稳妥的代价:有些问题在这种假设下根本没法解决,FLP 定理给出了最著名的一条。

从哪来(补充)

FLP 定理出自 Michael J. Fischer、Nancy Lynch、Michael S. Paterson 三人 1985 年发表在 Journal of the ACM 上的论文《Impossibility of Distributed Consensus with One Faulty Process》,名字就是三人姓氏的首字母。这篇论文后来获得了 Dijkstra 奖。

出处:Wikipedia: Consensus (computer science)

直觉

异步模型下消息可以晚到任意久。一台机器崩了和一台机器很慢,从外面看完全一样:都是没回音。你永远等不到一个可以下结论的时刻。

一步一步看

目标:看异步模型下,A 为什么在任何时刻都分不清 B 是崩了还是只是慢。

  1. 情况一:A 发心跳给 B,B 收到后崩溃了,不会再回复。

  2. 情况二:A 发心跳给 B,B 活着,可它的回复在路上走了很久。

  3. 在任何一个时刻,A 能看到的都只是「还没收到」,两种情况对 A 来说一模一样。

    上下两行时空图:上面 B 收到心跳后崩溃,下面 B 活着但回复走了很久才到。两行里都有一条青绿竖线表示 A 的此刻,那一刻 A 都还没收到回复,看到的完全相同,所以无法靠超时判断 B 是否崩溃

  4. 把这个困境放到共识上:一群机器要商量出同一个值,只要其中一台可能崩溃,大家就分不清它是崩了还是慢。等它,可能永远等下去;不等它,它又可能带着不同的意见回来。

怎么判断

FLP 的完整陈述:在异步环境中,只要有一个进程可能崩溃,确定性算法就不能在所有允许的执行里同时保证安全性和终止。

意思是:三个条件同时满足才触发它。

条件 去掉它会怎样
纯异步,延迟无上界 加时序假设,走部分同步模型,PBFT 和 HotStuff 走这条
确定性算法 加随机性,用随机化共识协议
同时保证安全与终止 弱化保证,比特币的概率最终性走这条

读题时看见「异步」「确定性」「有一台可能崩」三个词同时出现,就该想到 FLP。

常见误解

把 FLP 读成「共识做不到」

FLP 不等于算法不存在,也不等于每次都失败。Paxos、Raft、PBFT 这些协议现实中都在跑,它们靠表里的三条路之一绕开了 FLP。FLP 说的是:在那三个条件下,没有哪个确定性算法能在所有可能的执行里两头都保住。

以为异步模型下设计的算法没用

为异步系统设计的算法非常健壮,因为它不依赖任何时序假设,什么网络状况下都对。代价是很多问题在这个模型下无解,所以实际协议常在「健壮」和「可解」之间折中。

试一下

有人说:「我的共识协议在异步网络里,就算有一台机器崩溃,也总能在有限时间内让所有正常机器达成一致,而且绝不出错。协议里没有用随机数。」这个说法和什么结论冲突?

和 FLP 冲突。条件是异步、确定性(没用随机数)、可能崩一台,而他声称同时保证了安全(绝不出错)和终止(有限时间内达成)。FLP 说这在所有允许的执行里做不到。

4. 部分同步与 GST

它解决什么问题

同步太理想,异步又让共识无解。实际的网络大多时候表现良好,偶尔会乱一阵。部分同步模型把这种情况写成形式化定义,让协议既不依赖不现实的假设,又能绕开 FLP。

从哪来(补充)

部分同步模型来自 Cynthia Dwork、Nancy Lynch、Larry Stockmeyer 1988 年发表在 Journal of the ACM 的论文《Consensus in the Presence of Partial Synchrony》,初版见 1984 年的 PODC 会议。

出处:Decentralized Thoughts: Synchrony, Asynchrony and Partial synchrony,论文全文见 MIT 存档

直觉

想象网络有一个「稳定下来」的时刻 GST。在它之前,网络可以任意乱;在它之后,消息都守 Δ 的规矩。GST 一定会到,可没人知道它是什么时候。

一步一步看

目标:看 GST 前后发出的两条消息,谁的送达期限协议用得上、谁的用不上。

取 Δ = 2,假设 GST 落在时刻 10(协议本身并不知道这个值),看两条消息。

  1. 第一条消息在时刻 3 发出,这时 GST 还没到。它的送达期限是 2 + max(3, 10) = 12,也就是 GST 之后 Δ 内送达。

  2. 第二条消息在时刻 15 发出,这时 GST 已经过了。它的送达期限是 2 + max(15, 10) = 17,就是发出后 Δ 内送达。

  3. 对第一条消息,期限取决于 GST,而协议不知道 GST,所以它等于没有可用的期限。对第二条,期限只取决于自己的发出时刻。

    一条从 0 到 20 的时间轴,GST 在 10 处用青绿竖线标出,Δ 取 2。第一条消息在 3 发出,期限是 Δ 加 max(3,10) 等于 12;第二条消息在 15 发出,期限是 Δ 加 max(15,10) 等于 17,也就是发出后 Δ 内送达

怎么算

形式定义:存在一个已知的有限时间界 Δ 和一个特殊事件 GST。GST 最终一定发生,时刻未知。任何在时刻 x 发出的消息,必须在 Δ + max(x, GST) 之前送达。

分两种情况代入:

  • x < GST 时,max(x, GST) = GST,期限 = Δ + GST。意思是:GST 未知,这个期限对协议没有用处,消息可以任意慢。
  • x ≥ GST 时,max(x, GST) = x,期限 = x + Δ。意思是:发出后 Δ 内必到,超时判故障重新可靠。

这个模型是现代 BFT 协议的标准假设。它让安全性在任何时候都保证,即使网络一直乱也不会出现两个矛盾的提交;活性只在 GST 之后保证,网络恢复后系统才保证能往前推进。

常见误解

以为部分同步模型下,等满 Δ 没回复就能判定对方崩溃

只有 GST 之后发出的消息才保证 Δ 内到达。GST 之前对方可能只是慢,这时按超时判它崩溃会误判。协议不知道 GST 是否已过,所以超时只能当作「可能出事了」的信号,不能用来断定故障,也不能让安全性依赖它。

试一下

Δ = 3,GST = 20。一条消息在时刻 8 发出,另一条在时刻 25 发出,各自的送达期限是多少?

第一条:3 + max(8, 20) = 3 + 20 = 23,GST 之前发出,期限由 GST 决定。第二条:3 + max(25, 20) = 3 + 25 = 28,GST 之后发出,发出后 Δ 内送达。

把它们串起来

上一页留下的「各自独立失败」带出一个问题:对方没回音,是挂了还是慢?这一页的答案是,看你假设了什么。

同步模型给了一个已知上界 Δ,等满 Δ 就能下结论,代价是这个假设在真实网络里常常不成立。异步模型什么都不假设,算法因此最健壮,可挂和慢永远分不清,FLP 定理据此证明:纯异步、确定性、可能崩一台,共识就保不全安全和终止。

部分同步把两者折中:GST 之前按异步对待,之后按同步对待。协议让安全性无条件成立,把活性推迟到 GST 之后,这就是绕开 FLP 的标准做法。下一页把「安全性」「活性」这两个词正式定义,再看网络断开时一致和可用的取舍。

课件里的坑

  • [说法过强] p.13 把 FLP 写成「不存在能解决共识问题的分布式算法」。准确说法要带上限定:纯异步、允许一个崩溃时,确定性共识不能在所有允许执行中同时保证安全与终止。答题时写课件原话可以,但要补一句它没有说「共识做不到」。
  • [前提没写全] p.12 说同步模型下「超时即可判定故障」。可靠的超时判定除了消息延迟有上界,还需要处理时间、心跳间隔也有已知上界。
  • [同名不同义] p.11 的「同步模型」和别处的「同步执行 / 异步执行」是两回事,前者说延迟上界,后者说任务是否顺序执行。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写三种同步模型的延迟假设和部分同步的形式定义;再把下面的「变式题」做一遍;最后回查两个最容易错的地方:把 FLP 读成「共识做不到」、在 GST 之前就用超时判故障。三步做完再往下看答案。

必背

  1. 同步模型是系统的时序假设,不是事实;选哪种假设是设计分布式协议的第一个决策点。
  2. 三种同步模型:同步有已知上界 Δ、异步无上界、部分同步在 GST 之后有界;可靠超时判定需消息、处理与心跳间隔的已知上界;GST 前超时可能误判。
  3. FLP:纯异步系统中允许一个崩溃时,确定性共识不能在所有允许执行中同时保证安全与终止;不等于算法不存在或每次都失败。
  4. 绕开 FLP 的三条路:加时序假设(部分同步,PBFT、HotStuff 走这条)、加随机性、弱化保证(比特币的概率最终性)。
  5. 部分同步的形式定义:存在 Δ 和 GST,GST 最终一定发生但时刻未知,时刻 x 发出的消息须在 Δ + max(x, GST) 之前送达。
  6. 安全性在任何时候都保证、活性只在 GST 之后保证,这是绕开 FLP 的标准做法。

课件例题

本讲课件没有例题(指这一页覆盖的 p.11–14)。这部分通常考三类题:给一个场景问属于哪种同步模型、超时能不能判故障;完整陈述 FLP 并说出它没有说什么;写出部分同步的形式定义,说明 GST 前后的延迟约束。

完整例题

这一题把部分同步的形式定义在 GST 前后各代一次,题面公式来自课件,代入过程是自己做的。

把 Δ + max(x, GST) 在 GST 前后各代一次

  1. 取一条在时刻 x 发出的消息,部分同步模型要求它在 Δ + max(x, GST) 之前送达。
  2. GST 之前发出,即 x < GST:max(x, GST) = GST,上界变成 Δ + GST。GST 本身未知,所以这个界等于没有约束,消息可以任意慢。
  3. GST 之后发出,即 x ≥ GST:max(x, GST) = x,上界变成 x + Δ,也就是发出后 Δ 内必须到,这时超时判故障才重新可用。
  4. 一句话结论:GST 一定会到来,但你不知道它什么时候到来。安全性不依赖这个假设、任何时候都成立;活性依赖它,所以只能承诺「最终」。

变式题(先自己做)

自编情境:下面三种说法各对不对,错在哪里?

  1. 「部分同步模型下,只要等满 Δ 还没收到心跳,就能断定对方崩溃。」
  2. 「FLP 证明了异步网络里不存在任何共识算法,所以 Paxos 在异步网络里一次都成功不了。」
  3. 「异步模型的算法不依赖任何时序假设,所以它能解决的问题最多。」
提示

第 1 题想想这次心跳是在 GST 之前还是之后发的。第 2 题回到 FLP 的原文:它限制的是哪一类算法、要同时保证哪两件事。第 3 题想想健壮和可解是不是一回事。

判分点与答案

判分点:① 第 1 题要点出 GST 前超时可能误判;② 第 2 题要说出「确定性」「同时保证安全与终止」两处限定;③ 第 3 题要说出异步模型下很多问题无解。

  1. 错。只有 GST 之后发出的消息才保证 Δ 内到达。GST 之前对方可能只是慢,这时据超时判它崩溃会误判。
  2. 错。FLP 说的是确定性共识不能在所有允许执行中同时保证安全与终止,不等于算法不存在,也不等于每次都失败。Paxos 始终保证安全,只是在网络很差时可能一直推进不下去。
  3. 错。异步算法健壮,是因为它在什么网络下都对;可正因为假设最少,很多问题在异步模型下根本无解,共识就是一例。

闪卡自测

1. 同步模型说的是什么?为什么说它是设计协议的第一个决策点?

同步模型是系统的时序假设,关心网络延迟和处理器延迟(p.11)。选哪种假设决定了协议能做什么,以及假设不成立时会怎样出错。

2. 三种模型下,超时能不能用来判定节点故障?

同步模型能,等了 Δ 还没消息就能确定对方挂了;异步模型不能,因为延迟没有上界;部分同步模型在 GST 之后能(p.12–14)。

3. 完整陈述 FLP 定理。它没有说什么?

在异步环境中,只要有一个进程可能崩溃,就不存在能解决共识问题的分布式算法(p.13)。准确地说是确定性算法无法同时保证安全性和终止;它没有说「共识做不到」。

4. 绕开 FLP 的三条路是什么?各举一个例子。

加时序假设(部分同步,PBFT、HotStuff)、加随机性(随机化共识协议)、弱化保证(比特币的概率最终性)(p.13)。

5. 写出部分同步的形式定义。GST 前后消息延迟各受什么约束?

存在 Δ 和 GST,GST 最终会到但时刻未知,时刻 x 发出的消息在 Δ + max(x, GST) 前送达(p.14)。GST 前等于没有约束,GST 后延迟不超过 Δ。

6. 为什么「安全性永远保证、活性 GST 后保证」能绕开 FLP?

FLP 说异步下不能两者兼得。部分同步让安全性无条件成立,把活性推迟到网络变好之后,两件事不必在同一时段同时保证(p.14)。

下一讲

L02a-3 安全性、活性与 CAP:怎么说一个协议「对不对」,以及网络断成两半时,一致和可用只能保一个。

下一讲 →
L02a-3 L02a-3 安全性、活性与 CAP:怎么说一个协议「对」

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