http://nil.csail.mit.edu/6.5840/2024/papers/gfs.pdf

定义

GFS (Google File System) 是谷歌的分布式文件系统，主要面向其他分布式系统提供存储服务。

Assumptions

  • 跑节点的都是便宜机器，很容易 fail，因此需要 fault tolerance

  • 系统存储的文件大部分都是大文件（原文中提到 > 100MB / Multi-GB），多针对大文件的读写进行优化

  • Workloads 可以初步分两种情况：大连续读（1 MB+）和小随机读（a few KB）。同一个 client 通常会读一个文件中连续的区域（局部性）。性能敏感的应用会将多次小的读操作累计排序起来批量读，以便向前读文件，而不是跳转到后面。

  • Workloads 中也存在很多 append 到文件末尾的大线性写操作，一旦写入之后就很少修改（像存储日志那种场景），需要针对这种场景进行优化

  • 系统必须完整实现多个 client 并发写文件的语义。GFS 中的文件经常用于生产者-消费者队列（生产者的写操作是 append 到文件末尾）或者多路合并（多个client 并发写文件不同的部分）。实现最小化同步开销的原子性至关重要。并且文件可能在写的同时被读，也可能在写操作完成后被整个读。

  • 高吞吐量比低延迟（low latency）更加重要，GFS 的使用场景追求整体高效的处理批量读写请求，而很少有场景要求针对单个读写操作的低延迟。

Interface

GFS 并没有实现 POSIX 接口，但实现了常用的 API，比如 create, delete, open, close, read, write 。

并且 GFS 提供了 snapshot 和 record-append 接口。snapshot 可以低成本的创建一个文件/目录的快照，而 record-append 接口可以让系统在多个客户端并发写一个文件的情况下保证原子性（本质上就是把原本的写 byte 操作变成了 append 一条 record，缩小了临界范围，系统只需要保证 append record 操作在并发环境是线性的即可低成本的保证写操作的原子性）。append record 对于实现生产消费者对列和多路合并非常有用，它可以让实现这些功能不需要加额外的锁。并且我们发现这些数据在分布式存储系统中是不重要的（都是临时数据，可以接受被丢弃）。

Architecture

image
文件被拆分成一个个固定大小的 chunk，通过 chunk handle 来索引到某个指定的 chunk。文件与 chunk 和 chunk 所在位置的映射关系保存在 master 节点。出于可靠性的考虑，每个 chunk 都保存了多份拷贝在不同的 chunkserver。master 节点也负责孤儿区块的垃圾回收，不同 chunkserver 之间的区块合并。并且 master 会定时向所有 chunkserver 发心跳包来发送指令，并收集其状态。

客户端侧在需要读写一个文件时先找 master 要到 chunk 的句柄和地址，在直接访问 chunk server 对某段字节进行读写。

客户端侧缓存作用有限，因为文件往往过大而不能全部放入缓存池。客户端不缓存简化了实现，并且避免了缓存不同步（cache coherence）的问题。chunk server 也不需要缓存，因为 chunk 是以文件的形式存储在磁盘上的，所以 linux 内核的缓存会起到效用。

Single Master

只有一个 master 节点简化了实现，但为了不让跟 master 节点通信成为瓶颈，客户端只从 master 节点获取元数据，通过元数据直接跟 chunk server 通信进行具体的读写操作。并且客户端会在一定时间内缓存元数据，减少跟 master 节点的通信。

客户端将读写的文件名和 offset 翻译成对应的 chunk index 和 offset，通过这个来索引到对应的 chunk server。客户端之后会发送请求给这个 chunk 的其中一个 replica，请求中包含了 chunk handle 和对应的 offset。客户端也可以在一次请求中索要多个 chunk 中的多段数据（batching）。

Chunk Size

Chunk 的大小也是系统的一个关键参数，这里选择 64 MB。因为 GFS 常常顺序读写大文件，而对同一个块的读写只需要发送一次请求，所以选择大的 chunk size 可以有效减少客户端读写请求的次数。客户端有可能需要对一个块进行多次操作，所以保持 TCP 长连接可以减少通信开销。并且大的 chunk size 也可以让客户端缓存的元数据量更少，更容易缓存到内存中。

