The Google File System

GFS 是一个可扩展的分布式文件系统，用于大型分布式数据密集型应用上。它可以运行在便宜的普通硬件上，提供了高性能和一定的容错性。

GFS 与过去的分布式文件系统有很多相似之处，如性能、扩展性、可靠性和高可用性。但对 GFS 的设计是由我们对应用负载和技术环节的探索所驱动的，它与之前的文件系统还是有设计上的明显区别。

我们考虑下面一些设计分布式文件系统时的关键点：

• 首先，组件出错是一个普遍情况，而不是异常事件。我们几乎可以确定在一个大型文件系统中，有一部分机器不可用，一部分机器无法从错误中恢复。造成错误的原因可能有：

  • 应用程序或操作系统的 bug。
  • 人为错误。
  • 磁盘、内存、网络等的错误。
  • 等等。

  因此，实时监控、错误检测、容错设计、错误恢复是这个系统不可或缺的一部分。

• 其次，文件是巨大的。每个文件通常包含很多对象，例如网页文档。当我们经常使用由数十亿个对象组成的、大小达到许多个 TB 且依然在快速增长的数据集时，即使文件系统不拒绝这样的需求，我们也必须重新审视设计的假设和参数，例如 IO 操作和存储块的大小。

• 第三，大多数文件通过追加数据而不是覆盖数据来进行操作，文件的随机写事实上并不存在。这些文件写入后只用作读需求，且经常只是顺序读，各种数据共享这些属性。

  • 一些组成了数据仓库，用于供数据分析程序使用；
  • 一些是正在运行的程序连续产生的数据流；
  • 一些是档案资料；
  • 一些是存储在一台机器上并在另一台机器上处理的中间数据（如 MapReduce 的中间键值对）

  对于上述这种文件的处理，在客户端缓存数据块已经没有意义，而追加操作成为了性能优化和原子性保证的焦点。

• 第四，应用程序和文件系统 API 在设计上的协作提高了整个系统的灵活性，从而优化了整个系统。例如我们放松了 GFS 在一致性上的要求，这大大简化了文件系统，同时没有为应用程序引入额外的负担。我们还采用了原子性的追加操作，以此使多个用户可以同时对一个文件进行追加操作，但又不用带来额外的同步开销。

在 Google，多个 GFS 集群以不同的目的进行部署，最大的一个集群包含了超过 1000 个存储节点，300TB 以上的磁盘存储，能让数百个不同机器上的客户端进行连续的频繁访问。

2.1 设想

在根据需求设计文件系统的过程中，我们也会依照一些挑战和机会并存的假设进行设计。在第一节提到的一些事实的基础上，我们在细节上展示我们的一些假设：

• 系统是由许多廉价的、普通的、易出错的组件组成的。它必须有不间断的自我监控、探测、容错，以及组件错误状态的快速恢复。
• 系统存储了适量的大文件。我们期望有几百万的文件，每个文件通常是 100MB 或者更大。GB 级别的文件是很常见的，并且能够有效的进行管理。小文件必须被支持，但是我们无需对它们进行优化。
• 工作负载主要由两种读操作组成：大规模的流读取和小规模的随机读取。在大规模的流读取中，单个的操作通常会读几百 KB 的数据，更常见的是 1MB 或者更多的数据。来自同一个客户端的连续操作通常读取一个文件的一个连续范围。小规模的随机读取通常在任意的位置读取几 KB 的数据。追求性能的应用通过批处理和排序小规模的读操作，用以顺序的读取文件，而不是在读取过程中前后移动。
• 工作负载同样还有很多大量的、序列写操作，它们将数据追加到文件末尾。一般操作的大小与相应的读操作相近。一旦写入，文件将很少再次改变。在文件任意位置进行的小规模的写操作虽然是支持的，但效率很低。
• 系统必须是高效的，这里的高效是指有很多客户端能够同时对一个文件进行数据追加。我们的文件通常用于生产者-消费者队列或者多路合并。运行在不同机器上的数百个生产者，将并发地对一个文件进行数据追加，使用最小同步开销的原子化操作是很有必要的。这个文件可能会在以后被读取，或者正在同时被一个消费者读取。
• 持续的高带宽比低时延更重要。大多数目标应用更看重大量地、高效地处理数据，而很少有应用对单个的读或写操作有严格的响应时间要求。

2.2 接口

GFS 提供了常见的文件系统接口，文件被存放到目录中，并由路径名进行标识。我们支持常见的操作如create、delete、open、close、read以及write文件。

特殊地，GFS 还有**快照 snapshot **和 记录追加 record append 操作。

• 快照低开销地创建了一个文件或目录树的拷贝。
• 记录追加允许多个客户端同时向一个文件追加数据，并保证每个单独的客户端追加操作的原子性。可以用于实现多路结果合并和生产者-消费者队列，它们使很多客户端在不加锁的情况下可以同时进行追加操作。

2.3 架构

一个 GFS 集群由一个 Master 和多个块服务器 chunkservers 组成，可以被多个客户端访问。每个节点都是一个运行在 Linux 上的普通进程。

GFS 文件被划分为固定大小的块，每个块由一个不变的、全局唯一的 64bit 块句柄标识，它是由主节点在创建块时分配的。块服务器存储这些块并对其进行读写操作，为了提高可靠性，每个块都会在多个块服务器上进行复制。默认情况下，我们会存储三个副本，用户也可以对不同的命名空间设置不同的复制级别。

Master 存储了整个文件系统的元数据，包含命名空间、访问控制信息、文件到块的映射，以及块的当前位置等等。它也控制了一些系统层的行为，如块的租约管理，孤儿块的垃圾回收，以及块服务器之间的块迁移。Master 周期性地与每个块节点进行通信，通过心跳信息发送指令并收集块服务器状态。

GFS 客户端代码嵌入到应用中，实现了文件系统 API，代表客户端进行读写数据，与主节点和块服务器进行通信。客户端与主节点进行元数据的交互操作，而与数据相关的通信则直接与块服务器进行。

2.4 单一的主节点

单一的主节点简化了我们的设计，令主节点能够根据整体信息确定块的位置，以及进行复制决策。

由于主节点是单一的，我们必须最小化对主节点的读写操作，以保证它不会成为系统性能的瓶颈。客户端不会通过主节点读写数据，而只会向主节点询问需要与哪些块服务器进行联系。客户端会将主节点的答复缓存一段时间，并在后续直接和块服务器交互。

简单解释一下上图中的一个读操作交互。

1. 首先，使用固定的块大小，客户端将文件名和应用指定的字节便宜转换为文件块的索引。

2. 然后，它向主节点发送一个包含文件名和块索引的请求，主节点回复相应的块句柄和副本的位置。客户端使用文件名和块索引作为 Key 缓存这条信息。

3. 客户端向其中一个副本发送请求，大多数时候选择最近的那个。请求指定了块句柄和那个块的一个字节范围。后续客户端无需和主节点交互，除非缓存信息过期或文件被重新打开。

   事实上，客户端通常在一个请求中询问多个块，主节点的回复也会包含紧跟在请求块后面的块的信息，这在实际中往往可以在未来减少一些客户端-主节点通信。

2.5 块大小

块大小是设计的关键参数，我们选择 64MB，这要比一般文件系统的块要大许多。每个块副本在块服务器上被存储为一个普通的 Linux 文件，只有在需要时才扩大。

令块的大小很大的最大隐患在于内部碎片。GFS 使用惰性空间分配避免了因内部碎片带来的空间浪费。

采用大小比较大的块有以下几个重要优点：

• 它能减少客户端和主节点的交互次数，因为一个块的位置信息代表了更多的数据的位置。
• 由于大的块大小，客户端能在一个块上进行更多操作。这样可以通过与块服务器在一段时间内保持一个 TCP 长连接赖减少网络开销。
• 主节点可以存储更少的元数据，这样我们可以把元数据存储在内存中。所带来的好处在 2.6.1 节中讨论。

采用大小大的块也有下面这个缺点：

当大量客户端访问相同的文件时，存储这个块的块服务器会成为热点。显然当块的大小比较大，出现热点块服务器的概率也就更大。

在实际中，热点不是一个主要问题，因为我们的应用大多会顺序读取大量的包含多个块的文件。

