分布式系统学习2.2

本篇虽然名为分布式系统学习2.2,但和分布式系统学习（二）没什么关联，作为两篇相互独立的博文

在上一篇博文分布式系统学习1.1学习了MapReduce框架；MapReduce框架解决了分布式系统如何使用大量廉价的机器来处理海量的数据，同时MapReduce框架还极大地简化了分布式系统处理大数据的工作流，使得工程师不用关心分布式系统底层，只需要进行简单编程就可以利用分布式系统处理海量数据。

解决了分布式系统数据处理的问题后，我们就需要关注分布式系统如何存储大量的数据，Google提供了GFS这一解决方案，在这篇博文中我们就要探讨GFS（Google file system）

我们现在设想这样一种场景，我们手中有一台服务器，上面装了两块1TB大小硬盘，而我们现在有10TB的数据，所以我们不得不采用将数据分片的方式来将数据分布式存储到不同的服务器上，在这种情况下，我们不得不面对组件故障，以及大规模数据处理等问题

先来看看在GFS之前，业界是如何应对这些问题的

在2003年Google发布GFS论文之前，业界在处理组件故障和大规模数据处理时，业界的普遍共识是“尽可能使用昂贵的硬件来避免故障发生”，通过“纵向扩展（Scale-up）或昂贵的专业系统来处理大规模数据。”，既成本极高、扩展性差、无法处理非结构化海量数据、运维极其痛苦。

和MapReduce的初衷一样，Google有TB级的数据，纵使Google这样的大公司面对这种级别数据的成本也很肉痛，所以GFS就是Google探索出来用于在大规模廉价硬件上满足足够稳定性的分布式存储系统。

Google放弃了业界以前服务完全无法容错的定式思维，采用了“拥抱故障、软件定义、横向扩展（Scale-out）”的新设计哲学，在GFS之前，系统架构师通常将“组件故障”视为硬件手段防御的异常，而不是软件自动恢复到常态。使得分布式存储面对的问题从硬件问题变成了可以通过软件来解决的问题，从而大大降低了维护和使用成本。

为什么需要分布式存储，分布式存储的难点在哪？

除了我们一开始提到的硬盘物理限制导致大量数据无法实现单机存储外，还有一个原因是性能。

人们设计大型分布式系统或大型存储系统出发点通常是，他们想获得巨大的性能加成，进而利用数百台计算机的资源来同时完成大量工作。因此，性能问题就成为了最初的诉求。之后，很自然的想法就是将数据分割放到大量的服务器上，这样就可以并行的从多台服务器读取数据。我们将这种方式称之为分片（Sharding）。

如果你在成百上千台服务器上进行分片，你将会看见常态的故障。如果你有数千台服务器，那么总是会有一台服务器宕机，每天甚至每个小时都可能发生错误。所以，我们需要自动化的方法而不是人工介入来修复错误。我们需要一个自动容错系统，这就引出了容错这个话题。

实现容错最有用的一种方法是使用复制，只需要维护2-3个数据的副本，当其中一个故障了，你就可以使用另一个。所以，如果想有容错能力，就得有复制。

如果有复制，那就有了两份数据的副本。可以确定的是，如果你不小心，他们就会不一致。所以，你本来设想的是，有了两个数据副本，你可以任意使用其中一个副本来容错。但是如果你不够小心，两个数据的副本就不是完全一致，严格来说，它们就不再互为副本了。而你获取到的数据内容也将取决与你向哪个副本请求数据。这对于应用程序来说就有些麻烦了。所以，如果我们有了复制，我们就有不一致的问题。

通过聪明的设计，你可以避免不一致的问题，并且让数据看起来也表现得符合预期。但是为了达到这样的效果，你总是需要额外的工作，需要不同服务器之间通过网络额外的交互，而这样的交互会降低性能。所以如果你想要一致性，你的代价就是低性能。但这明显不是我们最开始所希望的。

此外，分布式系统必须要面对高并发，所以有这样的情况：现在有一个分布式系统，使用两台服务器对外同时提供读写服务，相互作为副本，现在我们有两个客户端同时对我们的副本发起请求，设这两个客户端为A和B,A要求将值x设为1,B要求将值x设为2,现在我们就面临了一个问题，两台服务器同时进行写操作，要如何决定执行的顺序？

如果服务器1先处理A的请求，再处理B的请求，最后x的值为2,而服务器2选择先处理B的请求，再处理A的请求，x的值就为1。又因为读操作无法由两台服务器同时提供（因为这样会丧失容错，客户端如果必须同时从两台服务器上拿到数据，如果有其中一台故障，服务就变得不可用了），所以就会出现客户端拿到的数据不一致，我们预期相连的读请求应该读出相同的数据。

解决这个问题的办法是让两台服务器进行通信，但这样又会损失一些性能。

GFS的设计目标

面对上面的问题，Google选择了性能，和我们搭建分布式系统的初衷一致，所以一定的错误数据是可以被容忍的。

这是Google在论文中的表述：

We have designed and implemented the Google File Sys- tem (GFS) to meet the rapidly growing demands of Google’s data processing needs. GFS shares many of the same goals as previous distributed file systems such as performance, scalability, reliability, and availability. However, its design has been driven by key observations of our application work- loads and technological environment, both current and an- ticipated, that reflect a marked departure from some earlier file system design assumptions. We have reexamined tradi- tional choices and explored radically different points in the design space. First, component failures are the norm rather than the exception. The file system consists of hundreds or even thousands of storage machines built from inexpensive com- modity parts and is accessed by a comparable number of client machines. The quantity and quality of the compo- nents virtually guarantee that some are not functional at any given time and some will not recover from their cur- rent failures. We have seen problems caused by application bugs, operating system bugs, human errors, and the failures of disks, memory, connectors, networking, and power sup- plies. Therefore, constant monitoring, error detection, fault tolerance, and automatic recovery must be integral to the system. Second, files are huge by traditional standards. Multi-GB files are common. Each file typically contains many applica- tion objects such as web documents. When we are regularly working with fast growing data sets of many TBs comprising billions of objects, it is unwieldy to manage billions of ap- proximately KB-sized files even when the file system could support it. As a result, design assumptions and parameters such as I/O operation and block sizes have to be revisited. Third, most files are mutated by appending new data rather than overwriting existing data. Random writes within a file are practically non-existent. Once written, the files are only read, and often only sequentially. A variety of data share these characteristics. Some may constitute large repositories that data analysis programs scan through. Some may be data streams continuously generated by running ap- plications. Some may be archival data. Some may be in- termediate results produced on one machine and processed on another, whether simultaneously or later in time. Given this access pattern on huge files, appending becomes the fo- cus of performance optimization and atomicity guarantees, while caching data blocks in the client loses its appeal. Fourth, co-designing the applications and the file system API benefits the overall system by increasing our flexibility. For example, we have relaxed GFS’s consistency model to vastly simplify the file system without imposing an onerous burden on the applications. We have also introduced an atomic append operation so that multiple clients can append concurrently to a file without extra synchronization between them. These will be discussed in more details later in the paper. Multiple GFS clusters are currently deployed for different purposes. The largest ones have over 1000 storage nodes, over 300 TB of disk storage, and are heavily accessed by hundreds of clients on distinct machines on a continuous basis.

我们设计并实现了谷歌文件系统（GFS），以满足谷歌数据处理需求的快速增长。GFS与之前的分布式文件系统（如性能、可扩展性、可靠性和可用性）有许多相同的目标。然而，其设计受到对我们当前和预期中的应用负载和技术环境的关键观察所驱动，这反映出为了满足谷歌数据处理需求的增长而做出的显著努力。

首先，组件故障是常态而非例外。该文件系统由成百上千台使用廉价通用部件构建的存储机器组成，并被数量相当的客户端机器访问。这些组件的数量和质量实际上保证了在任何时刻都有一些组件无法正常工作，并且有些组件无法从当前的故障中恢复。我们曾见过由应用程序错误、操作系统错误、人为错误以及磁盘、内存、连接器、网络和电源故障引起的问题。因此，持续的监控、错误检测、容错和自动恢复必须是系统不可或缺的一部分。

其次，按照传统标准，文件非常巨大。多GB的文件很常见。每个文件通常包含许多应用对象，如Web文档。当我们经常处理包含数十亿对象、快速增长的数TB数据集时，即使文件系统能够支持，管理数十亿个大约KB大小的文件也是不切实际的。因此，设计假设和参数（如I/O操作和块大小）需要重新审视。

第三，大多数文件通过追加新数据而非覆盖现有数据来改变。文件内的随机写入实际上是不存在的。一旦写入完成，文件只会被读取，而且通常是顺序读取。多种数据都具有这些特性。一些可能构成大型存储库，供数据分析程序扫描。一些可能是正在运行的应用持续生成的数据流。一些可能是归档数据。一些可能是在一台机器上生成并在另一台机器上处理（无论是同时还是稍后）的中间结果。鉴于这种对大型文件的访问模式，追加操作成为性能优化和原子性保证的焦点，而客户端缓存数据块则失去了吸引力。

第四，协同设计应用程序和文件系统API通过增加我们的灵活性而使整个系统受益。

例如，我们放宽了GFS的一致性模型，以极大简化文件系统，同时不给应用程序带来过重负担。我们还引入了一个原子追加操作，使得多个客户端可以并发地向同一个文件追加数据，而无需它们之间进行额外的同步。这些将在后文中更详细地讨论。

目前部署了多个GFS集群用于不同目的。最大的集群拥有超过1000个存储节点、超过300 TB的磁盘存储，并被数百台不同机器上的客户端持续大量访问。

Google设计了一个可供内部人员共同协作的大型文件系统，这个文件系统全局有效，也就是说各种不同的应用程序都可以从中读取数据，任何在Google内部的人员都可以根据名字读取这个文件系统中可被共享的内容。

如同论文中描述的，GFS搭建在大量廉价通用部件组成的服务器上，所以故障是常态，必须容忍这些故障，在发生故障时，我们期望系统能自动修复自己；其次，数据规模非常巨大；第三，大多数文件通过追加新数据而非覆盖现有数据来改变。

构建分布式系统的最初目标是实现大容量和高性能，每个包含了数据的文件会被GFS自动的分割并存放在多个服务器上，这样读写操作自然就会变得很快。因为可以从多个服务器上同时读取同一个文件，进而获得更高的聚合吞吐量。将文件分割存储还可以在存储系统中保存比单个磁盘还要大的文件，这一点我们在上面已经提到过了。

这种对大型文件的访问模式，追加操作成为性能优化和原子性保证的焦点，而客户端缓存数据块则失去了吸引力。

