分布式计算课程知识点总结

一、知识点

进程：程序运行起来之后成为进程

线程：进程内的执行流，负责实际执行代码

进程是运行中的程序实例，线程是进程内部具体执行任务的单元

同一进程中可以存在多个线程

并发（Concurrency）：多个任务在同一时间段内均有所推进（同时只能运行一个任务）（单核CPU）

并行（Parallelism）：多个任务在同一时刻真正同时执行（多核CPU）

并行是并发的一种特殊情形，并发不一定并行

Go中的并发：goroutine

竞争条件：程序的执行结果依赖于线程调度的相对时序，而某些时序会导致错误的结果

n = n + 1 问题（三步）

原子性：一个操作要么完整执行，要么完全不执行，执行过程不可被中断或观察到中间状态

临界区（critical section）：不能被多个线程同时执行的一段代码

临界区是需要受到保护的关键代码段

竞态条件经常发生在临界区没有被正确保护的时候

互斥：同一时刻最多允许一个线程进入临界区执行

互斥作用：防止多个线程同时修改同一份共享状态，从而保证数据的一致性

锁是实现互斥最常见的机制

锁的作用：确保共享状态不被同时破坏

互斥锁（Mutex）

可并发的部分尽量并发，需要保护的部分必须互斥

• 线程 → 操作系统调度的最小执行单位

• 进程 → 资源分配的基本单位

• 并发 → 多线程在同一时间段内交替推进

• 共享内存 → 线程间协作方便，但存在相互干扰的风险

• race condition →执行顺序的差异导致结果不一致（问题）

• critical section→ 需要保护的关键代码段（地方）

• atomicity → 操作若不可分割，则不会出现中间状态被观察的问题

• mutual exclusion → 同一时刻仅允许一个线程执行临界区

• lock → 实现互斥最常见的机制

• 并发不等于并行：并行 ⊂ 并发

• 共享内存在提供通信便利的同时，也引入了竞争风险

• 锁的目的不是提升性能，而是首先保证正确性

同步：控制执行顺序，让某些步骤必须「先发生」

忙等：一个线程（或 goroutine）在等待某个条件满足时，不释放 CPU，而是一直在那里反复检查条件，做“无用功”

条件同步：一个执行流等待某个条件成立，另一个执行流在条件成立后通知它继续

Python的GIL：同一时刻只允许一个线程执行 Python 字节码

Channel：一根带类型的通信管道，可以发送数据、接收数据，顺便完成同步

无缓冲 Channel：

ch := make(chan int)

发送和接受必须同时准备好，否则阻塞（发送和接受需要放在两个不同的goroutine里面，一个负责发；一个负责接受（两个goroutine））

无缓冲 channel 的发送操作，必须要有另一个 goroutine 在同时接收，否则发送方会永远卡住

有缓冲 Channel：

ch := make(chan int , 3 )

发送完毕后，别忘了 close(chan)

WaitGroup 相当于计数器，作用：等一组goroutine全都结束

Waitgroup 的 Add必须在启动 goroutine 之前调用

Channel：收发消息 + 同步；WaitGroup：计数器，等待任务完成

Select：同时等好几个 channel，谁先准备好就执行谁

Select + timeout，timeout的作用：防卡死

Select + default，default 的作用：让 select 变成非阻塞的

并发使多个任务得以同时推进；共享内存使它们容易相互干扰；锁通过互斥机制保护临界区，确保共享状态的一致性

三类并发bug：1）Data Race；2）DeadLock；3）Goroutine泄露

检查 data race

go run-racemain.go

如何解决data race问题：加Mutex以及WaitGroup

无缓冲channel有一个goroutine发送，没有goroutine同时接收 —— 会导致死锁

无缓冲通道的接收操作没有对应的发送操作 —— 导致 Goroutine泄露

RPC：远程调用

分布式系统：多台计算机通过网络相连，一起完成某件事

网络分层

Socket（操作系统 提供的网络接口）：Socket 是操作系统暴露给应用程序的网络 API（接口）

