Andrewei's Blog
0%

Google File System 总结

发表于 更新于

本文是博主学习 MIT6.824 课程的学习笔记，其中会总结论文知识点并加入自己的理解，内容可能与论文原文有出入，想要了解细节的读者可以阅读论文原文或者学习 MIT6.824课程。

The Google File System

GFS MIT Video

简介

Google File System 简称 GFS 是 Google 设计并实现的一个面向数据密集型应用的、可伸缩的分布式文件系统。

GFS 的设计基于以下使用场景:

  1. 运行在廉价的日用硬件上，组件失效是常态事件。因此，系统必须具有持久的监控、错误侦测、容错以及自动恢复的功能。
  2. 以存储大文件（100MB 到 数GB）为主，同时要支持小文件，但是不需要针对小文件做优化。
  3. 支持两种读操作：大规模的流式读取（数百KB，或者一次读取 1MB 甚至更多）和小规模的随机读取（在任意位移上读取 几个KB）。
  4. 支持两种写操作：大规模的、顺序的对文件的追加和小规模的任意位置写入（不必高效）。
  5. 必须支持高效的多客户端同时并行追加数据到同一个文件的语义（Google 的场景下，GFS 中存储的文件通常用于 生产者-消费者 队列，或者其他多路文件合并操作）
  6. 大吞吐量优先于低延时

GFS 架构

图一：GFS 结构图

一个 GFS 集群包含一个单独的 Master 节点和多台 Chunk Server，并且同时被多个（几百个）客户端同时访问。

单独的 Master 节点并不是集群中只有一个可以成为 Master 的服务器，只是说在任意时刻只能有一个节点的角色为 Master，当这个节点挂掉时，会有新的 Master 节点起作用。

GFS 存储的文件都被分割成固定大小的 Chunk，每个 Chunk 在被创建的时候，会由 Master 分配一个不变的、全球唯一的 64 位 Chunk 标识。Chunk Server把 Chunk 以 linux 普通文件的形式保存在本地硬盘上，并且根据指定的 Chunk 标识和字节范围来读写块数据。同时为了可靠性，每个块会被复制多份，存储在不同的 Chunk Server上（通常是 3 份）

副本同时可以在大规模读取的时候起到负载均衡的作用

Master 节点管理着整个文件系统，主要涉及以下几个方面：

  1. 整个文件系统的元数据：包括命名空间（namespace）、访问控制信息（access control information）、文件与Chunk Server的映射关系以及每个 Chunk 的当前位置（the current locations of chunks）

  2. 文件系统的动态信息：Chunk 租用管理（chunk leases management）、孤儿 Chunk 的回收（garbage collection of orphaned chunks）以及Chunk 在 Chunk Server 之间的迁移

  3. 使用心跳周期性与每个 Chunk Server通信，发送至指令到各个 Chunk Server并接受 Chunk Server的状态信息

  4. 接受并回应客户端的操作请求

GFS 客户端代码实现了 GFS 文件系统的 API 接口函数调用、与 Master 节点和 Chunk Server通信以及数据进行读写等操作。

鉴于整个系统只有一个 Master 节点，为了防止 Master 节点成为瓶颈，客户端与 Master 节点的通信只获取元数据，所有的数据操作都是客户端直接和 Chunk Server进行交互的，同时客户端会将从 Master 拿到的元数据缓存一段时间。另外无论是客户端还是 Chunk Server都不需要缓存文件数据。

元数据

Master 服务器存储 3 种主要类型的元数据：

  1. 文件和 Chunk 的命名空间（namespace）
  2. 文件和 Chunk 的映射关系
  3. 每个 Chunk 的存放位置

上述元数据信息都保存在 Master 服务器的内存中，这使得 Master 节点对元数据变更变得极为容易，Master 可以在后台简单、高效的周期性扫描自己保存的全部状态信息，以实现 Chunk 垃圾收集、Chunk Server 失效时重新复制数据、Chunk Server 的负载均衡以及磁盘使用情况统计等。唯一有风险的是，元数据放在内存中可能会使得集群能管理的 Chunk 数会受限于 Master 的内存大小。但从论文来看，Google 并没有遇到这个问题，因为 64MB的 Chunk 只会占用 64B 的 Master 内存，并且在 Google 的场景中，大多数 Chunk 都是被填充满的。

