## 摘要

我们设计和实现了谷歌文件系统，一个面向大规模分布式数据密集型应用的可伸缩文件系统。即使在普通廉价的商用机器上，它也提供了容灾和高性能服务。

GFS的设计目标和传统分布式文件系统类似，但是我们的设计和实现是由我们的应用负载和技术环境驱动的。不管是现在还是将来，GFS和早起的设想都有出入，我们重新审视了传统文件系统在设计上的折中选择，并衍生出完全不同的设计思路。

GFS完全满足我们对存储的需求。Google内部广泛使用GFS生成和处理大数据集。最大的集群使用数千台机器，提供了数百T的存储空间，服务于数百台客户机。

本文介绍GFS对于分布式应用的接口支持和扩展，讨论GFS的设计思路和细节，列出小规模测试和生产环境中的性能数据。

## 1. Introduction

GFS的设计和实现是为了满足谷歌快速增长的数据处理需求。GFS和传统的分布式文件系统具有许多相同的设计目标，如性能、可伸缩性、可靠性、可用性。但是，其设计由我们的技术环境驱动而来，因此和早期的文件系统又有着标志性的不同。我们考虑了传统文件系统的折衷选择，并给出了完全不同的设计思路。

首先，组件失败被认为是常态事件，而非意外事件。GFS包括数百台甚至数千台机器，支持可观数量的客户机访问。在任何时刻，机器组件都有可能发生故障，或者无法恢复有效服务。我们曾经遇到过程序bug、操作系统bug、人为失误、磁盘损坏、内存损坏、网络故障、电源损坏等各种各样的问题。所以，持续的监控、错误检测、容错和自动恢复等机制需要集成到GFS中。

其次，以传统的角度看，我们的文件庞大，数G大小的文件非常普遍。。每个文件通常包含许多应用程序对象，比如web文档。当处理数亿个对象构成的数以TB的数据集时，采用管理数亿个KB大小的小文件的方式是不明智的，尽管有些文件系统支持。因此，I/O操作、文件块尺寸等因素都需要重新考虑。

第三，绝大多数文件通过在文件尾部添加新数据的方式修改，而不是覆写已有数据。对文件的随机写入，在实际生产环境中几乎不存在。一旦文件写入完成，那么这些文件通常是只读，并且是按顺序读。比如，数据分析程序扫描超大数据集；正在运行的程序不断生成数据流；已归档的数据；一台机器上生成的中间结果，会被另一台机器同时或者稍后处理。在海量文件的处理方式中，客户端对数据快的缓存没有意义，文件的追加操作是性能优化和原子性保证的主要考虑因素。

第四，应用程序和GFS API的协同设计有利于提高整个系统的灵活性。比如，我们放宽了GFS的一致性要求，从而简化了文件系统的设计，并减轻对应用程序的苛刻要求。我们引入了原子性的追加操作，以便于多个客户端操作一个文件时不需要额外的同步操作。本文稍后会介绍更多细节。

Google已经在多个项目中部署GFS集群。最大的GFS集群，拥有1000个存储节点，超过300TB的磁盘空间，支持数百台客户机连续不断的访问。

## 2 设计概览

### 2.1 假设前提

这里给出预期目标的一些细节。

* 系统由许多廉价、经常故障的商用机器组成。它必须持续监控自身、检测错误、容错和恢复失效的组件
* 系统可以存储一定数量的大文件。我们预期有几百万个文件，文件大小约100MB或者更大。数G大小的文件普遍存在，并且可以得到有效管理。小文件也支持，但是并不会为其做优化。
* 工作负载主要有两种读操作：大数据流读取和小规模的随机读取。在大数据流读取中，每次操作读取数百KB的数据，更常见的是读取1MB或者更多的数据。同一个客户端的读取操作通常会连续读取一个文件。在小规模的随机读取中，每次读操作在随机位置读取几KB的数据。性能敏感的应用，通常会打包和排列小规模的读操作，批量读取，避免来回移动文件读取位置
* 工作负载有许多大规模、顺序的、数据追加的写操作。通常操作的粒度大小和读操作类似。一旦写入完成，文件很少再次改动。随机位置的小规模写操作被支持，但效率不高
* 系统必须定义高效的、行为良好的多客户端并发追加同一文件的语义。我们的文件通常用于生产者-消费者队列或者多路合并。多台机器上数百个生产者可能会并发地追加同一文件。最小化实现原子性的同步开销是必不可少的。文件可以稍后读取，或者消费者同时读取。
* 高性能稳定网络远比低延迟重要。我们目标程序的多数都希望可以高速率的处理数据，只有极少数对单个读写操作有严格的响应时间限制

### 2.2 接口

GFS尽管没有提供POSIX风格的API，但是也提供了我们所熟悉的文件系统接口。文件以分层目录形式组织，以路径名区分。GFS支持常用的操作，如创建文件、删除文件、打开文件、关闭文件、文件读写。

此外，GFS提供文件快照和记录追加操作的功能。快照功能以较低开销，完成文件和目录树的拷贝。记录追加操作，可以保证多个客户端对同一文件发起追加操作时的原子性。记录追加操作在多路合并和生产者-消费者模型中十分有用，用户省去了额外的同步操作。这类文件在构建大型分布式应用时十分重要。快照和记录追加分别在3.4和3.3中详细讨论。

### 2.3 架构

