【论文阅读笔记】The Google File System

1 简介

Google File System (GFS) 是一个可扩展的分布式文件系统，专为快速增长的Google数据处理需求而设计。这篇论文发表于2003年，此前已在Google内部大规模应用。

GFS不仅追求性能、可伸缩性、可靠性和可用性等传统分布式文件系统的设计目标，还基于对自身应用负载情况和技术环境的深入观察，提出了独特的设计思路，与早期文件系统的假设明显不同。

2 设计概述

2.1 设计目标

GFS 在设计的时候有一些假想，即预期要实现的目标。

1. 系统由许多廉价的普通组件组成，因此组件失效是一种常态。GFS必须能够持续监控自身的状态，将组件失效作为一种常态事件，并能够迅速侦测、冗余和恢复失效的组件。
2. 系统能存储一定数量的大文件。Google预期会存储几百万个文件，这些文件通常大小在100MB以上，数GB大小的文件也是普遍存在的。系统必须能够高效管理这些大文件，同时，系统也必须支持小文件，但不需要针对小文件进行专门优化。
3. 工作负载主要包括两类读操作：
   • 大规模流式读取：单个读操作一般读几百 KB，更常见的是读 1MB 甚至更多。来自同一个客户端的连续操作通常是读取同一个文件中连续的一个区域。
   • 小规模随机读取：一般是在文件的某个随机位置读几个 KB 数据。注重性能的应用程序通常会将小规模随机读取操作合并并排序，之后按顺序批量读取，避免在文件中前后移动读取位置。
4. 系统的工作负载也会有很多大规模的、顺序的、数据追加方式的写操作。一般这种操作的大小和大规模读类似。一旦写入操作完成，这个文件很少会被修改。小规模的随机写也支持，但是不太高效。
5. 系统必须高效的、行为定义明确的实现多客户端并行追加数据到同一个文件里的语意。GFS 中的文件通常用作“生产者—消费者”队列或其他多路文件合并操作。系统中通常有数百个生产者，每个机器上运行一个，这些生产者并发地追加修改一个文件，因此以最小的同步开销来实现原子性是必不可少的。这些文件可能随后被读取，也可能是消费者在追加的操作的同时读取文件。
6. 高性能的稳定网络带宽远比低延迟重要。GFS 的大多数目标应用程序都重视以高速率的、大批量的处理数据，而很少有应用程序对单个读或写有严格的响应时间要求。

2.2 接口

GFS 提供了一套类似传统文件系统的 API 接口函数，虽然并不是严格按照 POSIX 等标准 API 的形式实现的。文件以分层目录的形式组织，用路径名来标识。GFS 支持常用操作以创建(create)、删除(delete)、打开(open)、关闭(close)、读(read)和写(write)文件。

另外，GFS 提供了快照和记录追加操作。

• 快照以很低的成本创建一个文件或者目录树的拷贝。
• 记录追加操作允许多个客户端同时对一个文件进行数据追加操作，同时保证每个客户端的追加操作都是原子性的。这对于实现多路结果合并、“生产者-消费者”队列非常有用，多个客户端可以同时追加写入，而不需要额外的同步锁。Google 发现在构建大型分布式应用时，这些类型的文件是非常有用的。

2.3 架构

一个 GFS 集群包含一个单独的master节点和多个chunk服务器，允许多个客户端访问，如下图所示。

所有这些机器通常是普通的 Linux 机器，运行用户级别的服务进程。可以将 chunkserver和客户端部署在同一台机器上，前提是机器资源允许，并能接受稳定性降低的风险。

其中GFS存储的文件都被分割成固定大小的chunk。在chunk 创建的时候，master会给每个 chunk 分 配一个不变的、全局唯一的 64 位的 chunk 句柄来标识。chunkserver把 chunk 以 Linux 文件的形式保存在本地硬盘上，并且根据指定的 chunk 句柄和字节范围来读写块数据。出于可靠性的考虑，每个chunk都会复制到多个chunk服务器上。默认使用3 个存储复制节点，不过用户可以为不同的文件命名空间设定不同的复制级别。

master节点管理所有的文件系统元数据。这些元数据包括命名空间、访问控制信息、文件和chunk 的映射信息、以及chunk当前的位置信息。Master 节点还管理着系统范围内的活动，比如，chunk 租用管理、孤儿 chunk的回收、以及 chunk 在 chunkserver之间的迁移。master 节点使用心跳信息周期地和每个 chunkserver通讯，发送指令到各个 chunkserver并接收 chunkserver的状态信息。

链接到每个应用程序的 GFS 客户端代码中实现了文件系统 API，这个 GFS 客户端代表应用程序与 master 和 chunk服务器通信以读写数据。客户端与 master 交互只进行元数据操作，所有的数据操作都是由客户端直接和 chunkserver进行交互的。GFS 没有提供 POSIX标准的API，因此不需要深入到 Linux 的 vnode 层。

客户端和 chunk服务器都不缓存文件数据。

