← COMP5567 全部讲次
L02a · 第 2 周

L02a 分布式系统是什么:少了三样东西,只剩发消息

从单机少掉的三样东西讲起,分清并行和分布式、分布式和去中心化,再学会按消息条数给分布式算法算账。

一句话版

分布式系统是一组各自独立的机器:每台有自己的表、自己的内存,谁都可能单独坏掉,彼此只能靠发消息合作。这一页讲清它比单机少了哪三样东西,它和「并行」「去中心化」差在哪,以及为什么它的算法要数消息条数。

这是第 2 讲的第一页,后面五页都建立在这里的三个「没有」之上。

先认识这几个词

词 全称 / 读法 一句人话
进程 / 节点 process / node 网络里的一台机器,本课两个词混用
全局物理时钟 global physical clock 所有机器共用、读数一致的一块表
共享内存 shared memory 好几个处理器都能直接读写的同一块内存
独立失败 independent failure 一台坏了,其余照常跑,也不会立刻知道
并行系统 parallel system 多个处理器一起算,目标是算得快
去中心化 decentralized 控制权分散,没有谁说了算
消息复杂度 message complexity 一个分布式算法总共要发多少条消息

一个类比:跨时区的项目群

三个人分在三个时区,合做一个项目。每人手机上的时间都差几分钟,谁也看不见别人电脑里的文件,想知道对方做到哪了,只能在群里发消息问。有人半天不说话,你不知道他是睡了、断网了,还是在埋头干活。

这个群对得上这一页的大部分内容:

  • 三部手机时间不一致:没有全局物理时钟。
  • 看不到别人的文件,只能发消息:没有共享内存。
  • 有人悄无声息掉线:各自独立失败。
  • 群里有没有一个「组长」说了算:中心化还是去中心化。
  • 发一条通知要让几个人看到、要来回几轮:消息复杂度。

类比在哪里失效:

  • 群聊背后有服务器统一给消息排顺序,本课的网络里没有这样的角色,顺序得由节点自己商量。
  • 群里的人会主动说「我下线了」,本课的机器坏了就是坏了,不会通知任何人。

从零讲起

1. 六个属性和其中三个「没有」

它解决什么问题

写分布式算法之前,先得知道手里少了哪些单机上理所当然的便利。少了什么,就得自己补什么。课件给分布式系统列了六个属性,前三条说的都是「没有什么」,后面整门课的难题基本都从这三条长出来。

直觉

想象把一台电脑拆成三台,用网线连起来。拆开之后,原来那块统一的表变成三块各走各的表;原来大家都能摸到的内存变成三块各自的内存;原来「电脑坏了就全坏」变成「坏一台、另外两台还在跑,而且不知道它坏了」。

一步一步看

目标:看一台电脑拆成三台之后,少了哪三样单机上理所当然的东西。

  1. 先看单机:一个时钟、一块内存,所有程序读到的时间和数据都一样,坏了就整台一起坏。

  2. 拆成三台 A、B、C:三块表读数不同,A 说 10:00,B 说 10:03,C 说 09:58。这就是没有全局物理时钟。

  3. 三台各有自己的内存,A 想知道 B 的数据,只能发消息去问。这就是没有全局共享内存。

  4. C 突然坏了,A 和 B 还在跑,可它们不会立刻知道 C 已经不在。这就是自治且独立失败。

    左边一台机器只有一个时钟和一块内存;右边三台机器 A、B、C 各有一块时间不同的表和自己的内存,彼此只靠消息箭头联系,C 被青绿叉划掉表示它独立失败,A 和 B 不会立刻知道

剩下三条属性说的是「有什么」:机器可以五花八门(异构),对用户表现为一个整体(对外一致),很多事同时在发生(并发)。

怎么判断

拿到一个系统,逐条问自己三个问题:

  • 各台机器读到的时间一样吗?不一样,就没有全局物理时钟。
  • 一台机器能直接读另一台的内存吗?不能,就没有共享内存。
  • 坏一台,其余会跟着停吗?不会,就是独立失败。

三条都答「没有」,就是本课说的分布式系统。三个「没有」各自逼出一样技术:

