存储入门文章(3)--the google file system

存储入门文章(3)--the google file system

名称：the google file system

出处：SOSP’03, October 19–22, 2003, Bolton Landing, New York, USA.

作者：Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung

单位：google

摘要

我们设计并实现了Google文件系统，一个为数据中心的大规模分布应用设计的可伸缩的分布文件系统。Google文件系统虽然运行在廉价的普遍硬件上，但是可以提供容错能力，为大量客户机提供高性能的服务。

我们的系统与许多以前的分布文件系统拥有许多相同的目标，但我们的设计还受到我们对我们的应用负载和技术环境观察的影响，不管现在还是将来，我们和早期文件系统的假设都有明显的不同。所以我们重新审视了传统的选择，发展了完全不同的设计观点。

Google文件系统成功的满足了我们的存储需求。它作为存储平台被广泛的部署在Google内部，用在我们的服务中产生和处理数据，还用于那些需要大规模数据集的研究和开发。目前为止最大的集群利用数千台机器内的数千个硬盘，提供了数百T的存储空间，同时为数百个客户机服务。

在这篇论文中，我们展现如果用文件系统接口扩展设计去支撑分布应用，讨论我们设计的许多方面，最后报告在小规模性能测试以及真实世界中系统的性能测试结果。

分类和主题描述

D [4]: 3—D分布文件系统

常用术语

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

关键词

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

1. 简介

我们设计并实现了Google文件系统(Google File System - GFS)，用来满足Google迅速增长的数据处理需求。GFS与过去的分布文件系统拥有许多相同的目标，例如性能，可伸缩性，可靠性以及可用性。然而，它的设计还受到我们对我们的应用负载和技术环境观察的影响，不管现在还是将来，我们和早期文件系统的假设都有明显的不同。所以我们重新审视了传统的选择，采取了完全不同的设计观点。

首先，组件失效不再被认为是意外，而是被看做正常的现象。这个文件系统包括几百甚至几千台普通廉价部件构成的存储机器，又被相应数量的客户机访问。组件的数量和质量几乎保证，在任何给定时间，某些组件无法工作，而某些组件无法从他们的目前的失效状态恢复。我们发现过，应用程序bug造成的问题，操作系统bug造成的问题，人为原因造成的问题，甚至硬盘、内存、连接器、网络以及电源失效造成的问题。所以，常量监视器，错误侦测，容错以及自动恢复系统必须集成在系统中。

其次，按照传统的标准来看，我们的文件非常巨大。数G的文件非常寻常。每个文件通常包含许多应用程序对象，比如web文档。传统情况下快速增长的数据集在容量达到数T，对象数达到数亿的时候，即使文件系统支持，处理数据集的方式也就是笨拙地管理数亿KB尺寸的小文件。所以，设计预期和参数，例如I/O操作和块尺寸都要重新考虑。

第三，在Google大部分文件的修改，不是覆盖原有数据，而是在文件尾追加新数据。对文件的随机写是几乎不存在的。一般写入后，文件就只会被读，而且通常是按顺序读。很多种数据都有这些特性。有些数据构成数据仓库供数据分析程序扫描。有些数据是运行的程序连续生成的数据流。有些是存档的数据。有些数据是在一台机器生成，在另外一台机器处理的中间数据。对于这类巨大文件的访问模式，客户端对数据块缓存失去了意义，追加操作成为性能优化和原子性保证的焦点。

第四，应用程序和文件系统API的协同设计提高了整个系统的灵活性。例如，我们放松了对GFS一致性模型的要求，这样不用加重应用程序的负担，就大大的简化了文件系统的设计。我们还引入了原子性的追加操作，这样多个客户端同时进行追加的时候，就不需要额外的同步操作了。论文后面还会对这些问题的细节进行讨论。

为了不同的应用，Google已经部署了许多GFS集群。最大的一个，拥有超过1000个存储节点，超过300T的硬盘空间，被不同机器上的数百个客户端连续不断的频繁访问着。 

2.设计概述 2.1设计预期

在设计我们需要的文件系统时，我们用既有机会又有挑战的设计预期来指导我们的工作。前面我们提到了一些关键的信息，这里我们讲更细节的描述我们的设计预期。

这个系统由许多廉价易损的普通组件组成。它必须持续监视自己的状态，它必须在组件失效作为一种常态的情况下，迅速地侦测、承担并恢复那些组件失效。

这个系统保存一定数量的大文件。我们预期有几百万文件，尺寸通常是100MB或者以上。数GB的文件也很寻常，而且被有效的管理。小文件必须支持，但是不需要去优化。

负载中主要包含两种读操作：大规模的流式读取和小规模随机读取。大规模的流式读取通常一次操作就读取数百K数据，更常见的是一次性读取1MB甚至等多。同一个客户机的连续操作通常是对一个文件的某个区域进行连续读取。小规模的随机读取通常是在随机的位置读取几个KB。对性能有所要求的程序通常把小规模的读批量处理并且排序，这样就不需要对文件进行时前时后的读取，提高了对文件读取的顺序性。

负载中还包括许多大规模的顺序的写操作，追加数据到文件尾部。一般来说这些写操作跟大规模读的尺寸类似。数据一旦被写入，文件就几乎不会被修改了。系统对文件的随机位置写入操作是支持的，但是不必有效率。

系统必须高效的实现良好定义的多客户端并行追加到一个文件的语意。我们的文件经常用于"生产者-消费者"队列，或者多路文件合并。数百个生产者，一个机器一个，同时的对一个文件进行追加。用最小的同步开销实现追加的原子操作是非常重要的。文件可能稍后被读取，也可能一个消费者同步的读取文件。

高度可用的带宽比低延迟更加重要。大多数我们的目标程序，在高传输速率下，大块地操作数据，因为大部分单独的读写操作没有严格的响应时间要求。

