且听风吟

分布式系统领域的经典论文，在 ChatGPT 和 Claude 的帮助下一遍读一边翻译，主要是前 5 章 这里看原文

Overview#

GFS 是一个用于大型分布式数据密集型应用的，可伸缩的分布式文件系统。

GFS 的应用场景和设计要点#

1. GFS 系统运行在许多廉价的普通硬件之上，故障非常常见，包括应用程序 bug 、操作系统 bug 、人为错误、磁盘 / 内存 / 驱动 / 网络 / 电源故障等。因此需要常态化的监控，错误检测，容错和自动恢复机制，将组件故障视作常态而非异常
2. GFS 系统存储的文件通常较大，达到 100MB 甚至 GB 级别都很常见。所以需要对大文件进行高效的管理，小文件可以支持但无需针对其进行优化
3. 文件修改更多是追加写而非覆盖，随机写非常少见。文件的读取一般是大规模的流式读取 (几百 KB 至数 MB) 或者小规模 (几 KB) 的随机读取
4. 负载主要主要来自于：大规模的流式读取 (几百 KB 至数 MB), 小规模 (几 KB) 的随机读取以及大量级的序列化的追加写
5. GFS 的文件经常用作生产 - 消费队列或者多路合并，所以系统必须高效的实现多个客户端对同一文件的并行追加语义
6. 高持续带宽比低延迟更重要

接口#

GFS 接口提供以下操作: create, delete, open, close, read, write, snapshot, record append 其中 snapshot 是一种低成本的文件创建或者目录复制操作，record append 是原子追加操作，允许多个 client 并行追加一个文件并保证每个 client 操作的原子性，用于多路合并。

架构#

一个 GFS 集群有一个 master 节点和多个 chunkserver 在集群中，所有文件被分割成固定大小的 chunk 每个 chunk 在创建时由 master 分配一个全局唯一的不可变的 64bit chunk handle. chunks 由 chunkserver 存储在本地磁盘上，通过 chunk handle 和 byte range 进行读写。为了保证可靠性，每个 chunk 会在多个 chunkserver 上创建副本，默认创建三个。

master 节点存储所有文件的 metadata 包括 namespace 权限控制信息，文件到 chunk 的映射，以及 chunk 的位置信息 master 节点同时控制系统级的活动如 chunk 租约管理，孤儿 chunk 的垃圾回收，以及 chunk 在 chunkserver 之间的迁移。master 节点定期的通过 HeartBeat 消息和 chunkserver 通信来下发指令和收集 chunkserver 的状态信息。

client 通过与 master 交互获取和修改 metadata 所有承载数据的通信都直接与 chunkserver 连接 client 和 chunkserver 都不缓存文件 (但是 client 会缓存 metadata) 有以下原因:

• client 做缓存的收益很小。因为大多数请求都会流式传输大文件或者有很大的 work set 无法缓存。没有缓存会使得客户端的实现更简单且整个系统可以不必考虑缓存失效 (一致性) 的问题
• chunserver 也没必要另作一层缓存因为 chunk 本身存储为普通文件 Linux 的 buffer cache 已经能够保持频繁访问的文件放在内存里面

交互流程#

1. client 根据固定的 chunksize client 将文件名和偏移量转换成 chunkindex
2. client 将文件名和 chunkindex 发送到 master
3. master 返回对应 chunk 的多个副本的 chunk handle 和位置信息
4. client 以文件名加上 chunkindex 作为 key 缓存服务端返回的信息
5. client 指定 chunk handle 和字节范围，向其中一个副本 (一般使用距离最近的那个) 所在 chunkserver 发送数据请求
6. 后续对同一 chunk 的读请求使用本地缓存，无需和 master 交互，直到缓存信息失效或者文件被重新打开
7. 通常 client 会在一个请求中包含多个 chunk 而 master 也会将多个之后可能需要的 chunk 一并返回以减少后续请求的消耗

chunk 大小#

GFS 选择的 chunksize 为 64MB 比通常操作系统的磁盘块要大，每个 chunk 副本在 chunkserver 上以 Linux 普通文件的形式存储，空间分配是惰性的，避免由于内部碎片造成的空间浪费。选择较大的 chunksize 有以下优点:

• 单个文件的 chunk 数量更少，减少 clieht 和 master 交互获取 chunkserver 位置信息的请求
• 一个 client 可以在同一个 chunk 上执行多个操作，只需保持一个持久的 TCP 连接即可，减少了许多连接创建连接的额外消耗
• 系统 chunk 总量更少，从而减少了 master 需要存储的 metadata 大小，使得 metadata 可以保持在内存中

