The Google File System

今天看了The Google File System的论文，我们简称其为GFS。GFS是谷歌的分布式文件存储系统，这篇论文是现代分布式软件系统入门的经典论文，并由此诞生了Hadoop生态中HDFS的开源实现。

我不会一字一句地翻译这篇论文，因为我并不是想实现这样一个系统，我打算将一些关键点提炼出来以供学习。

介绍

GFS shares many of the same goals as previous distributed file systems such as performance, scalability, reliability, and availability.

GFS与之前的分布式文件系统有着许多共同的目标，比如性能、可扩展性、可靠性和可用性。

但是，Google在实践中提出了与早期分布式文件系统不同的设计。

首先，组件失效是常态而不是例外。因此，持续监控(constant monitoring)、错误检测(error detection)、容错( fault tolerance)和自动恢复(automatic recovery) 必须是系统的组成部分。

其次，文件很大，几个GB的文件是很常见的。但是把他们分成KB大小的文件(数量可以达到上亿个)来管理是难以处理的。因此需要重新设计IO操作和块大小。

第三，大多数文件被修改的方式是追加新数据而不是重写已存在数据。文件中的随机写入实际上是不存在的。一旦写入，文件就只能被读取，而且通常只能按顺序读取。考虑到这种对大文件的访问模式，追加成为性能优化和原子性保证的重点。

第四，共同设计应用程序和文件系统API可以增加我们的灵活性，从而使整个系统受益。例如，我们使用弱一致性模型，以简化文件系统。我们还引入了原子追加操作，以便多个客户机可以并发地追加到一个文件，而无需在它们之间进行额外的同步。

设计

假设

以下假设来指导我们设计一个符合需求的文件系统：

1. 该系统由许多经常失效的组件构建而成。它必须不断地监控自身，并在常规基础上检测、容忍组件故障，并迅速从组件故障中恢复。

2. 系统存储适当数量的大文件。我们期望有几百万个文件，每个文件的大小通常为100mb或更大。几GB大小的文件是常见的情况，应该有效地管理。必须支持小文件，但我们不需要针对它们进行优化。

3. 工作负载主要由两种类型的读取（操作）组成：大规模流读取和小规模随机读取。在大规模流读取操作中，单次操作通常读取数百KB大小，更常见的是1M或者更多。来自同一客户端的连续操作经常读取某一文件的一个连续区域。小规模的随机读取通常在任意偏移位置读取若干KB大小。

4. 这些工作负载还有许多大的、顺序的写操作，将数据追加到文件中。文件一旦写入，就很少再被修改。支持在文件中的任意位置进行小的写操作，但不一定要高效。

5. 系统必须有效地为并发追加到同一文件的多个客户端实现定义良好的语义。

6. 高持续带宽比低延迟更重要。我们的大多数目标应用程序都重视以高速率批量处理数据，而很少有对单个读或写有严格的响应时间要求。

接口

GFS提供了熟悉的文件系统接口。文件在目录中按层次组织，并由路径名标识。GFS支持常见的操作来 create, delete, open, close, read, 和 write 文件.

GFS还有快照(snapshot)和记录追加(record append)操作。 snapshot 以低开销创建文件或者目录的副本。record append 确保每个单独客户端 append 的原子性，允许多个客户端并发地向相同的文件追加数据。

架构

GFS集群由单个 master 和多个 chunkservers 组成，并且可以被多个 clients 访问，如图1所示。

这些机器都是运行用户层面服务进程的普通的Linux机器。

文件被划分成固定大小的 chunks 。每个 chunk 由一个不可变且全局唯一的 64 位 chunk handle 标识，是在 chunk 创建时由 master 分配的。

Chunkservers 将 chunks 作为 Linux 文件存储在本地磁盘，通过指定的 chunk handle 和 byte range 读写 chunk 数据。为了提高可靠性，每个 chunk 被复制到多个 chunkservers 上。默认情况下，存储三个副本，不过用户可以为 file namespace 的不同区域指定不同的复制级别。

master 维护所有文件系统元数据(metadata)。包括 namespace 、访问控制信息、files 到 chunks 的映射以及 chunks 的当前位置。它还控制系统范围的活动，如 chunk lease management 、孤立 chunks 的垃圾回收和 chunkservers 之间的 chunks 迁移。master 定期使用 HeartBeat 消息与每个 chunkserver 通信，给它指令并且收集它的状态。

连接到每个应用程序中的 GFS client 代码实现文件系统 API ，并与 master 和 chunkserver 通信，以代表应用程序读取或写入数据。Clients 与 master 交互以进行元数据操作，但是所有承载数据的通信都直接通过 chunkservers 。