而RPC 就是在 Socket 上面再加一层，让你“像调用本地函数一样”调用远程函数

RPC：Remote Procedure Call（远程过程调用）：让调用远程函数看起来像调用本地函数一样。

RPC 的设计目标：透明性

RPC要解决的三大问题：

RPC的异构性问题，解决方法：Interface Description Language：接口描述语言（IDL）

接口描述语言（IDL）：核心：Marshal（序列化）

结构化数据→字节流（把内存中的数据结构变成平台无关的字节流）

UnMarshal（反序列化 ）：把字节流变回内存中的数据结构

Server stub实际上有两个部分：

• Dispatcher（分发器）：收到请求后，确定调用哪个函数
• Skeleton（骨架）：unmarshal参数 → 调用函数 →marshal返回值

GO的RPC方法签名规则：

func (t *T) MethodName(args T1, reply *T2) error

RPC概念：本地代码调用另一台服务器上的函数 / 方法，像调用本地函数一样

同步RPC缺点：调用方会堵塞

异步RPC：调用方不会堵塞，结果不会立即拿到

异步方式：1）goroutine + channel；2）client.go

• Worker是 RPCclient（主动要任务、主动报告）

• Coordinator是 RPCserver（分配任务、收报告）

RPC可能出错的环节：

解决方法：

At-Least-Once：策略内容：Client 等待一段时间，没收到回复就重发请求。重复几次还没回复就返回错误。

适用场景：操作为只读；操作为幂等；应用层能自己处理重复

At-Most-Once：策略内容：Client 给每个请求附带一个唯一 ID（xid）。Server 记录已经处理过的 xid。收到重复的 xid → 返回缓存的结果，不重新执行。

故障类型（都会导致：timeout / no reply）

处理上述故障：

Maybe Semantics（也许语义）发一次，等一会，没结果就判断为报错

At-Least-Once（至少一次）：Client 等待一段时间，没收到回复就重发请求。重复几次还没回复就返回错误。

At-Most-Once（最多一次）：Client 给每个请求附带一个唯一 ID（xid）。Server 记录已经处理过的 xid。收到重复的 xid → 返回缓存的结果，不重新执行。

At Most Once解决了：因为重传导致的重复执行

物理时钟同步：让多台机器的时钟尽量保持一致

Cristian 算法，核心思想：测量网络来回花了多久，然后估算出更准确的时间

Cristian算法的前提假设：请求去程和回复回程的网络延迟大致相等

工程上实际常运用的是：NTP协议—— 解决物理时钟同步问题

Lamport的关键：先不要执着于真实几点几分几秒，先抓住真正重要的顺序关系（happens before）

Lamport Clock 的规则：

• 规则1：本地事件：每个进程维护自己的本地计数器 Ci。在每个本地事件发生前：Ci = Ci + 1
• 规则2：发送消息：发送消息时，先给发送事件打时间戳，再把当前时钟值一起放进消息里。
• 规则3：接收消息：收到消息时：Cj = max(Cj, C(m)) + 1

Lamport Clock 保证了：如果 a → b，那么 C(a) < C(b)，反过来不保证

Lamport Clock不能判断两个事件是否真的有因果关系，适合用来构造一个一致的事件排序

Total Order的作用：让系统里所有节点都按同一顺序处理事件

Total Order的局限性：系统人为选出一个统一顺序。但它不等于这个顺序就是物理世界里的真实先后。

Lamport Clock 只能告诉你"顺序"，不能告诉你"因果"

向量时钟（Vector Clock）：能判断因果关系

MapReduce大致流程：

• 将输入切分为多个独立分片
• 各分片由独立的map任务并行处理
• 中间结果经过shuffle后由reduce任务聚合

MapReduce 的核心逻辑：把超大的整体数据，切成很多份小数据块，分给多台机器同时并行计算，最后再汇总结果

Map（分治计算）→ Shuffle（分拣转运）→ Reduce（汇总合并）

