Google File System Note

GFS是一个可扩展的分布式文件系统,可以运行在普通的商用硬件上,提供高性能和容错能力;GFS在Google内部广泛使用,用于满足各种服务产生和处理数据的需求。

这篇笔记基于Google的 GFS 论文

1. Introduction

GFS的 设计目标 和以前的分布式系统类似

  • Performance
  • Scalability
  • Reliability
  • Availability

不过还基于一些别的观察:

  • 普通商用机器产生 故障 是常态而不是意外:监控,错误检测,容错,自动恢复等需要被集成到系统中
  • 以传统标准来看,文件是 巨大 的(Multi-GB)
  • 负载以 append/sequential read 为主而不是random write/read
  • 协同设计应用和文件系统API有益于增加灵活性

目前最大的GFS集群有超过1k个节点和300TB+的数据,被几百个客户端持续使用 P.s. 指Google内部,本篇论文发表于2003年

2. Design Overview

2.1 Assumptions

  • 基于普通商用硬件,故障是常态
  • 主要用于存储大文件
  • 两种主要的读负载:large streaming read / small random read
  • 一种主要的写负载:large sequential write(append)
  • 需要高效支持并发的append
  • 持续的大带宽传输比低延迟更重要

2.2 Interface

GFS提供类似于普通文件系统的接口,基于文件和目录的层级结构;此外还提供了snapshot和append功能。

  • create,delete
  • open,close
  • read,write
  • snapshot: 低代价复制文件或目录,copy-on-write
  • record append: 并发地、原子地追加记录,可以用于多路合并或生产者-消费者场景

2.3 Architecture

GFS Architecture

GFS集群包括一个master节点和多个chunkserver节点,被client访问;这些基本都是运行在Linux机器上的用户态程序;

GFS里的文件被分成固定大小的chunk,每个chunk有一个全局唯一的、不可变的64-bit chunk handle;这些chunk作为Linux文件存储在chunkserver,通过chunk handle + byte range进行读写;chunk会被复制到其他的chunkserver上,一般会有三个副本;

master维护所有的文件系统元信息,包括namespace,访问控制信息,文件到chunk的映射,chunk当前的位置等。它也控制系统范围的活动,包括chunk的租约管理,GC,chunk迁移等。master与chunkserver之间通过HeartBeat信息交互。

GFS client链接到了应用当中,它实现了文件系统的API接口。client与master交互元信息,与chunkserver交互数据。

client和chunkserver都不缓存数据。client不缓存是因为文件一般很大,缓存并没有意义,另一方面缓存会带来一致性问题。chunkserver使用Linux的缓存,自己并不维护缓存。

2.4 Single Master

单主可以极大的简化设计,但是必须减少master在读写中的参与,避免其成为瓶颈。client不会通过主读数据,只会读取元数据。如Figure1所示,一个简单的读过程如下:

  1. client根据文件名,偏移和固定的chunk大小,计算chunk index
  2. client向master获取对应的chunk handle和chunk地址
  3. client缓存chunk地址(key为文件名+chunk index)
  4. client发送chunk handle和偏移,向chunkserver请求数据

缓存的chunk地址信息,可以在下一个请求的时候使用,避免client-master频繁交互。

2.5 Chunk Size

GFS里的chunk大小为64MB,比传统的文件系统块大很多。chunk在chunkserver上作为普通的Linux文件存储,按需扩展;延迟空间分配可以避免内部碎片;内部碎片可能也是这么大的chunk size最不好的地方。

优点:

  • 减少client-master交互,尤其对于大文件来说
  • 减少了元数据数量,可以把元数据存放在内存里
  • 对一个较大的chunk进行操作时,可以使用一个持久TCP连接(不需要多次建连接)

缺点:

  • 一个小文件可能只有几个甚至一个chunk,那么某些chunkserver可能会成为热点

热点问题实际中一般很少出现,因为应用主要使用一些比较大的文件。不过GFS第一次被一个batch-queue系统使用的时候,遇到了这个问题。这个系统存储了一个可执行的二进制文件,占一个chunk,然后在几百台机器上启动了。存储这个二进制文件的chunkserver有几百个并发请求,负载变得很高。

解决方法是调整这个二进制文件的复制参数(副本数?),并且使应用渐进启动它。

