猪小花1号

个人签名

281篇博客

最新博客

最新资源下载

编辑推荐

网易数帆开源API网关与容器云项目，让云原生生产落地“多快好网易汪源：统一负载与多云环境的“开放姿态”，才是云原生网易数帆如何用 Kubernetes“原语”搞定云原生中间件快手打新挤爆券商系统，网易数帆推出券商稳定性保障方案探索智慧校园新模式，网易有数在教育行业的实践分享金融行业大数据治理之路——数据模型篇

GFS论文（2003）小结

猪小花1号2018-09-03 10:06

作者：李小翠


Motivation

  • meet the rapidly growing demands of Google's data processing needs
  • 目标：高性能、高可扩、高可用
  • 背景： 元器件失效是常事、大文件(Multi-GB files are common)、大多数文件为追加(appending over than overwriting)、应用程序和文件系统的API协同设计，不遵循POSIX规范(co-designing the application and the file system API)
  • 使用场景：生产者-消费者队列

Workload

  • big data(tipically 100MB/multi-GB files/growing data sets of many TBs comprising billions of objects)
  • small files support but not optimize
  • append rather than overwriting
  • detect、tolerant and recover promptly from component failures
  • large streaming reads(1M or more) and small random reads
  • large sequential writes that append data to files
  • concurrently append to the same file
  • high sustained bandwidth more important than low latency

Interface

creat delete open close read write snapshot record append

snapshot ：creates a copy of a file or directory tree at low cost [copy-on-write]record append：allowmutiple clients to append data to the same file concurrently [producer-consumer queues]

Architecture


组成


  • sigle master
  • mutiple chunkservers
  • accessed by mutiple clients

chunk： 文件被分解成固定大小的chunks——由全局唯一的64bit chunk handle标识（在创建文件的时候由master分配）

chunkserver：

  1. 把chunk以linux文件的形式存储在磁盘上
  2. 通过chunk handle 和 byte range来读取文件
  3. 每个chunk备份在不同的chunkserver中（默认三备份）

master：

  1. 存储文件系统的所有元数据[命名空间(kept persistent by logging mutations to a operation log stored on the masters local disk)，控制信息，文件和chunk的映射信息(log)、chunk副本存放信息]
  2. 系统控制[chunk租约管理、垃圾回收、chunckserver之间chunk的迁移]
  3. 定期和chunkserver进行心跳[give insturctions and collect state]

client：

  1. 以库的形式被连接到程序中
  2. 实现了GFS系统的API函数
  3. 应用程序通过client完成与master节点和chunkserver的通信，以及对数据的读写操作
  4. 客户端从master获取元数据，从chunkserver中获取数据

tips： client和chunkserver都不会缓存文件数据

reason：

  1. 大部分程序以流的方式读取一个巨大的文件，或者工作集太大无法缓存
  2. chunk是保存在本地文件中，Linux系统的文件系统缓存会把进场访问到的数据放在内存中

读取流程：

  1. 应用程序指定文件名和字节偏移量
  2. 客户端把根据chunk的大小，把应用程序指定的文件转换成文件的chunk index；并把文件名和chunk index发送给master节点
  3. master将相应的chunk handle和副本位置信息返还给客户端
  4. 客户端用文件名和chunk索引作为key缓存master发送过来的信息
  5. 客户端发送请求到副本（一般选择最近的），请求包含[chunk handle和字节范围]

操作日志：

  • 包含关键元数据的变更历史（元数据唯一持久化的存储记录）
  • 这里运用的就是WAL，把相应的日志记录写到硬盘之后，才会响应客户端的操作请求

一致性模型

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

已定义：对文件修改之后，各副本是一致的，并且客户端能够看到写入操作的全部内容（隐含了一致性）

一致：无论从哪个副本读取，读到的数据都是一样的

一致未定义：所有客户端看到同样的数据，但是无法读到任何一次写入操作写入的数据

不一致：不同客户端在不同的时间看到不同的数据（也是未定义的）

数据修改操作包括：

写入：把数据写在应用程序指定的文件偏移位置上。

追加：并行执行时，记录追加操作至少可以把数据原子性的追加到文件中一次，偏移位置由GFS返回

GFS追加流程的特色： 链式复制 + 分离数据流与控制流（如下图所示）
链式复制：减少延迟 
分离数据流与控制流：前提是每次追加的数据都比较大


系统交互

