GFS阅读总结

2019/03/24 Paper

GFS作为分布式文件系统,是分布式存储一个经典的类型。读研的时候读过GFS论文,当时只是略读,也没有体会到这篇论文牛在什么地方。工作一段时间之后,再来读这篇论文,有不一样的感觉,有很多问题的解决方法和结论是可以作为工作中的参考。所以详细总结一下,再遇到类似问题可以从中寻找答案。本文中以tips:开头的标黑内容为本人注解,原文中不涉及。

业务场景

互联网公司研发的组件,一般都是有其业务场景的,尤其Google的论文,一般都会把他的业务场景进行描述,这个业务场景影响了组件的设计。

  • 用大量的廉价计算机构建集群,集群越大,节点出现问题的概率越大,因此GFS要能进行各种异常情况的容错。这一点已经成为现在分布式组件的常规要求。
  • 面向大文件存储,一般100M以上,大部分在几个G。
  • 面向大量的顺序读和少量的随机读。
  • 面向大量顺序写和少量随机写,一旦写入,文件内容很少发生变化。
  • 必须对多客户端并发追加写有很好的支持,这是主要写入的业务场景。
  • 大吞吐量比低时延更加重要。

以上分别从存储文件的大小、读写场景、业务特性、吞吐量、时延几个方面描述了业务场景,当我们设计存储系统的时候,也可以从这几个方面对业务场景进行Profile。

提供的接口

  • create、delete、open、close、read、write
  • snapshot(包括命名空间和文件两类),record append

总体架构

总体架构如图所示。最左侧是业务要写入GFS的大文件,在GFS中,文件是分为chunk存储的,每个chunk大小64M。根据业务要访问的文件的位置,可以计算出chunkIndex,把<fileName,chunkIndex>发给Master。Master在内存中主要保存了三类信息:namespace就是目录树,fileName到chunkHandle列表得的映射,及chunk在chunkServer集群中的位置信息。chunkHandle可以理解为chunk的uuid,根据chunkHandle可以摘到对应的chunk。Master收到客户端的<fileName,chunkIndex>后,根据内存中的信息,把<chunkHandle, chunkLocation>返回给客户端。客户端会以<fileName,chunkIndex>为key缓存Master返回的信息,减少访问Master获取元数据的压力。客户端根据<chunkHandle, chunkLocation>访问对应chunkServer的对应chunk。chunk在chunkServer中对应linux文件系统中一个普通的文件,对chunk的操作其实就是对这个linux文件的操作。每个chunk在其他的chunkServer上都有副本,具体数据在各副本的写入参见后文数据写入一节。chunkServer和Master之间通过心跳不断交换信息,这些信息包括chunkServer的存活状况,chunk的分布信息,master根据这些信息进行chunk均衡,chunk恢复等,详细见Master操作一节。

客户端缓存

在GFS中,client不会缓存具体的数据信息,这是由GFS的业务场景决定的,大部分都是顺序读这种场景,缓存数据信息没有太大的意义。但是client会缓存元数据信息,减少client和Master的通信次数,并且元信息很少发生变化,缓存的命中率较高。

chunkSize

chunkSize是GFS至关重要的一个参数。与传统文件系统的chunk相比,64M是一个比较大的数字,比较大的chunkSize有以下好处:

  • 更多的数据访问落在一个chunk上,这样通过缓存就可以得到元数据信息,减少访问Master的次数。
  • 更多的数据访问落在一个chunk上,client与chunkServer的单个连接可以传输更多的数据。
  • 减少Master元数据的大小。所有元数据均保存在内存中,减少元数据的大小可以使GFS保存更多的数据。

同时也有以下缺点:

  • 空间浪费,对于一个小文件或者大文件的最后一块,占用了整个chunk,chunkSize越大浪费越大。
  • 小文件数据热点问题:小文件的chunk较少,大量的数据访问都落在这为数不多的chunk上,容易导致chunk压力过大。

对以上缺点,GFS提出如下应对策略:

  • 懒加载,chunk在创建的时候只是初始化一个空文件,当需要的时候再进行扩展,避免空间浪费。且这样Master进行chunk创建会是一个很轻的操作,可以快速响应客户端。
  • 对于可能存在热点问题的文件,增大副本数,可以提升读性能。

Master元数据和元数据检查点(check point)

上文提到Master中共包含三类信息:namespace信息,fileName到chunkHandle列表的映射及chunk的位置信息。这三类信息中,前两类是需要持久化的,避免Master宕机后元数据丢失。chunk的位置信息是不需要持久化的,因为chunk的位置信息是在不断变化的,通过chunkServer的心跳可以得到最新的位置信息,如果位置信息丢失,等待几个心跳就可重建。相反如果持久化位置信息还会带来数据一致性的问题。tips:这是个很经典的设计,后续的很多分布式系统都采用了这个思想,如TiDB,Elasticsearch等

