A489e6bff549f3eba0ea8f5106f59dae
GFS —— 取舍的艺术

小引

GFS 是谷歌为其业务定制开发的,支持弹性伸缩,为海量数据而生的分布式大文件存储系统。它运行于通用廉价商用服务器集群上,具有自动容错功能,支持大量客户端的并发访问。

GFS 是为大文件而生的,针对读多于写的场景。虽然支持对文件修改,但只对追加做了优化。同时不支持 POSIX 语义,但是实现了类似的文件操作的API。它是谷歌在 MapReduce 同时期,为了解决大规模索引等数据存储所实现的具有开创性的工业级的大规模存储系统。

其主要设计细节如下:

  • 简化系统元信息:Master 中维持了两个重要的映射,分别是文件路径到逻辑数据块,逻辑块与其多副本之间的关系。
  • 较大的数据块:选择了当时看来相当大的 64M 作为数据存储的基本单位,以此来减少元信息。
  • 放宽的一致性:允许多副本间内容不一致来简化实现、提高性能,通过读校验来保证损坏数据对用户不可见。
  • 高效副本同步:在多副本同步时分离控制流和数据流,利用网络拓扑提高同步效率。
  • 租约分散压力:Master 通过租约将部分权力下放给某个 Chunkserver ,负责某个块的多副本间的读写控制。
  • 追加并发优化:多客户端对同一文件进行并发追加,保证数据原子性及At Least Once的语义。
  • 快速备份支持:使用 COW 策略实现快照操作,并通过块的引用计数来进行写时拷贝。
  • 逐节点锁控制:对于每个操作,需要沿着文件路径逐节点获取读锁,叶子节点获取读锁或者写锁,当然文件路径会进行前缀压缩。
  • 异步垃圾回收:将数据删除与其他一些主节点的维护操作(损坏块清除,过期数据块移除)统一起来,成为一个定期过程。
  • 版本号标记:帮助客户端识别过期数据。
  • 数据块校验和:针对每 64KB 的小块打上 32 bit 的校验和。

概述

基本假设

像任何系统一样,其面向的场景需要有一些核心假设,这样其后的所有设计,才能根据这些假设进行取舍。那么 GFS 作为一个分布式的文件系统,其基本假设是什么?可以从几方面来看:错误处理、文件尺寸、修改方式、一致性模型。

错误处理

该文件系统的开创之一在于摒弃昂贵工业级的系统硬件,选用普通廉价的商用服务器硬盘集群作为存储介质。于是就必须在软件层面屏蔽这些廉价硬件的不可靠性,为上层应用提供一个可靠的存储服务,这个和 MapReduce 这种计算框架面对的问题是一致的。另外,在软件层面,通常会有成百上千的客户端在同时访问集群,而他们可能又分布在同等规模的其他机器上。

也就是说,在这种存储介质上构建如此尺度的系统,软硬组件出问题不应该被当做异常而应该认为是常态。比如用户代码有bug、操作系统出 bug、硬盘内存网络甚至电源供应,统统有可能出问题。

那么我们在设计系统的时候,就必须在系统内引入持续的监控以监控各个软硬组件的健康状态;整合出错检测、错误容忍、自动恢复机制,以对基本的错误进行告警、处理和自动恢复。

面向大文件

GFS 设计目标是针对单文件数十M到数G的尺寸。这在当时(2003)看来,已经是很大尺寸的了。当然,随着互联网和通信基础设施的进一步发展,图片和视频等非文本数据的爆炸式增长,现在看来这个假设已经很稀松平常了;不过也由此看出谷歌系统演进的前瞻性。

回到当时的情景,对于数百万计的 KB 尺寸的文件,纵然文件系统可以支持其存储,但是却难以高效地对其管理。因此,GFS 重新对常规文件系统的一些基本设计做了调整:包括文件块(block)的大小,IO操作的流程等等。

追加为主

在 GFS 针对的场景下,所有的文件修改类型,基本以追加为主,很少出现对已经存在的部分的覆盖。至于随机写,更是事实上不存在的。大体上来说,一旦写入完毕,文件就变为只读,并且是顺序读

这样的场景有很多,比如应用持续运行所产生的数据流,比如归档数据,比如一些机器产生的待另一些机器同步或者异步消费的中间数据集。考虑到这些访问模式都是针对大数据文件,如何保证追加操作并发性原子性成为文件系统设计的要点;而传统的考虑数据访问局部性而在客户端做cache,在这里就没有那么有吸引力了,并不需要针对其做额外优化。

协同设计