client 和 chunkserver 都不缓存文件数据。客户端缓存提供的好处很少，因为文件很大，无法缓存。这样可以消除缓存一致性问题，简化系统，但是客户端会缓存 metadata 。chunkserver 不需要缓存文件数据，因为 chunks 被存储为本地文件，因此 Linux 的 buffer cache 已经将频繁访问的数据保存在内存中。

博主注：这里的 namespace 可能让人一头雾水，我们见过了太多的 'namespace' ，在 Linux 系统中，在 C++ 中，不同的语境下其含义各不相同，但是其大体意思都是一致的，即 隔离 。借助 wikipedia 上的定义：

A namespace in computer science (sometimes also called a name scope) is an abstract container or environment created to hold a logical grouping of unique identifiers or symbols (i.e. names).

namespace 是一个抽象容器或环境，被创建用于保存唯一标识符或者符号的逻辑分组。

使用单个的master

使用单个 master 极大简化了设计，并使得 master 可以借助全局知识做出复杂的 chunk placement 和 replication decisions 。

master 不参与文件读写，client 询问 master 自己应该联系哪些 chunkservers，并且会在一段时间内缓存这个信息， 在后续操作中直接与 chunkservers 交互。

让我们模拟一下一次简单读取的流程:
首先，使用固定的 chunk 大小，client 将应用程序指定的 file name 和 byte offset 转换为文件中的 chunk 索引。
然后，它向 master 发送一个包含 file name 和 chunk索引 的请求。
master 返回相应的 chunk handle 和副本的位置。client 使用 file name 和 chunk索引 作为键来缓存这些信息。
然后，client 向其中一个副本(很可能是最近的副本)发送请求。这个请求指定 chunk handle 和该 chunk 中的 byte range 。在缓存的信息过期或文件被重新打开之前，对同一 chunk 的进一步读取不需要更多的 client-master 交互。

实际上，client 通常会在同一个请求中请求多个 chunk ，而 master 也可以在请求后立即包含 chunk 的信息。这些额外的信息避免了未来的几个 client-master 交互，几乎没有额外的成本。

chunk size

使用 64MB 作为 chunk size ，每个 chunk 副本以普通Linux文件的形式存储在 chunkservers 上，只根据需要进行扩展。

大的 chunk size 带来了如下的优点：

1. 减少了 client 需要与 master 交互的次数
2. 大的 chunk 使得 client 可以在其上做很多操作，减少了网络开销
3. 减小了存放在 master 上的 metadata 的大小

Metadata

master 存储三种主要类型的 metadata : the file and chunk namespaces , the mapping from files to chunks 和 the locations of each chunk’s replicas .

所有 metadata 都保存在 master 的内存中。前两种类型也通过将改变记录到存储在 master 本地磁盘中并复制到远程机器上的 operation log 中来保持持久化。使用日志允许我们简单、可靠地更新 master 的状态，并且在 master 崩溃时不会冒不一致的风险。master 不持久化 chunk 的位置信息（也就是第三种类型的 metadata ）。相反，它会在 master 启动时以及每当有 chunkserver 加入集群时询问每个 chunkserver 关于它的 chunk 信息。

In-Memory Data Structures

由于 metadata 存储在 master 的内存中，所以 master 的操作很快。而且，master 可以在后台周期性地扫描其整个状态，这既简单又有效。这种周期性扫描用于实现 chunk 垃圾回收、出现 chunkserver 故障时的重新复制以及 chunk 迁移，以平衡 chunkserver 之间的负载和磁盘空间使用。

这种只使用内存的方法的一个潜在问题是，chunk 的数量以及整个系统的容量受到 master 拥有多少内存的限制。这在实践中并不是一个严重的问题。

master 为每个 64mb 的 chunk 维护少于 64 字节的 metadata 。大多数 chunk 都是满的，因为大多数文件包含许多 chunk ，只有最后一个 chunk 可能被部分填充。

同样的，每个文件的 file namespace 数据通常要求小于 64 字节，因为它使用前缀压缩紧凑地存储文件名。

Chunk Locations

master 不会持久记录哪些 chunkservers 拥有给定 chunk 的副本。它只是在启动时轮询 chunkservers 以获取该信息。此后，master 可以使自己保持最新状态，因为它控制所有 chunk 的放置，并使用常规的 HeartBeat 消息监视 chunkserver 状态。

