GFS 论文阅读

本文为 Google 发表的The Google File System论文阅读笔记，GFS（Google File System）是由Google设计并实现的为大规模分布式数据密集型应用程序设计的可伸缩（scalable）的分布式文件系统。

GFS 概述

GFS假设

• 设备故障是常态：GFS 假设设备故障是常态，因此设计了一套完善的容错机制，包括数据备份、自动恢复等。
• 文件是大文件：GFS 假设文件是大文件，期望是能够存储几百万个大小为100MB左右或更大的文件。系
• 顺序读写：GFS 假设大部分的读写操作是顺序读写，因此设计了一套适合顺序读写的存储管理机制。
• 多用户并发读写：GFS 假设有多个用户并发读写文件，Google的文件通常在生产者-消费者队列中或多路归并中使用。来自不同机器的数百个生产者会并发地向同一个文件追加写入数据。
• 高吞吐率比低延迟更重要：GFS 假设高吞吐率比低延迟更重要，Google的大多数应用程序更重视告诉处理大量数据，而很少有应用程序对单个读写操作有严格的响应时间的需求。

GFS接口

对于客户端而言，GFS 提供了一个类似于 POSIX 的文件系统接口，包括创建、删除、打开、关闭、读、写、定位、重命名等操作。客户端只需要调用这些接口，而不需要关心底层的存储管理机制。另外，GFS 还提供了一些额外的接口，如 snapshot(快照)、record append(追加记录)。

GFS 架构

一个GFS集群由一个 主节点（master）和多个 chunkserver组成。主节点负责元数据管理，chunkserver负责数据存储。客户端通过主节点获取元数据信息，然后直接与chunkserver通信进行数据读写。

在GFS中，文件被分为固定大小的 chunk，chunk是GFS的基本存储单元，每个 chunk的大小为64MB, chunk的元数据大小为64bit。chunk的副本数由用户指定，通常为3个。chunk的副本分布在不同的 chunkserver上。

master负责存储GFS的元数据，元数据包括 文件和chunk的命名空间（namespace）、文件与chunk的映射关系（维护了一个文件是由哪些chunk组成的）、chunk的位置（chunk存在于哪一个chunksever上，这个数据不会持久化）。所有元数据都存储在master的内存中，对于前两种元数据，master会定期地将其持久化到本地磁盘上，并在远程备份。master不会持久化保存哪台chunkserver含有给定的chunk的副本的记录，而是简单地在启动时从chunkserver获取信息。

master还控制系统级活动如chunk 租约（chunk lease）管理、孤儿chunk垃圾回收（garbage collection of orphaned chunks）和chunkserver间的 chunk迁移（migration）。master周期性地通过心跳（HeartBeat）消息与每个chunkserver通信，向其下达指令并采集其状态信息。

在GFS中，chunk的大小设计为64MB，是一个比较大的值。这样做主要有下面几个优点：

1. 减少元数据的数量：相对于小文件，chunk的数量会减少很多，从而减少了元数据的数量。
2. 减少网络开销：为chunk较大，client更有可能在一个chunk上执行更多的操作，这可以通过与chunkserver保持更长时间的TCP连接来减少网络开销。
3. 减少了client与master交互的次数：client在读写文件时，只需要与master交互一次，获取文件的元数据信息，然后直接与chunkserver通信。

但是，chunk较大也会带来一些问题：

1. 内部碎片：如果一个文件的大小不是 chunk的整数倍，那么最后一个 chunk会有很多内部碎片。
2. hot spot：由于一个chunk太大，那么可能对这个 chunk的访问频率也会很高，这样就会导致 hot spot问题。

操作日志

包含重要的元数据更改的历史记录，master会将操作日志持久化到本地磁盘上，操作日志还能定义并发操作的顺序。

文件区域状态

GFS定义了三种文件区域状态，文件区域状态可能会在被写入时发生变化，这三种状态分别是：

1. consistent：一个文件区域的任意一个副本被任何client读取总能得到相同的数据。
2. defined：在一个文件区域的数据变更后，如果它是一致的，且client总能看到其写入的内容。
3. inconsistent：文件区域在一个失败的变更后状态会变为inconsistent,不同client可能看到不同的数据。
4. consistent but undefined：所有客户端能考到同样的数据，但数据可能并不反映任何一个变更写入的数据。通常，数据融合了多个变更的内容。

GFS能够保证在一系列变更执行成功后，被变更的文件区域状态为defined的 这一点是GFS通过以下方式实现的：

1. 对chunk执行变更时，其所有副本按照相同的顺序应用变更；
2. 使用chunk版本号（chunk version）来检测因chunkserver宕机而错过了变更的陈旧的chunk副本（章节4.5）。陈旧的chunk副本永远不会在执行变更时被使用，也不会在master返回client请求的chunk的位置时被使用。它们会尽早地被作为垃圾回收。

GFS租约

