谷歌技术“三宝”之一的Google文件系统和Kosmos 文件系统

转：http://www.cppblog.com/jack-wang/archive/2010/02/26/108503.aspx

谷歌技术“三宝”之一的Google文件系统和Kosmos 文件系统
    虽然针对大规模分布式存储系统，Google将推陈出新，推新的理由有很多，如"single-master design,…… but it was certainly unacceptable for latency-sensitive applications, such as video serving."。参考《Google File System II: Dawn of the Multiplying Master Nodes》和《GFS:Evolution on Fast-forward》。但是GFS毕竟为其服务了10年时间，连李开复博士也宣称每个计算机学生都有必要学学这套系统。

      本篇也一起谈谈Kosmos文件系统，传闻Google的两个共同创始人佩奇和布林有两个大学同窗，是两个印度人,名叫Anand Rajaraman和Venky Harinarayan，看到Google获得巨大成功之后，就动手做了个一个新的搜索引擎CloudStore (原先一直叫Kosmos filesystem，现在搭上了云计算的顺风车改了头衔)。在做这个搜索引擎的过程中，他们实现了一个类似GFS的文件系统KFS(很多理念都从GFS那里搬过来，比如constant monitoring, error detection, fault tolerance, and automatic recovery)。因为GFS的论文只是设计，而KFS是开源的，两者结合看效果可能比较好。

     首先，看过谷歌工程师写地这篇《The Google File System》的能不能做下面这道证明题：考虑一个拥有1000个节点的GFS集群，定性(不定量)证明：在有800个节点失效的情况下，剩下的200个节点仍然能够完成工作，即performance下降的情况下，scalability,reliability,availability等保持良好。

 

本文想阐释谷歌文件系统的一些设计理念。

一 架构：

下图为谷歌文件系统的结构图，一个GFS集群包含一个主服务器和多个块服务器, 这是一个单一主服务器模型：

 

      概括一下块(chunk)的一些信息：块尺寸是64MB；文件被分割成固定尺寸的块，在每个块创建的时候，服务器分配给它一个不变的、唯一的64位的块句柄对它进行标识；每个块都会复制到多个块服务器上。

      主服务器保存三种主要类型的metadata：文件和块的命名空间，文件到块的映射，以及每个块副本的位置，它通过全局的信息精确确定块的位置以及进行复制决定。主服务器的主要工作有：主服务器在后台周期扫猫自己的整个状态，用来在块服务器间实现块的垃圾收集的功能，用来实现块服务器失效的时复制新副本的功能，用来实现负载均衡的块移动的功能，以及用来实现统计硬盘使用情况的功能等。

      块服务器保存着块，并根据指定的块句柄和字节区间来读写块数据。

      客户端不通过主服务器读写数据。反之，客户端向主服务器询问它应该联系的块服务器。客户端短期缓存这些信息，后续的操作直接跟块服务器进行。

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

      此系统可靠性方面相关的一些设计，下面概要叙述一下，后面会有详细描述：

      1主服务器不持久化保存块的位置信息。主服务器在自己启动以及块服务器加入集群的时候，询问块服务器它所包含的块的信息，然后定期的心跳信息监控块服务器的状态。

      2 名称空间和文件块映射的metadata，会用log的方式保存在主服务器的硬盘上的操作日志内，并在远程的机器内复制一个副本。使用log，可以更新主服务器的状态，而且不用担心服务器崩溃带来的数据不一致的风险。

      3. 主服务器通过重放operation log恢复其文件系统。operation log是metadata唯一的持久化存储记录，起到了定义同步操作顺序的逻辑时间线的作用。文件和块及其版本都是唯一和持久地由他们创建时的逻辑时间标识的。进行恢复仅需要最新的checkpoint和相应的日志文件。日志增长到一个特定尺寸的时候，主服务器汇总的状态为一个checkpoint。

4文件命名空间的修改（例如，文件创建）是原子性的。他们仅受主服务器的控制：命名空间锁定保证了原子性和正确性；主服务器的操作日志定义了这些操作的全局总顺序。在修改操作成功后，部件故障仍可以使数据受到破坏。GFS通过master和chunkserver间定期的handshake，借助校验和来检测对数据的破坏。一旦检测到，就从一个有效的副本尽快重新存储。只有在GFS检测前，所有的副本都失效，这个块才会丢失。

5…………….

 

二 系统交互

