Google File System 笔记


创新点

  • 把组件故障当做常态,而不是异常。即,要有完备的监控,错误检测,故障恢复机制
  • 通常文件都是巨大的,数以GB是常态
  • 多数文件的修改是追加新数据,而不是覆盖已有数据
  • 综合应用以及系统API一起来设计,从而增加整个系统的灵活性

设计假设

  • 整个系统构建在许多廉价的商用组件之上,所以故障是在所难免的
  • 系统存储了适当数量(几千万)的大文件,大小从几百MB到数以GB不等
  • 读操作通常包含大量的流式读取,和少量的随机读。应用可以通过对小的读取操作组合排序成批量操作从而提高效率
  • 写操作通常是许多大量的顺序的写来追加数据到文件里
  • 对于多client向同一文件并发append的情况,系统必须有效实现一套明确定义的规则
  • 持续的高带宽比低延迟更重要

接口

只支持了一些常规的create,delete,open,close,read 以及 write接口,并没有支持POSIX标准的接口

架构

整体架构图

  • 系统整体由master,chunkservers,client三部分组成
  • 文件的存储单元为chunk,chunk size = 64M(一般FS也就kb级别),默认每个chunk有3个备份(可配置)
    • 大chunksize的优点:
      • 可以利用client的cache,有效减少client同master的交互
      • 意味着client能够在同一个chunkserver上执行更多的操作,节省了网络开销(如果chunksize过小,极端情况下一次数据读取要和多个chunkservers进行交互)
      • 大的chunk size 可以有效减少master上metadata的存储量
    • 大的chunksize的缺点:
      • 如果某个chunk 的访问过热,单机就会变为热点
        • 解决方案:优化业务 or 允许client从其他client获取数据
  • 只有一个master角色,用以存储文件的元数据信息,同时这些元数据信息会备份在多个远程机器上
  • Master通过HeartBeat与chunkservers保持通讯

数据一致性模型

GFS放宽了数据的一致性模型,从而降低系统的复杂度以及可以高效的实现

Namespace
  • Namespace的修改(例如文件创建,重命名)操作是原子性的
