The Google File System 论文阅读

发表于 更新于 分类于 阅读次数： 本文字数： 7k 阅读时长 ≈ 25 分钟

很早就想读读大名鼎鼎的 GFS 的论文了，这次终于抽出时间好好读一下。

#0. 摘要

GFS 是一个可伸缩的分布式文件系统，用于大的、分布式的数据密集型应用。 GFS 在运行在廉价的商用硬件上运行的同时，对外提供容错性。 服务大量客户端时，能提供良好的总性能。

在 Google 的环境中经过了实际考验。

#1. 引言

GFS 的设计目标：高性能、伸缩性、可靠性、可用性。

  1. 在大规模系统中，组件故障是常态。因此持续监测，错误检测，容错性和自动恢复是必须包含的部分；
  2. 预期文件会很大，常见的是 GB 级别；
  3. 大多数 workload 模式是追加写而非覆盖写，文件写入后只会被读取，读取通常是顺序读。 因此关键点在于保证追加写的性能和原子性；
  4. 协同设计上层应用和 FS 的 API 对提供整个系统的弹性有好处。例如放宽一致性约束简化应用程序。

#2. 设计概述

#2.1 假设

  1. 使用经常故障的廉价商用硬件
  2. 保存相当多的大文件
  3. 读 workload 主要是大量顺序读和少量随机读
  4. 写 workload 主要是大块的追加写
  5. 需要给追加写操作提供明确的并发语义
  6. 高带宽比低延迟更重要

#2.2 接口

GFS 提供的文件系统接口有：create, delete, open, close, read, write, snapshot 和 record append。

record append 是原子性的追加写操作，用于多个客户端并发写入同一个文件。

#2.3 架构

GFS 包括一个 master 节点，多个 chunkserver 节点。都是普通 Linux 机器上运行的用户态进程。

文件会分成固定大小的 chunks，每个 chunk 有一个全局唯一的 64-bit 的 chunk handle 作为标识。 chunkserver 将 chunks 保存在本地磁盘上，通过 chunk handle 去读写，可以只读写其中某一段。 为了数据可靠性，每个 chunk 会被复制到多个 chunkserver 上，默认是 3 副本。

master 负责元数据管理，包括 namespace, ACL 信息, 文件到 chunk 的映射，chunk 的位置信息。 还负责控制全局的任务，例如 chunk 租约管理, 垃圾回收, chunk 迁移。 master 通过 HeartBeat 消息给 chunkserver 分发任务和回收状态。

GFS 客户端是一个用户态库的形式，和应用程序链接在一起。提供用户态的类文件系统接口。

因为大多数应用程序都是流式访问大文件，客户端和 chunkserver 都不缓存数据。 这样避免了缓存一致性问题，可以简化实现。 因为 Linux 本身对磁盘文件会有缓存，chunkserver 也不缓存数据。

#2.4 Master 设计

单个 Master 可以简化设计，因为所有信息都保存在这个节点上，所以可以使用更高级的 chunk 的放置策略。 但是必须注意最小化 Master 对读写的参与，避免单点形成系统瓶颈。 客户端先问 Master 获取 chunk 的位置信息，然后直接和 chunkserver 通信。 这个位置信息会缓存一段时间。

客户端的读操作：

  1. 由于 chunk 大小固定，客户端先将欲访问的 byte range 转换成 chunk index
  2. 向 Master 请求 chunk 的位置信息。客户端缓存这个信息一段时间。
  3. 客户端和最近的持有该 chunk 的 chunkserver 通信，获取实际数据。

#2.5 Chunk 大小

大 chunk 的好处：

  1. 减少客户端和 Master 之间的交互次数
  2. 应用程序对文件的操作具有局部性，可以减少与 chunkserver 的通信
  3. 减小了元数据的大小，使之可以放在内存中

坏处：

  1. 对小文件不友好，容易导致局部热点。 一个例子：一个 exe 文件写到 GFS 上，然后很多机器同时拉取这个文件去执行。 临时解决方案是提高这个文件的备份数量，并且让读机器随机启动。 长期解决方案是允许客户端之间 P2P 分发文件。

#2.6 元数据

