Intro

GFS 设计前的观察 :

设备故障经常发生，GFS由许多台廉价设备作为存储节点组成，设备数量和质量决定任何时间都有部分设备无法工作，甚至有些设备会无法恢复。
文件越来越大。需要重新考虑 I/O 操作和 Chunk 大小的参数设计
大部分文件变更是以 Append 而非 Overwirte。
放宽一致性协议，能大幅简化系统，减少应用程序负担，

Design

假设 Assumptions

系统由经常发生故障的廉价商用设备组成，而系统能持续监控自身并检测故障、容错和及时恢复的能力。
系统存储一定数量的大文件，但也能支持小文件
Workload 主要源于两种 Read 操作: 大规模的流式读取和小规模的随机读取。大规模中同一个 Client 端连续读操作会经常访问同一个区域，小规模中会在文件某个任意偏移位置读几KB
Workload 还来自很多文件的大规模 Append 写入。一般情况下当写入规模与读取规模相似时，文件一旦写入就不会被修改。
文件通常在 Producer-Consumer 队列中或 Multi-way Merge 中使用。因此最小化原子性需要的同步开销非常重要，方便文件在被生产后可以同时或者一小段时间后被消费者读取。
持续高吞吐比低延迟重要。大多数 Apps 应更重视 big data 的处理，而不是对单个 R/W 操作有严格的时间要求。

接口 Interface

GFS 没有 POSIX 类似的标准 API，但也提供了常用的文件接口。

文件由文件路径名统一标识，GFS 支持 create, delete, open, close, read, write 等常用文件操作。

此外，GFS 还支持 snapshot 和 record append 操作。分别在 3.3 和 3.4 中详细说。

架构 Infra

一个 GFS 集群包括单个 master 和多个 chunkserver，并被多个 client 访问。如果单个节点允许接受不稳定 app 带来的低可靠性，则这个机器上可以同时运行 chunkserver 和 client。

文件被划分为若干个固定大小的 chunk，每个 chunk 被全局唯一的 64-bits chunk handle (由 master 分配) 唯一标识。 chunkserver 将 chunk 存储在本地磁盘中 client 通过 (chunk handle, byte range) 唯一确定需要被读写的 chunk 和 chunk 中的数据。

可靠性: 每个 chunk 会有 3 份 copy，存储在 3 个不同的 chunkserver。用户也可以为不同 namespace 的域指定不同的副本级别。

master 维护系统所有的 metadata，包括 namespace , access control, 文件到 chunk 的映射, chunk location。

master 也控制着 chunk lease（chunk 租约）, gc of orphaned chunks (孤儿 chunk 回收), chunkserver 间 chunk 的 migration。master 周期性地通过心跳与每个 chunkserver 通信，采集 chunkserver 信息并下达指令。

单 master

master 可以通过全局信息做复杂的 chunk placement 和与 replica 相关的决策。但是基于系统瓶颈的考虑，必须最小化 master 参与 R/W。

client 不会直接从 master 读取数据，而是询问 master 它需要与那个 chunkserver 通信。client 会缓存 chunkserver 信息，但不会缓存文件信息。

“读”操作:

根据固定的 chunk 大小，client 将 apps 指定的文件名和 chunk 偏移量翻译为文件中的 chunk index (块序号)。

client 向 master 发送一个包含 (file name, chunk index) 的 request，master 返回相应的 (chunk handle, chunk location) 的信息。client 根据该信息以 (file name, chunk index) 为 key 作缓存

client 向最近的 replica 所在的 chunkserver 发送 requests，指定文件的 (chunk hanlde, byte range) 。现实中 client 会在同一个 request 中请求多个 chunks，master 也可以返回多个 chunk 的响应，避免 client 与 master 的更多通信，减少额外开销的情况下得到更多信息

Chunk size

chunk size 选择了 64MB，远大于通常的文件系统中的块大小。

较大的 chunk size 优势:

减少 client 与 master 的交互次数，因为一个 chunk 足够存储许多的 chunk 位置信息
chunk 方便 client 在一个 chunk 上执行多个操作，与 chunkserver 保持更长时间的 TCP 连接来减少网络开销
减少了 master 中保存的元数据大小，方便 metadata 保存在 master 的内存中 (???)

劣势:

如果多个 client 访问同一个文件，存储这个文件的 chunkserver 会成为 hot spot。

GFS 首次在批处理队列系统中使用时，一个可执行文件可以存在单个 chunk 中，存储这个可执行程序的几台 chunkserver 被几百个并发请求超载。