• 客户端缓存文件数据几乎没什么好处，因为大多数应用程序通过巨大的文件进行流式传输，或者工作集太大而无法缓存。不缓存文件数据使得客户端代码和总体系统的代码得以简化，因为无需编写代码解决缓存一致性的问题（不过客户端是缓存元数据的）。
• chunk服务器不需要缓存文件数据是因为 chunk 以本地文件的方式保存，Linux 操作系统的文件系统缓存会把经常访问的数据缓存在内存中。

2.4 单个Master

单一的 Master 节点策略大大简化了系统设计。单一的 Master 节点能够通过全局信息精确定位 chunk 的位置，并做出复制决策。不过必须最小化在读写中 master 的调用次数，防止 master 成为 GFS 系统的性能瓶颈。客户端永远不通过 Master 节点直接读写文件数据，而是向 master 节点请求应联系的 chunkserver，并将这些元数据缓存一段时间，后续操作直接与 chunkserver进行。

以上图GFS架构为例，在一次简单读取操作中：

1. 客户端将文件名和字节偏移量转换成文件的 chunk索引（chunk_index = offset / chunk_size），并将文件名和 chunk 索引发送给 master 节点。
2. master 节点返回相应的 chunk 句柄和副本的位置信息，客户端将这些信息缓存。
3. 客户端将请求发送给一个副本，通常选择最近的副本，请求包含 chunk 句柄和字节范围。在后续对该 chunk 的读取操作中，客户端无需再次与 master 节点通讯，除非缓存的元数据信息过期或文件被重新打开。

客户端通常会在一次请求中查询多个 chunk 信息，master 节点的回复可能包含后续 chunk 的信息，这些额外信息在避免未来多次通讯的同时，不增加额外代价。这种设计保证了系统的高效性，减少了 master 节点的负担，提高了整体性能。

2.5 chunk大小

chunk 的大小是 GFS 的关键设计参数之一，GFS 选择了 64MB 的 chunk 大小，这远大于一般文件系统的 block 大小。每个 chunk 的副本都以普通 Linux 文件的形式保存在 chunkserver上，并且只有在需要时才扩大，采用惰性空间分配策略避免了内部碎片造成的空间浪费。

将 chunk 设置为 64MB 这么大，有以下几个有点：

1. 它减少了客户端和 master 节点之间的通信需求。因为一次与 master 节点通信即可获取 chunk 的位置信息，之后可以对同一个 chunk 进行多次读写操作。
2. 较大的 chunk大小使客户端能够对同一个 chunk 进行多次操作，通过与 chunkserver保持较长时间的 TCP 连接来减少网络负载。
3. 较大的 chunk大小减少了 master 节点需要保存的元数据数量，允许将所有元数据放在内存中，从而提高访问速度。

然而，较大的 chunk 大小也有缺点。小文件包含的 chunk 较少，甚至只有一个 chunk。当多个客户端频繁访问同一个小文件时，存储这些 chunk 的服务器容易成为热点。在实际应用中，这种情况较少发生，因为程序通常是连续读取包含多个 chunk 的大文件。

但将GFS应用于批处理队列系统中，热点问题曾经出现过：一个可执行文件保存在一个单一 chunk 中，当数百台机器同时启动这个文件时，存储这个 chunk 的服务器因并发请求导致系统局部过载。为解决这个问题，GFS通过增加可执行文件的复制参数和错开程序启动时间来缓解。此外，一个长效解决方案是允许客户端在这种情况下从其他客户端读取数据。

2.6 元数据

master 中主要存储三种类型的元数据：

1. 文件和 chunk 的命名空间；
2. 文件和 chunk 的映射；
3. 每个 chunk 的副本的位置。

所有的元数据都存储在 master 的内存里。前两种类型也会通过在操作日志(operation log)上记录修改来持久化，操作日志文件存储在 master 的本地磁盘上，同时日志会被复制到其它的远程master服务器上。使用日志使得我们能够简单可靠的更新 master 的状态，，而不用担心 master 崩溃导致的不一致性的风险。master 不会持久的存储 chunk 位置信息，而是会在 master 启动时或一个 chunkserver加入集群时向 chunkserver轮询其 chunk 信息。

2.6.1 内存中的数据结构

GFS 的设计将所有元数据保存在内存中，使 master 的操作速度非常快。这种设计允许 master 在后台简单而高效地周期性扫描所有状态信息，实现如 chunk 垃圾收集、在 chunkserver失效的时重新复制数据、通过 chunk 的迁移实现跨 chunkserver的负载均衡以及磁盘使用状况统计等功能。

虽然将元数据保存在内存中会使 chunk 的数量和系统的承载能力受限于 master 的内存大小，但在实际应用中，这并不是严重问题。具体而言，master 管理每个 64MB 的 chunk 只需不到 64字节的元数据。由于大多数文件包含多个 chunk，绝大多数chunk 都是满的，只有最后一个 chunk 可能部分填充。同样，每个文件在命名空间中的数据大小通常在 64 字节以下，因为文件名经过前缀压缩。

即便需要支持更大的文件系统，增加 master 的内存成本也相对较低。通过增加少量内存，可以使元数据全部保存在内存中，从而增强系统的简洁性、可靠性、高性能和灵活性。

2.6.2 chunk位置信息

