分布式系统实现

GFS:Google File System

背景与设计目标

GFS（Google File System）是Google为解决海量数据存储问题而设计的分布式文件系统。与传统的分布式文件系统不同，GFS的设计目标紧密围绕Google的业务场景：

• 使用廉价机器：系统由大量普通PC服务器组成，硬件故障是常态而非异常
• 存储大文件：典型文件大小为数百MB到数GB，需要支持数TB的数据集
• 追加写为主：写操作几乎都是追加（append），很少有随机写；文件一旦写完，通常只顺序读
• 高吞吐优于低延迟：批处理场景对吞吐量要求高，对单次读写的延迟不敏感
• 应用协同设计：GFS提供宽松的一致性模型，将部分一致性责任交给应用层，换取更高的性能

整体架构

GFS采用单Master + 多ChunkServer的架构：

┌──────────────┐
│   GFS Master │  (元数据管理、副本管理、GC)
└──────┬───────┘
       │ heartbeat
┌──────┴──────────────────────────┐
│         ChunkServer集群          │
│  ┌─────┐  ┌─────┐  ┌─────┐     │
│  │Chunk│  │Chunk│  │Chunk│ ... │
│  │  1  │  │  2  │  │  3  │     │
│  └─────┘  └─────┘  └─────┘     │
└─────────────────────────────────┘

• 文件被切分为固定大小的Chunk（64MB），每个Chunk由Master分配一个全局唯一的64位Chunk Handle标识
• 每个Chunk默认3副本，分布在不同的ChunkServer上
• Master只存元数据（文件命名空间、文件到Chunk的映射、Chunk位置信息），所有元数据常驻内存
• Client与ChunkServer直接交互读写数据，Master只负责元数据查询，避免了Master成为数据I/O瓶颈

Master的核心职责

元数据管理

Master维护三类元数据，全部存放在内存中：

• 命名空间（Namespace）：文件和Chunk的命名空间，以及文件的访问控制信息
• 文件到Chunk的映射：每个文件由哪些Chunk组成
• Chunk位置信息：每个Chunk的副本分布在哪些ChunkServer上（这部分信息通过Heartbeat动态获取，不持久化）

操作日志（Operation Log）记录了所有元数据的变更，是元数据持久化的核心。Master会定期做Checkpoint（类似数据库的快照），减少故障恢复时需要重放的日志量。

副本管理

• 副本放置策略：跨机架放置副本，提高可用性和网络带宽利用率
• Chunk创建：选择磁盘利用率低、最近创建Chunk少的ChunkServer
• 再副本化（Re-replication）：当副本数低于阈值时，自动补足副本
• 再均衡（Rebalancing）：定期检查磁盘使用情况，迁移Chunk以平衡负载
• 垃圾回收：采用延迟删除策略，删除文件后不立即回收空间，而是定期批量清理

租约机制（Lease）

对于每个Chunk的写操作，Master会将租约（Lease）授予其中一个副本，该副本成为Primary。租约初始为60秒，Primary可以通过心跳续租。

• Primary负责确定写操作的顺序，其他副本（Secondary）按照Primary指定的顺序执行
• 如果Master与Primary失联，租约过期后Master可以将租约授予另一个副本
• 租约机制保证了在Master不直接参与数据写入的前提下，所有副本的写入顺序一致

命名空间管理与锁

Master使用读写锁管理命名空间，路径上的每个节点都有对应的锁：

• 对 /home/user/foo 的写操作，需要获取 /home、/home/user 的读锁和 /home/user/foo 的写锁
• 这种锁机制保证了同一目录下的并发创建/删除操作不会冲突，同时允许同一目录下的不同文件被并发修改

读写流程

读流程

1. Client根据文件名和字节偏移，计算出Chunk Index
2. Client向Master发送请求（文件名 + Chunk Index）
3. Master返回Chunk Handle和副本位置列表
4. Client缓存该信息，直接向最近的ChunkServer请求数据
5. ChunkServer直接返回数据

对一个大文件的顺序读，Client只需与Master交互一次即可获取所有Chunk的位置信息。

写流程（写入 / 记录追加）

控制流与数据流分离是GFS写操作的关键设计：

1. Client向Master询问Chunk的租约持有者（Primary）和其他副本位置
2. Master返回Primary和Secondary的信息，Client缓存
3. 数据流：Client将数据推送到所有副本，数据沿着一个精心选择的ChunkServer链流水线推送（每个ChunkServer收到数据后立即转发给下一个）
4. 控制流：数据沿链推送完成后，Client向Primary发送写请求
5. Primary确定写入偏移量，并要求所有Secondary按相同顺序执行
6. 所有Secondary完成后，Primary回复Client
7. 如果有副本失败，Client会重试

