6.824 Lecture 3 GFS Notes & Paper Reading

Posted on 一 02 八月 2021 in course • 6 min read

1 概要

本课主要是针对分布式系统中容错这个主题进行了讨论，关注的领域是分布式存储系统。先是概述了分布式存储系统的关键点和挑战，然后围绕 GFS 的实现进入了更深入的探讨。GFS 是一个曾经在谷歌中大规模应用的真实分布式系统，对之前课程中涉及到的 MapReduce 应用提供了底层的文件系统支撑。

本课相关的材料:

课堂 Paper - GFS: https://pdos.csail.mit.edu/6.824/papers/gfs.pdf
课堂录像: https://youtu.be/6ETFk1-53qU
课堂 Note: https://pdos.csail.mit.edu/6.824/notes/l-gfs.txt

PS. 从课程官网发现 2021 学年新的课程录像已经同步更新到了 Youtube 上，因为疫情原因，课程是线上授课的形式。和 2020 年度现场授课的课程录像相比，线上授课可以直接打开论文进行讨论，整体的信息更丰富一点。所以从第 3 课开始，切换为 2021 年的课程录像进行学习，之前的两课就不再更新了。此外，课程安排相对旧学年有所调整。

2 要点

2.1 存储系统

构建容错的分布式存储系统是分布式领域的一个关键领域:

分布式存储保持全局的持久状态
应用可以基于分布式存储无状态部署和运行

2.1.1 分布式存储为什么困难?

高性能 -> 数据分片(多服务器)，提升系统吞吐量
大量的服务器 -> 错误是常态: 一台计算机一年出现一次错误，一千台服务器，每天都可能会出现错误
容错设计在大型分布式系统中是必须考虑的 -> 复制
复制 -> 数据同步问题(可能存在潜在的不一致)
强一致性 -> 一致性协议 -> 复杂消息交互和传输 -> 性能降低

在系统引入了复杂性之后，往往会带来另外一个问题，复杂系统就是需要不断地解决不同的问题，然后在实现时对不可能的点做权衡取舍。

2.1.2 分布式系统中的一致性 (high level)

理想的一致性: 就和单服务器表现一样 (完全隐藏背后的大量服务器和复杂交互)
服务器在并发时也能逐次执行客户端操作
读取到的数据是最近写的数据
并发: 单机在应对大量客户端请求时，也需要处理好并发

为了容错引入复制机制，让分布式系统实现强一致性更困难，对于复制协议的实现需要更多的考虑。而复制协议的选择需要考虑实际系统的需求和真实的业务场景。

2.2 GFS

本课的论文是 Google File System，在谷歌当年广泛应用在各种大数据应用(MapReduce, 爬虫, 日志存储分析)中的底层文件系统。

高性能: 复制+容错+某种程度的一致性
成功的系统: 在谷歌内部广泛应用，MapReduce 的底层文件系统，成千台的服务器

2.2.1 Non-standard design

单 Master: 存在单点故障问题
存在不一致性: 弱一致性实现

GFS 的实现不是一个完美实现分布式算法或者理论的标准分布式系统，它是一个谷歌基于自身实际业务特征实现的一个可大规模部署应用的成功的分布式系统。

2.2.2 特点

大规模: 大量的数据集
文件自动分片
全局性: 上千台存储服务器对于所有应用代码来说都是同一个文件系统
容错: 错误比如会出现，容错及自动恢复
业界应用的真实大型分布式系统

2.2.3 设计

应用: 类似 MapReduce 中的 Map 或者 Reduce 任务，作为 GFS 的客户端
Master: 应用与 Master 进行通信执行创建、打开、写入文件操作 -> chunk locations
Chunk: 64 MB，可以多副本
读写: 应用直接与 ChunkServer 通信 -> 系统吞吐量可以很大，多个应用可以并发操作访问
ChunkServer: 文件没有特殊格式，就是以 64MB 保存到 Linux 文件系统中

2.2.4 Master 状态数据

filename -> chunk handles 数组: 一个文件可以由多个 chunk 组成
Chunk handle: 版本号+chunkserver 列表(primary + secondaries)+租约(lease)
Log + Checkpoint : 操作日志及检查点数据
Log -> 持久存储: 操作先写入到 Log
Checkpoint -> 持久存储: Master 内存数据的快照，方便重启时快速启动

单点的 Master 受限于单服务器资源限制，整个 GFS 系统能容纳的文件是存在一个上限的，而且根据后面谷歌工程师的访谈记录，这个限制在谷歌实际应用时，随着业务的发展和数据量的扩大，的确达到了，成为了一个瓶颈。谷歌后来也开始实现了多 Master 的类似系统来优化这个系统。

2.2.5 读文件

客户端向 Master 发送读请求，带上文件名和 offset
Master -> 客户端: chunk handle + chunk servers + version number
客户端: 缓存 Master 返回的数据 -> 降低对 Master 的压力
客户端从最近的 chunk server 读取 -> 减少网络传输时间及降低集群网络流量
chunk server 检查 version number -> ok，发生数据，避免读取到旧数据

2.2.6 写文件

Append 是常见的操作场景: MapReduce 场景，Map 写中间文件和 Reduce 写最终文件都是 Append 操作
写操作需要考虑 chunk 是否有 primary
如果没有 primary 需要提升一个 secondary 为 primary ，并且增加 verison number
version number 必须保存在持久存储中：恢复时需要读取
客户端可以从 Master 拿到该 chunk 的所有 Primary 及 Secondary 节点信息
数据先从客户端写到该 chunk 所有节点: pipeline 的方式，流水线传输数据
Master 需要检测客户端写操作的 version number + lease
存在一个 secondary 写失败，会返回错误给客户端，客户端需要重新尝试写操作
at least once
Chunk 的多个节点之间的数据文件可能不一致