由此，GFS在各个方面对大型文件的读写做了定制。由于99%的写操作都是在文件末尾追加，所以系统不需要去实现复杂的“修改文件中间内容”的逻辑，只要把追加写的性能做到极致就好。同时，如果有多个程序同时往一个文件末尾追加数据，系统必须保证它们不会相互覆盖（原子性）

GFS的大致架构

1-GFS-Architecture

GFS Master节点

假设我们有上百个客户端和一个Master节点。尽管实际中可以拿多台机器作为Master节点，但是GFS中Master是Active-Standby模式，所以只有一个Master节点在工作。Master节点保存了文件名和存储位置的对应关系。除此之外，还有大量的Chunk服务器，可能会有数百个，每一个Chunk服务器上都有1-2块磁盘。

Active-Standby 模式（中文通常称为主备模式或主从热备模式）是 IT 系统架构中一种经典的高可用性（High Availability, HA）设计方案。它的核心思想是：在一个集群或系统中，同时配置一个主节点（Active）和一个或多个备用节点（Standby）。平时只有主节点对外提供服务，备用节点处于待命状态并实时同步数据；当主节点发生故障时，备用节点会迅速接管工作，以保证业务不中断。

在这里，Master节点用来管理文件和Chunk的信息，而Chunk服务器用来存储实际的数据。这是GFS设计中比较好的一面，它将这两类数据的管理问题几乎完全隔离开了，这样这两个问题可以使用独立设计来解决。Master节点知道每一个文件对应的所有的Chunk的ID，这些Chunk每个是64MB大小，它们共同构成了一个文件。如果我有一个1GB的文件，那么Master节点就知道文件的第一个Chunk存储在哪，第二个Chunk存储在哪，等等。当我想读取这个文件中的任意一个部分时，我需要向Master节点查询对应的Chunk在哪个服务器上，之后我可以直接从Chunk服务器读取对应的Chunk数据。

GFS默认使用3副本的架构，然后由Master节点指派其中一个作为主副本（Primary），由Primary决定写入的顺序

更进一步，我们看一下GFS的一致性以及GFS是如何处理故障。为了了解这些，我们需要知道Master节点内保存的数据内容，这里我们关心的主要是两个表单：

第一个是文件名到Chunk ID或者Chunk Handle数组的对应。这个表单告诉你，文件对应了哪些Chunk。但是只有Chunk ID是做不了太多事情的，所以有了第二个表单。
第二个表单记录了Chunk ID到Chunk数据的对应关系。这里的数据又包括了：
- 每个Chunk存储在哪些服务器上，所以这部分是Chunk服务器的列表
- 每个Chunk当前的版本号，所以Master节点必须记住每个Chunk对应的版本号。
- 所有对于Chunk的写操作都必须在主Chunk（Primary Chunk）上顺序处理，主Chunk是Chunk的多个副本之一。所以，Master节点必须记住哪个Chunk服务器持有主Chunk。
- 并且，主Chunk只能在特定的租约时间内担任主Chunk，所以，Master节点要记住主Chunk的租约过期时间。
以上数据都存储在内存中，如果Master故障了，这些数据就都丢失了。为了能让Master重启而不丢失数据，Master节点会同时将数据存储在磁盘上。所以Master节点读数据只会从内存读，但是写数据的时候，至少有一部分数据会接入到磁盘中。更具体来说，Master会在磁盘上存储log，每次有数据变更时，Master会在磁盘的log中追加一条记录，并生成CheckPoint（类似于备份点）。

有些数据需要存在磁盘上，而有些不用。它们分别是：
- Chunk Handle的数组（第一个表单）要保存在磁盘上。我给它标记成NV（non-volatile, 非易失），这个标记表示对应的数据会写入到磁盘上。
- Chunk服务器列表不用保存到磁盘上。因为Master节点重启之后可以与所有的Chunk服务器通信，并查询每个Chunk服务器存储了哪些Chunk，所以我认为它不用写入磁盘。所以这里标记成V（volatile），
- 版本号要不要写入磁盘取决于GFS是如何工作的，我认为它需要写入磁盘。我们之后在讨论系统是如何工作的时候再详细讨论这个问题。这里先标记成NV。
- 主Chunk的ID，几乎可以确定不用写入磁盘，因为Master节点重启之后会忘记谁是主Chunk，它只需要等待60秒租约到期，那么它知道对于这个Chunk来说没有主Chunk，这个时候，Master节点可以安全指定一个新的主Chunk。所以这里标记成V。
- 类似的，租约过期时间也不用写入磁盘，所以这里标记成V。

任何时候，如果文件扩展到达了一个新的64MB，需要新增一个Chunk或者由于指定了新的主Chunk而导致版本号更新了，Master节点需要向磁盘中的Log追加一条记录说，我刚刚向这个文件添加了一个新的Chunk或者我刚刚修改了Chunk的版本号。所以每次有这样的更新，都需要写磁盘。GFS论文并没有讨论这么多细节，但是因为写磁盘的速度是有限的，写磁盘会导致Master节点的更新速度也是有限的，所以要尽可能少的写入数据到磁盘。

这里在磁盘中维护log而不是数据库的原因是，数据库本质上来说是某种B树（b-tree）或者hash table，相比之下，追加log会非常的高效，因为你可以将最近的多个log记录一次性的写入磁盘。因为这些数据都是向同一个地址追加，这样只需要等待磁盘的磁碟旋转一次。而对于B树来说，每一份数据都需要在磁盘中随机找个位置写入。所以使用Log可以使得磁盘写入更快一些。

当Master节点故障重启，并重建它的状态，你不会想要从log的最开始重建状态，因为log的最开始可能是几年之前，所以Master节点会在磁盘中创建一些checkpoint点，这可能要花费几秒甚至一分钟。这样Master节点重启时，会从log中的最近一个checkpoint开始恢复，再逐条执行从Checkpoint开始的log，最后恢复自己的状态。

GFS的读写

现在可以关注GFS是如何具体读写文件的

GFS读文件

对于读请求，应用程序需要提供一个文件名和它想从文件的某个位置读取的偏移量（offset），应用程序会将这些信息发送给Master节点。Master节点会从自己的file表中查询文件名，得到Chunk ID的数组。因为每个Chunk是64MB,所以偏移量除以64MB就可以从数组中得到对应的Chunk ID。之后Master再从Chunk表单中找到存有Chunk的服务器列表，并将列表返回给客户端。所以，第一步是客户端（或者应用程序）将文件名和偏移量发送给Master。第二步，Master节点将Chunk Handle（也就是ID）和服务器列表发送给客户端。

可以看到Master只需要返回文件数据所在服务器，然后由对应的chunk服务器来和客户端进行数据交流，从而大大减轻了可能由Master节点导致的系统卡顿。

客户端可以从Chunk服务器中挑选一个来读取数据。GFS论文说，客户端会选择一个网络上最近的服务器（Google的数据中心中，IP地址是连续的，所以可以从IP地址的差异判断网络位置的远近），并将读请求发送到那个服务器。因为客户端每次可能只读1MB或者64KB数据，所以，客户端可能会连续多次读取同一个Chunk的不同位置。所以，客户端会缓存Chunk和服务器的对应关系，这样，当再次读取相同Chunk数据时，就不用一次次的去向Master请求相同的信息。

GFS写文件

我们前面提到了，在写入时，当存在备份的情况下，为了保证一致性，写入的顺序是非常重要的，GFS采用了3副本的格局，Master会在3个副本中选定一个作为主副本（Primary），由Primary来决定并发请求的写入顺序。

此时我们就必须考虑主副本不存在的情况。对于Master节点来说，如果发现Chunk的主副本不存在，Master会找出所有存有Chunk最新副本的Chunk服务器。如果你的一个系统已经运行了很长时间，那么有可能某一个Chunk服务器保存的Chunk副本是旧的，比如说还是昨天或者上周的。导致这个现象的原因可能是服务器因为宕机而没有受到任何的更新。所以，Master节点需要能够在Chunk的多个副本中识别出，哪些副本是新的，哪些是旧的。所以第一步是，找出新的Chunk副本。这一切都是在Master节点发生，因为，现在是客户端告诉Master节点说要追加某个文件，Master节点需要告诉客户端向哪个Chunk服务器（也就是Primary Chunk所在的服务器）去做追加操作。所以，Master节点的部分工作就是弄清楚在追加文件时，客户端应该与哪个Chunk服务器通信。

每个Chunk可能同时有多个副本，最新的副本是指，副本中保存的版本号与Master中记录的Chunk的版本号一致。Chunk副本中的版本号是由Master节点下发的，所以Master节点知道，对于一个特定的Chunk,哪个版本号是最新的。这就是为什么Chunk的版本号在Master节点上需要保存在磁盘这种非易失的存储中的原因，因为如果版本号在故障重启中丢失，且部分Chunk服务器拥有旧的Chunk副本，这时，Master是没有办法区分哪个Chunk服务器的数据时旧的，哪个Chunk服务器是最新的。

当客户端想要对文件进行追加，但是又不知道文件尾的Chunk对应的Primary在哪时，Master会等所有存储了最新Chunk版本的服务器集合完成，然后挑选一个作为Primary,其他的作为Secondary。然后Master会增加版本号，并将版本号写入磁盘，这样就算故障了也不会丢失这个数据。接下来，Master节点会向Primary和Secondary副本对应的服务器发送消息并告诉它们，谁是Primary,谁是Secondary,Chunk的新版本是什么。Primary和Secondary服务器都会将版本号存储在本地的磁盘中。这样，当它们因为电源故障或者其他原因重启时，它们可以向Master报告本地保存的Chunk的实际版本号。

好了，现在我们有了一个Primary，它可以接收来自客户端的写请求，并将写请求应用在多个Chunk服务器中。Master管理Chunk版本号的原因，一是这样Master可以将实际更新Chunk的能力转移给Primary服务器。Master通过Chunk版本号，保证在一段时间内只有一台服务器可以决定写入顺序，这样Master只需要控制Chunk版本号，而不需要直接参与数据写入，由客户端直接和Chunk服务器交互进行写入。二是在将版本号更新到Primary和Secondary服务器之后，如果Master节点故障重启，还是可以在相同的Primary和Secondary服务器上继续更新Chunk。

现在，Master节点通知Primary和Secondary服务器，你们可以修改这个Chunk。同时Master给Primary一个租约，这个租约告诉Primary说，在接下来的60秒中，你将是Primary,60秒之后你必须停止成为Primary这种机制确保我们不会同时有两个Primary。

前面写得有点乱，这里有张执行图可以帮助理解

我们通过跟踪一次写入的控制流程步骤来说明这一过程。