这样的做法更简单，因为 chunkserver 离开和加入集群是常有的事，如果持久地存储这部分信息会导致同步问题。

Operation Log

操作日志记录了 metadata 重大变更的历史记录。这是 GFS 的核心。它不仅是 metadata 的唯一持久记录，而且还用作定义并发操作顺序的逻辑时间线。file 和 chunk ，以及它们的版本，都是由它们被创建时的逻辑时间唯一且永久地标识的。

由于操作日志是至关重要的，我们必须可靠地存储它，并且在 metadata 更改持久化之前，不能使更改对客户机可见。否则，即使 chunks 本身被保存下来，我们也会丢失整个文件系统或最近的客户端操作。因此，我们在多台远程机器上复制它，并且只有在本地和远程将相应的日志记录刷新到磁盘之后才响应客户机操作。master 在刷新之前将多个日志记录 batch 在一起，从而减少刷新和复制对整个系统吞吐量的影响。

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

恢复只需要最新的完整 checkpoint 和后续的日志文件。

一致性模型

GFS 采用弱一致性模型，足以满足需求， 实现起来简单且高效。

GFS的保证

文件 namespace 的改变(例如，文件创建)是原子性的。namespace 锁保证原子性和正确性;master 的操作日志定义了这些操作的全局总顺序。

数据改变之后的文件区域的状态取决于改变的类型、成功还是失败以及是否存在并发改变。表 1 总结了结果。

如果所有客户端总是看到相同的数据，无论他们从哪个副本读取，那么文件区域就是 consistent 。一个文件改变之后，如果它是 consistent 的，并且客户端可以看到整个改变写了什么，那么这个文件区域被称为 defined 。

当一个改变成功而不受并发写入的干扰时，受影响的区域就被定义( defined )了(并且暗含一致性):所有客户端都将始终看到改变所写的内容。

并发成功的改变使区域 undefined ，但保持一致:所有客户端都看到相同的数据，但它可能不反映任何一个改变所写的内容。

失败的改变使区域不一致(因此也 undefined ):不同的客户端可能在不同的时间看到不同的数据。

我们将在下面描述应用程序如何区分 defined 区域和 undefined 区域。应用程序不需要进一步区分不同类型的 undefined 区域。

数据变化可能是写入或追加记录。写操作导致在应用程序指定的文件偏移量处写入数据。记录追加会导致数据(“记录”)至少原子性地自动追加一次，即使在存在并发改变的情况下也是如此，但是以 GFS 选择的偏移量进行追加。(相反，“常规”追加只是在客户端认为是文件当前结束的偏移量处进行写操作。) 偏移量返回给客户端，并标记包含该记录的 defined 区域的开始。

在一系列成功的改变之后，保证被更改的文件区域defined，并包含由最后一个改变写入的数据。GFS通过(a)在其所有副本上以相同的顺序对 chunk 应用改变，以及(b)使用 chunk version numbers 来检测任何由于在其 chunkserver 关闭时错过改变而变得过时的副本来实现这一点。失效副本将永远不会涉及到改变，也不会给向 master 请求块位置的客户端。他们会被垃圾回收。

在成功的改变之后很长一段时间，组件故障当然仍然会损坏或破坏数据。GFS 通过 master 和所有 chunkserver 之间的定期握手来识别故障的 chunkserver ，并通过校验和来检测数据损坏。一旦问题出现，数据会尽快从有效的副本中恢复。只有在 GFS 做出反应之前(通常在几分钟内)所有副本都丢失时，chunk 才会不可逆转地丢失。即使在这种情况下，它也变得不可用，而不是损坏:应用程序接收到明显的错误，而不是损坏的数据。

对于应用程序的影响

GFS 应用程序可以通过一些简单的技术来适应宽松的一致性模型：依赖于追加而不是覆写，checkpointing ， 以及写自验证的，自识别的记录。

系统交互

我们设计系统的目标是最小化 master 在所有操作中的参与。在这个背景下，我们现在描述 client， master， chunkservers 是怎样交互来实现 data mutations, atomic record append, 以及 snapshot 的。

Leases和Mutation顺序

mutation 操作改变一个 chunk 的内容或者 metadata ，例如一个写或者一个 append 操作。mutation 作用于一个 chunk 的所有副本。我们使用 leases 来在副本间维持一致的 mutation 顺序。master 为其中一个副本授予一个 chunk lease ， 我们称之为 primary 。primary 为 chunk 上的所有 mutation 选择一个顺序。所有的副本在应用 mutations 时遵循这个顺序。于是，全局的 mutation 顺序首先被 master 选择的 lease 授予顺序定义，在 lease 内由 primary 分配的序列号定义。

