The Google File System

谷歌文件系统

Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung
Google $^(^∗)$

摘要

我们设计并实现了谷歌文件系统（Google File System, GFS）——这是一个面向大规模分布式数据密集型应用的可扩展分布式文件系统。它能够在廉价的商用硬件上运行，同时提供容错能力，并向大量客户端提供高聚合性能。

尽管与此前的分布式文件系统有着诸多相同目标，但我们的设计源于对应用负载和技术环境的观察（包括当前现状与未来预期），这些观察反映出我们与一些早期文件系统假设存在显著分歧。这促使我们重新审视传统选择，并探索截然不同的设计切入点。

该文件系统已成功满足了我们的存储需求。它作为存储平台在谷歌内部被广泛部署，用于生成和处理各项服务所使用的数据，以及需要大规模数据集的研发工作。截至目前，最大的集群在超过一千台机器的数千块磁盘上提供了数百TB的存储容量，并被数百个客户端并发访问。

在本文中，我们介绍了为支持分布式应用而设计的文件系统接口扩展，讨论了设计中的诸多方面，并给出了微观基准测试与实际应用场景下的性能测量结果。

分类与主题描述
D [4]: 3-分布式文件系统

通用术语
设计、可靠性、性能、测量

关键词
容错、可扩展性、数据存储、集群存储

*作者联系方式：{sanjay, hgobioff, shuntak}@google.com

未经许可，不得以营利或商业优势为目的制作或分发本文的数字或纸质副本；副本需标注本声明及首页完整引用信息。如需其他形式的复制、再发布、在服务器上发布或向列表重新分发，需要事先获得特定许可和/或支付费用。

1. 引言

我们设计并实现了谷歌文件系统（GFS），以满足谷歌数据处理需求的快速增长。GFS与此前的分布式文件系统有着许多相同目标，例如性能、可扩展性、可靠性和可用性。然而，其设计的驱动力源于对我们应用负载和技术环境的关键观察（包括当前现状与未来预期），这些观察反映出与一些早期文件系统设计假设的显著差异。我们重新审视了传统选择，并在设计空间中探索了截然不同的切入点。

首先，组件失效是常态而非异常。文件系统由数百甚至数千台存储机构成，这些机器均由廉价的商用部件组装而成，并且被数量相当的客户端机器访问。从部件的数量和质量来看，几乎可以保证其中一些在任何给定时间都无法正常工作，还有一些将无法从当前故障中恢复。我们见过由应用程序bug、操作系统bug、人为错误，以及磁盘、内存、连接器、网络和电源故障导致的各种问题。因此，持续监控、错误检测、容错和自动恢复必须成为系统不可或缺的组成部分。

其次，文件规模远超传统标准。数GB的文件十分常见。每个文件通常包含大量应用对象，例如网页文档。当我们常规处理数十亿个对象、数TB级的快速增长数据集时，即使文件系统能够支持，管理数十亿个KB级大小的文件也难以操作。因此，I/O操作和块大小等设计假设与参数都需要重新考量。

第三，绝大多数文件的修改方式是追加新数据，而非覆盖已有数据。文件内的随机写入在实际中几乎不存在。文件一旦写入，就只会被读取，而且通常是顺序读取。各类数据都具有这些特征：有些是数据处理程序扫描的大型存储库；有些是运行中的应用持续生成的数据流；有些是归档数据；还有些是在一台机器上生成、在另一台机器上处理的中间结果（可以是同时处理，也可以是后续处理）。鉴于大文件的这种访问模式，追加操作成为性能优化和原子性保证的重点，而在客户端缓存数据块则失去了吸引力。

第四，应用程序与文件系统API的协同设计通过提升灵活性让整个系统受益。例如，我们放宽了GFS的一致性模型，极大地简化了文件系统，同时不会给应用程序带来沉重负担。我们还引入了原子追加操作，使得多个客户端可以并发地向同一个文件追加数据，而无需在它们之间进行额外同步。这些将在本文后续部分详细讨论。

目前已有多个GFS集群部署用于不同用途。最大的集群拥有超过1000个存储节点、超过300TB的磁盘存储，并被数百台不同机器上的客户端持续密集访问。

2. 设计概述

2.1 设计假设

在设计满足我们需求的文件系统时，我们以一系列假设为指导，这些假设既带来挑战，也带来机遇。我们在前文已经提及一些关键观察，现在将更详细地阐述这些假设。

系统由大量廉价商用组件构建，这些组件经常发生故障。系统必须持续监控自身，并例行地、及时地检测、容忍和从组件故障中恢复。
系统存储数量适中的大文件。我们预期有数百万个文件，每个文件通常为100MB或更大。数GB的文件是常见情况，应当被高效管理。小文件必须得到支持，但无需针对它们进行优化。
工作负载主要由两种读取组成：大规模流式读取和小规模随机读取。在大规模流式读取中，单次操作通常读取数百KB，更常见的是1MB或更多。来自同一客户端的连续操作通常读取文件的连续区域。小规模随机读取通常在任意偏移处读取几KB。注重性能的应用通常会将小规模读取进行批量和排序，以在文件中稳步推进，而非来回跳转。
工作负载中也有大量向文件追加数据的大规模顺序写入。典型的操作大小与读取类似。文件一旦写入，就很少再被修改。文件中任意位置的小规模写入是被支持的，但无需保证高效。
系统必须为并发向同一文件追加的多个客户端高效实现定义明确的语义。我们的文件常被用作生产者-消费者队列或多路归并。数百个生产者（每台机器运行一个）会并发地向一个文件追加数据。具有最小同步开销的原子性至关重要。文件可能在之后被读取，或者消费者可能同时读取文件。
高持续带宽比低延迟更重要。我们的大多数目标应用都优先考虑以高速率批量处理数据，而很少有应用对单次读取或写入有严格的响应时间要求。

2.2 接口

GFS提供了熟悉的文件系统接口，尽管它并未实现POSIX之类的标准API。文件以层次化目录结构组织，并通过路径名标识。我们支持创建、删除、打开、关闭、读取和写入文件等常规操作。