客户端向主节点询问哪个块服务器持有该块的当前租约以及其他副本的位置。如果没有人持有租约，主节点会向其选择的一个副本授予租约（未显示）。
主节点回复主副本的身份和其他（次级）副本的位置。客户端缓存这些数据以供将来变更使用。只有当主副本不可达或回复说它不再持有租约时，它才需要再次联系主节点。
客户端将数据推送到所有副本。客户端可以按任何顺序进行。每个块服务器将数据存储在一个内部LRU缓冲区缓存中，直到数据被使用或过期。通过将数据流与控制流解耦，我们可以根据网络拓扑调度昂贵的数据流，而不管哪个块服务器是主副本，从而提高性能。第3.2节将进一步讨论这一点。
一旦所有副本都确认收到数据，客户端向主副本发送写入请求。该请求标识之前推送到所有副本的数据。主副本为其接收到的所有变更（可能来自多个客户端）分配连续的序列号，这提供了必要的序列化。它按序列号顺序将变更应用到自己的本地状态。
主副本将写入请求转发给所有次级副本。每个次级副本以主副本分配的相同序列号顺序应用变更。
次级副本都回复主副本，表明它们已完成操作。
主副本回复客户端。任何副本上遇到的任何错误都报告给客户端。如果发生错误，写入可能已在主副本和任意子集的次级副本上成功。（如果它在主副本上失败，则不会被分配序列号并转发。）客户端请求被视为失败，修改后的区域处于不一致状态。我们的客户端代码通过重试失败的变更来处理此类错误。它会在步骤（3）到（7）中尝试几次，然后回退到从头开始重试写入。

如果应用程序的写入很大或跨越块边界，GFS客户端代码会将其分解为多个写入操作。它们都遵循上述控制流程，但可能与其他客户端的并发操作交织并被覆盖。因此，共享文件区域可能最终包含来自不同客户端的片段，但由于各个操作在所有副本上以相同顺序成功完成，副本将是一致的。

GFS的一致性

现在我们要进一步讨论GFS的一致性问题

当我们追加数据时，面对Chunk的三个副本，当客户端发送了一个追加数据的请求，要将数据A追加到文件末尾，所有的三个副本，包括一个Primary和两个Secondary，都成功的将数据追加到了Chunk，所以Chunk中的第一个记录是A。

假设第二个客户端加入进来，想要追加数据B，但是由于网络问题发送给某个副本的消息丢失了。所以，追加数据B的消息只被两个副本收到，一个是Primary，一个是Secondary。这两个副本都在文件中追加了数据B，所以，现在我们有两个副本有数据B，另一个没有。

之后，第三个客户端想要追加数据C，并且第三个客户端记得下图中左边第一个副本是Primary。Primary选择了偏移量，并将偏移量告诉Secondary，将数据C写在Chunk的这个位置。三个副本都将数据C写在这个位置。

对于数据B来说，客户端会收到写入失败的回复，客户端会重发写入数据B的请求。所以，第二个客户端会再次请求追加数据B，或许这次数据没有在网络中丢包，并且所有的三个副本都成功追加了数据B。现在三个副本都在线，并且都有最新的版本号。

之后，如果一个客户端读文件，读到的内容取决于读取的是Chunk的哪个副本。客户端总共可以看到三条数据，但是取决于不同的副本，读取数据的顺序是不一样的。如果读取的是第一个副本，那么客户端可以读到A、B、C，然后是一个重复的B。如果读取的是第三个副本，那么客户端可以读到A，一个空白数据，然后是C、B。所以，如果读取前两个副本，B和C的顺序是先B后C，如果读的是第三个副本，B和C的顺序是先C后B。所以，不同的读请求可能得到不同的结果。

或许最坏的情况是，一些客户端写文件时，因为其中一个Secondary未能成功执行数据追加操作，客户端从Primary收到写入失败的回复。在客户端重新发送写文件请求之前，客户端就故障了。所以，你有可能进入这种情形：数据D出现在某些副本中，而其他副本则完全没有。

在GFS的这种工作方式下，如果Primary返回写入成功，那么一切都还好，如果Primary返回写入失败，就不是那么好了。Primary返回写入失败会导致不同的副本有完全不同的数据。

GFS这样设计的理由是足够的简单，但是同时也给应用程序暴露了一些奇怪的数据。这里希望为应用程序提供一个相对简单的写入接口，但应用程序需要容忍读取数据的乱序。如果应用程序不能容忍乱序，应用程序要么可以通过在文件中写入序列号，这样读取的时候能自己识别顺序，要么如果应用程序对顺序真的非常敏感那么对于特定的文件不要并发写入。例如，对于电影文件，你不会想要将数据弄乱，当你将电影写入文件时，你可以只用一个客户端连续顺序而不是并发的将数据追加到文件中。

参考

Lecture 03-GFS中文翻译

The End

以上就是我们关于GFS的学习了，这篇博文前前后后写了快半个月，由于不是一气呵成，导致有的地方读起来可能会逻辑混乱，这时推荐去读论文原文和MIT6.824的具体讲解，写这样一篇博客断断续续都很难将逻辑理顺，更加佩服发论文的人在长期工作的时候是如何不丢失上下文的

在最后我也会和上篇分布式系统（1.1）一样贴出GFS的论文链接和中文翻译

The Google File System

谷歌文件系统

摘要

我们设计并实现了谷歌文件系统（Google File System，GFS），这是一个为大规模分布式数据密集型应用打造的、可扩展的分布式文件系统。它能在运行于廉价的通用硬件上时提供容错能力，并为大量客户端提供很高的聚合性能。

虽然GFS与之前的分布式文件系统有许多相同的目标，但其设计受到了对我们当前和预期中的应用负载及技术环境的观察所驱动，这些观察反映出与早期文件系统假设的显著差异。这促使我们重新审视传统选择，并探索了截然不同的设计思路。

该文件系统已成功满足了我们的存储需求。它在谷歌内部被广泛部署，作为生成和处理我们服务所用数据的存储平台，也用于需要大型数据集的研发工作。迄今为止最大的集群拥有超过一千台机器、数千块磁盘，提供数百TB的存储空间，并被数百个客户端并发访问。

在本文中，我们将介绍为支持分布式应用而设计的文件系统接口扩展，讨论设计的诸多方面，并报告微基准测试和实际应用中的测量结果。

类别与主题描述符

D [4]:3 - 分布式文件系统

通用术语

设计、可靠性、性能、测量

关键词

容错、可扩展性、数据存储、集群存储

1. 引言

我们设计并实现了谷歌文件系统（GFS），以满足谷歌数据处理需求的快速增长。GFS与之前的分布式文件系统（如性能、可扩展性、可靠性和可用性）有许多相同的目标。然而，其设计受到对我们当前和预期中的应用负载和技术环境的关键观察所驱动，这反映出为了满足谷歌数据处理需求的增长而做出的显著努力。

首先，组件故障是常态而非例外。该文件系统由成百上千台使用廉价通用部件构建的存储机器组成，并被数量相当的客户端机器访问。这些组件的数量和质量实际上保证了在任何时刻都有一些组件无法正常工作，并且有些组件无法从当前的故障中恢复。我们曾见过由应用程序错误、操作系统错误、人为错误以及磁盘、内存、连接器、网络和电源故障引起的问题。因此，持续的监控、错误检测、容错和自动恢复必须是系统不可或缺的一部分。

其次，按照传统标准，文件非常巨大。多GB的文件很常见。每个文件通常包含许多应用对象，如Web文档。当我们经常处理包含数十亿对象、快速增长的数TB数据集时，即使文件系统能够支持，管理数十亿个大约KB大小的文件也是不切实际的。因此，设计假设和参数（如I/O操作和块大小）需要重新审视。

第三，大多数文件通过追加新数据而非覆盖现有数据来改变。文件内的随机写入实际上是不存在的。一旦写入完成，文件只会被读取，而且通常是顺序读取。多种数据都具有这些特性。一些可能构成大型存储库，供数据分析程序扫描。一些可能是正在运行的应用持续生成的数据流。一些可能是归档数据。一些可能是在一台机器上生成并在另一台机器上处理（无论是同时还是稍后）的中间结果。鉴于这种对大型文件的访问模式，追加操作成为性能优化和原子性保证的焦点，而客户端缓存数据块则失去了吸引力。

第四，协同设计应用程序和文件系统API通过增加我们的灵活性而使整个系统受益。

例如，我们放宽了GFS的一致性模型，以极大简化文件系统，同时不给应用程序带来过重负担。我们还引入了一个原子追加操作，使得多个客户端可以并发地向同一个文件追加数据，而无需它们之间进行额外的同步。这些将在后文中更详细地讨论。

目前部署了多个GFS集群用于不同目的。最大的集群拥有超过1000个存储节点、超过300 TB的磁盘存储，并被数百台不同机器上的客户端持续大量访问。

2. 设计概述

2.1 假设

在为我们的需求设计文件系统时，我们遵循了既带来挑战也带来机遇的假设。我们之前已经暗示了一些关键观察结果，现在更详细地阐述我们的假设。

系统由大量经常发生故障的廉价通用组件构成。它必须持续监控自身，并例行地检测、容忍并迅速从组件故障中恢复。

系统存储数量适中但规模巨大的文件。我们预期有数百万个文件，每个文件通常为100 MB或更大。多GB文件是常见情况，应被高效管理。必须支持小文件，但我们无需为它们进行优化。

工作负载主要由两种读取组成：大型流式读取和小型随机读取。在大型流式读取中，单个操作通常读取数百KB，更常见的是1 MB或更多。来自同一客户端的连续操作通常读取文件的一个连续区域。小型随机读取通常在任意偏移处读取几KB。注重性能的应用程序通常会批处理和排序它们的小型读取，以便稳定地向前推进文件，而不是来回移动。

工作负载还包括许多大型的、顺序写入，这些写入向文件追加数据。典型的操作大小与读取类似。文件一旦写入，很少再次被修改。支持在文件任意位置进行的小型写入，但不必高效。

系统必须为多个客户端并发追加到同一文件高效地实现定义良好的语义。我们的文件常被用作生产者-消费者队列或多路合并。数百个生产者，每台机器运行一个，将并发地向一个文件追加数据。原子性及最小的同步开销至关重要。该文件可能稍后被读取，或者一个消费者可能同时正在读取该文件。

高持续带宽比低延迟更重要。我们的大多数目标应用都重视以高速度批量处理数据，而很少有应用对单个读或写有严格的响应时间要求。

