前言

这个部分来自课程 MIT6.824，这门课每节课都会精读一篇分布式系统领域的经典论文，并由此传授分布式系统设计与实现的重要原则和关键技术。

个人认为阅读论文比课程本身更加重要，课程围绕论文展开，可以快速获取论文的核心观点，课程的一切细节以及未提及的内容在论文中具有最详细的解释。另外教授会从当今立场（2022）评价论文的意义和缺陷，同时可能补全论文中缺失的信息解释，教授对学生提问的一些回答具有很好的启发意义，这些内容不被包含在论文中。

本文综合课程内容和论文核心观点，并参考一些其他资料整理，希望对你学习课程有所帮助。

课程官方：https://pdos.csail.mit.edu/6.824/

博主整理：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824

B 站录屏：https://www.bilibili.com/video/BV1qk4y197bB

​请阅读论文 GFS： https://pdos.csail.mit.edu/6.824/papers/gfs.pdf

什么是 GFS？

在 GFS 出现之前，分布式系统实际已经进行了数十年的学术研究，但事实上在工业上它仍然很少被认可。在 2003 年，实际上互联网规模已经相当巨大，像 Google 这样的大数据公司开始实际使用分布式系统。GFS 几乎作为第一个严格意义上的分布式系统，它做了很多工作解决包括性能和容错性上的问题，在相当长的时间内颇具影响力。

GFS 的设计目标

GFS 的设计目标包括：大容量、快速、全局共享、容错、自动恢复。

GFS 的局限性：

  • GFS 的设计仅局限于一个数据中心，它并未将数据分布到世界各地。
  • GFS 始终是 Google 内部使用的系统，Google 从未直接向外部售卖 GFS 系统。

GFS 的特征：

  • 数据切片，它将大文件切片存储在不同机器上。
  • 大型顺序 IO 场景，GFS 被设计用于大型顺序 IO，它不对小规模随机访问进行优化。
  • GFS 在当时并没有提供新颖的想法，但它是第一个被用于工业界的系统。
  • GFS 并不保证返回正确的数据，这样的弱一致性在当时是反学术的。

GFS 的 master 节点

GFS 集群中，具有三种角色：master、chunkserver、client。其中，master 采用主备模式，一个集群中只有一个 master 在工作。

master 的数据结构

master 仅用于存储元数据，它仅包含这三类数据：文件空间域、文件到 chunk 的映射关系、chunk 所在的位置。每个 chunk 的大小为 64MB，当 client 获取文件时，首先向 master 获取文件包含哪些 chunk 以及它们的位置，然后 client 直接从对应的 chunkserver 获取数据。具体地，master 的数据主要有：

  • File（文件空间域和文件到 chunk 的映射关系）→\to
    • Chunk ID 列表。
  • Chunk ID（chunk 所在的位置） →\to
    • 每个 chunk 所在的 chunkserver 列表，表示多个副本位置。
    • chunk 对应的最新版本号（Version），版本落后表示已失效。
    • 主 chunk（Primary Chunk），所有写控制从主 chunk 开始，它是多个 chunk 副本之一。
    • 租约到期（Lease Expiration），主 Chunk 只在租约时间内担任主 chunk，一份租约是 60 秒。

master 的容错性

master 包含的三类元数据中，文件空间域和文件到 chunk 的映射关系使用 NV（非易失性）方式存储，而 chunk 所在的位置及其一些相关信息（chunkserver 列表、主 chunk、租约到期）使用 V（易失性）方式存储。例外地，chunk 的最新版本号应该是 NV 方式存储的，我们后面会讲到为什么。

对于前者的 NV 方式存储，包括以下两个方面：每次操作元数据的 Operation Log 同时在主备 master 存储，一旦宕机重启，从 Operation Log 顺序恢复；当 Operation Log 达到一定数量，生成 checkpoint 快照并清空 Operation Log，这样有利于平衡容错开销。

对于后者的 V 方式存储，即无需额外容错开销。master 启动时，从 chunkserver 获取 Chunk ID 和 Version 信息。至于主 chunk 和租约，完全可以遗忘并重新任命。

另一方面 master 具有 standby master 和 shadow master。standby master 可以在宕机时接替工作，而 shadow master 可以提供短期的只读服务和分担部分 master 压力。

