本文将详细介绍由Google在2003年提出的分布式文件系统GFS（Google File System）。GFS是一个分布式的可扩展文件系统，主要用于大规模的数据密集型应用。

GFS设计

GFS是一个用于支持分布式应用程序的文件系统，在分布式文件系统中，我们需要考虑以下问题：首先，组件的失败是不可避免的，比如磁盘损坏，网络不稳定及应用程序Bug等，所以一个分布式的文件系统必须具备持续监控、错误检测、错误容忍和自动恢复的能力；其次，文件系统中的文件通常非常巨大，动辄几百GB，当然也有大量的小文件，所以分布式的文件系统中的IO操作和数据块大小必须精心设计；最后，大多数对分布式文件系统中的写操作通常是追加写，而不会对文件系统中已经存在的数据进行覆盖，所以提高系统的追加写性能和其原子性是非常重要的。GFS就是大致基于这些设计假设来设计的分布式文件系统。

GFS设计假设

文件系统由一些廉价的商用组件组成，它们有一定的失败（损坏）概率，所以他们需要自我检测并在失败时迅速自我恢复。
文件系统中的文件通常为大文件（100MB或更大），小文件也被支持，但不会被优化
文件系统的读工作负载通常由两种读操作组成：大规模的流式读取和小规模的随机读取。小规模随机读取通常由偏移量来控制，同时大量的小规模读取在文件系统中被重排，以减少文件读取过程中回溯。
文件系统的写工作负载通常为追加，很少去修改已经写入的数据，文件一经写入很少会被修改。系统支持随机少量数据的写入但不会对其做优化。
文件系统在并发写文件下要有高效的语义实现，要确保原子性和最小的同步开销。因为该系统经常会被当作生产者消费者队列来使用，或用于多路归并。
高带宽比低延迟更重要。

接口

GFS主要提供以下接口：create、delete、open、close、read、write、snapshot和record append。

系统构建

GFS主要由以下几部分构成：单个master（主节点），多个chunkserver（块服务器）和多个client（客户机）。在GFS中文件被分为合适大小的区块，每个区块有一个chunk handle（区块句柄）唯一标定，这个句柄在区块建立时由master分配。默认每个区块在系统中存在三个备份。master保管所有文件的metadata（元数据），其中包括文件的命名空间、访问权限和文件到区块的映射，master会周期的通过HeartBeat消息同chunkserver通信，发布自己的命令并收集每个chunkserver的状态。client和chunkserver都不提供缓存功能。

GFS系统构件如下图所示：

GFS构建图

单个master

单个master可以简化系统的设计，并且确保master通过全局的知识可以精确的控制区块的部署，但是为了不让单个的master变为系统的瓶颈，client的读写操作不会和master产生任何联系，它只会询问master应该请求那个chunkserver，同时缓存这个信息（减少和master的交流次数），一个简单的读操作流程如下：

使用固定的块大小，client将应用程序指定的文件名和字节偏移量翻译成文件内的块索引。
client向主节点发送包含文件名和块索引的请求。
主节点回复对应的块句柄和每个备份所在的位置。同时客户端使用文件名和块索引作为键缓存该信息。
client访问最近的备份所在的chunkserver，通过块句柄和块的字节范围

再次请求相同的文件内容时，client只需要从缓存中读出信息即可，无需再次请求master，除非缓存消失或者chunkserver损坏。

区块大小

GFS采用64MB作为块大小，远大于传统文件系统。每个块副本以Linux文件形式存储，使用延迟空间分配策略来避免空间浪费。这种大块设计具有三个主要优势：减少了客户端与主服务器的交互需求，因为同一数据块操作只需请求一次位置信息；客户端可与数据服务器保持持久TCP连接，降低网络开销；减少主服务器的元数据存储量，使其能完全保存在内存中。不过，大块设计也面临挑战：小文件通常只有一个数据块，多客户端同时访问时可能造成服务器热点问题。为此，系统采取了增加热点文件副本数量、错开应用启动时间等解决方案，并考虑实现客户端间直接数据传输。

metadata（元数据）

