原论文：The Google File System

1. Introduction

• 组件故障是常态而非例外
  • 因此，我们需要持续监控、错误检测、容错和自动恢复！
• 按照传统标准，文件数量巨大
• 大多数文件都是通过添加新数据而不是覆盖现有数据来改变的，因此文件内的随机写入几乎不存在
  • 因此，追加成为性能优化和原子性保证的重点！

2. Design Overview

2.1 Architecture

• 组成：单个master、多个chunkservers、多个clients
• master维护所有文件系统元数据
• 文件被分成固定大小的块
• clients和chunkservers都不缓存文件数据

2.2 Single Master

• 设计目标：尽量减少其参与读写的次数，以免master成为性能瓶颈
• clients会在一定时间内缓存最新访问的chunkservers的信息

2.3 Large chunk size as 64 MB

• 优点
  • 减少clients与master交互的需要，对同一数据块的读取和写入只需向master发出一次初始请求，以获取数据块位置信息
  • 在一个大块上，clients更有可能对一个给定的块执行许多操作，它可以通过长时间保持与chunkservers的持久 TCP 连接来减少网络开销
  • 减少存储在主服务器上的元数据的大小
• 缺点
  • 数百台机器同时访问的单块热文件时导致某个chunkserver超负荷运行
    • 解决方案：允许clients从其他clients读取数据

2.4 Metadata

• 元数据主要包括：文件与chunk的命名空间（记录日志）、文件与 chunk 之间的映射关系（记录日志）、每个 chunk replica 所在的位置
• 元数据存储在内存中，每个chunk有大概64字节的元数据
• 控制所有块的放置，通过定期的 HeartBeat 消息监控chunkservers的状态来记录chunk的位置
• 操作日志
  • 只有在本地和远程将相应的日志记录刷新到磁盘后，才能响应client操作。
  • 为了尽量减少启动时间，master会使用紧凑型 B 树，在日志增长超过一定大小时，对其状态进行检查点。
  • 在不延迟的情况下创建新的检查点时，主站会切换到新的日志文件，并在单独的线程中创建新的检查点。

2.5 Consistency Model

• 修改的类型
  • 一致的：如果所有client无论从哪个副本读取数据，都能始终看到相同的数据，那么文件区域就是一致的。
  • 确定的：所有client都能看到上一次修改的所有完整内容，且这部分文件是一致的，那么文件区域就是确定的。
• 数据修改后的文件区域状态
  • 当修改成功，且不受并发写入器的干扰时，则该文件区域是确定的
  • 如果有若干个写入操作并发地执行成功，那么这部分文件会是一致的但会是不确定的，在这种情况下，client所能看到的数据通常不能直接体现出其中的任何一次修改
  • 失败的写入操作会让文件进入不一致的状态
• GFS 通过主服务器与所有主服务器之间的定期握手来识别故障的主服务器，并通过校验和检测数据损坏情况。

3. System Interaction

3.1 Chunk Lease

在clients对某个 chunk 做出修改时，GFS 为了能够处理不同的并发修改，会把该 chunk 的 Lease 交给某个 replica，使其成为 primary,primary 会负责为这些修改安排一个执行顺序，然后其他 replica 便按照相同的顺序执行这些修改。Chunk Lease 在初始时会有 60 秒的超时时间。在未超时前，primary 可以向 Master 申请延长 Chunk Lease 的时间，必要时 Master 也可以直接撤回已分配的 Chunk Lease。

3.2 Read and Write Control and Data Flow

• 文件读取流程

  • 根据指定的filename和读取位置offset，client可以根据固定的 chunk size来计算出该位置在该文件的哪一个 chunk 中
  • client向master 发出请求，其中包含要读取的文件名以及 chunk index
  • master 向client响应该 chunk handle 以及其所有 replica 当前所在的位置。client会以filename和 Chunk index为键缓存该数据
  • client选取其中一个 replica 所在的 chunkserver 并向其发起请求，请求中会指定需要读取的 chunk 的 handle 以及要读取的范围
    

• 文件写入流程

  • client向 master 询问目前哪个 chunkserver 持有该 chunk 的 Lease
  • master 向client返回 primary 和其他 replica 的位置
  • client将数据推送到所有的 Replica 上。chunkserver 会把这些数据保存在缓冲区中，等待使用
  • 待所有 replica 都接收到数据后，client发送写请求给 primary。primary 为来自各个client的修改操作安排连续的执行序列号，并按顺序地应用于其本地存储的数据
  • primary 将写请求转发给其他 replica，replicas按照相同的顺序应用这些修改
  • replicas 响应 primary，表示已经完成操作
  • primary 响应client，并返回该过程中发生的错误（若有）