master 不持久化存储哪个 chunkserver包含指定 chunk 副本的信息，master 只是在启动时会轮询 chunkserver以获取这些信息，并通过控制 chunk 位置分配和定期的心跳信息监控chunk服务器状态保持最新。

Google起初尝试将 chunk 位置信息持久化保存在 master 上，但发现启动时轮询 chunkserver并定期更新更为简便。这种设计简化了在 chunkserver加入、离开、更名、故障和重启时的数据同步问题，适应了大规模集群中频繁发生的事件。

这个设计的另一个理解思路：只有 chunkserver才能最终确定一个 chunk 是否在其硬盘上。在 master 上维护全局视图是不现实的，因为 chunkserver的错误可能导致 chunk 自动消失，或者操作人员可能重命名 chunkserver。这种方法确保了系统的简洁性和可靠性。

2.6.3 操作日志

操作日志包含关键的元数据变更历史记录，是元数据唯一的持久化存储和判断同步操作顺序的逻辑时间基线。每个文件和 chunk，还有它们的版本， 都由它们创建的逻辑时间唯一的、永久的标识。

日志文件必须确保完整性。只有在元数据变更被持久化后，日志才对客户端可见，以防止丢失文件系统或最近的客户端操作。为此，日志会被复制到多台远程机器，只有在本地和远程机器都写入日志后，master 才响应客户端请求。master 会收集多个日志记录后批量处理，以减少写入和复制对系统性能的影响。

在灾难恢复时，master 通过重演操作日志恢复文件系统。为了缩短启动时间，日志必须足够小。当日志增长到一定量时，master 会进行 checkpoint，将所有状态数据写入 checkpoint 文件。恢复时，master读取 Checkpoint 文件并重演之后的日志文件即可。Checkpoint 文件以压缩 B-树形式存储，可以直接映射到内存，在用于命名空间查询时无需额外的解析，提高了恢复速度和系统可用性。

创建 Checkpoint 文件时，master 确保不会阻塞正在进行的操作，通过独立线程切换到新的日志文件和创建新的 Checkpoint 文件。生成一个 Checkpoint 文件大约需要一分钟，完成后Checkpoint会被写入本地和远程硬盘。

master 恢复仅需最新的 Checkpoint 文件和后续日志文件。虽然旧的 Checkpoint 文件和日志文件可以删除，但通常会保留一些历史文件以应对灾难性故障。Checkpoint 失败不会对正确性产生任何影响，因为恢复功能的代码可以检测并跳过没有完成的 Checkpoint 文件（使用前一个完整的 Checkpoint 文件和之后的操作日志来恢复系统）。

2.7 一致性模型

GFS 有一个宽松的一致性模型，很好地支持我们的高度分布式应用程序，但是实现起来依然简单且高效。

我们现在讨论 GFS 如何保证一致性，以及这对应用程序来说有何意义。我们也会强调 GFS 如何维护这些保证，但是更详细的内容将在本文的其他部分来说。

2.7.1 GFS一致性保障机制

文件命名空间的修改（例如，文件创建）是原子性的，且仅由 master 控制。命名空间锁保证了操作的原子性和正确性（详见4.1），而操作日志定义了这些操作的全局顺序（详见2.6.3）。

数据修改后的文件区域状态取决于操作类型、成功与否以及是否同步修改。下表总结了各种操作的结果。

• 如果所有客户端，无论从哪个副本读取，读到的数据都一样，那么我们认为文件区域是consistent；
• 如果对文件的数据修改之后，文件区域是一致的，并且客户端能够看到写入操作全部的内容，那么这个 region 是defined。

其中，对于一个文件区域，只要所有客户端看到的数据都是一样的，那这个区域就是 consistent 的。在 consistent 的前提下，如果所有修改都已经被写入，就是 defined 的。consistent 是 defined 的子集。即 defined 的一定是 consistent 的，但 consistent 的不一定是 defined 的。

当一个数据修改操作成功执行，并且没有受到同时执行的其它写入操作的干扰（即串行修改），那么受影响的区域就是 defined（隐含了 consistent ）：所有的客户端都可以看到写入的内容。

当多个并行修改操作成功完成后，文件区域处于consistent但undefined的状态：即所有的客户端看到的数据是一样的，但这并不意味着每个修改都已经被写入。一般来说，写入的内容由多个修改的混合片段组成。

失败的修改操作导致文件区域inconsistent (因此也是 undefined )：不同客户端在不同时间看到的数据不同。后面我们将描述应用如何区分 defined 和 undefined 的区域。应用程序没有必要再去细分 undefined 区域的不同类型。

数据修改操作分为写入或者记录追加两种：

• 写入操作：数据写在应用程序指定的文件偏移位置上。
• 记录追加操作：数据（记录）原子性追加到文件中至少一次（即使是并发修改），但偏移位置由 GFS 选择（3.3）。

作为对比，一个普通的追加操作仅仅是一个在客户端认为是当前文件末尾的偏移处的写入操作。GFS 返回给客户端一个偏移量，表示包含写入记录的 defined 区域的起点。另外，GFS 可能会在文件中间插入填充数据或者重复记录。这些数据占据的文件区域被认定是 inconsistent（即上表 中的 defined interspersed with inconsistent，即 defined 区域中穿插了 inconsistent 区域，但这些区域不会影响读取数据的结果，因为会被过滤掉）， 这些数据通常比用户数据小的多。