没有什么 直接后果 逼出的技术
全局物理时钟 两台机器的时间戳不能直接比大小 逻辑时钟(本讲后半)
全局共享内存 只能发消息,消息会延迟、丢失、乱序 消息传递协议
统一的失败 一台坏了别人不知道 容错

意思是:你在后面每一讲看到的新机制,几乎都能追溯到这张表里的某一行。

常见误解

以为给每台机器装上准确的网络对时,就有了全局时钟

对时只能让各台的表尽量接近,误差永远在。两件事相隔很短时,靠两块表的读数分不出谁先谁后。本课的处理办法是干脆不用物理时间排先后,改用逻辑时钟,见本讲的 L02b-1 到 L02b-3。

以为「对外一致」说的是各台机器数据一致

课件的「对外一致」(coherent)是说用户看到的是一个整体系统,看不到背后有几台机器。各台数据是否一致是另一件事,后面 CAP 那页专门讲。

试一下

一家公司把数据库放在两个机房,两个机房之间用专线连接。说出它满足的三个「没有」各体现在哪里。

两个机房的服务器时钟读数不同,没有全局物理时钟;一个机房的程序读不到另一个机房的内存,只能通过专线发请求,没有共享内存;一个机房断电,另一个机房还在运行,而且要等发现对方没回应才知道,这是独立失败。

2. 并行系统和分布式系统

它解决什么问题

「好多处理器一起干活」既可以叫并行,也可以叫分布式,两个词经常被混用。课件把它们分开,因为两者追求的目标不同,设计时取舍的方向也就不同。

直觉

并行像一个厨房里四个厨师围着同一张案板切菜,案板上的东西谁都能直接拿,目标是出菜快。分布式像四家分店各有各的厨房,靠电话互通有无,一家停电了其他照常营业,目标是不会一停全停。

一步一步看

目标:对照两张图的内存和目标,看出并行系统求快、分布式系统求坏一部分还能跑。

  1. 看左边的并行系统:四个 CPU 连到同一块共享内存,谁写进去的数据,别人马上能读到。

  2. 它追求的是高性能,把一个大计算拆开同时算,算得更快。

  3. 看右边的分布式系统:每个 CPU 下面挂着自己的本地内存,彼此之间只有网络。

  4. 它追求的是容忍部分失败,坏掉一部分,剩下的还能继续提供服务。

    左边并行系统四个 CPU 连到同一块共享内存,目标是高性能;右边分布式系统三个 CPU 各带一块本地内存,本地内存用青绿描边,彼此只通过网络虚线发消息,目标是容忍部分失败

怎么判断

看两个地方:

看什么 并行系统 分布式系统
首要目标 高性能 容忍部分失败
内存 处理器直接访问共享内存 每个处理器只有本地内存
处理器之间怎么交流 读写同一块内存 发消息

意思是:判断时先看内存是不是共享的,再看系统主要担心的是「慢」还是「坏」。

常见误解

以为分布式只是「更大的并行」

两者的难点不一样。并行系统的处理器通常一起生一起死,难点在怎么拆任务;分布式系统的机器各自会坏,难点在一部分坏了以后其余怎么继续对外给出正确结果。

试一下

一台服务器里插了八块显卡一起训练模型,显卡之间直接读写同一块显存池。它更接近并行还是分布式?

更接近并行:目标是算得快,处理器访问的是共享的存储。要是改成八台各自独立的机器通过网络交换梯度,而且要求一台掉线后训练还能继续,就更接近分布式。

3. 中心化、分布式与去中心化

它解决什么问题

「分布式」和「去中心化」在区块链语境里常被当成同义词。课件专门把两个词拆开:一个说机器放在哪,一个说谁有权做决定。分清了,才能理解区块链到底比普通分布式系统多做了什么。

直觉

一家连锁店有一百家分店,开在一百个城市,这是分布式;但所有决定都由总部拍板,所以它不去中心化。一个没有总部、各家店投票决定菜单的联盟,才是去中心化的。

一步一步看