流水线推送的核心价值：将网络带宽最大化。一台机器将数据转发给离它最近的下一台机器，充分利用每台机器的出站带宽，而不是让Client单独发给所有机器。

原子记录追加（Atomic Record Append）

这是GFS最有特色的操作之一，专为Google的MapReduce等场景设计：

• Client只需指定要追加的数据，GFS选择偏移量，保证至少一次原子追加到文件中
• 如果追加导致Chunk超过64MB，会填充到边界，然后下一个Chunk继续
• 失败的追加会重试，因此同一数据可能出现多次，应用需要自行处理重复（例如写入checksum）
• Google的MapReduce使用Atomic Append来实现生产者-消费者之间的数据传递，非常高效

一致性模型

GFS提供宽松的一致性模型，核心定义如下：

操作	无故障	有故障（部分副本失败）
Write（非追加写）	Consistent（所有副本看到相同数据）	Inconsistent
Record Append	Defined（至少原子追加一次，数据完整）	Inconsistent（部分副本可能有多段重复）

关键点：

• Consistent：所有Client看到相同的数据，但数据可能是旧数据或部分写入的数据
• Defined：Consistent + 所有Client看到的是完整写入的数据
• GFS不保证所有副本完全一致——它只保证在不发生故障时，经过成功的写操作后，所有副本一致
• 应用通过写入checksum、记录边界等方式自己处理一致性问题

容错设计

Master的容错

• 操作日志：所有元数据变更先写日志，再修改内存状态。日志会同步到远端
• Checkpoint：定期将内存中的元数据做快照，恢复时先加载快照，再重放后续日志
• Shadow Master：提供只读的备用Master，在主Master故障时提供只读服务（不是自动切换，而是人工介入）

ChunkServer的容错

• 多副本：默认3副本，跨机架分布
• 快速恢复：ChunkServer重启后自动加入集群，Master通过心跳感知
• Checksum校验：每个Chunk的64KB块都有32位checksum，读数据时校验，防止磁盘数据静默损坏

实际表现

GFS在Google内部集群中运行了多年，支撑了MapReduce、BigTable等关键系统。在实际使用中：

• 读吞吐：多个Client并发读时，集群读吞吐可以接近网络总带宽
• 写吞吐：多个Client并发Append时，写吞吐可以达到网络带宽的60%-70%
• Master负载：Master的内存和CPU负载都不高，因为数据不走Master，元数据查询频率相对较低
• 故障恢复：ChunkServer故障后，副本恢复通常在几分钟内完成

设计取舍总结

取舍	选择	理由
一致性 vs 性能	宽松一致性	Google的应用场景（MapReduce）可以接受并处理不一致
单Master vs 分布式元数据	单Master	简化设计，元数据量小可以全部放内存
大Chunk(64MB) vs 小Chunk	大Chunk	减少Master元数据量，减少网络往返次数
中心化 vs 去中心化	中心化Master+去中心化ChunkServer	Master管元数据，数据流去中心化，兼顾简洁和性能

GFS最大的贡献不在于技术上的绝对领先，而在于它证明了针对特定业务场景定制分布式系统的巨大价值——放弃通用的POSIX语义，换来了极高的吞吐能力和简洁的架构。

BigTable：A Distributed Storage System for Structured Data

The Chubby Lock

Find a Needle in Haystack

WAS：Windows Azure Storage

Resilient Distributed Datasets

这篇是Spark

Scaling Distributed Machine Learning with the parameter Server

现在机器学习都上AllReduce

Dermel

Pregel

Spanner

分布式存储数据库，结合了GPS+原子钟，将TrueTime时间误差控制在1-7ms

Dynamo

一致性哈希算法，提升类似购物车的KV store性能

S4

类似于Strom和Flink的流计算

Storm:@Twitter

Large-Scale Cluster Management at Google with Borg

k8s的前身

F1- The Fault-Tolerant Distributed RDBMS Supporting Google’s ad Business

提出了New-SQl

Cassandra

去中心化高可用Nosql数据库

MegaSotre

跨数据中心分片方案

Dapper

SkyWalking分布式追踪框架，zipkin等追踪框架

Kafka

Amazon Azure :Design considerations for high Throughput Cloud-Native Relational Database

云环境下数据库操作范式