GFS论文阅读笔记

论文链接

Architecture

• 一个GFS Cluster由一个master和多个chunkserver组成

  
  

• 一个文件会被切分为固定大小（64MB）的chunk。在创建chunk时，master会分配一个64bit的全局唯一且不可修改的 chunk handler 来标志这个chunk。

• chunkserver 将chunk存储在本地磁盘中，并通过chunk hander和byte range来读写chunk文件。为了可靠性，chunk被复制多份 chunk replica 存储在不同的chunkserver上（默认3份，用户也可以对文件系统名字空间的不同地方设置不同的复制份数）。

• GFS client为应用程序提供了文件系统API），包括create, delete, open, close, read, write, record append等（但没有实现POSIX的标准接口）。Client在和master交互元数据后，直接和chunkserver交互进行读写数据。

Master

• Master负责维护文件系统的所有元数据（metadata），包括：命名空间（namespace，也就是常规文件系统的中的文件树），访问权限，文件到chunk的映射，每个chunk replica的当前位置等。

Metadata

• 所有的元数据都存储在master的内存里。
• master会将命名空间，文件到chunk的映射等信息通过 operation log 的方式进行持久化到本地磁盘，再备份到远程机器。在metadata的change没有持久化之前，client是不能看到的数据的更改。而且只有当操作记录持久化存储在本地和远端以后，才会回复client数据更改成功。
• 而chunk replica的当前位置信息不会被持久化，而是在master启动时向chunkserver查询其chunk信息，然后通过 heartbeat 来持续更新master的副本分布信息，以与chunkserver数据保持一致。
• 可以通过回放operation log恢复文件系统。为了减少系统启动时的恢复时间，master可以定期存储metadata的 checkpoint ，master重启时可以从checkpoint加载metadata（checkpoint是类似B-Tree的数据结构，可以直接加载进内存），然后回放checkpoint之后的少量日志即可。

数据更改

• 数据修改包括chunk的write或者append操作:

1. write：写数据到应用程序指定的file offset
2. append：将数据(record)至少一次原子性的append到文件中，offset由GFS选择(通常是将data append到某个文件的尾部)。 这个offset会返回给客户端

• 数据的修改会在chunk的所有副本上执行，GFS使用 lease 机制来保证chunk副本上修改操作的执行顺序。master将lease颁发给chunk的一个副本，称之为 primary ，primary然后选择chunk上其他replica（称为secondary）的修改执行顺序。具体步骤为：

1. client向master查询chunk的primary和secondary所在的chunkserver，如果没有一个replica拥有lease，master会选择一个replica并授予lease（需要等待lease过期，以防止脑裂）
2. master返回primary和secondary的信息。client会cache返回的信息。直到primary不拥有lease（默认持有lease 60秒）或不可访问，client将需要再次请求master。
3. client将数据发送给所有的replica，顺序可以是任意的。每个chunkserser会将数据存储在内存的LRU buffer cache中。
4. 当所有的副本都返回已经接收数据成功后，client会向primary发送一个写请求。primary会为每一个数据更改的请求附加一个序列号，primary按照序列号顺序执行本地数据更改。
5. primary传递数据更改请求到secondary中，这些replica也按照序列号顺序执行本地数据更改。
6. secondary完成数据更改后，回复primary
7. primary回复client。期间发生的所有错误都会报给client，表示请求失败。客户端会重试，直到成功。

• 如果客户端写操作的数据跨了chunk的边界，那么写操作会被分割成多个chunk上的写操作，每个chunk上的写操作遵循上面的流程。各个chunk上写写操作可能会被来自其他的客户端的写操作交错并覆盖。

Data Flow

• 每个chunkserver传输数据给在网络拓扑结构中最近的还没收到数据的chunkserver。

Atomic Record Append

• 如果record append在某个replica上失败了，client会进行重试。因此可能造成同一个chunk的不同的replicas包含不一样的数据，有的replica有重复的record，或者包含record的一部分。GFS不保证不同的replicas的数据每个bit都是一样的，但保证如果record append操作成功了，数据在同一个chunk的所有的replicas的offset是相同的。

