The Google File System
中文版

摘要

我们设计并实现了Google文件系统，一个面向分布式数据密集型应用的、可伸缩的分布式文件系统。虽然运行在廉价的日用硬件设备上，但是它依然了提供容错功能，为大量客户机提供了很高的总体性能。

虽然与很多之前的分布式文件系统有很多相同目标，但是，我们的设计已经受应用的负载情况和技术环境影响，现在以及可预见的将来都反映出，我们的设计和早期的分布式文件系统的设想有了显著的分离。这让我们重新审视了传统文件系统在设计上的选择，探索彻底不同的设计点。

GFS成功满足了我们的存储需求。其作为存储平台被广泛的部署在Google内部，该平台用来产生和处理数据，这些数据被我们的服务以及需要大规模数据集的研究和开发工作使用。迄今为止，最大的一个集群利用一千多台机器上的数千个硬盘，提供数百TB的存储空间，同时被数百个客户机访问。

在本论文中，我们展示了设计用来支持分布式应用的文件系统接口的扩展，讨论我们设计的许多方面，最后对小规模基准测试和真实使用作了测量报告。

常用术语

设计，可靠性，性能，测量

关键词

容错，可伸缩性，数据存储，集群存储

1.    
简介

为了满足Google迅速增长的数据处理需求，我们设计并实现了Google文件系统(Google File System–GFS)。GFS与之前的分布式文件系统有着很多相同的目标，比如，性能、扩展性、可靠性以及可用性。但是，我们的设计还受对我们的应用的负载和技术环境的观察的影响，现在以及可预见的将来都反映出，我们的设计和早期的分布式文件系统的设想有了显著的分离。这让我们重新审视了传统文件系统在设计上的选择，在设计上探索了彻底不同的设计点。

首先，组件失效被认为是常态事件，而不是意外事件。文件系统由几百乃至数千台由廉价的日常部件组装成的存储机器组成，同时被相当数量的客户机访问。部件的数量和质量事实保证了任意给定时间，一些部件无法工作，一些部件无法从它们目前的失效状态中恢复。我们遇到过如下原因导致的问题，比如应用程序bug、操作系统的bug、人为失误，甚至还有硬盘、内存、连接器、网络以及电源失效。因此，持久的监控、错误侦测、容错以及自动恢复必须集成在系统中。

其次，以传统的标准衡量，我们的文件非常巨大。数GB的文件非常普遍。每个文件通常包含许多应用程序对象，比如web文档。当我们定期由数亿个对象构成的快速增长的数TB的数据集时，即使文件系统支持，管理数十亿KB大小的小文件也是不实用的。因此，设计的假设条件和参数，比如I/O
操作和Block的尺寸都不得不重新考虑。

第三，绝大部分文件的变更是采用在追加新数据，而不是重写原有数据的方式。文件内部的随机写在实际中几乎不存在。一旦写完之后，文件只能读，而且通常只能顺序读。各种数据符合这些特性，比如：一些可能组成了数据分析程序扫描的超大数据集；一些可能是正在运行的应用程序生成的连续数据流；一些可能是档案数据；一些可能是由一台机器生成、另外一台机器处理的中间数据，同时处理或者稍后适时处理。考虑到这种针对海量文件的访问模式，数据的追加是性能优化和原子性保证的焦点所在，客户端对数据块缓存毫无吸引力。

第四，通过增加灵活性，应用程序和文件系统API的协同设计对整个系统有益。比如，我们放松了对GFS一致性模型的要求，不用在应用程序中强加繁重负担，大大简化了文件系统。我们甚至引入了原子性的追加操作，这样多个客户端可以对一个文件同时进行追加操作，不需要他俩之间额外的同步机制。这些问题会在下文进行详细讨论。

当前针对不同目的部署了多重GFS集群。最大的一个集群拥有超过1000个存储节点，超过300TB的硬盘存储，被不同机器上的数百个客户端连续不断的频繁访问。

2.设计概述

2.1 假设

在设计满足我们需求的文件系统时候，我们被这种现实指引着：我们的假设既有机遇、又有挑战。我们之前提到一些关键关注点，现在更详细地展示我们的假设。

系统由许多廉价的日用组件组成，组件失效是一种常态。系统必须持续监控自身状态，探测，处理容错并且迅速地恢复失效的组件。

系统存储一定数量的大文件。我们预期会有几百万个文件，文件的大小通常在100MB或者以上。数个GB大小的文件也是普遍存在，并且应该被被有效的管理。系统也必须支持小文件，但是不需要针对小文件做优化。

