之前上学的时候读过Google三架马车的论文，后续再读时，发现有些地方以前理解还是不够深刻。本文是重新学习GFS论文时记录的阅读笔记，行文比较散，主要是记录一下自己比较感兴趣的点，有需要的同学还是请直接参考原始论文。

1 背景

用大量普通机器搭建集群，因此节点失效成为集群中常态的问题，GFS必须要考虑这个问题。

GFS主要用来存放大文件，应用访问时，也基本是顺序流式读取，比如上面跑MapReduce程序，IO基本就是顺序读写。

2 接口

GFS是应用层的文件系统，但提供的接口基本类似POSIX标准API。目录树、打开关闭文件等接口在GFS都有。

此外，GFS提供了快照和记录追加操作。快照是创建一个拷贝，记录追加能够保证多个客户端同时对一个文件追加数据时，操作都是原子的。

3 架构

GFS包含一个Master和多个ChunkServer。像HDFS会给Master做HA（除了Namenode之外，还有一个Secondary Namenode热备）。

GFS的文件通常都比较大。GFS将大文件分割成若干个Chunk。Chunk是固定大小的块，大小默认为64MB。一个Chunk会存三份来提高可用性。

Master节点负责管理所有系统元数据。比如namespace、文件和Chunk的映射关系、chunk的位置信息等。此外master还管理chunk的租约、chunk的迁移、节点的在线信息。

GFS客户端以库的形式连接到应用的程序里。

一次简单读取的大致流程：客户端先算一下要读的数据在哪些Chunk上，然后把文件名和Chunk ID发给Master，Master告诉客户端，然后客户端就去访问对应的ChunkServer。后续会介绍更加细节的流程。

因为访问模式的原因，GFS基本不额外缓存文件数据。客户端要缓存从Master拉取的元数据信息。

4 Chunk大小

Chunk设大的好处：

• 减少了客户端和Master通讯次数；客户端能够缓存更多的Chunk元数据信息。

• 客户端可以对一个Chunk多次操作，这些操作都在一个TCP连接里完成。

• 减少了元数据信息，减轻了Master节点的负担。

Chunk设大的坏处：

• 小文件可能只有一个chunk，有可能成为热点chunk。

• 内部碎片

5 元数据管理

主要包括如下几类元数据：文件和Chunk的namespace，文件和Chunk的映射关系、Chunk的位置信息。前两种类型的元数据采用变更日志的方式持久化并同步到备机上，Chunk的位置信息是在Master启动时去询问所有的Chunk，新的ChunkServer加入时也会向Master报告。元数据信息都保存在内存中。

文件名的保存会经过前缀算法压缩，具体方法不明（猜测可能是类似于SSTable中前缀相同的就不记录了，只记录后面不同的部分），有了解的读者敬请指教。后面提到了GFS不支持ls_dir之类的函数，它管理的是全路径到元数据的映射关系。每个全路径都有读写锁。

元数据的锁：类似于数据库的意向锁，对数据项加锁时，要先对上层数据项加意向锁。加锁也要按照顺序来，先是从上层往下层申请，然后同层内按名字的字典序加锁，避免死锁问题。

操作日志类似于数据库的redo日志。Checkpoint等技术也在GFS日志中有应用。

6 写流程

我们看一下数据修改的流程。

!http://loopjump.com/wp-content/uploads/2015/06/write_flow.png

• 1 客户端问Master，哪一个ChunkServer持有指定Chunk的租约、所有Chunk副本的位置。如果没人有租约，Master设置一个。
• 2 Master告诉客户端谁是主副本（有租约的称为主副本），都有哪些备副本。客户端会缓存收到的信息。
• 3 客户端向所有的副本推送数据（次序任意）。ChunkServer收到数据会缓存在本地的buffer中。
• 4 客户端发现所有的副本都收到了数据之后，向主副本发送写操作命令。主副本收到写命令后，负责确定写次序（因为可能会有多个客户端向同一个Chunk写），并本地写盘。
• 5 主副本向所有备副本发写入命令（带有上一步已经确定的次序）。备副本收到后，按照主副本确定的次序将数据写盘。
• 6 备副本告诉主副本执行结果。
• 7 主副本回应客户端。任何一个副本写错了，就告诉客户端错误。