但大的 chunk size 也存在问题，某些热点文件可能就会被存储在一个 chunk server 中，而不是分割到多个 chunk server，这样可能会有大量请求并发打到某个 chunk server 上。目前是通过针对性的提高热点块的 replica 数量和给请求排队来解决这个问题。

Metadata

Master 节点存储三种类型的 metadata：文件和 chunk 的 namespace，mappings from files to chunks，the locations of each chunk’s replicas。所有的 metadata 都保存在 master 节点的内存中。文件和 chunk 的 namespace 和文件到 chunk 的映射同时也通过修改日志（operation log）的形式持久化在磁盘上并在其他机器上保有副本。

而 chunk 副本的位置没有被持久化的存储，它在 master 节点拉起来或 chunk server 节点加入集群时向 chunk server 询问。

Operation Log

Operation log 是 GFS 的核心，其不仅是元数据的唯一持久化记录，还充当定义并发操作顺序的逻辑时间线。GFS 在多台远程机器上复制日志，并在将相应日志记录刷新到本地和远程磁盘后，才响应客户端操作。（多副本的 Write Ahead Log）

当日志达到一定规模时需要设置 checkpoint（跟 DB 一样），需要恢复时从最近的 checkpoint 开始重放所有 operation log。

Consistency Model

GFS 的一致性模型是 relaxed consistency，优先考虑性能和可用性而非强一致性。它只保证：

  • 所有副本最终会收敛到相同状态

  • 成功的 append 操作在所有副本上都是原子的

  • 但不保证所有副本在任意时刻都完全一致

Guarantees By GFS

image
文件 namespace 的更改（创建/重命名/删除文件）是原子的，这个原子性是由 master 保证的

表1中 defined 的意思是行为是定义过的，比如 serial access write 结果是确定的，所以是 defined。concurrent successes 结果因为并发是不确定的，但所有 client 都能看到一样的结果，所以是 consistent but undefined。

Record append 的语义在并发的情况下也是 defined 的，GFS 允许多个客户端同时对同一个文件进行 record append 操作。由于没有严格的全局排序机制，不同副本（replicas）上的记录可能以不同的顺序出现，或者在某些副本上成功而在其他副本上失败，因此是 inconsistent 的。

Failure 最终都会导致 inconsistent 的结果。

Implications for Applications

事实上 GFS 上存储的所有文件基本上都使用 record append 写入而不是 write，比如 MapReduce。

作为生产者-消费者队列使用时可能需要考虑幂等性的问题，append 操作的语义只保证至少 append 一次，但可能会消费到多条一样的消息，这个时候用 msgID 去下重就行。

System Interactions

Leases and Mutation Order

image
GFS 使用租约（lease）来维持各副本间一致的 mutation 顺序。master 会在chunk的各副本中选择一个作为主副本授予租约，主副本为该 chunk 的所有 mutation 操作分配串行顺序。租约会有一个 60s 的超时时间，但如果 chunk 一直在发生变更也可以通过心跳消息无限续约。

  1. 客户端向主服务器查询：当前持有该数据块租约的块服务器身份，以及其他副本的位置。若尚无任何副本持有租约，主服务器会将租约授予其选择的一个副本（图中未显示）。

  2. 主服务器响应：返回主副本（Primary）的标识及其他从副本（Secondary）的位置。客户端缓存该数据以供后续突变操作使用，仅在主副本无法访问或响应 “不再持有租约” 时，才需再次联系主服务器。

  3. 客户端推送数据至所有副本：推送顺序不限，每个块服务器会将数据存储在内部 LRU 缓冲区中，直至数据被使用或过期。通过将数据流与控制流解耦，我们可基于网络拓扑调度高开销的数据流（与主副本无关），以提升性能（3.2 节将进一步讨论）。

  4. 所有副本确认接收数据后：客户端向主副本发送写入请求，请求中标识此前推送给所有副本的数据。主副本为接收到的所有突变操作（可能来自多个客户端）分配连续序列号，以此实现必要的串行化，并按序列号顺序在本地应用突变。

  5. 主副本将写入请求转发至所有从副本：每个从副本按主副本分配的相同序列号顺序应用突变。

  6. 从副本向主副本回复操作完成。

  7. 主副本向客户端回复：若任意副本在操作中出错，错误会被报告给客户端。此时，写入可能仅在主副本和部分从副本上成功（若主副本失败，则不会分配序列号及转发请求）。客户端请求被视为失败，修改后的区域处于不一致状态。客户端代码通过重试失败的突变操作处理此类错误：会先重试步骤 3 至 7，若失败则回退至从写入操作的初始阶段重新尝试。