系统的工作负载主要由两种读操作组成：大规模的流式读取和小规模的随机读取。大规模的流式读取中，单次操作通常读取数百KB的数据，更常见的是一次读取1MB甚至更多的数据。来自同一个客户机的连续操作通常是读取一个文件中一个连续区域。小规模的随机读取通常是在任意位移上读取几个KB数据。对性能敏感的应用程序通常把小规模的随机读取分批处理并排序，如此在文件中稳固前进而不是往复来去。

系统的工作负载还包括许多大规模的、顺序的、对文件追加数据的写操作。通常操作的大小和读操作类似。数据一旦被写入后，文件很少被再次变更。系统支持在文件任意位置写入的小型操作，但是这种操作不必高效。

系统必须高效的、定义明确的（alex注：well-defined）实现多客户端并行追加数据到同一个文件里的语意。我们的文件通常作为“生产者-消费者”队列，或者为多路合并使用。数百个生产者，每台机器上运行一个，并发地对一个文件进行追加。最小同步开销原子性是必要的。文件可以在稍后读取，或者是消费者在追加同时读取文件。

高可持续的网络带宽比低延迟更重要。我们的大多数目标程序很看重高速率大批量地处理数据，极少有程序对单一的读写操作有严格的响应时间要求。

2.2 接口

GFS 提供了一套常见的文件系统接口，尽管它没有实现像POSIX的一套标准API。文件以目录的形式分层组织，用路径名标识。我们支持常用的操作，如创建、删除、打开、关闭、读写文件。

另外，GFS
有快照和记录追加操作。快照以很低的成本创建一个文件或者目录树的拷贝。记录追加操作允许多个客户端同时对一个文件进行追加，同时保证每个单一客户端追加的原子性。多个客户端可以在不需要额外锁的情况下，同时追加数据，这对于实现多路结果合并，以及”生产者-消费者”队列非常有用。我们发现这些类型的文件对于构建大型分布应用是非常重要的。快照和记录追加操作将在3.4和3.3节分别作进一步讨论。

2.3 架构

一个GFS
集群包含一个单独的master（alex注：这里的一个单独的master节点的含义是GFS系统中只存在一个逻辑上的master组件。后面我们还会提到master节点复制，因此，为了理解方便，我们把master节点视为一个逻辑上的概念，一个逻辑的master节点包括两台物理主机，即两台master服务器）和多台chunkserver，并且被多个客户端访问，如图1
所示。其中的每台机器通常都是运行着用户级别(user-level)的服务器进程的日常Linux机器。我们可以很容易地把chunk服务器和客户端都运行在同一台机器上，前提是机器资源允许，并且运行古怪应用程序代码而引起的不可靠性是可以接受的。

文件都被分割成固定大小的块。在创建块的时候，master会对每个块分配一个不可变的、全球唯一的64位的块句柄来进行标识。Chunkserver将块作为linux
文件保存在本地硬盘上，并且根据指定的块句柄和字节范围来读写块数据。为了可靠，每个块都会复制到多个chunkserver上。缺省情况下，我们存储三个副本，不过用户可以为不同的文件命名空间区域指定不同的复制级别。

Master维护所有的文件系统元数据。这些元数据包括命名空间、访问控制信息、文件到块的映射信息、以及当前块的位置。Master节点还控制着系统范围内的活动，比如，块租用管理(alex注：BDB也有关于lease的描述，不知道是否相同)
、孤立块的垃圾回收、以及块在Chunkserver间的迁移。Master用心跳信息周期地和每个Chunkserver通讯，向Chunkserver发送指令并收集其状态。

链接到每个应用程序里的GFS客户端代码实现了文件系统API，代表应用程序与master和Chunkserver通讯以及读写数据。客户端和master交互元数据操作，但是所有承载数据的通信都是直接和Chunkserver进行的。我们不提供POSIX标准的API，因此不需要在Linux
vnode层建立钩子程序。

无论是客户端还是Chunkserver都不需要缓存文件数据。客户端缓存收效甚微，因为大多数程序要么流式处理一个巨大文件，要么工作集太大根本无法缓存。通过消除缓存相关的问题简化了客户端和整个系统。（然而，客户端会缓存元数据。）Chunkserver不需要缓存文件数据的原因是，数据块以本地文件的方式保存，Linux
缓冲区已经把经常访问的数据缓存在了内存中。

2.4 单一Master节点