3 Paper

本课的论文是来自谷歌的 GFS，即 Google File System，发表于 2003 年。GFS 在谷歌的服务器集群中是作为 MapReduce 框架等大数据应用的底层分布式文件系统，运行于大量的廉价商用服务器上，并且实现了容错机制，对于大数据任务提供了很不错的性能。GFS 对业界分布式系统设计和实现影响很大，Hadoop 生态中的 HDFS 就是它的开源实现版本。

3.1 简介

GFS 的设计和实现来自谷歌中对于大数据处理急剧增长的需求，是一个基于实际业务需求而设计的分布式系统。实现上，除了考虑传统分布式系统中的扩展性、鲁棒性和可用性等常见特性之外，还根据谷歌的应用实际负载模式和技术环境有额外的考虑：

组件失效是常态而不是异常：硬件是廉价的商用服务器，各种组件都很可能出错，应用 bug、操作系统 bug、磁盘、内存、连接器、网络，甚至电源都会出现问题；
要处理的文件很大：GB 级别，对于当年常见的数据文件来说是非常巨大的；
大部分文件写是追加写：这个是基于类似 MapReduce 这类型应用来说的，并且文件内容一旦写入了，比较少更新，大部分情况下是读取文件内容进行处理，这就说明 GFS 不是用于替换操作文件系统的；
系统 API 设计上是基于应用实际需求来进行的，比如对应用提供的原子 Append 操作支持，在谷歌的应用常见下就非常有用；

GFS 不是设计用来作为操作系统基础的文件系统的，所以并没有提供 POSIX 兼容的文件系统 API。

3.2 设计与实现

3.2.1 假设

GFS 的设计是基于下面这些假设来进行的，在设计一个系统时，先对系统的应用场景进行假设和限制，这样我们最终实现的系统才是真正需要的系统：

系统是在廉价的商业服务器上构建的，服务器经常会失效，这意味着系统必须要时刻检测自身的节点状态，实现容错和快速及时地从错误恢复；
系统存储的是大量的大文件，可能会有上百万个 100 MB 甚至更大的文件，几个 GB 大小的文件也是常见的，小文件可以支持，但是不会考虑特别的优化；
工作负载常见是两种读方式：数据量大的流式读和小数据量的随机读，流式读通常是每个操作几百 KB 或者 1MB 的数据量，同一个客户端一般会顺序读取一个文件的内容，随机读则是在文件的任意 offset 读取几 KB 的数据，对于关注性能的应用来说，通常是将随机读批量打包为顺序往前读取的操作，而不是前后移动；
写方式则常见是大量顺序的追加写文件，操作大小和流式读差不多，并且一旦写入文件内容，基本是不再进行修改，小数据量的随机写也支持，但是不会做特别的优化，效率不会很高；
对于多客户端并发写入到同一个文件的场景，系统必须高效地实现相关的并发语义支持。常见的应用方式是基于文件做生产者和消费者队列的方式，数百个分布在数百个服务器的生产者并发追加写入到一个文件，并发操作的原子同步实现尽量要最少的额外开销，这是很关键的一点；文件读取可能是滞后的，也可能是和写同时进行的；
对于系统来说，高吞吐量要比低延迟更重要，系统支持的应用对于数据处理的吞吐量需求要高于处理延迟，批量大数据处理才是整个系统的目标；

总结下来，GFS 应该是一个支持容错、支持大量大文件和超大文件(GB 级别)存储、特别对顺序流式写和读优化、支持并发追加写和关注整体系统吞吐量的一个分布式存储系统。对于上面的这些假设或者说需求，GFS 是怎么实现的呢？下面是详细的一个架构和交互设计。

3.2.2 接口

GFS 虽然没有实现一个标准的 POSIX 文件系统 API，但是也提供了和常见文件系统非常相似的接口。文件也是层级组织的目录，并且根据路径名标识，支持常见的 create, delete, open, close, read 和 write 操作接口。

除了常见的文件操作之外，GFS 还支持两个比较独特的操作， snapshot 和 record append 。snapshot 操作主要是用来对数据进行备份，支持对目录树或者文件进行低成本的拷贝，实现上是基于 copy on write 的。而 record append 则是特别针对 GFS 的常见应用场景和需求而实现提供的，支持多客户端原子并发写入到同一个文件。

3.2.3 整体架构

上图是 GFS 整体的一个架构，包含了主要的交互节点角色及部分的数据流转和控制交互。在 GFS 中，关键的节点和组件如下：

Master：单节点部署，保存整个 GFS 集群中所有文件的元数据，包括文件命名空间、访问控制信息、文件到 chunk 列表的映射关系、每个 chunk 保存的 chunkserver 位置等；还会进行整个系统基本的操作处理，比如 chunk 的租约信息管理、孤儿 chunk 的垃圾回收检索处理、chunk 在 chunkserver 之间的迁移、复制，并且还会和每个 chunkserver 定时有心跳消息，下发指令及采集状态；
Chunk：文件被划分为多个 chunk，每个 chunk 是固定大小的一个文件，由 Master 分配的一个不可变且唯一的 64 位的 chunk handle 唯一标识，读写操作都是基于 chunk handle 进行的；chunk 保存在普通的 linux 文件系统上，由 chunkserver 管理，并且基于高可用考虑每个 chunk 会有复制的备份保存在多个 chunkserver 上；
ChunkServer：每个数据服务器上都会部署 chunkserver 来负责对文件的 chunk 进行维护，所以一个 GFS 集群中会有大量的 chunkserver；chunkserver 会与 Master 进行心跳交互，向 Master 汇报维护的 chunk 列表及信息，并且根据 Master 的指令进行 chunk 的迁移复制等操作；chunkserver 直接和客户端交互传输和接收文件数据，大量的 chunkserver 可以实现很大的吞吐量；
Client：应用代码会链接上 GFS 的客户端库，通过库提供的文件操作 API 和 GFS 进行读写操作交互，客户端和 Master 交互获取和执行元数据相关操作，然后直接和 chunkserver 进行文件数据传输，GFS 库不提供 POXISX API 支持文件操作，不会接入到 linux 的 vnode 层；