此外，GFS还拥有快照（snapshot）和记录追加（record append）操作。快照以低成本创建文件或目录树的副本。记录追加允许多个客户端并发地向同一文件追加数据，同时保证每个客户端追加操作的原子性。它可用于实现多路归并结果和生产者-消费者队列，多个客户端可以同时向其中追加数据而无需额外加锁。我们发现这些类型的文件在构建大型分布式应用时极具价值。快照和记录追加将分别在第3.4节和第3.3节进一步讨论。

2.3 架构

一个GFS集群由一个主服务器（master）和多个块服务器（chunkserver）组成，并被多个客户端访问，如图1所示。其中每个角色通常都是运行用户级服务器进程的商用Linux机器。只要机器资源允许，并且运行可能不稳定的应用代码所导致的可靠性下降是可接受的，在同一台机器上同时运行块服务器和客户端是很容易实现的。

文件被划分为固定大小的块（chunk）。每个块在创建时由主服务器分配一个不变且全局唯一的64位块句柄（chunk handle）来标识。块服务器将块以Linux文件的形式存储在本地磁盘上，并根据块句柄和字节范围来读写块数据。为了可靠性，每个块在多个块服务器上进行复制。默认情况下，我们存储三个副本，不过用户可以为文件命名空间的不同区域指定不同的复制级别。

主服务器维护所有文件系统元数据。这包括命名空间、访问控制信息、文件到块的映射，以及块的当前位置。它还控制系统范围的活动，例如块租约管理、孤立块的垃圾回收，以及块服务器之间的块迁移。主服务器定期通过心跳消息与每个块服务器通信，向其下达指令并收集其状态。

链接到每个应用程序中的GFS客户端代码实现了文件系统API，并代表应用程序与主服务器和块服务器通信以读写数据。客户端与主服务器交互以进行元数据操作，但所有承载数据的通信都直接发往块服务器。我们不提供POSIX API，因此无需接入Linux的vnode层。

客户端和块服务器都不缓存文件数据。客户端缓存几乎没有益处，因为大多数应用要么流式读取超大文件，要么工作集太大而无法缓存。不做缓存简化了客户端和整个系统，因为消除了缓存一致性问题。（不过客户端确实会缓存元数据。）块服务器无需缓存文件数据，因为块以本地文件形式存储，Linux的缓冲区缓存已经将频繁访问的数据保存在内存中。

2.4 单主服务器

采用单主服务器极大地简化了我们的设计，并且使主服务器能够利用全局信息做出复杂的块放置和复制决策。然而，我们必须尽量减少主服务器在读写操作中的参与，以避免它成为瓶颈。客户端永远不通过主服务器读写文件数据。相反，客户端向主服务器询问它应该联系哪些块服务器。它将该信息缓存一段时间，并在后续多次操作中直接与块服务器交互。

让我们结合图1说明一次简单读取的交互过程。首先，利用固定的块大小，客户端将应用程序指定的文件名和字节偏移转换为文件内的块索引。然后，它向主服务器发送包含文件名和块索引的请求。主服务器回复相应的块句柄和副本位置。客户端以文件名和块索引为键缓存该信息。

随后，客户端向其中一个副本（最可能是最近的那个）发送请求。请求指定了块句柄和块内的字节范围。对同一块的后续读取无需再与主服务器交互，直到缓存信息过期或文件被重新打开。事实上，客户端通常在同一次请求中请求多个块，而主服务器也可以包含紧随请求块之后的那些块的信息。这些额外信息几乎无需额外成本，就避开了后续多次客户端-主服务器交互。

图1：GFS架构

2.5 块大小

块大小是关键设计参数之一。我们选择了64MB，这比典型的文件系统块大小要大得多。每个块副本以普通Linux文件的形式存储在块服务器上，并且仅在需要时才进行扩展。惰性空间分配避免了内部碎片造成的空间浪费——这或许是反对使用如此大块大小的最主要理由。

大块大小具有几个重要优势：

减少了客户端与主服务器交互的需求，因为同一块上的读写只需向主服务器请求一次块位置信息。对于我们的工作负载而言，这种减少尤为显著，因为应用大多顺序读写大文件。即使对于小规模随机读取，客户端也可以轻松缓存数TB工作集的所有块位置信息。
由于在大块上，客户端更可能对给定块执行多次操作，因此可以通过在较长时间内保持与块服务器的持久TCP连接来减少网络开销。
减少了主服务器上存储的元数据大小。这使我们能够将元数据保存在内存中，进而带来其他优势，我们将在第2.6.1节讨论。

另一方面，即使采用惰性空间分配，大块大小也有其缺点。小文件由少量块组成，可能只有一个。如果许多客户端访问同一个文件，存储这些块的块服务器可能会成为热点。在实践中，热点并不是主要问题，因为我们的应用大多顺序读取多块的大文件。

然而，当GFS最初被批处理队列系统使用时，热点确实出现了：一个可执行文件作为单块文件写入GFS，然后同时在数百台机器上启动。存储该可执行文件的少数块服务器因数百个并发请求而过载。我们通过提高此类可执行文件的复制因子，并让批处理队列系统错开应用启动时间，解决了这个问题。一个潜在的长期解决方案是允许客户端在这种情况下从其他客户端读取数据。

2.6 元数据

主服务器存储三类主要元数据：文件和块命名空间、文件到块的映射，以及每个块副本的位置。所有元数据都保存在主服务器的内存中。前两类（命名空间和文件到块的映射）还通过将变更记录到操作日志中进行持久化存储，该日志存储在主服务器本地磁盘并复制到远程机器。使用日志使我们能够简单、可靠地更新主服务器状态，并且在主服务器崩溃时不会有不一致的风险。主服务器不持久化存储块位置信息。相反，它在主服务器启动时以及块服务器加入集群时，向每个块服务器询问其块的情况。

2.6.1 内存数据结构

由于元数据存储在内存中，主服务器操作速度很快。此外，主服务器可以轻松高效地在后台定期扫描其全部状态。这种定期扫描用于实现块垃圾回收、块服务器故障时的重新复制，以及为负载均衡和磁盘空间均衡而进行的块迁移。

