这节课讲支撑 Google 各种应用的文件系统——GFS。可以借此回顾一下在操作系统课程中学到的 Linux 文件系统，从而提炼出来一个文件系统应该具有的共同点。

GFS 是一个相当复杂的系统，可以提出各种各样的「what if」问题。如果发生了这种情况，系统会不会出错？我觉得相较于死抠系统的每个细节，不如当作一次思维训练（毕竟现在 Google 已经不用 GFS 了），理解系统设计的取舍。

我觉得也要培养批判性思维吧。我时常在读论文的时候，很难找到其中的 weakness points，尤其是顶会论文。在教师讲义的指导下，可以提出一些高价值的问题。

为什么读这篇文章

GFS 是一个存储系统，支撑了许多上层应用。如果我们可以让存储系统容错，那么上层应用就可以无状态。例如 k8s，如果一个 Pod 挂了，直接找另外一个 Node 启一个新的。

我发现，在数据中心里面，把容器当作一次性用品是一个常见手段。后端容器挂了？重启一个新的。ReplicaSet 副本数量不满足要求？随便新建就可以了。没有考虑与之关联的状态信息。

可是，现代服务总应该有状态吧？持久化在哪里了？数据库、文件系统里。所以有 StatefulSet 这种负载，还有 etcd 这种维护信息的组件。不过，我们今天关注的是一个可靠的文件系统。

换句话说，总要有组件考虑容错这一问题。计算机系统是层层封装的，上层应用不必考虑 dirty work，是因为有人默默付出，而不是理所应当。处理容错涉及到了很多工程实现的取舍，仔细看挺无趣的，可是，还是要稍微了解一下。

GFS 就是一个经典的文件系统实现，它触碰了这门课 6.824 的很多主题，包括并行性能、容错、副本、一致性等。是一个很好的系统论文，15 页，讲解了真实系统设计的细节。

之前我研究过所谓地理分布式数据中心的绿色调度问题，现在想想，很不成熟。毕竟，作为一名本科生，很多时候是在脑中假想了一个问题场景，并不是真实存在的情况。所以无法推进下去是很自然的。

为什么分布式存储系统很复杂

我觉得教授讲这个主题的逻辑展开很有调理。这是一个循环：

  1. 高性能 => 把数据分散到多台服务器上；
  2. 许多服务器 => 总有错误发生；
  3. 容错 => 多副本；
  4. 复制 => 潜在的不一致性问题；
  5. 强一致性 => 低性能。

也就是说，我们期待高性能（高性能ですから！），但是从逻辑推导的角度来看，必然会得到低性能。似乎是个无解的问题，每一步推导都很清晰。所以必然涉及工程的取舍，比如弱一致性。

GFS

背景

GFS 提出的背景是，Google 的许多服务需要一个大而快速的存储系统，比如 MapReduce、索引、日志分析等。这样，一个数据中心范围内的所有客户可以读取任何文件，应用之间可以共享数据。文件可以分布在不同服务器上，提供并行性能以及提升总的可用空间。

此外，系统应该自动从错误中恢复。而且，因为只给 Google 内部应用提供服务，系统处在可信的环境下，而不像 Internet 那样有很多鉴权的开销。以及，系统的目标是大文件的读取或者追加，而不是作为支持小文件的低延迟数据库。

Why Accepted

如果未来要走科研路，应该思考，这篇文章为什么被接收。

我感觉科研、面试以及类似的事情，不得不让自己作为一个舔狗，去舔面试官、审稿人。没办法。但我不太喜欢、也不太擅长这种事情。

这篇文章在 2003 年被接收的原因，并不是分布式、分散存储和容错这样的基本思想（换言之，在 2026 年更不可能凭这些理论中文章了），而是大规模、真实工业应用、弱一致性，以及单 master 的成功（虽然后面单 master 成为了瓶颈）。

系统结构

系统有这样几个组分：

  • 客户。如支撑 MapReduce 的库函数、RPC 等；
  • 块服务器。负责数据的存储；
  • 单 master，以及一些 master 副本。负责控制命令的产生。