上面所有的节点组件都是运行在廉价的商用服务器上，不会依赖特别高性能或者特殊的硬件。

3.2.4 单节点 Master

从上节的架构中，我们可以注意到，在 GFS 集群中，Master 是单节点部署的。在 GFS 中，单节点 Master 的设计极大简化了整个系统的复杂度，让 Master 可以基于全局完整的信息对文件的 chunk 位置和复制等操作进行策略决定。

另外一方面，GFS 必须对读写等操作交互仔细考虑设计，尽量降低操作和 Master 的相关性，避免单点的 Master 成为整个系统的瓶颈。具体设计上，客户端只会向 Master 请求获取操作相关的 chunkserver 信息，并且将获取到的数据缓存下来作为后续操作的依据，然后直接和 chunkserver 进行文件数据读写交互。文件数据永远不会经过 Master 节点。

一个简单的读流程如下：

首先，根据 chunk 的大小值，客户端将文件名和要读取的字节位置 offset 信息转换为文件中的 chunk 索引位置；
客户端发生一个包含了文件名和 chunk 索引位置信息的读请求到 Master 节点；
Master 节点给客户端回复该文件的 chunk 对应的 chunk handle 值和 chunk 所在的 chunkserver 列表信息，这里应该包含 chunk 的复制数据位置；
客户端根据文件名和 chunk 索引缓存 Master 返回的信息；
客户端直接请求该 chunk 复制数据所在 chunkervser 节点中的一个，提供 chunk 的 handle 值和要读取的字节范围信息，接下来的读操作是由 chunkserver 和客户端进行交互，不再需要 Master 参与；

实现上，客户端选择 chunk 的 chunkserver 节点原则上是尽量选择最近的一个，而谷歌内部集群的服务器 IP 地址是经过精心编排的，可以根据 IP 地址来计算哪个节点是最近的。此外，在应用中，常见的方式是客户端向 Master 请求多个 chunk 的位置信息，缓存到本地，后续再读取文件时，都可以直接和 chunkserver 交互，大大减少了 Master 的压力。

3.2.5 Chunk 大小

chunk 文件的大小是 GFS 中一个关键的设计点，通常是采用 64 MB ，比一般的文件系统块大小要大得多。每个 chunk 都是以普通 linux 文件的方式保存在服务器上。GFS 的每个chunk 在创建时不会一下子分配 64MB 的文件，而是采用了延迟分配的方式，只有在实际写数据的时候才按需进行分片。这样可以避免空间浪费和文件碎片。

一个大的 chunk 文件大小值有几个好处：

减少了客户端和 Master 的交互，因为读写都是可以基于客户端向 Master 初始请求拿到的 chunk 相关信息缓存数据进行；
因为 chunk 比较大，一段时间内客户端和 chunkserver 的交互都是对于同一个 chunk 进行操作，这样实现上可以采用持久的 TCP 连接，降低网络相关的开销；
减少了 Master 需要保存的元数据数量，实现上 Master 会将元数据保存到内存中，整体数据的大小很关键；

同时这个设计也存在不好的地方，比如对于一个只包含几个 chunk 的小文件，如果过多的客户端同时从这个小文件读取数据，有可能会成为系统中的一个热点文件，相关应用的性能会出现问题。

在 GFS 的使用中，这种情况曾经出现过，在一个批量队列的系统应用中，一个程序往 GFS 写入一个单 chunk 的文件，然后触发数百个服务器同时执行读操作，导致保存这个文件的 chunkserver 严重超负载，影响到了这些 chunkserver 上其他文件 chunk 数据的读写操作。简单的一个处理方案是对于这种类型的应用，在执行写操作时，提高文件的复制系数，把文件分散到足够多的 chunkserver 中，降低单个 chunkserver 的可能负载。

3.2.6 元数据

Master 主要是保存以下三种元数据：

文件和 chunk 的命名空间，也就是目录结构及文件路径信息；
文件到 chunk 的映射关系，一个文件可以由多个 chunk 组成；
每个 chunk 的每个副本的位置信息，也就是保存在哪个 chunkserve 上；

对于命名空间和文件到 chunk 的映射信息，Master 会保存相关的修改操作本地磁盘的操作日志文件上持久化存储，并且还会复制到一个远程备用的服务器上。这种方式可以简单地保证 Master 崩溃时相关操作和数据的一致性和可靠性。至于 chunk 的位置信息，Master 不会持久化保存下来，只会在每次启动时或者一个 chunkserver 加入到集群时，直接和每个 chunkserver 节点交互获取相关的信息。

下面将会对 Master 元数据的关键设计点进行说明。

3.2.6.1 内存数据结构

Master 将数据保存到内存中有几个好处:

内存访问速度快，也就意味着 Master 节点处理请求操作的速度很快；
Master 可以方便地定期扫描整个 GFS 集群的状态，根据状态执行一系列的后台处理；