2.6 Metadata

master在内存里存储了三种主要的元数据:文件和chunk的namespace,文件到chunk的映射和chunk的位置。前两种元数据通过operation log持久化到磁盘上,并且复制到其他机器上。chunk的位置信息并不持久化,master会在启动的时候或者新的chunksever加入的时候要求chunkserver汇报这些信息。

2.6.1 In-Memory Data Structures

由于元数据放在内存里,master的操作一般很快,而且还可以高效的扫描整个状态,比如实现garbage collection, re-replication, chunk migration等。

一个可能的问题是,master的内存大小决定了系统的容量。实际上,每个64MB的chunk的元数据一般小于64个字节,所以这一般不是个问题;如果需要,也可以扩展master的内存大小。

2.6.2 Chunk Locations

master并不持久化chunk位置,它可以在启动的时候轮询chunkserver,获得这些信息。此外,master控制了所有的chunk的放置信息,并且通过HeartBeat更新这些信息。

在master上不持久化chunk的位置信息,是一个更好的设计选择。因为持久化需要维护master和chunkserver上的信息一致,在chunkserver加入/离开集群,重启,更改名字等等操作的时候,做相应改变。在一个有几百台机器的集群里,这些事情一致在发生。

从另一个角度来理解这个设计决策,chunkserver对有哪些chunk和没有哪些chunk有发言权。维护master和chunkserver的一致是不可能的,因为总会有各种事情发生的chunkserver上,比如文件消失了,或者chunkserver改名了。

2.6.3 Operation Log

operation log是元信息的持久化记录,反映了并发操作的执行顺序,对GFS来说非常重要。operation log需要被可靠的存储起来,每次操作需要复制到本地和远端之后才能给客户端响应。master可以将operation log做批量提交以进行优化。

master通过回放operation log恢复文件系统状态,可以通过checkpoint机制减少启动时间。回放的时候,装载最近的checkpoint和之后的log就可以。checkpoint本身是类似B-tree的结构,可以被直接map到内存里,不需要额外的解析。

checkpoint可能需要一段时间,master可以在不阻塞修改的情况下进行checkpoint。master先切换到一个新的日志文件,并且在独立的线程里进行checkpoint,新的checkpoint包含切换之前的所有修改;同样,完成之后需要持久化到本地和远端。

2.7 Consistency Model

Consistency Model

2.7.1 Guarantees by GFS

master的修改操作是原子的,通过namespace的锁机制保证原子性和正确性,并且是全局有序的。

对文件某一区域的数据修改后的状态,取决于不同的修改类型,成功与否,是否有并发,表1总结了各种情况。

  • consistent : 客户端无论从哪个副本读,看到的都是一样的数据
  • defined : 客户端修改数据后,数据是consistent的,并且客户端可以看到完整的数据修改

当没有并发的请求,并且修改成功时,被修改的区域是defined - 所有的客户端看到同样的、修改后的数据。

并发的、成功的修改,被修改的区域是undefined,但是consistent - 所有的客户端看到同样的,但不是任何一次修改的完整数据。

如果修改失败,被修改区域是in-consistent,因为不同客户端可能看到不同的数据。

上述修改可能是write或者append操作,write写入一个应用指定的位置,append追加数据到GFS选择的位置,这个位置被返回给应用,作为一个defined 区域的offset。对于append,GFS至少会插入一次。GFS可能会插入填充内容或者冗余的记录,占据in-consistent区域。

经过一系列的成功修改,被修改的区域可以保证是defined,GFS通过如下方式保证:

  1. 在所有副本上有序修改(由primary 定序,后面会讲到)
  2. 使用chunk的version number检测过期的副本(没有接收到部分修改,stale replica)

由于客户端缓存了chunk的位置,他们可能在过期的副本信息还没刷新的时候,读了这些副本。这个时间窗口,可以由chunk位置信息过期和文件重新打开(会刷新位置信息)收窄。append操作不会返回错误的数据,只会返回一个不正确的offset。

注:看上去还是有问题

修改成功很久以后,组件故障当然还是会损坏或者毁灭数据。GFS通过握手信息识别损坏的chunkserver,通过checksum校验数据。如果发现了问题,数据将通过可用的副本复制出来。如果一个chunk的所有副本同时丢失,那么这个副本将是不可恢复的,通常是在几分钟里发生,GFS还来不及反应的情况下。

