猪小花1号

个人签名

282篇博客

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

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