元数据全部存储在内存中也有潜在的缺点，即整个系统的容量（以及每个块服务器的块数量）受限于主服务器的内存大小。这在实践中并不是严重的限制。对于64MB的块，64MB的元数据可以支持数PB的数据。即使块大小更小，数百万个文件的元数据也只占用主服务器少量内存。因此，内存限制不会成为我们工作负载下的瓶颈，而为了获得内存元数据带来的简洁性、性能和灵活性，付出这个代价是值得的。

2.6.2 块位置

主服务器不持久化记录块副本的位置。它在启动时简单地从块服务器获取这些信息。之后，由于主服务器控制所有块的放置并通过定期心跳消息监控块服务器状态，因此它始终掌握最新信息。

这种设计避免了在块服务器加入、离开、重命名或故障时，主服务器与块服务器之间同步块位置信息的复杂问题。在一个拥有数百台块服务器的集群中，这些事件会持续发生。

换个角度看，块服务器是其自身块列表的最终权威。没有必要让主服务器维护块位置的一致视图，因为块服务器上的块集合可能随时因本地操作而改变。

2.6.3 操作日志

操作日志包含关键元数据变更的历史记录。它是GFS的核心。它不仅是元数据的唯一持久化记录，还作为定义并发操作顺序的逻辑时间线。文件和块，以及它们的版本（见第4.5节），都通过它们被创建时的逻辑时间唯一且永久地标识。

由于操作日志至关重要，我们必须可靠地存储它，并且在元数据变更持久化之前，不能让客户端看到变更。否则，即使块本身得以保留，我们实际上也会丢失整个文件系统或最近的客户端操作。因此，我们将其复制到多台远程机器上，并且只有在将相应的日志记录刷新到本地和远程磁盘之后，才响应客户端操作。主服务器在刷新前会将多条日志记录批量处理，从而减少刷新和复制对整体系统吞吐量的影响。

主服务器通过重放操作日志来恢复其文件系统状态。为了最小化启动时间，我们必须保持日志较小。当日志增长超过一定大小时，主服务器会对其状态设置检查点，这样它就可以通过从本地磁盘加载最新检查点，然后仅重放检查点之后的有限数量的日志记录来进行恢复。检查点采用紧凑的B树形式，可以直接映射到内存中，无需额外解析即可用于命名空间查找。这进一步加快了恢复速度并提高了可用性。

由于构建检查点可能需要一段时间，主服务器的内部状态采用了这样的结构：创建新检查点时不会延迟传入的变更操作。主服务器切换到新的日志文件，并在单独的线程中创建新检查点。新检查点包含切换之前的所有变更。对于拥有数百万个文件的集群，检查点可以在一分钟左右创建完成。完成后，它被写入本地和远程磁盘。

恢复只需要最新的完整检查点和后续的日志文件。旧的检查点和日志文件可以自由删除，不过我们会保留几份以防灾难性故障。检查点过程中的故障不会影响正确性，因为恢复代码会检测并跳过不完整的检查点。

2.7 一致性模型

GFS采用宽松的一致性模型，很好地支持了我们的高度分布式应用，同时实现起来相对简单高效。现在我们讨论GFS提供的保证，以及它们对应用程序的意义。我们还将强调GFS如何维护这些保证，但具体细节留待本文其他部分介绍。

2.7.1 GFS的保证

文件命名空间变更（例如文件创建）是原子的。它们完全由主服务器处理：命名空间锁保证了原子性和正确性（第4.1节）；主服务器的操作日志定义了这些操作的全局全序（第2.6.3节）。

数据变更后文件区域的状态取决于变更类型、变更是否成功，以及是否存在并发变更。表1总结了结果。如果所有客户端无论从哪个副本读取，看到的数据始终相同，则该文件区域是一致的。如果文件数据变更后区域是一致的，并且客户端将看到变更写入的全部内容，则该区域是已定义的。

当变更成功且没有并发写入者干扰时，受影响的区域是已定义的（并且隐含是一致的）：所有客户端将始终看到变更写入的内容。并发的成功变更会使区域处于未定义但一致的状态：所有客户端看到相同的数据，但该数据可能不反映任何一个变更写入的内容。通常，它由来自多个变更的混合片段组成。失败的变更会使区域不一致（因此也是未定义的）：不同客户端在不同时间可能看到不同的数据。

我们将在下文介绍应用程序如何区分已定义区域和未定义区域。应用程序无需进一步区分不同类型的未定义区域。

	写入	记录追加
串行成功	已定义	已定义，中间夹杂不一致
并发成功	一致但未定义	已定义，中间夹杂不一致
失败	不一致	—

表1：变更后的文件区域状态

2.7.2 对应用程序的影响

GFS应用程序可以通过一些简单的技术来适应这种宽松的一致性模型，这些技术本来也适用于其他分布式系统。这些技术包括：依赖追加而非覆盖、写入校验和、写入唯一标识符，以及写入时写入预期的序列号。应用程序可以使用校验和来验证记录的完整性，并识别并丢弃填充或重复的记录。大多数应用程序只需要在恢复时重放少量记录。

对于大多数应用而言，追加写入语义远比覆盖写入更有用。追加操作天然高效，并且不存在并发写入者相互覆盖的问题。例如，在生产者-消费者队列中，生产者可以并发地向文件追加记录，而消费者可以通过检查点机制记录已处理的位置。

对于读取操作，只要应用程序能够容忍偶尔的不一致区域，就不需要额外的同步。例如，在数据处理作业中，读取数据的程序通常只扫描整个文件，并且能够处理偶尔出现的损坏或重复记录。

如果应用需要更强的一致性，可以使用以下机制：

写入后校验：写入者可以在数据中包含校验和，读取者验证校验和。
序列号：每条记录包含唯一的序列号，读取者可以据此检测重复和缺失。
命名空间原子操作：文件创建等命名空间操作是原子的，可以用于同步。

3. 系统交互

