1. 设计概要

1.1. 预期

可在廉价组件上运行（组件经常失效），系统能监测、冗余并恢复；
系统对大文件存储优化
读取支持：大规模流式读（上MB数据）、小规模随机读（几KB数据，可通过合并进行优化）
写入支持：大规模顺序追加写入，小规模随机写入
支持并行追加文件到同一文件，高效且定义明确
大批量数据处理要求高速，单一读写的响应时间要求较少

1.2. 接口

提供类似传统文件系统的API（不严格按照POSIX标准）

此外还提供快照（以很低成本创建文件/目录的拷贝）和追加操作（支持并行追加，且每次追加都是原子性的）。

1.3. 架构

一个GFS包含：

单一Master节点（逻辑上的，实际上可以有多台机器组成一个Master节点）：
- 存储的文件分割成固定大小的Chunk，它给每个Chunk分配不变且全局唯一的标识
- 管理所有文件系统的元数据（名字空间，访问全序，文件和Chunk映射，当前Chunk的位置）
- 管理系统范围内的活动（Chunk租用管理，孤儿Chunk回收，Chunk迁移）
- 周期心跳到每个Chunk节点，发送指令获取它们的状态
多台Chunk节点：
- 存储文件内容，内容分割成Chunk，Chunk大小固定
多个客户端
- 从Master只获取元数据
- 其它文件操作直接和Chunk节点交互

对于Chunk节点和客户端，没必要缓存文件数据，因为目标场景是以流的形式处理大文件，且Chunk节点底层是Linux文件系统，它做了缓存。

1.4. 单一Master节点

读取流程：

在客户端中，把文件名和偏移量转换成文件的Chunk索引（根据Chunk大小）
将文件名和Chunk索引发送给Master，获取到Chunk标识和副本位置信息（客户端将其缓存起来，键为文件名和Chunk索引）
客户端发送请求（包含Chunk标识和字节范围）到一个Chunk节点处（一般是最近的），Chunk节点执行后续读取操作

单一Master，要保证：

Master要全局定位Chunk位置，并进行复制决策
减少Master的读写（这一点可通过只从Master获取元数据解决）

1.5. Chunk尺寸

一般远大于文件系统的块大小，通常为64MB，且只有在需要时扩大。

优点：

减少客户端和Master的通信需求（因为Chunk个数少），尤其是针对大文件，轻松缓存大文件的Chunk元数据
客户端与Chunk节点可保持长时间TCP连接，减少网络负载
减少Master的元数据存储量（可允许元数据全部存储在内存）

缺点：

小文件同时多次访问时，某个Chunk可能成为热点，造成负载偏移

1.6. 元数据

Master存放三类元数据，都存放在内存中：

文件和Chunk的名字空间
文件和Chunk的映射关系
每个Chunk副本的存放地址

前两种还会以变更日志的形式记录，且日志会被复制到其它Master机器上

Master启动或新Chunk节点加入时，会轮询获取存储的Chunk信息。

Master后台也会周期扫描这些数据，定期轮询，可用于实现Chunk回收、Chunk节点失效的重新复制、Chunk迁移（实现负载均衡）以及磁盘使用统计等功能。

操作日志

前2个元数据会被记录到变更日志中，只有被记录到日志中时，变更才对客户端可见。

日志可用于恢复，需要日志变小：

让日志增长到一定量时，进行Checkpoint（将状态写入Checkpoint文件）

文件以压缩B-Tree存储，可直接映射到内存，查询时无需额外解析；

创建Checkpoint时，用独立线程切换新的日志文件和创建Checkpoint，不阻塞客户端的操作。
恢复时，读取最新Checkpoint文件（旧的可以删除），并重做之后的日志项即可

1.7. 一致性模型

1.7.1. GFS一致性保障

定义：

一致：所有客户端无论读哪个副本，读到的都一样
已定义：文件修改后，满足”一致“，且客户端能看到写入的全部内容

对于某些操作的的保证：

文件命名空间的修改（如文件创建）：原子性&正确性，由Master控制，命名空间锁提供保障
操作的全局顺序：由操作日志保证

写操作一致性：

	写	追加
串行成功	已定义	已定义但部分不一致
并行成功	一致（未定义，即看不到任何一次写入数据）	已定义但部分不一致
失败	不一致	不一致

追加的”已定义但部分不一致“：

偏移位置由GFS选择，偏移量会返回给客户端。

GFS可能会在文件范围（region，即修改涉及文件中的某个范围）中间填充数据或者重复记录（因为at-least-once），这些数据占据的文件范围是不一致的，但比例非常小。

一系列操作成功后，GFS要确保文件范围是已定义（包含最后一次写入），通过以下措施保证：

Chunk所有副本修改操作顺序一致（2.1）
利用Chunk版本号监测Chunk节点是否因为宕机而错过修改（3.5），导致副本失效（失效后不会修改，会被回收）

组件失效导致数据损坏/删除时：

Master定期轮询Chunk节点找到失效节点
利用校验和监测数据是否损坏（4.2）
若有问题则使用有效副本进行恢复（3.3）