GFS（Google文件系统）中的元数据由主服务器存储，主要包括文件和块的命名空间、文件与块的映射关系以及每个块副本的位置。所有元数据保存在主服务器的内存中，命名空间和文件到块的映射通过操作日志进行持久化，以确保在主服务器崩溃时不会出现不一致。主服务器在启动时向每个chunkserver请求块位置的信息，而不持久保存这些信息。

由于元数据存储在内存中，主服务器的操作速度非常快，并且可以定期扫描状态以实现块垃圾回收、重新复制和负载均衡等功能。虽然内存限制了系统的块数量，但实际使用中，这并不是一个严重的问题，因为每个64MB的块仅需64字节的元数据，大多数文件包含多个完整的块，只有最后一个块是不完整的。

操作日志是GFS的核心，记录了关键的元数据变化，并定义了并发操作的顺序。为了保证日志的可靠性，GFS在多个远程机器上复制操作日志，并在将更改对客户端可见之前，确保日志记录已持久化。主服务器通过重放操作日志来恢复文件系统状态，并在日志增大时创建检查点以加快恢复过程。检查点以紧凑的B树形式存储，可以直接映射到内存中，从而提高查找速度和可用性。检查点创建过程不会影响系统性能，确保了系统的高效性和可靠性。

一致性模型

GFS（Google文件系统）采用了一种宽松的一致性模型，既支持高度分布式的应用，又保持了实现的简单高效。

GFS的一致性保证

文件命名空间的变更操作是原子的，由主服务器独家处理。文件区域在数据变更后的状态取决于变更类型、是否成功以及是否有并发变更。成功且无并发写入的变更会使区域变为已定义状态；并发的成功变更会导致区域处于未定义但一致的状态；失败的变更则使区域变得不一致。
数据变更包括写入和记录追加两种操作。GFS保证在一系列成功的变更后，变更的文件区域将处于已定义状态，并包含最后一次变更写入的数据。这是通过在所有副本上按相同顺序应用变更，并使用块版本号检测过时副本来实现的。
GFS通过定期与数据服务器进行握手来识别故障，并通过校验和检测数据损坏。一旦发现问题，系统会尽快从有效副本恢复数据。只有在GFS反应之前所有副本都丢失的极端情况下，数据才会不可逆转地丢失，但即便如此，应用程序也会收到明确的错误提示，而不是损坏的数据。

应用程序的隐含语义

GFS的应用程序通过几种简单技术来适应其宽松的一致性模型：依赖追加而非覆写、使用检查点机制以及写入自验证和自识别的记录。在典型应用场景中，写入程序从头到尾生成文件，完成后通过原子重命名操作确定文件名，或定期设置检查点标记写入进度。读取程序只处理到最后一个检查点的文件内容，确保数据处于已定义状态。这种追加方式比随机写入更高效，也更能抵御应用程序故障。对于多写入者并发追加的场景，系统通过”至少追加一次”的语义来保护每个写入者的输出。写入的记录包含校验和等额外信息以验证有效性，读取程序可以通过校验和识别并丢弃多余的填充和记录片段，必要时还可以使用记录中的唯一标识符过滤重复内容。

GFS系统构件间的交互

这个章节将具体介绍GFS中master、client和chunkserver如何交互以实现我们前面提到的数据修改，原子的记录追加和快照。

数据修改

在GFS中，数据修改（mutation）是指改变块内容或元数据的操作，如写入或追加。为了在副本之间保持一致的变更顺序，GFS使用租约（lease）机制。主服务器将块租约授予一个副本，称为主副本（primary），该副本为所有变更指定一个串行顺序，所有副本按照这个顺序应用变更。租约的初始超时时间为60秒，但只要块正在被变更，主副本可以请求并通常会获得无限期的延长。

数据修改流程图如下：
GFS数据修改流程

以下是写入过程的控制流程：

