GFS论文阅读笔记

---

---

摘要

GFS（Google File System）是由我们设计并实现的为大规模分布式数据密集型应用程序设计的可伸缩（scalable）的分布式文件系统。GFS为在廉价商用设备上运行提供了容错能力，并可以在有大量客户端的情况下提供较高的整体性能。

一、引言

GFS与过去的分布式系统有着很多相同的目标，如performance、scalability、reliability、availability。而设计来自于对应用负载与技术环境观察下获得的结果：

• 我们认为设备故障发生。因为GFS会由于很多廉价设备组成的存储节点组成，每个节点都会被一定数量的客户端访问。每个节点都可能会在任何时间crash，因此系统必须要有持续监控、错误检测、容错、与自动恢复的能力。
• 文件比传统标准更大。 需要重新考虑像I/O操作和chunk大小等设计和参数。
• 大部分文件会以“追加”（append）的方式变更（mutate），而非“覆写”（overwrite）；
  因为实际上overwrite的情况基本不存在大部分都是append，且在程序分析的大型data set或者stream application生成的数据等情形下，通常读取都是顺序读取。
• 设计应用程序与文件系统共同进行，例如放宽一致性模型，又或者是引入原子附加操作，使多个客户端同时附加到一个文件时不需要进行额外的操作。（笔者的理解是就是，在设计GFS这个系统时，当时已经是有很多痛点了，因此设计应用程序与文件系统同时进行的意思应该就是如何在这些应用程序设计的基础上设计出更合理简单的存储系统）

二、设计总览

2.1、假设

• 系统是由一堆廉价机器构成的，因此会经常发生crash，因此系统需要持续监控、错误检测、容错、与自动恢复的能力。

• GFS预计会存储几百万个文件，每个文件的大小会在100MB甚至更大，同时会存储少量的大型文件，多GB文件时常见的情况，因此应该进行有效的管理。同时也必须支持小文件，但是不需要针对他们进行优化。

• 系统负载主要来自两种读操作：大规模的流式读取和小规模的随机读取。在大规模的流式读取中，每次读取通常会读几百KB、1MB或更多。来自同一个客户端的连续的读操作通常会连续读文件的一个区域。小规模的随机读取通常会在文件的某个任意偏移位置读几KB。性能敏感的应用程序通常会将排序并批量进行小规模的随机读取，这样可以顺序遍历文件而不是来回遍历。

• 系统负载还来自很多对文件的大规模追加写入。一般来说，写入的规模与读取的规模相似。文件一旦被写入就几乎不会被再次修改。系统同样支持小规模随机写入，但并不需要高效执行。

• 系统必须良好地定义并实现多个客户端并发向同一个文件追加数据的语义。我们的文件通常在生产者-消费者队列中或多路归并中使用。来自不同机器的数百个生产者会并发地向同一个文件追加写入数据。因此，最小化原子性需要的同步开销是非常重要的。文件在被生产后可能同时或稍后被消费者读取。

• 持续的高吞吐比低延迟更重要。我们的大多数应用程序更重视告诉处理大量数据，而很少有应用程序对单个读写操作有严格的响应时间的需求。

2.2、接口

GFS提供了常用的接口，尽管不像POSIX那样标准化。文件是按层次结构组织在目录中，并通过路径名进行标识。 常用的接口操作有创建、删除、打开、关闭、读取、写入、快照、原子性的并发追加。

2.3、架构