每个 Chunk 被设计为 64MB 大小，主要出于一下考虑：

  1. 减少了元数据的数量从而减少了客户端与 Master 的交互频率（每个 Chunk 覆盖了更多的数据范围 && 客户端可以缓存更多数据的元数据信息）
  2. 每个 Chunk 覆盖较大的数据范围，客户端可以对同一个 Chunk 进行比较多的操作，可以通过 TCP 长连接与 Chunk Server交互，减少网络开销
  3. 减少元数据的数量可以减少 Master 的内存压力

但相对的，Chunk 较大也会引入一些问题，比如小文件只有一个 Chunk，对其操作时会造成热点。对于这个问题，论文中给出的缓解方式为：

  1. 这样的 Chunk 配置较多的副本，分担读取压力
  2. 尽可能不要同时对这个 Chunk 进行操作

或者可以实现读取时，客户端之间可以共享数据。

为了防止 Master 节点崩溃造成状态丢失，对于 文件和Chunk的命名空间 以及 文件和Chunk的映射关系 这两种元数据，会按照修改时间以操作日志(Operation Log)的形式持久化在本地硬盘，同时复制到其他 Master 节点。并且对于一个更改上述元数据的客户端请求，只有当本地和其他 Master 节点都把 操作日志 持久化到硬盘后，才会响应客户端。

Master 会在 操作日志 增长到一定量时，对系统状态做一次 Checkpoint，当 Master 启动时，只需要从最近的 Checkpoint 状态启动并重演 Checkpoint 之后有限的 操作日志就可以恢复到奔溃前的状态。

每个 Chunk 的存放位置 并不会被持久化，Master 服务器只是在启动的时候轮询 Chunk服务器 以获取这些信息，并且会周期性的通过心跳信息监控 Chunk Server 的状态。这种设计简化了当 Chunk Server 加入集群、离开集群、更改名称、失效以及重启时的数据变更问题。

一致性模型

GFS 提供了相对宽松的一致性，在支撑高度分布式的同时，保持了相对简单切容易实现的优点。

一致性保障机制

由于整个文件系统的元数据都存储在 Master 节点的内存中，所以文件命名空间的修改（比如文件的创建）可以通过 Master 的锁来保障原子性和正确性。同时，Master 节点的 操作日志 定义了这些操作在全局的顺序。

GFS 定义了一些概念，来标识文件修改后的状态：

  1. 如果所有的客户端，无论从哪个副本（replica）读取，读到的数据都相同，我们称 文件region 是一致的（Consistent）
  2. 相反，如果存在任意两个客户端，从某些副本（replica）读取，读到的数据不相同，我们称 文件region 是不一致的（Consistent）
  3. 对于一致的文件 region，如果每个客户端都能读取到它上次修改的内容，我们称 文件region 是 确定的（Defined）

这里的一致、确定 是从客户端的角度来理解的：

  1. 10 个客户端同时 GET 修改后的数据发现每个客户端获取到的数据都相同，就称为 一致
  2. 10 个客户端同时执行了 不同 的修改操作（例如，修改的是文件的不同部分，不会发生重叠），然后 GET 修改后的数据，发现每个客户端获取到的数据都相同（此时已经可以称为 一致 状态），且跟自己修改后的预期相同，故客户端可以 确定 自己的修改成功了，故称之为 确定的。
  3. 10 个客户端同时执行了 不同 的修改操作（例如，修改的是文件的相同部分，会发生重叠），然后 GET 修改后的数据，发现每个客户端获取到的数据都相同（此时已经可以称为 一致 状态），但是客户端发现获取到的数据跟自己修改后的预期不同，此时客户端的角度无法知道结果是否正确，故称之为不确定 状态。

对于数据修改后的 文件region，它的状态取决于操作类型、成功与否以及是否同步修改，下面我们结合论文给出的表格，以及论文原文描述分情况讨论几种情况。

对于 region 的定义论文中没有提到，猜测是修改操作涉及到的文件范围

表1：文件region修改后的状态

随机写（Write）

A write causes data to be written at an application-specified file offset.

