6.824 笔记

零、简介

https://mit-public-courses-cn-translatio.gitbook.io/mit6-824/

人们使用大量的相互协作的计算机驱动力是

• 并行提高性能
• 容错（复制）
• 空间上分布的设备之间需要协调
• 限制出错域，提高安全性

分布式系统的挑战

• 组件之间的同步
• 组件没有正常工作带来局部错误
• 水平扩展保证性能达到扩展预期

分布式基础架构

存储、通信、计算

分布式系统三个指标

• 可扩展性 - 性能
  • 指增加设备就能够提高性能的能力
• 可用性 - 容错
  • 在特定的故障范围内，系统仍然能够提供服务，系统仍然是可用的
  • 弱一级：可恢复性
  • 方案：非易失存储 + 复制（灾备）
• 一致性
  • 强一致：
    • 所有机子都能读到最近的一次写入。
    • 通信昂贵、同步代价很高
  • 弱一致：
    • 允许读取出旧的数据
    • 高性能

一、MapReduce

编程模型

• 用户自定义的Map函数接受一个输入的key/value pair值，然后产生一个中间key/value pair值的集合。MapReduce库把所有具有相同中间key值I的中间value值集合在一起后传递给reduce函数。
• 用户自定义的Reduce函数接受一个中间key的值I和相关的一个value值的集合。Reduce函数合并这些value值，形成一个较小的value值的集合。

工作方式

1. 用户程序首先调用的MapReduce库将输入文件分成M个数据片度，每个数据片段的大小一般从16MB到64MB(可以通过可选的参数来控制每个数据片段的大小)。然后用户程序在机群中创建大量的程序副本。
2. 这些程序副本中的有一个特殊的程序–master。副本中其它的程序都是worker程序，由master分配任务。有M个Map任务和R个Reduce任务将被分配，master将一个Map任务或Reduce任务分配给一个空闲的worker。
3. 被分配了map任务的worker程序读取相关的输入数据片段，从输入的数据片段中解析出key/value pair，然后把key/value pair传递给用户自定义的Map函数，由Map函数生成并输出的中间key/value pair，并缓存在内存中。
4. 缓存中的key/value pair通过分区函数分成R个区域，之后周期性的写入到本地磁盘上。缓存的key/value pair在本地磁盘上的存储位置将被回传给master，由master负责把这些存储位置再传送给Reduce worker。
5. 当Reduce worker程序接收到master程序发来的数据存储位置信息后，使用RPC从Map worker所在主机的磁盘上读取这些缓存数据。当Reduce worker读取了所有的中间数据后，通过对key进行排序后使得具有相同key值的数据聚合在一起。由于许多不同的key值会映射到相同的Reduce任务上，因此必须进行排序。如果中间数据太大无法在内存中完成排序，那么就要在外部进行排序。
6. Reduce worker程序遍历排序后的中间数据，对于每一个唯一的中间key值，Reduce worker程序将这个key值和它相关的中间value值的集合传递给用户自定义的Reduce函数。Reduce函数的输出被追加到所属分区的输出文件。
7. 当所有的Map和Reduce任务都完成之后，master唤醒用户程序。在这个时候，在用户程序里的对MapReduce调用才返回。

Map 函数和 Reduce 函数

• Map 函数：
  输入文件存储位置：GFS 进行存储，优先选择距离存储位置近的 worker 做 Map 任务
  接受参数：（Key: 文件名, Value: 文件内容)
  emit 函数： 在 worker 的本地磁盘上创建文件，包含 Map 函数生成的所有 Key 和 Value
• Reduce 函数
  输入文件存储位置： 各个Map 函数处理结果包含目标 key 的 worker 本机
  接受参数：（Key: reduce 目标, Value: key 在各个 worker 中的存储的聚合 list)
  emit 函数： 在共享文件服务中创建文件，包含全部key和聚合结果

二、GFS 谷歌文件系统

简介

GFS 是一个大型的快速的全局文件系统

• 全局：所有应用程序均使用这一个文件系统，用户可以申请权限来查看其中的数据。
• 大容量和高速：每个包含了数据的文件会被GFS自动的分割并存放在多个服务器之上，可以从多个服务器上同时读取同一个文件，还可以在存储系统中保存比单个磁盘还要大的文件。此外，GFS在各个方面对大型的顺序文件读写做了定制。
• 自动故障恢复。
• GFS可能会返回错误的数据，但是可以在应用程序中做一些补偿。
• 只有一个Master节点在工作，还有大量的Chunk服务器。

GFS 的 Master 节点

Master节点用来管理文件和Chunk的信息，而Chunk服务器用来存储实际的数据。Master节点知道每一个文件对应的所有的Chunk的ID以及存储位置（Chunk每个是64MB大小）。

Master 保存的数据内容

