阅读 209

The Google File System 论文笔记

在阅读本论文时,我还阅读了 OceanBase 的大佬写的书[1],配合论文阅读会更加有收获。这本书虽是13年写的,但对于当时许多主流的技术均有涉及(不过有罗列的嫌疑),作者本人的功力也是非常深厚的。

在论文简介中给出了 GFS 的 4个决策依据(第4个感觉不是假设,而是结果):

  • 组件的失败是频繁的。包括磁盘、内存、网络、系统,甚至人为因素。计算机是不可信的。
  • 文件系统中的文件很大(GB 以上)。这一点决定了之后的一些设计决策,比如块的大小。对于谷歌而言,这是非常自然的,因为谷歌的搜索依赖于倒排索引,数量非常巨大。不过,这个假设时至今日已经不再有力,所以不论是谷歌还是阿里都有自己支持小文件的分布式文件系统。
  • 大部分文件都是追加而非修改操作。不存在随机的数据写入。这个假设熟悉 HDFS 的人应该都不陌生。这实际上是数据仓库的基本条件之一。
  • 应用程序和文件系统 API 的协同设计提高了整个系统的灵活性。这个指的是 GFS 使用了比较弱的一致性模型,所以应用程序不需要做很多复杂的操作比如加锁。

架构

GFS 的架构很简单,但它不是通常意义上的主从结构,而是 master 和 chunkserver,也就是存储元数据和文件数据的两种服务器。这里虽然论文中用了 single 这个词,但 master 是有 replication 机制的。

The master maintains all file system metadata. This includes the namespace, access control information, the mapping from files to chunks, and the current locations of chunks. It also controls system-wide activities such as chunklease management, garbage collection of orphaned chunks, and chunkmigration between chunkservers. The master periodically communicates with each chunkserver in HeartBeat messages to give it instructions and collect its state.
GFS client code linked into each application implements the file system API and communicates with the master and chunkservers to read or write data on behalf of the application. Clients interact with the master for metadata operations, but all data-bearing communication goes directly to the chunkservers.
Neither the client nor the chunkserver caches file data. Client caches offer little benefit because most applications stream through huge files or have working sets too large to be cached. Not having them simplifies the client and the overall system by eliminating cache coherence issues. (Clients do cache metadata, however.) Chunkservers need not cache file data because chunks are stored as local files and so Linux’s buffer cache already keeps frequently accessed data in memory.

GFS 的单点 master 决定了它必须减少 master 的负载,因此客户端在得到了 元数据信息之后,会进行缓存,从而避免和 master 通信。另外,客户端在获取元信息时也会尽可能多的获取 chunk 的信息,这样就减少了重复通信。

master 给每个 chunkserver 一个唯一的标识符,这个在 hdfs 里就是 clusterId,可以在dfs.namenode.data.dir 配置的目录下的 current/version 里找到。

一个大致的读流程是这样的:首先,客户端根据固定 的 Chunk 大小把文件名和程序指定的字节偏移转换成文件的 Chunk 索引。然后它把文件名和 Chunk 索引发送给 Master 节点。Master 节点将相应的 Chunk 标识和副本的位置信息发给客户端,客户端用文件名和 Chunk 索引作为 key 缓存这些信息。

在实际中,我们所谓的客户端(比如说笔记本)不太可能直连集群,因为我们实际上会访问诸多数据节点,这里面除了网络通信的问题,还有安全问题。

可以看到,这里最小化了 master 的开销。

Chunk Size

在 GFS 中设计的分块大小是 64MB(Hadoop 也效仿了,后来改成了 128MB)。为什么要选择一个大于文件块大小的分块呢?主要有两个原因:

  • 元数据信息变小。这可以保证 master 可以将所有元数据载入内存,同时客户端可以缓存更多的元信息;
  • 减少通信。由于前面假设存储的文件通常是大文件,因此可以保证尽可能多地读写同一个块的内容。

但是,更大的块会造成数据的热点问题。但这主要是因为小文件的密集访问导致的(大文件我们可以错开各个块的访问)。

Meta Data

元数据分为3类:文件和 Chunk 的命名空间、文件和 Chunk 的对应关系、每个 Chunk 副本的存放地点。这些元数据是保存在内存里的,前二者也会存储它们的变更日志。为什么副本的位置不需要呢?还是因为组件是很容易崩溃的,因此 GFS 采用轮询来获取这个信息(也就是 hdfs 的 BlockReport),而没有进行持久化。

实际上,论文中也指出,他们在一开始也尝试过持久化 chunk 的位置信息,但是并不理想。显然,持久化意味着一致性问题,在 chunkserver 上下线甚至更名的时候,都是很麻烦的。不过,由于 master 没有一致性的(全局)视图,所以我们有可能在读写数据时出错,这时就需要实现一些容错的机制。

Operation Log

这个操作日志的设计就不用说了,基本上就是数据库里的老生常谈了,包括 CheckPoint,分组提交等等。Checkpoint 文件以压缩B-树存储,可以直接映射到内存中。

按照论文的说法,诸如 CheckPoint 的生成和日志的切换都是在一个新的线程里完成的,实际上就是 hdfs 的 Secondary Name Node。这个节点通常会被放在另一个服务器中,从而彻底的避免对 master 的delay。

Consistency Model

一致性是 GFS 的重头戏之一。可以参考论文给出的一幅图:

