1 导论
GFS的设计基于以下几点：
(1) 首先组间故障是一个很常见的事情。
(2) 普遍都是大文件，GB规模的文件也很常见。
(3) 大多数文件的更改方式是追加新数据而不是覆盖已经存在的数据。
(4) 共同设计应用程序和文件系统API可以增加灵活性，从而使整个系统受益
2 设计综述
2.1 假设
- 系统包含许多廉价的商业组间，这些组间会经常故障。因此系统必须经常监控自身，定期检测、容忍和及时从组件故障中恢复。
- 系统存储少量的大文件。我们希望有几百万个文件，每个文件的大小通常为100 MB或更大。多gb文件是常见的情况，应该进行有效的管理。必须支持小文件，但是不需要对它们进行优化。
- 负载主要包括两种读操作：大数据流的读和小的随机读。
- 负载还包括大而且连续的追加数据操作，但是在任意位置的小数据写也是支持的。
- 系统必须有效地为并发附加到同一文件的多个客户端实现定义良好的语义。
- 高持续带宽比低延迟更重要。
2.2 接口
GFS的文件按层次结构组织在目录中，并由路径名标识。并且GFS提供了常见的create、delete、open、close、read和write操作，此外还支持snapshot和record append。Record append允许多个客户端并发地将数据追加到同一个文件中，同时保证每个客户端追加的原子性。
2.3 架构
GFS集群包括一个master节点和多个chunkservers节点。文件时被划分成固定大小的chunk，每个chunk被创建时，由master分配一个全局唯一的64位的chunk handle。chunk以Linux文件的形式存放在chunkserver的本地磁盘中，并通过chunk handle和字节范围。为了可用性，每个chunk会有多个副本存储在多个chunkserver上。
master节点维持文件系统的全部元数据，包括namespace、访问控制信息、文件到chunk的映射和chunk的位置。master还控制了系统级别的活动，比如chunk租约管理、孤儿chunk的垃圾回收和chunkserver之间的chunk迁移。最后master周期性的与每一个chunkserver通过心跳消息来收集状态。
2.4 单一master
必须减少客户端和master的交互，避免单一master成为瓶颈。客户端仅仅向master询问它应该联系哪一个hunkserver，然后缓存这些信息一段时间，后续可以直接和chunkserver交互。因此读取同一个chunk只需要和master交互一次，直到客户端缓存信息已经失效或者文件被重新打开。
2.5 chunk大小
64MB大于典型的文件系统块大小。
2.6 元数据
master节点存储三个主要的元数据：文件和chunk的namespace，文件到chunk的映射和每一个chunk副本的位置信息。所有的元数据保存在master的内存中。另外文件和chunk的namespace，文件到chunk的映射还要持久化到磁盘中，这是通过记录一个operation log到磁盘中，并在远程机器上存储副本。master并不持久化chunk的位置信息，相反，当master启动的时候或者chunkserver加入集群的时候，master询问每一个chunkserver所包含的chunk。
2.6.1 内存数据结构
利用内存保存元数据信息可以获得较快的访问性能。而且不用担心内存空间的问题，因为一个64MB的数据块的元数据要少于64字节。相似的，每个文件namespace数据也要少于64字节，因为通过前缀压缩的方式存储文件名。
2.6.2 数据块位置
数据块位置之所以不持久化在内存中，是因为chunkserver对数据块的存放位置具有决定权，如果chunkserver故障，则会造成数据块消失。
2.6.3 Operation Log
operation log包含关键元数据改变的历史记录。这是GFS的核心，operation log不仅仅是唯一的元数据持久记录，而且它还定义了并发操作的逻辑时间线。GFS在多个机器上保存这部分日志，仅当多这些机器上的操作日志都刷新到磁盘上才回应客户端。master将多个log记录批量刷新到磁盘中，来提升性能。
master通过回放operation log来恢复文件系统的状态。为了最小化启动时间，GFS尽量使log很小。当operation log达到一定的大小后，checkpoint master的状态，所以master能够通过加载磁盘中最新的checkpoint和回放最新checkpoint点之后的日志记录来恢复状态。checkpoint是一个压缩的B-tree，可以直接映射到内存中，并用于namespace的查找。
因为建立一个checkpoint要花费一定的时间，所以master会新创建一个新的log文件，并在另外一个线程创建新的checkpoint。恢复仅仅需要最新的完整的checkpoint和随后的log文件，旧的checkpoint和log文件可以被释放。在checkpoint期间的故障不影响正确性，因为恢复代码会检测和跳过不完整的checkpoint。
2.7 一致性模型
2.7.1 GFS的保证
文件命名空间的更改是原子的，命名空间锁保证了更改的原子性和正确性，master的operation log定义了一个全局的操作顺序。
数据更改后文件区域（file region）的状态依赖于更改的类型，是否成功或者失败，或者是否是并发的更改。如表1所示，如果所有客户端无论从哪个副本读取到的数据都是相同的，则文件区域是一致的。如果文件区域是一致的，并且客户端可以读取到所更改的内容，则是已定义的。（1）当一个更改不涉及到并发写时，则相关的区域是定义的（同时也说吗是一致性的）。（2）并发更改操作成功的话，会使这段区域未定义但是一致的，所有的客户端可以读取到相同的内容，但是这段内容不和任何客户端所写的内容相同，通常它包含多个更改的混合片段。（3）失败的更改会使区域不一致，也未定义，因为不同的客户端可能会在不同时间读取到不同的数据。
数据更改可能是写或者记录追加。写操作是将数据写入到用户指定的文件偏移处，记录追加操作将数据追加到GFS选择的末尾偏移处，相反普通的追加操作仅仅是写在客户端认为的文件末尾处，如果存在并发的情况，则追加是atomically at least once。追加结束后，GFS将偏移返回给客户端，并标记包含这个记录的已定义区域的开始处。
连续的更改成功后，被更改的文件区域保证是定义的且包含最后一次更改的数据内容。GFS通过以下两点保证，(1)在所有的副本上以相同顺序更改。(2)使用chunk版本号来检测旧的副本，这些副本可能因为所在chunkserver异常导致没有更改。旧的副本会在合适的机会被进行垃圾回收。
因为客户端会缓存chunk的位置信息，所以在缓存的信息失效之前可能会读取旧的副本。这个窗口由缓存信息的超时时间决定。
3 系统交互
3.1 租约和更改顺序
master给其中一个副本授权一个chunk lease，该副本叫主副本，主副本给该副本所有的更改分配顺序，所有副本在应用更改时均要遵守这个顺序。因此全局的更改顺序首先是由lease授予顺序选择的，在lease内的顺序是由主副本分配的。
如图2所示：
(1) 客户端向master询问哪一个chunkserver持有当前chunk的租约，和其它副本的位置信息。如果没有人持有租约，则选择一个。
(2) master回复主副本和其它副本的位置，客户端会缓存这些信息。客户端仅当和主副本连接不上或者主副本回应说它不在持有一个租约时，才会和master联系。
(3) 客户端将数据发送给全部的副本。
(4) 一旦所有副本都收到了数据，客户端就会发送一个写请求给主副本。主副本给所接收到的所有更改分配连续的编号，这些更改可能属于多个客户端。主副本依据编号来将更改应用到它的状态中。
(5) 主副本转发写请求给所有的副本，每个从副本均以相同的编号来执行更改。
(6) 从副本完成更改操作后，要回应主副本更改已经完成。
(7) 主副本回应客户端。只要一个副本出错，则都会回应客户端更改失败。如果主副本失败的话就不会分配编号和转发请求。
如一个写操作足够大或者跨越一个块边界，GFS客户端会将其划分成多个写操作。它们都遵循上面描述的控制流，但是可能被来自其他客户端的并发操作交错和覆盖，因此，共享文件区域可能最终包含来自不同客户端的片段，尽管副本将是相同的，因为各个操作在所有副本上以相同的顺序成功完成。这使得文件区域处于一致但未定义的状态，如2.7节所述。
3.2 数据流
3.3 原子记录追加
GFS提供叫做记录追加的原子追加操作。传统写操作中，客户端指定数据写入的偏移位置。并发写到相同区域是不连续的，即这部分区域可能最终包含来自多个客户端的数据片段。然而在记录追加中，客户端仅仅指定数据，GFS负责将数据至少一次原子性(at least once atomically)追加到由GFS选择的文件末尾处，并把这个偏移返回给客户端，这和Unix系统中的O_APPEND模式很像。至少一次原子性应该是能保证一个客户端的一次记录追加操作是原子的，但是一个客户端的多个记录追加操作就不能保证了。
客户端将数据推送到所有副本后，发送一个请求给主副本。主副本检查追加记录到当前chunk中是否超过最大大小(64MB)。如果超过，则主副本将填充该chunk到最大大小，从副本也是如此，并让客户端在下一个chunk重试。如果追加记录没有超过最大大小，主副本追加记录，并告诉从副本在相同的位置追加记录，最后返回给客户端成功消息。
如果任何一个副本记录追加失败，则客户端需要重试操作。相同chunk的副本可能包含不同额数据，这些数据也可能包括相同记录的多个重复记录。GFS不保证chunk的所有副本内容都相同，仅仅保证数据以至少一次原子单元被写入到chunk。这个属性很容易从简单的观察中得出:为了报告操作成功，必须在某个块的所有副本上以相同的偏移量写入数据。此外，在这之后，所有的副本至少与记录的结束一样长，因此任何未来的记录将被分配一个更高的偏移量或一个不同的块，即使一个不同的副本以后成为主副本。就我们的一致性保证而言，成功记录追加操作写入数据的区域是被定义的(因此是一致的)，而中间区域是不一致的(因此是未定义的)。
因此可以看出GFS保证一个客户端的一次记录追加操作是原子的，并且每次记录追加操作都属于一个chunk，不会跨越多个chunk。
3.4 快照
快照使用copy-on-write机制
4 master操作
4.1 命名空间管理和加锁
GFS将其名称空间逻辑地表示为将完整路径名映射到元数据的查找表。通过前缀压缩，可以在内存中有效地表示这个表。名称空间树中的每个节点(绝对文件名或绝对目录名)都有一个关联的读写锁
master的每一个操作都需要获得一组锁，比如一个针对/d1/d2/…/dn/leaf的操作，master需要获得/d1，/d1/d2，/d1/d2/…/dn的的读锁，同时也需要获得/d1/d2/…/dn/leaf的读锁或者写锁。再比如，如果一个操作正在将/home/user做快照到/save/user，此时再/home/user下创建foo文件将会阻塞。因为快照操作会对/home和/save加读锁，对/home/user和/save/user加写锁。而创建/home/user/foo需要获得/home和/home/user的读锁和/home/suer/foo的写锁。文件创建不需要再父目录加写锁，因为GFS中不存在目录或者像Inode之类的防止被改变的数据结构，读锁足以保护父目录不被删除、重命名或者快照等。
加锁机制允许对同一个目录的多个并行更改，例如同一目录下的文件创建可以并行执行。
4.4 垃圾回收
4.4.1 机制
当用户删除一个文件时，master会在日志中记录删除操作，但是并不会立即回收资源，而是将文件重命名为一个包含删除时间戳的隐藏名字。在master扫描文件系统命名空间时会删除超过三天的未回收的文件。在此未真正删除期间，这些文件都可以被读取到或者被恢复删除。
在master日常扫描chunk命名空间中，master会确定孤儿chunk(即那些不属于任何文件的chunk)，并删除孤儿chunk的元数据。在chunkserver和master的心跳消息中，每个chunkserver都会报告它所拥有的数据块集合，master回复给chunkserver元数据中不再存在的chunk，之后chunkserver便可以删除掉这些chunk。
4.5 旧副本检测
如果chunkserver故障，则其中的一些chunk副本会因为没有更改而变成旧的。对每个chunk，master维持了一个chunk版本号来区分最新的和旧的副本。
当master给一个chunk分配一个新的lease时，会增加这个chunk的版本号。master和所有副本都要记录最新的版本号。如果一个副本不可访问，则版本号可能不是最新的。当chunkserver重启后并向master报告它的chunk集合和版本号，master将会检测到这个chunkserver的副本是旧的。如果master看到一个版本号大于它记录的，则说明master分配Lease出现故障，于是就会采取这个版本号为最新的版本号。
master在垃圾收集中回收旧的副本。
5 容错和诊断
5.1 高可用
5.1.1 快速恢复
5.1.2 chunk副本
chunk默认是3副本，当chunkserver下线或者corrupt时，master负责克隆存在的副本来保证每个chunk有足够的副本。
5.1.3 master副本
为了可用性，master的状态被复制成多份。master的log和checkpoint会被复制到多个机器上。一个更改操作仅当log记录被刷新到本地和所有master副本上的磁盘上才算完成。如果master的机器或者磁盘故障，会与GFS之外的监控基础设施会从副本中启动一个新的master节点。
此外，“影子”master（不是上述的master副本）提供对文件系统只读的访问权限，即使主master下线时也是这样。影子master的内容一般会比主master落后不到1秒钟。为了让自己保持知情状态，影子主机读取增长操作日志的副本，并对其数据结构应用与主服务器相同的更改序列。与主master一样，它在启动时(之后也不经常)轮询chunkservers以定位chunkreplicas，并与它们频繁交换握手消息以监视它们的状态。它仅依赖于主服务器来执行由于主服务器决定创建和删除副本而导致的副本位置更新。
5.2 数据完整性
每个chunkserver必须独立的利用保存的checksum来确认副本的完整。每个chunk划分为64KB大小的块，每个块对应一个32bit的checksum，checksum在内存和og中均存在。
对于读操作，chunkserver确认读操作所涉及的block的checksum是否正确，无论对方是客户端还是chunkserver，因此chunkserver不会传播错误的副本到其它机器。如果一个块不匹配就的checksum，chunkserver给请求者返回一个错误，并向master报告。请求者将会从其它副本读取数据，同时Master从其它副本克隆chunk（意思是只要有一个block错误，就会从新拷贝整个chunk），完成之后，master要求报告错误的chunkserver删除含有的chunk副本。
针对追加记录操作，对原有的最后一个块（也是追加记录的第一个块）进行增量更新，而对其它新加的块重新计算checksum，如果原有的最后一个块（也是追加记录的第一个块），在增量更新前已经corrupt，则在增量更新时不会发现，但是增量更新后，此块的checksum匹配依然会失败，在下次读取这个块时才发发现。
对普通的写操作，可能会更改第一个和最后一个块的部分内容，因此需要先检查这两个块的checksum，然后从新计算checksum。如果写之前不进行checksum检查，如果原有的块已经corrupt，就会发现不了。对其它块，反正都是全量覆盖写，则也需要重新计算checksum。