0. 小引
GFS 是谷歌为其业务定制开发的，支持弹性伸缩，为海量数据而生的分布式大文件存储系统。它运行于通用廉价商用服务器集群上，具有自动容错功能，支持大量客户端的并发访问。
GFS 是为大文件而生的，针对读多于写的场景。虽然支持对文件修改，但只对追加做了优化。同时不支持 POSIX 语义，但是实现了类似的文件操作的API。它是谷歌在 MapReduce 同时期，为了解决大规模索引等数据存储所实现的具有开创性的工业级的大规模存储系统。
其主要设计细节如下：
- 简化系统元信息：Master 中维持了两个重要的映射，分别是文件路径到逻辑数据块，逻辑块与其多副本之间的关系。
- 较大的数据块：选择了当时看来相当大的 64M 作为数据存储的基本单位，以此来减少元信息。
- 放宽的一致性：允许多副本间内容不一致来简化实现、提高性能，通过读校验来保证损坏数据对用户不可见。
- 高效副本同步：在多副本同步时分离控制流和数据流，利用网络拓扑提高同步效率。
- 租约分散压力：Master 通过租约将部分权力下放给某个 Chunkserver ，负责某个块的多副本间的读写控制。
- 追加并发优化：多客户端对同一文件进行并发追加，保证数据原子性及At Least Once的语义。
- 快速备份支持：使用 COW 策略实现快照操作，并通过块的引用计数来进行写时拷贝。
- 逐节点锁控制：对于每个操作，需要沿着文件路径逐节点获取读锁，叶子节点获取读锁或者写锁，当然文件路径会进行前缀压缩。
- 异步垃圾回收：将数据删除与其他一些主节点的维护操作（损坏块清除，过期数据块移除）统一起来，成为一个定期过程。
- 版本号标记：帮助客户端识别过期数据。
- 数据块校验和：针对每 64KB 的小块打上 32 bit 的校验和。
1. 概述
1.1 基本假设
像任何系统一样，其面向的场景需要有一些核心假设，这样其后的所有设计，才能根据这些假设进行取舍。那么 GFS 作为一个分布式的文件系统，其基本假设是什么？可以从几方面来看：错误处理、文件尺寸、修改方式、一致性模型。
错误处理
该文件系统的开创之一在于摒弃昂贵工业级的系统硬件，选用普通廉价的商用服务器硬盘集群作为存储介质。于是就必须在软件层面屏蔽这些廉价硬件的不可靠性，为上层应用提供一个可靠的存储服务，这个和 MapReduce 这种计算框架面对的问题是一致的。另外，在软件层面，通常会有成百上千的客户端在同时访问集群，而他们可能又分布在同等规模的其他机器上。
也就是说，在这种存储介质上构建如此尺度的系统，软硬组件出问题不应该被当做异常而应该认为是常态。比如用户代码有bug、操作系统出 bug、硬盘内存网络甚至电源供应，统统有可能出问题。
那么我们在设计系统的时候，就必须在系统内引入持续的监控以监控各个软硬组件的健康状态；整合出错检测、错误容忍、自动恢复机制，以对基本的错误进行告警、处理和自动恢复。
面向大文件
GFS 设计目标是针对单文件数十M到数G的尺寸。这在当时（2003）看来，已经是很大尺寸的了。当然，随着互联网和通信基础设施的进一步发展，图片和视频等非文本数据的爆炸式增长，现在看来这个假设已经很稀松平常了；不过也由此看出谷歌系统演进的前瞻性。
回到当时的情景，对于数百万计的 KB 尺寸的文件，纵然文件系统可以支持其存储，但是却难以高效地对其管理。因此，GFS 重新对常规文件系统的一些基本设计做了调整：包括文件块（block）的大小，IO操作的流程等等。
追加为主
在 GFS 针对的场景下，所有的文件修改类型，基本以追加为主，很少出现对已经存在的部分的覆盖。至于随机写，更是事实上不存在的。大体上来说，一旦写入完毕，文件就变为只读，并且是顺序读。
这样的场景有很多，比如应用持续运行所产生的数据流，比如归档数据，比如一些机器产生的待另一些机器同步或者异步消费的中间数据集。考虑到这些访问模式都是针对大数据文件，如何保证追加操作的并发性和原子性成为文件系统设计的要点；而传统的考虑数据访问局部性而在客户端做cache，在这里就没有那么有吸引力了，并不需要针对其做额外优化。
协同设计
通过对系统侧和应用侧的联合设计，能够大大提升系统的灵活性。比如 GFS 弱化了一致性模型，在不加重用户代码负担的情况下大大简化了系统设计；又比如，GFS 引入了原子的追加操作，使得多个客户端不用额外的同步操作就可以并发地对同一文件进行追加。
高吞吐
设计上，高吞吐优先于低延迟。因此为了保证吞吐量，可以适当牺牲延迟。也就是说，GFS 比较适合批量任务而非实时任务。
1.2 接口
GFS 虽然并没有实现 POSIX （可移植操作系统接口） 语义，但其 API 和文件系统类似，有 create, delete, open, close, read 和 write。此外，比较特别的一个操作是 record append，这个就比较厉害了，或者说是谷歌针对其场景专门优化的——支持多客户端并发写，在 MapReduce 任务 reduce 落盘阶段能大大提高吞吐。
那 GFS 相对于 POSIX的文件系统语义削减了什么呢？比如细粒度的权限控制，多用户、组用户控制，符号链接等等。
1.3 架构图
图画的微言大义，能看出不少信息：
- 物理上来说，系统有三种角色。客户端（Client），Master 节点和 Chunkserver 节点。Master 节点只有一个，其他的都有多个。本质上，Chunkserver 和 Client 都表现为 Linux 系统上的一个或一组进程。因此 Client 和 Chunkserver 可能在同一台 Linux 机器上。
- 逻辑上来说，系统有两大部分，元信息和数据。其中元信息主要包括文件系统命名空间，访问控制信息，文件到其所包含文件块的映射信息。这部分数据结构存储在 Master 上。数据包括一个个文件的实际数据部分，每个文件又被划分为固定大小的 chunk，以某种方式分散在各个 Chunkserver 上。
- Client 端包括用户代码和 GFS Client Library 两部分。后者以库代码形式提供，为前者调用。每次进行文件操作，Client 会首先向 Master 询问文件元信息，然后依据获取的数据位置信息去相应的 Chunkserver 找对应数据。
还有一些东西图中没详细说明，但是实现上却十分重要的：
- Master 维持一些和 Chunkserver 间的系统事件， 包括租约管理、孤儿块回收、数据块的迁移等等。Master 和 Chunkservers 间通过心跳来收集元信息并下发上述控制信息。
- 每个文件块（chunk）会在不同机器机架上进行三备份，这是进行容错的最直接粗暴的做法。但是它能带来很多其他的好处，如并发读等等，后面会详细说明。
- 客户端（Client）和 块服务器（Chunkserver）都没有像计算机的存储体系结构一样，在 GFS 层面对最近访问的数据进行缓存。一来能简化设计，二来数据块太大，缓存也没啥用。三来，可以利用 linux 系统自身的缓存。
1.4 单点 Master
都说单点不好，怎么还爱用单点 Master 呢？因为实在太能简化设计了。如果有全局信息的话，可以很方便的实现复杂的全局控制策略。但是缺点当然也是很明显的，最主要的就是，Master 挂了怎么办，Master 对外带宽过小怎么办。
对于前者，可以通过多种方式来做 backup。在 MapReduce paper解读中分析过几种：snapshot+log，主从，状态外存，心跳恢复。GFS 应该1，3，4都用到了。
对于后者，就是尽量减小 Client 端与 Master 的请求交互与数据传输。GFS 的主要做法：
- Client 不与 Master 发生实际文件数据交互，只请求元信息，比如 Primary 数据块的位置信息，然后就去找相应 Chunkserver。
- Client 端会做有限时间内的元信息的缓存，这样对于同客户端的一系列连续请求，对于元信息的请求次数也会降到最低。
下面来详细说下读取（filename+offset）流程：
- Client 将文件内 offset 翻译为 chunk id + chunk 内 offset。
- Client 与 Master 交互，通过 filename + chunk id + chunk inner offset 获取该 chunk 所有 replica 的位置。Client 会缓存此信息到 filename+chunk id -> replica locations 的字典中。
- Client 于是就近选一个（当然失败了会尝试下一个）replica， 给其发送请求，带上 chunk handle + byte range，读取数据。
由于上述缓存存在，只要其不过期，后面同一 chunk 的访问就不必再经过 Master。而且这还可以再继续优化，比如 Client 一个请求中同时请求多个 chunk 位置；比如 Master 返回的时候不仅返回该 chunk 的各个 replica 位置，还返回在同一文件中请求的 chunk 后面几个 chunk 的各 replica 位置。这些都能有效减小 Master 的负载。
1.5 块尺寸（Chunk Size）
chunk 大小选择是个核心设计点。选择了当时看来比较大的尺寸 64MB 作为 chunk 的固定大小，每个块物理上是一个 linux 系统下的文件。这么做好处有三：
- 减小 Client 与 Master 的交互次数：Client 向 Master 请求信息，是以 chunk 为单位的，因此在请求数据量一定的情况下，单个 chunk 越大，请求次数就越少。
- 减少单个请求的跨 chunk 读取：这也好理解，单个 chunk 越大，同一个请求的 byte range 落到单个 chunk 中的概率就越大。
- 减少总 chunk 的原信息尺寸：存总大小一定的数据，单个块越大，所需块的数量就越少。而单个块的元信息是相对固定的，因此元信息总量就会变小。在 Master 的内存不变的情况下，就能存下更多的元信息，从而使整个系统的容量上限提高。
任何设计都是取舍，选择大块既然有以上好处，就会随之带来以下坏处：
- 内部碎片。比如需要存储大量小文件，这些小文件的单个文件尺寸小于一个 chunk 大小，但在 GFS 也至少得占一个 chunk，由此带来大量内部碎片。当然每个文件的最后一个 chunk 大概率也会存在一些碎片。
- 小文件热点。如果系统中有大量小文件，并且被分配到一个 Chunkserver 上的话，那么该 Chunkserver 就可能会成为热点（因为每个 Chunkserver 可以存的 chunk 一定的话，单个文件占 chunk 越少，那么其 serve 的文件数就会越多），一般不会有问题。如果真碰到这种问题，可以通过提高小文件 replica 个数来临时解决（那么就可以有更多的备胎来分散请求了）。其他可能的办法，谷歌开始开脑洞了：用类似于 p2p 的方式解决，即一个 Client 可以从其他 Client 上读数据。
不过对于 GFS 来说，小文件不是主要目标流量。
1.6 元数据
主要包括几大集合和映射，都存在 Master 的内存中。因此 Master 内存和单位尺寸的数据对应的元信息大小决定了系统的容量。
1. file list 和 logic chunk list 2. file name -> chunks(identify by id) 3. chunk id -> chunk replica location
这里 GFS 学了数据库的惯常操作，将对前两个数据结构的任何改动都存在了操作日志里，以便在必要的时候进行恢复。至于最后一个映射，它采用了另外一种策略：每次 Master 恢复时，通过各个 Chunkserver 的心跳来构建和维持该映射。为什么会有这个不同呢，卖个关子，下面讲。
基于内存的优劣(In-Memory Data Structures)
将所有元信息存放在 Master 内存中，有诸多好处：
- 最直接的就是简单。很多时候简单就是强大：意味着好维护，好扩展，性能好等等。
- Master 能很方便获取全局信息，从而用来：回收孤儿 chunk 以释放空间，重新备份 chunk 以应对故障，不断迁移 chunk 以平衡负载。
- 当内存成为瓶颈时，加内存就好了。
坏处就是 Master 内存确实可能成为瓶颈和单点。单点这里不细说。关于容量瓶颈问题，首先当时 GFS 的面对的存储量级还没现在这么大；其次每 64M 文件块可以压缩到只有平均 64 bit 元信息。最后，大多数文件假设都是占好多块的。总体来说，就是尽量压缩单位数据所对应的元信息，从而在 Master 内存受限的情况下最大化系统容量。这个上面好像说了，没办法，谷歌的论文就是重复再重复，毕竟，对于写文章来说，呼应就是美嘛。
块位置(Chunk Locations)
一开始 GFS 也是打算在 Master 上持久化 chunk 的各个副本位置的信息。后来发现，每次被动的从各个 Chunkserver 中收集更简单直接。因为每个 Chunkserver 天然的知道自己一亩三分地的 chunk replica 的信息，每次由他们汇报给 Master 能保持信息最一致。假设这个信息持久化在 Master 中，Master 宕机后恢复时从本地恢复这个信息到内存，但是在这个空当内，好多 Chunkserver 挂了，好多 Chunkserver 又加入了集群，这样信息就不一致了，还得通过心跳来同步达到一致，那么干嘛不一开始就通过心跳来构建呢？
我思考了下，以为这么设计 chunk id -> chunk replica location 的持久化方案的核心点在于，它不像 filename，file -> chunk 这两个映射，在 Master 宕机的情况下，是无法更新的；而由于大规模集群的中单个 Chunkserver 的不靠谱性以及各种运维操作的不确定性，是不断变化着的。这是分布式集群的一个固有特点，因此这个设计可以说是会心一击。
操作日志(Operation Log)
操作日志，用来持久化 file namespace 和 file name -> chunk 的映射，有两方面的作用：
- 如前所述，用以持久化上述元信息，并且在 Master 宕机恢复后进行元信息重建。
- 对于并发操作，用来确定操作顺序，相当于一个''锁''的概念。
因此，对于 GFS中文件，文件块以及版本号的信息，都可以唯一的由他们写入操作日志的顺序所决定。
操作日志如此重要，因此我们不能只在 Master 硬盘上对其进行备份，万一 Master 整个完蛋了呢？还要将其同步至其他远程机器。之前也提到了，这个日志有点类似于 WAL （Write Ahead Log），所有修改操作必须先要写入操作日志之后，才能应用到 Master 的内存数据结构中，进而暴露给 Client。否则，宕机恢复时，Client 和 Master 拿到的信息的往往不一致。(当然为了避免频繁刷盘影响正常请求性能，可以将一些操作 batch 后再刷盘，但是也这会带来不一致问题，因此这些考虑需要根据实际业务场景进行灵活调整)
有操作日志的地方就有 checkpoint。因为一个大型系统面对的请求实在太多，如果每次 Master 恢复时，就从最开始读操作日志进行恢复，这个过程将会相当漫长。为了压缩操作日志，很自然的想法便是定期 checkpoint，将某个时间节点之前的日志所对应的状态机或者内存数据结构以某种方式持久化下来。GFS 选的是 B 树，因为它可以对应加载到内存中，而不用做一些转化（比如说 通过kv 对构建字典），从而进一步加速恢复时间。
做 snapshot 时，GFS 用了一个小技巧，来避免和当前对操作日志的写入冲突（毕竟同时修改一个文件得加锁）。就是每次到了做 checkpoint 的时间，就将操作日志切到一个新文件中。然后新启动一个线程，在后台将老文件转化为 checkpoint。
虽然做完最新的 checkpoint 之后老的 snapshot 就可以释放了。但是小心驶得万年船，GFS 在实践中往往会多保留几个 checkpoint。
1.7 一致性模型
这一块是我最初读论文的时候觉得比较难理解的地方，但是后来想通了发现很巧妙——在系统满足应用需求的情况下，适当放宽一致性的限制，会大大简化实现。
在详细展开 GFS 的设计之前呢，必须先要搞清楚一个问题，是什么引发了一致性问题？如果这个问题不清楚，那么下面所讲 GFS 的一大堆设计，你可能根本不知道它在干嘛，这也是当初我读不懂这一块的原因。答案是多副本（replica），凡是有多副本的系统，必然需要面对一致性问题。因为网络的不靠谱性，Client 的不靠谱性，Chunkserver 的不靠谱性，总而言之，就是分布式系统各个节点，以及各个节点间的通信都不靠谱。而将一份内容同步到多个副本是需要时间的（因此该操作不是原子的，可能会使系统停在一种蛋疼的中间状态），在这个时间段内，任何一个部件（Client，Chunkserver以及网络）出现问题，就会造成不同副本的不一致，后面的 Client 在读的时候面对不一致的 replica 就会发愁了，以谁为准呢？
GFS 的承诺
GFS 觉得，不用提供完全的 POSIX 文件系统的语义，只需要以下几个基本承诺，在所面对的场景下，就够用了：
- 文件命名空间的改动（如文件创建操作）是原子的
对于第一点，最简单的实现就是在 Master 中文件命名空间的数据结构外加一把大锁，所有操作都是互斥的，也就是对他的任何改动是原子的，通过操作日志能将所有的操作确定一个顺序。但是锁的粒度太大必然影响性能，因此在文件目录树中，其实每个节点都会有锁，具体加锁过程，稍后会详述。
- 修改后的文件块的状态取决于修改类型，修改成功或者失败，是否为并发改动。
如上图，文件块的状态有三种，一致性级别由高到底：已定义（defined），未定义（undefined）但是一致的（consistent），不一致的。理解这几个级别需要一些背景，论文中不同的地方提到了，这里重新组织一下：
- 修改操作。包括写操作和追加操作，写操作需要指定文件块+offset。追加操作成功后系统会将追加成功的偏移量返回给客户端。
- 并发写。如果两个客户端同时写同一个文件块的同一偏移量，那么就有先后顺序问题，如果接近同时，系统不保证并发顺序。那么其中客户端再去读，就不一定能读到自己刚写的数据。
- 追加失败。追加操作会保证至少成功一次。追加操作时，假设配置三副本，但是只有两个副本写成功，最后一个副本超时了（可能对应块服务器宕机，当然重启后 GFS 会用 chunk version 来标记其过期 stale 了，从而跳过该 offset。），那么追加操作会重试，并且失败数据不会删除，但是 GFS 有对齐操作，即重试成功后，三个副本中该追加数据的起始偏移量是定义的（也就是一致的），那么其中那个上次失败的副本就会有个空洞，系统会用特殊字符填充。
明白了这些背景，先说一个结论，定义未定义针对的是多客户端并发写同一个偏移量的覆盖顺序问题；一致不一致针对的是多个副本相同偏移量的内容是否相同。再来详细解释这几个名词：
- 已定义（defined）：客户端写某个偏移量后，再读该偏移量的数据，读到的一定是刚才自己所写。
- 未定义的但是一致的（undefined but consistent）：多个客户端并发写同一个偏移量，不确定谁会覆盖谁（这个顺序由 Primary Replica 所在 Chunkserver 来安排，后面将会讲），即写完后再读，不确定是自己写的还是其他人写的。但是保证最终一致性，即并发写完成后，最后几个副本是一致的。
- 不一致的（inconsistent）：即修改操作后，所有副本同一偏移量的数据并不完全相同。
此外值得一提的是，由于客户端会缓存文件块位置，它可能会读到旧的信息。当然，缓存过期事件以及文件重新打开都会刷新缓存信息，但是在文件元信息更新后到缓存信息刷新前，有时候会存在一个窗口，在这个窗口内，客户端会拿到过期的缓存信息。但由于GFS大部分场景是追加的，因此一般不会拿到过期数据。
对用户代码的影响
通过使用其他技术手段：依赖追加而非随机写，检查点技术以及可以自校验、自定位的 Record 写（就是在应用层或者库中做校验和打ID），可以放心使用上面所放宽的一致性模型。下面对这几个技术详细解释一下。
- 追加写和检查点
GFS 事实上面对的场景是追加写远多于随机写的，那么在几乎只有追加写的场景下，保持一致性的策略就简单的多了。一个典型的场景，就是一个 writer 从头写到结尾，利用两个小手段可以保证一致性：a. 写完后重命名；b. 定期做检查点。前者可以保证写文件的原子性，要么完全可见，要么完全不可见。后者来说，每个检查点其实就是已定义的，自然是一致的，reader 可以放心的读到最后一个检查点。哪怕 writer 故障重启后，也可以从上一个检查点开始增量写。在此过程中，reader 不会读到不一致的数据。
- 自校验和自定位
另一个经典的场景是多 writer 并发追加以合并分片结果或者充当生产消费队列。之前也提到，对于追加写，GFS 提供至少成功一次的语义保证。由于记录写失败了会重试，但是并不会删除，那么就必然存在一些失败记录（表现为一些 replica 上的失败记录和另一些 replica 上的 padding）。
GFS 的策略是在 Reader 端对这些错误记录进行处理，读入 block 以及对应校验和在内存中作比对，如果不一致就跳过。对于写重的记录，writer 提供了 record id，reader 可以在读取的时候根据其进行过滤。
当然，上述逻辑的代码都内置在了库函数中，应用层代码可以很方便的调用。
2 系统交互
所有读写流程设计有个大方向，就是尽量减少主节点(Master)的参与，因为主节点很容易变成单点瓶颈。基于此，接下来详细描述一下客户端、主节点、块服务器是如何交互来完成数据的变动、原子的记录追加以及快照操作的。
2.1 租约和修改顺序
分布式系统上的文件修改包括元信息的修改和文件块的写入和追加操作。文件块的修改操作会作用于其所有副本上，不同副本的写入顺序需要是确定的，而前面所说，必须减少主节点的参与，所以由主节点来安排这个顺序是不合适的。因此 GFS 使用了租约(lease)的手段，Master 会定期向 chunk 的某个 replica 所在的服务器进行授权（有超时时间，所以称为租约），拿到授权的副本称为主副本（primary replica），由其进行写入顺序的安排。这样就将主节点的权力用类似于尚方宝剑的形式在某一段时间内代理给了其选定的副本所在的服务器，当然，有两个限制：
- 权力范围。只针对该 Chunk。
- 租约时间。有超时时间（初始为60s），需要定期续约。一般只要其不死，Master 都会同意其续约请求。不过偶尔 Master 也有为了防止某些 Chunk 被修改主动收回租约的时候，比如要做快照的时候。
租约这种方式的确减少了客户端与 Master 节点的交互，但是它很依赖多个节点的时钟同步。举个例子，假设每个租约会带上其失效的时间戳，此时间戳在 Master 上产生，在主备份节点上被测试，如果主备份节点时钟慢，那么它续约之前 Master 可能就认为该租约超时了，从而将租约授权给另一个备份节点。这时就同时存在了两个备份节点，从而带来一些问题。
下面来对照流程图来分步骤详细说一下写流程：
- 客户端向 Master 询问要写的 Chunk 的主副本和其他副本的位置。如果还没有主副本，那么 Master 就通过租约授权一个。
- Master 会给客户端这些位置信息，客户端会将其缓存起来。并且除非主副本不可达或者其租约到期，客户端不会再向 Master 发送请求。
- 客户端将要写的数据推送给各个副本所在的服务器。这里需要注意的一个设计是，GFS 将数据流和控制流进行了解耦，即客户端可以以任何顺序进行数据推送而不用像控制流一样先到主备份再到从备份。这样可以使我们独立优化数据流的推送，甚至可以并行推送；对于大数据块写入是很有好处的，下面章节会详细讨论这个事情。每个 Chunkserver 收到数据后不立即落盘，而是使用 LRU 策略放在缓存里，这也是一个将网络IO和硬盘IO进行解耦的一个操作，一是为了提高效率，一是等待主备份安排写入顺序。
- 当客户端被告知所有副本的数据推送完成后，会向主备份服务器发送写（落盘）请求。主备份所在服务器会把多个并发客户端（如果有的话）的写请求安排一个写入顺序（给每个写请求指定一个序列号），并将其写入前面所说的操作日志。
- 主备份所在服务器将客户端的写请求以及序列号转给其他副本所在服务器。有了这个唯一对应的序列号，所有副本的落盘顺序就能保持一致。
- 所有从备份服务器落完盘后给主备份所在服务器复命。
- 主备份所在服务器回复客户端，如果任何副本写入出现了问题，都会报告给客户端。如果遇到问题，可能有两种：a. 所有副本数据均未落盘。b.部分副本数据落盘成功。对于后者就会出现不一致的状态。客户端的库代码（意味着不用应用代码进行处理）检测到错误后会进行重试，因此在真正成功写入之前，步骤 3~7 可能会重复多次。
这里需要一提的是一种特殊情况，如果要写入的数据过大，超过一个设计的 Chunk 大小怎么办？答案是将其拆开分成多次写。每次写的流程和上面一样，因此所有副本的数据顺序肯定会保持一致。但是如果同时有其他客户端也在进行写入的话，那么该次写请求的数据可能会被间隔开，由此造成前面所说的一致但是未定义的状态（consistent but undefined）。
2.2 数据流
GFS 将控制流和数据流解耦以充分利用网络带宽。控制流都是从主备份节点到从备份节点，但是数据流就可以根据实际情况来动态调整。主要目标就是最大化利用网络带宽，避免网络瓶颈，最小化数据传输延迟。
GFS 的主要手段有：
- 利用网络拓扑来组织传输顺序
- 线性的、流水式的传输数据
对于第一点，GFS 利用 IP 组织来反应网络拓扑——即根据 IP 的关系可以判断出其节点的网络上的远近关系。
对于第二点，如果是树形传输可能会造成根节点负载过重，不能均摊负载和网络带宽。但如果只是单纯线性同步而不做流水并行的话，效率又会很低。
2.3 记录追加
GFS 提供一种原子性的追加操作，叫做记录追加（Record Append）。不同于普通的写入操作，需要指定偏移量和数据，记录追加操作只需要指定数据，在写成功后，写成功的记录偏移量将会返回给客户端。如果多个客户端并发写同一个区域，大概率会造成数据的交叠：即重叠区域的数据部分来自客户端A，另外部分来自客户端B，从而造成不一致的现象。但是对于记录追加操作，系统会通过以下手段来保证写入的数据的原子性（即单个记录内容只来自一个客户端）和可靠性：
- 如果遇到多客户端并发，由系统统一安排追加顺序，并且单个记录追加时不会被中断。
- 如果由于节点或者网络故障导致追加失败，会对记录进行重试，即保证至少写成功一次。
这个设定有点像 Linux 文件系统中，多个线程使用 O_APPEND 标志进行文件追加操作。设置此标志位后，Linux 的系统调用保证移动到文件末尾并且进行数据追加是一个原子调用。而对于记录追加操作，GFS 也提供了类似的原子性保证。只不过 Linux 是针对多进程，而 GFS是针对可能跨节点的多个客户端。
GFS 的分布在多台机器上的多个客户端并发写一个文件的应用很依赖此操作。如果 GFS 只支持传统的写入操作，那此类应用就必须要自己进行互斥写以保证数据不产生交叠。比如分布式锁，但是代码复杂度就上去了，而性能也大概率会下来。在 GFS 所面对的场景中，就常利用这个记录原子追加的特性，拿 GFS 上的文件当多生产者单消费者的队列用，或者充当多个客户端对结果进行合并的媒介（比如 MR 的多个 Paritition Reduce 后的结果归并）。
具体到实现上，只需要在上面图2提到的数据流中稍作改动即可。在数据被推送到各个备份节点之后，客户端会向主备份节点发送落盘请求。主备份节点首先会检查写入数据之后，当前块是否会超过规定块尺寸（64M）。如果超过，则并不落盘，而将当前块剩余空间打满padding（比如说填入特殊字符）；然后提醒客户端在下一个块进行重试（这可能是因为客户端在追加写的时候需要提供 chunk id + data，因此需要客户端进行 chunk id 增加，并重试。而非系统直接在下一个块重试后将 offset 返回，可能因为返回值没有 chunk id 吧。我觉得稍微改下接口以使系统自动重试可能会更好一些，因为同步到各个节点的数据可以被直接复用，并且减少一次与 Client 的交互）。因此追加写对记录的最大大小是有要求的，不能超过块大小的四分之一，这样每次追加写的时候每个块浪费最多不超过四分之一。
如果记录在任何一个备份节点上写入失败，客户端都会对该追加操作进行重试。由此可能会造成某个备份中存在超过一份的该记录数据。如前面一致性一些所说，GFS 不严格保证所有备份间数据逐字节一致，它仅保证记录作为一个整体被原子的成功的写入一次，并且各个备份的这份成功数据的所有偏移量保持一致。由此，才能仅返回一个偏移量给客户端，并且下一个操作可以从同一个偏移量进行下一次写。
根据前面所定义的一致性模型，对于记录追加操作来说，成功写入的请求是已定义的，因此也是一致的。而不成功写入的请求，是不一致的，即未定义的。至于应用在读取时如何处理这些失败的写入部分，之前讨论过，这里不再详述。
2.3 快照操作
快照操作可以很快的对单个文件或者文件目录树做一个拷贝，注意此接口是会暴露给用户的，而不是像有些系统只是用来自己做备份的。用户在对数据做处理前通常利用快照操作将数据备份。
实现上，和 AFS 一样，用的写时复制（copy-on-write）的技术。当要执行快照操作时，Master 会召回所有待拷贝的文件所包含的块的租约，暂时冻结这些文件的写入操作，以进行复制。复制时只是对这些文件的元信息进行拷贝，拷贝后的元信息逻辑上变成新文件， 但是其数据仍然指向原文件。
当进行快照操作后，客户端想对做了快照的文件进行写入时，首先会向 Master 询问租约持有者，Master 注意到该块的引用数超过1，于是 Master 先不急进行租约授权，而是通知该数据块 C 及其副本所在的服务器对其各个副本在本地进行数据块复制，产生新数据块 C'。Master 然后修改文件的引用为新数据块，并对其中一个副本进行租约授权，然后将被授权副本返回给客户端。
如此一来，Client 就可以在无感知的情况下以为写了一个新文件。并且所有的写时复制都发生在本地，以加快复制速度，减小网络开销。
3 主节点操作（Master Operation）
Master 负责所有的文件命名空间的操作。此外，还负责管理全系统范围内的数据块各备份的相关操作。包括：
- 副本放置决策
- 数据块的创建
- 各副本的同步
- 块服务器间的负载均衡
- 回收无用的资源
下面将对上述内容逐一讨论。
3.1 命名空间的管理和上锁
Master 上的有些操作，比如快照操作是很耗时的，因为它需要收回所有相关块的租约。但是 GFS 不想让这些耗时操作中断其他操作，但同时又要保证操作间互不影响。于是就只能有一种解决方法——分区域加锁。当多个操作作用于不同文件区域时，可以并行；当作用于同一文件区域时，需要通过锁来保持互斥。
不同于传统文件系统，GFS 没有专门针对每个目录的数据结构（比如 inode）以列出该目录下的所有文件。GFS 也没有对文件或者目录取别名的操作（对应 Unix-like 文件系统的硬链接和符号链接）。GFS 使用一个查找表来保存文件路径到其元信息的映射，并且使用前缀压缩（prefix compression）的技术来优化存储（这么看来有可能使用了压缩过的前缀树作为数据结构？）。
命名空间树中的有效节点，要么是一个文件路径，要么是一个文件目录路径，GFS 为每个节点都配了一把读写锁，以此作为命名空间互斥操作的数据结构基础。具体来说，每当涉及到命名空间改动（重命名，文件增删等）的操作时，都要顺着文件路径每个节点从前到后依次获取锁。举个例子，针对路径 /d1/d2/…/dn/leaf，Master 会依次获取 /d1，/d1/d2，…， /d1/d2/../dn 的读锁，然后依据操作类型获取 /d1/d2/…/dn/leaf 的读锁或者写锁。当然，leaf 可能是个文件，也可能是个文件目录。
使用此种获取锁的策略可以保证，当 /home/user 被做快照到 /save/user 时，/home/user/foo 不能够同时被创建。根据上面的策略描述，GFS 在做快照时，会分别获取 /home 和 /save 的读锁以及 /home/user 和 /save/user 的写锁。而在创建 /home/user/foo 时，会需要获取 /home， /home/user 的读锁以及 /home/user/foo 的写锁。因此这两个操作一定是互斥的，因为他们同时只能有一个操作获取 /home/user 的锁。
一个问题是，对于路径上的"父级"节点，只需要获取读锁就够了。因为 GFS 是没有真正的文件系统层级组织或者 inode-like 的概念的。因此只需要获取读锁避免"父级"节点被删除就够了，而不需要像传统文件系统一样获取 inode 的写锁，互斥地更改其元信息。这样做有另一个好处，就是多个客户端可以并发的往一个文件目录写多个文件，因为每个客户端只需要获取目录的读锁，从而避免目录被删除、重命名或者做快照等修改操作，就够了。而对于同一个文件，需要获取写锁，从而将多个客户端的对同一个文件的修改请求序列化（指安排一个特定顺序，而非数据结构序列化反序列化中的序列化）。
另一个很自然的疑问是，每个操作都获取这么多锁，会不会造成死锁？答案是不会，因为针对相同的文件区域（例如同一个文件路径），每个操作获取锁的顺序是一样的（按照文件路径的来说，不同层是从上到下，同一层是按照字母序）。因此针对同一块资源，不会发生占有并等待的情况，不满足死锁的条件。由于每个操作都要获取很多锁，GFS 又想保证尽可能的高吞吐高并发，因此需要及时的释放不用的锁以避免不必要的等待。
3.2 副本放置（Replica Placement）
GFS 面对的物理环境是多层次的：单个 GFS 集群可能分布于多个数据中心的多个机架上的上千台机器，这样就有 数据中心 -> 机架 -> 物理机 三个层次。但一般一个 GFS 集群会局限在一个数据中心中，这样也有两层。这样不同块服务器的通信可能会跨越机架，通过交换机。而机架内网络带宽一般会大于机架间网络带宽。这种多层次的网络拓扑为 GFS 保持可扩展性（scalability），可靠性（reliability）和可用性（availability）提出了很大挑战，当然，这也是任何分布式系统设计所面临的问题。
基于此，GFS 中的副本放置策略有两大目标：
- 最大化大数据的可靠性和可用性。
- 最大化网络带宽的利用。
为了满足第一点，我们不能把鸡蛋放一个篮子里，即同一个集群的 Chunkserver 不能只放一个机架内，以容忍整个机架故障。同时意味着需要有大量的跨机架的读写请求，一方面可以充分利用网络带宽，但是跨机架间的读写请求又会存在一些性能问题，总之都是权衡（tradeoff）。
3.3 副本创建（creation），副本补齐（re-replication）和副本平衡（rebalancing）、
数据块被创建，有三种情况：数据块初始创建时，副本补齐时与跨节点再平衡时。
首先，当 Master 在给一个新创建的数据块副本选择位置时，会考虑以下几个因素：
- 节点的硬盘利用率。以使得数据分布均衡。
- 节点最近备份的数量。GFS 所面对场景大多是一次写后紧跟多次读，为了均衡负载，需要将最近写入尽量分散到多个节点。
- 多副本的多机架分散。
其次，当某个数据块的实际存活副本数量小于系统设定值时，就会启动备份补齐流程。造成备份补齐的原因有很多，比如说某些机器宕机，某些硬盘故障，某些数据块设定值增大等等。GFS 中数据块一般都会很多，因此同一时刻可能有很多数据块需要进行再备份，因此我们必须给所有再备份请求安排一个优先级。在安排先后次序时，我们有这么几个要考虑的点：
- 存活数与设定值的差值。副本数差的越多，优先级就越高，这不难理解，毕竟差的越多，该数据块不可恢复的危险就越大。
- 文件的活跃状态。举两个极端例子，如果最近文件很活跃，比如说在创建中，那么就优先对该文件所含文件块进行副本补齐。如果文件刚被删除，那么明显地，我们就不在需要对其进行操作。
- 是否阻塞当前客户端操作。如果因为某数据块副本数不足导致某个客户端等待，那么就优先处理此数据块的补齐请求。
在对所有副本补齐请求按照上述三个影响因子加权排序后，Master 渐次选择权重最高的请求，指示某个块服务器进行副本的复制，复制后放置策略跟初次创建时放置策略大体相同。为了不影响客户端的正常请求，GFS 会在集群总范围和单个块服务器范围内都限制副本复制的进程数。同时，在也在带宽层面对副本补齐的总带宽进行了限制。
最后，Master 会周期性的进行系统范围内的副本挪动以充分利用硬盘空间并进行负载均衡。同时，这种周期性操作也会将一个新加入集群的节点慢慢的填满，而不是直接将所有的写请求打过去以迅速填满该节点。后者很容易造成请求震荡以及系统复杂度的提升。在删除副本时，倾向于对硬盘剩余空间少于平均水平的节点下手；而增加副本时，策略和创建时大抵相同。
3.4 垃圾回收
当 GFS 上的文件被删除后，GFS 不会立即回收相应的物理存储。而是通过周期性的垃圾回收程序在文件层面和数据块层面对这些不用的存储做回收。将删除和回收解耦会使得系统变的简单和健壮。至于为什么，下面一一道来。
基本机制
和其他操作一样，当 GFS 的用户删除一个文件时，Master 会立即在操作日志上记下一笔。不同的是，GFS 并不会真的立即删除文件并且回收相应资源，而是将该文件重命名为一个隐藏文件，并且带上删除操作的时间戳。GFS 文件系统命名空间有周期性的检查操作，当某个隐藏文件存在超过三天（这是一个运维人员可配置项）时，会将其元信息进行删除，注意，此时该文件对应的数据还在块服务器的的，只不过我们没法找到它们了。
与 Master 上的命名空间（文件路径到逻辑块）周期性检查一样，Master 也会对所有的数据块（逻辑块到物理副本）进行检查，当发现某些逻辑块不能通过任何文件访问时（结合前面 Snapshot 操作可以猜想，逻辑块中应该都维护了文件的引用计数，因此只要引用计数减到0 就说明该逻辑块已经没有文件引用，变成了孤儿块），就会删除该该逻辑块的信息。注意，此时仍不会同步的去删除块服务器上的数据。
每个块服务器会周期性的上报其所持有的数据块物理副本的信息，Master 收到这些信息后，会去上面提到的数据块到物理副本的集合中逐一查找对应信息，并在心跳 RPC 的回应中将这些信息带回。块服务器拿到本机上所有孤儿物理副本的信息后，才会真正的将这些副本删除（不晓得这一步是不是同步的，大概率不是）。
额外探讨
虽然对于编程语言来说，垃圾回收是一个复杂的话题。但在 GFS 的设定下，垃圾数据块的定位相当简单，它的追踪主要依据之前提到的两个数据结构。一个是文件路径到逻辑块的映射，所有不在该映射中被引用的数据块都是无用数据块。另一个是逻辑块到物理副本（以Linux 文件形式存储）的映射，它们由各个块服务器心跳汇报来构建，所有存在块服务器上，但是不为 Master 所知（即其对应的逻辑数据块不在第一个映射中了），都可以被认为是垃圾。
相比于同步相应删除操作，异步的垃圾回收有诸多好处：
- 在各种出错的大型集群中，垃圾回收更简单可靠。不可靠的环境下，创建可能会出错，删除可能会出错，更改可能也会出错，因此这些操作都可能会留下垃圾。对于同步删除来说，如果出错还要记下出错数据，不断进行重试。而垃圾回收能够提供一种统一回收上述出错遗留的垃圾的方法。如果使用同步删除的方法，要处理其他出错留下的垃圾还得产生很多冗余相似代码。
- 垃圾回收将分散的删除操作改为定期集中清理。批量回收，效率可能更好一些。而且因为所有的垃圾回收操作被集中到了 Master 的周期性检查上，因此就可以对具体的操作时机做出选择，以避开用户正常请求的高峰期。
- 异步、惰性的垃圾回收还能应对误删操作。
凡事利弊相随，异步惰性垃圾回收策略在我们真想立即删除某些数据的时候就很捉急了。此外，如果有大量的临时小文件产生，会很影响集群利用率。为了解决这些问题，可以做以下优化：
- 被删除的文件变成隐藏文件后，如果再被显式的删除，我们就会加快其的删除步伐。
- 按文件命名空间分而治之。比如用户可以指定某些目录下的文件不进行多备份；又可以规定另外一些文件目录下的文件删除后就会真正立即删除。
当然，这样都会带来额外的逻辑和实现复杂度，如何在不可靠环境中优雅的实现、如何和现有的代码逻辑相洽，那就是另外的，干起来不那么美好的事情了。
3.5 过期副本检测（Stale Replica Detection）
当数据块服务器宕机恢复时，其存储的一些数据块可能在此间进行了更改操作，这就导致该服务器上存储的对应数据块的副本过期。为了解决这一问题，GFS 引入了针对逻辑块的版本，以此来甄别同一数据块的不同副本是否过期。
具体做法为，每次 Master 对数据块进行租约授权时，都会增加版本号并通知所有副本进行更新，Master 和所有副本都会持久化最新版本号。然后 Master 将持有租约的副本以及更新后的版本号发送给客户端。客户端在读写数据的时，会根据最新版本号逐一检查所有副本是否为最新副本，所有过期副本会被当做不存在，上文提到的垃圾回收程序会周期性的将其清除。
4 容错和诊断
GFS 设计和构建的一大挑战就是单个组件不可靠而组件数量又特别多。我们既不能完全信任机器，也不能完全信任硬盘，组件故障会导致系统故障，甚至数据损坏。接下来讲一讲 GFS 在这方面遇到的问题以及应对之道。
4.1 高可用
对于数百台机器组成的集群，任何给定时刻都可能出现组件故障。为了应对这些问题，GFS 使用了两条看来简单但是行之有效的策略：数据备份和快速恢复。
快速恢复（Fast Recovery）
GFS 系统中总共有三个角色：Master， Chunkserver 和 Client。前两者都设计为无论如何死掉都可以快速恢复其状态，最后一个在遭遇问题时会通过提供的系统库做一些重试策略。事实上，GFS 也不区分是人为关闭，意外退出还是偶尔超时，所有失败组件都会迅速重启，重试和重连（对于客户端来说）。
数据块备份（Chunk Replication）
如前所述，对于数据块我们默认进行三备份，但是应用侧可以按命名空间（比如说某个目录下）来对数据块副本数进行调整。GFS 系统中 Master 会控制保持数据块副本数满足要求，即当数据块副本数因为 Chunkserver 宕机、校验和出错，用户设置等等而小于设定数时，Master 会指定 Chunkserver 去增加副本。有时候，哪怕副本数满足容错需求，GFS 为了高并发等需求也会提高副本数量。此外，还探索了 EC 等方式进行跨机器冗余。当然，GFS 希望能够松耦合的实现这些额外的设计，毕竟 GFS 的流量是面对追加写和顺序读而不是随机写。
Master 冗余
Master 的状态会通过操作日志的形式在本机持久化并且同步到多台其他物理机。GFS 中的一个操作，只有在被提交到操作日志后才会被认为是应用到了文件系统中；不过为了不影响正常文件操作和后台工作，这些都是额外进程在做的，如果进程死掉，会很快被重启。如果 Master 硬盘或者系统故障而不能提供服务，GFS 外部的基础设施会及时检测到，在其他机器重启一个 Master，并通过操作日志副本进行状态恢复。那么客户端如何发现新的 Master 呢？GFS 用了主机名而非具体 IP 来让客户端连接 Master，因此只需要修改内部 DNS，将 Master 主机名指向新的机器 IP 就行。
此外，还可以使用影子 Master 来分流数据读取压力。影子 Master 会在延迟上稍微有些牺牲，通常在一秒左右。因此适用于应对那些不怎么发生改变的文件或者对稍微过期的数据不是很敏感的流量。所有决策（主要是各个副本的位置决策）依赖于真正的 Master，影子 Master 只做被动信息同步，即要么通过操作日志加载，要么通过和块服务器握手来获取。
4.2 数据完整性（Data Integrity）
块数据服务器使用校验和来发现损坏的数据块。考虑到一个 GFS 集群通常由横跨数百台机器的数千块硬盘组成，读写时遇到损坏的数据块很正常。GFS 会通过其他副本来恢复损坏副本，但是将不同副本逐字节校验来保证数据的正确性是不可行的，一来性能受不了，二来 GFS 并不保证多副本的数据逐字节一致（比如并行追加重试遗留的未完成数据块）。因此每个块服务器通过校验和来分别对自己所管辖的块进行校验。
每个数据块会以64KB 为一个小块（block），构造一个对应的的32bit 的校验和，作为元信息存在内存中，并且通过操作日持进行持久化。即，校验和与真正用户数据是分开存储的。
在读取前，主要包括客户端读取或者其他块服务器读取，块服务器会校验读取的数据范围所对应的所有小块的校验和。如果校验出现不一致，块服务器会返回错误，并且将其报告给 Master，因此数据块损坏并不会在块服务器间进行传播。收到报错后，请求者会去读取其它副本，Master 会指示选定块服务器对其进行拷贝，以维持有效副本数。新副本就位后，损坏副本会被当做垃圾进行回收。校验和对于读取的性能影响并不大，首先其所占的额外存储和计算开销并不大，其次校验和都存在内存中，其计算和验证不耗费额外IO，可以和数据流 IO 进行并行。
写请求包括常规写和并行追加写。后者是 GFS 的主要流量，GFS 针对其做校验和进行了高度优化。每次只需要不断对最后一个小块的校验和进行更新。但是对于指定偏移量覆盖写来说，在写入前必须先对要写范围对应的首尾小块做验证，因为他们可能是部分写，不经验证直接部分覆盖的话，可能会隐藏原来数据块已经损坏的事实。
最后，块服务器会周期性的对不活跃的数据块进行校验，检测到任何不一致，会像前面提的流程一样，向 Master 进行报告，重新备份该块，然后删除损坏块。
4.3 诊断工具
GFS 会保存额外的系统日志以进行问题定位，bug调试和性能分析，这样做会带来很小额外空间开销。但如果不保存这些日志，事后可能会很难理解机器间的一些系统行为，由于网络的复杂性和普通商用机的不稳定性，它们当时的情景可能很难复现。当然，如何记录合适的日志事件也需要一些经验和技巧。GFS 会对一些机器关键性（块服务器的上下线）的事件，所有的 RPC 请求和回应等等，在空间允许的情况下，GFS 会尽可能多的保留系统日志。
通过收集所有的 RPC 请求，可以重建 GFS 组件间系统交互的历史，以辅助定位问题。我们也可以通过对日志挖掘来对其负载分布进行追踪。再次强调一遍，记这些日志并不会对正常的客户端请求有太多影响，因为所有日志都是异步的、顺序地记录下来的，所有实时的状态信息都存在内存中并且以监控页面的形式呈现给用户。
5 名词释义
Master：主节点，GFS 集群中用于维护文件系统元信息和中心控制的中央节点，实际表现为 Master 节点上的一组进程。
Client：客户端，本文专指连接 GFS 集群进行文件操作的应用。
Chunkserver：块服务器，以普通 linux 文件存储数据块的数据节点（实际上是运行于节点上的进程）。
consistent but undefined：有时候指 chunk 的某个副本；有时候指 chunk 某个副本所在的服务器。
Operation Log：操作日志，用来进行错误恢复和确定并发写入顺序。
consistent but undefined：一致但是未定义，指多个客户端并发写入的时候，虽然最终副本的数据顺序一致，但是如果某个客户端再去读数据，并不知道能读到自己写的数据，还是被其他客户端覆盖写的数据。
Primay Replica：主副本/备份，或者主副本/备份所在节点。
Re-replication：翻译成了副本/备份补齐
6 参考
- GFS 论文：static.googleusercontent.com
- 铁头乔 GFS一致性总结： blog.csdn.net/qiaojiali
