GFS-Google论文阅读笔记

众所周知，Hadoop的存储基础，HDFS分布式文件系统，是按照GFS的思想实现的。

本文参考：Google File System 中文版 1.0 版 译者 alex，原文地址 http://blademaster.ixiezi.com/

GFS是面向大规模数据密集型应用的，可伸缩的分布式文件系统。

1. 重要设计思路

1. 组件失效被认为是常态而不是突发事件，高度强调灾备和自动恢复
2. 按照文件非常巨大的方向设计
3. 绝大部分修改是在文件尾部追加，而不是覆盖原有数据：文件写完之后对文件最多的操作是读取，客户端无需缓存数据块，通过数据追加来优化性能和保证原子性
4. 应用程序和文件系统API的协同设计提高系统灵活性。e.g. 通过原子性的记录追加的引入.放松GFS对一致性模型的要求

2. 设计概述

2.1 设计预期

• 对于小文件随机读取的解决方式：通常做法是把小规模的随机读取操作合并并排序，之后按照顺序批量读取，这样可以避免在文件中前后来回读取位置

• 高性能带宽比低延迟重要，我们要求高速数据交换，不要求响应时间

  这一特性在做数据分析的时候没有问题，但是对于要求相应时间的工作上，后来又提出了许多解决方案，但并没有实质上改变这一设计初衷

2.2 接口

GFS提供了一套类似传统文件系统的API接口，虽然并不是严格按照POSIX(The Portable Operating System Interface)等标准实现的。

• 快照：快照以很低的成本创建一个文件或者目录树的拷贝。
• 记录追加：操作允许多个客户端同时对一个文件进行数据追加操作，同时保证每个客户端的追加操作都是原子性的。这对于实现多路结果合并，以及生产者-消费者队列非常有用，多个客户端可以在不需要额外的同步锁定的情况下，同时对一个文件追加数据。

2.3 架构

• Master 节点：

  管理所有的文件系统元数据。这些元数据包括名字空间、访问控制信息、文件和 Chunk 的映射信息、以及当前 Chunk 的位置信息。 Master 节点还管理着系统范围内的活动，比如， Chunk 租用管理（Lease）、（orphaned ）孤儿 Chunk的回收、以及 Chunk 在 Chunk 服务器之间的迁移。 Master 节点使用心跳信息周期地和每个 Chunk服务器通讯，发送指令到各个 Chunk 服务器并接收 Chunk 服务器的状态信息。

• Chunk节点：

  在 Chunk 创建的时候， Master 服务器会给每个 Chunk 分配一个不变的、全球唯一的 64 位的 Chunk 标识。 Chunk 服务器把 Chunk 以 Linux 文件的形式保存在本地硬盘上，并且根据指定的 Chunk 标识和字节范围来读写块数据。

无论是客户端还是 Chunk 服务器都不需要缓存文件数据，不过客户端会缓存元数据。 Chunk 服务器不需要缓存文件数据的原因是， Chunk 以本地文件的方式保存， Linux 操作系统的文件系统缓存会把经常访问的数据缓存在内存中。

2.4 单一Master节点

客户端并不通过 Master 节点读写文件数据。反之，客户端向 Master 节点询问它应该联系的 Chunk 服务器。客户端将这些元数据信息缓存一段时间，后续的操作将直接和 Chunk 服务器进行数据读写操作。

根据Figure 1。

• 首先，客户端把文件名和程序指定的字节偏移，根据固定的 Chunk 大小，转换成文件的 Chunk 索引。然后，它把文件名和 Chunk 索引发送给 Master 节点。 Master 节点将相应的 Chunk 标识和副本的位置信息发还给客户端。客户端用文件名和 Chunk 索引作为 key 缓存这些信息。
  • 之后客户端发送请求到其中的一个副本处，一般会选择最近的。

请求信息包含了 Chunk 的标识和字节范围。在对这个 Chunk 的后续读取操作中，客户端不必再和 Master 节点通讯了，除非缓存的元数据信息过期或者文件被重新打开。客户端通常会在一次请求中查询多个 Chunk 信息， Master 节点的回应也可能包含了紧跟着这些被请求的 Chunk 后面的 Chunk 的信息。