Master 节点保存三类元数据：

  1. 文件和 chunk 的 namespace
  2. 文件到 chunk 的映射
  3. chunk 的每个副本的位置信息。

所有这些元数据都存在内存中。2 和 3 还会额外通过 Operation Log 的方式持久化到本地磁盘上。

#2.6.1 内存数据结构

Master 会周期性地扫描所有的状态，用于当 chunkserver 故障的时候，实现 chunk 垃圾回收，再复制等操作；以及在 chunkserver 间平衡负载和磁盘空间。

一个潜在的考虑是，整个系统可能被内存大小限制。但实际上没问题，每个 64MB 的 chunk 仅需要 64B 的元数据。

相对于单点的种种好处（简单性、可靠性、性能、弹性），多花费一点内存，这个 trade-off 是值得的。

#2.6.2 chunk 位置

Master 节点不持久化 chunk 的位置信息，而是在开机时从 chunkserver 处轮询一遍。

如果持久化 chunk 位置信息，就需要额外的机制保证两者同步，增加了复杂度。

另一个理解方式是: chunkserver 对于自己持有的 chunks 有最终决定权，因此 master 在保存一次位置信息是多余的。

#2.6.3 Operation Log

Operation Log 记录了对元数据的修改，是整个 GFS 的关键。

因此我们需要保证元数据持久化完毕之前，不能暴露给客户端看到。 GFS 会把 Operation Log 复制到多个远程机器上，而且只有所有机器上都落盘完成，才会回应客户端。 Master 会累计几条 Log，然后一次性刷入磁盘。

Master 机器会重放所有的 Operation Log 来恢复状态。为了加快恢复速度，Master 会定期生成 checkpoint。 Checkpoint 采用了压缩 B 树的形式，可以快速加载到内存中。

为了防止 Checkpoint 过程阻塞住 Master 的正常操作，Master 会先切换到一个新的 Log 文件，然后在单独的线程中生成 Checkpoint。

老旧的 checkpoint 和 Log 可以直接删掉了，但实践中，会保存一段时间，以防止意外的故障。

#2.7 一致性模型

GFS 采用了一种宽松的一致性模型。

#2.7.1 GFS 的承诺

对于 namespace 的变更（例如文件创建）操作是原子的。对文件内容的修改不是原子的。 我们首先定义一段数据区域是：

  • 一致的（consistent）：如果所有 client 都能读到一样的数据

  • 确定的（defined）：如果该区域是 consistent，而且 client 能够读到自己刚刚写入的数据

  • 串行写: 数据区域是一致且确定的，因为只有一个 client 写入。

  • 并发写: 是一致的但不是确定的，因为所有 client 都能读到一样的数据，但是不确定是哪一个写入。

  • 写失败: 会导致数据区域 inconsistent，因为 client 读到的数据不一样。

GFS 有两种写的方法：

  • write: 写入到指定的 offset
  • record append: 原子地写入到文件末尾，at least once 语义, 返回写入的 offset

#2.7.2 对应用程序的影响

GFS 应用程序只要进行一些简单的修改，就可以适应这种一致性模型。

  • 依赖追加写而不是覆盖写
  • 做 checkpoint
  • 写能够自校验、自定位的数据

#3. 系统交互

设计的目标是尽可能减小 Master 在所有操作中的参与。

#3.1 租约和变更顺序

变更是一次修改文件数据或者 chunk 元数据的操作，例如写或者追加。 变更需要在 chunk 的所有副本上进行。

GFS 使用租约来维持多个副本之前修改顺序的一致性。 Master 会给一个 chunk 的一个副本颁发一个租约，称之为 primary。 由 primary 选择一个所有副本之间修改的顺序，所有副本会按照这个顺序来修改。

租约有 60 秒的有效期，但是如果时间不够，primary 可以请求 master 续约。 续约通过 HeartBeat 消息来完成。 Master 可以随时撤销租约，例如当 primary 故障。

