L02 分布式系统：一个没有统一手表的跨时区群聊

一句话版

一组没有统一手表、也不共享内存的机器，靠互发消息把事情办成——这一讲给出干这件事需要的全部词汇。

一个类比：跨时区群聊

三个人在三个时区的群里讨论一件事。每人手机上的时间都不太准，谁也看不见别人的手机，信息只能靠发消息传。这时候「谁先说的」是个真问题：两条消息上的时间戳出自两块不同的表，比大小没有意义。

你唯一能百分之百确定的先后是引用关系——B 这句话里回应了 A 的话，B 就一定在 A 之后。顺引用链能追到的是先后，追不到的是「各说各的」，硬排顺序只能靠人为规定。群里还常有人半天不吭声，你分不清他是掉线还是在慢慢打字，等多久都不能下断言。

这个场景对得上本讲大半内容：手机时间各不准（没有全局物理时钟），只能发消息（没有共享内存），有人悄无声息掉线（自治且独立失败），引用链（happens-before），互不引用（并发），给消息编号（Lamport 时钟），每人记「我见过每个人的几条」（向量时钟）。

类比在哪里失效：群聊背后有一台服务器统一给消息定序，所以它分布式但不去中心化（p.5、p.6），而本课假设的网络里没有这台服务器，顺序得由节点自己协商。群聊里消息基本都会到，模型里的异步网络对送达时间不设任何上界（p.13）。「正在输入」这种带外提示在模型里也不存在——分不清慢和挂，正是后面所有难题的源头（p.4）。

概念卡

1. 三种同步模型与 FLP（Synchrony Models）

人话定义：同步模型是你对网络延迟做的时序假设，也是设计任何协议的第一个决策点。

例子：同步模型假设延迟有已知固定上界 Δ，典型场景是片上系统和嵌入式系统（p.12）；异步模型不设上界，为它设计的算法极其健壮，代价是很多问题根本无解（p.13）；部分同步假设存在有限时间界 Δ 和一个全局稳定时间 GST，GST 最终一定发生但时刻未知，时刻 x 发出的消息须在 Δ + max(x, GST) 前送达（p.14）。

差别只在延迟有没有上界：

常见误解

把 FLP 读成「共识做不到」→ 它说的是异步环境中只要有一个进程可能崩溃，确定性算法就无法同时保证安全性和活性，而 Paxos、Raft、PBFT 现实中都在跑。绕开它只有三条路：加时序假设（PBFT 与 HotStuff 走这条）、加随机性、弱化保证（比特币的概率最终性）（p.13）。还有一处同名不同义：p.9 的「同步执行 / 异步执行」说的是任务是否顺序执行，和 p.11–14 的同步模型是两回事。

2. happens-before 与两种逻辑时钟（Lamport Clock & Vector Clock）

人话定义：happens-before 是一个非自反的偏序关系，只有三条判定规则；Lamport 时钟用一个整数近似它，向量时钟用一个长度为 n 的向量精确刻画它。

例子：判定规则是同一进程内的先后、同一条消息的发送先于接收、以及传递性（p.16），实操就是沿时间轴和消息箭头「走路」，走得到是 →，互相走不到是并发。Lamport 四条规则：计数器初值 0、每个事件加 1、发消息带上当前值、收消息设为 Max(local, received) + 1（p.19）。向量时钟四步：初值 [0,0,0]、内部事件自己那一位加 1、发消息带整个向量、收消息先给自己那一位加 1 再逐位取较大值（p.22）。

把「走路」法画出来：

常见误解

看到 LC(a) < LC(b) 就反推 a → b → 时钟条件只是单向蕴含，两个事件完全可能并发（p.20）。附上进程 ID 只能打破平局造出一个人为的全序，判定并发这个局限它解决不了（p.21），这正是向量时钟出场的理由。向量时钟自身最常错的两处：接收的两步顺序记反或只做 max 忘了自增；发送时带走的是完整向量（p.22）。Lamport 是 O(1) 空间、判不了并发，向量时钟是 O(n) 空间、能判并发。

3. 正确性的两套语言：safety / liveness 与 CAP

人话定义：安全性是「坏事不会发生」，活性是「好事终将发生」；CAP 讨论分区发生时，线性一致性与所有非故障节点可用性之间的冲突。

例子：课件用临界区举例——两个线程不能同时处于临界区是安全性，每个线程最终都会进入临界区是活性（p.23）。CAP 那边：一致性指所有客户端同一时刻看到相同数据（无论连哪个节点），可用性指即使存在故障仍响应请求，分区容错指链路断开时仍能继续正确运行（p.24）。p.26 据此分类：CP 在分区时关掉不一致的节点使其不可用，AP 让所有节点保持可用但错误一侧可能返回旧数据，CA 一旦出现分区就做不到。

