论文精读：《The Google File System》——大规模分布式数据存储的核心

type

status

date

slug

summary

引言

Google 文件系统（GFS）是 Google 用于满足其大规模数据处理需求的核心基础设施。随着 Google 数据量的迅速增长，传统的文件系统在性能、可扩展性和可靠性方面都无法满足需求。因此，Google 的工程师们设计了 GFS，这是一种专为分布式数据密集型应用设计的可扩展分布式文件系统。

GFS 的设计目标包括性能、可扩展性、可靠性和可用性。然而，其设计受当前及预期的应用工作负载和技术环境的驱动，显著不同于早期文件系统的假设。

GFS 的设计考虑了以下几个关键观察：

组件故障是常态：系统由数百到数千个廉价商品硬件组成，任何时候都会有一些组件故障。因此，GFS 的设计必须能够容忍这些故障，并确保系统的高可用性。

文件规模巨大：多 GB 的文件很常见，文件通常包含许多应用对象。传统文件系统的设计假设在处理这些大文件时显得捉襟见肘，因此需要重新评估 I/O 操作和块大小等设计参数。

文件操作模式：与传统文件系统不同，GFS 主要处理的是数据追加操作而非覆盖操作。随机写入在 GFS 中几乎不存在，文件一旦写入完成，通常只进行顺序读取。

应用和文件系统 API 的共同设计：通过放宽一致性模型，GFS 简化了系统设计，同时满足了应用的需求。例如，GFS 引入了原子追加操作，允许多个客户端并发地追加数据到同一个文件。

在接下来的部分中，我们将详细介绍 GFS 的设计概述、系统交互、主服务器操作、故障容忍和诊断以及性能测量。

设计概述

GFS 的设计基于以下假设和目标：

系统组件：系统由许多廉价商品组件构建，因此需要常规的监控、容错和恢复能力。组件故障是常态，而非异常情况。

文件规模：系统存储大量大文件，通常每个文件大小为 100 MB 或更大，通常为 GB 级别。尽管小文件也需要支持，但系统不需要对其进行优化。

工作负载：工作负载主要包括两种读取类型：大规模流式读取和小规模随机读取。大规模流式读取通常读取数百 KB 或更多的数据，而小规模随机读取通常读取几 KB 的数据。性能意识强的应用程序通常会批处理并排序小规模读取，以稳步推进文件读取。

写入操作：工作负载中还包括大量的顺序写操作，通常是追加数据。一次写入操作的大小通常与读取操作类似。一旦写入，文件很少被修改。小规模写入操作也需要支持，但不需要高效。

并发操作：系统必须有效地实现多个客户端对同一文件的并发追加操作的语义，确保原子性和最小化同步开销。文件通常用作生产者-消费者队列或多路合并。

带宽要求：高持续带宽比低延迟更重要。大多数目标应用程序更关注以高速度处理大量数据，而不是单个读取或写入操作的响应时间。

接口

GFS 提供了类似于传统文件系统的接口，但并未实现标准的 POSIX API。文件按层次结构组织在目录中，通过路径名标识。支持的操作包括创建、删除、打开、关闭、读取和写入文件。此外，GFS 提供了快照和记录追加操作，支持分布式应用程序。例如，快照操作能够低成本地创建文件或目录树的副本，记录追加操作允许多个客户端并发地追加数据到同一个文件，保证每个客户端追加操作的原子性。

体系结构

一个 GFS 集群包括一个主服务器、多个块服务器和多个客户端。文件被分割成固定大小的块，每个块由主服务器分配一个唯一的 64 位块句柄，块服务器通过该句柄来读写块数据。为确保可靠性，每个块在多个块服务器上存储副本。

例如，某个文件被分割成多个 64 MB 的块，每个块在三个块服务器上存储副本。主服务器负责管理文件系统元数据，包括文件到块的映射、块的位置以及副本的管理。客户端通过主服务器获取块的位置信息，然后直接与块服务器通信进行数据读写操作。

内存数据结构

由于 GFS 的设计需要处理大量的元数据，主服务器需要一种高效的方法来管理和访问这些数据。将元数据存储在内存中可以显著提高操作速度，因为内存访问的速度远快于磁盘 I/O 操作。这使得主服务器能够快速响应客户端请求，并进行各种系统维护任务。