这一节讨论客户机，服务器和块服务器三者如何交互以实现数据操作，原子化的记录追加及快照。

2.1 leases and mutation order

Mutations是一个会改变块内容或者元数据的操作，例如写入或者记录追加。每个变更执行在块的所有副本上。使用leases来保持多个副本间变更顺序的一致性，leases机制的设计是为了最小化主服务器的管理负载。由于Master首先grants一个主块（即副本中的一个块lease），所以全局的mutation order就形成了：首先由主服务器选择的lease生成顺序决定，然后由lease中主块分配的序列号决定。再用图来说明写入操作的控制流程：

 

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

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

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

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

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

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

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

 2.2 数据流

      数据流和控制流分开。控制流从客户机到主块然后再到所有二级副本的同时，数据顺序推送到一个精心选择的管道形式的块服务器链。特点：用IP地址就可以计算出节点的远近；用在TCP连接上管道化数据传输来最小化延迟。

2.3 原子性的记录追加

      GFS提供了一个原子性的添加操作：record append。在传统的写操作中，client指定被写数据的偏移位置，向同一个区间的并发的写操作是不连续的：区间有可能包含来自多个client的数据碎片。在record append中， client只是指定数据。GFS在其选定的偏移出将数据至少原子性的加入文件一次，并将偏移返回给client。

在分布式的应用中，不同机器上的许多client可能会同时向一个文件执行添加操作，添加操作被频繁使用。如果用传统的write操作，可能需要额外的、复杂的、开销较大的同步，例如通过分布式锁管理。在我们的工作量中，这些文件通常以多个生产者单个消费者队列的方式或包含从多个不同 client的综合结果。

      Record append和前面讲的write操作的控制流差不多，只是在primary上多了一些逻辑判断。首先，client将数据发送到文件最后一块的所有副本上。然后向primary发送请求。Primary检查添加操作是否会导致该块超过最大的规模（64M）。如果这样，它将该块扩充到最大规模，并告诉其它副本做同样的事，同时通知client该操作需要在下一个块上重新尝试。如果记录满足最大规模的要求，primary就会将数据添加到它的副本上，并告诉其它的副本在同样的偏移处写数据，最后primary向client报告写操作成功。如果在任何一个副本上record append操作失败，client将重新尝试该操作。这时候，同一个块的副本可能包含不同的数据，因为有的可能复制了全部的数据，有的可能只复制了部分。GFS不能保证所有的副本每个字节都是一样的。它只保证每个数据作为一个原子单元被写过至少一次。这个是这样得出的：操作要是成功，数据必须在所有的副本上的同样的偏移处被写过。进一步，从这以后，所有的副本至少和记录一样长，所以后续的记录将被指定到更高的偏移处或者一个不同的块上，即使另一个副本成了primary。根据一致性保证，成功的record append操作的区间是已定义的。而受到干扰的区间是不一致的。

 2.4快照

      快照操作几乎在瞬间构造一个文件和目录树的副本，同时将正在进行的其他修改操作对它的影响减至最小。

我们使用copy-on-write技术来实现snapshot。当master受到一个snapshot请求时，它首先要撤消将要snapshot的文件上块上的lease。这使得任何一个向这些块写数据的操作都必须和master交互以找到拥有lease的副本。这就给master一个创建这个块的副本的机会。

副本被撤销或终止后，master在磁盘上登记执行的操作，然后复制源文件或目录树的metadata以对它的内存状态实施登记的操作。这个新创建的snapshot文件和源文件（其metadata）指向相同的块（chunk）。

       Snapshot之后，客户第一次向chunk c写的时候，它发一个请求给master以找到拥有lease的副本。Master注意到chunk c的引用记数比1大，它延迟对用户的响应，选择一个chunk handle C’,然后要求每一有chunk c的副本的chunkserver创建一个块C’。每个chunkserver在本地创建chunk C’避免了网络开销。从这以后和对别的块的操作没有什么区别。

 

3.Mast操作

MASTER执行所有名字空间的操作，除此之外，他还在系统范围管理数据块的复制：决定数据块的放置方案，产生新数据块并将其备份，和其他系统范围的操作协同来确保数据备份的完整性，在所有的数据块服务器之间平衡负载并收回没有使用的存储空间。

3.1 名字空间管理和加锁

      与传统文件系统不同的是，GFS没有与每个目录相关的能列出其所有文件的数据结构，它也不支持别名（unix中的硬连接或符号连接），不管是对文件或是目录。GFS的名字空间逻辑上是从文件元数据到路径名映射的一个查用表。

