重读 Google File System

前言

本着常读常新的原则，最近又一次阅读了Google三架马车之一的《Google File System》。它里面的一些设计思想，实现原则以及取舍，时至今日仍很有参考价值。

注：下文中我们将Google File System简称为GFS。

GFS特点

Google File System在考虑通用分布式文件系统设计的同时，也更多地从自身业务需求出发，提出了一些新的设计理念和新的系统特点：

• 将机器宕机，重启，挂掉视为常态。 在这样的前提前下，就要求GFS本身要具备快速自动地故障侦测和转移的能力，在监控上允许一定范围内诸如磁盘或网络IO等的小波动，对于客户端来说通过重试或重新获取meta信息后再重试即可平缓过渡到稳定状态。 GFS的这一设计理念，更长远的意义我认为是对于大型存储，计算系统来说，大型机，小型机等不再是唯一的选择，它们同样可以使用相对廉价的普通服务器来构建。
• 支持分块存储超大文件 将大文件作分块存储，每块固定长度64M。GFS的64M可谓是为后世的各个分布式存储块大小定了个基调。下面我们简单说下块大小的优劣势。 大块 小块 元数据量 少（更便于完全加载到内存） 多（元数据过多，可能需多级索引，复杂度增加） 磁盘文件数 少（inode数量不易成为瓶颈） 多 元数据与数据占比 小 大 并行读取效率 低 同一文件有更多的块分散在不同机器上，读取并行度更高 迁移 略慢 单个块迁移更快 空间利用率 略低，剩余空间不足一块大小时会浪费 相对高 压缩存储率 高 低 论文里有提到： Lazy space allocation avoids wasting space due to internal fragmentation, perhaps the greatest objection against such a large chunksize. 在写入前扩充文件空间来实现，但这种方式如何能减少碎片从而避免空间浪费呢？ 按我的理解使用fallocate一次性先预分配64M的chunk文件空间，更有利用磁盘空间的连续分配，且提前锁定磁盘空间，确保写入时不会出错。
• 对文件的修改尽量是追加写，而不是随机写 尽量使用追加写，一是因为追加写是顺序IO，性能高；二是Google的使用场景多是流式读取文件，经过数据分析，然后将中间或最终结果写入到新的文件，不需要特别的随机写需求。 另外，追加写更容易保证写入操作的原子性，这点我们后面会详细讲述。

GFS架构图

下面这张架构图，相信大家已经看过千百遍，我们还是让它再一次闪亮登场：

gfs-architecture.jpg

对于绝大部分分布式系统，都需要解决元数据和用户数据的存储，另外还有客户端读写数据的SDK这三部分。GFS也不例外，在上图可以看出：

• GFS master: 存储元数据
• GFS chunkserver: 存储用户写入的数据
• GFS client: 使用GFS SDK读写数据

GFS元数据管理

元数据分类

• 文件命名空间 类似于Linux目录树的命名空间管理方式。由于对于客户端来说，它们访问分布式文件系统和分布本地文件系统最好是没有任何的差别和感知，因此这种目录树式的管理方式应该是最自然的。 目录树的每个层次可以设置自己的属性，比如chunk复本数等。 目录树的每个层次节点都拥有自己的读写锁，来控制当对前目录的删除，更改等的并发操作，以及其子目录或文件的读，写，删除等并发操作； 此元数据持久化保存。
• 文件到chunk列表的映射 记录每个文件对应的chunk列表 此元数据持久化保存。

gfs-namespace.png

• 每个chunk的所有复本的位置信息 此复本位置信息不持久化保存。 新的Chunk server启动时会将自己注册到Master。Master发送心跳到各个ChunkServer，ChunkServer上报自己所拥有的chunk给Master。

元数据一致性

• 同一时刻，对外提供服务的Master只有一个节点；
• 对元数据的更改都需要加锁进行，比如命名空间各节点上的读写锁；
• 对元数据的变更信息已日志的方式记录到本地，并且同步到其他多台备份Master节点后，才返回给客户端；
• 当前Master节点挂掉后，会迅速切换到热备的Master；
• 除了备份Master节点外，还有影子Master，其上面的元数据版本略落后于Master。影子Master是个兜底的策略，它确保所有的Master节点都无法启动时，影子Master对客户端提供有限的只读服务。

从上面的描述可知，对元数据的变更是以变更日志的方式同步到多个Master节点，然后Master节点在启动时重放变更日志，达到与之前的Master节点一致的状态。

Master的两快

对于Master来说，最重要的是需要两类快速的操作：