GFS 主服务器在内存中存储三种主要类型的元数据：

文件和块命名空间：这是一个逻辑上表示文件系统命名空间的查找表，将完整路径名映射到相应的元数据。

文件到块的映射：这是从文件映射到块的关系表，每个文件被分割成多个块，主服务器需要维护这些块的位置信息。

块副本的位置：这是每个块在不同块服务器上的副本位置的记录。

内存数据结构的实现细节

命名空间管理：

命名空间树：GFS 采用前缀压缩技术在内存中高效存储命名空间树。每个节点（即文件或目录）都有一个读写锁，用于控制并发访问。

锁机制：主服务器操作在运行前会获取相应的锁，例如文件创建操作需要获取父目录的读锁和文件名的写锁，以确保操作的原子性和一致性。

文件到块的映射：

映射表：GFS 在内存中维护文件到块的映射表，每个文件被分割成固定大小的块。主服务器需要知道每个文件由哪些块组成，以及这些块的位置。

块副本的位置：

块位置记录：主服务器在内存中记录每个块在不同块服务器上的位置。块服务器定期向主服务器报告其持有的块，主服务器通过这些报告保持块位置记录的最新状态。

内存数据结构的优势：

高效的操作速度：

快速响应：由于元数据存储在内存中，主服务器可以快速响应客户端的元数据操作请求，如文件创建、删除、打开和关闭等。

快速扫描：主服务器可以定期扫描整个元数据状态，以执行垃圾回收、重新复制和重新平衡等任务。这些操作在内存中进行速度非常快。

内存使用的优化：

前缀压缩：命名空间数据使用前缀压缩技术，可以高效地表示文件名，从而减少内存占用。

块元数据的高效存储：每个 64 MB 块的元数据占用少于 64 字节的内存，这意味着主服务器可以在内存中维护大量块的元数据而不会导致内存不足。

灵活的扩展能力：

增加内存：如果需要支持更大的文件系统，可以通过增加主服务器的内存来实现。增加内存的成本相对较低，但可以显著提高系统的性能和容量。

分布式管理：通过在多个机器上分布存储元数据，GFS 可以有效地管理和扩展其内存数据结构。

内存数据结构的持久化

虽然元数据主要存储在内存中，但为了防止数据丢失，GFS 还采用了操作日志（operation log）和检查点（checkpoint）机制来持久化元数据：

操作日志：所有的元数据变更都会记录在操作日志中，并在主服务器的本地磁盘和远程机器上进行复制。这样，即使主服务器发生故障，也可以通过重放操作日志恢复元数据。

检查点：主服务器定期将当前的元数据状态保存为检查点，从而缩短恢复时间。在主服务器重启时，它会加载最新的检查点，并重放自检查点以来的操作日志。

示例说明

假设有一个文件 /home/user/data 被创建并写入数据。在这个过程中，主服务器会进行以下操作：

创建文件：主服务器在内存中更新命名空间树，为 /home/user/data 创建一个新的节点，并记录其元数据。

分配块：主服务器为该文件分配一个或多个块，并在文件到块的映射表中记录这些块的信息。

记录块位置：块服务器将块的位置报告给主服务器，主服务器在内存中记录每个块的位置。

主服务器

主服务器在 GFS 中负责管理整个文件系统的元数据。它主要负责以下几项关键任务：

命名空间管理：维护文件和目录的层次结构，包括创建、删除、重命名文件和目录等操作。

文件到块的映射：记录每个文件由哪些块组成，以及这些块的位置。

块副本管理：跟踪每个块在不同块服务器上的副本位置，负责副本的创建、删除和重新复制。

协调客户端操作：处理客户端对文件系统的操作请求，并协调多个客户端对同一文件的并发操作。

单一主服务器的优势

简化设计：单一主服务器的设计使得系统架构更简单，避免了多主服务器之间的复杂协调问题。所有的元数据操作都集中在一个地方进行管理，简化了系统的实现。

一致性保证：由于所有的元数据变更都通过主服务器进行，可以更容易地保证文件系统的一致性。主服务器可以控制对文件和块的访问，确保不会出现冲突。