GFS 读文件

当 client 需要读取文件时，它会首先询问 master 主机。client 将告知 master 包括文件名、文件偏移量、读取字节数，master 通过两表查询会告知这段文件所在的 Chuck ID 的所有相关信息。client 得到这些信息后从相应的 chunkserver 请求数据。

需要注意的是：

  • client 会缓存 master 返回的这些元数据，这样 client 有时不再需要向 master 询问。这些缓存会在租约过期、文件关闭、缓存池满时清理。
  • 当出现数据跨 chunk 时，由 client 将询问切片后询问 master。虽然 client 不知道这些数据在哪个切片中，但它可以计算哪些数据在一个切片中。这样做的好处是，client 可以充分利用缓存的元数据。
  • client 将获取 chunk 的所有副本位置，这时 client 会选择最近的 chunkserver 请求数据，由于在 Google 的数据中心，IP 地址是连续的，client 可以轻易的计算其中最近的 chunkserver。

GFS 写文件

具体而言，这个问题是如何追加文件，它与写不同，就像 write mode 和 append mode 的区别。

GFS 的写操作相较于读操作复杂的对，因为它需要保证多个副本之间是一致的。当 client 需要写入文件时，它会首先询问 master 主机。client 同样将告知 master 包括文件名、文件偏移量、读取字节数，master 通过两表查询会告知这段文件所在的 Chunk ID 的所有相关信息。

client 获取的这些信息包括 chunk 所在的 chunkserver 和其中的主 chunk 及租约时间。我们将持有主 chunk 的 chunksever 称为 primary，将持有其他副本的 chunksever 称为 secondary。client 首先通知 primary 准备接收数据，primary 将通知所有 secondary 准备接收数据。然后 client 会将数据发送到 primary 和 secondary，它们（primary 和 secondary）会首先将数据存储在临时文件中，然后追加到 chunk 中。如果这一切正常，secondary 将发送成功响应到 primary，primary 确认所有响应成功后发送成功响应到 client。

如果 client 收到异常响应或者未收到响应，client 将重试整个流程。最后 client 还会缓存 master 返回的这些元数据，这样 client 有时不再需要向 master 询问。同样地，缓存会在租约过期时清理。

需要注意的是，client 的数据传输具有不同的传输路径，我们称之为数据流，而称之前的传输方式为控制流。与控制流不同，数据流更专注传输效率，数据流会从 client 发送到网络距离最短的 chunkserver A，然后 A 将它转发到剩余最近的 chunkserver B，依此类推。我们称之为 pipeline 模式，它的优势在于均衡交换机负担，同时更好利用全双工模式。

版本和租约 (Version & Lease)

我们在之前多次提到了版本（Version）和租约（Lease）的概念，但并未介绍它是如何工作的。版本和租约定义了 primary 的任期时间和任期版本，每次分发租约时将更新版本。版本和租约在 GFS 的容错机制中具有相当重要的地位。

由于一些 chunkserver 可能暂时处于离线状态，当它恢复并重新加入系统时，其上的 chunk 版本可能是陈旧的。如果 chunkserver 使用了陈旧的 chunk 版本，它会被 master 忽视。master 会将不足数量的 chunk 拷贝到其他 chunkserver，而这些陈旧的 chunk 版本会在连接上 master 后定期清理。

当一个写操作到达 master 时，它会查询 chunk 的 primary 及其租约时间。如果 primary 不存在或者租约过期，master 会重新指定一个 primary，并更新当前 chunk 的版本。然后正如我们先前描述的那样，client 将完成后面的流程。

值得注意的是，租约只会在过期时分发。例如 primary 失去连接，master 不会重新分发租约，而是等待租约过期。因为这里可能存在网络分区的问题，这时在这个网络中 primary 可能对 client A 或 master 是不可见的，而对 client B 是可见的。这时如果重新分发租约，那么在这个网络中就存在两个 primary 是局部可见的（因为 client 存在缓存），这种现象称为脑裂，也一定会产生一致性问题。我们通过租约协调这个问题，即使存在网络分区，当一个分区的 primary 被任命时，另一个分区的 primary 将自动过期。