但是当 GFS 第一次用于一个批处理序列系统时，还是发生了热点问题：一个可执行文件以单个块的形式写入 GFS，然后在数百台机器上同时启动。少量的存储这个文件的块服务器会由于数百台机器的同时访问而过载。我们通过以下两个手段解决这个问题：

• 提高可执行文件的复制因子 replication factor。让更多的块服务器存储这些热点数据。
• 令批处理序列系统和应用程序不同时， 而是交替启动。

一个可能的长期的解决方案是让客户端能从其他客户端读取数据。

2.6 元数据

主节点存储了三种主要类型的元数据：文件和块的命名空间，文件到块的映射，以及每个块副本的位置，所有元数据都保留在主节点的内存中。

命名空间，以及文件到块的映射，通过将操作记录存储在本地磁盘上的日志文件中得以永久保存，并在远程的机器上进行日志备份。使用日志使我们能够简单可靠地更新主节点状态，并且不用担心主节点崩溃造成的不一致。主节点不会永久保存块位置信息，而会在启动时，以及有新的块服务器加入集群时，询问每个块服务器的块信息。

2.6.1 内存中的数据结构

得益于元数据存放在内存中，主节点的操作非常快。它也能使主节点能够周期性地在后台简单有效的地浏览整个系统的状态。这个周期性的浏览操作用于实现块的垃圾回收、块服务器出错后的重复制，负载均衡和磁盘空间使用的块迁移，4.3 和 4.4 节会深入的讨论这些行为。

但将元数据放在内存中有一个潜在问题，即块的数量和将来整个系统的容量受到主节点的内存大小限制。但由于块的元数据大小实际很小，所以在实际中这不是一个严重的问题。更何况，即使需要为主服务器增加额外的内存，这个花费相比将元数据存放在内存中带来的简单性、可靠性、有效性和扩展性来说，也是很值得的。

2.6.2 块位置

主节点不会永久保留类似哪些块服务器含有一个给定的块的记录这样的信息。而是在启动时轮询块服务器获取这些信息。主节点可以将自己保持在最新状态，因为它控制所有块的放置，并且通过常规的心跳消息来监控块服务器的状态。

起初我们考虑在主节点永久地保存块位置信息，但后来发现在启动时向块服务器请求数据并在此后进行周期性更新要简单许多。这消除了当块服务器加入或离开集群、更改名字、出错、重启等异常发生时，保持主节点和块服务器同步的问题。在大型集群中这些问题发生得很频繁。

理解这种设计的另一个角度是：认识到块服务器对他的磁盘上最终存储或不存储某个块有最终的决定权。在主节点上维护这些信息的一致性视图是没有意义的，因为块服务器上的错误可能会导致块发生主服务器不能及时知悉的变动，例如块被删除或重命名等。

2.6.3 操作日志

操作日志包含了关键的元数据变化的历史记录，是 GFS 的核心。它不仅永久的记录了元数据，还能提供确定并发操作顺序的逻辑时间线服务。文件和块，连同它们的版本，都是由它们创建的逻辑时间唯一的、永久的进行标识的。

因为操作日志是临界资源，我们必须可靠的存储它，在元数据的变化持久化之前，客户端是无法看到这些操作日志的。否则，即使块本身保存下来，仍然有可能丢失整个文件系统或者客户端最近的操作。因此，我们将它复制到几个远程的机器上，并在将相应的操作刷新（flush）到本地和远程磁盘后再回复客户端。主节点会在刷新之前批处理一些日志记录，以此减少刷新和系统内复制对整个系统吞吐量的影响。

主节点通过重新执行操作日志来恢复状态。为了使启动时间尽量短，我们必须保持日志较小。当日志超过一个特定的大小时，主节点会检查它的状态。这样一来，以使它能够在足够小的代价下通过载入本地磁盘的最后一个检查点及之后的日志记录进行恢复。检查点是一个类似 B 树的数据结构，能够直接映射到内存中，并且在用于命名空间查询时无需额外的解析。这大大提高了恢复速度，增加了可用性。

因为创建检查点需要一定的时间，所以主节点的内部状态会被格式化，格式化的结果保证了新检查点的创建不会阻塞正在进行的修改操作。当主节点切换到新的日志文件时，GFS 通过另一个线程进行新检查点的创建。新检查点包括切换前所有的修改操作。对于一个有几百万文件的集群来说，创建一个新检查点大概需要1分钟。当创建完成后，它将写入本地和远程磁盘。

恢复只需要最近完成的检查点和在此之后的日志文件。老的检查点和日志文件能够被删除，但为了应对灾难性故障，我们会保留其中的一部分。检查点的失败不会影响恢复的正确性，因为恢复代码会探测并跳过未完成的检查点。

2.7 一致性模型

GFS 采用弱一致性模型，能很好的支持分布式应用，同时实现上比较简单。我们在这里将讨论 GFS 的一致性保障机制以及其对于应用的意义。我们也将着重描述了 GFS 如何维持这些一致性保障机制，但将一些细节留在了其它章节。

2.7.1 GFS的一致性保障机制

文件命名空间修改（如，创建文件）是原子性的。它们仅由主节点进行处理：命名空间锁保障了操作的原子性和正确性；主节点操作日志定义了这些操作的全局排序。

下图是经过修改后的文件区域状态表：

一个文件区域（region）在一个数据修改后的状态依赖于该修改的类型、成功或失败、以及是否为同步的修改。表1 总结了一次修改后的结果。

• 如果所有的客户端无论从哪些副本读取数据，得到的数据都是相同的，则这个文件区域为一致的 consistent。

• 在一个文件数据修改后，如果它是一致的，则这个区域已定义 defined，客户端将看到被写入的全部内容。

• 当一个修改完全没有受到并发写入操作的影响并成功时，那么影响到的区域已定义（隐含一致性） consistent interspersed undefined：所有的客户端将总会看到修改已经写入的内容。

  已定义的一定一致

• 并发成功的修改使区域处于一致，但未定义状态 consistent but undefined：所有的客户端将看到相同的数据，但是它可能不能反映出任意一个修改已写入的内容。

  • 通常，它是由一些来自多个修改操作的、混合的数据碎片组成的。

  一致的未必已定义，因为数据一致，但有些操作可能未成功或成功了一半

• 一个失败的修改会造成区域的不一致性（因此也没有被定义）inconsistent：不同的客户端在不同的时间可能会看到不同的数据。

我们将在后面描述我们的应用如何区分已定义和未定义的区域。这些应用程序不需要更深入的区分不同种类的未定义区域间的区别。

数据修改操作可能是写入 write 或记录追加 append 操作。一个写操作会将数据写入到应用指定的文件位置。偏移位置将被返回给客户端，并标明包含这个记录的已定义区间的开始位置。

• 如果有多个并发修改操作，一个记录追加操作会将数据（记录）至少一次的原子性的追加到文件，而具体的偏移量是由GFS选定的。
• 一个通常的追加操作仅仅是将数据追加到客户端认为是当前文件结尾的位置。

此外。GFS 能够在文件中插入数据或复制记录，这种情况下这些数据占据的文件区域被认为为非一致性的，但数量通常比用户数据总量要小很多。

在一系列成功的修改操作后，被修改的文件区域被保证为是已定义的，并且包含了最后一次修改操作写入的数据。GFS通过以下步骤完成上面行为：

1. 在所有副本上按相同的顺序执行一个块上的修改操作（3.1）
2. 使用版本号来检测并复制过期文件（4.5）
   • 这种过期可能是由于块服务器宕机而造成了部分修改丢失引起的。过期的副本不会再涉及修改操作，主节点也不会将该副本返回给客户端。它们会尽快的进行垃圾回收操作。

因为客户端缓存了块位置信息，它们可能会在位置信息更新前直接访问到一个过期的副本。这个问题出现的窗口是受缓存条目的超时时间和下一次文件的打开时间限制的，下一次文件打开时才会对这个文件的所有块信息的缓存进行清理。此外，由于大多数文件都是只能追加的，一个过期的副本经常会返回一个因过早结束而缺失数据的块，而不是过期的数据。当一个读客户端再次向主节点查询时，它将会立即获得块的当前位置信息。

在一个修改操作成功执行完一段时间后，组件的失效依然能损坏或删除数据。

• GFS通过在主节点和所有块服务器间定期的握手来标识失效的块服务器，并通过校验和来探测数据损坏（5.2）。
• 一旦问题被发现，数据将会尽快的利用有效副本进行恢复（4.3）。