• 客户端可以从Master处快速获取到元数据 GFS的作法是将所有的元数据都加载到内存，前面介绍过的64M大的Chunk块减少了元数据量，让这个成为可能。 另外，客户端通常一次会获取多个chunk的元数据，且后续的读写操作不再与master通信，这大大降低了master负载，使其可以高效处理过来的请求。
• master启动快 master发生故障转移，新的master需要将所有元数据信息尽量快速地加载到内存中，以便完成启动并对外提供服务。 前面我们介绍过，master将变更依次持久化到本地磁盘文件。重启后如果重放所有的变更日志，势必会很慢。因此master会定期作内存元数据的checkpoint，这样重启后只需要加载最新的checkpoint文件，然后回放此checkpoint后的变更日志即可。 那加载checkpoint文件会不会很慢呢？Checkpoint 文件以压缩b-tree的数据结构存储，可以直接映射到内存，在用于命名空间查询时无需额外的解析。

Master的高可用

这部分其实前面已经提及到了，从论文上看master分为当前可用的master，实时同时变更日志的备份master，准实时的影子master。

gfs-master.png

常用MetaServer实现方案

通常来说MetaServer至关重要，meta数据的丢失可能直接导致用户数据的丢失。

目前常用的实现方案是MetaServer使用raft协议等作成AP系统，元数据的更改经raft模块后写入每台MetaServer的本地存储，比如RocksDB。

如果集群元数据量非常大，可以将MetaServer集群作分组处理，每组MetaServer管理整个集群的一个子域。客户端首先连接到一个前置服务，获取对应的MetaServer集群信息。

GFS数据读写

数据写入

写入流程图如下：

GFS-WRITE.png

• GFS支持多个客户端对同一Chunk的并发写入 客户端间没有交互，但是GFS需要保证在各个复本上写入的请求顺序是一致的，这需要MetaServer来针对当前的Chunk上确定一个当Chunk。主Chunk来决定到达的并发写请求的写入顺序； 主Chunk由MetaServer来选定，同时赋予一个租约，并通过心跳来续租， 然后客户端要查询Chunk信息时也就获取到了主Chunk的相关信息。
• GFS采取数据流和控制流分离的策略 客户端写入一条数据时，需要和ChunkServer集群有两次交互。 一次是是数据流的传输，为了尽量减少延迟和充分利用每台机器的出口带宽，客户端将数据推送到离其最近的chunk节点，当前chunk节点再继续将数据推送到离它最近的节点，依次类推，直到推送到所有复本。 客户端最终收到推送成功的反馈，然后发送立即写入的控制请求到主Chunk。 由此看到数据流和控制流对应的chunk有可能不是同一个。 GFS这样的数据流式推送方式，能充分利用每台机器的带宽，且是自带三复本“强一致”写入语义，但量从客户端算起经过了三跳，会导致网络延迟增加，而且叠加上数据和控制流产生的多次请求，使得这个网络延迟进一步增加。 目前开源系统常用的基于quorum机制的写入策略有两类：
  1. 星型写 客户端同时写三个复本，只经过一跳，延迟小。写入的一致型，即是否写入成功由客户端决定。需要客户端有较大的出口带宽。
  2. 主从Y型写 三复本选出一个主，客户端将写请求打到主，主同时写两个复本，这样经过两跳，延迟有所增加，也但客户端不需要较大的出口带宽。
• 并发写入流程

gfs-multi-write.png

1.  C1,C2,C3,C4分别代表四个不同的客户端发送的写请求，此刻它们在当前Chunk的三个复本上的推送情况如上图所示，C3和C4已经推送到了所有的复本，并给各自的客户端返回了推送成功的回应；

2.  C3,C4客户端分别给主Chunk发送写入的控制指令；

3.  推测主Chunk为了提高效率批量写入，可能会缓存积累多个写入控制指令。比如C3的写入指令先到，在delay时间内如果C4的写入控制指令也到了，则确定好C3,C4的顺序，先写入本地；

4.  将排序好的写入指令序列推送给其他复本，其他复本在本地写入成功后，将响应返回给主Chunk；

5.  主Chunk将响应分别返回到C3,C4两个客户端；

6.  如果有部分复本写入失败，则此失败的信息也会返回到对应的客户端。

主Chunk失效

分为两种情况：

• 主Chunk宕机
  1. 客户端的写入将失败，重试几次后客户端会请求Master获取新的Chunk信息；
  2. 主Chunk宕机，无法响应Master的心跳，Master确定新的主Chunk;
  3. 客户端获取到新的Chunk信息继续写。

  这里如里Master继续在原Chunk上选取复本，再短时间内复本数少一个。Master也可以封印当前的Chunk，然后返回给客户端，要求客户端创建新的Chunk。

• 主Chunk未宕机，与Master网络中断
  1. 如果当前主Chunk和其他复本间网络正常，客户端可继续通过当前的主ChunkServer写入数据（此时的写入数据有效），直到主Chunk续租失败，此时客户端与Master通讯，重新获取Chunk信息（有可能是创建新的Chunk）；
  2. 如果当前主Chunk和其他复本间网络中断，客户端写入为失败，同样会与Master通讯，重新获取Chunk信息；