有学生提出，既然每次 client 向 master 提出请求，master 为何不每次指定 primary？首先是并发问题，如果存在两个 client 对同一个 chunk 执行写操作，它们必须由同一个 primary 指定其次序，否则就出现了脑裂。其次 client 是存在缓存的，因此它不一定每次向 master 请求。最后网络在传输过程中可能存在延迟，网络重试可能比他更快到达，这时也会存在冲突。

我们回到写操作。由于 master 只会在租约过期时重新分发，因此如果一些机器不可逆的发生故障，那么它只有在租约过期时才有可能重新恢复。当然一些网络故障通过重试即可解决。另外一个需要注意的点是，虽然我们的写操作返回了异常，但它可能依然存在正常的副本，之后的读操作可能读到正常的数据也有可能是缺失的，这对一个分布式系统而言是可接受的。

GFS 的一致性

GFS 是弱一致性系统，也就是说它可能存在一致性问题。

当 client 追加数据段 A 时，它可能是成功的，这时所有副本都将包含数据段 A。然后追加数据段 B 时，可能某个 secondary 失败了，这时将出现重试。其中我们成功追加了数据段 C，然后数据段 B 的重试成功。当然，也有可能出现 D 追加失败，并且重试失败。于是如图中所示，我们的 chunk 可能存在空缺（padding）和重复（duplicate），更糟糕的是如果不断重试它的重复可能进入下一 chunk。

GFS 的应用应该具有容许错误的能力，例如在收到错误响应时，应用应当自动过滤其中缺失的数据。我们提供 checksum 用于检测 chunk 的数据完整性，这可以用于验证是否存在空缺和重复。另外如果你的数据存在幂等性问题，你必须剔除重复数据，这可以利用唯一标识区分，这些方法被包含在我们的库中。

目前没有将 GFS 改进为强一致系统的方案，不过它发布的前 5-10 年在 Google 具有非常出色的表现，许多 Google 的基础架构例如 BigTable 和 MapReduce 都运行在它上面。

副本放置与回收

GFS 考虑副本放置策略出于负载均衡和容错性的考量。副本放置会发生在以下场景：副本创建、失效重放置、重平衡。

出于负载均衡的考量，GFS 会将新副本放置在负载最低的 chunkserver 中；另一方面，出于容错性考量副本必须是跨机架的，因为同一机架下的 chunkserver 可能同时离线。考量的第三个方面是重要性考量，对于副本创建是立即的，GFS 必须立即执行创建。而失效重放置和重平衡作为后台任务进行，他们以较低的速率运行避免抢占立即任务资源。在这里失效根据失效副本数排序，失效副本越多的 chunk 更急切完成拷贝放置以避免损失数据。而重平衡优先级最低，它会在空闲时将副本从一个 chunkserver 移动到另一个，从而完成负载均衡。这些任务均在 master 的控制下完成。

GFS 提供了垃圾回收机制，同样以缓慢的后台任务清理失效副本。失效副本主要包括两种：租约过期的副本、用户删除的副本、损坏的副本，其中租约过期是租约版本低于最新版本的副本，它通常是 chunkserver 在一段时间离线导致的。这些副本会在被 master 检测到时从 metadata 删除，然后 chunkserver 会定期发送心跳，这些数据包含了部分 chunkserver 的本地 chunk，它会在多次心跳中扫描全部本地 chunk。每次 chunkserver 发送心跳，master 将回复哪些 chunk 不在 master 的 metadata 中，然后 chunkserver 将清理这些 chunk 和相关的 metadata。可以发现这样被动的垃圾回收机制更加简单可控。

GFS 的缺陷

GFS 作为单 master 的分布式系统，向业界证明了单 master 系统依然可以很好的工作，但也是单 master 成为了系统很多的缺陷所在。

  • master 存储了所有的元数据，随着文件的增加，这些数据可能会占满其资源。
  • master 需要支持数千台机器的集群，而 master 的 CPU 每秒只能处理数百个请求。
  • master 的主备切换不是自动的，它需要人工干预或外部设施支持，前者可能需要等待几个小时。
  • 另外一点就是 GFS 奇怪的语义可能为应用带来一些困扰，尽管这些不一致性发生的概率很低。
  • 网络是制约当时 GFS 这类分布式系统的主要瓶颈，这些系统早已不再使用。