只有在GFS反应之前的几分钟之内，一个块的所有副本都丢失，这个块才会彻底的丢失。在这种情况下，应用会接收到明确的错误码，而不是损坏的数据。

2.7.2 应用的实现

GFS 基于一些简单的技术实现了一个宽松的一致性模型：

• 依赖追加而不是覆盖。
• 检查点
• 写入时自验证。
• 自标识的记录。

这些技术在 GFS 的其他设计目标已经是必不可缺的，所以我们可以理解为一致性模型没有带来额外的负担。

实际中，我们所有的应用都是通过 append 而不是 overwriting 来修改文件。在一个典型的例子中，一个写操作生成一个文件，并从头到尾的写入数据。它将写入完数据的文件原子地重命名为一个不变的名字，或者周期性的创建检查点来记录有多少执行成功的写操作。

检查点也含有应用层的校验和。读操作仅验证并处理上一个检查点之后的文件区域，这个文件区域应该是已定义的。即使一致性和并发性问题，这个方法很好地满足了我们的需求。追加写操作比随机写操作更有效率，对应用的错误更有弹性。检查点允许写操作逐步地进行重启，并防止读操作处理已成功写入但在应用视角上没有处理完毕的文件数据。

在另一个典型应用中，许多写操作并行的追加一个文件，如进行结果的合并或者作为一个生产者-消费者队列。记录追加方式的“至少一次追加”的特性保证了每个写操作都有输出。

读操作使用下面的方法处理偶尔的填充数据和重复数据：

• 每个写操作写入的记录都包含了一些额外的信息，如校验和，以使这个记录能够被验证。
• 一个读操作能够通过校验和识别并丢弃额外的填充数据和记录碎片。
• 如果它不能忍受偶现的重复数据（如会导致非幂等的文体），它能通过记录中的唯一标识来进行过滤。这些标识通常应该可以用于命名相关的应用实体，如网页文档。
• 这些处理 I/O 的函数（除了删除重复数据）都在应用的共享库中，并且适用于 Google 其它的文件接口实现。

于是，相同序列下的记录，加上偶尔出现的重复数据，总是被分发到记录的读操作上。

我们设计这个系统时，需要最小化所有操作与 Master 的交互。依照这个前提，我们描述了客户端、Master 和块服务器之间如何进行交互，来实现数据的修改、原子记录追加，以及快照。

3.1 租约(Lease)和修改操作顺序

一个修改操作是一个改变了内容或块元数据的操作，如一个写操作或者一个追加操作。一个修改操作将在一个块的所有副本上进行。我们使用租约来保证一个修改在副本间的顺序一致性。

• Master 将一个块租约授予所有副本中的一个，这个副本成为 Primary。

  • 此时 Master 会找到一个持有最新版本数据的块作为 Primary，并将这个 Primary 自增后的新版本号作为最新的版本号，除非在后面发现其他块中有更新的版本号，那它会认为他在寻找 Primary 时出错了。正常情况下除非 Master 崩溃过，那么他一定知道最新的版本号是什么。

• Primary 对一个块的所有修改操作选择一个串行的顺序，所有的副本在执行修改时都按照这个顺序。

• 因此，全局的修改操作的顺序首先由 Master 选择的授予租约的顺序决定，然后由租约中Primary 分配的序列号决定。

租约机制的设计是为了最小化 Master 的管理开销，一个租约初始超时时间为 60 秒，然而，只要块正在被修改，Primary 就能向主节点请求租约延长（一般会被同意）。这些续约的请求和授予都包含在主节点和所有块服务器间定期交换的心跳消息中。

主节点有时会在租约到期之前尝试取消它（如，当 Master 想要禁止对一个被重命名的文件的修改操作时，就不再授予先前的 Primary 重命名操作的租约）。即使 Master 与 Primary 失去通信，它也能在前一个租约到期后安全的将一个新租约授予另一个副本。

下图是写操作的控制流和数据流：

在图2中，我们通过跟踪一个写操作的控制流，描述了整个过程：

1. 客户端询问 Master 哪个块服务器持有这个块的当前租约，以及这个块的其它副本位置。如果没有任何一个块服务器拥有租约，则 Master 选择一个副本并授予一个租约（没有在图上显示）。

2. Master 回复客户端 Primary 的标识，以及其它（Secondary）副本的位置。客户端缓存这些数据用于以后的修改操作。只有当 Primary 不可达或者接收到 Primary 不再持有租约时才需要再一次请求主节点。

3. 客户端将数据推送到所有的副本。一个客户端能够以任意顺序进行推送。每个块服务器将数据保存在内部的 LRU 缓存中，直到数据被使用或者过期被替换掉。

   通过对数据流和控制流的解耦，不管哪个块服务器为 Primary，我们都能够通过基于网络拓扑来调度数据流，以此提高性能。3.2节将进一步讨论。

4. 一旦所有的副本都确认接收到了数据，客户端将向 Primary 发送一个写请求。这个请求确定了之前的数据被推送到了所有副本。Primary 为接收到的所有修改操作分配连续的序列号，这些操作可能来自多个客户端，序列号提供了严格的序列化，应用按序列号顺序执行修改操作，进而改变自己的状态。

   前面只是推送了数据到块服务器的缓存中，此时才正式请求执行写入

5. Primary 将写请求发送到所有的 Secondary 副本上。每个 Secondary 副本按照 Primary 分配的相同的序列号顺序执行这些修改操作。

6. Secondary 副本回复 Primary，表示它们已经完成了所有的操作。

7. Primary 回复客户端。任意副本上的任意错误都将报告给客户端。在一些错误情况下，可能部分写操作已经在 Primary 和一些 Secondary 副本上执行成功。（如果失败发生在 Primary，它将不会分片一个序列号，并且不会被传递。）

   此时客户端的请求将被视为已经失败，而那些被修改的区域停留在不一致的状态上。我们的客户端代码通过重试失败的修改操作来处理这种错误。在从头开始重复执行之前，它将在第3步到第7步上做几次重做的尝试。

如果一个应用的写操作数据很大或者跨越了块边界，GFS 客户端会将这个操作分割成几个写操作。这些操作都遵循上面描述的控制流，但是可能会被其它客户端上的请求打断或覆盖。因此，一块共享的文件区域可能最终包含不同客户端的数据碎片。尽管如此，一个快服务器内的所有的副本的对应文件区域都是完全相同的，因为这些独立的写操作在所有副本上一定都按着相同的顺序成功执行。如 2.7 节所提到的那样，这使文件区域处于一个一致但未定义的状态。

3.2 数据流

为了有效的利用网络，我们将数据流和控制流分开。控制流从客户端到 Primary 上，再到所有的Secondary 上，而数据则以管道形式、线性的沿一个精心设计的块服务器链进行推送。我们的目标是最大限度的使用每台服务器的网络带宽，避免网络瓶颈和高延迟，最小化推送所有数据的时间延迟。

为了有效利用每台机器的网络带宽，数据被线性的沿一个块服务器组成的链进行推送，而不是按着其它拓扑进行分发（如，树）。因此每台机器的出口带宽都用于以最快的速度专注地传输数据，而不是分配给多个接收者。

为了尽可能的避免网络瓶颈和高延迟链路，每台机器只将数据推送给网络拓扑中最近的没有接收到数据的机器。假设客户端将数据推送给块服务器 S1 到 S4。它将数据发送给最近的块服务器，我们称之为 S1，S1 将数据推送给 S2 到 S4 中最近的块服务器，我们称之为 S2，类似的，S2 将数据推送到 S3 或 S4 中距离 S2 较近的块服务器等等。我们的网络拓扑足够简单，可以通过IP地址来精确的估计距离。

最后，我们通过在 TCP 连接上使用管道传输数据来最小化时间延迟。一旦一个块服务器接收到数据，则马上开始进行数据推送。管道对我们的帮助很大，因为我们采用了全双工的交换网络。立刻推送数据不会降低数据的接收速率。在没有网络拥塞的情况下，将 B 个字节传输到 R 个副本的理想时间消耗为 B/T+RL，这里 T 是网络的吞吐量，L 是两台机器间的传输延迟。我们的网络链路通常为100Mbps（T），并且 L 远小于1ms，因此，在理想情况下，1MB 的数据能够在 80ms 内分发完成。