通过对系统侧和应用侧的联合设计,能够大大提升系统的灵活性。比如 GFS 弱化了一致性模型,在不加重用户代码负担的情况下大大简化了系统设计;又比如,GFS 引入了原子的追加操作,使得多个客户端不用额外的同步操作就可以并发地对同一文件进行追加。

高吞吐

设计上,高吞吐优先于低延迟。因此为了保证吞吐量,可以适当牺牲延迟。也就是说,GFS 比较适合批量任务而非实时任务。

接口

GFS 虽然并没有实现 POSIX (可移植操作系统接口) 语义,但其 API 和文件系统类似,有 create, delete, open, close, read 和 write。此外,比较特别的一个操作是 record append,这个就比较厉害了,或者说是谷歌针对其场景专门优化的——支持多客户端并发写,在 MapReduce 任务 reduce 落盘阶段能大大提高吞吐。

那 GFS 相对于 POSIX的文件系统语义削减了什么呢?比如细粒度的权限控制,多用户、组用户控制,符号链接等等。

架构图

GFS Architecture

GFS Architecture

图画的微言大义,能看出不少信息:

  1. 物理上来说,系统有三种角色客户端(Client),Master 节点和 Chunkserver 节点。Master 节点只有一个,其他的都有多个。本质上,Chunkserver 和 Client 都表现为 Linux 系统上的一个或一组进程。因此 Client 和 Chunkserver 可能在同一台 Linux 机器上。
  2. 逻辑上来说,系统有两大部分,元信息和数据。其中元信息主要包括文件系统命名空间,访问控制信息,文件到其 所包含文件块的映射信息。这部分数据结构存在 Master 上。数据包括一个个文件的实际数据部分,每个文件又被划分为固定大小的 chunk,以某种方式分散在各个 Chunkserver 上。
  3. Client 端包括用户代码和 GFS Client Library 两部分。后者以库代码形式提供,为前者调用。每次进行文件操作,Client 会首先向 Master 询问文件元信息,然后依据获取的数据位置信息去相应 Chunkserver 找对应数据。

还有一些东西图中没详细说明,但是实现上却十分重要的:

  1. Master 维持一些和 Chunkserver 间的系统事件, 包括租约管理、孤儿块回收、数据块的迁移等等。Master 和 Chunkservers 间通过心跳来收集元信息并下发上述控制信息。
  2. 每个文件块(chunk)会在不同机器机架上进行三备份,这是进行容错的最直接粗暴的做法。但是它能带来很多其他的好处,如并发读等等,后面会详细说明。
  3. 客户端(Client)和 块服务器(Chunkserver)都没有像计算机的存储体系结构一样,在 GFS 层面对最近访问的数据进行缓存。一来能简化设计,二来数据块太大,缓存也没啥用。三来,可以利用 linux 系统自身的缓存。

单点 Master

都说单点不好,怎么还爱用单点 Master 呢?因为实在太能简化设计了。如果有全局信息的话,可以很方便的实现复杂的全局控制策略。但是缺点当然也是很明显的,最主要的就是,Master 挂了怎么办,Master 对外带宽过小怎么办。

对于前者,可以通过多种方式来做 backup。在 MapReduce paper解读中分析过几种:snapshot+log,主从,状态外存,心跳恢复。GFS 应该1,3,4都用到了。

对于后者,就是尽量减小 Client 端与 Master 的请求交互与数据传输。GFS 的主要做法:

  1. Client 不与 Master 发生实际文件数据交互,只请求元信息,比如 Primary 数据块的位置信息,然后就去找相应 Chunkserver。
  2. Client 端会做有限时间内的元信息的缓存,这样对于同客户端的一系列连续请求,对于元信息的请求次数也会降到最低。

下面来详细说下读取(filename+offset)流程:

  1. Client 将文件内 offset 翻译为 chunk id + chunk 内 offset。
  2. Client 与 Master 交互,通过 filename + chunk id + chunk inner offset 获取该 chunk 所有 replica 的位置。Client 会缓存此信息到 filename+chunk id -> replica locations 的字典中。
  3. Client 于是就近选一个(当然失败了会尝试下一个)replica, 给其发送请求,带上 chunk handle + byte range,读取数据。

由于上述缓存存在,只要其不过期,后面同一 chunk 的访问就不必在经过 Master。而且这还可以再继续优化,比如说 Client 一个请求中同时请求多个 chunk 位置;比如说 Master 返回的时候不仅返回该 chunk 的各个 replica 位置,还返回在同一文件中请求的 chunk 后面几个 chunk 的各 replica 位置。这些都能有效减小 Master 的负载。