GFS 的写过程如下：

  1. 客户端向 Master 请求 chunk 的位置信息，包括谁是 primary 还有其他副本的位置。 如果此时没有 primary，Master 会选择一个。
  2. Master 回复 primary 的身份和其他副本的位置。客户端会缓存这个信息一段时间。除非 primary 故障，客户端不会重新请求 Master。
  3. 客户端以任意顺序把数据推送到每一个副本上。每个 chunkserver 会把收到的数据先放进一个 LRU 缓存中，等待被取走或者过期。
  4. 当所有的副本都确认收到了数据，客户端会通知 primary，发送一个写请求。 然后 Primary 会给每个客户端的写请求分配一个序列号。
  5. Primary 把写请求转发给所有涉及到的副本，每个其他副本按照 primary 执行的序列号顺序来从 LRU 缓存中取数据然后写入。
  6. 其他副本写入成功后，会回复 primary。
  7. Primary 收到所有回复后，会回复客户端。如果有副本写入失败，也会报告给客户端。

如果一次写操作跨越了 chunk 边界，那么客户端会把这个操作分成多个写操作，然后按照上面的方式处理。 因此可能导致修改区域处在一致但不确定的状态。

#3.2 数据流

GFS 将数据流和控制流解耦。

为了最大限度利用机器网络带宽，数据是在 chunkserver 中链式传递而非星型传递。

为了尽可能避免撞到网络瓶颈和慢链路，每台机器会优先把数据转发给最近的、没有收到过数据的机器。

复用 TCP 连接发送数据以减小延迟。

#3.3 原子记录追加

GFS 提供了一种原子的追加写操作，称之为 record append。 客户端只需要提供数据，GFS 会找到合适的地方写入然后返回 offset，GFS 提供 at least once 的语义。

record append 仍然延续 GFS 的写过程，除了一点不同：

  • 客户端会把所有数据都推送到文件的最后一个 chunk。
  • Primary 会检查追加是否会导致新增 chunk，如果会，则会在当前 chunk 末尾填充空洞，其他副本同理，然后叫客户端去重试。
  • 否则，Primary 会把数据写入到 chunk 的最后，然后返回 offset。

如果某个副本上执行追加失败，客户端会重试这个操作。因此，GFS 不保证所有副本都有相同的数据，只保证写操作 at least once。

实际上，有可能会出现这种情况：primary 的数据比其他副本的数据要长。（待确认）

#3.4 快照

快照操作用于给文件或者目录快速创建一个副本，同时尽可能减小对写操作的中断。

和 AFS 类似，GFS 使用了 CoW 的方式来实现快照。 当 master 收到一个快照请求时，会先把所有涉及到的 chunk 的租期都收回。阻塞住后续的写操作，防止影响当前快照。

在全部租期都被收回或者过期后，master 就会把这个操作（指快照操作）先写到磁盘上的 WAL 上，然后再改内存数据结构。

新创建的快照文件会和原始文件指向相同的 chunk。 当客户端第一次想要写入一个快照过的 chunk C 的时候，master 就会注意到 chunk C 的引用计数大于 1，此时 master 会进行 CoW：

  • 先创建一个新的 chunk handle C’；
  • 要求每个持有 C 的 chunkserver 复制一份 C 作为 C’。

然后再正常处理写请求。

这里要求 chunkserver 复制有一个好处是不需要占用网络带宽，因为复制是在 chunkserver 本地进行的。

#4. Master 操作

Master 负责管理整个系统的元数据。

#4.1 命名空间管理和锁

很多 master 的操作是很慢的，例如打快照会导致撤回所有租约。 GFS 通过减小锁的粒度来提高并发度。

GFS 没有使用每个目录一个数据结构的方式表示文件和目录，而是采用了类似多级查找表的结构。 由于文件系统是层级结构，使用前缀压缩可以节约很多空间。

每一级目录都有一把读写锁，每次变更操作都需要获取从根目录到目标目录的所有锁。举例：

  • 创建/home/user/foo：需要 /home 和 /home/user 的读锁，/home/user/foo 的写锁；
  • 快照/home/user 到/save/user：需要 /home 和 /save 的读锁，/home/user 和 /save/user 的写锁；

由于文件数量可能很多，读写锁对象都是动态懒分配的，并且一旦不用就会删掉。

为了防止死锁，GFS 会按照目录的路径顺序，以及字典序来获取锁。

#4.2 副本放置策略

GFS 集群的网路拓扑是分层的，每个机房有多个机架，每个机架有多个机器。 GFS 会尽量把副本放在不同的机架上，以防止单个机架故障。

