6.824 分布式系统 The Google File System

设计

假设

分布式文件系统

1. 廉价的组件失效是常态: 需要持续检测, 错误检测, 容错, 自动恢复
2. 一般存储大文件, 大文件应该被高效管理. 小文件被支持, 但不必高效
3. 工作负载
   • 读取: 大规模流读取, 小规模随机读取(批处理并排序, 从而稳定遍历文件)
   • 写入: 大规模数据追加, 小规模随机写入(支持, 不必高效)
4. 多个客户端程序并发写入文件: 原子操作需要有最小的同步开销
5. 高持续带宽更重要, 更重视以高速率处理大量数据而不是对单个的读写有严格的响应时间要求

接口

创建, 删除, 打开, 关闭, 读取, 写入

快照: 低开销创建一个文件或目录树的拷贝

记录追加: 允许多个客户端并发对同一个文件追加数据

架构

一个 Master, 多个 chunkserver, 多个 client

chunkserver

文件被分成若干固定大小的块, 由唯一的 64 为 chunk handle(块句柄) 标识

块句柄在 Master 创建块的时候被赋予, 每个 chunkserver 把块存储在本地, 通过块句柄和字节区间来访问

默认情况下出于可靠性考虑, 每个 chunk 被复制三份

Master

维护所有文件的元数据

1. 命名空间, 访问控制信息, 文件到块的映射, 块的当前位置
2. 块租约管理, 孤儿块的垃圾回收, chunkserver 间块迁移
3. 以心跳 (HeartBeat) 的方式周期性地与 chunkserver 通信

client

与 Master 通信进行元数据操作

与 chunkserver 进程所有承载真正数据的通信

chunkserver 和 client 都不缓存文件数据

1. client 处理的文件太大, 无法缓存, 只缓存元数据
2. chunkserver 本地存储块, cache 已经把经常访问的数据放在内存中

1. 应用程序把文件名和应用程序指定的字节偏移量转换为一个文件内的块索引, 向 Master 发送
2. Master 回复对应的快句柄和副本的位置, client 用文件名和块索引作为 Key 缓存这条信息
3. client 发送请求到其中一个副本(可能是最近的), 指定块句柄和字节区间读取数据
   
   对于同一个块的读取, 在缓存被替换之前, client 不需要和 Master 交互

块大小

较大的块大小: 64MB

1. 优点
   • 减少 client 和 Master 交互的需要
   • client 可能在大数据块上做很多操作, 可以使用更长时间持续的 TCP 连接减少网络开销
   • 减少了 Master 中元数据的大小
2. 缺点
   • 热点问题: 多个 client 访问一个小文件, 小文件在一个或几个块中
     
     可以使用更高的复制因子, 使批处理队列系统错开应用启动时间来解决这个问题

元数据

1. 命名空间和文件到块的映射 这两种信息的改变会被记录在 操作日志中, 持久化保存
   
   如果发生 Master 崩溃也不会出现不一致的风险
   
   在 Master 启动和 chunkserver 加入集群时更新 chunkserver 存储的块信息
2. Master 不保存哪个 chunkserver 中有哪些块的信息, 通过周期性的心跳来获知块位置并监控 server 状态
   
   试图维护这个信息没有意义: chunkserver 上的错误可能让块自动消失
3. 操作日志: 在多个远端服务器上进行复制, 对应的日志在本地和远端都被刷入磁盘之后才会响应 client
   
   刷入之前对若干条日志记录进行批处理, 从而减少刷入
   
   操作日志增长到一定大小的时候, Master 开一个线程用来把核对点写入硬盘

一致性模型

1. 如果所有的 client 不论从文件的哪个副本读取, 都能读到相同的数据, 那这个文件区域就是一致的
2. 如果一个区域在文件变更后是一致的, client 能看到变更写入的所有内容, 那这个区域是被定义的
3. 并发的成功变更产生未定义却一致的区域: client 看到相同的数据, 但是它可能看不到变更写入的所有内容

为了保证在一系列成功变更之后, 文件区域是被定义的且一致的

1. 在所有副本上以相同的顺序对块进行变更
2. 使用块版本号来检测 任何 因为在 chunkserver 宕机时错过变更的过期副本
   
   过期的副本不会参与变更, 也不会作为 Master 给 client 的返回结果, 会被当作垃圾而回收

client 缓存的块信息可能会让它从一个过期的块读取, 这时一定会读取超时

此时重新打开文件, 清除缓存中关于这个块的信息

GFS 通过 Master 和 chunkserver 定期的握手来识别失效的 chunkserver 并通过校验和来检测数据损坏