我们现在详细描述客户端、块服务器和主服务器之间的交互，以实现数据变更、租约管理、数据流和原子追加。

3.1 租约与变更顺序

GFS使用租约（lease）机制来保持多个副本之间的变更顺序。主服务器向其中一个副本授予块租约，该副本称为主副本（primary）。主副本为块的所有变更选择一个串行顺序。所有副本都遵循这个顺序执行变更，从而保证全局一致性。

租约机制的设计目标是最小化主服务器的管理开销。租约初始超时时间为60秒。然而，只要块正在被写入，主副本就可以请求并通常获得主服务器的续期。这些续期请求和响应通过块服务器与主服务器之间的常规心跳消息捎带传输。

以下是写入操作的完整步骤（参见图2）：

客户端向主服务器询问哪个块服务器持有该块的租约，以及其他副本的位置。如果没有任何副本持有租约，主服务器选择一个副本授予租约。
主服务器回复主副本和次要副本的位置。客户端缓存这些数据以便后续写入。只有当主副本不可达或者主副本回复称其不再持有租约时，客户端才需要重新联系主服务器。
客户端将数据推送到所有副本。客户端可以以任意顺序推送数据。每个块服务器在内部LRU缓存中保存数据，直到数据被使用或过期。通过将数据流与控制流分离，我们可以独立于数据推送顺序来调度昂贵的网络流量。我们将在第3.2节进一步讨论数据流。
一旦所有副本都确认收到数据，客户端就向主副本发送写入请求。该请求标识了之前推送到所有副本的数据。主副本为收到的所有变更分配连续的序列号，这提供了必要的串行化。它按序列号顺序将变更应用到自己的本地状态。
主副本将写入请求转发给所有次要副本。每个次要副本按照主副本分配的相同序列号顺序应用变更。
所有次要副本都回复主副本，表示它们已完成操作。
主副本回复客户端。任何副本上遇到的任何错误都将返回给客户端。如果发生错误，写入可能在主副本和部分次要副本上成功（如果在次要副本上失败，则步骤6可能不会全部完成）。客户端可以通过重试来处理错误。它在重试之前会重新执行步骤3到7。

对于失败的写入，区域可能处于不一致状态。客户端代码通过重试写入来处理这种情况。在向应用层报告失败之前，会在几个不同的块副本上重试几次。

图2：写入控制与数据流

3.2 数据流

我们将数据流与控制流分离，以高效利用网络。控制流从客户端流向主副本，再流向次要副本。而数据则以流水线方式沿着精心选择的服务器链线性推送，以充分利用每个机器的网络带宽。

目标是在避免网络瓶颈和高延迟链路的同时，最大化网络吞吐量。我们不通过树形结构广播数据，而是采用线性的、沿服务器链的流水线传输。在我们的网络环境中，每台机器的入站和出站带宽大致相当，而跨机架链路通常比机架内链路更慢、更拥塞。

具体来说，数据沿着块服务器链逐跳推送。每台机器收到数据后，立即将其转发给链中的下一台机器。这样可以充分利用每个机器的出站带宽，因为接收和转发可以并行进行。

例如，假设有三台块服务器A、B、C在不同机架上。客户端将数据发送给A，A转发给B，B转发给C。如果每跳需要时间t，那么整个传输大约需要3t时间。相比之下，如果客户端分别发送给三台机器，则需要3t的出站带宽，并且可能在客户端网络接口处形成瓶颈。

选择哪条链路由网络拓扑决定。理想情况下，数据在从客户端到最终副本的路径上，每台机器只经过一次。我们通过让每台机器将数据转发给尚未收到数据的最近副本，来近似这个目标。

流水线的另一个好处是，接收方可以在收到完整数据块之前就开始转发。由于我们使用TCP，一旦数据到达就可以立即转发，无需等待整个块。这大大减少了传输延迟。

3.3 原子记录追加

GFS提供了一种称为记录追加的原子追加操作。在传统的写入中，客户端指定写入偏移量。对同一区域的并发写入不具有串行性——该区域最终可能包含多个写入者的数据片段。而在记录追加中，客户端仅指定数据，GFS自动将数据追加到文件的至少一个偏移位置，并将该偏移位置返回给客户端。这保证了原子性，即使有多个客户端并发追加也是如此。

记录追加对于实现生产者-消费者队列至关重要。多个生产者可以并发地向同一个文件追加记录，而无需任何显式同步。每个消费者读取文件时，会看到完整的记录。

记录追加的实现与常规写入类似，但主副本需要处理一些额外的逻辑。客户端将数据推送到文件最后一个块的所有副本，然后向主副本发送请求。主副本检查追加该记录是否会导致块超过64MB的限制。如果不会，主副本将数据追加到自己的副本中，然后将相同的偏移量和长度发送给所有次要副本，并要求它们在完全相同的偏移处写入数据。

如果追加会使块超过最大大小，主副本会将当前块填充到最大大小，然后通知次要副本也这样做，并回复客户端，指示操作应该在下一个块重试。（记录追加的数据大小严格限制为最大块大小的四分之一，以保证最坏情况下的碎片率仍然可接受。）

当记录追加在某些副本上失败时，客户端会重试。因此，不同副本可能包含不同的数据——同一记录可能出现重复，或者在不同副本中出现在不同位置。GFS不保证所有副本在字节级别完全相同。它只保证数据作为一个整体被至少写入一次——这是原子性的基本含义。

应用程序必须能够处理重复和可能的填充记录。可以通过在每条记录中写入唯一标识符，然后扫描并跳过重复项来处理。应用程序还可以使用校验和来检测填充数据。

3.4 快照

快照操作几乎可以瞬间创建文件或目录树的副本，而不会中断正在进行的变更。我们使用标准的**写时复制（copy-on-write）**技术来实现快照。

当主服务器收到快照请求时：

它首先撤销对即将被快照的文件中所有块的租约。这确保任何后续写入都必须与主服务器交互以查找新的租约持有者。这给了主服务器先创建块副本的机会。
租约撤销或过期后，主服务器将操作记录到磁盘。然后，它通过复制源文件或目录树的元数据，将该日志记录应用到其内存状态。新创建的快照文件指向与源文件相同的块。