看了一些系统论文，发现在分布式系统中，在控制层面，也就是在主-从层面下功夫了。比如，在调度领域，负责调度的 master，要么只有一个，要么有多个同级别的，要么是分层的。而和 master 交互的客户端，例如 kubelet，没什么可做文章的。

希望随着我阅历的增加，能够产生一些和现在不同的见解。

那么，既然是单个 master，一个自然而然的问题是单点故障。连计算机网络的课程设计都要求用两个核心交换机避免单点故障，Google 的工程师不知道吗？那，GFS 是如何避免单点故障的？

GFS 确实可以通过日志 + 检查点的方式快速从错误中恢复，而且单 master 通过一些工程手段，能够支撑一定量的集群规模。但是，后面发现这一工程奇迹说到底还是成为了瓶颈。

Master 需要记录的内容

既然是单 Master 架构，先看看为什么它能够支撑很大的集群规模。为了确保响应速度，必须把所有信息存在内存里，看看这是怎么做到的。

仔细讨论，发现 master 需要在内存中维护的状态有：

  • 文件名到小块把柄列表的映射（非易失）；
  • 每个小块把柄的版本号（非易失）；
  • 块服务器列表、主块服务器、租约时间（易失）。

非易失是通过增加日志做到的，

使用日志的原因很简单，因为需要持久化元信息。这是个基操，勿 6。操作系统课都涉及了这个内容。

实现崩溃一致性的两个视角，引自 jyywiki.cn

数据结构有两种视角，一方面，它是实际的结构，链表、二叉树等等。但是，如果以这种视角来审视数据结构，我们没有办法完成数据一致性。比如，在一个双向链表中插入一个结点，需要同时修改这个结点的父亲以及这个结点自己的指针域，这个操作不一定是原子的。

但从另外一个视角来看，其实不管是哪种数据结构，本质上都是一组操作，我只需要把这个操作顺序记录下来，理论上可以反映任何数据结构，从而实现崩溃一致性。

所以，GFS 使用日志来记录操作顺序，完全是基本操作，没有什么意外的地方，甚至，不这么做才意外。

为了加速启动速度，日志数量必须要少。所以，每当日志数量超过某一阈值时，创建一个检查点，包括了当前时刻所有需要持久化的状态。

读取操作

读取过程，引自论文

  1. 如果没有缓存文件位置，客户端把文件名和块下标发送给 master（因为每块大小是固定的，所以可以通过偏移量得到下标）；
  2. master 返回文件块把柄，以及块存放的位置（只返回最新版本的块）；
  3. 客户端缓存把柄和服务器列表；
  4. 客户端向最近的服务器发送块把柄和字节范围；
  5. 服务器读取磁盘上的块文件，并返回数据。

很多教材把 handle 翻译成句柄，实际上这是个错误的翻译。句柄是编译原理的内容，句子的把柄。这里其实应该叫块柄，干脆直接叫把柄吧。

一个讨论的地方是，master 怎么知道每个块存放在哪些服务器上？在 2.6.2 节有展开，在 master 启动后，会和集群中的块服务器沟通。毕竟，块服务器是权威信息源，没必要在 master 维护一份冗余的元信息。

追加操作

写过程，引自论文