在实际应用中，这些额外的信息在没有任何代价的情况下，避免了客户端和 Master 节点未来可能会发生的几次通讯。

2.5 chunk尺寸和元数据

• chunk尺寸

  Chunk 的大小是关键的设计参数之一。我们选择了 64MB，这个尺寸远远大于一般文件系统的 Block size。每个 Chunk 的副本都以普通 Linux 文件的形式保存在 Chunk 服务器上，只有在需要的时候才扩大。

  这种chunk尺寸可以减少对master节点的请求；可以保持长的tcp请求；减少元数据

  同时缺点也非常明显，小文件只有一个chunk的话可能会导致热点问题

• 元数据：

  Master 服务器存储 3 种主要类型的元数据，包括：文件和 Chunk 的命名空间、文件和 Chunk 的对应关系、每个 Chunk 副本的存放地点。所有的元数据都保存在 Master 服务器的内存中。前两种类型的元数据同时也会以记录变更日志的方式记录在操作系统的系统日志文件中，日志文件存储在本地磁盘上，同时日志会被复制到其它的远程 Master服务器上。

2.6 一致性模型

	写	记录追加
串行成功	已定义	已定义
并行成功	一致但是未定义	部分不一致
失败	不一致	不一致

3. 系统交互

原则：最小化所有操作和Master节点的交互。

1. 使用租约lease机制来保持多个副本间变更顺序的一致性

   

2. 数据流

   沿着Chunk服务器数据链进行推送，接受数据的Chunk服务器同时通过管道在全全双工的模式下向距离自己最近的同时也在链路上的Chunk服务器推送。在没有网络阻塞的情况下，传送B字节到R个副本的理想时间B/T+L*R，T是吞吐量，L是两台机器之间的传输延迟。

3. 原子记录增加

   GFS 提供了一种原子的数据追加操作–记录追加。传统方式的写入操作，客户程序会指定数据写入的偏移量。对同一个 region 的并行写入操作不是串行的： region 尾部可能会包含多个不同客户机写入的数据片段。使用记录追加，客户机只需要指定要写入的数据。 GFS 保证至少有一次原子的写入操作成功执行（即写入一个顺序的 byte 流），写入的数据追加到 GFS 指定的偏移位置上，之后 GFS 返回这个偏移量给客户机。这类似于在 Unix 操作系统编程环境中，对以 O_APPEND 模式打开的文件，多个并发写操作在没有竞态条件时的行为。

4. 快照

   使用copy-on-write技术实现快照。

   当 Master 节点收到一个快照请求，它首先取消作快照的文件的所有 Chunk 的租约。这个措施保证了后续对这些 Chunk 的写操作都必须与 Master 交互以找到租约持有者。这就给 Master 节点一个率先创建Chunk 的新拷贝的机会。

4. Master节点的操作

1. 名称空间和锁

   我们不希望在一些工作量较大的master节点的操作的运行时，延缓了其它的 Master 节点的操作。因此，我们允许多个操作同时进行，使用名称空间的 region 上的锁来保证执行的正确顺序。 因为名称空间可能有很多节点，读写锁采用惰性分配策略，在不再使用的时候立刻被删除。同样，锁的获取也要依据一个全局一致的顺序来避免死锁：首先按名称空间的层次排序，在同一个层次内按字典顺序排序。

2. 副本的位置

   Chunk 副本位置选择的策略服务两大目标：最大化数据可靠性和可用性，最大化网络带宽利用率。

3. 创建，重新副本，重新负载均衡

   需要考虑的几个因素：

   1. 平衡硬盘使用率
   2. 限制同一台Chunk服务器上进行的创建/复制的操作数量
   3. 在机架间分布副本

4. 垃圾回收

   一开始只做日志标记，将文件隐藏，然后过几天在做删除

   所有不能被Master节点识别的副本将被删除。垃圾回收会分散到各种例行操作里，同时会在Master节点相对空闲的时候完成。master节点会保存副本的版本号确保访问数据的正确性。

5. 容错和诊断

