谷歌文件系统(Google File System，GFS)

原文链接：https://pdos.csail.mit.edu/6.824/papers/gfs.pdf

摘要

我们设计并实现了 GFS：为大型分布式数据密集型应用提供的可扩展分布式文件系统。GFS 可在廉价的商用主机上提供容错能力，并为大批量客户端提供高综合性能。

虽然和已有的分布式文件系统的设计目标有共通之处，基于对我们当前和未来的应用程序工作负载和技术环境的观察，我们发现我们的需求背离了部分早期对文件系统的假设。这使得我们重新审视传统设计选择并探索完全不同的设计方案。

GFS 成功满足我们的存储需求。它作为 Google 内部的存储平台被广泛使用，用于生成和处理我们的服务以及大型数据集研究所需的数据。

在本文中，我们提出了旨在支持分布式应用的文件系统扩展，讨论了我们设计的各个方面，并报告了在小型基准测试和实际应用中的性能表现。

1. 介绍

为了应对 Google 内部迅速增长的对数据处理的需求，我们设计并实现了 GFS。GFS 和之前的许多分布式文件系统都有相同的目标，例如：性能、扩展性、可靠性和可用性。然而，它的设计基于对我们现有和未来的应用程序工作负载和技术环境的观察，然而观察结果背离了早期对文件系统的假设。我们重新审视传统的选择并探索全新的设计。

第一，组件故障是常态而不是偶尔发生。该文件系统中包含几百台使用廉价商用设备构成的存储机器，并支持大量客户端访问。组件的数量和质量肯定会导致部分组件在某些时间无法工作，而且另一部分组件可能无法从宕机中恢复。我们遇到过由应用程序 bug、操作系统 bug、运维人员问题、磁盘、内存、连接器、网络、电源等故障导致的问题。因此，持续监控、问题检测、容错和自动恢复都是该系统所必须的。

第二，和传统标准相比，该文件系统中的文件都比较大。几 GB 的文件都是很常见。每个文件通常包含很多应用程序产生的数据，例如网络文档。当我们定期处理包含几十亿个对象的 TB 级数据时，即使文件系统支持，管理几十亿个 KB 级的文件也是困难的。因此，必须重新设计 IO 操作和块大小。

第三，大多数文件都是通过追加新数据而不是覆写已有数据的方式来修改的。在一个文件中随机写操作基本不存在于生产环境中。数据一旦写入文件，这些文件基本上都是只读的，而且是顺序读取。很多种数据都有这种特征。有些数据用于分析程序扫描使用。有些可能是运行中的应用程序不断生成。有的可能是归档数据。有的可能是一台机器上产生的中间结果，并由另一台机器立即或稍后处理。鉴于这种对大文件的访问方式，追加写成为性能优化和原子性保证的焦点，如果在客户端中缓存数据则丧失了该优点。

第四，共同设计应用程序和文件系统来提高我们的灵活性，进而优化整个系统。例如，我们放宽了 GFS 的一致性模型来简化文件系统，从而为应用程序减轻负担。我们也提供了一个原子追加操作，这样多个客户端可以并发追加数据到同一个文件中，而不需要额外的同步流程。这些内容将在下文讨论。

目前基于不同的目的部署了多个 GFS。最大的拥有超过 1000 个存储节点，超过 300TB 磁盘存储，并由几百个客户端在不同的机器上不间断访问。

2. 设计概览

2.1. 假设

针对我们的需求设计文件系统时，我们所遵循的假设即带来了挑战也带来了机遇。我们之前提到了一些关键的观察结果，现在更详细阐述我们的假设。

• 该系统构建于廉价的商用设备，并且这些设备经常宕机。它必须持续监控自身状态、定期检测、容错并快速恢复。
• 系统存储适量的大文件。我们预计有几百万个文件，每个文件的大小通常为 100 MB 或更大。多 GB 文件是常见情况，应该进行有效管理。系统必须支持小文件，但我们不需要针对它们进行优化。
• 工作负载主要由两种读操作组成：大型流式读取和小型随机读取。在大型流式读取操作中，单个操作通常读取数百 KB，更常见的是 1MB 或更多。来自同一客户端的连续操作通常会读取文件的连续区域。小规模随机读取通常会在某个任意偏移处读取几KB。注重性能的应用程序通常会对它们的小读取进行批处理和排序，以便在文件中稳定地增加偏移量，而不是来回移动。
• 工作负载还有一些追加写文件的大型写入操作。典型的操作大小与读取操作的大小类似。文件一旦写入，就很少被修改。系统支持在文件中随机写少量数据，但是不需要效率很高。
• 系统必须为同时追加写同一文件的多个客户端实现完整高效的语义。我们的文件通常用作生产者-消费者队列或多路数据合并。几百个生产者(每台机器运行一个生产者)将同时追加写到一个文件中。具有最小同步开销的原子操作至关重要。该文件可以支持稍等一段时间读取，也支持消费者同时读取。
• 高持续带宽比低延迟更重要。我们的大多数目标应用程序都注重高速批量处理数据，而很少有应用程序对单个读取或写入有严格的响应时间要求。

2.2. 接口

虽然 GFS 并没有实现 POSIX 等标准 API，它也提供一套熟悉的文件接口。文件在目录中分层管理，并通过路径名唯一确定。我们支持常用的操作：创建、删除、打开、关闭、读取、写入文件。

而且，GFS 支持快照和记录追加写操作。快照以最小的开销创建一个文件或者目录的副本。记录追加写操作允许多个客户端同时追加写同一个文件，并保证了每个客户端追加写操作的原子性。它对于实现多路合并数据和生产者-消费者队列非常有用，许多客户端可以同时追加写这些文件而无需额外的锁机制。我们发现这些类型的文件对于构建大型分布式应用程序非常有价值。快照和记录追加分别在 3.4 和 3.3 节中进一步讨论。

2.3. 架构

一个 GFS 集群包含一个单机 master 和多个块服务器(chunkserver)，该集群可支持多客户端访问。如图 1 所示为该集群结构。