若应用程序的写入操作数据量较大或跨数据块边界，GFS 客户端代码会将其拆分为多个写入操作。这些操作均遵循上述控制流，但可能与其他客户端的并发操作交叉或覆盖。因此，共享文件区域可能包含不同客户端的片段，但由于所有副本按相同顺序成功完成单个操作，副本数据将保持一致 —— 如 2.7 节所述，该文件区域处于 “一致但未定义” 的状态。

Data Flow

GFS 的设计解耦了数据流和控制流，因此在上传数据时就可以链式的分发数据流（客户端发给最近的副本，副本又发给离他最近的副本），尽可能提升整体的速度。

Atomic Record Appends

记录追加属于突变操作，遵循 3.1 节中的控制流，仅在主副本处增加少量额外逻辑。客户端先将数据推送到文件最后一个数据块的所有副本，然后向主副本发送请求。主副本会检查将记录追加到当前数据块是否会使其超过最大大小（64MB）。若超过，主副本会将该数据块填充至最大大小，并告知从副本执行相同操作，同时回复客户端提示应在下一个数据块重试该操作（为将最坏情况下的碎片控制在可接受水平，记录追加的大小限制为最大数据块大小的四分之一）。在常见情况下，若记录大小符合最大限制，主副本会将数据追加到自身副本，并告知从副本在其写入的精确偏移量处写入数据，最后向客户端回复操作成功。
若记录追加在任意副本上失败，客户端会重试该操作。因此，同一块的副本可能包含不同数据，可能完整或部分包含相同记录的副本。GFS 不保证所有副本字节级完全一致，仅保证数据以原子单元至少写入一次。这一特性源于以下简单逻辑：若操作报告成功，则数据必定已在某个数据块的所有副本的相同偏移量处写入。此外，在此之后，所有副本的长度至少为记录末尾，因此即使后续其他副本成为主副本，任何未来记录也会被分配更高偏移量或不同数据块。就一致性保证而言，成功记录追加操作写入数据的区域是已定义的（因此一致），而中间区域是不一致的（因此未定义）。我们的应用程序可按 2.7.2 节所述处理不一致区域。

Snapshot

Snapshot 可以快速创建一个文件/目录的副本，使用 Copy On Write 实现。

当主服务器接收到快照请求时，会首先撤销即将快照的文件中数据块的所有未到期租约。这确保后续对这些数据块的写入操作需与主服务器交互以查找租约持有者，从而为主服务器提供先创建数据块新副本的机会。
租约被撤销或到期后，主服务器将操作记录到磁盘，然后通过复制源文件或目录树的元数据，将该日志记录应用到内存状态中。新创建的快照文件指向与源文件相同的数据块。
快照操作后，客户端首次尝试写入数据块 C 时，会向主服务器发送请求以查找当前租约持有者。主服务器发现数据块 C 的引用计数大于 1，会暂缓回复客户端请求，转而选择新的数据块句柄 C’，并要求每个持有 C 当前副本的块服务器创建名为 C’ 的新数据块。通过在与原数据块相同的块服务器上创建新数据块，我们确保数据可在本地复制，而非通过网络传输（我们的磁盘速度约为 100 Mb 以太网链路的三倍）。从此时起，请求处理与任何数据块无异：主服务器向新数据块 C’ 的某个副本授予租约并回复客户端，客户端可正常写入该数据块，而无需知晓它是由现有数据块创建而来。

Master Operation

所有 namespace operation 都是由 master 执行的，同时 master 也负责放置 chunk，创建新 chunk 和相应副本，协调系统活动以确保每个 chunk 都有指定数量的副本以保证所有 chunk server 负载均衡，以及回收未使用的 chunk。

Namespace Management and Locking

