为了在分布式系统的技术栈中有更深的意识和更松软的根底，筹备在这个季度破费工作外的工夫对Google和Amazon一系列分布式数据的论文进行研读学习，并将研读后果整顿为博客记录。

本篇研读的论文是The Google File System，发表于2003年的SOSP，介绍了Google的GFS文件存储系统。

Design Overview

Assumptions

GFS自身属于分布式存储系统，其设计次要针对以下几点假如：

  • 零碎构建于便宜的部件上，部件生效是失常事件。
  • 零碎存储的是数量较少的大文件。具体来说，预期文件数量在百万级，每个文件大小通常会达到100MB以上，也会有文件达到几个GB的大小。
  • 零碎上文件的读场景次要有两种。一种是每次读取操作会拜访几百K甚至1MB以上间断数据的大规模流式读取。一种则是一次读取几百K随机地位数据的小规模随机读取。
  • 零碎上会有大量程序写入的append操作，数据量与读操作相当，且一旦写入很少会进行批改。
  • 零碎须要无效地实现定义良好的语义来反对多客户端的并发操作。其重点是应用起码的同步开销来保障操作原子性。
  • 相比于低提早，继续的高带宽更重要。

这些假如实际上也就是GFS分布式文件系统的需要。为了准确匹配这些需要，GFS做了许多非凡设计和优化操作。

而从零碎设计的角度来说，没有哪一种设计是可能服务所有场景的。在进行零碎、算法、数据结构的设计之前，咱们都应该为它建设一个精准的场景假如，从而在计划取舍时有明确的倾向性，也合乎程序“do one thing and do it well”的哲学。

Architecture

GFS的次要架构如下图：

零碎由一个master节点和多个chunk server节点组成。数据文件都被切分成了固定大小的chunk，并由一个64bit的chunk handle惟一标识。同时每个chunk会保留3份正本以保障高可用性。

Single Master

单个主节点可能简化整个集群的设计，主节点可能实现所有的决策工作。但同时，为了保障主节点不会成为性能瓶颈，设计时做了几点优化：

  • master节点从不负责数据传输，只负责控制协议，即告知client申请的chunk在哪个chunk server上。
  • client对同一个chunk的申请只须要一次和master的交互，之后会缓存chunk的信息直到过期。
  • client能够一次申请多个chunk信息。
  • master也能够返回申请chunk之后紧跟着的chunk信息给client，缩小client和master节点的交互。

能够看到，大部分的优化都利用了程序的局部性，简略且实用。

Chunk

在GFS零碎中，为了应答非凡的大数据需要，chunk设计也有如下特点：

  • chunk大小为64MB，远高于传统的文件系统。
  • chunk存储采纳惰性空间调配，尽可能防止碎片。

chunk设计的很大，一方面实用于大数据利用的场景，另一方面缩小了client和master、chunk server的交互。同样的数据量下，chunk的地位信息和元数据也更少，client更容易缓存，master也更容易存储。

这种chunk设计也有一个毛病，就是如果一份文件比拟小，只占用几个或只有一个chunk，同时又是一个热点文件时，会造成存储这份文件的几个chunk server负载过重。论文中给出了两个计划：

  • 疾速的解决方案是减少热点文件的正本数量，扩散client的读取。
  • 更长期的解决方案，是容许一个client从其它client上读取热点数据。

Metadata

主节点保留了所有的元数据。元数据包含文件和chunk的namespace、文件到chunk的映射关系、以及各个chunk所在节点的信息。为了保障整个集群的高可用性，对metadata有以下非凡解决：

  • 所有的metadata均保留在master节点的内存中。这里再次显示出大chunk设计的劣势，每个chunk通常只须要64 bytes的metadata。如果数据量进一步减少，只须要再减少master节点的内存即可。
  • master节点并不会长久化存储chunk server存储的chunk正本信息，而是在启动时，以及chunk server退出集群时向chunk server查问。同时通过监控和心跳包时刻放弃信息更新。起因则是chunk server是很有可能呈现故障的，理论的chunk地位信息也可能会因为各种起因产生扭转。
  • GFS会长久化存储的是operation log，操作日志。它记录了并时序化了整个零碎metadata的变动信息，所有事件的前后程序以操作日志记录为准。操作日志通常会保留多个近程正本，只有在所有正本都同步后才会响应metadata的批改操作。
  • 同时当master节点宕机时也会通过反复操作日志来复原，master节点会在操作日志达到肯定大小时在本地保留checkpoint，每次复原从上一个checkpoint开始反复执行无限的操作。checkpoint是一个压缩B树，能够不便的映射到内存。

Consistency Model