• 文件追加流程

  • client将数据推送到每个 replica，然后将请求发往 primary
  • primary 首先判断将数据追加到该块后是否会超过块的大小上限：如果是，primary 会为该块写入填充至其大小达到上限，并通知其他 replica 执行相同的操作，再响应client，通知其应在下一个块上重试该操作
  • 如果数据能够被放入到当前块中，那么 primary 会把数据追加到自己的 replica 中，返回追加成功返回的偏移值，然后通知其他 replica 将数据写入到该偏移位置中
  • 最后 primary 响应client
  • 如果追加操作在部分 replica 上执行失败时，primary 会响应client，通知它此次操作已失败，client便会重试该操作。重试操作可能会使得部分数据重复，但GFS的一致性模型不保证每个replica保持完全一致

• 快照：Copy on Write

  • 快照就是几乎可以瞬间复制一个文件或目录得到一个副本，同时最大限度地减少对正在进行的突变的干扰。
  • 在 master 接收到快照请求后，它首先会撤回这些 chunk 的 Lease，使得接下来其他client对这些 chunk 进行写入时都会需要请求 master 来获知 primary 的位置，master 便可利用这个机会创建新的 chunk
  • 当 chunk Lease 撤回或失效后，master 会先写入日志，然后对自己管理的命名空间进行复制操作，复制产生的新记录指向原本的 chunk
  • 当有client尝试对这些 chunk 进行写入时，master 会注意到这个 chunk 的引用计数大于 1。此时，master 会为即将产生的新 chunk 生成一个 handle，然后通知所有持有这些 chunk 的 chunkservers 在本地复制出一个新的 chunk，应用上新的 handle，然后再返回给client

4. Master Operation

4.1 Namespace Management and Locking

• GFS 在逻辑上将其命名空间表示为一个将完整路径名映射到元数据的查找表。通过前缀压缩的方法来减少内存开销。
• 每一个master operation在执行之前都会首先获得一个锁
• 通过分别在目录、文件上加相应操作的读写锁实现并发控制。
• 读写锁会在实际需要时才进行创建，一旦不再需要时就被销毁。所有的锁获取操作按照一个相同的顺序进行，以避免发生死锁：锁首先按 Namespace 树的层级排列，同一层级内则以路径名字典序排列。

4.2 Replica Placement

• 两个目标：最大化数据可靠性和可用性、最大化网络带宽利用率
• 将chunk replicas分布存储在多个racks中，保证单rack容错能力
• 创建chunk replicas的三个原因：创建 chunk、为 chunk 重备份、replicas均衡
• replica 放置策略
  • 把新的replicas放置在磁盘使用率低于平均水平的chunkservers中
  • 限制每个chunkserver中最新创建的replica的数量
  • 将chunk replicas分布存储在多个racks中
• 当为 chunk 重备份时
  • 时机：当可用的replicas数量低于用户预期时，有两种情况：某些replicas发生故障、用户预期提高
  • 制定优先级
    • 优先备份距离用户预期较大的replicas
    • 优先备份存活文件的replicas（而不是已被删除的）
    • 加速备份阻塞用户进程的chunk
  • 过程由master指定chunkserver来完成
  • 为防止clone流量超过client流量，master会限制集群和每个chunkserver的active clone操作次数，同时每个chunkserver会限制其用在clone操作上的带宽
• master阶段性做replicas均衡
  • 检查当前replica的分布状态，将一些replica转移到条件更好的磁盘中来实现负载均衡，同时均衡磁盘利用率

4.3 Garbage Collection

• 当一个文件被删除时，master立即完成日志记录
• lazily delete，删除文件实际上是将文件重命名为一个隐藏文件，该文件包含一个删除时间戳，并不是立即释放资源。
• master会定期扫描，删除“过期”的隐藏文件以及不可达的chunk，并删除相应的元素据和从命名空间中删除，同时chunkserver也会通过与master确认来删除master没有存储相应元数据的chunk。
• 删除文件在“过期”前可以被恢复和读取
• 定性为regular background activities，可以在master空闲时进行
• Stale Replica Detection via a 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通过校验和来判断存储的数据是否发生损坏，每个chunk会以64KB为单位进行分割，每单位数据都有一个32比特的校验和，校验和存储在内存中同时通过日志来实现持久性。
• 当client向primary请求一个chunk时，如果该chunk未通过校验，则chunkserver会返回一个错误并向master报告该错误，然后client会通过其他replicas获得该chunk，master也会指示chunkserver从其他replicas复制得到另一个replica，然后删除原来未通过校验的数据。
• 对于追加方式的数据写入：new_checksum = old_checksum OP appended_partial_checksum；对于覆盖写入，chunkserver 必须读取并校验包含写入范围起始点和结束点的校验和块，然后进行写入，最后再重新计算校验和，否则可能覆盖写入前chunk已损坏的信息。
• 在空闲时，chunkserver 会周期地扫描并校验不活跃的 chunk replica 的数据，以确保某些 chunk replica 即使在很少被读取的情况下，其数据的损坏依然能被检测到。

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