The Google File System 论文概览

MIT6.824 第三节课阅读的论文，三驾马车之一，Google 内部的大型分布式文件系统

（PS：有讲的不对的，以论文为准

Google File System（GFS）的诞生基于 Google 内部快速增长的数据处理需求，是 Google 针对其业务场景专门设计的分布式文件系统。GFS 使用的技术和算法并不算新颖，都是学术界在其几十年前就已经提出的，但它是最早一批将这些技术在工业界大规模落地的。而且以现在的眼光来看，在当时（2003年）的背景下，学术界普遍认为存储系统应该具备强一致性模型，而 GFS 认为在现实中可以接受弱一致性模型的异端一般的想法无疑是具有突破性的

设计概览

Google 根据其内部的工作场景和负载，重新审视了系统设计上的传统选择，探索了一些不一样的观点

场景 or 假设

运行在廉价机器上，故障率高 —— 需要持续监控和容错
大量（数百万）的大文件（100MB 或更大，通常为数 GB）
读取负载通常是大文件的顺序读取，对于小型随机访问，通常是批量排序进行
写入类似，追加（append）比随机写更常见
存在大量并发，要保证小的同步开销和原子性语义

总结：场景是在单个 IDC 内，由普通机器组成的大型集群。负载倾向于大文件的顺序读写（高吞吐比低延迟更重要）

接口

GFS 提供了与 POSIX 不同的文件系统接口，不同的是文件在目录中按层次组织，通过路径名标识，包括 创建（create）、删除（delete）、打开（open）、关闭（close）、读取（read）、写入（write） 几个基本接口

除此之外，还有 快照（snapshot） 和 记录追加（record append） 操作，前者可以低成本创建一个文件副本；后者可以对文件进行原子追加数据，在合并结果和生产者消费者队列中很有用

架构

GFS 采用单 master 多 chunkservers，以及多 clients 的架构

文件划分成固定大小的块（chunks），每个块由一个全局唯一的 64bit chunk handle 标识，chunservers 将块存储在本地磁盘上，块通常会被复制多份（用户指定，默认三份）存储在不同 chunkserver 中

master 的工作：

维护了整个文件系统的元数据，包括命名空间（namespace），访问控制和块的映射信息
管理系统，控制块的租约（lease），孤立块的垃圾回收和 chunkserver 之间块的迁移
和 chunkservers 之间进行周期的心跳检测和信息收集

GFS 客户端被链接到应用程序内，客户端与 master 进行元数据操作，而数据传输和 chunkservers 进行，GFS 客户端提供的是有别于 POSIX 的文件系统接口，因此不会耦合于 Linux 的 vnode 层

客户端也不会进行缓存文件（但会缓存元数据），前面提到 GFS 的设计场景是大型文件，难以缓存。取消缓存避免了缓存一致性问题。服务器也不需要额外的缓存逻辑，因为 chunk 是作为本地文件存储，操作系统已经提供了这样的缓存机制

单 Master

单 master 简化了设计和实现的复杂度，单主相比多主和无主架构能只需要更少的全局知识（global knowledge）就进行 chunk 的管理，这意味着更少的通信，能带来更好的性能

相应的，单 master 也可能造成系统瓶颈，因此 GFS 不会通过 master 进行读写，而是通过 master 确定文件位于哪一个 chunkserver，然后访问它。同时客户端缓存了元数据，缓存命中时连 master 都不必访问，直接访问 chunkserver 即可。客户端交互流程见图 1

块（Chunk）大小

在系统设计中，这种常数通常被称为巫毒常量（voo-doo constant），其很难被确定。在 GFS 中块的大小被设计为 64 MB，比普通文件系统大得多，这是 Google 根据 GFS 的设计场景而定的

较大的块提供了几个优势：相比小块，它减少了客户端与 master 通信的次数，也更利于客户端缓存元数据（块越小，块个数就会越多，元数据也越大）；其次大的块也让客户端更可能在同一个 chunkserver 上执行操作，这样就可以通过持久（persistent） TCP 连接来减小网络开销

