摘要：GFS在设计上有很多值得学习的地方，最近重读了一下GFS的设计论文，试图从架构设计的角度对GFS进行剖析，希望可以借鉴一些分布式系统的设计思路。

1 设计约束

       GFS是针对Google迅速增长的数据处理需求的定制化文件系统，它的设计初衷就不是提供兼容POSIX的通用文件系统。这使得它没有太多束缚，能够很灵活的进行方案设计，以最简单的方式实现Google应用程序需要的特性。 

       文件通常被用于“生产者-消费者” 队列，或者其它多路文件合并操作。通常会有数百个生产者，每个生产者进程运行在一台机器上，同时对一个文件进行追加操作。使用最小的同步开销来实现的原子的多路追加数据操作是必不可少的。文件可以在稍后读取，或者是消费者在追加的操作的同时读取文件。

       GFS客户程序访问特征：

       1）文件通常比较大。

       2）数据一旦被写入后，文件就很少会被修改。

       3）对文件的修改通常都是在文件尾部追加数据，而不是覆盖原有数据。

       4）系统的主要工作负载是大规模的流式读取和小规模的随机读取。

       5）高性能的稳定网络带宽比低延迟重要。

       组件失效被认为是常态事件，而不是意外事件。GFS是一个典型的分布式系统，系统由许多廉价的普通组件组成，组件失效是一种常态。系统必须持续监控自身的状态，它必须将组件失效作为一种常态，能够迅速地侦测、冗余并恢复失效的组件。

2. 架构剖析

2.1 中心服务器架构

       GFS选择了中心服务器（Master）架构，相较于依赖分布式算法来保证一致性和可管理性的架构，设计更加简单，增加了可靠性，能够灵活扩展。 

       Master 节点管理所有的文件系统元数据。这些元数据包括名字空间、访问控制信息、文件和 Chunk 的映射信息、以及当前 Chunk 的位置信息。 Master 节点还管理着系统范围内的活动，比如， Chunk 租用管理、孤儿 Chunk的回收、以及 Chunk 在 Chunk Server之间的迁移。 Master 节点使用心跳信息周期地和每个 Chunk Server通讯，发送指令到各个Chunk Server 并接收 Chunk Server的状态信息。

       由于处于中心位置的 Master 服务器保存有几乎所有的 Chunk 相关信息，并且控制着 Chunk 的所有变更，因此，它极大地简化了原本非常复杂的 Chunk 分配和复制策略的实现方法。通过减少 Master 服务器保存的状态信息的数量，以及将 Master 服务器的状态复制到其它节点来保证系统的灾难冗余能力。

2.2 高可用存储架构

      存储高可用方案的本质都是通过将数据复制到多个存储设备，通过数据冗余的方式来实现高可用，其复杂性主要体现在如何应对复制延迟和中断导致的数据不一致问题。

2.2.1 数据分散集群

      GFS中一个文件被顺序分割为多个Chunk，在Chunk Server集群分散保存Chunk的多个副本，来实现存储高可用。这是典型的“数据分散集群”架构，即数据存储在多个分片上，有一个角色来负责执行数据分配算法，在GFS中这个工作是由Master节点完成的。Master节点负责分配Chunk存储在哪些Chunk Server。分配算法根据各个Chunk Server的机架分布、硬盘使用率、繁忙程度等因素来执行，以达到最大化数据可靠性和可用性，最大化网络带宽利用率的目标。

      Chunk Server负责存储数据，维护数据可用性，并向Master节点同步本地Chunk元数据，以方便Master节点建立文件到Chunk映射的完整视图。另外，为了避免 Master 成为系统瓶颈，GFS设计了租约机制。租约由Master负责授权，持有Chunk租约的Chunk Server成为主节点，而其他Chunk Server成为跟随节点。在租约有效期内，对该Chunk的写操作由主节点来控制。

2.2.2 Write流程(数据分片和复制)

