Google File System (GFS)

2018 - Lecture 3

为什么要读这篇论文

  • GFS 是 MapReduce 所使用的文件系统

  • 论文与本课主题相关

    • 牺牲部分一致性（consistency），换取更简单的设计和更高效的性能

  • 它是一篇优质的系统设计论文，细节包含从应用层到网络性能、容错以及一致性

  • 它是一篇影响巨大的论文，许多其它系统依赖于或基于 GFS

    • Google 的 Bigtable，Spanner

    • Hadoop Distributed File System (HDFS)

什么是一致性

我们来思考一个问题：当一个写请求执行成功以后，下一个读请求会得到什么结果？

在单机环境下，只要应用本身的读写是原子性的，下一个读请求肯定能获取最后一次写成功的结果；在多机复制集合环境下，每一次写请求必须在多台机器上都执行，这时候下一个读请求能够获取的结果情况就比较复杂。在不同情况下，后者可能读取到过期的数据、得到读取错误信息、读取到最新的信息。写前后读取的信息一致性，就是本节标题中的一致性。

弱一致性

read() 可能得到过期的信息，而不是最新的信息

强一致性

read() 始终返回最新的信息

强/弱一致性之间的基本关系

对比项

强一致性

弱一致性

开发人员

逻辑简单

逻辑复杂

应用性能

差

好

规模化

不容易

容易

在一致性上的取舍产生了不同的一致性模型（consistency models）

理想的一致性模型

一言以蔽之：应用在多机复制集环境下与在单机环境下的行为一致。以文件系统为例，如果一个文件系统部署在多机复制集环境下，与本地单机部署效果一样，就很完美。

如下面这个场景：当两个应用并发地向同一个文件发送写请求

  • 多机复制集环境下：多个并发写请求的内容可能混合到一起，如 C1 写入 AAA，C2 写入 BBB，结果可能是 AAABBB 的全排列

  • 单机环境下：多个并发写请求的内容相互独立：如 C1 写入 AAA，C2 写入 BBB，结果可能是 AAABBB 或 BBBAAA。

达到理想的一致性模型的难点

  • 并发：不同操作并发进行，任何时间点执行到任意一步都有可能

  • 机器故障：任何操作都可能执行失败

  • 网络分区：有时候可能无法与其它机器通信

现实中大部分系统都不支持理想的一致性模型，GFS 就是其中之一

Google File System

High-level/Low-level design

GFS 由 1 个 master 和 多个 chunk servers 组成：

Master

master 存储所有文件系统的元数据：

  • 文件信息

    • 命名空间：文件夹、文件名

    • 每个文件与 chunks 的映射关系

    • 每个 chunk 当前的位置

  • 权限控制信息

    • chunk lease 信息

master 需承担一些日常维护工作：

  • lease 的管理

  • ophaned chunks 的垃圾回收

  • chunks 在不同的 chunk servers 之间转移，如在发现 chunk replicas 分布不够合理的时候 （rebalancing）

  • 一旦发现某个 chunk 的数量低于阈值，复制新的 chunk

  • 与 chunk servers 保持通信

此外为了使 master 的信息持久化，遇到系统崩溃后能正常恢复，所有的 operation log 都会被存储在 master 的磁盘中。

因为 GFS 只有一个 master，因此设计上它需要尽量避免自己成为系统的瓶颈（bottleneck），具体体现在：

  • 单个 chunk 的大小选择较大（64MB），从而减少每个文件所占用的 chunk 数量

  • client 对元数据的请求作了合并和缓存

  • client 只经过 master 取元数据，所有的原始数据的存取都不经过 master

  • 所有的元数据都存储在 master 的内存中

Chunk Server

Chunk Server 负责以 chunk 为单位，保存文件的原始数据。每个 chunk 是 chunk server 本地磁盘中的一个普通文件，每个 chunk 被一个全局唯一的 chunk handle 所标识。每个 chunk 的会被复制存放到多个不同的 chunk servers 上（通常为 3 个），以支持数据的高可用性（availability）。

Client

读取数据的过程，如图 1 所示：

  1. 根据固定的 chunk 大小，client 将文件名和位移转换成 chunk index

  2. 把文件名和 chunk index 发送给 master，获取 chunk handle 和 chunk server replicas 的地址，同时以 file name 和 chunk index 作为 key 缓存这些信息

  3. 从最近的 replica 处读取数据