大块的缺点在于可能造成空间浪费，例如当存在远小于块大小的文件时，大部分空间都被浪费了。一个解决方法是惰性空间分配（lazy space allocation），数据首先缓存在 buffer 中，等被 append 到接近块大小再实际分配物理空间。

另外，对这种单块的文件的频繁访问可能造成块成为热点，可以通过更高的复制因子（更多副本）来均摊 chunkserver 的开销

不过总的来说，在 GFS 的场景（为大文件设计）中，这种情况并不多见，大块带来的优点远比缺点多

元数据

master 主要存储了三种元数据：

文件和块的命名空间
文件到块的映射
块副本的位置

元数据存储在 master 的内存中，前两者还会持久化到硬盘的操作日志（operation log）中

块副本的位置不持久化的原因是，chunkservers 对属于它自己的块拥有最终决定权，而 master 要保持这些数据的同步就需要在 chunkservers 状态变化时进行大量的通信，这是不必要的。所以 master 在启动时会向 chunkservers 获取它们的信息，之后的心跳消息会保持 master 上的元数据是最新的。当 master 宕机重启后，它会重新收集块位置

因为元数据主要存储在内存中，所以它的维护效率很高，便于后台定期扫描以进行块的垃圾回收，和复制与迁移。但潜在问题是块个数受限于内存大小，Google 认为这种代价是可接受的

GFS 的操作日志（operation log）存储了关键事件和元数据更改的历史记录，它是 GFS 的核心。其同时也作为并发操作顺序的逻辑时间线，文件和块还有它们的版本都由创建时的逻辑事件唯一标识

操作日志会被复制到多台机器上，只有在本地和远程机器上都持久化写入后才能响应客户端操作，以此保证数据不会丢失。master 会在刷新日志前批量将不同的日志放到一起以降低对吞吐量的影响

master 可以通过重放（replay）操作日志来在宕机时恢复文件系统状态，为此需要保持日志是小的，所以当日志到达一定大小，会进行快照，每个快照就是一个检查点（checkpoint），检查点是一个紧凑的类似 B 树的结构，它可以在内存中进行直接映射而不用额外解析，能加快恢复速度。快照期间日志会被写入另一个文件，对一个上百万文件的集群，检查点可以在约一分钟的时间作业被创建完毕然后被写入硬盘。这样在宕机恢复时，只需要用最近的检查点和它之后的操作日志恢复即可

一致性模型

GFS 采用了一个弱的一致性模型

只有文件命名空间变化（mutation）是原子的（例如文件创建和重命名），master 上的锁保证了原子性和正确性。操作日志定义了这些操作的全序

修改（mutation）后的文件区域（file region）状态取决于操作的类型，成功与否和存在并发操作（concurrent mutations），如下表所示

文件区域状态可能有两种：

（一致的）consistent：所有客户端看到的都是一样的数据
（确定的）defined：一致并且客户端可以看到完整的修改

可能存在「一致但未确定（consistent but undefined）」的状态，当并发修改均成功时就可能产生这种情况，有点类似于数据库中的脏写

数据的修改操作可能有写入（write）和记录追加（record append），在一系列成功的修改后，被修改的文件区域被保证是确定的（defined），GFS 通过以下方式实现这一目标：

在所有副本上以相同顺序来对一个块进行修改
使用块的版本号来检测块是否过时（可能因 chunkserver 宕机而错过一些修改），过时的副本将不会参与修改和参与对 master 报告块位置更新，它们会最早被垃圾回收

由于客户端会缓存块位置，因此可能在信息刷新前读取到旧的副本，这与缓存超时时间和文件的下一次打开有关。此外因为大部分文件都是仅追加（append）写入的，所以旧副本可能会返回一个过早结束的分块，而不是过时的数据，这种时候客户端就会立即重试并联系 master，获得当前块位置而不会产生一致性问题

GFS 会通过和 chunkservers 间进行定期心跳来检测故障，对于数据本身也会使用校验和来检测数据损坏，并进行恢复。只有当恢复完成前，一个块的所有副本都损坏时才是不可逆的

通过 GFS 使用的这些技术，它可以实现弱一致性模型，这些技术包括文件写入通常是追加而非覆盖，检查点，写时自验证（writing self-validating），自标识记录（self-identifying records）：