首先定义：一块文件区域是“consistent”，代表无论从哪个分片，读取到的数据是统一的。一块文件区域是“defined”，代表在一次数据扭转之后，这块文件区域是“consistent”，且所有客户端能够察看到这次操作所作的具体批改。这里的批改示意“Write”随机写操作和“append”开端增加操作。

GFS对于零碎的一致性有如下的保障：

  • 文件命名空间的扭转（例如创立文件）是原子的。这部分操作由master节点加锁实现，会通过操作日志造成一个惟一的时序动作。
  • 一次胜利的批改操作，在没有并发生产者的烦扰下，文件区域是“defined”的。
  • 一次胜利的并发“write”操作，文件区域是“consistent”的。客户端尽管能读到同样的数据，然而并不能确定每一次操作具体批改了哪一部分。
  • 一次胜利的并发“append”操作，文件区域是“defined”的。起因是append的地位是由零碎算法抉择的，并会返回给客户端以标记出此批改的开始和完结地位。
  • 一次失败的批改操作，会导致文件区域“inconsistent”。

System Interactions

为了实现上一章中形容的架构，达成一致性模型，GFS零碎外部通过通信合作实现三类次要工作：批改数据，原子的append操作以及快照。

Data Flow

数据批改的流程如下图：

首先须要阐明，在一个chunk的多个正本中，有一个正本作为“primary”正本。primary正本会整合对chunk的所有写操作，造成一个线性序列。

  1. client询问master节点持有chunk lease的正本以及其它chunk正本的地位。如果还没有调配lease，则由master节点进行调配。
  2. master节点回复primary和其它正本的地位信息，client会缓存这些信息。
  3. client将批改推送到所有正本。每个chunk server会将批改缓存到LRU的缓冲区，直到被生产或过期。图中能够看到数据流和控制流进行理解耦，使得数据流的流向能够依据拓扑决定，例如图中正本A离Client更近，数据再由正本A发往primary正本。primary正本再发到正本B，是一条依据最近准则形成的转发链。
  4. 当所有正本都收到批改数据后，client向primary正本发送一个写申请。primary正本会对相似的所有client发来的申请进行排序，并按程序执行。
  5. primary正本再告诉其它正本依照同样的程序执行批改。
  6. 其它正本批改完后就告知primary正本。
  7. primary正本将批改后果告知client。

如果这其中有任何的谬误，client都会重试步骤3-7若干次。此时如上一章所述，文件区域是“inconsistent”的。

而如果一次批改波及到多个chunk，那么client就会把它合成为对应各个chunk的若干个独自批改。此时如果还有其它client在并发批改，那么文件区域就处于“consistent”但不“defined”状态。各个分片上的数据是统一的，但批改是混合的。

Atomic Record Appends

append的数据流与数据批改基本一致。不同点在于，primary在接到写申请后，会计算写的起始和完结地位，并告知其它正本截然不同的地位。而此时并发的其它写操作，则会在排序后在上一个写操作之后的高地址进行。操作间不会写同一块文件区域。也因而append操作是原子的，且文件区域是“defined”。

须要留神的是，当append操作失败时，同样会进行重试，而此时重试会产生在新的高地址中。也因而chunk中会蕴含一条record的反复数据。此时须要生产端通过记录的校验和和惟一标识等进行判断。

那么问题是，这里为什么不设计成在原地址上进行重试呢？：在旧址上进行重试就变成了overwrite而不是append操作了。实际上append操作要比overwrite高效很多，因为它不用思考过多的分布式锁等问题。那么能够看到，GFS在这里宁愿多节约存储空间，也要应用append操作晋升性能。

Snapshot

GFS创立快照利用了已有的copy-on-write技术。顾名思义，这种办法在拷贝时会首先创立新的虚拟空间指向原空间，在有写改变时再进行理论的复制。

在GFS中，当创立快照的申请到来时，master会先发出所有待拷贝的chunk租约，保障后续的写申请会先通过和master节点交互。发出租约后就复制原有chunk的metadata，此时新的chunk其实依然指向旧的空间。接着当一个新的写申请到来时，须要向master询问primary chunk信息，master会筛选一个新的chunk持有租约，并告诉所有chunk原来地位的chunk server本地复制chunk，失去新的chunk并开始失常的写操作。

Master Operations

能够看到，整个GFS零碎逻辑最简单的中央其实是master节点。论文第四章就单列一章讲述了master节点做各种操作的办法。

Namespace

GFS不会像传统文件系统一样对每个目录产生具体的数据结构，而是将每个文件和它后面残缺的目录前缀映射到metadata中。例如“/d1/d2/.../dn/leaf”，作为一个残缺的文件门路进行映射。

为了反对并发操作，文件的读操作会依目录程序顺次申请各级目录的读锁：“/d1”、“/d1/d2”、“/d1/d2/.../dn/”、“/d1/d2/.../dn/leaf”，而写操作则会顺次申请各级目录的读锁，和最终写文件的写锁“/d1/d2/.../dn/leaf”。