可能出现一些副本写成功（如果有成功者，按流程主副本必然在其中），一些写失败的情况。此时，操作被客户端认为失败，数据其实是不一致的（在各个副本上内容不同），客户端重试。

7 一致性模型

Namespace的修改由Master负责互斥。

文件修改后的Region（可以理解为文件中的一段）状态取决于操作类型、操作是否成功、操作是否并发。

GFS提供的一致性模型归结为下表。

!http://loopjump.com/wp-content/uploads/2015/06/gfs_consistency.png

consistent: 客户端不管读哪个副本，都能读到一样的数据。

defined: 首先是consistent，其次还满足客户端读到的数据是某次变更操作的全部内容，而不是多个写操作的混杂的数据。

数据修改包括两类操作：写操作（write）；记录追加（record append）。

写操作是在应用指定的一个偏移位置写数据。记录追加会将数据原子地追加到文件中（偏移位置是GFS定的，不是通常所说的追加到文件末尾）。

写操作的一致性：如果串行操作成功，文件状态是defined的。如果是并发写成功，文件状态是consistent but undefined。也就是说，客户端看到的数据都是一样的，但是可能看到的内容不能反映任何一个写操作的全部内容，而是来自多个修改的混杂的数据（mingled fragments from multiple mutations.）。如果失败，结果是inconsistent的。

consistent but undefined可能不太好理解，它实际说的是写请求不是serializable的。我们举个例子可能就清楚了。假如多个客户端同时修改一个文件的[a,b]这个范围的内容，其中a=64M,b=64M+1，即这两个字节正好跨两个chunk的边界。某个客户端想把内容改为”AA”，另一个客户端想改成”BB”。 consistent but undefined是说，可能出现”AB”或”BA”的结果。这个结果并不能反映任何一个操作的全部修改。

对于记录追加，操作成功了，其结果是defined interspersed with inconsistent的。为理解这个结论，我们先看记录追加的过程。

记录追加和上述描述的写操作流程基本类似，只是多了一步追加padding的逻辑。追加padding的目的是保证记录追加的原子性。跨Chunk的追加可能导致非serializable的结果，所以假如文件最后一个Chunk剩余空间不够存放本次写操作的数据，就要把该Chunk填满padding（备副本也要同样地填上padding），再让客户端在新的Chunk上重试。在新的Chunk上（如果原Chunk剩余空间足够，就是在原Chunk上），主副本会将数据追加到Chunk内，然后通知备副本在同样的偏移量上追加数据。如果失败，会有如下的结果：某些副本上的数据写成功了，而另一些副本上没有该数据或只有部分数据。失败的操作会被重试。GFS不能保证副本的每个字节都是一样的，但是能够保证数据作为一个整体被至少一次原子地写入了，而且最后写成功的那次个各个副本上该记录对应的偏移量都是一样的。这就是为何前面说对于记录追加，操作成功了，其结果是defined interspersed with inconsistent。

GFS的这种一致性，给应用带来了一些麻烦。对于那些padding、垃圾数据和重复数据，应用需要自己过滤掉。至于过滤方式，可以使用CheckSum标记垃圾数据、重复数据可以使用唯一id标识。总之，应用不友好。

8 快照

快照是对一个文件或者目录树做拷贝。GFS快照是copy-on-write的方式实现的。创建快照时，不直接复制Chunk，而是对该Chunk增加引用计数。对一个文件做修改时，需要先确保该文件只有一个引用，如果不是，则说明有若干快照引用指向该Chunk，此时要先克隆一个Chunk出来，在克隆的Chunk上修改。显然，为了控制对Chunk的修改， Master要先取消该Chunk的租约（否则可能发生有某个不经过Master的写操作成功了），以便Master在更新Chunk之前检查Chunk的引用计数。

9 过期失效的副本检测

过期失效副本是说，如果Chunk的某个副本错过了一些修改，那么这个副本就不能提供服务了。这种副本要找出来删掉。检测方式就是每次续租约的时候Master让Chunk的版本号增加，这个版本号会被Master和所有Chunk副本持久化。有了这个版本号，我们就能检测过期失效的副本了。