客户端向master询问当前持有块租约的chunkserver及其他副本的位置。如果没有租约，主服务器将其授予一个副本。
主服务器回复主副本的身份和其他（次级）副本的位置。客户端缓存这些数据，以便未来的变更，只需在主副本不可达或不再持有租约时再次联系master。
客户端将数据推送到所有副本，可以按任意顺序进行。每个chunkserver器会在内部LRU缓冲区缓存数据，直到数据被使用或过期。
一旦所有副本确认接收到数据，客户端向主副本发送写请求，请求中标识了之前推送的数据。主副本为接收到的所有变更分配连续的序列号，以提供必要的序列化，并按序列号顺序将变更应用于其本地存储的数据。
主副本将写请求转发给所有次级副本。每个次级副本按照主副本分配的序列号顺序应用变更。
所有次级副本回复主副本，表示已完成操作。
主副本向客户端回复。如果任何副本遇到错误，将报告给客户端。如果在主副本成功但某些次级副本失败，则请求被视为失败，修改区域处于不一致状态。客户端代码会通过重试失败的变更（3～7步）来处理这些错误。

如果应用程序的写入较大或跨越块边界，GFS客户端代码会将其拆分为多个写操作，这些操作遵循上述控制流程，但可能与其他客户端的并发操作交错。因此，共享文件区域可能包含来自不同客户端的片段，但由于各个操作在所有副本上成功完成且顺序相同，最终结果仍然保持一致但未定义状态。

数据流传输

GFS将数据流与控制流分离，以实现网络的高效利用。控制流从客户端流向主副本，再到所有次级副本；而数据则通过精心选择的chunkserver链进行流水线式传输。系统采用线性链式传输而非树形等其他拓扑结构，确保每台机器的网络带宽得到充分利用。每台机器将数据转发给网络拓扑中最”近”的、尚未接收数据的机器，从而避免网络瓶颈和高延迟链路。系统通过IP地址可以准确估算机器间的”距离”（这得益于Google的网络拓扑结构）。为了最小化延迟，数据通过TCP连接进行流水线传输。块服务器一旦接收到数据就立即开始转发，这种方式在全双工链路的交换网络中特别有效。

原子的记录追加

GFS提供了一种称为记录追加（record append）的原子追加操作。在传统写入中，客户端需要指定数据写入的偏移量，导致并发写入可能产生数据片段混合的问题。而在记录追加中，客户端只需指定要追加的数据，GFS会将其原子性地追加到文件中，偏移量由GFS自行选择，并将该偏移量返回给客户端。这种方式类似于Unix中以O_APPEND模式打开文件的写入，避免了多写入者并发时的竞争条件。

快照

GFS的快照（snapshot）操作能够几乎瞬间复制文件或目录树，同时最小化对正在进行的变更的干扰。用户可以利用快照快速创建大型数据集的分支副本，或在进行实验性更改前保存当前状态。快照实现采用写时复制技术。当master收到快照请求时，首先撤销待快照文件中所有块的未过期租约，确保后续写入需要与master交互（必须重新请求master租约的持有者）。master将操作记录到磁盘后，通过复制源文件或目录树的元数据来更新内存状态。新创建的快照文件指向与源文件相同的数据块。当快照操作后客户端首次要写入某个块时，master会注意到该块的引用计数大于1。此时，master会选择一个新的块标识符，并要求拥有当前副本的块服务器创建新块。通过在相同的块服务器上创建新块，确保数据可以在本地复制，避免网络传输，提高效率。之后的请求处理与普通块处理相同。

Master

master在GFS中负责执行所有命名空间操作，同时管理整个系统中的块副本。其核心职责包括决定块的放置位置、创建新的块和副本、协调系统范围的活动，以确保块的完整复制、在块服务器之间实现负载均衡，以及回收未使用的存储空间。

基于读写锁的命名空间管理

