GFS论文笔记

介绍

GFS的诞生来源于google日益增长的数据量的处理需求，它是一个可扩展的分布式文件系统，用于大型分布式数据密集型应用，在廉价的通用硬件上运行时提供容错机制，并且可以为大量客户端提供较高的聚合性能。
它的设计由当前和预期的应用负载(当时的)和技术环境驱动，与以前的文件系统的假设有着明显不同，因此gfs在设计上有几个不同的points：

1. 组件故障是正常现象。文件系统包含成百上千台由廉价组件构成的机器并且被大量客户端访问，某些组件可能会在任意时刻出现故障，这些问题可以来源于应用bugs、操作系统bugs、人的操作失误、硬盘内存连接器网络和电源故障等，因此系统监控、错误检测、容错和自动恢复功能都是系统不可或缺的。
2. 传统系统中的文件是非常大的，数GB的文件非常常见。每个文件通常包含很多应用的objects，当应用于快速增长的数据集中时，数TB的文件包含数十亿的objects，这种管理方式将会很难控制。因此必须重新设计例如I/O操作和块大小。
3. 大多数文件的变动是通过append新的数据而不是重写已存在的数据。随机写几乎不存在。基于这个特征，appending成为性能优化和原子保证的关键，在客户端缓存数据块已经不再有吸引力。
4. 共同设计应用程序和文件系统API，提高灵活性。比如gfs简化了一致性模型，以极大简化文件系统而又不会给应用程序带来繁重的负担，还引入了原子的append以使得多个客户端可以并发地操作，它们不用增加额外的同步逻辑。

当前已部署多个集群用于不同目的，最大的拥有1000多个存储节点，超过300TB的存储服务，并且有数百个客户端连续不断地高负载请求。

设计概述

假设

前面提到一些对应用负载和技术环境的观察，现在更详细地进行阐述：

1. 系统构建在许多廉价的组件之上，它们会经常出故障，因此系统必须不断地自我监控、定期检测、容错并可以从故障中快速恢复。
2. 系统存储适量的大文件。预计有几百个文件，每个文件的大小通常为100MB或者更大，数GB的文件也是常见的，需要有效地进行管理。小文件必须支持但不需要专门地优化。
3. 读负载主要包含两种类型的请求：large stream read and small random read。数MB与数KB。性能敏感的应用程序通常会对小的读请求做批量处理和排序。
4. 写负载通常是大的顺序写，通过追加写的方式。操作的大小与读请求相似，一旦写后文件几乎不会再次被修改。也支持小的随机写，但是效率很低。
5. 多个客户端可以高效地进行并发append操作很关键。例如文件经常用于生产者-消费者队列或者多路归并，数百个生产者并发地append数据到同一个文件，同步的代价将是不可忽视的。
6. 高吞吐比低延迟更重要。大多数的目标应用都非常重视是否可以高速率地处理数据，很少会对读写的相应时间有较高的要求。

接口

虽然GFS不能提供像POSIX标准的API，但它提供一个相似的文件系统接口。文件在目录中按层次结构组织，并以路径名作为标识。支持create、delete、open、close、read and write files。

gfs支持快照和record append操作。快照以低代价创建文件副本或者目录树，record append支持多个客户端并发地写文件，保证每个独立客户端append的原子性。

架构

一个gfs集群包含一个master和多个chunkservers，chunkserver被多个客户端访问，如图1所示。每一个都是普通linux机器上运行的用户态服务进程。资源允许的情况下，客户端可以和chunkserver部署在同一台机器上。

文件被划分为固定大小的块。每个chunk由一个独一无二的64位大小的chunk handle所标识，chunk handle在chunk被创建时由master分配。每个chunk的副本分布在多个机器上，系统默认为三副本模式，用户也可以为不同namespace的文件指定不同级别的副本。

master包含文件系统的所有元信息。包含namespace、访问控制权限信息、文件到chunks的映射、当前chunks的位置信息。也控制着全局的活动，像chunk租约管理、gc、chunk迁移等。master通过心跳的方式与每个chunkserver交流来发送它的指令和收集状态。