2.2 接口

GFS提供了一个类似传统文件系统的接口，虽然它并没有实现类似POSIX的标准API。文件在目录中按照层次组织，用路径名来标识。我们支持常用的操作，如创建，删除，打开，关闭，读和写文件。

而且，GFS有快照和记录追加操作。快照操作可以用很低的成本创建文件或者目录树的拷贝。记录追加操作可以在保证原子性的前提下，允许多个客户端同时在一个文件上追加数据。这对于实现多路结果合并以及"生产者-消费者"模型非常有好处，多个客户端可以同时在一个文件上追加数据，而不需要任何额外的锁定。我们发现这些文件类型对构建大型分布应用是非常有价值的。快照和记录追加将分别在3.4和3.3章节讨论。

2.3 架构

一个GFS集群包含一个主服务器和多个块服务器，被多个客户端访问，如图1。这些机器通常都是普通的Linux机器，运行着一个基于用户层的服务进程。如果机器的资源允许，而且运行多个程序带来的低稳定性是可以接受的话，我们可以很简单的把块服务器和客户端运行在同一台机器。

文件被分割成固定尺寸的块。在每个块创建的时候，服务器分配给它一个不变的、全球唯一的64位的块句柄对它进行标识。块服务器把块作为linux文件保存在本地硬盘上，并根据指定的块句柄和字节范围来读写块数据。为了保证可靠性，每个块都会复制到多个块服务器上。缺省情况下，我们保存三个备份，不过用户可以为不同的文件命名空间设定不同的复制级别。

主服务器管理文件系统所有的元数据。这包括名称空间，访问控制信息，文件到块的映射信息，以及块当前所在的位置。它还管理系统范围的活动，例如块租用管理，孤儿块的垃圾回收，以及块在块服务器间的移动。主服务器用心跳信息周期地跟每个块服务器通讯，给他们以指示并收集他们的状态。

GFS客户端代码被嵌入到每个程序里，它实现了Google文件系统API，帮助应用程序与主服务器和块服务器通讯，对数据进行读写。客户端跟主服务器交互进行元数据操作，但是所有的数据操作的通讯都是直接和块服务器进行的。我们并不提供POSIX API，而且调用不需要深入到Linux的vnode级别。

不管是客户端还是块服务器都不缓存文件数据。客户端缓存几乎没什么好处，因为大部分程序读取巨大文件的全部，或者工作集太大无法被缓存。不进行缓存简化了客户端和整个系统，因为无需考虑缓存相关的问题。（不过，客户端会缓存元数据。）块服务器不需要缓存文件数据的原因是，块保存成本地文件形式，Linux的缓冲器会把经常被访问的数据缓存在内存中。

2.4 单一主服务器

单一的主服务器大大简化了我们的设计，这样主服务器可以通过全局的信息精确确定块的位置以及进行复制决定。然而，我们必须减少主服务器对数据读写的影响，避免使主服务器成为系统的瓶颈。客户端不通过主服务器读写数据。反之，客户端向主服务器询问它应该联系的块服务器。客户端短期缓存这些信息，后续的操作直接跟块服务器进行。

让我们解释下图一表示的一次简单读取的流程。首先，利用固定的块尺寸，客户端把文件名和程序指定的字节偏移转换成文件的块索引。然后，它把文件名和块索引发送给主服务器。主服务器回答相应的块句柄和副本们的位置。客户端用文件名和块索引作为键值缓存这些信息。

然后客户端发送请求到其中的有一个副本处，一般会选择最近的。这个请求指定了块的块句柄和字节范围。对同一块的更多读取不需要客户端和主服务器通讯，除非缓存的信息过期或者文件被重新打开。实际上，客户端通常在一次请求中查询多个块，而主服务器的回应也可以包含紧跟着这些请求块后面的块的信息。这些额外的信息实际上，在没有代价的前提下，避免了客户端和服务器未来的几次通讯。

2.5 块尺寸

块尺寸是关键设计参数之一。我们选择了64MB，这远大于一般文件系统的块尺寸。每个块副本保存在块服务器上的Linux文件内，尺寸只在需要的时候才扩展变大。惰性空间分配避免了造成内部碎片带来的空间浪费，或许对巨大的块尺寸最没有争议的就是这点。

巨大的块尺寸有几个重要的好处。首先，它减少了客户端和主服务器通讯的需求，因为对同一个块的读写，只需要一次用于获得块位置信息的与主服务器的通讯。对我们的工作负载来说，这种减少尤其明显，因为我们的应用程序经常连续读写巨大的文件。即使是对小规模随机读取也有好处，因为客户端也可以轻松的缓存一个数TB工具集的所有块位置。其次，由于块尺寸很大，所以客户端会对一个给定的块进行许多操作，这样就可以通过跟块服务器保持较长时间的TCP连接来减少网络负载。第三，它降低了主服务器需要保存的元数据的尺寸。这就允许我们把元数据放在内存中，这样会带来一些其他的好处，我们将在2.6.1章节讨论。

另一方面，巨大的块尺寸，即使配合惰性空间分配，也有它的缺点。小文件包含较少的块，甚至可能是一块。如果有许多的客户端访问同一个小文件，那么存储这些块的块服务器就会变成热点。在实践中，热点没有成为主要的问题，因为我们的程序通常是连续的读取多个块的大文件。

然而，在GPS第一次用于一个批处理队列系统的时候，热点还是产生了：一个执行文件被写为GFS的一个单块文件，然后在数百个机器上同时启动。保存这个执行文件的几个块服务器被数百个并发请求访问到过载的地步。我们解决了这个问题，方法是用更高的复制参数来保存这类的执行文件，以及让批处理队列系统错开程序的启动时间。一个可能的长期解决方案是，在这样的情况下，允许客户端从其他客户端读取数据。（译者注：这个热点事件，其实就是一个典型的文件分发问题，而后面提到的所谓可能的长期解决方案其实就是p2p。）