clint向GFS更改数据只能从租约节点进行，租约节点是一个chunkserver，由master授权。primary为应用于该chunk的所有变更选取顺序。所有副本都会按照这个顺序来应用变更。

这种租约机制是为了最小化master管理负载而设计的。租约的初始超时时间为60秒。然而，一旦chunk被变更，primary就可以向master请求延长租约时间，或者（通常为）接受来自master的租约时间延长操作。这些租约延长请求和租约授权请求依赖master与chunkserver间周期性地心跳消息来实现。

GFS写流程

1. client向master询问哪个chunkserver持有指定chunk的租约及该chunk的其他副本的位置。如果没有chunkserver持有租约，那么master会选择一个副本对其授权（这一步在图中没有展示）。

2. master回复primary副本的标识符和其他副本（也称secondary）的位置。client为后续的变更缓存这些信息。client只有当primary不可访问或primary向client回复其不再持有租约时才需要再次与master通信。

3. client将数据推送到所有副本（并没有将数据直接写入文件，而是先写入到一个临时区域）。client可以按任意顺序推送。每个chunkserver都会将数据在内部的LRU中缓存，直到数据被使用或缓存老化失效（age out）。通过将数据流和控制流解耦，我们可以使用基于网络拓扑的技术来提高开销高昂的数据流的性能，且与哪台chunkserver是primary无关。

4. 一旦所有副本都确认收到了数据，client会向primary发送一个write请求。这个请求标识了之前推送到所有副本的数据的作用。primary会为其收到的所有的变更（可能来自多个client）分配连续的编号，这一步提供了重要的顺序。primary对在本地按照该顺序应用变更。

5. primary将write请求继续传递给其他secondary副本。每个secondary副本都按照primary分配的顺序来应用变更。

6. 所有的secondary副本通知primary其完成了变更操作。

7. primary回复client。任意副本遇到的任何错误都会被报告给client。即使错误发生，write操作可能已经在primary或secondary的任意子集中被成功执行。（如果错误在primary中发生，那么操作将不会被分配顺序，也不会被继续下发到其他副本。）只要错误发生，该请求都会被认为是失败的，且被修改的区域的状态为inconsistent。client中的代码会通过重试失败的变更来处理这种错误。首先它会重试几次步骤（3）到步骤（7），如果还没有成功，再从write请求的初始操作开始重试。

如果应用程序发出的一次write请求过大或跨多个chunk，GFS的client代码会将其拆分成多个write操作。拆分后的write请求都按照上文中的控制流执行，但是可能存在与其他client的并发的请求交叉或被其他client的并发请求覆盖的情况。因此，共享的文件区域最终可能包含来自不同client的片段。但共享的文件区域中的内容最终是相同的，因为每个操作在所有副本上都会以相同的顺序被成功执行。

数据流与控制流解耦

GFS将数据流和控制流解耦，这样可以使用基于网络拓扑的技术来提高开销高昂的数据流的性能，且与哪台chunkserver是primary无关。

在控制流从client向primary再向所有secondary推送的同时，数据流沿着一条精心挑选的chunkserver链以流水线的方式线性推送。Google的目标是充分利用每台机器的网络带宽，避免网络瓶颈和高延迟的链路，并最小化推送完所有数据的时延。

当chunkserver收到一部分数据时，它会立刻开始将数据传递给其他chunkserver。因为GFS使用全双工的交换网络，所以流水线可以大幅减少时延。发送数据不会减少接受数据的速度。如果没有网络拥塞，理论上将$B$个字节传输给$R$个副本所需的时间为$B/T+RL$，其中$T$是网络的吞吐量，$L$是两台机器间的传输时延。

名词解释

chunk

GFS的基本存储单元，每个chunk的大小为64MB。chunk的副本数由用户指定，通常为3个。chunk的副本分布在不同的chunkserver上。

chunkserver

GFS的存储节点，负责chunk的存储、读写等操作。

master

GFS的主节点，负责元数据管理，chunk的分配、副本的管理、chunk的迁移等。

chunk lease

chunk租约，master通过租约机制来控制chunk的读写权限。master会向一个chunkserver授予一个chunk的租约，这个chunkserver就可以对这个chunk进行读写操作。

garbage collection of orphaned chunks

孤儿chunk垃圾回收，master会定期扫描文件系统，找出不再被使用的chunk，然后通知chunkserver删除这些孤儿chunk。

check point

Master节点会在磁盘中创建一些checkpoint点，这可能要花费几秒甚至一分钟。这样Master节点重启时，会从log中的最近一个checkpoint开始恢复，再逐条执行从Checkpoint开始的log，最后恢复自己的状态。(这样能够避免当Master节点故障重启，并重建它的状态，你不会想要从log的最开始重建状态，因为log的最开始可能是几年之前)

chunk 版本号

master使用chunk版本号来检测因chunkserver宕机而错过了变更的陈旧的chunk副本。陈旧的chunk副本永远不会在执行变更时被使用，也不会在master返回client请求的chunk的位置时被使用。它们会尽早地被作为垃圾回收。