集中管理：主服务器集中管理文件系统的所有元数据，使得系统维护和监控更为简单。任何对文件系统结构的修改都可以通过主服务器统一处理。

单一主服务器的挑战

单点故障：主服务器是整个系统的核心，一旦主服务器出现故障，整个文件系统将无法正常工作。虽然 GFS 设计了主服务器的快速恢复机制，但依然存在一定的风险。

性能瓶颈：随着系统规模的扩大，主服务器需要处理的元数据请求量也会增加，可能成为系统性能的瓶颈。虽然元数据存储在内存中，访问速度很快，但依然需要高效的管理策略来避免过载。

扩展性限制：单一主服务器在处理超大规模集群时可能面临扩展性问题。尽管通过增加内存和优化算法可以缓解这一问题，但依然存在一定的物理和管理限制。

系统交互

租约和变更顺序

GFS 使用租约机制来维护跨副本的一致变更顺序。主服务器将块租约授予一个副本（称为主副本），该副本负责为所有变更选择一个序列号，其他副本按照此顺序应用变更。例如，当客户端请求写入数据时，主服务器首先将租约授予某个块的一个副本（主副本），主副本负责为所有的写操作分配一个序列号，然后将数据推送到所有副本。副本按照主副本指定的顺序应用这些变更，从而保证所有副本的一致性。

写操作的控制流程如下：

客户端请求主服务器，获取持有当前块租约的块服务器以及其他副本的位置。

主服务器回复主副本和其他副本的位置。

客户端将数据推送到所有副本。

所有副本确认接收到数据后，客户端向主副本发送写请求。

主副本将写请求转发给其他副本，并分配序列号。

所有副本按照序列号顺序应用变更。

所有副本确认完成变更后，主副本向客户端回复。

数据流

GFS 的设计中，数据流与控制流是分离的。数据在一个精心挑选的块服务器链中逐步传输，以高效利用网络带宽，避免网络瓶颈和高延迟链接。例如，数据流沿着块服务器链以流水线方式传输，每个块服务器接收到数据后立即开始转发，从而最小化数据传输的总延迟。

，数据传输过程如下：

客户端将数据推送到第一个块服务器。

第一个块服务器将数据转发给下一个块服务器。

依此类推，直到所有块服务器接收到数据。

这种数据流设计的优势在于：

充分利用网络带宽：每个块服务器的输出带宽用于尽快传输数据，而不是在多个接收者之间分配带宽。

避免网络瓶颈：数据传输尽可能避免经过高延迟的网络链路，如跨交换机的链路。

最小化延迟：通过流水线传输，一旦块服务器接收到数据就立即开始转发，从而减少了总的传输时间。

原子记录追加

GFS 提供了原子追加操作，允许多个客户端并发地追加数据到同一个文件。客户端仅需指定数据内容，GFS 将其追加到文件的末尾，保证操作的原子性。主副本负责为追加操作分配偏移量，并通知其他副本执行相同的操作。

原子记录追加的过程如下：

客户端将数据推送到所有副本。

客户端向主副本发送追加请求。

主副本检查数据追加是否会导致块超出最大大小。

如果不会超出最大大小，主副本将数据追加到块的末尾，并通知其他副本执行相同的操作。

所有副本确认完成操作后，主副本向客户端回复操作成功。

这种设计确保了多个客户端可以并发追加数据，而不会导致数据不一致或冲突。

快照

快照操作几乎瞬时地创建文件或目录树的副本，最小化对正在进行的变更的中断。通过标准的写时复制技术，GFS 能够高效地创建快照，而不会对系统性能产生显著影响。

快照操作的过程如下：

主服务器撤销正在进行的块租约，以确保对快照块的任何写入都需要与主服务器交互。

主服务器将快照操作记录到日志中，并在内存中复制源文件或目录树的元数据。

当客户端请求写入快照块时，主服务器为块创建新副本，并将写入请求指向新副本。

这种设计使得快照操作既高效又对系统性能影响最小。

主服务器操作

命名空间管理和锁定

GFS 使用锁定机制确保命名空间操作的正确性。每个命名空间节点（绝对路径名）有一个读写锁，主服务器操作在运行前获取相应的锁，以防止并发冲突。例如，当进行文件创建操作时，主服务器需要获取父目录的读锁和文件名的写锁，以确保操作的原子性和一致性。

