分布式系统笔记 (3)-GFS
本系列文章是学习课程 6.824: Distributed Systems 时的一些学习笔记，整个课程的相关材料已整理至 DistributedSystemInGo。本文是 LEC3 的内容，介绍了分布式文件系统 GFS，GFS 为 MapReduce 提供了存储，同样是出自 Google，同样是年代久远，但是其中的一些设计思想同样值得我们参考。
设计理念
GFS 的设计理念也可以理解为其适用场景
- 整个分布式系统是由普通的商用机器构成的，因此故障会比较频繁
- 系统存储着数百万级的大文件，每个文件的大小基本都大于 100MB；小文件也存在，但是不是优化的目标
- 文件系统读操作主要有两种：large streaming read 和 small random read，且前者占主导；区别在于 large streaming read 是顺序访问，读取量大；small random read 则刚好相反
- 文件系统的写操作主要是对文件进行追加 (append) 操作，追加的数据是 large、 sequencial 的；且写入后文件就很少会被修改；同样的 small random write 也支持，但是不是优化的目标
- 系统需要支持多个 client 同时写一个文件
- 相比低延迟，更看重高吞吐量
系统结构
GFS 总体的系统结构如下图所示
整个系统包括一个 master 和若干个 chunkservers，master 存储着文件系统的 metadata，chunkservers 则存储着真正的文件内容，client 会先从 master 获取文件存储在哪一个的 chunkserver，然后从这个 chunkserver 直接读取。该过程有以下几点需要注意:
metadata
master 存储的 metadata 主要包括文件系统的 namespace、文件与 chunk 的映射、chunk 的位置等。
文件系统的 namespace 在 GFS 中存储为 B + 树。树上的每个叶子节点代表普通文件，而中间节点则代表目录文件。根节点是文件系统的根目录。
master 启动时会将所有元数据加载至内存中，优点是元数据操作速度很快，但是由于采用的是 single master，master 的内存会限制了文件系统的可扩展性，由于每个 64MB 的 chunk 会占据 64B 的 metadata，则 64GB 内存的服务器最多可支持的 chunk 的数量约为 64GB/64B = 10 亿。但由于 GFS 应用场景是大文件，所以这个问题并不是严峻
chunk
每个大文都件被划分为若干个固定大小的 chunk，每个 chunk 在创建的时候都会被 master 赋予一个唯一的 ID，称为 chunk handle
chunk 的大小理论上可为任意值，GFS 中为 64MB)，大的 chunk size 有以下优点与不足
- 减少了 client 与 master 的通信次数，从而减少了 master 和 network 的负载；对于 sequential read，chunk size 越大，数据在同一个 chunk 上的概率就越大，因此避免了读取多个 chunk
- 减少 master 存储的 metadata 的大小，因为 chunk size 越大，chunk 的数量就越小
- 可能会浪费空间，如一个 65MB 的文件会被分成两个 chunk，但是第二个 chunk 只有 1MB 的数据却占了 64MB 的大小
- 可能会导致 load imbalance，如一个小文件只有一个 chunk，因此存储这些 chunk 的 chunkserver 会成为 hot spot；但是在文章提到的应用中，hot spot 并不是一个大问题，因为文章内的应用应用场景是 read large multi-chunk files sequentially
此外，在每个 chunk 都会有另外的两个副本，分别存储在三台机器上，其作用有两个：high availability 和 load balancing；在这个机制中，副本位置的选取是一个比较关键的问题，一个好的副本位置定义算法满足下面特性：
- 保证足够的可靠性，例如，不能将所有副本存放在同一个磁盘或者物理机器上；
- 保证写入高效性，多副本位置尽量靠近，降低写入延迟，提高读写性能
论文中创建 chunk 时副本位置的选择方法如下：
（1）选择存储空间利用率最低的节点和磁盘 （2）选择最近一段时间内新建 chunk 数量较少的节点和磁盘； （3）将多个副本分散在不同的机架上
1 和 3 比较容易理解，2 是为了保证一个节点 / 磁盘不会被频繁新建 chunk（新建完接下来就是数据写入了），否则很容易沦为 hot spot，导致磁盘 IO 和网络带宽被占满，影响效率。
operation log
由于 metadata 存储着 GFS 的核心信息，因此 GFS 还设置了日志记录 metadata 的变更信息，这个日志就是 operation log
operation log 中一个关键信息是时间信息，包括 chunk 的版本、创建时间等，从而能够处理 concurrent opration
client 请求的 operation 首先会被 master 接受，然后 master 会先写日志，在修改内存中的 metadata，这样即使出现断电等异常，也不会丢失更新，因为可以在重启时通过 operation log 重新构造内存的 metadata
如果 operation log 记录着 GFS 自使用以来的所有 operation，那么 log 会非常大且重启时构建耗时会非常长，GFS 采用的机制是当 log 达到一定大小时，将当前内存的 metadata 持久化到硬盘上，称为 checkpoint；则 operation log 只需要存储创建 checkpoint 的时刻后的所有 operation，恢复时根据 latest checkpoint 恢复最新状态，且重新执行一遍 opration log 里面的操作即可
single master
single master 的设计显然存在着单点故障的问题，但是论文表明这么做两个理由
- (1) 这样大大减化了设计和实现
- (2) 实际数据直接在 client 和 chunkserver 间交流，所以 single master 不会成为 bottleneck
master 与 chunkserver 通过周期性的 HeartBeat 通信，用于动态搜集 chunkserver 的状态：如 chunkserver 上有哪些 chunk，从而 master 能够及时更新而无需长期存储这些信息
读写操作
下面主要讨论 GFS 中的读写操作
读
读操作比较简单，上面的系统架构图也显示了这一过程，其步骤如下
- client 告诉 master 需要读取的具体文件及其位置 (chunk index)
- master 返回这部分文件所在的 chunservers 以及 chunk 的 version
- client 缓存这些信息 (信息有一个过期时间，client 会等到这个信息过期后才会再次向 master 请求，从而缓解了频繁读写时，向 master 请求次数过多从而导致 master 负载过大)
- client 请求最近的 chunkserver，然后检查 chunkserver 上 chunk 的 version 是否与从 master 获取的相同；如果相同则读取数据，否则重新向 master 请求这些信息
写
写操作主要分为两种：write 和 append，write 是修改数据，append 则是在文件末尾添加数据
首先是 write 的过程，为了让同一个 chunk 多个副本数据保持一致， master 将存储 chunk 的其中一个 chunkserver 作为 primary，其他是 secondary，primary 用于确定数据写入这个 chunk 的顺序，secondary 则复制 primary 的写入顺序即可，下图是一个写操作的流程
各个步骤的具体操作如下
- client 询问 master 要写入的 chunk 所对应的 primary 和 secondary 位置（如果这时没有 primary，master 就会指定一个
- master 返回相关信息 (chunk locatioin，chunk version 等)，client 会把信息存入 cache，以后就不再重复询问 master 以节省开销，直到该 primary 的身份失效
- 客户端把数据发给所有 replicas (包括 primary 和 secondary)，replicas 们会把数据暂存在 LRU buffer cache 中，但是此时还并没有真的写入磁盘
- 当所有 replica 都确认收到数据后，client 发写入指令给 primary；primary 会给这个指令定一个序列号 (当同时收到多个 client 的请求时，在 primary 这里确定顺序)，primary 依序列号修改本地的数据
- primary 把写入指令和序列号发给 secondary，secondary 都依同样序列号修改自己的数据
- 当 primary 收到 secondary 的回复时，返回成功信息给客户端
- 如果有 secondary 失败了，primary 会返回失败信息给客户端。此时数据就是不一致的。客户端会发起重试。
另外一个写操作是 record append，其过程与上面相似，但是在这里 client 不会指定 offset，而是只提供数据，GFS 会把数据 append 进去后再返回 offset 给 client。
record append 还在 primary 添加了以下逻辑：
- 每次 append 时会针对待写文件的最后一个 chunk; 如果发现该 chunk 剩余空间不足以写入，则把当前 chunk 用空白补齐（padding)，然后把数据写入新的 chunk
- 数据的写入是 at-least-once，如果写失败了（即只在部分 secondary 上写成功），则会在新的末尾重新写一次，这样就会导致上次已经写成功的 replica 上数据出现两次，而上次写失败的 replica 上会有一段空白。返回给客户端的是成功写入的 offset 位置
- 客户端程序需要能正确处理这些情况：对于不正确的数据，可以在每个记录开头加一个 magic number，或者加一个 checksum 之类；对于重复的数据，需要客户端判重，比如在记录里加一个 unique id。
其他策略
- chunk version
- 上面提到读写过程中，master 均会告诉 client 对应的 chunk 目前的 version，从而保证 clinet 读取的是最新的数据
- chunk version 会在 master 为这个 chunk 选择新的 primary 时增加，并通知包含这个 chunk 的所有 chunkservers 更新这个 version
- 如果 client 在某个 chunkserver 读到的 chunk 的 version 与从 master 读取的不同，说明这个 chunkserver 的数据不是最新的
- snapshot
- snapshot 是对系统当前状态进行的一次拍照。用户可以在任意时刻回滚到快照的状态
- 采用 COW(copy-on-wirte) 机制实现 snapshot，即如果被 snapshot 的文件有更新操作时，就将文件的要被更新的 chunk 复制一份，然后对复制的 chunk 进行更新，而原来的 chunk 作为快照数据被保留，以后要恢复到该快照时，直接将该 chunk 读出即可
- 当 GFS 的 Master 节点收到 Snapshot 请求时，其处理逻辑如下
- 回收 snapshot 请求覆盖的文件的 chunks 上的租约 (即撤销 primary)，这样的话接下来客户端要对文件修改时，就必须向 master 申请，而此时 master 就可以对 chunk 进行复制
- master 在日志中记录本次 snapshot 操作，然后在内存中执行 snapshot 动作，具体是将被 snapshot 的文件或目录的元数据复制一份，被复制出的文件与原始文件指向相同的 chunk；
- 假如客户端申请更新被 snapshot 的文件内容，那么找到需要更新的 chunk，向其多个副本发送拷贝命令，在其本地创建出 chunk 的副本 ，之所以本地创建是因为可以避免跨节点之间的数据拷贝，节省网络带宽；
- 客户端收到 master 的响应后，表示该 chunk 已经 COW 结束，接下来客户端的更新流程与正常的没有区别。
- checksum
- checksum 解决的是数据完整性问题，即磁盘损坏从而导致数据损坏的问题
- 每个 chunk 会被划分为大小为 64KB 的 block，每个 block 有一个 32 位的 checksum
- client 从某个 chunkserver 读取数时，chunkserver 首先会验证要读取的数据的 checksum，如果 checksum 不符合已知记录 (写入时的记录)，会返回错误，从而让 client 去读取其他 chunkserver 上的 chunk
一致性
由于 GFS 中的 metadata 只在 master 可写，因此通过加锁保证修改的 atomicity；而对于修改 metadata 的 concurrent operation，operation log 中定义了这些 operation 的顺序， metadata 的一致性能够得到保证。
因此这里的一致性着重讨论的是文件的一致性，GFS 针对文件定义了以下的一致性状态
上图中的四种状态含义如下
- defined：从客户端角度来看，客户端完全了解已写入集群的数据的 offset，例如，客户端串行写入且成功（serial success），此时的状态是 defined
- consistent：客户端角度来看，chunk 多副本的数据完全一致，但不一定 defined (defined 包含了 consistent)
- inconsistent：多副本数据不一致
- undefined：数据未定义
下面分别以几个案例介绍上面的状态，这部分内容主要摘自这里
serial write
当 client 串行更新时时，客户端自己知道写入文件范围以及写入数据内容，且本次写入在数据服务器的多副本上均执行成功。因此，本次写结果对于客户端来说就是明确的，且多副本上数据一致，故而结果是 defined。如下图：
concurrent write
多个 client 同时写入时， 由于多个客户端由于写入范围可能交叉而形成交织写。这时候，由于单个客户端无法决定写入顺序（只有 primary 才能决定谁先写谁后写），因此，即使写入成功，客户端仍无法确定在并发写入时交叉部分最终写入结果，但是因为写入成功，所以多副本数据必然一致， 如下图所示
图中红色部分代表并发追加的部分，这部分数据由于无法确定谁先谁后执行，因此结果不确定；但由于跟新成功，因此，副本间数据是一致的，这就是 consistent but undefined。需要注意的是，consistent but undefined 只会出现在原始的 write 操作被划分为几个子操作时，原文解析如下
If a write by the application is large or straddles a chunk boundary, GFS client code breaks it down into multiple write operations. They all follow the control flow described above but may be interleaved with and overwritten by concurrent operations from other clients. Therefore, the shared file region may end up containing fragments from different clients, although the replicas will be identical because the individual operations are completed successfully in the same order on all replicas. This leaves the file region in consistent but undefined state as noted in Section 2.7.
而无论是 serial write 还是并行 concurrent write，一旦失败，多个 chunk 副本上的数据可能都不一致了，因此便是 inconsistent，必然也是 undefined。
append
上面提到，client 的 append 操作无需指定 offset，由 chunk 的 primary 根据当前文件大小决定写入 offset，在写入成功后将该 offset 返回给客户端。因此，客户端能够根据 offset 确切知道写入结果，无论是串行写入还是并发写入，其行为是 defined。如下所示
假设上面的 append 经历了一次重试，那可能实际 chunk 的布局如下
由于第一次写失败（错误可能发生在任意一个副本），导致了多副本之间从 50 至 80 的数据可能不一致。但接下来重试成功，从 80 至 110 之间的数据一致，因此，其状态是 interspersed with inconsistent。
小结
本文主要介绍了 GFS 的适用场景、系统架构、读写过程以及 一致性的保证，GFS 可以说是为 MapReduce 量身定做的文件系统: 大文件、文件写入后基本不修改、更着重吞吐量等，也有人说认为 GFS 也就没有 MapReduce 了，其实与其说 MapReduce 多么牛，不如说是 GFS 牛，因为 MapReduce 模型早就是数据库领域几十年前玩剩下的了，但是只有 Google 做出了那种廉价高效的分布式系，主要是因为 Google 的下层的支持系统也就是 GFS 做得好。
参考
- The Google File System
- Google File System
- Paper Reading: GFS