客户端与master的交互涉及元信息操作，所有数据操作直接与chunkserver交互。gfs不提供POSIX标准API，因此不需要挂接到linux的vnode层。

客户端和chunkserver都不缓存文件数据。大多数应用传输大文件，客户端缓存收益很低。chunks作为本地的文件存储，linux系统有自己的buffer cache，chunkserver不需要再增加缓存。

单master

单master简化了系统的设计，但是会有单点的瓶颈问题，这是必须要解决的。客户端不会从master读写数据文件，客户端请求master它需要的交互的chunkserver信息，并且将其缓存一段时间，后续的操作直接与chunkservers交互。

客户端会发送请求给离它最近的一个副本。实际上，客户端通常会向master请求多个chunk的信息，以减少未来与maser交互的代价。

Chunk Size

chunk size定为64MB，相比普通的文件系统的block size更大。每个chunk副本以linux文件的形式存在chunkserver上，仅根据需要来扩展。使用lazy space allocation的方式避免空间浪费。

large chunk size有以下几个优点：

1. 减少客户端与master的交互。对于数TB的工作集，客户端可以缓存住所有chunks的位置信息。
2. 减少网络overhead开销。
3. 减少了master所维护的元信息大小。

但是large chunk size with lazy space allocation也有其缺点：单个文件可能包含很少数量的chunks，或许只有一个，当许多客户端访问相同文件时这些chunks成为热点。但由于目标应用大多是顺序的读多个large chunk文件，热点并不是主要的问题。
然而GFS第一次用于批处理队列系统时确实出现了热点问题，数百个客户端同时访问一个单chunk文件，存储这个文件的几个chunkserver超负荷运转，当时通过错开应用的启动时间避免了这个问题，一个潜在、长期的解决方法是允许客户端从其它客户端读取数据。

元数据

master保存三种类型的元数据：

• the file and chunk namspaces
• 文件到chunks的映射
• 每个chunk副本的位置信息

所有元数据都保存在内存中。对于元数据的内存操作是很快的，后台任务周期巡检整个状态也是比较简单高效的。周期巡检用于实现chunk gc、在chunkserver故障时重新构造副本、chunk迁移以平衡多个chunkserver的负载和disk usage。
虽然系统的容量受master内存大小的限制，但这并不是一个严重的问题，64MB的chunk只需要不到64byte大小的元信息，如果一定需要更大的文件系统，那么增加内存的代价相比为可靠性、性能和灵活性等付出的代价是较小的。

前两种类型的元数据通过写日志来保证持久化，并且会复制日志到远程机器上。master不需要将chunks的位置信息持久化，而是在master启动和新的chunkserver加入集群时向每个chunkserver询问它的位置信息，之后通过心跳信息监控chunk位置变更信息。chunkserver作为最后一关是确切知道自己本地有没有哪些chunk的，因此维护一个一致性的视图是没有必要的。

operation log包含元数据的变更记录，它是GFS的核心，它不仅仅是唯一的元数据持久化记录，也表明了并发操作的逻辑时间线。文件、chunks和它们的版本都是由逻辑时间线唯一标识。元数据变更记录在持久化之前对客户端是不可见的，而且日志被复制到多个远程的机器，只有相应的记录在本地和远程都持久化到硬盘了才可以回复客户端。master使用批处理log的方式提高系统的吞吐。

master通过回放日志来恢复文件系统的状态，为提高恢复速度需要保持log量足够小。当log增长超过特定大小时，master会checkpoint它的状态，以加速恢复提高可用性。构建checkpoint可能需要花费一段时间，因此master以一种不delay后续变化的方式来组织内部状态，先switch到一个新的日志文件，使用独立的线程创建checkpoint，新的checkpoint包含了所有switch之前的变化。几百万个文件的集群在一分钟内可以完成，完成后将同时被写入本地和远程。恢复只需要最新的checkpoint和之后的日志文件，旧的checkpoints和日志文件可以完全删除。

一致性模型