lease 机制被设计来最小化 master 管理开销。一个 lease 的初始超时时间为 60 秒。然而，一旦 chunk 被 mutated ，primary 可以请求并且通常无限期地从 master 接收扩展。这些扩展请求和 grants 承载在 master 和所有 chunkservers 之间定期交换的 HeartBeat 消息上。master 有时尝试在 lease 到期前撤销它。即使 master 丢失了与一个 primary 的通信，在老 lease 期限后，它可以安全地授予一个新 lease 给别的副本。

在图二中，我们经由这些步骤通过跟随写控制流来阐述这个过程：

1. 客户端询问 master 哪一个 chunkserver 保存了 chunk 的当前 lease 以及其他副本的位置。如果没有人有 lease ，master 选择一个副本授予它 lease。
2. master 返回 primary 的身份以及其他副本（ secondary ）的位置。客户端缓存这些数据用于未来的 mutatios 。只有当 primary 不可达或者副本不再保存一个 lease 时，客户端才需要再次联系 master 。
3. 客户端把数据推给所有的副本。客户端可以按照任何顺序这样做。每个 chunkserver 将数据存储在内部的 LRU buffer 缓存中，直到数据被使用或者老化。通过解耦数据流和控制流，我们可以基于网络拓扑来调度昂贵的数据流，而不用去管哪个 chunkserver 是 primary 。
4. 一旦所有的副本确认了接收数据，客户端给 primary 发送一个写请求。该请求将标识之前推送到所有副本的数据。primary 为它收到的所有 mutation 分配连续的序列号，可能来自多个客户端，它提供必要的序列化。它按照序列号的顺序把 mutation 应用到自己的本地。
5. primary 将写请求转发给所有的次级副本。每个次级副本采用与 primary 相同的序列号顺序应用 mutations 。
6. 次级副本都回复 primary 表示他们已完成操作。
7. primary 回复客户端。在任何副本中遇到的任何错误都将报告给客户端。如果出现错误，写入操作可能在 primary 成功，在次级副本上成功了任意子集。（如果它在 primary 失败，它将不会分配一个序列号并且转发。）客户端请求被认为失败，修改的区域处于不一致状态。我们的客户端代码通过重试出错的 mutation 来处理这样的错误。它会在步骤 3 到 7 之间进行几次尝试。

如果应用程序的写入值很大或者跨越块边界， GFS 客户端将他拆成多个写操作。他们都遵循上面描述的控制流，但是可能会与来自其他客户端的操作交织和覆盖。因此，共享的文件区域最终可能包含来自不同客户端的片段，尽管副本是相同的，因为所有副本在各个操作上都以相同的顺序成功完成。这使得文件区域处于一致但是未定义的状态。

数据流（Data Flow）

我们使用网络有效地解耦了数据流和控制流。当控制流从客户端流向 primary ，然后流向所有次级副本时，数据以流水线的方式沿着精心挑选的 chunkservers 链线性推送。我们的目标是充分利用每台机器的网络带宽，避免网络瓶颈和高延迟连接，最小化推送所有数据的延迟。

为了充分地利用每台机器的网络带宽，数据被沿着 chunkservers 链线性推送，而不是分布在别的拓扑结构中（例如，树）。因此，每台机器的全部出站带宽用于尽可能快地传输数据，而不是在多个接收者之间分配。

为了尽可能避免网络瓶颈和高延迟连接，每台机器将数据转发给网络拓扑中没有收到数据的最近的机器。假定客户端正在将数据推送到 chunkservers S1 到 S4 。它将数据发送到最近的 chunkserver ，称为 S1 。S1 将数据转发给 S2 到 S4 中离他最近的 chunkserver ，称为 S2 。同样地，S2 转发数据到 S3 和 S4 中离自己更近的机器。我们的网络拓扑足够简单，以至于可以从 IP 地址准确地估计出距离。

最后，我们流水线化 TCP 连接上的数据来最小化延迟。一旦一个 chunkserver 接收到了一些数据，它立即开始转发。流水线对我们特别有帮助，因为我们使用全双工链路的交换网络。立即转发数据不会降低接收速率。

原子记录追加

未完待续…

参考文献

[1] Adusumilli P .THE GOOGLE FILE SYSTEM[J].[2023-08-30].
[2] Hades. 【译文】The Google File System 经典的分布式文件存储系统[EB/OL]. [2023-08-31]. https://zhuanlan.zhihu.com/p/522459187.