0%

论文研读之GFS

Posted on In

GFS是谷歌内部使用的一种分布式文件系统. 论文为: The Google File System

Assumption and Motivation

  • 部件错误很常见.
  • 文件非常大, GB大小的文件很常见.
  • 绝大多数的文件修改操作是append, 也支持随机写.
  • 读操作主要是顺序读取大量数据, 随机读取少量数据.
  • 为多个客户端同时对同一文件append提供高效的同步支持, 保证append的原子性.
  • 稳定的网络比低延迟更加重要.

架构

  • 一个master和很多chunkserver, 多个客户端可以并发访问, 见Figure 1. 显然存在单点故障问题.

  • 一个文件被划分为多个固定大小的部分, 称为chunk, 每个chunk都有一个chunk handle唯一标识, 是 在创建该chunk时由master分配的(由于只有一个master, 可以保证其唯一性).

  • 每个chunk会被复制多份(一般是3份), 分散到不同chunkserver, 以保证容错. 由master选择其中一 个chunk授权, 称为lease, 其余称为replica, 获得lease的chunk所在chunkserver控制了这些副 本间的同步.

  • chunk由64KB大小的块组成, 称为block, 每个block在内存中有32bit的校验码. master记录了文 件系统的所有状态, 文件名到对应chunk handle的映射, 所有chunk所在的chunkserver, 同一 chunk中的lease, 等等。有的信息保存在磁盘, 有的只保存在内存中, 加快了这些信息的返回速度, 但 是每次master重启时都需要询问chunkserver来获取这些信息(chunk所在服务器地址).

  • master定期和每个chunkserver联系, 以发送指令或获取信息. 客户端和master的交互只涉及控制信 息, 状态信息等, 而没有数据. 数据直接在chunserver和客户端间流动, 减小了master的负载。

  • 客户端不缓存数据, 但是客户端会缓存部分状态信息. 系统或其他部件实现的缓存不在讨论范围内. 在系 统中, 很容易根据服务器的ip获取最佳路径.

master的功能

  • 维护层次文件系统结构, 文件系统用前缀树来保存。
  • 维护filename-chunk映射
  • 记录每个chunk的位置
  • 管理并发数据修改操作的顺序, 采用读写锁来实现同步。注意GFS没有目录的概念。
  • lease管理
  • 检测, 处理失效chunk
    • 定期检查chunk是否有效, 无效则重复制以保证副本数量。
    • 采用lazy deletion, 客户端请求删除chunk时, 并不立即删除chunk, 只是将其标记为无效, 定时 删除这些chunk。
  • 复制chunk, 保证至少有3个副本, 或满足LB的需要, 当某个chunk成为瓶颈时, 会增加此chunk的副本数量。
  • 副本位置迁移
    • 根据访问, 迁移副本的位置, 以提高带宽。
    • 为了平衡chunkserver的数据量, 迁移副本。

chunkserver的任务

  • 保存chunk
  • 同步对chunk的写操作

操作日志(Operation Log)和checkpoint

  • checkpoint记录了某个时刻master的所有状态, master可以通过一个checkpoint恢复到那个时刻的 状态.

  • 操作日志记录了master的写操作.

  • 先载入最近的checkpoint, 再重放此checkpoint之后的所有操作日志, 即可恢复master的状态. 因 此, 采用日志先写的原则, 并将日志保存到磁盘中. master在日志达到一定大小后就建立checkpoint.

chunk lease

  • 由于每个chunk有多个副本, 因此在写chunk时, 需要考虑如何保证副本间的一致性. GFS使用了Lease 的概念, 即授予一个chunk lease, 获得lease的chunk所在的服务器协调副本的写, 称此副本为 primary. 这个想法最初是来自论文 <<Leases: An Efficient Fault-Tolerant Mechanism for Distributed File CacheConsistency.pdf>>. 详细的写入步骤在文件append中.

文件读取

下面是理想情况下的步骤:

  1. client根据文件偏移计算对应chunk号, 向master发送消息询问chunk地址, 消息包含: 文件名, chunk号.
  2. master返回：chunk handle, chunk所在服务器ip列表(因为有多个副本).
  3. client根据ip计算最近服务器, 发送消息请求数据。消息包含: chunk handle, 要读取的数据范围 (byte range).
  4. chunkserver返回数据.

之后一段时间client会缓存该chunk的地址, 再次读取chunk时不需要与master交互。

Append

下面是理想情况下的步骤:

  1. client询问要append的chunk的primary及其地址。
  2. master如果发现此chunk还没有授予lease, 就选择一个授予lease. 返回primary和其他副本 (secondary)的地址.
  3. client通过所有副本的ip地址, 计算出一条分发数据的路径, 然后推送数据. 中间收到数据的副本 所在服务器在收到部分数据后就立即向其他副本所在服务器转发. 而不是等到所有数据都受到后才转发. 收到的数据被还没有写入.
  4. 副本所在服务器收到数据后, 向client返回ack, 并包含一个id以标记此数据.
  5. client收到所有副本的ack之后, 向primary请求开始写入. 请求中必须包含此数据的id(副本返回的).
  6. primary收到写入请求, 尝试写入, 如果成功就为之赋予一个序号, 以此将所有写入序列化, 并将请求 转发到secondary. 如果失败则向client返回错误, return.
  7. secondary完成写入后, 回复primary.
  8. 当primary收到所有secondary的写入成功回复后, 即回复写入成功. 否则返回写入失败.

容错

  • 当append时, primary写入失败, 如何处理?

    此时primary chunk有错误数据, 而secondary对应区域没有数据, 关键就是保证副本间的一致性. GFS的处理简单粗暴, 放弃这个区域, 重新选择一个区域append.

  • 那么又有问题了, 再之后顺序读取中, 如何识别区域是无效的呢?

    好像文章里没有说, 不过实现起来应该很简单. 因为有检验码, 或者有其他标志.

  • 如果primary成功, 某些secondary失败呢?

    参照上面的方法处理.

  • 在chunkserver向客户端或其他chunkserver返回数据时, 都会检查每个chunk的校验码, 防止错误数 据扩散.

  • master的状态会复制到多个机器上, 这些机器作为备份。操作日志会保证先写到这些备份机器上再在 master执行. master重启速度非常快, 并且从各个chunkserver获取chunk位置的速度也很快.

快照(Snapshot)

复制一个文件/目录, 采用copy-on-write策略. 因此每个文件有一个引用计数, 当修改引用计数超过1的 文件时, 需要将其复制一份才能修改.