2.6 元数据

主服务器保存三种主要类型的元数据：文件和块的命名空间，文件到块的映射，以及每个块副本的位置。所有的元数据都保存在主服务器的内存里。除此之外，前两种类型（命名空间和文件块映射）的元数据，还会用日志的方式保存在主服务器的硬盘上的操作日志内，并在远程的机器内复制一个副本。使用日志，让我们可以简单可靠的更新主服务器的状态，而且不用担心服务器崩溃带来的数据不一致的风险。主服务器不会持久化保存块的位置信息。主服务器在自己启动以及块服务器加入集群的时候，询问块服务器它所包含的块的信息。

2.6.1 内存内数据结构

因为元数据保存在内存中，所以主服务器操作的速度很快。而且，主服务器可以在后台，简单而高效的周期扫猫自己的整个状态。这种周期性的扫描用来在块服务器间实现块的垃圾收集的功能，用来实现块服务器失效的时复制新副本的功能，用来实现负载均衡的块移动的功能，以及用来实现统计硬盘使用情况的功能等。4.3和4.4章节将深入讨论这些行为。

这种纯内存的机制一种可能的问题是，块的数量和整个系统的容量都受限于主服务器拥有的内存尺寸。不过实际上这不是一个严重的限制。对于每个64MB的块，服务器只需管理不到64字节的元数据。大多数的块是满的，因为每个文件只有最后一块是部分填充的。类似的，每个文件的命名空间通常在64字节以下，因为保存的文件名是用前缀压缩算法压缩过的。

如果需要支持更大的文件系统，为主服务器增加额外内存的花费是很少的，而把元数据保存在内容带来了系统的简洁性，可靠性，高性能和灵活性。

2.6.2 块位置

主服务器并不保存哪个块服务器有给定块的信息的持久化记录。它只是在启动的时候向块服务器要求这些信息。然后主服务器就可以保持它的信息最新，因为它控制了所有的块位置分配，而且用规律的心跳信息监控块服务器的状态。

开始的时候，我们试图把块位置信息持久化的保存在主服务器，但是我们发现在启动的时候查询块服务器，然后定期询问的方式更简单。这简化了在块服务器在加入和离开集群，改名，失效，重启等等情况下，主服务器和块服务器的同步问题。在一个有数百台服务器的集群，这些事件发生的太频繁了。 

理解这个设计思想的另外的途径是，理解块服务器才能最后确定一个块是否在它的硬盘上。我们没有打算在主服务器上面管理一个这些信息的全局视图，因为块服务器的错误可能会导致块自动消失，亦或者管理员可能会改变一个块服务器的名字。

2.6.3 操作日志

操作日志包含核心元数据变化的历史记录。这对GFS很重要。这不仅是因为它是元数据唯一的持久化存储记录，而且因为它起到了定义同步操作顺序的逻辑时间线的作用。文件和块以及他们的版本，都是唯一和持久地由他们创建时的逻辑时间标识的。

因为操作日志很重要，我们必须稳定的保存它，并保证只有在元数据的变化被持久化保存后，这种变化才对客户端可见。否则，即使块没有发生任何问题，我们仍有可能丢失整个文件系统，或者丢失近期的客户端操作。所以，我们把操作日志复制到多台远程机器，而且仅在把最近的日志记录写入本地以及远程机器的硬盘后，才会对客户端操作进行响应。写入之前主服务器批量处理数个日志记录，减少写入和复制的负载。

主服务器通过重放操作日志恢复它的文件系统。为了降低启动时间，我们必须保持日志足够小。当日志增长到一个特定尺寸的时候，主服务器就会汇总它的状态为一个检查点，这样它就可以通过从硬盘调入最新的一个检查点来恢复系统，只需要重放检查点后有限数目的日志记录即可。检查点保存在一个压缩B-树形式的结构里，可以直接映射到内存，而且用于命名空间查询时无需额外的解析。这大大提高了恢复速度，而且增强了可用性。

创建一个检查点可能会花点时间，所以主服务器的内部状态被结构为一种形式，这种形式保证了检查点的创建不会对正好这时进入的动作造成延迟。主服务器用分别的线程切换到新的日志文件和创建新的检查点。新的检查点包括切换前所有的动作。集群有百万文件时，创建一个检查点需要一分钟左右。创建完成后，检查点会被写入在本地和远程的硬盘里。

进行恢复仅需要最新的检查点和相应的日志文件。老的检查点和日志文件可以自由的被删除，不过我们通常会保存一些用来应付数据灾难。创建检查点过程中的失败不会对正确性产生任何影响，因为恢复代码可以检测并跳过没有完成的检查点。

2.7 一致性模型

GFS有一个简化的一致性模型可以完美的支持我们高度分布的应用，但保持了简单以及容易实现的优点。我们现在讨论GFS系统对一致性的保证，以及应用程序如何保证。我们强调GFS如何管理这些保证，但是实现细节我们将在论文的其他部分介绍。

2.7.1 GFS的保证（？）

文件命名空间的修改（例如，文件创建）是原子性的。他们仅受主服务器的控制：命名空间锁定保证了原子性和正确性（4.1章）；主服务器的操作日志定义了这些操作的全局总顺序（2.6.3章）。

数据操作后文件范围的状态取决于操作的类型，是否成功，以及是否是同步操作。表1概述了这些结果。如果所有客户端，不管从哪个副本读取，看到的数据都一样，那么我们说文件区域是一致的。如果数据操作后，文件范围是一致的，且客户端可以知道到操作写入了什么内容，那么文件区域是已定义的。当数据操作完成，同步写入者间没有冲突，那么影响的文件范围就是已定义的（隐含了一致性）：所有的客户端一直都可以看到写入的内容。成功的同步操作后，文件范围未定义，但是是一致的：所有的客户端看到同样的数据，但是任何一个操作的写入内容都不会被表现出来。通常情况下，文件范围内包含了混杂的来自多个操作的数据片段。一个失败的操作，会让文件范围不一致（所以也是未定义的）：不同的时间不同的客户端会看到不同的数据。后面我们将描述我们的应用如何区分已定义和未定义的范围。应用程序没有必要进一步区分未定义范围的不同类型。

