GFS 论文笔记

Google 三驾马车之一

1. 介绍

列出了设计 GFS 的三大基本假设

• 首先，组件故障是一种常态，而不是例外。因此，持续监控、错误检测、容错和自动恢复必须与系统集成在一起。
• 其次，文件大小很大 ，因此，设计假设和参数(如I/O操作和块大小)必须重新考虑。
• 第三，大多数文件是通过追加新数据而不是覆盖现有数据来改变的

2. 设计摘要

系统由大量廉价的普通服务器组成，需要容错

负载基本是 大量的流式读取和小量随机读

高持续带宽比低延迟更重要。

此外，GFS还有快照和记录追加操作。

2.3 架构

GFS集群由单个主服务器（其实还有几个影子 master）和多个chunkserver组成，并由多个客户机访问，架构图如下所示：

文件被分成固定大小的块。每个块都由一个不可变且全局唯一的64位块句柄标识，该句柄是在创建块时由master分配的。Chunkservers将块作为Linux文件存储在本地磁盘上，并读取或写入由块句柄和字节范围指定的块数据。为了提高可靠性，每个块都被复制到多个chunkserver上。默认情况下，存储三个副本

master 主服务器维护所有文件系统元数据，主服务器定期与心跳消息中的每个块服务器通信，给它指令并收集它的状态。

客户端和chunkserver都不会缓存文件数据，然而，客户端会缓存元数据。

2.4 单 master

客户端从不通过主服务器读写文件数据。相反，客户端询问主服务器它应该联系哪个块服务器。它在有限的时间内缓存这些信息，并直接与chunkserver进行交互以进行许多后续操作。

然后，它向主服务器发送一个包含文件名和块索引的请求。主服务器使用相应的块句柄和副本的位置进行响应。客户端使用文件名和块索引作为键来缓存该信息。

直到缓存的信息过期或文件重新打开。

2.5 块大小

块大小的设计：

• 首先减少了客户与主机交互的需求

• 其次减少网络开销

• 第三，它减少了存储在主服务器上的元数据的大小。

一个小文件由少量块组成，可能只有一个块。

对于热点块的数据，我们通过使用较高的复制因子存储这些可执行文件，并使批处理队列系统错开应用程序的启动时间，解决了这个问题。

2.6 元数据

master 存储三种类型的元数据：文件和块名称空间、从文件到块的映射以及每个块副本的位置。

前两种类型(名称—块名称空间和文件到块的映射)也通过将突变记录到存储在master的本地磁盘上并复制到远程机器上的操作日志来保持持久化

master不会持久地存储块位置信息。相反，它会在主服务器启动时询问每个chunkserver关于它的chunk的信息，以及每当有chunkserver加入集群时。

2.6.1 内存数据结构

master 会定期扫描内存的元数据

这种定期扫描用于实现块垃圾收集、在chunkserver故障时的重新复制，以及块迁移以平衡负载和磁盘空间

2.6.2 块位置

块位置包含在每次的心跳中

2.6.3 操作日志

元数据唯一 的持久记录

master通过重放操作日志恢复文件系统状态。为了最小化启动时间，我们必须保持日志较小。每当日志超过一定的大小时，主检查点就会改变其状态，以便它可以通过从本地磁盘加载最新的检查点并在此之后只重放有限数量的日志记录来恢复。检查点是一种紧凑的类似b树的形式，可以直接映射到内存中，并用于名称空间查找，而不需要额外的解析。这进一步加快了恢复速度并提高了可用性。

恢复只需要最新的完整检查点和后续的日志文件。旧的检查点和日志文件可以*删除，但我们保留了一些以防止灾难发生。检查点期间的失败不会影响正确性，因为恢复代码会检测并跳过不完整的检查点。

2.7 一致性模型

GFS 为强一致性，通过使用 块版本号 来检测块的一致性和是否进行磁盘垃圾回收

GFS通过主服务器和所有块服务器之间的常规握手识别出失败的块服务器，并通过校验和检测数据损坏

2.7.2 应用的实现

GFS 一致性的实现手段：依赖追加而不是覆盖、检查点和写入自验证、自标识的记录。

读取器只验证和处理直到最后一个检查点的文件区域，该检查点已知处于已定义的状态。

读取器可以使用校验和识别并丢弃额外的填充和记录片段。

3. 系统交互

3.1 租约

我们使用租约来维持副本间一致的变异顺序。

primary为chunk的所有突变选择一个序列顺序。当应用突变时，所有的复制都遵循这个顺序。

这些扩展请求和授权由master和所有块服务器之间定期交换的HeartBeat消息承载。

master 和 主服务器之间存在租约，默认超时60s，是当主服务器在租约期间，就可以在心跳包中无限地延长租约时间；master 也可以在主服务器的租约期间进行租约撤销，如果主服务器失去和 master 的连接，master 也可以把租约用在从服务器上

GFS 的数据流如下图所示：