此外，GFS具有快照和记录追加操作。快照能以低成本创建文件或目录树的副本。记录追加允许众多客户端并发地向同一文件追加数据，同时保证每个单独客户端追加的原子性。这对于实现多路合并结果和生产者-消费者队列非常有用，许多客户端可以同时追加而无需额外锁定。我们发现这类文件在构建大型分布式应用中不可或缺。快照和记录追加将分别在3.4节和3.3节进一步讨论。

2.2 接口

GFS提供了一个熟悉的文件系统接口，尽管它没有实现POSIX等标准API。文件按目录层次组织，并由路径名标识。我们支持常用的创建、删除、打开、关闭、读取和写入文件操作。

2.3 架构

一个GFS集群由一个单一的主节点（master）和多个块服务器（chunkserver）组成，并被多个客户端访问，如图1所示。这些通常都是运行用户级服务器进程的通用Linux机器。只要机器资源允许，并且运行可能有缺陷的应用代码所导致的较低可靠性可以接受，就很容易在同一台机器上同时运行块服务器和客户端。

文件被划分为固定大小的块（chunk）。每个块由一个不可变的、全局唯一的64位块句柄（chunk handle）标识，该句柄由主节点在块创建时分配。块服务器将块作为Linux文件存储在本地磁盘上，并根据块句柄和字节范围读取或写入块数据。为了可靠性，每个块会在多个块服务器上复制。默认情况下，我们存储三个副本，尽管用户可以为文件命名空间的不同区域指定不同的复制级别。

主节点维护所有文件系统元数据。这包括命名空间、访问控制信息、从文件到块的映射，以及块的当前存储位置。它还控制系统范围的活动，如块租约管理、孤立块的垃圾回收，以及块服务器之间的块迁移。主节点通过心跳（HeartBeat）消息定期与每个块服务器通信，向其发送指令并收集其状态。

链接到每个应用程序的GFS客户端代码实现了文件系统API，并代表应用程序与主节点和块服务器通信以读取或写入数据。客户端与主节点交互进行元数据操作，但所有数据相关的通信都直接与块服务器进行。我们不提供POSIX API，因此无需接入Linux vnode层。

客户端和块服务器都不缓存文件数据。客户端缓存收益不大，因为大多数应用程序流式处理大文件，或者工作集太大无法缓存。没有缓存通过消除缓存一致性问题简化了客户端和整个系统。（但客户端会缓存元数据。）块服务器无需缓存文件数据，因为块作为本地文件存储，Linux的缓冲区缓存已经将频繁访问的数据保留在内存中。

2.4 单一主节点

采用单一主节点极大地简化了我们的设计，并使主节点能够利用全局知识做出复杂的块放置和复制决策。然而，我们必须尽量减少它在读写操作中的参与，以免成为瓶颈。客户端永远不会通过主节点读写文件数据。相反，客户端会询问主节点应该联系哪些块服务器。它将这些信息缓存一段时间，并直接与块服务器进行后续的许多操作。

让我们参照图1解释一次简单读取的交互。首先，客户端使用固定的块大小，将应用程序指定的文件名和字节偏移量转换为文件内的块索引。然后，它向主节点发送一个包含文件名和块索引的请求。主节点回复相应的块句柄和副本的位置。客户端使用文件名和块索引作为键来缓存此信息。

然后，客户端向其中一个副本发送请求，通常选择最近的那个。请求指定块句柄和该块内的字节范围。对该块的进一步读取无需再与主节点交互，直到缓存的信息过期或文件被重新打开。实际上，客户端通常会在同一个请求中询问多个块，主节点也可以包含紧随所请求块之后的信息。这些额外信息几乎不增加额外成本，却可以避免未来多次客户端与主节点的交互。

2.5 块大小

块大小是关键的设计参数之一。我们选择了64 MB，这远大于典型的文件系统块大小。每个块副本在块服务器上存储为一个普通的Linux文件，并且仅在需要时扩展。延迟空间分配避免了因内部碎片而浪费空间，这或许是对如此大块大小的最大反对意见。

大的块大小有几个重要优点。首先，它减少了客户端与主节点交互的需求，因为对同一块的读写只需要一次向主节点请求块位置信息。这种减少对于我们的工作负载尤其显著，因为应用程序大多顺序读写大文件。即使对于小型随机读取，客户端也可以轻松地为数TB的工作集缓存所有块位置信息。其次，由于块较大，客户端更可能对给定块执行许多操作，它可以通过长时间保持与块服务器的持久TCP连接来减少网络开销。第三，它减少了主节点上存储的元数据大小。这使我们能够将元数据保存在内存中，这反过来又带来了我们将在2.6.1节讨论的其他优点。

另一方面，大的块大小，即使有延迟空间分配，也有其缺点。一个小文件由少量块（可能只有一个）组成。如果许多客户端访问同一个文件，存储这些块的块服务器可能成为热点。在实践中，热点并未成为主要问题，因为我们的应用程序大多顺序读取大的多块文件。

然而，当GFS首次被批处理队列系统使用时，确实出现了热点：一个可执行文件作为单块文件写入GFS，然后同时在数百台机器上启动。存储该可执行文件的少数块服务器被数百个并发请求压垮。我们通过以更高的复制因子存储此类可执行文件，并让批处理队列系统错开应用程序启动时间来解决此问题。一个潜在的长期解决方案是允许客户端在这种情况下从其他客户端读取数据。

2.6 元数据

主节点存储三种主要类型的元数据：文件和块命名空间、从文件到块的映射，以及每个块副本的位置。所有元数据都保存在主节点的内存中。前两种类型（命名空间和文件到块映射）也通过将变更记录记录到存储在主节点本地磁盘并复制到远程机器上的操作日志中来持久化。使用日志使我们能够简单、可靠地更新主节点状态，并且避免在主节点崩溃时出现不一致的风险。主节点不持久存储块位置信息。相反，它在主节点启动时以及每当块服务器加入集群时，向每个块服务器询问其块信息。

2.6.1 内存数据结构

由于元数据存储在内存中，主节点操作速度很快。此外，主节点可以轻松高效地在后台定期扫描其整个状态。这种定期扫描用于实现块垃圾回收、在块服务器故障时重新复制，以及迁移块以平衡负载和磁盘空间使用。第4.3和4.4节将进一步讨论这些活动。

这种纯内存方法的一个潜在担忧是，块的数量以及整个系统的容量受到主节点内存大小的限制。这在实践中并不是一个严重的限制。主节点为每个64 MB块维护不到64字节的元数据。大多数块是满的，因为大多数文件包含许多块，只有最后一个块可能部分填充。类似地，文件命名空间数据通常每个文件需要不到64字节，因为它使用前缀压缩紧凑地存储文件名。

如果必要，为了支持更大的文件系统，向主节点增加内存的成本与我们通过将元数据存储在内存中获得的简单性、可靠性、性能和灵活性相比，是一个很小的代价。

2.6.2 块位置

主节点不持久记录哪个块服务器拥有给定块的副本。它只是在启动时轮询块服务器以获取该信息。主节点此后可以保持自身更新，因为它控制所有块放置，并通过定期心跳消息监控块服务器状态。

我们最初尝试在主节点持久保存块位置信息，但我们认为在启动时（以及此后定期）向块服务器请求数据要简单得多。这消除了当块服务器加入和离开集群、更改名称、失败、重启等时，保持主节点和块服务器同步的问题。在拥有数百台服务器的集群中，这些事件发生得过于频繁。

理解此设计决策的另一种方式是认识到，块服务器对其自身磁盘上拥有或不拥有哪些块拥有最终决定权。试图在主节点上维护此信息的一致性视图是没有意义的，因为块服务器上的错误（例如，磁盘可能损坏并被禁用）或操作员可能重命名块服务器，都可能导致块自发消失。

2.6.3 操作日志

操作日志包含关键元数据更改的历史记录。它是GFS的核心。它不仅是元数据的唯一持久记录，而且还充当逻辑时间线，定义了并发操作的顺序。文件和块，以及它们的版本（参见第4.5节），都由它们创建时的逻辑时间唯一且永恒地标识。

由于操作日志至关重要，我们必须可靠地存储它，并且在元数据更改持久化之前，不要使更改对客户端可见。否则，即使块本身幸存，我们也会有效地丢失整个文件系统或最近的客户端操作。因此，我们将其复制到多个远程机器上，并且仅在将相应的日志记录刷新到本地和远程磁盘后才响应客户端操作。主节点在刷新之前将多个日志记录批处理在一起，从而减少刷新和复制对整体系统吞吐量的影响。

主节点通过重放操作日志来恢复其文件系统状态。为了最小化启动时间，我们必须保持日志较小。当日志增长超过一定大小时，主节点会对其状态进行检查点（checkpoint），以便它可以通过从本地磁盘加载最新的检查点并仅重放之后有限数量的日志记录来恢复。检查点采用紧凑的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应用程序可以通过一些简单的技术来适应宽松的一致性模型，这些技术也已因其他原因而需要：依赖追加而非覆盖、检查点，以及写入自验证、自标识的记录。

实际上我们所有的应用程序都是通过追加而不是覆盖来变更文件。在一种典型用法中，写入者从头到尾生成一个文件。它在写入所有数据后原子地将文件重命名为永久名称，或者定期检查点记录已成功写入多少。检查点也可能包括应用级校验和。读取器仅验证并处理到最后一个检查点（已知处于已定义状态）之前的文件区域。无论一致性和并发性问题如何，这种方法对我们来说效果都很好。追加比随机写入效率高得多，并且更能抵御应用程序故障。检查点允许写入者增量式重新启动，并防止读取器处理从应用程序角度看仍然不完整但已成功写入的文件数据。

在另一种典型用法中，许多写入者并发地向一个文件追加数据，用于合并结果或作为生产者-消费者队列。记录追加的“至少一次”追加语义保留了每个写入者的输出。读取器处理偶尔的填充和重复，如下所示。写入者准备的每个记录都包含额外信息，如校验和，以便验证其有效性。读取器可以使用校验和识别并丢弃额外的填充和记录片段。如果它不能容忍偶尔的重复（例如，如果它们会触发非幂等操作），它可以使用记录中的唯一标识符过滤掉它们，这些标识符通常也用于命名相应的应用实体，如Web文档。这些用于记录I/O的功能（除重复删除外）位于我们应用程序共享的库代码中，并且也适用于谷歌的其他文件接口实现。这样，相同的记录序列，加上罕见的重复，总是被传递给记录读取器。

3. 系统交互

我们设计系统以最小化主节点在所有操作中的参与。在此基础上，我们现在描述客户端、主节点和块服务器如何交互以实现数据变更、原子记录追加和快照。

3.1 租约和变更顺序