GFS使用一个宽松的一致性模型，这种模型可以很好地支持分布式应用程序，而且实现起来简单有效。
file namesapce变化(例如文件创建)是原子的，使用namespace锁。
master的operation log定义了这些操作的全局顺序。

数据变化后文件region的状态取决于变化的类型，是否成功、失败或者是并发的。Table1做了总结。如果所有客户端都能看到相同的数据，无论它们读的是哪个副本，则这个file region是一致的。

• region defined: 一致的并且客户端可以看到变化的全貌。比如没有并发的write并且是成功的。
• undefined but consistent： 并发且成功的变化使region是一致的，但是客户端无法识别出哪一个mutation写了什么。
• inconsistent: failed mutations。不同的客户端可能在不同时间看到不同的数据。

数据变化有两种：writes或者record appends。write是指从应用指定offset处开始写数据，record append指即使存在并发冲突，数据也要被原子地append到文件至少一次，但offset是由GFS选定。

GFS保证在一系列成功的mutations后，file region是defined，通过下面两点来保证：

1. 以相同的order在所有包含数据的副本上apply这些mutations。
2. 使用chunk version来检测副本是否遗漏了mutations而过期(它的chunkserver下线)。

过期的副本将不会再涉及到任何mutation，master也不会将其位置信息回应给客户端，不久后将会被gc。但客户端缓存的信息可能包含过期的副本，缓存失效存在一个时间窗口，文件再次打开也会清除该文件的所有chunk信息。由于大多数文件是append-only，过期的副本通常返回的是过早的结尾???而不是过期的数据。

系统交互

介绍客户端、master和chunkserver之间如何交互来实现数据变化、原子追加写和快照的。

租约和Mutation Order

使用租约的方式维护多个副本间一致的mutation order。master授权租约给副本中的一个，称之为primary。primary为chunk的mutaions选择一个顺序，所有副本都按照这个顺序apply。
租约机制最小化了master的管理overhead。租约初始的超时时间是60s，如果chunk一直在变化过程中，primary可以申请续租。这些授权和续租请求由master和chunkserver之间的心跳信息携带。master也可以尝试撤销租约，即使它与primary失去了联系，也可以等租约过期后安全地授权给另外一个副本。

在Figure2中，跟随着写入控制流展示了处理过程：

1. 客户端请求master持有当前租约的chunk和其它副本的位置信息，如果没有人持有租约，master选择一个授权。
2. master回应客户端primary和其它副本的位置信息，客户端将其缓存，只有当primary连接不上或者不再持有租约时需要再次请求master。
3. 客户端将数据push到所有的副本，可以以任意的顺序。每个chunkserver将数据存储在LRU缓存中，直到数据被使用或者过期。通过将数据流和控制流分离，忽略哪个chunkserver是primary，数据流以网络拓扑的方式传输提升性能。
4. 当所有副本都确认收到了数据，客户端发送写请求给primary，primary为收到的mutations分配一个顺序，这些mutations可能是来自多个客户端，然后以这个顺序将mutation应用到自己本地状态。
5. primary将写请求发给所有的副本，每个副本按照相同的顺序应用到本地。
6. 二级副本完成操作后回应给primary。
7. primary回应客户端。在任何副本上遇到的任何错误都将报告给客户端，一旦出现错误，write可能在primary和任意二级副本的子集中成功完成(如果primary失败，则不会分配序列并转发)。客户端请求将被认为failed，修改的region处于不一致的状态，通过客户端重试来处理，将从步骤3开始到步骤7。

如果一个写请求比较大或者超出了chunk边界，GFS客户端将它拆为多个写操作，但是多个操作可能与其它客户端并发交叉写入，因此共享的fie region最终可能包含多个不同客户端的碎片，这会造成一致性模型中所描述的file region处于consistent but undefined状态。

数据流

数据以pipline的机制在chunkserver链上线性传输，而控制流是从客户端到primary再到所有的其它副本。分离数据流和控制流可以更高效地使用网络。可以带来以下好处：

