Google File System(Google翻译)

Google File System Google File System 收件人： 发件人： 崮山路上走9遍 抄送： 日期： 2005-08-08 关于： The Google File System Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung Google∗ {sanjay,hgobioff,shuntak}@google.com 首页版权 Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SOSP’03, October 19–22, 2003, Bolton Landing, New York, USA. Copyright 2003 ACM 1-58113-757-5/03/0010 ...$5.00. 摘要 我们已经设计和实现了Google File System，一个适用于大规模分布式数据处理相关应用的，可扩展的分布式文件系统。它基于普通的不算昂贵的硬件设备，实现了容错的设计，并且为大量客户端提供极高的聚合处理性能。 我们的设计目标和上一个版本的分布式文件系统有很多相同的地方，我们的设计是依据我们应用的工作量以及技术环境来设计的，包括现在和预期的，都有一部分和早先的文件系统的约定有所不同。这就要求我们重新审视传统的设计选择，以及探索究极的设计要点。 这个文件系统正好与我们的存储要求相匹配。这个文件系统在Google内部广泛应用于作为存储平台使用，适用于我们的服务要求产生和处理数据应用，以及我们的研发要求的海量数据的要求。最大的集群通过上千个计算机的数千个硬盘，提供了数百TB的存储，并且这些数据被数百个客户端并行同时操作。 在这个论文里，我们展示了用于支持分布式应用的扩展文件系统接口设计，讨论了许多我们设计的方面，并且列出了我们的micro-benchmarks以及真实应用性能指标。 分类和主题描述 D[4] ：3 – 分布式文件系统 普通条目 设计，可靠性，性能，测量 Design，reliability，performance，measurement 关键词 容错，扩展性，数据存储，集群数据存储 1 介绍 我们已经为Google迅速增长的数据处理需要而设计和实现了Google File System(GFS)。GFS和上一个分布式文件系统有着很多相同的设计目标，比如性能，扩展性，可靠性，以及可用性。不过，他的设计是基于我们应用的工作量和技术环境驱动的，包括现在和预期的，都有部分和上一个版本的约定有点不同。这就要求我们重新审视传统的设计选择，以及探索究极的设计要点。 首先，节点失效将被看成是正常情况，而不再视为异常情况。整个文件系统包含了几百个或者几千个由廉价的普通机器组成的存储机器，而且这些机器是被与之匹配数量的客户端机器访问。这些节点的质量和数量都实际上都确定了在任意给定时间上，一定有一些会处于失效状态，并且某一些并不会从当前失效中恢复回来。这有可能由于程序的bug，操作系统的bug，人工操作的失误，以及硬盘坏掉，内存，网络，插板的损坏，电源的坏掉等等。因此，持续监视，错误检测，容错处理，自动恢复必须集成到这个文件系统的设计中来。 其次，按照传统来看，文件都是非常巨大的。数个GB的文件是常事。每一个文件都包含了很多应用程序对象，比如web文档等等。当我们通常操作迅速增长的，由很多TB组成的，包含数十亿对象的数据集，我们可不希望管理数十亿个KB大小的文件，即使文件系统能支持也不希望。所以，设计约定和设计参数比如I/O操作以及blocksize（块大小），都需要重新审查。 第三，大部分文件都是只会在文件尾新增加数据，而少见修改已有数据的。对一个文件的随机写操作在实际上几乎是不存在的。当一旦写完，文件就是只读的，并且一般都是顺序读取得。多种数据都是有这样的特性的。有些数据可能组成很大的数据仓库，并且数据分析程序从头扫描到尾。有些可能是运行应用而不断的产生的数据流。有些是归档的数据。有些是一个机器为另一个机器产生的中间结果，另一个机器及时或者随后处理这些中间结果。对于这些巨型文件的访问模式来说，增加模式是最重要的，所以我们首要优化性能的以及原子操作保证的就是它，而在客户端cache数据块没有什么价值。 第四，与应用一起设计的的文件系统API对于增加整个系统的弹性适用性有很大的好处。例如我们不用部署复杂的应用系统就可以把GFS应用到大量的简单文件系统基础上。我们也引入了原子的增加操作，这样可以让多个客户端同时操作一个文件，而不需要他们之间有额外的同步操作。这些在本论文的后边章节有描述。 多个GFS集群现在是作为不同应用目的部署的。最大的一个有超过1000个存储节点，超过300TB的硬盘存储，并且负担了持续沉重的上百个在不同机器上的客户端的访问。 2 设计概览 2.1 约定 在为我们的需要设计文件系统得时候，我们需要建立的事先约定同时具有挑战和机遇。我们早先提到的关于观测到的关键要点，现在详细用约定来说明。 · 系统是建立在大量廉价的普通计算机上，这些计算机经常故障。必须对这些计算机持续进行检测，并且在系统的基础上进行：检查，容错，以及从故障中进行恢复。 · 系统存储了大量的超大文件。我们与其有好几百万个文件，每一个超过100MB。数GB的文件经常出现并且应当对大文件进行有效的管理。同时必须支持小型文件，但是我们不必为小型文件进行特别的优化。 · 一般的工作都是由两类读取组成：大的流式读取和小规模的随机读取。在大的流式读取中，每个读操作通常要读取几百k的数据，每次读取1M或者以上的数据也很常见。对于同一个客户端来说，往往会发起连续的读取操作顺序读取一个文件。小规模的随机读取通常在文件的不同位置，读取几k数据。对于性能有过特别考虑的应用通常会作批处理并且对他们读取的进行排序，这样可以使得他们的读取始终是单向顺序读取，而不需要往回读取数据。 · 通常基于GFS的操作都有很多超大的，顺序写入的文件操作。通常写入操作的数据量和杜如的数据量相当。一旦完成写入，文件就很少会更改。对于文件的随机小规模写入是要被支持的，但是不需要为此作特别的优化。 · 系统必须非常有效的，明确细节的对多客户端并行添加同一个文件进行支持。我们的文件经常使用生产者/消费者队列模式，或者作为多路合并模式进行操作。好几百个运行在不同机器上的生产者，将会并行增加一个文件。其本质就是最小的原子操作的定义。读取操作可能接着生产者操作进行，消费者会同时读取这个文件。 · 高性能的稳定带宽的网络要比低延时更加重要。我们的目标应用程序一般会大量操作处理比较大块的数据，并且很少有应用要求某个读取或者写入要有一个很短的响应时间。 2.2 接口 GFS提供了常见的文件系统的接口，虽然他没有实现一些标准的API比如POSIX。文件是通过pathname来通过目录进行分层管理的。我们支持的一些常见操作：create,delete,open,close,read，write等文件操作。 另外，GFS有snapshot，record append等操作。snapshort创建一个文件或者一个目录树的快照，这个快照的耗费比较低。record append允许很多个客户端同时对一个文件增加数据，同时保证每一个客户端的添加操作的原子操作性。这个对于多路合并操作和多个客户端同时操作的生产者/消费者队列的实现非常有用，它不用额外的加锁处理。这种文件对于构造大型分布式应用来说，是不可或缺的。snapshot 和record append在后边的3.4 和3.3节有单独讲述。 2.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到了内存里。 2.4 单个master 引入一个单个master的设计可以大大简化我们的设计，并且也让master能够基于全局的角度来管理chunk的存放和作出复制决定。不过，我们必须尽量减少master的读和写操作，以避免它成为瓶颈。客户端永远不会通过master来做文件的数据读写。客户端只是问master它应当访问那一个chunkserver来访问数据。客户端在一定时间内cache这个信息，并且在后续的操作中都直接和chunkserver进行操作。 这里我们简单介绍一下图1中的读取操作。首先，客户端把应用要读取的文件名和偏移量，根据固定的chunk大小，转换成为文件的chunk index。然后向master发送这个包含了文件名和chunkindex的请求。master返回相关的chunk handle以及对应的位置。客户端cache这些信息，把文件名和chunkindex作为cache的关键索引字。 于是这个客户端就像对应的位置的chunkserver发起请求，通常这个会是离这个客户端最近的一个。请求给定了chunk handle以及一个在这个chunk内需要读取得字节区间。在这个chunk内，再次操作数据将不用再通过客户端-master的交互，除非这个客户端本身的cache信息过期了，或者这个文件重新打开了。实际上，客户端通常都会在请求中附加向master询问多个chunk的信息，master于是接着会立刻给这个客户端回应这些chunk的信息。这个附加信息是通过几个几乎没有任何代价的客户端-master的交互完成的。 2.5 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启动时间来解决这样的问题。一劳永逸的解决方法是让客户端能够互相读取数据，这样才是解决之道。 2.6 元数据 master节点保存这样三个主要类型的数据：文件和chunk的namespace，文件到chunks的映射关系，每一个chunk的副本的位置。所有的元数据都是保存在master的内存里的。头两个类型（namepspaces和文件到chunk的映射）同时也是由在master本地硬盘的记录所有变化信息的operation log来持久化保存的，这个记录也会在远端机器上保存副本。通过log，在master宕机的时候，我们可以简单，可靠的恢复master的状态。master并不持久化保存chunk位置信息。相反，他在启动地时候以及chunkserver加入集群的时候，向每一个chunkserver询问他的chunk信息。 2.6.1 内存数据结构 因为元数据都是在内存保存的，master的操作很快。另外master也很容易定时后台扫描所有的内部状态。定时内部状态扫描是用于实现chunk的垃圾回收机制，当chunkserver失效的时候重新复制，以及为了负载均衡和磁盘空间均衡使用的目的做chunkserver之间的chunk镜像。4.3 和4.4节将讨论这些操作的细节。 这种内存保存数据的方式有一个潜在的问题，就是说整个系统的chunk数量以及对应的系统容量是受到master机器的内存限制的。这个在实际生产中并不是一个很重要的限制。master为每64Mchunk分配的空间不到64个字节的元数据。大部分的chunks都是装满了的，因为大部分文件都是很大的，包含很多个chunk，只有文件的最后部分可能是有空间的。类似的，文件的名字空间通常对于每一个文件来说要求少于64个字节，因为保存文件名的时候是使用前缀压缩的机制。 如果有需要支持到更大的文件系统，因为我们是采用内存保存元数据的方式，所以我们可以很简单，可靠，高效，灵活的通过增加master机器的内存就可以了。 2.6.2 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上保存这个资料啥用处也没有。 2.6.3 操作记录（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。 2.7 一致性模型 GFS是一个松散的一致性检查的模型，通过简单高效的实现，来支持我们的高度分布式计算的应用。我们在这里讨论的GFS的可靠性以及对应用的可靠性。我们也强调了GFS如何达到这些可靠性，实现细节在本论文的其他部分实现。 2.7.1 GFS的可靠性保证 文件名字空间的改变（比如，文件的创建）是原子操作。他们是由master来专门处理的。名字空间的锁定保证了操作的原子性以及正确性（4.1节）；master的操作日志定义了这些操作的全局顺序（2.6.3） 什么是文件区，文件区就是在文件中的一小块内容。 不管数据变化成功还是失败，是否是并发的数据变化，一个数据变化导致的一个文件区的状态依赖于这个变化的类型。表一列出了这些结果。当所有的客户端都看到的是相同的数据的时候，并且与这些客户端从哪个数据的副本读取无关的时候，一个文件区是一致性的。一个文件区是确定的，当数据发生变化了，在一致性的基础上，客户端将会看到这个全部的变化。当一个更改操作成功完成，没有并发写冲突，那么受影响的区就是确定的了（并且潜在一致性）：所有客户端都可以看到这个变化是什么。并发成功操作使得文件区是不确定的，但是是一致性的：所有客户端都看到了相同的数据，但是并不能却分到底什么变化发生了。通常，他是由好多个变动混合片断组成。一个失败的改变使得一个文件区不一致（因此也不确定）：不同的用户可能在不同时间看到不同的数据。我们接下来会描述我们的应用如何能够辨别确定的和不确定的区块。应用程序并不需要进一步区分不同种类的不确定区。 数据更改可能是写一个记录或者是一个记录增加（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也是不可用，而不是损坏：这样是给应用程序一个明确的错误提示，而不是给应用程序一个损坏的数据。 2.7.2 应用的实现。 GFS的应用程序可以用简单的几个技术来实现相关的一致性，这些技术已经被其他目的而使用了：尽量采用追加方式而不是更改方式，checkpoint，写自效验，自标示记录等等。 实际上几乎我们所有的应用程序都是通过追加方式而不是覆盖方式进行数据的操作。通常都是一个程序创建一个文件，从头写到尾。当所有的数据都写完的时候，才把文件名字更改成为正式的文件名，或者定期checkpoint有多少数据已经完成写入了。Checkpoint可以包括应用级别的checksum。读取程序只校验和处理包含在最近checkpoint内的文件区，这些文件区是确定的状态。不管在一致性方面还是并发的方面，这个已经足够满足我们的应用了。追加方式对于应用程序来说更加有效，并且相对随机写操作来说对应用程序来说更加可靠。Checkpoint使得写操作者增量的进行写操作并且防止读操作者处理已经成功写入，但是对于应用程序角度看来并未提交的数据。 在另一种常见情况下，很多个写操作者对一个文件并发增加，用来合并结果数据，或者提供一个生产者-消费者的队列。增加记录的 至少增加一次 的机制保护了每一个写入者的输出。读取者需要处理这些非必然的空白填充以及记录的重复。写入者写入的每一个记录都包含额外的信息，比如checksum等等，这样可以使得每条记录都能够效验。读取者可以通过这些checksum辨别和扔掉额外的填充记录或者记录碎片。如果读取者不能处理这些偶然的重复记录（比如，如果他们触发了一种非等幂操作等等non-idempotent operations）,他可以通过记录的唯一标志来区分出记录，这些唯一标志常常用来标记相关的应用实体，比如web文档等等。这些记录I/O的功能（除了移出复制记录），都是放在库中的，用于我们的应用程序，并且可应用于google里边的其它的文件接口实现。通过这些函数库，相同序列的记录，和一些重复填充，就可以提供给记录的读取者了。 3 系统交互 我们设计的一个原则是尽量在所有操作中减少master的交互。在这个基础上，我们现在讨论客户端，master，chunkserver如何交互，实现数据的变动，原子的记录增加，以及快照。 3.1 令牌 和变化顺序 变动操作是一种改变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也可以很安全的在原始令牌超时后授予另外一个副本一个令牌。 图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节讲述的一样）。 3.2 数据流 我们把数据流和控制流分开，是为了更有效的利用网络资源。当控制流从客户端到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。 3.3 原子纪录增加 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中有所讨论。 3.4 快照 快照操作在尽量不影响正在发生的变动的情况下，几乎即时产生一个文件或者目录树（”源”）。我们的用户是用快照来迅速创建举行数据集的一个分支拷贝（经常还有拷贝的拷贝，递归拷贝），或者在提交变动前做一个当前状态的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上创建的。 4 master操作 master执行所有的namespace的操作。另外，他管理系统中所有chunk的副本；他决定chunk的放置策略，穿件新的chunk及其副本，以及相关的多个系统级别的操作来保持chunk有好几个副本，平衡所有chunkserver之间的附在，回收未使用的存储。我们现在讨论每一个小节。 4.1 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树种的级别顺序，以及相同级别下根据字典顺序进行分配的。 4.2 副本位置 GFS集群是在不止一个级别上的多级别的高度分布的系统。通常由好几百台分布在很多机架上的chunkserver组成。这些chunkserver可能被相同或者不同的机架的几百台客户端轮流访问。两个机架上的两台机器可能会跨越不止一个网络交换机。此外，机架的入口带宽或者出口带宽往往会比在机架内的机器聚合带宽要小。多级别的分布凸现了一个独特的要求，为了可扩展性，可靠性，以及可用性要把数据进行分布。 chunk复本存放机制有两个目的：最大限度的保证数据的可靠和可用，并且最大限度的利用网络带宽。对于两者来说，仅仅在机器之间进行复本的复制时不足够的，它只保证了磁盘或者机器的实效，以及每一个机器的网络带宽的使用。我们必须也在机架之间进行chunk的复制。这就保证了当整个机架都损坏的时候（或者掉线的时候），对于任意一个chunk来说，都有一些副本依旧有效（比如，由于共享资源的失效，例如网络交换机或者电源故障，导致机架不可用）。这也意味着网络冲突的减轻，尤其是对于读取操作来说，对于一个chunk的读取来说，使用的是每一个机架内部的聚合带宽。换句话说，会增加跨越各个机架的写流量，这个是我们相比较愿意承受的代价。 4.3 创建，重新复制，重新均衡 有三个原因需要创建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，这样会平衡磁盘空间使用。 4.4 垃圾回收 当文件被删除以后，GFS并不立刻要求归还可用的物理存储。它是通过滞后的基于文件和chunk级别的普通垃圾回收机制来完成的。我们发现这样可以使得系统更加简单和可靠。 4.4.1 机制 当应用删除了一个文件，master像记录其他变动一样，立刻记录这个删除操作。不过不同于立刻回收资源，这个文件仅仅是改名称为一个隐藏的名字，并且包含了一个删除时戳。在master的常规的文件系统namespace的检查中，他会移出这些超过3天隐藏删除文件（这个3天是可以配置的）。直到此时，文件依旧可以通过新的，特别的名字读取，并且可以通过改名来恢复成为未删除状态。当隐藏文件从namespace删除后，它在内存的元数据也随之删除。这个会影响他所指向的各个chunk。 在对chunk的namespace的常规扫描中，master识别chunk孤点（就是说，没有被任何文件所指向）并且删除这些孤点的元数据。在chunkserver和master的常规心跳消息中，每一个chunkserver都报告自己的chunk集合，并且master回复在master的元数据中已经不存在的chunk标记。chunkserver随即释放和删除这些chunk的副本。 4.4.2 讨论 虽然分布式的垃圾回收是一个艰巨的问题，在程序设计的时候需要复杂的解决，但是在我们的系统中却是比较简单的。我们可以轻易辨别出对一个chunk的全部引用：它们都唯一保存在master的文件-chunk影射表中。我们也可以容易辨别所有的chunk副本：它们是在各个chunkserver上的指定目录下的linux文件。所有不被master知道的副本就是”垃圾”。 垃圾回收比较类似提供几种便利删除机制的存储回收。首先，他在一个由非可靠节点组成的超大分布式系统中可靠而简单的运行。chunk的创建在某些chunkserver可以成功但是在某些chunkserver却会失败，这样导致master不知道的某些副本。副本删除消息可能会丢失，master被迫记住并且重发这些失败的副本删除消息，不仅仅是它自己的副本删除消息，也包含chunkserver的。垃圾回收机制提供了一个统一的可靠的方式来清除未知的副本，这种机制非常有用。其次，他把存储的回收合并到常规的master后台操作，如同常规的对namespace的扫描，以及对chunkserver的握手。因此，它是作为批处理的，处理开销也是分批地。另外，这仅仅是当master的负载相对较轻的时候进行的。master可以更快的相应客户的请求，不过这需要花时间来关注客户的请求（所以对垃圾的回收时在负载较轻的情况下执行的）。第三，在存储回收的延后回收也提供了某种程度的由于网络故障导致的不可回收的删除的恢复。 在我们的经验中，主要的缺点就是当存储紧张的时候，滞后删除会导致阻碍我们尝试调整磁盘使用情况的效果。应用程序重复创建和删除临时文件可能不会正确重用存储。我们通过如果一个已经删除了的文件再次删除的操作，来加速存储回收，部分解决这个问题。我们也允许用户对于不同的namespace部分，使用不同的复制和回收策略。例如，用户可以指定所有的在某目录树下的文件chunk的保存没有副本，任何删除的文件立刻并且不可撤销的从文件系统状态中删除。 4.5 过期副本删除 chunk副本可能会因为chunkserver失效期间丢失了对chunk的变动而导致过期。对于每一个chunk，master保持一个chunk的版本号码来区分最新的和过期的副本。 无论何时master为一个chunk颁发一个令牌，他都增加chunk的版本号码并且通知最新的副本。master和这些副本在他们的持久化状态中都记录最新的版本号码。这在任何客户端被通知前发生，并且因此在开始对这个chunk写之前发生。如果另一个副本当前不在线，那么他的chunk的版本号码就不会改变。当这个chunkserver重新启动，并且向master报告它的chunk以及相关版本号码的时候，master会根据版本号码来检查出这个chunkserver有一个过