1.7.2. 应用的实现

应用尽量追加写入（效率更高），并定期做checkpoint（恢复更容易）。

此外，可以通过写入checksum以实现有效性验证，并可通过附加唯一标识符去重（本身GFS保证写入”at-least-once“，但不是”exactly-once”）

2. 系统交互

2.1. 租约和变更顺序

GFS使用租约保持多个副本变更顺序的一致性：

Master节点给Chunk某个副本建立租约，此时该副本为主Chunk，它对所有更改进行序列的串行化（类似主从复制的架构，租约即选主）
- 租约初始为60s，若Chunk被修改了则可申请更长的租期；
- Master也可以取消租期（如取消文件修改操作）；
- 若Master与主Chunk失去联系，也可以在租期安全到期后与另一个Chunk建立租约。
这些内容会在心跳中捎带。
得到序列后，所有副本遵循这个序列进行修改

写入的过程：

客户端向Master询问哪个Chunk节点持有租约，若没有Master则选择一个Chunk建立租约）
Master将主Chunk标识符和其它副本位置返回给客户端，客户端将其缓存

只有主Chunk不可用/不再持有租约时，才会和Master重新联系
客户端将数据推送到所有副本上，可以以任何顺序推送，数据会缓存到Chunk节点的LRU缓存中（数据流会在2.2说明，它是链式发送的）
所有副本都确认接收到数据后，客户端发送写请求到主Chunk节点（标识了之前推送的所有数据），主Chunk为操作分配连续序列号，然后按顺序执行
主Chunk将写请求传递给其它副本，按顺序执行
所有其它副本回复主Chunk
主Chunk返回给客户端结果（若任意副本失败，则操作失败，客户端会重复执行）

若数据量很大，请求会被拆分

2.2. 数据流

控制流和数据流分开。

数据流以管道方式，沿着Chunk节点链推送（而非其它分散的拓扑），利于有效利于带宽。

Chunk节点会挑选一台没收到数据且距离最近的节点，作为链中下一个节点。距离可通过IP地址算出。

理想情况下，传送$B$字节到$R$个副本的时间为$B/T + RL$，$T$为网络吞吐量，$L$为两节点的延迟

2.3. 原子追加

客户端指定数据，GFS指定偏移量，原子追加且保证”at-least-once“，并将偏移量返回给客户端。

流程和2.1.中一样，但在主Chunk上有额外的逻辑（判断Chunk溢出）：

检查追加操作是否让当前Chunk溢出
若会，则先填充Chunk到最大尺寸，并通知其它副本也这么做
然后回复客户端，要求对下一个Chunk重新进行追加操作

同样，若请求失败，客户端要重新操作，因此不同副本上会有重复数据（因为只保证”at-least-once”），可能重复次数不同。

2.4. 快照

即一个瞬间可完成的对文件/目录的拷贝。它使用copy-on-write技术实现，快照会让对应的Chunk的引用计数增加（Chunk维护一个引用计数，默认1，快照时大于1，孤儿时为0）。

过程：

客户端向Master请求快照，Master首先取消所有Chunk租约（目标文件的）
Master将快照操作记录到日志
Master将日志记录的变化加载到内存中（复制目录元数据或复制源文件），新的快照文件指向源文件的Chunk地址

客户端写入：

客户端从Master获取当前租约持有者，
Master检查Chunk引用计数大于1（即存在快照），若是，则选择新的Chunk句柄，并要求其它副本对应创建新的Chunk句柄（本质就是copy-on-write）
Master确保某个新Chunk句柄获得租约，然后回复客户端，之后的写入和之前一样

source --> chunk(ref_cnt = 2) <-- snapshot 
====>
source/snapshot --> chunk(ref_cnt = 1)
snapshot/source --> new_copied_chunk(ref_cnt = 1)			

3. Master节点操作

Master功能：执行命名空间操作，管理Chunk副本（决定存储位置，创建Chunk，复制，迁移与负载均衡，垃圾回收）

3.1. 命名空间管理和锁

GFS没有针对实现ll命令的数据结构，也不支持链接，它逻辑上就是路径和元数据映射的查找表。

GFS目录是树形的，每个节点都拥有一个读写锁。

锁获取：假设操作/d1/d2/../dn/leaf，则需要获取/d1,/d1/d2,…,/d1/d2/../dn的读锁以及/d1/d2/../dn/leaf的读/写锁（取决于操作）

优点：可并行在同一目录下创建多个文件，只需对目录上读锁，对文件上写锁即可

锁获取需要将操作串行化，以防止死锁：

先按名称空间的层次排序
同一层次内按字典序

锁释放：不再使用时，立即释放锁

3.2. 副本的位置

目标：最大化数据可靠性和可用性，最大化网络带宽利用率。因此需要跨多机架保存Chunk副本（提升可用性）。

3.3. 创建，重新复制，重新平衡

3.3.1. Chunk创建

Master会考虑下面因素：

在平均磁盘使用率低的节点创建
限制每个Chunk节点最近一段时间内的创建次数
跨多个机架