每个主服务器操作在运行前会获取一组锁。通常，如果操作涉及 /d1/d2/.../dn/leaf，则会获取目录名 /d1、/d1/d2、…、/d1/d2/.../dn 的读锁，以及完整路径名 /d1/d2/.../dn/leaf 的读锁或写锁（取决于操作类型，leaf 可能是文件或目录）。
下面说明此锁机制如何防止在将 /home/user 快照到 /save/user 时创建文件 /home/user/foo：快照操作获取 /home 和 /save 的读锁，以及 /home/user 和 /save/user 的写锁；文件创建操作获取 /home 和 /home/user 的读锁，以及 /home/user/foo 的写锁。这两个操作会被正确串行化，因为它们尝试在 /home/user 上获取冲突的锁。文件创建不需要父目录的写锁，因为没有需要保护的 “目录” 或类似 inode 的数据结构，对目录名的读锁足以防止父目录被删除。

此外，锁按一致的全局顺序获取以避免死锁：首先按命名空间树中的层级排序，同层级内按字典序排序。

Replica Placement

块副本放置策略有两个目标：最大化数据可靠性和可用性，以及最大化网络带宽利用率。

将一个块的副本放置在不同的机器是不够的，需要将其放在不同的机房，这样可以保证即便整个机房不可访问，数据也有可用的副本。不过这会导致写入通信成本的增加，这是可以接受的权衡。

Creation, Re-replication, Rebalancing

Chunk副本的创建有三个原因：chunk创建、重新复制和重新平衡。当master创建一个chunk时，它会选择在哪里放置初始的空副本。它会考虑几个因素：
(1) 磁盘空间利用率均衡
我们希望将新副本放置在磁盘空间利用率低于平均水平的chunkserver上。随着时间推移，这将平衡各个chunkserver的磁盘利用率。
(2) 限制”最近”创建的数量
我们希望限制每个chunkserver上”最近”创建的chunk数量。虽然创建本身成本很低，但它可靠地预示着即将到来的大量写入流量，因为chunk是在写入需求时创建的，并且在我们的”写入一次-读取多次”工作负载中，一旦完全写入，它们通常变成实际上的只读状态。
(3) 跨机架分布
如前所述，我们希望将一个chunk的副本分布在不同的机架上。
重新复制
一旦可用副本数量低于用户指定的目标，master就会重新复制chunk。这可能由多种原因导致：chunkserver变得不可用、报告其副本可能损坏、其中一个磁盘因错误而被禁用，或者复制目标数量增加。
每个需要重新复制的chunk都会基于几个因素进行优先级排序：

  • 距离复制目标的远近：例如，我们给丢失两个副本的chunk比只丢失一个副本的chunk更高的优先级

  • 活跃文件优先：优先重新复制属于活跃文件的chunk，而不是属于最近删除文件的chunk

  • 阻塞客户端进度：为了最小化故障对运行中应用程序的影响，我们提升任何阻塞客户端进度的chunk的优先级

Master选择最高优先级的chunk并通过指示某个chunkserver直接从现有有效副本复制chunk数据来”克隆”它。新副本的放置目标与创建时类似：平衡磁盘空间利用率、限制单个chunkserver上的活跃克隆操作，以及跨机架分布副本。
为了防止克隆流量压倒客户端流量，master会限制集群和每个chunkserver的活跃克隆操作数量。此外，每个chunkserver通过限制对源chunkserver的读取请求来限制其在每个克隆操作上花费的带宽。
重新平衡
最后，master会定期重新平衡副本：它检查当前的副本分布，并移动副本以获得更好的磁盘空间和负载平衡。通过这个过程，master也会逐渐填充新的chunkserver，而不是立即用新chunk和随之而来的大量写入流量压垮它。
新副本的放置标准与上述讨论的类似。此外，master还必须选择移除哪个现有副本。一般来说，它倾向于移除那些在可用空间低于平均水平的chunkserver上的副本，以便平衡磁盘空间使用。

Garbage Collection

当应用程序删除文件时，master会像处理其他变更一样立即记录删除操作。但是，它不会立即回收资源，而是将文件重命名为一个包含删除时间戳的隐藏名称。
在master对文件系统命名空间的定期扫描过程中，它会移除任何存在超过三天的隐藏文件（该间隔是可配置的）。在此之前，文件仍然可以通过新的、特殊的名称读取，并且可以通过重命名回正常名称来取消删除。
当隐藏文件从命名空间中移除时，其内存中的元数据被清除。这有效地切断了它与所有chunk的链接。
在对chunk命名空间的类似定期扫描中，master识别孤立的chunk（即那些无法从任何文件访问到的chunk）并清除这些chunk的元数据。
在与master定期交换的HeartBeat消息中，每个chunkserver报告它拥有的chunk子集，master回复所有在master元数据中不再存在的chunk的标识。chunkserver可以自由删除这些chunk的副本。