#4.3 创建、再备份和再平衡

#chunk 创建

当 Master 创建一个 chunk 时，需要决定这个 chunk 的副本放在哪些 chunkserver 上。主要考虑这些因素：

  1. 优先放置在磁盘剩余空间较多的 chunkserver 上。
  2. 优先放置在近期新文件较少的 chunkserver 上。因为 Google 的 workload 大多是 append-once-read-many 类型。
  3. 分散副本，避免放在同一个机架上。

#chunk 再备份

当 chunk 的副本数量低于用户设定的目标数量时，Master 就会进行再备份。 这种情况发生的原因有：chunkserver 掉线，chunkserver 数据损坏，或者用户期望提高。再备份时也会做一些优化，例如优先备份 live file，其次是最近删除的文件。 当某些失败的 chunk 影响了应用程序运行时，GFS 会提高这些文件的优先级，加快恢复的过程。

Master 每次会选择一个优先级最高的 chunk，然后要求 chunkservers 去复制这个 chunk。新副本的放置策略和创建 chunk 时一样。 为了防止再备份操作压倒客户端的流量，Master 会限制再备份的速度。

#chunk 再平衡

Master 周期性地检查当前的副本分布，移动副本以达到更好的磁盘利用率和负载均衡。 通过再平衡操作，Master 逐渐填满新的 chunkserver 而不是一口气填满。 再平衡的策略也和前面类似。

#4.4 垃圾回收

文件删除之后，GFS 不会立即回收可用的物理空间。而是在文件和 chunk 级别进行懒惰回收。

#4.4.1 机制

在 GFS 上删除的文件会被重命名为一个名字包含删除时间戳的隐藏文件。 这个文件在 Master 的定期扫描中会被发现，如果这个文件已经被删除超过 3 天，那么这个文件会被真正删除。 在真正删除之前，这个隐藏文件都是可以被正常读的，而且可以被恢复（通过重命名为正常文件名）。 当隐藏文件被真正删除，相关的内存中的元数据也会被删除。

在对 chunk namespace 的日常扫描中，Master 会发现一些不再被引用的 chunk，这些 chunk 会在和 chunkserver 通信对数据的时候被发现并回收。

#4.4.2 一些讨论

采用懒惰回收的方式有一些好处：

  1. 简单，可靠：避免删除文件失败导致数据删不掉
  2. 均摊了删除操作的开销，不会给 Master 带来额外的压力
  3. 增加误删除的恢复机会

相对地，也有坏处：

  • 用户想要释放磁盘空间的时候，不能立即释放
  • 对于反复创建和删除临时文件的程序不友好

一点小优化是，如果再删除一次已经删除的文件，就加速删除过程。

#4.5 陈旧副本检测

如果 chunkserver 挂了，然后丢失了变更，那么这个 chunk 的副本就会变成陈旧的。 Master 会维护一个每个 chunk 的版本号来区分陈旧的副本。

Master 每一次授权租期的时候，都会让该 chunk 的版本号加一，然后提醒所有最新的副本。Master 和副本都会将新的版本号持久化。 如果某一个副本挂了，Master 下一次重启的时候就会发现这个副本的版本号比其他的小，然后会把这个副本标记为陈旧的。 如果 Master 看到了一个更大的版本号，说明 Master 在授权租期的时候挂了，因此就会把大的版本号当成最新的（没看懂，存疑）。

Master 在垃圾回收过程中移除陈旧的副本。 为了防止客户端读到陈旧的数据，在实际移除之前，Master 也会假装陈旧的副本是不存在。 除此以外，Master 在回复客户端 Primary 身份、以及叫 chunkserver 复制 chunk 的时候，也会带上这个 chunk 的版本号，以便客户端和 chunkserver 去校验，确保读到的数据是最新的。

#5. 容错和诊断

#5.1 高可用

GFS 集群保持高可用的两个策略是：快速回复和复制。

#5.1.1 快速恢复

Master 和 chunkserver 都设计成可以快速重启的（几秒钟恢复状态）。 即使重启了，对其他部分的影响也仅仅是小卡顿一下，直到网络请求超时重试。

#5.1.2 chunk 复制