通常，小文件只包含少量甚至仅有一个 chunk。如果许多 client 访问相同的文件，这些 chunkserver 可能会是热点，实际情况下热点不是主要问题，因为应用大多顺序读取多 chunk 文件。然后当 GFS 首次应用在批处理队列系统上时，确实出现了热点问题：一个可执行文件被写入到 GFS 作为一个单 chunk 文件后续上百台机器同时访问，存储这个文件的少量 chunkserver 由于数百个同时请求导致过载。我们通过两个方式修复这个问题: 1. 增大副本数量 2. 应用程序将 chunk 读取的时间错位避免同时请求。还有一种可能有效解决方案是：在这种场景下允许 client 读取其他 client 的数据

元信息#

master 存储三种 medatada: 文件和 chunk 的 namespace、文件到 chunks 的映射、每个 chunk 副本的位置信息。所有 metadata 都会一直存在 master 的内存中，而且 master 会将前两种信息的变更日志持久化到本地和远端的磁盘。通过日志回放可以简单的更新 master 的状态，保证可靠性和崩溃后状态恢复的一致性问题。

master 不持久化存储 chunk 副本的位置信息，而是在启动时向 chunkserver 询问或者是有 chunkserver 新加入集群时询问。

内存状态#

由于 metadata 存储在内存中所以 master 的操作一般都很快，且可以很高效的在后台对完整状态进行周期性的遍历。周期性的扫描用于：实现垃圾回收、为失效的 chunserver 上的 chunk 重新创建副本、执行 chunk 的迁移以保证 chunkserver 间的负载和磁盘空间的负载均衡。

全部存在内存中的问题是，整个系统 chunk 的容量受到 master 机器内存限制，在实践中一般不是什么问题，一个 64MB chunk 的 metadata 一般小于 64byte 而且大多数文件的 chunk 是满的，除了最后一个 chunk 这样就不会有很多稀碎的 chunk. 同时文件 namespace 的 metadata 一般也小于 64byte 文件名使用了前缀压缩存储的很紧凑。最后，如果真的需要支持更大的文件系统只需要简单的增加 master 机器的内存即可。

chunk 位置#

master 上没有存储哪个 chunkserver 有哪些 chunk 的副本的持久化记录，只是在启动时轮询所有的 chunkserver 且 master 能够保证这些信息是最新的因为 master 控制所有 chunk 的位置的安排，而且还会通过 HeartBeat 监控所有 chunkserver 的状态。

通过启动时查询能够消除很多由于 master 和 chunkserver 同步问题，比如 chunkserver 加入集群，离开集群，修改名称，重启，崩溃等等，在一个比较大的集群里，这些事情会经常发生。另一个方面来说，由于 chunkserver 上的很多错误可能导致 chunk 凭空消失 (比如磁盘故障导致不可用) 或者重命名操作，只有 chunkserver 自己才知道是不是真正存储了一个有效的 chunk 所以在 master 上存储这个信息也没有意义。

操作日志#

操作日志包含了关键的 metadata 的变更历史记录，也是 metadata 仅有的持久化信息，而且为所有的并行操作提供了逻辑上的时间线顺序。所有的 chunk 创建和版本号变更时，都会标记一个逻辑时间。由于操作日志的重要性，必须保证足够可靠的存储，而且在持久化完成之前对 client 不可见。操作日志会在远端机器上创建副本，并且只有在本地和远端磁盘上都刷新后才返回给客户端。

master 通过回放操作日志进行恢复，为了最小化 master 启动时间，日志需要尽可能小。在日志量达到一定大小时 master 会为当前完整状态创建一个 checkpoint 再次启动时只需要从最后一个 checkpoint 往后回放日志即可。checkpoint 本身是一颗紧凑 B-tree 结构可以直接映射到内存并进行命名空间的查询而无需额外的解析。

创建 checkpoint 本身需要一定的时间 master 内部的状态是结构化的，新的 checkpoint 的创建可以不阻塞当前的修改操作。创建 checkpoint 时会在另外一个线程上，切换到新的日志文件，新创建的 checkpoint 包含之前的所有变更。百万级别文件的系统 checkpoint 可以在一分钟内创建，创建完成后还需要写入到本地和远端的磁盘才算成功。master 恢复时只需要回放从最后一个完整有效的 checkpoint 之后的操作日志，更早的 checkpoint 可以直接删除，创建 checkpoint 期间的失败不影响正确性，因为恢复时会检查并且跳过不完整的 checkpoint.