数据操作可以是写或者记录追加。写操作会把数据写在应用程序指定的偏移位置。即使是在同步进行多个操作时，记录追加至少可以把数据（记录）原子性的追加到文件中一次，但是偏移位置是GFS选择的（3.3章）。（相比而言，通常说的追加写入的偏移位置在文件的尾部。）偏移位置被返回给客户端，用来标明包含记录的已定义范围的起点。此外，GFS可能会在中间插入填充数据或者记录的副本。他们占用那些被认定是不一致的范围，通常他们比用户数据的量小的多。

在一系列成功的操作后，被操作的数据范围被保证为已定义的，并且包含最后一次操作写入的数据。（a） GFS对块的多个副本采用一样的顺序进行操作（3.1章）。（b）并使用块版本号来检测副本是否因为它所在的块服务器当机（4.5章）而错过了某些操作，而失效了。失效的副本不会再被任何操作涉及，也不会被主服务器作为块位置告知客户端。他们会优先被垃圾收集。

由于客户端缓存块位置，所以在信息刷新前，他们有可能从一个失效的副本读取数据。时间窗口由缓存的超时以及文件的下一次打开时间决定，文件打开后会清除缓存中与文件有关的所有块信息。而且由于我们的文件大多数都是只进行追加的，所以一个失效的副本通常返回一个提前结束的块而不是过期的数据。读取者重新尝试并联络主服务器后，就会立刻得到当前的块位置。

成功操作很久以后，组件的失效当然也可以损坏或者毁掉数据。GFS用主服务器和块服务器之间的定期握手来找到失效的块服务器，用校验和来检测数据的损坏（5.2章）。一旦发现问题，数据会尽快从有效的副本中恢复出来（4.3章）。只有一个块的所有副本在GFS做出反应之前，全部丢失，这个块才会不可逆转的丢失，而通常GFS的反应是在几分钟内的。即使在这种情况下，块不可用，而不是损坏：应用程序会收到清晰的错误信息而不是损坏的数据。

2.7.2 程序的实现

基于GFS的应用程序利用一些其他目的也需要的简单技术就可以跟简化的一致性模型协作了：倚靠追加而不是其他的写入，检查点，写操作的自验证，自说明的记录。

实际上，我们所有的程序对文件的操作追加比覆盖多。一种典型的使用情况是，写入者从头到尾生成了一个文件。写入所有数据后写入者把文件名改为一个持久的文件名，或者周期性的检查成功写入了多少数据。检查点可以包含程序级别的校验和。读取者仅验证并处理上个检查点内的文件区域，这些文件区域的状态一定是已定义的。这个方法满足了我们所有的一致性和并行性的要求。追加比随机位置写入更加有效率，而且对应用程序的失败更有弹性。检查点可以让写入者渐进的重新开始，并且可以保证读取者处理已经被成功写入的文件数据，即使从应用程序的观点来看文件的写入并未完成。

另外一种典型的使用情况下，许多写入者并行的追加数据到同一个文件，进行结果的合并或者进行生产者-消费者模型队列。记录追加的至少一次追加的语意保证了每个写入者的输出。读取者用下面的方法来处理偶然填充数据和重复内容。写入者准备的每条记录都包含了额外的信息，例如校验和，可以用来验证它的有效性。读取者可以利用校验和抛弃额外的填充数据和记录片段。如果应用不能容忍偶尔的重复内容(比如，如果他们想触发非幂等操作)，可以用记录的唯一标识符来过滤它们，这些唯一标识符通常用于命名相应的程序节点，例如web文档。这些记录I/O的功能都包含在库代码中在我们的程序中共享，并且适用于Google实现的其他的文件接口。所以，相同系列的记录，加上一些罕见的重复，总是直接被分发给记录读取者。

3. 系统交互

我们设计这个系统来最小化主服务器对所有操作的参与。在这样的背景下，我们现在描述一下客户机，服务器和块服务器如何交互以实现数据操作，原子化的记录追加以及快照。

3.1 租约和变更顺序

变更就是一个会改变块内容或者元数据的操作，例如写入或者记录追加。每个变更执行在块的所有副本上。我们使用租约来保持多个副本间变更顺序的一致性。主服务器为其中一个副本签署一个块租约，我们把这个副本叫做主块。主块选择对块所有操作的一系列顺序。进行操作的时候所有的副本遵从这个顺序。这样全局的操作顺序首先由主服务器选择的租约生成顺序决定，然后由租约中主块分配的序列号决定。

租约机制的设计是为了最小化主服务器的管理负载。租约的初始超时是60秒。然而一旦块被修改过，主块可以请求更长的租期，通常可以通过主服务器的确认收到额外的时间。这些额外时间的请求和批准都通过服务器和块服务器之间的心跳信息来传递。有时候，主服务器会在租约到期前取消它（例如，当服务器想取消施加在一个已经被改名的文件上的操作。）。即使主服务器和主块失去联系，它仍旧可以安全地在老租约到期后产生一个加诸于其他的副本的租约。

在图2中，我们将用如下这些数字步骤，展现写入操作的控制流程。

1.客户机向主服务器询问哪一个块服务器保存了当前的租约，以及其他副本的位置。如果没有一个块服务器有租约，主服务器就选择一个副本给它一个租约（没有被显示出来）。