每个 map worker 在执行完 map 任务后，把中间结果分成R 份（R = reduce 任务数量）

关键：同一个 key 的所有值必须落入同一个分区

reduce 在 shuffle 过程中拉取完自己分区的数据后，在执行聚合操作前，先要对中间数据进行排序（升序排序）

每个 reduce 任务：

1. 接收属于自己分区的所有中间数据

2. 排序、分组

3. 调用reduce函数

4. 输出最终结果

coordinator：1.任务调度；2.状态维护；3.元信息转发

coordinator 为每个任务维护三个状态：

中间文件位置由 coordinator 统一管理

coordinator 转发的是文件位置，不是文件内容。

调度目标：最大化资源利用效率

任务粒度：任务数量应 > worker 数量

coordinator超时检测（故障检测）

• 周期性向 worker 发送探测请求

• 超过规定时间没收到响应 → 将该 worker 标记为 failed

coordinator 检测到故障后的第一步

1. 把该 worker 上in-progress状态的任务退回到idle状态

2. 更新 worker 状态记录，将其重新放入待调度队列

3. 重新分配给别人，由其他 worker 重新执行，从而确保作业继续向前推进

为什么 map 完成的结果也会丢？

• map 中间结果写的是本地磁

• worker 一挂，本地磁盘就访问不了了

为什么 reduce 完成的结果不丢？

• reduce 输出写的是全局文件系统（GFS/HDFS）

• worker 挂了，文件还在，其他节点依然可以访问

如何防止读到半成品文件？临时文件 + 原子提交

Locality（数据本地性）：优先把 map 任务调度到存有该数据副本的 worker 上

分区 Partition函数：默认：hash(key) % R，把 key 均匀分配到各个 reduce

每个 reduce 分区内，系统保证：中间 key/value 按 key升序处理

Combiner（本地预聚合）在 map 端先做一次局部聚合，减少 shuffle 的数据量。

• 数据流：map → shuffle → reduce

• 状态机：idle → in-progress → completed

• 容错：超时检测 + 任务重试 + 临时文件 + 原子重命名

• 优化：locality + combiner + backup task

分布式存储的两大基本技术：

为什么需要复制（为什么需要多副本）？避免机器挂了导致数据不可用（相当于备份一份）

复制 = 同一份数据存到多个节点

单主复制最简单，一致性最容易保证；多主复制和无主复制能提高可用性，但一致性更难

什么是 KV store？即Key → Value 的映射

四种常见的存储类型：关系型数据库 SQL，文档型数据库，列式存储，图数据库

什么是一致性？每个操作看起来在某个瞬间生效，这个瞬间落在调用和返回之间。

一致性的唯一关键约束：real-time order

两个操作时间上有重叠 → 生效顺序可以任意排。
一个操作在另一个结束之前开始 → 也没有强制顺序。
只有先结束 vs 后开始，才有强制先后。

实现 Linearizability（线性一致性） 的常见方式：

单机：mutex 串行化

多机并发：

• 选出一个 leader 处理所有写操作（单主复制）
• 写操作同步复制到多数副本后再返回
• 读操作也从 leader 处或者 副本 中确认最新值

Sequential Consistency（顺序一致性）就是比 Linearizability 稍弱的一种一致性保证。

Sequential Consistency 只关心每个进程自己的操作顺序，不关心不同进程之间的先后关系。

Linearizability：按真实时间顺序执行。
Sequential Consistency：按每个进程自己的逻辑顺序执行，不同进程之间可以重排。

Causal Consistency（因果一致性）：有因果关系的操作，必须按相同顺序被看到。

这个比刚刚的 sequential 还要弱一点

Eventual Consistency（最终一致性）：没有新更新的话，最终所有副本会收敛到相同状态。不保证什么时候收敛，中间状态可以不一致。

最弱的一致性

Mutex的作用：使请求串行化

确保在同一个时刻，只有一个请求能进入临界区（修改 map 的代码）。其他请求都在门外排队。