由论文原文可知，随机写是由客户端来指定写入位置的，所以无论是否存在重试，写入的位置和内容都相同。

  1. 并行写入

    由论文 3.1 Leases and Mutation Order 一节可知，并行写入时，写入的顺序是由 Chunk 的 Master 来指定的，并且所有的副本写入顺序都一致。所以只要最后都成功写入，Chunk 的所有副本的内容就一定是相同的，即状态为 一致的。但由于各个客户端写入的范围可能存在重叠，故会存在 不确定 的情况。

    例如某个 Chunk 的原始内容如下

    位置 0 1 2 3 4 5 6 7 8 9
    内容 a b c d e f g h i j

    此时 客户端1 需要改写 [0, 3] 范围内的数据为 0，客户端2 需要改写 [2, 5] 范围内的数据为 1。

    1. 若写入顺序为 客户端1 、客户端2 ，则写入完成后，Chunk 内容变为
    位置 0 1 2 3 4 5 6 7 8 9
    内容 0 0 1 1 1 1 g h i j
    1. 若写入顺序为 客户端2、客户端1，则写入完成后，Chunk 内容变为
    位置 0 1 2 3 4 5 6 7 8 9
    内容 0 0 0 0 1 1 g h i j

    除了上述讨论的情况外，论文 3.1 Leases and Mutation Order 一节中还提到，如果某次写操作横跨多个 Chunk，则会将这个写操作分开，分别在每个 Chunk 中进行。由于写入顺序的控制在 Chunk 级别，所以有可能 Chunk1 的写入顺序为 客户端1、客户端2，而 Chunk2 中的顺序为 客户端2 、客户端1。这种情况会更加糟糕。

  2. 顺序成功

    顺序成功意味着同一时刻，只有一个客户端在写入，写入完成后可以读取到自己预期的数据，即状态为 确定的

  3. 写入失败

    当 Chunk 的某些副本写入成功，但是另外一些副本写入失败时，就会陷入 不一致 状态。

追加写（Append Records）

A record append causes data (the “record”) to be appended atomically at least once even in the presence of concurrent mutations, but at an offset of GFS’s choosing (Section 3.3). (In contrast, a “regular” append is merely a write at an offset that the client believes to be the current end of file.) The offset is returned to the client and marks the beginning of a defined region that contains the record. In addition, GFS may insert padding or record duplicates in between. They occupy regions considered to be inconsistent and are typically dwarfed by the amount of user data.

由论文原文可知，GFS 为追加写操作的几个特点：

  1. 追加写操作为 原子性 操作（即不会出现交叉写的情况）
  2. 追加写操作的 offset 由 GFS 指定（准确的说是被选为 primary 的 Chunk 指定）
  3. 追加写操作失败时，GFS 会重试，此时 GFS 可能会插入一些 padding 或者会有一些重复数据

我们仍然举例来说明此时可能出现的状态，由于写操作的 原子性，我们将 并发追加 和 顺序追加 合并在一起讨论

  1. 并发成功、顺序成功

    由于追加写为原子性的，所以客户端数据不可能出现重叠，即每个客户端在写入之后都能获取到预期的数据，是 确定的 状态。

    当客户端出现重试操作时，考虑下面的情况，某个 Chunk 共存在 3 个副本

    Chunk1（primary）

    位置 0 1 2
    内容 a b c

    Chunk2

    位置 0 1 2
    内容 a b c

    Chunk3

    位置 0 1 2
    内容 a b c

    此时，客户端请求追加写操作，追加内容为 123，如果 Chunk1 成功但是 Chunk2 失败了，则 Chunk 内容变为

    Chunk1（primary）

    位置 0 1 2 3 4 5
    内容 a b c 1 2 3

    Chunk2

    位置 0 1 2 3 4
    内容 a b c 1 2

    Chunk3

    位置 0 1 2
    内容 a b c

    客户端感知到错误后，开始发起重试，由于追加写的 offset 由 primary 指定，所以 Chunk1将会指定此次追加写操作从 offset = 6 开始。Chunk2 和 Chunk3 会填充特殊字符使其文件尾 offset与 primary 一致。

    Chunk1（primary）

    位置 0 1 2 3 4 5 6 7 8
    内容 a b c 1 2 3 1 2 3

    Chunk2

    位置 0 1 2 3 4 5 6 7 8
    内容 a b c 1 2 - 1 2 3

    Chunk3

    位置 0 1 2 3 4 5 6 7 8
    内容 a b c - - - 1 2 3

    对于客户端来说，GFS 会使用一些检查和重复校验，使得客户端获取到的数据为 确定的（祥见论文 2.7.2 Implications for Applications 小节）。

    但是对于真实的 Chunk 副本来说，确实出现了 不一致。

  2. 写入失败

    写入失败同随机写入一样，会造成 不一致 的状态。

程序实现

基于 GFS 的特点，GFS 建议使用它的应用程序尽量使用以下技术来获得最佳实践：

  1. 尽量采用追加写入操作
  2. Checkpoint
  3. 自验证写入操作
  4. 自标识记录