经过一系列成功的修改操作后，GFS 确保被修改的文件区域是defined的，并包含最后一次修改操作写入的数据。GFS 通过以下措施确保这一点：

1. 对chunk的所有副本的修改操作顺序一致。
2. 使用 chunk 版本号检测副本是否因其所在的 chunkserver宕机而错过了修改操作导致失效。失效的副本不再进行修改操作，master 也不会返回该副本的位置信息给客户端，失效副本会被垃圾收集系统尽快回收。

由于 chunk 位置信息会被客户端缓存，在信息刷新前，客户端可能从失效的副本读取数据。只有当缓存条目超时，或文件被重新打开时，这个问题才能解决，因为条目超时或重新打开文件会清除客户端缓存中的所有跟这个文件有关的 chunk 信息。此外，大多数文件只进行追加操作，因此失效副本通常返回一个提前结束的 chunk 而不是过期的数据（也就是说，数据还是有效的数据，只是返回的偏移位置不对）。当 Reader 程序 重新尝试联络 master 时，会立刻得到最新的 chunk 位置信息。

即使修改操作成功执行后很长时间，组件故障仍可能损坏或删除数据。GFS 通过 master 和所有 chunkserver的定期“握手”找到失效的 chunkserver，并使用校验和检测数据是否损坏。一旦发现问题，数据将尽快利用有效副本进行恢复。只有当一个 chunk 的所有副本在 GFS 检测到错误并采取应对措施之前全部丢失，chunk 才会不可逆转地丢失。通常，GFS 的反应时间（master 节点检测到错误并采取应对措施）为几分钟。即便如此，chunk 也只是不可用而非损坏，应用程序会收到明确的错误信息而非损坏的数据。

2.7.2 对应用程序的影响

使用 GFS 的应用程序可以利用一些简单的技术来实现宽松的一致性模型，也可以实现其他目标功能，包括尽量采用追加写入而不是覆盖、Checkpoint、写入自验证和自识别的记录。

在实际应用中，我们所有的应用程序对文件的写入操作都尽量采用追加方式而不是覆盖方式。例如，应用程序从头到尾写入数据生成一个文件，写入完成后自动将文件改名为一个永久文件名，或者定期进行 Checkpoint，记录成功写入的数据量。Checkpoint 文件可以包含程序级别的校验和。Readers 仅校验并处理上个 Checkpoint 之后的文件区域，这些区域的状态是defined的。这种方法满足了我们的一致性和并发处理需求。追加写入比随机写入更加高效，对应用程序的失败处理更具弹性。Checkpoint 允许 Writer 以渐进方式重新开始，并防止 Reader 处理已成功写入但从应用程序的角度来看未完成的数据。

另一个典型的应用场景是，许多应用程序并行追加数据到同一个文件，例如进行结果合并或者是一个生产者-消费者队列。记录追加方式的“至少一次追加”特性保证了 Writer 的输出。Readers 可以通过以下方法处理偶然性的填充数据和重复内容：Writers 在每条写入记录中包含额外信息，例如 Checksum，用来验证有效性。Reader 可以利用 Checksum 识别并丢弃额外的填充数据和记录片段。如果应用不能容忍偶尔的重复内容，可以使用记录的唯一标识符来过滤重复数据，这些唯一标识符通常用于命名程序中处理的实体对象，如 web 文档。这些记录 I/O 功能都包含在我们共享的程序库中，并适用于 Google 内部的其他文件接口实现。这样，相同序列的记录，加上偶尔出现的重复数据，都能正确分发给 Reader。

3 系统交互

Google 设计 GFS 系统一个重要的原则是最小化所有操作和 master 的交互（因为 master 只有一个，必须减轻 master 的压力）。在这个背景下，我们现在来说客户端、master 和 chunk服务器如何互动以实现数据修改、原子记录追加(append)，以及快照(snapshot)。

3.1 租约（lease）和变更顺序

变更是一个会改变 chunk 内容或者元数据的操作（如写入或记录追加），会在 chunk 的所有副本上执行。为了保持多个副本间变更顺序的一致性，GFS 采用了租约（lease）机制。master 节点为 chunk 的一个副本（主 chunk）建立租约，初始租期为 60 秒。主 chunk 对所有更改操作进行序列化，所有副本遵从这个序列进行修改。因此，修改操作全局的顺序首先由 master 选择的租约的顺序决定，然后由租约中主 chunk 分配的序列号决定。

只要 chunk 被修改了，主 chunk 就可以申请更长的租期，通常会得到 master 的确认并收到租约延长的时间。 这些租约延长请求和批准的信息通常都是附加在 master 和 chunkserver之间的心跳消息中来传递。有时 master 会试图提前取消租约（例如，master 想取消在一个已经被改名的文件上的修改操作）。即使 master 和主chunk失去联系，它仍然可以安全地在旧的租约到期后和另外一个chunk副本签订新的租约。

在下图中，我们通过列出 写入操作的控制流描述了这个过程，并且用数字标记了步骤顺序。