MASTER在执行某个操作前都要获得一系列锁，例如，它要对/d1/d2…/dn/leaf执行操作，则它必须获得/d1，/d1/d2，…， /d1/d2/…/dn的读锁，/d1/d2…/dn/leaf的读锁或写锁（其中leaf可以使文件也可以是目录）。MASTER操作的并行性和数据的一致性就是通过这些锁来实现的。

3.2 备份存储放置策略

一个GFS集群文件系统可能是多层分布的。一般情况下是成千上万个文件块服务器分布于不同的机架上，而这些文件块服务器又被分布于不同机架上的客户来访问。因此，不同机架上的两台机器之间的通信可能通过一个或多个交换机。数据块冗余配置策略要达到多个目的：最大的数据可靠性和可用性，最大的网络带宽利用率。因此，如果仅仅把数据的拷贝置于不同的机器上很难满足这两个要求，必须在不同的机架上进行数据备份。这样即使整个机架被毁或是掉线，也能确保数据的正常使用。这也使数据传输，尤其是读数据，可以充分利用带宽，访问到多个机架，而写操作，则不得不涉及到更多的机架。

3.3 产生、重复制、重平衡数据块

      当MASTER产生新的数据块时，如何放置新数据块，要考虑如下几个因素：（1）尽量放置在磁盘利用率低的数据块服务器上，这样，慢慢地各服务器的磁盘利用率就会达到平衡。（2）尽量控制在一个服务器上的“新创建”的次数。（3）由于上一小节讨论的原因，我们需要把数据块放置于不同的机架上。

      MASTER在可用的数据块备份低于用户设定的数目时需要进行重复制。这种情况源于多种原因：服务器不可用，数据被破坏，磁盘被破坏，或者备份数目被修改。每个被需要重复制的数据块的优先级根据以下几项确定：第一是现在的数目距目标的距离，对于能阻塞用户程序的数据块，我们也提高它的优先级。最后， MASTER按照产生数据块的原则复制数据块，并把它们放到不同的机架内的服务器上。

       MASTER周期性的平衡各服务器上的负载：它检查chunk分布和负载平衡，通过这种方式来填充一个新的服务器而不是把其他的内容统统放置到它上面带来大量的写数据。数据块放置的原则与上面讨论的相同，此外，MASTER还决定哪些数据块要被移除，原则上它会清除那些空闲空间低于平均值的那些服务器。

3.4 垃圾收集

      在一个文件被删除之后，GFS并不立即收回磁盘空间，而是等到垃圾收集程序在文件和数据块级的的检查中收回。

当一个文件被应用程序删除之后，MASTER会立即记录下这些变化，但文件所占用的资源却不会被立即收回，而是重新给文件命了一个隐藏的名字，并附上了删除的时间戳。在MASTER定期检查名字空间时，它删除超过三天（可以设定）的隐藏的文件。在此之前，可以以一个新的名字来读文件，还可以以前的名字恢复。当隐藏的文件在名字空间中被删除以后，它在内存中的元数据即被擦除，这就有效地切断了他和所有数据块的联系。

在一个相似的定期的名字空间检查中，MASTER确认孤儿数据块（不属于任何文件）并擦除它的元数据，在和MASTER的心跳信息交换中，每个服务器报告他所拥有的数据块，MASTER返回元数据不在内存的数据块，服务器即可以删除这些数据块。

3.5 过时数据的探测

      在数据更新时如果服务器停机了，那么他所保存的数据备份就会过时。对每个数据块，MASTER设置了一个版本号来区别更新过的数据块和过时的数据块。

      当MASTER授权一个新的lease时，他会增加数据块的版本号并会通知更新数据备份。MASTER和备份都会记录下当前的版本号，如果一个备份当时不可用，那么他的版本号不可能提高，当ChunkServer重新启动并向MASTER报告他的数据块集时，MASTER就会发现过时的数据。

      MASTER在定期的垃圾收集程序中清除过时的备份，在此以前，处于效率考虑，在各客户及英大使，他会认为根本不存在过时的数据。作为另一个安全措施， MASTER在给客户及关于数据块的应答或是另外一个读取数据的服务器数据是都会带上版本信息，在操作前客户机和服务器会验证版本信息以确保得到的是最新的数据。

 

4、容错和诊断

4.1 高可靠性

4.1.1 快速恢复