一致性模型#

GFS 使用了相对宽松的一致性模型，但是仍然能够保证相对简单且高效的实现 GFS 的保证如下: namespace 的变更 (mutation)(如创建文件) 具有原子性、master 节点会在 namespace 上添加互斥锁来执行操作、master 节点上的操作日志能够定义变更的全局顺序。

文件区域 (file region 指文件在存储设备上的字节范围) 在数据变更后的状态取决于数据变更的类型：成功 / 失败，是否是并发变更。

文件区域 (file region) 指的是文件在存储设备上的字节范围，如果所有 client 无论从哪个副本，都始终能读取到相同的数据，则这个文件区域是一致的。如果一个文件数据变更后保持一致的同时，所有 client 都能看到变更写入的完整内容则这个区域是 defined (这个词不太好翻译，可以理解为这个文件区域的内容是 client 可以确定的)

• 写失败：结果当然是不一致了
• 非并发 (顺序) 写成功：结果肯定是 defined 对应文件区域的内容就是 client 写入的内容
• 并发写成功后：文件区域是一致的，但是对应文件区域写入的内容可能是多个写入片段混合在一起，所以是 undefined
• 顺序 / 并发追加成功：由于追加具有原子性，所以最终成功的那个区域的文件内容是确定即 defined 但是在此之前可能还有成功或失败的写入以及填充数据等

数据变更可能是写入或者追加：写入需要客户端指定偏移量，追加是在 client 认为是文件结尾的位置作为偏移量进行写入。追加操作会原子性的执行至少一次，即使存在并发变更，但是执行追加时，最终偏移量是由 GFS 选择的，最终写入成功使用的偏移量会返回给 client 并且标记为包含这条 append record 的 defined 的文件区域的起点 (前面可能也写成功或失败过)。

GFS 可能会插入填充或者重复添加记录，这块区域会被认为是不一致的。在一系列的变更之后，最终的文件可以保证在一定范围内是 defined 并且包含最后一次变更写入的数据。

GFS 通过按顺序将变更应用到 chunk 的所有副本来进行归档，然后使用 chunk 版本号检查所有过时的副本，这些副本可能是由于 chunkserver 下线导致变更丢失变更。过时的副本不会参与后续的所有变更，也不会在 client 请求 master 时被返回给 client 它们会尽可能早的被垃圾回收掉。由于 client 缓存了 chunk 的位置信息，所以在此缓存刷新前 client 可能会从一个过时的副本中读取数据，这个时间窗口受到缓存单元的超时时间和下一次文件的打开时间限制。由于大多数文件都是只追加的，所以过时的副本相对于最新的数据只是文件的结束位置较早，需要读最新数据的 client 会读取失败，重试时会向 master 重新请求 chunk 信息，此时就能够立即得到最新的 chunk 位置信息了。

在一个变更成功很久之后，组件故障也能导致数据损坏或丢失 GFS 会通过和所有 chunkserver 的握手请求，检查校验和发现数据损坏，然后将 chunkserver 标记为失效。一旦发现了错误，数据会可能快的从其他有效副本中重新复制存储，一个 chunk 只有在 GFS 反应过来之前所有副本都失效了才有可能不可逆的丢失，通常这个时间大概是数分钟。在这种情况下会返回给 client 数据不可用而不是损坏。

对于使用 GFS 的应用，为了适应这种宽松的一致性，应该尽量使用追加写而非随机写，根据写入的位置自己定义文件，周期性的设置已经写入完成的 checkpoint 并且包含应用层的校验和。然后只读取 checkpoint 之前的数据，并进行校验和检查。无论是一致性问题还是并发问题，这样都能很好的处理。在发生写入错误时，应用可以在自己记录的 checkpoint 后重新增量写入。应用可以根据 checksum 丢弃填充的内容和碎片记录。应用也可以给每条记录添加一个唯一 ID 标识重复记录。

系统交互#

租约和变更顺序#

变更是一个改变数据或者 metadata 的操作，每个变更都会应用到 chunk 的所有副本 GFS 使用租约机制维护所有副本间变更的一致性。在执行变更前 GFS 会在 chunk 的所有副本中选择一个授予租约，此副本称为 primary primary 负责决定在这个 chunk 执行变更操作的串行顺序，所有的其他副本在执行 chunk 变更操作时都遵循这个顺序。