常见误解

真的去「三选二」→ p.26 明写「在分布式系统中，分区是无法避免的」，P 必选，真正的选择只在 C 和 A 之间；CA 也可描述假设无分区的分布式运行条件。把比特币称为 AP 只是课件类比，须限定操作和确认语义，不能把暂时收交易等同于最终确认；PBFT 类偏 CP，节点数不够就停下不出块。另一处误解是以为安全性够了就行 → 一个「永远不做任何决定」的协议绝对安全，却完全没有活性（p.23）。

把它们串起来

这一讲的因果链从 p.3 六属性里的三个「没有」开始——无全局物理时钟、无全局共享内存、处理器自治且独立失败。没有全局共享内存，所以协作只能靠发消息，于是分布式算法的复杂度度量换成了消息条数而不是指令条数（p.7）——后面 PBFT 的 O(n²)、HotStuff 的 O(n) 都是这么数出来的。没有全局物理时钟，所以时间必须重新定义，于是有了 happens-before 和它的两种实现。各自独立失败，所以要容错，而容错的前提是能判断「它是挂了还是只是慢」，这一判断又回过头来依赖你选的同步模型。

中间一段先把讨论对象拆细：进程就是一台机器，事件只有内部事件、消息发送、消息接收三类（p.8），全局快照叫割，不存在「接收在割内、发送在割外」这种消息的才是一致割（p.10）——从不一致割恢复，会出现「钱收到了但没人发过」的鬼状态。有了这套词汇才能谈顺序。

终点是两组正确性语言。safety 与 liveness 是描述协议做没做对的标准句式，CAP 把分区场景下的取舍摆明。两者在部分同步模型上合流：安全性任何时候都保证、活性只在 GST 之后保证，这就是绕开 FLP 的标准姿势。本讲在全课地图上的位置是「事件排序」这一环，下一讲的因果序广播会直接拿向量时钟来用。

课件里的坑

• 本讲课件未发现错误。

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——三种同步模型与 FLP 的边界、向量时钟收发两条规则、CAP 里 P 是必选；再把下面的「变式题」做一遍；最后回查两个最容易错的地方——看到 LC(a) < LC(b) 就反推因果、真的去「三选二」。三步做完再往下看答案。

必背

1. 六属性里的三个「没有」：无全局物理时钟、无全局共享内存、处理器自治且独立失败，分布式算法的困难全从这里来。
2. 所有去中心化系统都是分布式的，反之不成立；distributed 说位置的分布，decentralized 说控制权的分布。
3. 分布式算法的复杂度用消息条数衡量，不是指令条数。
4. 三种同步模型：同步有已知上界 Δ、异步无上界、部分同步在 GST 之后有界；可靠超时判定需消息、处理与心跳间隔的已知上界；GST 前超时可能误判。
5. FLP：纯异步系统中允许一个崩溃时，确定性共识不能在所有允许执行中同时保证安全与终止；不等于算法不存在或每次都失败。
6. Lamport 时钟收消息时取 Max(local, received) + 1；a → b ⟹ LC(a) < LC(b) 成立，反向不成立，因此判不出并发。
7. 向量时钟接收时先给自己那一位 +1 再逐位取 max；每位都 ≤ 且至少一位 < 为因果先后，有的位大有的位小为并发。
8. CAP：发生网络分区时，不能同时保证线性一致性 C 与所有非故障节点的可用性 A；CA 可在不发生分区的假设下讨论。

完整例题

「向量时钟是什么」开卷翻书就有，值得练的是给你一组向量现场判关系（我的判断，课程没公布题型）。这两问都是把课件的规则直接代进去。

(1) 逐位判定课件给的四组向量

1. 判定规则先写死：每一位都 ≤ 且至少一位严格 < ⟹ 前者 happens-before 后者；两个方向都不成立（有的位大、有的位小）⟹ 并发。
2. Case 1，(1,0,0) 与 (4,1,3)：逐位比 1 ≤ 4、0 ≤ 1、0 ≤ 3，且第 1 位 1 < 4 严格小 ⟹ a → m。
3. Case 2，(0,1,0) 与 (4,1,3)：0 ≤ 4、1 ≤ 1、0 ≤ 3，第 1 位严格小 ⟹ h → m。
4. Case 3，(2,2,0) 与 (4,1,3)：第 1 位 2 < 4、第 3 位 0 < 3，但第 2 位 2 > 1 ⟹ 有大有小 ⟹ i ‖ m 并发。
5. Case 4，(4,1,0) 与 (2,2,0)：第 1 位 4 > 2，第 2 位 1 < 2 ⟹ 有大有小 ⟹ 并发。
6. 反过来想 Lamport 为什么做不到：它把整个向量压成一个整数，压完之后「有的位大有的位小」这个信息就没了，只剩下两个数谁大谁小，而大小关系推不出因果（p.20）。