块尺寸(Chunk Size)

chunk 大小选择是个核心设计点。选择了当时看来比较大的尺寸 64MB 作为 chunk 的固定大小,每个块物理上是一个 linux 系统下的文件。这么做好处有三:

  1. 减小 Client 与 Master 的交互次数:Client 向 Master 请求信息,是以 chunk 为单位的,因此在请求数据量一定的情况下,单个 chunk 越大,请求次数就越少。
  2. 减少单个请求的跨 chunk 读取:也好理解,单个 chunk 越大,同一个请求的 byte range 就越大概率落到单个 chunk 中。
  3. 减少总 chunk 的原信息尺寸:存总大小一定的数据,单个块越大,所需块的数量就越少。而单个块的元信息是相对固定的,因此元信息总量就会变小。在 Master 的内存不变的情况下,就能存下更多的元信息,从而使整个系统的容量上限提高。

任何设计都是取舍,选择大块既然有以上好处,就会随之带来以下坏处:

  1. 内部碎片。比如需要存储大量小文件,这些小文件的单个文件尺寸小于一个 chunk 大小,但在 GFS 也至少得占一个 chunk,由此带来大量内部碎片。当然每个文件的最后一个 chunk 大概率也会存在一些碎片。
  2. 小文件热点。如果系统中有大量小文件,并且被分配到一个 Chunkserver 上的话,那么该 Chunkserver 就可能会成为热点(因为每个 Chunkserver 可以存的 chunk 一定的话,单个文件占 chunk 少,那么其 serve 的文件数就会多),一般不会有问题。如果真碰到这种问题,可以通过提高小文件 replica 个数来临时解决(那么就可以有更多的备胎来分散请求了)。其他可能的办法,谷歌开始开脑洞了:用类似于 p2p 的方式解决,即一个 Client 可以从其他 Client 上读数据。

不过对于 GFS 来说,小文件不是主要目标流量。

元数据

主要包括几大集合和映射,都存在 Master 的内存中。因此 Master 内存单位尺寸的数据对应的元信息大小决定了系统的容量。

1. file list 和 logic chunk list
2. file name -> chunks(identify by id)
3. chunk id -> chunk replica location

这里 GFS 学了数据库的惯常操作,将对前两个数据结构的任何改动都存在了操作日志里,以在必要的时候进行恢复。至于最后一个映射,它采用了另外一种策略:每次 Master 恢复时,通过各个 Chunkserver 的心跳来构建和维持该映射。为什么会有这个不同呢,卖个关子,下面讲。

基于内存的优劣(In-Memory Data Structures)

将所有元信息存放在 Master 内存中,有诸多好处:

  1. 最直接的就是简单。很多时候简单就是强大:意味着好维护,好扩展,性能好等等。
  2. Master 能很方便获取全局信息,从而用来:回收孤儿 chunk 以释放空间,重新备份 chunk 以应对故障,不断迁移 chunk 以平衡负载
  3. 内存成为瓶颈了,加内存就好了。

坏处就是 Master 内存确实可能成为瓶颈和单点。单点这里不细说。关于容量瓶颈问题,首先当时 GFS 的面对的存储量级还没现在这么大;其次每 64M 文件块可以压缩到只有平均 64 bit 元信息。最后,大多数文件假设都是占好多块的。总体来说,就是尽量压缩单位数据所对应的元信息,从而在 Master 内存受限的情况下最大化系统容量。这个上面好像说了,没办法,谷歌的论文就是重复再重复,毕竟,对于写文章来说,呼应就是美嘛。

块位置(Chunk Locations)

一开始 GFS 也是打算在 Master 上持久化 chunk 的各个副本位置的信息。后来发现,每次被动从各个 Chunkserver 中那里收集更简单直接。因为每个 Chunkserver 天然知道自己一亩三分地的 chunk replica 的信息,每次由他们汇报给 Master 能保持信息最一致。假设这个信息持久化在 Master 中,Master 宕机后恢复时从本地恢复这个信息到内存,但是在这个空当内,好多 Chunkserver 挂了,好多 Chunkserver 又加入了集群,这样信息就不一致了嘛,还得通过心跳来同步达到一致,那么干嘛不一开始就通过心跳来构建呢?

我思考了下,以为这么设计 chunk id -> chunk replica location 的持久化方案的核心点在于,它不像 filename,file -> chunk 这两个映射,在 Master 宕机的情况下,是无法更新的;而由于大规模集群的中单个 Chunkserver 的不靠谱性以及各种运维操作的不确定性,是不断变化着的。这是分布式集群的一个固有特点,因此这个设计可以说是会心一击。