重要原则：最小化所有操作和Master节点的交互
客户端、Master服务器、chunk服务器之间的交互，以实现数据修改操作、原子的记录追加操作、快照功能

1. 租约机制

GFS的追加操作每次为几十KB到几MB不等，每次追加都请求Master的话会使Master成为系统性能瓶颈，GFS通过lease机制将chunk的写操作授权给chunk，在租约有效期内，对该chunk的写操作都由主chunk负责，减轻master的负载，主chunk对chunk的所有更改操作进行序列化，所有副本都遵从这个序列进行修改操作。

总的来说，对于修改操作，首先由master节点选择的租约的顺序决定，然后由租约中主chunk分配的序列号决定！

上面的追加流程为：

  1. client询问Master持有租约的chunk server及其副本位置。如果没有chunk server持有租约，master会按照一定的策略将chunk租约授权给其中一台chunk server
  2. master返回客户端主副本和备副本所在的chunk server的位置信息，client缓存这些信息供以后使用。如果没有故障，客户端以后读写该chunk都不需要再次请求master
  3. client将需要追加的记录发送到每一个副本（GFS采用的是数据流和控制流分离的方法）
  4. 副本确认都收到了数据，client发起写请求到主chunk server。这个请求标识了早前推送到所有副本的数据，主chunk为接收到的所有操作分配连续的序列号，保证操作的顺序执行。它以序列号的新婚徐把操作应用到自己本地状态机上，RSM.
  5. 主chunk把请求传递到所有secondaries，secondaries依照主chunk分配的序列号以相同的顺序执行这些操作
  6. secondaries发送消息给主副本告知操作完成
  7. 主chunk回复客户机。任何副本产生的任何错误都会返回给client，client会进行重试等处理

如果应用程序一次写入的数据量很大，或者跨越了多个chunk，client会把它们分成多个写操作。这就可能会被其他client同时进行的操作打断或者覆盖。因此共享文件可能包含来自不同client的数据。但是这些分解后的写入操作是以相同的顺序在chunk上执行的，chunk所有副本都是一致的，这就使得文件处于一致的、但是未定义的状态。

2. snapshot

snapshot操作是对源文件/目录进行snapshot，生成该时刻源文件/目录的一个瞬间状态存放在目标文件/目录中。GFS使用copy on write技术（只增加GFS中chunk的引用技术，表示这个chunk被快照文件引用了，等到客户端修改这个chunk时，才需要在chunkserver中拷贝chunk的数据生成新的chunk，后续的修改操作落到新生成的chunk上）

对某个文件做快照:

  1. 通过租约机制收回对文件每个chunk的写权限，停止对文件的写服务
  2. master拷贝文件名等元数据生成一个新的快照文件
  3. 对执行快照的文件的所有chunk增加引用技术

Master的操作

1. namespace management and locking

逻辑上，GFS的namespace是一个全路径和元数据映射关系的查找表。利用前缀压缩这个表可以高效的存储在内存中。

每个绝对路径的文件名或绝对路径的目录名都有一个关联的读写锁。

2. 副本位置的选择

策略目标：最大化数据可靠性和可用性，最大化网络带宽利用率

3. 创建、重新复制、负载均衡

creation：把chunk副本分布在多个机架之间（考虑硬盘的使用率，限制每台chunk上“最近”的创建操作次数）

re-replication：chunk的有效副本数量少于用户指定复制因数的时候，master节点重新复制它

rebalance：周期性地对副本进行重新负载均衡

4. GC

GC采用延迟删除机制。删除文件后，GFS不要求立即归还物理内存，在元数据中将文件改名为一个隐藏的名字，并且包含一个删除时间戳。
GC一般在服务低峰期执行

master定期检查，发现删除文件超过一段时间：

  • 先把文件从内存元数据中删除
  • 在chunk server和master的心跳消息中，master回复元数据已经不存在该chunk信息
  • chunk server释放chunk副本

容错

1. Master容错

  • 操作日志加checkpoint，定期将内存中的数据以checkpoint文件的形式转存储到磁盘中，从而减少日志的回放量
  • shadow master 实时热备

2. chunk server容错

  • 复制多个副本，确保副本保持一定的个数
  • 对存储的数据维持校验和，以block（64KB）为单位，每个block对应32位校验和。


网易云大礼包：https://www.163yun.com/gift

本文来自网易实践者社区，经作者李小翠授权发布。


推荐博客