GFS论文中文翻译

冷不防 2022-08-07 06:35 185阅读 0赞

原文地址：  
[http://labs.google.com/papers/gfs.html][http_labs.google.com_papers_gfs.html]

## 摘要 ##

我们已经设计和实现了Google File System，一个适用于大规模分布式数据处理相关应用的，可扩展的分布式文件系统。它基于普通的不算昂贵的硬件设备，实现了容错的设计，并且为大量客户端提供极高的聚合处理性能。  
我们的设计目标和上一个版本的分布式文件系统有很多相同的地方，我们的设计是依据我们应用的工作量以及技术环境来设计的，包括现在和预期的，都有一部分和早先的文件系统的约定有所不同。这就要求我们重新审视传统的设计选择，以及探索究极的设计要点。  
这个文件系统正好与我们的存储要求相匹配。这个文件系统在Google内部广泛应用于作为存储平台使用，适用于我们的服务要求产生和处理数据应用，以及我们的研发要求的海量数据的要求。最大的集群通过上千个计算机的数千个硬盘，提供了数百TB的存储，并且这些数据被数百个客户端并行同时操作。  
在这个论文里，我们展示了用于支持分布式应用的扩展文件系统接口设计，讨论了许多我们设计的方面，并且列出了我们的micro-benchmarks以及真实应用性能指标。

### 分类和主题描述 ###

D\[4\] ：3 – 分布式文件系统

### 普通条目 ###

设计，可靠性，性能，测量  
Design，reliability，performance，measurement

### 关键词 ###

容错，扩展性，数据存储，集群数据存储

## 介绍 ##

我们已经为Google迅速增长的数据处理需要而设计和实现了Google File System(GFS)。GFS和上一个分布式文件系统有着很多相同的设计目标，比如性能，扩展性，可靠性，以及可用性。不过，他的设计是基于我们应用的工作量和技术环境驱动的，包括现在和预期的，都有部分和上一个版本的约定有点不同。这就要求我们重新审视传统的设计选择，以及探索究极的设计要点。

*  首先，节点失效将被看成是正常情况，而不再视为异常情况。整个文件系统包含了几百个或者几千个由廉价的普通机器组成的存储机器，而且这些机器是被与之匹配数量的客户端机器访问。这些节点的质量和数量都实际上都确定了在任意给定时间上，一定有一些会处于失效状态，并且某一些并不会从当前失效中恢复回来。这有可能由于程序的bug，操作系统的bug，人工操作的失误，以及硬盘坏掉，内存，网络，插板的损坏，电源的坏掉等等。因此，持续监视，错误检测，容错处理，自动恢复必须集成到这个文件系统的设计中来。
 *  其次，按照传统标准来看，文件都是非常巨大的。数个GB的文件是常事。每一个文件都包含了很多应用程序对象，比如web文档等等。当我们通常操作迅速增长的，由很多TB组成的，包含数十亿对象的数据集，我们可不希望管理数十亿个KB大小的文件，即使文件系统能支持也不希望。所以，设计约定和设计参数比如I/O操作以及blocksize（块大小），都需要重新审查。
 *  第三，大部分文件都是只会在文件尾新增加数据，而少见修改已有数据的。对一个文件的随机写操作在实际上几乎是不存在的。当一旦写完，文件就是只读的，并且一般都是顺序读取得。多种数据都是有这样的特性的。有些数据可能组成很大的数据仓库，并且数据分析程序从头扫描到尾。有些可能是运行应用而不断的产生的数据流。有些是归档的数据。有些是一个机器为另一个机器产生的中间结果，另一个机器及时或者随后处理这些中间结果。对于这些巨型文件的访问模式来说，增加模式是最重要的，所以我们首要优化性能的以及原子操作保证的就是它，而在客户端cache数据块没有什么价值。
 *  第四，与应用一起设计的的文件系统API对于增加整个系统的弹性适用性有很大的好处。例如我们不用部署复杂的应用系统就可以把GFS应用到大量的简单文件系统基础上。我们也引入了原子的增加操作，这样可以让多个客户端同时操作一个文件，而不需要他们之间有额外的同步操作。这些在本论文的后边章节有描述。  
    多个GFS集群现在是作为不同应用目的部署的。最大的一个有超过1000个存储节点，超过300TB的硬盘存储，并且负担了持续沉重的上百个在不同机器上的客户端的访问。

## 设计概览 ##

### 约定 ###

在为我们的需要设计文件系统得时候，我们需要建立的事先约定同时具有挑战和机遇。我们早先提到的关于观测到的关键要点，现在详细用约定来说明。

*  系统是建立在大量廉价的普通计算机上，这些计算机经常故障。必须对这些计算机持续进行检测，并且在系统的基础上进行：检查，容错，以及从故障中进行恢复。
 *  系统存储了大量的超大文件。我们与其有好几百万个文件，每一个超过100MB。数GB的文件经常出现并且应当对大文件进行有效的管理。同时必须支持小型文件，但是我们不必为小型文件进行特别的优化。
 *  一般的工作都是由两类读取组成：大的流式读取和小规模的随机读取。在大的流式读取中，每个读操作通常要读取几百k的数据，每次读取1M或者以上的数据也很常见。对于同一个客户端来说，往往会发起连续的读取操作顺序读取一个文件。小规模的随机读取通常在文件的不同位置，读取几k数据。对于性能有过特别考虑的应用通常会作批处理并且对他们读取的内容进行排序，这样可以使得他们的读取始终是单向顺序读取，而不需要往回读取数据。
 *  通常基于GFS的操作都有很多超大的，顺序写入的文件操作。通常写入操作的数据量和杜如的数据量相当。一旦完成写入，文件就很少会更改。对于文件的随机小规模写入是要被支持的，但是不需要为此作特别的优化。
 *  系统必须非常有效的，明确细节的对多客户端并行添加同一个文件进行支持。我们的文件经常使用生产者/消费者队列模式，或者作为多路合并模式进行操作。好几百个运行在不同机器上的生产者，将会并行增加一个文件。其本质就是最小的原子操作的定义。读取操作可能接着生产者操作进行，消费者会同时读取这个文件。
 *  高性能的稳定带宽的网络要比低延时更加重要。我们的目标应用程序一般会大量操作处理比较大块的数据，并且很少有应用要求某个读取或者写入要有一个很短的响应时间。

### 接口 ###

GFS提供了常见的文件系统的接口，虽然他没有实现一些标准的API比如POSIX。文件是通过pathname来通过目录进行分层管理的。我们支持的一些常见操作：create,delete,open,close,read，write等文件操作。  
另外，GFS有snapshot，record append等操作。snapshort创建一个文件或者一个目录树的快照，这个快照的耗费比较低。record append允许很多个客户端同时对一个文件增加数据，同时保证每一个客户端的添加操作的原子操作性。这个对于多路合并操作和多个客户端同时操作的生产者/消费者队列的实现非常有用，它不用额外的加锁处理。这种文件对于构造大型分布式应用来说，是不可或缺的。snapshot 和record append在后边的3.4 和3.3节有单独讲述。

### 架构 ###

GFS集群由一个单个的master和好多个chunkserver（块服务器）组成，GFS集群会有很多客户端client访问（图1）。每一个节点都是一个普通的Linux计算机，运行的是一个用户级别（user-level）的服务器进程。只要机器资源允许，并且允许不稳定的应用代码导致的低可靠性，我们就可以运行chunkserver和client可以运行在同一个机器上。  
在GFS下，每一个文件都拆成固定大小的chunk(块)。每一个块都由master根据块创建的时间产生一个全局唯一的以后不会改变的64位的chunk handle标志。chunkservers在本地磁盘上用Linux文件系统保存这些块，并且根据chunk handle和字节区间，通过LInux文件系统读写这些块的数据。出于可靠性的考虑，每一个块都会在不同的chunkserver上保存备份。缺省情况下，我们保存3个备份，不过用户对于不同的文件namespace区域，指定不同的复制级别。  
master负责管理所有的文件系统的元数据。包括namespace，访问控制信息，文件到chunk的映射关系，当前chunk的位置等等信息。master也同样控制系统级别的活动，比如chunk的分配管理，孤点chunk的垃圾回收机制，chunkserver之间的chunk镜像管理。master和这些chunkserver之间会有定期的心跳线进行通讯，并且心跳线传递信息和chunckserver的状态。  
连接到各个应用系统的GFS客户端代码包含了文件系统的API，并且会和master和chunkserver进行通讯处理，代表应用程序进行读写数据的操作。客户端和master进行元数据的操作，但是所有的数据相关的通讯是直接和chunkserver进行的。我们并没有提供POSIX API并且不需要和LInux的vnode层相关。  
客户端或者chunkserver都不会cache文件数据。客户端cache机制没啥用处，这是因为大部分的应用都是流式访问超大文件或者操作的数据集太大而不能被chache。不设计cache系统使得客户端以及整个系统都大大简化了（少了cache的同步机制）(不过客户端cache元数据)。chunkserver不需要cache文件数据，因为chunks就像本地文件一样的被保存，所以LInux的buffer cache已经把常用的数据cache到了内存里。

### 单个master ###

引入一个单个master的设计可以大大简化我们的设计，并且也让master能够基于全局的角度来管理chunk的存放和作出复制决定。不过，我们必须尽量减少master的读和写操作，以避免它成为瓶颈。客户端永远不会通过master来做文件的数据读写。客户端只是问master它应当访问那一个chunkserver来访问数据。客户端在一定时间内cache这个信息，并且在后续的操作中都直接和chunkserver进行操作。  
![这里写图片描述][20150318123539489]  
这里我们简单介绍一下图1中的读取操作。首先，客户端把应用要读取的文件名和偏移量，根据固定的chunk大小，转换成为文件的chunk index。然后向master发送这个包含了文件名和chunkindex的请求。master返回相关的chunk handle以及对应的位置。客户端cache这些信息，把文件名和chunkindex作为cache的关键索引字。  
于是这个客户端就像对应的位置的chunkserver发起请求，通常这个会是离这个客户端最近的一个。请求给定了chunk handle以及一个在这个chunk内需要读取得字节区间。在这个chunk内，再次操作数据将不用再通过客户端-master的交互，除非这个客户端本身的cache信息过期了，或者这个文件重新打开了。实际上，客户端通常都会在请求中附加向master询问多个chunk的信息，master于是接着会立刻给这个客户端回应这些chunk的信息。这个附加信息是通过几个几乎没有任何代价的客户端-master的交互完成的。

### chunk块大小 ###

chunk的大小是一个设计的关键参数。我们选择这个大小为64M，远远大于典型的文件系统的block大小。每一个chunk的实例（复制品）都是作为在chunkserver上的Linux文件格式存放的，并且只有当需要的情况下才会增长。滞后分配空间的机制可以通过文件内部分段来避免空间浪费，对于这样大的chunksize来说，（内部分段fragment）这可能是一个最大的缺陷了。  
选择一个很大的chunk大小提供了一些重要的好处。首先，它减少了客户端和master的交互，因为在同一个chunk内的读写操作之需要客户端初始询问一次master关于chunk位置信息就可以了。这个减少访问量对于我们的系统来说是很显著的，因为我们的应用大部分是顺序读写超大文件的。即使是对小范围的随机读，客户端可以很容易cache一个好几个TB数据文件的所有的位置信息。其次，由于是使用一个大的chunk，客户端可以在一个chunk上完成更多的操作，它可以通过维持一个到chunkserver的TCP长连接来减少网络管理量。第三，它减少了元数据在master上的大小。这个使得我们可以把元数据保存在内存，这样带来一些其他的好处，详细请见2.6.1节。  
在另一方面，选择一个大型的chunk，就算是采用滞后分配空间的模式，也有它的不好的地方。小型文件包含较少树木的chunk，也许只有一个chunk。保存这些文件的chunkserver就会在大量客户端访问的时候就会成为焦点。在实践中，焦点问题不太重要因为我们的应用大部分都是读取超大的文件，顺序读取超多的chunk的文件的。  
不过，随着batch-queue系统开始使用GFS系统的时候，焦点问题就显现出来了：一个可执行的程序在GFS上保存成为一个单chunk的文件，并且在数百台机器上一起启动的时候就出现焦点问题。只有两三个chunkserver保存这个可执行的文件，但是有好几百台机器一起请求加载这个文件导致系统局部过载。我们通过把这样的执行文件保存份数增加，以及错开batchqueue系统的各worker启动时间来解决这样的问题。一劳永逸的解决方法是让客户端能够互相读取数据，这样才是解决之道。

### 元数据 ###

master节点保存这样三个主要类型的数据：文件和chunk的namespace，文件到chunks的映射关系，每一个chunk的副本的位置。所有的元数据都是保存在master的内存里的。头两个类型（namepspaces和文件到chunk的映射）同时也是由在master本地硬盘的记录所有变化信息的operation log来持久化保存的，这个记录也会在远端机器上保存副本。通过log，在master宕机的时候，我们可以简单，可靠的恢复master的状态。master并不持久化保存chunk位置信息。相反，他在启动地时候以及chunkserver加入集群的时候，向每一个chunkserver询问他的chunk信息。

#### 内存数据结构 ####

因为元数据都是在内存保存的，master的操作很快。另外master也很容易定时后台扫描所有的内部状态。定时内部状态扫描是用于实现chunk的垃圾回收机制，当chunkserver失效的时候重新复制，以及为了负载均衡和磁盘空间均衡使用的目的做chunkserver之间的chunk镜像。4.3 和4.4节将讨论这些操作的细节。  
这种内存保存数据的方式有一个潜在的问题，就是说整个系统的chunk数量以及对应的系统容量是受到master机器的内存限制的。这个在实际生产中并不是一个很重要的限制。master为每64Mchunk分配的空间不到64个字节的元数据。大部分的chunks都是装满了的，因为大部分文件都是很大的，包含很多个chunk，只有文件的最后部分可能是有空间的。类似的，文件的名字空间通常对于每一个文件来说要求少于64个字节，因为保存文件名的时候是使用前缀压缩的机制。  
如果有需要支持到更大的文件系统，因为我们是采用内存保存元数据的方式，所以我们可以很简单，可靠，高效，灵活的通过增加master机器的内存就可以了。

#### chunk的位置 ####

master并不持久化保存chunkserver上保存的chunk的记录。它只是在启动的时候简单的从chunkserver取得这些信息。master可以在启动之后一直保持自己的这些信息是最新的，因为它控制所有的chunk的位置，并且使用普通心跳信息监视chunkserver的状态。  
我们最开始尝试想把chunk位置信息持久化保存在master上，但是我们后来发现如果再启动时候，以及定期性从chunkserver上读取chunk位置信息会使得设计简化很多。因为这样可以消除master和chunkserver之间进行chunk信息的同步问题，当chunkserver加入和离开集群，更改名字，失效，重新启动等等时候，如果master上要求保存chunk信息，那么就会存在信息同步的问题。在一个数百台机器的组成的集群中，这样的发生chunserver的变动实在是太平常了。  
此外，不在master上保存chunk位置信息的一个重要原因是因为只有chunkserver对于chunk到底在不在自己机器上有着最后的话语权。另外，在master上保存这个信息也是没有必要的，因为有很多原因可以导致chunserver可能忽然就丢失了这个chunk（比如磁盘坏掉了等等），或者chunkserver忽然改了名字，那么master上保存这个资料啥用处也没有。

#### 操作记录（operation log） ####

操作记录保存了关键的元数据变化历史记录。它是GFS的核心。不仅仅因为这时唯一持久化的元数据记录，而且也是因为操作记录也是作为逻辑时间基线，定义了并行操作的顺序。chunks以及文件，连同他们的版本（参见4.5节），都是用他们创建时刻的逻辑时间基线来作为唯一的并且永远唯一的标志。  
由于操作记录是极关键的，我们必须可靠保存之，在元数据改变并且持久化之前，对于客户端来说都是不可见的（也就是说保证原子性）。否则，就算是chunkserver完好的情况下，我们也可能会丢失整个文件系统，或者最近的客户端操作。因此，我们把这个文件保存在多个不同的主机上，并且只有当刷新这个相关的操作记录到本地和远程磁盘之后，才会给客户端操作应答。master可以每次刷新一批日志记录，以减少刷新和复制这个日志导致的系统吞吐量。  
master通过自己的操作记录进行自身文件系统状态的反演。为了减少启动时间，我们必须尽量减少操作日志的大小。master在日志增长超过某一个大小的时候，执行checkpoint动作，卸出自己的状态，这样可以使下次启动的时候从本地硬盘读出这个最新的checkpoint，然后反演有限记录数。checkpoint是一个类似B-树的格式，可以直接映射到内存，而不需要额外的分析。这更进一步加快了恢复的速度，提高了可用性。  
因为建立一个checkpoint可能会花一点时间，于是我们这样设定master的内部状态，就是说新建立的checkpoint可以不阻塞新的状态变化。master切换到一个新的log文件，并且在一个独立的线程中创建新的checkpoint。新的checkpoint包含了在切换到新log文件之前的状态变化。当这个集群有数百万文件的时候，创建新的checkpoint会花上几分钟的时间。当checkpoint建立完毕，会写到本地和远程的磁盘。  
对于master的恢复，只需要最新的checkpoint以及后续的log文件。旧的checkpoint及其log文件可以删掉了，虽然我们还是保存几个checkpoint以及log，用来防止比较大的故障产生。在checkpoint的时候得故障并不会导致正确性受到影响，因为恢复的代码会检查并且跳过不完整的checkpoint。

### 一致性模型 ###

GFS是一个松散的一致性检查的模型，通过简单高效的实现，来支持我们的高度分布式计算的应用。我们在这里讨论的GFS的可靠性以及对应用的可靠性。我们也强调了GFS如何达到这些可靠性，实现细节在本论文的其他部分实现。

#### GFS的可靠性保证 ####

文件名字空间的改变（比如，文件的创建）是原子操作。他们是由master来专门处理的。名字空间的锁定保证了操作的原子性以及正确性（4.1节）；master的操作日志定义了这些操作的全局顺序（2.6.3）  
什么是文件区，文件区就是在文件中的一小块内容。  
![这里写图片描述][20150318123939465]  
不管数据变化成功还是失败，是否是并发的数据变化，一个数据变化导致的一个文件区的状态依赖于这个变化的类型。表一列出了这些结果。当所有的客户端都看到的是相同的数据的时候，并且与这些客户端从哪个数据的副本读取无关的时候，一个文件区是一致性的。一个文件区是确定的，当数据发生变化了，在一致性的基础上，客户端将会看到这个全部的变化。当一个更改操作成功完成，没有并发写冲突，那么受影响的区就是确定的了（并且潜在一致性）：所有客户端都可以看到这个变化是什么。并发成功操作使得文件区是不确定的，但是是一致性的：所有客户端都看到了相同的数据，但是并不能却分到底什么变化发生了。通常，他是由好多个变动混合片断组成。一个失败的改变使得一个文件区不一致（因此也不确定）：不同的用户可能在不同时间看到不同的数据。我们接下来会描述我们的应用如何能够辨别确定的和不确定的区块。应用程序并不需要进一步区分不同种类的不确定区。  
数据更改可能是写一个记录或者是一个记录增加（writes/record appends）。写操作会导致一个应用指定的文件位置的数据写入动作。记录增加会导致数据（记录）增加，这个增加即使是在并发操作中也至少是一个原子操作，但是在并发record append中，GFS选择一个偏移量（3.3）增加。（与之对应的是，一个”普通”增加操作是类似一个客户端相信是写到当前文件最底部的一个操作）。我们把偏移量返回给客户端，并且标志包含这个纪录的确定的区域的开始。另外，GFS可以在这些记录之间增加填充，或者仅仅是记录的重复。这些确定区间之间的填充或者记录的重复是不一致的，并且通常是因为用户记录数据比较小造成的。  
在一系列成功的改动之后，改动后的文件区是确保确定的，并且包含了最后一个改动所写入的数据。GFS通过（a）对所有的数据副本，按照相同顺序对chunk进行提交数据的改动来保证这样的一致性（3.1节），并且（b）采用chunk的版本号码控制，来检查是否有过期的chunk改动，这种通常发生在chunkserver宕机的情况下（4.5节）。过期的副本将不参加到改动或者提交给master，让master通知客户端这个副本chunk的位置。他们属于最早需要回收的垃圾chunk。  
另外，由于客户端会cache这个chunk的位置，他们可能会在信息刷新之前读到这个过期的数据副本。这个故障潜在发生的区间受到chunk位置cache的有效期限制，并且也受到下次重新打开文件的限制，重新打开文件会把这个文件所有的chunk相关的cache信息全部丢弃重新设置。此外，由于多数文件都是只是追加数据，过期的数据副本通常返回一个较早的chunk尾部（也就是说这种模式下，过期的chunk返回的仅仅是说，这个chunk它以为是最后一个chunk，其实不是），而不是说返回一个过期的数据。当一个热ader尝试和master联系，它会立刻得到最新的chunk位置。  
在一个成功的数据更改之后，并且过了一段相对较长的时间，元器件的实效当然可以导致数据的损毁。GFS通过master和chunkserver的普通握手来标记这些chunserver的损坏情况，并且使用checksum来检查数据是否损坏（5.2节）。当发现问题的时候，数据会从一个有效的副本立刻重新恢复过来（4.3节）。只有当GFS不能在几分钟内对于这样的损坏做出响应，并且在这几分钟内全部的副本都失效了，这样的情况下数据才会永远的丢失。就算这种情况下，数据chunk也是不可用，而不是损坏：这样是给应用程序一个明确的错误提示，而不是给应用程序一个损坏的数据。

#### 应用的实现。 ####

GFS的应用程序可以用简单的几个技术来实现相关的一致性，这些技术已经被其他目的而使用了：尽量采用追加方式而不是更改方式，checkpoint，写自效验，自标示记录等等。  
实际上几乎我们所有的应用程序都是通过追加方式而不是覆盖方式进行数据的操作。通常都是一个程序创建一个文件，从头写到尾。当所有的数据都写完的时候，才把文件名字更改成为正式的文件名，或者定期checkpoint有多少数据已经完成写入了。Checkpoint可以包括应用级别的checksum。读取程序只校验和处理包含在最近checkpoint内的文件区，这些文件区是确定的状态。不管在一致性方面还是并发的方面，这个已经足够满足我们的应用了。追加方式对于应用程序来说更加有效，并且相对随机写操作来说对应用程序来说更加可靠。Checkpoint使得写操作者增量的进行写操作并且防止读操作者处理已经成功写入，但是对于应用程序角度看来并未提交的数据。  
在另一种常见情况下，很多个写操作者对一个文件并发增加，用来合并结果数据，或者提供一个生产者-消费者的队列。增加记录的 至少增加一次 的机制保护了每一个写入者的输出。读取者需要处理这些非必然的空白填充以及记录的重复。写入者写入的每一个记录都包含额外的信息，比如checksum等等，这样可以使得每条记录都能够效验。读取者可以通过这些checksum辨别和扔掉额外的填充记录或者记录碎片。如果读取者不能处理这些偶然的重复记录（比如，如果他们触发了一种非等幂操作等等non-idempotent operations）,他可以通过记录的唯一标志来区分出记录，这些唯一标志常常用来标记相关的应用实体，比如web文档等等。这些记录I/O的功能（除了移出复制记录），都是放在函数库中的，用于我们的应用程序，并且可应用于google里边的其它的文件接口实现。通过这些函数库，相同序列的记录，和一些重复填充，就可以提供给记录的读取者了。

## 系统交互 ##

我们设计的一个原则是尽量在所有操作中减少master的交互。在这个基础上，我们现在讨论客户端，master，chunkserver如何交互，实现数据的变动，原子的记录增加，以及快照。

### 令牌 和变化顺序 ###

变动操作是一种改变chunk内容或者chunk的原数据的操作，比如改写或者增加操作。每一个变动操作都要对所有的chunk的副本进行操作。我们用租约的方式来管理在不同副本中的一致的更改顺序。master首先为副本中的一个chunk分配一个令牌，这个副本就是primary副本。这个primary对所有对chunk更改进行序列化。所有的副本都需要根据这个primary的序列进行更改。这样，全局的更改顺序就是首先由master分配的chunk令牌顺序决定的，并且primary决定更改的序列。  
令牌机制设计用来最小化master的管理负载。一个令牌初始化的有效期是60秒。不过，随着chunk的更改操作的进行，primary可以请求延期并且一般情况下都会收到master的批准。这些延期请求并且批准延期都是通过在master和所有chunkserver之间的HeartBeat心跳消息来承载的。master有可能会在令牌超时前收回令牌（比如，master可能会终止正在改名的文件上的修改操作等等）。即使master和primary丢失了联系，master也可以很安全的在原始令牌超时后授予另外一个副本一个令牌。  
![这里写图片描述][20150318123959891]  
图2中，我们展示了这个更改的控制流过程：

1.  客户端向master请求当前chunk的令牌位置以及其他所有副本的位置。如果没有chunkserver持有这个chunk的令牌，则master选择一个chunk副本授权一个令牌（在图上没有标出）
2.  master给出应答，包括了primary和其他副本位置（secondary）标记。客户端cache这些数据，用于以后的变动。只有当primary不能访问或者primary返回它不再持有令牌的时候，客户端才需要重新联系master。
3.  客户端把数据发布给每一个副本。客户端可以以任意顺序发布这些数据。每一个chunkserver都在内部的LRU缓冲中cache这些数据，这些数据一旦被提交或者过期就会从缓冲中去掉。通过把数据流和控制流的分离，我们可以不考虑哪个chunkserver是primary，通过仔细调度基于网络传输的代价昂贵的数据流，优化整体的性能。3.2节进一步讨论了这个。
4.  当所有的副本都确认收到了数据，客户端发起一个写请求给primary。这个请求标记了早先发给所有副本的数据。primary分配一系列连续的序列号给所有的收到的变动请求，这个可能是从好多客户端收到的，这提供了必要的序列化。primary按照这个序列号顺序变动他自身本地的状态。
5.  prmary把写请求发布到所有的secondary副本。每一个secondary副本都依照和primary分配的相同的序列号顺序来进行变动的提交。
6.  secondary副本全部都给primary应答，表示他们都已经完成了这个操作。
7.  primary应答给客户端。如果有任何副本报告了任何错误，都需要报告给客户端。在发生错的情况下，写入者会在primary成功但是在secondary副本的某些机器上失败。（如果在primary失败，不会产生一个写入的序列号并且发布序列号）。客户端请求就是由失败的情况，并且修改的区域就有不一致的状态。我们的客户端代码是通过重试改动来处理这些错误。他可能会在从头开始重试前，在第三步到第7步尝试好几次。  
    如果应用的一个写入操作不止一个chunk或者是跨chunk的操作。GFS客户端代码把这个写入操作分解成为多个写入操作。每一个写操作都按照上边描述的控制流进行的，这些写操作可能和其他客户端的操作并发进行交叉存取和改写。因此，虽然因为每个操作都是对每个副本相同顺序完成的，对每一个副本都是一致的，但是大家共享操作的文件区块可能最后会包含不同客户端的小块。这就使得文件区虽然一致，但是是不确定的（如同2.7节讲述的一样）。

### 数据流 ###

我们把数据流和控制流分开，是为了更有效的利用网络资源。当控制流从客户端到primary，记者到所有的secondary副本，数据是通过一个精心选择的chunkserver链，在某种程度上像是管道线一样线形推送的。我们的目的是完全利用每一个机器的网络带宽，避免网络瓶颈以及高延时的连接，最小化同步数据的时间。  
为了挖掘每一个机器的网络带宽，数据是依据一个chunkserver链路进行线形推送的，而不是根据其他的拓扑结构推送的（比如树形）。因此，每一个机器的全部输出带宽都是用于尽可能快地传送数据，而不是在多个接收者之间进行分配。  
为了尽可能避免网络的瓶颈和高延时连接（比如inter-switch连接通常既是瓶颈延时也高），每一个机器都是把数据发送给在网络拓扑图上”最近”的尚未收到数据的机器。假设客户端把数据从chunkserver S1 发送到S4。他首先发送给最近的chunkserver，假设是S1。S1 把数据发送给S2到S4内的最近chunkserver，假设是S2。类似的，S2发送给S3或者S4，看谁更近，以此类推。我们的网络拓扑图是很简单的，所以，”距离”可以直接根据IP地址进行推算。  
最后，我们通过流水线操作基于TCP连接数据传输，来最大限度的减少延时。当一个chunkserver接收到一些数据，它就立刻开始转发。因为我们用的是全双工交换网络，所以流水线对于我们特别有用。立刻发送数据并不会降低接收数据的速率。抛开网络阻塞，传输B个字节到R个副本的理想时间是B/T+RL，T是网络吞吐量，L是两点之间的延时。我们网络连接时100M（T），L通常小于1毫秒。因此，1M通常理想情况下发布时间小于80ms。

### 原子纪录增加 ###

GFS提供了原子增加操作，叫做record append。在传统写操作中，客户端给定写入数据的偏移量。对同一个区域的并发写操作并没有序列化；这个区域可能会包含多个客户端的分段的数据。在record append，客户端只是给出数据，GFS在其指定的一个偏移量上，原子化的保证起码增加一次（也就是说，保证在一个连续的字节序内），并且把这个偏移量返回给客户端。这个很类似当多个写者并发操作的情况下，unix下没有竞争条件的O\_APPEND写文件操作。  
纪录添加模式大量在我们的应用中是用，在我们的分布式应用情况下，大量的客户端分布在不同的机器上，同时向同一个文件进行追加纪录得操作。客户端需要额外的复杂的代价高昂的同步操作，比如如果按照传统的写操作，就基于一个分布的锁管理。在我们的工作量下，这样的文件经常需要为多生产者/单消费者的队列或者包含从多个客户端合并结果集的操作。  
纪录增加也属于一种改动操作，并且遵循3.1 描述的控制流，它在primary上只有一点额外的逻辑操作。客户端把数据分布给文件最后一个chunk所在的每个副本。于是，他把请求发送给primary。primary检查看看是否这些对当前chunk的增加是否会导致chunk超过最大大小（64M）。如果超过了，它就把chunk填写到最大大小，告诉secondary也跟着填写到最大，并且返回给客户端表示这个操作需要在下一个chunk重试。（纪录增加操作严格限制在1/4最大chunk大小，来保证最坏的分段情况下还是可以接受的）。如果纪录可以在最大大小内存放，这也是常见的情况，primary就增加这个纪录到它自己的副本，告诉其他secondary副本也在相同的偏移量开始写，并且最终返回成功给客户端。  
如果任意一个副本报告纪录增加失败，客户端就重新尝试这个操作。因此，副本中，对于相同chunk可能包含不同的数据，这些不同数据包括了相同纪录的完整或者部分的重复纪录。GFS并不保证所有的副本都是byte级别相等的。它只保证数据时基于原子级别至少写入一次。这个特性是从对操作开始到成功完成的一个简单研究得出的，数据必须写在所有副本的相同chunk的相同偏移量写入。此外，所有的副本都必须起码和纪录结束点等长，并且因此即使另外一个副本成了primary，所有后续的纪录都会被分配在一个较高的偏移量或者在另外一个chunk中。在我们一致性的保证中，成功追加纪录操作写入他们的数据的区域是确定的（因此也是一致的），但是追加纪录与纪录之间的区域却是不一致的（因此也使不确定的）。我们的应用可以处理这些不一致的区域，我们在2.7.2中有所讨论。

### 快照 ###

快照操作在尽量不影响正在发生的变动的情况下，几乎即时产生一个文件或者目录树（”源”）。我们的用户是用快照来迅速创建举行数据集的一个分支拷贝（经常还有拷贝的拷贝，递归拷贝），或者在提交变动前做一个当前状态的checkpoint，这样可以使得接下来的commit或者回滚容易一点。  
如同AFS\[5\],我们用标准的copy-on-write(写时拷贝)的技术来实现快照。当master收到一个快照请求，他首先收回所有的相关快照文件中发布出去的chunk令牌。这确保了后续的对chunk的写入都会产生一个和master的交互来寻找令牌持有者。这使得master可以在产生写入操作的时候先产生一个chunk的副本。  
当令牌收回或者已经过期以后，master把这个操作纪录到磁盘。接着他把这个log纪录通过复制源文件或者目录树的元数据的方式，提交到内存状态中。新创建的快照文件指向和源文件相同的chunk。  
等客户端在快照操作后，首次吸入一个chunk C的时候，他发送请求给master来寻找当前的令牌持有者。master发现这个chunk C的引用次数超过1。它就推迟应答给客户端，并且找一个新的chunk来处理C’。接着向每一个包含当前C副本的chunk服务器创建一个新chunk C’。通过在和原始chunk有相同的chunkserver上新的chunk，我们确保数据可以进行本地拷贝，而不是通过网络（本地硬盘速度大概是100M网络连接速度的3倍）。从这点开始，对于请求的后续处理就和处理其他chunk没有什么不同了，master分配一个令牌给新的chunk C’，并且回答给客户端，这样客户端可以正常的写操作，不需要知道chunk是刚从现存的chunk上创建的。

## master操作 ##

master执行所有的namespace的操作。另外，他管理系统中所有chunk的副本；他决定chunk的放置策略，穿件新的chunk及其副本，以及相关的多个系统级别的操作来保持chunk有好几个副本，平衡所有chunkserver之间的附在，回收未使用的存储。我们现在讨论每一个小节。

### namespace管理及锁定 ###

很多master的操作都可能执行比较长的时间；比如，一个快照操作可能要回收快照所覆盖的所有chunk所在的chunkserver的令牌等等。我们不希望这个操作执行的同时，阻碍其他master的操作。因此，我们允许多个操作同时进行，并且使用基于namespace的区域的锁来保证必须要得序列化。  
不同于很多传统的文件系统，GFS没有一个per-directory数据结果列出了所有在此目录下的文件，也不支持对同一个文件或者目录的别名（比如，unix系统下的硬连接或者符号连接）。GFS从逻辑上是通过一个查找路径名到元数据映射表的方式来体现namespace的。通过前缀压缩，这个表可以有效地在内存中存放。每一个namespace树种的节点（不论是绝对文件名还是绝对目录名），都有一个相关的读写锁。  
每一个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-like的数据结构。在名字上的读锁已经足够来保护父目录不被删除。  
这种锁机制带来一个好处就是在同一个目录下允许并发改动。比如，在同一个目录下的多个文件创建可以并行执行；每一个要求一个在目录名上的读锁，并且要求在一个文件名上的写锁。在目录名上的读锁足以防止目录被删除，改名或者快照。在文件名上的写锁序列化对两次同一文件的创建操作。  
因为namespace可以有很多的节点，读写锁对象是滞后分配以及一旦没有使用就立刻删除的。并且，锁是基于一个相同的总顺序来分配的，这样放置死锁：他们是首先根据namespace树种的级别顺序，以及相同级别下根据字典顺序进行分配的。

### 副本位置 ###

GFS集群是在不止一个级别上的多级别的高度分布的系统。通常由好几百台分布在很多机架上的chunkserver组成。这些chunkserver可能被相同或者不同的机架的几百台客户端轮流访问。两个机架上的两台机器可能会跨越不止一个网络交换机。此外，机架的入口带宽或者出口带宽往往会比在机架内的机器聚合带宽要小。多级别的分布凸现了一个独特的要求，为了可扩展性，可靠性，以及可用性要把数据进行分布。  
chunk复本存放机制有两个目的：最大限度的保证数据的可靠和可用，并且最大限度的利用网络带宽。对于两者来说，仅仅在机器之间进行复本的复制时不足够的，它只保证了磁盘或者机器的实效，以及每一个机器的网络带宽的使用。我们必须也在机架之间进行chunk的复制。这就保证了当整个机架都损坏的时候（或者掉线的时候），对于任意一个chunk来说，都有一些副本依旧有效（比如，由于共享资源的失效，例如网络交换机或者电源故障，导致机架不可用）。这也意味着网络冲突的减轻，尤其是对于读取操作来说，对于一个chunk的读取来说，使用的是每一个机架内部的聚合带宽。换句话说，会增加跨越各个机架的写流量，这个是我们相比较愿意承受的代价。

### 创建，重新复制，重新均衡 ###

有三个原因需要创建chunk的副本：chunk的创建，chunk的重新复制，chunk的重新均衡。  
当master创建了一个chunk，它会选择放置初始化空白副本的位置。它会考虑几个因素：(1)我们希望新副本所在的chunkserver有着低于平均水平的磁盘空间利用率。随着时间的推进，chunkserver上的磁盘利用率会趋于均匀。(2)我们希望限制每一个chunkserver上的”最近”创建的数量。虽然创建操作本身的负载很轻，但是它却意味着随后立刻又很重的写操作，因为chunk是因为要写东西才会创建，并且在我们的写一次读多次的工作量下，他们通常完成写操作以后，他们实际上就成为只读的了。(3)如同上边讨论得这样，我们希望把副本跨越机架。  
当chunk的副本数量小于一个用户指定的数量后，master会立刻尝试重新复制一个chunk副本。这有可能由好几种原因引起：比如chunkserver失效，或者chunkserver报告自己的副本损坏了，或者它的某一个硬盘故障，或者增加了副本数量等等。每一个需要重新复制的chunk于是根据几个因素进行优先级分布。一个是与副本指定数量差距决定优先级。例如，我们对于一个差了两个副本的chunk给定一个高优先级，而给一个只差一个副本的chunk一个较低的优先级。此外，我们倾向于首先重新复制活跃文件的chunk，而不是复制刚刚被删掉的文件的副本（参见4.4）。最后，为了减少失效的chunk对正在运行应用的影响，我们提高妨碍客户端进程的chunk副本的优先级。  
master选择最高优先级的chunk并且通过通知一些chunkserver从现有副本上直接复制这个chunk数据的方式来”克隆”这个chunk。新的副本是用和他们创建时相同的策略来选择存放位置的：均衡磁盘利用率，在单个chunkserver上限制活跃克隆操作，在机架间进行副本的分布。  
为了防止克隆导致的带宽消耗大于客户端的带宽消耗，master限制集群上和每个chunkserver上的活跃的克隆操作。此外，每个chunkserver通过限制对源chunkserver的克隆读取请求来限制克隆操作的带宽开销。  
最后，master定期重新进行均衡副本：他检查当前的副本分布情况，并且把副本调整到更好的磁盘和负载分布。并且通过这个步骤，master逐渐渗透使用一个新的chunkserver，而不是立刻大量分布新chunk给新的chunkserver从而导致新chunkserver过载。选定副本分布的策略和上边讨论的策略类似。此外，master必须决定哪个副本需要移动。总的来说，它会倾向于移动分布在低于平均磁盘剩余空间chunkserver上的chunk，这样会平衡磁盘空间使用。

### 垃圾回收 ###

当文件被删除以后，GFS并不立刻要求归还可用的物理存储。它是通过滞后的基于文件和chunk级别的普通垃圾回收机制来完成的。我们发现这样可以使得系统更加简单和可靠。

#### 机制 ####

当应用删除了一个文件，master像记录其他变动一样，立刻记录这个删除操作。不过不同于立刻回收资源，这个文件仅仅是改名称为一个隐藏的名字，并且包含了一个删除时戳。在master的常规的文件系统namespace的检查中，他会移出这些超过3天隐藏删除文件（这个3天是可以配置的）。直到此时，文件依旧可以通过新的，特别的名字读取，并且可以通过改名来恢复成为未删除状态。当隐藏文件从namespace删除后，它在内存的元数据也随之删除。这个会影响他所指向的各个chunk。  
在对chunk的namespace的常规扫描中，master识别chunk孤点（就是说，没有被任何文件所指向）并且删除这些孤点的元数据。在chunkserver和master的常规心跳消息中，每一个chunkserver都报告自己的chunk集合，并且master回复在master的元数据中已经不存在的chunk标记。chunkserver随即释放和删除这些chunk的副本。

#### 讨论 ####

虽然分布式的垃圾回收是一个艰巨的问题，在程序设计的时候需要复杂的解决，但是在我们的系统中却是比较简单的。我们可以轻易辨别出对一个chunk的全部引用：它们都唯一保存在master的文件-chunk影射表中。我们也可以容易辨别所有的chunk副本：它们是在各个chunkserver上的指定目录下的linux文件。所有不被master知道的副本就是”垃圾”。  
垃圾回收比较类似提供几种便利删除机制的存储回收。首先，他在一个由非可靠节点组成的超大分布式系统中可靠而简单的运行。chunk的创建在某些chunkserver可以成功但是在某些chunkserver却会失败，这样导致master不知道的某些副本。副本删除消息可能会丢失，master被迫记住并且重发这些失败的副本删除消息，不仅仅是它自己的副本删除消息，也包含chunkserver的。垃圾回收机制提供了一个统一的可靠的方式来清除未知的副本，这种机制非常有用。其次，他把存储的回收合并到常规的master后台操作，如同常规的对namespace的扫描，以及对chunkserver的握手。因此，它是作为批处理的，处理开销也是分批地。另外，这仅仅是当master的负载相对较轻的时候进行的。master可以更快的相应客户的请求，不过这需要花时间来关注客户的请求（所以对垃圾的回收时在负载较轻的情况下执行的）。第三，在存储回收的延后回收也提供了某种程度的由于网络故障导致的不可回收的删除的恢复。  
在我们的经验中，主要的缺点就是当存储紧张的时候，滞后删除会导致阻碍我们尝试调整磁盘使用情况的效果。应用程序重复创建和删除临时文件可能不会正确重用存储。我们通过如果一个已经删除了的文件再次删除的操作，来加速存储回收，部分解决这个问题。我们也允许用户对于不同的namespace部分，使用不同的复制和回收策略。例如，用户可以指定所有的在某目录树下的文件chunk的保存没有副本，任何删除的文件立刻并且不可撤销的从文件系统状态中删除。

### 过期副本删除 ###

chunk副本可能会因为chunkserver失效期间丢失了对chunk的变动而导致过期。对于每一个chunk，master保持一个chunk的版本号码来区分最新的和过期的副本。  
无论何时master为一个chunk颁发一个令牌，他都增加chunk的版本号码并且通知最新的副本。master和这些副本在他们的持久化状态中都记录最新的版本号码。这在任何客户端被通知前发生，并且因此在开始对这个chunk写之前发生。如果另一个副本当前不在线，那么他的chunk的版本号码就不会改变。当这个chunkserver重新启动，并且向master报告它的chunk以及相关版本号码的时候，master会根据版本号码来检查出这个chunkserver有一个过期的副本。如果master发现一个更高版本号码的chunk，master会认为他在颁布令牌的时候失败了，于是会取较高的版本号来作为最新的chunk。  
master通过正常的垃圾回收机制来删除过期的副本。在删除之前，它需要确认在它给所有客户端的chunk信息请求的应答中，都没有包含这个过期的副本。作为另外一个安全控制，master采用了chunk版本号，当它告诉客户端那个chunkserver有这个chunk的令牌，或者指使chunkserver从另一个chunkserver去克隆一个chunk的副本的时候，都会采用版本号来控制。客户端或者chunkserver会在执行操作前检查版本号，确保操作的数据都是最新的数据。

## 容错和故障诊断 ##

我们遇到的最大难题就是设计的系统会有经常性的节点故障。节点数量和质量导致了这个问题还不是意外情况：我们不能完全相信机器，也不能相信磁盘。节点失效可以使得系统不可用，或者更糟糕的是会损坏数据。这里我们讨论我们怎样解决这样的难题，以及我们构建在系统内部的工具用来侦测系统不可避免的会存在的问题。

### 高可用性 ###

在一个GFS集群里，会有好几百台服务器，在任何时候都可能会有机器不可用。我们用两条很简单有效的策略来保证整体上的系统高可用性：迅速的恢复机制以及副本机制。

#### 快速恢复机制 ####

master和chunkserver都设计成为本地保存状态，并且无论他们正常或者异常退出都可以在几秒钟之内启动。实际上，我们不用讨论正常和异常退出；服务器通常是直接杀掉进程来关机的。客户端和其他服务器在他们正在发起的请求上会获得一个超时，感觉一点颠簸，他们会重新尝试连接这个重新启动的服务器，并且重试这个请求。6.2.2节讲述了启动过程。

#### chunk副本机制 ####

如同早先讨论过的，每一个chunk都在不同的机架上的不同chunkserver上有副本。用户可以对不同的文件namespace指定不同的复制级别。缺省是3个。master根据需要克隆现有的副本，并且维持当chunkserver 掉线的时候，每一个chunk都有完善的副本，以及master通过checksum检查来删除损坏的副本（5.2节）。虽然复制机制对我们来说已经很有效了，我们依旧在探索其他的跨机器的冗余机制，比如对于我们日益增长的只读存储需要，设计奇偶或者其他标记代码。因为我们的网络负载受控于增加性质的修改以及大量的读取，很少有随机的写，所以我们可以预期我们可以克服挑战，在我们的很松散的系统上，设计和实现更复杂的冗余机制。

#### master的复制 ####

master的状态基于可靠性的理由也要做复制。master的所有操作都是基于log和checkpoint的，这些log和checkpoint将被复制到多个机器上。一个对master状态的修改操作只有当所有远程master副本提交成功，并且也提交到了本地磁盘的时候，才认为是已经提交了。简单说来，一个master的进程负责所有的改动，包括后台的服务，比如垃圾回收等等内部活动。当它失效的时候，几乎可以立刻启动。如果机器或者磁盘失效，GFS外部的监控机制在别的地方包括操作副本log的机器上启动一个新的master进程。客户端只用规范的名字来访问master（比如gfs-test）,这个市一个DNS的别名，可以由于master改动到别的机器上执行而更改实际地点。  
进一步说，master的”影子进程”，提供了对文件系统的只读操作，即使当当前的master失效的时候也是只读的。他们是影子进程，并非镜像进程，他们可能会比primary master稍慢一拍，通常是不到一秒钟。这些进程增强了对于那些并不是很活跃修改的文件的读取能力，或者对那些读取脏数据也无所谓的应用来说，提高了读取性能。实际上，因为文件内容是从chunkserver上读取的，应永不不能发现文件内容的过期。什么原因会导致在一个很小的时间窗内文件的元数据会过期呢，目录内容或者访问控制信息的变动会导致小时间窗内元数据过期。  
为了保证master的影子进程能维持最新状态，它从当前的操作log的副本中读取，并且根据与primary完全相同顺序来更改内部的数据结构。如同primary一样，他在启动的时候从chunkserver拉数据（并且启动以后定期拉），这些数据包括了chunk的副本位置信息，并且也会和chunkserver进行握手来确定他们的状态。它从primary master上只处理因为primary决定创建或者删除副本导致的副本位置更新结果。

### 数据完整性 ###

每一个chunkserver都是用checksum来检查保存数据的完整性。通常一个GFS集群都有好几百台机器以及几千块硬盘，磁盘损坏是很经常的事情，在数据的读写中经常出现数据损坏（7节讲了一种原因）。我们可以通过别的chunk副本来解决这个问题，但是如果跨越chunkserver比较这个chunk的内容来决定是否损坏就很不实际。进一步说，允许不同副本的存在;在GFS更改操作的语义上，特别是早先讨论过的原子纪录增加的情况下，并不保证byte级别的副本相同。因此，每一个chunkserver上必须独立的效验自己的副本的完整性，并且自己管理checksum。  
我们把一个chunk分成64k的块。每一个都有相对应的32位的checksum。就像其他的元数据一样，checksum是在内存中保存的，并且通过分别记录用户数据来持久化保存。  
对于读操作来说，在给客户端或者chunkserver读者返回数据之前，chunkserver效验要被读取的数据所在块的checksum。因此chunkserver不会把错误带给其他设备。如果一个块的checksum不正确，chunkserver会给请求者一个错误，并且告知master这个错误。收到这个应答之后，请求者应当从其他副本读取这个数据，master也会安排从其他副本来做克隆。当一个新的副本就绪后，master会指挥刚才报错的chunkserver删掉它刚才错误的副本。  
checksum对于读取性能来说，在几方面有点影响。因为大部分的读取操作都分布在好几个block上，我们只需要额外的多读取一小部分相关数据进行checksum检查。GFS客户端代码通过每次把读取操作都对齐在block边界上，来进一步减少了这些额外的读取。此外，在chunkserver上的chunksum的查找和比较不需要附加的I/O，checksum的计算可以和I/O操作同时进行。  
checksum的计算是针对添加到chunk尾部的写入操作作了高强度的优化（和改写现有数据不同），因为它们显然占据主要工作任务。我们增量更新关于最后block的checksum部分，并且计算添加操作导致的新的checksum block部分。即使是某一个checksum块已经损坏了，但是我们在写得时候并不立刻检查，新的checksum值也不会和已有数据吻合，下次对这个block的读取的时候，会检查出这个损坏的block。  
另一方面，如果写操作基于一个已有的chunk（而不是在最后追加），我们必须读取和效验被写得第一个和最后一个block，然后再作写操作，最后计算和写入新的checksum。如果我们不效验第一个和最后一个被写得block，那么新的checksum可能会隐藏没有改写区域的损坏部分。  
在chunkserver空闲的时候，他扫描和效验每一个非活动的chunk的内容。这使得我们能够检查不常用的chunk块的完整性。一旦发现这样的块有损坏，master可以创建一个新的正确的副本，然后把这个损坏的副本删除。这个机制防止了非活动的块损坏的时候，master还以为这些非活动块都已经有了足够多的副本。

### 诊断工具 ###

详细的扩展诊断日志对于问题的发现和调试解决，以及性能分析来说，有着不可估量的作用，并且记录详细的扩展诊断日志只需要一点小小的开销。如果没有日志，很难理解偶发的，不能重现的机器间的交互作用。GFS服务器产生诊断日志，记录下很多关键时间（比如chunkserver启动和停止等等），以及所有的RPC请求和应答。这些诊断日志可以在不影响系统正确性的前提下删除。不过，如果磁盘空间允许，我们希望尽量保留这些日志信息。  
RPC日志包括了在网络上传输的除了被操作的文件数据以外的请求和应答细节。通过匹配和比较不同机器上的RPC请求和应答，我们可以重构整个的交互历史，这样可以诊断问题。这些日志同样用于追踪负载测试以及性能分析。  
记录日志对于性能的影响来说是比较小的（相比较而言产生的效果却是巨大的），因为日志是顺序的并且是异步的。最新的时间是在内存中保留，并且可以作持续的在线监控。

## 度量 ##

在本节，我们通过几个小型的bechmark来演示GFS架构和实现上的性能瓶颈，并且展示了一些再GOOGLE内使用的真实地集群的性能数据。

### 小型benchmark ###

我们在一个有一个master，两个master副本，16个chunkserver，16个客户端的GFS集群上进行的性能测试。这个配置是用于便于测试使用的。实际上的集群通常有好几百台chunkserver和几百台客户端组成。  
所有的机器都是有双1.4G PIII处理器，2GB内存，两个80GB 5400转硬盘，一个100M全双工网卡（连接到HP2524交换机）组成。全部19台GFS服务器都是连接到一个交换机上的，16台客户端连接到另一个交换机。两台交换机之间是用的1G链路连接的。

#### 读取 ####

N个客户端并行从文件系统读取。每一个客户端从320GB文件集合中，读取随机选取的4M区域。重复读取256次，每一个客户端最终读取1GB数据。chunkserver总共有32GB内存，这样我们预期有最多10%的Linux buffer cache命中率。我们的结果应当和冷cache的结果一致。  
图三（a）展示了Nge客户端合计读取速度，以及它的理论上限。合计的理论上限是两个交换机之间的1GB链路饱和的情况下达到，就是125MB/s的速度，或者当客户端的100M网卡饱和的情况下的每客户端12.5MB/s的速度。当只有一个客户端读取的时候，观测到的读取速度是10MB/s，或者80%客户端的限制。16个客户端的合计读取速度达到了94MB/s，大约是75%的125MB/s的理论限制。由80%降低到75%的原因是由于读取者的增多，导致多个读取者同时从一个相同chunkserver读取得可能性增加，导致的读取性能下降。

#### 写入 ####

N个客户端同时向N个不同的文件写入。每一个客户端每次写入1MB，总共写入1GB的数据到一个新的文件。合计写入速度以及它的理论上限在图三(b)中展示。理论限制是67MB/s，是因为我们需要把每一个字节写入3个chunkserver，每个都有12.5MB/s的输入连接。  
每一个客户端的写入速度是6.3MB/s,差不多是一般的限制主要原因是我们的网络协议栈。它和我们使用的推送数据到chunk副本的流水线机制的交互并不是很好。再把数据从一个副本传输到另一个副本的延时导致了整个写入速度的降低。16个客户端的合计写入速度差不多是35MB/s（或者2.2MB/s每客户端），差不多是理论极限的一般。和读取情况比较类似，这样的情况多半发生于多个客户端同步写入同一个chunkserver时导致的性能下降。此外，由于16个写者要比16个读者更容易产生冲突，这是因为每一个写入要写三份副本的原因。  
写入速度比我们预期的要慢一点。在实际情况下，这并不是一个大问题，因为即使在单个客户端上能够感受到延时，他也不会对大量客户端的情况下，对整个写入带宽造成明显的影响。

#### 记录增加 ####

图三（c）展示了记录增加的性能。N各客户端同时对一个文件进行增加记录。性能是受到保存文件的最后一个chunk的chunkserver的带宽限制，而与客户端的数量无关。他从单个客户端的6.0MB/s降低到16个客户端的4.8MB/s,主要是由于不同客户端的网络拥塞以及网络传输速度的不同导致的。  
我们的应用多属于同步产生多个这样的文件。换句话说，N个客户端对M个共享文件同步增加，N和M都是数十或者数百。因此，在我们实验中出现的chunkserver网络拥塞就在实际的情况下就不是一个问题，因为一个客户端可以在chunkserver对另一个文件忙得时候进行写入文件的操作。

### 实际的集群 ###

我们现在通过Google的两个有代表性的集群来检查一下。集群A用于上百个工程师的研发。通常这个集群上的任务都是由人工发起的，运行好几个小时的任务。读取范围从好几M到好几TB数据，分析和处理数据，并且向集群写回结果。集群B是当前的生产数据处理集群。它上面的应用通常需要持续处理，并且产生和处理上TB的数据集，很少需要人工干预。在两个集群下，单个“task”意味着包含在很多机器上进行的很多读取和写入多个文件的并发进程。  
![这里写图片描述][20150318124538780]

#### 存储 ####

如同上表中描述的，两个集群都有上百台chunkserver，支持很多TB的硬盘空间，几乎不会满。”已用空间”包含了所有的chunk副本。一般来说所有的文件都有三个副本。因此，集群实际上各存储了18TB和52TB的文件数据。  
两个集群都有相近的文件数目，虽然集群B有着很大的死文件数量，也就是说文件被删掉了或者用新版本代替了，而集群还没有来得及清理。并且应为文件比较大，集群B也有比较多的chunk数目。

#### 元数据 ####

chunkserver一共保存了十几个GB的元数据，主要是用户数据的64KB block的checksum数据。其他在chunkserver上保存的元数据是chunk的版本号，在4.5节有讲述。  
在master上保存的元数据就小多了，只有数十MB，或者说平均每个文件100字节。这和我们的预期的一样，master的内存在实际上并不会是系统容量的限制瓶颈。大部分的文件的元数据都是文件名，而且是用的前缀压缩模式保存的。其他的元数据包括了文件的所有者和权限，以及文件到chunk的应设关系，以及每一个chunk的当前版本号。此外，每一个chunk我们都保存当前的副本位置以及对其的引用数字，用于实现写时拷贝\[copy-on-write，3.4\]。  
每一个单独的服务器，chunkserver或者master，都只有50到100MB的元数据。因此恢复时很快：只需要几秒钟时间从磁盘读取这些数据就可以了响应请求了。不过，master会慢一点-通常30-60秒-它需要从所有的chunkserver获取当前chunk位置信息。

#### 读写速率 ####

表三显示了不同时段的读写速率。两个集群都采样了一周的时间。（集群最近因为升级新版本的GFS而重新启动了）。重新启动后，平均写入速率小雨30MB/s。当我们在采样期间，集群B在峰值写入速度达到了100MB/s，并且因为产生三个副本的原因，它产生了300MB/s的网络负载。  
![这里写图片描述][20150318124506621]  
图三：合计吞吐量：上边的曲线显示了我们网络拓扑下的合计理论吞吐量上限。下边的曲线显示了观测到的吞吐量。这个曲线有着95%的可靠性，因为有时候测量会不够精确。  
![这里写图片描述][20150318124554575]  
表三：两个GFS集群的性能表  
读取速率要比写入速率高很多。总共的负载包含的读取要远大于包含的写入，这符合我们的预期。两个集群都处于中等的读取压力。特别是，集群1在一周内都维持了580MB/s的读取速度。他的网络支持750MB/s，因此它很有效的利用了资源。集群B可以支持峰值读取速度是1300MB/s，它的应用只用到了380MB/s

#### master的负载 ####

表三也包括了对master的操作率，大概是每秒200到500个操作。master可以轻松应付这样的访问速率，因此这不是主要的负载瓶颈。  
在早期版本的GFS，master偶然会成为负载瓶颈。它花费了大量的时间顺序扫描大型目录（包含了数十万文件）来查找某一个文件。因此我们改了一下master的数据结构，这样支持高效的二进制的namespace检索。现在它可以支持每秒很多个上千个文件的访问。如果需要，我们还可以使用名字查找cache在namespace的数据结构来进一步提高性能。

#### 恢复时间 ####

在某一个chunkserver失效以后，其上的chunk可能会低于副本数量，这样于是就需要把这些chunk进行复制来达到相应的副本级别。这个操作所花的时间取决于资源的数量。在我们一个试验中，我们把集群B上编的一个chunkserver删掉。这个chunkserver上有大概15000个chunk，共计600GB数据。为了减少对正在运行的应用程序的影响，以及修正调度决策，我们缺省参数是限制这个集群中的并发克隆数量是91个（总chunkserver数量的40%），每一个克隆操作可以展到6.25MB/s（50mbps）的带宽。所有的chunk在23.2分钟内恢复了，大约有效复制速率是440MB/s。  
在另外一个是严重，我们杀掉了两个chunkserver，每个chunkserver大概有16000个chunk并且包含大概660GB数据。这种双重故障导致了266个chunk只有单个副本。这些266个chunk于是克隆操作就提升到比较高的优先级，并且至少要在2分钟内恢复到起码两个副本，这样就可以能让系统恢复到容错另一个chunkserver失效的情况。

### 处理能力细目 ###

在本节中，我们对比展示了两个GFS集群的工作量的细目情况。这两个集群和6.2中应用的集群不同。集群X是用于研发部分的，集群Y是生产数据处理的。

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

我们考虑得处理能力只包含客户端发起的原始请求，这些请求代表了整个我们应用程序产生的对文件系统的工作量。处理能力中不包括处理客户请求所引起的中间请求，以及内部的后台应用，比如转发写请求或者重新均衡chunk分布等等。  
I/O操作的统计是基于GFS服务器的实际RPC请求log重构的。例如，GFS客户端代码可能把一个读操作分解成为多个RPC调用，这样来增加并发度，我们从这些RPC来推断原始的读取请求。因为我们的操作模式是高度程式化的，所以我们可以把任何不符合的数据认为是误差。应用程序记录的日志可能会稍微对数据的精确性有点帮助，但是基本上不可能在上千个客户端上重新编译和重新运行应用程序，并且从这些机器上获得这些日志结果也是很麻烦的事情。  
我们应当避免从我们的负载中进行过度归纳和推广。因为Google完全控制GFS和其上的应用程序，并且应用程序也是因为GFS而特意做调优，并且反过来说，GFS也是特意为这些应用而设计的。这些相互影响也可能在通用的应用和文件系统中，但是在我们的例子中更显著而已。

#### chunkserver的负载 ####

![表4：操作大小百分比细目（%）。对于读操作，大小是实际读取的数据和传送的数据，而不是请求的数据量。][4]

![表5：操作大小字节传输细目表（%）。对于读取来说，这个大小是实际读取的并且传输的，而不是请求读取的数量。两个不同点是如果读取尝试读超过文件结束的大小，那么实际读取大小就不是试图读取的大小，尝试读取超过文件结束的大小这样的操作在我们的负载中并不常见。][5]  
表4显示了操作大小的分布。读取操作的大小体现了一个双峰分布。小型的读取请求（小于64KB），是从面向查找的客户端发起的，用于在巨量文件中查找小块数据的。大型的读取请求（大于512KB）是来自于对整个文件的序列读取。  
在集群Y上，没有读到任何数据的请求占了相当的一部分。在我们的应用中，尤其是在生产系统中，经常使用文件作为生产者-消费者队列。生产者并行添加到文件，同时消费者从文件读取。某些情况下，消费者超过了生产者的速度的时候，就会出现没有读到任何数据的情况。集群X这样的情况出现的比较少见，这是因为通常集群X用于短期的数据分析任务，而不是长期的分布是应用。  
写请求的大小也同样体现了双峰分布。大型写入（超过256KB）通常由写入者的重要缓存操作产生。写入者缓存较小的数据，checkpoint或者同步点，或者小型写入产生的小数据（小于64KB）。至于记录增加操作来说，集群Y看起来再大型记录增加方面要比集群X占百分比多，这是因为我们的实用集群Y的生产系统，是为GFS做了更极端的调优。  
表5显示了不同大小的操作请求中的数据传输总数。多于所有操作来说，较大的操作（超过256KB）占据了主要的传输量，较小的读取（小于64KB）占据的传输量比较小，但是却是读取操作的相当一部分，这是因为随即寻找的工作量导致的。

#### 增加纪录与写操作 ####

纪录增加是在我们的应用系统中大量使用的。对于集群X来说，增加纪录写操作和普通写操作的比例按照字节比试108:1,按照操作比试8:1。对于集群Y来说，我们的生产系统的比例是3.7:1和2.5:1。进一步说，这个比例说明在我们的两个集群上，纪录增加都比写操作要大。对于集群X来说，在测量过程中，整体纪录增加占据的比率相对算小的，因此结果受到一个或者两个应用的某些特定的buffer大小的影响。  
如同我们预期的，我们数据操作负载是受到纪录增加的影像而不是是改写的影响。我们测量第一个副本的数据改写情况。这近似于一个客户端故意覆盖刚刚写入的数据情况，而不是增加新数据的情况。对于集群X来说，改写操作在所占据字节上小于0.0001%，并且在所占据操作上小于0.0003%。对于集群Y，这个比率都是0.05%。虽然这只是某一片断的情况，依旧是高于我们的预期。这是由于大部分这些覆盖写，是因为客户端发生错误或者超时以后重试的情况。这本质上不算作负载量，而是重试机制的一个结果。

#### master的负载 ####

![表6：master请求类型明细（%）][6_master]  
表6显示了master上的请求类型区分的明细表。大部分的请求都是询问chunk位置的（FindLocation）和对读取和颁布令牌信息（FindLease-Locker）以及对数据更新的。  
集群X和Y在删除请求上有着显著的不同，因为集群Y存储了生产数据集，会定义重新产生和用新的版本替换。这些不同点也在Open请求中有所体现，因为一个文件的旧版本可能随着新打开改写而默认删除（如同unix的open操作中的”w”模式）。  
FindMatchingFiles是一个模式匹配请求，支持”ls”以及类似文件系统的操作。它不同于其他master上的请求，他可能会检索namespace的大部分内容，因此可能会非常耗时。集群Y这种操作要多一些音位自动化数据处理进程需要尝试检查文件系统的各个部分来试图理解整体的进程状态。与之不同的是，集群X的应用程序更加倾向于单独的用户控制，通常预先知道自己所需要使用的全部文件名。

## 经验 ##

在建造和部署GFS的过程中，我们经历了不少问题，某些是操作上的，某些是技术上的  
起初，我们构思GFS用于我们生产系统的后端文件系统。随着时间推移，增加了对研发任务的支持。于是开始增加一些小的功能比如权限和配额，到现在全面支持了这些内容。因为我们生产系统是严格受控的，但是用户层却不是这样的。于是我们研发了更多的架构支持用于防止用户间的干扰。  
我们最大的问题是磁盘和linux相关的问题。很多磁盘都声称他们支持只要是IDE的linux驱动都可以，但是实际上却不是，实际上他们只支持最新的驱动。因为协议版本很接近，所以大部分磁盘都可以用，但是偶尔也会由于这些不匹配导致驱动和核心对于驱动器的状态误判。这会导致kernel无知觉的丢失数据。这些问题促使我们是用checksum来检查数据的损坏，同时我们也修改了核心来处理这些协议上的不匹配。  
早先情况下，我们在linux2.2核心上有些问题，出在fsync（）的效率问题。它的效率与文件的大小有关而不是和文件修改部分的大小有关。这在我们的操作log过长的时候就会有问题，尤其是在我们尚未实现checkpoint的时候。我们费了很大的力气用同步写操作解决这个问题，最后移植到linux2.4核心上。  
另一个linux问题时单个写者-读者锁，就是说在某一个地址空间的任意一个线程都必须在从磁盘载入（page in读者锁）的时候先hold住,或者在mmap()调用（写者锁）的时候改写地址空间。我们发现在我们系统负载很轻的情况下有偶尔超时的情况，并且费了好大的力气去寻找资源的瓶颈或者硬件的问题。终于，我们发现这是单个lock，在磁盘线程交换以前的映射数据到磁盘的时候，锁住了当前的网络线程把新数据map到内存。因为我们主要受限于网络接口，而不是内存copy的带宽，所以，我们用pread()替换掉mmap，用了一个额外的copy动作来解决这个问题。  
尽管偶尔还是有问题，linux的源代码还是使得沃恩能够迅速定位并且理解系统的行为。在适当的时候，我们会改进内核并且和公开源码组织共享这些改动。

## 相关工作 ##

如同其他大型分布式文件系统比如AFS\[5\]一样，GFS提供了一个与位置无关的namespace，使得数据可以根据负载或者容错的原因在不同位置进行移动。但是不同于AFS的是，GFS把文件的数据分布到存储服务器上的方式，更类似Xfs\[1\]和Swift\[3\]，这是为了提高整体性能以及增强容错能力。  
由于磁盘相对来说比较便宜，以及副本方式比传统的RAID\[9\]简单许多，GFS目前只使用副本方式来进行冗余，因此要比xFS或者Swift花费更多的存储。  
与AFS，xFS,Frangipani\[12\]，以及Intermezzo\[6\]不同的是，GFS并没有在文件系统层面提供cache机制。我们的主要工作量在单个应用执行的时候几乎不会有重用的可能，因为他们无论是流式读取还是随机寻找，都是对大型数据集的操作。  
某些分布式文件系统比如Frangipani,xFS,Minnesota’s GFS\[11\],GPFS\[10\]，去掉了中心服务器，并且依赖于分布式算法来保证一致性和管理性。我们选择了采用中心服务器的做法是为了简化设计，增加可靠性和扩展能力。尤其是，一个中心master，由于它已经有了几乎所有的相关chunk信息以及控制chunk信息的能力，它可以非常简化实现传统的chunk分布和副本机制。我们通过减少master的状态量大小（元数据大小）以及全面分布master的状态到不同的机器上来保证容错能力。扩展能力和高可用性（对于读取）目前是通过我们的影子master机制来保证的。对master的状态更改是通过增加到一个往前写的log中持久化。因此我们可以在使用如同在Harp\[7\]中使用的primary-copy机制来保证高可用性以及对我们机制的一个强有效的一致性保证。  
我们用类似Lustre\[8\]的方法来提供针对大量客户端的整体性能。不过，我们通过面向我们的应用的方式简化了问题的解决方法，而不是面向提供兼容POSIX文件系统的方式。此外，GFS假设我们大量使用了非可靠节点，所以容错处理是我们设计的核心。  
GFS很类似NASD架构\[4\]。NASD架构是基于网络磁盘的。GFS用的是普通计算机作为chunkserver，如同NASD原形中一样。所不同的是，我们的chunkserver是滞后分配固定大小的chunk而不是用一个变长的结构。此外，GFS实现了诸如重新负载均衡，副本，恢复机制等等在生产环境中需要的特性。  
与Minnesota’s GFS和NASD不同，我们并不改变存储设备的访问方式。我们集中于解决用普通计算机来解决日常的分布式系统所需要的数据处理。生产者消费者队列是通过原子的纪录增加来解决的，类似在River\[2\]中的分布式队列。River使用的是分布在机器组的基于内存的队列，并且仔细控制数据流。GFS用的是持久化文件，可以由很多生产者并发增加的方式。River模式支持m-到-n的分布式队列但是缺少用持久化存储的容错机制，GFS只支持m-到-1的队列。多个消费者可以同时读取一个文件，但是他们输入流的区间必须是对齐的。

## 结束语 ##

Google 文件系统展示了使用常规硬件支持大规模数据处理的质量属性。虽然很多设计要素都是针对我们的特殊需要而定制的，但是很多都可以适用于基于成本考虑的类似规模的数据处理任务。首先我们依据现在和预期的应用负载和技术环境来审视传统的文件系统约定。我们的审视引导我们使用设计领域完全不同的思路来设计。我们在设计上认为部件失效属于常态而不是异常，通过面向巨型文件的主要追加模式进行优化（并发优化）并且读取优化（通常序列化读取），以及扩展和放松了标准文件系统接口来改进整个系统。  
我们系统使用持续监控，复制关键数据，快速自动恢复来提供了容错处理。chunk复制使得我们可以对chunkserver的失效进行容错。这些失效的经常发生使得在线修复机制变得很有必要，使得需要尽快修复和补偿丢失的副本。此外，我们使用checksum来检查磁盘或者IDE系统级别的数据损坏，因为在这样大的一个系统中，磁盘数量惊人，所以损坏率也很高。  
我们的设计要求对不同任务的大并发读取和写入有一个很高的合计吞吐量。我们通过分离文件系统控制和文件数据传输的设计来实现，我们通过master来进行文件系统的控制，通过chunkserver和客户端来进行文件数据的传输。master包括了常用的操作，并且通过大块的chunk大小进行元数据的缩小，以及通过chunklease令牌减少数据量，chunk令牌是授权给第一个副本以数据变更操作。这些使得一个简单，中心master不再成为一个瓶颈。我们相信我们对网络协议栈的优化可以提升对于每个客户端的当前的写入吞吐量限制。  
GFS成功的实现了我们的存储要求以及在Google内部广泛应用于研发部门和生产数据处理的存储平台。它是我们持续创新和解决整个web范围的一个有力工具。  
致谢  
在这里我们想感谢对GFS和本论文做出贡献的人们。Brain Bershad(我们的领头人)以及其他阅读这给了我们有用的意见和建议。Anurag Acharya,Jeff Dean,David desJardins 建立了早期的设计。Fay Chang 在对比chunserver之间的副本作了重要工作。Guy Edjiali在存储部分作主要工作。Markus Gutschke在测试框架和提高安全性。David Karmer在性能提高上作工作。Fay Chang，Urs Hoelzle,Max Lbel,Sharon Perl,Rob Pike, Debby Wallach 对本文早期版本提出了建议。Google的很多同僚都很勇敢的信任我们的新系统，把他们的数据放上来，并且给了我们很有用的反馈。Yoshka在早期测试工作中作了贡献。

[http_labs.google.com_papers_gfs.html]: http://labs.google.com/papers/gfs.html
[20150318123539489]: /images/20220805/5420292c56364421a3d7d37c856074a6.png
[20150318123939465]: /images/20220805/37eff82db4374919a40080f5cf4ff9a1.png
[20150318123959891]: /images/20220805/b71d8711eea1498a8ec05ee014f7c64f.png
[20150318124538780]: /images/20220805/788a6357ca0e4ae8ae73719f0dac9fa2.png
[20150318124506621]: /images/20220805/5514cb48d1bf46c59ad6d3bddef25189.png
[20150318124554575]: /images/20220805/8be9bb0065794213bed9c4ecbfb10455.png
[4]: /images/20220805/ddc6da470683460c8ab315c20b54aa77.png
[5]: /images/20220805/22e457642d0b4920a3d7c15f85fbcfa9.png
[6_master]: /images/20220805/2effa3b06d2d4a73a54ab57ac51dc7e9.png