《Google File System》（2003，SOSP）
摘要
- GFS是一个可扩展的分布式文件系统，提供容错功能，并为大量客户机提供高聚合性能
- 广泛部署在谷歌中作为存储平台，用于服务数据的生成和处理，以及基于大型数据集的研究和开发任务
介绍
组件故障是常见的，而不是例外，因此持续的监控、错误检测、容错和自动恢复必须是分布式系统的组成部分
文件很大，因此必须考虑I/O操作和block size
大多数文件需要附加新数据，而不是直接覆盖原有数据——引入了一个原子的追加操作，多个客户机可以并发地在同一个文件内追加内容，而不必进行额外的同步
co-designing the applications and the file system API benefits the overall system by increasing our flexibility
设计概述
假设
必须持续检测、容错和迅速从组件故障中恢复
系统存储的大文件数量适中，系统同样支持小文件的处理
工作时的负载主要包括两种读取：大的流读取和小的随机读取。前者的单个操作通常读取数百个KB，后者通常读取一些任意偏移量的KBs
工作时的负载还包括许多向文件追加数据的连续写操作。同时支持在文件中的任意位置进行小的写操作，但不一定高效
系统必须高效地、行为明确地实现多客户端并行追加数据到同一个文件里
高性能的稳定网络带宽远比低延迟重要
接口
- GFS提供一套类似传统文件系统的API接口函数（支持常用的操作如创建和删除、打开和关闭文件、读写文件），文件以分层目录的形式组织，用路径名来标识
- GFS提供快照和记录追加操作。快照能创建一个文件或目录树的副本。记录追加操作允许多个客户端同时对一个文件进行数据追加操作，每个客户端的追加操作都是原子性的——利于多路结果合并，和”生产者-消费者”实现
架构
GFS集群包含一个单独的Master节点（系统中只存在一个逻辑上的Master组件，一个逻辑的Master节点包括两台Master服务器）、多台Chunk服务器，同时被多个客户端访问
可以把Chunk服务器和客户端放在同一台机器上，前提是机器资源允许，并且能够接受不可靠的应用代码降低系统的稳定性
Master节点：
管理所有的文件系统元数据（名字空间、访问控制、文件和Chunk的映射信息、当前Chunk的位置）。
管理系统范围内的活动，如Chunk租用管理 、回收孤儿Chunk（orphaned chunk）、Chunk服务器之间迁移Chunk
周期地和各个Chunk服务器通通讯，发送指令并接收Chunk服务器的状态信息
GFS客户端：
- 客户端代码以库的形式链接到客户程序
- 实现了GFS文件系统的API接口、应用程序与Master节点和Chunk服务器通讯、对数据读写操作
- 客户端和Master节点的通信只获取元数据，数据操作由客户端直接和Chunk服务器进行交互
Chunk服务器不缓存文件数据，直接以本地文件的方式保存
单一Master节点
- 单一的Master节点通过全局信息精确定位Chunk的位置
- 必须减少对Master节点的读写，避免其成为系统的性能瓶颈
- 客户端向Master节点询问应该联系的Chunk服务器，并将Master节点返回的元数据缓存，后续直接和Chunk服务器进行数据读写
- 简单读取的流程：
- 客户端把文件名和程序指定的字节偏移量，根据Chunk大小（固定值）转换成文件的Chunk索引
- 客户端把文件名和Chunk索引发给Master
- Master将相应Chunk标识和副本的位置发回客户端
- 客户端用文件名和Chunk索引作为key缓存这些信息，之后客户端给最近的目标Chunk副本发送申请（包含了Chunk标识和字节范围）
- 后续读取Chunk时客户端不再和Master通讯，除非缓存的元数据过期或者文件被重新打开
- 客户端通常会在一次请求中查询多个Chunk信息
Chunk尺寸
- Chunk size设计为64MB
- 选择较大的Chunk尺寸：
- 能够减少客户端和Master的通讯需求，并且能够对一个块进行多次操作
- 通过与Chunk服务器保持较长时间的TCP连接减少网络负载
- 减少Master需要保存的元数据数量
- 但是，小文件包含较少的Chunk，甚至只有一个Chunk。当许多客户端对同一个小文件进行多次的访问时，存储这些Chunk的Chunk服务 器就会变成热点。在实际应用中，由于我们的程序通常是连续的读取包含多个Chunk的大文件，热点还不 是主要的问题。 然而，当我们第一次把GFS用于批处理队列系统的时候，热点的问题还是产生了：一个可执行文件在GFS 上保存为single-chunk文件，之后这个可执行文件在数百台机器上同时启动。存放这个可执行文件的几个 Chunk服务器被数百个客户端的并发请求访问导致系统局部过载。我们通过使用更大的复制参数来保存可 执行文件，以及错开批处理队列系统程序的启动时间的方法解决了这个问题。一个可能的长效解决方案 是，在这种的情况下，允许客户端从其它客户端读取数据
元数据
- Master服务器主要存储3种类型元数据：文件和Chunk的命名空间、文件和Chunk的映射关系、每个Chunk副本的存放位置，都存放在内存里
- 前两种类型元数据还会以记录变更日志的方式，记录在OS的系统日志文件，存储在本地磁盘。日志会复制到其它远程Master服务器——可以简单可靠地更新Master服务器 的状态
- Master服务器在启动时，或有新的Chunk服务器加入时，向各个Chunk服务器轮询相应的Chunk信息
内存中的数据结构
- 元数据保存在内存中，因此Master服务器操作速度很快，能够周期性扫描保存的全部状态信息
- 但此时Chunk的数量以及系统的承载能力受限于Master服务器的内存大小——实际应用中这不是一个大问题
Chunk位置信息
- Master服务器不持久化保存“哪个Chunk服务器存有指定Chunk的副本”，而是启动时轮询Chunk服务器以获取该信息
- 这种设计简化了Chunk服务器加入集群、离开集群、更名、失效、以及重启的时，Master服务器和Chunk服务器数据同步的问题
操作日志
- 操作日志包含关键的元数据变更历史记录——操作日志是元数据唯一的持久化存储记录，也是判断同步操作顺序的时间基准——通过逻辑日志的序号作为操作发生的逻辑时间——文件、Chunk、它们的版本都由它们创建的逻辑时间唯一地标识
- 只有把相应的日志记录写入本地以及远程机器的硬盘后，才会响应客户端的操作请求（会收集多个日志记录后批量处理）
- 为了缩短Master启动时间，必须使日志足够小——Master服务器在日志规模到一定程度时对系统状态保存为一个Checkpoint，并删除之前的日志文件
- 灾难恢复时，Master服务器读取磁盘中Checkpoint文件，以及重复Checkpoint之后的有限个日志记录即可恢复
- 创建Checkpoint需要时间，因此Master服务器内部状态被组织为特殊的格式，确保创建时不会阻塞正在进行的修改操作（包含百万个文件的集群创建一个Checkpoint需要1分钟）
- Checkpoint文件会被写入在本地和远程的硬盘，旧的Checkpoint文件和日志文件可以被删除
一致性
- 文件命名空间的修改（如文件创建）是原子的
- 在客户端缓存的超时时间和文件下一次被打开的时间之间存在一个时间窗，文件再次被打开后会清除缓存中与该文件有关的所有Chunk位置信息
- GFS通过Master服务器和所有Chunk服务器的定期“握手”来找到失效的Chunk服务器，使用Checksum来校验数据是否损坏 ，只有当一个Chunk的所有副本在GFS检测到错误并采取应对措施之前全部丢失，这个Chunk才会不可逆转的丢失
系统交互
租约（lease）和变更顺序
变更：一个会改变Chunk内容或者元数据的操作，如写入操作或者记录追加操作，变更操作在Chunk 的所有副本上执行
使用租约（lease）机制来保持多个副本间变更顺序的一致性
Master为Chunk的一个副本建立一个租约，该副本称主Chunk。主Chunk对Chunk的所有更改操作进行序列化。所有的副本都遵从操作序列进行修改
写入操作的控制流程：（上图）
- 客户机向Master节点询问哪个Chunk服务器持有当前的租约，以及其它副本的位置。若没有Chunk持有租约，Master选择一个副本建立租约
- Master将主Chunk标识符及其它副本（二级副本）的位置返回给客户机。客户机缓存这些数据，只有主Chunk不可用，或者主Chunk回复已不再持有租约时，客户机才重新跟Master联系
- 客户机以任意的顺序把数据推送到所有的副本上
- 当所有副本都确认接收到数据，客户机发送写请求到主Chunk服务器。主Chunk为接收到的所有操作分配连续的序列号（操作可能来自不同的客户机，序列号保证操作顺序执行），并以序列号的顺序在本地执行这些操作
- 主Chunk把写请求传递到所有的二级副本，二级副本依照主Chunk分配的序列号以相同的顺序执行操作
- 二级副本回复主Chunk表示已经完成操作，主Chunk服务器回复客户机。任何副本产生的任何错误都会返回给客户机，客户机代码通过重复执行失败的操作来处理
- 一次写入的数据量很大，或者数据跨越了多个Chunk，GFS客户机代码会把它们分成多个写操作
数据流
- 把数据流和控制流分开
- 在控制流从客户机到主Chunk、再到二级副本的同时，数据以管道的方式沿一个精心选择的Chunk服务器链推送——而不是以其它拓扑形式分散推送
- 线性推送下，每台机器所有的出口带宽都用于以最快的速度传输数据， 而不是在多个接受者之间分配带宽
- 网络拓扑非常简单，通过IP地址就可以计算出节点的“距离”
- 利用基于TCP连接的、管道式数据推送方式来最小化延迟
原子的记录追加
- GFS提供了一种原子的数据追加操作–记录追加
- 传统的写入操作里，客户程序会指定数据写入的偏移量
- 使用记录追加，客户机只需要指定要写入的数据，GFS保证至少有一次原子的写入操作成功执行，写入的数据追加到GFS指定的偏移位置上，之后GFS返回偏移量给客户机
- 记录追加是一种修改操作，也遵循上一节描述的控制流程
- 客户机把数据推送给文件最后一个Chunk的所有副本后，发送请求给主Chunk。主Chunk检查这次记录追加操作是否会使Chunk超过最大尺寸
- 如果超过了最大尺寸，主Chunk先将当前Chunk填到最大尺寸，之后通知所有二级副本做同样的操作，回复客户机要求其对下一个Chunk重新进行记录追加操作
- 如果没有超过，主Chunk把数据追加到自己的副本内，通知二级副本把数据写在跟主Chunk一样的位置上，回复客户机操作成功
- 如果在任何一个副本上失败，客户端需要重新进行操作
快照
- (alex注：这一节非常难以理解，总的来说依次讲述了什么是快照、快照使用的COW技术、快照如何不干 扰当前操作)
- 快照操作几乎可以瞬间完成对一个文件或者目录树的拷贝，几乎不会对正在进行的其它操作造成干扰
- 用户可以使用快照创建一个大数据集的分支拷贝，或者在数据操作前使用快照备份当前状态
- 用标准的copy-on-write技术实现快照
Master节点的操作
命名空间管理和锁
- Master节点的很多操作会花费很长时间，因此允许多个操作同时进行，使用名称空间的region上的锁来保证执行的正确顺序
- 在逻辑上，GFS的名称空间是一个全路径和元数据映射关系的查找表。利用前缀压缩，查找表可以存储在内存中
- 在存储名称空间的树型结构上，每个节点（绝对路径的文件名或绝对路径的目录名）都有一个关联的读写锁，Master节点的操作在开始之前都要获得一系列的锁
- 采用这种锁方案的优点是支持对同一目录的并行操作
- 锁的获取也要依据一个全局一致的顺序来避免死锁：首先按名称空间的层次排序，在同一个层次内按字典顺序
副本的位置
- Chunk副本位置选择的策略：最大化数据可靠性和可用性，最大化网络带宽利用率
- 必须在多个机架间分布储存Chunk的副本
创建，重新复制，重新负载均衡
- Chunk的副本有三个用途：Chunk创建，重新复制和重新负载均衡
- 当Master节点创建一个Chunk，它会选择在放置初始的空的副本位置，选择因素包括：
- 在低于平均硬盘使用率的Chunk服务器上存储新的副本
- 限制在每个Chunk服务器上”最近”的Chunk创建操作的次数
- 把Chunk的副本分布在多个机架之间
- 当Chunk的有效副本数量少于用户指定的复制因数时，Master节点会重新复制它
- 为了最小化失效的Chunk对正在运行的应用程序的影响，提高会阻塞客户机程序处理流程的Chunk的优先级。 Master节点选择优先级最高的Chunk，命令某个Chunk服务器直接从可用的副本”克隆”一个副本
- Master服务器周期性地对副本进行重新负载均衡：检查当前的副本分布情况，移动副本以更好的利用硬盘空间、更有效的进行负载均衡
垃圾回收
- 惰性策略，只在文件和Chunk级的常规垃圾收集时进行
- 当一个文件被应用程序删除时，Master节点把删除操作以日志的方式记录 下来，但并不马上回收资源，而是把文件名改为一个包含删除时间戳的隐藏名
- Master节点对文件系统命名空间做常规扫描时，会删除所有三天前的隐藏文件
- 当隐藏文件被从名称空间中删除，Master服务器内存中保存的这个文件的相关元数据才会被删除——切断了文件和它包含的所有Chunk的连接
- 类似的，Master节点找到孤儿Chunk（不被任何文件包含的Chunk） 并删除它们的元数据。Chunk服务器在和Master节点交互的心跳信息中，报告拥有的Chunk子集，Master节点回复哪些Chunk的元数据中已经删除，Chunk服务器据此删除相应Chunk
过期失效的副本检测
- Master节点保存每个Chunk的版本号，以区分当前副本和过期副本
- 若某个副本所在的Chunk服务器正好处于失效状态，副本的版本号就不会被增加。在这个Chunk服务器重新启动，并向Master节点报告拥有的Chunk集合及相应的版本号时，Master会检测出它包含过期的Chunk
- Master节点在例行的垃圾回收过程中移除所有的过期失效副本
- Master节点在通知客户机哪个Chunk服务器持有租约、或者指示Chunk服务器从哪个Chunk服务器进行克隆时，消息中都附带Chunk的版本——客户机或Chunk服务器都会验证版本号，以确保访问最新数据