3.3 原子性的记录追加

GFS 提供了一种原子性的追加操作称为记录追加：

• 在传统的写操作中，客户端指定数据写入的位置在文件中的偏移量，这样对同一个文件区域的并行写操作不能进行序列化：该区域最终可能包含来自多个客户端的数据片段。
• 然而，在一个记录追加操作中，客户端只需要指定数据，GFS 将数据至少一次原子性地追加到文件（如，一个连续的字节序列）的 GFS 选定的一个偏移位置，并将这个偏移位置返回给客户端。这与在没有竞争的情况下，Uinx 下多个并发写操作向一个使用 O_APPEND 选项打开的文件中写数据相似。

记录追加操作在我们的分布式应用中使用频繁，许多运行在不同机器上的客户端并行的向同一文件上追加数据。如果使用传统的写操作进行并发写，客户端将需要额外复杂的、昂贵的同步机制，比如，通一个分布式锁的管理器。在我们的工作中，这样的文件通常用于多个生产者/一个消费者队列，或者合并来自许多不同客户端的数据结果。

记录追加操作是修改操作中的一种，遵循 3.1 中介绍的控制流程，只在 Primary 上有一些额外的逻辑。客户端把数据推送到文件最后一个块的所有的副本上，然后将向 Primary 发送它的请求。Primary 会检查这次追加操作是否使块的大小超过了最大尺寸（64MB）。

• 如果超过，它将把这个块填充满，通知所有的 Secondary 副本进行相同的操作，并回复客户端表明这个操作将在下一个块上重新执行。（记录追加操作的数据大小严格控制在最大尺寸的 1/4 以内，以确保最坏情况下碎片的数量在一个可接受范围。）
• 通常情况下，如果记录不超过最大尺寸，Primary 将数据追加到它的副本上，然后通知Secondary 把数据写到与 Primary 相同的位置上，最后回复客户端操作成功。

如果在任意一个副本上的记录追加失败，客户端将重试这个操作。因此，在同一个块的副本上可能包含不同的数据，包括同一个记录的全部或部分的重复数据。GFS 不保证写入的数据在字节上完全相同，它只保证作为一个原子单元至少被写入一次。这个特性能够通过简单的观察得到：如果操作执行成功，数据肯定被写入到了某些块副本的相同位置。此外，在这之后，所有副本至少都达到了记录尾部的长度。因此，即使一个不同的副本成为了 Primary，以后的任何记录也都将被放置在更大的偏移位置或者是一个不同的块上。在我们的一致性保障方面，记录追加操作成功的写入数据的区域是被定义的（因此是一致的），反之，介于中间状态的区域是不一致的（因此是未定义的）。我们的应用使用在 2.7.2 讨论的方法处理这种不一致的区域。

3.4 快照

快照操作几乎瞬间为一个文件或一个目录树（源）创建一个拷贝，并且不会对正在进行的其它操作造成任何影响。我们的用户使用它为一个巨大的数据集创建一个拷贝分支（而且经常递归的对拷贝进行拷贝），或者是在尝试变化之前对当前的状态创建检查点，之后可以轻松的进行提交或回滚。

像 AFS 一样，我们使用标准的写时拷贝（Copy-On-Write）技术来实现快照。当 Master 接收到一个快照请求时，它先取消快照相关的文件块的所有租约。这确保了任何后面对这些块的写操作将需要与 Master 进行交互，以获取租约的持有者，这将为 Master 提供一个为块创建一个新拷贝的机会。

写时拷贝：在被修改时才真正执行拷贝

在租约被取消或者过期后，Master 将这些操作记录到磁盘，然后以复制源文件或目录树元数据的方式来在内存上执行这些日志记录。新创建的快照文件与源文件指向相同的块。

在快照操作后，我们以下面的方式来执行复制写入：

1. 客户端第一次想要向块 C 中写入数据前，它将向 Master 发送一个请求来查找当前的租约持有者。
2. Master 注意到块 C 的引用计数大于 1，它将推迟回复客户端的请求，并选择一个新的块句柄 C’，然后通知每个拥有块 C 副本的块服务器，创建一个新的块 C’。通过在同一个块服务器上创建一个新的块，我们能确保这个拷贝是本地的，不需要通过网络进行的（我们的磁盘速度是100MB以太网链路的3倍）。
3. 从这点上看，请求的处理不会与其它的块处理有差别：主节点将新块 C’ 的租约授予其中一个副本，并回复客户端，客户端能够进行一般的写操作，并不知道这个块是从一个已存在的块上创建出来的。

Master 完成了以下这些工作：

1. 执行所有的命名空间操作。
2. 管理整个系统内的所有块的副本。
   • 决定块的存储位置。
   • 协调系统范围内的各种行为以保障块能够有足够的副本。
   • 均衡所有块服务器的负载。
   • 以及回收不再使用的存储空间。

4.1 命名空间管理与锁

许多 Master 操作会占用较长时间：例如，一个快照操作必须撤销所有进行快照的块所在块服务器的租约，我们不想推迟正在进行的其它 Master 操作，因此，我们允许多个操作同时进行，并使用命名空间区域的锁来确保这些操作按适当的顺序执行。

不像许多传统的文件系统那样，GFS 没有一个目录数据结构来列出这个目录下的所有文件，也不支持对文件和目录的别名操作（如，Unix术语中的硬链接或符号链接）。GFS 的命名空间逻辑上表现为一个将全路径名映射为元数据的查询表。利用前缀压缩，这个表能够高效的存储在内存中。每个命名空间树中的节点（无论是一个绝对文件名还是一个绝对目录名）都有一个与之关联的读写锁。

每个主节点操作在执行前都先获得一系列的锁，通常，如果它涉及到/d1/d2/.../dn/leaf，它将：

• 获得目录名的读锁/d1，/d1/d2，...，/d1/d2/.../dn。
• 获取完全文件名/d1/d2/.../dn/leaf的一个读锁或写锁。

注意，这里的 leaf 根据其操作，可能是一个文件，也可能是一个目录。

我们现在举例说明在/home/user构造快照成/save/user时，这个锁机制如何防止另一个 Master 任务创建一个文件/home/user/foo：

• 快照操作获得了/home和/save上的读锁，以及/home/user和/save/user上的写锁。
• 而文件创建操作则获得了/home和/home/user上的读锁，以及/home/user/foo上的写锁。因为它们都试图获得/home/user上的锁而造成冲突，所以这两个操作将适当的进行排序。

文件创建不需要获取它的父目录的写锁，因为这里没有“目录”或类似 inode 等用来防止被修改的数据结构。文件名上的读锁足以防止父目录被删除。

这种锁机制的一个很好的性质是它允许对同一个目录下的并发操作。比如，在一个相同目录下，多个文件创建操作可以同时进行：每个操作获取目录上的读锁，以及其文件名上的写锁。目录名上的读锁足以防止目录被删除、重命名或进行快照。文件名上的写锁可以使使用同一名字创建文件的两次操作顺序执行。

因为命名空间可能包含很多节点，所以读写锁对象采用惰性分配策略，一旦不再使用则被删除。同样，锁需要按一个相同的顺序被获取来防止死锁：他们先对命名空间进行排序，并在同一级别按字典序排序。

4.2 副本布局

一个GFS集群采用高度分布的多层结构，它通常有几百个块服务器分布在许多机器架构上。这些块服务器被来自相同或不同机器架构上的数百个客户端轮流访问。不同机架上的两台机器间的通信可能要经过一个或多个网络交换，此外，机架的入口或出口带宽可能比机架上所有机器的带宽总和要小。多层的分布式对数据的灵活性、可靠性和可用性提出了挑战。

块副本布局策略有两大目标：最大化数据的可靠性和可用性，最大化带宽利用率。为了这两个目标，将副本分布在不同的机器是不够的，它只防止了磁盘或机器的失效，以及最大化了机器的带宽利用率。我们也必须将副本分布到不同的机架上，这样可以确保在整个机架损坏或掉线（例如，由于网络交换或电源线路的问题造成的资源共享失效）的情况下，一个块的一些副本能够保存下来并能正常使用。这意味着在网络流量上，特别是在读取一个块时，可以利用多个机架的整合带宽。另一方面，写操作必须将数据导向多个机架，这个代价是我们愿意付出的。

4.3 块副本的创建、重新复制和重新负载均衡