由此，整个系统的全局变更顺序就能够由 master 授予租约的顺序，以及各个 primary 的执行变更顺序决定。租约机制是为了最小化在 master 节点上的管理开销，租约有一个初始为 60s 的超时时间，但只要有 chunk 变更完成 primary 就可以扩充超时时间 master 会将此超时时间扩充通过 HeartBeat 消息发送给所有的 chunkserver. master 在某些情况下可能会撤销租约比如 master 想要禁用在一个已经重命名的文件上的变更，在 master 和 primary 丢失通信的情况下，可以通过超时机制重新赋予新的租约。

client 执行一个变更的流程如下:

1. client 向 master 请求持有指定 chunk 租约的 chunkserver 及其他副本的位置信息。如果当前没有租约，则 master 选择一个副本授予租约
2. master 返回所有副本的位置信息，并标识哪个是 primary 然后 client 会缓存这些信息供后续使用 client 只有在无法和 primary 通信或者是 primary 不再持有租约时才再次请求 master 节点
3. client 以任意顺序将数据推送到所有的副本，每个 chunkserver 会将数据存储在内部的 LRU buffer cache 中，直到数据被使用或者过期。将数据流和控制流解耦后，可以基于网络拓扑调度数据流来提升性能
4. 当所有副本都确认收到数据后 client 向 primary 发送一个写请求，并标识早先已经推送给所有副本的数据 primary 为收到的所有变更赋值连续的序列号，然后按照序号执行所有的变更到自己本地的状态上
5. primary 将写请求转发到所有的 secondary 上，然后 secondary 按照 primary 赋值的序列号顺序执行所有的变更
6. 所有的 secondary 回复 primary 后表明他们都已经完成了操作
7. 如果在任意 secondary 失败 (即没有在全部 secondary 上成功) primary 会将对应的失败的错误返回给 client 已经修改的文件区域现在变成了不一致状态，然后 client 会重试失败的变更，即重复步骤 3 至步骤 7

如果一个写入非常大或者是跨 chunk 写入 GFS 的 client 代码会将其分割成多个写入操作，分别按照以上流程进行写入。但是如果多个 client 并发执行，交错执行可能导致覆写，共享的文件末尾就包含多个 client 写入的片段，这种情况下由于所有副本按照相同的顺序执行，文件区域是一致的，但是文件的状态是 undefined 不确定哪个在前哪个在后

数据流#

解耦控制流和数据流是为了使网络传输更加高效，控制流从 client 到 primary 然后再到其他 secondary 而数据流以流水线的方式沿着精心挑选的 chunkserver 链路线性推送，目的是为了最大化的利用每台机器的带宽以及最小化推送所有数据的延迟。每台机器的全部出口带宽都尽可能用于尽快传输数据，而不是为多个接收者进行数据的切分。

为了尽可能避免网络瓶颈和高延迟链路，每台机器转发数据会选择网络拓扑上距离最近还没有收到数据的机器 GFS 内部的网络拓扑非常简单，可以通过 IP 地址精确的估计距离。GFS 内部通过流水线传输数据以降低延迟，一旦 chunkserver 开始收到数据，就会立即开始转发。

原子性记录追加#

GFS 提供了一种具有原子性的追加操作称为 record append 与一般的写入不同的是 record append 不指定写入位置 GFS 保证会将此数据原子性的追加到文件末尾至少一次，然后将偏移量返回给 client 有点类似 Unix 下 O_APPEND 模式并发写入文件，不会有数据竞争。如果用普通写想到达到此效果需要分布式锁。

record append 是变更的操作一种，遵循相同的控制流，但是在 primary 上稍有不同 client 将追加数据推送到文件末尾的最后一个 chunk 的所有副本，然后将请求发送到 primary 然后 primary 检查在当前 chunk 上追加记录后是否会超过最大大小 (64MB)

• 如果超过了则 primary 会先将当前 chunk 填充到最大大小，告诉所有的 secondary 执行相同的操作，然后返回给 client 此操作应该在下一个 chunk 上重试 (record append 的大小被限制在 1/4 个 chunksize 以避免比较极端的碎片化的情况)。
• 如果没有超过 chunksize 则 primary 在本地的副本上追加记录然后将偏移量发送给所有的 secondary 进行数据写入，最终返回响应给 client.

如果 record append 在任一副本上追加失败 client 会重试此操作，最终同一 chunk 的不同副本可能包含不同数据，包含全部或部分重复的同一记录。