• 充分利用每个机器的网络带宽。数据push按照chunkserver链线性传输而非一些其它拓扑形式，每台机器可以打满自己outbound bandwidth。
• 避免网络瓶颈和高延迟连接。每台机器选择网络拓扑中没有接收数据并且离他最近的一个进行传输数据。网络拓扑的"距离"使用IP地址简单估算。
• 最小化数据传输的延迟。通过pipline传输数据的方式，因为使用全双向连接的网络，发送数据不会减少接收的速率。

Atomic Record Appends

GFS提供原子的append operaton叫作record append。传统的write中，客户端指定offset，并发写相同region时不是serializable，最终region可能包含多个客户端的碎片数据。而对于record append，客户端仅指定数据，GFS保证至少一次成功的原子append，offset由GFS选定，与Unix的O_APPEND模式相似。

多个客户端并发操作相同文件是比较重的。如果处理传统的write，客户端需要额外复杂和昂贵的同步逻辑，像分布式锁。而record append仅需要primary增加一点额外的逻辑：primary检查是否并发append数据的chunk会超出max size，如果会超出则将chunk填充到max size，并且告诉所有二级副本同样操作，然后回应客户端指出这个操作应该选择另一个chunk重试；大多数情况下记录是在max size内的，primary将数据append到自己的副本，并告诉所有二级副本按照确切的offset写数据，最后回应给客户端。

如果中间出现错误，客户端重试，相同chunk的副本可能包含不同的数据，可能包含相同的记录或者一部分相同，GFS不保证bytewise identical，仅仅保证数据至少有一次被成功地原子写入。从report success逻辑可以容易得出，数据必须是在某个chunk的所有副本上以相同的offset写入。在此之后，所有副本都与记录end一样长，即使后面不同的副本成为primary，任何将来的记录也将分配到更高的offset或者不同的chunk。根据上述的一致性保证，成功的record append的region是defined和一致的，而中间的region是不一致的(undefined)。GFS的应用可以处理这种不一致的region(2.7.2)。

snapshot

snapshot 操作拷贝一份文件或者目录树，几乎是实时的，同时最大程度减少对正在进行中的mutation的干扰。
像AFS一样，使用标准的COW技术实现snapshot。当master接收到一个snapshot请求，首先将所有涉及到chunks的租约撤销，这保证了这些chunks后续的write将会先请求master查找租约持有者，master会创建一个新的副本来回应。

租约被撤销或者过期后，master将这个操作记录日志到disk。新创建的snapshot引用元数据相同的chunks。
当snapshot操作完成后，客户端第一次要写chunk C，发送请求给master查询持有租约者，master察觉到chunk C的引用大于1，则让每个含有当前chunk副本的chunkserver创建一个新的chunk叫作C'，所有创建都使用本地的副本，相比100Mb的网络本地速度大约是三倍速度。master授权租约给新的chunk C'中的一个并且回复给客户端，之后正常地写chunk。整个过程对客户端是透明的。

MASTER OPERATION

master执行所有的namespace操作。另外，它管理整个系统的chunk副本：

• 放置决策
• 创建新chunk和副本
• 协调系统范围内的各种活动以保持chunk的副本数量
• 平衡chunkservers的负载
• 回收空间

接下来，详细探讨这些细节。

Namespace Management and Locking

许多master操作可能花费较长一段时间，比如snapshot操作需要撤销相关的所有chunks的租约。因此为了不delay其它master操作，在namesapce的regions上使用locks来确保串行化。
GFS没有按目录列出该目录中所有文件的结构，也不支持文件和目录的别名(unix中的硬链和软链)。GFS将完整的路径名到元数据的映射表作为它的逻辑namespace。使用前缀压缩，这个表可以有效保存在内存中。namespace tree中的每个节点都有一个关联的读写锁。
每个master操作在运行前都会获取一组锁。如果涉及到/d1/d2/../dn/leaf，它将获取目录名称/d1、/d1/d2、...、/d1/d2/.../dn上的读锁，完整路径/d1/d2/../dn/leaf的读锁或者写锁。leaf可以是文件或者目录。

