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的时候更新。在垃圾回收的时候删除过期的版本。

Reference

[1] The Google File System. SOSP ‘03