GFS 不保证所有副本字节级别的完全相同，只能保证数据会被至少原子性的写入一次，对于写入成功的操作，数据一定在 chunk 的所有副本上的写在相同偏移量上，所有副本的长度至少会跟追加数据的长度相同，后续的追加只会有更高的偏移量。按照之前一致性的定义 record append 操作成功后文件区域可以被认为是 defined 当然也是具有一致性的。

快照#

snapshot 操作可以几乎立刻的的创建文件或者目录树的拷贝，尽量减少正在进行的变更或者任何的中断。

GFS 使用 copy-on-write 技术来实现 snapshot 当 master 收到 snapshot 请求后，首先将相关文件的 chunks 的所有未完成的租约撤销掉，保证对这些 chunk 上的任何后续的写入都需要请 master 获取新的租约的持有者，这样 master 就有机会在这之前先创建 chunk 拷贝。

在租约被撤销 / 过期后 master 将 snapshot 操作日志写到到本地磁盘，修改内存状态，复制一份源文件 / 目录树的 metadata.

新创建的 snapshot 文件仍指向源文件的 chunk 在 snapshot 操作完成后，当有一个 client 向想要向 chunk 写入内容时会向 master 请求当前租约的持有者。此时 master 可以发现对应 chunk 的引用计数大于 1 然后 master 会延迟响应 client 首先选择一个新的 chunk handle 然后告知拥有 chunkC 副本的所有 chunkserver 创建一个新的 chunk 每个 chunkserver 在本地进行文件复制而无需经过网络 (GFS 系统内磁盘速度是网络的三倍，这里比的应该是读文件？) 接着 master 会在新的 chunk 上授予新的租约返回给 client 后续在复制出来的 chunk 上正常写入即可。

master 操作#

master 执行所有 namespace 相关的操作，管理系统内所有 chunk 的副本，决定在什么位置创建新的 chunk 及其副本，协调各种系统级别的活动，保证所有的 chunk 备份完整，平衡 chunkserver 的负载，回收未使用的存储等。

命名空间管理和锁#

master 上许多操作都很耗时，为了避免单个耗时的操作对其他操作的影响 GFS 允许同时执行多个操作，通过对 namespace 上的某个 region 加锁来确保正确的串行化。

和传统的文件系统不同 GFS 中目录本身没有一个单独数据结构 (相对于传统的文件系统，存储目录下的文件等), 也不支持文件 / 目录别名 (软 / 硬链接)。逻辑上相当于只有一张表包含了文件全名到 metadata 信息的映射表，利用前缀压缩这个表可以在内存中高效的表示。

namespace 中的每个节点 (文件名或者目录名的绝对路径) 有一个相关联的读写锁 master 在执行每个操作前需要获取这些锁的某个集合。比如某个操作和 /d1/d2/.../dn/leaf 关联则需要获取 /d1, /d1/d2, ..., /d1/d2/.../dn 的读锁和 /d1/d2/.../dn/leaf 的读锁或者写锁 (根据对应操作的需要), 这里路径上的叶子节点在不同的操作中可能是一个文件也可能是目录。

考虑一个场景：在 /home/user 被 snapshot 到 /save/user 过程中创建 /home/user/foo 首先 snapshot 操作会获取 /home 和 /save 的读锁以及 /home/user 和 /save/user 的写锁，而 /home/user/foo 的创建需要 /home 和 /home/user 的读锁以及 /home/user/foo 的写锁，这两个操作会在 /home/user 上产生锁冲突，文件创建操作无需在 /home/user 上加写锁，因为 GFS 的 "目录" 没有任何需要修改的信息，只需要在目录上加读锁就足以避免其被删除 / 重命名或者被 snapshot 的情况。

这种锁模式可以很好的支持在同目录下的并发变更操作，比如在同一目录下并发创建多个文件。由于 namespace 下可以用很多节点，读写锁对象都是惰性创建的并且一旦不再使用就立即删除。

为了避免死锁，所有的锁都按照一致的顺序申请：先按照在 namespace 中的层级排序，然后同级以字典序排序。

副本位置#

一个 GFS 集群中可能有数百上分布在不同机架上的 chunkserver 而这些 chunkserver 又被来自于相同或不同机架上的数百个 client 访问，不同机架上的机器进行通信可能要跨过一个或者多个交换机。而机架本身的输入输出带宽可能比机架上所有机器的带宽之和要小。