创建文件不需要对父级目录加锁，因为没有"目录"的概念不会修改它，而加读锁是防止它被删除、重命名或者snapshot。这种锁机制的好处是允许相同目录下并发的mutations。

副本放置

一个GFS集群通常具有分布在多个机架上的数百个chunkserver，这些chunkserver也会被相同或者不同机架的数百个客户端访问。不同机架上的两台计算机之间的通信可能会跨越一个或者多个网络交换机。另外进出机架的带宽可能小于机架内所有计算机的总带宽。多级分布式对如何分发数据以实现可伸缩性、可靠性和可用性提出了独特的挑战。
副本放置策略有两个目的：最大化数据可靠性和可用性，最大化网络带宽利用率。不仅要在多台机器上放置，还要在多个racks上，即使整个racks损坏也可以确保部分副本保持可用。也可以利用多个racks的总带宽。

Creation，Re-replication，Rebalancing

chunk副本创建有三个原因：

• creation
• re-replication
• rebalancing

当master创建新的chunk时，根据几个因素考虑如何放置新的副本：

1. 选择空间利用率低的chunkserver。
2. 限制一台chunksever最近新创建的chunks数量。虽然创建的代价小，但是创建意味着写请求，避免写负载过重。
3. 如上所述，希望在多个racks中分布。

当chunk可用副本的数量低于用户指定时，master会重新复制。可能发生在几种情况：

1. chunkserver不可用。
2. 副本损坏。
3. disk error。
4. 要求的副本数量增加。

需要重新复制的chunk根据以下几个因素确定优先级：

1. 剩余副本的数量。
2. 文件的热度。
3. 提高block客户端进度的chunk的优先级。

master限制集群和每一个chunkserver内的活跃的clone数量，另外chunkserver通过限制其对源chunkserver的读请求来限制在每个clone操作上花费的带宽。

master会定期重新平衡副本：检查当前副本的分布，迁移副本以获得更好的磁盘空间利用率和负载平衡。同样通过此过程，master逐渐填充一个新的chunkserver。另外，master通常更倾向于移除具有低磁盘利用率chunkservers上的副本，以平衡空间使用。

GC

当文件被删除时，master记录日志，但不会立即回收资源，而是将文件重命名为包含删除时间戳标记的隐藏名称。如果这些文件存在时间超过三天(时间可配置)，master巡检时会将其删除。在此之前，仍然可以用特殊名称来读取文件，并且可以重命名为正常名称来取消删除。当从namesapce中删除隐藏文件时，其内存元数据将被删除，这有效切断了所有chunk的连接，在对chunk namespace的扫描中，master识别出孤立的chunk并清除元数据。在心跳信息中，每个chunkserver报告其拥有的chunks子集，而master将回应不在存在于master元数据中的所有的chunk的标识。chunkserver可以自由删除此类chunk的副本。

这种gc机制相比立即删除有以下几个优点：

1. simple and reliable。
2. 将gc任务合并到master常规的后台活动中，减少额外的开销，仅在master相对空闲时执行。
3. 提供可逆的删除。

这种机制主要的缺点是当存储空间紧张时，延迟有时会影响用户的使用，重复创建和删除临时文件的应用可能无法立即重用存储。如果删除的文件再次被明确删除，GFS将通过加快存储回收来解决这些问题。还允许用户将不同的复制和回收策略应用于不同的namespace的不同部分中。

过期副本删除

如果一个chunkserver故障或者chunk丢失了mutations，这个chunk副本可能是过期的。对于每个chunk，master都维护了一个chunk版本号。

当master授权租约给一个chunk时，这个chunk的版本号增加1，如果一个副本当前不可用了，则其版本号将不会领先。当chunkserver重新启动并报告其chunks集合和相关联的版本号时，master将检测到该chunkserver上具有过期的副本。如果master看到的版本号大于它记录的版本号，则认为在授权租约时失败了，因此将较高的版本号更新。

master在常规gc中删除旧的副本。另一个保护措施，在master回应客户端哪个chunk持有租约或者clone操作中chunkserver从另一个chunkserver读取chunk时会包含chunk的最新版本号。客户端或者chunkserver在执行操作时会验证版本号。