每个 chunk 会被复制到多个机架的多个 chunkserver 上。 用户可以为不同的目录设置不同的副本数量，以适应不同的容错需求。默认是 3 副本。

除了复制外，GFS 还在探索使用一些跨服务器的冗余技术，例如奇偶校验码等。

#5.1.3 Master 复制

为了可靠性，Master 状态也有副本。Master 的 Operation log 和快照都会被复制到多个机器上。 一条变更只有在所有机器上都落盘成功后，才会认为是已提交。 如果机器挂了，守护进程会在其他持有 logs 的机器上新建一个 Master 进程。 客户端只会用 Master 的 canonical name 来连接 Master，一般是一个 DNS 名字，方便 Master 迁移。

Master 会有一些只读副本，对外提供读服务，用于增强系统的读性能。 这些只读副本会读取备份机器上的 Operation log 并重放，因此会稍微落后于 Master。 只读副本启动时也会轮询一遍所有的 chunkserver。

#5.2 数据完整性

每个 chunkserver 都会用校验码来校验自己保存的 chunk 数据的完整性。 注意 GFS 不承诺多个副本之间的数据一致性，只保证 at least once 语义。

具体来说，每个 chunk 会拆分成 64KB 的块，每个块会计算一个 32 位的校验码。 校验码会在内存和磁盘上都保存一份。

每次有客户端或者其他 chunkserver 读数据的时候，chunkserver 会读取（读取范围覆盖到的）数据块然后验证校验码。 如果校验码不对，chunkserver 不会返回数据，而是会报错。请求方就会去其他副本上读取数据。 当找到一个正确的数据块后，Master 就会通知这个 chunkserver 删掉这个坏的副本。

校验码对读性能的影响很小。而且客户端代码在读取的时候会对齐到块边界，

校验码计算针对追加写操作做了深度的优化。GFS 的校验码实现了增量计算，只需要计算新增的数据块的校验码。

对于覆盖写操作，需要先读取写入范围的起始和结束块，进行校验，然后再写入新的数据，计算新的校验码。 如果不检查起始和结束块的校验码，那么可能会导致数据不一致。

当 chunkserver 空闲的时候，可以扫描和校验不活跃的 chunk，以检验很少读的 chunk 的完整性。 如果发现坏的数据块，Master 可以通知 chunkserver 删掉这个坏的副本。

#5.3 诊断工具

为了方便 debug，GFS 生成诊断日志记录关键事件和所有的网络请求和响应。

#GFS - FAQ

翻译自 MIT 6.824.

#Q1. 只有一个 Master 是好的设计吗？

长期来看不是。Google 发表在 ACM Queue 上的文章 GFS: Evolution on Fast Forward 中提到了，在长期实践中，GFS 的很多设计都是有问题的。 文件的数量一直增长，把所有文件元数据都放在单点 Master 的内存中是不合理的。 随着客户端的数量增长，单点 Master 的 CPU 也会逐渐变得不够用。 实际上，GFS 切换 Master 需要人工干预，因此很慢。 下一代 GFS，Colossus，已经用了多个 Master，而且有更加自动化的 Master HA。

#Q2. GFS 的 record append 为什么是 at least once 语义？

在第 3.1 节的第 7 步中提到，如果写入在任意副本上失败，客户端会重试。 这会导致数据在没有失败的副本上被追加多次。 另一种设计方案是对客户端请求做去重，不管发生任意故障（例如，在客户端第一次请求和重试之间，Primary 故障） 你将在实验 3（指 6.824 的 Raft）中实现这样的设计，但这会显著增加复杂性和性能开销。

#Q3. 应用程序怎么识别 chunk 中的 padding 和 duplicate record？

为了检测 padding，应用程序可以在有效记录的开头放置一个可预测的 magic number，或者包含一个 checksum，该校验和仅在记录有效时才会有效。

应用程序可以通过在记录中包含 Unique ID 来检测重复记录。然后，如果它读取到一个与之前记录具有相同 ID 的记录，它就知道这些记录是重复的。

GFS 为应用程序提供了一个库来处理这些情况。GFS 设计的这一方面实际上将复杂性从 GFS 转移到了应用程序，这可能并不理想。

#Q4. 既然 record append 写入的位置是不确定的，那么应用程序如何找到他们写入的数据？