在追加写入所有数据之后，应用程序自动将文件改名为一个永久保存的文件名，或者周期性的作 Checkpoint，记录成功写入了多少数据。 Checkpoint 文件可以包含程序级别的校验和。Readers 仅校验并处理上个 Checkpoint 之后产生的文件内容，这些文件内容的状态一定是已定义的。这个方法满足了我们一致性和并发处理的要求。追加写入比随机位置写入更加有效率，对应用程序的失败处理更具有弹性。 Checkpoint 可以让 Writer 以渐进的方式重新开始，并且可以防止 Reader 处理已经被成功写入，但是从应用程序的角度来看还并未完成的数 据。Readers 使用下面的方法来处理偶然性的填充数据和重复内容。Writers 在每条写入的记录中都 包含了额外的信息，例如 Checksum，用来验证它的有效性。Reader 可以利用 Checksum 识别和抛弃额外的填充数据和记录片段。如果应用不能容忍偶尔的重复内容，可以用记录的唯一标识符来过滤它们。

GFS 中的常见操作

读取

图一：GFS 结构图

客户端在读取 GFS 中的数据时，过程如下

  1. 客户端把文件名称和指定的字节偏移，根据 Chunk 的大小，转换成文件的 Chunk 标识
  2. 客户端把文件名称和 Chunk 标识发送给 Master 节点
  3. Master 节点将相应 Chunk 标识的副本位置信息返回给客户端
  4. 客户端以文件名称和 Chunk 标识为 key 缓存这些信息
  5. 客户端发送读取请求（其中包含了 Chunk 标识和字节范围）到最近的 Chunk 副本处。

租约（lease）

GFS 使用租约 （lease）机制来保持多个副本间变更顺序的一致性。Master 节点为 Chunk 的某个副本建立一个租约，这个副本被称为 主Chunk（primary）。主Chunk 对 Chunk 的所有更改操作进行排序，所有的副本都遵从这个序列进行修改操作。因此，修改操作全局的顺序首先由 Master 节点选择的租约的顺序决定，然后由租约中 主Chunk 分配的序列号决定。

租约可以减小 Master 节点的负担，并且租约的默认有效时间为 60s，在此期间 主Chunk 可以通过在与 Master 的心跳中附加信息来申请延长租期。Master 也可以提前取消租约，亦或者在 主Chunk失联且租约过期后，与其他的 Chunk 副本签订新的租约。

写入操作

图2：写入和数据流

写入操作的过程如下：

  1. 客户机向 Master 节点询问哪一个 Chunk Server持有当前的租约，以及其它副本的位置。如果没有一个 Chunk 持有租约，Master 节点就选择其中一个副本建立一个租约（这个步骤在图上没有显示）。
  2. Master 节点将 主Chunk 的标识符以及其它副本（又称为 secondary副本、二级副本）的位置返回给客户端。客户机缓存这些数据以便后续的操作。只有在 主Chunk 不可用，或者 主Chunk 回复信息表明它已不再持有租约的时候，客户端才需要重新跟 Master 节点联系。
  3. 客户端把数据推送到所有的副本上。客户端可以以任意的顺序推送数据。Chunk Server接收到数据并保存在它的内部 LRU缓存 中，一直到数据被使用或者过期交换出去。由于数据流的网络传输负载非常高，通过分离数据流和控制流，我们可以基于网络拓扑情况对数据流进行规划，提高系统性能，而不用去理会哪个 Chunk Server保存了 主Chunk。
  4. 当所有的副本都确认接收到了数据，客户端发送写请求到 主Chunk 服务器。这个请求标识了早前推送到所有副本的数据。主Chunk 为接收到的所有操作分配连续的序列号，这些操作可能来自不同的客户端，序列号保证了操作顺序执行。它以序列号的顺序把操作应用到它自己的本地状态中。
  5. 主Chunk 把写请求传递到所有的二级副本。每个二级副本依照 主Chunk 分配的序列号以相同的顺序执行这些操作。
  6. 所有的二级副本回复 主Chunk，它们已经完成了操作。
  7. 主Chunk 服务器回复客户端。任何副本产生的任何错误都会返回给客户端。在出现错误的情况下，写入操作可能在 主Chunk 和一些二级副本执行成功。（如果操作在主Chunk 上失败了，操作就不会被分配序列号，也不会被传递。）客户端的请求被确认为失败，被修改的region处于不一致的状态。客户端代码通过重复执行失败的操作来处理这样的错误。在从头开始重复执行之前，客户机会先从步骤（3）到步骤（7）做几次尝试。

如果写入的数据量很大，跨域了多个 Chunk ，客户端会将其分成多个写操作。