单一的master节点极大地简化了我们的设计。并且使master可以使用全局信息(knowledge)进行复杂的块部署和副本决策。然而，我们必须使其与读写的相关性降到最小，以避免其成为瓶颈。客户端绝不通过master读写文件数据。相反，客户端询问master它应该联系哪一个Chunkserver。客户端将这些信息缓存有限的时间，后续的操作直接和Chunkserver进行交互。

我们参考图1解释一次简单读取交互。首先，客户端使用固定的块大小将应用程序指定的文件名和字节偏移转换成文件中的块索引。然后，它将包含文件名和块索引的请求发给master。Master回复相应的块句柄和副本位置信息。客户端使用文件名和Chunk索引作为键缓存这些信息。

之后客户端发送请求到其中的一个副本处，一般是最近的。请求信息指定了Chunk句柄和块内字节范围。对同一个块的进一步读取不再需要客户端和master的交互了，知道缓存信息过期或者文件被重新打开。实际上，客户端通常会在一次请求中请求多个块，master也可能立刻包含了那些请求之后的块信息。这些额外的信息在实际上没有任何额外代价的情况下，回避了客户端和master未来一些可能的交互。

2.5 Chunk尺寸

块的大小是关键的设计参数之一。我们选择了64MB，这个尺寸远远大于通常文件系统的块大小。每个块副本都以普通Linux文件的形式保存在Chunkserver上，只有在需要的时候才扩大。惰性空间分配策略避免了由于内部碎片导致的空间浪费，也许这是对这么大的块尺寸最有争议的地方。

大尺寸块有几个重要的优势。首先，它减少了客户端和master交互的需求，因为对同一块的读写只需要一次和mater的初始请求来获取块的位置信息。这种缩减我们的工作负载至关重要，因为应用程序大都是连续读写大文件。即使是小规模的随机读取，客户端可以轻松地为一个数TB的工作集缓存所有的块位置信息。其次，因为采用较大块，客户端很可能对一个块执行多次操作，这样可以通过与Chunkserver在很长的时间内保持持久的TCP
连接来减少网络负载。再者，它减少了在master上保存的元数据的大小。这就允许我们把元数据保存在内存中，这也带来了其它优势，我们将在在2.6.1节进行讨论。

另一方面，即使配合惰性空间分配，大尺寸块也有其缺点。小文件包含少量的块，甚至只有一个块。如果许多客户端访问同一个小文件，存储这些块的Chunkserver就会变成热点。在实际中，由于我们的程序通常是连续的读取包含多个块的大文件，热点还不是主要问题。

然而，当GFS第一次被批处理队列系统使用的时候，热点问题还是显露了：一个可执行文件作为一个单块文件写在了GFS上，之后同时在数百台机器上启动。存放这个可执行文件的几个Chunkserver被数百个并发请求造成过载。我们通过使用更大的复制因子来保存这样的可执行文件，并且让批处理队列系统错开程序的启动时间的方法解决了这个问题。一个可能的长效解决方案是，在这种的情况下允许客户端从其它客户端读取数据（p2p?）。

2.6 元数据

Master（alex注：注意逻辑的master节点和物理的master服务器的区别。后续我们谈的是每个master服务器的行为，如存储、内存等等，因此我们将全部使用物理名称）存储3种主要类型的元数据：文件和块的命名空间、文件到块k的映射、每个块副本的位置。所有的元数据都保存在master的内存中。前两种类型（命名空间、文件到块的映射）同时也会通过记录变更到操作日志的方式持久存储，该日志存储在master的本地磁盘上，并且在远程机器上备份。使用日志使我们能够简单可靠地更新master的状态，并且不用冒着万一master崩溃数据不一致的风险。Master不会持久存储块位置信息。相反，Master会在启动，或者有新的Chunkserver加入集群时，向各个Chunkserver询问它们的块信息。

2.6.1 内存中的数据结构

因为元数据保存在内存中，master的操作非常快。并且，Master在后台周期性扫描自己的整个状态简单高效。这种周期性的扫描用于实现块垃圾收集、在Chunkserver失效时重新备份、通过块迁移来均衡跨Chunkserver的负载及磁盘使用状况。4.3和4.4章节将进一步讨论这些行为。

对于这种memory-only式的方法的一个潜在担心在于：块的数量亦即整个系统的容量受限于master所拥有的内存大小。这在实际应用中并不是一个严重的限制。Master为每个64M数据块维护少于64个字节的元数据就。由于大多数文件包含多个块，因此大多数块是满的，除了最后一个块是部分填充的。同样，每个文件需要的文件命名空间数据通常少于64字节，因为它使用前缀压缩紧密地存储文件名字。