![title](https://leanote.com/api/file/getImage?fileId=5e660120ab64413596002687)
一个GFS集群包含一个master节点和多个chunkservers节点，供多个client访问，如图1。只要机器资源允许，一台机器可以同时运行chunkserver和client，我们可以接收不可靠程序带来的稳定性降低。

文件被分割为固定大小的chunk。每个chunk被创建时，由master指定64位唯一id标识。chunkserver将chunks存储在本地硬盘，通过chunk id和字节范围读写chunk数据。为了提高可靠性，每个chunk会被复制到多个chunkserver上，默认为3。用户可以为不同命名空间的chunk指定不同的复制级别。

master节点掌管所有文件系统的元数据，包括命名空间、访问控制信息、从文件到chunks的映射信息、chunks的当前位置。master也控制整个系统的活动，比如chunk租借管理、孤儿chunk的回收以及chunkserver之间的chunk合并。master周期性以心跳包的方式和chunkserver维持通信，包括发送指令和获取chunkserver状态。

GFS客户端代码库实现文件系统API、和master节点的通信、和chunkserver节点的通信、读写chunkserver上的数据。client和master之间交互元数据，所有直接的数据操作都是client直接访问chunkserver。

无论是client还是chunkserver都不需要缓存文件数据。大多数应用直接处理大数据流或者数据太大无法缓存，因此客户端不需要做缓存。不需要缓存简化了客户端和整个系统的设计（但客户端会缓存元数据）。chunkserver不需要缓存文件数据，因为文件数据就在本地，linux系统会将经常访问的数据缓存在内存中。

### 2.4 Single Master

单一master节点简化了设计。单一master节点通过全局的元数据信息，定位chunk位置、执行复制策略。master节点不应该参与文件数据的读写，以避免成为系统瓶颈。client不通过master读写文件数据。client会询问master，得知chunkserver具体信息，然后直接访问chunkserver上的文件数据。client会将chunkserver元数据缓存，并在随后多个操作中使用。

图1展示了一个简单读操作的流程。首先，根据文件名、字节偏移位置、chunk的固定大小，client计算出chunk索引。之后，client将文件名、chunk索引发给master，询问chunk id和副本位置信息。client缓存这些信息，以文件名和chunk索引作为键，chunk id和副本位置信息作为值。

之后，client发送请求给其中最近的一个chunkserver副本。请求包含chunk id和字节范围。对相同chunk的后续操作中，client和master不会再有通信，除非缓存信息过期或者文件重新被打开。事实上，client通常会在一次请求中访问多个chunks，master也可能会范围紧跟这些chunk之后的chunk信息。这些额外信息都是为了避免client和master可能多余的交互，减少开销。

### 2.5 chunk大小

chunk大小是关键设计参数之一。我们定为64MB，比通常的文件系统要大很多。每个chunk副本被当做普通的linux文件，只有需要的时候才扩展。惰性的空间分配，避免因为内部碎片浪费空间，内部碎片可能是选择这么大的chunk大小最具争议的一点。

大尺寸chunk有如下优点。首先，减少client和master的通信，因为一次请求就可以获取所需chunk的位置信息，之后只需要在相同chunk上读写即可。这种开销减小显著降低负荷，因为应用通常顺序读写大文件。对小规模随机读取，client可以轻松缓存数TB数据集的chunk位置信息。其次，一个client可能会在某个chunk上执多个操作，保持一个TCP长链接可以减少client和chunk之间的网络负载。第三，大尺寸chunk可以减少master上存储的元数据数量，这样我们可以将元数据缓存在内存中。2.6.1中会讨论元数据放在内存中的其他优点。

### 2.6 元数据

master主要存储三类元数据：文件和chunk命名空间，文件到chunk的映射，每个chunk副本的位置信息。所有元数据保存在master内存中。前两种元数据类型，也以日志变更的方式记录在操作系统的系统日志文件中，并被复制到远程机器。通过日志记录变更，允许我们简单可靠的更新master状态，当master崩溃重建时避免数据不一致的风险。master不会持久地存储chunk位置信息，master会在启动或者一个新的chunkserver加入时，向每个chunkserver询问机器上所存储的chunk信息。

#### 2.6.1 内存中的数据结构

因为元数据保存在内存中，所以master操作极快，master可以在后台简单和有效地周期性扫描整个状态。这种周期性的扫描，可以用于实现chunk垃圾回收、chunkserver失效时重新复制、chunk迁移来达到负载均衡和磁盘使用状况。4.3和4.4会进一步讨论。

将全部元数据保存在内存中存在的一个隐患是，Chunk的数量以及整个系统的承载能力都受限于Master服务器所拥有的内存大小。在实际生产环境中，这也不算特别严重的问题。master管理每64MB个chunk，只需要少于64字节的元数据。同样地，每个文件命名空间数据也只需要少于64字节，因为保存的文件名使用前缀压缩算法压缩过的。

即使需要支持更大的文件系统，为master添加额外内存的花销也是极少的。付出很少的代价，将全部元数据保存在内存中，提高系统的简洁性、可靠性、性能和灵活性。

#### 2.6.2 chunk位置

Master节点并不持久化保存chunkserver的元数据。master节点在启动时轮询chunkserver并获取元数据。master控制了所有chunk的分配，并通过周期性的心跳监控chunkserver的状态，因此master节点能够保证元数据是最新的。

设计之初，我们试图将chunk的位置信息持久化地保存在master节点上。但是后来的设计中，我们发现启动轮询+心跳更新的方式更加简单。这种设计可以简化，当有新的chunkserver加入集群、离开集群、更名、失效以及重启时，master和chunkserver数据同步问题。在数百台机器的集群中，该类事件会频繁发生。

可以从另外一个角度理解设计决策：只有chunkserver本身才能确定一个chunk是否在它的硬盘上。没有必要在master节点上维护这些信息的全局视图，因为chunkserver的错误可能会导致chunk木了（比如，硬盘坏了或者无法访问），或者操作人重命名了一个chunkserver。

#### 2.6.3 操作日志

操作日志包含了关键的元数据变更历史记录。这对GFS十分重要。不仅是因为操作日志是元数据唯一的持久化存储记录，操作日志也是用于操作同步的判断基准。文件、chunk以及对应版本（见4.5），对应着创建时逻辑时间的唯一标识。

操作日志十分重要，我们必须保证日志文件的完整，确保只有在元数据的变化记录持久化之后，日志文件才对client可见。否则，即使chunk本身没有出现问题，但是我们仍有可能丢失整个文件系统，或者丢失client最近的操作。所以，我们会将日志复制到多台远程机器，只有将相应日志记录写入到本地以及远程机器的磁盘后，才会响应client的操作请求。master节点会批量处理多个日志记录，减少磁盘IO对系统资源的占用。

master在容灾恢复时，会重新执行操作日志，将文件系统恢复到最新状态。为减少master启动时间，日志文件应该足够小。master在日志增长到一定大小事，会对系统状态作一次快照，将所有状态数据写入到一个快照文件中。在容灾恢复时，master会从磁盘上读取快照文件，并重新执行快照文件之后的有限个日志文件就能够恢复系统。快照文件以B-数的数据结构存储，可以直接加载到内存中，在命名空间查找时无需额外解析，提高恢复速度和可用性。

创建一个快照文件需要一些时间，所以master内部状态被组织为一种格式，这种格式确保在生成快照的过程中，不会阻塞正在进行的修改操作。master节点使用独立的线程切换到新的日志文件和创建新的快照文件。新的快照文件包含切换钱所有的修改。对于一个包含数百万个文件的集群，创建一个快照文件约需1分钟。快照创建完成后，快照文件被写入本地和远程机器的磁盘。

master节点的恢复，只需要最新的快照文件和之后的日志文件。旧的快照文件和日志文件可以被删除，但是为了应对灾难性故障（即，超出预期的故障），尽量多保存一些历史文件。快照失败不会对系统的正确性产生任何影响，因为恢复部分的代码可以检测并跳过没有完成快照文件。

### 2.7 一致性模型

GFS放宽模型的一致性，这个模型可以在支持我们的分布式应用的同时，保持相对简单。本节讨论GFS一致性保障机制，以及对应用的意义。我们也描述了GFS如何管理一致性保障机制，实现细节将在本文其他部分讨论。

#### 2.7.1 GFS一致性保障机制

文件命名空间的修改（如，文件创建）是原子性的。它们仅由master节点控制：命名空间锁保证原子性和正确性；master节点的操作日志定义了这些操作在全局的顺序。

![title](https://leanote.com/api/file/getImage?fileId=5e671fb9ab6441339b005ed1)

数据修改后的文件区域的状态取决于操作类型、成功与否、是否同步修改。表1总结各种操作的结果。如果所有客户端，从任一副本都可以读取相同的数据，则文件区域是一致的；如果对文件修改之后，文件区域是一致的，且客户端可以看到写入操作的所有内容，则该文件区域是已定义的。当一个数据修改操作执行陈宫，且未受到其他写操作的干扰，则影响的文件区域是已定义的（隐含了一致性）：所有客户端都可以看到写入的内容。并发的修改操作成功执行后，文件区域处于一致的、未定义的状态：所有客户端看到同样的数据，但是无法读到任何一次写入操作的写入数据。通常，文件区域包含来自多个修改操作、混杂的数据片段。失败的修改操作会导致文件区域处于不一致状态（同时也是未定义的）：不同客户端在不同时间会看到不同的数据。后面将介绍应用如何区分已定义和未定义的文件区域。应用没有必要细分未定义文件区域的不同类型。

数据修改操作分为写入或者记录追加两种。写入操作指的是，在应用指定文件偏移位置上写入数据。即使有多个修改操作并行执行，记录追加操作保证原子性，但是偏移位置是由GFS选择（3.3），GFS返回给客户端一个偏移量，表示包含了写入记录、已定义的文件区域的起点。另外，GFS可能会在文件中插入填充数据或者重复记录。这些数据占用的文件区域是不一致的，通常比用户数据小的多。

经过一系列成功的修改操作之后，GFS确保被修改的文件区域是已定义的，并且包含了最后一次修改操作写入的数据。GFS保证上述行为的措施有：（a）对chunk的所有副本的修改操作顺序一致 (b) 使用chunk版本号检测副本是否因为所在chunkserver宕机而错过修改操作，致使失效。失效的chunk副本不会再有任何修改操作，master节点也不再将该chunk副本的位置信息返回给client。失效的chunk副本会尽快被垃圾收集系统回收。

由于chunk位置信息被client缓存，所以在信息刷新之前，client可能从给一个失效的chunk副本读取数据。在缓存过期时间和文件下一次被打开时间之间存在一个时间窗口，文件再次被打开后，会清楚缓存中与该文件有关的所有chunk信息。而且我们大多数文件都只是进行追加操作。所以一个失效的chunk副本通常返回一个chunk失效的信息，而不是过期的chunk数据。当一个client重新尝试并联络master服务器时，它会立刻得到最新的chunk位置信息。

即使修改操作成功执行很长时间，组件失效也可能损坏或者删除数据。GFS通过master服务器和所有chunkserver的定期心跳来找到失效的chunkserver，并通过校验码来检验数据是否损坏。一旦检测到问题，数据会尽快使用有效副本进行恢复。只有一个chunk的所有副本在GFS检测错误并恢复之前全部丢失。这个chunk才会不可逆的丢失。通常，GFS检测到错误并采取措施的时间长度是几分钟。在这种情况下，chunk不可用，应用程序会收到明确错误信息，并不会收到损坏的chunk数据。

#### 2.7.2 应用程序的实现

使用GFS的应用可以利用一些简单技术来实现这个宽松的一致性模型，这些技术也可以用来实现一些其他目标功能：尽量采取追加操作而不是覆写数据、快照、自校验写入、自标识的记录。

实际上，我们所有应用对文件的写入都是尽量采取追加操作。最常见的应用之一，就是从头到尾写入数据，生成一个文件。所有数据写入完成之后，应用将文件重命名为一个持久化的文件名，或者周期性的作快照，记录成功写入多少数据。快照文件包含程序级别的校验和。Reader仅校验并处理上一个快照点之后产生的文件区域，这些文件区域的状态必然是已定义的。该方法满足我们对一致性和并发处理的要求。追加操作比随机写入更加有效，且失败处理更有弹性。快照让writer渐进重新开始，且防止reader处理已经被成功写入、但实际并未完成（从应用的角度看）的数据。

另外一种典型情况就是，多个应用并发追加一个文件，如多路合并或者生产者=消费者。writer在每天写入记录中都包含额外的信息，如校验和，用于检验是否有效。reader利用校验和识别和抛弃额外的填充数据和记录片段。如果应用无法容忍偶然的重复内容（如，重复数据触发了非幂等操作），可以用唯一标识来进行过滤。这些标识通常用于命名空间中处理的实体对象，如web文档。这些I/O功能都包含在程序库中，适用于Google内部其他文件接口。

## 3 系统交互

系统设计时考虑了最小化所有操作和master的交互，在这个背景下，我们现在描述一下client、master、chunkserver之间如何交互，来实现数据修改、原子性追加操作、快照。

## 3.1 租约和更改顺序

更改（如写入操作和记录追加操作）是一个会改变chunk内容以及元数据的操作。更改操作会在chunk所有副本执行。我们使用租约机制来保持多个副本间更改顺序的一致性。master节点为chunk的一个副本建立一个租约，我们把这个副本称为主chunk。主chunk对该chunk的所有更改操作进行序列化。所有其他副本遵从该顺序进行修改。master通过租约顺序定义全局的修改操作顺序，之后租约中的主chunk分配序列号。

租约机制为了最小化master节点的负担而设计。租约的初始超时设置为60秒。不过，只要chunk被修改了，主chunk就可以向master申请延长租期。租约延长请求和批准信息附加在master节点和chunkserver之间的心跳中。有时，master节点会试图提前取消租约（如，master节点想撤销在一个已经重命名了的文件上的修改操作）。即使master节点与主chunk失去联系，master仍然可以在旧租约到期后和另外一个chunk副本签订新的租约。

![图2](https://leanote.com/api/file/getImage?fileId=5e67407cab6441339b006529)

图2展示了写入操作的控制流程，描述如下：

1. client询问master哪一台chunkserver持有当前租约，以及其他副本位置。如果没有一个chunk持有租约，master节点选择其中一个副本建立一个租约
2. master节点将主chunk的标识符以及副本返回给client。client缓存这些数据以便后续操作。只有主chunk不可用或者主chunk回复不再持有租约，client才需要和master节点重新联系
3. client将数据推送给所有副本。client可以以任意顺序推送数据。chunkserver接收到数据并保存在内部的LRU缓存中，直到数据被使用或者过期交换出去。由于网络数据流的传输负责飞铲高，通过分离数据流和控制流，可以基于网络拓扑情况对数据流进行规划，提高系统性能，而不用管哪台chunkserver保存了主chunk，3.2会进一步讨论
4. 当所有副本都确认接收到数据，client发送写请求到主chunkserver。这个请求标识了之前推送到所有副本的数据。主chunk为接收到的所有操作分配连续的序列号，这些操作可能来自不同的client，序列号保证操作顺序执行。主chunk按照序列号的顺序顺序执行这些操作，并更新自己的状态
5. 主chunk将写请求传递给所有的其他副本，其他副本按照主chunk分配的序列号以相同顺序执行操作
6. 所有其他副本回复主chunk，已经完成操作
7. 主chunkserver响应client。任何副本产生的任何错误都会返回给client。在出现错误的情况下，写入操作可能在主chunk和一些其他副本上执行成功。（如果主chunk上操作失败，则操作不会被分配序列号，也不会被传递给其他副本）。client的请求被确认为失败，被修改的文件区域处于不一致的状态。client代码通重试失败的操作来处理这样的错误。在从最开始重复执行之前，client会从步骤3到步骤7做多次尝试。

### 3.2 数据流

为了提高网络效率，我们将数据流和控制流分开。控制流从client到主chunk，再传递到次chunk，数据以管道的方式，沿着chunkserver链顺序推送。这样的方式，可以充分利用每台机器的带宽，避免网络瓶颈和高延时的连接，最小化推送所有数据的延时。

为了充分利用每台机器的带宽，数据沿着一个chunkserver链顺序推送，而不是以拓扑形式分散推送（如树型拓扑结构）。线性推送模式下，每台机器所有出口带宽都用于以最快速度传输数据，而不是只作为接受者占用带宽。

为了尽可能的避免出现网络瓶颈和高延迟的链接，每台机器都尽量选择在网络拓扑中选择一台尚未收到数据、最邻近的机器作为目标推送数据。

最后，利用TCP链接、管道式推送数据的方式最小化延迟。chunkserver接收到数据后，马上开始向前推送。管道方式的数据推送对我们帮助很大，因为我们采用全双工的交换网络。接收到数据后，立刻向前推送数据，不会降低接收速度。在没有网络拥塞的情况下，传送B字节到R个副本的理想时间是B/T+RL，其中T是网络吞吐量，L是两台机器传输延迟。通常，网络带宽是100Mbps（T），L远小于1ms。因此，1MB的数据在理想情况下约80m就可以分发出去s

### 3.3 原子的记录追加

GFS提供一种原子性的数据追加操作--记录追加。传统的写入操作，client会指定数据写入的偏移量，对同一个文件区域的并发写入不容易串行化：文件区域尾部可能会包含多个不同client写入的数据片段。使用记录追加操作，client只需要指定写入的数据。GFS保证至少有一次原子性写入操作可以成功执行（即写入一个顺序的字节流），写入的数据追加到GFS指定的偏移位置，之后GFS返回这个偏移量给client。就像在unix编程环境中，对O_APPEND模式打开的文件，多个并发写操作在无竞争时的表现。

记录追加在我们的分布式应用中使用非常频繁。如果我们采用传统的写入文件操作，client需要额外的、复杂的、代价高昂的同步机制，比如使用分布式锁。在我们的应用中，绝大多数文件用于多生产者-单消费者的队列文件，或者多路合并。

记录追加是一种更改操作，遵循3.1介绍的控制流程，此外在主chunk有些额外的控制逻辑。当client将数据推送给文件最后一个chunk的所有副本之后，发送请求给主chunk。主chunk会检查此次记录追加操作是否会使chunk超过最大尺寸（默认64MB）。如果超过，主chunk会将当前chunk填充至最大尺寸，之后通知所有次chunk执行相同操作，再回复client要求对下一个chunk冲下进行记录追加操作。（记录追加的数据大小严格控制在chunk最大尺寸的1/4，这样即使在最坏情况下，数据碎片的数量仍然可控）。通常，追加记录大小不会超过chunk最大尺寸，主chunk将数据追加到本地存储副本内，再通知次副本将数据写在和主chunk相同的位置上，最后回复client操作成功。

如果记录追加在任意一个副本上失败，client需要重试。重新进行记录追加可能会导致，同一个chunk的不同副本会包含不同的数据，因为某个副本可能会重复包含一个记录。GFS不保证chunk的所有副本在字节级别完全一致，GFS只保证作为一个整体原子性的被至少写入一次。该性质可以如此理解：如果操作执行成功，数据已经写入到chunk所有副本的相同偏移位置上，之后所有副本都到了记录尾部的长度，任何后续记录都会追加到更大的偏移位置，或者是不同的chunk上。对于一致性保障模型来说，记录追击曹邹成功写入文件区域是已定义行为（即一致的），反之是未定义（即不一致）。我们在2.7.2讨论过，我们的程序可以处理不一致的区域。

### 3.4 快照

快照操作几乎可以瞬间完成一个文件或者目录树的拷贝，且几乎不会对正在进行的其他操作造成干扰。我们的用户可以用它快速创建巨大数据集的分支副本，或者快照当前系统状态，方便之后提交或者回滚。

以AFS(Andrew File System)举例，它使用copy-on-write技术来实现快照。当master节点接收到快照请求，首先撤销所做快照文件的所有chunk租约。这样，之后的写操作，需要先和master交互查找主chunk。master节点便有机会创建chunk的新副本。

租约取消或者过期之后，master记录操作到日志。master拷贝元数据副本，并将日志记录重新应用到内存中的状态数据上。新创建的快照文件指向和源文件相同的chunk。

快照操作之后，client第一次想要写入某个chunk C的时候，会询问master主chunk位置。master发现chunk C副本不止一个，master先不会回复client，而是先去创建新的chunk副本C'。之后，就是确认主chunk，然后回复client即可。

## 4 master节点操作

master节点执行所有命名空间的操作。此外，master管理整个系统的chunk副本：决定chunk位置、创建新chunk及其副本、协调系统活动来保证chunk的完整拷贝、chunkserver负载均衡、回收不再使用的存储空间。

### 4.1 命名空间管理和锁

Master节点的很多操作会花费很长的时间：比如，快照操作必须取消Chunk服务器上快照所涉及的所有Chunk的租约。我们不希望在这些操作的运行时，延缓了其它的Master节点的操作。因此，我们允许多个操作同时进行，使用命名空间上的区域锁来保证正确顺序。

不同于传统文件系统，GFS没有针对每个目录建立数据结构，来列出目录下的所有文件。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和/home/user的读取锁，以及/home/user/foo的写入锁。这两个操作要顺序执行，因为它们试图获取的/home/user的锁是相互冲突。文件创建操作不需要获取父目录的写入锁，因为这里没有”目录”，或者类似inode等用来禁止修改的数据结构。文件名的读取锁足以防止父目录被删除。

采用这种锁方案的优点是支持对同一目录的并行操作。比如，可以再同一个目录下同时创建多个文件：每一个操作都获取一个目录名的读取锁和文件名上的写入锁。目录名的读取锁足以的防止目录被删除、改名以及被快照。文件名的写入锁序列化文件创建操作，确保不会多次创建同名的文件。

因为命名空间可能有很多节点，读写锁采用惰性分配策略，在不再使用的时候立刻被删除。同样，锁的获取也要依据一个全局一致的顺序来避免死锁：首先按命名空间的层次排序，在同一个层次内按字典顺序排序。

### 4.2 副本位置

GFS集群是高度分布的多层布局结构，而不是平面结构。典型的拓扑结构是有数百个Chunk服务器安装在许多机架上。Chunk服务器被来自同一或者不同机架上的数百个客户机轮流访问。不同机架上的两台机器间的通讯可能跨越一个或多个网络交换机。另外，机架的出入带宽可能比机架内所有机器加和在一起的带宽要小。多层分布架构对数据的灵活性、可靠性以及可用性方面提出特有的挑战。

Chunk副本位置选择的策略服务两大目标：最大化数据可靠性和可用性，最大化网络带宽利用率。为了实现这两个目的，仅仅是在多台机器上分别存储这些副本是不够的，这只能预防硬盘损坏或者机器失效带来的影响，以及最大化每台机器的网络带宽利用率。我们必须在多个机架间分布储存Chunk的副本。这保证Chunk的一些副本在整个机架被破坏或掉线（比如，共享资源，如电源或者网络交换机造成的问题）的情况下依然存在且保持可用状态。这还意味着在网络流量方面，尤其是针对Chunk的读操作，能够有效利用多个机架的整合带宽。另一方面，写操作必须和多个机架上的设备进行网络通信，但是这个代价是我们愿意付出的。

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

Chunk的副本有三个用途：Chunk创建，重新复制和重新负载均衡。

当Master节点创建一个Chunk时，它会选择在哪里放置初始的空的副本。Master节点会考虑几个因素。（1）我们希望在低于平均硬盘使用率的Chunk服务器上存储新的副本。这样的做法最终能够平衡Chunk服务器之间的硬盘使用率。（2）我们希望限制在每个Chunk服务器上”最近”的Chunk创建操作的次数。虽然创建操作本身是廉价的，但是创建操作也意味着随之会有大量的写入数据的操作，因为Chunk在Writer真正写入数据的时候才被创建，而在我们的”追加一次，读取多次”的工作模式下，Chunk一旦写入成功之后就会变为只读的了。（3）如上所述，我们希望把Chunk的副本分布在多个机架之间。

当Chunk的有效副本数量少于用户指定的复制因数的时候，Master节点会重新复制它。这可能是由几个原因引起的：一个Chunk服务器不可用了，Chunk服务器报告它所存储的一个副本损坏了，Chunk服务器的一个磁盘因为错误不可用了，或者Chunk副本的复制因数提高了。每个需要被重新复制的Chunk都会根据几个因素进行排序。一个因素是Chunk现有副本数量和复制因数相差多少。例如，丢失两个副本的Chunk比丢失一个副本的Chunk有更高的优先级。另外，我们优先重新复制活跃（live）文件的Chunk而不是最近刚被删除的文件的Chunk（查看4.4节）。最后，为了最小化失效的Chunk对正在运行的应用程序的影响，我们提高会阻塞客户机程序处理流程的Chunk的优先级。

Master节点选择优先级最高的Chunk，然后命令某个Chunk服务器直接从可用的副本”克隆”一个副本出来。选择新副本的位置的策略和创建时类似：平衡硬盘使用率、限制同一台Chunk服务器上的正在进行的克隆操作的数量、在机架间分布副本。为了防止克隆产生的网络流量大大超过客户机的流量，Master节点对整个集群和每个Chunk服务器上的同时进行的克隆操作的数量都进行了限制。另外，Chunk服务器通过调节它对源Chunk服务器读请求的频率来限制它用于克隆操作的带宽。

最后，Master服务器周期性地对副本进行重新负载均衡：它检查当前的副本分布情况，然后移动副本以便更好的利用硬盘空间、更有效的进行负载均衡。而且在这个过程中，Master服务器逐渐的填满一个新的Chunk服务器，而不是在短时间内用新的Chunk填满它，以至于过载。新副本的存储位置选择策略和上面讨论的相同。另外，Master节点必须选择哪个副本要被移走。通常情况，Master节点移走那些剩余空间低于平均值的Chunk服务器上的副本，从而平衡系统整体的硬盘使用率。

### 4.4 垃圾回收

GFS在文件删除后不会立刻回收可用的物理空间。GFS空间回收采用惰性的策略，只在文件和Chunk级的常规垃圾收集时进行。我们发现这个方法使系统更简单、更可靠。

#### 4.4.1 机制

当一个文件被应用程序删除时，Master节点象对待其它修改操作一样，立刻把删除操作以日志的方式记录下来。但是，Master节点并不马上回收资源，而是把文件名改为一个包含删除时间戳的、隐藏的名字。当Master节点对文件系统命名空间做常规扫描的时候，它会删除所有三天前的隐藏文件（这个时间间隔是可以设置的）。直到文件被真正删除，它们仍旧可以用新的特殊的名字读取，也可以通过把隐藏文件改名为正常显示的文件名的方式“反删除”。当隐藏文件被从命名空间中删除，Master服务器内存中保存的这个文件的相关元数据才会被删除。这也有效的切断了文件和它包含的所有Chunk的连接。

在对Chunk命名空间做类似的常规扫描时，Master节点找到孤儿Chunk（不被任何文件包含的Chunk）并删除它们的元数据。Chunkserver在和Master节点交互的心跳信息中，报告它拥有的Chunk子集的信息，Master节点回复Chunkserver哪些Chunk在Master节点保存的元数据中已经不存在了。Chunkesrver可以任意删除这些Chunk的副本。

#### 4.4.2 讨论

虽然分布式垃圾回收在编程语言领域是一个需要复杂的方案才能解决的难题，但是在GFS系统中是非常简单的。我们可以轻易的得到Chunk的所有引用：它们都只存储在Master服务器上的文件到块的映射表中。我们也可以很轻易的得到所有Chunk的副本：它们都以Linux文件的形式存储在Chunkserver的指定目录下。所有Master节点不能识别的副本都是”垃圾”。

垃圾回收在空间回收方面相比直接删除有几个优势。首先，对于组件失效是常态的大规模分布式系统，垃圾回收方式简单可靠。Chunk可能在某些Chunkserver创建成功，某些Chunkserver上创建失败，失败的副本处于无法被Master节点识别的状态。副本删除消息可能丢失，Master节点必须重新发送失败的删除消息，包括自身元数据信息的和Chunkserver的。垃圾回收提供了一致的、可靠的清除无用副本的方法。第二，垃圾回收把存储空间的回收操作合并到Master节点规律性的后台活动中，比如，例行扫描和与Chunk服务器握手等。因此，操作被批量的执行，开销会被减少。另外，垃圾回收在Master节点相对空闲的时候完成。这样Master节点就可以给那些需要快速反应的客户机请求提供更快捷的响应。第三，延缓存储空间回收为意外的、不可逆转的删除操作提供了安全保障。

根据我们的使用经验，延迟回收空间的主要问题是，延迟回收会阻碍用户调优存储空间的使用，特别是当存储空间比较紧缺的时候。当应用程序重复创建和删除临时文件时，释放的存储空间不能马上重用。我们通过显式的再次删除一个已经被删除的文件的方式加速空间回收的速度。我们允许用户为命名空间的不同部分设定不同的复制和回收策略。例如，用户可以指定某些目录树下面的文件不做复制，删除的文件被即时的、不可恢复的从文件系统移除。

#### 4.5 失效副本检测
 
当Chunkserver失效时，Chunkserver有可能因错失了一些修改操作而过期失效。Master节点保存了每个Chunk的版本号，用来区分当前的副本和过期副本。

无论何时，只要Master节点和Chunk签订一个新的租约，它就增加Chunk的版本号，然后通知最新的副本。Master节点和这些副本都把新的版本号记录在它们持久化存储的状态信息中。这个动作发生在任何客户机得到通知以前，因此也是对这个Chunk开始写之前。如果某个副本所在的Chunk服务器正好处于失效状态，那么副本的版本号就不会被增加。Master节点在这个Chunk服务器重新启动，并且向Master节点报告它拥有的Chunk的集合以及相应的版本号的时候，就会检测出它包含过期的Chunk。如果Master节点看到一个比它记录的版本号更高的版本号，Master节点会认为它和Chunkserver签订租约的操作失败了，因此会选择更高的版本号作为当前的版本号。

Master节点在例行的垃圾回收过程中移除所有过期失效副本。在此之前，Master节点在回复客户机的Chunk信息请求的时候，简单的认为那些过期的块根本就不存在。另外一重保障措施是，Master节点在通知客户机哪个Chunk服务器持有租约、或者指示Chunkserver从哪个Chunkserver进行克隆时，消息中都附带了Chunk的版本号。客户机或者Chunkserver在执行操作时都会验证版本号以确保总是访问当前版本的数据。

## 5 容错和诊断

我们在设计GFS时遇到的最大挑战之一是如何处理频繁发生的组件失效。组件的数量和质量让这些问题出现的频率远远超过一般系统意外发生的频率：我们不能完全依赖机器的稳定性，也不能完全相信硬盘的可靠性。组件的失效可能造成系统不可用，更糟糕的是，还可能产生不完整的数据。我们讨论我们如何面对这些挑战，以及当组件失效不可避免的发生时，用GFS自带工具诊断系统故障。

## 5.1 高可用性

在GFS集群的数百个服务器之中，在任何给定的时间必定会有些服务器是不可用的。我们使用两条简单但是有效的策略保证整个系统的高可用性：快速恢复和复制。

### 5.1.1 快速恢复

不管Master服务器和Chunkserver是如何关闭的，它们都被设计为可以在数秒钟内恢复它们的状态并重新启动。事实上，我们并不区分正常关闭和异常关闭；通常，我们通过直接kill掉进程来关闭服务器。客户机和其它的服务器会感觉到系统有点抖动，正在发出的请求会超时，需要重新连接到重启后的服务器，然后重试这个请求。6.6.2章节记录了实测的启动时间。

### 5.1.2 Chunk复制

正如之前讨论的，每个Chunk都被复制到不同机架上的不同的Chunkserver上。用户可以为文件命名空间的不同部分设定不同的复制级别。缺省是3。当有Chunkserver离线了，或者通过校验和（参考5.2节）发现了已经损坏的数据，Master节点通过克隆已有的副本保证每个Chunk都被完整复制。虽然Chunk复制策略对我们非常有效，但是我们也在寻找其它形式的跨服务器的冗余解决方案，比如使用奇偶校验、或者Erasure codes来解决我们日益增长的只读存储需求。我们的系统主要的工作负载是追加方式的写入和读取操作，很少有随机的写入操作，因此，我们认为在我们这个高度解耦合的系统架构下实现这些复杂的冗余方案很有挑战性，但并非不可实现。

### 5.1.3 master节点的复制

为了保证Master服务器的可靠性，Master服务器的状态也要复制。Master服务器所有的操作日志和checkpoint文件都被复制到多台机器上。对Master服务器状态的修改操作能够提交成功的前提是，操作日志写入到Master服务器的备节点和本机的磁盘。简单说来，一个Master服务进程负责所有的修改操作，包括后台的服务，比如垃圾回收等改变系统内部状态活动。当它失效的时，几乎可以立刻重新启动。如果Master进程所在的机器或者磁盘失效了，处于GFS系统外部的监控进程会在其它的存有完整操作日志的机器上启动一个新的Master进程。客户端使用规范的名字访问Master（比如gfs-test）节点，这个名字类似DNS别名，因此也就可以在Master进程转到别的机器上执行时，通过更改别名的实际指向访问新的Master节点。

此外，GFS中还有些“影子”Master服务器，这些“影子”服务器在“主”Master服务器宕机的时候提供文件系统的只读访问。它们是影子，而不是镜像，所以它们的数据可能比“主”Master服务器更新要慢，通常是不到1秒。对于那些不经常改变的文件、或者那些允许获取的数据有少量过期的应用程序，“影子”Master服务器能够提高读取的效率。事实上，因为文件内容是从Chunk服务器上读取的，因此，应用程序不会发现过期的文件内容。在这个短暂的时间窗内，过期的可能是文件的元数据，比如目录的内容或者访问控制信息。

“影子”Master服务器为了保持自身状态是最新的，它会读取一份当前正在进行的操作的日志副本，并且依照和主Master服务器完全相同的顺序来更改内部的数据结构。和主Master服务器一样，“影子”Master服务器在启动的时候也会从Chunk服务器轮询数据（之后定期拉数据），数据中包括了Chunk副本的位置信息；“影子”Master服务器也会定期和Chunk服务器“握手”来确定它们的状态。在主Master服务器因创建和删除副本导致副本位置信息更新时，“影子”Master服务器才和主Master服务器通信来更新自身状态。

### 5.2 数据完整性

每个Chunkserver都使用Checksum来检查保存的数据是否损坏。考虑到一个GFS集群通常都有好几百台机器、几千块硬盘，磁盘损坏导致数据在读写过程中损坏或者丢失是非常常见的（第7节讲了一个原因）。我们可以通过别的Chunk副本来解决数据损坏问题，但是跨越Chunk服务器比较副本来检查数据是否损坏很不实际。另外，GFS允许有歧义的副本存在：GFS修改操作的语义，特别是早先讨论过的原子纪录追加的操作，并不保证副本完全相同。因此，每个Chunkserver必须独立维护Checksum来校验自己的副本的完整性。

我们把每个Chunk都分成64KB大小的块。每个块都对应一个32位的Checksum。和其它元数据一样，Checksum与其它的用户数据是分开的，并且保存在内存和硬盘上，同时也记录操作日志。

对于读操作来说，在把数据返回给客户端或者其它的Chunk服务器之前，Chunk服务器会校验读取操作涉及的范围内的块的Checksum。因此Chunk服务器不会把错误数据传递到其它的机器上。如果发生某个块的Checksum不正确，Chunk服务器返回给请求者一个错误信息，并且通知Master服务器这个错误。作为回应，请求者应当从其它副本读取数据，Master服务器也会从其它副本克隆数据进行恢复。当一个新的副本就绪后，Master服务器通知副本错误的Chunk服务器删掉错误的副本。

Checksum对读操作的性能影响很小，可以基于几个原因来分析一下。因为大部分的读操作都至少要读取几个块，而我们只需要读取一小部分额外的相关数据进行校验。GFS客户端代码通过每次把读取操作都对齐在Checksum block的边界上，进一步减少了这些额外的读取操作的负面影响。另外，在Chunk服务器上，Chunksum的查找和比较不需要I/O操作，Checksum的计算可以和I/O操作同时进行。

Checksum的计算针对在Chunk尾部的追加写入操作作了高度优化（与之对应的是覆盖现有数据的写入操作），因为这类操作在我们的工作中占了很大比例。我们只增量更新最后一个不完整的块的Checksum，并且用所有的追加来的新Checksum块来计算新的Checksum。即使是最后一个不完整的Checksum块已经损坏了，而且我们不能够马上检查出来，由于新的Checksum和已有数据不吻合，在下次对这个块进行读取操作的时候，会检查出数据已经损坏了。

相比之下，如果写操作覆盖已经存在的一个范围内的Chunk，我们必须读取和校验被覆盖的第一个和最后一个块，然后再执行写操作；操作完成之后再重新计算和写入新的Checksum。如果我们不校验第一个和最后一个被写的块，那么新的Checksum可能会隐藏没有被覆盖区域内的数据错误。

在Chunk服务器空闲的时候，它会扫描和校验每个不活动的Chunk的内容。这使得我们能够发现很少被读取的Chunk是否完整。一旦发现有Chunk的数据损坏，Master可以创建一个新的、正确的副本，然后把损坏的副本删除掉。这个机制也避免了非活动的、已损坏的Chunk欺骗Master节点，使Master节点认为它们已经有了足够多的副本了。

### 5.3 诊断工具

详尽的、深入细节的诊断日志，在问题隔离、调试、以及性能分析等方面给我们带来无法估量的帮助，同时也只需要很小的开销。没有日志的帮助，我们很难理解短暂的、不重复的机器之间的消息交互。GFS的服务器会产生大量的日志，记录了大量关键的事件（比如，Chunkserver启动和关闭）以及所有的RPC的请求和回复。这些诊断日志可以随意删除，对系统的正确运行不造成任何影响。然而，我们在存储空间允许的情况下会尽量的保存这些日志。

RPC日志包含了网络上发生的所有请求和响应的详细记录，但是不包括读写的文件数据。通过匹配请求与回应，以及收集不同机器上的RPC日志记录，我们可以重演所有的消息交互来诊断问题。日志还用来跟踪负载测试和性能分析。

日志对性能的影响很小（远小于它带来的好处），因为这些日志的写入方式是顺序的、异步的。最近发生的事件日志保存在内存中，可用于持续不断的在线监控。

## 6 测量

本节中，我们将使用一些小规模基准测试来展现GFS系统架构和实现上的一些固有瓶颈，还有些来自Google内部使用的真实的GFS集群的基准数据。

### 6.1 小规模基准测试

我们在一个包含1台Master服务器，2台Master服务器复制节点，16台Chunk服务器和16个客户机组成的GFS集群上测量性能。注意，采用这样的集群配置方案只是为了易于测试。典型的GFS集群有数百个Chunk服务器和数百个客户机。

所有机器的配置都一样：两个PIII 1.4GHz处理器，2GB内存，两个80G/5400rpm的硬盘，以及100Mbps全双工以太网连接到一个HP2524交换机。GFS集群中所有的19台服务器都连接在一个交换机，所有16台客户机连接到另一个交换机上。两个交换机之间使用1Gbps的线路连接。

![title](https://leanote.com/api/file/getImage?fileId=5e6b508aab6441424e00285e)

#### 6.1.1 读取

N个客户机从GFS文件系统同步读取数据。每个客户机从320GB的文件集合中随机读取4MB region的内容。读取操作重复执行256次，因此，每个客户机最终都读取1GB的数据。所有的Chunk服务器加起来总共只有32GB的内存，因此，我们预期只有最多10%的读取请求命中Linux的文件系统缓冲。我们的测试结果应该和一个在没有文件系统缓存的情况下读取测试的结果接近。

这个曲线有着95%的可靠性，因为有时候测量会不够精确。图3（a）显示了N个客户机整体的读取速度以及这个速度的理论极限。当连接两个交换机的1Gbps的链路饱和时，整体读取速度达到理论的极限值是125MB/S，或者说每个客户机配置的100Mbps网卡达到饱和时，每个客户机读取速度的理论极限值是12.5MB/s。实测结果是，当一个客户机读取的时候，读取的速度是10MB/s，也就是说达到客户机理论读取速度极限值的80%。对于16个客户机，整体的读取速度达到了94MB/s，大约是理论整体读取速度极限值的75%，也就是说每个客户机的读取速度是6MB/s。读取效率从80%降低到了75%，主要的原因是当读取的客户机增加时，多个客户机同时读取一个Chunk服务器的几率也增加了，导致整体的读取效率下降。

#### 6.1.2 写入

N个客户机同时向N个不同的文件中写入数据。每个客户机以每次1MB的速度连续写入1GB的数据。图3（b）显示了整体的写入速度和它们理论上的极限值。理论上的极限值是67MB/s，因为我们需要把每一byte写入到16个Chunk服务器中的3个上，而每个Chunk服务器的输入连接速度是12.5MB/s。
 
 一个客户机的写入速度是6.3MB，大概是理论极限值的一半。导致这个结果的主要原因是我们的网络协议栈。它与我们推送数据到Chunk服务器时采用的管道模式不相适应。从一个副本到另一个副本的数据传输延迟降低了整个的写入速度。
 
 16个客户机整体的写入速度达到了35MB/s（即每个客户机2.2MB/s），大约只是理论极限值的一半。和多个客户机读取的情形很类型，随着客户机数量的增加，多个客户机同时写入同一个Chunk服务器的几率也增加了。而且，16个客户机并行写入可能引起的冲突比16个客户机并行读取要大得多，因为每个写入都会涉及三个不同的副本。
 
写入的速度比我们想象的要慢。在实际应用中，这没有成为我们的主要问题，因为即使在单个客户机上能够感受到延时，它也不会在有大量客户机的时候对整体的写入带宽造成显著的影响。

#### 6.1.3 记录追加

图3（c）显示了记录追加操作的性能。N个客户机同时追加数据到一个文件。记录追加操作的性能受限于保存文件最后一个Chunk的Chunk服务器的带宽，而与客户机的数量无关。记录追加的速度由一个客户机的6.0MB/s开始，下降到16个客户机的4.8MB/s为止，速度的下降主要是由于不同客户端的网络拥塞以及网络传输速度的不同而导致的。

我们的程序倾向于同时处理多个这样的文件。换句话说，即N个客户机同时追加数据到M个共享文件中，这里N和M都是数十或者数百以上。所以，在我们的实际应用中，Chunk服务器的网络拥塞并没有成为一个严重问题，如果Chunk服务器的某个文件正在写入，客户机会去写另外一个文件。

### 6.2 实际应用中的集群

![title](https://leanote.com/api/file/getImage?fileId=5e6b51aaab6441424e002897)

我们现在来仔细评估一下Google内部正在使用的两个集群，它们具有一定的代表性。集群A通常被上百个工程师用于研究和开发。典型的任务是被人工初始化后连续运行数个小时。它通常读取数MB到数TB的数据，之后进行转化或者分析，最后把结果写回到集群中。集群B主要用于处理当前的生产数据。集群B的任务持续的时间更长，在很少人工干预的情况下，持续的生成和处理数TB的数据集。在这两个案例中，一个单独的”任务”都是指运行在多个机器上的多个进程，它们同时读取和写入多个文件。

#### 6.2.1 存储

如表2前五行所描述的，两个集群都由上百台Chunk服务器组成，支持数TB的硬盘空间；两个集群虽然都存储了大量的数据，但是还有剩余的空间。“已用空间”包含了所有的Chunk副本。实际上所有的文件都复制了三份。因此，集群实际上各存储了18TB和52TB的文件数据。

两个集群存储的文件数量都差不多，但是集群B上有大量的死文件。所谓“死文件”是指文件被删除了或者是被新版本的文件替换了，但是存储空间还没有来得及被回收。由于集群B存储的文件较大，因此它的Chunk数量也比较多。

#### 6.2.2 元数据

Chunk服务器总共保存了十几GB的元数据，大多数是来自用户数据的、64KB大小的块的Checksum。保存在Chunk服务器上其它的元数据是Chunk的版本号信息，我们在4.5节描述过。

在Master服务器上保存的元数据就小的多了，大约只有数十MB，或者说平均每个文件100字节的元数据。这和我们设想的是一样的，Master服务器的内存大小在实际应用中并不会成为GFS系统容量的瓶颈。大多数文件的元数据都是以前缀压缩模式存放的文件名。Master服务器上存放的其它元数据包括了文件的所有者和权限、文件到Chunk的映射关系，以及每一个Chunk的当前版本号。此外，针对每一个Chunk，我们都保存了当前的副本位置以及对它的引用计数，这个引用计数用于实现写时拷贝（：即COW，copy-on-write）。

对于每一个单独的服务器，无论是Chunk服务器还是Master服务器，都只保存了50MB到100MB的元数据。因此，恢复服务器是非常快速的：在服务器响应客户请求之前，只需要花几秒钟时间从磁盘上读取这些数据就可以了。不过，Master服务器会持续颠簸一段时间–通常是30到60秒–直到它完成轮询所有的Chunk服务器，并获取到所有Chunk的位置信息。

#### 6.2.3 读写速率

![title](https://leanote.com/api/file/getImage?fileId=5e6b525bab6441444c00280e)

表三显示了不同时段的读写速率。在测试的时候，这两个集群都运行了一周左右的时间。（这两个集群最近都因为升级新版本的GFS重新启动过了）。

集群重新启动后，平均写入速率小于30MB/s。当我们提取性能数据的时候，集群B正进行大量的写入操作，写入速度达到了100MB/s，并且因为每个Chunk都有三个副本的原因，网络负载达到了300MB/s。

读取速率要比写入速率高的多。正如我们设想的那样，总的工作负载中，读取的比例远远高于写入的比例。两个集群都进行着繁重的读取操作。特别是，集群A在一周时间内都维持了580MB/s的读取速度。集群A的网络配置可以支持750MB/s的速度，显然，它有效的利用了资源。集群B支持的峰值读取速度是1300MB/s，但是它的应用只用到了380MB/s。

#### 6.2.4 Master服务器的负载

表3的数据显示了发送到Master服务器的操作请求大概是每秒钟200到500个。Master服务器可以轻松的应付这个请求速度，所以Master服务器的处理能力不是系统的瓶颈。

在早期版本的GFS中，Master服务器偶尔会成为瓶颈。它大多数时间里都在顺序扫描某个很大的目录（包含数万个文件）去查找某个特定的文件。因此我们修改了Master服务器的数据结构，通过对名字空间进行二分查找来提高效率。现在Master服务器可以轻松的每秒钟进行数千次文件访问。如果有需要的话，我们可以通过在名称空间数据结构之前设置名称查询缓冲的方式进一步提高速度。

#### 6.2.5 恢复时间

当某个Chunk服务器失效了，一些Chunk副本的数量可能会低于复制因子指定的数量，我们必须通过克隆副本使Chunk副本数量达到复制因子指定的数量。恢复所有Chunk副本所花费的时间取决于资源的数量。在我们的试验中，我们把集群B上的一个Chunk服务器Kill掉。这个Chunk服务器上大约有15000个Chunk，共计600GB的数据。为了减小克隆操作对正在运行的应用程序的影响，以及为GFS调度决策提供修正空间，我们缺省的把集群中并发克隆操作的数量设置为91个（Chunk服务器的数量的40%），每个克隆操作最多允许使用的带宽是6.25MB/s（50mbps）。所有的Chunk在23.2分钟内恢复了，复制的速度高达440MB/s。

在另外一个测试中，我们Kill掉了两个Chunk服务器，每个Chunk服务器大约有16000个Chunk，共计660GB的数据。这两个故障导致了266个Chunk只有单个副本。这266个Chunk被GFS优先调度进行复制，在2分钟内恢复到至少有两个副本；现在集群被带入到另外一个状态，在这个状态下，系统可以容忍另外一个Chunk服务器失效而不丢失数据。

### 6.3 工作负荷分析

本节中，我们展示了对两个GFS集群工作负载情况的详细分析，这两个集群和6.2节中的类似，但是不完全相同。集群X用于研究和开发，集群Y用于生产数据处理。

#### 6.3.1 方法论和注意事项

本章节列出的这些结果数据只包括客户机发起的原始请求，因此，这些结果能够反映我们的应用程序对GFS文件系统产生的全部工作负载。它们不包含那些为了实现客户端请求而在服务器间交互的请求，也不包含GFS内部的后台活动相关的请求，比如前向转发的写操作，或者重新负载均衡等操作。

我们从GFS服务器记录的真实的RPC请求日志中推导重建出关于IO操作的统计信息。例如，GFS客户程序可能会把一个读操作分成几个RPC请求来提高并行度，我们可以通过这些RPC请求推导出原始的读操作。因为我们的访问模式是高度程式化，所以我们认为任何不符合的数据都是误差。应用程序如果能够记录更详尽的日志，就有可能提供更准确的诊断数据；但是为了这个目的去重新编译和重新启动数千个正在运行的客户机是不现实的，而且从那么多客户机上收集结果也是个繁重的工作。

应该避免从我们的工作负荷数据中过度的归纳出普遍的结论。因为Google完全控制着GFS和使用GFS的应用程序，所以，应用程序都针对GFS做了优化，同时，GFS也是为了这些应用程序而设计的。这样的相互作用也可能存在于一般程序和文件系统中，但是在我们的案例中这样的作用影响可能更显著。

#### 6.3.2 Chunk服务器工作负荷

![title](https://leanote.com/api/file/getImage?fileId=5e6b5593ab6441444c0028cf)

表4显示了操作按涉及的数据量大小的分布情况。读取操作按操作涉及的数据量大小呈现了双峰分布。小的读取操作（小于64KB）一般是由查找操作的客户端发起的，目的在于从巨大的文件中查找小块的数据。大的读取操作（大于512KB）一般是从头到尾顺序的读取整个文件。

在集群Y上，有相当数量的读操作没有返回任何的数据。在我们的应用中，尤其是在生产系统中，经常使用文件作为生产者-消费者队列。生产者并行的向文件中追加数据，同时，消费者从文件的尾部读取数据。某些情况下，消费者读取的速度超过了生产者写入的速度，这就会导致没有读到任何数据的情况。集群X通常用于短暂的数据分析任务，而不是长时间运行的分布式应用，因此，集群X很少出现这种情况。

写操作按数据量大小也同样呈现为双峰分布。大的写操作（超过256KB）通常是由于Writer使用了缓存机制导致的。Writer缓存较小的数据，通过频繁的Checkpoint或者同步操作，或者只是简单的统计小的写入（小于64KB）的数据量。

再来观察一下记录追加操作。我们可以看到集群Y中大的记录追加操作所占比例比集群X多的多，这是因为集群Y用于我们的生产系统，针对GFS做了更全面的调优。

![title](https://leanote.com/api/file/getImage?fileId=5e6b55fbab6441424e002977)

表5显示了按操作涉及的数据量的大小统计出来的总数据传输量。在所有的操作中，大的操作（超过256KB）占据了主要的传输量。小的读取（小于64KB）虽然传输的数据量比较少，但是在读取的数据量中仍占了相当的比例，这是因为在文件中随机Seek的工作负荷而导致的。

#### 6.3.3 记录追加 vs. 写操作

记录追加操作在我们的生产系统中大量使用。对于集群X，记录追加操作和普通写操作的比例按照字节比是108:1，按照操作次数比是8:1。对于作为我们的生产系统的集群Y来说，这两个比例分别是3.7:1和2.5:1。更进一步，这一组数据说明在我们的两个集群上，记录追加操作所占比例都要比写操作要大。对于集群X，在整个测量过程中，记录追加操作所占比率都比较低，因此结果会受到一两个使用某些特定大小的buffer的应用程序的影响。

如同我们所预期的，我们的数据修改操作主要是记录追加操作而不是覆盖方式的写操作。我们测量了第一个副本的数据覆盖写的情况。这近似于一个客户机故意覆盖刚刚写入的数据，而不是增加新的数据。对于集群X，覆盖写操作在写操作所占据字节上的比例小于0.0001%，在所占据操作数量上的比例小于0.0003%。对于集群Y，这两个比率都是0.05%。虽然这只是某一片断的情况，但是仍然高于我们的预期。这是由于这些覆盖写的操作，大部分是由于客户端在发生错误或者超时以后重试的情况。这在本质上应该不算作工作负荷的一部分，而是重试机制产生的结果。

#### 6.3.4 Master的工作负荷

![title](https://leanote.com/api/file/getImage?fileId=5e6b5653ab6441424e002987)

表6显示了Master服务器上的请求按类型区分的明细表。大部分的请求都是读取操作查询Chunk位置信息（FindLocation）、以及修改操作查询lease持有者的信息（FindLease-Locker）。

集群X和Y在删除请求的数量上有着明显的不同，因为集群Y存储了生产数据，一般会重新生成数据以及用新版本的数据替换旧有的数据。数量上的差异也被隐藏在了Open请求中，因为旧版本的文件可能在以重新写入的模式打开时，隐式的被删除了（类似UNIX的open函数中的“w”模式）。

FindMatchingFiles是一个模式匹配请求，支持“ls”以及其它类似的文件系统操作。不同于Master服务器的其它请求，它可能会检索namespace的大部分内容，因此是非常昂贵的操作。集群Y的这类请求要多一些，因为自动化数据处理的任务进程需要检查文件系统的各个部分，以便从全局上了解应用程序的状态。与之不同的是，集群X的应用程序更加倾向于由单独的用户控制，通常预先知道自己所需要使用的全部文件的名称。

## 7 经验

在建造和部署GFS的过程中，我们经历了各种各样的问题，有些是操作上的，有些是技术上的。

起初，GFS被设想为我们的生产系统的后端文件系统。随着时间推移，在GFS的使用中逐步的增加了对研究和开发任务的支持。我们开始增加一些小的功能，比如权限和配额，到了现在，GFS已经初步支持了这些功能。虽然我们生产系统是严格受控的，但是用户层却不总是这样的。需要更多的基础架构来防止用户间的相互干扰。

我们最大的问题是磁盘以及和Linux相关的问题。很多磁盘都声称它们支持某个范围内的Linux IDE硬盘驱动程序，但是实际应用中反映出来的情况却不是这样，它们只支持最新的驱动。因为协议版本很接近，所以大部分磁盘都可以用，但是偶尔也会有由于协议不匹配，导致驱动和内核对于驱动器的状态判断失误。这会导致数据因为内核中的问题意外的被破坏了。这个问题促使我们使用Checksum来校验数据，同时我们也修改内核来处理这些因为协议不匹配带来的问题。

较早的时候，我们在使用Linux 2.2内核时遇到了些问题，主要是fsync()的效率问题。它的效率与文件的大小而不是文件修改部分的大小有关。这在我们的操作日志文件过大时给出了难题，尤其是在我们尚未实现Checkpoint的时候。我们费了很大的力气用同步写来解决这个问题，但是最后还是移植到了Linux2.4内核上。

另一个和Linux相关的问题是单个读写锁的问题，也就是说，在某一个地址空间的任意一个线程都必须在从磁盘page in（读锁）的时候先hold住，或者在mmap()调用（写锁）的时候改写地址空间。我们发现即使我们的系统负载很轻的情况下也会有偶尔的超时，我们花费了很多的精力去查找资源的瓶颈或者硬件的问题。最后我们终于发现这个单个锁在磁盘线程交换以前映射的数据到磁盘的时候，锁住了当前的网络线程，阻止它把新数据映射到内存。由于我们的性能主要受限于网络接口，而不是内存copy的带宽，因此，我们用pread()替代mmap()，用了一个额外的copy动作来解决这个问题。

尽管偶尔还是有其它的问题，Linux的开放源代码还是使我们能够快速探究和理解系统的行为。在适当的时候，我们会改进内核并且和公开源码组织共享这些改动。

## 8 相关工作

类似于其他如AFS的大型分布式文件系统，GFS提供了一个与位置无关的名字空间，这使得数据可以为了负载均衡或者灾难冗余等目的在不同位置透明的迁移。不同于AFS的是，GFS把文件分布存储到不同的服务器上，这种方式更类似Xfs和Swift，这是为了提高整体性能以及灾难冗余的能力。

由于磁盘相对来说比较便宜，并且复制的方式比RAID方法简单的多，GFS目前只使用复制的方式来进行冗余，因此要比xFS或者Swift占用更多的裸存储空间(alex注：Raw storage，裸盘的空间)。
 
与AFS、xFS、Frangipani以及Intermezzo等文件系统不同的是，GFS并没有在文件系统层面提供任何Cache机制。我们主要的工作在单个应用程序执行的时候几乎不会重复读取数据，因为它们的工作方式要么是流式的读取一个大型的数据集，要么是在大型的数据集中随机Seek到某个位置，之后每次读取少量的数据。
 
某些分布式文件系统，比如Frangipani、xFS、Minnesota’s GFS、GPFS，去掉了中心服务器，只依赖于分布式算法来保证一致性和可管理性。我们选择了中心服务器的方法，目的是为了简化设计，增加可靠性，能够灵活扩展。特别值得一提的是，由于处于中心位置的Master服务器保存有几乎所有的Chunk相关信息，并且控制着Chunk的所有变更，因此，它极大地简化了原本非常复杂的Chunk分配和复制策略的实现方法。我们通过减少Master服务器保存的状态信息的数量，以及将Master服务器的状态复制到其它节点来保证系统的灾难冗余能力。扩展能力和高可用性（对于读取）目前是通过我们的影子Master服务器机制来保证的。对Master服务器状态更改是通过预写日志的方式实现持久化。为此，我们可以调整为使用类似Harp中的primary-copy方案，从而提供比我们现在的方案更严格的一致性保证。
 
我们解决了一个难题，这个难题类似Lustre在如何在有大量客户端时保障系统整体性能遇到的问题。不过，我们通过只关注我们的应用程序的需求，而不是提供一个兼容POSIX的文件系统，从而达到了简化问题的目的。此外，GFS设计预期是使用大量的不可靠节点组建集群，因此，灾难冗余方案是我们设计的核心。
 
GFS很类似NASD架构。NASD架构是基于网络磁盘的，而GFS使用的是普通计算机作为Chunk服务器，就像NASD原形中方案一样。所不同的是，我们的Chunk服务器采用惰性分配固定大小的Chunk的方式，而不是分配变长的对象存储空间。此外，GFS实现了诸如重新负载均衡、复制、恢复机制等等在生产环境中需要的特性。
 
不同于与Minnesota’s GFS和NASD，我们并不改变存储设备的Model(alex注：对这两个文件系统不了解，因为不太明白改变存储设备的Model用来做什么，这不明白这个model是模型、还是型号)。我们只关注用普通的设备来解决非常复杂的分布式系统日常的数据处理。
 
我们通过原子的记录追加操作实现了生产者-消费者队列，这个问题类似River中的分布式队列。River使用的是跨主机的、基于内存的分布式队列，为了实现这个队列，必须仔细控制数据流；而GFS采用可以被生产者并发追加记录的持久化的文件的方式实现。River模式支持m-到-n的分布式队列，但是缺少由持久化存储提供的容错机制，GFS只支持m-到-1的队列。多个消费者可以同时读取一个文件，但是它们输入流的区间必须是对齐的。

## 9 结束语
Google文件系统展示了一个使用普通硬件支持大规模数据处理的系统的特质。虽然一些设计要点都是针对我们的特殊的需要定制的，但是还是有很多特性适用于类似规模的和成本的数据处理任务。
 
首先，我们根据我们当前的和可预期的将来的应用规模和技术环境来评估传统的文件系统的特性。我们的评估结果将我们引导到一个使用完全不同于传统的设计思路上。根据我们的设计思路，我们认为组件失效是常态而不是异常，针对采用追加方式（有可能是并发追加）写入、然后再读取（通常序列化读取）的大文件进行优化，以及扩展标准文件系统接口、放松接口限制来改进整个系统。
 
我们系统通过持续监控，复制关键数据，快速和自动恢复提供灾难冗余。Chunk复制使得我们可以对Chunk服务器的失效进行容错。高频率的组件失效要求系统具备在线修复机制，能够周期性的、透明的修复损坏的数据，也能够第一时间重新建立丢失的副本。此外，我们使用Checksum在磁盘或者IDE子系统级别检测数据损坏，在这样磁盘数量惊人的大系统中，损坏率是相当高的。
 
我们的设计保证了在有大量的并发读写操作时能够提供很高的合计吞吐量。我们通过分离控制流和数据流来实现这个目标，控制流在Master服务器处理，而数据流在Chunk服务器和客户端处理。当一般的操作涉及到Master服务器时，由于GFS选择的Chunk尺寸较大，以及通过Chunk Lease将控制权限移交给主副本，这些措施将Master服务器的负担降到最低。这使得一个简单、中心的Master不会成为成为瓶颈。我们相信我们对网络协议栈的优化可以提升当前对于每客户端的写入吞吐量限制。
 
GFS成功的实现了我们对存储的需求，在Google内部，无论是作为研究和开发的存储平台，还是作为生产系统的数据处理平台，都得到了广泛的应用。它是我们持续创新和处理整个WEB范围内的难题的一个重要工具。

逆风起笔