目标:分清三种拓扑,看出去中心化系统一定是分布式的,反过来不成立。

  1. 中心化:所有节点都连向一台主节点,由它说了算,它一挂,全体停摆。

  2. 分布式:机器分散在多处,可以有一个协调者,也可以分层组织。搜索引擎和分布式数据库属于这一类。

  3. 去中心化:节点彼此对等,没有中心,没有单点故障。区块链和 P2P 网络属于这一类。

  4. 对比后两者:去中心化系统的机器也分散在多处,所以它一定也是分布式的;反过来,分布式系统可以有中心。

    三个拓扑并排:左边中心化是星形,一台主节点连着六台;中间分布式是一棵有协调者的分层树,例子是搜索引擎和分布式数据库;右边去中心化是六个对等节点互相连线,连线用青绿描出,例子是区块链和 P2P 网络

怎么判断

问两个问题,顺序不能反:

  1. 机器是不是分散在多处、靠网络协作?是 → 分布式。
  2. 有没有某台机器或某个机构对全局说了算?没有 → 去中心化。

意思是:distributed 说的是位置的分布,decentralized 说的是控制权的分布。所有去中心化系统都是分布式的,反之不成立。

常见误解

以为机器越多就越去中心化

一万台机器听一台主节点调度,仍然是中心化控制下的分布式系统。判断去中心化只看「谁有权做决定」,和机器台数无关。

试一下

一个云盘服务把文件切块存在全球多个数据中心,所有权限由公司的一台账号服务器统一管理。它分布式吗?去中心化吗?

分布式:数据分散在多个数据中心,靠网络协作。不去中心化:权限由公司统一管理,账号服务器说了算。

4. 按消息条数给分布式算法算账

它解决什么问题

单机算法比快慢,数的是执行了多少条指令。分布式算法的大部分时间花在等网络上:发出去、等对方收到、再等回复。指令数在这里不是瓶颈,所以要换一把尺子来量它的代价。

直觉

开一次跨城市的电话会议,真正耗时的是每个人轮流发言、等别人听完回应,每人脑子里想了多少不重要。会议要来回几轮、每轮要对几个人说话,决定了会开多久。

一步一步看

目标:用四个节点 N1 到 N4,数两种发消息方式各要多少条,看节点变多时谁涨得更快。

  1. 一对多:N1 把一条消息分别发给其余 3 个节点,每人一条,共 3 条。

    四个节点 N1 到 N4,N1 向 N2、N3、N4 各发一条青绿箭头,右边写着 n − 1 = 4 − 1 = 3 条消息,消息数随 n 线性增长

  2. 全互发:每个节点都把自己的消息发给其余 3 个节点,4 个节点各发 3 条,共 12 条。

    四个节点两两之间都有来回两条青绿箭头,右边写着 n × (n − 1) = 4 × 3 = 12 条消息,消息数随 n 平方增长

  3. 节点数翻倍到 8 时,一对多变成 7 条,全互发变成 56 条,差距越拉越大。

怎么算

n 个节点时:

  • 一对多:消息数 = n − 1。意思是:除了自己,每个节点收一条,随 n 线性增长,记作 O(n)。
  • 全互发:消息数 = n × (n − 1)。意思是:每个节点都要给其余所有节点各发一条,随 n 平方增长,记作 O(n²)。

后面讲共识协议时,比较两个协议谁更省,主要就是这样数一轮要发多少条消息。

常见误解

以为分布式算法也该按指令条数比较快慢

顺序算法一个操作接一个执行,瓶颈在指令;分布式算法各节点并发执行、靠消息通信,代价集中在网络往返上。所以课件规定用消息条数衡量复杂度。

试一下

5 个节点,先由一个节点把提案发给其余所有节点,再由每个节点把自己的投票发给其余所有节点。一共多少条消息?

第一轮一对多:5 − 1 = 4 条。第二轮全互发:5 × 4 = 20 条。合计 4 + 20 = 24 条。

把它们串起来

这一页从一台电脑被拆成几台讲起。拆开之后少了三样东西:统一的表、共享的内存、一起坏一起好的命运。三个「没有」是本门课所有难题的根。

少了共享内存,协作只能靠消息,所以这类系统和追求速度、共享内存的并行系统走向了不同的方向,它首先要的是坏掉一部分还能工作。机器分散在多处只说明它是分布式的,控制权有没有集中在某一处,决定了它是否去中心化,区块链属于后一种。

也正因为一切都靠消息,分布式算法的账要按消息条数算。下一页接着问一个更难的问题:消息要多久才能到?对这件事的不同假设,就是三种同步模型。

