论文下载
前言
继续拜读三驾马车，最近阅读了 GFS 的论文。这篇于 2003 年被收录在 SOSP 上的论文描述了一个工作在上千台机器的集群上的文件系统，其设计影响了后续很多项目，比如 HDFS 就是它的一种开源实现。我没有参与那个年代的技术变革，但是看了很多对这篇论文的评价，大家的观点基本是一样的，即，GFS 在技术上并没有什么创新点，它只是非常好地做了 trade-off，并以一种非常简单的设计做出了适合 Google 内部需求的强大系统。
于是这篇文章就用来记录一些我的读后总结，欢迎一起交流:-)
概述
GFS 的使用者是 Google 内部的一些应用（比如之前的 MapReduce），所以其设计就需要满足内部的需求。论文的第 1 节和第 2.1 节中都有一些需求上的描述，具体来说包括以下几点：1）GFS 应该工作在由很多常规设备组建的集群上，这意味着需要把“设备会出错”作为一种必然事件来对待；2）操作的文件都是大文件，通常有几个 GB 大小，所以 GFS 在大文件的处理上要优于小文件；3）在写入文件时，追加操作是非常频繁的，几乎没有随机写操作，所以 GFS 对追加写操作做了一些优化，并且也相对更强调它的一致性。
在设计上，GFS 中包括三个组件，分别是 Master、ChunkServer 和 Client，其中 Master 和 ChunkServer 都是用户态的程序，而 Client 以库的形式被业务代码使用。
下面简单介绍下这三个组件，更详细的内容见后文。
Client 负责根据业务代码的需求发送请求与 Master 和 ChunkServer 交互，从而完成各项操作，为了优化性能，它还会缓存一些信息在本地；
ChunkServer 负责实际的文件存储，它管理的基本单元就是 Chunk，一个完整的文件会被拆分成多个 Chunk，并被存储在 ChunkServer 上。为了更好地容错，每个 Chunk 都会保存多份，这些 replica 被分布在不同的 ChunkServer 上，其数量可以由用户指定。Chunk 在被创建时会被分配一个全局唯一的 Chunk handle 作为标识，这个标识有 64bit 大小，客户端可以使用它向某个 ChunkServer 索要数据。在表现上，每个 Chunk 都是一个按需动态扩展大小的文件（最大 64MB），也就是说 GFS 直接使用了 Linux 的文件系统来提供存储能力，而由于 Linux 在读取文件时自带缓存，所以 GFS 并没有实现自己的缓存；
Client 在读取文件时是只知道文件名的，那它如何知道文件对应的 Chunk 是哪些，而这些 Chunk 又在哪台 ChunkServer 上呢？这就要通过 Master 了，具体而言，Master 中保存了所有文件到 Chunk 的映射，以及 Chunk 的具体位置，Client 在读写文件时首先通过 Master 来获知对应的 Chunk 和其位置，然后就直接与对应的 ChunkServer 进行交互了，Master 在这里只是起到类似索引的作用。而除了这个功能，Master 还负责锁管理、垃圾回收、过期 Chunk 检测等功能。
操作接口
论文 2.2 小节中提到，GFS 并没有实现类似 POSIX 标准的文件系统接口，它支持的操作有 create、delete、open、close、read、write、snapshot、record append。除了这些操作外，根据后文的描述以及之前对 MapReduce 的解读，还可以推知 GFS 也支持 rename 操作。根据我的理解，这些操作可以被划分为三组，具体见下表：
| 组编号 | 操作 | 主要被操作的组件 |
|---|---|---|
| 1 | open/close | Client |
| 2 | create/delete/snapshot/rename | Master |
| 3 | read/write/record append | ChunkServer |
为什么这样区分呢？且听我细细道来。
第1组
对于 open/close 操作，论文中并没有过多的提及，但我们前面提到为了优化性能，Client 会缓存一些信息。比如在读取时，它会通过 Master 查询“文件 A 的第 X 个 Chunk 在哪”这样的信息，并以文件名+Chunk下标作为键进行缓存，缓存的过期方式有两个，其一是达到了设置的过期时间，其二就是重新打开这个文件。对于重新打开文件这一点，论文 2.7.1 节中的描述是 which purges from the cache all chunk information for that file。基于这一点，我推测文件的打开和关闭操作主要影响的是客户端，比如 open 操作用于在客户端建立对应文件的缓存结构，而 close 操作将这个结构释放掉。
我没有在论文中找到类似排他打开的操作，如果 GFS 支持这种操作，那么 open/close 必然要通知到 Master。与之类似的，如果 GFS 可以避免文件在打开时被删除，那么这两个操作也同样需要被通知到 Master。
第2组
我们前面提到，Master 中保存了文件到 Chunk 的映射。这里所谓的文件，其实就是 /x/y/z 这样的一个字符串，GFS 并没有常规文件系统中的目录的结构（这种结构中记录了目录中的内容），所以我认为在实现上Master 的这种映射关系保存成 kv 存储也没问题，但是出于减小体积、加快查找速度、方便恢复（详见后文）等方面的考虑，GFS 将文件路径组织成树状结构，并称其为 Namespace。在这棵树上的每个节点都有一对锁，分别是 read 锁与 write 锁，两种锁相互配合来避免并发的操作导致 Namespace 的混乱。这里的操作指什么呢，主要指的就是第二组中的内容。
create 操作
顾名思义，create 用于在 Namespace 中建立一个新的节点，论文中没有提到 create 的流程，但我认为如果仅仅是 create 文件，那并不需要立即为其创建一个 chunk，可以把 chunk 的创建延迟到到对这个文件执行写入时。前面提到 Namespace 中的每个节点都有一对锁，在 create 一个新节点时这对锁也会参与进来。具体来说，假设我们要创建 /home/hygao/file1，那么在创建的过程中 /home、/home/hygao 都会被加上 read 锁，而 /home/hygao/file1 会被加上 write 锁。这意味着，我们可以同时创建 /home/hygao/file2，因为 /home 和 /home/hygao 都是 read 锁，而 read 锁之间并不冲突，但我们不能同时创建 /home/hygao/file1，因为 /home/hygao/file1 已经被上了 write 锁，write 锁之间是相互冲突的。
delete 操作
论文中重点介绍了删除文件的场景，但没怎么提及删除目录的场景（从论文 4.1 小节中可以推断出 GFS 是支持删除目录的），所以这里仅讨论删除文件的相关内容。GFS 的 delete 包括 Master 中元数据的删除以及对应 Chunk 的删除，整个过程需要和 Master 的垃圾回收功能相配合。
具体而言，当用户申请删除一个文件时，GFS 将这个文件 rename 为一个隐藏名（其实个人电脑的回收站也是这个原理），这个隐藏名中记录了删除时的时间戳。GFS 会定期扫描 Namespace，所以它可以知道这些被标记为“应该删除”的文件已经在“回收站”中保存了多久，而用户可以配置一个最大保存时间，超过这个时间的“应该删除”的文件就会真的执行删除，在此之前，用户可以通过将这些文件 rename 成普通文件的方式来避免它们被删除。所谓”真的执行删除“，就是将这个节点从 Namespace 中移除掉，这样该文件对应的 Chunk 就变成了孤儿（orphaned chunk），即没有任何一个文件引用它们，此时 Master 就可以向对应的 ChunkServer 发送指令，让它们删除掉对应的 chunk，从而释放硬盘空间。
这种机制的好处在于删除操作会非常快速（因为仅涉及 namespace 的操作），且误删时在一定时间内还可以将其快速恢复。与之相对的，坏处在于所谓的删除其实并没有立即释放出硬盘的空间，这在空间吃紧的情况下是非常无力的。如何解决这个问题呢？根据论文的描述，如果用户重复删除同一个文件，那么垃圾回收会被加速；此外，用户可以指定一个节点的删除策略，这样在用户执行 delete 时文件就会被立即删除并释放空间，这样的删除不可恢复，而这里提到的节点，其实就代表可以在目录和文件两个维度进行配置。
其实根据上面的描述，可以推测出还有第三种加速删除的方式，因为 GFS 判断文件在“回收站”里保存了多久是根据文件名中的时间戳，而用户首先可以访问这些文件，其次可以对其 rename，那只要修改掉文件中的时间戳，让 GFS 认为这个文件已经被保存很久了，就可以在下次垃圾回收时将它清理掉了:-P
此外由于在对文件操作时（比如后面的 snapshot）不能将其删除，所以可以推测 delete 也会给文件加上 write 锁。
snapshot 操作
根据我的理解，snapshot 操作应该类似于个人电脑上对文件或文件夹的复制，复制后的文件或目录拥有与复制源相同的内容，但对复制后的内容的修改不会影响到复制源。GFS 支持目录和文件两个级别的 snapshot，不过论文中只介绍了文件级别的流程，所以这里也同样仅讨论文件的 snapshot 操作。GFS 对这个操作做了一些优化，具体包括 CoW 和本地复制。
CoW 也就是 copy-on-write，这项技术旨在尽可能复用已有的内容。在 GFS 的场景下，表现为当用户执行 snapshot 时，新的文件对应的 chunk 同样使用源文件的 chunk。也就是说，如果有文件 /file1，其对应的 chunk 为 A、B、C，那么对其执行 snapshot 创建文件 /file2 时，这个新文件对应的 chunk 同样是 A、B、C。由于 snapshot 出的新文件本身就拥有和源文件同样的内容，所以在用户对新文件执行 read 操作时不会感受到有什么问题。
但是写文件时就不一样了，如前所述，对新文件的修改不会影响到源文件，这要怎么做呢？就是 CoW，即用户对文件对应的某个 chunk 执行写入时，Master 会让 ChunkServer 复制一个新的 chunk 出来，并为其分配 chunk handle，再把这个新的 chunk handle 返回给客户端，此后客户端的写入请求都在这个新的 chunk 上生效，从而避免了对源 chunk 的影响。这里 Master 会认为需要创建一个新的 Chunk，是因为每个 Chunk 保存了一个引用计数，如果它大于 1，那么就说明需要创建新的 Chunk，创建后会将源 Chunk 的引用计数减一，因为此时被读取的文件已经引用了新的 Chunk。
那么本地复制指的是什么呢，其实这是我自己起的名字:-P。它实际表示的是，Master 在创建新的 chunk 时，会让源 chunk 所在的 ChunkServer 来创建这个新的 chunk，这样的好处在于 chunk 的复制不需要走网络，相关的 IO 都仅发生在磁盘上，根据论文，Google 的磁盘读写速度差不多是网络的 3 倍。但是这也会有一个问题，就是如果源 ChunkServer 上的磁盘容量不足以创建这个新的 chunk 该怎么办，我不清楚文件系统会不会对此做什么优化，不过论文中并没有对这种情况作出说明。
最后，根据 4.1 小节，snapshot 会给文件加上 write 锁，从而避免 snapshot 的过程中发生删除、创建新文件等。
rename 操作
论文中并没有描述 rename 的流程，但是从 MapReduce 以及文中的一些描述我们可以推断 GFS 是支持这个操作的，而且这个操作是原子的。根据这一点，我推测 rename 操作会给源文件与目标文件加 write 锁。
而 rename 的原理应该就是节点内容的迁移，比如把 /file1 文件 rename 成 /file2，就是把 /file1 对应的 chunk 给 /file2，然后删除 /file1 这条记录，这个操作只涉及 Master，不会对 ChunkServer 产生影响。这里的删除指的是从 Namespace 中直接删掉，而不是前面提到的 delete 操作。
第 3 组
最后一组就是最重要的操作了，因为它主要与 ChunkServer 进行交互，也就是完成对文件的读写，这是一个文件系统的核心能力。虽然这是 GFS 中最有趣的部分，但是为了避免这篇文章太长，所以这部分以及后续的内容就放在下一篇文章中来讨论吧:-)
