关于分布式:Google-File-System

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

零碎由一个 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 设置为远超常见的文件系统的 64MB, 并且只在须要是调配新的 chunk. 较大的 chunk size 对于零碎既有益处亦有害处.

长处:

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

毛病:

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

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 字节的数据保护, 并且通过拓展内存来反对更大容量非常低廉.

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

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

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 会通过校验和检测到, 并通过备份正本尽快恢复. 当所有备份都不可用时, 数据真正的失落. 但此时仍旧只会收到异样而不是未知的数据.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

关于分布式:Google-File-System

设计

架构

实现

Chunk Size

Metadata

内存限度

Chunk Locations

Operation Log

一致性模型

文件内容更新

Lease

Atomic Record Append

Master 操作

Namespace Locking

Chunk Creation

create

re-replicates

rebalance

Garbage Collection

Stale Replica Detection

Master 容错