Master 节点的后台处理是 GFS 集群中很重要的内容，对于 GFS 整体集群的数据一致性和高可用等等保证是关键的处理，包含以下内容：

垃圾回收：处理异常导致的无效的 chunk；
重新复制：对于一个 chunk ，如果有副本所在的 chunkserver 服务器挂掉导致复制系数达不到设定的值，需要选择新的 chunkserver 节点重新复制数据，以保证 chunk 数据的高可用；
基于服务器的负载和磁盘空间信息将 chunk 数据在不同的 chunkserver 之间进行迁移，保持整个 GFS 集群的稳定和高效利用；

以上处理在实现上存在比较多的细节和考虑，论文下面的章节中都有具体地进行了讨论。

对于把元数据保存到内存中这个方案，一个常见的关注点是整个 GFS 集群的文件容量是受限于 Master 节点服务器的内存大小的。论文中给出了几点解释，一个是每个 64MB chunk 的元数据不会超过 64 字节，另外真的出现容量问题，在 Master 节点服务器上添加内存的代价是比较低的。相对于可能存在的容量限制和需要硬件更新的代价，完全内存数据结构带来的简单、高效、可靠、性能和灵活性是非常值得的。

PS. 在谷歌应用 GFS 的过程中，容量最终成为了一个不可忽略的问题，根据一个与 GFS 开发工程师的访谈记录，随着谷歌内部的数据量从数百 T 到 PB，甚至到数十 PB 级别，单节点 Master 的确成为了系统的瓶颈。所以后续 GFS 也实现了类似多 Master 的模式。这个访谈记录透露了关于 GFS 的不少有趣内幕，可以看看。

3.2.6.2 Chunk 位置

对于每个 chunk 数据及其复制在哪个 chunkserver 服务的位置信息，Master 虽然会在内存中保存完整的数据，但是不会将这部分数据持久化到磁盘上。Master 节点启动的时候，直接从每个 chunkserver 拉取所有 chunk 的信息，然后后续定期通过心跳消息维持数据的时效性。这个设计有几点考虑：

实现起来比较简单，不需要考虑太多 chunk 位置信息在 Master 内存、磁盘及 chunkserver 状态变化时的同步处理；
此外，chunkserver 是保存 chunk 数据的服务，应当有最准确的 chunk 信息，没必要在 Master 还保持一份持久化信息，chunkserver 的失败是很常见的，数据持久化了再处理同步就很麻烦；

3.2.6.3 操作日志

操作日志是 GFS Master 中很重要的一类数据，关系到 GFS 关键元数据的完整性和可靠性。此外，对于 GFS 上的并发操作，操作日志也天然存在一个逻辑顺序的时间线。对于元数据操作日志， GFS 有以下处理：

用户的操作产生的元数据只有在成功持久化到磁盘后才会对客户端可见；
操作日志会被复制备份到多个远程服务器上，并且要在 Master 本地和远程复制节点都把操作日志持久化到磁盘后才会返回响应给用户；
Master 会将操作日志批量写到磁盘上；

Master 重新启动时，会读取操作日志进行执行来恢复元数据的内存状态。为了减少加载时间，GFS 支持定时将 Master 内存状态数据作为 checkpoint 数据保存到磁盘上。checkpoint 是元数据按内存数据结构直接保存的，在重启时可以直接加载到内存中恢复数据状态，不再需要解析和执行操作。加载完最新的 checkpoint 数据后，Master 只需要将最新 checkpoint 后的操作日志进行重新执行就可以把整体状态恢复到最新了。创建 checkpoint 之前的操作日志可以直接删除掉以减少空间。

checkpoint 数据的创建也有需要注意的地方，在元数据比较多的时候，整个操作可能是比较耗时的，应该尽量避免对 GFS 正常的业务处理造成影响。所以实现上，Master 会在分离的线程上执行相关的创建操作，此外也会切换一个新的日志文件记录新的操作日志。在 checkpoint 创建完毕之后，会持久化到本地和远程磁盘上。

操作日志是现在一些分布式系统中比较常见的设计方案，有些系统也会将其称为 Binary Log (binlog), Write Ahead Log (WAL) 等等。实现上也是差不多，首先系统存在状态，操作日志记录的是对系统状态的变更操作，包括插入/更新/删除。正常业务和处理多节点复制之前，都需要保证操作日志持久化成功。然后为了加速服务重启加载，通常也是采用定时 checkpoint 整个状态数据的方式，此外，还可以对操作日志进行压缩处理，比如同一个 Key 的多个变更操作，可以压缩为最后一个更新或者删除操作。

现在常见的分布式系统中，操作日志也多应用于多复制节点间的数据同步处理，实现上也有差不多的考虑。

3.2.7 一致性模型

GFS 实现的一致性模型是宽松一致性模型，很好地支持了谷歌的大规模分布式应用，同时实现上也是比较简单和高效的。本节内容主要是具体讨论 GFS 提供的一致性保证，以及对于应用的实现上的影响和需要考虑的地方。

3.2.7.1 GFS 的保证

首先，文件命名空间，也就是文件目录树相关的变更操作是原子性的，实现上是通过 Master 的锁机制和操作日志来保证的。锁机制保证操作的原子性及数据的正确性，而操作日志则是明确了操作的全局执行顺序。

对于文件的数据变更操作则复杂得多，操作是否成功，是否并发，都需要考虑。首先需要明确对于文件数据的几个概念:

一致(consistent) : 所有客户端从所有的 chunk 数据副本总是能读到同样的数据;
确定(defined) : 如果对于文件数据的一个变更操作是一致的，并且所有客户端都读到这个写的内容，那么这个文件数据是确定；

变更操作一致性的几种情况：

非并发成功的变更操作，所有受影响的文件都是确定的，也就是这个操作是一致的：所有客户端都可以读到同样的数据，并且看到变更操作的内容；
并发且执行成功的变更操作，所有受影响的文件是未定义状态，但是是一致的: 所有客户端可以读到同样的数据，但是数据可能不是来源同一个操作，更常见的情况是多个并发的变更操作数据混合在一起；
失败的操作会导致文件不一致：不同的客户端在不同的时间点可能从不同的复制节点文件读取到不一样的数据；

变更操作主要包含以下两种:

写操作: 将数据写入到文件指定位置中；
追加写操作: 将数据原子地写入到文件的当前位置，由 GFS 决定和解决并发写的情况；

成功的变更操作后，GFS 会保证相关的文件所有的节点都是确定的，实现的方式首先是在每个 chunkserver 上对 chunk 的多个变更操作顺序都是保持一致的，另外，还会利用 chunk 的版本号信息来判断 chunk 的副本数据是否过期失效。包含了失效数据的复制节点不会参与变更操作或者读操作，并且会尽快被执行回收处理。

之前有提到，客户端会缓存 chunk 的位置信息，所以这个缓存是的确有可能会导致客户端读取到已经过期的副本数据。这个情况无法完全避免，但是实现上会尽量缩减存在的时间窗口和影响。首先客户端的缓存数据是有超时的，在超时后会重新从 master 获取和刷新缓存。然后，对于谷歌来说，大部分的应用模式是追加操作，过期的副本节点一般是返回前面的位置信息，当读者重新从 Master 获取 chunk 信息时，会获取到当前的 chunk 位置信息。

在一个长期运行的 GFS 集群中，即使操作都是成功的，还是会存在组件失败导致数据损坏或者丢失。GFS 主要是通过定期的握手识别失效的 chunkserver 节点，然后通过 checksum 校验检测数据文件是否已经损坏。一个 chunk 的数据只会在 GFS 检测和处理异常之前完全丢失所有复制节点数据的情况下才会丢失，并且也只是丢失，而不是返回错误的数据。

3.2.7.2 应用实现的考虑

对于基于 GFS 的应用来说，要实现宽松的一致性模型很简单，只需要以下几个方式:

优先使用追加操作
数据检测点(checkpoint)快照
写数据自校验、自标识

论文中对于应用的常见提了两个常见的应用例子和实现上的一些细节：

writer 完整写入一个文件的内容：

完成数据写入后会原子地重命名文件；
定期 checkpoint 已写入的数据，可能会包含一些应用层的 checksum 信息；
reader 只会校验和处理到最新 checkpoint 的数据；
追加操作相对随机写更高效并且对于应用错误有更好的容错性；
checkpoint 支持 writer 重启时增量处理数据而不需要重新开始；
checkpoint 可以让 reader 避免处理到已经成功写入但是从应用层面还是不完整的数据；

多 writer 追加写入到一个文件，作为一种生产者-消费者队列的模式:

GFS 数据追加操作的 append-at-lease-once 语义实现保留每个 writer 的输出；
每个 writer 写的记录数据都包含额外的信息，比如 checksum ，这样 reader 可以进行校验；
reader 在读取数据时可以利用 checksum 信息忽略掉额外的 padding 数据和记录数据碎片；
对于重复的记录数据，可以通过记录的唯一标识信息进行过滤处理，比如 web 文件的唯一信息；

3.3 系统交互

GFS 系统设计上考虑尽量减少系统操作交互中涉及到 Master 节点，以降低 Master 的压力。这一节内容主要是描述在 GFS 的数据变更操作、原子记录追加操作、和快照具体实现上，Master，Client 和 chunkserver 是如何交互的。

3.3.1 租约和变更顺序

在 GFS 中，变更是指会修改一个 chunk 的内容或者元数据的操作，比如写或者追加写操作。每个针对 chunk 的变更操作都会应用到该 chunk 的所有副本上。GFS 主要是利用租约机制来实现保证 chunk 变更操作在多个副本上的一致。首先 Master 会选择一个 chunk 的节点，并且给其分片一个租约，这个节点被成为该 chunk 的 primary 节点。然后对于该 chunk 的所有变更操作，primary 节点会选择分配一个顺序的操作序号，其他的 chunk 副本都会按照 primary 选择的顺序应用变更操作。

所以全局的变更顺序是由两个内容决定的:

Master 选择分配的租约顺序；
在一个租约内，primary 节点指定的序列；

租约机制主要是基于减少 Master 的管理开销而设计的。一个租约初始的超时时长是 60 秒，不过，只要这个 chunk 一直被修改，primary 就可以一直请求 Master 扩展租约。租约扩展的请求和分配是附加在 chunkserver 和 Master 之间的定时心跳消息中实现的。Master 也可以在某个租约过期前主动地取消其有效期，以实现一些需要的处理操作。如果 Master 和 primary 节点之间的通讯丢失，Master 在上个租约过期后可以安全地将租约分配给一个新的副本。

下面是一个详细的写操作流程，租约在变更操作中有着非常大的作用：

