The Google File System
INTRODUCTION
Google File System (GFS)是谷歌提出的一种快速处理数据的文件系统，与传统的分布式文件系统一样，对于性能，可扩展性，可靠性和可用性都有一定的需求。但通过与传统的分布式文件系统相比较，Google认为：
- 组件故障是常态的而非例外；
- 传统标准意义的文件很大；
- 大多数文件在发生变更时，是通过添加新的数据，而不是覆盖原有数据；
- 通过提高我们的灵活性，共同设计应用程序和文件系统API有益于整个系统；
DESIGN OVERVIEW
Assumptions
为了设计符合需求的文件系统，有一些细节需要明确的。
- 该系统的组成部分容易出故障；
- 系统需存储大量的文件；
- 在读取时产生workload，主要出现在大型的流式读取和小的随机读取；
- 在写入时产生workload，主要出现在顺序的追加写入；
- 系统必须为同时附加到同一文件的多个客户端有效地实现明确定义的语义，需要使用原子写入；
- 高带宽比低延迟更重要；
Interface
GFS提供了熟悉的文件系统接口，但它没有实现POSIX等标准API。
此外，GFS还实现了快照和记录追加操作，Record append允许多个客户端同时将数据追加到同一文件，同时保证每个客户端追加的原子性。
Architecture
一个GFS集群包含了一个master服务器和多个被client访问的chunk服务器，每个chunk服务器都是跑着用户级进程的Linux主机。文件被分成固定大小的块存储在chunkserver上，拥有一个唯一的、由master分配的64位ID。为了可靠性，每个chunkserver都做了多重备份，如三备份。
master存储着所有的文件元数据信息，并且与chunkserver通过心跳机制进行沟通。
client和chunkserver都不对文件进行缓存，而是有Linux本身的文件、内存机制进行管理，因为文件太大了。
Single Master
单个master对于我们的设计非常有帮助，为了不使master成为系统的瓶颈，我们需要减少master的IO。因此client不会直接通过master会读写数据，而是向master发送(file name, chunk index)请求，master返回(chunk handle, chunk locations)，这样client就可以通过这个handle和byte range向最近的chunk server获取数据。
对于相同的chunk的读取，client不会再向master做请求，而是到了cache的信息过期了，或者相关文件重新被打开了，才会去与master交互。
Chunk Size
chunk size是关键的设计参数，在这里选定了64MB大小，比一般的文件系统的block略大。
优点：
- 减少了与master交互，因为只需要一次初始的请求得知chunk的位置即可；
- client能对chunk做尽可能多的操作，减少了通过TCP连接时的网络负载；
- 减少了存在master的元数据信息大小，使得其可以存放在内存；
缺点：
- 对于一个小文件，可能只有一个chunk，这很可能因为client都访问同一个文件，造成hot spot的问题；
Metedata
master会保存三种元数据类型：文件和块的命名空间，文件到块的映射，块的位置，所有这些元数据都在master的内存中。
In-Memory Data Structures
把元数据存储在内存中，提高了master的操作速度，并使得master定期扫描元数据状态变得更加方便。另外，虽然这种方式受制于机器内存，但由于每个文件都会有少数的块是部分满的，对于64MB大小的chunk size，我们会采用64个字节去存储元信息。因此可以用来存储这些小于64个字节的元数据信息。除此之外，必要地增加内存也不是很麻烦的事情。
Chunk Locations
master不会拥有chunkserver中关于某个块位置的持久化记录，而是在启动后定期轮询chunkserver（或者有新的GFS chunkserver加入时），获取该信息。因为GFS chunkserver很容易出现宕机，重启等行为，这样GFS master在每次发生这些事件的时候，都要修改持久化存储里面的位置信息的数据。
Operation Log
操作日志包含关键元数据更改的历史记录。 它是GFS的核心。它不仅是元数据的唯一持久记录，而且还充当定义并发操作顺序的逻辑时间线。
在存储时，只有当操作日志被写入到本地master和远程时，master才会对client返回成功。并且，为了提高IO吞吐，master会对日志记录进行批处理。
关于操作日志，master只有在操作日志达到一定大小时才会进行checkpoint，并且checkpoint以B树的结构在内存中存在，之后则可以通过加载最新的checkpoint来重放这之后的操作日志。因为build checkpoint需要一定的时间，所以master会新开一个线程做checkpoint，从而避免影响到来的请求。
Consistency Model
Guarantees by GFS
文件命名空间的修改，比如创建文件，都是由master进行的院子操作，master的操作日志定义了一个全局的执行顺序。
数据修改后，文件区域的状态取决于修改类型，如下图：
- consistent: 所有的client都能看到相同的数据；
- defined: 在文件被修改后，该区域时consistent的并且client能够看到其修改了什么；
Implications for Applications
事实上，应用在修改文件时往往是追加而不是覆盖，典型的，一个writer创建文件后从头到尾追加。追加文件的操作相对于随机写，其效率更高，并且更容易应对应用失败，只需要使用checkpoint重启增量写即可，还可以避免reader读到不完整的数据。
除此之外，还会经常出现的场景是，多个writers并发地追加到一个文件，以作归并输出。readers通过辨识writer留下的检验信息，可以认出并去除额外的对齐和记录碎片，还可以用唯一的ID去除重复的记录。
SYSTEM INTERACTIONS
所有的操作都应该尽量减少与master的交互
Leases and Mutation Order
由于master对于后续的数据流操作是不作控制的，因此需要一种机制保证，多副本以相同的操作顺序写入。GFS会从chunk选定一个chunk server，发送lease，称作primary。由这个primary chunkServer控制写入的顺序。
lease的初始超时为60秒，这些lease是搭载在HeartBeat信息上的，当master与primary失去连接，也可以在旧lease过期重新选择primary。
下图为该控制流程：
- client向master请求当前lease是哪个chunk，和所有的相关副本。如果还没有lease，master则分配一个；
- master返回primary的id和其副本的所在位置给client。client会缓存这些信息，只有当无法连上primary或者其不再持有lease，才会重新联系master；
- client将这些数据信息推送到所有副本，每个chunkserver都会将数据存放在内部的LRU缓存中；
- 一旦所有副本都确认收到数据，client会向primary发送写请求，包含之前写的数据的信息。primary会给此次的请求分配一个序列号，保证多客户端并发时能得到唯一的操作顺序；
- primary向所有副本转发写请求，副本以primary的序列号去修改数据；
- 副本写成功后向primary确认；
- Primary返回给client。任何副本发生任何错误都会返回给client
Data Flow
为了尽可能避免网络瓶颈和链路延迟，每台机器都将数据转发到尚未接收到它的网络拓扑中的“最近”的机器，可以通过IP地址估算距离。
在没有网络拥塞的情况下，将B字节传输到R副本的理想经过时间是B / T + RL，其中T是网络吞吐量，L是在两台机器之间传输字节的延迟。
Atomic Record Appends
GFS提供了一个名为record append的原子追加操作，客户端仅指定数据，GFS选择偏移量，然后以原子方式将其附加到文件至少一次，并将该偏移量返回给客户端。
记录追加与上面的流程有一个额外的逻辑：客户端将数据推送到文件最后一个块的所有副本之后，将其请求发送给primary。primary检查是否将记录附加到当前块将会导致块的大小超过限制（64 MB）。如果是，会把当前的chunk的剩余空间pad起来，然后告诉其他的副本也这么干，最后告诉client这个chunk满了，写入下个chunk。
如果任何副本上的记录追加失败，则客户端将重试该操作。因此，同一块的副本可能包含不同的数据，但副本必须要与primary对齐，使得下次再追加时，无论哪个副本成为了primary，都能保证所有的操作都从同样的偏移开始追加。
Snapshot
我们采用写时拷贝的方法来完成快照操作：
- client向master请求snapshot操作；
- master取消该snapshot涉及到的chunk的所有lease；
- master将该操作持久化到磁盘；
- 复制相关chunk的元数据信息到内存中；
当client要写入相关snapshot的chunk C时：
- client向master请求当前的primary；
- master注意到该chunk的引用计数大于1，然后推迟回复客户端请求，选择一个新的块句柄C'。然后它要求每个具有C的当前副本的块服务器创建一个名为C'的新块；
- master授予其中一个副本在新块C'上的lease并回复客户端；
MASTER OPERATION
The master executes all namespace operations.
Namespace Management and Locking
由于很多master操作会花费很多时间，为了避免master阻塞，允许多种master操作同时running，我们使用锁保证序列化。
GFS逻辑上将namespace表示为完整路径名映射到元数据的查找表，并且通过前缀压缩保证了其在内存中的使用，namespace树中的每个节点都有一个读写锁。
每个master操作前都会获取一组锁，如果设计了路径/d1/d2/.../dn/leaf，那么就会获得一组关于/d1, /d1/d2, ..., /d1/d2/…/dn， /d1/d2/.../dn/leaf的锁。
举个例子，当/home/user被快照到/save/user的时候，/home/user/foo的创建是被禁止的。因为快照操作获取/home和/save上的读锁，以及/home/user和/save/user上的写锁。文件创建需要/home和/home/user上的读锁，以及/home/user /foo上的写锁。其中，/home/user的锁产生冲突。
这种方案的一个好处是保障其可以在同一个文件目录并发执行多个文件创建。
Replica Placement
在GFS集群中，通常有数百个chunk server分布在许多rack上。副本的放置策略有两个目的：最大化数据可靠行和可用性，并最大化网络带宽的利用率。我们必须把chunk的副本分发到不同的rack，这样即使整个rack故障了，这些副本仍然可以存活可用。而且这样在读取的时候也可以利用多个rack的聚合带宽。
Creation, Re-replication, Rebalancing
Chunk replicas are created for three reasons: chunk creation, re-replication, and rebalancing.
- 创建chunk
当chunk server要创建一个chunk时，会考虑以下几种因素：
- 希望chunk server低于平均磁盘空间利用率；
- 限制每个chunk server最近创建的数量，因为创建chunk往往意味着后续会有大量写入；
- 希望在rack上分散chunk的副本；
- 重复复制
一旦可用副本的数量低于用户指定的目标，主服务器就会重新复制一个数据块。需要重新复制的每个块根据几个因素进行优先级排序，一个是它与复制目标的距离（比如优先复制丢失了更多副本的块），另外就是优先重新复制活动文件的块，而不是属于最近删除的文件的块。最后，为了最大限度地减少故障对运行应用程序的影响，我们提高了阻止客户端进度的任何块的优先级。
- 重新平衡
master会定期重新平衡副本，通过检查当前的副本分发并移动副本来获得更好的磁盘空间和负载平衡。同样，对于新加入的的chunk server，master会逐渐填满，而不是用大量的写入流量将其打挂。
Garbage Collection
文件会删除后，GFS不会立即GC，而且在常规GC时，也只是做了lazy delete。
Mechanism
当应用程序删除文件时，master会立即记录删除，并将文件重命名为包含删除时间戳的隐藏名称。在master定期扫描文件系统的期间，如果发现其存在已经超过一定间隔（三天），它将删除此类隐藏文件。在此之前，我们可以通过重命名的方式取消删除。从命名空间中删除隐藏文件时，将删除其内存中的元数据。在与master定期交换的HeartBeat消息中，每个chunkserver报告它具有的块的子集，并且主服务器回复主服务器元数据中不再存在的所有块的标识。这样chunkserver就可以自由删除了。
Discussion
这种回收方法有许多优势：
- 不用担心副本删除信息的丢失，因为heartbeat消息携带了相关信息，可以重试；
- GC被放在master的后台活动中，和定期命名空间扫描等活动一起，使得cost均摊，master可以更加迅速回应其它紧急请求；
- GC的延迟提供了防止意外、不可逆删除的保障；
Stale Replica Detection
当chunkserver失败并且此时错过了chunk的写入变化时，chunk副本很可能会变得过时。
每当master给chunk授予lease时，它会增加chunk的版本号并作持久化，然后其他副本也会做对应更新，这些操作会在返回给客户端之前完成。当失败的chunkserver重启后，其版本号还是落后的，它会向master汇报版本号和chunk。
master在其常规垃圾回收中会删除过时的副本，并且当有客户端作请求时，它会认为落后副本不存在。
FAULT TOLERANCE AND DIAGNOSIS
One of our greatest challenges in designing the system is dealing with frequent component failures.
High Availability
我们通过两种简单而有效的策略保持整个系统的高可用性：快速恢复和复制。
Fast Recovery
无论是正常终止还是异常终止，master和chunkserver都被设计为可以在几秒内快速恢复。
Chunk Replication
每个chunk都被复制在不同rack的多个chunkserver上，client可以指定其复制级别（默认为3），master则根据需要克隆现有的副本。
Master Replication
master的操作日志和checkpoint会在多台计算机上进行复制，只有在其日志记录在本地和所有主副本上刷新到磁盘后，才会认为状态变化已提交。其中，一个master进程仍然在复制所有的修改变化和后台活动。
当master失败时可以立即重启，而当master所在机器故障时，则在其他位置使用复制的操作日志启动新的主进程。
新启动的“shadow” masters只提供读服务，因为可能在挂掉的一瞬间，有些日志记录到primary master上，而没有记录到secondary master上。
Data Integrity
每个chunkserver都使用校验和来检测存储数据是否损坏。
一个chunk被分成64kb大小的块，每个块都有32位的校验和被存在内存和持久化到日志。
对于读取的请求，chunkserver会检查数据块的校验和是否正确，如果checksum不正确，chunkserver会报告给client和master，返回错误，让client从其它副本读取数据。而master会clone一个新副本，当新副本clone好后，master会删除掉这个checksum出错的副本。
Diagnostic Tools
GFS服务器生成诊断日志，记录许多重要事件，比如上下游的chunkservers，RPC的请求和回复。