chunk 副本的选择选择策略服务于两个目标：最大化数据的可靠性和可用性，最大化网络带宽利用。

将副本分散到所有机器上仅能够避免磁盘或者机器故障并且最大化利用每台机器的网络带宽，同时也需要分散到不同的机架，以保证在整个机架不可用 (共享资源故障 / 交换机 / 电源故障等) 的情况下 chunk 仍有可用的副本 (保证可用性), 而且对一个 chunk 的读取能够利用到多个机架的总带宽，但是另一方面，写入数据必须在多个机架之间传输，这是需要取舍权衡的点。

副本的创建，重做 (复制) 和平衡#

chunk 副本会在三种情况下被创建: chunk 创建，重新复制 (re-replication), 重新平衡。

当 master 创建一个 chunk 时会选择副本的存放位置，主要考虑几个因素:

1. 存放在磁盘利用率低于平均值的 chunkserver 上这样长时间以后所有 chunkserver 的磁盘利用率会相对均衡
2. 限制每个 chunkserver 上最近创建副本的数量，因为一般文件创建后就会有较大流量的写入，需要避免在这种情况下的网络拥挤
3. 尽可能的将 chunk 分散到不同机架上的 chunkserver

当一个 chunk 的可用副本数量低于用户指定的目标时，比如 chunkserver 不可用或者是磁盘故障导致副本损坏等导致可用副本数量减少，或者用户增加了指定的副本数量 master 会尽快的进行重新复制。

每个需要重新复制的 chunk 会根据以下条件划分优先级:

1. 离复制目标还有多远，比如丢失了两个副本的 chunk 会比丢失了一个副本的 chunk 的优先级高
2. 优先复制当前存活的文件而非最近要被删除的文件
3. 为了最小化故障对运行中应用的影响，阻塞 client 请求的 chunk 的优先级会被提高

master 会选取优先级最高的 chunk 下发指令到选定的 chunkserver 直接从当前存在的有效的副本上复制数据，新的副本的位置选择和 chunk 创建时的选择规则一致。

为了避免副本复制时的流量淹没客户端流量 master 会限制集群内和每个 chunkserver 上执行复制的数量，此外每个 chunkserver 会通过限制向源 chunkserver 发送的请求来限制副本复制的带宽占用。

master 还会定期的进行副本的重新平衡 master 会检查当前副本的分布情况，通过将副本移动到更合适的磁盘空间上来进行负载均衡。新的副本的位置的选择策略同上，在新副本创建后由于副本数量多出来了 master 需要选择当前存在的副本进行删除，一般倾向于选择空闲空间低于平均值的 chunkserver 来平衡磁盘空间使用。

垃圾收集#

在一个文件被删除后 GFS 并不立即回收其占用的物理空间而是在常规的 GC 期间进行文件和 chunk 级别的回收，这种方式使整个系统更加简单和可靠。

当应用删除文件时 master 立即记录删除日志，然后将其重命名成一个包含有删除时间的隐藏文件。在 master 常规扫描文件系统时会移除已经存在了三天以上的隐藏文件，在移除之前，隐藏文件一样可以通过其特殊文件名进行访问，也可以通过将其重命名回普通文件名实现删除回滚。

当隐藏文件从 namespace 中移除后其内存中的 metadata 也会一并擦除，这样相当于切断了其跟 chunk 的联系。在常规的 chunk namespace 扫描期间 master 会标记孤儿 chunk (即哪些不会从任何文件上访问到的 chunk) 并且将这些 chunk 的 metadata 擦除。在 master 和 chunkserver 通信的 HeartBeat 消息中 chunkserver 会报告自己拥有的 chunk 的一个子集，然后 master 会在响应中标记那些在 master 中没有 metadata 的 chunk 然后 chunkserver 就可以随时将其副本删除了。

这种 GC 方式的优点:

1. 在大规模分布式系统中这种实现方式很简单且可靠，每个 chunk 的创建在某些 chunkserver 上可能会失败，副本删除的消息可能会丢失，但是 master 不必重试或记住这些失败的副本
2. 所有存储空间的回收都是在后台分期分批次进行的，而且是在 master 相对空闲的时期在平时 master 可以更加迅速的响应要紧的 client 的请求
3. 延迟回收空间的方式可以防止意外导致的不可逆删除

