设计

  1. 零碎由大量便宜机器组成, 组件生效属于常见景象, 须要监测运行状况, 容错以及复原.
  2. 文件绝大多数超100MB, GB级别常见且是次要优化对象. 反对小文件, 但不保障高效率.
  3. 读操作包含流式读取(streaming reads)以及随机读取(random reads). 流式读取每次读取上百KB至1MB内容, 而随机读取往往只波及几KB且不保障高效率.
  4. 写操作包含追加写以及随机写. 追加写下一旦写入, 很少批改. 对随机写不保障高效率.
  5. 相较于低提早更偏向于继续高带宽.

架构

零碎由一个master以及多个chunkserver形成. 一个文件被切分成多个大小固定的chunk(默认64MB)并将多个备份(默认3个)存储在不同的chunkserver上.

master存储文件系统的metadata, 包含namespace, access control information, mapping from file to chunks, current locations of chunks.

master周期性的与chunkserver通过心跳包下达指令并监测状态.

client与master通信取得文件的metadata并缓存后与chunkserver间接通信进行读写.

实现

Chunk Size

chunk size设置为远超常见的文件系统的64MB, 并且只在须要是调配新的chunk. 较大的chunk size对于零碎既有益处亦有害处.

长处:

  1. 缩小多chunk读写时与master的交互次数.
  2. 操作在单个chunk上更加集中, 缩小了TCP连贯的网络开销.
  3. 缩小了存储在master上的metadata, 使得master上的元数据能够维持在内存中.

毛病:

  1. 由一个chunk组成的小文件可能会呈现hot spot. 但零碎内文件往往由多个chunk组成.

Metadata

master将三类metadata维持在内存中, 包含namespace, access control information, mapping from file to chunks, current locations of chunks.

namespace以及access control information通过operation log长久化存储在master的本地磁盘上并在远端备份.

current locations of chunks在master启动时以及新chunkserver退出时被动询问.

内存限度

metadata被严格限度全副维持在内存中, 缩小了master操作的工夫, 但内存大小限度了GFS存储数据的大小.

实际上对metadata的存储做了很多压缩, 64MB的chunk能够通过小于64字节的数据保护, 并且通过拓展内存来反对更大容量非常低廉.

Chunk Locations

master启动时, 以及有新的chunkserver退出时, master会被动询问并存储chunk location.

因为master管制chunk的置放并且通过心跳包监测, 能够维持chunk locations信息处在最新态.

Operation Log

operation log记录了metadata的更新, 并且作为逻辑工夫线定义并发操作的程序. 文件, chunk以及其版本号通过创立时的逻辑工夫对立治理.

operation log自身须要牢靠存储, 并且在metadata的更新长久化前保障对客户端的不可见. 否则master的宕机可能会导致文件或操作的失落.

因而operation log被存储在多个机器上, 并且只在本地以及远端记录胜利后才会回应client的操作.

master宕机时通过重做operation log重启, 为了保障重启的速度, 当operation log达到肯定的大小时须要对master的状态做checkpoint, 重启只需重做operation log中逻辑工夫线在最近checkpoint创立时之后的.

当checkpoint创立时失败, 只需从上次checkpoint处复原, 尽管可能会减少复原工夫, 但仍旧能保障可靠性.

一致性模型

namespace的更新由master保障原子性, 并且由operation log提供可靠性.

consistent: client在所有的正本中看到的数据是雷同的.

defined: client写入的数据可能残缺的被看到.

对于record append, 保障appended atomically at least once. GFS可能会在多个defined region之间插入padding以及record duplicates导致inconsistent. 但GFS可能监测到这部分数据并治理, 最终对client是不可见的.

并发更新操作在operation log里取得逻辑程序并执行, 并通过chunk version检测chunk的数据是否落后, 落后的数据不再参加更新操作并且master不会返回其chunk location, 它期待下一次的垃圾回收.

因为client会缓存metadata, 那么就有可能间接拜访蕴含落后数据的chunk. 过期工夫以及关上文件会导致client从新向master申请metadata. 另外, 当操作为append时, 落后的chunk会返回异样的文件结尾, 导致client从新向master申请metadata.