首先客户端会请求 Master 获取指定 chunk 当前持有租约的 chunkserver 信息和其他所有副本的位置信息，如果暂无节点持有租约，则 Master 会在所有副本中选择一个进行分配；
Master 响应 chunk 的 Primary 节点标识及其他副本位置信息给客户端，客户端缓存这些信息，在 Primary 节点无法访问或者响应不再持有租约时才需要再次和 Master 节点进行交互；
客户端将数据推送到所有的副本节点，并且顺序可以随意选择，每个副本节点 chunkserver 会将数据保存到内部的一个 LRU 缓存中，知道数据被使用或者过期。这是将数据流和控制流解耦的方法，这样客户端可以根据副本节点的网络拓扑信息来优化数据流调度，提升整体的性能，而不用受到 Primary 节点的限制；
一旦所有的副本节点都响应确认接收到数据，客户端会发生一个携带了之前推送的数据标识的写请求到 Primary 节点。Primary 会给这个写请求分配一个顺序的序号，如果存在多个客户端并发的写请求，Primary 节点会选择一个顺序进行分片，然后该写请求的数据将会按序号顺序保存到节点的本地存储中；
Primary 节点完成写操作序号的分配和本地保存后，将写请求发生给其他的复制节点，并且补充序号信息，每个 Secondary 节点都按照序号顺序保存写数据；
所有的 Secondary 完成本地保存的操作后响应给 Primary 节点通知已经完成操作；
Primary 节点响应客户端，如果有任意的副本节点出现错误，这个错误信息也会响应给客户端。这种错误情况一般是 Primary 成功，然后 Secondary 节点的任意子集也成功的情况，这个通常也视为该客户端的请求已经失败，之前被修改的数据会保持在一个不一致的状态。客户端代码会通过重试几次 3 ~ 7 的步骤来处理这种异常，最后会从一开始再尝试整个请求。

如果一个应用的写请求数据大小超过一个 chunk 的大小，GFS 客户端会将这个写请求拆分为多个写操作，然后所有的写操作都会按照上面描述的顺序和各个节点进行交互，也有可能和其他客户端的写请求顺序重叠。所以最终文件的数据是很有可能不同客户端的写请求数据分段保存在一起的，不过所有的副本的有效文件数据内容是一致的，因为都是按照 Primary 节点分配的序号进行保存的。

3.3.2 数据流

在 GFS 中，数据流和控制流是分离的，控制流是从客户端到 Primary 再到各个 Secondary 节点，而数据则是根据具体的网络拓扑信息来流转的。首先，数据是线性地在选择好的一系列 chunkserver 节点中流转的，一台 chunkserver 不会同时把数据发生给多个其他 chunkserver。chunkserver 是基于网络拓扑选择最近的另外一个 chunkserver 发送数据，并且是利用以 pipeline 的模式进行数据转发，也就是每收到一些数据，立即就转发给下一个 chunkserver。chunkserver 之间的距离是可以通过 IP 地址信息来计算的，在服务器集群中，服务器的 IP 是经过特意设计，根据物理位置来进行分配的。

这种数据流转方式，一来每个 chunkserver 都只发生数据给一个其他 chunkserver ，可以最大地利用服务器之间的带宽，另外以 pipeline 的模式发送数据，可以极大地降低整体的数据推送延迟，每个 chunkserver 不需要等待接收到完整的数据再进行转发。

3.3.3 原子追加操作

GFS 对于指定位置的并发随机写并不能保证数据的顺序性，文件最终可能会包含来自多个客户端的数据分片。而对于追加写操作，客户端只是提供了具体的数据，但是最终的文件位置则是由 GFS 选择，原子写入后再返回位置信息给客户端。普通的写需要客户端使用类似分布式锁的机制来实现同步，实现上比较重而且性能开销大。在谷歌的应用中，常见的是追加类型的写操作，一般都是将文件作为多生产者/单消费者的模式应用。追加写的流程和上面描述的类似，只是有一些额外的处理。当客户端推送数据到所有的副本节点后向 Primary 节点发起写请求时，Primary 节点会检查是否写入数据会导致 chunk 超过最大值 (64MB)，如果超过则将 chunk 填充到最大文件大小，并且指示客户端重新在下一个 chunk 发起追加写请求。

任意副本节点上的写失败都会导致客户端重试写请求，这样会导致同一个 chunk 在不同副本节点上可能会包含了不同的数据，有可能是同样数据全部或部分重复保存。GFS 只保证数据在一个原子操作中至少写入一次，并且只要写操作是成功的，对于同一个 chunk 的数据，所以复制节点都是写在同样的位置上。

3.3.4 快照

快照是针对文件或者目录树的，用于备份和数据回滚，实现上基于常见的写时拷贝 (copy-on-write) 技术。当 Master 节点接收到一个创建快照的请求时，会给相关的 chunk 分片一个新的租约，这样客户端进行写操作时就必须再与 Master 节点交互获取最新的 Primary 节点信息，这样 Master 有机会对已创建快照的 chunk 数据执行拷贝处理。

租约被废除或者过期后， Master 会记录这个快照操作日志到本地磁盘，然后再同步到内存的元数据状态中，复制记录一个快照涉及到的文件和 chunk 等元数据。快照创建后，当一个客户端尝试写到一个之前快照操作相关的 chunk 时，Master 会注意到这个 chunk 当前有大于 1 的引用，将会复制原来的数据创建一个新的 chunk ，之后的写操作就是基于新的 chunk 进行的了，和上面描述的流程类似，先选择一个 Primary 节点分配租约，然后进行相关的写流程。

3.4 Master 操作

Master 节点负责着 GFS 中的命名空间的相关操作，包含 chunk 副本节点的控制

决定 chunk 放置的服务器位置
创建 chunk 和复制数据
在整个系统层面协调处理，以保证每个 chunk 都能满足需求的复制程度，均衡整体负载
回收未使用的存储空间

