System|分布式|GFS

gfs被称为谷歌的三驾马车之一，主要面向谷歌的大流量流式读取和append写，通过控制流与数据流解耦提升并发能力。

GFS架构

GFS核心在于，master只告诉你地址，不给你数据，要取数据？自己去问chunkserver。至于chunksever给不给，master说了算。

GFS架构

GFS的本质就是将数据流和控制流解耦，master只负责控制流，提供metadata，chunkserver只负责数据流，提供data。

Performance can be improved by scheduling expensive data flow based on the network topology。在数据推送过程中，可以选择最近的chunkserver，而不需要在意推送顺序。推送顺序由同步保证

就是这么设计，master只提供url，但是client允许直接访问数据而没有加入校验的控制流，所以也不是很完善，而且返回url本身开销也很大(once per request)，增加控制流开销，也算是trade-off了。

相比之下，gfs增加了master对数据的控制流，并且数据流远远大于控制流，在这种workload下控制流和数据流分离就是绝佳的设计了。此时虽然client上控制流和数据流仍然耦合，但是因为他只是边缘端的，根本没有多少流量，所以也不会有什么性能瓶颈。

Single Master

存储文件系统的metadata于内存中

• Namespace
• Access Control Information
• Mapping from files to chunks
• Current locations of chunks

namespace和mapping同时通过operation log持久化，location则通过chunkserver的心跳来获得，决定系统的访问权限。

这里的namespace并非inode文件系统，没有symlink也没有hardlink，路径名并非真正的目录，通过前缀压缩性能优化。（猜测数据结构为Trie，单词查找树，是哈希树的变种）每个节点都有一把读写锁。

master虽然有全局了解，简化设计，但不是bottleneck(后来的改进证明谷歌还是乐观了）

• client从不读写master，只请求通信的chunkserver地址
• master可以提供后续chunk的额外信息，从而减少延迟
• 这些后续的chunk的读并不需要访问master

master的状态通过log和checkpoint备份，宕机时启动备份并且修改DNS从而得到primary。

这些备份的"shadow"master提供只读权限，但不要求强一致性从而避免性能开销，允许延后根据日志来进行同步。因此master在恢复的时候也允许进行读取，提供fault tolerance。

Multiple Chunkservers

存储文件系统的data于内存中，每个chunk大小固定64MB。

数据冗余采用3-way mirror，分散在不同机器、不同rack，防止同时崩溃。

通过心跳信息与master通信，由master决定访问权限，但是chunk是否存在则由chunkserver自己决定而非master。

存在primary/backup，由primary决定写入顺序保证同步并减轻master负担，primary通过抢锁获得，抢到锁的成为primary，但是需要定期续约，否则会自动释放（primary崩溃）。

读操作

• 应用向client发出读请求read(filename, byte range)
• client翻译为read(filename, chunk index) 并请求master
• master响应chunk handle并告诉所有replicas的地址
• client选择一个replicas并请求read (chunk handle, byte range)
• chunk根据访问权限，决定是否返回请求的数据
• client将数据返回给用户

如果选择replicas检测到checksum不正确，则会返回错误并要求client重试其他replicas，并向master请求同步其他replicas。

checksum具体实现复制 https://www.cnblogs.com/lushilin/p/8665178.html

• 读操作的Checksum：只取Chunk小部分额外相关数据进行校验，客户端每次把读取操作对齐在Chunk块的边界上

写操作

• 应用向client发出写请求write(filename,data)
• client翻译为write(filename, chunk index) 并请求master
• master响应chunk handle并告诉所有primary/backup replicas的地址
• client对所有replicas请求write(chunk handle, byte range, data)或单纯append(chunk handle , data)
• client请求primary 进行同步，进行持久化
• primary决定buffer数据写的顺序，并写入chunk
• primary把顺序告诉所有的backup要求他们以同样顺序执行
• primary等待所有backup响应
• primary返回响应给client，如果任意backup失败，client重试同步。

checksum具体实现复制 https://www.cnblogs.com/lushilin/p/8665178.html

• 记录追加操作的Checksum（高度优化）：只增量更新最后一个不完整Chunk块的Checksum
• 写操作的Checksum：先读取和校验被写操作覆盖的第一个和最后一个Chunk块，写操作完成后再重新计算和写入Chunksum

云时代的改进

对于Master采取数据切分，进一步提高并发能力

对于Chunk使用1.5倍的冗余编码Reed-Solomon减少冗余备份，提供纠错机制

Problem: 提供大规模文件的分布式存储

Related work: 组件故障是常态,规模不够大,没有append专门优化，应用API没有共同设计

Observation: 控制流数据流分离 + 先推送数据再执行同步

Solution: Master只寻址chunk,Primary只需要顺序同步不需要数据同步。

Evaluation: 单Master掌握全局,高度中心化

Comments: 如果每个区域都需要本地化的GFS,那么Master放哪里呢？如果全球通用GFS,那么如何保证时延平衡呢？