课件里的坑

  • [术语约定] 本课的 process 指网络里的一台计算机,和 node 同义(p.8)。它和操作系统课里的「进程」含义不同,看时空图时每条横线就是一台机器。
  • [容易记反] p.3 六个属性里只有 Coherent(对外一致)是「有什么」里的目标,系统内部再乱,对用户也要像一台机器(例如搜索引擎对客户端就像一台服务器)。它是要达成的目标,不能当作前提条件来用。
  • [常考辨析] p.6 的「所有去中心化系统都是分布式的」是最典型的辨析题,答题要点出「前者说控制权,后者说位置」,并各举一例。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写三个「没有」和它们各自逼出的技术;再把下面的「变式题」做一遍;最后回查两个最容易错的地方:把去中心化和分布式当同义词、拿指令条数比较分布式算法。三步做完再往下看答案。

必背

  1. 六属性里的三个「没有」:无全局物理时钟、无全局共享内存、处理器自治且独立失败,分布式算法的困难全从这里来。
  2. 六个属性:无全局物理时钟、自治且独立失败、无全局共享内存、异构、对外一致、并发。
  3. 并行系统求高性能、处理器共享内存;分布式系统求容忍部分失败、每个处理器只有本地内存。
  4. 所有去中心化系统都是分布式的,反之不成立;distributed 说位置的分布,decentralized 说控制权的分布。
  5. 分布式算法的复杂度用消息条数衡量,不是指令条数。

课件例题

本讲课件没有例题(指这一页覆盖的 p.1–7,算题类例题都在讲逻辑时钟的几页)。这部分通常考概念辨析:给一个系统,问它是并行还是分布式、是否去中心化;或者默写六个属性、说出三个「没有」各引出了什么。

完整例题

题面(自编):判断下面三个系统各属于中心化、分布式(有中心)、去中心化中的哪一类,并说明依据。

① 一台学校选课服务器,所有学生都连它。② 一个搜索引擎,几千台机器分布在全球,由总控节点分配爬取任务。③ 一条公链,任何人都能运行节点,节点之间对等。

  1. ① 只有一台服务器说了算,它挂了全体选不了课 → 中心化。
  2. ② 机器分散在全球,靠网络协作,满足分布式;但有总控节点分配任务,控制权集中 → 分布式,不去中心化。
  3. ③ 节点分散在各处,满足分布式;节点对等、没有谁说了算 → 去中心化。
  4. 检查一句话规则:③ 去中心化,它同时也是分布式的;② 是分布式,但不去中心化。和「所有去中心化系统都是分布式的,反之不成立」一致。

变式题(先自己做)

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

  1. 「我们有 100 台服务器,所以系统是去中心化的。」
  2. 「分布式系统里,只要每台机器都装了高精度时钟,就可以直接用时间戳判断两件事谁先发生。」
  3. 「比较两个分布式算法时,应该看谁执行的 CPU 指令少。」
提示

第 1 题想想去中心化看的是机器数量还是控制权。第 2 题回到三个「没有」的第一条。第 3 题想想分布式算法的时间主要花在哪。

判分点与答案

判分点:① 第 1 题要说出去中心化看控制权;② 第 2 题要说出时钟之间仍有误差、本课没有全局物理时钟;③ 第 3 题要说出用消息条数衡量。

  1. 错。机器多只说明它是分布式的。若 100 台都听一台主节点调度,控制权仍然集中,不算去中心化。
  2. 错。各台时钟再准也有误差,没有一块所有机器共用的表。两件事相隔很近时,时间戳比不出可靠的先后,所以本讲后半要引入逻辑时钟。
  3. 错。分布式算法的代价集中在网络往返上,复杂度按消息条数衡量。

闪卡自测

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

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

2. 并行系统和分布式系统的首要目标各是什么?内存上有什么区别?

并行系统求高性能,处理器直接访问共享内存;分布式系统求容忍部分失败,每个处理器只有本地内存(p.4)。

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

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

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

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

5. n 个节点全互发一轮,消息数是多少?

n × (n − 1),每个节点给其余 n − 1 个节点各发一条,随 n 平方增长。

下一讲

L02a-2 同步模型与 FLP:消息到底要多久才能到?对这件事的三种假设,决定了超时能不能用来判断一台机器挂没挂。

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

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