变更（mutation）是更改块内容或元数据的操作，例如写入或追加操作。每个变更都在块的所有副本上执行。我们使用租约（lease）来维护副本之间一致的变更顺序。主节点将块租约授予一个副本，我们称之为主副本（primary）。主副本为对块的所有变更选择一个序列顺序。所有副本在应用变更时遵循此顺序。因此，全局变更顺序首先由主节点选择的租约授予顺序定义，在租约内则由主副本分配的序列号定义。

租约机制旨在最小化主节点的管理开销。租约的初始超时为60秒。然而，只要块正在被变更，主副本可以请求并通常获得主节点的无限期延长。这些扩展请求和授予被搭载在主节点与所有块服务器定期交换的心跳消息上。主节点有时可能会尝试在租约到期前撤销它（例如，当主节点想要禁用正在被重命名的文件上的变更时）。即使主节点与主副本失去通信，它也可以在旧租约到期后安全地向另一个副本授予新租约。

在图2中，我们通过跟踪一次写入的控制流程步骤来说明这一过程。

客户端向主节点询问哪个块服务器持有该块的当前租约以及其他副本的位置。如果没有人持有租约，主节点会向其选择的一个副本授予租约（未显示）。
主节点回复主副本的身份和其他（次级）副本的位置。客户端缓存这些数据以供将来变更使用。只有当主副本不可达或回复说它不再持有租约时，它才需要再次联系主节点。
客户端将数据推送到所有副本。客户端可以按任何顺序进行。每个块服务器将数据存储在一个内部LRU缓冲区缓存中，直到数据被使用或过期。通过将数据流与控制流解耦，我们可以根据网络拓扑调度昂贵的数据流，而不管哪个块服务器是主副本，从而提高性能。第3.2节将进一步讨论这一点。
一旦所有副本都确认收到数据，客户端向主副本发送写入请求。该请求标识之前推送到所有副本的数据。主副本为其接收到的所有变更（可能来自多个客户端）分配连续的序列号，这提供了必要的序列化。它按序列号顺序将变更应用到自己的本地状态。
主副本将写入请求转发给所有次级副本。每个次级副本以主副本分配的相同序列号顺序应用变更。
次级副本都回复主副本，表明它们已完成操作。
主副本回复客户端。任何副本上遇到的任何错误都报告给客户端。如果发生错误，写入可能已在主副本和任意子集的次级副本上成功。（如果它在主副本上失败，则不会被分配序列号并转发。）客户端请求被视为失败，修改后的区域处于不一致状态。我们的客户端代码通过重试失败的变更来处理此类错误。它会在步骤（3）到（7）中尝试几次，然后回退到从头开始重试写入。

如果应用程序的写入很大或跨越块边界，GFS客户端代码会将其分解为多个写入操作。它们都遵循上述控制流程，但可能与其他客户端的并发操作交织并被覆盖。因此，共享文件区域可能最终包含来自不同客户端的片段，但由于各个操作在所有副本上以相同顺序成功完成，副本将是一致的。这使得文件区域处于一致但未定义的状态，如第2.7节所述。

3.2 数据流

我们将数据流与控制流解耦，以高效利用网络。控制流从客户端到主副本，然后到所有次级副本，而数据则沿着精心选择的块服务器链以流水线方式线性推送。我们的目标是充分利用每台机器的网络带宽，避免网络瓶颈和高延迟链路，并最小化推送所有数据的延迟。

为了充分利用每台机器的网络带宽，数据沿着块服务器链线性推送，而不是以其他拓扑（例如树）分发。这样，每台机器的全部出站带宽都用于尽可能快地传输数据，而不是在多个接收者之间分配。

为了尽可能避免网络瓶颈和高延迟链路（例如，交换机间的链路通常两者兼具），每台机器将数据转发给网络拓扑中“最近”的尚未接收数据的机器。假设客户端将数据推送到块服务器S1到S4。它将数据发送到最近的块服务器，比如S1。S1将它转发给距离S1最近的S2到S4中的块服务器，比如S2。类似地，S2将它转发给距离S2最近的S3或S4，依此类推。我们的网络拓扑足够简单，可以通过IP地址准确估计“距离”。

最后，我们通过流水线化TCP连接上的数据传输来最小化延迟。一旦块服务器收到一些数据，它立即开始转发。流水线化对我们特别有帮助，因为我们使用全双工链路的交换网络。立即发送数据不会降低接收速率。在没有网络拥塞的情况下，将B字节传输到R个副本的理想经过时间是 \(B/T + RL\)，其中 \(T\) 是网络吞吐量，\(L\) 是两台机器之间传输字节的延迟。我们的网络链路通常为100 Mbps \((T)\)，而 \(L\) 远低于1毫秒。因此，1 MB理想情况下可以在约80毫秒内分发完成。

3.3 原子记录追加

GFS提供了一种称为记录追加（record append）的原子追加操作。在传统写入中，客户端指定数据写入的偏移量。对同一区域的并发写入是不可序列化的：该区域最终可能包含来自多个客户端的数据片段。然而，在记录追加中，客户端只指定数据。GFS将其原子地（即作为连续的字节序列）追加到文件中至少一次，偏移量由GFS选择，并将该偏移量返回给客户端。这类似于在Unix中以O_APPEND模式打开文件进行写入，但没有多个写入者并发时的竞争条件。

记录追加被我们的分布式应用程序大量使用，其中许多不同机器上的客户端并发地向同一文件追加数据。如果使用传统的写入，客户端将需要额外复杂且昂贵的同步，例如通过分布式锁管理器。在我们的工作负载中，此类文件通常用作多生产者/单消费者队列，或包含来自许多不同客户端的合并结果。

记录追加是一种变更，遵循第3.1节中的控制流程，但主副本处有一些额外的逻辑。客户端将数据推送到文件最后一个块的所有副本。然后，它向主副本发送请求。主副本检查将记录追加到当前块是否会导致块超过最大大小（64 MB）。如果是，它将块填充到最大大小，通知次级副本也这样做，并回复客户端指示应在下一个块上重试该操作。（记录追加的大小被限制为最大块大小的四分之一，以将最坏情况下的碎片保持在可接受水平。）如果记录适合最大大小（这是常见情况），主副本将数据追加到其副本，通知次级副本在它写入的确切偏移量处写入数据，最后向客户端回复成功。

如果记录追加在任何副本上失败，客户端会重试该操作。因此，同一块的不同副本可能包含不同的数据，可能包括相同记录的完整或部分重复。GFS不保证所有副本在字节级别完全相同。它只保证数据至少一次作为原子单元被写入。这个性质可以从一个简单的观察中很容易地得出：为了报告成功，数据必须已经写入某个块的所有副本上的同一偏移量。此外，在此之后，所有副本至少与记录末尾一样长，因此即使稍后不同的副本成为主副本，任何未来的记录也将被分配更高的偏移量或不同的块。就我们的一致性保证而言，成功的记录追加操作写入其数据的区域是已定义的（因此是一致的），而中间的填充区域是不一致的（因此是未定义的）。我们的应用程序可以像我们在第2.7.2节中讨论的那样处理不一致的区域。

3.4 快照

快照操作几乎可以瞬时地创建文件或目录树（“源”）的副本，同时最小化对正在进行的变更的中断。我们的用户使用它来快速创建大型数据集的支线副本（并经常递归地创建这些副本的副本），或者在尝试稍后可以提交或轻松回滚的更改之前检查点当前状态。

与AFS [5]类似，我们使用标准的写时复制技术来实现快照。当主节点收到快照请求时，它首先撤销即将快照的文件中块的所有未完成租约。这确保了对这些块的任何后续写入都需要与主节点交互以查找租约持有者。这将给主节点一个机会先创建块的新副本。

在租约被撤销或过期后，主节点将操作记录到磁盘。然后，它通过复制源文件或目录树的元数据将此日志记录应用到其内存状态。新创建的快照文件指向与源文件相同的块。

快照操作后，客户端第一次想要写入块C时，它会向主节点发送请求以查找当前租约持有者。主节点注意到块C的引用计数大于1。它推迟回复客户端请求，而是选择一个新的块句柄C’。然后，它要求拥有C当前副本的每个块服务器创建一个名为C’的新块。通过在与原始块相同的块服务器上创建新块，我们确保数据可以在本地复制，而不是通过网络（我们的磁盘速度大约是我们100 Mb以太网链路的三倍）。从此时起，请求处理与任何其他块没有区别：主节点授予其中一个副本对新块C’的租约，并回复客户端，客户端可以正常写入该块，而不知道它刚刚从现有块创建。

4. 主节点操作

主节点执行所有命名空间操作。此外，它管理整个系统中的块副本：做出放置决策，创建新块及其副本，并协调各种系统范围的活动以保持块完全复制，平衡所有块服务器的负载，并回收未使用的存储。我们现在讨论这些主题中的每一个。

4.1 命名空间管理和锁定

许多主节点操作可能需要很长时间：例如，快照操作必须撤销快照所涵盖的所有块上的块服务器租约。我们不希望在这些操作运行时延迟其他主节点操作。因此，我们允许多个操作同时活动，并使用命名空间区域上的锁来确保正确的序列化。

与许多传统文件系统不同，GFS没有列出该目录中所有文件的每个目录数据结构。它也不支持同一文件或目录的别名（即Unix术语中的硬链接或符号链接）。GFS在逻辑上将其命名空间表示为将完整路径名映射到元数据的查找表。通过前缀压缩，该表可以在内存中高效表示。命名空间树中的每个节点（绝对文件名或绝对目录名）都有一个关联的读写锁。

每个主节点操作在运行前都会获取一组锁。通常，如果它涉及 /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的数据结构需要被保护免受修改。名称上的读锁足以保护父目录免遭删除。

这种锁定方案的一个好特性是它允许在同一目录中进行并发变更。例如，可以在同一目录中并发执行多个文件创建：每个获取目录名的读锁和文件名的写锁。目录名的读锁足以防止目录被删除、重命名或快照。文件名上的写锁序列化两次尝试创建同名文件的操作。

由于命名空间可以有许多节点，读写锁对象是延迟分配的，并在不再使用时删除。此外，锁以一致的全局顺序获取以防止死锁：它们首先按命名空间树中的级别排序，同一级别内按字典序排序。

4.2 副本放置

GFS集群在多个层面上高度分布。它通常有数百个块服务器，分布在不同机架的多台机器上。这些块服务器又可能被来自相同或不同机架的数百个客户端访问。不同机架上的两台机器之间的通信可能跨越一个或多个网络交换机。此外，进出机架的带宽可能小于该机架内所有机器的总带宽。多级分布为可扩展性、可靠性和可用性分配数据带来了独特的挑战。