2.7.2 Implications for Aplications

GFS的应用程序可以通过一些其他的技术,来适应GFS的一致性模型。

  • 尽量使用append而不是write : append比write更高效可靠
  • 使用应用层的checkpoint和checksum : 应用处理的时候只读到checkpoint之前的部分,避免reader读到不完整的数据
  • 使用可以自我验证、自我识别的数据 - append可能会插入填充数据或者冗余数据,reader可以通过记录的唯一键和checksum处理

应用层的checkpoint方法允许writer重启增量更新,避免reader读到不完整的数据;

如果reader不可以容忍重复数据(比如操作不幂等),那么需要加入唯一键标志每一条记录,在读取后去重;

3. System Interaction

3.1 Leases and Mutation Order

修改在所有的副本上进行,但是master会授予其中一个副本租约,使之成为主,主决定了修改的线性化顺序。所以全局的序首先由master授予租约定义,然后由主副本定义的线性化number决定。

租约信息在心跳(HeartBeat)中维护,并且可以延长。master可以根据需要撤销租约,也可以在与chunkserver丢失通信后,等它租约到期,重新授予另外一个副本租约。

Write Control and Data flow

如上图所示,一个写的流程如下:

  1. 客户端向master获取主副本
  2. master回复主副本和其他副本位置
  3. 客户端把更新推送到所有的副本,存放在副本的LRU Buffer里
  4. 所有副本收到推送后,客户端向主副本发送写请求(标识之前的推送);主副本分配线性化number(可能有并发的写请求),提供必要的线性化
  5. 主副本转发写请求给所有副本,其他副本按照线性化number写入修改
  6. 所有其他副本回复主副本已完操作
  7. 主副本回复客户端

任何副本写失败都会返回给客户端,这时候可能主成功了但是其他副本存在失败。这时候认为写入失败,被修改区域处于不一致状态。客户端此时需要处理这种情况,重试写入,重复上述3-7步过程。达到重试次数后可能要从步骤1重新开始。

如果写的请求比较大,或者跨了chunk的边界,那么client会把这些数据分成多个写请求,走上述流程。

3.2 Data Flow

在上述流程里,为了充分利用网络带宽,数据流和控制流是分开的。

为了避免网络瓶颈和高延迟的链路,充分利用网络带宽,数据流推送是线性推送,推送选择“最近”的机器进行推送,而不是其他拓扑(比如树的模式)。根据我们的(Google)网络拓扑,距离可以通过IP地址计算。

为了减小延时,chunkserver之间的数据转发使用TCP,以流水线的方式发送,收到数据后立即转发。在没有网络拥塞的理想情况下,传输B字节数据到R个副本上耗时为:B / T + RL。其中T为网络带宽,L是两台机器之间的传输延时。一般情况下,T为100Mbps,L < 1ms,那么1MB数据可以在80ms左右传输完成。

3.3 Atomic Record Appends

GFS提供了原子的追加操作record append。并发的write到文件的同一个区域是不能序列化的,修改后的区域可能是并发写的混合产物。但是append操作提供原子的至少追加一次的语义,类似于UNIX的O_APPEND。

append操作的执行流程类似于write流程,不同的地方在于,如果append后超过了64MB限制,那么GFS户先做填充,然后让客户端重试下一个chunk。

如果任何一个副本的append失败,客户端会重试这个操作;所以同一个chunk的不同副本可能会包含不同的数据,因为有重复的record。GFS并不保证两个副本每一个字节都相同,只保证数据至少写一次。这个性质与一个成功的写的现象保持一致,即成功的写入数据肯定已经在所有的副本上、相同的offset位置写入了数据,后续写入也应该从一个更高的offset继续。

对于不一致数据的处理如2.7.2所述。

3.4 Snapshot

snapshot功能可以快速的进行文件或者目录的复制,同时尽量减少对写入的影响。用户一般用snapshot快速的拷贝巨大的数据集,或者为当前的状态进行快照,保存状态,然后可以进行更改的实验,最后提交或者回滚。

snapshot使用copy-on-write技术。当master收到snapshot请求后,首先对待快照的所有文件的chunk撤销lease,这样可以让master有机会进行chunk的复制。当lease撤销以后,master把snapshot记录到日志。然后把日志应用到内存中,即拷贝相应的文件或目录的元数据,新创建的文件指向源文件的chunk。