命名空间操作的锁定过程如下：

如果操作涉及 /d1/d2/.../dn/leaf，主服务器将对 /d1、/d1/d2、...、/d1/d2/.../dn 获取读锁，并对 /d1/d2/.../dn/leaf 获取读锁或写锁。

例如，当执行 /home/user/foo 文件的创建操作时，主服务器需要对 /home 和 /home/user 获取读锁，并对 /home/user/foo 获取写锁。

这种锁定机制确保了并发操作的正确性，例如，在 /home/user 正在被快照到 /save/user 时，文件 /home/user/foo 的创建操作将被正确地序列化。

这种锁定机制的一个优点是，它允许在同一目录中的并发变更。例如，可以在同一目录中并发创建多个文件，因为每个文件创建操作对目录名获取读锁，对文件名获取写锁。

副本放置

块副本的放置策略旨在最大化数据的可靠性和可用性，以及最大化网络带宽利用率。副本跨多个机架分布，以确保即使整个机架不可用，块仍然可用。例如，在创建新块时，主服务器会优先选择磁盘利用率较低的块服务器，并将副本分布在不同的机架上，以避免单点故障。

副本放置的策略如下：

磁盘利用率：主服务器选择磁盘利用率较低的块服务器，以平衡磁盘使用。

活动块创建限制：限制每个块服务器上的“最近”创建操作数量，以避免块服务器因大量写操作而过载。

机架分布：确保块副本分布在不同的机架上，以避免单点故障。

这种策略确保了数据的高可靠性和可用性，同时优化了系统性能。

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

主服务器在创建块时选择副本放置位置，并在副本数量低于用户指定的目标时进行重新复制。此外，主服务器还定期重新平衡副本，以优化磁盘空间和负载分布。例如，当某个块服务器上的副本数量过多时，主服务器会将部分副本迁移到其他块服务器，以均衡负载。

创建、重新复制和重新平衡的过程如下：

块创建：主服务器根据磁盘利用率和机架分布选择块副本的放置位置。例如，当一个新块被创建时，主服务器会选择磁盘利用率较低的块服务器，并将副本分布在不同的机架上。

重新复制：当副本数量低于目标时，主服务器会选择一个块服务器从现有副本复制数据，以恢复副本数量。例如，当某个块服务器故障导致副本数量减少时，主服务器会选择一个块服务器从现有副本复制数据。

重新平衡：主服务器定期检查副本分布，并在需要时进行重新平衡。例如，当某个块服务器上的副本数量过多时，主服务器会将部分副本迁移到其他块服务器，以均衡负载。

这种策略确保了系统的高可用性和性能优化。

垃圾回收

文件删除后，GFS 不立即回收物理存储，而是通过定期的垃圾回收过程来实现。这样简化了系统设计，提供了对误删除的保护。例如，当文件被删除时，主服务器仅将其重命名为隐藏文件，定期扫描文件系统时才真正删除这些文件，确保数据可以在一定时间内恢复。

垃圾回收的过程如下：

文件删除：当文件被删除时，主服务器将其重命名为隐藏文件，并记录删除时间。

延迟回收：在定期扫描文件系统时，主服务器删除已存在超过三天的隐藏文件，并删除其元数据。例如，当文件被删除后，系统会在定期扫描中删除这些文件，确保数据可以在一定时间内恢复。

孤立块删除：主服务器在定期扫描块命名空间时，识别孤立块（即不再被任何文件引用的块），并删除这些块的元数据。在 HeartBeat 消息中，块服务器报告其持有的块，主服务器回复不再存在于元数据中的块，块服务器随后删除这些块。

这种延迟回收机制使得系统更加简单和可靠，同时提供了对误删除的保护。

过时副本检测

主服务器通过块版本号区分最新副本和过时副本。主服务器在授予新租约时增加块版本号，未能更新的副本被标记为过时副本，在垃圾回收过程中删除。例如，当某个块服务器重新加入集群时，主服务器会检查其块版本号，并将过时的副本标记为垃圾。

过时副本检测的过程如下：