当客户端随后想要写入这些块之一时，它首先向主服务器请求当前租约持有者。主服务器注意到该块的引用计数大于1。它不会直接回复租约信息，而是要求每个块服务器创建该块的新副本。每个块服务器在本地创建新块后，主服务器可以将租约授予其中一个新副本，并回复客户端。客户端然后可以正常写入该块，而不会影响现有的快照。

4. 主服务器操作

主服务器执行所有命名空间操作。此外，它管理整个系统中的块副本：创建块、重新复制、重新均衡，以及垃圾回收。

4.1 命名空间管理与加锁

主服务器在执行任何命名空间操作之前，都会获取适当的锁以保证串行化。与传统文件系统不同，GFS没有每个目录的inode或目录条目数据结构。相反，它使用表示路径名的字符串的前缀树（trie）来表示命名空间。树中的每个节点都有一个关联的读写锁。

每个命名空间操作在执行前都会获取一组锁。通常，涉及路径/d1/d2/.../dn/leaf的操作会获取路径/d1、/d1/d2、…、/d1/d2/.../dn上的读锁，以及完整路径/d1/d2/.../dn/leaf上的读锁或写锁。

例如，快照操作获取/home和/save上的读锁，以及/home/user和/save/user上的写锁。文件创建操作获取/home和/home/user上的读锁，以及/home/user/foo上的写锁。这两个操作会被正确串行化，因为它们尝试获取/home/user上的冲突锁。

文件创建不需要在父目录上获取写锁，因为不存在”目录”或类似inode的数据结构需要防止修改。名称上的读锁足以防止父目录被删除、重命名或快照。

这种加锁方案的一个优良特性是允许同一目录中的并发变更。例如，多个文件创建可以在同一目录中并发执行：每个都获取目录名上的读锁和文件名上的写锁。目录名上的读锁足以防止目录被删除、重命名或快照。文件名上的写锁则串行化了两次创建同名文件的尝试。

由于命名空间可能有很多节点，读写锁对象采用惰性分配方式，并且在不再使用时删除。此外，锁按照一致的全序获取以防止死锁：首先按命名空间树的层级排序，同一层级内按字典序排序。

4.2 副本放置

GFS集群高度分布在多个机架上。块副本放置策略有两个目标：最大化数据可靠性和可用性，以及最大化网络带宽利用率。仅在机器之间分散副本是不够的——这只能防止机器故障，但不能防止整个机架故障（例如网络交换机、电源故障）。

因此，我们将块副本分布在不同的机架上。这确保即使整个机架损坏或离线，每个块也有副本幸存。这也意味着读取（尤其是大规模读取）可以利用多个机架的聚合带宽。另一方面，写入必须遍历多个机架，这是我们愿意接受的权衡。

副本放置还考虑磁盘空间利用率和负载均衡。主服务器在放置新块时，会选择磁盘空间利用率低于平均水平的块服务器。此外，它会限制每个块服务器上最近的创建数量，以防止写入风暴。当然，最终副本必须分布在不同机架上。

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

主服务器在三种情况下创建块副本：块创建、重新复制和重新均衡。

当创建一个新块时，主服务器选择在哪里放置初始副本。它考虑几个因素：

我们希望在磁盘空间利用率低于平均水平的块服务器上放置新副本。
我们希望限制每个块服务器上”最近”创建的数量，以防止写入流量激增。
如上所述，我们希望将副本分布在不同机架上。

当块的可用副本数量低于目标时，主服务器会重新复制该块。这可能由多种原因触发：块服务器不可用、块服务器报告其副本可能已损坏、磁盘出现故障，或者复制目标被提高。

每个需要重新复制的块都有优先级。优先级主要取决于缺失了多少副本以及缺失了多久。例如，丢失了两个副本的块比丢失了一个副本的块优先级更高。此外，属于活跃文件的块比属于最近删除文件的块优先级更高。最后，为了最小化对运行中工作负载的影响，我们提高了阻塞客户端的块的优先级。

主服务器按优先级顺序重新复制块。它选择一个块，然后指示某个块服务器直接从现有的有效副本”克隆”该块。目标副本的放置标准与新块类似：均衡磁盘空间、限制单个服务器上的并发克隆数量、跨机架分布。

为了防止克隆操作占用过多带宽，主服务器限制每个块服务器上的并发克隆数量。此外，每个块服务器通过限制向源块服务器的读取请求速率，来限制每个克隆操作消耗的带宽。

最后，主服务器定期重新均衡副本：它检查当前的副本分布，并移动副本以实现更好的磁盘空间和负载均衡。通过这个过程，主服务器逐渐填满新的块服务器，而不是立即用新块和随之而来的大量写入流量淹没它。新副本的放置标准与上述类似。此外，主服务器还必须选择移除哪个现有副本。通常，它优先移除磁盘空闲空间低于平均水平的块服务器上的副本，以均衡磁盘空间使用率。

4.4 垃圾回收

文件删除后，GFS不会立即回收可用的物理存储空间。它仅在常规垃圾回收期间惰性地回收，包括文件级和块级的回收。我们发现这种方法使系统更简单、更可靠。

4.4.1 机制

当应用程序删除文件时，主服务器会像其他变更一样立即记录删除操作。然而，它不会立即回收资源，而是将文件重命名为一个包含删除时间戳的隐藏名称。在主服务器定期扫描文件系统命名空间时，如果这些隐藏文件已存在超过三天（该间隔可配置），就会将其移除。在此之前，文件仍然可以通过新的特殊名称读取，并且可以通过重命名回正常名称来撤销删除。当隐藏文件从命名空间中移除时，其内存中的元数据被擦除。这实际上切断了它与所有块的链接。

在类似的块命名空间定期扫描中，主服务器识别孤立块（即无法从任何文件到达的块），并擦除这些块的元数据。在与主服务器定期交换的心跳消息中，每个块服务器报告其拥有的块的子集，主服务器回复所有已不存在于主服务器元数据中的块的标识。块服务器可以自由删除这些块的副本。