GFS主服务器的操作可能耗时较长，为了避免延迟其他操作，系统采用锁机制来确保命名空间区域的正确序列化。与传统文件系统不同，GFS不维护目录数据结构，也不支持文件别名，而是将命名空间表示为一个将完整路径名映射到元数据的查找表。GFS的锁机制基于命名空间树中的节点，每个节点都有一个读写锁。操作执行时，会获取相关路径上的一系列锁。例如，对于路径/d1/d2/…/dn/leaf的操作，会获取各级目录的读锁（/d1, /d1/d2, … , /d1/d2…/dn的读锁），以及最终路径（/d1/d2/…/dn/leaf）的读锁或写锁。这种设计允许同一目录下的并发修改操作，比如多个文件可以同时在同一目录下创建。为了防止死锁，锁的获取遵循一致的顺序规则：首先按命名空间树的层级排序，同一层级内按字典序排序。考虑到命名空间可能包含大量节点，读写锁对象采用懒加载方式分配，不使用时即被删除。

副本部署

GFS集群在多个层面上实现高度分布式：数百个chunkserver分布在多个子网上，同时被来自相同或不同子网的数百个客户端访问。不同子网间的机器通信可能需要经过多个网络交换机，且子网的带宽可能小于其内部所有机器的总带宽。块副本的部署策略主要取决于两个目标：最大化数据的可靠性和可用性，以及最大化网络带宽利用率。系统不仅要将副本分布在不同机器上以防止磁盘或机器故障，更要将块副本分布在不同子网上。这样即使某个子网出现故障（如网络交换机或电路故障），部分副本仍能存活并保持可用。这种策略也使得数据访问可以利用多个子网的总带宽，尽管写入流量需要经过多个子网，但为了数据的可用性这是必须作出的权衡。

区块（副本）的创建、重部署和再平衡

区块创建

Master在创建新块时会综合考虑多个因素来决定副本的放置位置。首先，系统会选择磁盘利用率低于平均水平的chunkserver，这样可以随时间推移实现各服务器间的磁盘使用均衡。其次，会限制每个服务器上最近创建的块数量，因为新创建的块往往预示着即将到来的大量写入操作。最后，系统会确保将副本分布在不同子网上，以提高数据可靠性和可用性。

区块重部署

当某个块的可用副本数量低于用户指定的目标值时，系统会触发重新复制机制。这种情况可能由多种原因导致，比如chunkserver不可用、副本损坏或磁盘故障等。系统会根据以下因素为需要复制的块分配优先级：

与目标副本数的差距（失去两个副本比失去一个副本的优先级更高）
文件的活跃状态（活跃文件优先于已删除文件）
是否影响客户端操作（阻塞客户端进度的块会获得更高优先级）

区块再平衡

Master会定期检查系统中副本的分布情况，并通过移动副本来优化磁盘空间使用和负载均衡。在处理新加入的chunkserver时，系统采用渐进式填充策略，避免突然分配大量数据而导致过重的写入负载。为了防止复制操作影响正常客户端访问，系统会对整个集群和单个chunkserver的同时复制操作数量进行限制，并通过限制带宽来控制复制速度。

这种多层次的副本管理机制确保了GFS能够在保持高可用性的同时，实现良好的负载均衡和资源利用率

GFS的垃圾回收机制

回收机制

当用户（client）删除一个文件时，GFS中的垃圾回收机制会被触发。当文件被删除后，系统不会立即回收其占用的物理存储空间，而是采用延迟处理的方式，这种懒惰回收的策略使得系统设计更加简单，同时也提高了系统的可靠性。这种方法虽然不会立即释放存储空间，但通过简化系统操作，降低了系统的复杂度，从而提高了整体的稳定性。

当应用程序删除文件时，master不会立即回收资源，而是将文件重命名为包含删除时间戳的隐藏文件。这些文件在三天内（可配置）仍然可以被读取和恢复。超过期限后，master会在例行扫描时删除这些隐藏文件的元数据，切断它们与数据块的联系（删除它的metadata）。

在master定期扫描数据块命名空间时，会识别出孤立的数据块（即无法从任何文件访问的块），并删除这些块的元数据。各个chunkserver在与master进行HeartBeat通信时，会报告它们持有的数据块信息，master则会告知哪些数据块在元数据中已不存在，chunkserver随后可以删除这些块的副本。

优缺点