写数据的过程，如图 2 所示：

由于写是数据修改（mutation）操作，每个修改操作都需要在多个 chunk replicas （注意，这里 chunk replica 指的是某个具体的 chunk 的复制单元，而不是 chunk server） 上执行，为了保证每个 chunk replica 存储的数据一致，master 会赋给一个 chunk replica 一个 chunk lease，得到 chunk lease 的 chunk replica 就是这个 chunk 的 primary。于是，由 primary 负责统一修改操作的执行顺序，所有 chunk replicas 都会按照相同的顺序来完成数据修改。基于 lease 管理，写操作的执行过程如下所示：

  1. 询问 master 哪个 chunk replica 拥有 chunk lease，以及所有 replicas 的地址

  2. 将要写入的数据上传到所有的 replicas。为了最大程度地利用网络带宽，数据会流式地被打入到最近的 chunk replica，记为 replica A；当 A 收到一部分数据后，就可以马上流式地传输给离他最近的 replica，如图所示为 primary；当 primary 收到一部分数据后，又可以马上流式地传输给 replica B，整个过程一气呵成

  3. primary 指定写数据的顺序，并在本地按该顺序执行，然后再把顺序信息传递给剩下的 replicas，后者再按该顺序执行

  4. 所有 replicas 执行完成后，primary 告诉 client 写操作执行完毕。

GFS 还支持 atomic record append：

许多大数据量的文件写入操作场景，都是在文件末尾追加记录，如：

  • 日志写入

  • MapReduce Job

因此 atomic record append 操作可以说是 GFS 非常定制化的设计。当多个 clients 并发地向单个文件作 atomic record append 时，由 primary chunk replica 来确定唯一的 record append 顺序。

GFS 的一致性模型

GFS 的一致性模型可以分别从文件和文件夹的角度来分析

文件的一致性模型

在介绍之前，需要先了解两个概念：

  • consistent: 不论从哪个 replica 上读取数据，所有 clients 看到的数据都是一样的

  • defined: 在数据修改操作执行之后，在保证 consistent 的前提上，修改的数据在媒介上是连续存在，而不是与其它修改操作混合在一起

Cases/Operations

Write

Record Append

Serial Success

defined

defined/interspersed with inconsistent

Concurrent Success

consistent/undefined

defined/interspersed with inconsistent

Failure

inconsistent

inconsistent

下面分别对不同操作进行分析：

Sequential Write

通过 chunk lease 来保证操作在不同 replicas 是 defined 的

Concurrent Write

虽然通过 chunk lease 能保证操作在不同 replicas 上按同一顺序执行，但不同的写操作可能同时修改同一个 chunk，导致修改的数据混合在一起，因此 consistent/undefined。

Serial/Concurrent Record Append

由于 record append 是一个 at-least-once 的操作，因此可能出现重复数据，导致 inconsistency；由于 record append 是原子操作，它永远是 defined 的。

Failure

失败的操作可能出现部分 replicas 更新成功，部分更新失败的情况，导致 inconsistency。

文件夹的一致性模型

由于 GFS 的文件夹操作都发生在 master 上，而 master 是单机环境，不难达到强一致性，事实也的确如此。GFS 通过前缀压缩（prefix compression），即树形结构，的方式来保存文件路径，并在树上的每个节点处加上读写锁（read-write lock），从而实现了强一致性。

GFS 的高可用性

Fast Recovery

master 和 chunkserver 在宕机后都能够快速恢复。master 除了记录 operation log，还会在日志数量达到一定程度时，将 operation log 整理成 checkpoint，每次恢复仅需从上一个 checkpoint 开始回放（replay）日志即可。

Chunk Replication

上文中已经详细描述

Master Replication

master 的状态，包含 operation log 以及 checkpoints，会被复制到多个不同的机器上，每个写操作只有在 operation log 复制完毕后，才会被 committed。一旦 master 宕机，监控系统会立即发现，并在存有 master 状态的机器上启动一个新的 master。除此之外，GFS 还提供 shadow master，在 master 宕机时提供只读服务。

参考

The Google File System paper, lecture node

PreviousLab: Primary/Backup Key/Value ServiceNextRaft

Last updated