GFS 简读

一致性

由于有多份副本，GFS 面临着一致性的问题。

当数据被进行 replicated 的时候，一致性是很重要的。你读一个副本的时候，先写了但是数据还没过来呢

关于一致性，有强一致性和弱一致性，又派生出最终一致性这些意义不明的狗东西

这篇文章 写得不错，另外 ddia 关于这个也有简单讨论。

https://zhuanlan.zhihu.com/p/48782892

General tension between these:
strong consistency is easy for application writers
strong consistency is bad for performance
weak consistency has good performance and is easy to scale to many servers
weak consistency is complex to reason about

GFS 的特性(我相信读者们读过一万遍了)

  1. 失效是常态，而非意外事件：这点同 mapreduce, 我们需要处理失效等问题，来保证程序能够稳步的运行

  2. 文件“非常巨大”

    我们经常需要处理快速增长的、并且由数亿个对象构成的、数以 TB 的数据
    集时，采用管理数亿个 KB 大小的小文件的方式是非常不明智的

    (都用tb, 数个gb算, 好强啊，我什么时候能买的起这么多存储)

  3. 文件的修改采取 append 形式，很少会实际的把数据弄掉。写完之后尽量只进行“顺序读”，而非 RandomAccess. 同时提供 atomic 的 append 调用。

  4. GFS 提供了快照操作，能够对文件/目录下的文件取 Snapshot

  5. 没用 POSIX API，但是仍然有弱化的相似 API

GFS

C7442FCD-3FDB-4930-8EEB-8CA54E3E396D

GFS 存储的文件都被分割成固定大小的 Chunk。在 Chunk 创建的时候，Master 服务器会给每个 Chunk 分 配一个不变的、全球唯一的 64 位的 Chunk 标识。Chunk 服务器把 Chunk 以 Linux 文件的形式保存在本地硬盘 上，并且根据指定的 Chunk 标识和字节范围来读写块数据。出于可靠性的考虑，每个块都会复制到多个块服 务器上。缺省情况下，我们使用 3 个存储复制节点，不过用户可以为不同的文件命名空间设定不同的复制级别。

Master 节点管理所有的文件系统元数据。这些元数据包括名字空间、访问控制信息、文件和 Chunk 的映 射信息、以及当前 Chunk 的位置信息。Master 节点还管理着系统范围内的活动，比如，Chunk Lease、孤儿 Chunk的回收、以及 Chunk 在 Chunk 服务器之间的迁移。

GFS 的代码跑在 user-space 上，同时被链接到库里。

论文提到 GFS 客户端和服务端都不用写缓存：

客户端缓存数据几乎没有什么用处，因为大部 分程序要么以流的方式读取一个巨大文件，要么工作集太大根本无法被缓存。

Chunk 服务器不需要缓存文件数据的原因是，Chunk 以本地文件的方式保存，Linux 操作系统的文件系统缓存会把经常访问的数据缓存在内存中。

Master’s metadata

14BB9EEE-7E8F-4EB4-9752-BF22671DFEB4

  • map(filename --> [chunk-servers]), ns tree
  • chunk handler, lease map(handle --> ([cs, version, primary, lease expiration]))
  • Chunk 的 信息
  • LOG, CKPT

Master 服务器不会持久保存 Chunk 位置信息。Master 服务器在启动时，或者有新的 Chunk 服务器加入时，向各个 Chunk 服务器轮询它们所存储的 Chunk 的信息。

同样的，每个文件的在命名空间中的数据大小通常在 64 字节以下，因为保存的文件名是用前缀压缩算法压缩过的。

操作日志

  • log 复制到 remote 多台机器，全部完成之后，才会响应客户端
  • chunk保证log持久化之后，对客户端是可见的
  • master 能够 replay log 和构建 ckpt

Read

EC865399-2D30-4FF9-B84A-02D81A237714