几乎所有的应用修改文件都只追加（appending）而不覆写（overwriting），一个典型用法就是，从头到尾生成一个新文件，然后通过原子重命名来替换掉旧文件，这样就只有追加而没有覆写数据
检查点可能还包括应用程序级的校验和，读取时只处理上个检查点之后区域的校验和，因为在它之前的状态肯定是确定的（defined）。检查点使得写入过程宕机，随后恢复时可以逐步重启（从上个检查点开始恢复），这时读也只读到上个检查点（因为从应用角度来说，上个检查点之后的数据还是没有被提交的）
在合并结果数据或生产者消费者队列场景下，会对一个文件进行并发追加（concurrently append），记录追加操作的「至少一次（least once）」语义保存了每个写操作的输出，每一个写入都包含了如校验和的额外的信息，读取时就可以通过这些检验和来判断数据是否完整，以及通过唯一标识区分重复记录（记录追加可能产生重复数据，后面会提到）

系统交互

前面提到，单 master 可能成为系统瓶颈，所以系统交互的一个设计原则就是尽量减少同 master 的交互

租约和修改顺序

修改操作会应用在块的所有副本上，GFS 使用租约（leases）机制维护多副本上的修改一致性

租约是为了减少 master 的管理开销，master 向块的一个副本授予租约，这个副本就成为 primary，primary 决定修改操作的顺序，其它副本（secondary）跟随 primary。租约时间默认为 60s，当块被修改时，primary 就会请求续约。当 master 想要禁止某些操作时，就会主动取消租约，即使它没到期

下图展示了一个写操作的控制流：

客户端询问 master 哪个 chunkservers 持有某个块的租约及其位置，如果没有租约，master 会选择一个副本授予租约
master 回复客户端，客户端会缓存这些数据，只有 primary 不可达或租约过期才会再请求 master
客户端将数据推到所有 secondary 副本，chunkserver 会将数据缓存到 LRU buffer 内，IDC 内的网络拓扑也会优化数据传输效率
一旦所有 secondary 副本都确认接收数据，客户端将向 primary 发送写请求，primary 确定操作顺序并按顺序在本地应用操作
然后 primary 将写请求发送到所有副本，每个副本按相同顺序应用修改操作
所有 secondary 副本通知 primary 确认操作完成
primary 回复客户端结果，包括 secondary 副本上可能的错误，这时客户端会尝试重试 3-7

如果一些操作的数据很大或者跨越了块，GFS 可能将它们分割成多个写操作来进行，单个写操作内可以保证顺序，但多个交叉的写操作顺序就无法保证。这可能就会导致前面提到的「一致但未确定（consistent but undefined）」的状态，例如一个副本上先写入了块 A 再写入块 B，而另一个副本上是相反的顺序，这样最后就不符合确定的（defined）状态的定义，因为对于一个写操作来说，块 A 或 B 的数据丢失了，不是一个完整的修改

数据流

GFS 中数据流和控制流被区分开来，控制流从客户端到 primary，再到所有 secondary 副本上。

而数据流沿着 chunkservers 的链进行线性传输，而不是如树之类的其它拓扑，这样的拓扑结构保证了每台机器的出口带宽都被用来传输数据而不是分配给多个接收者。并且为了避免延迟，每台机器都只推送数据给网络中最近的机器

在 TCP 连接上还会通过流水线（pipelining）的方式来优化延迟，一旦服务端接收到数据，就会立即转发给链上的下一个 chunkserver，在全双工交换网络下这并不会降低数据接收速率

原子记录追加

记录追加（record append）是原子的，这在分布式文件系统上很有用，因为可以避免需要如分布式锁之类复杂的同步机制

每次追加的大小被限定在不超过块大小的 1/4，因为当 primary 检测到一个块在追加后超过了最大大小（64MB），它就会填充这个块到最大大小，然后将追加操作应用到新块上。如果每次追加的大小都很大，那就会有很多块充满了碎片，大量空间被浪费