• 一个GFS集群包括一个master（主服务器）与多个chunkservers（块服务器），并且被多个client（客户端）进行访问。每个节点通常为一个运行着用户级服务进程的Linux主机。如果资源允许且可以接受不稳定的应用程序代码所带来的低可靠性，那么可以轻松地在一台机器上同时运行chunkserver和client。
• 文件将会被划分在固定大小的chunks中，每个chunk被一个不可变的全局唯一的64位chunk handle（块标识符）唯一标识，chunk handle在chunk被创建时由主节点分配。chunkserver将chunk作为Linux文件存储到本地磁盘中，通过chunk handle和byte range（字节范围）来确定需要被读写的chunk和chunk中的数据。为了可靠性，每个chunk都会有默认三个副本存在不同的chunkserver上。
• Master负责维护文件系统中所有的元数据（metadate），元数据中包括了命名空间（namespace）、访问控制（access control）信息、文件到chunks的映射关系、当前chunks的位置信息。master还控制系统级活动如chunk租约（chunk lease）管理、孤儿chunk垃圾回收（garbage collection of orphaned chunks）和chunkserver间的chunk迁移（migration）。master周期性地通过心跳（HeartBeat）消息与每个chunkserver通信，向其下达指令并采集其状态信息。
• 被链接到应用程序中的GFS client的代码实现了文件系统API并与master和chunkserver通信，代表应用程序来读写数据。进行元数据操作时，client与master交互。而所有的数据（这里指存储的数据，不包括元数据，metedata由master操作）交互直接由client与chunkserver间进行。因为GFS不提供POXIS API，因此不会陷入到Linux vnode层。
• client与chunkserver都不需要缓存文件数据。 对于client来说因为大部分应用程序需要流式的处理大型文件或者数据集，以至于无法缓存。也因此不需要处理缓存一致性问题，简化了系统。对于chunkservers来说chunks都是在本地直接储存文件，并且Linux系统已经在内存中对经常访问的数据在缓冲区缓存。

2.4 单Master

• 只有单一的Master可以极大的简化设计，并且可以通过全局信息处理复杂的chunk分配（chunk placement）与副本决策（replication decisions）。同时我们应该尽量避免master对于读写的参与，使其不会成为成为瓶颈。Clients不会读写数据通过master，而是去询问master应该访问哪个chunkservers。之后client会在一定时间内缓存通信信息，后续通过对应的chunkserver完成操作。
• 通过架构图，可以简单理解下读的过程。首先，通过固定的chunk大小，client将应用程序指定的文件名和chunk偏移量命名为该文件中的块序号（chunk index）。然后，client向master发送一个包含了文件名和chunk index的请求。master会返回其相应的chunk handle和副本所在的位置。client将这个信息以文件名和chunk index为键进行缓存。
• client接着向最有可能为最近的副本所在的chunkserver发送请求。请求中指定了chunk handle和byte range。之后，client再次读取相同的chunk时不再需要与master交互，直到缓存过期或文件被重新打开。事实上，client通常会在同一个请求中请求多个chunk，master也可以返回包含多个chunk的响应。这种方式避免了client与master进一步的通信，在几乎不需要额外开销的情况下得到更多的信息。
• client接着向最有可能为最近的副本所在的chunkserver发送请求。请求中指定了chunk handle和byte range。之后，client再次读取相同的chunk时不再需要与master交互，直到缓存过期或文件被重新打开。事实上，client通常会在同一个请求中请求多个chunk，master也可以返回包含多个chunk的响应。这种方式避免了client与master进一步的通信，在几乎不需要额外开销的情况下得到更多的信息。

2.5 Chunk大小

• chunk size被设置为64MB（比典型的文件系统中的块更大）。每个chunk的副本被当做普通的Linux文件存储在chunkserver，并仅在需要时扩展。懒式空间避免了因为内部碎片的空间浪费。
• 选择较大的chunk size有一下几个重要的优点。
  • 减少了client与master之间的交互。因为对一个chunk的读写仅需要与master通信一次以请求其位置信息，这对我们需要流式的读取大型文件是很重要。即使对于小规模的随机读取，client也能轻松的cache下几TB下的数据集的chunk位置信息。（数据集需要的chunk更小了）。
  • 因为chunk变得更大,一个client可以在一个chunk上完成更多的操作，则这可以通过保持TCP的更长连接而减少网络开销.
  • 减少了存储在Master上的元数据的大小。（因为总的chunks数量变少，元数据存储的映射信息也会对应减少。）
• 即使有懒式空间分配，较大的chunk大小也存在着缺点 。管理仅有几个chunk的小文件就是其中之一。如果多个client访问同一个文件，那么存储这这些文件的chunkserver会成为hot spot（热点）。在实际情况下，因为应用程序大部分都顺序地读取包含很多chunk的大文件，所以hot spot不是主要问题。
  然而在GFS首次被批处理队列（batch-queue）系统使用时，确实出现了hot spot问题：一个可执行文件被以单个chunk文件的形式写入了GFS，然后在数百台机器上启动。存储这个可执行程序的几台chunkserver因几百个并发的请求超载。我们通过提高这种可执行文件的副本数（replication factor）并让批处理队列系统错开应用程序启动时间的方式修复了这个问题。一个潜在的长期解决方案是在让client在这种场景下从其他client读取数据。