这种垃圾回收方式比直接删除有几个优势：首先，它在大规模分布式系统中更可靠；其次，它将存储回收与master的常规后台活动合并，成本分摊且不影响主要业务；最后，延迟删除可以防止意外删除（Rename文件就可以恢复它）。主要缺点是在存储空间紧张时可能会影响用户对存储空间的精细控制，对此系统提供了一些解决方案，比如允许用户为不同的命名空间设置不同的复制和回收策略。

旧副本（无效副本）检测

Master为每个数据块维护一个版本号，用于区分最新和过期的副本。当master授予数据块新的租约时，会增加版本号并通知所有最新的副本。master和这些chunkserver都会在持久存储中记录新的版本号，这个过程发生在通知客户端之前。

如果某个chunkserver在宕机期间错过了数据块的修改，其副本就会变得过期。当这个服务器重启并报告其数据块信息时，master会通过比对版本号发现过期的副本。如果master发现某个版本号比自己记录的更高，它会认为这是由于自己在授予租约时发生了故障，并采用较高的版本号作为最新版本。

master会在常规垃圾回收中移除过期副本。在此之前，当回应客户端请求数据块信息时，它会完全忽略过期副本的存在。作为额外的安全措施，master在告知客户端哪个chunkserver持有租约，或指示chunkserver从其他服务器克隆数据时，都会包含版本号信息。客户端或chunkserver在执行操作时会验证版本号，确保始终访问最新的数据。

错误容忍与诊断

在分布式系统中，处理频繁的组件故障是最大的挑战之一。由于系统规模庞大且使用大量普通硬件设备，组件故障已经成为一种常态而非异常情况。系统既不能完全信任机器，也不能完全信任磁盘的可靠性。这些组件故障可能导致系统不可用，更严重的是可能造成数据损坏。因此，GFS必须建立相应的故障诊断工具和机制来应对这些不可避免的问题。

高可用性

高可用性主要由两个简单且高效的机制保证：快速恢复和复制（冗余）。

快速恢复

master和chunkserver都被设计为能在几秒钟内恢复状态并重新启动，无论是何种原因导致的终止。系统对正常终止和异常终止的处理方式是一样的，服务器甚至可以通过直接终止进程的方式来进行例行关闭。当服务器重启时，客户端和其他服务器只会经历短暂的中断：它们会在当前请求超时后，重新连接到重启的服务器并重试之前的操作。

块复制

每个数据块都会在不同机架的多个chunkserver上进行复制。用户可以为文件系统命名空间的不同部分指定不同的复制级别，默认是三个副本。当chunkserver离线或通过校验和验证检测到损坏的副本时，master会克隆现有副本以保持每个数据块的完整复制。

虽然复制机制运行良好，但系统也在探索其他形式的跨服务器冗余方案，如奇偶校验或纠删码，以满足不断增长的只读存储需求。由于系统的流量主要是追加写入和读取操作，而不是小型随机写入，因此在这种松耦合系统中实现这些更复杂的冗余方案虽然具有挑战性，但仍是可控的。

Master复制

为了保证可靠性，master的状态会在多台机器上进行复制，包括操作日志和检查点。只有当日志记录在本地磁盘和所有master副本上都完成刷新后，对状态的修改才被视为已提交。为了简单起见，一个master进程负责所有的修改操作和后台活动。如果master发生故障，它可以几乎立即重启；如果其机器或磁盘出现故障，GFS外部的监控基础设施会在其他地方启动新的master进程。

系统还设置了”影子”master，提供文件系统的只读访问服务。这些影子master与主master可能会有轻微的时间差，通常是几分之一秒。它们主要用于提高那些不经常修改的文件或对略微过期的结果可以容忍的应用程序的读取可用性。由于文件内容是从chunkserver读取的，应用程序不会看到过期的文件内容，可能过期的只是文件元数据，如目录内容或访问控制信息。影子master通过读取操作日志副本并按照与主master相同的顺序应用更改来保持信息更新。它们在启动时会轮询chunkserver以定位数据块副本，并通过定期的握手消息监控其状态。影子master只在副本位置更新方面依赖主master，这些更新是由主master创建和删除副本的决策产生的。

数据完整性

GFS主要通过校验和来保障块及其副本的数据完整性。

