论文笔记 [SOSP '03] The Google File System

google file system， 谷歌经典论文之一。GFS通过single master，Garbage Collection，control path 与data path分离等机制，很好的在便宜机器上实现了Availability, recoverability, High throughput。但是GFS针对的是特定的workloads（写一次，读多次，大批量的读等），并且需要appication支持, 以避免不一致数据的情况。

Assumptions

既然是google file system，当然是针对google的应用场景做的优化。这篇发在03年的sosp，现在workloads已经变了很多了，gfs已经有了第二代Colossus，不过没paper出来。

• 便宜的设备，会经常损坏(fault tolerate)
• 大量的大文件，基本都在100MB以上或者更大，GB级别的文件是很常见的
• read workloads: Mostly large streaming reads（1MB or more）和Some sorted random reads(a few KB)。
• write workloads: many large，sequential write。append居多。写一次，读多次。
• 多用户并发向同一个文件进行append操作
• google的大都是高速批量写入的应用，所以它更要求持久稳定的带宽。

Architecture

GFS是一个single master，multiple chunkserver的架构。 比较有意思的是GFS将control path 和data path做了分离。所有的control path从master走，data path由client直接与chunkserver通信。

master存metadata，比如namespace，控制权限等。这些信息都是存在内存里的，用WAL保证持久。WAL会有副本（replication state machine），防止master挂掉导致不可用。这里注意的是，尽管所有chunk的metadata都存在master内存中，但这并不会成为一个瓶颈。因为数据量非常小，每个文件64bytes（利用前缀压缩）。

master和chunkserver直接通过heartbeat（心跳包）通信来监测chunk 的位置等信息。

chunk

每一个文件被分成了多个固定大小的chunk（64MB）。chunk就是直接存在chunkserver上的，就是一个单个机器上就是一个普通的文件存在ext4或别的文件系统。chunk会存在多个副本在不同的chunkserver上。需要注意的是chunk比 linux 上普通的block要大很多，这是基于google应用场景做的优化（large streaming read）。这么做存在一些优缺点。

• advantages
  • 减少了client和master通信的次数。因为同一个chunk，client只需要最开始的时候向mater要一下location即可。
  • 减少网络通信。
  • 减少master需要管理的metadata。
• disadvantages
  • 当文件很小时，单个chunk就是一个文件。假如这个文件是热点数据。同时几百个client同时请求同一个chunk，chunkserver会过载。这种情况可以通过调整chunk副本数量来做负载均衡。或者让client从别的client那里读chunk（减少chunkserver压力）。

Consistency Model

首先gfs提出了几个名词来表示consistency。

• consistent: 所有client都看到相同的数据，无所是从哪个副本读的。
• defined: 当发出一个mutation后，所有client都能看到这个mutation修改后的数据。
• consistent but undefined: 所有client都看到相同的数据，但并不反映任何一个mutation修改后的结果。（多个client并发操作）

如下图。

metadata修改都是原子的，master内部会用锁和全局有序的log来保证这个。这也是single master的好处。

data修改的顺序是由primary server定的。串行写可以保证所有副本的defined。但是多个client并发写，数据就会出现被覆盖等情况，即consistent but undefined。这是write的情况，即由用户指定offset的情况。

而GFS的大部分的wrokload都是append模式的。这种情况下，gfs可以保证原子性的completes at least once（通过失败之后重复请求等方式）。但还是会有重复的record或者padding这种情况，这需要application自己来检测（chunksum，unique id）。

Implemention

系统的实现目标是尽可能的减少与master的交互。master会选择一个副本作为primary，同时授予primary 一个60s的lease。在lease有效期内，由primary来决定每个副本mutation的顺序。lease是可以被master 收回或者延长的（heartbeat更新lease）。

Mutation

下图是mutation的顺序图。

1. client询问master，chunk的location。master会选择一个副本作为primary（授予lease，如果没有的话）
2. master返回副本的location和primary信息。client会缓存这些信息。直到lease过期，或者副本挂掉。
3. client将data push到所有副本（任意order，这里可以利用网络结构做优化，pipelining）。
4. 当所有副本收到data之后，client发送写请求给primary。primary会选择一个串行的顺序，并按顺序修改本地data
5. primary转发写请求到所有副本，另外的副本按同样的顺序修改。
6. 副本返回给primary，表明写入完成
7. primary回复client。若有错误，client进行重试（3-7）

Snapshot

snapshot操作就是快速copy 一份文件或者目录，并减少对正在进行中的mutation的干扰。GFS利用copy-on-write的方式。当master收到snapshot请求之后，master会立即收回所有相关chunk的lease。

1. snapshout 某一个文件
2. master回收所有相关chunk的lease（保证后续写操作会和master交互）
3. log snapshot操作
4. copy一份这个文件的metadata，指向相同的chunk
5. 延迟到client发起写相关文件的chunk时，master会让chunkserver创建一个新的chunk，并修改metadata指向新的chunk，并授予lease，返回给client。

Garbage Collection

当一个文件被删除时，并不会立即删除。master先log 删除操作，然后将这个file修改成特殊的名字(比如.xxx)隐藏起来。在进行垃圾回收的时候才删除那些已经存在了3天以上的隐藏文件（天数是可配置的）。然后通过和chunkserver进行heartbeat通信，将这个信息告诉chunkserver，让chunkserver进行物理删除data。

也就是只要是master所不知道的副本都是garbage。这种lazy 删除的方法，将删除的操作batch到一起，更高效。

Stale Replica Detection

chunk的副本还有可能过期。当chunkserver挂掉的时候，有mutation操作的话。所以为每一个chunk，master会维护一个版本号来追踪是否是最新的版本。version number在master授予lease的时候更新。在垃圾回收的时候删除过期的版本。