由于数据推送需要消耗大量的网络带宽，客户端在推送数据的时候，会沿着一个 Chunk Server链顺序的推送，而不是以其它拓扑形式分散推送（例如，树型拓扑结构）。线性推送模式下，每台机器所有的出口带宽都用于以最快的速度传输数据，而不是在多个接受者之间分配带宽。

同时，利用基于 TCP 连接的、管道式数据推送的方式来让延长最小化，Chunk Server接收到数据后，马上开始向前推送。

追加写入

追加写入与上文提到的覆盖写入过程基本一致：

  1. 客户端只需要指定要追加的数据，写入的偏移量由 GFS 来决定
  2. 客户端把数据推送完毕后，向 主Chunk 发送写入请求
  3. 主Chunk 会首先检查当前的追加操作是否超出了 Chunk 的最大尺寸（64MB）
    1. 如果超出则 主Chunk 会首先将当前的 Chunk 填充到最佳尺寸，然后通知所有 二级副本 做相同的操作，最后回复客户端要求其对下一个 Chunk 继续进行追加操作
    2. 如果没有超出，则 主Chunk 将数据追加到自己的副本内，再通知 二级副本 写在跟 主Chunk 相同的位置上

关于追加失败的场景，前面讲 一致性模型 时已经提到，不再在此赘述。

快照

快照使用 Copy-on-Write 技术，当 Master 节点收到一个快照请求时：

  1. 取消作快照文件的所有租约。这样就保证了，后续与这些文件有关的操作，都必须先请求 Master 节点（参考前面提到的写入流程）
  2. 等租约撤回后，Master 首先会将这个操作以日志的形式记录到磁盘，然后开始在内存中复制相关文件或者目录的元数据，这些元数据指向相同的 Chunk
  3. 当客户端第一次查询 Chunk C 的 primary 以及副本位置，想要做写入操作时，Master 发现指向 Chunk C 的引用计数超过了 1。此时 Master 不会马上响应客户端的请求，而是首先创建一个 Chunk C 的新 handle，并要求每个拥有 Chunk C 的服务器在本地复制一个相同的 Chunk C，之后在新创建出的 Chunk C 中选择一个签订租约，并将信息返回给客户端

命名空间和锁

为了能允许客户端并发操作，Master 会使用命名空间上的锁来保证操作的正确性。

与传统的文件系统不同，GFS 没有维护一个目录树，也不支持文件或者目录的链接（unix 中的符号链接）。在逻辑上，GFS 的名称空间就是一个全路径和元数据映射关系的查找表。利用前缀压缩，这个表可以高效的存储在内存中。在存储名称空间的树型结构上，每个节点（绝对路径的文件名或绝对路径的目录名）都有一个关联的读写锁。

每个 Master 节点的操作在开始之前都要获得一系列的锁。通常情况下，如果一个操作涉及 /d1/d2/…/dn/leaf，那么操作首先要获得目录 /d1，/d1/d2，…，/d1/d2/…/dn 的读锁，以及 /d1/d2/…/dn/leaf 的读写锁。注意，根据操作的不同，leaf 可以是 一个文件，也可以是一个目录。

为了优化锁占用的内存，读写锁采用惰性分配的方式，且不再使用的时候会被及时回收。

锁的获取也要依据一个全局一致的顺序来避免死锁：首先按名称空间的层次排序，在同一个层次内按字典顺序排序。

副本

位置

副本位置的选择主要遵循两个目标：

  1. 最大化数据可靠性和可用性
  2. 最大化网络带宽利用率

而仅仅在多台机器上存储副本只能保证硬盘损坏或者机器失效带来的影响，以及最大化每台机器的带宽利用率。所以必须要在多个机架见分布存储 Chunk 副本。

创建、复制和负载均衡

除去读写之外，副本主要还有三个操作：创建、重新复制和负载均衡（迁移）

创建

创建副本时，要选择在什么地方放置空的副本，Master 在选择时主要考虑下面几个因素：

  1. 优先考虑硬盘使用率低于平均水平的服务器
  2. 保证每个服务器上最近创建的 Chunk 不要过多，因为 Chunk 创建意味着接下来会有大量的写入和查询。
  3. 如上文所说，倾向于分布在不同的机架上

复制

当 Chunk 副本由于以下几个可能的原因，导致副本数量小于用户指定的复制因数的时候，Master 节点就会重新复制它：

  1. Chunk Server不可用
  2. Chunk Server报告它所存储的一个副本损坏
  3. Chunk Server的一块磁盘不可用
  4. Chunk 副本的复制参数被增加