GFS写控制流

      1）客户端向Master请求Chunk每个副本所在的Chunk Server，其中Primary Chunk Server持有租约。如果没有Chunk Server持有租约，说明该Chunk最近没有写操作，Master会发起一个任务，按照一定的策略将Chunk的租约授权给其中一台Chunk Server；

      2）Master返回客户端Primary和其它Chunk Server的位置信息，客户端将缓存这些信息供以后使用。如果不出现故障，客户端以后读写该Chunk都不需要再次请求Master；

      3）客户端将要追加的记录发送到Chunk副本所在的任意一个Chunk Server，通常选择距离最近的Chunk Server。Chunk Server在本地缓存数据，并转发给距离最近的下一个Chunk Server，直到所有的Chunk Server都收到数据；

      4）当所有副本都确认收到了数据后，客户端发起一个写请求控制命令给Primary。由于Primary可能收到多个客户端对同一个Chunk的并发追加操作，Primary将确定这些操作的顺序并写入本地硬盘；

      5）Primary把写请求提交给所有的Secondary副本，每一个Secondary会根据Primary确定的顺序执行写操作；

      6）Secondary副本成功完成后应答Primary；

      7）Primary应答客户端。

      在Write流程中，写入成功必须保证所有副本均成功，也就是说不存在类似其他分布式系统中的复制延迟问题。如果有任何副本发生错误，将会出现Primary写成功但是某些Secondary不成功的情况，此时Primary给客户端回失败，但已经写入数据的副本不会回滚。客户端稍后进行重试，所有发副本会在统一的偏移地址再次写入记录，这会出现两种情况：

     (1) 第一次写入成功的副本，记录发生重复。

     (2) 第一次写入失败的副本，存在填充的脏数据。在GFS的一致性模型中，这种情况是可以接受的，需要应用程序来处理。

2.2.3 容错机制

      Master的容错与传统的方法类似，通过操作日志加checkpoint的方式进行，并且有一台称为”Shadow Master”的实时热备。

      Master上保存了三种元数据信息：

       (1) 命名空间（Name Space），也就是整个文件系统的目录结构以及chunk基本信息；

       (2) 文件到chunk之间的映射；

       (3) Chunk副本的位置信息，每个Chunk通常有三个副本；

       GFS Master的修改操作总是先记录操作日志，然后再修改内存，当Master发生故障重启时，可以通过磁盘中的操作日志恢复内存数据结构；另外，为了减少Master宕机恢复时间，Master会定期将内存中的数据以checkpoint文件的形式转储到磁盘中，从而减少回放的日志量。为了进一步提高Master的可靠性和可用性，GFS中还会执行实时热备，所有的元数据修改操作都必须保证发送到实时热备才算成功。远程的实时热备将实时接收Master发送的操作日志并在内存中回放这些元数据操作。如果Master宕机，还可以秒级切换到实时备机继续提供服务。为了保证同一时刻只有一个Master，GFS依赖Google内部的Chubby服务进行选主操作。

       Master需要持久化前两种元数据，即命令空间及文件到chunk之间的映射关系；对于第三种元数据，即Chunk副本的位置信息，Master可以选择不进行持久化，这是因为ChunkServer维护了这些信息，即使Master发生故障，也可以在重启时通过ChunkServer汇报来获取。

       GFS采用复制多个副本的方式实现Chunk Server的容错，每一个Chunk有多个存储副本，分别存储在不同的Chunk Server上。对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入。如果相关的副本出现丢失或不可恢复的情况，Master自动将给副本复制到其它Chunk Server，从而确保副本保持一定的个数。

2.2.4 一致性模型

      GFS提供的一致性模型归结为下表，