集群的每个节点都是典型商用 Linux 设备并运行用户级进程。块服务器和客户端可以同时运行在同一台机器上，前提是机器的资源充足，并且可以容忍由于用户应用程序代码导致服务器可用性降低。

文件被分为固定大小的块。每个块在创建时都会分配一个全局唯一 64 位块句柄，该句柄唯一识别块。块服务器把块数据以 Linux 文件的形式存在本地磁盘，并且通过块句柄和字节范围来读写块数据。为保证可靠性，每个块都会复制到多台块服务器中。GFS 默认储存三个副本，用户可以为文件名称空间的不同区域指定不同的复制水平。

master 维持所有的文件系统元数据。这包括名称空间、访问控制信息、文件到块的映射关系及这些块的当前位置。它也控制系统级的活动，例如块租约管理、孤儿块的垃圾回收以及在块服务器之间移动块数据。master 定期与每个块服务器通过心跳交互，向其发指令并收集块服务器状态。

GFS 客户端代码链接到实现文件系统 API 的应用程序中，该代码同 master 和块服务器通信并以应用程序的身份读取数据。客户端同 master 交互以获取元数据，但是所有承载数据的通信都是和块服务器进行。GFS 不提供 POSIX API，因此不需要关联到 Linux 的 vnode 层。

客户端和块服务器都不缓存文件数据。客户端缓存几乎没有什么好处，因为大多数应用程序都会处理巨大的文件或由于过大而无法缓存的工作集。没有它们可以消除缓存一致性问题，从而简化客户端和整个系统。(但是，客户端会缓存元数据。) 块服务器不需要缓存文件数据，因为块存储为本地文件，而 Linux 的缓冲区缓存已经将频繁访问的数据保存在内存中。

2.4. 单 master 结构

单 master 结构极大简化了 GFS 的设计并让其可以通过全局数据来制定块数据放置以及副本相关的决策。然而，我们必须尽量减少它对读写的涉及，不让它成为瓶颈。客户端从来不通过 master 读写文件数据。相反的是，客户端向 master 询问需要访问哪些块服务器。它把这些信息缓存一段时间，并且直接和块服务器交互以执行后续操作。

我们根据图 1 来解释一个简单的读操作交互流程。首先，根据固定的块大小，客户端将应用程序指定的文件名和字节偏移量转换为文件内的块索引。然后，它向 master 发送包含文件名和块索引的请求。master 回复对应的块句柄和副本位置。客户端使用文件名和块索引作为键缓存此信息。

然后，客户端向副本之一发送请求，很可能是最近的副本。该请求指定块句柄和该块内的字节范围。之后读取同一个块数据不需要客户端与 master 再进行交互，直到缓存的信息过期或文件被重新打开。事实上，客户端通常会在同一个请求中请求多个块，并且 master 还包含后面的块信息。这些额外的信息几乎不需要过多成本就可以避免后续客户端与 master 的若干通信。

2.5. 块尺寸

块尺寸是关键设计参数之一。我们选择 64MB，比典型的文件系统块尺寸要大。每个块的副本都以 Linux 文件的形式储存在块服务器中，并且仅在需要时进行扩展。惰性空间分配避免了由于内存碎片导致的空间浪费，但是对大型块尺寸来说优势不大。

大型块尺寸有几个重要的优势。首先，它减少了客户端同 master 通信的次数，因为读写同一个块只需要一个同 master 的请求来获取块的位置信息。这种减少对于我们的工作负载来说尤其重要，因为应用程序大多按顺序读写大文件。即使对于小型随机读取，客户端也可以轻松缓存多 TB 的块位置信息。第二，客户端可能在一个块数据中执行许多操作，它可以通过与块服务器维持一个短暂的 TCP 链接以降低网络开销。第三，它也减少了 master 中元数据的大小。我们可以直接在内存中维护元数据，具体的优势将在 2.6.1 节中讨论。

另外，即使有惰性空间分配，大型块尺寸也有优势。一个小文件由一个或几个块组成。储存这些块的块服务器可能由于多个客户端访问而成为热点。实际生产中，热点不会成为主要问题，因为我们的应用程序大多数是顺序读取多个块数据。

然而，热点问题在 GFS 最初应用在批队列系统时也出现过，该系统是把一个可执行文件作为单块写入 GFS 中，并且在几百台设备上启动。储存这些块的块服务器由于几百个并发请求而过载。我们通过以更高的复制因子存储此类可执行文件以及让批处理队列系统错开应用程序启动时间来解决此问题。一个可能的长期解决方案是让客户端在这种情况下从其他客户端读取数据。

2.6. 元数据

master 储存三种主要的元数据：文件和块名称空间，文件到块的映射，以及每个块副本的位置。所有的元数据都在 master 的内存中。前两类数据(名称空间和文件到块的映射)通过把变更操作写入 master 磁盘的操作日志中并复制到其他机器上以持久化。使用日志可以让我们简单、可靠地更新 master 状态，并且避免在 master 崩溃时出现不一致的风险。master 不会持久存储块位置信息。相反，当 master 启动时和块服务器加入集群时 master 会向每个块服务器请求所有的块信息。

2.6.1. 内存中的数据结构

master 在内存中维持元数据，故 master 的读写都很快。master 可以简单有效地在后台扫描它的所有状态。这个定期扫描会进行块垃圾回收、块服务器故障时重新复制副本、移动块以在块服务器之间平衡负载和磁盘空间。4.3 和 4.4 节将会讨论这些活动。

这种仅使用内存的方法的一个潜在问题是块的数量以及整个系统的容量受 master 内存限制。这在生产中并不是一个严重的问题。master 为每个 64MB 块维护不超过 64 字节的元数据。因为大多数文件包含许多块，所以基本上大多数的块都是满的，只有最后一个块没有填满。因为 GFS 使用前缀压缩来紧凑地存储文件名，文件名称空间中每个文件只需要不超过 64 个字节来储存元数据。

如果有必要支持更大的文件系统，那么为 master 添加额外内存的成本对于我们通过将元数据存储在内存中获得的简单性、可靠性、性能和灵活性来说只是一个很小的代价。

2.6.2. 块位置