当客户端在snapshot后第一次写入chunk C的时候,会向master请求lease的持有者(主副本)。master注意到chunk C的引用计数大于1,于是延迟响应客户端请求,生成一个新的chunk handle C',并要求所有有C副本的chunkserver生成一个新的chunk C',从现在开始,新的chunk写入和普通写入就完全一样了。

在chunk C所在的chunkserver复制C'可以在本地磁盘复制,避免通过网络复制。

4. Master Operation

master会执行各种namespace相关的操作,并且管理chunk和副本信息,控制系统范围的各种活动

4.1 Namespace Management and Locking

许多master的操作需要执行很长的时间,比如snapshot,而我们又不想推迟其他的操作。所以,我们允许多个操作同时进行,并且使用锁来保证合适的线性化。

GFS并没有一个类似于UNIX的、每个目录一个的数据结构,来记录所有目录的文件,实际上它使用类似查找表的结构,把全路径映射到元数据。使用前缀压缩方法,可以有效的在内存里存储这个查找表。每个namespace的节点(路径或者文件)都有一个对应的读写锁。

例如,一个master操作如果涉及到/d1/d2/.../dn/leaf,它会获得d1, d2...dn的读锁,并且获取leaf的读锁或者写锁;

以snapshot为例,我们将创建/home/user的快照/save/user,这时需要获得/home和/save的读锁,以及/home/user和/save/user的写锁。此时如果要创建文件/home/user/foo,那么需要获取/home的读锁和/home/user的读锁,以及/home/user/foo的写锁。那么这两个操作会被合理的线性化,因为他们试图获取/home/user的锁冲突了。文件创建不需要获取父目录的节点的写锁,因为这里并不是目录,也没有类似i-node的结构,不需要修改父亲节点,无需被保护。

这种锁机制的一个好处是,允许同一个目录的并发修改:只需要获取父目录的读锁和被创建文件的写锁。父目录的读锁可以保证目录不被修改:比如被删除,重命名或者snapshot。被创建文件的写锁可以避免同名文件被创建两次。

由于namespace可能会有很多个节点,读写锁是被延迟分配(lazily)的,并且不适用的时候会被删除。另外,锁是以一致的顺序获取的以避免死锁问题:先按照层级获取,再按照字母序获取。

4.2 Replica Placement

GFS的集群在多个层级上都是高度分布的:通常有几百台chunkserver,跨很多个机架,这些chunkserver又被几百个来自相同或者不同机架的客户端访问。不同机架的机器之间通讯可能跨一个或者多个交换机。此外,一个机架的进出带宽会比这个机架所有机器的总带宽要小。

chunk副本的分布策略,一方面要最大化数据可靠、可用性,另一方面要最大化带宽利用。因此,仅跨机器的分布是不够的(防止磁盘或者机器故障,利用每台机器的带宽),还要跨机架分布。这样,即使整个机架故障(比如共享资源损坏,电源或者交换机等),也可以继续用。同时,对于读来说,可以利用不同机架的带宽。不过带来的代价是,写流量要流过不同的机架。

4.3 Creation, Re-replication, Rebalancing

chunk副本的创建因为三个原因:chunk创建,re-replication, rebalancing

chunk创建的时候,选择在哪里创建副本,考虑一下几个因素:

  1. 磁盘使用率比较低的机器
  2. 最近创建chunk比较少的机器
  3. 跨不同的机架分布

master re-replicate副本发生在副本数低于用户指定的副本数的时候,可能由于以下几个原因:

  1. chunkserver机器故障
  2. chunkserver汇报chunk副本损坏
  3. chunkserver的磁盘故障
  4. 副本数目增加

对于需要re-replicated副本,需要指定复制的优先级:

  1. 丢失的副本数多则优先级高
  2. 正常文件比已经删除的文件优先级高
  3. 阻塞客户端运行的chunk优先级高

master会选择最高优先级的chunk,选择某个chunkserver从一个有效的副本拷贝数据,复制副本的分布和创建副本有类似的考虑:

  1. 磁盘使用率比较低的机器
  2. 控制活跃的并发创建副本的任务数
  3. 跨不同的机架分布