1. 客户端向master询问哪个chunk服务器持有当前的租约，以及其他副本的位置。如果没有一个chunk服务器持有租约，master则会选择其中一个副本建立一个租约（图中没有显示此步骤）；
2. master将主chunk的标识符以及其他副本（又称二级副本）的位置返回给客户端。客户端缓存这些数据以便后续的操作。只有在主 chunk 不可用，或者主 chunk 回复信息表明它已不再持有租约的时候，客户端才需要重新跟 master 联系。
3. 客户端把数据 push 给所有的副本，客户端可以以任意的顺序 push。chunkserver接收到数据并保存在它的内部 LRU 缓存中，一直到数据被使用或者过期交换出去。通过将数据流与控制流解耦，我们可以基于网络拓扑情况调度昂贵的数据流来提高性能，而不管哪个 chunk服务器是主 chunk。
4. 当所有的副本都确认接收到了数据，客户端发送写请求到主chunk服务器。这个请求标识了之前推送到所有副本的数据。主 chunk 为接收到的所有操作分配连续的序列号，这些操作可能来自不同的客户端，序列号保证了操作顺序执行。它以序列号的顺序把操作应用到它自己的本地状态中。
5. 主chunk把写请求传递到所有的二级副本。每个二级副本依照主chunk分配的序列号以相同的顺序执行这些操作。
6. 所有完成了操作的二级副本向主chunk 回复，表明它们已经完成了操作。
7. 主 chunk 回复客户端。任何副本产生的任何错误都会返回给客户端。在出现错误的情况下，写入操作可能在主chunk和一些二级副本执行成功（因为是主chunk 先成功完成修改后，才会让二级副本开始应用修改，如果主 chunk 失败了，二级副本就不会收到序列号以及应用更改的命令）。客户端的请求被确认为失败，被修改的区域处于inconsistent的状态。我们的客户端代码通过重复执行失败的操作来处理这样的错误。在从头开始重复执行之前，客户端会先从步骤（3）到步骤（7） 做几次尝试。（Q：已经完成操作或部分完成操作的副本，接收到重试的数据后，如何处理？A：直接在文件末尾（最后一个 chunk 末尾）继续写入，之前成功的二级副本会重复写入，去重任务由读取数据的客户端来完成。）

如果应用程序一次写入的数据量很大，或者数据跨越了多个 chunk，GFS 客户端代码会把它们分成多个写操作。这些操作都遵循前面描述的控制流程，但是可能会被其它客户端上同时进行的操作打断或者覆盖。 因此，共享的文件区域的尾部可能包含来自不同客户端的数据片段，尽管如此，由于这些分解后的写入操作在所有的副本上都以相同的顺序执行完成，chunk 的所有副本都是一致的。这使文件 region 处于 2.7 节描述 的consistent但是undefined的状态。

3.2 数据流

为了提高网络效率，GFS采取了将数据流和控制流分开的措施。在控制流从客户端到主 chunk再到所有二级副本的同时，数据以管道方式顺序沿着精心选择的 chunkserver链推送，充分利用每台机器的带宽，避免网络瓶颈和高延时连接，最小化数据推送延时。

数据顺序沿着一个 chunkserver链推送，而不是分散推送（如树型拓扑结构），以充分利用每台机器的出口带宽，实现最快速度的传输，而不分散带宽。为避免网络瓶颈和高延迟连接，每台机器尽量选择网络拓扑中离自己最近且尚未接收到数据的机器作为目标推送数据。例如，客户端将数据推送到最近的 chunkserver S1，S1 推送到 S2，以此类推，基于 IP 地址计算节点距离。

利用基于 TCP 连接的管道式数据推送方式最小化延迟。chunkserver接收到数据后立即向前推送，利用全双工交换网络的优势，传输不会减慢接收速度。在无网络拥塞情况下，传送 $B$ 字节的数据到 $R$ 个副本的理想时间为 $\frac{B}{T} + RL$（$T$ 是网络吞吐量，$L$ 是传输延迟）。通常，我们的网络连接速度是 100Mbps，传输 1MB 数据的理想时间约为 80ms。

3.3 原子的记录追加

GFS 提供了一种原子的记录追加操作，客户端只需指定要写入的数据，GFS 保证至少一次原子写入成功执行（即写入一个顺序的byte流），写入数据追加到 GFS 指定的偏移位置，并返回该偏移量给客户端。类似于 Unix 的 O_APPEND 模式，多个并发写操作无竞态条件。

记录追加在分布式应用中频繁使用，特别是在多个客户端并行追加数据的情况下。传统写入需要复杂的同步机制，如分布式锁管理器，而记录追加简化了这种需求，常用于生产者/消费者队列系统或数据合并文件。

记录追加遵循 3.1 节描述的控制流程，主 chunk 有额外控制逻辑。客户端将数据推送到最后一个 chunk 的所有副本，然后发送请求给主 chunk。主 chunk 检查是否超出最大大小（64MB），如果超出，则填充到最大大小并通知二级副本做同样的操作，然后回复客户端要求其对下一个chunk重新进行记录追加。通常情况下，主 chunk 追加数据并通知二级副本写入相同位置，最后回复客户端操作成功。