延迟删除的主要的缺点是会妨碍用户在存储紧缺时候的空间调整工作 (比如想删除一部分文件), 应用重复的创建和删除临时文件并不能直接重用存储。解决方式是，如果一个已经删除的文件被再次删除，系统内部会加快对应存储的回收进程，同时允许应用在不同的 namespace 上使用不同的副本和回收策略，比如用户可以指定在某个目录树下的所有 chunk 都不需要存储副本，并且任何文件删除都立即执行，在文件系统上做不可恢复的移除。

检查过时副本#

副本可能会由于 chunkserver 下线导致过时和丢失变更，对每个 chunk master 维护一个版本号来区别最新的副本和过时的副本，当 master 在 chunk 上授予租约时会增加其版本号，并告知所有其当前最新的副本，然后 master 和这些副本会将新的版本号持久化，以上步骤发生在 client 写 chunk 之前。

如果有副本当前不可用则其 chunkversion 就会落后，在 chunkserver 重启时 master 会检测到其拥有过时的副本然后通知 chunkserver 对应过时的 chunk 及最新的版本号。如果 master 检测到比当前记录高的 chunkversion 可以认为是在授予租约失败的过程中产生的 (租约失败也不可能有写入), 然后可以直接将这个较高的 chunkversion 修改为当前版本。

master 在常规的 GC 期间移除过时的副本，在返回给 client chunk 相关信息时会无视过时的副本。作为另一重保证: master 在告知 client 哪个 chunkserver 持有租约，或者指示一个 chunkserver 从另一个 chunkserver 上复制数据时，会包含 chunkversion 然后 client 和 chunkserver 在执行操作时会校验 chunkverison 以保证访问的是最新的数据。

容错和诊断#

GFS 系统设计的最大挑战之一是应对频繁的组件故障。组件的质量和数量导致故障是一种常态而非异常：即不能完全信任机器和磁盘。组件故障可能导致系统不可用甚至数据损坏。

高可用#

一个 GFS 集群中有数百个服务，其中一些可能在任意时间不可用 GFS 通过两个简单而有效的方式保证系统的高可用性：快速恢复和副本 (复制)。

快速恢复#

master 和 chunkserver 都被设计成无论如何终止都能够在几秒钟之内恢复状态并启动。事实上 GFS 也并不区分正常终止和异常终止，服务器例行关机时就直接把进程 kill 掉 client 或者其他服务在其未完成的请求超时时会短暂的停顿一下然后重新连接重启的服务进行重试。

chunk 复制#

chunk 复制以上说过很多了 master 会在 chunkservers 下线或者检测副本损坏时 (通过校验和) 通过 clone 操作复制。此外 GFS 还会使用奇偶校验或者擦除码以满足越来越多的只读存储需求。

master 复制#

为了保证可靠性 master 的状态也会被复制，操作日志和 checkpoint 会被复制到多台机器上，每个状态变更操作只有在日志已经被刷新到本地磁盘和所有的 master 副本上以后才能被认为是提交了的。

为了保证简单，只有一个 master 负责所有的变更操作和后台活动如 GC 等，当 master 进程故障时，可以几乎瞬间重启，如果 master 的机器或者磁盘产生故障 GFS 以外的监控基础设施会启动一个新的 master 进程使用操作日志副本继续进行处理。而 client 只会使用一个标准名称比如 gfs-test 来访问 master 而不是 IP 或者其他会根据机器修改而变更的名称。

此外 master 的副本即 shadow master 也可以提供对文件系统的只读访问，即使是 primary master 下线的时候，但是 master 副本相对于 primary 可能会稍微滞后几分之一秒。对于不经常修改的文件，或者在实时性要求相对较弱的情况下，这样方式可以提升读的可用性。事实上文件内容是从 chunkserver 上读取的应用根本感知不到文件内容是否是过时。只有目录内容或者是权限控制信息这种 metadata 会在一个很小的时间窗口内过期。

每个 shadow master 读取和执行操作日志副本上的递增操作，并且像 primary 一样按照顺序执行并修改自己的内存状态。和 primary master 类似 shadow master 在启动时轮询所有的 chunkserver 来定位所有 chunk 副本的信息，后续通过频繁的的握手消息交换来监控他们的状态。除此以外，只有创建和删除副本这种由 primary 做出的决定导致的副本位置更新上才会依赖 primary master.

数据完整性#

每个 chunkserver 使用校验和检查数据是否损坏。一个 GFS 集群可能有分布在数百台机器上的数千个磁盘，在读或写时数据损坏和丢失都很常见，此时可以使用其他的 chunk 副本上进行恢复。通过比较不同 chunkserver 上的副本来检查数据损坏不太实际。此外，在一些操作比如 atomic record append 中并不能保证所有副本完全一致，但是这些副本也是合法的。因此每个 chunkserver 必须通过维护校验和独立验证数据的完整性。