由于需要控制复制副本带来的流量,master会限制整个集群和每个chunkserver的活跃的复制操作的任务数;并且每个chunkserver会通过控制发给源chunkserver的请求,限制用在复制上的带宽。

最后,master会定期的rebalance副本:它检查当前的副本分布并移动副本,以达到更好的磁盘利用和负载均衡。在这个过程里,master会逐渐的进行这个过程,防止一下带来大的流量。此外,master也要通过删除副本来释放可用空间。

4.4 Garbage Collection

文件被删除后,GFS并不立即删除物理空间,而是延后删除(文件和chunk两个级别)。

4.4.1 Mechanism

在文件被删除后,master会像其他操作一样,记录删除日志。但是文件并不是直接被删除,而是被改成了一个隐藏的名字。

在master的扫描中,真正删除超过三天的文件;三天以内,被删除的文件仍然可以使用新的名字访问,并且可以被恢复。当文件被彻底删除后,它的元数据也被删除,文件与chunk之间的链接也被断开。

对于chunkserver,会向master汇报chunk信息,master识别孤儿chunk返回。chunkserver可以就可以删除这些chunk副本了。

4.4.2 Discussion

尽管分布式的GC在编程语言里是一个困难的问题,在我们这种情况下却很简单:master保存了文件到chunk的映射,chunk的副本是Linux里的文件。那么所有master不知道的副本就是垃圾。

对于立即删除来说,延迟删除有几个好处:

  1. 简单而且可靠:比如chunk创建时,某些副本可能成功,有些失败了;chunk删除时,删除消息可能丢失了,master要重新发送,并处理自己失败和chunkserver失败的情况等等;这些情况下,延迟删除更加可靠
  2. 把删除整合进master的后台进程,以更及时的相应客户端请求
  3. 防止误删除操作,可以恢复

延迟删除主要的问题在于,不能立即释放空间。这里提供了处理的方法,如果一个被删除的文件再次被删除,那么空间会立即释放。此外,还允许用户为不同部分的namespace设置相应的复制和释放策略。比如,用户可以指定某些目录树下的文件不需要replication,并且被删除的文件立即释放。

4.5 Stale Replica Detection

对于每一个chunk,master维护了一个chunk version number,来区分正常的和落后的副本。

当master给一个chunk授予lease的时候,会增加这个version number;master自己和chunk的所有副本都应该更新这个version number。如果有chunkserver宕机并重启,重新汇报chunk的时候,master可以检查到。此外,如果master看到了一个值比自己的version number更大,master会假设自己在授予lease的时候挂了,会更新自己的值。

master在和client以及chunkserver通讯的时候,会带上version number以确保chunk是最新的。master会在GC的时候,回收掉这些落后的副本。

5. Fault Tolerance and Diagnosis

组件损坏是正常现象而不是异常,比如宕机或者磁盘损坏。我们必须处理这些情况。

5.1 High Availability

基于两个简单有效的策略来实现高可用:快速恢复和复制

5.1.1 Fast Recovery

master和chunkserver都被设计成在秒级别启动和恢复状态,并不区分正常结束和异常结束。对于客户端来说可能有一点波动,需要重新发送当时的请求。

5.1.2 Chunk Replication

如前所述,chunk可以根据用户设置进行复制,默认是3个副本。

5.1.3 Master Replication

master的日志和checkpoint分布在不同的机器上,有一个master进程会管理所有修改和背景活动(比如GC)。当这个master宕机之后,外部的监控会拉起来一个新的master。客户端使用别名访问master,使用DNS解析。

当主master宕机后,被master可以提供只读访问,但可能和主master有一定的延时,读到的信息可能有落后。

和主master一样,被master也会读取operation log并且应用日志,在启动的时候也会轮询chunkserver,并且会和chunkserver保持通信。但是只有主可以做一些类似副本创建之列的操作。

5.2 Data Integrity

chunkserver使用checksum机制检测数据。GFS的集群里可能有上千个磁盘,上百台服务器,在读和写的时候都可能遇到磁盘损坏等导致数据出错的情况。虽然chunk有副本存在,但是每次做副本间比较是不现实的,因此chunkserver需要自己维护checksum,以独立检测数据是否有问题。