2.6 元数据

master节点主要存储三种元数据，文件与chunk的命名空间（namespaces），文件到chunk的映射关系，以及到chunk的每个副本位置的映射关系。所有的metadata都保存在master的内存中。 前两种类型（namespaces、file-to-chunk mapping）将会通过变更日志中的操作日志持久化在master的本地磁盘，并在远程机器上备份。master不会持久化存储chunk的位置信息，而是在启动时和当chunkserver加入集群时向chunkserver询问其存储的信息。

2.6.1 内存数据结构
因为元数据储存在内存中。master操作则变得很快。此外master在后台周期性的扫描整个状态信息时会变得简单高效。周期性的扫描用来实现chunk的gc，以及在chunkserver发生故障时的重备份，以及chunk的迁移为了保证负载均衡以及跨chunkservers之间的磁盘空间均衡。
这种仅使用内存的潜在问题是块的数量与整个系统的容量收到master内存的限制。但在实践中这不是最紧要的限制，master为每个64MB的chunk维护少于64 bytes的数据。 大部分的chunks都被占用满了，因为大部分的文件都将包括很多个chunk，只有最后一个chunk才可能会被部分占用。并且因为采用了前缀压缩的方式紧凑地存储文件名，每个文件的命名空间数据通常需要少于64字节。
如果一定要支持更大的文件系统,往master中放入额外的内存开销也是小的，以至于保证元数据储存在内存中的简单性，可靠性，高性能与灵活性。
2.6.2 chunk位置
master不会持久化保存哪台chunkserver含有给定的chunk的副本的记录，而是简单地在启动时从chunkserver获取信息。随后，master就可以保证自己的记录是最新的，因为master控制着所有chunk的分配并通过周期性的心跳消息监控chunkserver状态。
相比chunk的位置信息持久化在master上，在chunkservers刚启动时发送request会简单的多并且通过周期性的心跳维护。这样也笑出了当chunkservers加入或离开集群，改变名字，故障，重启等带来的同步问题，这在上百个服务器的集群里经常发生。
另一种理解这种设计的方法是，chunkserver对其磁盘上有或没有哪些chunk有着最终决定权 。因为chunkserver中的错误会导致chunk消失（例如磁盘可能损坏或被禁用）或一个操作者可能重命名一个chunkserver。因此，试图在master上维护一个持久化的快位置信息视图是没有以意义的。
2.6.3 操作日志

• 操作日志包含关键元数据的历史数据的改变，这是GFS的核心，这不仅是元数据持久化记录唯一的地方，而且还是充当了定义并发操作顺序的逻辑时间线。 带有版本号的文件和chunk都在他们被创建时由逻辑时间唯一、永久地确定。
• 操作日志是GFS至关重要的部分，其必须被可靠存储，且在元数据的变更被持久化前不能让client对变更可见。否则当故障发生时，即使chunk本身没有故障，但是整个文件系统或者client最近的操作会损坏。我们将操作日志备份到多台远程主机上，且只有当当前操作记录条目被本地和远程主机均写入到了磁盘后才能向客户端发出响应。master会在操作记录被写入前批量合并一些操作记录来减少写入和备份操作对整个系统吞吐量的影响。
• master通常是通过重放操作日志来恢复系统状态，为了保证最小化的启动时间，所以系统会定期进行检查点更新，恢复时也是通过最新的检查点进行更新。

。检查点的结构为一个紧凑的B树（B-tree）这样它就可以在内存中被直接映射，且在查找命名空间时不需要进行额外的解析。 这进一步提高了恢复速度，并增强了系统的可用性。

• 因为创建一个检查点需要一段时间，所以master被设计为可以在不推迟新到来的变更的情况下创建检查点。创建检查点时，master会切换到一个新的日志文件并在一个独立的线程中创建检查点。 这个新的检查点包含了在切换前的所有变更。一个有着几百万个文件的集群可以再一分钟左右创建一个检查点。当检查点被创建完成后，它会被写入master本地和远程主机的磁盘中。

2.7 一致性模型

2.7.1 GFS提供的保证
文件命名空间的变更（例如创建文件）操作时原子性的。它们仅由master处理。命名空间锁保证了原子性和正确性（章节4.1）；master的操作日志定义了这些操作的全局总顺序（章节2.6.3）。
在数据变更后，无论变更的成功与否，一个文件区域（file region）的状态都取决于变更类型。 表1总结了变更后文件区域的状态。