master 不会为储存哪个块服务器有那些块。它在启动时轮询块服务器获取这些数据。并通过定期的心跳消息来更新块信息。

我们最开始试图让 master 持久化这些块位置数据，但是后来认为让 master 启动时及之后定期从块服务器获取块数据更简单。这消除了在块服务器加入和离开集群、更改名称、宕机、重新启动等时需要保持 master 和 块服务器数据同步的问题。这些事件在数百台服务器的集群中经常发生。

理解这一设计决策的另一种方式是块服务器对自己磁盘上有或没有哪些块拥有最终决定权。尝试在 master 上维护此信息的一致视图是没有意义的，因为块服务器上的错误可能会导致块自己消失(例如，磁盘可能会损坏并被禁用)，或者操作员重命名块服务器

2.6.3. 操作日志

操作日志包含关键元数据更改的历史记录。它是 GFS 的核心。它不仅是元数据的唯一持久记录，而且还充当定义并发操作顺序的逻辑时间线。文件和块，以及它们的版本(参见第 4.5 节)，都是由它们创建的逻辑时间唯一且永久地标识的。

因为操作日志很重要，我们必须可靠存储并保证在元数据没有持久化之前不让客户端看到变更结果。否则，即使块数据保存了下来，我们也会丢失整个文件系统或最近的客户端操作。因此，我们将其复制到多台远程主机上，只有在本地和远程将对应日志记录刷新到磁盘后才响应客户端操作。master 在刷新磁盘前将多个日志记录一起批处理，从而减少刷新和复制对整个系统吞吐量的影响。

master 通过重放操作日志来恢复其文件系统状态。为了减少启动耗时，我们必须保持该日志较小。每当日志超过一定大小时，master 都会对当前状态设置检查点，以便 master 可通过从磁盘上的最近检查点和之后的操作日志进行系统恢复。检查点采用紧凑的 B 树形式，可以直接映射到内存并用于名称空间查找，无需额外解析。这进一步加快了恢复速度并提高了可用性。

设置检查点可能需要一段时间，因此 master 内部创建检查点时不能阻塞后续的操作。master 会切换到一个新日志文件并在单独的线程中创建新检查点。新检查点包括切换之前的所有变更。对于具有几百万个文件的集群，master 可以在一分钟左右的时间内创建检查点。创建完成后，它会被写入本地和远程磁盘。

系统恢复只需要最近的检查点和后续的日志文件。旧检查点和日志文件可以自由删除，但我们会保留一些检查点和日志文件以容灾。生成检查点期间的失败不会影响正确性，因为恢复代码会检测并跳过不完整的检查点。

2.7. 一致性模型

GFS 具有宽松的一致性模型，可以很好地支持高度分布式应用程序并且实施起来仍然相对简单且高效。我们现在讨论 GFS 的一致性保证及其对应用程序的意义。我们还重点介绍了 GFS 如何维持该一致性保证，但将细节留给本文的其他部分。

2.7.1. GFS 的一致性保证

文件名称空间内的变更操作(例如文件创建)是原子的。它们由 master 互斥处理：名称空间的锁机制保证原子性和正确性(第 4.1 节)；master 的操作日志定义了这些操作的全局总顺序(第 2.6.3 节)。

变更文件数据之后，文件范围内的状态取决于变更操作的类型、变更是否成功以及是否有并发的变更操作。表 1 归纳了这些操作导致的结果。

当所有客户端无论从哪个副本读数据，都能读到相同的数据，就说明该文件区域是一致的(consistent)。如果一个文件区域是一致的，并且所有客户端都能看到是哪些变更操作应用到文件中，说明该文件区域是已定义(defined)：所有的客户端都能看到这些变更写入了什么。

并发的变更操作会导致文件区域变成非定义但是一致：所有客户端能看到相同的数据，但是不能反映出来哪些变更写了什么。一般来说，文件区域包括不同变更操作的数据。一个失败的变更可能导致文件区域不一致(并且非定义)：不同的客户端可能在不同的时间点看到不同的数据。我们在下面描述了应用程序如何从非定义的文件区域中识别已定义的文件区域。应用程序不需要区分不同类型的未定义文件区域。

数据变更操作可能是写操作或者记录追加写操作。写操作把数据写到应用程序定义的文件偏移位置。即使存在并发变更操作，记录追加写操作也能让数据(记录)至少一次原子追加到 GFS 选择的偏移位置处(第 3.3 节)。(相反的是，一个常规追加操作仅仅是把数据写到客户端认为的当前文件最后位置)。写入数据的偏移位置会返给客户端，它也标记了包含该记录的已定义区域的开始位置。另外，GFS 可能在两者之间插入空洞或者重复记录项。这些数据所在的区域就存在不一致，这部分数据只占用户数据的一小部分。

在一系列变更操作都成功之后，变更后的文件区域保证是已定义的，并且包含了由最后一个变更操作写入的数据。GFS 通过两部分实现该保证：

1. 在 GFS 的所有副本上按照相同的数据对块进行变更(3.1 节)
2. 当块服务器宕机后，块服务器因为错过变更操作导致该块服务器上的块失效。GFS 通过块上的版本号识别失效块。

失效的副本之后不会进行变更，也不会经由 master 返回给获取块位置的客户端。它们是会高优回收的垃圾。

客户端缓存块位置信息，因此它们在信息更新前还会读失效的副本数据。该窗口期受到缓存超时时间和下一次打开文件时刻的限制，之后客户端会从缓存中清除该文件的所有块信息。此外，由于我们的大多数文件都是仅追加的，所以过时的副本通常会返回块中靠前的偏移。当客户端重试并联系 master 时，它将立即获取当前块位置信息。

在一个变更操作之后，机器故障仍然会损坏或破坏数据。GFS 通过 master 和所有块服务器之间的定期握手来识别失败的块服务器，并通过校验和检测数据损坏(第 5.2 节)。一旦出现问题，就会尽快从有效副本中恢复数据(第 4.3 节)。仅当在 GFS 做出反应之前(通常在几分钟内)所有副本都丢失时，块数据才会不可逆地丢失。即使在这种情况下，它也会变得不可用，而不是损坏：应用程序收到明确的错误而不是损坏的数据