每个chunk被分成了64KB的块,每个块有32bit的checksum。checksum和其他元数据一样,存储在内存里,并且通过日志持久化。

对于读操作,chunkserver会检查数据块的checksum,如果出错,那么会返回错误; 并且向master报告错误,master会从别的副本复制一个chunk,并且删掉损坏的副本。

checksum机制对读性能影响不大,因为:

  1. checksum只需要处理一小部分数据
  2. client会对齐block
  3. 在chunkserver上,checksum的查找和比较并不需要IO,计算的代价相比读IO也可以被忽略

checksum的计算为append进行了特别优化(工作流以append为主),checksum可以随着append进行被增量的更新。即使新添加的部分数据已经损坏,但是我们没有检查到,也可以在读的时候检查到。

对于随机写(覆盖部分已有数据),我们会覆盖掉原来的checksum,因此必须先验证写range覆盖的的第一个block和最后一个block的checksum是没有问题的,然后才能进行写,最后计算新的checksum。

P.S. 对于写range覆盖的block,中间部分的block无论对错都会被覆盖掉,无需验证;但是对于写range涉及的第一个block和最后一个block,没有覆盖到的部分,可能数据是存在错误的,需要先进行验证才能覆盖他们的checksum

在空闲的时候,chunkserver可以对不活跃的chunk进行扫描,以检测很少被读到的chunk是否有数据错误。

5.3 Diagnostic Tools

详细的诊断日志对于问题定位,调试和性能分析都很有帮助,并且代价不大。GFS会记录所有有用的事件,比如server起停,所有的RPC的请求和响应等。日志会被保留尽可能长的时间。

诊断问题时,通过整理不同机器上的RPC的日志可以还原整个交互过程。负载测试和性能分析时,日志可以作为trace分析。

打印日志带来的性能影响是很小的,因为日志是顺序、异步的写;此外,最近的时间也会记录在内存里,用于持续的线上监控。

6. Measurements

6.1 Micro-benchmarks

配置信息: master:一主两备
chunkserver:16台
client:16个

机器硬件配置: processor:1.4GHz PIII
memory:2GB
disk:80GB 5400 rpm
network:100Mbps full-duplex Ethernet
switch: HP 2524
所有机器连接到同一个交换机,客户端连接到另外一个交换机;两个交换机使用1Gbps的网络链接

测试结果:

performance

6.1.1 Reads

N个客户端同时访问GFS,每个客户端每次读320GB文件集合里的4MB,重复256次,一共读取1GB数据。chunkserver一共有32GB内存,预估测试里Linux的缓存命中率大概10%,实际上和cold cache结果类似。

  1. 单客户端,理论上限为12.5MB/s,实际10MB/s,利用率80%
  2. 16个客户端,理论上限125MB/s,实际94MB/s,利用率75%

利用率有所下降是因为可能有多个client同时访问一个chunkserver

6.1.2 Writes

N个客户端同时写入N个文件,每个客户端写入1GB数据,每次写入1MB。理论上限为67MB/s因为每次写都要同时写入3个chunkserver,每个连接上限为12.5MB/s。

  1. 单客户端,理论上限为12.5MB/s,实际6.3MB/s,利用率50%
  2. 16个客户端,理论上限125MB/s,实际35MB/s,利用率28%

单个客户端利用率只有50%是因为网络栈问题,对于pipe line的方式支持不是很好,降低了写入速度。

写入利用率降低和读的情况类似,可能有多个客户端同时写入一个chunkserver。

写入速度比我们想要的要慢,不过实际上这不是一个主要的问题,因为这虽然增加了单个客户端的延时,但在客户端数量很多的情况下带宽并没有受到太大影响。

P.S. 带宽利用率随着客户端增加也会上升

6.1.3 Record Appends

N个客户端同时追加到一个文件,性能受限于最后一个chunk在的chunkserver的带宽。开始速度为6MB/s,增加到16个客户端后,性能降到了4.8MB/s,主要是由于拥塞控制和不同客户端的网络传输速度不同。

在GFS的应用里,一般会同时产生很多个这种文件,也就是说,N个客户端同时append到M个文件,N和M基本会到几十个或者上百个,因此一个chunkserver繁忙的时候,另外一个client还是可以继续append(到另外一个文件?)

flacro

Read more posts by this author.