操作日志(Operation Log)

操作日志,用来持久化 file namespace 和 file name -> chunk 的映射,有两方面的作用:

  1. 如前所述,用以持久化上述元信息,并且在 Master 宕机恢复后进行元信息重建。
  2. 对于并发操作,用来确定操作顺序,相当于一个''锁''的概念。

因此,对于 GFS中文件,文件块以及版本号的信息,都可以唯一的由他们写入操作日志的顺序所决定。

操作日志如此重要,因此我们不能只在 Master 硬盘上对其进行备份,万一 Master 整个完蛋了呢?还要将其同步至其他远程机器。之前也提到了,这个日志有点类似于 WAL (Write Ahead Log),所有修改操作必须先要写入操作日志之后,才能应用到 Master 的内存数据结构中,进而暴露给 Client。否则,宕机恢复时,Client 和 Master 拿到的信息的往往不一致。(当然为了避免频繁刷盘影响正常的请求性能,可以将一些操作 batch 后再刷盘,但是也这会带来不一致问题,因此这些考虑需要根据实际业务场景进行灵活调整)

有操作日志的地方就有 checkpoint。因为一个大型系统面对的请求实在太多,如果每次 Master 恢复时,就从最开始读操作日志进行恢复,这个过程将会相当漫长。为了压缩操作日志,很自然的想法便是定期 checkpoint,将某个时间节点之前的日志所对应的状态机或者内存数据结构以某种方式持久化下来。GFS 选的是 B 树,因为它可以对应加载到内存中,而不用做一些转化(比如说 通过kv 对构建字典),从而进一步加速恢复时间。

做 snapshot 时,GFS 用了一个小技巧,来避免和当前对操作日志的写入冲突(毕竟同时修改一个文件得加锁)。就是每次到了做 checkpoint 的时间了,就将操作日志切到一个新文件中。然后新启动一个线程,在后台将老文件转化为 checkpoint。

虽然做完最新的 checkpoint 之后老的 snapshot 就可以释放了。但是小心驶得万年船,GFS 在实践中往往会多保留几个 checkpoint。

一致性模型

这一块是我最初读论文的时候比较难以理解的地方,但是后来想通了发现很巧妙——在系统满足应用需求的情况下,适当放宽一致性的限制,会大大简化实现

在详细展开 GFS 的设计之前呢,必须先要搞清楚一个问题,是什么引出了一致性问题?如果这个问题不清楚,那么下面所讲 GFS 的一大堆设计,你可能根本不知道它在干嘛,这也是当初我读不懂这一块的原因。答案是多副本(replica),凡是有多副本的系统,必然需要面对一致性问题。因为网络的不靠谱性,Client 的不靠谱性,Chunkserver 的不靠谱性,总而言之,就是分布式系统各个节点,以及各个节点间的通信都不靠谱。而将一份内容同步到多个副本是需要时间的(因此该操作不是原子的,可能会使系统停在一种蛋疼的中间状态),在这个时间段内,任何一个部件(Client,Chunkserver以及网络)出现问题,就会造成不同副本的不一致,后面的 Client 在读的时候面对不一致的 replica 就会发愁了,以谁为准呢?

GFS 的承诺

GFS 觉得,不用提供完全的 POSIX 文件系统的语义,只需要以下几个基本承诺,在所面对的场景下,就够用了:

  1. 文件命名空间的改动(如文件创建操作)是原子的

对于第一点,最简单的实现就是在 Master 中文件命名空间的数据结构外加一把大锁,所有操作都是互斥的,也就是对他的任何改动是原子的,通过操作日志能将所有的操作确定一个顺序。但是锁的粒度太大必然影响性能,因此在文件目录树中,其实每个节点都会有锁,具体加锁过程,稍后会详述。

  1. 修改后的文件块的状态取决于修改类型,修改成功或者失败,是否为并发改动

修改后的文件状态

修改后的文件状态

如上图,文件块的状态有三种,一致性级别由高到底:已定义(defined),未定义(undefined)但是一致的(consistent),不一致的。理解这几个级别需要一些背景,论文中不同的地方提到了,这里重新组织一下:

  1. 修改操作。包括写操作和追加操作,写操作需要指定文件块+offset。追加操作成功后系统会将追加成功的偏移量返回给客户端。
  2. 并发写。如果两个客户端同时写同一个文件块的同一偏移量,那么就有个先后顺序问题,如果接近同时,系统不保证并发顺序。那么其中客户端再去读,就不一定能读到自己刚写的数据。
  3. 追加失败。追加操作会保证至少成功一次。追加操作时,假设配置三副本,但是只有两个副本写成功,最后一个副本超时了(可能对应块服务器宕机,当然重启后 GFS 会用 chunk version 来标记其过期 stale 了,从而跳过该 offset。),那么追加操作会重试,并且会失败数据不会删除,但是 GFS 有对齐操作,即重试成功后,三个副本中该追加数据的起始偏移量是定义的(也就是一致的),那么其中那个上次失败的副本就会有个空洞,系统会用特殊字符填充。