容错和诊断

这个系统最大的挑战之一是处理经常故障的组件。组件的质量和数量造成的问题会超出预期，组件故障可能造成系统不可能，甚至数据错误。接下来讨论GFS如何应对这些挑战，还有系统如何诊断不可避免问题。

高可用

使用两个简单有效的方式保证系统的高可用：快速恢复和复制。
master和chunkserver的恢复都是秒级别的。
master维护每个chunk的副本数量，当chunkserver下线或者checksum检测出错误副本时，master会通过已有副本来复制。尽管复制提供了很好的解决方式，但仍在探索其它形式的跨服务器冗余方案，例如奇偶校验或者纠删码，以适应不断增长的只读存储需求。在非常松耦合的系统中实现这些更复杂的冗余方案更具有挑战性。

master的操作日志和checkpoint会被复制到多台机器上，状态的变化只有在本地和所有副本上都持久化以后才可以commit。master进程负责所有的mutations以及后台任务，当它宕机时可以很快重启，如果机器或者磁盘故障，GFS的外部监控将使用日志在其它节点重启新的master进程。在master宕机时，master的备节点只提供只读服务，它们不与master保持强一致，可能会落后于master，通常在1/4秒内。它们保证了那些不介意读到过期数据的应用的高可用读。类似于chunk的primary机制，master的备按照相同的序列应用日志。与master一样，在启动时从每个chunkserver拉取chunks的位置信息，与它们频繁交换握手消息来监控其状态。

数据完善

每个chunkserver使用checksum来检测存储数据的损坏。数据损坏的chunk可以通过其它的副本来恢复，但是通过副本间比较来检验数据是不切实际的。正常的副本也不是完全一样的，如前文所讲，原子的append并不能保证完全一样的副本。因此每个chunkserver会维护自己的checksum。
每个chunk分为多个64kb的blocks，每个block包含一个32位的checksum，与其它元数据一样，checksum保存在内存中，依靠log持久化，与用户数据分离。

对于读，chunkserver在返回数据给请求者前先检测checksum，确保不会将出错的数据传输给其它chunkservers或者客户端。如果数据是坏的，chunkserver将错误返回给请求者并报告给master，请求者将会去读其它副本， master将会根据其它副本重新克隆一份。当新的副本创建以后，master指示chunkserver将错误的副本删除。checksum的计算不涉及I/O，对读的影响比较小，客户端通常尝试使用对齐block边界读来减少overhead。

为append写是做了checksum计算上的优化的，因为append写是主要的负载(相比于overwrite)。GFS只增量地更新最后部分block的checksum，为新的block的计算新的checksum。这样即使block已经损坏，新的checksum将与存储的数据不会匹配，下次读时将会与正常一样被检测出来。
如果一个写请求要写一个chunk中已存在的region，必要要先检验region的第一个和最后一个block的checksum，然后再重写，最后计算新的checksums。因为第一个和最后一个block可能含有不被重写的内容，如果这部分数据是损坏的，则新的checksum将包含错误的数据。

在idle时，checkserver可以扫描并检查不活跃的chunks，可以检测到冷chunks的错误，一旦错误被检测到，master可以创建一个新的副本。

总结

GFS在设计上与传统文件系统有很多不同，这些点是基于对当时应用负载和技术环境的观察所重新设计，将组件故障看作平常的事件而非异常，为大文件的读取和追加写做优化，扩展和放宽了标准的文件系统接口以改善整个系统。通过监控、复制以及快速恢复能力提供容错能力，使用checksum机制来校验数据的正确性。通过将控制流和数据流分离，数据直接在chunkservers、客户端之间传输，为许多并发的各种任务的读取和写入提供了高吞吐量。大chunk size和租约机制使得master的操作足够轻量化，使得这样一个简单中心化的master不会成为瓶颈。

GFS成功地满足了google的存储需求，作为研究、开发和数据处理的存储平台广泛地应用于google内部。