2.主服务器回复主块的标识符以及其他副本的位置。客户机为了后续的操作缓存这个数据。只有主块不可用，或者主块回复说它已经不在拥有租约的时候，客户机才需要重新跟主服务器联络。

3.客户机把数据推送到所有的副本上。客户机可以用任意的顺序推送。每个块服务器会把这些数据保存在它的内部LRU缓冲内，直到数据被使用或者过期。通过把数据流和控制流分离，我们可以基于网络负载状况对昂贵的数据流进行规划，以提高性能，而不用去管哪个块服务器是主块。3.2章节会更详细地讨论这点。

4.所有的副本都被确认已经得到数据后，客户机发送写请求到主块。这个请求标识了早前推送到所有副本的数据。主块为收到的所有操作分配连续的序列号，这些可能来自不同的客户机。它依照序列号的顺序把这些操作应用到它自己的本地状态中。

5.主块把写请求传递到所有的二级副本。每个二级副本依照主块分配的序列号的顺序应用这些操作。

6.所有二级副本回复主块说明他们已经完成操作。

7.主块回复客户机。任何副本产生的错误都会报告给客户机。错误的情况下，主块和一些二级副本可能成功的写入了数据。（如果主块写入失败，操作就不会被分配序列号，也不会被传递。）客户端请求被确认为失败，已经修改的区域保持不一致的状态。我们的客户机代码通过重复失败的操作来处理这样的错误。在完全从头开始写入之前，可能会先从步骤3到步骤7进行几次尝试。

如果应用程序的写入量很大或者包含多个块，GFS客户机代码会把他们分成多个写操作。他们都遵循前面描述的控制流程，但是他们可能会被来自其他客户机的同步操作插入或者覆盖。所以，共享的文件范围的尾部可能包含来自不同客户机的片段，虽然这些副本是一致的，因为这些分别的操作在所有的副本都按照相同的顺序成功完成了。这使文件范围处于2.7章描述过的一致但是未定义的状态。

3.2 数据流

为了提高网络的效率我们把数据流和控制流分开。控制流从客户机到主块然后再到所有二级副本的同时，数据顺序推送到一个精心选择的管道形式的块服务器链。我们的目标是完全利用每个机器的带宽，避免网络瓶颈和延迟过长的连接，最小化推送所有数据的耗时。

为了完全利用每个机器的带宽，数据顺序推送到一个块服务器链，而不是分布在其他的拓扑下（例如，树）。这样，每个机器的带宽就会完全用于尽快的传输数据，而不是分散在多个副本间。

为了避免网络瓶颈和延迟过长的连接，每个机器都把数据传送到在网络拓扑中最近的机器。假设客户推送数据到块服务器S1至S4。它把数据传送给最近的块服务器S1。S1把数据传递给S2到S4之间最近的机器S2。同样的，S2把数据传递给S3和S4之间更近的机器。我们的网络拓扑非常简单，简单到用IP地址就可以计算出节点的远近。

最后，我们利用在TCP连接上管道化数据传输来最小化延迟。块服务器一旦得到一些数据，马上开始传递它们。管道化对我们帮助极大，因为我们使用全双工连接的交换网络。马上发送数据不会降低接收的速度。没有网络拥塞的情况下，传送B字节的数据到R个副本的理想时间是 B/T+RL ，T是网络的吞吐量，L是两台机器传输字节的延迟。我们的网络连接是100Mbps（T），L远小于1ms。这样，1MB的数据理想情况下会在80ms左右分发出去。

3.3 原子性的记录追加（？）

GFS提供了一个叫做记录追加的原子性的追加操作。传统的写入操作，客户机指定数据写入的偏移位置。同意范围的并行写入是不可串行的：范围内会包括来自不同客户机的数据片段。而对于记录追加，客户机只能指定数据。GFS至少一次自动地把数据追加到文件中GFS选定的偏移位置，然后把偏移位置返回给客户机。这类似于在Unix下，多个并行写入者在没有竞争条件下，对以O_APPEND模式打开的文件的写入。

记录追加在我们的分布应用中使用的非常频繁，许多客户机并行地追加数据到同一个文件。如果采用传统的写入方式，客户机需要额外的复杂和代价昂贵的同步机制，例如一个分布的锁管理器。在我们的工作中，这样的文件经常服务于多生产者/单消费者队列，或者包含来自多个不同客户机的合并的结果。

记录追加是遵循章节3.1描述的控制流程的一个操作，仅有主块有点额外的控制逻辑。客户机把数据推送给文件最后一个块的所有副本，然后发送请求给主块。主块检查对当前块的记录追加操作是否会造成块超过最大值（64MB）。如果是这样，它首先把块填充到最大值，告诉所有二级块做同样的操作，然后回复客户机说明需要对下一个块也进行操作。（一次记录追加操作的数据尺寸严格规定不超过4倍的最大块尺寸，这样即使最坏情况下存储碎片的数量仍旧控制在可接受的级别。）如果记录不超过最大尺寸，这是比较常见的，主块把数据追加到自己的副本内，然后通知二级副本把数据写在跟主块一样的位置，最后通知客户机操作成功完成。

如果任何副本上追加失败，客户端重新进行操作。所以，同一块的不同副本可能包含不同的数据，可能包括一个记录全部或者部分的重复。GFS并不保证所有的副本是字节级别一致的。它仅保证数据会作为原子性单元被至少写入一次。这个属性是由如下的简单观察推导而来的，如果操作报告成功，数据一定已经写入在同一块的所有副本的相同偏移位置上。此后，所有的副本至少达到了记录尾部的长度，任何额外的记录都会附加到更大的偏移或者不同的块，即使其他的块后来成为了主块。在我们一致性保障措施的术语中，成功被执行追加操作的区域的数据是已定义的（所以也是一致的），反之则是不一致的（也就是未定义的）。我们的程序可以处理不一致的区域，我们在2.7.2章节讨论过这些。 