块副本放置策略有两个目的：最大化数据可靠性和可用性，以及最大化网络带宽利用率。对于这两个目的，仅仅将副本分散到不同机器是不够的，这只能防止磁盘或机器故障，并充分利用每台机器的网络带宽。我们还必须将块副本分散到不同机架。这确保即使整个机架损坏或离线（例如，由于网络交换机或电源电路等共享资源故障），块的某些副本仍能存活并可用。这也意味着对块的流量，尤其是读取，可以利用多个机架的总带宽。另一方面，写入流量必须流经多个机架，这是我们愿意做出的权衡。

4.3 创建、重新复制、再平衡

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

当主节点创建块时，它会选择放置初始空副本的位置。它考虑几个因素：(1) 我们希望将新副本放置在磁盘空间利用率低于平均水平的块服务器上。随着时间的推移，这将均衡各块服务器的磁盘利用率。(2) 我们希望限制每个块服务器上“近期”创建的数量。尽管创建本身很廉价，但它可靠地预示着即将到来的大量写入流量，因为块是在写入需要时创建的，而在我们的“一次追加多次读取”工作负载中，一旦完全写入，它们通常变得几乎是只读的。(3) 如上所述，我们希望将块的副本分散到不同机架。

一旦可用副本数量低于用户指定的目标，主节点就会重新复制块。这可能由多种原因引起：块服务器变得不可用，它报告其副本可能已损坏，其某个磁盘因错误被禁用，或复制目标提高。每个需要重新复制的块都基于几个因素进行优先级排序。一个是它距离复制目标有多远。例如，我们为丢失了两个副本的块提供比丢失了一个副本的块更高的优先级。此外，我们更倾向于首先重新复制活动文件的块，而不是属于最近删除文件的块（见第4.4节）。最后，为了最小化故障对正在运行的应用的影响，我们提高了任何阻塞客户端进度的块的优先级。

主节点选择最高优先级的块，并通过指示某个块服务器直接从现有有效副本复制块数据来“克隆”它。新副本的放置目标与创建时类似：均衡磁盘空间利用率，限制任何单个块服务器上的活动克隆操作数量，并将副本分散到机架。为了防止克隆流量压垮客户端流量，主节点限制集群和每个块服务器上的活动克隆操作总数。此外，每个块服务器通过限制对源块服务器的读取请求来限制其花费在每个克隆操作上的带宽。

最后，主节点定期进行副本再平衡：它检查当前副本分布，并移动副本以实现更好的磁盘空间和负载均衡。同样通过这个过程，主节点逐渐填充新的块服务器，而不是立即用新块及其带来的大量写入流量淹没它。新副本的放置标准与上述类似。此外，主节点还必须选择移除哪个现有副本。通常，它倾向于移除那些位于空闲空间低于平均水平的块服务器上的副本，以均衡磁盘空间使用。

4.4 垃圾回收

文件被删除后，GFS不会立即回收可用的物理存储。它只在文件和块级别的常规垃圾回收期间惰性地进行回收。我们发现这种方法使系统更简单、更可靠。

4.4.1 机制

当应用程序删除文件时，主节点像其他更改一样立即记录删除。然而，资源不会立即回收，而是将文件重命名为一个包含删除时间戳的隐藏名称。在主节点定期扫描文件系统命名空间期间，它会删除任何存在时间超过三天（间隔可配置）的此类隐藏文件。在此之前，该文件仍然可以通过新的特殊名称读取，并且可以通过将其重命名回正常名称来取消删除。当隐藏文件从命名空间中移除时，其内存元数据被擦除。这有效地删除了其到所有块的链接。

在类似的块命名空间定期扫描中，主节点识别孤立块（即从任何文件都无法访问的块），并擦除这些块的元数据。在定期与主节点交换的心跳消息中，每个块服务器报告其拥有的块子集，主节点回复不再存在于主节点元数据中的所有块的标识。块服务器可以自由删除此类块的副本。

4.4.2 讨论

尽管分布式垃圾回收在编程语言上下文中是一个需要复杂解决方案的难题，但在我们这里却相当简单。我们可以轻松识别所有对块的引用：它们位于主节点独占维护的文件到块映射中。我们也可以轻松识别所有块副本：它们是每个块服务器上指定目录下的Linux文件。主节点未知的任何此类副本都是“垃圾”。

这种存储回收的垃圾回收方法与急切删除相比有几个优点。首先，它在组件故障常见的大规模分布式系统中简单可靠。块创建可能在某些块服务器上成功，但在其他块服务器上失败，留下主节点不知道存在的副本。副本删除消息可能丢失，主节点必须记住在故障（包括自身故障和块服务器故障）后重新发送它们。垃圾回收提供了一种统一且可靠的方式来清理任何未知有用的副本。其次，它将存储回收合并到主节点的常规后台活动中，例如命名空间的定期扫描和与块服务器的心跳握手。因此，它是批量进行的，成本被分摊。此外，它只在主节点相对空闲时进行。主节点可以更及时地响应需要及时关注的客户端请求。第三，回收存储的延迟为防止意外不可逆删除提供了安全网。

根据我们的经验，主要缺点是当存储紧张时，延迟有时会妨碍用户微调用法的努力。反复创建和删除临时文件的应用程序可能无法立即重用存储。我们通过如果删除的文件被再次显式删除则加速存储回收来解决这些问题。我们还允许用户对命名空间的不同部分应用不同的复制和回收策略。例如，用户可以指定某个目录树中所有文件的块无需复制存储，并且任何删除的文件将立即且不可撤销地从文件系统状态中移除。

4.5 过时副本检测

如果块服务器在停机期间错过了对块的变更，块副本可能会变得过时。对于每个块，主节点维护一个块版本号，以区分最新副本和过时副本。

每当主节点授予块的新租约时，它会增加块版本号，并通知最新的副本。主节点和这些副本都将新版本号记录在其持久状态中。这发生在任何客户端被通知之前，因此也发生在它可以开始写入该块之前。如果另一个副本当前不可用，其块版本号将不会增加。当该块服务器重启并报告其块集合及其关联版本号时，主节点将检测到它具有过时的副本。如果主节点看到版本号大于其记录中的版本号，则主节点假定它在授予租约时失败，因此将较高的版本视为最新的。

主节点在其常规垃圾回收中移除过时的副本。在此之前，当回复客户端对块信息的请求时，它实际上将过时副本视为不存在。作为另一项保障，当主节点通知客户端哪个块服务器持有块的租约，或指示块服务器在克隆操作中从另一个块服务器读取块时，它会包含块版本号。客户端或块服务器在执行操作时验证版本号，以确保始终访问最新数据。

5. 容错与诊断

我们设计系统时最大的挑战之一是处理频繁的组件故障。组件的质量和数量共同使得这些问题更像是常态而非例外：我们不能完全信任机器，也不能完全信任磁盘。组件故障可能导致系统不可用，更糟糕的是，数据损坏。我们讨论如何应对这些挑战，以及我们在系统中内置的诊断工具，以便在问题不可避免地发生时进行诊断。

5.1 高可用性

在GFS集群的数百台服务器中，某些在任何给定时间都必然不可用。我们通过两种简单而有效的策略保持整个系统的高可用性：快速恢复和复制。

5.1.1 快速恢复

主节点和块服务器都被设计为无论以何种方式终止，都能在几秒钟内恢复其状态并启动。事实上，我们不区分正常和异常终止；服务器通常通过直接杀死进程来例行关闭。客户端和其他服务器在等待其未完成请求超时、重新连接到重启的服务器并重试时，会经历轻微的中断。第6.2.2节报告了观察到的启动时间。

5.1.2 块复制

如前所述，每个块在位于不同机架的多台块服务器上复制。用户可以为文件命名空间的不同部分指定不同的复制级别。默认是三个。主节点根据需要克隆现有副本，以在块服务器离线或通过校验和验证检测到损坏副本（见第5.2节）时保持每个块的完全复制。尽管复制对我们来说效果很好，但我们正在探索其他形式的跨服务器冗余，如奇偶校验或纠删码，以满足我们日益增长的只读存储需求。我们预计，在我们这种非常松耦合的系统中实现这些更复杂的冗余方案具有挑战性但可控，因为我们的流量主要由追加和读取主导，而不是小型随机写入。

5.1.3 主节点复制

主节点状态为可靠性而复制。其操作日志和检查点在多台机器上复制。只有当日志记录已在本地和所有主节点副本上刷新到磁盘后，对状态的变更才被视为已提交。为简单起见，一个主进程仍然负责所有变更以及内部更改系统的后台活动，如垃圾回收。当它失败时，它可以几乎立即重启。如果其机器或磁盘故障，GFS外部的监控基础设施会在其他地方使用复制的操作日志启动一个新的主进程。客户端只使用主节点的规范名称（例如 gfs-test），这是一个DNS别名，如果主节点迁移到另一台机器，可以更改它。

此外，“影子”主节点在主主节点宕机时提供对文件系统的只读访问。它们是影子而非镜像，因为它们可能略微滞后于主节点，通常只有几分之一秒。它们增强了对于未被积极变更的文件或不介意稍微过时结果的应用程序的读取可用性。实际上，由于文件内容是从块服务器读取的，应用程序不会观察到过时的文件内容。可能过时的是文件元数据，如目录内容或文件属性。

5.2 数据完整性

每个块服务器使用校验和来检测存储数据的损坏。由于磁盘数量庞大，我们发现在磁盘或IDE子系统级别发生数据损坏的可能性不小。因此，校验和对GFS的正常运行至关重要。

每个块被划分为64 KB的块（block）。每个这样的块都有一个相应的32位校验和。与元数据类似，校验和存储在内存中，并使用日志持久存储，与用户数据分开。

在读取时，块服务器在将数据返回给客户端之前，验证所请求范围内数据块的校验和。因此，校验和不会传播到客户端。如果块服务器检测到损坏的块，它会向读取器返回错误，并通知主节点损坏情况。读取器将尝试从其他副本读取。同时，主节点会尽快克隆一个有效的副本，以将损坏的副本替换为健康的副本。由于主节点知道所有副本的位置，因此无需其他机制即可重新复制。

校验和对读取性能影响不大，因为块服务器在将数据返回给客户端之前会验证校验和。我们通过几种方式优化校验和计算。由于大多数读取跨越至少几个块，我们只计算和验证与读取范围重叠的部分的校验和，从而减少开销。此外，我们通常将校验和与数据块的布局对齐，以确保校验和计算在追加写入中成本最低。对于追加写入，我们只更新最后一个部分块的校验和，而对于新创建的完整块，我们计算其校验和并存储。如果现有块已损坏且无法恢复，即使在读取时我们发现它已损坏，我们也不会从磁盘读取它。