3.3.2. 重新复制

当Chunk有效副本数量小于用户指定复制因子时，触发副本重新复制。

流程：

每个需要重新复制的Chunk会按照某些因素排出一个优先级（如缺失数量，如优先复制活跃文件的Chunk而不是刚删除的，又如提高可能阻塞客户端处理的Chunk优先级）。
Master选择优先级最高的Chunk，命令某台Chunk节点从一个可用副本中复制出来。新副本的位置选择和3.3.1.差不多。

防止复制流量过大：

Master限制集群和每个Chunk节点同时复制的操作数量
Chunk节点调节它对源Chunk（有效副本，copy from there）的读请求频率

3.3.3. 重新负载平衡

Master周期检查副本分布情况，然后移动副本，以实现更好的负载均衡和均衡的磁盘使用率。

新副本的位置选择和3.3.1.差不多，而旧副本通常位于剩余空间低于平均值的Chunk节点上。

3.4. GC

GFS删除为懒惰删除，实际数据的回收只会在周期的GC中进行。

3.4.1. 机制

删除文件时：

Master将删除操作记录到日志
Master把文件名修改为包含删除时间戳的隐藏文件名
Master会对文件系统的命名空间进行周期扫描，删除所有$X$天前的隐藏文件（仅元数据，切断与Chunk的连接而已）
Master会对Chunk名字空间周期扫描，若找到孤儿Chunk（不被任何文件包含），则删除它们的元数据
通过心跳捎带哪些孤儿Chunk被删除的信息，这样Chunk节点可以真正删除数据

3.4.2. 讨论

该机制的优势：

GC简单可靠，提供一致可靠的清除方法；
GC在后台运行，并合并在某些活动中（如扫描和例行心跳），开销会被分散，且不影响Master处理正常请求；
延缓空间回收，为意外、不可逆转的删除提供安全保证（有几率在该情况下恢复）

当空间紧缺时，可显式再删除一次已被删除的文件，以加速回收速度。

3.5. 过期失效的副本监测

副本失效场景：Chunk节点失效导致副本错过了一些修改操作

解决方法：为Chunk维护版本号以区分过期副本

签订新租约时，版本号增加，并通知其它最新的副本。版本号会被记录到持久化存储中；
Chunk节点向Master报告拥有Chunk集合时（如节点重启），可检测出过期的Chunk
Master若收到更高的版本号时，会认为目前的租约失败，因而选择更高的版本号

监测到过期后，在例行的GC过程中回收这些副本空间。

此外，Master回复客户端时，会捎带这个版本号，以供客户端/Chunk节点验证；另外Master返回客户端的信息中，认为过期的块是不存在的。

4. 容错和诊断

4.1. 高可用

使用2个策略保证高可用：快速恢复、复制。

4.1.1. 快速恢复

客户端/集群节点一旦请求超时，则会重新尝试连接到重启后的节点，任何重试请求。

4.1.2. Chunk复制

每个Chunk会被复制到不同的节点（通常不同机架上）。若某个副本损坏/Chunk离线，Master节点会克隆已有副本，保证每个Chunk被完整复制，见3.3.2.。

4.1.3. Master的复制

Master可由多台机器组成（分为主Master和备Master，真正处理客户端请求的进程只有1个），因此也要复制，将操作日志和checkpoint文件复制到多台机器（见此）。

Master操作提交成功的要求：日志写入到主节点磁盘和备节点。

Master切换：GFS配有外部监控进程，当Master进程所在机器硬件失效时（否则Master进程可直接重启），它会在其它存有完整操作日志的机器上重启一个新Master进程（重新选主），实现Master的切换。

影子Master：当主Master宕机时，启动以提供只读访问服务。

它的更新会稍落后于主Master，因为主Master挂掉时，可能写入到主，但没写入到备。

更新时，从一份当前正在进行的操作日志副本读取，并按照日志顺序操作。

此外它启动时也会轮询Chunk节点以获取Chunk位置信息，并定期与它们握手心跳以确定它们的状态。

当主Master的操作导致副本位置信息更新时，影子Master才会向主Master通信以维护最新状态。

4.2. 数据完整性

Chunk节点使用checksum检查数据完整性，checksum每个节点独立维护，而每个Chunk都会有一个checksum（保存在内存和日志中）。

当客户端读取时，Chunk节点会进行校验，若失败：

返回客户端错误
返回Master错误，通知其进行重新复制

checksum优化：

读：只取Chunk小部分额外相关数据进行校验，对齐在checksum块的边界上
追加：只对checksum进行增量更新
写：先读取和校验被覆盖的第一个和最后一个Chunk，写操作完成后再重新计算和写入checksum

Chunk节点也会在空闲时扫描损坏的Chunk，通知Master进行复制并删除原有的Chunk。

4.3. 诊断工具

GFS服务记录大量诊断日志，包括关键事件以及RPC请求和回复（不包含文件数据）。这些都可以删除。

诊断日志的生成是顺序且异步的，最近的事件会保存在内存中，这对性能影响很小。

论文阅读-GFS