4.4.2 讨论

尽管在编程语言上下文中，分布式垃圾回收是一个需要复杂解决方案的难题，但在我们的场景中却相当简单。我们可以轻松识别所有对块的引用：它们都在主服务器唯一维护的文件到块映射中。我们也可以轻松识别所有块副本：它们是每个块服务器上指定目录下的Linux文件。任何主服务器不知道的副本都是”垃圾”。

与立即删除相比，垃圾回收方式回收存储有几个优势：

简单可靠：在组件故障频发的大规模分布式系统中，这一点至关重要。块创建可能在部分块服务器上成功而在其他服务器上失败，留下主服务器不知道存在的副本。副本删除消息可能丢失，主服务器必须记住在故障（自身故障和块服务器故障）后重发。垃圾回收提供了一种统一且可靠的方式来清理所有已知无用的副本。
批量处理，成本摊销：它将存储回收合并到主服务器的常规后台活动中，例如命名空间的定期扫描和与块服务器的心跳握手。因此，它以批量方式执行，成本被摊销。此外，它只在主服务器相对空闲时执行。主服务器可以更及时地响应需要及时处理的客户端请求。
安全网：存储回收的延迟为意外的、不可逆的删除提供了安全保障。

根据我们的经验，主要缺点是当存储紧张时，这种延迟有时会妨碍用户调整使用量。反复创建和删除临时文件的应用可能无法立即重用存储空间。我们通过以下方式解决这些问题：如果已删除文件被再次显式删除，则加速存储回收。我们还允许用户对命名空间的不同部分应用不同的复制和回收策略。例如，用户可以指定某个目录树中文件的所有块都不进行复制存储，并且任何删除的文件都会立即且不可撤销地从文件系统状态中移除。

4.5 过期副本检测

如果块服务器发生故障并且在停机期间错过了块的变更，块副本可能会过期。对于每个块，主服务器维护一个块版本号，以区分最新副本和过期副本。

每当主服务器授予块的新租约时，它都会增加块版本号，并通知所有最新副本。主服务器和这些副本都在它们的持久化状态中记录新的版本号。这发生在任何客户端收到通知之前，因此也发生在客户端可以开始写入块之前。如果另一个副本当前不可用，其块版本号不会被提升。当块服务器重启并报告其块集合及相应的版本号时，主服务器会检测到该块服务器拥有过期副本。如果主服务器看到的版本号大于其记录中的版本号，主服务器会认为自己在授予租约时发生了故障，因此采用更高的版本号作为最新版本。

主服务器在常规垃圾回收中移除过期副本。在此之前，当回复客户端的块信息请求时，它实际上认为过期副本根本不存在。作为另一项保障，当主服务器通知客户端哪个块服务器持有块的租约时，或者当它指示块服务器在克隆操作中从另一个块服务器读取块时，都会包含块版本号。客户端或块服务器在执行操作时验证版本号，以确保始终访问最新数据。

5. 容错与诊断

设计系统的最大挑战之一是处理频繁的组件故障。组件的质量和数量共同使得这些问题成为常态而非异常：我们不能完全信任机器，也不能完全信任磁盘。组件故障可能导致系统不可用，或者更糟的是，数据损坏。我们将讨论如何应对这些挑战，以及系统中内置的诊断工具。

5.1 高可用性

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

5.1.1 快速恢复

主服务器和块服务器都被设计为无论如何终止，都能在数秒内恢复状态并启动。事实上，我们不区分正常终止和异常终止；服务器通常通过直接杀死进程来关闭。客户端和其他服务器会经历轻微的中断，因为它们的未完成请求超时，然后重新连接到重启后的服务器并重试请求。

5.1.2 复制

如前所述，每个块都被复制到多个机架上的多个块服务器。用户可以为文件命名空间的不同区域指定不同的复制因子。默认值为三。当块服务器离线或检测到损坏的副本时，主服务器会使用现有副本重新创建块。

对于主服务器，其状态也被复制以实现高可用性。操作日志和检查点被复制到多台机器上。只有在日志记录被刷新到本地和所有远程副本之后，状态变更才被视为已提交。主服务器进程在任何时候只在一台机器上运行。当主服务器发生故障时，可以使用其在其他机器上的持久化状态在其他地方启动新的主服务器。

“影子”主服务器在主主服务器出现故障时提供只读访问。它们是影子，而非镜像，因为它们的状态可能略微滞后于主服务器，通常不到一秒。它们增强了文件系统在主服务器更新期间或主服务器故障切换期间的读取可用性。

5.2 数据完整性

每个块服务器都使用校验和来检测存储数据的损坏。考虑到每个块服务器上有许多磁盘，磁盘和IDE子系统级别的数据损坏并不罕见。

每个64MB的块被划分为64KB的块。每个块对应一个32位的校验和。与其他元数据一样，校验和存储在内存中，并持久化记录到磁盘，与用户数据分开。

对于读取，块服务器在返回数据之前验证相应块的校验和。这防止了损坏的数据被传播到其他客户端或块服务器。如果某个块损坏，块服务器向请求者返回错误，并通知主服务器。然后客户端可以从其他副本读取数据，主服务器可以从其他副本重新创建该块。

对于追加写入，校验和计算经过优化以匹配追加为主的工作负载。我们增量地更新部分填充的最后一个块的校验和，并为新追加的完整块计算新的校验和。

对于覆盖写入（即写入现有块的中间位置），我们必须读取被覆盖区域的第一个和最后一个块，验证它们的校验和，然后执行写入，最后重新计算校验和。这就是为什么随机写入效率较低的原因之一。

在空闲时间，块服务器可以扫描和验证不活跃块的校验和。这使我们能够检测未被读取的块的损坏。一旦检测到损坏，主服务器可以创建新的完好副本并删除损坏的副本。

5.3 诊断工具

广泛的诊断日志记录极大地帮助了问题隔离、调试和性能分析，而开销却微乎其微。GFS服务器生成各种事件日志和大量的RPC日志。