三个原因造成了块副本的创建：块创建、重新复制和重新负载均衡。

当主节点创建一个块时，它会选择在哪个块服务器上初始化一个空的副本。主节点会考虑几个因素：

1. 我们想要在一个空间使用率低于平均值的块服务器上放置新的副本，这会使块服务器间的磁盘利用率基本相等。
2. 我们想要限制每台块服务器上近期创建块的数量。尽管创建本身是廉价的，但是它也预示着马上就会有大量的数据写入。块服务器往往在一波写入后就变成实际只读的了。
3. 我们想要将一个块的副本分布到不同的机架上。

当副本的可用数量低于用户指定的值时，Master 会尽快进行块的重新复制。以下原因可能引起这个操作：

1. 一个块服务器不可用。
2. 块服务器报告存储的副本可能被损坏。
3. 其中一个磁盘由于错误不可用。
4. 备份数量的设置值变大了。

每个需要进行重新复制的块基于几个因素优先进行：

1. 一个是块现有的副本数量与目标数差多少。比如一个丢失两个副本的块比丢失一个副本的优先级高；
2. 相对于最近被删除的文件的块来说，我们优先对活跃的文件的块进行重新复制（4.4）；
3. 为了最小化失效对正在运行的应用的影响，我们会提高阻塞客户进程的块的重新复制优先级。

Master 选取优先级最高的块，通过通知一些块服务器从一个可用副本上拷贝块数据来“克隆”它。选择副本位置的方法与创建时类似：平均磁盘空间使用率，限制单一块服务器上运行的克隆操作熟练，以及跨机架分布。

为了防止克隆操作的流量影响到客户端的流量，Master 限制了集群和每个块服务器上正在运行的克隆操作数量。此外，每个块服务器通过减少发往源块服务器的读请求，限制了每个克隆操作所占用的带宽。

最后，Master 周期性地对副本重新进行负载均衡：它检查当前的副本分布情况，并将副本移动到更合适的磁盘空间上，达到负载均衡。通过这个过程，Master 逐步的填充新的块服务器，而不是马上使用新的块和大量的写入流量填充它。这个新副本的分布标准与上面提到的类似。此外，Master 必须选择移动哪个已存在的副本，通常情况下，它更倾向于从剩余空间小于平均值的那个块服务器上移动副本，以使磁盘使用率相等。

4.4 垃圾回收

在一个文件被删除后，GFS 不会立即回收可用的物理存储空间。而是只在文件和块级别上定期地进行垃圾回收。我们发现，这个方法使系统更加简单，更加可靠。

4.4.1 机制

当一个文件被应用删除时，Master 会像其他操作一样立即记录下这个删除操作。然而，文件仅仅会被重命名为一个包含删除时间戳且隐藏的名字，而不是立即回收资源。在 Master 定期扫描文件系统的命名空间期间，它将真正删除已经被隐藏超过三天的文件（这个间隔可以配置）。在此之前，文件仍然可以通过新的特殊的名字进行读取，也可以通过重命名为普通的文件名从而撤销删除操作。当隐藏文件从命名空间中真正被删除时，内存中对应的元数据也会被清除，这样能有效的切断文件和它的所有块的连接。

在对块的命名空间做类似的扫描时，Master 标识出孤儿块（任何文件都无法访问到的块），并将那些块的元数据清除。在与 Master 进行定期的心跳信息交换时，每个块服务器报告其所含有块的集合，Maste r回复块服务器哪些块没有出现在 Master 的元数据中，块服务器将释放并删除这些块的副本。

4.4.2 讨论

虽然分布式回收机制在编程语言领域是一个需要复杂解决方案的难题，但在我们的系统中十分简单。我们能简单的确定一个块的所有引用：它们唯一的保存在 Master 的文件-块映射中。我们也能轻松的确定一个块的所有副本：它们都以 Linux 文件的形式存储在每台块服务器的指定目录下。任何 Master 不认识的副本都是“垃圾”。

用于存储回收的垃圾回收方法通过惰性删除拥有几个优势：

• 首先，对于组件失效是常态的大规模分布式系统来说，这种方式简单可靠。块创建操作可能在一些块服务器上执行成功，但在另一些服务器上执行失败，残余的副本在主节点上无法识别。副本删除消息可能丢失，Master 必须重新发送执行失败的消息，包括自身的和块服务器的。垃圾回收机制提供了一个一致的、可靠的方法来清除没用的副本。
• 其次，它将存储回收操作合并到了 Master 定期的后台操作中，比如定期浏览命名空间和与块服务器握手。批处理的方式分摊了任务的开销。此外，只有在 Master 相对空闲时才会完成垃圾回收，Master 对客户端需要及时回复的请求有更高的优先级进行响应。
• 第三，延迟回收存储空间可以为防止意外的、不可撤销的删除操作提供一个安全保障。

在我们的经验中，上述机制主要的缺点是：当存储空间紧张时，会阻碍用户对系统进行及时调整。频繁创建和删除临时文件的应用不能马上重用删除数据后的可用空间。我们通过在已被删除的文件上显式的再次进行删除来解决垃圾回收的这些问题；我们也可以允许用户对命名空间的不同部分应用不同的复制和回收策略。比如，用户可以指定一些目录树下的所有文件进行无副本存储，任何被删除的文件会从系统上迅速的、不可恢复的删除。

4.5 过期副本的检测

如果一个块服务器失效并在宕机期间丢失了块的修改操作，块副本可能会过期。对于每个块，Master 维护一个块版本号来区分最新的副本和过期的副本。

1. 每当 Master 授予某个块一个新租约，这个 Primary 副本都会自增版本号，并向所有副本通知新版本号。
2. 在客户端接收到通知并开始进行写操作之前，Master 和 Master 的副本将此块的新版本号持久化。
3. 如果其它副本当前不可用，它的块版本号将不会被更新。
4. 当块服务器重启并报告它所有的块集合和它们相应的版本号时，Master 还会探测这个块服务器下副本的版本号。

Master 在定期的垃圾回收操作中清除过期的副本。在这之前，当它回复客户端的块信息请求时，它将认为一个过期的副本实际上根本并不存在。

另一个安全措施是，当 Master 通知客户端哪个块服务器持有这个块的租约时，或者在进行克隆操作期间它通知一个块服务器从另一个块服务器上读取数据时，请求中包含块版本号。客户端或块服务器在执行操作时会验证这个版本号，以保证总是可访问的最新的数据。

在设计系统时，最大的挑战之一就是如何处理频繁的组件故障。组件的数量和质量让这些问题变得非常普遍。我们不能完全的信任机器，也不能完全的信任磁盘。组件故障可能会造成系统不可用，甚至损坏数据。我们将讨论如何面对这些挑战，以及当组件不可用时系统内部用于诊断问题的工具。

5.1 高可用性

在 GFS 集群的数百台服务器中，必定有一些机器在给定的一段时间内是不可用的。我们通过两个简单但有效的策略来保证整个系统的高可用性：快速恢复和复制。

5.1.1 快速恢复

Master 和块服务器都被设计为无论如何终止，它们都能够在几秒内恢复自己的状态并重新启动。实际上，我们并不区分正常的和不正常的终止；可以通过 kill 掉进程来关闭服务。由于它们的请求超时而没有完成，客户端或其他服务器可能经历小的颠簸，但它们会重新连接服务器并重试。6.2.2 节记录了实际实验中观察得到的重启时间。

5.1.2 块复制

如之前讨论过的，每个块被复制到不同机架上的多个块服务器上。用户能够为文件命名空间的不同部分指定不同的复制级别，默认有三个。当有块服务器掉线或通过校验和（5.2节）检测出损坏的副本时，Master 克隆已存在的副本来保证每个块有足够的副本。

尽管复制策略非常有效，但我们也在探索其他的跨服务器的冗余解决方案，如奇偶校验，或者纠删码（erasure code），来应对我们日益增长的只读存储需求。在我们高度低耦合的系统中，这些复杂的冗余方案是具有挑战的，但并不是不可实现的，因为我们的操作主要是追加和读取，而不是小规模的随机写。

5.1.3 Master复制