6. 测量

在本节中，我们通过微基准测试和实际集群测量来呈现GFS性能的快照。

6.1 微基准测试

我们在一组由16个块服务器和16个客户端组成的集群上测量了GFS的性能。使用此配置来清晰隔离网络拓扑的影响。块服务器和客户端机器配置相同：双路PIII 1.4 GHz处理器，2 GB内存，两个80 GB 5400 rpm ATA-100硬盘，以及100 Mbps全双工以太网连接到一台HP 2524交换机。所有16台机器都连接到同一台交换机；其上行链路通过一台HP 4108交换机以1 Gbps连接到另一台有16块服务器的交换机。块服务器的磁盘容量为160 GB，但文件系统仅使用其中的部分空间。

6.1.1 读取

N个客户端并发地从GFS读取。每个客户端从一组包含总计1 GB数据的320个文件中的随机文件读取。读取操作每次读取1 MB，除了最后一次。图3(a)显示了N个客户端的聚合读取速率及其理论极限。当两台交换机之间的1 Gbps链路饱和时，极限峰值达到125 MB/s的总聚合吞吐量，或者当客户端的100 Mbps网络接口饱和时，达到每个客户端12.5 MB/s，以先达到者为准。当只有一个客户端读取时，观察到的读取速率为10 MB/s，即每个客户端限制的80%。对于16个读取器，聚合读取速率达到94 MB/s，约为125 MB/s链路限制的75%，即每个客户端6 MB/s。效率从80%下降到75%，因为随着读取器数量的增加，多个读取器同时从同一个块服务器读取的概率也增加了。

6.1.2 写入

N个客户端同时向N个不同的文件写入。每个客户端以一系列1 MB写入的方式向一个新文件写入1 GB数据。聚合写入速率及其理论极限如图3(b)所示。极限在67 MB/s处达到平台期，因为我们需要将每个字节写入16个块服务器中的3个，每个块服务器的输入连接为12.5 MB/s。

单个客户端的写入速率为6.3 MB/s，约为限制的一半。主要原因是我们的网络堆栈。它与我们用于将数据推送到块副本的流水线方案交互不佳。数据从一个副本传播到另一个副本的延迟降低了整体写入速率。

16个客户端的聚合写入速率达到35 MB/s（或每个客户端2.2 MB/s），约为理论极限的一半。与读取情况类似，随着客户端数量的增加，多个客户端同时写入同一个块服务器的可能性增加。此外，16个写入者的冲突可能性比16个读取者更大，因为每个写入涉及三个不同的副本。

写入速度比我们期望的要慢。在实践中，这并未成为主要问题，因为尽管它增加了单个客户端看到的延迟，但并未显著影响系统提供给大量客户端的聚合写入带宽。

6.1.3 记录追加

图3(c)显示了记录追加性能。N个客户端同时向单个文件追加数据。性能受限于存储文件最后一个块的块服务器的网络带宽，与客户端数量无关。它从单个客户端的6.0 MB/s开始，下降到16个客户端的4.8 MB/s，主要是由于拥塞和不同客户端看到的网络传输速率差异。

我们的应用程序倾向于同时生成多个此类文件。换句话说，N个客户端同时向M个共享文件追加数据，其中N和M都在几十或几百。因此，我们实验中的块服务器网络拥塞在实践中不是重大问题，因为当另一个文件的块服务器繁忙时，客户端可以在一个文件上继续写入。

6.2 实际集群

我们现在检查谷歌内部使用的两个集群，它们代表了其他几个类似的集群。集群A定期用于研发，由一百多名工程师使用。典型任务由人类用户发起，运行数小时。它读取几MB到几TB的数据，转换或分析数据，并将结果写回集群。集群B主要用于生产数据处理。任务运行时间长得多，持续生成和处理多TB数据集，只有偶尔的人工干预。在这两种情况下，单个“任务”由许多机器上的许多进程同时读取和写入许多文件组成。

6.2.1 存储

如表的前五个条目所示，两个集群都有数百个块服务器，支持许多TB的磁盘空间，并且相当满但未完全满。“已用空间”包括所有块副本。几乎所有文件都复制了三份。因此，这些集群分别存储了18 TB和52 TB的文件数据。

这两个集群的文件数量相似，但B中死文件（即已被删除或被新版本替换但存储尚未回收的文件）的比例更大。它也有更多的块，因为它的文件往往更大。

6.2.2 元数据

块服务器总共存储了数十GB的元数据，主要是用户数据64 KB块的校验和。块服务器上唯一保留的其他元数据是第4.5节讨论的块版本号。

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

每个单独的服务器，无论是块服务器还是主节点，只有50到100 MB的元数据。因此恢复很快：在服务器能够响应查询之前，只需几秒钟即可从磁盘读取这些元数据。然而，主节点在一段时间内（通常为30到60秒）会受到一定阻碍，直到它从所有块服务器获取块位置信息。

6.2.3 读写速率

表3显示了不同时间段的读写速率。进行这些测量时，两个集群都已运行约一周。（集群最近被重启以升级到新版本的GFS。）

自重启以来的平均写入速率低于30 MB/s。当我们进行这些测量时，B正处于写入活动爆发期，生成约100 MB/s的数据，因为写入传播到三个副本，产生了300 MB/s的网络负载。

读取速率远高于写入速率。总工作负载包含的读取多于写入，正如我们的假设。两个集群都处于大量读取活动中。特别是，A在过去一周一直维持着580 MB/s的读取速率。其网络配置可以支持750 MB/s，因此它正在有效利用其资源。集群B可以支持1300 MB/s的峰值读取速率，但其应用程序仅使用了380 MB/s。

6.2.4 主节点负载

表3还显示发送到主节点的操作速率约为每秒200到500次操作。主节点可以轻松跟上此速率，因此对于这些工作负载来说不是瓶颈。

在早期版本的GFS中，主节点有时会成为某些工作负载的瓶颈。它大部分时间用于顺序扫描大型目录（包含数十万个文件）以查找特定文件。此后，我们更改了主节点数据结构，以允许通过命名空间进行高效二进制搜索。它现在可以轻松支持每秒数千次文件访问。如果需要，我们可以通过在命名空间数据结构前放置名称查找缓存来进一步加速。

6.2.5 恢复时间

块服务器故障后，一些块将变得复制不足，必须克隆以恢复其复制级别。恢复所有这些块所需的时间取决于资源量。在一个实验中，我们终止了集群B中的一个块服务器。该块服务器拥有约15,000个块，包含600 GB数据。为了限制对运行中应用程序的影响并为调度决策留出余地，我们的默认参数将此集群的并发克隆限制为91个（块服务器数量的40%），其中每个克隆操作允许消耗最多6.25 MB/s（50 Mbps）。所有块在23.2分钟内恢复，有效复制速率为440 MB/s。

在另一个实验中，我们终止了两个块服务器，每个拥有约16,000个块和660 GB数据。这种双重故障导致266个块只剩下一个副本。这266个块以更高的优先级克隆，并在2分钟内全部恢复到至少2倍复制，从而使集群处于能够容忍另一次块服务器故障而不丢失数据的状态。

6.3 工作负载细分

在本节中，我们详细介绍了两个GFS集群的工作负载细分，它们与第6.2节中的集群相当但不完全相同。集群X用于研发，而集群Y用于生产数据处理。

6.3.1 方法和注意事项

这些结果仅包括客户端发起的请求，因此它们反映了我们的应用程序对整个文件系统生成的工作负载。它们不包括为执行客户端请求而发出的服务器间请求或内部后台活动，如转发写入或再平衡。

I/O操作的统计数据基于从GFS服务器记录的RPC请求启发式重建的信息。例如，GFS客户端代码可能将一次读取分解为多个RPC以增加并行性，我们从中推断原始读取。由于我们的访问模式高度程式化，我们预计任何误差都在噪声范围内。应用程序显式日志记录可能提供稍准确的数据，但重新编译和重启数千个运行中的客户端在逻辑上不可行，并且从这么多机器收集结果也很麻烦。

应注意不要过度概括我们的工作负载。由于谷歌完全控制GFS及其应用程序，应用程序倾向于针对GFS进行调优，反之GFS也为这些应用程序设计。这种相互影响也可能存在于通用应用程序和文件系统之间，但在我们的情况下效果可能更明显。

6.3.2 块服务器工作负载

表4显示了按大小分类的操作分布。读取大小呈现双峰分布。小型读取（小于64 KB）来自在大型文件中查找小块数据的、以寻道为主的客户端。大型读取（超过512 KB）来自对整个文件进行长顺序读取。

在集群Y中，相当数量的读取不返回任何数据。我们的应用程序，尤其是生产系统中的应用程序，经常将文件用作生产者-消费者队列。生产者并发地向文件追加数据，而消费者读取文件末尾。偶尔，当消费者超过生产者时，不会返回数据。集群X较少出现这种情况，因为它通常用于短期数据分析任务，而不是长期运行的分布式应用。

写入大小也呈现双峰分布。大型写入（超过256 KB）通常由写入者内部的大量缓冲产生。缓冲较少、检查点或同步更频繁，或生成数据较少的写入者对应较小的写入（小于64 KB）。

至于记录追加，集群Y看到的较大记录追加百分比远高于集群X，因为使用集群Y的生产系统针对GFS进行了更积极的调优。

表5显示了各种大小操作传输的总数据量。对于所有类型的操作，较大的操作（超过256 KB）通常占传输字节的大部分。小型读取（小于64 KB）确实传输了一小部分但相当可观的读取数据，因为存在随机寻道工作负载。

6.3.3 追加与写入

记录追加在我们生产系统中尤其被大量使用。对于集群X，按传输字节计算，写入与记录追加的比例为108:1，按操作计数为8:1。对于用于生产系统的集群Y，这些比例分别为3.7:1和2.5:1。此外，这些比例表明两个集群的记录追加往往大于写入。然而，对于集群X，在测量期间记录追加的整体使用率相当低，因此结果可能被一两个具有特定缓冲区大小选择的应用程序所偏斜。

正如预期，我们的数据变更工作负载以追加而非覆盖为主。我们测量了主副本上被覆盖的数据量。这近似于客户端有意覆盖先前写入的数据而不是追加新数据的情况。对于集群X，覆盖占变更字节的不到0.0001%，占变更操作的不到0.0003%。对于集群Y，这两个比例均为0.05%。尽管这微不足道，但仍高于我们的预期。事实证明，这些覆盖大部分来自因错误或超时而导致的客户端重试。它们本身不是工作负载的一部分，而是重试机制的后果。

