光与影的个人博客

NEUCoder

0%

GFS论文总结

发表于 更新于 分类于 ，

GFS

论文地址：The Google File System

google file system，入门大数据必读三篇文章之一，最近懒得看视频，小研究一波这篇论文，读完发现这种系统论文要比人工智能论文难读一些，涉及的技术比较多，粗浅的总结一下。

论文结构

论文结构有点像我的毕业论文，首先从系统的结构出发，描述系统架构、组成等,从静态角度了解系统组成，然后从动态系统交互出发，描述系统交互，主要数据和操作流，最后单独两章描述mater节点的主要职责以及系统如何实现fault tolerance.

  1. intro 介绍

    没讲很多背景，直接讲GFS这套解决方案与以往的GFS不同点，解决不同问题：

    1. 分布式系统中组件经常失效（norm rather than exception）
    2. 按照以往的标准，目前文件大小都很大
    3. 目前对文件操作主要是添加和顺序读
    4. 面向应用设计GFS，增加了整个系统的灵活性

  2. DESIGN OVERVIEW

    系统的组成+一致性模型，基本讲明白了系统怎么实现的文件系统功能

  3. SYSTEM INTERACTIONS

    描述了系统与client读写文件的交互流程，在这过程中如何保证GFS特性（从使用的角度，描述系统）

  4. MASTER OPERATION

    阐述master节点的职责，client与GFS交互中不直接相关的操作（从管理的角度）

  5. FAULT TOLERANCE AND DIAGNOSIS

    阐述容错机制（从策略角度）

  6. MEASUREMENTS + EXPERIENCES + RELATED WORK + CONCLUSIONS

    实验验证+经验总结+相关工作+总结

前提假设

论文中说了GFS的设计是文件系统API和服务于应用的co-designing（需求来源于生活）， 对其解决的问题做了一定的假设和限定：

  1. 分布式系统构建于便宜、容易出错的硬件上
  2. 系统存储一定数量的大文件（GB级别）
  3. 系统将要面临的读操作主要为大量的顺序读和少量随机读
  4. 系统面临的写操作主要为大量顺序添加操作，但也支持随机写
  5. 系统必须高效支持多客户端并发append写操作
  6. 重要性：高带宽>低延时

从前提假设中，我们就能得到GFS设计目标中的重点

  1. 重点：为多客户端的大文件存储以及顺序读+追加写提供高稳定高带宽服务
  2. 相对而言不重要的（系统支持，但不一定效率高）：随机读+随机写+低延时

系统架构

单管理节点（master）+多存储节点（chunk server）+多客户端（client）架构

  1. master节点职责
    • 管理文件系统的元数据，包括访问控制信息，文件命名空间，文件到存储块的映射，存储块到存储节点的映射
    • 进行系统管理活动，包括存储块释放，垃圾回收，不同存储节点上存储块的迁移、复制，定时获取chunk server状态
  2. chunk server节点职责
    • 存储文件存储块（chunk）
    • 通过HeartBeat消息，告知master节点自身状态
    • 与client进行文件操作交互
  3. client主要操作
    • 与master节点进行元数据操作（获取文件存储的chunkserver等）
    • 与chunk server进行文件操作（文件实际读写）

几个主要概念

Metadata

The master stores three major types of metadata: the file and chunk namespaces, the mapping from files to chunks, and the locations of each chunk’s replicas

文件系统的元数据，存储在master节点的内存中（论文里不断强调这一点，为了方便master扫描，执行一些列管理操作，主要包括三种类型

  1. 文件和文件块的命名空间信息（前缀压缩减少空间占用）
  2. 文件到文件块的映射
  3. 文件块的存储位置
    • master节点在每次启动时，向chunk server请求其拥有的chunk信息，初始化文件块存储位置信息
    • 并通过不断的Heatbeat Message 保证chunk信息不过时。（某种程度的低耦合）
  4. operation Log 操作记录
Operation Log

记录系统操作、作为系统逻辑时间的最重要的元数据

  • operation log持久存储，多处备份，每次操作只有真正的记录到Operation Log中时，才会对客户端可见
  • operation log大小超过一定程度时，系统创建checkpoint，将当前operation log存储到本地
  • 以compact B-tree的形式存储checkpoint，方便快速读取和加载
  • checkpoint的创建与切换新 operation log file并行进行
atomically at least once

追加写操作保证”原子性“，我理解的是：真实追加写入的offset相较于client发出请求offset不一定一致，但是我保证所有副本最后在追加的offeset一定相同，并将这个offset返回给客户端。

举个例子，例如向A,B,C三个chunk server的同一文件的副本追加文件，A，B写入成功，C写入失败，GFS并不会单独重新在C上追加，而是在C上补充空白（insert padding or record duplicates in between.），使得三个文件的偏移量相同，重新写入ABC。