这里的 file region 应该指的是一个文件中的某个内容范围。如果一个 region 对于所有的客户端都是一致的,那么就认为是图中的 consistent;而 defined 的要求更高,不仅是 consistent,而且必须要保证写入有效(客户端可以看到所有写入的内容),但在并发写入下可能会被覆盖。

GFS,一致性模型里,“已定义”和“不一致”具体表示的什么含义?

如果失败就会不一致,因为可能存在部分节点已写的情况。但为什么并发追加成功了也会造成部分的不一致呢?而为什么并发写没有这个问题呢?

Data mutations may be writes or record appends. A write causes data to be written at an application-specified file offset. A record append causes data (the “record”) to be appended atomically at least once even in the presence of concurrent mutations, but at an offset of GFS’s choosing (Section 3.3).

这里出现了一个分布式系统的术语——至少一次。也就是说,这里的成功是存在重试的,因为 chunkserver 可能存在暂时的不可用。在追加模式下,master 可能会重新分配新的 region,这样就造成了各个副本之间并不是完全一致。但由于可以通过校验和来抛弃重复数据,因此至少一次并没有太大的影响——即使 reader 端会因此产生非幂等操作,也可以通过增加唯一标识的方式来避免。

可以看到,GFS 没有采用 2PC 来进行多副本的复制,这意味着各个副本可能存在不一致性。但可以通过客户端重试来解决这个问题。

System Interactions

Leases and Mutation Order

这一部分在 Hadoop 里实现差异比较大。在 GFS 中,租约是一种针对每个 chunk 的委托,将多副本协调的权力交给了其中一个副本,从而减少 master 的压力。租约实际上是 master 上的一种锁。持有租约的 chunkserver 会序列化对 chunk 的修改操作来保证次序。但在 HDFS 里,租约是颁给客户端的,它是客户端写和创建文件的凭据。当然,它也是一种锁。

显然,如果客户端独占了该文件,那么就不存在并发写入的问题了。Hadoop 的一大特点就是不支持并发写(不论是追加还是随机写)。GFS 后来的复盘也说明,这是一个英明的决定[2]

Was this done by design?

At the time, it must have seemed like a good idea, but in retrospect I think the consensus is that it proved to be more painful than it was worth. It just doesn't meet the expectations people have of a file system, so they end up getting surprised. Then they had to figure out work-arounds.

In retrospect, how would you handle this differently?

I think it makes more sense to have a single writer per file.

decouple the flow

GFS 分离了数据流和控制流。但在 HDFS 里,我们知道控制信息和数据都是通过某个离客户端较近的 datanode 发送的。但数据的 pipeline 是相同的,因为这可以最大化网络传输的效率。

Atomic Record Appends

因为 HDFS 不支持并发写,所以这个特性对于 hdfs 就不是必要的了。这个原子并不是传统意义上几个机器之间的同步,而指的是写入操作本身不能被再分块[3]。这是有可能的,因为我们可能希望在一个文件写入的位置和长度超过了这个 chunk。此时 GFS 会通过填充 padding 来处理,也就是说,强制从一个新的 chunk 开始来保证写入是原子的。

Snapshot

这个使用 COW 的快照机制和我们想的差不多,就是针对当前快照的目录或者文件做标记,从而在下次写入请求之前进行重定向,就地(指的是在 chunkserver 上)创建一个新的副本。唯一需要注意的是,master 在收到快照请求后,它会立即取消快照对应文件的所有租约。这样就报证了之后所有的写都可以被 master 先收到。

Master

Namespace Management and Locking

GFS 通过给命名空间增加读写锁来保证多线程并发不受干扰。唯一比较 trick 的地方是,这里只需要获取父目录的读锁,就可以保证父目录不被删除或者改名。

Garbage Collection

GFS 的垃圾回收是惰性的。首先,它隐藏而不是直接删除元数据;其次,它不发送删除消息(因为可能会丢失),而是等待握手时将 chunk 失效的信息发送出去。延迟回收的缺点是不能获得即时的空间调优,但 GFS 论文里也提到,可以通过设置命名空间不同的回收策略来达到优化的目的,或者显式的再次删除一个已经删除的文件。

Stale Replica Detection

对于过期的副本,GFS 通过版本号来确定(这有点像 MVCC)。并且在垃圾回收中,可以移除所有过期的副本。

If the master sees a version number greater than the one in its records, the master assumes that it failed when granting the lease and so takes the higher version to be up-to-date.

不太清楚什么时候 master 会看到一个比自己高的版本号。难道是 master 宕机的时候?

Fault tolerance

容错是分布式系统的核心问题。GFS 在高可用上的措施是非常简单的,和 MySQL 非常像,也就是 Checkpoint 加上 edit log 的模式。

Master 是具有高可用机制的,存在外部的监控程序来进行 master 的替换:

If its machine or disk fails, monitoring infrastructure outside GFS starts a new master process elsewhere with the replicated operation log. Clients use only the canonical name of the master (e.g. gfs-test), which is a DNS alias that can be changed if the master is relocated to another machine.

但这个机制一直没有被 hadoop 引入。直到后来 hdfs 才有了Standby NameNode 的高可用机制(我记得好像是华为的大佬贡献的?)。

另外 GFS 里还提到了 shadow master,它是 master 的只读副本,相当于真正的主从结构。

References


  1. 大规模分布式存储系统:原理解析与架构实战 ↩︎

  2. GFS: Evolution on Fast-forward ↩︎

  3. 从 GFS 失败的架构设计来看一致性的重要性 ↩︎