单机：Map + Mutex = Linearizability。

Clerk = client 端的代理

最简单的复制方案：Primary-Backup

核心思想：

• 指定一个节点为primary（主），其余为backup（备）

• 所有写请求发给 primary

• Primary 负责把数据同步给 backup

• 读请求可以只从 primary 读

State Machine Replication（状态机复制）

核心思路：如果两台机器从相同初始状态出发，按相同顺序执行相同的操作，它们的最终状态一定相同。

Failover（故障转移）

如何检测到故障？

Primary 和 backup 之间定期发心跳。如果 backup 连续 N 次没收到心跳 → 判定 primary 故障。

什么是split brain？

系统中同时存在两个（或多个）节点认为自己是 primary

Split Brain 导致：两个 primary 各自接收不同的写

导致 Split Brain 的根本原因：

网络分区（Network Partition）：节点之间的通信中断，但节点本身还在正常运行。

如何解决 split brain：多数派

共识（Consensus）三条性质：

解释：FLP 认为，在完全异步的模型中，能保证 Safety（不能选出两个 leader）；但不能保证最终一定能达成共识（liveness）

在纯异步模型里，不能无条件保证 termination

决定之前，先看多数派那里有没有历史。

Paxos，核心思想：如果某个值已经可能被选中，后面的人必须继续用它。如果还没有任何值被选中，proposer 才能用自己的值。

Paxos 的角色分工：

Paxos 里提案不是单独一个值，而是一对：(proposal number, value) = (n, v)

Paxos 的两个阶段

• Phase 1（Prepare）：先问多数派，有没有接受过历史值

• Phase 2（Accept）：再把一个值写入多数派

Acceptor 会记住自己 promise 过的最大编号。如果已经 promise 过更大的n，就不能再接受更小的n。

为什么Paxos是安全的

任意两个多数派（quorum）必有交集，交集节点保留了历史信息，保证了已选中的值不会被覆盖。

Paxos 本身不关心 value 代表什么。只保证“大家投出同一个结果”

Basic Paxos的问题：每决定一个位置，都跑完整 Phase 1 + Phase 2。

Multi-Paxos：稳定时只走 Accept

广播协议谱系：best-effort → reliable → FIFO → causal → total order（弱到强）

FLP：纯异步系统中 consensus 无法保证终止；实践用部分同步解决

Paxos 两阶段：prepare 探测历史并拿 promise，accept 把值写入多数派

Multi-Paxos：稳定 leader 期间复用 Phase 1 的结果，后续操作直接复制

二、判断习题

• 判断：并发就是多个线程同时执行（错）

• 并发强调“多个任务均在推进”，并不要求每一时刻都真正同时执行

• 判断：只有一行代码，就不会有并发问题（错）

  单行高级语言代码在底层通常对应多个机器指令

• 判断：使用更多线程，程序一定更快（错）

  多线程频繁竞争同一把锁时，等待开销可能使程序比单线程还慢

• 判断：使用 Go 或 goroutine，共享数据自动是安全的（错）

  只要多个 goroutine 访问共享数据，且没有适当的同步机制，race condition 依然存在

• goroutine 启多了就一定快（错）

  goroutine 轻量，但不是零成本，有调度开销，有同步开销，有内存开

• channel 不会死锁（错）

  也会，例如：没人收，硬发；没人发，硬收；大家都在等对方

并发程序的核心矛盾是：多条执行流需要同时推进，但它们可能访问同一份共享状态

• 时间戳更小，就一定更早发生（错）

  原因：因为不同机器的表，本来就可能没对齐（物理时钟）

• 如果本地时钟偏快，不能直接往回调时间。而是：1）调整走表速度：让钟走得慢一点或快一点，慢慢追上；2）保证单调递增：时间只往前走，不往后退。从而保证monotonicity（单调性）

• Lamport clock不保证：C(a) < C(b) 不代表 a → b

三、解答习题

1、Raft