如果有必要支持更大的文件系统，相比于通过在内存中存储元数据而获得的简洁性、可靠性、高性能和灵活性而言，为master增加额外内存的费用也是很少的。

2.6.2 Chunk
位置信息

Master不保存哪个Chunkserver拥有指定块的副本的持久化记录。Master只是在启动的时候轮询Chunkserver以获取那些信息。Master可以保持自己是最新的（thereafter），因为它控制了所有的块的部署，而且通过定期心跳信息监控Chunkserver的状态。

我们最初试图把块的位置信息持久地保存在master上，但是我们认定在启动的时候从Chunkserver请求数据，之后定期轮询更简单。这样消除了在Chunkserver加入、离开集群、更名、失效、以及重启等情况发生的时候，保持master和Chunkserver同步的问题。在一个拥有数百台服务器的集群中，这类事件会频繁的发生。

理解这个设计决策的另外一种方式就是认识到：对于块是否在它的硬盘上，Chunkserver才说了算。试图在master上维护一个这些信息的一致视图是毫无意义的，因为Chunkserver上的错误可能会导致块不由自主地消失(比如，硬盘可能损坏不能用了)，或者操作人员可能会重命名一个Chunkserver。

2.6.3 操作日志

操作日志包含了关键的元数据变更历史记录。这对GFS
非常重要。不仅是因为它是元数据的唯一持久化记录，它也作为定义同步操作顺序的逻辑时间基线（alex注：也就是通过逻辑日志的序号作为操作发生的逻辑时间，类似于事务系统中的LSN）。文件和块，连同它们的版本(参考4.5节)，都由它们创建时的逻辑时间唯一的、永久的标识。

由于操作日志至关重要，我们必须对其可靠地存储，并且只有在元数据的变化被持久化后，这种变化对客户才是可见的。否则，即使块本身没有问题，我们（effectively）有效地丢失整个文件系统或者最近的客户操作。因此，我们会把日志复制到多台远程机器，并且只有把相应的日志记录写入到本地以及远程硬盘之后，才会响应客户端的操作请求。Master会在写入之前将一些日志记录分批处理，从而减少写入和备份对整体系统吞吐量的影响。

Master通过重演操作日志恢复它的文件系统状态。为了缩短启动时间，我们必须保持日志很小（alex注：即重演系统操作的日志量尽量的少）。每当日志增长到超过一定大小的时候master对系统状态做一次检查点，(shijin：Checkpoint是一种行为，一种对数据库状态作一次快照的行为，将所有的状态数据写入一个Checkpoint文件，并删除之前的日志文件)如此一来，通过从本地磁盘加载最新检查点，然后仅仅重演检查点之后有限数目日志记录的方式，master即可恢复系统。检查点是一个紧密的类B-树格式，该格式可以直接映射到内存，可以在无需额外解析的情况下用于命名空间查询。这进一步提高了恢复速度，增强了可用性。

由于创建一个检查点需要一定的时间，所以master的内部状态被组织为这样的形式，这种形式可以在不阻塞后续变更操作的同时创建新的检查点。Master在一个独立的线程切换到新的日志文件并创建新的检查点。新的检查点包含切换前所有的变更。为一个有数百万文件的集群创建一个检查点大约需要1
分钟的间。创建完成后，检查点被写入本地和远程硬盘中。

Master只需要最新的检查点和后续的日志文件。旧的检查点和日志文件可以被自主删除，但是为了提防灾难性故障（alex注：catastrophes，数据备份相关文档中经常会遇到这个词，表示一种超出预期范围的灾难性事件），我们还是会随手保存一些。创建检查点期间的失败不会影响正确性，因为恢复代码检测并跳过没完成的检查点。

2.7 一致性模型

GFS有一个宽松的一致性模型，这个模型很好地支撑我们的高度分布的应用，但是却依然相当简单且可以高效实现。现在我们讨论GFS的一致性保障及其对应用程序的意义。我们也强调了GFS
如何维护这些保障，但是实现的细节将在本论文的其它部分讨论。

2.7.1 GFS一致性保障机制

文件命名空间的变更（例如，文件创建）是原子性的。它们只能由master控制：命名空间锁保证了原子性和正确性（4.1节）；master的操作日志定义了这些操作的一个全局完整的顺序（2.6.3节）。