1. 客户端请求 master 拥有租约的主服务器地址，如果没有，则指定一个
2. master 返回主服务器标识以及从服务器的位置；客户端缓存数据，仅当主服务器不可达或不再持有租约
3. 客户端发送数据给所有副本，通过将控制信息和数据流解耦，可以根据网络拓扑对数据流调度，不用关心主从
4. 一旦所有副本接收数据后，客户端发送写请求到主服务器，主服务器将接收到的所有突变编号并按序应用到本地
5. 主服务器转发写请求到所有副本，每个副本按照同样编号序应用突变
6. 副本成功后返回成功给主服务器
7. 任意副本出错都将返回错误给客户端，有可能最终出错了但是主和部分从是成功；若主服务器出错，则不会应用到副本上；目前应对出错的办法是重试

对过大的写请求，如跨 chunk，客户端还会分成几个操作进行

3.2 数据流

数据沿着块服务器链线性推送

每台机器都将数据转发到网络拓扑中“最近的”没有接收数据的机器。

我们的网络拓扑结构非常简单，可以从IP地址准确地估计“距离”。

一旦chunkserver接收到一些数据，它立即开始转发。

在没有网络拥塞的情况下，将B字节传输到R副本的理想运行时间是B/T + RL，其中T是网络吞吐量，L是两台机器之间传输字节的延时。

3.3 原子数据追加

如果客户端使用传统的写操作，则需要额外复杂和昂贵的同步，例如通过分布式锁管理器。

Record append是一种变体，它遵循3.1节中的控制流，在主节点上只添加了一点额外的逻辑。

块碎片

客户端将数据推入文件最后一块的所有副本，然后将请求发送给主服务器。主程序检查将记录追加到当前块是否会导致块超过最大大小(64 MB)。如果是，它将块填充到最大大小，告诉辅助程序做同样的事情，并回复客户机，指示应该在下一个块上重试操作。(Record append被限制为最多为最大块大小的四分之一，以使最坏情况的碎片保持在可接受的水平。)

一致性保证

根据我们的一致性保证(antees)，成功记录追加操作写入数据的区域是定义的(因此是一致的)，而插入的区域是不一致的(因此是未定义的)。

3.4 快照

快照操作几乎是瞬间复制一个文件或一个目录树(“源”)，同时最小化正在进行的突变的任何中断。

像AFS[5]一样，我们使用标准的写时复制技术来实现快照

4. master 操作

master 执行如下操作：

它做出放置决策，创建新的块和副本，并协调各种系统范围的活动，以保持块完全复制，在所有chunkserver之间平衡负载，并回收未使用的存储

4.1 命名空间管理和锁

master 允许多个操作处于活动状态，并在名称空间的区域上使用锁以确保适当的序列化

GFS逻辑上将其命名空间表示为一个将完整路径名映射到元数据的查找表。使用前缀压缩，可以有效地在内存中表示该表。命名空间树中的每个节点(无论是绝对文件名还是绝对目录名)都有一个关联的读写锁。

每个主操作在运行之前都会获得一组锁。通常，如果涉及/d1/d2/…/dn/leaf，它将获得目录名/d1， /d1/d2，…, / d1、d2 /……/d1/d2/…/dn/叶上的读锁或写锁。注意，根据操作的不同，leaf可能是一个文件或目录。

现在我们演示这种锁定机制如何防止在/home/user被快照到/save/user时创建文件/home/user/foo。快照操作获得/home和/save上的读锁，以及/home/user和/save/user上的写锁。文件创建ac-查询/home和/home/user上的读锁，以及/home/user/foo上的写锁。这两个操作将被正确地序列化，因为它们试图在/home/user上获得冲突的锁。在父目录上创建文件不需要写锁，因为没有目录或类似inode的数据结构可以保护不被修改。名称上的读锁足以保护父目录不被删除。

它们首先在名称空间树中按级别排序，并按字典顺序排列在同一级别内。

4.2 副本放置

我们还必须在机架上放置块的复制

它还意味着一个块的流量(尤其是读)可以利用多个机架的聚合带宽。另一方面，写流量必须流经多个机架，这是我们愿意做的一种权衡。

4.3 创建，重复制，再平衡

创建块副本有三个原因:块创建、重新复制和再平衡。

1. 我们希望在磁盘空间利用率低于平均水平的chunkserver上放置新的副本。
2. 我们想要限制每个块服务器上“最近”创建的数量。
3. 如上所述，我们希望将块的副本分散到各个机架上。

chunkserver变得不可用，它报告它的副本可能已损坏，它的一个磁盘由于错误而被禁用，或复制目标增加。需要重新复制的每个块都根据几个因素进行了优先级排序。一个是它离复制目标有多远。例如，我们给丢失两个副本的块比只丢失一个副本的块更高的优先级。此外，我们更倾向于首先为活动文件重新复制块，而不是那些属于最近删除的文件的块(参见4.4节)。

均衡磁盘空间利用率，限制任何单个chunkserver上的活动克隆操作，并跨机架分布副本。为了防止克隆流量超过客户机流量，主服务器对集群和每个块服务器的活动克隆操作数量进行了限制。此外，每个chunkserver通过对源chunkserver的读请求进行节流来限制它在每个克隆操作上花费的带宽。