追加操作（以及 GFS 整体）主要面向那些需要顺序读取整个文件的应用程序。 这类应用程序会扫描文件以查找有效记录（参见 Q3），因此它们不需要提前知道记录的具体位置。 例如，文件可能包含一组并发网络爬虫遇到的 URL。任何特定 URL 的文件偏移量并不重要；读取者只需要能够读取整个 URL 集合即可。

#Q7. 基于 POSIX API 开发的应用程序适配到 GFS 上需要修改吗？

是的，但是 GFS 是为了新开发的程序设计的，例如 Google 的 MapReduce。

#Q10. 假如 S1 是某一个 chunk 的 Primary，然后 Master 和 S1 之间的网断了。Master 会选另一个 S2 作为 Primary。因为 S1 没有实际挂掉，那么系统中会有两个 Primary 吗？

这样会出大问题，因为会有两个 Primary 会同时进行不同的更新操作。 幸运的是，GFS 的租约设计避免了这种情况。Master 给 S1 一个 60s 的租约。 S1 会在过期之后主动退位。S1 退位之前，Master 不会给其他 chunkserver 发送租约。 所以 S1 停止之前，S2 不会成为 Primary。

（PS. 但是怎么保证 Master 和 S1 的时间同步呢？）

#Q12. Google 还在用 GFS 吗？

传言说 GFS 已经被 Colossus 取代了。它们的设计目标一直，性能和容错性都有所提高。 此外，很多 Google 内部的应用程序已经迁移到了 BigTable、Spanner 之类的类数据库系统。 然而，大部分 GFS 的设计都跑到了 HDFS 里面。

拓展阅读：Colossus under the hood: a peek into Google’s scalable storage system

#Q13. GFS 为了性能和简单性而牺牲正确性，这在多大程度上是可以接受的？

这是分布式系统中一个反复出现的主题。 强一致性通常需要复杂的协议，并且需要通信和等待回复（正如我们将在接下来的几节课中看到的那样）。 通过利用特定应用程序类别可以容忍弱一致性的特点，可以设计出具有良好性能和足够一致性的系统。 例如，GFS 针对 MapReduce 应用程序进行了优化，这些应用程序需要对大文件进行高性能读取，并且能够容忍文件中的空洞、记录多次出现以及不一致的读取。 另一方面，GFS 并不适合用于存储银行的账户余额。

#Q16. 内部碎片是什么？懒惰分配有什么好处？

内部碎片是指当系统使用的分配单元大于请求分配所需的空间时，浪费的空间。如果 GFS 以 64MB 为单位分配磁盘空间，那么一个 1 字节的文件将浪费近 64MB 的磁盘空间。

GFS 通过懒惰分配磁盘空间来避免这个问题。每个数据块都是一个 Linux 文件，而 Linux 文件系统使用几十 KB 的块大小；因此，当应用程序创建一个 1 字节的 GFS 文件时，该文件的数据块仅消耗一个 Linux 磁盘块，而不是 64MB。

(PS. 估计就是用 fallocate，实际写入数据时才真正分配空间)

#Q17. GFS 从弱一致性上获得了什么好处？

更容易理解的角度是，假如 GFS 需要实现更强的一致性，需要补充的工作。

Primary 不应让 Secondaries 执行写入操作，除非所有 Secondaries 都能够完成该操作。这可能需要两轮通信：

  • 第一轮询问所有 Secondaries 是否存活并能够承诺在请求时执行写入操作，以及（如果所有 Secondaries 都回答“是”）
  • 第二轮通知 Secondaries 提交写入操作。

如果 Primary 挂了，某些 Secondaries 可能错过了 Primary 发送的最后几条更新消息。这将导致剩余的 Secondaries 拥有略微不同的副本。在恢复操作之前，新的 Primary 应确保所有 Secondaries 拥有完全相同的副本。

由于客户端在怀疑出现问题时会重新发送请求，Primary 需要过滤掉已经执行过的操作。

客户端缓存了数据块的位置，并且可能向持有过时副本的 chunkserver 发送读取请求。GFS 需要一种方式来确保这种读取不会成功。

#参考

  • The Google File System
  • GFS —— 取舍的艺术