SOSP'03-The Google File System

[CookiePieWw]

https://storage.googleapis.com/gweb-research2023-media/pubtools/4446.pdf

[CookiePieWw]

GFS

为面向大规模分布式数据密集型应用设计和实现的可扩展的分布式文件系统，在大量的廉价商用硬件机器上运行并提供容错机制和聚合性能。

[CookiePieWw]

Introduction

Different Points in The Design Space

First, component failures are the norm rather than the exception.

Second, files are huge by traditional standards. Multi-GB files are common.

Third, most files are mutated by appending new data rather than overwriting existing data.

Fourth, co-designing the applications and the file system API benefits the overall system by increasing our flexibility.

[CookiePieWw]

Design Overview

Assumptions

1. 在廉价商用硬件机器上运行，因此组件失效是常见的。为此需要设计对组件的监控、探测和快速的自动恢复。
2. 存储大文件。单个文件的大小通常在 100 MB 以上，包括 GB 级别的文件。支持存储小文件，但不会单独优化。
3. 主要支持大量的顺序读取和少量的随机读取。顺序读取通常在 1 MB 以上，随机读取通常在 KB 级别。关注性能的应用通常会按批读取数据而非进行大量随机读取，以获取更好的性能表现。
4. 主要支持顺序写入，向文件末尾添加数据。写入的大小和读取相仿。极少进行修改，支持随机写入但效率不高。
5. 对并行的 append 需要有良定义的语义。
6. 倾向于更高的带宽而不是更低的延迟。（面向批处理系统）

Interfaces

POSIX 标准的文件接口 + snapshot + record append

Architecture

A GFS cluster consists of a single master and multiple chunkservers and is accessed by multiple clients.

Files are divided into fixed-size chunks. For reliability, each chunkis replicated on multiple chunkservers.

The master maintains all file system metadata. It also controls system-wide activities.

GFS client code linked into each application implements the file system API.

Neither the client nor the chunkserver caches file data.

Single Master

Having a single master vastly simplifies our design and enables the master to make sophisticated chunk placement and replication decisions using global knowledge.
we must minimize its involvement in reads and writes so that it does not become a bottleneck.

Master 上的信息不太多，Client 会 batch 和 cache 请求，相对简单。可能需要解决单点失效的问题。

Chunk Size

默认 64 MB。大 chunk size 减少 metadata ，减少 client 和 master 的交互次数，减少 client 和 chunkserver 的连接数量。但是：

The chunkservers storing those chunks may become hot spots if many clients are accessing the same file.

Metadata

The master stores three major types of metadata: the file and chunknamespaces, the mapping from files to chunks, and the locations of each chunk’s replicas.

前两者写 log 以做持久化，重新启动后重放。后者通过 lease 来保证一致性，通过和 chunk sever 的 HeartBeat 来更新。

In-Memory Data Structures

所有 metadata 全部在内存中，好处在于快，坏处在于 master 的内存大小限制了 gfs 的容量。解决办法：加内存。

Chunk Locations

通过 HeartBeat 来更新。

This eliminated the problem of keeping the master and chunkservers in sync.

a chunkserver has the final word over what chunks it does or does not have on its own disks.

Operation Log

The checkpoint is in a compact B-tree like form that can be directly mapped into memory and used for namespace lookup without extra parsing.

Consistency Model

Guarantees by GFS

元数据的修改是 atomic 的。

A file region is consistent if all clients will always see the same data, regardless of which replicas they read from. A region is defined after a file data mutation if it is consistent and clients will see what the mutation writes in its entirety.

	Write	Record Append
Serial success	defined	defined or inconsistent
Concurrent successes	consistent but undefined	defined or inconsistent

看起来就是没什么并发控制，不太喜欢并发写。不过这个 Serial 的 Record Append 还会 inconsistent 是不是太过分了点。

Implications for Applications

这里建议应用自己写校验码、标识重复项来避免读到错误的数据。其实就是 GFS 对并行的写不太提供什么一致性，所以应用得自己维护。

[CookiePieWw]

System Interactions

Leases and Mutation Order

修改应用于所有 replica。其中一个 primary replica 会持有一个来自 master 的 lease，其余所有 replica 跟随 primary replica。

写入时：