如果记录追加在任何副本上失败，客户端需要重新操作，可能导致同一个chunk的不同副本包含不同数据。GFS 只保证数据整体原子性写入至少一次，而不保证字节级别一致。成功执行操作的数据区域是defined的（且consistent的），否则是inconsistent的（且undefined义的）。程序可以处理这些inconsistent区域。

3.4 快照

快照操作在 GFS 中几乎瞬间完成，且不干扰其他操作。用户可以用快照快速创建数据集的分支拷贝或在实验前备份当前状态，方便之后提交或回滚。

就像AFS（Andrew File System，一种分布式文件系统），GFS 使用标准的“写时复制”（copy-on-write）技术实现快照。当 master 收到快照请求时，它会取消作快照的文件的所有 chunk 的租约，确保后续写操作必须与 master 交互，使 master 有机会先创建 chunk 的新拷贝。

租约取消或过期后，master 将操作记录到硬盘日志，并通过复制源文件或目录的元数据将变化反映到内存中。新创建的快照文件与源文件共享相同的 chunk 地址。

快照操作后，当客户端首次写入 chunk C 时，会先请求 master 查询当前租约持有者。master 发现 chunk C 的引用计数超过 1（写时复制方法创建快照时是给这个chunk加一个引用计数，没有立刻真的拷贝，一个 chunk 的引用计数大于 1 的话就代表这个 chunk 是某个快照的一部分，要保留原样数据的。当这个 chunk 上有新的写入的时候，这个 chunk 才会真的被复制，客户端在新复制的 chunk 上写入，而原来的旧 chunk 被快照继续引用），不立即回复客户端，而是选择新的 chunk 句柄 C'，并要求所有持有 chunk C 副本的服务器创建 C'。通过在本地创建新的 chunk 避免了网络复制，提高了效率。master 确保新 chunk C'的一个副本拥有租约后回复客户机，客户机即可正常写入该 chunk。

4 Master操作

master 执行所有的命名空间操作。此外，它还管理着整个系统里所有 Chunk 的副本：

1. master 决定 chunk 副本的存储位置；
2. 创建新的 chunk 和它的副本；
3. 协调各种各样的系统范围内的活动以保证 chunk 被完全拷贝；
4. 在所有的 chunkserver上做负载均衡；
5. 回收不再使用的存储空间。

下面我们深入讨论下上述的几点。

4.1 命名空间管理和锁

在 GFS 中，master 节点的操作可能耗时较长，例如快照操作需取消所有相关 chunk 的租约。为避免延缓其他操作，GFS 允许多个操作同时进行，并通过命名空间的区域锁保证顺序正确。

GFS 命名空间是一个全路径与元数据映射的查找表，采用前缀压缩高效存储在内存中。不同于传统文件系统，GFS 不支持列出目录下所有文件的结构，也不支持文件或目录的链接。每个节点（绝对路径的文件名或目录名）有一个关联的读写锁。

每个 master 操作开始前都要获得相关锁。通常，涉及路径/d1/d2/.../dn/leaf 的操作需要获得/d1，/d1/d2，…，/d1/d2/.../dn 的读锁，以及/d1/d2/.../dn/leaf 的读写锁。根据操作不同，leaf 可以是文件或目录。例如，在/home/user 快照到/save/user 时，锁机制防止创建文件/home/user/foo。快照操作获得/home 和/save 的读锁及/home/user 和/save/user 的写锁；文件创建操作获得/home 和/home/user 的读锁及/home/user/foo 的写锁。由于/home/user 锁冲突，这两个操作顺序执行。文件创建操作不需要获取父目录的写入锁，因为这里没有“目录”，或者类似 inode 等用来 禁止修改的数据结构。文件名的读取锁足以防止父目录被删除。

这种锁方案支持对同一目录的并行操作。例如，可在同一目录下同时创建多个文件：每个操作获取目录名的读锁和文件名的写锁。目录名的读锁防止目录被删除、改名或快照；文件名的写锁序列化文件创建操作，确保不会多次创建同名文件。

由于命名空间节点众多，读写锁采用惰性分配策略，不再使用时立刻删除。锁的获取依据全局一致的顺序避免死锁：首先按命名空间层次排序，在同一层次内按字典顺序排序。

4.2 副本放置

GFS 集群采用高度分布的多层布局结构，典型拓扑包括数百个 chunkserver分布在多个机架上，由来自同一或不同机架的数百个客户机访问。通信可能跨越一个或多个网络交换机，且机架出入带宽可能较小。多层分布架构带来数据灵活性、可靠性和可用性挑战。

chunk 副本位置选择旨在最大化数据可靠性和可用性，以及网络带宽利用率。仅在多台机器上存储副本不足以达到目标，需在多个机架间分布储存 chunk 的副本。这保证即使整个机架故障或掉线，某些副本仍可用，且网络流量尤其读操作可利用多个机架的带宽。尽管写操作需与多个机架设备通信，但这是值得的。

4.3 创建、重新复制、重新平衡

chunk 副本在 GFS 中有三个主要用途：chunk 创建、重新复制和重新平衡。