客户端并不通过 Master 节点读写文件数据。反之，客户端向 Master 节点询问它应该联系的 Chunk 服务器。 客户端将这些 metadata 缓存一段时间，后续的操作将直接和 Chunk 服务器进行数据读写操作。

  • Client 把 (filename, offset) 发送给 Master
  • Master 发送 (u64_chunk_id, [chunk_servers]) 回去，客户端有一定的对这个结果的缓存
  • Client 从 Chunk Server 读数据，一般会选取 [chunk_server] 里面最近的机器去读取。

这个其实和文件系统 inode 和 block 的设计有一定相似性，逻辑上一定程度上可以按照那个理解。目前 GFS 的默认 Chunk Size 是 64M，这个值似乎在 HDFS 里面是可以调的。64M 减轻了 Master 的内存开销和 Client 的 metadata 缓存开销。但是其实这样也会造成很大的 internal fragments, 不适合小文件的处理，所以还是用户自己看情况 trade-off 把。

论文提到了：

在实际应用中，由于我们的程序通常是连续的读取包含多个 Chunk 的大文件，热点还不是主要的问题。

然而，当我们第一次把 GFS 用于批处理队列系统的时候，热点的问题还是产生了:一个可执行文件在GFS 上保存为 single-chunk 文件，之后这个可执行文件在数百台机器上同时启动。存放这个可执行文件的几 个 Chunk 服务器被数百个客户端的并发请求访问导致系统局部过载。我们通过使用更大的复制参数来保存可 执行文件，以及错开批处理队列系统程序的启动时间的方法解决了这个问题。一个可能的长效解决方案是， 在这种的情况下，允许客户端从其它客户端读取数据。

Consistency

GFS 对 file namespace 的修改，包括创建文件，是 atomic 的。 file namespace 只在 master 节点上操作。

the master’s operation log defines a global total order of these operations

但是并行的client写入是危险的，可以参考截图和对下面 phenomena 的定义

When a mutation succeeds without interference from concurrent writers, the affected region is defined (and by implication consistent): all clients will always see what the mutation has written. Concurrent successful mutations leave the region undefined but consistent: all clients see the same data, but it may not reflect what any one mutation has written. Typically, it consists of mingled fragments from multiple mutations. A failed mutation makes the region in- consistent (hence also undefined): different clients may see different data at different times. We describe below how our applications can distinguish defined regions from undefined

通俗的讲，需要辨别“一致”和”已定义”, 前者是多个副本内容的一致，后者是针对写/append 语义的。

GFS 保证写入的文件是“一致的”，这包括：

(a) 对 Chunk 的所有副本的修改操作顺序一致(3.1 章)，

(b)使用 Chunk 的版本号（这个值是跟 Lease 挂钩的，不理解的话可以看后面）来检测副本是否因为它所在的 Chunk 服务器宕机(4.5 章)而错过了修改操作 而导致其失效。失效的副本不会再进行任何修改操作，Master 服务器也不再返回这个 Chunk 副本的位置信息 给客户端。它们会被垃圾收集系统尽快回收。

a 很好理解，b 相对难理解很多, 所以我贴原文：

using chunk version numbers to detect any replica that has become stale because it has missed mu- tations while its chunkserver was down

然后注意 refresh

Since clients cache chunk locations, they may read from a stale replica before that information is refreshed. This win- dow is limited by the cache entry’s timeout and the next open of the file, which purges from the cache all chunk in- formation for that file. Moreover, as most of our files are append-only, a stale replica usually returns a premature end of chunk rather than outdated data. When a reader retries and contacts the master, it will immediately get current chunk locations.

所以我认为上面这段含义是，GFS 可能给客户端返回非最新但一致的数据，然后等待从客户端读取/刷新

在实际应用中，我们所有的应用程序对文件的写入操作都是尽量采用数据追加方式，而不是覆盖方式。 一种典型的应用，应用程序从头到尾写入数据，生成了一个文件。写入所有数据之后，应用程序自动将文件 改名为一个永久保存的文件名，或者周期性的作 Checkpoint，记录成功写入了多少数据。Checkpoint 文件可以 包含程序级别的校验和。Readers 仅校验并处理上个 Checkpoint 之后产生的文件 region，这些文件 region 的状 态一定是已定义的。这个方法满足了我们一致性和并发处理的要求。追加写入比随机位置写入更加有效率， 对应用程序的失败处理更具有弹性。Checkpoint 可以让 Writer 以渐进的方式重新开始，并且可以防止 Reader 处理已经被成功写入，但是从应用程序的角度来看还并未完成的数据。