• 如果一个文件区域的任意一个副本被任何client读取总能得到相同的数据，那么这个文件区域状态为consistent（一致的）。
• 在一个文件区域的数据变更后，如果它是一致的，且client总能看到其写入的内容那么这个文件区域的状态为defined。
• 文件区域在并发变更执行后的状态为consistent but undefined（一致的但非确定的）：所有客户端能考到同样的数据，但数据可能并不反映任何一个变更写入的数据。
• 通常，数据融合了多个变更的内容。文件区域在一个失败的变更后状态会变为inconsistent（不一致的）（且undefined）：不同client在不同时刻可能看到不同的数据。

在这里笔者认为可以先区分出两种概念：

• consistent: 多个replicas之间的数据相同；
• defined： 每个client最初写入指定offset的数据 和 后来从offset读出的数据相同；

数据变更操作可能为write或record append（record append操作与文件的append有所不同，下文中会有对record append的介绍）。write操作会在应用程序指定的文件与偏移处写入数据。record append会将数据至少一次（at least once）地原子性地写入文件，即使在record append的同时可能存在并发的变更，但是record append写入位置是由GFS选择的偏移量（章节3.3）。（与常规的append不同，append仅会在client认为的文件末尾处写入数据。）record append的偏移量会被返回到client，这个偏移量为record append写入的数据的起始位置。除此之外，GFS可能会在记录的中间插入填充（padding）和或重复的记录。它们占用的区域状态为inconsistent的，通常情况下，它们的数量远少于用户数据。

• 这里可以复现解读并发写入一个chunk的场景：

每一个chunk默认有3个副本，不同的副本存在不同的节点上，master会设置一个primary replica，两个secondary replica。
当写操作和追加操作失败，数据会出现部分被修改的情况，肯定会出现副本不一致的情况，这时就依赖master的重备份机制，将正确的副本重新备份到设定阈值的数量为止。
此时有两个client要并发写入同一个chunk，分别写入a,b。
那么这时，primary replica会根据某种方式，将并行操作，进行串行序列化。 要么是a -> b ,要么是b -> a。然后primary replica会将这种序列化好的方式传给下一个secondary replica。这样即保证了之前所说的全局一致性。所以对于每个chunk，都能保证数据是相同的也就是consistent的。但是对于两个client来说谁也不能保证刚刚的数据是自己写出来的，所以这就是undefined。

• 上一种写入大多为写入（覆盖），接下来解读下追加的场景：
  
  追加写入b时失败了，此时client2重新发起追加。
  
  此时可以看到offset2、3各个副本是确定的（defined），但是offset1是各个副本间却不一致，所以这个时候则是table表中的unconsistent but defined。

在一系列变更执行成功后，被变更的文件区域状态为defined的，且该区域中包含最后一次变更写入的数据。这一点是GFS通过以下方式实现的：
（a）对chunk执行变更时，其所有副本按照相同的顺序应用变更（章节3.1）
（b）使用chunk版本号（chunk version）来检测因chunkserver宕机而错过了变更的陈旧的chunk副本（章节4.5）。陈旧的chunk副本永远不会在执行变更时被使用，也不会在master返回client请求的chunk的位置时被使用。它们会尽早地被作为垃圾回收。

由于client会缓存chunk的位置，在缓存信息刷新前，client可能会访问陈旧的副本。**这个时间窗口会受缓存过期时间和下一次打开文件限制（下一次打开文件会清除文件的所有chunk位置信息）。 ** 除此之外，由于我们大多数文件是仅追加的，陈旧的副本的通常会返回一个版本较早的结束位置处的数据，而不是陈旧的数据（译注：这里陈旧的数据指错过了write变更的数据）。当reader重试并与master通信时，它将立刻获取目前的chunk位置。

即使在变更被成功应用的很长时间后，设备故障仍然可以损坏（corrupt）会销毁（destroy）数据。GFS通过master和所有chunkserver周期性握手的方式来确定故障的chunkserver，并通过校验和（checksunmming）的方式检测数据损坏（章节5.2）。 一旦出现问题，数据会尽快地从一个合法的副本恢复章节4.3）。一个chunk只有在GFS作出反应前（通常在几分钟内）失去了所有的副本，chunk才会不可逆地丢失。即使在这种情况下，chunk也仅变得不可用而非损坏，因为应用程序可以收到明确的错误而非损坏的数据。（译注：本节中的“损坏corrupt”指读到错误的数据，“销毁（destory）”指数据丢失。）
2.7.2 对应用程序的影响
GFS应用程序可以通过一些简单的技术来使用其宽松的一致性模型，且这些技术已经因其他目标而被使用，如：依赖append而不是overwrite、检查点、自验证写入（writing self-validating）、自标识记录（self-identifying records）。