3.4.1 命名空间管理及锁定

Master 支持并发的操作，对于存在竞态的数据主要是使用锁机制来保证操作恰当的执行顺序。GFS 的文件逻辑上是以一个全路径的查找表形式来实现命名空间的管理的，路径管理到文件具体的元数据信息。而命名空间树以前缀压缩的形式保存在内存中，并且该树上每个节点都存在一个读写锁。

举个例子，/d1/d2/d3/.../dn/leaf ，这样一个路径文件的操作，需要获取整个路径上所有节点的锁才可以进行，具体锁类型，前缀的节点需要获取到读锁： /d1, /d1/d2, /d1/d2/d3, /d1/d2/d3.../dn, 而文件上 /d1/d2/d3/.../dn/leaf 根据操作类型需要获取到读或者写锁。

GFS 中的文件组织不存在目录或者类似 inode 的机制，对于子文件的写操作，只需要获取到父目录的读锁就可以避免文件创建时父目录被删除。并且当前的锁机制可以支持同个目录下多个文件的并发更新操作。

GFS 的锁机制还有两点值得注意：

读写锁对象是延迟创建的，并且在不使用的时候就立即删掉；
Master 操作获取锁的时候为了避免死锁是按照一致的顺序进行：首先是按照命名空间树的层级顺序，然后同层级是按照字典顺序获取；

3.4.2 副本放置

在真实场景中 GFS 集群是高度分布的，具有很高的复杂性：

数百个 chunkserver (服务器) 节点；
数百个客户端请求访问 chunkserver ；
多个服务器机架，机架之间可能需要跨越一个或者多个交换机；
机架内部的带宽流量要大于机架之间的；

对于 chunk 副本的调度和放置，GFS 主要是基于以下两个原则进行的：

最大化数据的可靠性和可用性；
最大化利用带宽；

所以实现上，副本需要分布在多个机架上，这样读写的流量也可能是需要跨机架进行的，具体实现上存在很多的取舍权衡。

3.4.3 创建、重新复制、均衡负载

GSF 的 chunk 副本创建有三种情况:

创建 chunk；
重新复制：机器出现异常，副本数量不满足设置的值；
负载均衡：需要在服务器之间基于访问和服务器空间均衡 chunk 的副本分布；

创建chunk 的第一个副本，会考虑以下内容：

选择低于平均磁盘空间使用率的 chunkserver 放置新副本，这样随着系统的运行，不同的 chunkserver 服务器的磁盘使用率是趋于相等的；
尽量限制每个 chunkserver 上最近创建的 chunk 副本数量：因为创建之后很可能接下来就是大量的写请求，特别是追加写的情况，这样可以均衡写的流量；
基于 chunk 可用性的考虑，同一个 chunk 的副本也尽量要分布到不同的机架上；

异常发生时可能会让某个 chunk 的副本数量低于用于设置的值，这时候 GFS 集群需要尽快让副本恢复到原来的状态。多个 chunk 的重新复制是存在一个优先级的，基于以下因素考虑：

chunk 的副本数量距离设置值的差距，差距越大优先级越高；
在用的文件的 chunk 优先级高于最近被删除的文件的 chunk；
阻塞用户操作的 chunk 优先级会被提升到最高；

chunk 重新复制和上面副本创建的考虑一致，此外为了避免副本重新复制影响到正常的其他读写业务，整个集群中的重新复制的克隆操作数量是受限的，基于 chunkserver 和集群都存在着一个限制值。此外，chunkserver 也会通过限制复制从源 chunkserver 读取的请求数量来限制复制流量。

GFS 会定期检测和计算 chunkserver 的磁盘使用状态，来进行 chunk 数据的重新负载均衡，尽量维持每个 chunkserver 的磁盘使用率接近平均值。

3.4.4 垃圾回收

GFS 对文件删除的磁盘空间回收不是立即的，而是延迟执行的，从文件和文件的 chunk 都是一样的处理机制。

对于应用主动请求删除的文件，Master 会将该文件重命名为一个新的隐藏的名字，并且补充删除的时间戳。在后续定时检查进行垃圾回收时，对于删除时间大于 3 天 (内部可配置) 的文件及其 chunk 数据，才会进行真正的数据删除和磁盘空间释放，相关的元数据也会被清理掉。在文件被真正删除前，数据都是可读可恢复的。

垃圾回收还存在另外一种情况，每个 chunkserver 都会和 Master 节点维持定时的心跳，心跳中包含了该 chunkserver 维护的 chunk 信息。而 Master 节点会检测并回复在 Master 已经不存在的 chunk 信息，这时候 chunkserver 需要进行对这些在 Master 已经被删除元数据的 chunk 进行删除处理。这种一般是在 Master 执行删除处理时与 chunkserver 的通信失败导致的情况，这些 chunk 也被称为孤儿 chunk。

延迟删除的机制有几点优点：

实现简单，并且在一个大型的分布式系统中，因为组件和服务的异常总是会发生的，及时删除不一定是稳定可靠的，要实现稳定可靠，实现上也存在很多额外的处理和开销，延迟删除提供了一种一致的处理，并且一次失败还会在后续的定时执行的处理中再进行重试；
随机的删除在定时执行检测时可以合并为批量处理，减少了 Master 节点和 chunkserver 之间的通信开销，并且删除时也可以进行批量的 IO 处理；
Master 可以选择在系统空闲时进行真的的删除操作，这样一方面避免影响了正常的应用业务，另外一方面也重复利用了服务器的资源；
延迟删除也可以在无意或者恶意删除时恢复数据；