如果某个副本上的记录追加失败，客户端会重试，因此可能某些副本上这个记录被写入多次。也就是 GFS 不保证他们是一致的，只保证作为一个原子单元至少被写入一次（least once），出现这种情况时需要使用前面一致性模型中提到的方法处理

快照

快照（snapshot）可以在几乎一瞬间就给一个文件或目录树创建一个拷贝。GFS 使用写时拷贝（Copy-On-Write）实现这一点，当 master 收到一个快照请求时，会取消和快照相关文件块的所有租约，然后将操作日志写入硬盘，再复制源文件或目录树在内存上的元数据，新创建的快照文件与源文件指向相同块

在客户端向快照文件写入前，master 通过引用计数发现这是一个快照块，然后会拷贝源块再执行修改，这个拷贝会在和源块相同的 chunkserver 上执行以避免网络开销，这个过程对客户端来说是透明的

Master 操作

master 执行所有的命名空间（namespace）操作，管理块副本和位置，协调系统和进行 chunkservers 的负载均衡，以及进行垃圾回收工作

命名空间管理和锁

GFS 没有传统文件系统的目录结构，而是通过将全路径名进行前缀压缩映射来查找，在这棵命名空间树上，每个节点都有个读写锁

每个节点在操作前，需要获取到根节点的所有锁，例如修改 /a/b/c，要获取 /a 和 /a/b 的读锁、/a/b/c 的写锁。这样的好处是允许同一目录下的并发操作，同一目录下多个文件创建操作可以同时进行，目录上的读锁防止目录被删除或重命名或快照。为避免死锁，加锁顺序是自顶向下按字典序进行的

副本布局

块副本的布局策略有两大目标：最大化数据的可靠性和可用性，以及最大化带宽利用率

所以块副本不单单只是分布在不同机器，它还应该分布到不同的机架上以避免整个机架的损坏和掉线，并且也更有利于利用多个机架的整合带宽

创建、重新复制和再平衡

三个原因造成块的复制：块创建，重新复制和再平衡

创建块时需要考虑：

在空间使用率低于平均值的机器上放置新块，以平衡空间使用率
限制每台服务器上最近创建块数量，创建块通常意味着随后的大量写入
分布到不同机架（网络分区）上

当副本可用数量低于指定值时（可能是 chunkservers 宕机或硬盘损坏或指定值被修改引起的），master 会进行块的重新复制，此时需要考虑一些优先级：

副本缺少数量，缺失更多副本的块更重要
活跃文件的块比不活跃文件的块更重要
为了最小化对应用的影响，要尽快处理阻塞客户进程的块

最后，master 会周期性的进行再平衡，检查当前副本分布并将副本移到更合理的硬盘空间上以达到负载均衡，通过这个过程逐步填充新的 chunkserver 而不是突然大量写入，策略和创建块与重新复制时一样

垃圾回收

删除文件时，GFS 并不会立即删除文件和回收空间。master 只会将文件重命名为一个包含删除时间戳的隐藏名字，只有被隐藏超过三天（这个时间可配置）才会在定期的垃圾回收扫描中被真正删除（通过删除内存中的元数据）。在这个时间点之前还是可以正常读取，并重命名为正常名字来撤销删除

文件元数据被删除后，其原来的块就成了孤立块。垃圾回收期扫描时会标记孤立块并清除其元数据，在与 master 的定期心跳时，chunkservers 会报告其拥有的块集合，master 回复哪些块没有在元数据中，chunkservers 随后会删除这些块副本

这种惰性删除给 GFS 带来了几个优势：

对于大规模分布式系统来说，操作通常在一些机器上成功，一些机器上失败。垃圾回收提供了一种可靠的机制来清除没用的副本
在 master 后台定期执行，分摊了开销（特别是在一些大量删除文件的场景下）
防止意外删除带来的影响，删除可以被回滚

但其一个缺点是用户可能希望通过删除一些文件来缓解空间紧张，惰性删除使得空间无法被立刻复用。GFS 提供了一个解决方案，再次删除隐藏名字的文件，可以真正地立即删除

过期副本检测

如果一个 chunkserver 宕机期间丢失了一些块的操作，块副本就会过期。master 对每个块维护了一个版本号来区分其是否最新