这样做会导致文件中出现无效数据，但是论文中说这些数据和用户数据相比微不足道（are typically dwarfed by the amount of user data）

一致性模型中的consistent 和 defined

两者定义

  • consistent 指所有的client看到相同的数据，即所有副本均相同

  • defined 指看到自己操作对于数据的改变 = 期望中的改变

成功和失败的操作定义为：

  • 成功：可能会导致操作后undefined(无法预期操作的结果)，但数据仍为consistent
  • 失败：导致unconsistent，即不同数据备份不一致
Leases and Mutation Order

lease用来记录对于一份文件多个并发操作的执行顺序，由master节点选取其中chunk server一个作为primary lease决定执行顺序，所有文件副本均按照primary lease操作顺序执行

  • 每个lease 60秒失效
  • 在与master节点的Heartbeat中primary的授权信息（These extension requests and grants are piggybacked on the HeartBeat messages regularly exchanged between the master and all chunk server）

系统交互

以写流程流程为例，涉及client、Master、Chunk server之间的交互

  1. Client 向 Master请求写入文件的Chunk Server地址（包括备份的Chunk Server）
  2. Master 返回给Client请求的Chunk Server地址，Client拿到地址后，将写入文件发送到所有目标Chunk Server中（不是分发，而是链式传输，论文中称“decoupling the data flow from the control flow”，提高了系统performance）
  3. 所有接收文件的Chunk Server确认接收完成后，client向被选为primary lease的Chunk Server发送写请求，由改Chunk Server确定包括该请求在内的其他并发请求的执行顺序，通知其他Replica Chunk Server，包括自在内按照该顺序执行操作（forwards the write request to all secondary replicas）
  4. Replica Chunk Server向Primary Chunk Server返回执行完成确认，Primary Chunk Server向Client返回执行完成确认。

一旦其中有一步失败，即向Client汇报失败，由Client自己进行处理（重试操作）

几个主要操作（策略）

Data Flow-数据传输

在Client向多个备份Chunk Server传输文件时，并不是采取传统的一个Client对多个Server的集中发送的方式，而是采取链式传输

  1. Client首先选取最近(IP地址上的近)的Chunk Server传输文件
  2. 该Chunk Server再选取离他最近的未传输过文件的ChunkServer传输文件
  3. 重复传输，直到所有待传输Chunk Server获得文件
Atomic Record Appends

传统基于offset的写入，同一个区域的并发写入操作是无法序列化的（需要严格同步机制），针对record append操作，GFS舍弃了由应用输入offset的机制，应用只需要写入数据，由GFS写入后，向应用返回offset，其中一致性保证 atomically at least once

  • 若添加的文件使得chunk大小超出了最大限制，Primary Chunk Server会在填充当前Chunk剩余空间，创建新Chunk存储添加的文件内容
  • GFS限制写入文件大小小于Chunk块大小的四分之一，避免padding导致的碎片问题过于严重
Namespace Management and Locking

说实话没理解并不是很深刻， GFS为系统中的每个路径前缀均设置了读写锁

  1. 读操作需要获取叶子节点所有前缀read-lock

  2. 写操作只需要叶子节点路径write-lock(因为目录并不是实际的数据结构，不需要修改目录，只需修改文件)

Snapshot

系统快照，快速保存文件系统状态，其主要步骤为

  1. master首先撤下快照涉及文件的primary lease(避免在快照过程中文件上发生操作)
  2. master将log record 操作记录存储到磁盘中
  3. 快照完成后，master接收到来自client对快照文件访问的新请求（通过操作记录数大小判断）时，延迟返回结果，创建一个与原Chunk相同的新Chunk供Client访问（懒备份）

这一过程对于Cilent来说是无感的

Garbage Collection

当删除一个文件时，GFS并直接回收文件占用资源，而是将文件名修改为hidden状态，待日后删除，基本流程

  1. 删除文件，master结点记录删除操作，在chunk中将文件修改为hidden状态
  2. master扫描到hidden状态文件，删除meta数据中关于hidden文件信息
  3. chunk server与master 的Heatbeat message交换中，发现master已没有了这部分信息，chunk server回收空间

同样通过Garbage Collection回收stale Replica

Data Integrity

checksum+chunk version number机制保证数据正确性和及时性（up-to-date）

  1. 每次读操作时，cunkserver验证本机数据check sum是否正确，不正确返回失败
  2. 为每个副本维护一个版本号，操作递增，当版本号不同时，由master在Garbage Collection回收过期副本

总结

按照自己的理解对GFS论文简单的理解了一下，感觉有些东西理解的还不是很透彻，慢慢深入了解