3.4 快照

快照操作可以非常迅速的创建一个文件或者目录数的副本，而且几乎不会被正在进行的其他操作打断。我们的用户使用它快速创建巨大数据集的分支副本（通常是递归的复制这些副本），或者是在改变之前，建立当前状态的检查点，这样之后可以轻松的提交确认或者进行回滚。

就像AFS，我们使用标准的copy-on-write技术实现快照功能。当主服务器收到快照请求，它首先取消关于快照相关文件所在块服务器上面的所有租约。这就确保了任何发生在这些块服务器上面的后续写操作都需要与主服务器沟通找到租约持有者。这就给主服务器一个机会，首先创建块的新副本。

取消或者这些租约过期后，主服务器把这些操作日志到硬盘上。然后，它通过复制源文件或者目录的元数据的方式，把这些日志记录应用到它保存在内存的状态中。新创建的快照文件指向与源文件完全相同的块地址。

客户机在快照操作后第一次想写入一个块C，它发送一个请求给主服务器来寻找当前的租约持有者。主服务器注意到块C的引用技术超过1。它延迟回复客户机的请求，取而代之的是选择一个新的块句柄C'。然后它要求每个拥有块C当前副本的块服务器创建一个叫做C'的新块。通过在源块所在块服务器创建新的块，我们确保数据可以本地化的复制，而不用通过网络（我们的硬盘比我们的100Mb以太网连接快3倍）。从这点看，请求的处理和任何其他的块也没什么不同：服务器保障新块C'的副本中的一个拥有租约，然后用它回应客户机，客户机可以正常的写这个块，而不需要知道它是刚刚从一个已存的块中创建出来的。

4. 主服务器的操作

主服务器执行所有的名称空间操作。另外，它管理整个系统的所有块副本：它决定块的位置，创建新块和相应的副本，协调多变的系统活动保持块被完全复制，均衡所有块服务器之间的负载，回收没有使用的存储空间。现在我们讨论每一个主题。

4.1 名称空间管理和锁

主服务器的许多操作会花费较长的时间：例如，快照操作必须取消快照内容涵盖的所有块服务器的租约。我们不希望这些操作的运行延迟其他的主服务器操作。所以我们允许多个操作同时进行，用名称空间的区域之上的锁来保证相应的秩序。

不同于许多传统文件系统的是，GFS没有一个用来列出目录内全部文件的，每个目录的数据结构。而且不支持同一文件或者目录的别名（Unxi术语中的符号链接或者硬链接）。GFS展现名称空间的逻辑就像一个全路径映射到元数据的查找表。利用前缀压缩，这个表可以高效的在内存中展现。名称空间树内的每个节点（绝对路径文件名和绝对路径目录名）都有一个与之对应的读写锁。

每个主服务器操作运行之前都需要获得一系列的锁。例如，如果操作包含/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集群是多层高度分布的。典型的来说有数百个块服务器安装在许多机架上。这些块服务器可能依次被数百个来自同一机架或者不同机架的客户机访问。来自不同机架的两台机器之间的通讯也许会跨越一个或多个网络交换机。另外，机架的出入带宽可能比机架内所有机器和在一起的带宽要小。多层分布带来伸缩性，可靠性以及可用性方面完全不同的挑战。

块副本布置策略服务于两个目标：最大化数据可靠性和可用性，最大化网络带宽利用率。为了这些，仅仅在机器间分布文件是不够的，这只能防止硬盘损坏或者机器失效带来的影响，以及最大化每台机器的网络带宽使用率。我们必须在机架间分布文件。这保证了即使某个机架完全被损坏或者离线，一些块的副本会幸存仍旧可以使用（例如，电源或者网络交换机故障造成的问题）。这还意味着网络通讯，尤其是读取，可以利用多个机架的整合带宽。另一面是，写操作的网络通讯必须通过多个机架，这是我们乐于付出的代价。

4.3 创建，重新复制，负载均衡

块副本创建有三种原因：块创建，重新复制和负载均衡。

当主服务器创建一个块，它会选择哪里放置初始的空副本。具体策略取决于几个因素。（1）我们希望把新的副本放置在低于平均硬盘使用率的块服务器。这样平衡块服务器之间的硬盘使用率。（2）我们希望限制每一个块服务器上"近期"创建操作的数量。虽然创建操作本身是廉价的，但是它总是会紧跟着沉重的写操作，因为写入者需要写的时候才会进行创建，而在我们的"追加一次多多次"的工作负载下块一旦被成功写入就会变为只读。（3）如上面讨论过的，我们希望把块分布在机架之间。

一旦块的可用副本数少于用户指定的值，主服务器会重新复制它。这可能发生在几个原因下：一个块服务器变得不可用，块服务器报告存储在之上的副本损坏了，因为错误它的硬盘不可用了，或者副本数目标提高了。每个需要被重新复制的块基于几个因素排序。一是，块离它的副本数量目标有多远。例如，我们给已经丢失两个副本的块比只丢失一个副本的块更高的优先级。另外，我们优先重新复制活着的文件而不是属于那些近期删除的文件的块（查看4.4章节）。最后，为了失效对正在运行的应用程序的影响，我们提高阻塞客户机流程的块的优先级。

主服务器选择优先级最高的块，然后通过通知一些块服务器上直接从已有的可用的副本复制数据的方式来"克隆"它。新副本位置的策略根创建操作类似：平均硬盘使用率，限制同一块服务器上的活动的克隆操作数量，在机架间分布副本。为了防止克隆所需的网络流量超过客户端流量，主服务器限制块和块服务器的活跃克隆操作数量。另外，每个块服务器，通过调节它对源块服务器的读请求来限制它花在每个克隆操作上面的带宽。