一旦出现问题, 会从有效的副本尽快恢复, 如果不存在有效的副本, 这个块会被丢弃

对应用程序的影响

弱一致性需要应用程序来处理不一致的情况

1. 生成核对点, 应用程序只处理核对点之前的情况
2. 使用校验和来识别数据的有效性
3. 使用唯一标识符过滤重复数据

系统交互

租约和变更顺序

Master 把一个块租约赋予其中一个副本, 称之为 primary

primary 为块上的所有变更选择一个顺序, 所有副本都使用这个顺序

1. client 询问 Master 哪个 chunkserver 持有块的当前租约以及当前位置
   
   如果没有租约, Master 会选一个副本赋予租约
2. Master 回复 client 租约的标识以及其他副本的位置, client 缓存这些位置
   
   当 primary 不可到达或者 primary 表示自己不再持有租约是, client 重新联系 Master
3. client 把数据推送给所有的副本, 每个 chunkserver 会把数据存储在 LRU Buffer 缓存,
   直到数据被使用或者超时
4. 一旦所有的副本都确认收到了数据, client 会向 primary 发送一个写请求, 标识之前所有推送的数据
   
   primary 为其收到的所有变更分配连续的序列号, 按照序列号顺序将其应用到本地状态
5. primary 转发写请求到所有的 从副本 每个副本以 primary 确定的顺序进行变更
6. 所有的副本向 primary 回复表明完成操作
7. primary 对 client 进行回复, 任何错误都会被返回到 client
   
   发生错误时, client 会重试几次
   
   写操作部分失败时, 可能有的副本已经写入数据, 这部分没必要恢复, 这就是 GFS 的工作方式(弱一致性)

数据流

数据在 chunkserver 中被推送, 呈链式

对 TCP 连接上的数据传输进行管道化来最小化时延

原子性记录追加

基本流程同 “租约与变更顺序” 这一节
新增: primary 检查追加的数据是否会超出当前块, 如果会的话就填满当前块

告诉 client 应该在下一个块追加 (追加的数据大小被限制为最大四分之一块, 这样不会产生太多内部碎片)

快照

使用写时复制的方法实现快照

1. Master 收到快照请求, 撤销目标文件上的租约
2. 租约被撤销或者过期之后, 把操作写入日志
3. 复制文件的目录树, 新创建的快照文件和源文件指向相同的块
4. client 要向块 C 写入时, 会向 Master 发送请求从而寻找租约持有者
5. Master 注意到当前对 C 的引用超过一个, 推迟对 client 的回复
6. 选择一个新的块句柄 C', 要求每个拥有块 C 副本的 chunkserver 创建一个名为 C' 的块

这样可以保证本地复制, 不需要通过网络

Master 操作

命名空间管理和锁

GFS 不支持对文件和目录的别名

每个 Master 操作要获取一组锁, 每个目录的读锁, 该文件的写锁

这样相同目录下可以执行并发更改

副本放置

最大化数据可靠性, 可用性, 带宽利用率

所谓鸡蛋不要放在一个篮子里, 副本分开放置可以有更高的可靠性

同时不同位置可以使用多个位置的总带宽

创建, 再复制, 再平衡

1. 创建: 新的副本放在磁盘利用率低的主机上
2. 再复制: 副本的数量低于用户指定的数量
3. 再平衡: 每隔一段时间, Master 迁移副本从而平衡磁盘空间和负载

垃圾回收

惰性回收

机制

删除块的时候删除元数据, 在每次的心跳中 Master 和 chunkserver 通信

此时 chunkserver 可以自由处理被删除块的空间

过期副本检测

Master 赋予块新的租约时, 块版本号会增加, 新的副本会被通知

chunkserver 向 Master 报告的时候, 如果发现有版本号更小的块, 就被标记为过期

Master 在垃圾回收中移除过期的副本

容错和诊断

高可用性

快速恢复和复制

1. 快速恢复: 不区分异常终止和正常终止, 都会在几秒钟内恢复
2. 复制
   • 副本复制: 用户为不同部分指定复制级别. Master 根据需要进行调度
   • Master 复制: 有一个监视器监视 Master 的情况, 有一个备份 Master, 还有一个影子提供滞后的几分之一秒状态的 Master

数据完整性

每个 chunkserver 对于自己的每个块有校验和

如果发现数据错误, chunkserver 会向 Master 报告并请求一份正确的数据

并且还会向 client 报告让他去找其他副本

chunkserver 在空闲时会对不活跃的块进行数据完整性检查