• 第一个是文件名到Chunk ID或者Chunk Handle数组的对应。
• 第二个表单记录了Chunk ID到Chunk数据的对应关系。这里的数据又包括了：
  • 每个Chunk存储在哪些服务器上。
  • 每个Chunk当前的版本号，所以Master节点必须记住每个Chunk对应的版本号。
  • 所有对于Chunk的写操作都必须在主Chunk（Primary Chunk）上顺序处理，主Chunk是Chunk的多个副本之一。所以，Master节点必须记住哪个Chunk服务器持有主Chunk。
  • 并且，主Chunk只能在特定的租约时间内担任主Chunk，所以，Master节点要记住主Chunk的租约过期时间。

Master 数据在磁盘上的保存情况：

• Chunk Handle 的数组（第一个表单）要保存在磁盘上。
• Chunk 服务器列表不用保存到磁盘上。因为 Master 节点重启之后可以与所有的 Chunk 服务器通信，并查询每个 Chunk 服务器存储了哪些 Chunk 。
• 版本号需要写入磁盘。
• 主 Chunk 的 ID 不用写入磁盘，因为 Master 节点重启之后会忘记谁是主 Chunk，它只需要等待60秒租约到期，那么它知道对于这个 Chunk 来说没有主 Chunk，这个时候，Master 节点可以安全指定一个新的主 Chunk。
• 租约过期时间不用写入磁盘。
• 此外，Log 在磁盘上进行维护。如果文件扩展到达了一个新的64MB，需要新增一个 Chunk 或者由于指定了新的主Chunk而导致版本号更新了，Master节点需要向磁盘中的 Log 追加一条记录。
• 在磁盘中会创建一些 Checkpoint，恢复时从这里开始执行 Log。

GFS 读文件

第一步，客户端将文件名和偏移量发送给 Master。
第二步，Master 节点将 Chunk Handle（也就是ID，记为H）和服务器列表发送给客户端。
第三步，客户端从最近的服务器读，并缓存 Chunk 与服务器的对应关系。

• 当读取的数据跨越 Chunk 边界，GFS 库会将其拆分成多个请求，分别获取Chunk ID 以及存储服务器，并到服务器获取数据写入 buffer 交给应用程序。

GFS 写文件

第一步，客户端将文件名发给 Master。
第二步，Master 将保存了文件最后一个 Chunk 的主副本和从副本列表告知客户端。
第三步，客户端将要追加的数据写入全部服务器的一个临时位置，直到所有服务器都返回了确认消息。
第四步，客户端告诉主服务器追加文件。服务器查看文件的结尾 Chunk，有足够的空间则通知所有从服务器和自己都将数据写入 Chunk 文件。

第二步 Chunk 主副本不存在

Master 找到所有保存的版本号与 Master 中记录的 Chunk 版本号一致的最新的副本。
然后挑选一个作为主副本，并告知主副本和从副本，副本将增加版本号、写入磁盘、返回确认消息。
最后 Master 将新版本号写入磁盘。

• 当副本上报的版本号大于 Master 存的最新版本号时，Master会更新版本号。

第四步从副本写入失败

从副本告诉主副本写入失败，主副本收到一个写入失败则告诉客户端写入失败，但什么也不会做。客户端收到写入失败之后会重新发起写入流程。

主副本挂了怎么处理

Master 定时 ping 主副本，当发现他挂了之后并不会立即指定新的主副本。因为有可能只是网络问题。
为了避免出现脑裂，主副本在上任时会和 Master 都维护一个租约时间，当 Master 发现主副本挂了会等到租约过期再指定新的主副本。

第二步追加新文件不存在副本

Master 会发现，该文件没有关联的 Chunk，然后通过随机数生成器创造一个新的Chunk ID。之后，Master 会创建一条新的 Chunk 记录，版本号为1，再随机选择一个 Primary 和一组 Secondary。

第四步写失败重写

一般写入失败都是因为网络问题，重试就行了。如果多次失败，Master会踢掉失败的从副本。
为了能够高并发，在写入B的时候可能就已经开始写C了，所以不会撤销B再写入C。代价是应用程序需要容忍乱序数据，可以通过加序列号来解决。

将 GFS 升级成强一致性系统需要考虑的点

• 你可能需要让Primary来探测重复的请求，确保数据在文件中不会出现两次。
• 对于Secondary来说，如果Primay要求Secondary执行一个操作，Secondary必须要么成功执行要么将Secondary从系统中移除。
• 当Primary要求Secondary追加数据时，确定所有副本都能提交之前不将数据暴露给读请求。使用两阶段提交，主副本先问从副本能不能提交，所有人都回复之后再提交。
• 新的Primary上任时，需要显式的与Secondary进行同步，以确保操作历史的结尾是相同的。
• 最后，时不时的，Secondary之间可能会有差异，或者客户端从Master节点获取的是稍微过时的Secondary。系统要么需要将所有的读请求都发送给Primary，因为只有Primary知道哪些操作实际发生了，要么对于Secondary需要一个租约系统，就像Primary一样，这样就知道Secondary在哪些时间可以合法的响应客户端。

