Google File System
Master metadata
- 文件和chunk的namespace（持久化到log）
- 文件到chunk的map（持久化到log）
- chunk副本的位置location
master启动、重启时询问所有chunkserver其chunk位置，当一个chunkserver加入时也如此
replica
所有副本不保证一样，插入时插入到一个相同且确定的offset，但是数据之间可能会有空白，数据块也可能会在同一个文件有多个复制版本
部署选址条件：
- chunkservers的硬盘空间低于平均
- 每个chunkserver最近一段时间新建的chunk数量，因为有了写命令才会新建的chunk，而由于是 append-once-read-many workload，新建好后可能有大量的读traffic导致拥塞
3.副本的部署应该跨机架
副本重新复制
chunkserver挂了，其下所有chunk都需要重新复制副本
副本重新复制选址条件：
- 距离被复制目标的远近，越近越好
- 先为活着的文件复制，而不是最近删除过的文件
- 阻塞client进程的chunk优先级更高
chunkserver限制了花在复制上的带宽
master周期性平衡副本分布：
把副本往硬盘空间更充裕和负载更均衡的地方移动，
在这个过程中，master逐渐地充满新的chunkserver而不是立马塞满，那样会有heavy write traffic
Snapshot
log从最新的snapshot后开始记，新建snapshot后会换个log文件
一致性
内容一致性
consistent：不论副本在哪，所有client都能看到同样的结果。
场景：写过程中被干扰了，内容中包含多个写操作的内容。
defined：consistent 且client会看到全部写的内容。
场景：写过程中没有被干扰。（类似完美单线程情况）
inconsistent：不同的客户端看到不同的数据
场景：写失败
区分defined区域
写分为两种：
- write：在应用指定的offset写。GFS不用这种写
- record append：原子性的，至少写入一次的，在GFS选择的offset追加。offset会返回给client，标志着记录的开始位置（defined区域）。offset之前可能有padding或记录的多份复制
副本的一致性保证
- 对所有的副本以相同的顺序操作
- chunk版本号
由于client缓存了chunk的位置，它可能从过时的副本处读数据。
限制办法：
- 通过缓存失效时间限制
- 下次打开文件时，更新缓存此文件所有chunk信息
- 过期的副本经常会回复一个premature end of chunk，而不是过期的数据（过期机制保证）。当client重试并与master通信后，他会得到所有chunk位置
lease
用于同步副本的一致性，包含版本号，新选primary时才升级版本号，但是会等前一个lease 60s超时。但是只要chunk正在被mutation，primary可以向master无限申请续租。续租申请附在HeartBeat上。
有时master会在lease超时之前撤销lease，例如master想禁用对某个正被重命名文件的mutation
用lease指定primary，primary决定一系列mutation的顺序，所有secondary副本按此顺序执行mutation
写流程
- chunkserver收到client数据后，把他存到LRU buffer中
- 一旦所有的replica都ACK收到了数据，client给primary发送写请求，请求中包含了这批数据的标识符（如id）。primary给收到的mutation用连续的序列号编号，其中可能有多个client的请求。primary按序列号顺序执行请求
- primary将所有的请求转给secondary，secondary按序列号顺序执行请求
- 所有的secondary都向primary返回，表示操作成功
- primary给client回应。若中途有任何错误，则操作失败，变更过的区域处于inconsistent。client会重试失败的操作
如果一个写操作超过了chunk的边界，GFS会将其分为多个写操作
数据传输TCP以流水线的方式
耗时：
$B/T + RL$
B —— 文件含B字节；R —— R个副本；T —— 网络吞吐量；L —— 两机器间的传输延迟；
Namespace Management and Locking
通过namespace锁保证对namespace的操作都是原子性的
namespace表
key:全量路径 value:元数据
路径锁
处理 /d1/d2/.../dn/leaf
读锁：/d1，/d1/d2, /d1/d2/.../dn
写锁：/d1/d2/.../dn/leaf
顺序拿锁来避免死锁:
they are first ordered by level in the
namespace tree and lexicographically within the same level
垃圾回收
文件删除时，master日志里立即记删除操作，然后将文件重命名为包含删除时间戳的隐藏名。
当master周期性扫描namespace时，再将超过三天（参数可调）的这种隐藏文件删除，并删除其在master内存中的元数据。在此之前，这些文件可以被通过重命名还原。
通过chunk中类似的常规扫描namespace，master能判别出orphaned chunks并删除这些chunk在master内存中的元数据。
master中有保存 file-chunk 映射的表。chunk replicas在chunkserver的特定的文件夹中。其他未知的文件都被master认为是垃圾。
不立即删除的好处：
- 简单可信赖
- 把回收放在master常规批处理后台程序中，cost被分摊掉了。只会当master相对空闲时跑批
- 拖延删除更安全，相对于立即的、不可恢复的删除
过时副本检测
master维护了chunk版本号
如果master看到了一个更大的版本号，当赋lease时此chunk被认为过时的并更新版本
master把过时副本在常规垃圾回收中删除
client和chunkserver在操作时会验证版本号
容错
高可用
快速恢复
master和chunkserver挂了后会在秒级时间恢复，不区分正常和非正常关闭
chunk副本数
默认是3，参数可调
master备份
log
master的log和检查点在多个机器上备份。
对client请求的response只会在log刷盘（包括本地和远端副本）后发出
master会把几条log记录一同刷盘来增加吞吐量
检查点
master通过重做最近检查点后的log来从故障中恢复，恢复时会跳过未完成创建的检查点
当log超过一个指定大小时，master会创造检查点
检查点是一种紧凑的B树形式，可以直接映射到内存中，用于namespace查找，而无需额外的解析
创建检查点的过程中不会delay请求，在另一个线程中做
master挂了
如果机器或硬盘挂了，GFS外的基础设施会用备份的log开一个新的master进程。由于client只是用的master的名字，所以只需改DNS即可打到另一台机器
当master挂了时，假master只会提供只读的入口
由于文件具体内容是从chunkserver读入，应用不会发现过时的文件内容。在这段短时间窗口内，可能过时的有文件元数据，如目录内容或访问权限
数据完整性
checksum
每个chunk分成64KB的块，每个块有32bit的checksum，此checksum保存在内存和持久化到log中。checksum的计算结果被加在chunk的末尾。checksum只会增量地被更新，计算最后一个块，追加后再计算新的checksum。就算最后一个块挂了而不知情，新checksum也不会和存储的数据匹配，则下一次读时，此挂掉也会被检查到。
读的时候，chunkserver在回复给client或其他chunkserver之前会校验checksum，以保证错误不会传播出此chunkserver。
若校验失败，chunkserver返回error，并向master报告。master会从其他副本另外复制一份chunk，当复制完成时，master命令此chunkserver删除错误chunk。
如果一个写请求要覆盖原数据，必须校验第一个和最后一个块。
诊断工具
GFS诊断log记录了重要的事件，如新加chunkserver或chunkserver挂了，和所有的RPC请求及回应。此log被异步的写
MEASUREMENTS
读比写多