master 每授予一个块新租约，就会增加它的版本号并通知最新的副本，master 和副本都会持久化版本号。如果有副本不可用，例如 chunkserver 宕机，在后续重启后通过心跳信息 master 会知道它是落后的。master 不会返回过期块的位置给客户端，直接认为它不存在，等垃圾回收将过期块删除

master 如果发现一个版本号高于自身的记录，可能说明在授予租约时 master 宕机了，所以它会选择这个更高的版本号来更新自己的版本号

最后，master 通知客户端块的租约 chunkserver 和位置时，以及通知 chunkservers 进行复制时也都会携带版本号，客户端和服务器在执行操作时总会检查版本号以确保数据最新

容错和诊断

对分布式系统来说最大的挑战就是如何容错

高可用

GFS 通过两个策略确保整个系统的高可用：快速恢复和复制

master 和 chunkservers 被设计为无论如何终止，都能在几秒内恢复自己的状态并重新启动。

默认每个块拥有三个副本，用户也可以自己指定这个值，通过块副本的冗余来实现容错，一些块副本不可用时，就会用前面提到的重新复制机制来恢复它的副本数量

同时，master 自身的状态也被复制，它的操作日志和检查点都被复制到多个机器上，这些信息只有在本地和远程都持久化后才算提交完成。当 primary master 宕机时，会在有其状态副本的机器上启动 shadow master，它只提供了对文件系统的只读操作，内部数据相比 primary master 可能有一定时间的延迟

数据完整性

在这个量级的系统上，硬盘故障也是常见的，这可能导致数据本身是一致的，但由于硬盘的原因数据被损坏。GFS 提供了一套机制让每个 chunkserver 能独立地检查数据完整性

一个块还会被分为 64KB 的 block，每个 block 有一个 32bit 的检验和，检验和保存在内存中，通过操作日志持久化，与用户数据分开。

读取数据时都会验证这些数据的 block 的校验和，如果数据损坏就不会被发送，并向 master 报告，master 会进行块的重新复制。读取时检验和不会造成什么性能影响，校验和的计算和文件 I/O 是同时进行的，客户端也通过将读操作对齐到检验和的 block 边界上减小了开销

对于追加操作，有一个重要的优化：仅增量更新最后一个不完整块的检验和，并用追加的新校验和来计算 block 的新的校验和。这样就算发生错误，也会在下次读取时被检测出。对于覆写操作，会对覆盖范围内的第一个和最后一个 block 进行验证，否者可能会隐藏掉没有被覆盖区域的错误

空闲时，chunkserver 会浏览和验证不活跃块的内容，以此发现很少被读取的块的数据损坏

诊断工具

日志是重要的，GFS 通过详细的日志来排除问题和进行性能分析

通过对日志异步、顺序地写入来避免性能影响，最近的内容也会保存在内存中用以在线监控

测量

主要是对 GFS 的性能测试的实验数据，略。看原论文就好了

经验

在 GFS 的构建和部署过程中，Google 也遇到了很多问题

例如硬盘和 Linux 驱动相关的问题，一些驱动和内核的错误导致数据损坏，迫使 Google 使用校验和检测数据完整性和修改 Linux 内核解决这些问题

早期 Linux 内核的 fsync() 效率与文件大小成正比而不是修改部分的大小，这对 GFS 中海量的日志很不友好，后来通过移植到更新内核解决

Linux 的一个读写锁设计使得系统在使用 mmap() 内存映射经常被阻塞在某些地方，后来通过 pread() 加上一些额外拷贝开销来绕过使用 mmap() 的这个问题

结论

GFS 展示了一个在一般硬件上支持大规模数据处理工作的核心性质，Google 根据它们的工作负载和场景重新审视了传统的技术选择，引出一个完全不同的设计思路：

组件故障作为常态现象处理
针对大文件、追加写、顺序读优化
放松标准文件系统的限制和扩展其接口
通过持续监控、复制和快速恢复来实现容错
解耦控制流和数据流提供高吞吐量，通过租约机制减少 master 交互

x³u³