事件日志记录服务器生命周期中的重要事件，例如服务器启动和关闭、故障检测等。RPC日志记录进出的每个RPC请求和响应的详细信息，包括时间戳、消息大小等。通过关联不同服务器上的RPC日志，我们可以重建完整的交互历史来诊断问题。

日志还用于性能分析和工作负载研究。由于日志是追加写入的，对正在运行的系统影响很小。

6. 性能测量

我们现在展示GFS在微观基准和真实生产集群中的性能表现。

6.1 微观基准

我们在一个包含1台主服务器、2台主服务器副本、16台块服务器和16台客户端的集群上测量了性能。所有机器都配备双1.4GHz PIII处理器、2GB内存、一个80GB 5400rpm IDE磁盘和100Mbps全双工以太网。它们连接到一个HP ProCurve 2524交换机。整个GFS集群位于同一个机架上。

6.1.1 读取

图3(a)显示了聚合读取吞吐量。我们启动了N个客户端，每个客户端同时从整个文件系统中读取数据。每个客户端读取4GB的数据，总共读取N×4GB。读取被分为64KB的大小，随机偏移。

随着客户端数量从1增加到16，聚合读取吞吐量从10MB/s增长到94MB/s。这接近网络的理论最大值（16台客户端×100Mbps = 200MB/s全双工，但交换机背板只有约120MB/s的容量）。

单客户端的读取性能约为10MB/s，这也接近单个100Mbps链路的限制。

6.1.2 写入

图3(b)显示了聚合写入吞吐量。N个客户端各自向N个不同的文件写入1GB数据。写入同样以64KB为单位。

单客户端写入速度约为6MB/s。随着客户端数量增加到16，聚合写入达到约35MB/s。这低于读取吞吐量，部分原因是写入需要写入三个副本，并且每个副本都消耗网络带宽。

6.1.3 记录追加

图3(c)显示了记录追加的性能。N个客户端并发地向同一个文件追加记录。每条记录大小为64KB。

单客户端速度约为5MB/s。随着客户端数量增加，聚合吞吐量增长到约20MB/s。由于所有客户端都写入同一个文件，主副本成为瓶颈。这是预期的行为——记录追加并非设计用于数百个客户端同时向同一个文件写入的场景。对于大多数应用，多个生产者写入不同的文件更为常见。

图3：聚合吞吐量。上方曲线表示由网络拓扑限制的理论上限；下方曲线表示实测值。(a) 读取 (b) 写入 (c) 记录追加

6.2 真实世界集群

表2展示了谷歌两个生产集群的特征。集群X用于研究和开发，集群Y用于生产数据处理。

	集群X	集群Y
块服务器数量	342	227
可用磁盘空间	72 TB	180 TB
文件数量	335万	735万
块数量	800万	1500万
元数据大小（主服务器）	53 MB	115 MB
每台块服务器平均读取速率	9 MB/s	15 MB/s
每台块服务器平均写入速率	3 MB/s	5 MB/s
主服务器操作速率	~700 ops/s	~500 ops/s

表2：生产集群特征

这些数字表明，主服务器的元数据内存占用很小——只有几十MB。这验证了我们的说法，即主服务器内存不是瓶颈。

集群Y的磁盘空间更大，但文件和块数量更少，因为它的文件平均更大。两个集群的读写速率都显示出健康的流量水平。

6.3 恢复时间

我们测量了块服务器故障后的恢复时间。我们杀死了一个持有约15000个块（总计约1TB数据）的块服务器。为了限制对运行中工作负载的影响，重新复制被限速，并且集群还有其他写入活动。

所有块在23.2分钟内恢复到完整的复制因子。平均恢复速率约为440Mbps，这是合理的，因为它允许多个源块服务器并行发送数据。

在另一个测试中，我们杀死了两个块服务器（每个约16000个块）。这导致266个块减少到只有一个副本。这些高优先级块在2分钟内全部被重新复制。

6.4 工作负载分解

表3显示了两个集群上操作类型的细分。操作按涉及的字节数和操作计数来衡量。

	集群X		集群Y
	字节	操作	字节	操作
读取	83%	61%	95%	72%
写入	17%	16%	5%	11%
记录追加	0%	23%	0%	17%

表3：工作负载分解（字节和操作计数）

读取在两个集群中都占主导地位，这符合预期。记录追加操作在操作数量上占比很大，但字节数很少，因为记录通常很小。

值得注意的是，元数据操作（打开、创建、删除等）在操作计数中占相当大的比例。这是因为许多应用程序创建和删除大量临时文件。集群Y中元数据操作的比例较低，因为其自动化数据处理任务倾向于检查文件系统的部分内容以了解全局应用状态。相比之下，集群X的应用受到更明确的用户控制，并且通常预先知道所有需要的文件名。

7. 经验与教训

在构建和部署GFS的过程中，我们经历了各种问题，有些是运维方面的，有些是技术方面的。

最初，GFS被构想为我们生产系统的后端文件系统。随着时间推移，其用途扩展到包括研发任务。它最初对权限、配额等支持很少，但现在已经包含了这些功能的基本形式。生产系统纪律严明、受控良好，但用户有时并非如此。需要更多基础设施来防止用户相互干扰。

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

早些时候，我们在Linux 2.2内核上遇到了一些与fsync()成本相关的问题。它的成本与文件大小成正比，而不是与修改部分的大小成正比。这对于我们的大型操作日志来说是个问题，尤其是在我们实现检查点之前。我们曾一度使用同步写入来解决这个问题，并最终迁移到Linux 2.4。

另一个Linux问题是单个读写锁——地址空间中的任何线程在从磁盘分页（读锁）或在mmap()调用中修改地址空间（写锁）时都必须持有该锁。我们在轻负载下看到系统出现瞬时超时，并努力寻找资源瓶颈或偶发硬件故障。最终我们发现，当磁盘线程正在分页调入先前映射的数据时，这个锁会阻塞主网络线程将新数据映射到内存。由于我们主要受网络接口而非内存拷贝带宽的限制，我们通过用pread()替代mmap()来解决这个问题，代价是多了一次拷贝。

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