通过提高可执行文件的副本数 (replication factor) 并让批处理队列系统错开 Apps 启动时间的方式修复了这个问题。

Metadata

metadata 主要存储三种数据:

file name
chunk namespace、文件到 chunk 的映射
chunk 中每个 replica 的位置

所有 metadata 存储在 master 的内存中，前两种类型的变更会记录到 log 中以持久化形式存储在 master 的磁盘上，并在远程机器上备份。

通过 log，可以简单可靠地更新 master 状态，即使 master 故障也不会有 inconsistent 的风险，master 不会持久化地存储 chunk 的位置信息，而是在启动时和当 chunkserver 加入集群时向 chunkserver 询问 chunkserver 存储的 chunk 信息。

这不是存储了 chunk 信息嘛…?

内存数据结构

metadata 存储在内存中，方便 master 对其快速操作。master 可以快速地周期性扫描整个状态实现 gc、chunkserver 故障时重做 replica、chunkserver 间的chunk migration。4.3和4.4会详细讨论。

chunk location

master 不会持久化保存哪台 chunkserver 含有给定的 chunk replica，而是在启动的时候从 chunkserver 中获取信息。

Q: 为什么是在启动时获取，而不是持久化保存?

A:

chunkserver 启动时比启动后去请求数据要简单(为什么?)

chunkserver 对其磁盘上有哪些 chunk 有着最终决定权，因为 chunkserver 中的错误会导致 chunk 消失 (如磁盘可能损坏或被禁用) 或一个操作者可能重命名一个chunkserver。

总而言之，试图在 master 上维护一个持久化的 chunk 位置信息视图是没有意义的。

操作日志 log

metadata 中唯一持久化的记录，所有带有版本号的文件和 chunks 在它们创建时由逻辑时间唯一、永久地确定。

将 log 备份到多台远程主机上，只有当 log 被本地和远程主机均写入到磁盘后才能向客户端发出响应。master 会在 log 被写入前批量合并一些 log 来减少写入和备份操作对系统吞吐量的影响。

master 通过 replay log 来恢复 GFS 状态，log 要尽可能小以减少启动时间。当日志超过一定大小时，master 会对其状态创建一个 checkpoint。checkpoint 的结构为一个 B-tree 来让它在内存中可以被直接映射，在查找 namespace 时也不需要做额外的解析。

这一步提高了系统恢复速度，增强了系统的可用性。

Q: 创建 checkpoint 时，若有 Read 请求咋办？

A:

创建 checkpoint 时，master 会切换到一个新的 log 文件并在一个独立的 thread 中创建 checkpoint，当 checkpoint 创建完成后会被写入 master 本地和远程主机的磁盘中

恢复只需要最后一个完整的 checkpoint 和后续的 log，旧的 checkpoint 和 log 可以随意删除，但会保留一段时间来容灾，创建 checkpoint 时发生错误时不会影响日志的正确性，因为恢复代码会检测并跳过不完整的 checkpoint

一致性模型

GFS 提供的保证

文件 namespace 的变更操作是 atomic 的，仅由 master 处理，namespace lock 保证了原子性和正确性；master 的 log 定义了这些操作的全局总顺序。

还没整完,这个一致性分级看得头有点疼

系统交互

设计系统时，希望 master 尽可能少地参与所有操作，这里主要描述 client、master 和 chunkserver 如何交互来实现数据变更、原子的 record append 和 snapshot 操作。

chunk lease

改变 chunk 或 metadata 的操作称为 “变更”，如 write/append，chunk 变更时其每个 replica 也需要变更。

使用 lease 来维护副本间变更顺序的一致性。 master 向其中一份副本授权一个变更的 lease，称这个副本为 primary。

chunkserver 收到 lease 及写请求后，才有权限决定多个写操作的执行顺序，此顺序被称为 serial order。当 primary 决定好顺序后，会将带有执行顺序的 lease 返回给 master 节点，master 节点随后将顺序分发给其他的 replica，replica 只能按照 primary 决定的顺序执行。

这种 lease 机制是为了最小化 master 管理 workload 而设计，lease 初始超时时间为 60s，但是一旦 master 又收到对同一个 chunk 的写操作，primary 就可以向 master 请求延长租约时间。

即使 master 与一个 primary 的通信丢失，master 仍可以在 old lease 过期后安全地向另一个副本授权 new lease。

举个栗子:

Client 向 master 询问哪个 chunkserver 持有指定 chunk 的 lease 及 chunk location，如果没有 chunkserver 持有 lease，master 会选择一个 replica 对其授权 (图中没有展示)
Master 回复给 client 的为 primary 的 chunk handle 和其他副本 (secondary) 的位置。client 同时缓存了这些信息方便后续 update。client 只有当 primary 不可访问或 primary 不再持有 lease 时才需要与 master 通信
client 将数据推送到所有副本。client 可以按任意顺序推送，每个 chunkserver 都会将推送来的数据缓存在内部的 LRU buffer cache 直到数据被使用或者缓存 age out (超时失效)。
client 发送写请求给 primary 节点，primary 为多个写操作确定执行的顺序(因为写操作可能来自多个 client)，然后将此顺序应用于本地 I/O 写
primary 节点将写操作请求转发给其他两个 replica，它们都将按照 primary 的顺序执行本地 I/O 写
primary 等待所有的 secondary 副本完成更新
primary 响应 client，并返回该过程中的错误，包括 replica的错误。如果 primary 自身发生错误，则不会向其他两个 replica 节点进行转发。如果 client 收到写失败响应，则其会重新进行写操作

Data Flow 数据流

两个关键字: linearly(线型) pipeline(管道)

GFS 目标是将数据流和控制流解耦，解耦的方式为以线型的方式传输数据，具体来说传数据的方式为:
$$
Client \rightarrow Primary \rightarrow Replica \ 1 \rightarrow Replica\ x
$$
这种方式能利用每台机器的网络带宽，避免网络瓶颈和高延迟链接，最小化通过所有数据的延迟。

Q: 高延迟链接是什么？

具体来说，避免 network bottlenecks 与 high-latency links 的线型链路采用了如下做法：每个节点会将数据转发给最近的还没收到数据的节点

节点通过 IP 地址估算两个节点之间的链路距离。

Data Flow 为了最小化延迟，采用了管道传输模型。

管道传输模型用自来水管道解释即，水（字节）经过一个节点就会去下一个节点。

当一个 chunkserver 接收到一些数据后（收到的字节达到某阈值）立即转发给下一个节点，而不是等此次写操作的所有数据接收完毕。因为 GFS 采用的是全双工网络，因此发送数据时不会降低数据的接受速率。

Atomic Record Appends - 原子记录追加

GFS 中 Client 仅负责指定要写的数据，GFS 以 at least once 的原子操作进行写，写操作的相关数据一定作为连续的字节序列存放在 GFS 选择的偏移量处，因为 record append 操作总是在文件末尾追加数据，因此这个地址偏移量应当交给 chunkserver 来确定。

如果设计多个 record append 操作，利用 lease 实现并发的安全性。

GFS record append 操作的内部执行逻辑如下：

Client 确定 file name 和要写入的 byte data(形式上可以选择一个 buffer 来存储要写入的字节数据)
Client 向 master 请求进行 record，附上要 append 的 file name(不用携带字节数据)
Master 返回内存中由 metadata 得到关于当前 file 分块存储的最后一个 chunk 的chunk handle 以及 chunk 所在的所有 chunkservers 信息
之后即 chunk lease 过程

这之中还涉及如何选择 primary:

Master 会找到此 file 最后一个 chunk 的 up-to-date version
Master 选择好 primary 节点后递增当前 chunk 的 chunk version，并通过 Master 的持久化机制持久化
通过 primary 与其他 chunkserver，发送修改此 chunk 版本号的通知，节点收到通知后会修改版本号，然后持久化
Primary 选择 file 最后一个 chunk 的末尾 offset 开始写入数据，写入后将此消息转发给其他 chunkserver，其他 chunkserver 对相同的 chunk 在 offset 处写数据。

一些问题：

若向 file 追加的数据超过了 chunk 的剩余容量怎么办?

record append 实际上一次能添加的数据大小最大限制为为 chunksize (64MB) 的 1/4
如果添加数据超过了 chunksize，priamry 会继续向该 chunk append 数据直到 64MB，后通知两个 replicas 执行相同操作。最后响应客户端，告知客户端创建新 chunk 后再继续填充，因为数据实际上没有完全消耗掉。

Read 读操作

client -> master: filename + offset (client打算读取的字节范围)
Master -> client: chunk handle + a list of servers
client 从 server lists 通过 IP 地址选出最近的 chunkserver，client 会优先向最近的 chunkserver 请求数据读取
chunkserver 收到数据读取请求后，根据 client 发来的 chunkhandle 进行磁盘 I/O 将最终数据返回给 clients