写永远比读困难。GFS 面对的写操作绝大部分是追加，只有很少的随机写。因此，整个系统的优化重心放在了追加操作上。以追加为例，交互流程是：

  1. 客户端向 master 询问，文件最后一块的位置；
  2. 如果 master 发现，这一块没有主块服务器（primary），或者租约过期
    1. 如果没有一个块服务器有最新版本的块，出错；
    2. 否则，选一个具有最新块版本的服务器作为主服务器；
    3. 增加版本号，写日志；
    4. 告诉主服务器，从服务器有哪些以及版本号；
    5. 各个含有副本的服务器将新版本号落盘。
  3. master 返回给客户端主服务器和从服务器的信息；
  4. 客户端缓存这一信息，除非无法连接到主服务器，或者主服务器返回租约过期；
  5. 客户端把要写的数据发送给所有含有副本的服务器，并等待，这一传送实际上是通过流水线接力实现的，并不是客户端将数据逐个发送给目标，有点像 recursive DNS V.S. iterative DNS；
  6. 当所有相关服务器表示收到了数据后，客户端给主服务器发送命令，写入；
  7. 主服务器检查租约是否过期，以及块是否有空间（否则要 padding）；
  8. 主服务器对收到的所有写入，决定一个串行顺序，并开始写，选择一个偏移量，并写文件；
  9. 主服务器告诉从服务器偏移量，并要求追加；
  10. 主服务器等待所有从服务器响应，或者触发超时/错误；
  11. 主服务器返回 OK 或错误；
  12. 客户端在出错时重试。

注意到前两步对客户端是透明的，不管先前是否有主服务器，客户端总会得到主服务器和从服务器列表。

头脑风暴

如果是正常流程，那就是图片展示的流程。但如果在任何一个位置出错，我们都必须审视，系统是否能容忍这个错误。教授的讲义给了许多可以提出的问题：

  • 如果一个正在进行追加的客户端在某个尴尬的时刻挂了，会发生什么？（似乎不会造成很大问题）
  • 如果客户端缓存了一个过期/错误的主服务器？（教授的讲义声称主服务器会检查其是否持有租约，如果这样就安全了，隐含在文章的第 2 步）；
  • 如果一个读客户端缓存了过期的从服务器列表？（为什么过期？可能服务器错过了一些版本更新。客户端读取内容时，会检查版本，版本不一致会放弃读取。在和 master 获取最新列表前，可能版本检查会通过，但获取最新列表后，过期的服务器无法通过版本检查。换句话说，有个危险的时间窗口。具体在 2.7.1 小节）；
  • master 崩溃+重启后，会不会忘记文件？或者忘记每个块存在哪个服务器上？（前者，不会，有日志+检查点；后者，是的，需要重新和服务器交互）；
  • 两个客户端同时记录追加，会不会覆盖对方的记录？（不会，主服务器会选定一个写入顺序）；
  • 假如有一个从服务器永远无法听到主服务器的追加命令，读客户端会从那个从服务器中读取，会发生什么？（危险时间窗口，无解。否则，版本号可能不同；或者，master 定时任务排除过期小块；读客户端会从主服务器获得新的正确服务器列表）；
  • 如果主服务器在发送追加命令给所有从服务器之前崩溃了，没看到这个追加的从服务器是否会被选为主服务器？（4.5 节考虑了这个情形。可以，因为它的版本号和 master 记录的一样。当主服务器崩溃前，相关服务器都接收到了最新版本号。客户端会收到错误，重试，发现无法连接主服务器，于是和 master 交互。。。）；
  • 有个块服务器 S4 含有过期的块并下线了，此外，所有含有这个块的的主服务器和从服务器都挂了。S4 又上线了，master 会选择 S4 作为主服务器吗？（在 2.7.1 和 4.5 有解释，当 S4 重启并和 master 交互时，过期的块会检测到，不会作为有效位置，并被垃圾回收）；
  • 如果一个从服务器总是写入失败，主服务器会做什么？（它不做什么，总是返回错误给客户端。master 可能会发现客户端反复在某个块写入失败，会做出一些块复制等）；
  • 如果主服务器 S1 正在接收客户端请求，但是 master 和 S1 的连接断了？（master 会在 S1 的租约超时后分配一个新的主服务器。S1 发现自己的租约超时后会拒绝客户端的请求）；
  • 如果有个被分隔开的主服务器 S 在接收客户端请求，之后租约过期了，master 选了另一个主服务器 S’，后者会具有 S 的最新内容吗？
    （租约过期，意味着 S 和 master 的通信断了。如果 S 和 S’ 没断开，那之前的写入都是 OK 的。如果 S 和 S’ 断了，意味着写入 S 成功，但 S’ 失败，客户端接收到错误，会在 S’ 重新写入内容）；
  • 如果 master 挂了，其替代者是否了解挂了的 master 的全部信息？（不。持久化的部分知道，租约时间、主服务器这些就忘记了）；
  • 谁决定 master 挂了没有？能否让影子 master 自动上位？（外部服务，手工重启。不行，因为涉及到复杂的分布式共识协议，GFS 没有）；
  • 如果整栋楼断电，电力恢复后，所有服务器重启，会发生什么？（一切如常，主服务器和各个块服务器从磁盘中读取持久化的元信息，如映射关系、版本号、校验和等）；
  • 如果某个块是正在被写入的块，且 master 想要为其创建副本，因为它的数量可能比较少。如何保证新的副本不错过任何追加？（可能无法保证，因为复制是块服务器之间的交互。可以通过校验和在读取的时候判断读取失败，从而从数据正确的块获取内容）；
  • 什么情况下，GFS 无法提供保证？比如，追加成功，但后续读请求无法看到记录（所有 master 的持久化副本丢失了，或者所有块服务器磁盘损坏，CPU 等组件计算出错，时序错误。。。）；