最后，主服务器周期性地对副本进行负载均衡：它检查当前的副本分布情况，然后移动副本以得到更好的硬盘剩余空间以及负载的均衡。同时在这个过程中，主服务器逐渐的填满一个新的块服务器，而不是用新块以及随之同时涌入的沉重的写通讯淹没它。新副本的布置标准根上面讨论的相同。另外，主服务器必须选择哪些现有的副本要被移走。一般来说，它移动那些剩余空间低于平均值的块服务器上面的副本，这样就可以平衡硬盘使用率。

4.4 垃圾回收

文件删除后，GFS不会立刻收回可用的物理空间。对文件和块的常规垃圾收集非常惰性。我们发现这样可以使系统更简单更可靠。

4.1.1 机制

当应用程序删除了一个文件，主服务器立刻把删除记录到日志里就像其他的改变一样。然而，它不是马上回收资源，而是把文件改成一个包含删除时间戳的隐藏的名字。当主服务器对文件系统命名空间进行常规扫描的时候，它会删除所有有如此隐藏文件名的文件，如果它们已经存在超过3天了（这个时间间隔是可以被设置的）。直到此时，文件仍旧可以用新的特殊的名字访问读取，可以被反删除，通过改名把它变为正常文件。如果隐藏文件从名称空间中移走，保存在内存中它的元数据就被删除了。这有效的服务于对所有块的连接。

在相似的对块命名空间的常规扫描，主服务器找到孤儿块（无法从任何文件到达的块）并擦除它们的元数据。在与主服务器交换数据的心跳信息中，每个块服务器报告它拥有的块的信息的一个子集，然后主服务器回复指出哪些块在主服务器的元数据中已经不存在了。块服务器上面就是任意删除这些块的副本了。

4.4.2 讨论

虽然分布垃圾回收在编程语言领域是一个需要复杂解决方案的难题，它在我们这里非常简单。我们可以很容易的识别所有块的引用：他们都在服务器独立掌握的文件到块的映射表中。我们也可以轻易的找到所有块的副本：在每个块服务器上他们都是指定目录下的Linux文件。所有主服务器不知道的副本都是"垃圾"。

垃圾回收在恢复存储空间的同时，提供直接删除无法得到的几个好处。首先，这样对于组件经常失效的大规模分布系统简单而且可靠。块创建可能在某些块服务器成功，某些服务器上失败，留着那些失败的副本反正主服务器也不知道。副本删除信息可能丢失，主服务器必须记得重新发送失败传递的目标，它自己的和块服务器的。垃圾回收提供了统一无依赖的途径，来清除那些不知道用处的副本。其次，它把存储回收操作合并到主服务器规律性的后台活动，如例行扫描以及跟块服务器握手。这样，操作会被批量的执行，开销会被分散。而且，操作会在主服务器相对空闲的时候完成。这样主服务器可以给那些需要快速反应的客户机请求提供更快捷的响应。三，有延迟的存储回收比随机、不可逆转的删除，更加安全。

在我们的经验中，主要的缺点是，在存储空间紧张的时候，这样的延迟有时候会阻碍用户去更好的调节存储空间的使用情况。应用程序重复创建和删除临时文件夹，存储空间不会马上恢复。我们解决这个问题的方式是，如果一个已删除文件明确的再次被删除，会加速空间回收速度。我们还允许用户为命名空间的不同部分设定不同的复制和回收策略。例如，用户可以指定某些目录树下面的文件没有任何副本，删除立即执行，从文件系统移除后无法恢复。

4.5 过期副本检测

如果块服务器失效，或者块服务器当机的时候错过了一些操作，块副本会过期。对于每个块，主服务器保存一个块版本号，用来分辨当前副本和过期副本。

无论何时主服务器获得一个块的新租约，它增加块的版本号，然后通知当前副本。主服务器和这些副本都把新的版本号记录在它们的持久化存储的状态中。这发生在任何客户机得到通知以前，发生在它写入块之前。如果另外一个块服务器正好不可用，那么它的块版本号就不会被更新。当这个块服务器重新启动，向主服务器报告它拥有的块的集合以及相应的版本号的时候，主服务器就会检测出来块服务器包含过期的块。当主服务器看到一个比它们的记录更高的版本号，主服务器假定那些块服务器在获取租约的时候失效了，所以选择更高的版本作为当前的版本。

主服务器在周期的垃圾回收中移除所有的过期副本。在这之前，当回复客户机的块信息请求的时候，主服务器只是高效的当作那些过期的块不存在而已。作为另外的保护措施，主服务器通知客户机哪个块服务器持有租约的时候，当主服务器指示块服务器从哪个块服务器读取数据进行克隆操作的时候，主服务器的信息都包含了块的版本号。客户机或者块服务器执行操作时会验证版本号，这样它们就可以总是访问当前版本的数据了。

5. 容错和诊断

我们面临的最大挑战之一就是设计一个系统处理频繁的组件失效。组件的数量和质量让这种问题变得比意外更常见：我们不能完全信任机器，也不能完全信任硬盘。组件的失效可能造成不可用的系统，坏的，不完整的数据。我们讨论我们如何面对这些挑战，讨论我们构建的用于诊断系统故障的工具。

5.1 高可用性

在GFS集群的数百个服务器之中，任何给定时刻都有一些是不可用的。我们用两条简单有效的策略保持整个系统的高可用性：快速恢复和副本。

5.1.1 快速恢复

不管主服务器和块服务器是如何关闭的，它们被设计为可以在数秒钟内恢复它们的状态并启动。事实上，我们并不区分正常或者非正常的关闭；通常关闭服务器的方法就是杀死它的进程。对客户机和其他的服务器来说，他们发出的请求超时只是个小问题，重新连接到重启后的服务器，重试。6.6.2章节报告了观察到的启动时间。

5.1.2 块复制