2.7.2. 对应用程序的影响

GFS 应用程序可以通过一些简单技术来实现该一致性模型：追加写替代覆盖写数据、检查点以及自验证数据写操作、记录数据验证。

实际应用中，我们所有应用都是通过追加而不是覆盖来更新文件。一个典型的应用是，一个写节点从头到尾生成一个文件。当所有数据都写入文件后，它会重命名为一个永久的名字，它也会定期生成校验点标识已经写入的数据。校验点也可能包含应用级别的校验和。读节点只校验并读取到最近的校验点，因为最近的校验点的状态是已定义的。无论一致性还是并发问题，这个方法都非常好用。追加写比随机写的效率更高，也对应用程序故障的恢复能力更强。通过校验点，写节点可以增量重启，并且保证读节点不会处理虽然写成功但是应用程序层面并不完整的数据。

在另一个典型的应用中，许多写节点并发追加一个文件，组成一个生产者-消费者队列。记录追加操作保证的最少追加一次的语义可以保存每个写节点生成的内容。读节点处理偶尔的空洞数据或者重复数据。每条记录在通过写节点生成时都会携带有校验和等额外信息，这样可以校验数据准确性。读节点通过校验和可识别和丢弃空洞或者数据片段。如果它不能容忍偶尔的重复数据(假设它们会触发非幂等操作)，它可以使用记录中的唯一标识符将其过滤掉，而这些标识符通常是用来命名相应的应用程序实体(例如网络文档)的。这些用于处理记录数据IO 操作的函数(除了去重)都在我们应用程序的共享库代码中，并且也可以应用在 Google 的其他文件系统实现上。通过这些函数，相同顺序的记录数据，以及少见的重复数据，都可以传递给读节点。

3. 系统交互

我们设计该系统旨在减少 master 对所有操作的参与。在这样的背景下，现在描述客户端、master 和块服务器如何交互以进行数据更改、原子记录追加操作和快照操作。

3.1. 租约和变更顺序

变更操作指的是改变一个块元数据或内容的操作，例如写操作或者追加操作。每个变更操作都会在所有的块副本中执行。我们使用租约对副本维持一个恒定的变更顺序。master 挑选一个副本作为主副本，并授予块租约。主副本为该块挑选一个串行的变更顺序。所有副本遵循该顺序来变更数据。因此，全局的变更数据是通过 master 的租约授予顺序决定的，在一个租约内则是通过主副本赋予的串行编号决定。

租约机制旨在减少 master 的管理开销。一个租约最初有 60s 的过期时间。然而，只要块数据存在变更，主副本可以无限期向 master 请求并延期租约。这些请求和续期操作是通过 master 和所有块副本的心跳消息实现的。master 有时想在租约过期前重置一个新租约(当 master 想要终止对一个已重命名的文件的变更操作时)。即使 master 无法与主副本通信，它也可以在旧租约过期之后给其他副本授予新租约。

图 2 所示，写操作的控制流共有如下几步。

1. 客户端询问 master 哪个块服务器持有某块数据的租约，并获取其他副本的位置。如果没有副本持有租约，master 选择一个副本并授予租约。
2. master 回复主副本的身份以及其他副本的位置信息。客户端缓存这些数据便于后续变更操作。客户端会持有这些数据，直到主副本无法访问或者主副本声称不再持有租约。
3. 客户端把数据推给所有副本。客户端可以任何顺序推送数据。每个块服务器会把这些数据存到 LRU 缓存，直到数据被使用或过期。通过把数据流和控制流解耦，我们可以基于网络拓扑调度昂贵的数据流，而不用管块服务器是主副本还是其他副本。3.2 节讨论了该场景。
4. 一旦所有副本声称收到数据，客户端会向主副本发一个写请求。请求中带有已发送数据的识别信息。主副本将连续的序列号分配给它接收到的所有变更操作(可能来自多个客户端)，该操作提供了必要的串行顺序。它会将变更按照串行顺序应用在副本的本地状态。
5. 主副本向所有的副本转发写操作。每个二级副本以主副本定义的顺序应用变更。
6. 二级副本全部回复主副本，表明它们完成该操作。
7. 主副本回复客户端。在任何副本上发生的错误都会上报给客户端。如果有错误发生，写操作可能在主副本上或二级副本的任意子集上成功执行。(如果它在主副本上已经失败，它不会进一步设置顺序编号并转发请求)。客户端请求视为失败，该请求变更的区域处于不一致的状态。我们的客户端代码通过重试该操作来处理错误。它会重试步骤3-步骤7，之后才会从头开始重试。

如果应用程序的写操作数据量很大或者跨过块边界，GFS 客户端代码会将它分成多个写操作。它们都遵循上述控制流，但可能与其他客户端的并发操作交织并被覆盖。因此，一个文件最终可能包含不同客户端的数据，但是这些副本都是一致的，因为每个操作都是按照相同顺序在所有副本上执行的。这使得文件区域是一致但是非定义状态，如 2.7 节定义。

3.2. 数据流

我们把数据流从控制流中解耦以高效利用网络。当控制信息从客户端流向主节点，然后流向所有辅助节点时，数据会以管道方式沿着精心挑选的块服务器链线性推送。我们的目标是充分利用每台机器的网络带宽，避免网络瓶颈和高延迟链路，并最大限度地减少推送所有数据的延迟。

为了充分利用每个机器的网络带宽，数据沿着块服务器链线性推送，而不是分布在其他拓扑(例如树)中。因此，每台机器的全部出站带宽都用于尽可能快地传输数据，而不是分配给多个接收者。

为了避免出现网络瓶颈和高延迟链路(交换机链路通常都有两种问题)，每台机器向网络拓扑中最近未收到数据的机器推送数据。假设客户端推送数据给块服务器 S1-S4。S1 把数据转发给 S2-S4 中距离 S1 最近的设备，假设是 S2。相同的，S2 转发数据给 S3 或者 S4，选择其中距离 S2 最近的机器。我们的网络拓扑很简单，距离可以通过 IP 地址来衡量。

