关于nosql:分布式存储论文研读一GFS

为了在分布式系统的技术栈中有更深的意识和更松软的根底，筹备在这个季度破费工作外的工夫对 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 的队列，但实现起来高效牢靠。