• 高可用性：
  • 快速恢复：不管 Master 服务器和 Chunk 服务器是如何关闭的，它们都被设计为可以在数秒钟内恢复它们的状态并重新启动。
  • Chunk复制：虽然 Chunk复制策略对我们非常有效，但是我们也在寻找其它形式的跨服务器的冗余解决方案，比如使用奇偶校验、或者 Erasure codes来解决我们日益增长的只读存储需求。
  • Master的复制：对 Master 服务器状态的修改操作能够提交成功的前提是，操作日志写入到 Master 服务器的备节点和本机的磁盘。 GFS 中还有些“影子” Master 服务器，这些“影子”服务器在“主” Master 服务器宕机的时候提供文件系统的只读访问。 这里要注意，我们都知道Namenode在Master上，但是SecondaryNamenode并不是其备份，而是辅助Namenode工作的。并不是这里提到的备用节点
• 数据完整性：每个 Chunk 服务器必须独立维护 Checksum 来校验自己的副本的完整性 。和其它元数据一样，Checksum 与其它的用户数据是分开的，并且保存在内存和硬盘上，同时也记录操作日志。 Checksum 的计算可以和 I/O 操作同时进行。
• 诊断工具：GFS 的服务器会产生大量的日志，记录了大量关键的事件（比如， Chunk 服务器启动和关闭）以及所有的 RPC 的请求和回复。

6. 实验，一些经验，相关工作

这里这里主要说一下相关工作

AFS类似，GFS 提供了一个与位置无关的名字空间 ：John Howard, Michael Kazar, Sherri Menees, David Nichols, Mahadev Satyanarayanan, Robert Sidebotham, and Michael West. Scale and performance in a distributed file system. ACM Transactions on Computer Systems,6(1):51–81, February 1988

和其它的大型分布式文件系统，比如 AFS类似， GFS 提供了一个与位置无关的名字空间，这使得数据可以为了负载均衡或者灾难冗余等目的在不同位置透明的迁移。不同于 AFS 的是， GFS 把文件分布存储到不同的服务器上，这种方式更类似 Xfs[1]和 Swift[3]，这是为了提高整体性能以及灾难冗余的能力。

Xfs:Thomas Anderson, Michael Dahlin, Jeanna Neefe, David Patterson, Drew Roselli, and Randolph Wang.Serverless networkfil e systems. In Proceedings of the 15th ACM Symposium on Operating System Principles, pages 109–126, Copper Mountain Resort, Colorado, December 1995.

Swift:Luis-Felipe Cabrera and Darrell D. E. Long. Swift: Using distributed disks triping to provide high I/O data rates. Computer Systems, 4(4):405–436, 1991.

GFS 很类似 NASD 架构[4]。 NASD 架构是基于网络磁盘的，而 GFS 使用的是普通计算机作为 Chunk 服
务器，就像 NASD 原形中方案一样。所不同的是，我们的 Chunk 服务器采用惰性分配固定大小的 Chunk 的方
式，而不是分配变长的对象存储空间。此外， GFS 实现了诸如重新负载均衡、复制、恢复机制等等在生产环
境中需要的特性。

Garth A. Gibson, David F. Nagle, Khalil Amiri, Jeff Butler, Fay W. Chang, Howard Gobioff, Charles Hardin, ErikR iedel, David Rochberg, and Jim Zelenka. A cost-effective, high-bandwidth storage architecture. In Proceedings
of the 8th Architectural Support for Programming Languages and Operating Systems, pages 92–103, San Jose,
California, October 1998.

我们通过原子的记录追加操作实现了生产者-消费者队列，这个问题类似 River[2]中的分布式队列。 River
使用的是跨主机的、基于内存的分布式队列，为了实现这个队列，必须仔细控制数据流；而 GFS 采用可以被
生产者并发追加记录的持久化的文件的方式实现。 River 模式支持 m-到-n 的分布式队列，但是缺少由持久化
存储提供的容错机制， GFS 只支持 m-到-1 的队列。多个消费者可以同时读取一个文件，但是它们输入流的区
间必须是对齐的。

Remzi H. Arpaci-Dusseau, Eric Anderson, Noah Treuhaft, David E. Culler, Joseph M. Hellerstein, David
Patterson, and Kathy Yelick. Cluster I/O with River: Making the fast case common. In Proceedings of the Sixth
Workshop on Input/Output in Parallel and Distributed Systems (IOPADS ’99), pages 10–22, Atlanta, Georgia, May

1. ​