最后，我们通过管道化 TCP 链接上的数据传输来降低时延。一旦一个块服务器收到数据，它立即开始转发。管道化对于我们特别有用，因为我们使用的是全双工交换网络。立即发送数据并不会降低接收速率。不考虑网络拥塞，把 B 字节数据发送给 R 个副本的理想耗时是 B/T + RL，其中 T 是网络吞吐量，L 是两台机器的传输延迟。我们的网络链路是通用的 100Mbps(T)，L 远小于 1ms。因此，1MB 理想传输时间是 80ms。

3.3. 原子性的记录追加操作

GFS 提供一个原子性的追加操作，称为记录追加操作(record append)。常规写操作中，客户端指定数据要写入的偏移位置。对同一区域的并发写入不是串行化的：该区域最终可能包含来自多个客户端的数据片段。然而，在记录追加操作中，客户端仅指定数据，不需要指定偏移位置。GFS 原子性把数据至少一次追加到文件中 GFS 指定的偏移位置(作为一个连续字节流)，并把该偏移返回给客户端。这类似于在 Unix 中写入以 O_APPEND 模式打开的文件，并且多个写入操作同时出现时不会出现竞争条件。

记录追加操作在我们的分布式应用程广泛使用，不同机器上的多个客户端并发追加写到同一文件。如果是常规写操作，客户端需要复杂且昂贵的同步流程，例如通过一个分布式锁。在我们的工作场景中，这种文件常作为多生产者-单消费者队列或者保存不同客户端的合并结果。

记录追加是一种变更操作且遵循 3.1 节中的控制流，但在主副本上有一点额外逻辑。客户端将数据推送到文件最后一个块的所有副本，然后将请求发送到主副本。主副本检查将记录附加到当前块是否会导致块超过最大大小(64 MB)。如果会超过，它将块填充到最大大小，告诉二级副本执行相同的操作，并向客户端回复，指示应在下一个块上重试该操作。(记录追加最多限制为最大块大小的四分之一，以将最坏情况下的碎片保持在可接受的水平。)如果记录符合尺寸要求(这是常见的情况)，则主副本会将数据追加到它的副本中，告诉二级副本将数据写入其所在的确切偏移量，并最终向客户端回复成功。

如果一个记录追加在任何一个副本上执行失败了，客户端重试该操作。最后，相同块的副本可能包含不同的数据，因为可能有部分或全部数据存在重复。GFS 不保证所有副本是字节范围一致。它只保证数据至少原子性写入一次。这个属性很容易从简单的观察中得出，为了使操作成功，数据必须以相同的偏移量写入某个块的所有副本上。在此之后，所有副本至少与记录末尾一样长，因此任何未来的记录都将被分配更高的偏移量或不同的块，即使不同的副本后来成为主副本。就我们的一致性保证而言，记录追加操作成功写入数据的区域是已定义的(因此是一致的)，而中间区域是不一致的(因此是未定义的)。正如我们在第 2.7.2 节中讨论的那样，我们的应用程序可以处理不一致的区域。

3.4. 快照

快照操作几乎立即创建文件或目录树(“源”)的副本，同时最大限度地降低正在进行的变更操作导致的中断时间。我们的用户使用它来快速创建大型数据集的分支副本(通常是这些副本的递归副本)，或者在提交或回滚更改之前存盘当前状态。

和 AFS 类似，我们使用经典的写时复制技术来实现快照功能。当 master 收到快照请求，它首先撤销需要快照的块上的未完成租约。这保证任何后续写入该块时都需要与 master 进行交互以获取持有租约的副本。这使得 master 有机会先创建一个块的新副本。

在租约被撤销或失效后，master 把该操作记录到磁盘上。然后，它通过复制源文件或目录树的元数据来将此日志记录应用于其内存中状态。新创建的快照文件指向与源文件相同的块。

快照操作之后，客户端第一次想要写入块 C 时，它向 master 发请求获取当前租约持有者。master 注意到块 C 的引用数量超过 1。它推迟回复客户端请求，而是选择一个新块句柄 C’。然后，它要求每个拥有 C 副本的块服务器创建一个名为 C’ 的新块。通过在与原始块相同的块服务器上创建新块，我们确保可以在本地复制数据，而不是通过网络复制(我们的磁盘速度大约是 100 Mb 以太网链路的三倍)。从这一点来看，请求处理与任何块的处理没有什么不同：主节点授予其中一个副本对新块 C’ 的租约，并回复客户端，客户端可以正常写入该块，而不知道它是刚刚创建出来的。

4. master 的操作

master 执行所有名称空间的操作。而且，它通过该系统管理块副本：它决策块数据放置，创建新块和副本，协调系统维度的活动以保证块充分被复制，平衡所有块服务器之间的负载，并回收未使用的存储。我们现在依次讨论这些主题。

4.1. 名称空间管理和锁机制

许多 master 操作会花很长时间：例如，快照操作需要撤销快照涉及的所有块服务器的租约。我们不希望执行这些操作的时候阻塞其他操作。因此，我们允许操作并发执行，并且使用名称空间范围的锁保证正确的串行化。

与传统文件系统不同，GFS 没有定义可列出目录下所有文件的目录数据结构。它也不支持为文件或目录起别名(Unix 术语中的硬链接或符号链接)。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/user/foo 文件时会获取 /home 和 /home/user 上的读锁以及 /home/user/foo 上的写锁。这两个操作会被串行执行，因为它们都要获取 /home/user 上的锁。文件创建不需要父目录上的写锁，因为没有“目录”或类似 inode 的数据结构可以防止修改。读锁足以保护父目录不被删除

这种锁机制的一个优点是它允许在同一个目录上并发变更操作。例如，多个文件创建操作可以同时在同一个目录下执行：每个操作获取目录上的读锁和文件上的写锁。目录名上的读锁足够阻止目录被删除、重命名或快照。文件名上的写锁会串行化想要多次创建同名文件的操作。

