Google File System
论文笔记
介绍
GFS 是一个分布式文件系统，他和以前的分布式文件系统有着相同的目标：性能、可扩展性和可靠性。它的设计是由于 google的应用工作负载和技术环境的影响。举例：
组件错误是常态。因此，持续监测、错误检测、容错和自动回复必须成为系统的一部分。
文件大小是巨大的，通常在 GB 甚至 TB 大小。必须重新审视设计的假设和参数，例如 I/O 和 block size。
大多数文件是以通过添加新的数据而不是覆盖现有的数据来突变的。文件内部的随机写入是不存在。一旦写入，文件只被可读，而且是按顺序读取的。鉴于这种对巨大文件的访问模式，追加写入成为性能优化和原子性保证的焦点，而在客户端缓存数据块则失去了吸引力。
设计概述
假设
系统是被建立在那些非昂贵并且经常发生故障的商品组件上。它必须持续的监视、检查、容忍和恢复。
系统存储适中的大文件，预计有几百万个文件，每个文件有 100 MB 甚至更大。当然必须支持小文件，但不需要为他优化。
工作负载主要包括俩个部分：大型流式读取和小型随机读取。
工作负载还有许多将数据附加到文件的大型顺序写入。支持文件中任意位置的小写操作，但不一定要高效。
系统必须为多写文件实现高效的同步语义。
高持续带宽比低延迟更重要。
接口
GFS 提供了许多熟悉的文件系统接口，例如：create, delete, open, close, read and write。 此外，GFS 提供了 snapshot 和 record append 操作。Snapshot 提供以低成本创建文件或目录的副本。Record append 在保证原子性的前提下允许多个客户端同时将数据追加到同一个文件。
架构
GFS 集群是由一个 master 和许多 chunkservers 组成的，并由多个客户端访问。每个客户端通常都是运用户级服务器进程的 Linux 机器。 文件被分成固定大小的 chunk。每个 chunk 都是由 master 在创建 chunk 时分配的不可变且全局唯一64位 chunk handle标识的。 Chunkservers 将 chunk 作为 Linux 文件在本地磁盘存储，并读取或写入由 chunk handle 和 byte range 指定的 chunk data。 Master 维护所有文件系统的元数据。这包括命名空间、访问控制信息、从文件到块的映射以及块的当前位置。它还控制系统范围的活动，例如块租用管理、孤立块的垃圾收集以及块服务器之间的块迁移。Master 周期性地在 HeartBeat 消息中与每个 chunkserver 通信，给它指令并收集它的状态。 链接到每个应用程序的 GFS 客户端代码实现文件系统 API 并与主服务器和块服务器通信以代表应用程序读取或写入数据。 客户端与 master 交互以进行元数据操作，但所有数据承载通信直接进入 chunkservers。我们不提供 POSIX API，因此不需要连接到 Linux vnode 层。 客户端和 chunkserver 都不缓存文件数据。客户端缓存几乎没有什么好处，因为大多数应用程序流式传输大量文件或工作集太大而无法缓存。没有它们可以通过消除缓存一致性问题来简化客户端和整个系统。（然而，客户端会缓存元数据。）Chunkservers 不需要缓存文件数据，因为块存储为本地文件，因此 Linux 的缓冲区缓存已经将经常访问的数据保存在内存中。
Single Master
拥有一个单一的 master 极大地简化了我们的设计，并使 master 能够利用全局消息做出复杂的块放置和复制决策。 客户端永远不会通过 master 读写文件数据。相反，客户端询问 master 它应该联系哪些块服务器。它会在有限的时间内缓存此信息，并直接与 chunkservers 交互以进行许多后续操作。 参考图一简单解释一下读写：
首先，使用固定块大小，客户端将应用程序指定的文件名和字节偏移量转换为文件内的块索引。
然后，它向 master 发送一个包含文件名和块索引的请求。
Master 回复相应的块句柄和副本的位置。
客户端使用文件名和块索引作为键来缓存此信息。然后客户端向其中一个副本发送请求，最有可能是最近的副本。该请求指定块句柄和该块内的字节范围。在缓存信息过期或文件重新打开之前，对同一块的进一步读取不需要更多的客户端与主机交互。事实上，客户端通常会在同一个请求中请求多个块，而主服务器也可以包含紧跟在请求之后的块的信息。这些额外的信息几乎无需额外费用即可回避未来几次客户与主人的互动。
Chunk Size
GFS 选择了 64MB 作为块大小，这比经典的文件系统的块大小都要大很多。
巨大的块大小有很多优势：
首先，它减少了客户端与 master 交互的需要，因为对同一块的读写只需要 master 发出一次初始请求以获取块的位置信息。
其次，由于在大块上客户端更有可能在给定块上执行许多操作，因此它可以通过在延长的时间段内保持与 chunkserver 的持久 TCP 连接来减少网络开销。
第三，它减少了存储在 master 上的元数据的大小。
当然也有缺点，一个小文件由少量块组成，也许只有一个。如果许多客户端访问同一个文件，存储这些块的 chunkservers 可能会成为热点。实际上，热点并不是主要问题，因为我们的应用程序大多按顺序读取大型多块文件。 然而，当 GFS 首次被批处理队列系统使用时，热点确实出现了：一个可执行文件作为单块文件写入 GFS，然后同时在数百台机器上启动。存储此可执行文件的少数 chunkservers 因数百个同时请求而超载。我们通过以更高的复制因子存储此类可执行文件并使批处理队列系统错开应用程序启动时间来解决此问题。一个潜在的长期解决方案是允许客户端在这种情况下从其他客户端读取数据。
Metadata
Master 存储三种主要类型的元数据：文件和块命名空间、从文件到块的映射以及每个块的副本的位置。所有元数据都保存在 master 的内存中。前两种类型（命名空间和文件到块的映射）也通过将突变记录到存储在主服务器本地磁盘上并复制到远程机器上的 operation log 中来保持持久性。 使用日志可以让我们简单、可靠地更新主节点状态，并且不会在主节点崩溃时冒不一致的风险。Master 不会持久存储块位置信息。相反，它会在 master 启动时以及每当一个 chunkserver 加入集群时向每个 chunkserver 询问它的 chunks。
Consistency Model
GFS 的一致性模型相对宽松，很好的支持高度分布式的应用程序。
Guarantees by GFS
数据突变后文件区域的状态取决于突变的类型、成功或失败以及是否存在并发突变。
consistent：如果所有客户端将始终看到相同的数据，无论它们从哪个副本读取，则文件区域是一致的。
defined：
如果文件数据突变是一致的，并且客户将看到该突变的整体写入内容，则在文件突变后，这片区域是被定义的。
当突变在没有并发写入者干扰的情况下成功时，受影响的区域被定义（并且暗示一致）：所有客户端将始终看到突变写入的内容。
undefined and consistent：并发成功的突变使该区域未定义但保持一致：所有客户端都看到相同的数据，但它可能不会反映任何一个突变所写的内容。通常，它由来自多个突变的混合片段组成。
unconsistent：失败的突变会使区域不一致（因此也是未定义的）：不同的客户端可能会在不同的时间看到不同的数据。
数据突变可能是 writes 或 record appends。Writes 造成数据写入应用程序指定的文件偏移量。Record appends 导致数据被原子地追加至少一次，即使存在并发突变，但在 GFS 选择的偏移量处。
在一系列成功的变异之后，变异的文件区域保证 defined 并包含最后一次变异写入的数据。GFS 会做一下动作：
在其所有副本上以相同的顺序对一个块应用突变。
使用块版本号来检测任何已经过时的副本，因为它在其块服务器关闭时错过了突变。
System Interactions
我们设计的系统是为了尽量减少 master 对所有操作的参与。在此背景下，我们现在描述客户端、master 和 chunkserver 如何交互以实现数据突变、原子记录追加和快照。
Leases and Mutation Order
突变是更改块的内容或元数据的操作，例如写入或追加操作。每个突变都在块的所有副本上执行。我们使用租约来维护副本之间一致的突变顺序。Master 将块租约授予其中一个副本，我们称之为 primary。The primary 为块的所有突变选择一个序列顺序。应用突变时，所有副本都遵循此顺序。因此，全局变异顺序首先由 master 选择的租约授予顺序定义，并在租约内由 primary 分配的序列号定义。
客户端向 master 询问哪个 chunkserver 持有该块的当前租约以及其他副本的位置。如果没有块有租约，则 master 将租约授予它选择的副本（未显示）。
Master 回复 primary 的身份和其他（secondary）副本的位置。客户端缓存此数据以备将来更改。仅当 primary 变得不可访问或回复 primary 不再持有租约时，客户端才需要再次联系 primary。
客户端将数据推送到所有副本。客户端可以按任何顺序执行此操作。每个 chunkserver 都会将数据存储在内部 LRU 缓冲区缓存中，直到数据被使用或老化。通过将数据流与控制流解耦，我们可以通过基于网络拓扑调度昂贵的数据流来提高性能，而不管哪个 chunkserver 是主要的。
一旦所有副本都确认接收到数据，客户端就会向 primary 发送写入请求。该请求标识了之前推送到所有副本的数据。 The primary 为它收到的所有 mutations 分配连续的序列号，可能来自多个 clients，这提供了必要的序列化。它按序列号顺序将突变应用于其自己的本地状态。
primary 将写入请求转发给所有 secondary 副本。每个 secondary 都按照 primary 分配的相同序列号顺序应用突变。
The secondary 都回复 primary 表示已经完成操作。
The primary 要回复客户端。在任何副本中遇到的任何错误都会报告给客户端。如果出现错误，写入可能已在 primary 和任意子集的 secondary 上成功。（如果 primary 失败，它就不会被分配序列号并被转发。）客户端请求被认为失败，修改后的区域处于不一致状态。我们的客户端代码通过重试失败的突变来处理此类错误。它将在步骤 (3) 到 (7) 中进行几次尝试，然后再回退到从写入开始重试。
如果应用程序的写入很大或跨越块边界，GFS 客户端代码会将其分解为多个写入操作。它们都遵循上述控制流程，但可能会与其他客户端的并发操作交错和覆盖。因此，共享文件区域可能最终包含来自不同客户端的片段，尽管副本将是相同的，因为各个操作在所有副本上以相同的顺序成功完成。这使文件区域处于 consistent and undefined 的状态。
Data Flow
我们将数据流与控制流分离，以有效地使用网络。当控制从客户端流向主服务器，然后流向所有辅助服务器时，数据以流水线方式沿着精心挑选的 chunkservers 链线性推送。
Atomic Record Appends
Record append 是一种 mutation，它遵循上述提到的控制流，在 primary 上只有一点点额外的逻辑。客户端将数据推送到文件最后一个块的所有副本，然后将其请求发送到 primary。The primary 要检查将记录附加到当前块是否会导致块超过最大大小 (64 MB)。如果是这样，它将块填充到最大大小，告诉辅助节点也这样做，并回复客户端指示应该在下一个块上重试该操作。（记录追加被限制为最多最大块大小的四分之一，以将最坏情况的碎片保持在可接受的水平。）如果记录适合最大大小，这是常见的情况，primary 将数据附加到其副本 , 告诉 secondary 将数据写入它所在的确切偏移量，最后向客户端回复成功。
如果记录追加在任何副本上失败，客户端将重试该操作。因此，同一块的副本可能包含不同的数据，可能包括同一记录的全部或部分副本。GFS 不保证所有的副本都是字节相同的。它只保证数据作为一个原子单元至少被写入一次。这个属性很容易从简单的观察中得出，即对于报告成功的操作，数据必须在某个块的所有副本上以相同的偏移量写入。此外，在此之后，所有副本至少与记录末尾一样长，因此即使不同的副本后来成为 primary，任何未来的记录都将被分配更高的偏移量或不同的块。就我们的一致性保证而言，成功的记录追加操作写入数据的区域是定义的（因此是一致的），而中间区域是不一致的（因此是未定义的）。
Snapshot
快照操作几乎在瞬间复制文件或目录树（“源”），同时最大限度地减少正在进行的突变的任何中断。 我们的用户使用它来快速创建庞大数据集的分支副本（通常是这些副本的副本，递归地），或者在试验更改之前检查当前状态，这些更改可以在以后轻松提交或回滚。
当 master 收到一个快照请求时，它首先撤销对它要快照的文件中的块的任何未完成的租约。这确保了对这些块的任何后续写入都需要与 master 交互以找到租约持有者。这将使 master 有机会首先创建块的新副本。
租约被撤销或过期后，master 将操作记录到磁盘。然后，它通过复制源文件或目录树的元数据，将此日志记录应用于其内存状态。新创建的快照文件指向与源文件相同的块。
客户端在快照操作后第一次想要写入块 C 时，它会向 master 发送请求以查找当前的租约持有者。The master 注意到块 C 的引用计数大于 1。它推迟回复客户端请求，而是选择一个新的 chunk handle C'。然后它要求每个拥有 C 的当前副本的块服务器创建一个名为 C' 的新块。通过在与原始块相同的块服务器上创建新块，我们确保可以在本地复制数据，而不是通过网络（我们的磁盘大约是 100 Mb 以太网链路速度的三倍）。从这一点来看，请求处理与任何 chunk 的处理都没有什么不同：master 授予其中一个副本对新 chunk C' 的租约，并回复客户端，客户端可以正常写入该 chunk，不知道它是刚刚从现有块创建的。
Master Operation
master 执行所有命名空间操作。此外，它管理整个系统中的块副本：它做出放置决策、创建新块和副本、并协调各种系统范围的活动以保持块完全复制、平衡所有块服务器之间的负载以及回收未使用的存储。
Namespace Management and Locking
我们允许多个操作（例如：snapshot）处于活动状态，并对命名空间的区域使用锁以确保正确的序列化。
每个主操作在运行前都会获取一组锁。通常，如果它涉及 /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 的数据结构可以防止修改。名称上的读锁足以保护父目录不被删除。
Creation, Re-replication, Rebalancing
块副本的创建出于三个原因：chunk creation、re-replication 和 rebalancing。
当 master create 一个块时，它会选择放置最初为空的副本的位置。它考虑了几个因素。
我们希望将新副本放置在磁盘空间利用率低于平均水平的块服务器上。随着时间的推移，这将均衡跨块服务器的磁盘利用率。
我们想限制每个 chunkserver 上“最近”创建的数量。尽管创建本身很便宜，但它可以可靠地预测即将到来的大量写入流量，因为块是在写入需要时创建的，并且在我们的一次附加读取多次工作负载中，它们通常在完全写入后实际上变成只读的。
我们希望跨机架传播块的副本。
一旦可用副本的数量低于用户指定的目标，master 就会重新复制一个块。发生这种情况的原因有多种：chunkserver 变得不可用，它报告其副本可能已损坏，其中一个磁盘因错误而被禁用，或者复制目标增加。每个需要重新复制的块都根据几个因素确定优先级。一个是它离复制目标有多远。例如，我们对丢失两个副本的块给予比只丢失一个副本的块更高的优先级。此外，我们更喜欢首先重新复制活动文件的块，而不是属于最近删除的文件的块。最后，为了尽量减少故障对正在运行的应用程序的影响，我们提高了任何阻止客户端进程的块的优先级。
最后，master 定期重新平衡副本：它检查当前副本分布并移动副本以获得更好的磁盘空间和负载平衡。同样通过这个过程，master 逐渐填满一个新的 chunkserver，而不是立即用新的块和随之而来的大量写入流量淹没它。新副本的放置标准与上面讨论的类似。此外，master 还必须选择要删除的现有副本。一般来说，它更喜欢删除那些空闲空间低于平均水平的 chunkservers，以平衡磁盘空间的使用。
Garbage Collection
删除文件后，GFS 不会立即回收可用的物理存储空间。它只是在文件和块级别的常规垃圾收集期间懒惰地这样做。我们发现这种方法使系统更加简单和可靠。
Mechanism
当应用程序删除文件时，master 会像其他更改一样立即记录删除。然而，文件并没有立即回收资源，而是被重命名为包含删除时间戳的隐藏名称。在 master 定期扫描文件系统命名空间期间，如果这些隐藏文件已经存在超过三天（时间间隔是可配置的），它会删除它们。在此之前，该文件仍然可以在新的特殊名称下读取，并且可以通过将其重命名为正常名称来取消删除。 当隐藏文件从命名空间中删除时，它在内存中的元数据将被删除。这有效地切断了它与所有块的链接。
在块名称空间的类似常规扫描中，master 识别孤立块（即无法从任何文件访问的块）并擦除这些块的元数据。在定期与 master 交换的 HeartBeat 消息中，每个 chunkserver 报告它拥有的块的一个子集，master 回复所有不再存在于 master 的元数据中的块的标识。Chunkserver 可以自由删除这些块的副本。
Fault Tolerance And Diagnosis
我们在设计系统时面临的最大挑战之一是处理频繁的组件故障。组件的质量和数量共同使这些问题成为常态而不是例外：我们不能完全信任机器，也不能完全信任磁盘。组件故障可能导致系统不可用，或者更糟的是，数据损坏。我们讨论了我们如何应对这些挑战，以及我们在系统中内置的工具，以便在问题不可避免地发生时对其进行诊断。
High Availability
在 GFS 集群中的数百台服务器中，有些服务器在任何给定时间都注定不可用。 我们通过两个简单而有效的策略保持整个系统的高可用性：快速恢复和复制。
Fast Recovery
master 和 chunkserver 都被设计为恢复它们的状态并在几秒钟内启动，无论它们如何终止。实际上，我们不区分正常终止和异常终止；服务器通常只是通过终止进程来关闭。客户端和其他服务器在未完成的请求超时、重新连接到重新启动的服务器并重试时会遇到轻微的问题。
Chunk Replication
如前所述，每个块都被复制到不同机架上的多个块服务器上。用户可以为文件命名空间的不同部分指定不同的复制级别。默认值为三个。Master 根据需要克隆现有副本，以在 chunkservers 离线或通过校验和验证检测损坏的副本时保持每个块完全复制。尽管复制对我们很有帮助，但我们正在探索其他形式的跨服务器冗余，例如奇偶校验或纠删码，以满足我们不断增加的只读存储需求。我们预计在我们非常松散耦合的系统中实施这些更复杂的冗余方案具有挑战性但易于管理，因为我们的流量主要是追加和读取而不是小的随机写入。
Master Replication
复制 master state 以确保可靠性。它的操作日志和检查点被复制到多台机器上。只有在其日志记录已在本地和所有 master 副本上刷新到磁盘后，才认为对状态的更改已提交。为简单起见，一个 master 进程仍然负责所有变更以及后台活动，例如在内部更改系统的垃圾收集。当它失败时，它几乎可以立即重新启动。如果它的机器或磁盘出现故障，GFS 外部的监控基础设施会在别处启动一个新的 master，并使用复制的操作日志。客户只使用 master 的规范名称（例如 gfs-test），这是一个 DNS 别名，如果 master 被重新定位到另一台机器，则可以更改该别名。
此外，“shadow” master 提供对文件系统的只读访问，即使在 primary master 关闭时也是如此。它们是影子，而不是镜子，因为它们可能会稍微滞后于主节点，通常是几分之一秒。它们增强了未被主动改变的文件或不介意获得略微过时结果的应用程序的读取可用性。事实上，由于文件内容是从 chunkservers 读取的，应用程序不会观察到过时的文件内容。短窗口内可能过时的是文件元数据，如目录内容或访问控制信息。
为了让自己了解情况，shadow master 读取不断增长的操作日志的副本，并将与 primary master 完全相同的更改序列应用于其数据结构。与 master 一样，它在启动时（之后很少）轮询块服务器以定位块副本并与它们交换频繁的握手消息以监视它们的状态。 它仅依赖 primary master 来获取由 primary master 创建和删除副本的决定所导致的副本位置更新。
Data Integrity
每个 chunkserver 使用校验和来检测存储数据的损坏。鉴于 GFS 集群通常在数百台机器上有数千个磁盘，它经常会遇到磁盘故障，导致读取和写入路径上的数据损坏或丢失。我们可以使用其他块副本从损坏中恢复，但是通过跨块服务器比较副本来检测损坏是不切实际的。此外，不同的副本可能是合法的：GFS 突变的语义，特别是前面讨论的原子记录追加，不保证相同的副本。因此，每个 chunkserver 必须通过维护校验和来独立验证自己副本的完整性。
Diagnostic Tools
广泛而详细的诊断日志记录在问题隔离、调试和性能分析方面提供了不可估量的帮助，同时仅产生最低限度的成本。没有日志，就很难理解机器之间短暂的、不可重复的交互。GFS 服务器生成诊断日志，记录许多重要事件（例如 chunkservers 启动和关闭）和所有 RPC 请求和回复。这些诊断日志可以随意删除而不影响系统的正确性。但是，我们尽量在空间允许的范围内保留这些日志。
最后更新于