为了可靠性，Master 的状态也被复制。它的操作日志和检查点被复制到多个机器上。一个修改操作只有在它的日志被刷新到本地磁盘和所有的 Master 副本后才认为被提交完成。简单的说，一个Master 负责所有的操作，包括后台的行为，如垃圾回收等改变系统内部状态的行为。当它失效时，能够瞬间重启。如果它的机器或磁盘发送故障，GFS 的外部监控会在其它有副本操作日志的机器上启动一个新的 Master。客户端视角下只使用主节点的名字（如，gfs-test），它是一个 DNS 的别名，可以更改这个名字来访问被重新放置到其它机器上的 Master。

此外，当 Primary Master 宕机时，“影子”Master可以为文件系统提供一个只读的访问接口。它们是影子，而不是镜像，它们内部的数据会稍微的落后于 Primary Master，通常不到1秒。因此，它们对于那些不经常修改的文件的读取，或是不太在意得到的是稍微过期的数据的应用来说是有效的。实际中，因为文件内容是从块服务器读取的，所以应用察觉不到过期的文件内容。在短暂的时间窗口内，过期的可能是文件的元数据，如目录内容，或访问控制信息。

为了保持最新的状态，影子 Master 读取一个正在增长的操作日志副本，并执行与 Primary Master相同的操作序列来改变自己的数据结构。像 Primary 那样，它在启动后轮询块服务器（之后很少）来定位块副本，并通过频繁的交换握手信息来监控它们的状态。当 Primary Master 决定创建或删除副本造成位置信息更新时，影子 Master 才会通过 Primary Master 更新状态。

5.2 数据完整性

每个块服务器使用校验和来探测存储的数据是否被损坏。考虑到一个 GFS 集群经常由数百个机器上的数千块磁盘组成，由于磁盘的损坏而造成的读和写路径上的数据损坏或丢失是很常见的。（其中的一个原因见7.1节）我们能够使用块的其它副本来进行恢复，但是无法通过不同块服务器上的副本的比较来探测出数据块是否损坏。此外，不同的副本之前有分歧可能是合理的：GFS 修改操作的语法，特别是之前讨论过的原子追加操作，本身就不能保证所有副本都相同。因此，每个块服务器必须独立的通过校验和验证它所拥有的拷贝是否合法。

一个块被分割成 64KB 大小的 block，每个 block 都有一个对应的 32bit 校验和。像其它元数据一样，校验和保存在内存中，并通过日志永久存储，与用户数据分开。

对于读操作，在把数据返回给请求者之前，块服务器要验证读范围内所有数据 block 的校验和，因此，块服务器不会将损坏的数据传播到其它机器上。如果一个 block 与记录的校验和不匹配，块服务器会返回给请求者一个错误，并向 Master 报告这个错误。在响应中，请求者将从其它的副本读取数据，同时，Master 将从其它副本上克隆这个块。在一个新的可用的副本复制完毕后，Master 会通知报告错误的块服务器删除出错的副本。

校验和对读操作几乎没有影响，原因有几个：

• 因为大多数的读操作至少需要读取几个块，我们只需要读取一小部分额外的数据用于验证验证和。
• GFS 客户端代码通过试图将读操作对齐到校验和的 block 边界上，大大减小了验证的开销。
• 此外，块服务器上的校验和查询和对比不需要任何 I/O 就能完成，校验和的计算可以和 I/O 操作同时进行。

校验和计算针对在块尾部进行追加写操作做了很大的优化（相对于覆盖已有数据的写操作）。我们仅增量更新最后一个不完整的块的校验和，并用追加的新的校验和来计算 block 新的校验和。即使最后一个不完整的校验和已经被损坏，并且我们现在没有探测出来，新的校验和将不匹配存储的数据，当这个块下一次被读取时，就会检测出数据已经损坏。

相反的，如果写操作覆盖块中已经存在的一部分，我们必须读取并验证要被覆盖的这个范围内的第一个和最后一个 block，然后执行写操作，最后计算并记录新的校验和。如果我们在覆盖它们之前不进行这一对验证，新的校验和可能会隐藏没有被覆盖区域的错误。

在空闲的时候，块服务器能浏览和验证不活跃的块，这允许我们探测很少被读取的块的数据损坏。一旦损坏被探测到，Master 就能创建一个新的没有损坏的副本，并删除已损坏的副本。这能够防止不活跃的、已损坏的块欺骗 Master，使 Master 认为它是块的一个可用的副本。

5.3 诊断工具

在问题隔离、调试和性能分析方面，详尽的、细节的诊断日志给我们很大的帮助。如果没有日志，我们很难理解短暂的、不重复的机器间的消息交互。GFS 服务器生成诊断日志用于记录许多关键的事件（如块服务器启动和关闭），以及所有的远程调用（RPC）的请求和响应。这些诊断日志能够被自由的删除，不会给系统带来任何影响。然而，在空间允许的情况下，我们会尽量保存这些日志。

远程调用（RPC）日志包括网络上所有的请求和响应，除了文件数据被读取或写入。通过匹配请求和响应，以及核对其它机器上的 RPC 记录，我们能重建这个交互历史用于诊断错误。这些日志也能用于跟踪负载测试和性能分析。

记录日志所造成的性能影响很小（远小于它带来的好处），因为这些日志异步的、顺序的被写入。最近的事件也会保存在内存中，可用于持续的在线监控。

在这章中，我们介绍几个微基准测试来描述 GFS 架构和实现中固有的瓶颈，还有一些来自于 Google 正在使用的集群中。

6.1 微基准测试

我们在一个由1个主节点，2个主节点副本，16个块服务器和16个客户端组成的GFS系统上进行性能测试。注意，这个配置是为了方便测试，一般的集群包含数百个块服务器和数百个客户端。

所有的机器都配置为两个1.4GHz的PIII处理器，2GB的内存，两个5400rpm的80GB的磁盘，以及一个100Mpbs全双工以太网连接到一个HP2524的交换机上。两个交换机之间只用1Gpbs的链路连接。

6.1.1 读操作

N个客户端同时从文件系统读取数据。每个客户端从320GB的数据中，随机的选取4MB区间进行读取。这个读操作会重复256次，使客户端最终读取到1GB的数据。块服务器总共只有32GB的内存，，所以我们期望最多有10%的缓存命中率。我们的结果应该与没有缓存的情况下相近。

图3：总吞吐量。顶上的曲线显示了理论情况下的由我们的网络拓扑引入的限制。下面的曲线显示了测试的吞吐量。它们显示了置信区间为95%的误差，在一些情况下，由于测量的方差小而不太明显。

图3（a）中显示了N个客户端的总读取速率和它的理论极限。当两个交换机之间的1Gpbs链路饱和时，理论极限为125MB/s，或者当客户端的网络接口达到饱和时，每个客户端的理论极限为12.5MB/s，无论哪个都适用。当只有一个客户端进行读取时，观测到的读取速率为10MB/s，或者是每个客户端极限的80%。对于16个读操作，总速率可以达到94MB/s，大约是125MB/s网络极限的75%，或者是每个客户端到达6MB/s的速率。效率从80%下降到75%的原因是，当读取操作的数量增加时，多个读操可能同时的从同一个块服务器上读取数据。

6.1.2 写操作

N个客户端同时往N个不同文件进行写操作。每个客户端以每次1MB的速率向一个新文件写入1GB的数据。总的写入速率和理论极限显示在图3（b）中。理论极限是67MB/s，因为我们需要把每个字节都写入到16个块服务器中的3个，而每个块服务器的输入连接极限为12.5MB/s。

每个客户端的写入速率为6.3MB/s，大约是极限的一半，主要的原因是我们的网络协议栈，它与我们用于推送块副本的管道（pipelining）方式不太适应。从一个副本到另一个副本传播数据的延迟降低了整个系统的写入速率。

16个客户端的总写入速率达到35MB/s（每个客户端的速率大概是2.2MB/s），大约是理论极限的一半。与多个客户端进行读操作的情况类似，由于进行写操作的客户端数量的增加，客户端同时向同一个块服务器写入的几率也会增加。此外，写操作冲突的几率比读操作的要更大，因为每次写操作需要涉及三个不同的副本。

写操作比我们想要的要慢，在实际中，这不会成为一个主要的问题，因为即使对于单个客户端它也增加了时延，但是对于含有大量客户端的系统来说，它不会对系统的写入带宽有太大影响。

6.1.3 记录追加