Stale Replica Detection

如果chunkserver故障并在宕机期间错过了对chunk的变更，chunk副本可能会变得过时。对于每个chunk，master维护一个chunk版本号来区分最新和过时的副本。
版本号管理机制
租约授予时的版本更新：每当master对chunk授予新租约时，它会增加chunk版本号并通知最新的副本。Master和这些副本都会在其持久化状态中记录新的版本号。这发生在通知任何客户端之前，因此在客户端开始写入chunk之前。
处理不可用副本：如果另一个副本当前不可用，其chunk版本号将不会被推进。当chunkserver重启并报告其chunk集合及其关联的版本号时，master会检测到该chunkserver拥有过时副本。
版本号冲突处理：如果master看到一个比其记录中更大的版本号，master会假设它在授予租约时失败了，因此采用较高的版本作为最新版本。
过时副本的处理
垃圾收集清理：Master在其常规垃圾收集中移除过时副本。在此之前，当它回复客户端对chunk信息的请求时，实际上完全不考虑过时副本的存在。
安全保障机制
版本号验证：作为另一重保障，当master通知客户端哪个chunkserver持有chunk租约，或当它指示chunkserver在克隆操作中从另一个chunkserver读取chunk时，master会包含chunk版本号。客户端或chunkserver在执行操作时验证版本号，以确保它始终访问最新数据。

Fault Tolerance and Diagnosis

High Availability

两条策略：fast recovery & replication

Fast Recovery

所有的节点都被设计成可以在几秒内恢复状态并启动，无论他们中断的原因是什么，server 可以直接通过杀进程来 shut down，客户端和其他服务器访问节点超时可以进行重试。

Chunk Replication

当 master 检测到 chunk server 下线或chunk损坏时（checksum 校验），master 会根据需要进行 chunk replication。

Master Replication

为了可靠性，master状态被复制存储。它的操作日志和检查点被复制到多台机器上。只有当日志记录已经在本地和所有master副本上刷新到磁盘后，对状态的变更才被认为是已提交的。
为了简化，一个master进程保持负责所有变更以及内部改变系统的后台活动（如垃圾收集）。进程挂掉时，可以几乎瞬间重启。如果其机器或磁盘挂掉，GFS外部的监控基础设施会在其他地方用复制的操作日志启动新的master进程。
此外，”影子”master即使在主master宕机时也能提供对文件系统的只读访问。它们是影子而不是镜像，因为它们可能稍微滞后于主master，通常是几分之一秒。
功能特点：

  • 为不被主动变更的文件或不介意获得略微过时结果的应用程序增强读取可用性

  • 由于文件内容是从chunkserver读取的，应用程序不会观察到过时的文件内容

  • 在短时间窗口内可能过时的是文件元数据，如目录内容或访问控制信息

影子master的工作机制
数据同步：为了保持信息更新，影子master读取不断增长的操作日志的副本，并像主master一样将相同的变更序列应用到其数据结构中。
状态监控：像主master一样，它在启动时（以及此后不频繁地）轮询chunkserver以定位chunk副本，并与它们交换频繁的握手消息来监控它们的状态。
依赖关系：它只依赖主master获取由主master创建和删除副本决策产生的副本位置更新。

Data Integrity

Chunk server 使用 checksum 来检测存储数据是否损坏。因为 GFS 有成千上万个节点，所以磁盘故障是很常见的。

对于读取操作，chunkserver在向请求者（无论是客户端还是另一个chunkserver）返回任何数据之前，会验证与读取范围重叠的数据块的校验和。因此，chunkserver不会将损坏传播到其他机器。
如果块与记录的校验和不匹配，chunkserver会向请求者返回错误并向master报告不匹配。作为响应，请求者将从其他副本读取，而master将从另一个副本克隆chunk。在有效的新副本就位后，master指示报告不匹配的chunkserver删除其副本。

Diagnostic Tools

GFS服务器生成诊断日志，记录许多重要事件（如chunkserver的上线和下线）以及所有RPC请求和回复。通过匹配请求与回复，并整理不同机器上的RPC记录，可以重建整个交互历史来诊断问题。