8. 相关工作

与AFS等其他大型分布式文件系统一样，GFS提供了位置无关的命名空间，使数据可以透明地移动以实现负载均衡或容错。与AFS不同的是，GFS将文件数据分散在存储服务器上，这种方式更类似于xFS和Swift，以提供聚合性能和更高的容错能力。

由于磁盘相对便宜，并且复制比更复杂的RAID方案更简单，GFS目前仅使用复制来实现冗余，因此比xFS或Swift消耗更多的原始存储空间。

与AFS、xFS、Frangipani和Intermezzo等系统不同，GFS不在文件系统接口之下提供任何缓存。我们的目标工作负载在单次应用运行中几乎没有数据重用，因为它们要么流式处理大型数据集，要么在其中随机查找并每次读取少量数据。

一些分布式文件系统（如Frangipani、xFS、明尼苏达大学的GFS和GPFS）移除了集中式服务器，依赖分布式算法来实现一致性和管理。我们选择集中式方法是为了简化设计、提高可靠性并获得灵活性。特别是，集中式主服务器使得实现复杂的块放置和复制策略变得容易得多，因为主服务器已经拥有大部分相关信息并控制其变化。我们通过保持主服务器状态较小并在其他机器上完整复制来解决容错问题。目前，我们的影子主服务器机制提供了可扩展性和高读取可用性。主服务器状态的更新通过追加到预写日志来持久化。因此，我们可以采用类似Harp中的主副本方案，以提供比当前方案更强一致性保证的高可用性。

我们正在解决与Lustre类似的问题，即向大量客户端提供聚合性能。然而，我们通过关注应用需求而非构建POSIX兼容的文件系统，大大简化了问题。此外，GFS假设有大量不可靠组件，因此容错是我们设计的核心。

GFS与NASD架构最为相似。NASD架构基于网络附加磁盘驱动器，而GFS使用商用机器作为块服务器，这与NASD原型中的做法相同。与NASD工作不同，我们的块服务器使用惰性分配的固定大小块，而不是可变长度对象。此外，GFS实现了生产环境所需的重新均衡、复制和恢复等功能。

与明尼苏达大学的GFS和NASD不同，我们不寻求改变存储设备的模型。我们专注于利用现有商用组件，解决复杂分布式系统的日常数据处理需求。

原子记录追加支持的生产者-消费者队列解决了与River中分布式队列类似的问题。River使用分布在机器上的基于内存的队列和精细的数据流控制，而GFS使用可以被多个生产者并发追加的持久化文件。River模型支持m到n的分布式队列，但缺乏持久化存储带来的容错能力，而GFS仅高效支持m到1的队列。多个消费者可以读取同一个文件，但它们必须协调以划分传入负载。

9. 结论

谷歌文件系统展示了在商用硬件上支持大规模数据处理工作负载所必需的品质。虽然一些设计决策是针对我们独特环境的，但许多决策可以应用于类似规模和成本意识的数据处理任务。

我们从根据当前和预期的应用负载与技术环境重新审视传统文件系统假设开始。我们的观察导向了设计空间中截然不同的切入点。我们将组件故障视为常态而非异常，针对主要是追加写入（可能是并发的）然后读取（通常是顺序的）的大文件进行优化，并且扩展和放宽了标准文件系统接口以改进整个系统。

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

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

我们已经展示了这样一个系统如何支持大规模生产环境，同时为研发提供灵活的平台。从这项工作中得出的关键教训是，对于大规模分布式系统，组件故障是常态，必须作为设计的一等公民来处理。通过接受故障、针对预期的访问模式进行优化，并放宽传统的一致性和接口约束，我们可以构建一个强大、高性能且具有成本效益的系统。

参考文献

[1] T. Anderson, M. Dahlin, J. Neefe, D. Patterson, D. Roselli, and R. Wang. Serverless network file systems. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 109-126, December 1995.

[2] E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson. Hoard: A scalable memory allocator for multithreaded applications. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 117-128, November 2000.

[3] D. A. D. R. J. M. D. S. H. D. C. B. J. Z. T. S. E. G. W. V. S. M. F. K. A. Swift: Using redundant disks to improve file system performance. In Proceedings of the 14th ACM Symposium on Operating Systems Principles, pages 94-105, December 1993.

[4] G. A. Gibson, D. F. Nagle, K. Amiri, J. Butler, F. W. Chang, H. Gobioff, C. Hardin, E. Riedel, D. Rochberg, and J. Zelenka. A cost-effective, high-bandwidth storage architecture. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 92-103, October 1998.

[5] J. H. Howard, M. L. Kazar, S. G. Menees, D. A. Nichols, M. Satyanarayanan, R. N. Sidebotham, and M. J. West. Scale and performance in a distributed file system. ACM Transactions on Computer Systems, 6(1):51-81, February 1988.

[6] J. J. Kistler and M. Satyanarayanan. Disconnected operation in the Coda file system. ACM Transactions on Computer Systems, 10(1):3-25, February 1992.

[7] B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams. Replication in the Harp file system. In Proceedings of the 13th ACM Symposium on Operating Systems Principles, pages 226-238, October 1991.

[8] P. J. Braam. The Lustre storage architecture. Cluster File Systems, Inc., November 2002.

[9] D. Patterson, G. Gibson, and R. Katz. A case for redundant arrays of inexpensive disks (RAID). In Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pages 109-116, June 1988.

[10] F. Schmuck and R. Haskin. GPFS: A shared-disk file system for large computing clusters. In Proceedings of the First USENIX Conference on File and Storage Technologies, pages 231-244, January 2002.

[11] S. A. Brandt, E. L. Miller, D. D. E. Long, and L. Xue. Efficient metadata management in large distributed file systems. In Proceedings of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies, pages 290-298, April 2003.

[12] C. A. Thekkath, T. Mann, and E. K. Lee. Frangipani: A scalable distributed file system. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 224-237, October 1997.