应用程序视角的不一致性

对应用程序来说，GFS 并不是传统的强一致性文件系统，所以可能会看到一些意外的内容：

  • 所有客户端都能看到相同的内容？（3.3 节。因为只保证内容至少被写入一次，可能有多次，去重？）
    • 一个客户端能否看到另一个客户端看不到的内容？（看选了哪个块服务器了）；
    • 如果一个客户端读两次同一个块，能看到不同的内容？（不一致窗口 and 租约过期 => 选了不同块服务器）；
  • 所有客户端能否看到成功追加的记录是相同的顺序？（万一某次追加失败，可能有重复或不一致片段，但顺序是一样的。因为都按照主服务器选定的顺序写入）。

所以在不一致发生时，对应用程序员来说，会有一些意外的、难以解释的情况发生，并不是特别友好。

如果绝对一致性

既然 GFS 的一致性不够强，如果要求绝对一致性呢？很难，但是有一些问题要考虑：

  • 主服务器应该能检测到客户端的重复请求，或者客户端保证不发送重复请求；
  • 所有从服务器要么完成写入，要么一点也不写入（原子性），可能需要事先协商；
  • 如果主服务器失败了，有些后备服务器可能会状态滞后，新的主服务器必须和所有后备服务器交互并同步状态；
  • 为了避免客户端和过期的“前”从服务器交互，要么都和主服务器交互，要么从服务器也必须有租约。

在实验 2 和实验 3 会遇到。

其他事项

值得考虑的问题

  • GFS 能很好地支持小文件吗？
  • 如果有几十亿文件呢？
  • GFS 能否作为一个广域文件系统？
    • 副本在不同城市？
    • 毕竟一个数据中心并不能很好容灾。
  • GFS 从错误中恢复要多久？
  • GFS 如何应对慢服务器？

从文章作者的角度看，这些问题都非常尖锐。

实际上，和 GFS 工程师的采访，可以发现，文件数量、客户端数量都带来了很大的问题。此外，master 失败后，重启工作起初全靠手工。此外，GFS 并不能很好地支持延迟敏感应用。

所以后面出现了 BigTable 和 Colossus。

避免死锁

讲义没有阐述 4.1 节有关命名空间和死锁的处理。在 GFS 中，对文件元信息做修改涉及 master 的共享区域，避免数据竞争要加锁。

需要获得这个文件所有父文件夹的读锁，以及当前文件（夹）的读锁或写锁。

We now illustrate how this locking mechanism can prevent a file /home/user/foo from being created while /home/user is being snapshotted to /save/user. The snapshot operation acquires read locks on /home and /save, and write locks on /home/user and /save/user. The file creation acquires read locks on /home and /home/user, and a write lock on /home/user/foo.