这种机制在保障并发操作正确性的状况下，提供了很好的并发性能。

Chunk Replica

在创立chunk正本时，master主机会思考：

  • 将chunk放在磁盘负载低于平均水平的机器上，保障负载平衡。
  • 限度每台主机最近新增的chunk数量，保障写操作可能扩散。
  • 将多个正本放在多个机架多个机房的主机上，可能容灾以及在读操作时最大限度利用带宽（当然写操作时也减少了带宽，是一个trade off）。

当chunk正本数量低于预期时，master会对须要复原的chunk进行排序，而后就像新建chunk一样申请新的地位并从还剩下的valid chunk中复制数据。排序次要遵循以下几点：

  • 正本少于冀望的数量越多，优先级越高。
  • 仍然存在的chunk优于文件曾经被删除的chunk
  • 阻塞了客户端过程，也即正在应用的chunk优先级更高。

master节点也会定期进行零碎的rebalance，而不是新增一台chunk server后就把所有新的chunk创立在这台机器上。这会造成短时间内的写入峰值。

Garbage Collection

GFS履行定期垃圾回收机制，已删除的文件会被master标记（按非凡格局重命名），在惯例扫描中发现存在了三天以上的这种文件就会被删除，它的metadata也会被相应革除。扫描中还会革除不再被任何文件指向的chunk。这些信息master会和chunk server在心跳包中交互，此时chunk server可删除对应的chunk。

Master节点还会为chunk存储version信息，用于检测曾经过期的chunk正本并进行垃圾回收。因为垃圾回收是定时的，因而master在返回给client对应的chunk信息时也会带上版本，避免client拜访到过期正本。

Fail Tolerance and Diagnosis

为了保障系统的高可用性，GFS的两大策略是疾速复原和应用正本。所有服务器都能疾速地保留状态并在几秒钟内重启。而如果硬件故障，不论是chunk server还是master节点都有正本能够疾速复原。master节点的“影子节点”还能够充当只读节点，提供略微滞后于主节点的信息，进步零碎的读性能。

为了保证数据一致性，数据不会在多个正本之间进行比拟，而是通过校验和进行本地校验：

  • 在收到读申请时，chunk会在计算查看校验和后再收回数据。
  • 在append操作时，会对最初一块数据校验和进行增加，并计算产生的新数据块的校验和，即便本来最初一块数据曾经有问题，那么在下一次读的时候仍然能发现。
  • 对应随机write操作，则必须先读取并查看写操作所笼罩的第一片和最初一片数据的校验和，而后进行写入，最初再从新计算校验和进行更新。否则新的校验和会笼罩曾经产生的数据谬误。
为什么append不须要先读取并查看校验和，write须要？：append操作对应的地位其实是空的，能够增量式增加校验和。write实质是笼罩写，须要从新计算校验和。如果不事后查看，则会笼罩原来曾经和数据不统一的校验和。

而因为大部分校验和查看产生在读数据时，零碎也会定时查看那些不沉闷的分块，免得在长时间不流动后生效分片越来越多。

整个零碎的诊断工具，最次要依附的就是各服务器具体地打印出日志。程序并异步地打印日志不会造成什么性能损失，然而能够用于剖析整个零碎的流程和性能。

Measurements

在这一章，论文简略介绍了GFS零碎的试验状况。在小规模benchmark试验中，读速率和append速率都与预期相符，write速率稍低，也反映了GFS适宜的工作场景。

在实在Google数据集中，试验数据更随机，但也反映了零碎读多于写，append多于随机write的特点，反映了零碎能很好地利用带宽，master节点不会成为瓶颈，在机器故障时数据恢复的速度也令人满意。

在浏览这一部分的时候，须要略微留神以下bps和MB之间的8倍数量转换，以及一些小的数学计算。

论文也阐明了实在场景的试验数据有肯定的偏颇，因为这是GFS零碎和Google利用互相调节适配的后果。但GFS依然实用于更加通用的分布式大数据存储场景。

"the ratio of writes to record appends is 108:1 by bytes transferred"，这句话的比例是否写反了？

Conclusion

读完这篇文章，我感触最深的是以下两点：

  • 作为一个分布式存储系统，GFS应用了一个Master节点来居中调度。这看起来没有那种纯正的数学美感，仿佛不能显示出零碎设计者的程度。然而，这一计划却是实用而且便宜的。相比于单节点的问题，它带来了更多的收益。况且带有主节点的分布式集群同样能展示摒除了简单算法的简洁美。
  • 一个计划应该解决一类具体的问题。咱们能够提前“优化”，能够思考一个放之四海而皆准的框架，然而这个世界上能解决一类具体问题的计划就曾经是一个好计划了。GFS的设计处处针对着Google的具体利用。定位精准的同时，保留了肯定的扩展性。大一统实践还是留给爱因斯坦吧。