当多个 Chunk 需要被复制时，优先级会考虑以下因素

  1. 当前副本数与复制因数的差值，差值越大优先级越高
  2. 优先复制未被删除的 Chunk （删除是惰性的，会被定时回收，下文有介绍）
  3. 优先复制会阻塞客户端查询处理流程的

复制时， Master 会 “命令” 拥有相应 Chunk 副本的 Chunk Server上克隆一个副本出来，并按照 Chunk 创建时的策略选择副本位置。

为了防止克隆时产生的流量影响客户端的操作，Master 对整个集群和每个 Chunk Server上同时进行克隆操作的数量做了限制，并且 Chunk Server通过调节它对源 Chunk Server读请求的频率来限制它用于克隆操作的带宽。

重新负载均衡

Master 服务器周期性地检查当前的副本分布情况，然后移动副本以便更好的利用硬盘空间、更有效的进行负载 均衡。而且在这个过程中，Master 服务器逐渐的填满一个新的 Chunk Server，而不是在短时间内用新的 Chunk 填满它，以至于过载。新副本的存储位置选择策略和上面讨论的相同。另外，Master 节点必须选择哪个副本要被移走。通常情况，Master 节点移走那些剩余空间低于平均值的 Chunk 服务 器上的副本，从而平衡系统整体的硬盘使用率。

垃圾回收

GFS 使用惰性删除策略来处理文件删除操作。

文件删除的流程为：

  1. Master 节点立即将删除操作写入操作日志中
  2. 把文件名改为一个包含删除时间戳的隐藏的名字
  3. 当 Master 对文件系统命名空间做常规扫描时删除所有三天前的隐藏文件

在真正删除隐藏文件之前，被客户端删除的文件都可以通过更改文件名的方式回滚删除操作。文件的元数据也是在删除隐藏文件时被删除的。

Master 在对 Chunk 名字空间做类似的常规扫描时，Master 节点找到孤儿 Chunk（不被任何文件包含的 Chunk）并删除它们的元数据。 Chunk Server在和 Master 节点交互的心跳信息中，报告它拥有的 Chunk 子集的信息，Master 节点回复 Chunk Server哪些 Chunk 在 Master 节点保存的元数据中已经不存在了。Chunk Server可以任意删除这些 Chunk 的副本。

惰性删除的优势：

  1. 对于组件失效是常态的大规模分布式系统，垃圾回收方式简单可靠。Chunk 可能在某些 Chunk Server创建成功，某些 Chunk Server上创建失败，失败的副本处于无法被 Master 节点识别的状态。副本删除消息可能丢失，Master 节点必须重新发送失败的删除消息，包括自身的和 Chunk服务器的 。 垃圾回收提供了一致的、可靠的清除无用副本的方法。
  2. 垃圾回收把存储空间的回收操作合并到 Master 节点规律性的后台活动中。因此，操作被批量的执行，开销会被分散。另外，垃圾回收在Master 节点相对空闲的时候完成。这样 Master 节点就可以给那些需要快速反应的客户机请求提供更快捷的响应。
  3. 延缓存储空间回收为意外的、不可逆转的删除操作提供了安全保障。

当然，延迟回收可能会造成空间的浪费，特别是当磁盘空间紧张或者客户端频繁创建、删除新文件的时候。对于这个问题，可以通过显式的再次删除一个已经被删除文件的方式来加速回收空间。另外 GFS 允许为命名空间的不同部分设置不同的复制参数和回收策略，比如可以指定某些目录下不做复制，删除时立即回收空间。

失效副本检测

Master 在每次跟 Chunk 签订租约时增加 Chunk 版本号，然后通知最新副本，只有当 Master 和所有副本都将新的版本号持久化存储后，才会响应客户端的请求。

当一个 Chunk Server在更新版本号时失效，在它重启向 Master 报告当前副本状态时，Master 就会检测出它包含过期 Chunk。相反如果 Master 发现他记录的版本号比自己要高，则会更新自己的版本号到最新版本。（此处 Master 会更新自己的 Chunk 吗？）

客户端请求 Master 节点 Chunk 信息时，对于已经过期的 Chunk，Master 会直接认为不存在。另外，Master 节点在通知客户端哪个 Chunk Server持有租约、或者指示 Chunk Server从哪个 Chunk Server进行克隆时，消息中都附带了 Chunk 的版本号。客户端或者 Chunk Server在执行操作时都会验证版本号以确保总是访问当前版本的数据。

容错和诊断

由于 GFS 在设计之初的目标为运行在廉价的日用硬件上，组件的频繁失效是一种常态，所以容错和诊断是 GFS 设计时非常重要的一部分。

高可用

GFS 使用两条简单的策略保证系统的高可用性：快速恢复和复制。