Chunk数据一致性

说到数据一致性，线性一致性，顺序一致性，因果一致性，最终一致性，大家应该都是耳熟能详。

我们来看一下GFS中数据一致性的表述：

GFS-FILE-REGION.png

先来解释两个概念：

• Defined 已定义的。意思是说对于一个客户端来说写入成功后，从同样位置读出的就是它写入的数据；
• Consistent 一致的。意思是说复本间相同位置的数据完全相同，客户端无论从读哪个复本，读出的数据都是一样的。

GFS支持多个客户端并行写入，又同时支持随机写和追加写，这给上面介绍的“defined”和“consistent”带来了很多的不确定性。

• 随机写 随机写是客户端提供写入的offset，写入位置固定。 下面我们的阐述都是基于写入相同位置。
  1. 对于串行写，随机写是一个幂等的动作，即使首次写入失败，接下来的重试只要成功，还是写到相同的位置，因此写入成功后读取出来的一定是刚写入的数据，行为是已定义的。
  2. 对于并行写，A,B两个客户端对相同位置的写入操作会在主Chunk上被排序，这样两个写操作的内容会互相覆盖，那么虽然对A的写入操作也返回了成功，但它随后读取到的可能是B写入的数据。此时的行为是一致的，但是是未定义的。
  3. 还有一种比较极端的情况。由于GFS的Chunk是定长，那么有可能客户端的一个写操作要跨两个Chunk。如果此时并行写的两个客户端都出现这种跨Chunk边界写的情况，那么这两个客户端的写入存在都不能保证写入的已定义。这个本质原因是一个写操作由于Chunk边界，打破了原子性。

  

  gfs-split-write.png

上面中客户端A的数据块1和客户端B的数据块1并行写ChunkA的尾部剩余空间，两个写入操作经主Chunk排序后会叠加覆盖，假设结终写入了客户端A的数据块1；同样的流程，新ChunkB的首部空间最终被写入的可能是客户端B的数据据2。如此这般，无论是客户端A还是客户端B想要来读取自己写入的完整数据块时，读取到的就都不完全是数据写入的数据了。

• 追加写 首先需要明确一点，追加写相比随机写不是幂等操作，在重试的过程中可能出现重复数据或空洞。
  1. 对于串行写，如果没有重试就写入成功，则是已定义的，复本上的数据也是一致的。 如果其中有复本写入失败，重试后成功，则结果也是已定义的，但复本局部出现了数据不一致的情况。

gfs-retry.png

如上图所示，左边在写入数据3时，复本1写入成功，复本2写入失败

然后重试，重试后数据3都成功写入了复本1和复本2，且返回客户端的offset是最后一次都成功写入后的数据3的

Offset，客户端用此offset可以读取到数据3，行为是已定义的。

但是对于复本1，写入了两次数据3，复本2中间有空洞，出现了不一致的问题。

对于空洞，GFS的处理是写入特殊的标记，比如特殊的crc校验值，在客户端读取时告知客户端。

对于重复数据，GFS要求客户端自行处理，比如写入的数据中带有唯一标识，供客户端去重用。

2.  对于并发写，由于追加写不会发生跨Chunk的情况(如果当前Chunk剩余空间不够写入，会作填充，然后新创建一个Chunk，供当有写入用)，保证了原子性，写入成功后读取是已定义的。但是会出现和串行写失败重试后出现空洞一样的问题，导致复本间数据局部不一致。

常见系统多点写处理

多点并行写入，会引入不确定性，而这些不确定性对系统的使用者来说也增加了复杂度。

因此，目前常见的系统，更多地是不支持多点写，只支持单点写。

实现上也比较简单，多个写者通过抢锁互斥，抢到锁的客户端通过不断续租来长期持有锁，并且提供主动释放锁的接口，来避免因持有锁的客户端意外挂掉，还需要等租约超时standby的客户端才能抢到锁的情况。

复本选择策略

复本位置选择，遵守两个大原则：

• 最大化数据可靠性和可用性
• 最大化数网络带宽利用率

这就需要在选择位置时，需要考虑不同复本分散到不同机架上，磁盘使用率低于平均磁盘使用率的磁盘被优先选中，而且也要避免同一块磁盘被连续多次选中，因为新的chunk被分配后，很可能紧接着有大量的数据写入，IO容易成为瓶颈。更细致的作法是各个ChunkServer上报各个的IO负载情况，在选择Chunk位置时，结合其负载情况来选择。

后记

关于《Google File System》的重读，我们就先到这里。论文里包含得比这里介绍得要丰富详实得多，这里算作是抛砖引玉吧。