每个chunkserver使用校验和技术来检测存储数据的损坏。由于GFS集群通常拥有数千个磁盘和数百台机器，定期会发生磁盘故障，导致读取和写入路径上的数据损坏或丢失。虽然可以通过其他副本恢复数据，但通过比较不同chunkserver之间的副本来检测损坏是不切实际的。此外，因GFS的修改语义（尤其是原子记录追加）可能导致不同的副本是合法的，因此每个chunkserver必须独立验证其副本的完整性，方法是维护校验和。

每个chunk被分为64 KB的块，每个块都有一个对应的32位校验和。校验和与其他元数据一样，保存在内存中并与日志一起持久存储。对于读取操作，chunkserver在返回数据之前会验证重叠读取范围内的数据块的校验和，从而避免将损坏的数据传播到其他机器。如果块与记录的校验和不匹配，chunkserver会向请求者返回错误并将不匹配情况报告给master。请求者会从其他副本读取，而master则会从另一个副本克隆该chunk。在有效的新副本就位后，master会指示报告不匹配的chunkserver删除其副本。

校验和对读取性能影响较小，因为大多数读取操作跨越多个块，只需读取相对较少的额外数据进行验证。此外，chunkserver上的校验和查找和比较不涉及任何I/O操作，且校验和计算通常可以与I/O操作重叠。对于追加写入操作，校验和计算经过优化，只需增量更新最后一个部分块的校验和，并为新填充的任何完整块计算新的校验和。如果最后一个部分块已损坏且未被及时检测到，新的校验和值在下次读取时仍会发现不匹配。

相反，对于覆盖写入操作，需要在写入之前读取并验证被覆盖范围的首尾块，然后执行写入并计算记录新的校验和。在未验证首尾块之前进行部分覆盖写入可能会隐藏未被覆盖区域的损坏。在空闲期间，chunkserver可以扫描并验证不活跃chunks的内容，以检测不常读取chunks中的损坏。一旦发现损坏，master可以创建新的未损坏副本并删除损坏副本，从而防止不活跃但已损坏的副本误导master认为有足够有效的副本存在。

诊断工具

GFS系统通过详细的诊断日志记录显著提升了问题隔离、调试和性能分析的能力，同时只带来了极小的成本。没有日志，很难理解机器之间瞬时且不可重复的交互。GFS服务器生成的诊断日志记录了许多重要事件（如chunkserver的上下线）以及所有RPC请求和响应。这些诊断日志可以在不影响系统正确性的情况下自由删除，但应当尽量在空间允许的情况下保留这些日志。

RPC日志包括在网络上发送的确切请求和响应，除了正在读取或写入的文件数据。通过将请求与响应匹配并整理不同机器上的RPC记录，我们可以重建整个交互历史以诊断问题。这些日志也可作为负载测试和性能分析的追踪记录。由于这些日志是顺序和异步写入的，因此其对性能的影响很小，且远远被其带来的好处所抵消。最新事件也会保存在内存中，以便进行持续的在线监控。

总结

GFS展示了在商品硬件上支持大规模数据处理工作负载所需的关键特性。尽管某些设计决策是针对Google独特环境的，但许多原则也适用于类似规模和成本意识的数据处理任务。GFS通过重新审视传统文件系统的假设，以适应当前和预期的应用工作负载及技术环境，做出了根本性的设计改变。

GFS将组件故障视为常态，优化了主要以追加方式写入的大文件，并在读取时通常采用顺序方式。系统通过持续监控、复制关键数据以及快速自动恢复来提供容错能力，数据块复制使其能够容忍chunkserver的故障。此外，GFS开发了一种在线修复机制，能够定期且透明地修复损坏并尽快补偿丢失的副本。校验和技术则用于检测磁盘或IDE子系统级别的数据损坏，这在系统中存在大量磁盘的情况下变得尤为重要。

通过将文件系统控制与数据传输分离，GFS为多个并发读写者提供了高总吞吐量。较大的块大小和chunk租约的设计减少了master在常见操作中的参与，使得简单的集中式master不会成为瓶颈。