诚如之前讨论的，每个块被复制到不同机架上的不同的块服务器上。用户可以为文件命名空间的不同部分设定不同的复制级别。缺省值是3。当有块服务器离线或者通过校验和验证（查看5.2章节）发现了坏块，主服务器克隆已存在的副本用来保证每个块被完全复制。虽然块复制工作的很好，但是我们也在寻找需要同等或者更少代码的，其他形式的跨服务器冗余方案来解决我们日益增长的只读存储需求。我们希望它更有挑战性，但是更加易于管理，在我们非常松散的系统结构下实现更复杂的冗余体系，因为我们的通讯主要是追加和读取构成的，而不是小的随机写。

5.1.3 主节点复制

为了可靠性主服务器状态要被复制。它的操作日志和检查点都要复制到多台机器上。对状态的操作被设计为，只有当它的日志记录被写入到本地硬盘以及所有的主服务器副本以后才会被提交。为了简化设计，一个主服务器进程管理所有改变系统状态的操作包括如垃圾回收这样的后台活动。当它失效，它几乎可以马上重新启动。当它的机器或者硬盘损坏，GFS架构之外的监视机构会总启动一个包含这操作日志副本的新主服务器进程。客户机只使用主服务器的规范名（例如，gfs-test）与之联络，这是一个DNS别名，如果主服务器被重新指定它可以相应的改变。

此外，还有些"影子"主服务器，它们即使在真正的主服务器当机的时候也只提供文件系统的只读访问。它们是影子，而不是镜像，所以它们的数据总是比主服务器更新要慢点，通常是1秒以下。它们可以提高那些不经常改变的文件的读取效率，或者是帮助那些不在乎数据更新略有延迟的程序。事实上，自从文件从块服务器被读走，应用程序就不再关心它们内容的变化了。在短暂窗口可以延迟的是文件的元数据，比如目录的内容或者访问控制信息。

为了保持自己被通知，影子主服务器增长中的操作日志的副本，并按照与主服务器完全相同的顺序对自己的数据结构执行修改。类同主服务器，它也在启动的时候轮询块服务器（之后定期访问）以获得块副本的位置，交换心跳信息以监控它们的状态。它仅在主服务器决定创建和删除副本的时候，才需要依靠主服务器得到副本位置的更新结果。

5.2 数据完整性

每个块服务器利用校验和来检查存储的数据是否损坏。一个拥有数百台机器数千个硬盘的GFS集群，硬盘故障带来的数据损坏和丢失是非常频繁的。(See Section 7 for one cause.)我们可以利用块的其他副本修复损坏，但是通过比较多台块服务器的数据来检查损坏是非常不可行的。而且，不一致的副本可能是合法的：GFS操作的语意，特别是前面讨论过的原子性的记录添加，不保证产生完全一致的副本。所以，每个块服务器必须通过校验和，独立的验证它自己拥有的拷贝的数据完整性。

块被分为64KB的大小。每个有一个对应的32位的校验和。和其他元数据一样，校验和保存在内存，持续化存储在日志里，与用户数据是分离的。

不管是对客户机还是其他的块服务器，在读取操作中，块服务器在返回任何数据之前验证读取范围的数据的校验和。这样块服务器就不会把损坏的数据传播给其他机器。如果块和记录的校验和不符，块服务器给请求者返回一个错误信息，然后把这个不匹配报告给主服务器。作为回应，请求者读取其他的副本，而主服务器从其他的副本克隆这个块。一个好的新块布置好后，主服务器指导报告不匹配的那台块服务器删除这个副本。

校验和对读取性能影响不大，基于几个原因。因为我们的读取范围至少是几个块，而我们只需要读取很少的额外数据去做验证。GFS客户机代码更进一步降低了负载，因为它尽量在校验和块的边界对齐读取。而且，校验和的查询和比较都在块服务器完成，不需要任何I/O，而且校验和的计算通常跟I/O同步进行。

在追加到文件尾的写入操作（而不是覆盖现有数据的写入操作），校验和的计算被严重的优化，因为这类操作是我们负载中最优先的。我们只是增量更新最后一块追加记录的校验和，用所有的追加来的新校验和块来计算新的校验和。即使最后一个校验和块破坏了，而我们无法检测到它，但是这样新的校验和就不会符合存储的数据，那么我们就可以在下次读的时候检测到这个损坏了。

相对而言，如果写入覆盖块的已存在区域，我们必须读取并且验证写入区域的第一个和最后一个数据块，然后执行写操作，最后计算和记录新的校验和。如果在写之前，我们不验证第一个和最后一个数据块，那么新的校验和可能会隐藏位于那些没有被覆盖区域的数据错误。

在空闲期间，块服务器可以扫描并验证不活跃块的内容。这就使我们可以检查那些很少被读取的块。一旦检测出损坏，主服务器就可以创建一个新的没有损坏的副本，并删掉损坏的副本。这就避免了一个不活跃的坏块骗过主服务器，让之以为块有足够的好的副本。

5.3 诊断工具

广泛而详尽的分析日志，在问题隔离，调试，性能分析等方面对我们的帮助无法估量，与此同时它几乎没有开销。没有日志，我们很难理解短暂的不重复的机器之间的交互。GFS的服务器们生成许多事件（例如，块服务器启动和当机）以及所有的RPC（译注：远程进程调用）请求和回复。这些分析日志即使被删除也不会影响系统的正确运转。然而，我们尽量保存这些日志，直到达到空间极限。

RPC日志包含了除了读写的文件数据本身以外的线上传输的所有详细的请求和回应。通过匹配请求与回应，收集不同机器的RPC记录，我们可以重建整个通信历史来分析问题。日志还用来跟踪负载测试和性能分析。

日志对性能的影响很小（原小于带来的好处），因为这些日志是顺序和异步的。最近的时间保存在内存中，可用于连续的在线监控。