单个 Master 存在的问题

• Master 为每个 Chunk 维护表单，内存会耗尽
• 客户端数量增加之后，CPU 处理能力不够使了
• 应用程序难以忍受 GFS 奇怪的语义
• Master 节点故障恢复时间很久

三、VMware FT

复制的方法

状态转移：备份完整状态，包括内存中的全部内容。
复制状态机：备份来自客户端的操作或者其他外部事件。

• 状态转移复制的量太大了，且需要高频率，性能较差
• 复制状态机基本只支持单核

复制的级别

应用程序级别的复制：更加的高效，但是复制的这个行为需要构建在应用程序内部。如 GFS 复制 Chunk 和 Chunk ID。
机器的完整状态的复制：复制每一个 bit，包括内存和寄存器。可以对任何软件进行复制，应用本身不需要操心复制的事儿。效率较低，比如说需要确保中断在主副本和备份的相同位置执行。

VMware FT 工作原理

每个物理计算机可以运行一个虚拟监控机器 VMM，VMM 上再运行一个或多个操作系统。
VMware FT 需要多个物理服务器，一个运行主副本，其他运行备份，目标是让他们的内存镜像完全一致。

工作流程：

1. 客户端发送请求
2. P 的 VMM 收到网络数据包产生的中断，模拟中断发给应用程序的 P 副本。
3. P 的 VMM 将网络数据包拷贝一份，通过 Log Channel 分发给 B 的 VMM。
4. B 的 VMM 模拟中断发给应用程序的 B 副本。
5. P 副本 处理请求进行回复，从虚拟网卡发出，P 的 VMM 收到后发给客户端。
6. B 副本 处理请求进行回复，从虚拟网卡发出，B 的 VMM 收到后直接丢弃。

副本故障

当备份的 VMM 收不到主副本的定时器 Log，会让备份上线，不在阻拦它的回复，不再由主副本的事件驱动，并且对外宣称自己有主副本的 IP 地址，使客户端与自己通信。

• 备份故障的时候，主副本停止向备份发 Log，并独立进行工作。

非确定性事件

包含客户端输入、怪异指令和多核 CPU。怪异指令包含随机数生成、获取时间、获取计算机唯一 ID 等。为了保证主副本与备份的一致性，通过 Log Channel 进行非确定性事件同步。

Log 组成

1. 事件发生时的指令序号，保证主副本和备份在相同的指令位置看到数据。
2. 日志条目的类型，普通网络数据包或怪异指令。
3. 数据，普通网络数据包则是数据内容，怪异指令则是在主副本执行的结果。

Log 同步过程

1. 主副本的 VMM 收到外部中断。
2. VMM 在适当的时候停止主副本的虚机执行并记下当前的指令序号。
3. 在指令序号的位置插入模拟外部中断并恢复虚机执行。
4. 主副本 VMM 将指令序号、终端内容打包成 Log 发送给备份。
5. 备份 VMM 保存 Log 并等待备份虚机执行到指令序号的位置，停止备份虚机的执行，插入外部中断。

• 为了避免备份的工作速度超过主副本导致错过中断，备份只有在备份 VMM 有存了 Log 的时候才能够执行到 Log 记录的指令序号的位置。

输出控制

直到备份 VMM 确认收到了相应的 Log 条目，主副本 VMM 不允许生成任何输出。

1. 客户端输入到达主副本 VMM。
2. 主副本 VMM 将输入的拷贝发送给备份 VMM。
3. 主副本 VMM 将输入发送给主副本虚机，虚机执行后将输出交给主副本 VMM。
4. 主副本 VMM 等待备份 VMM 对之前的 Log 都进行了回复之后，将输出发给客户端。

• 中断（网络数据包和定时器等）多起来之后，主副本一直等待会带来性能问题，可以考虑在更高层级做复制。
• 备份上线的时候要先将全部的 Log 执行完之后再开始服务。

重复输出

问题：客户端一次请求在主副本得到了回应之后，主副本离线，备份上线执行完 Log 之后再次给出回复。
解决：备份与主副本的内存全都一样，使用相同的 TCP 源端口，重复的报文会被 TCP 丢弃。

• 物理机和 VMM 不会修改虚机的 IP 地址和 MAC 地址，报文直接透传到局域网。
• 备份上线之后虚机发起 GARP 更新交换机 MAC 地址表。

Test-and-Set 服务

当备份认为主副本挂了，想要上线的时候，要向第三方权威 Test-and-Set 服务请求许可，拿到锁才行。每次主从切换都需要获得锁。

四、Raft