乐趣区

关于分布式:Google-File-System

设计

  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 无奈保障元数据永远是最新的, 但文件内容是不会过期的.

退出移动版