四组逐位比对摆在一起：

(2) 把 Δ + 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. (3,2,1) 与 (3,2,4)
2. (2,5,1) 与 (3,4,1)
3. (0,0,2) 与 (0,0,2)

提示

前两组照规则逐位比就行。第三组先别急着套「并发」的定义，想一想：两个不同的事件，有可能拿到一模一样的向量吗？

参考答案与自检（非官方评分标准）

自检要点：① 每一位都要比，只看第一位就下结论是主要失分方式；② 「有的位大、有的位小」才判并发；③ 第三组要答出”这是同一个事件”，直接套并发是陷阱。

1. 3 ≤ 3、2 ≤ 2、1 < 4，每位都 ≤ 且第 3 位严格小 ⟹ 前者 happens-before 后者。
2. 第 1 位 2 < 3，第 2 位 5 > 4 ⟹ 有大有小 ⟹ 并发。第 3 位相等不影响判定。
3. 两个向量完全相等。按字面套”两个方向都不严格成立”会判成并发，但这是陷阱：每发生一个事件，本地分量必定加一，所以不同事件不可能拥有相同的向量。相等只说明这是同一个事件的时间戳被写了两遍。

闪卡自测

1. 六个属性里哪三个是「没有什么」？各自逼出了什么技术手段？

没有全局物理时钟 → 逻辑时钟；处理器自治且各自独立失败 → 容错；没有全局共享内存 → 只能传消息，而消息会延迟、丢失、乱序（p.3）。

2. 「所有去中心化系统都是分布式的，但反之不然」，各举一例。

Google 搜索、分布式数据库是分布式但不去中心化，可能有中央协调者、架构可以是层级式的；区块链和 P2P 网络两者都是，节点互为对等、没有单点故障（p.5、p.6）。

3. 为什么分布式算法用消息数而不是指令数衡量复杂度？

顺序算法一个操作接一个执行，瓶颈在指令；分布式算法并发执行、靠消息传递通信，代价集中在网络往返上，所以复杂度度量是消息条数（p.7）。

4. 事件有哪几类？什么样的割是不一致的？

只有三类：内部事件、消息发送、消息接收（p.8）。某条消息的接收在割内而发送在割外，这个割就不一致——它记录了一个「收到了还没被发出的消息」的状态，现实中不可能存在；反过来「发了但还没收到」是合法的（p.10）。

5. 三种模型下，超时能不能用来判定节点故障？

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

6. 完整陈述 FLP 定理。它没有说什么？

在异步环境中，只要有一个进程可能崩溃，就不存在能解决共识问题的分布式算法（p.13）。它说的是确定性算法无法同时保证安全性和活性，没有说「共识做不到」——绕开的三条路是加时序假设、加随机性、弱化保证。

7. happens-before 的三条判定规则是什么？实操怎么判并发？

同一进程内 e 先于 f 执行、e 是消息 m 的发送而 f 是同一条 m 的接收、以及传递性（p.16）。实操是「走路」：沿本进程时间轴和消息箭头能走到就是 →，互相都走不到就是 ‖。

8. 写出 Lamport 时钟的四条规则。收消息时为什么不能只写 received + 1？

计数器初值 0；每发生一个事件加 1；发消息时带上当前值；收消息时设为 Max(local, received) + 1（p.19）。取 max 是为了保证接收事件的时间戳一定大于发送事件的时间戳，同时不能把本地已经走得更远的进度倒退回去。

9. 向量时钟接收事件的两步，顺序能不能反？发送时带走什么？

课件先自增再逐位 max；在标准向量时钟、无重置模型下，收到的自身分量不会超过本地，所以与先 max 再自增等价（p.22）。发送时带走的是完整向量，不是单个数。

10. 安全性和活性各自能不能被有限的执行片段证伪？CA 系统为什么在分布式环境下不存在？

安全性能——抓到一次坏事发生就破了；活性不能——等了很久不代表永远不会发生（p.23）。CA 要求一旦任意两节点间出现分区就得同时保住一致和可用，做不到，而分区在分布式系统中无法避免，所以所谓 CA 系统其实是单机系统或假定网络永不分区的系统（p.26）。

下一讲

下一讲把「节点之间怎么发消息」正式立成问题：先区分 receive 和 deliver 这两件常被混为一谈的事，再沿可靠性和顺序两条轴往上爬，其中的因果序广播会直接把本讲的向量时钟搬过去用。