Atomic Append

  1. client 想 append, 所以 ask for last chunk, 有可能是 master 上 no primary 的。
  2. master 寻找版本号等于 master 的数据，然后如果没有 primary 分配 primary 和 lease。注意，只有认为没有 primary 的时候，master 才会 increase version
    1. 如果联系不上，master 需要 wait for the lease, generate new primary
    2. 写顺序由 Primary 决定，是 chunk 内确定的, 具体参考论文3.2
  3. 给客户端返回 (P, S, #V + Lease)
  4. Master 持久化这个 version number

GFS 􏰂供了一种原子的数据追加操作–记录追加。传统方式的写入操作，客户程序会指定数据写入的偏 移量。对同一个region的并行写入操作不是串行的:region尾部可能会包含多个不同客户机写入的数据片段。 使用记录追加，客户机只需要指定要写入的数据。GFS 保证至少有一次原子的写入操作成功执行(即写入一 个顺序的 byte 流)，写入的数据追加到 GFS 指定的偏移位置上，之后 GFS 返回这个偏移量给客户机。这类似 于在 Unix 操作系统编程环境中，对以 O_APPEND 模式打开的文件，多个并发写操作在没有竞态条件时的行 为。

所以，你仍然可能有各种各样的问题，虽然它是指定顺序运行的。所以论文在2最后写了，应该在应用层做一定的决定（不知道这个部分有没有被封装成库）

在实际应用中，我们所有的应用程序对文件的写入操作都是尽量采用数据追加方式，而不是覆盖方式。 一种典型的应用，应用程序从头到尾写入数据，生成了一个文件。写入所有数据之后，应用程序自动将文件 改名为一个永久保存的文件名，或者周期性的作 Checkpoint，记录成功写入了多少数据。Checkpoint 文件可以 包含程序级别的校验和。Readers 仅校验并处理上个 Checkpoint 之后产生的文件 region，这些文件 region 的状 态一定是已定义的。这个方法满足了我们一致性和并发处理的要求。追加写入比随机位置写入更加有效率， 对应用程序的失败处理更具有弹性。Checkpoint 可以让 Writer 以渐进的方式重新开始，并且可以防止 Reader 处理已经被成功写入，但是从应用程序的角度来看还并未完成的数据。

我们再来分析另一种典型的应用。许多应用程序并行的追加数据到同一个文件，比如进行结果的合并或 者是一个生产者-消费者队列。记录追加方式的“至少一次追加”的特性保证了 Writer 的输出。Readers 使用 下面的方法来处理偶然性的填充数据和重复内容。Writers 在每条写入的记录中都包含了额外的信息，例如 Checksum，用来验证它的有效性。Reader 可以利用 Checksum 识别和抛弃额外的填充数据和记录片段。如果 应用不能容忍偶尔的重复内容(比如，如果这些重复数据触发了非幂等操作)，可以用记录的唯一标识符来过滤 它们，这些唯一标识符通常用于命名程序中处理的实体对象，例如 web 文档。这些记录 I/O 功能18都包含在我 们的程序共享的库中，并且适用于 Google 内部的其它的文件接口实现。所以，相同序列的记录，加上一些偶 尔出现的重复数据，都被分发到 Reader 了。

而系统只能保证：

如果操作成功执行，数据一定已经写入到 Chunk 的所有副本的相同偏移位置上

Snapshot

你可以把这个 GFS 系统当成是允许 cow 的，当你请求 snapshot 的时候：

  1. 取消所有现有的 Lease, 并写 wal
  2. copy metadata, 并且记录 rc, 拷贝有同样的 metadata
  3. 处理写 chunk 的时候，如果是快照写 C，Master 会 copy 一份新 chunk C’