GFS一致性模型

     1）写操作一致性

     如果串行操作成功，文件状态是defined的。如果是并发写成功，文件状态是consistent but undefined。也就是说，客户端看到的数据都是一样的，但是可能看到的内容可能不能反映任何一个写操作的全部内容，而是来自多个修改的混杂的数据（mingled fragments from multiple mutations）。如果失败，结果是inconsistent的。

      consistent but undefined可能不太好理解，它实际说的是写请求不是serializable的。举个例子可能就清楚了。假如多个客户端同时修改一个文件的[a,b]这个范围的内容，其中a=64M,b=64M+1，即这两个字节正好跨两个chunk的边界。某个客户端想把内容改为”AA”，另一个客户端想改成”BB”。 consistent but undefined是说，可能出现”AB”或”BA”的结果。这个结果并不能反映任何一个操作的全部修改。

      2）记录追加一致性

      对于记录追加，操作成功了，其结果是defined interspersed with inconsistent的。为理解这个结论，我们先看记录追加的过程。

      记录追加和上述描述的写操作流程基本类似，只是多了一步追加padding的逻辑。追加padding的目的是保证记录追加的原子性。跨Chunk的追加可能导致非serializable的结果，所以假如文件最后一个Chunk剩余空间不够存放本次写操作的数据，就要把该Chunk填满padding（备副本也要同样地填上padding），再让客户端在新的Chunk上重试。在新的Chunk上（如果原Chunk剩余空间足够，就是在原Chunk上），主副本会将数据追加到Chunk内，然后通知备副本在同样的偏移量上追加数据。如果失败，会有如下的结果：某些副本上的数据写成功了，而另一些副本上没有该数据或只有部分数据。失败的操作会被重试。GFS不保证副本的每个字节都是一样的，但是能够保证数据作为一个整体被至少一次原子地写入，而且最后写成功的那次在各个副本上该记录对应的偏移量都是一样的。这就是为何前面说对于记录追加，操作成功了，其结果是defined interspersed with inconsistent。

      GFS主要是为了追加（Append）而不是改写（Overwrite）而设计的。一方面是因为是改写的需求比较少，或者可以通过追加来实现，比如可以只使用GFS的追加功能构建分布式表格系统Bigtable；另一方面是因为追加的一致性模型相比改写要更加简单有效。考虑Chunk A的三个副本A1，A2，A3，有一个改写操作修改了A1，A2但没有修改A3，这样，落到副本A3的读操作可能读到不正确的数据；相应地，如果有一个追加操作往A1，A2上追加了一个记录但是追加A3失败，那么即使读操作落到副本A3也只是读到过期而不是不正确的数据。如果不发生异常，追加成功的记录在GFS的各个副本中是确定并且严格一致的；但是如果出现了异常，可能出现某些副本追加成功而某些副本没有成功的情况，失败的副本可能会出现一些可识别的填充(padding)记录。GFS客户端追加失败将重试，只要返回用户追加成功，说明在所有副本中都至少追加成功了一次。当然，可能出现记录在某些chunk副本中被追加了多次，即重复记录；也可能出现一些可识别的填充记录，应用程序需要能够处理这些问题。

       另外，由于GFS支持多个客户端并发追加，那么多个客户端之间的顺序是无法保证的，同一个客户端连续追加成功的多个记录也可能被打断，比如客户端先后追加成功记录R1和R2，由于追加R1和R2这两条记录的过程不是原子的，中途可能被其它客户端打断，那么GFS的chunk中记录的R1和R2可能不连续，中间夹杂着其它客户端追加的数据。

      GFS的这种一致性模型是追求性能导致的，这也增加了应用程序开发的难度。对于那些padding、垃圾数据和重复数据，应用需要自己过滤掉。至于过滤方式，可以使用CheckSum标记垃圾数据、重复数据可以使用唯一id标识。对于MapReduce应用，由于其批处理特性，可以先将数据追加到一个临时文件，在临时文件中维护索引记录每个追加成功的记录的偏移，等到文件关闭时一次性将临时文件改名为最终文件。