master 定期检查当前副本分布并移动副本以获得更好的磁盘空间和负载平衡。

此外，主服务器还必须选择要删除的现有副本。通常，它倾向于删除空闲空间低于平均水平的chunkserver上的那些服务器，以便均衡磁盘空间使用。

4.4 垃圾回收

删除文件后，GFS不会立即回收可用的物理存储。它只在文件和块级别的常规垃圾收集期间惰性地这样做。

4.4.1 机制

不是立即回收资源，文件只是重命名为一个隐藏的名称，其中包括删除时间戳。在主服务器对文件系统名称空间的常规扫描期间，如果隐藏文件存在超过三天(间隔是可配置的)，它将删除这些隐藏文件。

在类似的块命名空间的常规扫描中，主块标识孤立的块(即从任何文件无法访问的块)，并擦除这些块的元数据。在与主服务器定期交换的HeartBeat消息中，每个chunkserver报告它所拥有的块的子集，主服务器用不再出现在主服务器元数据中的所有块的标识进行响应。

回收策略利弊

1. 垃圾回收简单可靠
2. master 负责，成本摊销
3. 给物理删除提供缓冲时间

主要的缺点是，当存储时间很紧时，延迟有时会妨碍用户调整使用。重复创建和删除临时文件的应用程序可能无法立即重用存储。如果已删除文件再次显式删除，我们通过加速存储回收来解决这些问题。

4.5 陈旧副本判断

对于每个块，主块维护一个块版本号，以区分最新的副本和陈旧的副本。

每当主服务器授予块的新租约时，它就增加块的版本号并通知最新的副本。

主服务器在其常规垃圾收集中删除过时的副本。

客户机或chunkserver在执行操作时验证版本号，以便始终访问最新的数据。

用版本号决定一个 chunk 的更新状态

5. 容错与诊断

5.1 高可用

快速恢复和复制

5.1.2 块复制

当chunkserver离线或通过校验和转换(参见5.2节)检测损坏副本时，主克隆现有副本，以保持每个块完全复制。

使用奇偶码或者擦除码

5.1.3 master 复制

它的操作日志和检查点被复制到多台机器上。只有当其日志记录在本地和所有主副本上刷新到磁盘后，才认为对状态的更改已提交

如果它的机器或磁盘出现故障，监视GFS外部的基础设施将在其他地方启动一个新的主进程，并使用复制的操作日志。

而且，“影子”主服务器提供对文件系统的只读访问，即使主服务器宕机。

5.2 数据完整性

每个chunkserver使用校验和来检测存储数据的损坏。

此外，不同的副本可能是合法的:GFS突变的语义，特别是前面讨论的原子记录附加，并不保证相同的副本。因此，每个块服务器必须通过主包含校验和独立地验证自己副本的完整性。

与其他元数据一样，校验和保存在内存中，并通过日志持久化存储，与用户数据分开。

对于读操作，chunkserver在将任何数据返回给请求者(无论是客户端还是另一个chunkserver)之前，验证重叠读范围的数据块的校验和。

在一个有效的新副本就位后，主服务器指示报告不匹配的chunkserver删除它的副本。

GFS客户端代码通过尝试在校验和块边界对齐读取进一步减少了这个开销。

我们只是增量地更新最后部分校验和块的校验和，并为append填充的任何全新校验和块计算新的校验和。

如果我们在部分覆盖第一个和最后一个块之前不验证它们，新的校验和可能隐藏存在于未被覆盖区域的损坏。

在空闲期间，chunkserver可以扫描和验证非活动块的内容。这允许我们检测很少被读取的块中的腐败。

5.3 诊断工具

通过将请求与应答进行匹配，并在不同的机器上整理RPC记录，我们可以重建整个交互历史来诊断问题。

log 是顺序和异步的

6. 测试

保存在master上的元数据要小得多，只有几十mb，或者平均每个文件大约100字节。这与我们的假设一致，即在实践中，主内存的大小不会限制系统的容量。大多数文件元数据是以前缀压缩形式存储的文件名。其他元数据包括文件所有权和权限，从文件到块的映射，以及每个块的当前版本。此外，我们为每个块存储当前的复制位置和一个用于实现写时复制的引用计数。

我们已经改变了主数据结构，允许通过名称空间进行有效的二进制搜索。

7. 经验

早些时候，由于fsync()的开销，我们在Linux 2.2内核上遇到了一些问题。它的开销与文件的大小成比例，而不是与修改部分的大小成比例。对于我们的大型操作日志来说，这是一个问题，特别是在我们实现检查点之前。我们使用同步写来解决这个问题，最终迁移到Linux 2.4。

另一个Linux问题是单个读写器锁，地址空间中的任何线程在从磁盘调入(读写器锁)或在mmap()调用中修改地址空间(写器锁)时都必须持有该锁。我们发现系统在低负载下出现了短暂的超时，并努力查找资源瓶颈或零星的硬件故障。甚至，我们发现，当磁盘线程在对先前映射的数据进行分页时，这个锁阻塞了主网络线程将新数据映射到内存。由于我们主要受到网络接口而不是内存复制带宽的限制，