数据变更后一个文件域（alex注：region这个词用中文非常难以表达，我认为应该是变更操作所涉及的文件中的某个范围）的状态取决于操作的类型、成功与否、以及是否有同步变更。表1
汇总了结果。如果所有客户端，无论从哪个副本读取，总是看到相同的数据，那么我们认为文件域是“一致的”；在一个文件数据变更以后，如果文件域是一致的，并且客户端能够看到变更写入的完整内容，那么这个域是“已定义的”。当一个数据变更操作成功执行，没有受到同步写操作的干扰，那么受影响的域就是已定义的（暗含了一致性）：所有的客户端总是可以看到变更写入的内容。并发变更操作成功完成之后，域处于一致的、未定义的状态：所有的客户端看到同样的数据，但是它无法反映任何一次变更写入写入的数据。通常情况下，文件域包含了来自多个变更的、混杂的数据片段。失败的变更操作导致这个域不一致（因此也是未定义的）：不同的客户可能在不同的时间会看到不同的数据。下面我们描述了我们的应用程序如何区分已定义和未定义的域。应用程序没必要进一步区分未定义域的不同类型。

数据变更可能是写入或者记录追加。写入操作把数据写在应用程序指定的文件偏移位置上。即使在并发变更面前，记录追加操作至少把数据（记录）原子性的追加一次，但是是在GFS
选择的偏移上（3.3节）（alex注：这句话有点费解，其含义是所有的追加写入都会成功，但是有可能被执行了多次，而且每次追加的文件偏移量由GFS自己计算）。（相比而言，通常的追加不过在这样一个偏移位置写，客户认为偏移位置是文件的当前的尾部。）GFS返回给客户端一个偏移量，该偏移量标明了包含了记录的、已定义的域的起点。另外，GFS
可能会在中间插入填充数据或者重复记录。它们占据被认定为不一致的域，并且这些数据和用户数据相比通常很小。

经过了一系列的成功的变更操作之后，GFS保证被变更的文件域是已定义的，并且包含最后一次变更操作写入的数据。GFS
通过以下措施达成目的：（a） 
对块的所有副本应用相同顺序的变更（3.1节），（b）使用块版本号来探测过期的副本，过期的副本是由于它所在的Chunkserver宕机（4.5章）期间错过了变更而引起的。过期的副本不会涉及变更，也不会返回给向master请求块位置信息的客户端。它们优先被垃圾收集。

由于客户端缓存块位置信息，所以在信息刷新前，客户端有可能从一个失效的副本读取了数据。这个时间窗口受限于缓存条目的超时时间和文件文件下一次被打开的时间，文件的再次打开会从缓存中清除该文件的块信息。并且，鉴于我们的大多数文件都是只进行追加操作，一个失效的副本通常返回一个提前结束的块而不是过期的数据。当一个Reader（alex注：本文中将用到两个专有名词，Reader和Writer，分别表示执行GFS读取和写入操作的程序）重新尝试并联络master时，它就会立刻得到当前的块位置信息。

变更操作成功执行很长时间之后，组件的失效仍然可以损坏或者销毁数据。GFS通过master和所有Chunkserver定期“握手”的方式来识别失效的Chunkserver，并且通过检查检验和来校验数据是否损坏（5.2节）。一旦问题浮出水面，数据要从效副本快速恢复（4.3节）。只有块的所有副本在GFS作出反应前全部丢失，该块才会不可逆转的丢失。GFS的反应时间（alex注：指master节点检测到错误并采取应对措施）通常是几分钟。即使在这种情况下，块变得不可用了，而不是损坏了：应用程序会收到清晰的错误信息而不是损坏的数据。

2.7.2 程序的实现

GFS 应用程序可以利用一些简单技术适应这个宽松的一致性模型，这些技术已经满足了其他目的的需要：依赖追加而不是重写，检查点，自验证，自标识的记录。

实际中，我们所有的应用通过追加而不是重写的方式变更文件。一种典型的应用中，写入程序从头到尾地生成一个文件。写完所有数据之后，程序原子性地将文件重命名为一个永久的文件名，或者定期地对成功写入了多少数据设置检查点。检查点也可以包含程序级别的检验和。Readers仅校验并处理上一个检查点之后的文件域，也就是人们知道的已定义状态。不管一致性和并发问题的话，该方法对我们很适合。追加比随机写更有效率，对程序失败有更弹性。检查点允许Writer递增地重启，并且防止Reader成功处理从应用程序的角度看来并未完成的写入的文件数据。