明白了这些背景,先说一个结论,定义未定义针对的是多客户端并发写同一个偏移量的覆盖顺序问题;一致不一致针对的是多个副本相同偏移量的内容是否相同。再来详细解释这几个名词:

  1. 已定义(defined):客户端写某个偏移量后,再读该偏移量的数据,读到的一定是刚才自己所写。
  2. 未定义的但是一致的(undefined but consistent):多个客户端并发写同一个偏移量,不确定谁会覆盖谁(这个顺序由 Primary Replica 所在 Chunkserver 来安排,后面将会讲),即写完后再读,不确定是自己写的还是其他人写的。但是保证最终一致性,即并发写完成后,最后几个副本是一致的。
  3. 不一致的(inconsistent):即修改操作后,所有副本同一偏移量的数据并不完全相同。

此外值得一提的是,由于客户端会缓存文件块位置,他可能会读到旧的信息。当然,过期事件和重新打开其所在文件会刷新此信息,但是有一个窗口期会拿到过期信息。但由于GFS大部分场景是追加的,因此一般不会拿到过期数据。

对用户代码的影响

通过使用其他技术手段:依赖追加而非随机写,检查点技术以及可以自校验,自定位的 Record 写(就是在应用层或者库中做校验和打ID),可以放心使用上面所放宽的一致性模型。下面对这几个技术详细解释一下。

  1. 追加写和检查点

    GFS 事实上面对的场景是追加写远多于随机写的,那么在几乎只有追加写的场景下,保持一致性的策略就可以简单的多了。一个典型的场景,就是一个 writer 从头写到结尾,利用两个小手段可以保证一致性:a. 写完后重命名;b. 定期做检查点。前者可以保证写文件的原子性,要么完全可以见,要么完全不可见。后者来说,每个检查点其实就是已定义的,自然是一致的,reader 可以放心的读到最后一个检查点。哪怕 writer 故障重启后,也可以从上一个检查点开始增量写。在此过程中,reader 不会读到不一致的数据。

  2. 自校验和自定位

    另一个经典的场景是多 writer 并发追加以合并分片结果或者充当生产消费队列。之前也提到,对于追加写,GFS 提供至少成功一次的语义保证。由于记录写失败了会重试,但是并不会删除,那么就必然存在一些失败记录(表现为一些 replica 上的失败记录和另一些 replica 上的 padding)。

    GFS的策略是将对这些错误记录留给 reader 进行处理。具体处理方法是,对于写坏的记录,可以用 writer 写入的校验和进行校验从而跳过;对于写重的记录,writer 提供了 record id,reader 可以在读取的时候根据其进行过滤。

    当然,上述逻辑的代码都内置在了库函数中,应用层代码可以很方便的调用。

系统交互

所有读写流程设计有个大方向,就是尽量减少主节点(Master)的参与,因为主节点很容易编程单点瓶颈。基于此,接下来详细描述一下客户端,主节点,块服服务器是如何交互来完成数据的变动,原子的记录追加以及快照操作的。

租约和修改顺序

分布式系统上的文件修改包括元信息的修改和文件块的写入和追加操作。文件块的修改操作会作用于其所有副本上,不同副本的写入顺序需要时确定的,而前面所说,必须减少主节点的参与,所以由主节点来安排这个顺序是不合适的。因此 GFS 使用了租约(lease)的手段,Master 会定期向 chunk 的某个 replica 所在的服务器进行授权(有超时时间,所以称为租约),拿到授权的副本称为主副本(primary replica),由其进行写入顺序的安排。这样就将主节点的权力用类似于尚方宝剑的形式在某一段时间内代理给了其选定的副本所在的服务器,当然,有两个限制:

  1. 权力范围。只针对该 Chunk。
  2. 租约时间。有超时时间(初始为60s),需要定期续约。一般只要其不死,Master 都会同意其续约请求。不过偶尔 Master 也有为了防止某些 Chunk 被修改主动收回租约的时候,比如说要做快照了。
top Created with Sketch.