Snapshot - 快照

Snapshot 即为文件创建一个副本或直接为一个目录树创建副本(有多个文件)

GFS 使用 standard copy-on-write 技术来实现 snapshot，其实现方式为:

当一个 master 节点收到 snapshot 请求时，它首先会撤销快照涉及到的文件的 chunk 上未完成的 lease，确保对这些 chunk 后续写入时都需要和 master 交互找到 lease 的持有者，这会给 master 优先拷贝这些 chunk 的机会
当 lease 被收回或者过期后，master 会将对快照的操作记录到日志中并写入到磁盘里，随后 master 会通过在内存中创建一个源文件或源目录树的metadata的副本方式作为 snapshot。新创建的 snapshot 和源文件指向相同的 chunk
当 client 向 master 请求对这些 chunk 进行写操作时，master 会检测到这些 chunk 的 chunkserver 引用计数大于 1，于是 master 会为这些 chunk 创建相关的 handler，通知拥有这些 chunk 的 chunkserver 创建数据相同的 chunk （这种方式不会在 master 上进行复制，目的是节约 master 带宽与内存）
最后 client 新的写请求将直接作用于这些新创建的 chunk 上，同时也会被颁发新的 lease

Master operation - 主节点操作

master 主要做的工作为：

所有 namespace 的管理工作
管理整个系统中的所有 chunk replicas:
- 确定 chunk 实际存储位置
- 创建新的 chunk 及其副本
- 协调系统的各种操作（如 R/W/Snapshot 等），用于保证 chunk 正确且有效地进行备份
- 管理 chunkserver 之间的负载均衡
- 回收没有被使用的存储空间

namespace management & locking

命名空间管理和锁机制

master 节点有很多操作都需要执行很长时间，如 snapshot 必须向 chunkserver 撤回其设计的所有 chunk lease。我们不希望这些耗时的操作会影响 master 节点的其他操作。

解决方法是通过给 namespace 上锁实现同时进行多个操作及确保操作的正确串行执行顺序。

GFS 中没有创建一个用于记录当前目录拥有哪些文件的数据结构，也不支持文件和目录的别名。GFS 逻辑上将 namespace 作为一个查询表，将文件路径映射为 metadata。

如果使用 prefix compression(前缀压缩)，则这个表可以在内存中被高效地表示，namespace 树中每一个节点对应一个 full pathname，拥有一个与之相关联的 read-write lock。

**Master 节点的每一个操作都必须先获得一系列锁才能够真正的运行 **

锁粒度问题：如果要修改一个 full pathname 表示的目录/文件，是给它的上级目录全部上锁吗？上什么锁呢？

关于写操作涉及的文件/目录的锁获取有如下规律:

最底层的文件/目录一定是 write lock
除了 current file/dir，其他所有 dir 仅需要获得 read lock， read lock 是一种共享锁

Replica Placement - 确定 Replica 的存放位置

chunk replica placement policy 有两个目的:

最大化数据 reliability 和 availability
最大化 network bandwidth utilization

为了达到上述目的：

需要在不同的 racks(机架) 上传输 chunk replicas，确保当有一个 rank 发生故障时，其他 racks 的存在保障系统的可靠性和可用性
由于 chunk replicas 分布存储在不同 rack 的 chunkserver 上，分布式读取降低了每一个 rack 读取 replicas 的带宽压力

Creation Re-replication Rebalancing

chunk replica 出于三个原因被创建：

chunk creation 创建
re-replication 重放置
rebalancing 均衡再建

chunk creation

默认情况下 master 创建一个 chunk 会另外创建 3 个 replica 分发到对应的 chunkserver 上：

master 选择将 replica 放置在 磁盘空间利用率 低于平均水平的 chunkserver 上，保持所有 chunkserver 在磁盘利用率上的一致性
限制每一个 chunkserver 上最近创建的 chunk 的个数
尽量将 replicas of chunk 分散放置在不同的 rack 上

re- replication

当 replicas 数量下降到用户阈值时，master 会开始 re-replicate chunk 操作：

chunkserver unavailable ，比如它给 master 发送这样的状态信息：它的 replica 崩溃了某一个磁盘不可读
程序员修改了配置动态增加了 replication 的个数要求

当 chunk 需要被 re-replicated 时， master 通过以下因素来确定执行优先级:

根据 replication goal 的配置距离确定优先级。如有一组 replicas 只有 1 个可用，另一组有 2 个可用，前者优先级更高
最近被读写的文件比最近删除的文件 chunk 有更高的优先级
若 chunk 的读写可能阻塞客户端，则该 chunk 将有较高的优先级，这能够减少 chunk 故障时对使用 GFS 应用程序的影响

rebalancing

master 检查当前 replica 的分布，将相关 replica 移动到更好的磁盘位置。通过这个机制 master 将一个新加入的 chunkserver 自动地逐渐填充，而不是一开始用大量写操作填充它，

Garbage Collection

当 master 发出删除文件请求后，GFS 不会立即回收文件的物理磁盘存储空间，GFS 提供了定期的垃圾回收机制，用于回收 file 和 chunk 级别的物理磁盘空间。

Mechanism 机制说明

当一个文件被删除时，master 会将此删除操作写入日志系统中，但是不会马上向相关 chunkserver 发出删除请求，而是将文件重命名为 hidden name。

文件重命名仅在 master namespace 中进行，其重命名名字包含接收到删除指令的时间戳。在 master 定期对 namespace 的扫描过程中，会移除所有距删除时间戳 3 天以上的 hidden files。

当 hidden file 从 namespace 中移除后，该文件在 master 中的所有 metadata 都被移除，chunkserver 会删除磁盘上的相关文件。这种垃圾回收的好处有以下优点:

方式简单可靠
- 通过定时 heartbeat，master 通知 chunkserver 删除相关 chunk，chunkserver 告知 master 他有什么 chunks
能够平均化垃圾回收成本
- 这种 gc 机制依赖于定时的 namespace 扫描及定时的 heartbeat 通信，因此 gc 最初是分批进行而不是集中进行。并且 master 只有当 idle 时才会扫描 namespace，因此 master 不会因为 gc 而有过多负担
三天的超时删除机制为不可逆删除提供了安全保障

Stale Replica Detection

当 chunkserver 故障或因为宕机而没能正确实施写操作时，chunk replicas 的状态则变为 stale。 master 为每个 chunk 维护一个 chunk version number 来辨别哪些 chunk 是 up-to-date，那些是 stale 的。

当 master 赋予一个 chunk 新 lease 时，相应的 chunk version 会自增，并将此 version 通知其他 replicas。

Fault Tolerance and Diagnosis

High Availability

提升系统总体可用性的策略为: fast recovery 和 replication.

Fast Recovery

master 及 chunkserver 无论出现什么故障，都能在几秒内恢复故障前的状态。
Chunk Replication

每个 chunk 会被复制到多个分布于不同 rack 的 chunkserver 上，可以为 namespace 不同区域制定不同的 replication 级别(默认级别为 3，即有三份 replicas)
Master Replication

Master 使用日志系统及 checkpoint 确保 master 状态信息的可靠性，只有当内存 snapshot 被刷新到本地磁盘或远程磁盘上，才会认为修改状态提交了。

master 还提供 shadow master，当 master 宕机时，shadow master 提供文件系统的只读访问。shadow master 通过读取 master 日志系统的 replicas 进行状态的更新，后日志的先后顺序执行操作。

shadow master 不参与和其他 chunserver 进行通信，如不存在心跳机制

Data Integrity - 数据完整性

chunkserver 通过 checksum 检测存储的数据是否损坏

一个 chunk 被划分为 64KB 的 block，每个 block 有其对应的 32-bit checksum。

client 向 chunkserver 发送读数据的请求时，chunkserver 首先对读操作涉及的所有 block 块作 checksum。若不匹配，返回错误并向 master 报告错误。

请求者接收到此响应后，会从其他 replica 上读数据，master 则会从另一个 replica 上 clone chunk，并指示 chunkserver 删除其 replica。

Diagonostic Tools - 诊断工具

GFS 会生成 diagnostic 日志 (chunkserver 的日志系统)，记录一些比较重要的事件:

Chunkserver 上线或离线
RPC 的请求或响应

Measurements

略

Experience 使用经验

流处理中消息送达的方式分为三种:

At-most-once

消息保证至少发送成功一次，也就是可能会重复发送，即一个消息可能会成功发送 1~n 次；
At-least-once

消息只保证最多发送一次，那就是要么成功，要么失败，即一个消息可能会成功发送 0-1 次；
Exactly-once

消息保证发送成功且仅发送成功一次，这种理想情况基本不存在