在另一种典型应用中。许多Writer为了合并结果或者作为生产者-消费者队列并发地向一个文件追加数据。记录追加的“至少追加一次”的语义维持了每个Writer的输出。Reader使用下面的方法来处理偶然的填充和重复。Writer准备的每条记录中都包含了类似检验和的额外信息，以便用来验证它的有效性。Reader可以用检验和识别和丢弃额外的填充数据和记录片段。如果偶尔的重复内容是不能容忍的(比如，如果这些重复数据将要触发非幂等操作)，可以用记录的唯一标识来过滤它们，这些标识符也通常用于命名相应程序实体，例如web文档。这些记录I/O功能（除了剔除重复数据）都包含在我们程序共享的代码库（library
code）中，并且适用于Google内部其它的文件接口实现。这样，记录的相同序列，加上些许重复数据，总是被分发到记录Reader中。

3. 系统交互

我们设计这个系统力图最小化master与所有操作的牵连。在这样的背景下，我们现在描述客户机、master和Chunkserver如何交互以实现数据变更、原子记录追加以及快照功能。

3.1 租约（lease）和变更顺序

变更是改变块内容或者块元数据的操作，比如写操作或者追加操作。每次变更在块所有的副本上执行。我们使用租约（lease）来维护副本间的一致性变更顺序。Master向其中一个副本授权一个块租约，我们把这个副本叫做主副本。主副本为对块的所有变更选择一个序列。应用变更的时候所有副本都遵照这个顺序。这样，全局变更顺序首先由master选择的租约授权顺序规定，然后在租约内部由主副本分配的序列号规定。

设计租约机制的目的是为了最小化master的管理开销。租约的初始过期时间为60秒。然而，只要块正在变更，主副本就可以请求并且通常会得到master无限期的延长。这些延长请求和批准信息附在master和所有Chunkserver之间的定期交换的心跳消息中。Master有时可能试图在到期前取消租约（例如，当master想令一个在一个重命名的文件上进行的修改失效）。即使master和主副本失去联系，它仍然可以安全地在旧的租约到期后和向另外一个副本授权新的租约。

 在图2
中，我们根据写操作的控制流程通过这些标号步骤图示说明了这一过程。

1．客户机询问master哪一个Chunkserver持有该块当前的租约，以及其它副本的位置。如果没有chunkserver持有租约，master将租约授权给它选择的副本（没有展示）。

2．master将主副本的标识符以及其它副本（次级副本）的位置返回给客户机。客户机为将来的变更缓存这些数据。只有在主副本不可达，或者其回应它已不再持有租约的时候，客户机才需要再一次联系master。

3．客户机将数据推送到所有副本。客户机可以以任意的顺序推送数据。Chunkserver将数据存储在内部LRU
缓存中，直到数据被使用或者过期。通过将数据流和控制流解耦，我们可以基于网络拓扑而不管哪个Chunksever上有主副本，通过调度昂贵的数据流来提高系统性能。3.2章节会作进一步讨论。

4．当所有的副本都确认接收到了数据，客户机对主副本发送写请求。这个请求标识了早前推送到所有副本的数据。主副本为接收到的所有变更分配连续的序列号，由于变更可能来自多个客户机，这就提供了必要的序列化。它以序列号的顺序把变更应用到它自己的本地状态中（alex注：也就是在本地执行这些操作，这句话按字面翻译有点费解，也许应该翻译为“它顺序执行这些操作，并更新自己的状态”）。

5．主副本将写请求转发(forward)到所有的次级副本。每个次级副本依照主副本分配的序列顺序应用变更

6．所有次级副本回复主副本并标明它们已经完成了操作。

7．主副本回复客户机。任何副本遇到的任何错误都报告给客户机。出错的情况下，写操作可能在主副本和次级副本的任意子集上执行成功。（如果在主副本失败，就不会分配序列号和转发。）客户端请求被认定为失败，被修改的域处于不一致的状态。我们的客户机代码通过重试失败的变更来处理这样的错误。在退到从头开始重试之前，客户机会将从步骤（3）到步骤（7）做几次尝试。

如果应用程序一次的写入量很大，或者跨越了多个块的范围，GFS客户端代码把它分成多个写操作。它们都遵照上面描述的控制流程，但是可能会被来自其它客户机的并发操作造成交错或者重写。因此，共享文件域可能以包含来自不同客户机的片段结尾，尽管如此，由于这些单个的操作在所有的副本上都以相同的顺序完成，副本仍然会是完全相同的。这使文件域处于2.7节提出的一致但是未定义的状态。

3.2 数据流

