GFS — The Google File System

分布式存储的难点

为什么要分布式存储？因为提升单台计算机的能力是有限的，要想存储大量的数据，不得不引入 多台 计算机，提高 性能

但是，计算机是不可靠的，集群中总会有一些计算机会出现一些问题，这要求我们的系统具有 错误忍受（Fault Tolerance） 的能力

实现容错，最常用的方式就是引入多个副本存储冗余数据，这样，即使某个副本出现问题，还可以切换到另一个副本。但是，副本之间的数据可能不完全同步，也就是 一致性保障

如果要保证副本间数据完全一致，这就是我们通常意义上的「强一致性」，那么需要引入很多额外的操作，系统的 性能又会降低

可以发现，整个形成了一个闭环，我们不得不 在性能与一致性之间做权衡，这也是分布式理论常常聊到的 C、A

GFS 的设计目标

GFS（Google File System），是 Google 内部使用的一种分布式文件系统

GFS 追求的是：

• 大文件的读写
• 高吞吐
• 顺序读写
• 具有容错能力：分片（shard）、故障恢复
• 较弱的一致性

架构

下面是 GFS 论文的架构图：

Master 节点

职责

Master 节点在 GFS 中起到一个协调作用，整个 GFS 集群中 只有一个 Master

GFS 把单个文件分成了若干个 块（chunk），ChunkServer 负责存储实际数据，而 Master 负责管理文件与 chunk 的信息

维护了什么数据

为了将客户端的读写请求正确路由到 ChunkServer，Master 需要维护：

• FileName 与 Chunk 数组的映射关系
• ChunkID 与 Chunk 数据的映射关系

这里的 Chunk 数据包括：

• ChunkServer 数组：一个 Chunk 会存储在多个 Server 上
• Version：该 Chunk 的版本号
• Primary Chunk Server：对 Chunk 的写操作需要在 Primary Chunk Server 上顺序处理
• 租期时间：Primary Chunk Server 在租期时间后，不再是 Primary Server

关于租期时间，后面 还会聊到

这些维护的数据（元数据）都存储在内存中

不过仅仅存储在内存中，是不够的，Master 应该将：

• FileName 与 Chunk 数组的映射关系
• Version

持久化到磁盘，以保证重启时可以恢复数据

为什么需要将这两个数据持久化？

假设不持久化 FileName 与 Chunk 数组的映射关系，那么 Master 重启时，需要向所有 ChunkServer 请求，并汇总，得到映射关系，这个过程非常耗时

而 Version 的作用主要是用于判断某个 ChunkServer 上的某个 Chunk 是不是 最新 的

为啥不直接使用最大的 Version？

假设 Master 重启后，向所有 ChunkServer 请求每个 Chunk 的 Version，这里存在问题：有可能 Version 最大的 ChunkServer 无法与 Master 通信（但是可以和客户端通信，即网络分区问题），那么 Master 拿到的 Version，就不是真实最大的 Version

因此，Version 需要持久化

怎么持久化？

Master 会以「操作日志」的方式，间接的将这些数据持久化到磁盘

当 Master 故障重启，并重建它的状态，你不会想要从 log 的最开始重建状态，因为 log 的最开始可能是几年之前，所以 Master 节点会在磁盘中创建一些 checkpoint 点，这可能要花费几秒甚至一分钟。这样 Master 节点重启时，会从最近的 checkpoint 恢复

GFS 读取数据的过程

Client 要想读取数据，需要给 Master 提供要读取的文件名、读取的起始偏移 Offset

Master 收到了 Client 的读取请求，会先从 FileName 到 Chunk 数组的映射 中获取 Chunk 数组

由于每个 Chunk 数组的大小为 64M，因此，可以很轻松的根据 Offset 获取待读取的 Chunk

知道应该读取哪个 Chunk 后，Master 会读取 ChunkID 到 ChunkServer 数组的映射，并将 ChunkServer 数组返回给 Client