块版本号：主服务器为每个块维护一个版本号，当授予新租约时增加版本号。例如，当主服务器为一个块授予新租约时，会增加该块的版本号，并通知持有最新副本的块服务器。

副本报告：块服务器在启动时报告其持有的块及其版本号，主服务器根据版本号判断副本是否过时。例如，当某个块服务器重新加入集群时，主服务器会检查其报告的块版本号，并将过时的副本标记为垃圾。

过时副本删除：在定期的垃圾回收过程中，主服务器指示块服务器删除过时副本。例如，当主服务器在定期扫描中发现过时副本时，会指示块服务器删除这些副本。

这种机制确保了系统中的块副本始终是最新的，防止数据不一致。

故障容忍和诊断

高可用性

通过快速恢复和复制策略保持系统高可用性。主服务器和块服务器设计为在几秒钟内恢复状态并重启。例如，当主服务器故障时，系统会自动启动备用主服务器，并从操作日志中恢复状态，确保系统快速恢复运行。

高可用性的实现包括以下几个方面：

快速恢复：主服务器和块服务器设计为能够在几秒钟内恢复状态并重启。例如，当块服务器故障时，系统会自动从其他副本恢复数据，并在几秒钟内重新启动块服务器。

块复制：每个块在多个块服务器上存储副本，通常为三个副本。用户可以为不同的文件指定不同的复制级别。例如，当某个块服务器故障时，系统会从其他副本恢复数据，并确保块的复制级别。

主服务器复制：主服务器的状态通过操作日志和检查点在多个机器上进行复制，以提高可靠性。例如，当主服务器故障时，系统会自动启动备用主服务器，并从操作日志中恢复状态。

这种设计确保了系统的高可用性，即使在某些组件故障时，系统仍能正常运行。

数据完整性

块服务器使用校验和检测存储数据的损坏，发现损坏后从其他副本恢复数据。例如，每个块被分为多个 64 KB 的块，每个块都有一个对应的校验和。在读取数据时，块服务器会验证校验和，以确保数据的完整性。

数据完整性的保证包括以下几个方面：

校验和验证：

每个块被分为多个 64 KB 的块，每个块都有一个对应的校验和。在读取数据时，块服务器会验证校验和，以确保数据的完整性。例如，当客户端请求读取数据时，块服务器会首先验证数据的校验和，然后将数据返回给客户端。

2. 数据恢复：

当发现数据损坏时，块服务器从其他副本恢复数据。例如，当块服务器在读取数据时发现校验和不匹配，会报告主服务器，并从其他副本恢复数据。

3. 空闲期验证：

在空闲期，块服务器会扫描和验证不活动块的内容，以检测数据损坏。例如，当块服务器在空闲期扫描数据时发现损坏，会报告主服务器，并从其他副本恢复数据。

这种机制确保了数据的完整性，即使在数据损坏的情况下，系统也能够从其他副本恢复数据。

诊断工具

GFS 服务器生成详细的诊断日志，记录重要事件和所有 RPC 请求和回复。这些日志可用于问题诊断、调试和性能分析。例如，通过分析 RPC 日志，可以重建服务器之间的交互历史，帮助工程师定位和解决问题。

诊断工具的使用包括以下几个方面：

诊断日志：GFS 服务器生成详细的诊断日志，记录重要事件和所有 RPC 请求和回复。例如，当块服务器故障时，系统会记录故障原因和恢复过程，帮助工程师诊断问题。

RPC 日志：RPC 日志包括在网络上传输的确切请求和响应（不包括读取或写入的文件数据）。通过匹配请求和回复，并整理不同机器上的 RPC 记录，可以重建交互历史。例如，通过分析 RPC 日志，可以了解客户端和块服务器之间的交互过程，帮助工程师定位和解决问题。

性能分析：诊断日志还可用于负载测试和性能分析。例如，通过分析诊断日志，可以了解系统的负载情况和性能瓶颈，帮助工程师优化系统性能。

这种详细的诊断日志记录和分析机制，使得工程师能够高效地定位和解决问题，并优化系统性能。

性能测量

微基准测试