为了有效地利用网络，我们将数据流从控制流中解耦。在控制流从客户机到主副本再到所有次级级副本的同时，数据以管道的方式，线性地的沿着一个精心挑选的Chunkserver链推送。我们的目标是充分使用每台机器的网络带宽，避免网络瓶颈和高延时的连接，最小化推送所有数据的延时。

为了充分使用每台机器的带宽，数据线性地沿着一个Chunkserver链推送，而不是其它拓扑分布（例如，树）。这样，每台机器所有出口带宽都用于尽快地传输数据，而不是在多个接受者之间分配带宽。

为了尽可能地避免网络瓶颈和高延迟的链接（比如，交换机之间的链路inter-switch经常既是瓶颈又高延迟），每台机器将数据转发到网络拓扑中离自己最近而又没收到数据的机器。假设客户机把数据推送到Chunkserver S1到S4。它把数据推送到最近的Chunkserver，比如说S1。S1将数转转发到从S2到S4中离S1最近的Chunkserver，比如说S2，同样的，S2转发数据到S3或者S4中离S2更近的那个，诸如此类。我们的网络拓扑足够简单，以至于从IP
地址就可以精确地估计“距离”。

最后，我们通过基于TCP连接的管道传输数据方式来最小化延迟。一旦Chunkserver接收到数据，它马立即开始转发。管道方式对我们帮助特别大，因为我们采用全双工连接的交换网络。立即发送数据不会降低接收速度。在没有网络拥塞的情况下，传输B字节数据到R个副本的理想经过时间是B/T+RL，其中T是网络的吞吐量，L是在两台机器间数据传输的延迟。我们的网络连接通常是100Mbps（T），L将远小于1ms。因此，1MB的数据在理想情况下80ms左右就分发出去。

3.3 原子的记录追加

GFS提供了一种叫做记录追加的原子追加操作。传统的写操作中，客户程序指定写入数据的偏移量。对同一个域的并行写不是串行的：域可能以包含来自多个客户机的数据片段结尾。在记录追加中，然而，客户机只需指定数据。GFS将其原子地追加到文件中至少一次（例如，作为一个连续的byte序列），数据追加到GFS选择的偏移位置，然后将这个偏移量返回给给客户机。这类似于在Unix中，对以O_APPEND模式打开的文件，多个并发写操作在没有竞态条件时对文件的写入。

记录追加在我们的分布应用中经常使用，其中很多在不同机器上的客户程序并发对同一文件追加。如果我们采用传统写方式处理，客户机将需要额外的复杂、昂贵的同步机制，例如通过一个分布式锁管理器。在我们的工作中，这样的文件通常用于多生产者/单消费者队列，或者是合并来自多个客户机的结果。

记录追加是一种变更，遵循3.1节的控制流，只主副本有些额外的控制逻辑。客户机把数据推送给文件最后一个块的所有副本，然后向主副本发送请求。主副本会检查如果追加这条记录会不会导致块超过最大尺寸（64MB）。如果超过，将快填充到最大尺寸，通知次级副本做同样的操作，然后回复客户机指出操作应该在下一个块重试。（记录追加限制在至多块最大尺寸的1/4，这样保证最坏情况下数据碎片的数量仍然在可控的范围。）如果记录在最大尺寸以内，这也是通常情况，主副本服务器将数据追加到自己的副本，通知次级副本将数据写在它准确的位移上，最后回复客户机操作成功。

如果记录追加在任何副本上失败，客户端重试操作。结果，同一个块的副本可能包含不同的数据，可能包括一个记录的全部或者部分重复。GFS并不保证所有副本在字节级别完全相同。它只保证数据作为一个原子单元的至少被写入一次。这个特性可以很容易地从简单观察中推断出来：操作如果要报告成功，数据一定已经写入到了一些块的所有副本的相同偏移上。并且，至此以后，所有副本至少都和记录尾部一样长，并且将来的记录会被分配到更高的偏移，或者不同的块，即之后一个不同的副本成为了主副本。就我们的一致性保障而言，记录追加操作成功写入数据的域是已定义的（因此也是一致的），然而中间域则是不一致的（因此也就是未定义的）。我们的程序可以像我们在2.7.2节讨论的那样处理不一致的域。

3.4 快照

(alex注：这一节非常难以理解，总的来说依次讲述了什么是快照、快照使用的COW技术、快照如何不干扰当前操作)

快照操作几乎瞬间完成对一个文件或者目录树（“源”）的拷贝，并且最小化对正在进行的变更的任何干扰。我们的用户使用它快速地创建一个大数据集的分支拷贝（而且经常递归地拷贝拷贝），或者是在做修改实验之前，对当前状态做检查点，这样之后就可以轻松的提交或者回滚。