Snapshot

• GFS使用copy-on-write的方法实现Snapshot。具体操作步骤为：

1. 当master收到snapshot的请求时，会收回snapshot涉及的文件的chunk的lease，之后client对相关文件进行写操作时，primary将回复client它已经不再hold lease，使其必须与master进行交互。
2. master执行snapshot操作，即将chunk的引用计数+1，复制源文件或者目录树相关的元数据，这份元数据也指向相同的chunk
3. snapshot操作过后，当client对chunk C进行写操作时，它询问master哪个replica持有chunk C的lease，这时，master发现chunk C的引用计数大于1，master将推迟回复客户端并
   选出一个新的chunk handle C'。然后让有chunk C replica的chunkserver 在本地复制出chunk C'出来，这个chunk就叫做C'
4. master授予lease给其中一个replica，最后回复客户端。后续的操作就和之前相同了。

命名空间管理和锁

• 逻辑上来说，GFS命名空间是一个文件完整路径名到元数据的lookup表。
• 命名空间树上的每个节点（一个
  绝对路径的文件名，或一个绝对路径的目录名）都有一个读写锁。
• 创建一个文件时，回对相关路径上读锁，对文件上写锁。

创建，再次复制，重新负载均衡

• chunk replica创建的原因有三种：1. chunk的创建 2. 再次复制 3. 重新负载均衡
• 当master创建一个chunk的时候，它选择在哪里放置新的空的replica。主要考虑如下因素：

1. chunkserver上面磁盘的利用率，尽量将replica放到低磁盘利用率的机器上
2. 限制chunkserver机器最近的创建的数目，为了防止单个chunkserver压力过大
3. 尽可能将replicas散布在不同的机架

• 当replica因为磁盘损坏等原因unavailable，replica数量低于设置阈值时，master会再次复制生成replica。master选择优先级最高的chunk，然后指示一个chunkserver从一个已经存在的合法的replica上复制一份，同样，replica的放置规则也会考虑前面提到的放置因素。复制的chunk的优先级基于以下几个因素：

1. 当前replica数量离目标数量的差距
2. 趋向于复制live file的chunk，而不是deleted file的chunk
3. 为了最小化失败对应用程序的影响，可能会阻塞客户端过程的chunk的优先级更高。

• master周期性地检查replica的分布，进行重新负载均衡，

垃圾回收

• 当删除一个文件后，master会立刻把这个删除操作记录在日志里，但这个删除操作并没有立即实际执行，它只是把这个文件重命名了为一个包含时间戳的隐藏文件。后面master定期扫描所有文件(namespace)时，如果文件为隐藏文件，会比较这个隐藏文件中的时间戳和现在的时间，如果超过3天(过期时间可配置)才真正删除文件。但在这个期限之内，这个隐藏文件依然可以被读到。
• master 不能识别的replica是垃圾
• GFS允许设置立即删除模式以快速释放存储空间，不同命名空间可以制定不同的复制和回收策略。

过期失效的replica检测

• replica可能因为chunkserver 失效，丢失了一些数据修改记录
• master 通过 Chunk 的版本号区分up-to-date replica和过期的replica
• master 授予lease时增加版本号，然后通知replica。master和replica都会将该版本号信息进行持久化。
• master 会在垃圾回收的过程中移除过期失效的replica

数据完整性(Data Integrity)

• Chunkserver 使用 checksum 来检查数据完整性。
• 每个 Chunk 分为 64KB 的 block，每个 block 对应一个 32位的 Checksum。checksum存储在内存中，并以日志的方式进行持久化在和用户数据分开的地方。
• 读操作时会检查 checksum 是否正确，如果不正确，会返回client错误信息，并告知master。client将从其它replica读取信息。同时master将从其它replica复制数据对其进行恢复。
• Checksum 效验不需要额外 IO，对性能影响小。并且Checksum 对 Chunk append写入操作做了优化，只增量更新最后一个不完整 block 的 Checksum