snapshot 需要在 /home/user 获取写锁，为什么？它又不写这个文件夹，一个读锁不就够了吗？

假如它获得读锁，那么，文件创建可以获得读锁，并获取 /home/user/foo 的写锁，这样在快照的同时还能创建新文件。干扰了创建进程。

不过这个小地方不是重点。重点在于如何避免死锁。我们说，死锁有四个条件：

  1. 授权访问；
  2. 持有并等待；
  3. 不可剥夺；
  4. 循环等待。

这里，前面 3 点都是成立的，为什么能避免死锁？

Also, locks are acquired in a consistent total order to prevent deadlock: they are first ordered by level in the namespace tree and lexicographically within the same level.

论文说，手段是，锁的分配按照目录层级的顺序，从根到叶子逐层分配，层内按字母顺序。为何这样就可以？

举个例子。操作 A 在等待第 3 层的某个锁，持有第 5 层的某个锁；操作 B 在等待 A 持有的、第 5 层的某个锁，持有第 3 层 A 等待的锁。注意到，操作 B 的状态可能出现，而操作 A 不可能出现这种状态，因为持有第 5 层锁的前提是已经获得了第 3 层的锁。

这个例子只是一个简单的举例，也不是说必须按照层数从浅到深。锁编号这一方法被广泛采用，只要给个顺序就行，不管是什么顺序。

死锁的避免，引自 jyywiki.cn

其实操作系统课上讲过这种经典的死锁避免方式，如果没好好上课，或者老师不好好教课，会觉得，哇，好神奇。其实是少见多怪。

看了看，王道这种考研辅导书上也有类似的内容。不过，我确实是看不下去。怎么说呢，不能说王道没有覆盖我眼中的干货，或许密度比较低吧。毕竟考研让计算机成了一个文科，有很多死记硬背，但是现实中用处不大的知识。

文件系统的共同点

从用户的角度看，文件系统暴露给我层次化的目录结构，每个文件有文件名，有条理的组织在一起。从磁盘的角度看，文件系统只是按需使用了某些块。这么看来，文件系统夹在中间，要把文件名和其占用的块关联起来。

Unix/Linux 文件系统采用 inode 结构，维护属性、权限、数据区等内容。数据区可能指向其他 inode 块，还有多级索引，支持各种大小的文件。

磁盘上的普通数据文件

混合索引树

磁盘上的目录文件

特殊类型的文件

回顾一下操作系统吧！关于课内所学的知识，老师教学的时候就比较混乱，可能教学方式不适合初学者。现在对操作系统有了更深刻的认识后，这几个 PPT 还是能理解什么意思的。

在 GFS 中，文件名和块的命名空间，以及映射关系由 master 维护。因为整个文件系统为可信用户提供服务，所以没有过多鉴权机制。关键的映射关系，类似于 Linux 里，int d_addr[10] 字段的功能。

联系、对比一下。在 Linux 文件系统中，现在目录项中查找到文件名对应的 inode，随后从 d_addr 字段可以得到数据块信息。虽然是分层的，但展平就是个列表了。在 GFS 中，master 维护一个文件名到块列表的映射，实质上和展平后的 Linux 文件系统列表相同。

每个块服务器不知道 GFS 的文件名，它只知道存了哪些块。

总结

对 GFS 做一个全面的总结：

Good ideas:

  • 全局的集群文件系统可以作为统一的基础设施；
  • 把命名和存储的工作分开；
  • 分区，从而获得并行吞吐量；
  • 采用大块（64 MB）减少开销；
  • 主服务器负责串行化；
  • 租约，避免脑裂问题。

不够好的：

  • 单 master 性能，可能用尽内存和 CPU；
  • 块服务器处理小文件并不是很高效；
  • 缺乏 master 失效时的自动恢复机制；
  • 一致性可能太宽松了。

如果从奥卡姆剃刀原则「如无必要，勿增实体」的角度来看，GFS 好复杂。它是一个成功的设计，但我感觉不是很优雅。