Google File System
Jaly
没什么好说的，传说中的文件系统，当代网络超大容量分布式文件系统设计的典范，Google的核心竞争力所在。Google的
Search、GMail、 video、blog spaces等等都是用这个技术做的。Google目前的中国区总裁李开复就认为学计算机的学生都
应该看看Google File System。
很佩服Google的开放精神，将GoogleFS的详细设计写成了Paper: The Google File System,
（http://labs.google.com/papers/GoogleFS-sosp2003.pdf）作者是Sanjay
Ghemawat, Howard Gobioff, and Shun-Tak Leung。该论文长达15页，对Google FS介绍得非常详
细，从设计时考虑的因素到详细的解决方案，以及测试和实际运行数据，都做了具体的说明，而不像IBM这么遮遮掩掩，从GPFS、 Storage
Tank到TotalStorage SAN File System，一直都是小里小气的样子，生怕别人知道它做了啥。
在Google公开了GoogleFS的论文后（2003年），已经有开源的项目开始借鉴GoogleFS的设计思想，开发类似的新型大容量分
布式文件系统，如NDFS/ Hadoop等。
拍完GoogleFS的马屁，下面就该轮到详细的介绍一下GoogleFS了。目前关于GoogleFS最权威的资料就是上文提到的那片15页
的技术论文。本来想把论文翻译部分贴出来，结果发现网上早就有现成的翻译版本了，我就脸皮厚点，从chinaunix转载过来了，然后修正一些明显的错
误，加上一些自己的理解，放在这里了，嘿嘿。
简介
GoogleFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对海量数据进行访问的应用。它运行于廉价的普通硬件上，但提供了容错复
制功能，可以给大量的用户提供总体性能较高的可靠服务。
1、设计概述
（1）设计假设
GoogleFS与传统的分布式文件系统有很多相同的目标，但GoogleFS的设计受到了当前及预期的应用方面的工作量以及技术环境的驱动，
因而形成了它与传统的分布式文件系统明显不同的设想。这就需要对传统的选择进行重新检验并进行完全不同的设计观点的探索。
GoogleFS与以往的文件系统的不同的特点如下：
1、硬件错误（包括存储设备或是存储节点的故障）不再被认为是异常的情况，而是将其作为常见的情况加以处理。因为文件系统由成千上万个用于存储
的机器节点构成，而这些机器是由廉价的普通硬件组成并被大量的客户机访问。硬件的数量和质量使得一些机器随时都有可能无法工作并且有一部分还可能无法恢
复。所以实时地监控、错误检测、容错、自动恢复对系统来说必不可少。（我们就吃过很多次这种亏啊，呜呜）
2、按照传统的标准，文件都非常大，长度达几个GB的文件是很平常的。每个文件通常包含很多应用对象。因为经常要处理快速增长的、包含数以万计
的对象、长度达TB的数据集，我们很难管理成千上万的KB规模的文件块，即使底层文件系统提供支持。因此，设计中操作的参数、块的大小必须要重新考虑。
对大型的文件的管理一定要能做到高效，对小型的文件也必须支持，但不必优化。
3、大部分文件的更新是通过添加新数据完成的，而不是改变已存在的数据。在一个文件中随机的操作在实践中几乎不存在。一旦写完，文件就只可读，
很多数据都有这些特性。一些数据可能组成一个大仓库以供数据分析程序扫描。有些是运行中的程序连续产生的数据流。有些是档案性质的数据，有些是在某个机
器上产生、在另外一个机器上处理的中间数据。由于这些对大型文件的访问方式，添加操作成为性能优化和原子性保证的焦点。而在客户机中缓存数据块则失去了
吸引力。
4、工作量主要由两种读操作构成：对大量数据的流方式的读操作和对少量数据的随机方式的读操作。在前一种读操作中，可能要读几百KB，通常达
1MB和更多。来自同一个客户的连续操作通常会读文件的一个连续的区域。随机的读操作通常在一个随机的偏移处读几个KB。性能敏感的应用程序通常将对少
量数据的读操作进行分类并进行批处理以使得读操作稳定地向前推进，而不要让它来来回回的读。
5、工作量还包含许多对大量数据进行的、连续的、向文件添加数据的写操作。所写的数据的规模和读相似。一旦写完，文件很少改动。在随机位置对少
量数据的写操作也支持，但不必非常高效。
6、系统必须高效地实现定义完好的大量客户同时向同一个文件的添加操作的语义。
（2）系统接口
虽然GoogleFS没有像POSIX那样实现标准的API，但它提供了一个相似地文件系统界面，文件在目录中按层次组织起来并由路径名标
识。
（3）体系结构
一个GoogleFS集群由一个Master和大量的chunkserver构成，并被许多客户（Client）访问。如图1所
示。Master和 chunkserver通常是运行用户层服务进程的Linux机器。只要资源和可靠性允许，chunkserver和Client
可以运行在同一个机器上。
图1 GoogleFS架构
文件被分成固定大小的块(block)。每个块由一个不变的、全局唯一的64位的chunk-handle标识，chunk-handle是在
块创建的时候由Master分配的。chunkserver将块当作Linux文件存储在本地磁盘并可以读和写由chunk-handle和位区间指定
的数据。出于可靠性考虑，每一个块被复制到多个chunkserver上。默认情况下，保存3个副本，但这可以由用户指定。
Master维护文件系统所有的元数据（metadata），包括名字空间、访问控制信息、从文件到块的映射以及块的当前位置。它也控制系统范
围的活动，如块租约（lease）管理，孤儿块的垃圾收集，chunkserver间的块迁移。Master定期通过HeartBeat消息与每一个
chunkserver通信，给chunkserver传递指令并收集它的状态。
与每个应用程序相连的GoogleFS客户端实现了文件系统的API并与Master和chunkserver通信，以访问文件系统的数据。客户端与
Master的交换只限于对元数据（metadata）的操作，所有数据方面的通信都直接和chunkserver联系。
客户端和chunkserver都不缓存文件数据。因为用户缓存的益处微乎其微，这是由于数据太多或工作集太大而无法缓存。不缓存数据策略简化
了客户端程序和整个系统，因为不必考虑缓存的一致性问题，但客户端缓存元数据（metadata）。chunkserver也不必缓存文件数据，因为块
是作为本地文件存储的。
（4）单Master。
只有一个Master也极大的简化了设计并使得Master可以根据全局情况做出高级的块放置和复制决定。但是我们必须要将Master对读和
写的参与减至最少，这样它才不会成为系统的瓶颈。Client从来不会从Master读和写文件数据。Client只是询问Master它应该和哪个
chunkserver联系。Client在一段限定的时间内将这些信息缓存，在后续的操作中Client直接和chunkserver交互。
以图1解释一下一个简单的读操作的交互。
1、Client使用固定的块大小将应用程序指定的文件名和字节偏移转换成文件的一个块索引（chunk index）。
2、给Master发送一个包含文件名和块索引的请求。
3、Master回应对应的chunk handle和副本的位置（多个副本）。
4、Client以文件名和块索引作为键值缓存这些信息。（handle和副本的位置）。
5、Client 向其中一个副本发送一个请求，很可能是最近的一个副本。请求指定了chunk handle（chunkserver以
chunk-handle标识chunk）和块内的一个字节区间。
6、除非缓存的信息不再有效或文件被重新打开，否则以后对同一个块的读操作不再需要Client和Master间的交互。
通常Client可以在一个请求中询问多个chunk的地址，而Master也可以很快回应这些请求。
（5）块规模：
块规模是设计中的一个关键参数。我们选择的是64MB，这比一般的文件系统的块规模要大的多。每个块的副本作为一个普通的Linux文件存储，
在需要的时候可以扩展。
块规模较大的好处有
1、减少Client和Master之间的交互。因为读写同一个块只是要在开始时向Master请求块位置信息。对于读写大型文件这种减少尤为
重要。即使对于访问少量数据的随机读操作也可以很方便的为一个规模达几个TB的工作集缓存块位置信息。
2、Client在一个给定的块上很可能执行多个操作，和一个chunkserver保持较长时间的TCP连接可以减少网络负载。
3、这减少了Master上保存的元数据（metadata）的规模，从而使得可以将metadata放在内存中。这又会带来一些别的好处。
不利的一面
一个小文件可能只包含一个块，如果很多Client访问该文件的话，存储这些块的chunkserver将成为访问的热点。但在实际应用中，应
用程序通常顺序地读包含多个块的文件，所以这不是一个主要问题。
（6）元数据（metadata）：
Master存储了三种类型的metadata：文件的名字空间和块的名字空间，从文件到块的映射，块的副本的位置。所有的metadata都
放在内存中。前两种类型的metadata通过向操作日志登记修改而保持不变，操作日志存储在Master的本地磁盘并在几个远程机器上留有副本。使用
日志使得我们可以很简单地、可靠地更新Master的状态，即使在Master崩溃的情况下也不会有不一致的问题。相反，Master在每次启动以及当
有 chunkserver加入的时候询问每个chunkserver的所拥有的块的情况。
A、内存数据结构：
因为metadata存储在内存中，所以Master的操作很快。进一步，Master可以轻易而且高效地定期在后台扫描它的整个状态。这种定
期地扫描被用于实现块垃圾收集、chunkserver出现故障时的副本复制、为平衡负载和磁盘空间而进行的块迁移。
这种方法的一个潜在的问题就是块的数量也即整个系统的容量是否受限与Master的内存。实际上，这并不是一个严重的问题。Master为每
个 64MB的块维护的metadata不足64个字节。除了最后一块，文件所有的块都是满的。类似的，每个文件的名字空间数据也不足64个字节，因为
文件名是以一种事先确定的压缩方式存储的.如果要支持更大的文件系统，那么增加一些内存的方法对于我们将元数据（metadata）保存在内存中所获得
的简单性、可靠性、高性能和灵活性来说，这只是一个很小的代价。
B、块位置：
Master并不为chunkserver所拥有的块的副本的保存一个不变的记录。它在启动时通过简单的查询来获得这些信息。Master可以
保持这些信息的更新，因为它控制所有块的放置并通过HeartBeat消息来监控chunkserver的状态。
这样做的好处：因为chunkserver可能加入或离开集群、改变路径名、崩溃、重启等，一个集群中有成百个chunkserver，这些事
件经常发生。这种方法就排除了Master与chunkserver之间的同步问题。
另一个原因是：只有chunkserver才能确定它自己到底有哪些块，由于错误，chunkserver中的一些块可能会很自然的消失，这样在
Master中就没有必要为此保存一个不变的记录。
C、操作日志：
操作日志包含了对metadata所作的修改的历史记录。它作为逻辑时间线定义了并发操作的执行顺序。文件、块以及它们的版本号都由它们被创建
时的逻辑时间而唯一地、永久地被标识。
操作日志是如此的重要，我们必须要将它可靠地保存起来，并且只有在metadata的改变固定下来之后才将变化呈现给用户。所以我们将操作日志复制到数
个远程的机器上，并且只有在将相应的日志记录写到本地和远程的磁盘上之后才回答用户的请求。
Master可以用操作日志来恢复它的文件系统的状态。为了将启动时间减至最小，日志就必须要比较小。每当日志的长度增长到超过一定的规模
后，Master就要检查它的状态，它可以从本地磁盘装入最近的检查点来恢复状态。
创建一个检查点比较费时，Master的内部状态是以一种在创建一个检查点时并不耽误即将到来的修改操作的方式来组织的。Master切换到一
个新的日志文件并在一个单独的线程中创建检查点。这个新的检查点记录了切换前所有的修改。在一个有数十万文件的集群中用一分钟左右就能完成。创建完后，
将它写入本地和远程的磁盘。
（7）数据完整性
名字空间的修改必须是原子性的，它们只能有Master处理：名字空间锁保证了操作的原子性和正确性，而Master的操作日志在全局范围内定
义了这些操作的顺序。
文件区间的状态在修改之后依赖于修改的类型，不论操作成功还是失败，也不论是不是并发操作。如果不论从哪个副本上读，所有的客户都看到同样的数
据，那么文件的这个区域就是一致的。如果文件的区域是一致的并且用户可以看到修改操作所写的数据，那么它就是已定义的。如果修改是在没有并发写操作的影
响下完成的，那么受影响的区域是已定义的，所有的Client都能看到写的内容。成功的并发写操作是未定义但却是一致的。失败的修改将使区间处于不一致
的状态。
Write操作在应用程序指定的偏移处写入数据，而record append操作使得数据（记录）即使在有并发修改操作的情况下也至少原子性
的被加到GoogleFS指定的偏移处，偏移地址被返回给用户。
在一系列成功的修改操作后，最后的修改操作保证文件区域是已定义的。GoogleFS通过对所有的副本执行同样顺序的修改操作并且使用块版本号检测过时
的副本（由于chunkserver退出而导致丢失修改）来做到这一点。
因为用户缓存了块位置信息，所以在更新缓存之前有可能从一个过时的副本中读取数据。但这有缓存的截止时间和文件的重新打开而受到限制。
在修改操作成功后，部件故障仍可以使数据受到破坏。GoogleFS通过Master和chunkserver间定期的handshake，借
助校验和来检测对数据的破坏。一旦检测到，就从一个有效的副本尽快重新存储。只有在GoogleFS检测前，所有的副本都失效，这个块才会丢失。