1. Master 节点在创建 chunk 时选择存放初始空副本的位置，考虑以下因素：

   • 优先选择硬盘使用率低于平均值的 chunkserver，以平衡硬盘使用率。
   • 限制每个 chunkserver上最近 chunk 创建操作的次数，以减少写入操作的集中度。
   • 分布在多个机架之间，以提高可靠性。

2. 当有效副本数量低于指定复制因数时，master 节点会重新复制 chunk，可能原因包括：

   • chunkserver不可用或报告副本损坏。

   • 磁盘错误或复制因数增加。

   • 重新复制优先级基于现有副本数量与复制因数的差异、chunk 活跃状态及其对客户端的影响。

   master 选择优先级最高的chunk，命令 chunkserver克隆副本，选择新副本的位置的策略类似于 chunk 创建。为防止克隆操作超载网络，master会限制克隆操作数量及其读请求频率。

3. master 周期性检查副本分布，移动副本以优化硬盘空间利用和平衡。在这个过程中，master 渐进式填充新 chunkserver，避免短期内填充过载。副本位置选择策略同上，并优先移走剩余空间低于平均值的服务器上的副本，以平衡整体硬盘使用率。

4.4 垃圾回收

GFS 在文件删除后不会立即回收物理空间，而是采用惰性垃圾回收策略，仅在文件和 chunk 级的常规垃圾收集中进行。这样简化了系统设计，提高了可靠性。

4.4.1 机制

当一个文件被应用程序删除时，master立刻把删除操作以日志的方式记录下来。但是，master 并不马上回收资源，而是把文件名改为一个包含删除时间戳的、隐藏的名字。当 master 对文件系统命名空间做常规扫描的时候，它会删除所有三天前的隐藏文件（这个时间间隔是可以设置的）。在文件被真正删除之前，它们仍旧可以用新的特殊的名字（即被重命名后的带有删除时间戳的名字）读取，也可以通过把隐藏文件改名为正常显示的文件名的方式“取消删除”。当隐藏文件被从命名空间中删除，master 内存中保存的这个文件的相关元数据才会被删除。这也有效的切断了文件和它包含的所有 chunk 的连接。

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

4.4.2 讨论

GFS 的垃圾回收方案简单可靠。可以轻易得到chunk 的引用：存储在 master 的文件到chunk的映射表中；也可以轻松得到chunk所有副本：以Linux文件的形式存储在 chunkserver指定目录下。所有master 不能识别的副本即为“垃圾”。

垃圾回收在空间回收方面相比直接删除有几个优势。

1. 在大规模分布式系统中，组件失效是常态。chunk 可能在某些服务器上创建成功，但在其他服务器上失败，失败的副本处于无法被 master 识别的状态。副本删除消息可能丢失，master 必须重新发送失败的删除消息， 包括自身的（元数据）和 chunkserver的。垃圾回收提供了一致的、可靠的清除无用副本的方法。
2. 垃圾回收将存储空间回收操作合并到 master 的规律性后台活动中，如例行扫描和与 chunkserver的握手。因此操作被批量执行，减少开销。回收在 master 相对空闲时进行，提高了响应速度。
3. 延迟回收为意外、不可逆转的删除操作提供了安全保障，防止误删。

虽然延迟回收可能阻碍存储优化，尤其在空间紧缺时。但可以通过显式再次删除文件可以加速回收。用户可以为不同命名空间设置不同的复制和回收策略，以优化存储使用。

4.5 过期副本检测

当 chunkserver失效时，chunk 的副本可能因错失一些修改操作而过期。master 通过保存每个 Chunk 的版本号来区分当前副本和过期副本。每次与 chunk 签订新租约时，master 都会增加 chunk 的版本号，并通知最新的副本，且这些副本会将新的版本号记录在其持久化存储中。这个过程在任何客户端得到通知前完成，因此也是在对这个 chunk 开始写之前完成的。如果某个副本所在的 chunkserver正好失效，那么其版本号就不会被更新。待该 chunkserver重新启动并向 master 报告其持有的 chunk 及相应版本号时，master 会检测出其包含过期的 chunk。若 master 发现一个比其记录的版本号更高的版本号，会认为之前签订租约的操作失败，并选择更高的版本号作为当前版本号。

master 在例行垃圾回收过程中移除所有过期副本。在此之前，master 在回复客户端的 chunk 信息请求时，master 实际上会认为根本不存在一个过期的副本（也就是说，给客户端返回的 chunk 列表中可能包含过期的 chunk，客户端有可能去读过期的 chunk。GFS 是弱一致性的）。另外一重保障措施是，master 在通知客户端哪个 chunkserver持有租约或指示 chunkserver从哪个 chunkserver进行克隆时，消息中都会附带 chunk 的版本号。客户端或 chunkserver在执行操作时会验证版本号，以确保总是访问当前版本的数据。

5 容错和诊断

5.1 高可用性

在 GFS 集群中，高可用性的策略主要包括快速恢复和复制。