图3（c）显示了记录追加的性能，N个客户端同时向一个单独的文件追加数据。性能受存储文件最后一个块的块服务器的网络带宽的限制，而不是客户端的数量。它的速率由一个客户端的6MB/s下降到16个客户端的4.8MB/s，主要是由冲突和不同客户端的网络传输速率不同造成的。

我们的应用倾向于同时处理多个这样的文件。换句话说，N个客户端同时向M个共享文件追加数据，N和M在0到几百之间。因此，在我们的经验中，块服务器网络冲突在实际中不是一个严重的问题，因为当块服务器正在忙于处理一个文件时，客户端可以进行另一个文件的写入操作。

6.2 实际应用中的集群

我们现在测试了两个Google正在使用的集群，它们有一定的代表性。集群A通常用于上百个工程师进行研究和开发。一个普通的任务被人为初始化，并运行几个小时，它读取几MB到几TB的数据，进行转换或分析数据，并将结果写回到集群中。集群B主要用于生产数据的处理。在很少人为干预下，这些任务运行更长的时间，持续的产生和处理几TB的数据集。在这两个实例中，一个单独的任务由运行在很多机器上的很多进程同时读和写很多文件组成。

6.2.1 存储

表2：两个GFS集群的属性

如表2的前五个条目所示，两个集群都有上百个块服务器，支持数TB的磁盘空间，存储了大小合适的数据，但没有占满。“已使用空间”包括所有的块副本。实际上，所有的文件都有三个副本，因此，集群实际上存储了18TB和52TB的文件数据。

两个集群的文件数量相近，不过B含有更大比例的死文件，死文件是指被删除或者被新版本替换的文件，但它们的存储空间还没有被回收。它也存储了更多的块，因为它的文件较大。

6.2.2 元数据

块服务器总共存储了数10GB的元数据，大多数是用户数据64KB的block的校验和。块服务器上其它的元数据则是4.5节讨论的块版本号。

Master上的元数据要小很多，只有几十MB，或者说，每个文件平均有100字节的元数据。这符合我们对Master内存在实际中不会限制系统能力的设想。大多数的文件元数据是以前缀压缩方式存放的文件名，其它的元数据包括文件的所有者和权限，文件到块的映射表，以及每个块的当前版本号。此外，还为每个块存储了当前副本的位置信息和引用计数用来实现写时拷贝（COW）。

每个单独的服务器，不论是块服务器还是Master，只有50-100MB的元数据。因此恢复速度很快：在服务器能够应答请求之前，它会只花费几秒时间先从磁盘中读取元数据。然而，主节点会持续颠簸一段时间，通常是30秒-60秒，直到它从所有的块服务器上获取到块位置信息。

6.2.3 读写速率

表3：两个GFS集群的性能度量

表3中显示了持续时间不同的读写速率，两个集群在做这些测试前都已经运行了大概一个星期的时间。（这两个集群是因为GFS更新到新版本而进行重启。）

自从重启后，平均写速率一直小于30MB/s。当我们做这些测试时，B正在进行速率为100MB/s的大量写操作，因为写操作被传送到三个副本上，所以将产生300MB/s的网络负载。

读速率要达到高于写速率。如我们设想的那样，整个工作由更多的读操作组成。两个集群都在进行繁重的读操作，特别是，集群A在前些周维持了580MB/s的读速率。它的网络配置能够支持750MB/s的速率，所以它有效的利用了它的资源。集群B支持的极限读速率为1300MB/s，但是，它的应用只用到了380MB/s。

6.2.4 Master复制

表3也显示了发往Master的操作速率，每秒有200-500个操作。Master可以轻松的应对这个速率，因此Master的处理性能不是瓶颈。

在早期的GFS版本中，Master有时会成为瓶颈。它花费大多数时间连续的浏览大的目录（可能含有几百几千个文件）来查找指定的文件。我们已经改变了Master的数据结构，使用二分查找在命名空间中进行查找，以此提高效率。它也能轻松的支持每秒数千次的文件访问。如果需要，我们能通过在命名空间数据结构之前放置名字查询缓存的方法来进一步提高速度。

6.2.5 恢复时间

在一个块服务器发生故障后，一些块的副本数量会小于指定值，必须进行克隆操作使副本数恢复到指定值。恢复所有块所需的时间由资源的数量决定。在一个试验中，我们杀掉了B集群中的一个单独的块服务器，这个块服务器大概有15,000个块，包含了600GB的数据。为了减小对正在运行的应用的影响，以及为调度决策提供修正空间，我们的默认参数限制了集群的并发克隆数为91（块服务器数量的40%），在这里，每个克隆操作被允许最多使用6.2MB/s的带宽。所有的块在23.2分钟后恢复，复制速率为440MB/s。

在另一个试验中，我们杀掉了两个块服务器，每个包含了大约16000个块和660GB的数据。这个双故障造成了有266个块的成为单副本。这266个块作为更高的优先级被克隆，并在两分钟之内恢复到至少有两个副本的状态，这样可以让集群处于一个能够容忍另一个块服务器故障而不丢失数据的状态。

6.3 工作量明细

在这章中，我们对两个GFS集群的工作进行详细的分解介绍，这两个集群与6.2节中的类似，但不完全相同。集群X用于研究和开发，而集群Y用于生产数据的处理。

6.3.1 方法论和注意事项

这些结果中包含了只有用户发起的请求，以至于它们能够反映出由应用文件系统整体产生的工作量。它们不包含用于执行客户端请求或者内部的后台行为的服务器间的请求，如正向写或重新均衡负载。

I/O操作的统计是基于从GFS服务器的实际RPC请求日志上重新建立起来的信息的。例如，GFS客户端为了增加并行性，会将一个读操作分解成多个PRC，通过这些调用，我们可以推导出原始的读操作。因为我们的访问模式是高度模程式的，我们认为任何错误都属于误差。应用记录的详细日志能够提供更准确的数据，但是为了这个目的重新编译和重启上千个客户端在逻辑上是不可能的，而且从这么多机器上收集结果也是非常麻烦的。

应该注意不要对我们的工作量做过度的归纳，因为Google完全控制着GFS和其它自己的应用，应用针对于GFS做了优化，同样，GFS也是为了这些应用而设计的。这类的相互作用同样也存在于普通应用和文件系统之间，但是在我们的实例中，这种作用更加显著。

6.3.2 块服务器工作量

表4：操作工作量大小明细表（%）

表4显示了操作数量的分布。读操作展现出一个双峰的分布，小规模读（64KB以内的）来自于查询为主的客户端，它从海量文件中查询小片的数据。大规模读取（大于512KB）来自于从头到尾读取整个文件的连续读操作。

在集群Y中有一些读操作没有返回任何数据。我们的应用，特别是哪些在生产系统中的，经常将文件用于生产者-消费者队列。生产者同时向一个文件追加数据，同时消费者从文件尾部读取数据。有时，当消费者超过生产者时，就没有数据返回了。集群X显示这种情况不常发生，因为它经常用于进行短暂的数据分析，而不是分布式应用的长久数据分析。

写操作也展现出一个双峰的分布。大规模写操作（超过256KB）通常是由于Writer使用了缓存机制造成的；缓存了较少的数据，频繁的进行检查点操作或同步操作，或者仅仅生成了少量数据的Writer解释了为什么存在小规模的写操作（小于64KB）。

表5：字节传输明细表（%）。对于读操作，这个大小是实际的读取和传输数据的总量，而不是请求的数据量。这两个可能的不同点在于如果试图读取超过文件结束的大小，这样的操作在我们的工作中并不常见。

对于记录追加操作，集群Y比集群X中有更高的大规模追加操作比例，这是因为我们的生产系统使用了集群Y，针对GFS做了更多的优化。

表5显示了按操作的数据大小得到的总的数据传输量。对于所有的操作，较大规模的操作（大于256KB）占据了主要的传输量；小规模的读操作（小于64KB）传输量较小，但是在读取的数据量中仍占有相当的比例，因为随机读操作需要进行查找工作。

6.3.3 追加操作 vs 写操作

追加操作被频繁的使用，尤其是在我们的生产系统中。对于集群X，写操作与记录追加操作在字节传输量上的比例为108:1，在操作数量上的比例为8:1。对于集群Y，，这个比例为3.7:1和2.5:1。此外，这些比例说明了对于两个集群，记录追加操作所占的比例都比写操作的大。然而，对于集群X，在测试期间，使用的追加操作相当少，以至于结果几乎被一两个使用特定缓存大小的应用歪曲了。