快速恢复

Master 节点和 Chunk Server 的状态都保存在本地，无论是正常的重启还是异常的重启都可以快速的恢复到之前的状态。

Master 的复制

Master 的所有操作日志和 Checkpoint 文件都被复制到多台机器上。并且凡是涉及更改 Master 状态的操作，一定会确保操作日志写入到 Master 和复制机器的磁盘上才会响应客户端的请求。客户端使用规范的别名（例如 gfs-master）访问 Master，一旦当前 Master 节点不可用，GFS 系统外部的监控进程会在其它的存有完整操作日志的机器上启动一个新的 Master进程，并将别名指向新的 Master 节点。

GFS 中还有一些 Shadow Master 节点，他们在 Master 宕机期间可以临时提供文件系统的只读访问，由于 Shadow Master 的元数据比 Master 节点更新慢（通常不到 1s），所以通过 Shadow Master 读取文件内容时，有可能读取到过期数据。

Shadow Master 服务器为通过读取正在进行操作的日志副本来保持自身状态是最新的，它依照和主 Master 服务器完全相同的顺序来更改内部的数据结构。Shadow Master 服务器在启动的时候也会从 Chun Server 轮询数据（之后定期拉数据），数据中包括了 Chunk 副本的位置信息；Shadow Master 服务器也会定期和 Chunk Server 通信以确定它们的状态。在主 Master 服务器因创建和删除副本导致副本位置信息更新时，Shadow Master 服务器才和主 Master 服务器通信来更新自身状态。

Chunk 的复制

每个 Chunk 都被复制到不同机架上的不同的 Chunk Server 上。用户可以为文件命名空间的不同部分设定不同的复制级别。缺省是 3。当有Chunk Server 离线了，或者通过 Chksum校验 发现了已经损坏的数据，Master 节点通过克隆已有的副本保证每个 Chunk 都被完整复制。

数据完整性

Chunk Server 会把每个 Chunk Replica 切分为若干个 64KB 大小的块，并为每个块计算 32 位校验和。和 Master 的元数据一样，这些校验和会被保存在 Chunk Server 的内存中，每次修改前都会用先写日志的形式来保证可用。当 Chunk Server 接收到读请求时，Chunk Server 首先会利用校验和检查所需读取的数据是否有发生损坏，如此一来 Chunk Server 便不会把损坏的数据传递给其他请求发送者，无论它是客户端还是另一个 Chunk Server。发现损坏后，Chunk Server 会为请求发送者发送一个错误，并向 Master 告知数据损坏事件。接收到错误后，请求发送者会选择另一个 Chunk Server 重新发起请求，而 Master 则会利用另一个 Replica 为该 Chunk 进行重备份。当新的 Replica 创建完成后，Master 便会通知该 Chunk Server 删除这个损坏的 Replica。

当进行数据追加操作时，Chunk Server 可以为位于 Chunk 尾部的校验和块的校验和进行增量式的更新，或是在产生了新的校验和块时为其计算新的校验和。即使是被追加的校验和块在之前已经发生了数据损坏，增量更新后的校验和依然会无法与实际的数据相匹配，在下一次读取时依然能够检测到数据的损坏。在进行数据写入操作时，Chunk Server 必须读取并校验包含写入范围起始点和结束点的校验和块，然后进行写入，最后再重新计算校验和。

除外，在空闲的时候，Chunk Server 也会周期地扫描并校验不活跃的 Chunk Replica 的数据，以确保某些 Chunk Replica 即使在不怎么被读取的情况下，其数据的损坏依然能被检测到，同时也确保了这些已损坏的 Chunk Replica 不至于让 Master 认为该 Chunk 已有足够数量的 Replica。

FAQ

MIT 6.824 的课程材料中给出了和 GFS 有关的 FAQ，以下是相关问答的翻译。

Q：为什么原子记录追加操作是至少一次（At Least Once），而不是确定一次（Exactly Once）？

要让追加操作做到确定一次是不容易的，因为如此一来 Primary 会需要保存一些状态信息以检测重复的数据，而这些信息也需要复制到其他服务器上，以确保 Primary 失效时这些信息不会丢失。在 Lab 3 中你会实现确定一次的行为，但用的是比 GFS 更复杂的协议（Raft）。

Q：应用怎么知道 Chunk 中哪些是填充数据或者重复数据？

要想检测填充数据，应用可以在每个有效记录之前加上一个魔数（Magic Number）进行标记，或者用校验和保证数据的有效性。应用可通过在记录中添加唯一 ID 来检测重复数据，这样应用在读入数据时就可以利用已经读入的 ID 来排除重复的数据了。GFS 本身提供了 library 来支撑这些典型的用例。