Six Questions

以下是我对这项技术本人的总结和意识：

这个技术呈现的背景、初衷和要达到什么样的指标或是要解决什么样的问题。

GFS是脱胎于Google公司外部的一个分布式文件系统。它的设计重点就是符合于Google外部的一系列文件存储的需要，而谷歌的数据最大的特点是数据量十分之大。其余需要还包含反对高可用，反对高并发等。

这个技术的劣势和劣势别离是什么，或者说，这个技术的trade-off是什么。

相比于在GFS之前的分布式文件系统，我认为GFS的最大劣势是其容许将整个零碎构建在便宜的服务器之上。据吴军博士的介绍，GFS加上MapReduce技术，使得Google得以“用大量的便宜服务器来代替超级计算机，而前者的价格不到后者的1/5，这也使得Google的经营老本比微软和雅虎低得多”。在过后“太阳公司的CEO麦克尼利讥笑Google这种便宜的服务器集群是‘3M胶带纸’粘起来的。然而就是这些‘3M胶带纸粘起来的’便宜服务器让生产高大上服务器的太阳公司关了门”。

而GFS最大的劣势，一是其严格限度了应用场景。因为它的很多设计和优化都是依据应用场景来进行的，那么这个文件系统就失去了通用性。最大的限度就是对读写场景的限度：程序读，程序写。另外其设计使得只有在上规模的零碎中能力充沛展示其劣势，否则出现的更多是其简单的设计，包含简单的流程设计和调度，以及其中对文件进行分片，存储索引信息等引起的空间节约。

另外还有一些小的trade-off，例如应用核心的master节点代替纯分布式设计，应用可能的master单点瓶颈替换了纯分布式系统设计的复杂性。

这个技术应用的场景。

GFS实质上是一个分布式文件系统。论文的Assumption环节曾经具体论述了GFS的应用场景，这里我再用本人的语言整顿一下：

  1. 低成本的硬件：零碎构建于一批便宜硬件之上，其良好的高可用性就是针对这一点进行设计。
  2. 大文件存储：个别的文件大小会达到100MB级别，总的文件数量在M级别。因而像视频流分片之类的存储就不实用。这类文件可能须要在下层的业务逻辑中进行整合。
  3. 流式读取：GFS最喜爱的读操作还是流式读取一整个大文件，而非随机读取，也只反对小规模的随机读取。
  4. 程序写入：于流式读取绝对应，GFS最喜爱一直地进行Append写，写入后很少进行批改。
  5. 反对高并发：这一点是GFS本身的原子操作设计实现的。
  6. 反对继续高带宽，而非低延时：GFS实质上还是一个文件存储系统，实质上作文件传输是其最次要的使命。又因为其上存储大文件的个性，持续保持高带宽更为重要。

技术的组成部分和关键点。

GFS最次要的组成部分就是两局部的实现：GFS master和GFS chunkserver。

技术的底层原理和要害实现。

GFS底层实际上是通过软件管制的形式应用磁盘来进行备份，实现其高可用性，单纯的磁盘相较于磁盘阵列要更加简略，也更加便宜。其中最次要的要害实现就是数据流的管制和数据一致性的保障。

已有的实现和它之间的比照。

依据论文的Related Work形容，GFS的次要比拟者有：AFS，xFS，Swift，Frangipani，Intermezzo，Minnesota's GFS，GPFS，Lustre，NASD等。

与这些零碎相比：

  1. GFS相似AFS提供了与地位无关的命名空间
  2. GFS数据流的过程更像xFS和Swift，不像AFS。
  3. GFS只应用磁盘做备份，不像xFS和Swift须要应用简单的RAID（磁盘阵列）
  4. 与AFS，xFS，Frangipani，Intermezzo相比，GFS不做缓存，因为它的应用场景是流式读取，跑一次个别整个文件只读一遍
  5. GFS有一个核心master服务器，而Frangipani，xFS，Minnesota's GFS和GPFS是纯依赖于分布式算法的零碎。
  6. 与Lustre雷同，GFS没有实现POSIX文件系统。
  7. GFS与NASD的架构很相像，不过GFS基于一般的chunkserver机器，应用固定大小的chunk，同时比NASD实现了更多功能，例如重均衡，快照，数据恢复等，更实用于生产环境。
  8. 与Minnesota's GFS和NASD相比，GFS不反对批改存储设备的模型。
  9. 在数据传输队列中，与River相比，River应用内存队列，反对m-n的分布式队列，但不保障高可用性。GFS只反对m-1的队列，但实现起来高效牢靠。