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

一、知识点进程程序运行起来之后成为进程线程进程内的执行流负责实际执行代码进程是运行中的程序实例线程是进程内部具体执行任务的单元同一进程中可以存在多个线程并发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一根带类型的通信管道可以发送数据、接收数据顺便完成同步无缓冲 Channelch : make(chan int)发送和接受必须同时准备好否则阻塞发送和接受需要放在两个不同的goroutine里面一个负责发一个负责接受两个goroutine无缓冲 channel 的发送操作必须要有另一个 goroutine 在同时接收否则发送方会永远卡住有缓冲 Channelch : make(chan int , 3 )发送完毕后别忘了 close(chan)WaitGroup 相当于计数器作用等一组goroutine全都结束Waitgroup 的 Add必须在启动 goroutine 之前调用Channel收发消息 同步WaitGroup计数器等待任务完成Select同时等好几个 channel谁先准备好就执行谁Select timeouttimeout的作用防卡死Select defaultdefault 的作用让 select 变成非阻塞的并发使多个任务得以同时推进共享内存使它们容易相互干扰锁通过互斥机制保护临界区确保共享状态的一致性三类并发bug1Data Race2DeadLock3Goroutine泄露Bug 类型一句话描述Data Race多人同时抢一块数据结果乱套Deadlock互相等对方大家一起卡死Goroutine 泄漏开了一堆 goroutine但忘了关内存越跑越大检查 data racego run-racemain.go如何解决data race问题加Mutex以及WaitGroup无缓冲channel有一个goroutine发送没有goroutine同时接收 —— 会导致死锁无缓冲通道的接收操作没有对应的发送操作 —— 导致 Goroutine泄露RPC远程调用分布式系统多台计算机通过网络相连一起完成某件事网络分层Socket操作系统 提供的网络接口Socket 是操作系统暴露给应用程序的网络 API接口而RPC 就是在 Socket 上面再加一层让你“像调用本地函数一样”调用远程函数RPCRemote Procedure Call远程过程调用让调用远程函数看起来像调用本地函数一样。RPC 的设计目标透明性RPC要解决的三大问题问题说明异构性两端语言、平台、数据格式可能不同故障网络丢包、服务宕机、超时性能远程调用比本地调用慢 1000 倍以上RPC的异构性问题解决方法Interface Description Language接口描述语言IDL接口描述语言IDL核心Marshal序列化结构化数据→字节流把内存中的数据结构变成平台无关的字节流UnMarshal反序列化 把字节流变回内存中的数据结构Server stub实际上有两个部分Dispatcher分发器收到请求后确定调用哪个函数Skeleton骨架unmarshal参数 → 调用函数 →marshal返回值GO的RPC方法签名规则func (t *T) MethodName(args T1, reply *T2) errorRPC概念本地代码调用另一台服务器上的函数 / 方法像调用本地函数一样同步RPC缺点调用方会堵塞异步RPC调用方不会堵塞结果不会立即拿到异步方式1goroutine channel2client.goWorker是 RPCclient主动要任务、主动报告Coordinator是 RPCserver分配任务、收报告RPC可能出错的环节解决方法At-Least-Once策略内容Client 等待一段时间没收到回复就重发请求。重复几次还没回复就返回错误。适用场景操作为只读操作为幂等应用层能自己处理重复At-Most-Once策略内容Client 给每个请求附带一个唯一 IDxid。Server 记录已经处理过的 xid。收到重复的 xid → 返回缓存的结果不重新执行。概念一句话解释RPC让远程调用看起来像本地调用stubClient/server 端代理负责 marshal/unmarshalIDL接口描述语言解决异构性透明性API 一样但行为不一样序列化(Marshal)结构化数据 → 字节流异构性两台机器不一样需要序列化来解决At-Least-Once没收到回复就重试可能重复执行At-Most-Once用唯一 ID 去重不重复执行Go net/rpc 局限不自动重试不告诉你失败原因故障类型都会导致timeout / no reply故障类型通俗解释特点Crash崩溃进程或机器直接挂了他不再继续执行之后也不再回复Omission遗漏消息丢了没送到两类1Request Lost2Reply LostDelay延迟消息太慢还没到延迟Partition分区网络断开两边都活着但互相联系不上集群没有整体挂掉但一部分节点彼此通信不了处理上述故障Maybe Semantics也许语义发一次等一会没结果就判断为报错At-Least-Once至少一次Client 等待一段时间没收到回复就重发请求。重复几次还没回复就返回错误。At-Most-Once最多一次Client 给每个请求附带一个唯一 IDxid。Server 记录已经处理过的 xid。收到重复的 xid → 返回缓存的结果不重新执行。At Most Once解决了因为重传导致的重复执行物理时钟同步让多台机器的时钟尽量保持一致Cristian 算法核心思想测量网络来回花了多久然后估算出更准确的时间Cristian算法的前提假设请求去程和回复回程的网络延迟大致相等工程上实际常运用的是NTP协议—— 解决物理时钟同步问题Lamport的关键先不要执着于真实几点几分几秒先抓住真正重要的顺序关系happens beforeLamport Clock 的规则规则1本地事件每个进程维护自己的本地计数器 Ci。在每个本地事件发生前Ci Ci 1规则2发送消息发送消息时先给发送事件打时间戳再把当前时钟值一起放进消息里。规则3接收消息收到消息时Cj max(Cj, C(m)) 1Lamport 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 任务接收属于自己分区的所有中间数据排序、分组调用reduce函数输出最终结果coordinator1.任务调度2.状态维护3.元信息转发coordinator 为每个任务维护三个状态状态含义idle还没分配in-progress已分配正在执行completed已完成结果可用中间文件位置由 coordinator 统一管理coordinator 转发的是文件位置不是文件内容。调度目标最大化资源利用效率任务粒度任务数量应 worker 数量coordinator超时检测故障检测周期性向 worker 发送探测请求超过规定时间没收到响应 → 将该 worker 标记为 failedcoordinator 检测到故障后的第一步把该 worker 上in-progress状态的任务退回到idle状态更新 worker 状态记录将其重新放入待调度队列重新分配给别人由其他 worker 重新执行从而确保作业继续向前推进为什么 map 完成的结果也会丢map 中间结果写的是本地磁worker 一挂本地磁盘就访问不了了为什么 reduce 完成的结果不丢reduce 输出写的是全局文件系统GFS/HDFSworker 挂了文件还在其他节点依然可以访问如何防止读到半成品文件临时文件 原子提交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分布式存储的两大基本技术技术作用比喻分区Partitioning / Sharding把数据拆开存到不同节点一本大书撕成多份每人拿一份复制Replication把数据复制多份存到不同节点同一本书印多本存不同地方为什么需要复制为什么需要多副本避免机器挂了导致数据不可用相当于备份一份复制 同一份数据存到多个节点模式特点代表单主复制一个 leader 处理所有写同步到 followerMySQL 主从、Raft多主复制多个节点都能写互相同步多数据中心部署无主复制所有节点平等客户端写多个节点Dynamo、Cassandra单主复制最简单一致性最容易保证多主复制和无主复制能提高可用性但一致性更难什么是 KV store即Key → Value 的映射操作含义比喻Get(key) → value读取 key 对应的值查字典Put(key, value) → void写入/覆盖key 的值往字典里写词条Append(key, value) → void把 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备所有写请求发给 primaryPrimary 负责把数据同步给 backup读请求可以只从 primary 读State Machine Replication状态机复制核心思路如果两台机器从相同初始状态出发按相同顺序执行相同的操作它们的最终状态一定相同。Failover故障转移如何检测到故障Primary 和 backup 之间定期发心跳。如果 backup 连续 N 次没收到心跳 → 判定 primary 故障。什么是split brain系统中同时存在两个或多个节点认为自己是 primarySplit Brain 导致两个 primary 各自接收不同的写导致 Split Brain 的根本原因网络分区Network Partition节点之间的通信中断但节点本身还在正常运行。如何解决 split brain多数派共识Consensus三条性质性质含义类型Agreement一致性所有做出决定的节点决定的是同一个值SafetyValidity合法性决定的值必须是某个节点提议过的SafetyTermination终止性所有非故障节点最终都会做出决定Liveness概念含义比喻Safety不能发生坏事不能选出两个 leaderLiveness好事最终要发生最终一定选出 leader解释FLP 认为在完全异步的模型中能保证 Safety不能选出两个 leader但不能保证最终一定能达成共识liveness在纯异步模型里不能无条件保证 termination决定之前先看多数派那里有没有历史。Paxos核心思想如果某个值已经可能被选中后面的人必须继续用它。如果还没有任何值被选中proposer 才能用自己的值。Paxos 的角色分工角色职责比喻Proposer提议者提出一个值提议人Acceptor接受者接受或拒绝 proposal投票者Learner学习者学习最终 chosen 的值围观群众Paxos 里提案不是单独一个值而是一对(proposal number, value) (n, v)部分含义例子proposal number提案编号全局唯一越来越大5, 7, 9...value值真正要提议的内容v1, v2...Paxos 的两个阶段Phase 1Prepare先问多数派有没有接受过历史值Phase 2Accept再把一个值写入多数派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 探测历史并拿 promiseaccept 把值写入多数派Multi-Paxos稳定 leader 期间复用 Phase 1 的结果后续操作直接复制二、判断习题判断并发就是多个线程同时执行错并发强调“多个任务均在推进”并不要求每一时刻都真正同时执行判断只有一行代码就不会有并发问题错单行高级语言代码在底层通常对应多个机器指令判断使用更多线程程序一定更快错多线程频繁竞争同一把锁时等待开销可能使程序比单线程还慢判断使用 Go 或 goroutine共享数据自动是安全的错只要多个 goroutine 访问共享数据且没有适当的同步机制race condition 依然存在goroutine 启多了就一定快错goroutine 轻量但不是零成本有调度开销有同步开销有内存开channel 不会死锁错也会例如没人收硬发没人发硬收大家都在等对方并发程序的核心矛盾是多条执行流需要同时推进但它们可能访问同一份共享状态问题答案远程调用时哪些环节可能出问题请求丢、执行挂、回复丢、太慢RPC 怎么解决异构问题用序列化Marshal/UnmarshalRPC 的透明性是什么意思代码写起来像本地调用但背后走了网络透明性的代价是什么延迟高、可能失败、不能传指针/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加起来得到总次数1Map 函数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行号代码作用1def Map(key: str, value: str):Map 函数接收两个参数key是文档名value是文档内容2value value.lower()把所有字母转成小写让 Hello 和 hello 算同一个词3re.findall(r[a-z], value)用正则表达式提取所有纯字母单词只含 a-z忽略数字和标点4ans.append((w, 1))每个单词生成一个(word, 1)对5return ans返回中间结果列表2Reduce函数def Reduce(key: str, values: list): result 0 for v in values: result int(v) # 把所有 1 加起来 return result行号代码作用1def Reduce(key: str, values: list):Reduce 函数接收key单词和values该单词对应的所有 1 的列表2result 0初始化计数器3-4for v in values: result int(v)把所有1转成整数后累加5return result返回最终计数3、MapReduce 的基本流程1输入Master 将输入数据切成很多 splitMaster 维护所有 map / reduce worker 的状态哪个 map worker 空闲就给他一个 split 去处理有限给本地的 worker2MapMap worker 收到数据切片读取 split 内容调用用户定义的 map 函数map 函数生成 中间key , value对将中间结果写入 map worker 的本地磁盘3Shufflemap worker 完成后中间结果按分区函数分为 R 份reduce worker 从各个 map worker 处拉取属于自己分区的数据4ReduceReduce worker 对拉回来的数据进行归并排序并调用 reduce 函数将结果写入分布式文件系统GFS5输出补充MapReduce失败会发生什么Map worker 挂了他已经完成的 map 任务也要重做因为 map 生成的中间结果存在这个 worker 的本地磁盘上机器挂了数据就没了Reduce worker挂了他已经完成的 reduce 任务通常不用重做因为 reduce 输出结果写道分布式系统中都访问得到4、RPC的基本流程10步两台机器Client 和 Server1、Client 调用client stub代理函数2、Client stub序列化参数转化为字节流3、Client machine 通过网络将消息发给 Server machine4、Server OS 接收到消息将消息传给 Server stub5、Server stub反序列化将字节流解析出函数名和参数分发根据函数名决定调用哪个函数6-7、Server stub 传递参数给 server process 并在 Server 处算出结果值8、Server stub 将这个结果值序列化打包为字节流然后传给 Server OS9-10、返回值通过网络传给 Client OS 然后 Client stub 反序列化解析返回值给到 Client process5、Paxos两阶段阶段一1Proposer 选一个唯一递增的提案号n比之前所有编号都大2向所有 Acceptor 发送Prepare(n)3Acceptor 如果没见过更大的编号就回复Promise承诺阶段二1Proposer 发送Accept(n, v)给所有 Acceptor2Acceptor 如果没有承诺过更大的编号就接受这个 proposal3多数派接受 → 值被选定Chosen