当然，延迟删除的机制也不一定是适应所有的场景的，并且也有其不足的地方。比如因为磁盘空间是延迟释放的，所以会存在一定的磁盘浪费问题，这样如果部署 GFS 集群的磁盘资源比较有限，也会存在一些问题。GFS 实现上支持对这种场景进行配置调优，可以对一些目录数下的文件 chunk 不进行复制，并且删除时是立即释放空间。

所有的机制都是取舍权衡，并不存在一个合适所有业务场景的方案，我们能做的只是根据具体的业务常见选择合适的方案，并且在实现上进行取舍。当然，我们也应该认识到方案存在的缺陷和不能解决的场景，在例外业务场景中更新方案或者调整规避。

3.4.5 无效副本检测

每个 chunk 都维护着一个版本号，每次 Master 给一个 chunk 的副本分配租约时，这个版本号都会增加。所以，对于出现异常不能接收数据更新版本号的 chunk 数据，Master 节点会将其视为已经过期无效，在读写中都会屏蔽掉这些 chunk 副本，并且在定期的垃圾回收中将其删除，释放空间。当然，定期检测 chunk 副本健康度的处理也会给这些 chunk 重新复制创建新的副本。

此外，Master 返回 chunk 信息给客户端时也会带上这个 chunk 版本号信息，这样客户端就可以在与 chunkserver 交互时提供最新的版本号信息，chunkserver 也可以根据这个版本号信息来决定是否可以执行相关的操作。这样，客户端总是能和有最新数据的 chunkserver 进行交互操作。

3.5 容错和诊断

论文从一开始就提及了，GFS 是设计运行在一个异常和错误普遍发生的硬件环境中，所以必须要考虑容错处理。此外，判断是否出现了异常，数据是否损坏也是很关键的内容。

3.5.1 高可用

GSF 的高可用是基于快速恢复和复制来实现的。快速恢复指的是无论 Master 还是 chunkserver 节点，在任何情况下出现异常终止，都会立即启动恢复状态，对于客户端和其他服务节点来说，必须要考虑连接失败和重试。

而复制则是指的 chunk 的副本数据分布在不同的 chunkserver 服务器上及不同的机架上，用户也可以基于实际应用的可用性需求来设置副本数量。Master 节点会在 chunk 副本数量不足或者存在副本的数据被检测到已经损坏的情况下对现有的 chunk 数据进行复制，创建新的副本。

至于 Master 节点，主要是基于可靠性的考虑针对其状态数据进行复制，变更操作日志和快照的创建都会复制到多个服务器上。并且对于状态数据的修改，只有在所有的 Master 副本上保存到磁盘上才被视为提交。这样在运行的 Master 节点失败挂掉时，另外一个 Master 的副本就可以立即基于复制的状态数据启动服务请求。

影子 Master 节点在 Primary Master 节点宕机时也可以作为只读的 Master 节点与客户端，因为通常与 Primary Master 的落后不是特别的大。影子 Master 节点会按照 Primary 节点的顺序应用操作日志修改状态，这样就可以和主 Master 节点保持一致的状态。

3.5.2 数据完整性

GFS 是通过 checksum 来判断存储的数据是否已经损坏的。每个 chunk 分为 64KB 大小的块，而每个块都有一个 32 位的 checksum，这个数据是和 chunk 的其他元数据一起保存在内存中的。chunkserver 在客户端读取请求数据时，在返回数据之前会进行 checksum 的检查，如果和内存的不一致，则说明数据已经损坏。这时候 chunkserver 一个是响应错误信息给客户端，让客户端再尝试从其他副本所在的 chunkserver 读取数据，另外还会汇报这个信息给 Master，Master 会创建新的副本，然后再删除这个数据损坏的副本。

checksum 对读操作有一定的影响，实现上客户端会对齐块大小来读取数据，方便校验 checksum。checksum 的计算对于追加写操作则有特别的优化，支持根据接收到的数据增量地进行 checksum 的计算和追加。对于指定位置的随机写则需要在写之前先校验文件覆盖区域的第一个和最后一个块的 checksum 值，这样如果写的范围是部分覆盖了这两个块数据，可以保证不会隐藏了已经损坏的内容。

chunkserver 也会在空闲的时候扫描和确认每个 chunk 的每个块的 checksum 值，这样也可以清理一些不太常用的 chunk 已经损坏的数据文件。

3.5.3 诊断工具

GSF 主要是基于日志进行诊断的，日志包含管家的事件，比如 chunkserver 的上下线信息，并且还包含了所有请求及响应信息，但是不会记录具体的文件数据。基于降低对主业务影响的考虑，日志的写是异步的，并且是顺序的磁盘写操作。

4 总结

整篇 GFS 的论文包含了大量的系统实现细节，讨论了一个业界真实应用的大型分布式系统中的方方面面，其中很多设计在现在很多新的开源分布式系统中都可以找到类似的实现。GFS 是基于实际的业务场景来设计，设计上即解决了实际的业务问题和硬件资源问题，同时也兼顾考虑实现上的简易性，最终还可以保持相当的健壮性和可靠性。

这是一篇值得不断重复阅读的论文。

5 后记

写这篇论文的阅读这节内容期间因为公司各种出差和事务繁忙，另外一方面也因为论文阅读这节内容一开始是逐句翻译，花费了大量的精力和时间。后面几节内容调整为记录重点内容和用自己的语言重新整理描述论文的实现和关键，整体的速度就快了很多，而且还可以加强理解和思考。后续的课程论文阅读也计划用这个方式进行。