鉴于名称空间会有很多节点，读写锁对象是惰性分配并且在不使用时立即删除。而且，锁是按照一个固定的顺序获取以阻止死锁：它们首先按名称空间树中的级别排序，并在同一级别内按字典顺序排序。

4.2. 副本放置决策

GFS 集群在不同层级上都是高度分布。它通常有数百个块服务器分布在许多机器机架上。这些块服务器又可以被来自相同或不同机架的数百个客户端访问。不同机架上的两台机器之间的通信可能会跨越一个或多个网络交换机。此外，进出机架的带宽可能小于机架内所有机器的总带宽。多级分布对分布数据的可扩展性、可靠性和可用性提出了独特的挑战。

块副本放置策略有两个目的：最大化数据可靠性和可用性，以及最大化网络带宽利用率。对于这两个目的，跨机器分布副本是不够的，这只能防止磁盘或机器故障并充分利用每台机器的网络带宽。我们还必须将块副本分布在不同机架上。这确保了即使整个机架损坏或离线(例如，由于网络交换机或电源电路等共享资源发生故障)，块的某些副本也将存活并保持可用。这也意味着块的流量(尤其是读取)可以利用多个机架的总带宽。另一方面，写流量必须流经多个机架，这是我们自愿做出的权衡。

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

块副本会因为三种原因创建：创建块、重新复制和重新平衡。

当 master 创建一个块，它决定把最初的空副本放在何处。它考虑几个因素。(1)我们希望将新副本放置在磁盘空间利用率低于平均水平的块服务器上。随着时间的推移，这将平衡块服务器之间的磁盘利用率。(2) 我们希望限制每个块服务器上“最近”创建的数量。尽管创建操作很廉价，但它可以可靠地预测即将到来的繁重写入流量，因为写入需要时会创建块，并且在我们的追加一次多次读取的工作负载中，它们被完全写入之后基本就是只读数据。(3) 如前面章节所述，我们希望将块的副本均匀分布在机架上。

一旦可用副本的数量低于用户指定的目标数量，master 就会重新复制块。发生这种情况的原因有多种：块服务器变得不可用，它报告其副本可能已损坏，其磁盘之一因错误而被禁用，或者复制目标增加。每个需要重新复制的块都会根据几个因素确定优先级。一是距离复制目标数量差多少。例如，我们对丢失两个副本的块给予比仅丢失一个副本的块更高的优先级。此外，我们更喜欢首先重新复制活动文件的块，而不是属于最近删除的文件的块(参见第 4.4 节)。最后，为了最大限度地减少故障对正在运行的应用程序的影响，我们提高了阻止客户端进度的块优先级。

master 选择最高优先级的块，并通过指示某些块服务器直接从现有的有效副本复制块数据来“克隆”它。新副本的放置目标与创建目标类似：均衡磁盘空间利用率、限制任何单个块服务器上的克隆操作以及跨机架分布副本。为了防止克隆流量压倒客户端流量，master 限制集群和每个块服务器的活动克隆操作数量。此外，每个块服务器通过限制其对源块服务器的读取请求来限制其在每个克隆操作上花费的带宽量。

最后，master 定期重新平衡副本：它检查当前副本分布并移动副本以获得更好的磁盘空间和负载平衡。同样通过这个过程，master 逐渐填满新的块服务器，而不是立即用新块和随之而来的大量写入流量淹没它。新副本的放置标准与上面讨论的类似。此外，master 还必须选择要删除哪个现有副本。一般来说，它更愿意删除可用空间低于平均水平的块服务器上的那些副本，以均衡磁盘空间使用。

4.4. 垃圾回收

文件删除后，GFS 不会立即回收可用的物理存储。它仅在文件和块级别的常规垃圾收集期间延迟执行此操作。我们发现这种方法使系统变得更简单、更可靠。

4.4.1. 回收机制

当应用程序删除文件时，master 会像其他更改一样记录删除操作。然而，文件并没有立即回收资源，而是被重命名为包含删除时间戳的隐藏名称。在 master 定期扫描文件系统名称空间期间，如果此类隐藏文件存在超过三天(时间间隔可配置)，它将删除它们。在此之前，该文件仍然可以用新的特殊名称读取，并且可以通过将其重命名回正常名称来取消删除状态。当隐藏文件从名称空间中删除时，其内存中的元数据将被删除。这有效地切断了它与所有块的链接。

在对块名称空间进行类似的定期扫描时，master 会识别孤立块(即无法从任何文件访问的块)并删除这些块的元数据。在与 master 定期交换的心跳消息中，每个块服务器报告其拥有的块的集合，并且 master 回复不再存在于 master 元数据中的块标识。块服务器可以自由删除此类块的副本。

4.4.2. 讨论

尽管分布式垃圾收集是一个难题，需要在编程语言的上下文中提供复杂的解决方案，但在我们的例子中它非常简单。我们可以轻松识别对块的所有引用：它们位于由主服务器专门维护的文件到块的映射中。我们还可以轻松识别所有块副本：它们是每个块服务器上指定目录下的 Linux 文件。任何不为 master 所知的副本都是“垃圾”。

与立即删除相比，垃圾回收方法具有许多优点。首先，在组件故障频繁发生的大规模分布式系统中，它简单可靠。块创建可能在某些块服务器上成功，但在其他服务器上则不然，从而留下主服务器不知道存在的副本。副本删除消息可能会丢失，master 必须记住在发生故障时重新发送它们，无论是它自己的还是块服务器的。垃圾收集提供了一种统一且可靠的方法来清理任何无用副本。其次，它将垃圾回收放置到主服务器的常规后台活动中，例如名称空间的定期扫描以及与块服务器的握手。因此，它是分批完成的，成本是摊销的。而且，只有在 master 比较空闲的时候才会这么做。master 可以更迅速地响应需要及时关注的客户请求。第三，垃圾回收的延迟提供了防止意外删除、不可逆转删除的安全缓冲。

根据我们的经验，垃圾回收的主要缺点是，当存储紧张时，延迟回收有时会妨碍用户微调使用情况。重复创建和删除临时文件的应用程序可能无法立即重用存储。如果已删除的文件再次显式删除，我们将通过加快存储回收来解决这些问题。我们还允许用户将不同的复制和回收策略应用于名称空间的不同部分。例如，用户可以指定某个目录树中的文件中的所有块都不带副本存储，并且任何已删除的文件将立即且不可撤销地从文件系统中删除。