6.3.4 主节点工作负载

表6显示了按请求类型细分的主节点请求。大多数请求是用于读取的块位置查找（FindLocation）和用于数据变更的租约持有者信息查找（FindReleaseLocker）。

集群X和Y看到的Delete请求数量显著不同，因为集群Y存储的生产数据集会定期重新生成并替换为新版本。这种差异的一部分进一步隐藏在Open请求的差异中，因为文件的旧版本可能通过从头开始以写入模式打开而被隐式删除。

FindMatchingFiles是一个模式匹配请求，支持“ls”和类似的文件系统操作。与对主节点的其他请求不同，它可能处理命名空间的大部分，因此可能开销较大。集群Y更频繁地看到它，因为自动化数据处理任务倾向于检查文件系统的部分以了解全局应用状态。相比之下，集群X的应用程序处于更明确的用户控制下，通常事先知道所有所需文件的名称。

7. 经验

在构建和部署GFS的过程中，我们遇到了各种各样的问题，有些是操作性的，有些是技术性的。

最初，GFS被设想为生产系统的后端文件系统。随着时间的推移，使用范围扩大到包括研发任务。它开始时对权限和配额等支持很少，但现在包含了这些的基本形式。尽管生产系统纪律严明且受到控制，但用户有时并非如此。需要更多的基础设施来防止用户相互干扰。

我们最大的一些问题与磁盘和Linux有关。我们的许多磁盘向Linux驱动程序声称支持一系列IDE协议版本，但实际上只能可靠地响应较新的版本。由于协议版本非常相似，这些驱动器大多可以工作，但偶尔的不匹配会导致驱动器与内核关于驱动器状态的分歧。这会由于内核问题而静默损坏数据。这个问题促使我们使用校验和来检测数据损坏，同时我们修改了内核以处理这些协议不匹配。

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

另一个Linux问题是一个单一的读写锁，任何线程在从磁盘读入页面（读锁）或在 mmap 调用中修改地址空间（写锁）时都必须持有该锁。我们在轻负载下看到了系统瞬态超时，并仔细寻找资源瓶颈或偶发硬件故障。最终，我们发现当磁盘线程正在调入先前映射的数据时，这个单一锁阻塞了主网络线程将新数据映射到内存。由于我们主要受限于网络接口而非内存复制带宽，我们通过用 pread 替换 mmap 来解决这个问题，代价是额外的一次复制。

尽管存在偶尔的问题，Linux代码的可用性一次又一次地帮助我们探索和理解系统行为。在适当的时候，我们改进内核并与开源社区分享更改。

8. 相关工作

像AFS [5]等其他大型分布式文件系统一样，GFS提供了位置无关的命名空间，使得数据能够透明地移动以实现负载平衡或容错。与AFS不同，GFS以类似于xFS [1]和Swift [3]的方式将文件数据分布到存储服务器上，以实现聚合性能和更高的容错能力。

由于磁盘相对便宜，并且复制比更复杂的RAID [9]方法更简单，GFS目前仅使用复制来实现冗余，因此消耗的原始存储比xFS或Swift更多。

与AFS、xFS、Frangipani [12]和Intermezzo [6]等系统相比，GFS在文件系统接口之下不提供任何缓存。我们的目标工作负载在单个应用程序运行中重用很少，因为它们要么流式处理大型数据集，要么在其中随机寻道并每次读取少量数据。

像Frangipani、xFS、Minnesota的GFS[11]和GPFS [10]等一些分布式文件系统去除了集中式服务器，并依赖分布式算法进行一致性和管理。我们选择集中式方法以简化设计、提高可靠性并获得灵活性。特别是，集中式主节点使得实现复杂的块放置和复制策略更加容易，因为主节点已经拥有大部分相关信息并控制其变化。我们通过保持主节点状态较小并在其他机器上完全复制来解决容错问题。可扩展性和高可用性（对于读取）目前由我们的影子主节点机制提供。对主节点状态的更新通过追加到预写日志来持久化。因此，我们可以采用类似Harp [7]中的主副本方案来提供比我们当前方案更强一致性保证的高可用性。

在向大量客户端提供聚合性能方面，我们处理的问题与Lustre [8]类似。然而，我们通过专注于应用程序的需求而不是构建POSIX兼容的文件系统，大大简化了问题。此外，GFS假设大量不可靠组件，因此容错是我们设计的核心。

GFS与NASD架构[4]最为相似。虽然NASD架构基于网络连接磁盘驱动器，但GFS使用通用机器作为块服务器，如同NASD原型所做的那样。与NASD工作不同，我们的块服务器使用延迟分配的固定大小块，而不是可变长度对象。此外，GFS实现了生产环境所需的诸如再平衡、复制和恢复等功能。

与Minnesota的GFS和NASD不同，我们不试图改变存储设备的模型。我们专注于使用现有通用组件满足复杂分布式系统的日常数据处理需求。

记录追加所实现的生产者-消费者队列解决了与River [2]中的分布式队列类似的问题。River使用分布在机器间的基于内存的队列和仔细的数据流控制，而GFS使用一个持久文件，许多生产者可以并发地追加到该文件。River模型支持m对n分布式队列，但缺乏持久存储带来的容错能力，而GFS仅高效支持m对1队列。多个消费者可以读取同一个文件，但它们必须协调以划分传入负载。

9. 结论

谷歌文件系统展示了在通用硬件上支持大规模数据处理工作负载所必需的关键品质。虽然某些设计决策特定于我们的独特环境，但许多可能适用于具有相似规模和成本意识的数据处理任务。

我们首先根据当前和预期的应用负载及技术环境，重新审视了传统文件系统假设。我们的观察导致了设计空间中截然不同的出发点。我们将组件故障视为常态而非例外，针对大多数被追加（可能并发地）然后被读取（通常是顺序地）的巨大文件进行优化，并扩展和放宽了标准文件系统接口以改善整体系统。

我们的系统通过持续监控、复制关键数据以及快速自动恢复来提供容错能力。块复制允许我们容忍块服务器故障。这些故障的频率促使了一种新颖的在线修复机制，该机制定期且透明地修复损坏，并尽快弥补丢失的副本。此外，我们使用校验和来检测磁盘或IDE子系统级别的数据损坏，鉴于系统中的磁盘数量，这变得非常普遍。

我们的设计为执行各种任务的众多并发读写器提供了高聚合吞吐量。我们通过将文件系统控制（流经主节点）与数据传输（直接在块服务器和客户端之间进行）分离来实现这一点。通过大块大小和块租约（将权限委托给主副本进行数据变更），最小化了主节点在常见操作中的参与。这使得一个简单、集中式的主节点不会成为瓶颈成为可能。我们相信，我们网络堆栈的改进将消除当前单个客户端所见写入吞吐量的限制。

GFS已成功满足我们的存储需求，并在谷歌内部被广泛用作研发和生产数据处理的存储平台。它是一个重要的工具，使我们能够继续创新并应对整个网络规模的问题。

致谢

我们希望感谢以下人员对系统或本文的贡献。Brian Bershah（我们的指导者）和匿名审稿人给了我们宝贵的评论和建议。Anurag Acharya、Jeff Dean和David desJardins为早期设计做出了贡献。Fay Chang致力于跨块服务器的副本比较工作。Guy Edjali致力于存储配额工作。Markus Gutschke致力于测试框架和安全增强。David Kramer致力于性能增强。Fay Chang、Urs Hoelzle、Max Ibel、Sharon Perl、Rob Pike和Debby Wallach对本文的早期草稿提供了评论。我们在谷歌的许多同事勇敢地将他们的数据托付给一个新的文件系统，并给了我们有用的反馈。Yoshka帮助了早期测试。

参考文献

[1] Thomas Anderson, Michael Dahlin, Jeanna Neefe, David Patterson, Drew Roselli, and Randolph Wang. Serverless network file systems. In Proceedings of the 15th ACM Symposium on Operating System Principles, pages 109-126, Copper Mountain Resort, Colorado, December 1995. [2] Remzi H. Arpaci-Dusseau, Eric Anderson, Noah Treuhaft, David E. Culler, Joseph M. Hellerstein, David Patterson, and Kathy Yelick. Cluster I/O with River: Making the fast case common. In Proceedings of the Sixth Workshop on Input/Output in Parallel and Distributed Systems (IOPADS ‘99), pages 10-22, Atlanta, Georgia, May 1999. [3] Luis-Felipe Cabrera and Darrell D. E. Long. Swift: Using distributed disk striping to provide high I/O data rates. Computer Systems, 4(4):405-436, 1991. [4] Garth A. Gibson, David F. Nagle, Khalil Amiri, Jeff Butler, Fay W. Chang, Howard Gobioff, Charles Hardin, Erik Riedel, David Rochberg, and Jim Zelenka. A cost-effective, high-bandwidth storage architecture. In Proceedings of the 8th Architectural Support for Programming Languages and Operating Systems, pages 92-103, San Jose, California, October 1998. [5] John Howard, Michael Kazar, Sherri Menees, David Nichols, Mahadev Satyanarayanan, Robert Sidebotham, and Michael West. Scale and performance in a distributed file system. ACM Transactions on Computer Systems, 6(1):51-81, February 1988. [6] InterMezzo. http://www.inter-mezzo.org, 2003. [7] Barbara Liskov, Sanjay Ghemawat, Robert Gruber, Paul Johnson, Liuba Shrira, and Michael Williams. Replication in the Harp file system. In 13th Symposium on Operating System Principles, pages 226-238, Pacific Grove, CA, October 1991. [8] Lustre. http://www.lustre.org, 2003. [9] David A. Patterson, Garth A. Gibson, and Randy H. Katz. A case for redundant arrays of inexpensive disks (RAID). In Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pages 109-116, Chicago, Illinois, September 1988. [10] Frank Schmuck and Roger Haskin. GPFS: A shared-disk file system for large computing clusters. In Proceedings of the First USENIX Conference on File and Storage Technologies, pages 231-244, Monterey, California, January 2002. [11] Steven R. Soltis, Thomas M. Ruwart, and Matthew T. O’Keefe. The Gobal File System. In Proceedings of the Fifth NASA Goddard Space Flight Center Conference on Mass Storage Systems and Technologies, College Park, Maryland, September 1996. [12] Chandramohan A. Thekkath, Timothy Mann, and Edward K. Lee. Frangipani: A scalable distributed file system. In Proceedings of the 16th ACM Symposium on Operating System Principles, pages 224-237, Saint-Malo, France, October 1997.

（翻译结束）