• 首先，对于快速恢复，无论是 master 还是 chunkserver，它们都能在数秒内恢复状态并重新启动。系统不区分正常关闭和异常关闭，通常通过直接终止进程来关闭服务器。
• 其次，对于 chunk 复制，每个 chunk 都被复制到不同机架上的不同 chunkserver上，并可以根据需要设定不同的复制级别。当有 chunkserver 离线或发现数据损坏时，master 通过克隆已有的副本来确保每个 chunk 都被完整复制。
• 最后，master 的状态也需要复制以保证其可靠性。master 的所有操作日志和 checkpoint 文件都被复制到多台机器上，确保操作日志写入备用节点和本机磁盘，以支持失败后的快速重新启动。此外，还存在“影子”master，用于提供文件系统的只读访问。这些“影子”服务器能够保持状态最新，并通过与主 master 相同的方式处理数据结构的更改。它们定期从 chunkserver拉取数据，并与其握手以确定状态，从而确保系统的高可用性。

5.2 数据完整性

每个 Chunkserver使用 checksum 来检查保存的数据是否损坏。由于 GFS 集群通常包含数百台机器和数千块硬盘，磁盘损坏导致的数据丢失或损坏在读写过程中是常见的。虽然可以通过其他副本恢复数据，但跨服务器比较副本以检查数据完整性并不实际。此外，由于 GFS 允许存在有歧义的副本，特别是在原子记录追加操作中，副本并不总是完全一致的（副本不是 byte-wise 完全一致的）。因此，每个 chunkserver必须独立维护 checksum 来校验自己的副本完整性。

每个 chunk 被分为 64KB 的块，每个块对应一个 32 位的 checksum，存储在内存和硬盘上，并记录在操作日志中。在读取数据之前，chunkserver会校验与读取范围重叠的数据块的checksum。如果 checksum 不匹配，服务器返回错误信息并通知 master，之后从其他副本读取数据并进行克隆恢复。一旦新的副本就绪，master 通知 chunkserver删除错误的副本。

checksum 对读操作性能影响很小，因为大部分读操作涉及多个块，而只需读取少量额外数据进行校验。通过对齐读操作到 checksum块的边界，可以进一步减少额外读取操作的影响。此外，checksum 的查找和比较不需要额外的 I/O 操作，计算可以与 I/O 操作并行进行。

针对追加写入操作，checksum 的计算进行了优化，因为这种操作在 GFS 工作中占很大比例。只需增量更新最后一个不完整块的 checksum，并使用新写入的数据计算新的 checksum。如果最后一个checksum块损坏，问题会在下次读取时被发现。

相比之下，覆盖写操作需要读取和校验被覆盖范围内的第一个和最后一个块，操作完成后重新计算和写入新的 checksum。如果不校验第一个和最后一个被写的块，新的 checksum 可能会隐藏未覆盖区域内的数据错误。

当 chunkserver空闲时，会扫描和校验每个不活动 chunk 的内容，以发现很少被读取的 chunk 是否完整。一旦发现数据损坏，master 可以创建新的正确副本并删除损坏的副本，避免非活动的损坏 chunk 误导 master，使其认为副本数量足够。

5.3 诊断工具

详尽的、深入细节的诊断日志在问题隔离、调试和性能分析等方面提供了极大的帮助，而所需开销却很小。没有日志，我们很难理解短暂的、不重复的机器间消息交互。GFS 服务器会生成大量日志，记录关键事件（如 chunkserver 的启动和关闭）以及所有 RPC 请求和回复。这些日志可以随时删除，不影响系统的正确运行，但我们在存储空间允许的情况下尽量保留这些日志。

RPC 日志详细记录了网络上的所有请求和响应，但不包括读写的文件数据。通过匹配请求与回应，并收集不同机器上的 RPC 日志，我们可以重现所有消息交互来诊断问题。这些日志还用于跟踪负载测试和进行性能分析。

日志对性能的影响很小，因为日志写入是顺序且异步的。最近的事件日志保存在内存中，用于持续的在线监控。

6 经验

在构建和部署 GFS 的过程中，Google 遇到了许多问题，包括操作和技术方面的挑战。最初，GFS 主要作为生产系统的后端文件系统，后来逐渐支持研究和开发任务，增加了权限和配额等功能。

最大的难题是磁盘和 Linux 相关问题。许多磁盘声称支持 Linux IDE 驱动，但实际应用中情况不一，导致协议不匹配，数据可能因内核问题而被破坏。为此，Google 使用校验和来验证数据，并修改内核处理这些问题。

早期使用 Linux 2.2 内核时，fsync() 效率与文件大小相关而非修改部分大小相关，导致操作日志文件过大时出现问题，尤其是在尚未实现checkpoint 的时候。Google费了很大的力气用同步写来解决这个问题，但是最后还是移植到了 Linux2.4 内核上。

另一个问题是单个读写锁，导致系统偶尔超时。Google 通过用 pread() 替代 mmap() 并增加额外复制操作解决了这个问题。

在任意地址空间的线程在磁盘读入（读锁）时或 mmap() 调用（写锁）时必须持有锁。即使系统负载很轻，也会偶尔超时。Google花费大量精力查找资源瓶颈或硬件问题，最终发现磁盘线程在交换数据到磁盘时，锁住了当前网络线程，阻止其将新数据映射到内存。由于性能主要受限于网络接口而非内存复制带宽，Google用 pread() 替代 mmap()，通过额外复制操作解决了问题。