The Google File System [SOSP‘03] 论文阅读笔记

原论文：[This file system was introduced by Alphabet Inc., developed by Google, and has become a cornerstone of distributed systems.](https://storage.googleapis.com(pub-tools-public-publication-data/pdf/035fc972c796d33122033a0614bc94cff1527999.pdf)

1. Introduction

• 故障通常被视为常见情况而非罕见事件。

• 基于上述分析结果表明：为了确保系统的稳定运行，在设计阶段就需要实施以下措施：

  • 持续进行实时监控以捕捉潜在问题；
  • 建立完善的错误检测机制；
  • 引入有效的容错策略；
  • 并制定自动化恢复流程。

• 基于传统标准而言，文件数量非常庞大。

  • 大部分文件并未采用覆盖现有数据的方式进行修改；相反地，在这种情况下几乎不会出现随机写入的问题。
    • 因此这意味着追加操作成为了性能优化和原子性保障的关键举措。

2. Design Overview

2.1 Architecture

• 组成：由单一的master节点、多个chunkservers节点以及多个client节点构成
• 单个master节点负责管理整个文件系统的元数据信息
• 文件被划分为固定大小的数据块
• 这些客户端和分片服务器均未缓存实际文件数据

2.2 Single Master

• 设计目标：主要目标是尽量减少其参与读写的次数，以避免 master 成为性能瓶颈 * clients 会存储最新访问的 chunkservers 的数据，在一定时间内保持缓存。

2.3 Large chunk size as 64 MB

• 优势

• 降低了客户端与主服务器之间的交互需求，并简化了对同一数据块读写操作的过程

• 在较大规模的数据块中进行大量操作时（即在一个大块中），通过持续保持与 chunkservers 的连接可显著减少网络开销

• 降低了主服务器上元数据文件体积

• 问题

• 多台机器并发访问

• 特定的热文件可能导致某个chunkserver超负荷

• 解决方法：使得各客户端之间能够互相共享数据

2.4 Metadata

• 元数据包含以下内容：文件与 chunk 的命名空间（用于记录日志）、文件与 chunk 之间的映射关系（用于记录日志）以及各个 chunk 复制品的位置信息。
• 元数据占用内存空间较大，在内存中每个 chunk 块大约含有约 64 字节的数据元信息。
• 系统通过定期发送 HeartBeat 消息来监控 chunkservers 状态，并实时更新各 chunk 的位置信息。
• 操作日志部分详细说明了相关的操作机制：
  • 只有当本地及远程端相应地将操作日志更新至磁盘后方能响应客户端操作。
  • 系统 master 采用紧凑型 B 树结构来管理 log 数据增长过程中的状态检查点。
  • 在不影响性能的前提下为系统自动创建新的状态检查点时，则会将主节点切换至新的 log 文件，并启动独立线程完成新检查点的建立工作。

2.5 Consistency Model

• 修改类型

• 保持一致性：不管从哪个副本读取数据，默认都会始终保持相同的数据显示。

• 保证一致性：所有客户端都能查看上一次完整的修改记录，并且这部分内容是保持一致的状态，则整个文件区域就被认为是确定好的状态。

• 数据更新后的情况

• 若单个操作成功且无并发写入器干扰，则该文件区域的状态为确定

• 当多个操作同时完成时会达成一致但存在分歧，在这种情况下客户无法直接识别任何一次修改的影响

• 提交失败的操作会导致系统出现不一致的状态

GFS 通过与所有主服务器之间的定期通信来判断哪些主服务器出现故障，并利用哈希值来检测数据完整性问题。

3. System Interaction

3.1 Chunk Lease

当客户对某个 chunk 进行修改操作时，在此过程中 GFS 系统会将该 chunk 的 lease权转给一个replica副本使其成为Primary副本 Primary副本则负责按照预定顺序处理这些请求 其他副本同样遵循这一操作流程 每个chunk最初都设置了一个60秒的有效期 在其有效期内 Primary副本可向Master提交延长lease的时间请求 并由Master决定是否批准 若有必要 Master也可直接撤销已分配的lease权

3.2 Read and Write Control and Data Flow

文件读取流程

• 通过给定filename和read position offset，并基于fixed chunk size来确定该位置属于该文件中的哪个chunk。
• client发起请求至master，并携带所需的文件名及chunk index。
• master响应处理该chunk handle及其所有replica当前所处的位置，并将与filename及Chunk index相关的数据缓存在客户端端。
• client从selected replica所属的chunkserver发起请求至master，并指示所需获取的具体handle及range.

文件写入流程

为了获取当前拥有该 chunk 的 chunkserver 的 Lease信息, client会请求 master。
master会将 primary节点及其复制节点的位置信息反馈给 client。
在此之前,为了确保后续读取操作能够快速响应, client会将数据分批推送到每个 Replica节点上。
同时, chunkserver会将接收到的数据暂存在本地缓存中,直到后续读取请求到来。
一旦所有复制节点都已成功接收数据后,主节点primary会对write request进行处理。
主节点primary会在处理完write request后将其转发给所有复制节点。
复制节点回应并确认已经完成操作。
最后,主节点primary随后会回复 client,并报告操作过程中出现的任何错误信息。

文件追加流程

• client向每个replica发送数据副本，并向primary节点提交请求。
• primary首先评估将此数据追加至当前块后是否会超出容量限制：若超出，则primary会为该块填充至达到容量上限，并通知其他replica执行相同的操作。
• 如果这些数据可被成功加入当前块中，则primary会将其添加到本地replica中，并返回追加成功的偏移值；同时通知其他replica将此数据写入指定偏移位置。
• 最终(primary)响应client。
• 如果追加操作仅部分replica成功完成时，则primary会告知client此次操作失败。重试操作可能导致部分节点上的重复数据出现。GFS的一致性模型并不保证所有replica保持完全一致。

快照：Copy on Write

• 快照基本上可以瞬间复制一个文件或目录得到一个拷贝，并尽量减少对正在进行修改的干扰。
• 当 master 接收快照请求时, 它会首先释放这些 chunk 的Lease, 这使得其他客户端在后续对该 chunk 进行写入操作时必须通过 master 来获取 primary 的位置信息。
• 一旦chunk的Lease被释放或失效后, master首先记录日志信息,随后会对自身管理的空间进行复制操作。
• 当有客户端试图修改这些chunk时,master意识到该chunk已经被引用超过一次.此时,master会生成一个新的handle并通知所有持有该chunk的相关chunkservers在其本地环境中复制出一个新的chunk并应用新的handle值.最后(master)将把这个结果返回给客户端。

4. Master Operation

4.1 Namespace Management and Locking

• GFS 在逻辑上将命名空间表示为一个查找表，在此查找表中将完整路径名对应到元数据。
• 每个master operation在执行前都会先获得一个锁。
• 通过分别对目录和文件施加相应的读写锁定来实现并发控制。
• 读写锁会在实际需要时才会创建，并在不再需要时被销毁。所有的锁获取操作会按照统一的顺序执行：首先按照Namespace树的层级排列，在同一层级中则按路径名称字典序排列。

4.2 Replica Placement

• 目标在于提升数据稳定性和可获得性的同时实现网络带宽的最大化

• 确保将chunk replicas分散部署以增强系统的容错能力

• 主因包括创建新的data chunk为现有chunk进行冗余备份以及实现replica数量均衡配置

• replica存放策略主要包括以下几点：

  • 将新的replicas存放于磁盘使用率低于系统平均水平的主要存储节点中以提高资源利用率
  • 对每个存储节点设定限制其最多接收的新replica数量从而避免资源过载
  • 将replicas分散部署于多个racks以降低单点故障风险并提升系统的整体容错能力

• 在对 chunk 进行重备份的情况下

• 时机：当可用的replicas数量低于用户预期时，在某些情况下（某些replicas发生故障或用户预期有所提高）

• 确定优先级

  • 选择距离用户预期较远的replicas进行备份
  • 避免对已删除的replicas进行操作
  • 提高对阻塞用户进程的chunk进行处理的速度

• master负责将过程分配给指定的chunkserver

• 为了避免cluster中的clone流量超出客户端流量, master将设置对集群以及每个chunkserver的active clone操作次数进行限制,同时设置每个chunkserver用于clone操作时的带宽使用上限

• 该master在阶段性的负责复制均衡任务。

• 检查当前replica的分布状态后，在条件更好的磁盘中转移一些replica以实现负载均衡，并平衡各磁盘的利用率。

4.3 Garbage Collection

• 当一个文件被删除时, master会启动并执行日志记录流程.
• 在lazily delete过程中, 删除操作实际上是将文件重命名为一个隐藏文件,该隐藏文件包含delete timestamp,并不立即释放资源.
• master定期扫描系统,去除已过期的隐藏文件以及无法到达的chunk,并移除相关元素数据; 同时, chunkserver也会通过与master确认的方式,去除那些不在master存储元数据中的chunk.
• 在隐藏文件过期前可恢复及读取.
• 该操作被归类为常规后台活动,可以在master空闲时段执行.
• 通过使用chunk version number进行复制检测以检测过时副本.

5. Fault tolerance

5.1 High Availability，高可用性

• fast recovery：无论是什么原因导致终止，master和chunkserver都可以记录终止时状态并在若干秒内恢复
• chunk repilcation：默认三副本策略，每个块在不同rack的chunkserver上部署副本
• master replication：master的操作日志和checkpoints备份在多个机器上，一个修改时成功的当且仅当在所有包含master的备份信息都已记录该修改操作。同一时间只会有一个 master 起作用。当 master 失效时，外部的监控系统会detect到这一事件，并在其他包含备份信息的地方重新启动新的 master 进程。此外还提供只读功能的Shadow Master：它们会同步 master 的状态变更，但有可能会有所延迟，其主要用于为 master 分担读操作的压力。

5.2 Data Integrity，数据完整性

每个 chunkserver 会计算数据块的校验和以判断其完整性，在每次存储操作后将这些计算结果保存在内存中，并同时借助日志机制实现持久化存储功能。
每当客户端 primary 尝试获取一个特定的 chunk 时：

• 如果该特定的 chunk 无法通过校验验证，则 server 返回相应的错误信息并通知 master；
• 然后客户端会从其他 replicas 中获取该 chunk；
• 同时 master 也会指示 server 从其他 replicas 中复制相关数据至当前 replica，并删除之前未成功验证的数据。
  对于追加方式的数据 write 操作而言：
• 新增量块的新奇偶校验码等于旧奇偶码与新增数据块奇偶码按位异或的结果；
• 对于覆盖 write 操作，
  必须执行读取、验证包含 write 操作起止点的相关奇偶块以及随后进行重写的步骤，
  这样才可以防止覆盖操作导致原有未被充分验证数据丢失。
  在系统空闲时段，
  每当 chunkserver 处于空闲状态时
  都会定期扫描所有不活跃的 chunk replica 数据块，
  并将扫描结果传递给 master 系统以便及时发现即使很少被访问也无法逃脱损坏风险的情况。

一些参考：Google File System 论文详析