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可以增加我们的灵活性，从而使整个系统受益。例如，我们使用弱一致性模型，以简化文件系统。我们还引入了原子追加操作，以便多个客户机可以并发地追加到一个文件，而无需在它们之间进行额外的同步。

设计

假设

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

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

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

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

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

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

接口

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

GFS还有快照(snapshot)和记录追加(record append)操作。

架构

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

这些机器都是普通的Linux机器。

文件被划分成固定大小的chunks。每个chunk由一个不可变且全局唯一的64位chunk handle标识，是在chunk创建时由master分配的。chunkservers将chunks作为Linux文件存储在本地磁盘，通过指定的chunk handle和byte range读或写chunk数据。为了提高可靠性，每个chunk被复制在多个chunkservers上。默认情况下，存储三个副本，不过用户可以为文件命名空间的不同区域指定不同的复制级别。

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

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

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

使用单个的master

使用单个master极大简化了设计，并使得master可以借助全局知识做出复杂的chunk placement和replication decisions。Master不参与文件读写，客户端询问master应该联系哪个chunkservers，直接与相应的chunkservers交互。

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

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

chunk size

使用64MB作为chunk size，每个chunk副本以普通Linux文件的形式存储在chunkservers上，当在有需要的时候扩展。

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位置信息。相反，它会在master启动时以及每当有chunkserver加入集群时询问每个chunkserver关于它的chunk。

In-Memory Data Structures

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

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

Chunk Locations

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

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

Operation Log

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

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

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

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

一致性模型

GFS采用弱一致性模型，足以满足需求。

GFS的保证

文件名称空间的变化(例如，文件创建)是原子性的。命名空间锁保证原子性和正确性;Master的操作日志定义了这些操作的全局总顺序。

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

如果所有客户端总是看到相同的数据，无论他们从哪个副本读取，那么文件区域就是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做出反应之前(通常在几分钟内)所有副本都丢失时，块才会不可逆转地丢失。即使在这种情况下，它也变得不可用，而不是损坏:应用程序接收到明显的错误，而不是损坏的数据。

Leases和Mutation顺序

Mutation操作改变一个chunk的内容或者元数据，并作用与一个chunk的所有副本。

我们使用Leases维护副本之间mutation顺序的一致性。Master把这个chunk lease授予一个副本，这个副本称为primary，它决定mutation顺序，其余的副本都遵循这个顺序。

未完待续…

参考文献

[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.