为了持久化前两类信息,Master采用了操作日志的方法,tips:这也是分布式系统中常见的方法,基本所有的存储系统都有类似的机制。每次元数据的更新都会以操作日志的方式记录到本地磁盘的operationLog中,并且复制到远端保存副本,当本地和远端都成功写入磁盘时,这个元数据的变更才返回给客户端。操作日志的另外一个作用是给并发的操作生成类一个先后顺序。

tips:有操作日志的地方离不开检查点机制。因为当你的操作日志很大的时候如果从头开始重放操作日志重建数据需要耗费很长的时间,并且操作日志本身也会占用磁盘空间。检查点就是选择一个时刻,把内存中的元数据持久化到磁盘中,则该时刻之前的操作日志可以清空。重建数据的时候只需要重放该时刻之后的操作日志即可。tips:很多有操作日志的系统都有检查点机制:Raft,Elasticsearch,Zab等。Elasticsearch和GFS类似称为为checkpoint,但是Raft和Zab中检查点被称为snapshot,GFS中的snapshot则是针对文件的备份操作,读这几篇论文得注意区分一下,避免搞混

一致性模型

对元数据的更改是严格一致的,主要依赖Master在元数据更改时候的锁机制保证,具体的锁机制参见后文的元数据加锁。并发的更改以操作日志中的顺序为准。

对数据更改的一致性比较复杂,如图所示。一致性是指:不管客户端访问哪个副本看到的数据是一致的。有定义是指:客户端可以读到一个完整的数据块。

  • 串行写成功:没有并发,并且所有副本复制也都成功,因此是一致并且有定义的。
  • 并发写成功:多个客户端对同一个offset写入内容,导致客户端之间的内容交叉存在,因此是没有定义的。但是副本之间的数据是一致的。
  • 追加写成功:无论是并发的还是串行的,只要成功写入,GFS保证至少有一分完整的数据,但是各个副本之间的数据不是完全一致的。可能存在padding和重复,主要是部分chunk写入失败后,Client重试导致的。

因此,基于GFS的应用应该尽量采用追加写入的方式,这样写入的数据是有定义的。但是应用需要自己处理padding和数据重复的问题。应用可以给每条记录包含一个checksum用于校验数据的完整性,从而抛弃padding数据。如果应用不能容忍数据重复,则需要定义记录的uuid进行去重。

系统交互

数据写入

每次数据的写入都要写多个chunk副本,为了避免并发写入出现的顺序问题,需要一个主chunk来定义数据的写入顺序,这个chunk称为Primary Chunk。Master通过心跳选定一个chunk为Primary Chunk, 该Primary Chunk有60s的租期,租期过期后Master需要重新选定Primary Chunk。60s内如果存在连续写入操作,Master则会延长该Primary Chunk的租期。对应的,其他的chunk称为Secondary Chunk。

数据的写入机制如图所示。

  1. Client根据<fileName, chunkIndex>向Master请求对应的chunk及位置信息,当然包括Primary Chunk的信息。
  2. Master向Client返回chunk信息,Client对该信息进行缓存。
  3. Client选定一个顺序将数据推送到各个chunk副本,这个顺序可以是任意的,Client一般会选择最近的chunkServer开始推送,收到数据的chunkServer会以pipeline的形式立即推送到下一个chunkServer。每个chunkServer收到数据后,放在内存中的LRU cache中。
  4. 等所有的chunkServer通知Client数据接收完毕后,Client向Primary Chunk发送写入命令。Primary Chunk会给该写入命令一个序列号,并把LRU cache中的数据写入本地磁盘。
  5. Primary Chunk向Secondary Chunk发送写入命令,Secondary Chunk会严格以序列号的顺序把LRU cache中的数据写入磁盘。
  6. Secondary Chunk回复Primary Chunk表示自己已经写入完毕。
  7. Client向用户返回结果。如果这个过程发生错误,各个chunkServer可能存在数据不一致地方,客户端会在相同的offset重试3-7这个步骤。

tips:这个过程经典的设计是数据流和控制流分开,这也是GFS写入数据量较大这个业务场景决定的。如果数据流和控制流走一样的路径,意味着Primary Chunk要向所有Secondary Chunk推送数据,在数据量大的情况下,Primary Chunk的带宽会成为瓶颈。

原子追加写入

普通写一般会指定一个offset写入,在并发的情况下,可能出现多个客户端数据交叉写入的情况。原子追加写入则只指定data,不指定offset,offset由GFS决定。原子追加写入从流程上和上述的普通写入流程是一样的,在Primay Chunk多了一个padding的流程。Primary Chunk会检查当前chunk剩余空间够不够,不够则进行padding,并通知Secondary Chunk进行padding,最后通知Client在下一个chunk重试。

