谷歌文件系统GFS
分布式文件系统是分布式存储系统的一种，根据处理数据的类型，分布式存储系统主要分为四类，分布式文件系统、分布式键值系统、分布式表格系统、分布式数据库。分布式文件系统存储三种类型的数据：Blob（Binary Large Object二进制大对象数据）对象，也就是图片，照片，视频等非结构化数据对象，以及定长块，大文件。在系统实现层面，分布式文件系统内部按照数据块（chunk）来组织数据。每个数据块大小大致相同，每个数据块可以包含多个Blob对象或者定长块，一个大文件也可以拆分为多个数据块。分布式文件系统将这些数据块分散到存储集群，处理数据复制、一致性、负载均衡、容错等分布式系统难题，并将用户对Blob对象、定长块以及大文件的操作映射为对底层数据块的操作。另外，分布式文件系统也常作分布式表格系统以及分布式数据库的底层存储。
Google文件系统（GFS）是构建在廉价服务器之上的大型分布式系统。他将服务器故障视为正常现象，通过软件的方式自动容错，在保证系统可靠性和可用性的同时，大大降低系统的成本。GFS是Google分布式存储的基石，其他存储系统，如Google Bigtable 、Google Megastore、Google Percolator均直接或者间接地构建在GFS之上。另外，Google大规模批处理系统MapReduce也需要利用GFS作为海量数据的输入输出。
GFS与过去的分布式文件系统有很多相同的目标，但GFS的设计受到了当前及预期的应用方面的工作量及技术环境的驱动，这反映了它与早期的文件系统明显不同的设想。这就需要对传统的选择进行重新检验并进行完全不同的设计观点的探索。GFS与以往的文件系统的不同如下：1.部件错误不再被当作异常，而是将其作为常见的情况加以处理。因为文件系统由成百上千个用于存储的机器构成，而这些机器是由廉价的普通部件组成并被大量的客户机访问。部件的数量和质量使得一些机器随时都有可能无法工作并且有一部分还可能无法恢复。所以实时地监控、错误检测、容错、自动恢复对系统来说必不可少。2.按照传统的标准，文件都非常大。长度达几个GB的文件是很平常的。每个文件通常包含很多应用对象。当经常要处理快速增长的、包含数以万计的对象、长度达TB的数据集时，我们很难管理成千上万的KB规模的文件块，即使底层文件系统提供支持。因此，设计中操作的参数、块的大小必须要重新考 虑。对大型的文件的管理一定要能做到高效，对小型的文件也必须支持，但不必优化。3.大部分文件的更新是通过添加新数据完成的，而不是改变已存在的数据。在一个文件中随机的操作在实践中几乎不存在。一旦写完，文件就只可读，很多数据都有这些特性。一些数据可能组成一个大仓库以供数据分析程序扫描。有些是运行中的程序连续产生的数据流。有些是档案性质的数据，有些是在某个机器上产生、在另外一个机器上处理的中间数据。由于这些对大型文件的访问方式，添加操作成为性能优化和原子性保证的焦点。而在客户机中缓存数据块则失去了吸引力。4.工作量主要由两种读操作构成：对大量数据的流方式的读操作和对少量数据的随机方式的读操作。在前一种读操作中，可能要读几百KB，通常达1MB和更多。来自同一个客户的连续操作通常会读文件的一个连续的区域。随机的读操作通常在一个随机的偏移处读几个KB。性能敏感的应用程序通常将对少量数据的读操作进行分类并进行批处理以使得读操作稳定地向前推进，而不要让它来反反复复地读。5.工作量还包含许多对大量数据进行的、连续的、向文件添加数据的写操作。所写的数据的规
模和读相似。一旦写完，文件很少改动。在随机位置对少量数据的写操作也支持，但不必非常高效。6.系统必须高效地实现定义完好的大量客户同时向同一个文件的添加操作的语义。7.高可持续带宽比低延迟更重。。
为此，GFS的整体架构如下。一个GFS集群由一个master和大量的chunk server构成，并被许多客户端（Client）访问。
GFS系统的节点可分为三种角色：GFS Master（主服务器）、GFS Chunk Server（CS，数据块服务器）以及GFS客户端GFS文件被划分为固定大小的数据块（Chunk），由Master在创建时分配一个64位全局唯一的Chunk句柄。CS以普通的Linux文件的形式将数据块存储在磁盘中。为了保证可靠性，数据块在不同的机器中复制多份，默认为三份。Master中维护了系统的元数据，包括文件及数据块名字空间，GFS文件到数据块之间的映射，数据块位置信息，同时它也负责整个系统的全局控制。客户端的读操作的交互流程为：1.首先客户端使用固定的块大小将应用程序指定的文件名和字节偏移转换成文件的一个块索引；2.然后给master发送一个包含文件名和块索引的请求；3.master回应对应的Chunk句柄和副本的位置（多个副本）；4.客户端以文件名和块索引为键缓存这些信息；5.客户端向其中一个副本发送一个请求，很可能是最近的一个副本。请求指定了chunk 句柄和块内的一个字节区间；6.除非缓存的信息不再有效或文件被重新打开，否则以后对同一个块的读操作不再需要客户端和master间的交互。通常情况下客户端可以在一个请求中询问多个chunk的地址，而master也可以很快回应这些请求。与此同时，客户端的追加操作流程为：1.客户端向GFS设计中只有一个Master，master请求chunk每个副本所在的chunk server，其中主chunk server持有修改租约；2.Master返回客户端主副本和备副本所在的chunk server的位置信息，客户端将缓存这些信息供以后使用。如果不出现故障，客户端以后读写该chunk都不需要再次请求Master；3.客户端将要追加的记录发送到每一个副本。每一个chunk server会在内部的LRU结构中缓存这些数据。GFS中采用数据流和控制流分离的方法，从而能够基于网络拓扑结构更好地调度数据流的传输；4.当所有副本都确认收到了数据，客户端发起一个写请求控制命令给主副本。由于主副本可能收到多个客户端对同一个chunk的并发追加操作，主副本将确定这些操作的顺序并写入本地；5.主副本把写请求提交给所有的备副本。每一个备副本会根据主副本确定的顺序执行写操作；6.备副本成功完成后应答主副本；7.主副本应答客户端，如果有副本发生错误，将出现主副本写成功但是某些备副本不成功的情况，客户端将重试。这样一个追加流程分离了数据流和
控制流，这么设计的目的是为了优化数据传输。前提是每次追加的数据都比较大。这种分离增加了追加流程的复杂度。还有一种追加流程采用传统的主备复制方法，追加流程会在一定程度上得到简化。其具体步骤为：1，2前步没有变化；3.客户端将待追加数据发送到主副本，主副本可能收到多个客户端的并发追加请求，需要确定操作顺序，并写入本地；4.主副本将数据通过流水线的方式转发给所有的备副本；5.每个主副本收到待追加的记录数据后写本地，所有副本都在本地写成功并且收到后一个副本的应答消息时向前一个副本回应，比如上图中A需要等待B应答成功且本地写成功后才可以应答主副本；6.主副本应答客户端。如果客户端在超时时间之内没有收到主副本的应答，说明发生了错误，需要重试。
对于GFS中的每一个数据块，其大小为64MB，这比一般的文件系统的块规模要大的多。每个块的副本作为一个普通的Linux文件存储，在需要的时候可以扩展。块规模较大的好处有：1.减少客户端和master之间的交互。因为读写同一个块只是要在开始时向master请求块位置信息。对于读写大型文件这种减少尤为重要。即使对于访问少量数据的随机读操作也可以很方便的为一个规模达几个TB的工作集缓缓存块位置信息；2.客户端在一个给定的块上很可能执行多个操作，和一个chunk server保持较长时间的TCP连接可以减少网络负载；3.这减少了master上保存的元数据的规模，从而使得可以将元数据放在内存中。这又会带来一些别的好处。与此同时，也会有不利的一面，一个小文件可能只包含一个块，如果很多客户端访问该文件的话，存储这些块的chunk server将成为访问的热点。但在实际应用中，应用程序通常顺序地读包含多个块的文件，所以这不是一个主要问题。对于master，上文中提到其存储了三种类型的元数据：文件的名字空间和块的名字空间，从文件到块的映射，块的副本的位置。所有的元数据都放在内存中。前两种类型的元数据通过向操作日志登记修改而保持不变，操作日志存储在master的本地磁盘并在几个远程机器上留有副本。使用日志使得我们可以很简单地、可靠地更新master的状态，即使在master崩溃的情况下也不会有不一致的问题。相反，master在每次启动以及当有 chunk server加入的时候询问每个chunk server的所拥有的块的情况。因为元数据存储在master内存中，所以master的操作很快。进一步，master可以轻易而且高效地定期在后台扫描它的整个状态。这种定期地扫描被用于实现块垃圾收集、chunk server出现故障时的副本复制、为平衡负载和磁盘空间而进行的块迁移。此外master并不为chunk server所拥有的块的副本的保存一个不变的记录。它在启动时通过简单的查询来获得这些信息。Master可以保持这些信息的更新，因为它控制所有块的放置并通过心跳消息来监控chunk server的状态。这样做的好处是因为chunk server可能加入或离开集群、改变路径名、崩溃、重启等，一个集群中有成百个server，这些事件经常发生，这种方法就排除了master与chunk server之间的同步问题。另一个原因是因为只有chunk server才能确定它自己到底有哪些块，由于错误，chunk server中的一些块可能会很自然的消失，这样在master中就没有必要为此保存一个不变的记录。
再来分析GFS中的几个关键问题，包括GFS的一致性模型，租约机制，数据追加流程和容错机制。1.一致性模型，GFS主要是为了追加而不是改写而设计的。一方面是因为改写的需求比较少，或者可以通过追加来实现，比如可以只使用GFS的追加功能构建分布式表格系统Bigtable；另一方面是因为追加的一致性模型相比改写要更加简单有效。考虑Chunk A的三个副本A1，A2，A3，有一个改写操作修改了A1，A2但没有修改A3，这样，落到副本A3的读操作可能读到不