1. client 向 master 询问持有 lease 的 primary replica 和其他 replica；
2. master 回应；
3. client 向所有 replica 推数据；
4. 所有 replica 得到数据之后，client 向 primary replica 发写入请求；
5. primary replica forward 写入请求到其他 replica；
6. 所有 replica 写完；
7. primary replica 返回写入成功到 client。

Data Flow

数据流和控制流分开，可以充分利用带宽。

Atomic Record Appends

相较于 write，Record Append 提供了更好的一致性保证（虽然可能不一致，但 at least append once），以及不用自己 manage offset。

Snapshot

cow copy。通过 lease 和 rc 做 cow。

[CookiePieWw]

Master Operations

The master executes all namespace operations.

it makes placement decisions, creates new chunks and hence replicas, and coordinates various system-wide activities to keep chunks fully replicated, to balance load across all the chunkservers, and to reclaim unused storage.

Namespace Management and Locking

GFS 提供目录层级的锁，如 /a/b/c 的修改操作需要获取 /a,/a/b,/a/b/c 的锁。

Replica Placement

Creation, Re-replication, Rebalancing

一些细节讨论，感觉可以略过。

Garbage Collection

Mechanism

lazy deletion，先软删除，然后删除元数据，最后通过 heartbeat 通知 chunkserver 删除 chunk。

Discussion

First, it is simple and reliable in a large-scale distributed system where component failures are common.
Second, it merges storage reclamation into the regular background activities of the master. Moreover, it is done only when the master is relatively free.
Third, the delay in reclaiming storage provides a safety net against accidental, irreversible deletion.

In our experience, the main disadvantage is that the delay sometimes hinders user effort to fine tune usage when storage is tight.

Stale Replica Detection

chunk replica 带 version number，stale 的会被 gc。

[CookiePieWw]

Fault tolerance and diagnosis

High Availabilit

Fast Recovery

Chunk Replication

多副本。提到可以让 gfs 自己做奇偶校验，类似 raid。

Master Replication

master 的 log 是有副本的。master 寄掉之后外部监控系统可以重启一个。

其实 master 有只读副本来着，不算完全的 single master。

Data Integrity

chunkserver 对 chunk 自带校验和。

Diagnostic Tools

日志相关。

[CookiePieWw]

Measurements

We measured performance on a GFS cluster consisting of one master, two master replicas, 16 chunkservers, and 16 clients.
All the machines are configured with dual 1.4 GHz PIII processors, 2 GB of memory, two 80 GB 5400 rpm disks, and a 100 Mbps full-duplex Ethernet connection to an HP 2524 switch.

Micro-benchmarks

读

Each client reads a randomly selected 4 MB region from a 320 GB file set. This is repeated 256 times so that each client ends up reading 1 GB of data. The chunkservers taken together have only 32 GB of memory, so we expect at most a 10% hit rate in the Linux buffer cache.

想知道这个 10% hit rate 怎么算出来的。

The observed read rate is 10 MB/s, or 80% of the per-client limit, when just one client is reading. The aggregate read rate reaches 94 MB/s, about 75% of the 125 MB/s link limit, for 16 readers, or 6 MB/s per client.

The efficiency drops from 80% to 75% because as the number of readers increases, so does the probability that multiple readers simultaneously read from the same chunkserver.

效率 75%-80%，随 client 增多，多个 client 从一个 chunkserver 读的概率增大，所以效率会略下滑。

写

N clients write simultaneously to N distinct files. Each client writes 1 GB of data to a new file in a series of 1 MB writes.

The write rate for one client is 6.3 MB/s, about half of the limit. The main culprit for this is our networkstack.

Aggregate write rate reaches 35 MB/s for 16 clients (or 2.2 MB/s per client), about half the theoretical limit.

写的碰撞会更严重。

In practice this has not been a major problem because even though it increases the latencies as seen by individual clients, it does not significantly affect the aggregate write bandwidth delivered by the system to a large number of clients.

Record Append

N clients append simultaneously to a single file.

It starts at 6.0 MB/s for one client and drops to 4.8 MB/s for 16 clients, mostly due to congestion and variances in networktransfer rates seen by different clients.

效率低于 50%。实际应用中每个 client 会同时 append 多个文件，因此在某个文件 stall 的时候可以 append 其他文件，不会损失速度。