谷歌分布式文件系统(GFS)
谷歌分布式文件系统(GFS)
摘要
我们设计并实现了 Google 文件系统（Google File System，GFS），这是一个可扩展的分布式文件系统，旨在支持大规模分布式数据密集型应用程序。它在使用廉价的商品硬件的同时提供了容错能力，并且能够为大量客户端提供高的整体性能。
虽然它与之前的分布式文件系统在许多目标上有相似之处，但我们的设计是基于对当前和预期技术环境及应用工作负载的观察，这些观察与一些早期文件系统假设存在明显的不同。这促使我们重新审视传统的选择，并探索了与之大相径庭的设计方案。
该文件系统已成功满足我们的存储需求，并广泛部署于 Google 内部，作为我们服务中用于生成和处理数据的存储平台，同时也支持需要大量数据集的研究和开发工作。目前最大的集群提供了数百 TB 的存储，分布在数千个磁盘和千余台机器上，并且由数百个客户端同时访问。
在本文中，我们介绍了旨在支持分布式应用程序的文件系统接口扩展，讨论了我们设计的各个方面，并报告了来自微基准测试和实际使用场景的测量结果。
1.介绍
我们设计并实现了谷歌文件系统（Google File System，GFS），以满足谷歌数据处理需求的快速增长。GFS 与之前的分布式文件系统有许多相同的目标，如性能、可扩展性、可靠性和可用性。然而，其设计是由对我们的应用工作负载以及当前和预期的技术环境的关键观察所驱动的，这与一些早期的文件系统设计假设明显不同。我们重新审视了传统的选择，并在设计空间中探索了截然不同的方向。
- 组件故障常态化：文件系统由大量廉价部件组成，故障不可避免，必须具备监控、容错和自动恢复能力。
- 文件大小巨大：文件通常为GB级，且数据集快速增长，管理数十亿个大文件是一个挑战，需要重新设计I/O操作和块大小。
- 文件修改方式：大多数文件通过追加数据而非随机修改，且写完之后通常是顺序读取，因此优化追加操作和保证原子性成为关键，客户端缓存不再具有优势。
- 设计应用程序与文件系统 API 的协同工作：通过放宽 GFS 的一致性模型，简化了文件系统，同时减轻了应用程序负担。引入原子追加操作使多个客户端能同时向文件追加内容，无需额外同步。
目前，多个谷歌文件系统（GFS）集群被部署用于不同的目的。最大的集群拥有超过 1000 个存储节点、超过 300TB 的磁盘存储，并且持续不断地被不同机器上的数百个客户端大量访问。
2.设计概述
2.1 假设
在为我们的需求设计文件系统时，一些既带来挑战又带来机遇的假设为我们提供了指导。我们在前面已经提及了一些关键观察结果，现在更详细地阐述我们的假设。
- 该系统由许多容易出现故障的便宜商品组件构建而成。它必须持续不断地自我监测，并在日常情况下迅速检测、容忍和从组件故障中恢复。
- 系统存储数量适中的大文件。我们预计会有几百万个文件，每个文件通常为 100MB 或更大。多 GB 的文件是常见情况，应该得到高效管理。小文件也必须得到支持，但我们无需针对小文件进行优化。
- 工作负载主要由两种读取类型组成：大型流式读取和小型随机读取。在大型流式读取中，单个操作通常读取几百 KB，更常见的是 1MB 或更多。来自同一客户端的连续操作通常会读取文件的连续区域。小型随机读取通常在某个任意偏移处读取几 KB。注重性能的应用程序通常会对其小型读取进行批处理和排序，以便稳定地遍历文件，而不是来回读取。
- 工作负载也有许多大型的顺序写入，向文件追加数据。典型的操作大小与读取操作类似。文件一旦写入，就很少再次被修改。支持在文件中的任意位置进行小型写入，但不一定要高效。
- 系统必须为同时向同一文件追加内容的多个客户端高效地实现明确界定的语义。我们的文件通常被用作生产者消费者队列或用于多路合并。数百个生产者（每台机器上运行一个）将同时向一个文件追加内容。以最小的同步开销实现原子性是至关重要的。文件可能在以后被读取，或者一个消费者可能同时正在读取该文件。
- 高持续带宽比低延迟更重要。我们的大多数目标应用程序优先考虑以高速度批量处理数据，而很少有应用程序对单个读或写操作有严格的响应时间要求。
2.2 接口
GFS 提供了一个熟悉的文件系统接口，尽管它没有实现像 POSIX 这样的标准 API。文件在目录中按层次结构组织，并通过路径名进行标识。我们支持常见的创建、删除、打开、关闭、读取和写入文件的操作。
此外，GFS 具有快照和记录追加操作。快照可以以较低的成本创建文件或目录树的副本。记录追加允许多个客户端同时向同一个文件追加数据，同时保证每个客户端追加操作的原子性。它对于实现多路合并结果以及生产者 - 消费者队列非常有用，许多客户端可以同时向其追加数据而无需额外的锁定。我们发现这些类型的文件在构建大型分布式应用程序中非常有价值。快照和记录追加分别在第 3.4 节和第 3.3 节中进一步讨论。
2.3 架构
一个 GFS 集群由一个主服务器和多个块服务器组成，并由多个客户端访问，如图 1 所示。这些通常都是运行用户级服务器进程的普通 Linux 机器。只要机器资源允许，并且可以接受由于运行可能不稳定的应用程序代码而导致的较低可靠性，那么在同一台机器上同时运行块服务器和客户端是很容易的。
文件被分成固定大小的块。每个块由一个不可变且全局唯一的 64 位块句柄标识，该句柄在块创建时由主服务器分配。块服务器将块作为 Linux 文件存储在本地磁盘上，并根据块句柄和字节范围读取或写入块数据。为了可靠性，每个块在多个块服务器上进行复制。默认情况下，我们存储三个副本，不过用户可以为文件命名空间的不同区域指定不同的复制级别。
主服务器维护所有的文件系统元数据。这包括命名空间、访问控制信息、从文件到块的映射以及块的当前位置。它还控制全系统范围的活动，如块租约管理、孤立块的垃圾回收以及块服务器之间的块迁移。主服务器通过定期发送的心跳消息与每个块服务器进行通信，以给予其指令并收集其状态。
链接到每个应用程序中的 GFS 客户端代码实现文件系统 API，并代表应用程序与主服务器和块服务器进行通信以读取或写入数据。客户端与主服务器进行元数据操作交互，但所有携带数据的通信都直接指向块服务器。我们不提供 POSIX API，因此无需挂接到 Linux 的虚拟节点层。
客户端和块服务器都不缓存文件数据。客户端缓存几乎没有什么好处，因为大多数应用程序是流式读取巨大的文件，或者其工作集太大而无法被缓存。不进行缓存简化了客户端和整个系统，消除了缓存一致性问题。（然而，客户端确实会缓存元数据。）块服务器不需要缓存文件数据，因为块是以本地文件的形式存储的，所以 Linux 的缓冲区缓存已经将频繁访问的数据保存在内存中。
2.4 单个主服务器
为了简化我们的设计，我们采用了单主服务器模型。为了减少它在读取和写入中的参与，以免它成为瓶颈，客户端的交互流程如下：
- 客户端询问主服务器它应该联系哪些块服务器，并在有限的时间内缓存此信息
- 在后续操作中直接与块服务器进行交互
让我们参照图 1 解释一个简单读取操作的交互过程。
- 首先，利用固定的块大小，客户端将应用程序指定的文件名和字节偏移量转换为文件中的块索引。然后，它向主服务器发送一个包含文件名和块索引的请求。主服务器用相应的块句柄和副本的位置进行回复。客户端以文件名和块索引作为键缓存此信息。
- 然后，客户端向其中一个副本发送请求，很可能是最近的一个。请求指定块句柄和该块内的字节范围。对同一块的进一步读取在缓存信息过期或文件重新打开之前不需要更多的客户端 - 主服务器交互。实际上，客户端通常在同一个请求中请求多个块，并且主服务器还可以包括紧接在请求的块之后的那些块的信息。这些额外信息几乎无需额外成本就避免了未来的几次客户端 - 主服务器交互。
2.5 块大小
块大小是关键设计参数之一。我们选择了 64 兆字节（64 MB），这比典型的文件系统块大小要大得多。每个块副本在块服务器上作为一个普通的 Linux 文件存储，并且仅在需要时进行扩展。
惰性空间分配避免了因内部碎片而造成的空间浪费，内部碎片问题可能是人们对如此大的块大小最主要的反对理由。
较大的块大小具有几个重要优势。
- 首先，它减少了客户端与主服务器交互的需求，因为对同一个块的读写操作只需向主服务器发起一次初始请求以获取块位置信息。由于应用程序大多是按顺序读写大文件，所以这种减少对于我们的工作负载来说尤为显著。即使是对于小的随机读取，客户端也可以轻松地缓存数太字节（TB）工作集的所有块位置信息。
- 其次，由于在一个大块上，客户端更有可能对给定的块执行许多操作，因此它可以通过在较长时间段内与块服务器保持持久的 TCP 连接来减少网络开销。
- 第三，它减小了存储在主服务器上的元数据的大小。这使得我们能够将元数据保存在内存中，进而带来我们将在 2.6.1 节讨论的其他优势。
另一方面，即使采用了惰性空间分配，较大的块大小也有其劣势。一个小文件由少量的块组成，可能只有一个块。如果有许多客户端访问同一个文件，存储这些块的块服务器可能会成为热点。实际上，热点问题并不是一个主要问题，因为我们的应用程序大多是按顺序读取由多个块组成的大文件。
然而，当批处理队列系统首次使用谷歌文件系统（GFS）时，确实出现了热点问题：一个可执行文件作为单块文件写入 GFS，然后在同一时间在数百台机器上启动。存储这个可执行文件的少数几块服务器因数百个同时发出的请求而超载。我们通过以更高的复制因子存储此类可执行文件以及让批处理队列系统错开应用程序启动时间来解决了这个问题。一个潜在的长期解决方案是允许客户端在这种情况下从其他客户端读取数据。
惰性分配是什么？
这里的惰性分配（lazy allocation）指的是在实际需要时才分配存储空间，而不是预先为每个块分配完整的64 MB空间。换句话说，当块大小设置为64 MB时，系统不会立即分配整个64 MB的磁盘空间，而是等到数据真正写入时才逐步扩展块的大小，直到达到64 MB的上限。
2.6 元数据
主服务器存储三大类元数据：
- 文件和数据块命名空间
- 文件到数据块的映射关系
- 每个数据块副本的存放位置。
所有元数据都保存在主服务器的内存中。前两类（命名空间和文件到数据块的映射关系）还会通过将变更记录到操作日志中实现持久化保存，该操作日志存储在主服务器的本地磁盘上，并在远程机器上进行复制。使用日志可以让我们简便、可靠地更新主服务器的状态，而且在主服务器发生崩溃的情况下不会有出现数据不一致的风险。主服务器不会持久化存储数据块的位置信息。相反，它会在主服务器启动时以及每当有数据块服务器加入集群时，向每个数据块服务器询问其管理的数据块的相关信息。
2.6.1 内存中的数据结构
由于元数据存储在内存中，主服务器的操作速度很快。此外，主服务器在后台定期扫描其整个状态既容易又高效。这种定期扫描用于实现数据块垃圾回收、在数据块服务器出现故障时进行重新复制，以及数据块迁移以平衡各数据块服务器间的负载和磁盘空间使用情况。第 4.3 节和第 4.4 节将进一步讨论这些操作。
这种仅使用内存的方式可能存在的一个担忧是，数据块的数量，进而整个系统的容量，会受到主服务器内存大小的限制。但在实际应用中，这并非一个严重的局限。主服务器为每 64MB 的数据块维护的元数据不到 64 字节。大多数数据块是满的，因为大多数文件包含多个数据块，只有最后一个数据块可能是部分填充的。同样，文件命名空间数据通常每个文件所需字节数也不到 64 字节，因为它使用前缀压缩技术对文件名进行了紧凑存储。
如果有必要支持更大的文件系统，为主服务器增加额外内存的成本相对于我们通过将元数据存储在内存中所获得的简单性、可靠性、性能和灵活性而言，只是一个很小的代价。
这里提到了前缀压缩，我的理解是很多文件的路径的前缀相同，可以帮这些相同的前缀提取出来，对于文件，只需要存储其差异性的部分。
例如
/data/app1/data.txt
/data/app1/img.txt
/data/app1/code.txt
这里三个记录的公共前缀是/data/app1/，因此每条记录可以转化为下面的存储方式:
prefix id：1， prefix ： /data/app1/
file1：data.txt prefix id: 1
file2：img.txt prefix id: 1
file3：code.txt prefix id: 1
2.6.2 数据块位置
主服务器不会持久记录哪些数据块服务器存有给定数据块的副本。它只是在启动时向数据块服务器轮询获取该信息。此后，主服务器能够保持自身信息的及时更新，因为它控制着所有数据块的放置，并通过定期的心跳消息监控数据块服务器的状态。
我们最初曾尝试在主服务器上持久保存数据块位置信息，但后来认为在启动时以及此后定期从数据块服务器请求该数据要简单得多。这样就消除了在数据块服务器加入和离开集群、更名、出现故障、重启等情况下保持主服务器和数据块服务器同步的问题。在一个拥有数百台服务器的集群中，这些情况发生得太过频繁。
理解这一设计决策的另一种方式是要认识到，对于其自身磁盘上存有或未存有哪些数据块，数据块服务器拥有最终决定权。试图在主服务器上维护关于此信息的一致视图是没有意义的，因为数据块服务器上的错误可能导致数据块自行消失（例如，磁盘可能出现故障并被停用），或者操作员可能会重命名数据块服务器。
2.6.3 操作日志
操作日志包含关键元数据变更的历史记录。它对谷歌文件系统（GFS）至关重要。它不仅是元数据唯一的持久记录，而且还充当了一条逻辑时间线，用于定义并发操作的顺序。文件和数据块，以及它们的版本（见第 4.5 节），都是通过其创建时的逻辑时间来进行唯一且永久的标识。
由于操作日志至关重要，我们必须可靠地存储它，并且在元数据变更被持久化之前，不能让客户端看到这些变更。否则，即使数据块本身完好无损，我们实际上也会丢失整个文件系统或近期客户端的操作。因此，我们将其在多台远程机器上进行复制，并且只有在将相应的日志记录在本地和远程都刷新到磁盘之后，才会对客户端操作做出响应。主服务器在刷新之前会将若干日志记录合并成批，从而减少刷新和复制操作对整个系统吞吐量的影响。
主服务器通过重放操作日志来恢复其文件系统状态。为了尽量缩短启动时间，我们必须控制日志的大小。每当日志增长超过一定规模时，主服务器就会对其状态进行检查点设置，这样它就可以通过从本地磁盘加载最新的检查点，并只重放此后有限数量的日志记录来实现恢复。检查点采用一种类似紧凑 B 树的形式，可以直接映射到内存中，并且无需额外解析就可用于命名空间查找。这进一步加快了恢复速度并提高了可用性。
因为创建一个检查点可能需要一些时间，所以主服务器的内部状态在构建方式上使得可以在不延迟传入变更的情况下创建新的检查点。主服务器会切换到一个新的日志文件，并在一个单独的线程中创建新的检查点。新的检查点包含切换之前的所有变更。对于拥有几百万个文件的集群来说，大约一分钟左右就可以创建好一个新的检查点。创建完成后，它会在本地和远程都写入磁盘。
恢复操作只需要最新的完整检查点以及后续的日志文件。较旧的检查点和日志文件可以自由删除，不过我们会保留一些以防万一出现灾难性情况。在设置检查点过程中出现故障不会影响正确性，因为恢复代码能够检测并跳过不完整的检查点。
2.7 一致性模型
谷歌文件系统（GFS）采用了一种宽松的一致性模型，该模型能很好地支持我们高度分布式的应用程序，而且在实现上仍然相对简单高效。现在我们来讨论一下 GFS 的保证以及这些保证对应用程序意味着什么。我们还会着重说明 GFS 是如何维持这些保证的，但具体细节会留到本文的其他部分再阐述。
2.7.1 GFS 的保证
文件命名空间的变更（例如文件创建）是原子性的。它们由主服务器专门处理：命名空间锁保证了原子性和正确性（见 4.1 节）；主服务器的操作日志定义了这些操作的全局全序（见 2.6.3 节）。
数据变更后文件区域的状态取决于变更的类型、变更是否成功以及是否存在并发变更。表 1 对此进行了总结。如果所有客户端无论从哪个副本读取，看到的总是相同的数据，那么一个文件区域就是一致的。如果在文件数据变更后一个区域是一致的，并且客户端能完整看到变更所写入的内容，那么这个区域就是已定义的。当一次变更在没有并发写操作干扰的情况下成功完成时，受影响的区域就是已定义的（也就意味着是一致的）：所有客户端将始终能看到变更所写入的内容。并发的成功变更会使区域处于未定义但一致的状态：所有客户端看到的是相同的数据，但这些数据可能无法反映任何一次单独变更所写入的内容。通常，它是由来自多次变更的混合片段组成的。一次失败的变更会使区域变得不一致（因此也是未定义的）：不同的客户端在不同时间可能会看到不同的数据。下面我们将描述我们的应用程序如何区分已定义区域和未定义区域。应用程序无需进一步区分不同类型的未定义区域。
数据变更可以是写入操作或记录追加操作。写入操作会按照应用程序指定的文件偏移量写入数据。记录追加操作即使在存在并发变更的情况下，也能保证数据（即 "记录"）至少被原子性地追加一次，但偏移量由 GFS 选定（见 3.3 节）。（相比之下，"常规" 追加仅仅是在客户端认为是当前文件末尾的偏移量处进行写入操作。）偏移量会返回给客户端，并标记包含该记录的已定义区域的起始位置。此外，GFS 可能会在其间插入填充数据或记录副本。它们所占据的区域被认为是不一致的，并且通常与用户数据量相比是微不足道的。
在一系列成功的变更之后，发生变更的文件区域保证是已定义的，并且包含最后一次变更所写入的数据。GFS 通过以下方式实现这一点：(a) 在所有副本上按照相同顺序对数据块应用变更（见 3.1 节）；(b) 使用数据块版本号来检测任何因所在数据块服务器停机而错过变更从而变得陈旧的副本（见 4.5 节）。陈旧的副本永远不会参与变更，也不会提供给向主服务器询问数据块位置的客户端。它们会尽早被当作垃圾回收。
由于客户端会缓存数据块位置，它们可能在该信息刷新之前从陈旧的副本读取数据。这个时间窗口受缓存条目超时时间和下次打开文件的限制，下次打开文件时会清除该文件的所有数据块信息缓存。而且，由于我们的大多数文件都是只追加的，一个陈旧的副本通常会返回一个过早的数据块末尾，而不是过时的数据。当读取器重试并联系主服务器时，它将立即获得当前的数据块位置。
在一次成功变更很久之后，组件故障当然仍有可能损坏或破坏数据。GFS 通过主服务器和所有数据块服务器之间的定期握手来识别出现故障的 数据块服务器，并通过校验和来检测数据是否损坏（见 5.2 节）。一旦出现问题，数据会尽快从有效副本中恢复（见 4.3 节）。只有在 GFS 能够做出反应之前（通常在几分钟内）所有副本都丢失的情况下，一个数据块才会不可逆转地丢失。即使在这种情况下，它也是变为不可用，而不是损坏：应用程序会收到明确的错误提示，而不是损坏的数据。
2.7.2 对应用程序的影响
GFS 应用程序可以通过一些原本就因其他目的而需要的简单技术来适应这种宽松的一致性模型：依靠追加操作而非覆盖操作、设置检查点以及写入可自我验证、自我标识的记录。
实际上，我们几乎所有的应用程序都是通过追加而不是覆盖的方式来修改文件的。在一种典型的用法中，写入程序会从头到尾生成一个文件。在写入所有数据后，它会以原子操作将文件重命名为一个永久名称，或者定期对已成功写入的内容设置检查点。检查点可能还包括应用程序级别的校验和。读取程序只会验证和处理到最后一个检查点为止的文件区域，因为已知该区域处于已定义状态。无论一致性和并发问题如何，这种方法对我们来说效果都很不错。与随机写入相比，追加操作的效率要高得多，而且对应用程序故障的适应能力也更强。设置检查点允许写入程序进行增量重启，并防止读取程序处理从应用程序角度来看仍未完成的已成功写入的文件数据。
在另一种典型用法中，许多写入程序会并发地向一个文件追加内容以获取合并结果，或者将其作为一个生产者 - 消费者队列。记录追加操作的 "至少追加一次" 语义保留了每个写入程序的输出。读取程序对偶尔出现的填充数据和重复数据的处理方式如下。写入程序准备的每个记录都包含诸如校验和之类的额外信息，以便可以验证其有效性。
读取程序可以利用校验和来识别并丢弃额外的填充数据和记录片段。如果它无法容忍偶尔出现的重复数据（例如，如果它们会触发非幂等操作），它可以利用记录中的唯一标识符将其过滤掉，反正通常也需要这些唯一标识符来为相应的应用程序实体（如网页文档）命名。这些用于记录输入 / 输出的功能（除了去除重复数据）都包含在我们的应用程序共享的库代码中，并且适用于谷歌的其他文件接口实现。这样一来，相同的记录序列，加上极少出现的重复数据，总是会被传送给记录读取程序。
3.系统交互
我们对系统进行了设计，目的是在所有操作中尽量减少主服务器的参与。基于这一背景，我们现在来描述客户端、主服务器和数据块服务器是如何相互作用以实现数据变更、原子记录追加以及快照功能的。
3.1 租约与变更顺序
变更指的是改变数据块内容或元数据的操作，比如写入或追加操作。每一次变更都会在数据块的所有副本上执行。我们通过租约来维持各副本间一致的变更顺序。主服务器会将数据块租约授予其中一个副本，我们将这个副本称为主副本。主副本会为对该数据块的所有变更选定一个串行顺序。所有副本在应用变更时都遵循这个顺序。因此，全局的变更顺序首先由主服务器选择的租约授予顺序来定义，而在一个租约范围内则由主副本分配的序列号来定义。
租约机制的设计旨在将主服务器的管理开销降至最低。租约的初始超时时间为 60 秒。然而，只要数据块正在被变更，主副本就可以向主服务器请求延长租约，而且通常情况下能够无限期地获得延长。这些延长请求和批准会附带在主服务器和所有数据块服务器定期交换的心跳消息中。主服务器有时可能会在租约到期之前尝试撤销租约（例如，当主服务器想要禁止对正在重命名的文件进行变更时）。即使主服务器与主副本失去了通信，在旧租约到期后，它也可以安全地将新租约授予另一个副本。
在图 2 中，我们通过跟踪一次写入操作的控制流程（按这些编号步骤）来说明这一过程：
1.客户端向主服务器询问哪个数据块服务器持有该数据块的当前租约以及其他副本的位置。如果没有任何服务器持有租约，主服务器会将租约授予它选定的一个副本（图中未展示这一情况）。
2.主服务器回复告知主副本的标识以及其他（从）副本的位置。客户端会缓存这些数据以便日后进行变更操作。只有当主副本无法访问或者回复说它不再持有租约时，客户端才需要再次联系主服务器。
3.客户端将数据推送到所有副本。客户端可以按任意顺序进行推送。每个数据块服务器会将数据存储在内部的最近最少使用（LRU）缓冲缓存中，直到数据被使用或因超时而被清除。通过将数据流与控制流解耦，我们可以根据网络拓扑结构来安排成本较高的数据流，从而提高性能，而无需考虑哪个数据块服务器是主副本。第 3.2 节会对此做进一步讨论。
4.一旦所有副本都确认已接收到数据，客户端就会向主副本发送写入请求。该请求会指明之前推送到所有副本的数据。主副本会为它接收到的所有变更（可能来自多个客户端）分配连续的序列号，这提供了必要的序列化操作。它会按照序列号顺序将变更应用到自身的本地状态。
5.主副本将写入请求转发给所有从副本。每个从副本会按照主副本分配的相同序列号顺序来应用变更。
6.所有从副本都会回复主副本，表明它们已经完成了操作。
7.主副本回复客户端。任何副本遇到的任何错误都会报告给客户端。如果出现错误，写入操作可能在主副本以及任意一部分从副本上已经成功。（如果在主副本上失败了，就不会被分配序列号并转发。）客户端的请求会被视为失败，并且被修改的区域会处于不一致状态。我们的客户端代码通过重试失败的变更来处理此类错误。它会在步骤（3）至（步骤（7））尝试几次，然后再退回到从写入操作的开头进行重试。
如果应用程序的一次写入操作数据量很大或者跨越了数据块边界，GFS 客户端代码会将其拆分成多个写入操作。这些操作都遵循上述所描述的控制流程，但可能会与其他客户端的并发操作相互交错并且被其覆盖。因此，共享的文件区域最终可能会包含来自不同客户端的片段，不过由于各个操作在所有副本上都是按照相同顺序成功完成的，所以副本之间是完全相同的。这会使文件区域处于如 2.7 节所提到的一致但未定义的状态。
3.2 数据流
我们将数据流与控制流分离开来，以便高效利用网络。当控制流从客户端流向主副本，然后再流向所有从副本时，数据会以流水线的方式沿着精心挑选的一连串数据块服务器线性推送。我们的目标是充分利用每台机器的网络带宽，避免出现网络瓶颈和高延迟链路，并将推送所有数据的延迟降至最低。
为了充分利用每台机器的网络带宽，数据是沿着一连串数据块服务器线性推送的，而不是按照其他某种拓扑结构（例如树形结构）进行分配。这样，每台机器的全部出站带宽都可用于尽可能快地传输数据，而不是在多个接收方之间进行分配。
为了尽可能避免网络瓶颈和高延迟链路（例如，交换机间的链路往往两者兼具），每台机器会将数据转发给网络拓扑结构中尚未接收该数据的 "最近" 的机器。假设客户端正在向数据块服务器 S1 到 S4 推送数据。它会将数据发送给距离最近的那个数据块服务器，比如 S1。S1 会将其转发给 S1 到 S4 中距离 S1 最近的另一个数据块服务器，比如 S2。类似地，S2 会将其转发给距离 S2 更近的 S3 或 S4，依此类推。我们的网络拓扑结构足够简单，以至于可以根据 IP 地址准确估算出 "距离"。
最后，我们通过在 TCP 连接上对数据传输进行流水线操作来将延迟降至最低。一旦数据块服务器接收到一些数据，它就会立即开始转发。流水线操作对我们特别有帮助，因为我们使用的是具有全双工链路的交换式网络。立即发送数据并不会降低接收速率。在没有网络拥塞的情况下，将 B 字节的数据传输到 R 个副本所需的理想耗时为 B/T + RL，其中 T 是网络吞吐量，L 是两台机器之间传输字节的延迟。我们的网络链路通常为 100Mbps（T），且 L 远低于 1 毫秒。因此，理想情况下，1MB 的数据可以在大约 80 毫秒内完成分发。
这里的推送机制和链式调用有点像，可以充分利用每一台机器的网络带宽。
3.3 原子记录追加
GFS 提供了一种名为记录追加的原子追加操作。在传统的写入操作中，客户端需要指定数据要写入的偏移量。对同一区域的并发写入是不可序列化的：该区域最终可能会包含来自多个客户端的数据片段。然而，在记录追加操作中，客户端只需指定数据。GFS 会在其自行选定的偏移量处将数据原子性地（即作为一个连续的字节序列）至少追加一次到文件中，并将该偏移量返回给客户端。这类似于在 Unix 系统中以 O_APPEND 模式打开文件并进行写入操作，且当多个写入者并发执行此操作时不会出现竞争条件。
我们的分布式应用程序大量使用记录追加操作，在这些应用程序中，不同机器上的许多客户端会并发地向同一个文件追加数据。如果客户端使用传统的写入方式来进行此类操作，就需要额外的复杂且昂贵的同步机制，例如通过分布式锁管理器来实现。在我们的工作负载中，此类文件通常用作多生产者 / 单消费者队列，或者包含来自许多不同客户端的合并结果。
记录追加是一种变更操作，它遵循 3.1 节所述的控制流程，只是在主副本处需要额外添加少许逻辑。客户端将数据推送到文件最后一个数据块的所有副本。然后，它将请求发送给主副本。主副本会检查将记录追加到当前数据块是否会导致该数据块超出最大尺寸（64MB）。如果会超出，它会将数据块填充到最大尺寸，通知从副本也进行同样操作，并回复客户端告知应在下一个数据块上重试该操作。（为了将最坏情况下的碎片化程度控制在可接受水平，记录追加操作被限制为最多不超过最大数据块尺寸的四分之一。）如果记录能够在最大尺寸范围内追加，这是常见情况，主副本会将数据追加到其自身的副本中，通知从副本在其已追加数据的准确偏移量处写入数据，最后向客户端回复操作成功。
如果记录追加操作在任何一个副本上失败，客户端会重试该操作。结果是，同一个数据块的副本可能包含不同的数据，可能包括完整或部分相同记录的重复内容。GFS 并不保证所有副本在字节层面完全相同。它只保证数据作为一个原子单元至少被写入一次。这一特性很容易从一个简单的观察中得出：为了使该操作报告成功，数据必须已经在某个数据块的所有副本的相同偏移量处被写入。此外，在此之后，所有副本的长度至少与记录末尾的长度相同，因此，即使之后不同的副本成为主副本，任何后续的记录也会被分配一个更高的偏移量或不同的数据块。就我们的一致性保证而言，成功的记录追加操作写入其数据的区域是已定义的（因此是一致的），而其间的区域是不一致的（因此是未定义的）。我们的应用程序可以按照我们在 2.7.2 节中所讨论的方式来处理不一致的区域。
3.4 快照
快照操作几乎能瞬间为一个文件或一个目录树（"源文件 / 源目录"）创建副本，同时将对正在进行的变更操作的干扰降到最低。我们的用户用它来快速创建大型数据集的分支副本（并且经常会递归地对这些副本再进行复制），或者在对数据进行可轻松提交或回滚的更改实验之前，对当前状态进行检查点设置。
和 AFS 一样，我们使用标准的写时复制技术来实现快照功能。当主服务器收到快照请求时，它首先会撤销即将被快照的文件中各个数据块上所有未完成的租约。这确保了后续对这些数据块的任何写入操作都需要与主服务器进行交互以找到租约持有者。这将给主服务器一个机会，使其能先为该数据块创建一个新的副本。
在租约被撤销或到期之后，主服务器会将该操作记录到磁盘上。然后，它通过复制源文件或目录树的元数据，将这条日志记录应用到其内存中的状态。新创建的快照文件指向的 数据块与源文件所指向的相同。
在快照操作完成后，当客户端第一次想要写入某个数据块 C 时，它会向主服务器发送一个请求以找到当前的租约持有者。主服务器会注意到数据块 C 的引用计数大于 1。它会延迟回复客户端的请求，而是选择一个新的数据块句柄 C'。然后，它会要求每个拥有数据块 C 当前副本的 数据块服务器创建一个新的数据块，名为 C'。通过在与原始数据块相同的 数据块服务器上创建新数据块，我们确保数据可以在本地进行复制，而无需通过网络传输（我们的磁盘速度大约是 100Mb 以太网链路速度的三倍）。从这一点开始，对请求的处理与处理任何其他数据块的请求没有什么不同：主服务器会将新数据块 C'的租约授予其中一个副本，并回复客户端，客户端就可以正常写入该数据块，而不知道它刚刚是由一个现有数据块创建而来的。
4.主服务器操作
主服务器执行所有命名空间操作。此外，它还管理整个系统中的数据块副本：它做出放置决策，创建新的数据块以及相应的副本，并协调各种全系统范围的活动，以确保数据块被完全复制、平衡所有数据块服务器间的负载，并回收未使用的存储空间。现在我们来逐一讨论这些方面。
4.1 命名空间管理与锁定
许多主服务器操作可能会耗费较长时间，例如，一次快照操作必须撤销快照所涉及的所有数据块在数据块服务器上的租约。我们不希望在这些操作运行期间延迟其他主服务器操作。因此，我们允许同时进行多个操作，并针对命名空间的各个区域使用锁来确保正确的序列化。 与许多传统文件系统不同，GFS 没有那种列出目录中所有文件的每个目录的数据结构。它也不支持同一文件或目录的别名（即 Unix 术语中的硬链接或符号链接）。GFS 在逻辑上将其命名空间表示为一个查找表，该表将完整路径名映射到元数据。通过前缀压缩，这个表可以在内存中高效表示。命名空间树中的每个节点（要么是绝对文件名，要么是绝对目录名）都有一个关联的读写锁。 每个主服务器操作在运行之前都会获取一组锁。通常，如果操作涉及到 /d1/d2/.../dn/leaf，它将获取目录名 /d1、/d1/d2、...、/d1/d2/.../dn 的读锁，以及完整路径名 /d1/d2/.../dn/leaf 的读锁或写锁。请注意，leaf 根据操作的不同可能是一个文件或目录。
如何防止冲突：
举个例子，假设要创建文件 /home/user/foo，而同时有一个快照操作正在将 /home/user 快照到 /save/user：
- 快照操作：会在
/home和/save上获取读锁，在/home/user和/save/user上获取写锁。 - 文件创建操作：会在
/home和/home/user上获取读锁，在/home/user/foo上获取写锁。 - 由于这两个操作在
/home/user路径上需要获取 写锁，它们会被正确序列化（即，按照顺序执行）。快照操作会阻止文件创建操作，反之亦然。
这种机制避免了冲突，因为只有一个操作能够对某个路径（文件或目录）进行写操作。
快照操作给人感觉对于源数据是只读操作，但是这里提到了要对/home/user上写锁。似乎有点奇怪。但是回头一想，如果这里不上写锁，那么创建/home/user/foo就不会报错，也就不能防止冲突了。但是这里确实和直观的感觉有些背离。
并发操作：
一个有趣的特性是，GFS 的锁机制可以让 同一目录下的多个文件创建操作并发执行：
- 每个文件创建操作会在目录名称上获取 读锁，在新文件名上获取 写锁。
- 读锁确保目录本身不会被删除、重命名或快照，而写锁则确保同一个目录下不会有两个文件尝试创建相同的名字。
由于命名空间可能有许多节点，读写锁对象是按需分配的，并且一旦不再使用就会被删除。此外，锁是按照一致的全序获取的，以防止死锁：它们首先按照命名空间树中的层级排序，在同一层级内则按照字典序排序。
4.2 副本放置
GFS 集群在多个层面上都是高度分布式的。它通常拥有数百个数据块服务器，这些服务器分布在许多机架上。反过来，这些数据块服务器可能会被来自相同或不同机架的数百个客户端访问。不同机架上的两台机器之间的通信可能会跨越一个或多个网络交换机。此外，进出一个机架的带宽可能会小于该机架内所有机器的总带宽。
多级分布给为了实现可扩展性、可靠性和可用性而进行的数据分布带来了独特的挑战。
数据块副本放置策略有两个目的：最大限度地提高数据的可靠性和可用性，以及最大限度地提高网络带宽的利用率。对于这两个目的来说，仅仅将副本分布在不同的机器上是不够的，这样做只能防范磁盘或机器故障以及充分利用每台机器的网络带宽。我们还必须将数据块副本分布在不同的机架上。这确保了即使整个机架损坏或离线（例如，由于网络交换机或电源电路等共享资源出现故障），一个数据块的某些副本也能存活并保持可用。这也意味着一个数据块的流量，尤其是读取流量，可以利用多个机架的总带宽。另一方面，写入流量必须流经多个机架，这是我们愿意做出的一种权衡。
这段话讲的是 GFS 中的 副本放置策略（Replica Placement），即如何在多个机器和机架（rack）之间合理地分布数据副本。其主要目的是提高数据的可靠性和可用性，并最大化网络带宽的利用。
1. 多级分布的挑战
GFS 的集群通常是 高度分布式 的，具有多个层级的分布：
- Chunkservers（数据块服务器）：这些服务器分布在多个 机架（rack）上，每个机架包含多个机器。
- 客户端（Client）：客户端可能位于同一机架或不同机架上，多个客户端可以同时访问不同的 chunkservers。
- 跨机架通信：不同机架之间的机器通信可能需要经过一个或多个 网络交换机，这会引入一定的延迟和带宽瓶颈。
- 带宽限制：一个机架内的所有机器共享同一个网络带宽，因此带宽可能会受限，尤其是在大量客户端同时访问时。
这种 多级分布 带来了一个挑战：如何分布数据才能兼顾 扩展性、可靠性 和 可用性？
2. 副本放置策略的目标
副本放置策略的核心目的是通过合理地分布数据副本来实现两个目标：
- 最大化数据的可靠性和可用性：确保即使部分机器、机架或网络出现故障，数据依然能被可靠地访问。
- 最大化网络带宽的利用：通过合理地分布数据副本，充分利用多个机架和机器之间的带宽，提升访问效率。
3. 副本放置的挑战
为了实现上述目标，单纯地把数据副本分布到 不同机器 上并不够。虽然这样可以应对 单机故障 或 硬盘故障，并能充分利用每台机器的带宽，但如果发生如下问题，仍然无法确保数据的高可用性和高带宽利用：
- 机架级故障：如果整个机架的机器都不可用（例如，机架内的交换机、电源故障等），那么该机架上的所有数据副本都会无法访问。
- 带宽瓶颈：如果客户端和服务器都集中在一个机架内，网络带宽可能会成为瓶颈，尤其是当有多个客户端同时访问时。
4. 副本分布策略
为了避免这些问题，GFS 必须将数据副本分布到不同的机架 上。这样做的好处有：
- 可靠性：如果某个机架出现故障（例如，电力故障、网络交换机故障等），由于副本已经分布到其他机架，即使一个机架失效，其他机架上的副本仍然可以提供数据服务，保证数据的高可用性。
- 带宽利用：通过将副本分布到多个机架上，读操作可以从多个机架的副本中获取数据，这样就能够利用 多个机架的带宽 来提升读取性能。例如，如果某个客户端和 chunkserver 都位于同一个机架，它就可以充分利用该机架内所有机器的带宽来进行数据读取。
- 写操作的权衡：虽然 写操作 需要跨多个机架传输数据，这会带来一定的带宽和延迟成本，但在实际设计中，这是一种可以接受的权衡。因为写操作相对来说发生频率较低，而且写入操作跨机架的带宽瓶颈通常是可管理的。
4.3 创建、重新复制、重新平衡
出于以下三个原因会创建数据块副本：数据块创建、重新复制以及重新平衡。
当主服务器创建一个数据块时，它会选择将最初为空的副本放置在哪里。它会考虑以下几个因素：
- (1) 我们希望将新副本放置在磁盘空间利用率低于平均水平的 数据块服务器上。随着时间的推移，这将使各数据块服务器的磁盘利用率趋于均衡。
- (2) 我们希望限制每个数据块服务器上 "近期" 创建的数量。虽然创建操作本身成本不高，但它能可靠地预示即将出现的大量写入流量，因为数据块是在写入操作有需求时创建的，而且在我们这种一次写入多次读取的工作负载下，一旦数据块被完全写入，它们通常实际上就变成只读的了。
- (3) 如前文所述，我们希望将一个数据块的副本分布在不同的机架上。
一旦可用副本的数量低于用户指定的目标，主服务器就会对数据块进行重新复制。这可能由于多种原因发生：数据块服务器不可用，它报告其副本可能已损坏，由于错误其某个磁盘被禁用，或者复制目标提高了。每个需要重新复制的数据块会根据几个因素确定优先级。其中一个因素是它距离复制目标的差距。例如，我们会给丢失了两个副本的数据块比只丢失一个副本的数据块赋予更高的优先级。此外，相对于属于近期删除文件的数据块，我们更倾向于首先对活动文件的数据块进行重新复制（见 4.4 节）。最后，为了将故障对正在运行的应用程序的影响降至最低，我们会提高任何阻碍客户端进展的数据块的优先级。
主服务器会挑选优先级最高的数据块并通过指示某些数据块服务器直接从现有的有效副本复制数据块数据来 克隆 它。新副本的放置目标与创建副本时的目标类似：均衡磁盘空间利用率、限制任何单个数据块服务器上的活跃克隆操作数量以及将副本分布在不同的机架上。为了防止克隆流量压垮客户端流量，主服务器会限制集群以及每个数据块服务器上的活跃克隆操作数量。此外，每个数据块服务器会通过限制其对源数据块服务器的读取请求来控制其在每个克隆操作上花费的带宽。
最后，主服务器会定期对副本进行重新平衡：它会检查当前副本的分布情况，并移动副本以实现更好的磁盘空间和负载平衡。同样通过这个过程，主服务器会逐渐填满一台新的数据块服务器，而不是立即用新的数据块以及随之而来的大量写入流量将其淹没。新副本的放置标准与上述讨论的类似。此外，主服务器还必须选择移除哪个现有的副本。一般来说，它更倾向于移除那些位于磁盘空闲空间低于平均水平的数据块服务器上的副本，以实现磁盘空间使用的均衡。
4.4 垃圾回收
在文件被删除后，GFS 不会立即回收可用的物理存储空间。它仅在文件和数据块层面的常规垃圾回收期间以惰性方式进行回收。我们发现这种方法能使系统变得更加简单且可靠。
4.4.1 机制
当应用程序删除一个文件时，主服务器会像记录其他变更一样立即记录此次删除操作。然而，它并不会立即回收资源，而是将文件重命名为一个包含删除时间戳的隐藏名称。在主服务器对文件系统命名空间的常规扫描过程中，如果这类隐藏文件存在时间超过三天（该间隔可配置），就会将其删除。在此之前，该文件仍可通过这个新的特殊名称进行读取，并且可以通过将其重新命名回正常名称来恢复删除。 当隐藏文件从命名空间中被移除时，其在内存中的元数据也会被清除。这实际上切断了它与所有相关数据块的链接。
在对数据块命名空间进行的类似常规扫描中，主服务器会识别出孤立的数据块（即那些无法从任何文件访问到的数据块），并清除这些数据块的元数据。在与主服务器定期交换的心跳消息中，每个数据块服务器会报告其所拥有的数据块的一个子集，主服务器则会回复告知所有那些在其元数据中已不存在的数据块的标识。数据块服务器就可以自行删除这些数据块的副本了。