Primary Chunk向Secondary Chunk复制的时候,如果发生错误则进行重试,并把对应的位置padding补齐。最后可能在Secondary Chunk存在不完整的冗余数据,原子追加写不保证各个chunk数据完全一致,但是保证至少包含一个完整的记录(defined),客户端需要自己实现响应的机制进行完整性检查和去重,可参见一致性模型小节。

Snapshot操作

snapshot就是对一个文件或者一个目录下所有文件进行备份操作。为了避免snapshot操作长时间阻塞文件的写操作,GFS采用了copy-on-write机制。当Master收到snapshot操作指令时,为了避免新数据的写入,Master会收回涉及到的Primary Chunk的租期,然后生成一个元数据的snapshot,并指向相同的chunk。当有数据写入时,Client发现没有Primary Chunk便向Master发出请求,Master发现对应的Chunk引用计数大于1,便将所有的chunk在本地复制一份,把复制后chunk对应的信息返回给Client,Client的数据写入也就发生在新的Chunk上,原来的Chunk作为snapshot保存。

tips:与GFS类似,Raft在对Raft Log进行检查点的时候也利用了copy-on-write机制,Raft提到c++的fork函数会把进程的内存空间也fork一份,非常方便实现copy-on-write机制。Zab则与两者不同,Zab采用了Fuzzy Snapshot的机制,简单的说就是比如一个更新操作i++,Zab会把它转化为i=2这样一个结果复制到其他节点,i=2这个操作是幂等的,apply多少次对结果没有影响,所以Zab的检查点只需记录对应的操作日志的id,然后apply该id之后所有的操作即可得到最新的数据。但是Zab的snapshot可能并不对应于某一时刻真实的数据

Master操作

元数据加锁

为了保证并发情况下对元数据修改的正确性,需要对元数据进行加锁。为了提高并发度,GFS采用了分层加锁的机制来减小锁的粒度。GFS元数据中每个目录或文件都有一个读写锁,根据操作的类型,决定对对哪些节点加读锁哪些节点加写锁。举一个文中的例子:当把/home/user snaphost到/save/user时如何避免/home/user/foo文件的创建?

  • snapshot操作会对/home,/save加读锁,对/home/user和/save/user加写锁
  • /home/user/foo文件创建会对/home,/home/user/加读锁,/home/user/foo加写锁

在/home/user上写锁和读锁冲突,从而保证了正确性。/home/user/foo文件和/home/user/bar两个文件的创建并不会冲突,从而提高了并发度。为了避免死锁,所有的加锁操作都要按照固定的顺序比如从根到叶子的顺序,这样可有效避免死锁。

tips:和数据库的X,IX,S,IS锁原理类似,可以参考数据库的隔离级别与2PL/MVCC算法原理 — langrx这篇文章

chunk分配

chunk分配的原则是保证数据可用性同时最大利用带宽。为了充分利用带宽,应该尽量将chunk分配在同一个rack内,这样不用经过交换机,带宽利用率高。但当该机柜不可用时,导致所有副本不可用。因此,GFS的分配原则是同一个rack内两个chunk,相邻的rack一个chunk。这是在数据可用性和带宽之间的一个权衡。

tips:Elasticsearch有一个Shard Allocation Awareness机制,可以给不同节点分配不同的标签,当分配Shard的时候选择标签的进行分配。Elasticsearch的这个机制在冷热数据分离,集群跨az方面有重要的用处

chunk调度

Master会在三种情况下新建chunk:创建chunk,恢复chunk,chunk均衡。

  • 当新建chunk时,Master遵循三个原则:1. 选择磁盘利用率较低的chunkServer。 2. 限制单个chunk同时创建的chunk个数,避免chunkServer之后压力过大。 3. 遵循上述的跨rack的原则。
  • 当某个chunk的副本数由于一些原因比如网络分区,节点挂掉等导致其副本数低于期望的副本数的时候,Master会进行chunk的恢复。在恢复chunk的时候,Master会分配相应的优先级,副本数损失较多的chunk优先恢复,当前处于打开的文件chunk优先恢复,阻塞Client操作的chunk优先恢复。恢复chunk位置的选择类似于上述新建chunk的原则。为了避免恢复操作给集群功能带来影响,Master会限制整个集群和每个chunkServer同时恢复chunk的个数。tips:Elasticsearch也有类似的参数由用户配置
  • 为了使整个集群chunkServer的负载比较均衡,Master会选择一些chunk进行迁移,把磁盘利用率较高的chunkServer上的chunk复制到磁盘利用率较低的chunkServer上,然后删除原来的chunk。当然这个过程也受上述shunk个数的限制。

chunk垃圾回收(GC)

当一个文件被删除的时候,GFS采用了懒删除机制,GFS把这个文件改为一个隐藏文件,对应的chunk也不会被删除。当3天以后,该隐藏文件被删除,在此之前,这个文件都是可以被恢复的。隐藏文件删除后,当chunkServer上报心跳时,Master发现对应的chunk已经没有用,回复chunkServer对应的chunk可以被删除。