File Region State
  • File Region的状态取决于其修改的类型以及操作结果(成功与否),如图:
    • Consisitent:不管从哪个replica读取数据,client看到的都是相同的数据
    • Inconsistent: 一般由操作失败引起
    • Defined:当一个改动操作完成,数据是consistent状态,并且client可以看到改动的内容
    • Undefined:
      • 并发操作存在相互影响时,数据虽然是consistent状体,但是无法看出每个client的修改(例如并发的在同一个位置写入两次
      • inconsistent
  • 概念区分(mutation):
    • write: 向application指定的位置写入数据,offset由application指定
    • record append:即使并发操作情形,也会保证append atomically at leaset once,offset是GFS选择的
  • How to:
    • Success:
      • 通过确保mutations的顺序在所有的replicas上一致来保证defined
      • 使用chunk version number来检测旧的数据(某chunksever宕机时,mutation依旧会Success,然后导致旧数据产生)
    • Failure:
      • 利用Master和chunkservers的心跳以及数据的checksum来检测操作失败生成的脏数据(通过其他replicas来恢复)
        Applications
  • 通过以下技术手段,application可以迁就GFS的较为放松的一致性模型
    • relying on appends rather than overwrites
    • checkpointing
    • writing self-validating
    • self-identifying
  • 场景举例:
    • 场景一: writer创建一个文件,并且从开始到结束(写满即结束?)一直持有这个文件,当数据写完,文件会被writer被重命名为一个permanent name; 或者,writer周期性的通过checkpoint记录写入成功了多少(不太明白啥意思
      • checkpoint可以包含application级别的校验码(checksum)
      • reader只会检验和处理那些和checkpoint对比最新的file region,即defined状态的数据
      • checkpoint可以允许writer增量重启并且让reader继续处理那些在application看来还未完成的数据
      • 不管是并发还是一致问题,当前这个场景都可以较好的应对
    • 场景二: 利用多路归并合,或者通过生产者消费者队列完成多个writer并发的append
      • readers 处理偶然的padding和重复,如下:
        • 由writer对写入的record增加额外的checksum
        • 由reader通过checksum来剔除掉额外的padding数据或者其他record fragments
        • 如果reader可以容忍偶然的重复(例如触发了非幂等的操作),可以通过唯一标识来剔除掉重复

Master

上图为根据论文猜测的结构,比如location可能并不是以这种方式存储的,也有可能是通过所谓的chunk namespace来获取

DATA
  • Namespace
    • 存储位置:disk + memory
    • File Namespace:
      • 启动时加载自Operation log
      • 数据结构为前缀压缩的lookup table,通常小于64byte
      • namespace tree 的每个节点(node)都有一个关联的读写锁
      • namespace的修改为原子操作(atomic)
    • Chunk namespace: 如果也是前缀压缩来实现,就解释不过去了,想不出chunk namespace有什么用
      • 论文中仅有两次提及,具体不详
  • Access control information
    • 存储位置:disk + memory
    • 备注: 文中较少提及,具体不详
  • Mapping from files to chunks
    • 存储位置:disk + memory
    • 详解:
      • 每个文件都被切分为了固定大小的chunk,master里仅存放chunk handle 以及 location
      • chunk handle 是个64bit的唯一标示(猜测是hash获得的,但是为什么不是chunknumber?)
  • Current locations of chunks
    • 存储位置:memory
    • 详解:
      • 通过询问chunkserver获取,一般在启动或者有新chunkserver加入等情况下发生
      • 与client交互时会把client请求的chunk的所有location都返回,由client自己决定(就近)与哪个chunkserver交互
  • Operation log
    • 存储位置:disk
    • 详解:
      • 存放了关键元数据的改动记录
      • 数据同时备份在remote machines上
      • 只有在数据刷新到磁盘上时,才响应client
      • 利用log replay来完成灾难恢复
      • 当日止文件超过一定大小,master会记录checkpoint(使用额外线程,不阻塞当前mutation)
      • B-tree结构存储(可以直接被加载进内存)的checkpoint,方便快速定位,恢复
        功能
  • Namespace Management and Locking
    • 简介:仅用于处理master内部操作(master’s operations)并发冲突
    • 例子:我们在对/home/user目录进行snapshot的时候,如何避免同一时间创建/home/user/foo操作
      • 绿色R代表获取读锁,红色W代表获取写锁
      • 如图:当create操作获取/home/user的读锁时,只能等到其他操作释放掉写锁才能继续
      • create操作不需要对父层目录(/home/user)加写锁,仅需要加读锁,防止该目录被删除即可
    • 注意:为了避免死锁,加锁是先按照namespace tree的level顺序进行的,同level按照字典序
  • Replica Placement
    • 简介:处理chunk replica placement,从而保证scalability,reliability, and availability
    • 目的:最大化数据的可靠性和可用性,同时最大利用化带宽
    • 策略:不仅仅是跨机器,同时需要跨机架(racks)
      • 优点: 是充分保证了可靠性和可用性,同时读操作可以有效利用多机架的带宽资源
      • 缺点: 是跨机架(racks)同样带来的弊端就是写操作时,数据流向不得不得跨机架
  • Creation, Re-replication, Rebalancing
    • 简介:chunk replicas 只在三种情况下被创建:chunk creation, re-replication, and rebalancing
    • Creation(where to place the initially empty replicas):
      1. 放在磁盘空间利用低于所有chunkservers均值的chunkserver上
      2. 限制单个chunkserver最近创建数(如果数字过高,意味着chunkserver会迎来一波大量的写操作)
      3. 跨机架(racks)存放
    • Re-replication:
      • when: 当可用的replicas数低于用户指定的数(默认为3)时
        • chunkservers unavailable
        • chunkservers report its replica corrupted(disk fail,error…)
        • 用户指定的replicas数进行了提升
      • where: 同Creation(此处限制的是单个chunkserver当前active clone操作的数)
    • Rebalance:
      • 对象:当前的replicas分配策略,以及移动已有的replicas
      • 目标: 获得较佳的磁盘使用率和负载均衡
      • 方式:定期的,缓慢进行(避免新的chunkserver一下负载大量写操作)
      • 策略:(选机器而不是选replica) 选择当前的磁盘剩余低于所有chunkservers均值的机器,对其replica进行move操作,从而均衡磁盘使用率
  • Garbage colleciton
    • 简介:GFS的文件删除是一种lazy的方式,依赖定期垃圾回收来回收磁盘物理空间,回收包括file级别和chunk级别
    • 机制:
      • 对于要删除操作,修改文件名为隐藏的名字(hidden name,猜测就像linux带.前缀的文件名),同时文件名带有删除时间戳
      • 定期扫描file namespace,发现如果这种文件存在超过指定时间(默认三天)则执行删除操作,同时删除其metadata
      • 定期扫描chunk namespace(chunk 的 namespace是什么结构,有什么意义??
        • 标记那些失效的chunk(对应的文件已不存在),删除其metadata
        • 同时利用和chunkservers的HeartBeat传递的信息,chunkservers会报告其持有的chunk集合,对比,告知其持有的chunk那些需要删除
    • 优点:
      • 增强了系统的容错性,失败操作造成的一些垃圾chunk,会通过此机制回收
      • 回收操作整合进了master的后台操作和与chunkservers的handshakes中,回收动作得以批量进行,整体开销被分担
      • 这种延迟删除的机制,同时避免了偶然和不可逆的删除操作
    • 缺点:
      • 浪费了存储空间,用户无法通过删除操作来立即释放空间
      • 解决方法:
        • 用户如果对于已经删除的文件再一次进行删除,系统将加快其回收的速度
        • 允许用户对不同的namespace制定不同的回收策略,以及复制策略(例如不进行备份/复制,其删除操作立即执行)
    • Stale Replica Detection
      • 定义:由于操作失败,或者chunkserver宕机造成chunk的修改没有被同步,形成了Stale Replica
      • 方案:
        • master持有chunk version number来区分某个chunk是否是旧的, 并通过垃圾回收机制来回收stale replica
        • 通过client的cache 超时时间以及重新打开文件来尽量限制client读取到过期数据(文中区分了早期(premature)和过期(outdated)数据,某些业务场景读到premature数据应该是可以的

系统交互

系统的整体设计旨在降低master的参与度,毕竟它是整个分布式系统中唯一一个单点,很容易形成瓶颈

租契(leases)和改动顺序(mutation order)
  • 背景:一条修改操作要在所有的chunk replicas上执行,我们使用租契(leases)来管理这个修改顺序
  • 描述
    • Master 向其中一个replicas发放租契(leases),该replica被称作 primary
    • Primary 针对chunk的所有修改动作选择一系列的顺序
    • 当改动提交时,其他replicas依照primary的顺序进行
  • 目的:降低master的管理开销
  • 细节
    • Lease初始的超时时间为60s,超时则意味着当前lease失效,需要master重新下发
    • 如果Lease正在被执行,即chunk正在被执行改动,primary会通过和master交互来确保Lease的超时时间可以无限扩展
    • 上述中的交互是通过Master与chunkservers的HeartBeat捎带进行的
    • 同时,Master可以在Lease过期之前予以撤销(例如撤销重命名)
    • 即使Master和Primary的通讯断开了,在当前Lease过期前,他同样可以下发给其他replica一个新的Lease
    • 如果需要write的数据太大,或者跨越单个chunk,那么该操作会被client拆分成多个write操作;
      • 由于有多个client存在,这些操作会按照相同的顺序进行,但是其中可能会穿插其他client的操作
      • Shared file region 尾部可能包含来自多个client(concurrent write)的数据段(比如clientA 向offset写入4个字节,clientB向ofset+2写入4个字节)
  • 示例
      • 1.client 询问Master对于指定chunk哪个chunkserver持有了当前的lease,同时询问其他replicas的位置;如果没有lease,那么master会选择一个replica,然后下发一个Lease
      • 2.Master告知client当前primary的标识以及其他replicas的位置(secondary),client会把这些数据cache起来,直到primary不可达或者其不再持有lease
      • 3.client会把所有数据push到所有的replicas,chunkservers 会把这些数据存放在内部的LRU cache中,直到过期或者被使用
      • 4.当所有replicas都确认收到了client push的数据,client会向Primary发送write请求,Primary会先行执行操作,同时会为改动操作分配一个序列号
      • 5.Primary想所有的secondary replicas转发此次写请求,secondary按照primary分配的序列号依次执行
      • 6.当操作完成,Secondary会向Primary进行确认回复
      • 7.Primary向Client进行回复,如果执行过程中有任何错误,都会反馈给client。如果写入失败,client会选择重试3-7。
数据流

系统把数据流从控制流中解耦出来,在Figure2中可以明显看出

  • 目标
    • 最大化单机带宽的使用
      • 采用线性的方式来push数据,确保单机的出口带宽可以被充分利用,而不是向树状push时需要将出口带宽分给多个replicas (并没有理解这样有什么高效,树状不也是充分利用了么?后续树状散射push出去貌似可以更高效?)
    • 避免网络瓶颈,和高延迟链接
      • 每个机器都向离其最近的机器push数据
      • distance 可以通过IP地址精确衡量(内网IP吧,肯定是事先按照这种规则分配的IP
    • 最小化延迟
      • 利用TCP链接管道化数据传输,收到数据,立马向下转发,这依赖与全双工的链接(结合这点,似乎能解释的通他比树状push数据高效了
Atomic Record Appends

传统的写入方式,如果client都指定在某个位置写入数据,那么并发写入同一region就不是序列化的,例如region结尾会包含来自多个client的数据段

  • 描述:GFS可以保证其追加操作至少有一次是原子性的(at least once atomically),类似于没有竞争情况下的Unix O_APPEND
    • GFS里大量使用了append操作(特意如此设计,避免随机写),如果按照传统的做法,client端需要额外的负载逻辑以及昂贵的同步机制(例如分布式锁)
    • GFS系统中对这种并发写的的操作通常使用多生产者-单消费者模型或者多client归并结果进行处理
    • record append操作和write一样,遵循Lease那套规则
  • 细节
    • 在执行append操作时,Primary会检查当前chunk(chunk固定最大64M)是否可以容纳这条记录
      • 如果不能,先填充满,填充操作不能超过chunk大小的1/4,避免过多碎片(猜测:如果超了就让client去拆成多条
      • 告知secondaries执行相同操作,同时告知client去下一个chunk重试该操作
      • 如果能容纳,按照Figure2中的处理逻辑处理即可
    • 如果append失败:
      • replicas 相同的chunk上的数据就会不一致(有的成功,有的失败了),replicas相互之间按字节不一致
      • 接下来的append操作需要在更高的offset上或者下一个chunk上去append即可
Snapshot

快照操作在保证最小化干扰当前的修改操作的情况下,利用copy-on-write瞬间完成对文件或文件夹的拷贝

  • 细节:
    • Master收到快照请求,会先撤销所涉及的chunk的所有未交付的Leases
    • Master 将此操作写入磁盘日志
    • 创建一个新的快照文件,其metadata 拷贝自源文件的metadata, 源文件对应的chunk引用计数都加一
    • 如果引用计数大于1的chunk要client被修改,那么Master会推迟响应client,然后告知chunkserver拷贝当前chunk(系统所处的磁盘速度3倍于其百兆网卡
    • Master针对client的请求,对新拷贝的chunk执行Leases

容错以及诊断

高可用

保证高可用的策略: faset recovery and replication

  • Chunk
    • 主要规则:
      • 每个chunk都会在不同的chunkservers,不同的机架(racks)上进行备份
      • 用户可以指定不同namespace下的文件执行不同的备份级别
      • 备份损坏或者服务器下线后,master会再增加备份,以满足相应的备份级别
    • 未来规划:
      • 使用奇偶校验(partiy)
      • 使用纠删码(ensure codes)
  • Master
    • Master通过备份来保证可靠性(not availability,master始终是单点
    • replication:
      • 仅将operation log 和 checkpoints备份至多台机器
      • 只有operation log 被刷入磁盘,并同步至备份服务器后,mutation才被认为完成
      • 如果监测点发现Master不可用(机器宕机,磁盘挂了之类的),会将备份机启动为新的master,client通过dns规则可以快速对接到新的master上
    • shadow:(区别于备份机
      • 仅对外提供只读服务
      • 通过读取master备份机上的operation log来保持状态一致,同步master的决策(仅能保证最终一致性
      • chunk locations 也是在启东时通过询问chunkservers获取location信息,后续也会通过握手信息来监控其状态(相对Master而言频率较低)
      • shadow 上的元数据信息会落后与master
        数据完整性
  • 由chunkservers端维护自己的数据校验
    • why?
      • 通过和其他备份进行交叉校验开销太大
      • 备份直接数据并不完全一样,例如GFS允许append失败发生时,有脏数据存在,不保证字节一致
    • how?
      • chunk被分为64KB大小的blocks,每个block有32bit的校验码
      • 校验码存放在内存中,并且持久化在日志里,和用户数据分离
      • 对于来自client或者其他chunkservers的读取操作:
        • 在返回数据前进行完整性校验,以保证损坏的数据不会传播
        • 如果校验结果失败
          • 返回错误码,并向master上报,master会令请求方去其他备份读取数据
          • 同时master会从其他备份拷贝当前chunk(没有说是master让当前chunkservers去恢复,那文中提到read from another chunkserver是什么场景?)
          • 当新的合法数据就位(master并不一定把数据恢复到当前机器上,也有可能是在另外某台机器上新建了一份备份),master会下令当前chunkservers删除其备份
        • 数据校验并不会对读取性能有很大影响,因为:
          • 大部分读取只会跨越很少的blocks,需要校验的数据非常少
          • 读取一方,尽量去对齐(align)读取数据的checksum block的边界来降低chunkservers数据校验成本(对齐就优化了?意思是说每次尽量读整个block?关键每次写入也不一定写入一个完整的block?怎么生出校验码?
          • 校验码的查找和数据校验的工作并不会产生磁盘IO,所以这个动作可以和磁盘IO重叠进行
      • 校验码的计算在写入操作(append)进行的深度优化
        • 仅仅增量的去更新最后一部分的checksum block的校验码, 计算通过append新添加的新的 checksum blocks的校验码(这里的checksum block 是个什么概念?
        • 即使最后一段的checksum block 已经损坏,而且我们没有检测到;新的checksum值也不会匹配存储的数据,在block下一次被读取时就会被检测到
      • 对于已经存在的chunk进行overwrite:
        • 我们必须读取并且验证被覆盖区域的第一个和最后一个block,然后执行写入操作
        • 否则,新的checksum就会隐藏其他没有被overwriten的区域的损坏数据
      • chunkservers在空闲时间会扫描验证不活跃的chunks,以此来对鲜有读取的损坏数据进行发现,master会重建备份(通过这一点保证GFS的备份级别是准确的,而不是自以为是的
诊断工具
  • 通过广泛且详细的诊断日志,以微小的开销来来协助完不可测量(immeasurably)问题的隔离,调试,性能分析
    • 记录特定的事件(例如chunkservers 上线或者宕机)(所以,究竟由谁来记录诊断日志?猜测是所有的角色都参与
    • 记录所有的RPC请求以及回复

经验总结

业务
  • 最初设想GFS只应用与产品环境,结果后来承担了科研和开发任务。因此例如权限,配额等功能被引入了进来
实现
  • GFS是依赖与linux 磁盘驱动,因为IDE接口协议版本不匹配有可能会造成数据损坏,也正是因为这一点促使了checksums机制的使用,同时开发团队也修改了kernel来处理这种协议不匹配
  • linux 2.2 kenel中的fsync() 的开销是跟文件大小成比例的,而不是和被修改的局部大小。这影响了size较大的operation log的写性能,尤其是checkpoint实现之前。后来的解决方案是使用同步写来完成这个操作,最终迁移到了linux 2.4
  • 涉及读写锁,mmap,当磁盘线程正在page之前的映射的数据时,锁会阻塞网络线程把数据映射进内存;最终把mmap()缓冲了pread()(不是很懂)

参考

Google File System

Comments