4.5. 失效副本检测

如果块服务器发生故障并在宕机时错过块的变更操作，则块副本可能失效。对于每个块，master 维护一个块版本号以区分最新副本和过时副本。

每当 master 授予一个块的新租约时，它就会增加该块的版本号并通知最新的副本。master 和块副本都在其持久化状态中记录新版本号。这发生在任何客户端收到通知之前，因此也在它可以开始写入块之前。如果另一个副本当前不可用，则其块版本号将不会更新。当块服务器重新启动时，master 将检测到该块服务器有一个失效副本，并报告其块集合及关联的版本号。如果 master 看到一个比记录中的版本号更高的版本，则 master 认为是授予租约时失败导致，因此将该较高版本设为最新版本。

master 在其定期垃圾收集中删除失效副本。在此之前，当它回复客户端对块信息的请求时，它实际上认为失效副本根本不存在。作为另一个保护措施，当 master 通知客户端哪个块服务器持有某个块的租约时，或者当它指示一个块服务器在克隆操作中从另一个块服务器读取该块时，master 会包含该块版本号。客户端或块服务器在执行操作时验证版本号，以便始终访问最新数据。

5. 容错和错误诊断

我们设计该系统的最大挑战之一就是处理频繁的组件故障。组件的数量和质量加在一起使这些问题更加常见：我们不能完全信任机器，也不能完全信任磁盘。组件故障可能会导致系统不可用，或者更糟糕的是，导致数据损坏。我们讨论如何应对这些挑战，以及我们在系统中内置的工具，用于在问题不可避免地发生时进行诊断。

5.1. 高可用

在 GFS 集群中的数百台服务器中，有些服务器在任何时间都可能不可用。我们通过两种简单而有效的策略保持整个系统的高可用性：快速恢复和复制。

5.1.1. 快速恢复

master 和块服务器都被设计支持无论如何终止机器，都可以恢复状态恢复和几秒内启动。事实上，我们不区分正常终止和异常终止；服务器通常只是通过终止进程来关闭。客户端和其他服务器在未完成的请求超时、重新连接到重新启动的服务器并重试时会遇到轻微的问题。第 6.2.2 节报告了观察到的启动时间。

5.1.2. 块复制

如前所述，每个块都被复制到不同机架上的多个块服务器上。用户可以为文件名称空间的不同部分指定不同的复制级别。默认值为三个。master 根据需要克隆现有副本，以在块服务器离线时保持每个块的完全复制，或者通过校验和验证检测损坏的副本(参见第 5.2 节)。尽管复制副本对我们很有帮助，我们正在探索其他形式的跨服务器冗余，例如奇偶校验或纠删码，以满足我们不断增长的只读存储需求。我们预计，在我们非常松散耦合的系统中实现这些更复杂的冗余方案是具有挑战性的，但也是可以管理的，因为我们的流量主要是追加写入和读取，而不是小型随机写入。

5.1.3. master 复制

master 状态使用副本保证可靠性。其操作日志和检查点被复制到多台机器上。仅当其日志记录已刷新到本地磁盘和所有 master 副本上后，状态的变更操作才被视为已提交。为简单起见，一个 master 进程负责所有变更操作以及后台活动，例如垃圾回收。当它失败时，它几乎可以立即重新启动。如果其机器或磁盘发生故障，GFS 外部的监控基础设施会在其他地方启动一个新的 master 进程，并复制操作日志。客户端仅使用 master 的规范名称(例如 gfs-test)，这是一个 DNS 别名，如果 master 重新定位到另一台机器，则可以更改该别名。

此外，即使主 master 宕机，“影子” master 也可以提供对文件系统的只读访问。它们是影子，而不是镜子，因为它们可能会稍微滞后于主 master ，通常是几分之一秒。它们提高了对未变更文件或不介意获得稍微落后结果的应用程序的读取可用性。事实上，由于文件内容是从块服务器读取的，应用程序不会观察到陈旧的文件内容。在短窗口期内会过时的是文件元数据，例如目录内容或访问控制信息。

为了保持同步，影子 master 会读取不断增长的操作日志的副本，并按照与主 master 完全相同的将更改应用于其数据结构。与主 master 一样，它在启动时轮询块服务器(此后很少轮询)以定位块副本并与它们频繁握手以监视它们的状态。它仅依赖于主 master 来更新由主 master 决策导致的副本位置更新。

5.2. 数据完整性

每个块服务器使用校验和来检测存储数据的损坏。鉴于 GFS 集群通常在数百台计算机上拥有数千个磁盘，因此它经常会遇到磁盘故障，从而导致读取和写入路径上的数据损坏或丢失。(请参阅第 7 节了解其中一个原因。) 我们可以使用其他块副本以恢复损坏的数据，但通过比较块服务器之间的副本来检测损坏是不切实际的。此外，不同的副本可能是合法的：GFS 变更的语义，特别是前面讨论的原子记录追加操作，不能保证相同的副本。因此，每个块服务器必须通过维护校验和来独立验证其自身副本的完整性。

一个块被分成 64 KB 的小块。每个都有一个相应的 32 位校验和。与其他元数据一样，校验和保存在内存中并通过日志记录永久存储，与用户数据分开。

对于读取操作，块服务器在将任何数据返回给请求者(无论是客户端还是另一个块服务器)之前验证与读取范围重叠的数据块的校验和。因此，块服务器不会将损坏数据传播到其他机器。如果某个块与记录的校验和不匹配，则块服务器会向请求者返回错误并向 master 报告不匹配情况。作为响应，请求者将从其他副本读取数据，而 master 将从另一个副本克隆该块。有效的新副本就位后，主服务器指示报告不匹配的块服务器删除其副本。