因为GFS的master中维护了fileName -> chunkHandle list的映射,所以与很多编程语言的垃圾回收相比,简单了很多。并且这种基于心跳的垃圾回收机制有很大的好处。如果采用Master向chunkServer发送删除命令的方式进行垃圾回收,由于各种各样的原因,删除命令可能会失败,甚至在网络隔离的情况下,Master都不清楚chunkServer是否把chunk删除了,这种情况下,维护Master元数据和chunkServer chunk的一致性是一个很麻烦的问题。但是采用心跳的方式进行垃圾回收,就无需考虑数据一致性的问题,如果一次删除失败,在下一次的心跳中,仍然可以回复chunkServer把对应的chunk删除。此外,Master可以选择进行GC的时机,Master可以选择在自己相对空闲的时候,以批量的形式进行垃圾回收,提升垃圾回收的效率,减小垃圾回收对集群的影响。这种延迟回收的机制也给用户恢复误删除的文件提供了机会。

这种延迟回收的缺点就是当集群空间紧张的时候,用户删除文件并不能立即释放集群的空间。因此GFS提供了一个机制,当用户删除一个已经被删除的文件的时候,GFS会加快该文件chunk的回收。并且用户可以给不同目录或文件设置不同的回收时间。

除了被删除的文件对应的chunk需要回收外,有些chunk因为网络隔离等原因,其数据已经过期,这种chunk也是可以被回收的。GFS是如何识别这种chunk呢?GFS对每个chunk维护了一个version,当用户写入数据时,Primary Chunk会将chunk version加1,并复制给Secondary Chunk,所以可以通过Chunk Version来判断哪些chunk是过期的。

tips:Elasticsearch的Shard也有对应version来判别Shard是否过期

高可用

快速恢复

无论是Master还是chunkServer都可以在宕机的时候进行快速恢复,Master通过CheckPoint并回放对应操作日志,快速恢复namespace和fileName->chunkHandle List,等待chunkServer的心跳恢复chunk的位置信息。chunkServer只需在启动后,向Master汇报自己的chunk信息即可。Client在这期间的失败请求,在集群恢复后进行重试即可。

多副本

通过给chunk设置多副本,默认是3保证chunk的高可用,在chunk的副本有损失的时候,Master会自动进行chunk恢复,使其副本数达到预期。

tips:Elasticsearch除了为每个Shard提供多副本以外,还提供了snapshot机制,可以将集群的数据snapshot到S3,HDFS等外部存储系统

Master副本

Master的OperationLog和checkpoint也都被复制到多个机器上,当一个operation在Master及其副本机器上落盘时,才会向Client返回成功。当Master挂之后可以快速在其他机器上重启一个Master,读取checkpoint文件并重放operation log恢复元数据。此外其他机器上的Master也可以提供元数据的读取操作,但是其数据与Master相比,有1s左右的滞后,适用于可以容忍这个窗口的应用。

由于Master会进行元数据的更改,GC,chunk迁移等操作,其他机器上的Master只提供read only的操作。也就是说Master的高可用是一个主备的方案。

tips:HDFS第一个版本没有实现Master的高可用,同时社区发现HDFS Master内存大小会成为限制集群存储容量的瓶颈。在之后的HDFS中,引入了HDFS HA和HDFS Federation分别解决了Master的高可用和单机内存限制的问题,有兴趣可以去HDFS社区查阅相关设计文档。总得来说HDFS HA实现还是比较复杂的,并且依赖很多,架构比较重。虽然GFS关于Master高可用的描述比较少,但是从HDFS社区实现的过程来看,还是比较复杂的。

数据容错

磁盘可能出现位翻转的错误,因此为了验证数据的完整性,chunkServer使用了checksum的机制。一个chunk被分成64K的block,每个block计算一个32bit的checksum。checksum被保存在内存中,并且持久化到log中,与用户的数据分开存储。当用户读取数据时,chunkServer计算block的checksum,校验失败则返回错误给客户端,并报告错误给Master。客户端收到校验和错误则换一个replica重试,Master收到校验和错误则知道该chunk已经不可用,会恢复一个新的chunk并把该chunk删除。checksum机制对读性能有很小的影响,因为当前block的checksum校验和下一个block的读可以并发进行。

针对GFS的原子追加写,GFS采用增量的方式计算checksum,它在写的时候并不会去校验之前最后一段的checksum是否正确,而是直接以增量的方式计算checksum。因为即便之前的checksum是错误的,这个错误也会在读的时候发现。这样增量的checksum计算机制,可以提高原子追加写操作的效率,这毕竟是GFS业务场景里最频繁的操作。

Search

    Table of Contents