不出所料的，记录追加操作占据了我们的数据修改的主要工作量，而不是覆盖写操作。我们测试了在primary副本上被覆盖的数据总量。这近似于一种情况，其中客户端故意的覆盖之前写入的数据，而不是追加新的数据。对于集群X，覆盖操作占字节修改的不到0.0001%，占操作数量的不到0.0003%。对于集群Y，这两个比例都为0.05%。尽管这是微小的，但是仍然比我们预期的要高。它证明了这些覆盖操作来自于客户端对于错误和超时的重试操作。它们不是工作量的一部分，而是重试机制的结果。

6.3.4 Master工作量

表6：主节点请求明细表（%）

表6显示了根据发往Master的请求类型的明细。大多数请求都是读取操作查询块的位置信息（FindLocation）和数据修改操作的租约持有者的信息（FindLeaseHolder）。

集群X和Y在删除请求的数量上有显现的差别，因为集群Y存储生产数据集，这些数据集会定期的重新生成数据以及用新版本的数据替换旧的数据。其中的一些不同被隐藏在了Open请求中，因为旧版本的文件可能以写模式打开并从头开始的方式，被隐式的删除。

FindMatchingFiles是一个模式匹配请求，提供了“ls”和类似的文件操作。不像其他的Master操作，它可能处理一大部分命名空间，所以可能很昂贵。集群Y中看到了更多的这类请求，因为自动化的数据处理任务倾向检测部分文件系统，来获知整个应用的状态。相反的，集群X的应用更多的处于用户的显式控制之下，经常预先知道所有所需文件的名字。

在建造和部署 GFS 的过程中，我们经历了各种问题，一些是操作上的，一些是技术上的。

起初，GFS 被想象为是我们生产系统的一个后台的文件系统。随着时间的推移，GFS 的使用逐渐包含了研究和开发的任务。它开始完全不支持类似权限和配额的功能，但是现在已经初步的包含了这些功能。虽然生产系统是被严格控制的，但是用户则不会总是这样。更多的基础构件被需要用来防止用户间的干扰。

一些最大的问题是磁盘和 Linux 相关的问题。我们的许多磁盘要求 Linux 驱动，它们支持一定范围的 IDE 协议版本，但在实际中，只对最新版本的响应可靠。因为协议版本非常相似，这些驱动多数可以工作，但是偶尔也会有错误，造成驱动和内核对驱动器状态的认识不一致。由于内核的问题，这会导致数据隐藏的被损坏。这个问题迫使我们使用校验和来检测数据是否损坏，同时我们修改内核来处理这些协议错误。

早期在使用 Linux2.2 内核时，由于fsync()效率问题，我们遇到了一些问题。它花费与文件大小成正比的时间，而不是修改部分的大小。对于我们的海量操作日志，特别是在检查点之前来说，确实是一个问题。我们在这个问题上花费了一些时间，通过同步写解决了这个问题，最后还是移植到了 Linux2.4 上。

Linux 的另一个问题是一个单独的读写锁的问题，在这个地址空间内的任何线程都必须在将磁盘page in时（读锁）或在调用mmap()进行修改地址空间时持有这个锁。我们发现我们的系统在低负载时，也会短暂出现超时现象，我们艰难的寻找资源瓶颈，或不定时发生的硬件故障。最后，我们发现在磁盘线程正在 page in 之前的映射数据时，这个单独的锁阻塞了主网络线程向内存中映射新数据。因为我们主要受网络接口的限制，而不是内存拷贝的带宽，所以，我们用pread()来代替mmap()，使用一个额外的拷贝开销来解决了这个问题。

尽管偶尔会有问题，Linux代码常常帮助我们发现和理解系统行为。在适当的时候，我们会推进这个内核，并与开源社区共享我们的这些改动。

像其他的大型分布式文件系统一样，如AFS，GFS提供了一个与位置无关的命名空间，它能使数据为了负载均衡或容错透明的迁移。与AFS不同的是，GFS把文件数据分别到不同的存储服务器上，这种方式更像xFS和Swift，这是为了提高整体性能和增加容错能力。

由于磁盘相对便宜，并且复制要比RAID的方法简单许多，GFS当前只使用了复制来提供冗余，所以比xFS和Swift存储了更多的原始数据。

与AFS、xFS、Frangipani以及Intermezzo等文件系统不同，GFS并没有在文件系统接口下提供任何缓存机制。我们的目标工作是一个运行的应用很少会读取重复的数据，因为他们要么是从一个大的数据集中流式的读取数据，要么是随机的进行读取。

一些分布式文件系统，如Frangipani、xFs、Minnesota’s GFS和GPFS，去掉了中间的服务器，依靠分布式算法来保证一致性和进行管理。为了简单的设计、增加它的可靠性和获得弹性，我们选择了中心化的方法。特别的是，因为Master已经保存有大多数有关的信息，并可以控制它们的改变，因此，它极大地简化了原本非常复杂的块分配和复制策略的方法。我们通过保持较小的Master状态信息，以及在其它机器上做完整的备份来提高系统容错性。弹性和高可用性（对于读操作）通过影子Master机制来提供的。更新Master状态是通过追加预写日志来实现持久化的。因此，我们可以调整为使用类似 Harp 的主拷贝方式来提供高可用性的，它比我们目前的方式有更高的一致性保证。

我们解决了一个类似 Lustre 在有大量客户端时总的传输性能的问题。然而，我们通过只关注我们自己的应用，而不是创建一个适用于 POSIX 的文件系统来简化这个问题。此外，GFS 采取大量的不可靠组件，所以容错将是我们设计的中心问题。

GFS 十分接近 NASD 架构，NASD 架构是基于网络磁盘的，GFS 使用了一般的机器作为块服务器，与 NASD 协议类型相同。但是与 NASD 不同的是，我们的块服务器使用了惰性分配固定大小块的方式，而不是可变大小的块。此外，GFS 实现了在生产环境中所需的一些功能，如重新负载均衡、复制和恢复等。

不像 Minnesota’s GFS 和 NASD，我们不会去追求改变存储设备的模式。我们只关注由一般组件组成的复杂分布式系统所需要的日常数据的处理。

通过原子记录追加操作实现的生产者-消费者队列解决了一个与 River 中的分布式队列类似的简单问题。River 使用了基于内存的分布式队列，必须小心的控制数据流，GFS则能够使用被很多生产者同时追加持久化的文件。River 模型支持 m-n 的分布式队列，但是缺少由持久化存储提供的容错功能，而 GFS 只能够有效的支持 m-1 的队列。多个消费者能够读取同一文件，但他们必须协调分区输入的负载。

Google 文件系统展示了一个在一般硬件上支持大规模数据处理工作的核心特性。一些设计决定都是根据我们的特殊环境定制的，但许多还是能够用于类似规模和成本的数据处理任务。

首先，根据我们当前的和预期的应用工作量和技术环境来重新考察传统的文件系统。观察结果引导出一个完全不同的设计思路。我们将组件失败看成是普通现象而非异常情况，对于向大文件进行追加（可能是并行的）和读操作（通常是序列化的）来进行优化，以及通过扩展接口和放松限制来改进整个系统。

我们的系统通过持续健康、复制关键数据以及快速自动的恢复来提供容错。块复制允许我们容忍块服务器的错误。这些错误的频率促进了一个新奇的在线修复机制，它定期的、透明的修复损坏的数据，并尽快对丢失的副本进行补偿。此外，在磁盘或IDE子系统层上，我们使用了校验和来探测数据是否损坏，在这种规模的磁盘数量上，这种问题十分普遍。

对于进行许多并行读写操作的各种任务，我们的设计提供了很高的总吞吐量。我们通过将控制流和数据流分开来实现这个目标，控制流直接经过 Master，数据流块服务器和客户端之间传输。通过大的块大小和在数据修改操作中授予主拷贝一个块租约，能够最小化 Master 涉及的操作，这使简单的、中心的 Master 不会太可能成为瓶颈。我们相信我们的网络协议栈的改进可以提高从客户端看到的写入吞吐量的限制。

GFS 很好的满足了我们的存储需求，并作为存储平台在 Google 中得到广泛使用，无论在研究和开发，还是生产数据处理上。它是我们持续创新和攻克整个 web 范围的难题的一个重要工具。