校验和对读取性能影响很小。由于我们的大多数读取至少跨越几个块，因此我们只需要读取相对少量的额外数据并进行校验和以进行验证。GFS 客户端代码通过尝试在校验和块边界对齐读取来进一步减少此开销。此外，块服务器上的校验和的查找和比较是在没有任何 I/O 的情况下完成的，并且校验和的计算可与 I/O 同步执行。

校验和的计算针对追加写入(而不是覆写现有数据的写入)进行了大量优化，因为它们在我们的工作负载中占主导地位。我们只是增量更新最后一个部分校验和块的校验和，并为追加操作填充的任何全新校验和块计算新的校验和。即使最后一个部分校验和块已经损坏并且我们现在无法检测到它，新的校验和值也将与存储的数据不匹配，并且下次读取该块时将照常检测到损坏。

相反，如果写入的数据覆盖了现有块数据，我们必须读取并验证被覆盖范围的第一个和最后一个块，然后执行写入，并且最后计算并记录新的校验和。如果我们在覆写数据前不验证第一个和最后一个块，则新的校验和可能会隐藏未覆写区域中存在的损坏。

在空闲期间，块服务器可以扫描并验证不活动块的内容。这使我们能够检测很少读取的块中的损坏。一旦检测到损坏，master 可以创建新的未损坏副本并删除损坏的副本。这可以防止不活动但已损坏的块副本欺骗 master ，使其认为它具有足够的有效块副本。

5.3. 诊断工具

广泛而详细的诊断日志记录对问题隔离、调试和性能分析有不可估量的帮助，同时只花费最小的成本。如果没有日志，就很难理解机器之间短暂的、不可重复的交互。GFS 服务器生成诊断日志，记录许多重要事件(例如块服务器的启动和关闭)以及所有 RPC 请求和回复。这些诊断日志可以自由删除，不会影响系统的正确性。但是，我们会尽力在空间允许的情况下保留这些日志。

RPC 日志包括在线路上发送的确切请求和响应，但不会记录正在读取或写入的文件数据。通过将请求与回复进行匹配并整理不同机器上的 RPC 记录，我们可以重建整个交互历史来诊断问题。这些日志还可以作为负载测试和性能分析的跟踪。

日志记录对性能的影响很小(并且远远超过其好处)，因为这些日志是按顺序异步写入的。最近的事件也保存在内存中并可用于连续在线监控。

6. 性能测试

不再翻译

7. 经验

在构建和部署GFS的过程中，我们遇到了各种各样的问题，有些是操作性的，有些是技术性的。

最初，GFS 被设想为我们生产系统的后端文件系统。随着时间的推移，用途逐渐演变为包括研究和开发任务。它一开始对权限和配额等内容的支持很少，但现在包含了对这些内容的基本支持。虽然生产系统受到良好的纪律和控制，但用户有时却不受控制。需要更多的基础设施来防止用户相互干扰。

我们最大的一些问题与磁盘和 Linux 相关。我们的许多磁盘都向 Linux 驱动程序声称它们支持一系列 IDE 协议版本，但实际上仅对较新的版本做出可靠响应。由于协议版本非常相似，这些驱动器大部分都可以工作，但偶尔不匹配会导致驱动器和内核对驱动器状态认知不一致。由于内核中的这些问题，导致会默默地损坏数据。这个问题促使我们使用校验和来检测数据损坏，同时我们修改内核以处理这些协议不匹配。

早些时候，由于 fsync() 的开销，我们在 Linux 2.2 内核中遇到了一些问题。其开销与文件的大小成正比，而不是与修改部分的大小成正比。这对于我们的大型操作日志来说是一个问题，尤其是在我们设置检查点之前。我们短期通过使用同步写入来解决这个问题，并最终迁移到 Linux 2.4。

Linux 的另一个问题是单个读写锁，地址空间中的任何线程在从磁盘调入(读取锁)或在 mmap() 调用中修改地址空间(写入锁)时都必须持有该锁。我们发现系统在轻负载下出现短暂超时，并努力查找资源瓶颈或偶发硬件故障。最终，我们发现这个单一的锁阻止了主网络线程将新数据映射到内存，而此时磁盘线程正在对先前映射的数据进行分页。由于我们主要受到网络接口而不是内存复制带宽的限制，因此我们通过用 pread() 替换 mmap() 来解决这个问题，但代价是额外的复制。

尽管偶尔会出现问题，Linux 代码的可用性一次又一次地帮助我们探索和理解系统行为。在适当的时候，我们会改进内核并与开源社区分享更改。

8. 相关工作

不再翻译

9. 结论

GFS 展示了支持商用硬件上的大规模数据处理工作负载所必需的特征。虽然一些设计决策是针对我们独特的环境的，但许多设计决策可能适用于具有类似规模和成本意识的数据处理任务。

我们首先根据当前和预期的应用程序工作负载和技术环境重新审视传统文件系统。我们的观察引申出截然不同的设计观点。我们将组件故障视为常态而不是偶尔发生，针对主要追加写(可能同时)然后读取(通常顺序)的大文件进行优化，并扩展和放宽文件系统接口的标准以改进整个系统 。

我们的系统通过持续监控、复制关键数据以及快速自动恢复来提供容错能力。块复制使我们能够容忍块服务器宕机。这些故障的频繁发生催生了一种新颖的在线修复机制，该机制可以定期、透明地修复损坏并尽快补偿丢失的副本。此外，我们使用校验和来检测磁盘或 IDE 子系统级别的数据损坏，考虑到系统中的磁盘数量，这种情况变得非常常见。

我们的设计为执行各种任务的许多并发读节点和写节点提供了高聚合吞吐能力。我们通过将通过 master 的文件系统控制与直接在块服务器和客户端之间传递的数据传输分开来实现该能力。通过较大的块大小和块租约，可以最大限度地减少主节点对常见操作的参与，这将数据变更中的权限委托给主副本。这使得 master 更简单、集中，且不会成为瓶颈。我们相信，网络栈的改进将解除当前对单个客户端的写入吞吐量的限制。

GFS成功满足了我们的存储需求，并在 Google 内部广泛用作研发和生产数据处理的存储平台。它是一个重要的工具，使我们能够在整个网络范围内不断创新和解决问题。