每个 chunk 会分割成 64KB 的 block 每个 block 有一个 32bit 的校验和，此校验和会被保存在内存和持久化到日志中与用户数据分离。对于读取请求，在返回数据给 client 或者 chunkserver 之前 chunkserver 会验证读取范围内的 block 的校验和，如果校验失败 chunkserver 不会将损坏的数据发送出去，而是返回一个错误给请求者然后向 master 报告错误。请求者则重新向其他副本请求数据，master 会执行副本重做 (此时有效副本数量不足), 然后通知校验出错的 chunkserver 删除它的副本。

计算校验和对读性能影响很小，因为大多数的读请求的跨度都只有很少的 block 因此只需要相关的很小的一部分额外数据用于校验，而且 GFS 的 client 代码会尽量按照 block 的大小进行对齐读取以减少这部分的开销。此外校验和的查找和校验本身没有任何的 I/O 开销，而且校验和的计算通常可以和 I/O 操作重叠 (读文件的时候就顺便计算了)。

对于 chunk 的追加写操作校验和计算是高度优化的，因为这项工作在负载中占据主导地位。我们只会增量更新最后一个不完整的 block 然后对之后追加写入的新的 block 计算新的校验和。即使最后一个不完整的 block 的数据已经损坏，虽然现在检查不到，但是新的校验会跟数据不匹配，在下次读取这一块数据的时候就能够检测到。

作为对比，如果一个写操作覆写 chunk 中已经存在的范围，我们必须先读取覆写范围内的第一个到最后一个 block 做校验，然后再执行写入操作，最后计算和记录新的校验和。

在空闲期间 chunkserver 会扫描和校验那些不活跃 chunk 的数据，一旦检查到损坏 master 会创建新的副本并将损坏的副本删除。这样可以避免在 master 不知情的情况下，不活跃的 chunk 悄悄损坏，导致没有足够的有效副本。

诊断工具#

详细且详尽的诊断日志在问题隔离，调试和性能分析上都提供了不可估量的帮助 GFS 服务会产生很多诊断日志，包含关键事件 (比如 chunkserver 上线或者下线) 和所有的 RPC 请求及响应。这些日志随时可以删除，但是我们总是尽量在存储空间允许的情况下保留足够的久。

RPC 日志中包含在通信线路上传输的的确切的请求和响应，通过匹配请求和响应日志以及在不同机器上的记录，可以重构出整个交互的历史来诊断一个问题。日志也可以用于负载测试追踪和性能分析。

日志对性能的影响很小，因为这些日志都是顺序且异步写的。大多数最近的事件也都会保存在内存中用于持续在线监控。

经验#

业务系统总是严谨可控的但用户不是，所以需要更多的基础设施来防止用户间的相互干预。

我们的很多问题都跟磁盘和 Linux 相关，许多磁盘对驱动声明自己支持一系列的 IDE 协议但是事实上只能可靠响应最近期的一个版本。由于协议在多个版本间非常相似，大部分情况下驱动会正常工作，但是偶尔产生的错误会导致驱动和内核的状态不一致，导致数据慢慢被损坏，这也是我们使用校验和的动机，我们也同时修改了内核以修改这些协议错误问题。

早期我们在使用 Linux2.2 内核时发现了一些问题 fsync 的耗时跟文件整体大小成比例而非写入的那一部分。对于大量级的操作日志，这是一个的问题，特别是在实现 checkpoint 之前。我们先是使用同步写处理这个问题，后续迁移到 Linux2.4 .

另一个 Linux 的问题是单一 (全局) 读写锁，地址空间内的任何线程在磁盘换入内存 (读锁) 或者修改 mmap 映射的内存地址 (写锁) 都需要获取这个锁。我们发现即使在系统负载很低的情况下会有短暂的超时，然后查找资源瓶颈和间歇性的硬件故障，最终我们发现，是这个单一 (全局) 锁阻塞了网络主线程将新数据映射到内存，因为磁盘线程正在将之前映射的内存换入。由于我们主要是受到网络接口带宽的限制而非内存复制带宽，我们通过将 mmap 替换为 pread 解决了这个问题。

结论#

GFS 很成功的支持了我们的存储需求，并且作为搜索和业务数据处理的存储平台在 Google 中被广泛应用。