在实际使用中，我们所有的应用程序都通过append而不是overwrite的方式对文件进行变更。其中一个典型的引用场景是：一个write从头到尾地生成一个文件。它会周期性地为已经写入的文件数据创建检查点，并在所有数据都被写入文件后自动将其重命名为一个永久的文件名。检查点可能包含应用程序级别的校验和。reader会验证文件仅处理跟上最新的检查点的文件区域，这些区域的状态一定的“defined”的。 尽管这种方法有一致性和并发问题，它仍很好地满足了我们的需求。append的效率远高于随机写入，且在应用程序故障时更容易恢复。检查点机制允许writer在重启时增量写入，并能够防止reader处理那些虽然已经被成功写入文件但是从应用程序的角度看仍然不完整的文件数据。

另一种典型的用途是，许多write并发地向同一个文件append数据以获得合并后的结果或文件作为生产者-消费者队列使用。record append的“至少一次追加（append-at-least-once）”语义保证了每个write的输出。而reader偶尔需要处理填充和重复的数据，如下文所述。每条被writer准备好的记录包含如校验和的额外信息，这样，记录的合法性就可被校验。一个reader通过校验和来识别并丢弃额外的填充和记录。如果rearder无法容忍偶尔发生的重复（如果重复的记录可能触发非幂等（non-idempotent）运算），它可以使用记录中的唯一标识符来对齐进行过滤。 通常，在命名应用程序相关的实体时（如web文档），总会使用唯一的标识符。数据记录的I/O的充能都在库代码中（除了去重），可以被我们的应用程序使用，且其还适应于Google实现的其他文件接口。通过这些库，带有极少的重复的记录，总会被以相同顺序交付给reader。

3 系统交互

在设计系统时，我们让master尽可能少地参与所有操作。在此背景下，我们将描述client、master和chunkserver如何交互来实现数据变更、原子地record append和快照操作。

3.1 租约和变更顺序

改变chunk或元数据的操作被称为“变更”，如write或append。chunk变更时，其每个副本都会应用变更。我们使用租约（lease）来维护副本间变更顺序的一致性。 master向其中一份副本授权一个变更的租约，我们称这个副本为primary（有时也可代指primary副本所在的chunkserver）。primary为应用于该chunk的所有变更选取顺序。所有副本都会按照这个顺序来应用变更。 因此，全局的变更顺序首先由master选取的租约授权顺序定义，接着在租约内由primary选取的顺序编号定义。（例如之前所画的图）

这种租约机制是为了最小化master管理负载而设计的。租约的初始超时时间为60秒。然而，一旦chunk被变更，primary就可以向master请求延长租约时间，或者（通常为）接受来自master的租约时间延长操作。这些租约延长请求和租约授权请求依赖master与chunkserver间周期性地心跳消息来实现。有时master可能会在租约过期前视图撤销租约（例如，当master想禁止对正在被重命名的文件进行变更时）。即使master与一个primary的通信丢失，master仍可以在旧租约过期后安全地向另一个副本授权新的租约。