不管如何终止服务，MASTER和数据块服务器都会在几秒钟内恢复状态和运行。实际上，我们不对正常终止和不正常终止进行区分，服务器进程都会被切断而终止。客户机和其他的服务器会经历一个小小的中断，然后它们的特定请求超时，重新连接重启的服务器，重新请求。

4.1.2 数据块备份

如上文所讨论的，每个数据块都会被备份到放到不同机架上的不同服务器上。对不同的名字空间，用户可以设置不同的备份级别。在数据块服务器掉线或是数据被破坏时，MASTER会按照需要来复制数据块。

4.1.3 MASTER备份

为确保可靠性，MASTER的状态、操作记录和检查点都在多台机器上进行了备份。一个操作只有在数据块服务器硬盘上刷新并被记录在MASTER和其备份的上之后才算是成功的。如果MASTER或是硬盘失败，系统监视器会发现并通过改变域名启动它的一个备份机，而客户机则仅仅是使用规范的名称来访问，并不会发现MASTER的改变。

4.2 数据完整性

每个数据块服务器都利用校验和来检验存储数据的完整性。原因：每个服务器随时都有发生崩溃的可能性，并且在两个服务器间比较数据块也是不现实的，同时，在两台服务器间拷贝数据并不能保证数据的一致性。

每个Chunk按64kB的大小分成块，每个块有32位的校验和，校验和和日志存储在一起，和用户数据分开。

在读数据时，服务器首先检查与被读内容相关部分的校验和，因此，服务器不会传播错误的数据。如果所检查的内容和校验和不符，服务器就会给数据请求者返回一个错误的信息，并把这个情况报告给MASTER。客户机就会读其他的服务器来获取数据，而MASTER则会从其他的拷贝来复制数据，等到一个新的拷贝完成时，MASTER就会通知报告错误的服务器删除出错的数据块。

附加写数据时的校验和计算优化了，因为这是主要的写操作。我们只是更新增加部分的校验和，即使末尾部分的校验和数据已被损坏而我们没有检查出来，新的校验和与数据会不相符，这种冲突在下次使用时将会被检查出来。

相反，如果是覆盖现有数据的写，在写以前，我们必须检查第一和最后一个数据块，然后才能执行写操作，最后计算和记录校验和。如果我们在覆盖以前不先检查首位数据块，计算出的校验和则会因为没被覆盖的数据而产生错误。

在空闲时间，服务器会检查不活跃的数据块的校验和，这样可以检查出不经常读的数据的错误。一旦错误被检查出来，服务器会拷贝一个正确的数据块来代替错误的。

4.3 诊断工具

广泛而细致的诊断日志以微小的代价换取了在问题隔离、诊断、性能分析方面起到了重大的作用。GFS服务器用日志来记录显著的事件（例如服务器停机和启动）和远程的应答。远程日志记录机器之间的请求和应答，通过收集不同机器上的日志记录，并对它们进行分析恢复，我们可以完整地重现活动的场景，并用此来进行错误分析。

 

 

以下是Kosmos filesystem的一些特性：

自动存储扩充（添加新的chunckserver,系统自动感知）

有效性（复制机制保证文件有效性，一般文件会被以三种方式存储，当其中一个chunkserver出现错误的时候，不会影响         数据的读取）

文件复制粒度：可以配置文件复制的粒度，最大可以被复制64份

还原复制：当其中一个Chunckserver出现故障的时候，Metaserver会强制使用其他的chunckserver

负载平衡（系统周期地检查chunkservers的磁盘利用，并重新平衡chunkservers的磁盘利用，HDFS现在还没有支持）

数据完整性（当要读取数据时检查数据的完整性，如果检验出错使用另外的备份覆盖当前的数据）

文件写入：当一个应用程序创建了一个文件，这个文件名会被立刻写入文件系统，但为了性能，写入的数据会被缓存在kfs客户端.并且周期性的从缓存中把数据更新到chunkserver中。当然，应用程序也可以强制把数据更新到服务器上。一旦数据被更新到服务器，就可以被有效的读取了。

契约（使用契约来保证Client缓存的数据和文件系统中的文件保持一致性）

支持FUSE（在linux系统下，可以通过Fuse 映射一个文件夹，从而可以很方便的读取kfs的文件）

支持C++,Java,Python方式的调用

提供了丰富的工具程序，如kfsshell,cp2kfs等

提供了启动和停止服务的脚本