通过微基准测试评估 GFS 的性能，展示了读、写和记录追加操作的聚合吞吐量。例如，在一个包含 1 个主服务器、2 个主服务器副本、16 个块服务器和 16 个客户端的 GFS 集群中，测量了不同客户端数量下的读写性能。

微基准测试的结果如下：

读操作：N 个客户端同时从文件系统读取数据。每个客户端从 320 GB 文件集中随机选择一个 4 MB 区域读取 256 次，总共读取 1 GB 数据。块服务器的总内存仅为 32 GB，因此 Linux 缓存命中率不会超过 10%。测试结果接近冷缓存结果。

写操作：N 个客户端同时向 N 个不同文件写入数据。每个客户端以 1 MB 的写入单位向新文件写入 1 GB 数据。总的写入速率和理论极限如下所示。

记录追加操作：N 个客户端同时向同一个文件追加数据。性能受限于存储文件最后一个块的块服务器的网络带宽，而与客户端数量无关。随着客户端数量增加，由于网络拥塞和传输速率的差异，性能略有下降。

例如，当只有一个客户端读取数据时，聚合读速率为 10 MB/s，占每客户端带宽的 80%。当有 16 个客户端读取数据时，聚合读速率达到 94 MB/s，占 125 MB/s 链路限制的 75%。

真实集群

在 Google 内部使用的两个代表性集群上测量的性能数据展示了 GFS 的实际应用效果。例如，一个用于研发的集群包含 342 个块服务器，提供 72 TB 的可用存储空间，另一个用于生产数据处理的集群包含 227 个块服务器，提供 180 TB 的可用存储空间。

两个真实集群的特点如下：

集群 A：用于研发，支持超过 100 名工程师的日常工作。任务通常由人类用户启动，持续数小时，读取从几 MB 到几 TB 的数据，进行数据转换或分析，然后将结果写回集群。

集群 B：主要用于生产数据处理。任务持续时间较长，连续生成和处理多 TB 数据集，几乎不需要人工干预。单个任务由多个进程组成，分布在多台机器上，同时读取和写入多个文件。

两个集群的存储和元数据如下：

存储：集群 A 提供 72 TB 的可用存储空间，使用了 55 TB；集群 B 提供 180 TB 的可用存储空间，使用了 155 TB。两者都有超过 700,000 个文件。

元数据：块服务器总共存储了数十 GB 的元数据，主要是 64 KB 数据块的校验和。主服务器的元数据较小，只有几十 MB，平均每个文件约 100 字节。大部分元数据是使用前缀压缩存储的文件名。

集群 A 的平均读速率为 589 MB/s，集群 B 的平均写速率为 117 MB/s。主服务器每秒处理数百个操作，轻松应对工作负载。

例如，当集群 B 中一个块服务器故障时，系统在 23.2 分钟内恢复了所有块的复制水平，恢复速率为 440 MB/s。在另一个实验中，当两个块服务器同时故障时，系统在 2 分钟内恢复了 266 个块的双重复制水平，确保了数据的高可用性。

经验总结

GFS 的设计和实现有效地满足了 Google 的大规模数据处理需求，通过创新的设计理念和强大的故障容忍能力，为分布式文件系统的发展提供了宝贵的经验。例如，通过分离数据流和控制流、使用大块大小和引入原子追加操作，GFS 能够高效地处理大量并发请求，并确保数据的一致性和完整性。

GFS 的成功经验包括以下几个方面：

大块大小：通过使用 64 MB 的大块大小，减少了客户端与主服务器的交互次数，简化了元数据管理，并提高了系统性能。

松散一致性模型：通过放宽一致性模型，简化了系统设计，满足了分布式应用程序的需求。例如，引入原子追加操作，允许多个客户端并发地追加数据，确保操作的原子性和一致性。

数据流与控制流分离：通过分离数据流和控制流，优化了网络带宽利用率，避免了网络瓶颈和高延迟链路。

高效的故障恢复：通过快速恢复和复制策略，确保了系统的高可用性和数据完整性。例如，当某个块服务器故障时，系统能够迅速从其他副本恢复数据，确保数据的高可用性。

详细的诊断日志：通过详细的诊断日志记录和分析机制，工程师能够高效地定位和解决问题，并优化系统性能。

这些经验为其他大规模分布式文件系统的设计提供了重要参考。

引言