2.2.5 数据完整性

       每个chunkserver使用checksum来侦测腐化的存储数据。一个GFS集群经常包含几百台服务器、几千个磁盘，磁盘故障导致数据腐化或丢失是常有的事儿。我们能利用其他正常的chunk副本恢复腐化的数据，但是通过跨chunkserver对比副本之间的数据来侦测腐化是不切实际的。另外，各副本内的字节数据出现差异也是正常的、合法的（原子的record append就可能导致这种情况，不会保证完全一致的副本，但是不影响客户端使用）。因此，每个chunkserver必须靠自己来核实数据完整性，其对策就是维护checksum。

       一个chunk被分解为多个64KB的块。每个块有对应32位的checksum。像其他元数据一样，checksum被保存在内存中，并用利用日志持久化保存，与用户数据是隔离的。

       在读操作中，chunkserver会先核查读取区域涉及的数据块的checksum。因此chunkserver不会传播腐化数据到客户端（无论是用户客户端还是其他chunkserver）。如果一个块不匹配checksum，chunkserver向请求者明确返回错误。请求者收到此错误后，将向其他副本重试读请求，而master则会尽快从其他正常副本克隆数据创建新的chunk。当新克隆的副本准备就绪，master命令发生错误的chunkserver删除异常副本。

       checksum对读性能影响不大。因为大部分读只会跨几个块，checksum的数据量不大。GFS客户端代码在读操作中可以尽量避免跨越块的边界，进一步降低checksum的花费。而且chunkserver查找和对比checksum是不需要任何I/O的，checksum的计算通常也在I/O 等待时被完成，不争抢CPU资源。

       checksum的计算是为append操作高度优化的，因为append是我们的主要应用场景。append时可能会修改最后的块、也可能新增块。对于修改的块只需增量更新其checksum，对于新增块不管它有没有被填满都可以计算其当前的checksum。对于最后修改的块，即使它已经腐化了而且append时没有检测到，还对其checksum执行了增量更新，此块的checksum匹配依然会失败，在下次被读取时即能侦测到。

       普通的写操作则比append复杂，它会覆盖重写文件的某个区域，需要在写之前检查区域首尾块的checksum。它不会创建新的块，只会修改老的块，而且不是增量更新。对于首尾之间的块没有关系，反正是被全量的覆盖。而首尾块可能只被覆盖了一部分，又不能增量更新，只能重新计算整个块的checksum，覆盖老checksum，此时如果首尾块已经腐化，就无法被识别了。所以必须先检测后写。

       在系统较空闲时，chunkserver会去扫描和检查不太活跃的chunk。这样那些很少被读的chunk也能被侦测到。一旦腐化被侦测到，master会为其创建一个新副本，并删除腐化副本。GFS必须保证每个chunk都有足够的有效副本以防不可逆的丢失，chunk不活跃可能会导致GFS无法察觉它的副本异常，此机制可以有效的避免这个风险。

2.3 高性能架构

2.3.1 缓存Chunk元数据

       客户端用文件名和 Chunk 索引作为 key 缓存这些信息。在对这个 Chunk 的后续读取操作中，客户端不必再和 Master 节点通讯了，除非缓存的元数据信息过期或者文件被重新打开。实际上，客户端通常会在一次请求中查询多个 Chunk 信息， Master 节点的回应也可能包含了紧跟着这些被请求的 Chunk 后面的 Chunk 的信息。在实际应用中，这些额外的信息在没有任何代价的情况下，避免了客户端和 Master 节点未来可能会发生的几次通讯。

2.3.2 Chunk尺寸

      选择较大的 Chunk 尺寸有几个重要的优点：

      + 减少了客户端和 Master 节点通讯的需求，因为只需要一次和 Mater 节点的通信就可以获取 Chunk 的位置信息，之后就可以对同一个 Chunk 进行多次的读写操作。

      + 采用较大的 Chunk 尺寸，客户端能够对一个块进行多次操作，这样就可以通过与 Chunk 服务器保持较长时间的 TCP 连接来减少网络负载。

      + 选用较大的 Chunk 尺寸减少了 Master节点需要保存的元数据的数量，这就允许我们把元数据全部放在内存中。

      Chunk设大的坏处：

       + 小文件可能只有一个chunk，有可能成为热点chunk。

       + 内部碎片

2.3.3 租约机制

       如前2.2.2所述，写操作是在主Chunk的控制下执行的，这种租约机制使得 Master 节点的管理负担最小化。

       GFS数据追加以记录为单位，每个记录的大小为几十KB到几MB，如果每次记录追加都需要请求Master，那么Master显然会成为系统的性能瓶颈，因此，GFS系统中通过Lease机制将chunk写操作授权给Chunk Server。获取Lease授权的Chunk Server称为Primary Chunk Server，其它副本所在的Chunk Server称为Secondary Chunk Server。Lease授权针对单个chunk，在Lease有效期内，对该chunk的写操作都有Primary Chunk Server负责，从而减少Master的负担。一般来说，Lease的有效期比较长，比如60秒，只要没有出现异常，Primary Chunk Server可以不断向Master请求延长Lease的有效期直到整个chunk写满。

      假设有Chunk A在GFS中保存了三个副本A1，A2，A3，其中，A1是Primary。如果副本A2所在Chunk Server下线后又重新上线，并且在A2下线的过程中，副本A1和A3有新的更新，那么，A2需要被Master当成垃圾回收掉。GFS通过对每个chunk维护一个版本号来解决，每次给Chunk进行Lease授权或者Primary Chunk Server重新延长Lease有效期时，Master会将Chunk的版本号加1。A2下线的过程中，副本A1和A3有新的更新，说明Primary Chunk Server向Master重新申请Lease并增加了A1和A3的版本号，等到A2重新上线后，Master能够发现A2的版本号太低，从而将A2标记为可删除的chunk，Master的垃圾回收任务会定时检查，并通知Chunk Server将A2回收掉。