Client 有了 ChunkServer 数组，会从里面选择一个网络位置距离自己最近的 ChunkServer 读取数据（根据 IP 地址判断，Google 机房的 IP 是连续的）

Client 会缓存 ChunkServer 数组，这样后续读取数据，就可以不用经过 Master，减小 Master 的请求压力

读取跨越多个 chunk 的情况

Client 可能会读取不止一个 Chunk 的数据，例如，一个 Client 读取了大于 64M 的数据，或者 Client 仅仅读取两个字节，但是这两个字节恰好处于两个不同的 Chunk 中

客户端本身依赖了一个 GFS 的库，这个库会注意到读请求跨越了 Chunk 的边界 ，并会将读请求拆分，之后再将它们合并起来。所以这个库会与 Master 节点交互，Master 节点会告诉这个库说 Chunk7 在这个服务器，Chunk8 在那个服务器。之后这个库会说，我需要 Chunk7 的最后两个字节，Chunk8 的头两个字节。GFS 库获取到这些数据之后，会将它们放在一个 buffer 中，再返回给调用库的应用程序。

Master 节点会告诉库有关 Chunk 的信息，而 GFS 库可以根据这个信息找到应用程序想要的数据。应用程序只需要确定文件名和数据在整个文件中的偏移量，GFS 库和 Master 节点共同协商将这些信息转换成 Chunk。

上面引用的内容来自 MIT-6.824 Lecture03-GFS 课程，Robert 教授的解释，翻译自 3.5 GFS 读文件（Read File）

GFS 写入数据的过程

我们这里仅讨论 Append 的情况

Master 收到了 Client 的写入请求，会先从 FileName 到 Chunk 数组的映射 中获取 Chunk 数组

由于 Chunk 的写入，必须在 Primary Server（主副本） 上进行，因此，Master 需要确定最后一个 Chunk 的 Primary Server 和 Secondary Server

在某一个时间点，Master 不一定指定了 Chunk 的主副本。所以，写文件的时候，需要考虑 Chunk 的主副本不存在的情况。

假设没有指定 Chunk 的主副本，Master 会在所有可用副本中，选择 Chunk Version 与 Master 上保存 Chunk Version 一致 的副本集合（即数据是最新的）

然后，这些副本集合中，会选择一个作为 Primary Server，其余的作为 Secondary Server

然后，Master 通知 Primary 和 Secondary 服务器，你们可以修改这个 Chunk，并给 Primary Server 设定租期（60s），当租期到了以后，Primary Server 就不再是 Primary 的了（租期的作用后面会聊）

现在，Master 需要更新本地存储的 Version，并持久化

有了 Primary Server 和 Secondary Server，Master 就可以将这些副本集合发给 Client

再来看看 Client 有了副本集合以后，数据的发送过程：

1. Client 给所有副本集合发送待追加的数据
2. 副本集合收到数据后，会将数据存到一个临时文件中，并给 Client 发送 ACK
3. Client 收到 ACK 以后，会告诉 Primary Server，说：“你可以将数据追加到 Chunk 中了”
4. Primary Server 收到请求后，会检查是否可以写入，如果可以，那么写入，并通知所有的 Secondary Server，可以写入
5. 每个 Secondary Server 收到请求后，会检查是否可以写入，如果可以，那么写入，并给 Primary Server 发 “yes”，否则写入失败，发送 “fail”
6. 只有到 Primary Server 收到了所有 Secondary Server 的 “yes”，才会给 Client 发送写入成功，否则告诉 Client，写入失败了

GFS 论文说，如果客户端从 Primary 得到写入失败，那么客户端应该重新发起整个追加过程。客户端首先会重新与 Master 交互，找到文件末尾的 Chunk；之后，客户端需要重新发起对于 Primary 和 Secondary 的数据追加操作。

一些问题

下面的问题来自 MIT-6.824 Lecture03-GFS 课程 学生提问

写文件失败之后 Primary 和 Secondary 服务器上的状态如何恢复

