# Google File System (GFS)

## 为什么要读这篇论文

* 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

![图 1 - GFS 架构](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LPfFFKIl0Cw-Vqmv9ce%2F-LPfFghRhvtMCuGvAaWk%2FScreen%20Shot%202018-10-25%20at%208.45.54%20PM.jpg?alt=media\&token=3f7c004b-ea9c-4de9-a03c-b922e869ddf1)

\
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 所示：

![图 2 - 写控制与数据流](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LPfFFKIl0Cw-Vqmv9ce%2F-LPf_lCF9nB7inrZc8v3%2FScreen%20Shot%202018-10-25%20at%2010.18.01%20PM.jpg?alt=media\&token=97d256a0-b5f4-4cb8-bcf5-861a711ebc75)

由于写是数据修改（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](http://nil.csail.mit.edu/6.824/2018/papers/gfs.pdf), [lecture node](http://nil.csail.mit.edu/6.824/2018/notes/l-gfs-short.txt)