2.3.4 数据流

       GFS写流程有一个特色：流水线及分离数据流与控制流。流水线操作用来减少延时。当一个ChunkServer接收到一些数据，它就立即开始转发。由于采用全双工网络，立即发送数据并不会降低接收数据的速率。抛开网络阻塞，传输B个字节到R个副本的理想时间是B/T + RL，其中T是网络吞吐量，L是亮点之间的延时。假设采用千兆网络，L通常小于1ms，传输1MB数据到多个副本的时间小于80ms。分离数据流与控制流主要是为了优化数据传输，每一个机器都是把数据发送给网络拓扑图上”最近”的尚未收到数据的数据。举个例子，假设有三台ChunkServer S1，S2和S3，S1与S3在同一个机架上，S2在另外一个机架，客户端部署在机器S1上。如果数据先从S1转发到S2，再从S2转发到S3，需要经历两次跨机架数据传输；相对地，按照GFS中的策略，数据先发送到S1，接着从S1转发到S3，最后转发到S2，只需要一次跨机架数据传输。

       分离数据流与控制流的前提是每次追加的数据都比较大，比如MapReduce批处理系统，而且这种分离增加了追加流程的复杂度。如果采用传统的Primary/backup复制方法，追加流程会在一定程度上得到简化。

数据流

       Client将待追加数据发送到Primary Chunk Server，Primary Chunk Server可能收到多个客户端的并发追加请求，需要确定操作顺序，并写入本地；

       Primary将数据通过流水线的方式转发给所有的Secondary；

       每个Secondary Chunk Server收到待追加的记录数据后写本地，所有副本都在本地写成功并且收到后一个副本的应答消息时向前一个副本回应，比如上图中A需要等待B应答成功且本地写成功后才可以应答Primary。

       Primary应答客户端。如果客户端在超时时间之内没有收到Primary的应答，说明发生了错误，需要重试。

       当然，实际的追加流程远远没有这么简单。追加的过程中可能出现Primary Lease过期而失去chunk修改操作的授权，Primary或者Secondary机器出现故障，等等。

2.3.5 快照

       快照（Snapshot）操作是对源文件/目录进行一个”快照”操作，生成该时刻源文件/目录的一个瞬间状态存放与目标文件/目录中。GFS中使用标准的copy-on-write机制生成快照，也就是说，”快照”只是增加GFS中chunk的引用计数，表示这个chunk被快照文件引用了，等到客户端修改这个chunk时，才需要在Chunk Server中拷贝chunk的数据生成新的chunk，后续的修改操作落到新生成的chunk上。

       为了对某个文件做Snapshot，首先需要停止这个文件的写服务，接着增加这个文件的所有chunk的引用计数，以后修改这些chunk时会拷贝生成新的chunk。对某个文件执行Snapshot的大致步骤如下：

       1）通过Lease机制收回对文件每一个chunk写权限，停止对文件的写服务；

       2）Master拷贝文件名等元数据生成一个新的Snapshot文件；

       3） 对执行Snapshot的文件的所有chunk增加引用计数；

       例如，对文件foo执行快照操作生成foo_backup，foo在GFS中有三个chunk C1，C2和C3。Master首先需要收回C1，C2和C3的写Lease，从而保证文件foo处于一致的状态，接着Master复制foo文件的元数据生成foo_backup，foo_backup同样指向C1，C2和C3。快照前，C1，C2和C3只被一个文件foo引用，因此引用计数为1；执行快照操作后，这些chunk的引用计数增加为2。以后客户端再次往C3追加数据时，Master发现C3的引用计数大于1，通知C3所在的Chunk Server本次拷贝C3生成C3′，客户端的追加操作也相应地转向C3′。

2.3.6 无阻塞创建Checkpoint

       由于创建一个 Checkpoint 文件需要一定的时间，所以 Master 服务器的内部状态被组织为一种格式，这种格式要确保在 Checkpoint 过程中不会阻塞正在进行的修改操作。 Master 服务器使用独立的线程切换到新的日志文件和创建新的 Checkpoint 文件。