题目：简述 Raft 系统中，当 Follower（农民）收不到 Leader 的心跳信号，到有新的 Leader 产生的具体过程。（如果同时有多个 Follower 成为候选人，会发生什么？）

1）具体过程

Leader 会周期性向所有 Follower 发送心跳表示自己活着。

当 Follower 等待时间超过了自己的超时时间（每个 Follower 的超时时间不同），先到达超时时间的 Follower 会将自己变成 Candidate 同时将自己的 term +1，然后向所有其他节点发送投票请求，并先给自己投一票。

其他节点在收到投票请求后，如果请求方 term 比自己小则拒绝投票；如果 term 比自己打，则更新自己的 term 并回应投票。

Candidate 收到所有投票结果后，如果 总票数 > 所有节点数的一半，Candidate 成为新的 Leader。如果没有，则重新开始选举过程。

2）如果同时有多个 Follower 成为候选人，会发生什么？

多个 Candidate 同时向其他节点发起投票，但是每个节点只能投一票，所以可能导致这一轮没有任何一个 Candidate 成为 Leader，导致这一轮选举失败，再次开始新一轮的选举，term +1，每个节点再等待自己随机的超时时间

2、MapReduce词频统计（python代码）

• Map：把一篇文章拆成单词，每个单词输出(word, "1")

• Reduce：把同一个单词的所有"1"加起来，得到总次数

1）Map 函数

def Map(key: str, value: str): value = value.lower() # ① 全部转成小写 ans = [] for w in re.findall(r'[a-z]+', value): # ② 用正则提取所有单词 ans.append((w, '1')) # ③ 每个单词输出 (word, "1") return ans

2）Reduce函数

def Reduce(key: str, values: list): result = 0 for v in values: result += int(v) # 把所有 "1" 加起来 return result

3、MapReduce 的基本流程

1）输入

Master 将输入数据切成很多 split

Master 维护所有 map / reduce worker 的状态，哪个 map worker 空闲，就给他一个 split 去处理，有限给本地的 worker

2）Map

Map worker 收到数据切片，读取 split 内容，调用用户定义的 map 函数

map 函数生成 中间（key , value）对

将中间结果写入 map worker 的本地磁盘

3）Shuffle

map worker 完成后，中间结果按分区函数分为 R 份

reduce worker 从各个 map worker 处拉取属于自己分区的数据

4）Reduce

Reduce worker 对拉回来的数据进行归并排序，并调用 reduce 函数

将结果写入分布式文件系统（GFS）

5）输出

补充：MapReduce失败会发生什么

• Map worker 挂了：他已经完成的 map 任务也要重做
  • 因为 map 生成的中间结果存在这个 worker 的本地磁盘上，机器挂了数据就没了
• Reduce worker挂了：他已经完成的 reduce 任务通常不用重做
  • 因为 reduce 输出结果写道分布式系统中，都访问得到

4、RPC的基本流程（10步）

两台机器：Client 和 Server

1、Client 调用client stub代理函数

2、Client stub序列化参数，转化为字节流

3、Client machine 通过网络将消息发给 Server machine

4、Server OS 接收到消息，将消息传给 Server stub

5、Server stub反序列化，将字节流解析出函数名和参数；分发（根据函数名决定调用哪个函数）

6-7、Server stub 传递参数给 server process 并在 Server 处算出结果值

8、Server stub 将这个结果值序列化打包为字节流，然后传给 Server OS

9-10、返回值通过网络传给 Client OS 然后 Client stub 反序列化解析返回值给到 Client process

5、Paxos两阶段

阶段一：

1）Proposer 选一个唯一递增的提案号n（比之前所有编号都大）

2）向所有 Acceptor 发送Prepare(n)

3）Acceptor 如果没见过更大的编号，就回复Promise（承诺）

阶段二：

1）Proposer 发送Accept(n, v)给所有 Acceptor

2）Acceptor 如果没有承诺过更大的编号，就接受这个 proposal

3）多数派接受 → 值被选定（Chosen）