GFS 没有做什么额外措施（例如回滚成功写入的数据），因此，如果写入失败，那么副本间的数据可能会 不一致

写文件失败之后，读 Chunk 数据会有什么不同

取决于读的哪个副本

如果读的是写入成功的副本，那么就可以读到之前追加的数据；否则读不到

什么时候版本号会增加

版本号只在 Master 节点认为 Chunk 没有 Primary 时才会增加。

在一个正常的流程中，如果对于一个 Chunk 来说，已经存在了 Primary，那么 Master 节点会记住已经有一个 Primary 和一些 Secondary，Master 不会重新选择 Primary，也不会增加版本号。它只会告诉客户端说这是 Primary，并不会变更版本号。

可不可以通过版本号来判断副本是否有之前追加的数据

所有的 Secondary 都有相同的版本号。版本号只会在 Master 指定一个新 Primary 时才会改变。

所以，副本（参与写操作的 Primary 和 Secondary）都有相同的版本号，你没法通过版本号来判断它们是否一样

客户端将数据拷贝给多个副本会不会造成瓶颈

在 GFS 论文中（包括前文提到的 写入数据过程 ），都说到「Client 给所有副本集合发送待追加的数据」

那 Client 的性能与网络带宽不会成为瓶颈吗？

实际上，之后，论文又改变了说法，说 客户端只会将数据发送给离它最近的副本，之后那个副本会将数据转发到另一个副本，以此类推形成一条链，直到所有的副本都有了数据。这样一条数据传输链可以在数据中心内减少跨交换机传输（否则，所有的数据吞吐都在客户端所在的交换机上）。

如果 Master 节点发现 Primary 挂了会怎么办 => 租期的作用

Master 指定了一个 Primary 后，会定期的 Ping 它，如果超时没有收到应答，那么 Master 认为这个 Primary 挂了

如果此时立即指定一个新的 Primary，会出现 脑裂 的问题：Primary 可能并没有挂，只是网络分区问题

立即指定一个新的 Primary，那么该 Chunk 就会有两个 Primary，这是我们不想看到的

因此，GFS 在实现这一点时，并没有立即指定新的 Primary，而是等待当前 Primary 的 租期到期 以后，才指定新的 Primary，这样，就可以安全指定 Primary 而无需担心脑裂的问题

如果是对一个新的文件进行追加，那这个新的文件没有副本，会怎样

基本上与 写入数据过程 一致

Master 会从客户端收到一个请求说，我想向这个文件追加数据。

Master 节点会发现，该文件没有关联的 Chunk。Master 节点会创造一个新的 Chunk ID。

之后，Master 节点通过查看自己的 Chunk 表单发现，自己其实也没有 Chunk ID 对应的任何信息。

之后，Master 节点会创建一条新的 Chunk 记录说，我要创建一个新的版本号为 1，再随机选择一个 Primary 和一组 Secondary 并告诉它们，你们将对这个空的 Chunk 负责，请开始工作。论文里说，每个 Chunk 默认会有三个副本，所以，通常来说是一个 Primary 和两个 Secondary。

GFS 的一致性

前面提到，如果写入失败，副本间会出现数据不一致的问题

因此，GFS 的一致性保障是比较弱的，这样设计与 GFS 的追求相同：高吞吐，高性能，允许一定的数据不一致

如果要追求强一致性，会不可避免的提高整个系统的复杂度，性能也会降低

如果要将 GFS 设计成强一致的，可以考虑以下几点：

• Primary 有重复检测的能力：实现 Exactly Once
• Secondary 必须成功执行写入请求，而不是返回一个错误
• Secondary 有可能同步比较慢，客户端可能需要强制请求 Primary 以获取最新的数据

GFS 的局限性

GFS 最严重的问题在于：只有一个 Master 节点

• 只有一个 Master，应对大量的 Client 的请求，可能处理不过来
• Master 挂了，故障转移是手动的
• Client 很难发现自己读取的数据可能是「错误」的

参考资料

• MIT-6.824 Lecture03-GFS
• The Google File System