Q：考虑到原子记录追加操作会把数据写入到文件的一个不可预知的偏移值中，客户端该怎么找到它们的数据？

追加操作（以及 GFS 本身）主要是面向那些会完整读取文件的应用的。这些应用会读取所有的记录，所以它们并不需要提前知道记录的位置。例如，一个文件中可能包含若干个并行的网络爬虫获取的所有链接 URL。这些 URL 在文件中的偏移值是不重要的，应用只会想要完整读取所有 URL。

Q：如果一个应用使用了标准的 POSIX 文件 API，为了使用 GFS 它会需要做出修改吗？

答案是需要的，不过 GFS 并不是设计给已有的应用的，它主要面向的是新开发的应用，如 MapReduce 程序。

Q：GFS 是怎么确定最近的 Replica 的位置的？

论文中有提到 GFS 是基于保存 Replica 的服务器的 IP 地址来判断距离的。在 2003 年的时候，Google 分配 IP 地址的方式应该确保了如果两个服务器的 IP 地址在 IP 地址空间中较为接近，那么它们在机房中的位置也会较为接近。

Q：Google 现在还在使用 GFS 吗？

Google 仍然在使用 GFS，而且是作为其他如 BigTable 等存储系统的后端。由于工作负载的扩大以及技术的革新，GFS 的设计在这些年里无疑已经经过大量调整了，但我并不了解其细节。HDFS 是公众可用的对 GFS 的设计的一种效仿，很多公司都在使用它。

Q：Master 不会成为性能瓶颈吗？

确实有这个可能，GFS 的设计者也花了很多心思来避免这个问题。例如，Master 会把它的状态保存在内存中以快速地进行响应。从实验数据来看，对于大文件读取（GFS 主要针对的负载类型），Master 不是瓶颈所在；对于小文件操作以及目录操作，Master 的性能也还跟得上（见 6.2.4 节）。

Q：GFS 为了性能和简洁而牺牲了正确性，这样的选择有多合理呢？

这是分布式系统领域的老问题了。保证强一致性通常需要更加复杂且需要机器间进行更多通信的协议（正如我们会在接下来几门课中看到的那样）。通过利用某些类型的应用可以容忍较为松懈的一致性的事实，人们就能够设计出拥有良好性能以及足够的一致性的系统。例如，GFS 对 MapReduce 应用做出了特殊优化，这些应用需要的是对大文件的高读取效率，还能够容忍文件中存在数据空洞、重复记录或是不一致的读取结果；另一方面，GFS 则不适用于存储银行账号的存款信息。

Q：如果 Master 失效了会怎样？

GFS 集群中会有持有 Master 状态完整备份的 Replica Master；通过论文中没有提到的某个机制，GFS 会在 Master 失效时切换到其中一个 Replica（见 5.1.3 节）。有可能这会需要一个人类管理者的介入来指定一个新的 Master。无论如何，我们都可以确定集群中潜伏着一个故障单点，理论上能够让集群无法从 Master 失效中进行自动恢复。我们会在后面的课程中学习如何使用 Raft 协议实现可容错的 Master。

问题

除了 FAQ，课程还要求学生在阅读 GFS 的论文后回答一个问题，问题如下：

Describe a sequence of events that result in a client reading stale data from the Google File System

描述一个事件序列，使得客户端会从 Google File System 中读取到过时的数据

通过查阅论文，不难找到两处答案：由失效后重启的 Chunk Server + 客户端缓存的 Chunk 位置数据导致客户端读取到过时的文件内容（见 4.5 和 2.7.1 节），和由于 Shadow Master 读取到的过时文件元信息（见 5.1.3 节）。以上是保证所有写入操作都成功时客户端可能读取到过时数据的两种情况 —— 如果有写入操作失败，数据会进入不确定的状态，自然客户端也有可能读取到过时或是无效的数据。

总结

论文的第六章为 GFS 的 Benchmark ，第七章为 GFS 在生产环境使用时遇到的一些问题，本文没有总结，有兴趣的读者可以阅读论文原文。

基于 Google File System 开发的 HDFS 一直是分布式文件系统开源实现的首选。本篇论文与 Map Reduce 是大数据的开山之作，与 Big Table 并称为 Google 的三驾马车，是非常经典的论文，值得不断的学习和推敲。

参考资料

  1. GFS FAQ

  2. MIT 6.824（二）GFS的一致性模型

  3. Google File System 总结