为了解决组件生效带来的存储数据失败, GFS会通过校验和检测到, 并通过备份正本尽快恢复. 当所有备份都不可用时, 数据真正的失落. 但此时仍旧只会收到异样而不是未知的数据.

文件内容更新

Lease

为了保证数据的一致性, 更新操作须要在所有的正本中以雷同的程序执行. 为了缩小master的负载, master将chunk的某个正本指认为primary, 并具备肯定的过期工夫, 所有的更新操作由primary对立治理. client的更新申请间接交付给primary replica.

另外, 在跨chunk写时, 操作会被切分, 导致会呈现写笼罩的状况, 但仍能保障consistent.

Atomic Record Append

流程与写入流程相似, 但为了保障原子性, primary在写入时查看chunk残余容量是否能包容此次操作的数据. 如果不能, primary以及secondaries将会填充直到chunk满, 并告诉client重试操作. 这样操作就会落到下次申请时创立的新chunk内了.

Master操作

Namespace Locking

master对namespace的治理不采纳前缀式的数据结构治理(相似字典树), 但采纳前缀压缩算法节俭空间, 同时每个结点也含有一个读写锁.

当须要对namespace进行更新时, 由根目录开始一直获取读锁直到指标门路的上一级, 再获取指标门路的写锁. 为了防止获取锁时死锁, 获取锁的程序必须严格依照namespace档次进行.

Chunk Creation

create

master创立chunk时, 根据以下准则抉择chunkserver

  1. 低硬盘使用率.
  2. 限度某个chunkserver近期创立操作的数量, 以均摊行将到来的写操作.
  3. 尽量将多个正本散布在不同的机架上.

re-replicates

当可用备份数量小于指标数量时, 须要re-replicate, 当多个chunk须要re-replicate时, 依据以下因素排序

  1. 间隔指标数量的差距
  2. 优先复制沉闷文件的备份, 而不是近期被删除的文件
  3. 为了最小化生效的 Chunk 对正在运行的应用程序的影响, 会阻塞客户机程序处理流程的 Chunk 优先在

在复制时, 对抉择哪个正本进行复制时, 根据以下因素抉择

  1. 均衡硬盘使用率
  2. 限度某个chunkserver正在进行的复制操作的数量
  3. 尽量将多个正本散布在不同的机架上.

rebalance

master周期性地对正本进行负载平衡, 它查看以后的正本散布状况, 而后挪动正本以便更好的利用硬盘空间, 更无效的进行负载平衡.

master移走那些残余空间低于平均值的chunkserver上的正本, 从而均衡零碎整体的硬盘使用率.

Garbage Collection

GFS 在文件删除后不会立即回收物理空间, 只在文件和 Chunk 级的惯例垃圾收集时进行.

当文件被应用程序删除时, master首先记录到operation log中, 后将文件名改为蕴含删除工夫的暗藏名. 当master对namespace惯例扫描时, 主动删除肯定天数前的暗藏文件的元数据. 因而在删除元数据前, 能够通过重命名的形式撤销删除.

另外在惯例扫描中, master会删除不被任何文件援用的chunk的元数据, 并在心跳信息中告知chunkserver哪些属于它的chunk元数据曾经不存在了, chunkserver可自行删除.

垃圾回收相较于间接删除有如下几个劣势:

  1. 垃圾回收在组件生效的状况下跟简略牢靠.
  2. 垃圾回收工作由master周期性的对立执行, 开销扩散.
  3. 为意外删除提供平安保障

垃圾回收的次要问题是会导致用户调优存储空间的利用率. 反复创立和删除临时文件将导致大量的存储空间无奈立刻重用. 能够通过显示的再次删除以减速工夫, 或者对namespace采纳不同的复制和回收策略.

Stale Replica Detection

在master签订租约, chunk复制时都会附带chunk的版本号. client和chunkserver会在操作时验证版本号以保障拜访的chunk数据是最新的.

Master容错

当master过程生效后, 能够根据operation log以及checkpoint疾速重启.

当master所在机器宕机后, 因为operation log是多机器备份的, 因而能够在其余机器上重新启动master过程.

另外还存在shadow master, 他们在master机器宕机后提供文件系统的只读拜访. 在master失常运行时, 他们和master以及chunkserver通信以更新元数据. shadow master无奈保障元数据永远是最新的, 但文件内容是不会过期的.