就像AFS
（alex注：AFS
，即Andrew File System ，一种分布式文件系统），我们使用标准的写时拷贝（copy-on-write）技术实现快照。当master收到快照请求，它首先取消在将要快照的文件中的块的任何未解决的租约。这保证了后续对这些块的写操作都需要与master交互以找到租约持有者。这就给master一个率先创建块拷贝的机会。

租约取消或者过期之后，master把这个操作以日志的方式记录到硬盘。然后，master通过复制源文件或者目录树的元数据的方式，把这条日志记录应用到内存状态。新创建的快照文件和源文件指向相同的块。

在快照操作之后，当客户机初次想写入数据到块C，它向master发送请求查询当前的租约持有者。Master注意到块C的引用计数比1大。Master延迟回复客户机请求，然后改为选择一个新的块句柄C`。之后，master要求每个拥有C当前副本的Chunkserver创建一个叫做C`的新块。通过在作为原件的同一Chunkserver上创建新的块，我们确保数据可以本地拷贝，不是通过网络（我们的硬盘比我们100Mb以太网链接大约快3倍）。从这点来讲，为任何块处理请求没有区别：master为其中一个副本授权新块C`的租约，之后回复客户机，客户机可以正常的写这个块，并不知晓它刚是一个现存的块创建出来。

4. Master节点的操作

Master执行所有的命名空间操作。另外，它管理整个系统里的块副本：它制定部署策略，创建新的块也就是副本，协调各种系统级活动以保证块全面备份，在所有Chunkserver间平衡负载，回收闲置的存储空间。本节我们分别讨论这些主题。

4.1 命名空间管理和锁

许多master操作会花费很长时间：比如，快照操作必须取消被快照覆盖的所有块上的Chunkserver租约。我们不想它们运行的时候耽搁其它master操作。因此，我们允许多个操作活跃，使用名称空间域上的锁来保证正确的串行化。

不同于许多传统文件系统，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
上的冲突锁。文件创建不需要父目录的写锁，因为这里没有“目录”，或者类似内部节点的数据结构需要防止修改。文件名的读锁足以防止父目录被删除。

这种锁机制的一个良好特性是支持对同一目录的并发变更。比如，可以在同一个目录下同时创建多个文件：每个都获得一个目录名的上的读锁和文件名上的写锁。目录名的读取锁足以防止目录被删除、改名以及被快照。文件名的写入锁序列化地尝试用同一个名字两次创建文件。

因为名称空间可以有许多节点，读写锁对象采用惰性分配，一旦不再使用立刻被删除。同样，锁在一个一致性的全局顺序中获取来避免死锁：首先按名称空间树中的层次排序，同层按字典顺序排序。

4.2 副本的部署

GFS集群高度分布在多层，而不是一层。它通常有分布在许多机柜上的数百个Chunkserver。这些Chunkserver反过来被来自同一或者不同机柜上的数百个客户机访问。不同机架上的两台机器间的通讯可能跨越一个或多个网络交换机。另外，出入机柜的带宽可能比机柜内部所有机器的总体带宽要小。多层分布架构对分布式数据的扩展性、可靠性以及可用性提出了特有的挑战。

块副本部署策略满足两大目标：最大化数据可靠性和可用性，最大化网络带宽利用率。为了实现这两个目的，将副本跨机器分布是不够的，这只能防止硬盘或机器失效以及全面使用每台机器的网络带宽。我们必须也跨机柜分布块副本。这保证块的一些副本在即使整个机架被破坏或掉线（比如，因为网络交换机或者电源电路等共享资源的失效）的情况下依然幸存并保持可用。这还意味着在网络流量方面，尤其对于读，对于块可以开发多个机柜的整合带宽。另一方面，写通信量必须流经多个机柜，这是我们自愿的折衷。

4.3 创建，重新备份，重新平衡负载

创建块副本的三个起因：块创建，重新备份和重新平衡负载。

当master创建一个块，它选择在哪里放置初始的空副本。它考虑以下几个因素：（1）我们想将新副本放在低于平均硬盘使用率的Chunkserver上。慢慢地这能平衡Chunkserver间的硬盘使用率。（2）我们想要限制在每个Chunkserver上“最近”创建的次数。虽然创建本身是廉价的，但是确实预示着临近的大量写入通信量，因为当写操作需要的时候才创建块，而在我们的“追加一次，读取多次”的工作模式下，块一旦完全写入通常实际上就变成了只读。（3）如上所述，我们想要把块副本分布在多个