1. client 将会询问master哪个chunkserver含有租约，以及其他replicas的位置。如果没有chunserver持有，则会选择一个chunkserver进行授权。
2. master将回复client关于primary/secondary的位置，并且client会缓存这些信息，当primary不可访问或primary不持有租约的时候再与master通信。
3. 此时client将会推送数据到所有的副本，每个chunkserver都会把数据先放到LRU里缓存（不应用），知道数据被真正使用或者失效(过期）。通过这种方式将数据流与控制流解耦，使得这一步与可以不考虑哪台chunkserver是primary。
4. 一旦所有副本都对收到的数据进行了应答，client将会发送一个write请求给primary.这个请求标识了之前推送到所有副本的数据。此时primary会给所有的标识(多个client)分配连续的编号(串行），以此提供顺序，并按此顺序在本地进行变更。
5. primary向所有的secondary副本应用此序列的更改。
6. 所有的secondary副本告诉primary完成了此次的变更操作。
7. primary回复client。任意副本遇到的任何错误都会被报告给client。即使错误发生，write操作可能已经在primary或secondary的任意子集中被成功执行。（如果错误在primary中发生，那么操作将不会被分配顺序，也不会被继续下发到其他副本。）只要错误发生，该请求都会被认为是失败的，且被修改的区域的状态为inconsistent。client中的代码会通过重试失败的变更来处理这种错误。首先它会重试几次步骤（3）到步骤（7），如果还没有成功，再从write请求的初始操作开始重试。

如果applicant发出的一次write请求过大/跨多个chunk,GFS的client就会拆分为多个write操作。每个操作都会按照上诉的控制流执行。但是可能存在与其他client的并发的请求交叉或被其他client的并发请求覆盖的情况。因此，共享的文件区域最终可能包含来自不同client的片段。但共享的文件区域中的内容最终是相同的，因为每个操作在所有副本上都会以相同的顺序被成功执行。正如章节2.7中所述，这会使文件区域变为consistent but undefined状态。

3.2 数据流

区分解耦数据流和控制流是很重要的。gfs的控制流就是通过流程将client推送到各个副本，而数据流则是primary可以把已经得到的数据按什么方式 (规则） 去进行applicate。

• 利用每台机器的网络带宽，避免网络瓶颈和高延迟的链路，并最小化推送完所有数据的时延。每台机器会将数据传递给在网络拓扑中最近的的且还没有收到数据的机器。每台机器可以打满自己outbound bandwidth。
• 最小化数据传输的延迟。通过pipline传输数据的方式，因为使用全双向连接的网络，发送数据不会减少接收的速率。

这一部分感觉跟业务中的领域驱动是一个道理，区分规则引擎与流程引擎，实现业务上的解耦，流程调度获取source/data(控制流），规则则通过source/data实现业务内的规则计算(数据流）。

3.3 原子性的操作：Record append

• record append提供了一种原子性的追加操作，适合于多个客户端并发写入同一个文件的场景，不需要考虑额外的复杂且开销很高的同步操作（例如分布式锁管理）。而write操作则需要客户端自己管理偏移量，并在跨块写入时可能面临原子性问题。
• 原子性的保证：record append操作限制了每次最多写入最大chunk大小的四分之一的数据，以保证在最坏的情况下产生的碎片在可接受的范围内，避免了跨越边界的写入分解成多个操作，从而保证了并发写入数据时的原子性。

3.4 快照-SNAPSHOT

• GFS可以允许用户几乎瞬间创建一个文件或目录树（称为“源”）的副本，同时最小化对正在进行的修改的中断。
• GFS使用COW(写时复制）技术实现快照,在实现快照的时候，涉及所有快照文件相关的未完成租约，将会被撤回。在租约被收回或过期后，master会将快照操作记录到日志中，并写入到磁盘。随后，master会通过在内存中创建一个源文件或源目录树的元数据的副本的方式来进行快照操作。新创建的快照文件与源文件指向相同的chunk。
• 首次写操作时的处理(COW)： 当客户端首次想要写入一个已经进行了快照操作的chunk C时，它会向master发送请求以找到当前的租约持有者。master注意到chunk C的引用计数大于1，于是暂不回复客户端，而是选择一个新的chunk句柄C’，并要求每个拥有chunk C当前副本的chunkserver创建一个新的chunk C’。通过在与原始chunk相同的chunkserver上创建新的chunk，可以确保数据能够进行本地复制，而不是通过网络传输，因为磁盘速度比网络链接快大约三倍（GFS所用的磁盘速度比100 Mb以太网链路快约三倍）。
• 请求处理的后续步骤： 从创建新chunk C’的这一刻起，请求处理与任何其他chunk的处理方式没有不同：master授予其中一个副本对新chunk C’的租约，并回复客户端，客户端可以像往常一样写入chunk，而不必知道它刚是从一个现有的chunk创建而来的。

4. master操作

master执行所有命名空间的操作。除此之外，master管理整个系统中的chunk的副本。这包括了chunk的分配决策（placement）。创建新的chunk与副本，协调各种系统范围内的活动，平衡所有chunkservers的负载并回收未使用的存储。

4.1 namespace的管理与锁定

• 命名空间管理与锁定的总体方式：GFS的命名空间管理与锁定机制允许多个操作同时活跃，通过在命名空间区域上加锁来确保正确串行化，避免长时间运行的主操作延迟其他操作。
• 命名空间的逻辑表示： GFS将命名空间逻辑上表示为一个查找表，映射完整路径名到元数据，使用前缀压缩高效地在内存中表示该表。每个命名空间树节点（绝对文件名或绝对目录名）都有一个读写锁。
• 主操作获取锁的方式： 每个主操作在运行前会获取一组锁。通常，若操作涉及路径/d1/d2/…/dn/leaf，则会获取/d1、/d1/d2、…、/d1/d2/…/dn的读锁，以及/d1/d2/…/dn/leaf的读锁或写锁（取决于操作类型）。
• 锁机制的优良特性： 该锁机制允许在同一个目录中进行并发修改操作。例如，多个文件创建操作可以在同一目录中并发执行，每个操作获取目录名的读锁和文件名的写锁，目录名的读锁足以防止目录被删除、重命名或快照，文件名的写锁则保护文件本身不被修改。

4.2 副本的分配

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

4.3 chunk（副本）的创建、重做副本、重均衡

chunk（副本）的创建往往有三个原因：创建、重做副本、重均衡。

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

• 区块重部署 : 当某个块的可用副本数量低于用户指定的目标值时，系统会触发重新复制机制。这种情况可能由多种原因导致，比如chunkserver不可用、副本损坏或磁盘故障等。系统会根据以下因素为需要复制的块分配优先级： 1. 与目标副本数的差距（失去两个副本比失去一个副本的优先级更高） 2. 文件的活跃状态（活跃文件优先于已删除文件） 3. 是否影响客户端操作（阻塞客户端进度的块会获得更高优先级）

• ** 区块重均衡** ：Master会定期检查系统中副本的分布情况，并通过移动副本来优化磁盘空间使用和负载均衡。在处理新加入的chunkserver时，系统采用渐进式填充策略，避免突然分配大量数据而导致过重的写入负载。为了防止复制操作影响正常客户端访问，系统会对整个集群和单个chunkserver的同时复制操作数量进行限制，并通过限制带宽来控制复制速度。这种多层次的副本管理机制确保了GFS能够在保持高可用性的同时，实现良好的负载均衡和资源利用率

4.4 垃圾回收

在文件被删除后，GFS不会立刻回收可用的物理存储空间。master仅在周期性执行懒式垃圾回收时回收物理存储空间，其中垃圾回收分为文件级垃圾回收和chunk级垃圾回收。我们发现这种方法可以让系统更为简单可靠。

4.4.1 机制

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

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

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

4.4.2 优缺点讨论

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

总结下来垃圾回收其实处理的方法都很普遍。常见的语言垃圾回收可以从：回收哪些，什么时候回收，怎么回收。这里回收哪些就是直接是用户删除。
像java回收就是一般回收堆内存，因为程序计数器、虚拟机栈、本地方法栈这三个区域随线程生、随线程死，然后再从堆里判断哪些又是死亡的对象，从而延伸引用计数、gc root可达，go和java都是root可达。这里就是chunk可达的，回收孤儿chunk的storage。然后从什么回收的层面上主要是内存分配失败、或者是系统空闲时回收 go和java都是类似的。而这里也是系统空闲时master心跳时合并处理。怎么回收就是标记清除、标记复制、标记整理等。这里则是直接扫描删除。

4.5 陈旧副本检测

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

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

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

这块在分布式中检测一致性的方法其实很普遍，就是通过一个额外的版本去作为是否在一个统一的周期。像raft则就是通过任期来判断，是否是同一个领导者的周期。

5 故障容错与诊断

5.1 高可用

在上百个GFS集群中总会有一些在某个时间段不可用，我们通过两个简单但有效的策略保证整个系统高可用：快速恢复和副本。

5.1.1 快速恢复

在master和chunkserver的设计中，它们都会保存各自的状态，且无论它们以哪种方式终止运行，都可以在数秒内重新启动。通常，服务会直接被通过杀死进程的方式终止。当client和其他服务器的请求超时时，它们会在发生一个时间很短的故障，并随后重新连接到重启后的服务器并重试该请求。

5.1.2 chunk复制

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

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

5.1.3 Master复制

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

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

5.2 数据完整性

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认为有足够有效的副本存在。