/ DISTRIBUTEDSYSTEM

浅谈Google的三驾马车之GFS

上图为古天乐——真·高富帅（GFS）

谷歌在2003到2006年间发表了三篇论文，《MapReduce: Simplified Data Processing on Large Clusters》，《Bigtable: A Distributed Storage System for Structured Data》和《The Google File System》介绍了Google如何对大规模数据进行存储和分析。这三篇论文开启了工业界的大数据时代，被称为Google的三驾马车。本文介绍Google File System的相关内容。

背景介绍

在21世纪初，互联网上的内容，大多数企业需要存储的数据量并不大。但是Google不同，Google的搜索引擎的数据基于爬虫，而由于网页的大量增加，爬虫得到的数据也随之急速膨胀，单机或简单的分布式方案已经不能满足业务的需求，所以Google必须设计新的数据存储系统，其产物就是Google File System（GFS）。不过，在Google的设计中，为了尽可能的解耦，GFS仅负责数据存储而不提供类似数据库的服务。也就是说，GFS只存数据，而对数据的具体内容一无所知，自然也就不能提供基于内容的检索功能。所以，更进一步，Google开发了Bigtable作为数据库，向上层服务提供基于内容的各种功能。此外，Google 的搜索结果依赖于PageRank算法的排序，而该算法又需要一些额外的数据，比如某网页的被引用次数，所以他们还开发了对于的数据处理工具MapReduce，在读取了Bigtable数据的技术上，根据业务需求，对数据内容进行运算。其总体架构如下，GFS能充分利用多个Linux服务器的磁盘，并向上掩盖分布式系统的细节。Bigtable在GFS的基础上对数据内容进行识别和存储，向上提供类似数据库的各种操作。MapReduce则使用Bigtable中的数据进行运算，再提供给具体的业务使用。

Troika

Google File System

GFS是三驾马车中最底层的组件，当然也是最复杂的，因为他直接和分布式的系统接触。在具体探讨实现细节之前，Google给出了一些设计前提和设计目标。

  1. 由于使用的机器是廉价的商业化机器，那么机器崩溃被认为是一种常态。
  2. 系统存储以大文件为主，但也支持小文件。文件大小通常在100MB左右并且需要高效的操作几个GB的文件。
  3. 系统需要支持大规模的连续读取和小规模的随机读取，以及大规模的追加写。
  4. 高性能稳定的网络带宽比延迟更重要。
  5. 以及最重要的，能在分布式的系统上运行。

在下面，我们根据具体的措施讨论如何实现以上目标。

总体架构

首先我们来看看GFS的总体架构。在这个架构中，GFS采用了单Master（Single Master）的设计来简化系统的复杂度。Master负责两点，一是存储和维护Chunk Server和数据块的相关信息，二是处理客户端的请求。也就是说，Master并不存储任何具体的数据，这些数据被存在被称为Chunk Server的数据节点上。其中Chunk就是指数据块，在GFS中被固定为64MB大小，我想着可能跟第二个目标相关。每当数据需要被写入时，就更新GFS中的信息，并把数据封装成Chunk写入到数据库中，具体流程在下面会仔细介绍。

GFS Architecture

上图演示了应用如何调用GSF进行读操作的具体流程

  1. 应用调用GFS Client的函数，要求其读取具体的文件/foo/bar，假设大小为50MB。
  2. GFS Client根据Chunk的固定大小计算出/foo/bar的Chunk的Index，即64/50向上取整，Chunk Index=1。以及其在Chunk内的偏移量Byte Range[0，50]，并将File Name和Chunk Index作为参数发送给GFS Master
  3. Master返回了对应的Chunk Handle（也就是Chunk的ID，上图中的2ef0）和Chunk Locations（Chunk Server和其副本的IP）
  4. GFS Client根据返回的Chunk Locations找到最近的Chunk Server，然后根据Chunk Handle找到对应的Chunk，最后按照这个文件在Chunk中偏移量Byte Range读取文件。
  5. Chunk Server按照其要求返回文件数据。

整个的流程相当清晰，客户端负责将文件在File Namespace的位置交给Master，Master根据其位置返回对应的Chunk和Chunk Server，然后客户端再根据这些信息去拿数据。但是，这里有很巧妙的设计，就是GFS将所有数据传输的压力都放到Chunk Server上，而不是Master。假设由Master根据Chunk Handle去找数据并返回给客户端，那么这里就有会造成系统带宽压力增大。如果按照假设设计，Chunk Server将数据传回给Master后，Master还要将数据传回给客户端，也就是64MB的流量陡然翻倍成128MB。而实际的GFS不仅降低了Master带宽的压力，还把读取数据的压力均摊到每个Chunk Server上，降低了整个系统的压力。这些设计明显有助于实现目标三。

通过对读取过程的分析，可以发现，GFS已经完全实现目标二中的大规模连续读和小规模随机读的要求。

Single Master

Master中保存三种信息（MATEDATA）

  1. 文件和chunk的namespace，即文件树形式的命名方式。
  2. 文件到chunk的映射，即每个文件需要哪几个Chunk来记录。
  3. 每一个chunk的具体位置。

这些信息都平时都存在内存中，以此提高响应速度。这似乎只能存储很少的信息，但是，Master只需要64byte的空间就能记录64MB的Chunk的相关信息，也就是说，128MB的内存能存储1PB的数据的相关信息。不过，为了保证Master能在崩溃后恢复，在执行改变前两种信息的操作前需要使用WAL的形式定期地保存到磁盘上。这样，在Master恢复的时候，就能通过磁盘上的WAL来重建前两种信息。而Chunk的位置则可以通过Heartbeats的形式查询并更新，这样不仅加速了Master的恢复，也能使GFS的配置更加灵活。

写数据（Write）

由于每个Chunk Server都有备份的副本，所以写操作要比读操作稍微复杂一点。具体的流程如下图所示

GFS Write

  1. 客户端向 Master 询问目前哪个Chunk Server持有该Chunk的Lease
  2. Master 向客户端返回Primary Replica和其他Replica的位置
  3. 客户端将数据推送到所有的Replica上。Chunk Server会把这些数据保存在缓冲区中，等待所有 Replica 都接收到数据。
  4. 客户端发送写请求给 Primary，Primary 为来自各个客户端的修改操作选定执行序列号，并按顺序地应用于其本地存储的数据。
  5. Primary 将写请求转发给其他 Secondary Replica，Replica 们按照相同的顺序应用这些修改
  6. Secondary Replica 响应 Primary，示意自己已经完成操作。
  7. Primary 响应客户端，并返回该过程中发生的错误

这里要说明的是，每个Chunk被复制到多个Chunk Server中，以此避免单个节点崩溃可能造成的数据损失。而这些Chunk Server中负责相应写操作的Chunk Server被称为Primary Replica，其余的被称为Secondary Replica，接受来自Primary Replica的请求。而为了保证写入数据的一致性，只能有一个Primary Replica，这里的唯一性就由Lease来实现。当需要写入数据时，Master会将特定的Lease分配给某个Replica，拿到Lease的这个Replica就称为了Primary Replica。

我们再仔细分析整个写的的流程。我们可以注意到为了保证数据的一致性，一次写入只能有一个Primary Replica，同样地，在正式写入数据之前要求所有Secondary Replica缓存数据也是为了一致性。这里的思想类似于WAL，将要执行的操作先保存下来，这样万一崩溃了也能从磁盘读入数据，继续执行未完成的操作。等待所有Secondary Replica完成操作后再相应客户端也是为了保证数据的一致性。

和读操作类似，在写操作中，为了降低Master的压力，所有的数据由客户端发向Chunk Server。

追加（Append）

为了提升性能，GFS提供并推荐使用追加操作修改文件。它与写操作不同之处仅仅在于它向文件尾端添加数据而不是覆盖，它的流程也he 写操作大同小异

  1. 客户端将数据推送到每个 Replica，然后将请求发往 Primary
  2. Primary 首先判断将数据追加到该块后是否会令块的大小超过上限：如果是，那么 Primary 会为该块写入填充至其大小达到上限，并通知其他 Replica 执行相同的操作，再响应客户端，通知其应在下一个块上重试该操作
  3. 如果数据能够被放入到当前块中，那么 Primary 会把数据追加到自己的 Replica 中，拿到追加成功返回的偏移值，然后通知其他 Replica 将数据写入到该偏移位置中
  4. 最后 Primary 再响应客户端

特别值得一提的是，GFS保证追加操作至少被执行一次（at least once），这意味着追加操作可能被执行多次。当追加操作失败时，为了保证偏移量，GFS会在对应的位置填充重复的数据，然后重试追加。也就是说，GFS不保证在每个副本中的数据完全一致，而仅仅保证数据被写入了。

数据一致性

在GFS中，由于分布式系统的原因，不同节点间处理请求和存储数据速度不一致导致了客户算读取数据时可能出现各种不同的情况。

文件的数据修改则相对复杂。在讲述接下来的内容前，首先我们先明确，在文件的某一部分被修改后，它可能进入以下三种状态的其中之一：

在文件的某一部分被修改后，它可能进入以下三种状态的其中之一：

  • 客户端读取不同的 Replica 时可能会读取到不同的内容，那这部分文件是不一致的（Inconsistent）。
  • 所有客户端无论读取哪个 Replica 都会读取到相同的内容，那这部分文件就是一致的（Consistent）。
  • 所有客户端都能看到上一次修改的所有完整内容，且这部分文件是一致的，那么我们说这部分文件是确定的（Defined）。

也就是说，在一致性和强度上，Defined>Consistent>Inconsistent。

在修改后，一个文件的当前状态将取决于此次修改的类型以及修改是否成功。具体来说：

  • 如果一次写入操作成功且没有与其他并发的写入操作发生重叠，那这部分的文件是确定的（同时也是一致的）。
  • 如果有若干个写入操作并发地执行成功，那么这部分文件会是一致的但会是不确定的：在这种情况下，客户端所能看到的数据通常不能直接体现出其中的任何一次修改。也就是说，操作成功执行了，但是有的操作的数据改变被覆盖了，客户端看不到被覆盖的数据改变。
  • 失败的写入操作会让文件进入不一致的状态。

论文中给出了总结的表格：

consistency

至于为什么追加（Append）是Defined但是有可能是不一致是因为：在追加写操作失败时，为了保证数据的偏移，可能为填充重复的数据，此时导致了不一致。但是失败的操作会被再次执行，此时又保证了数据的一致性。而由于使用的是追加，所以任何数据的改动都可以观察到，所以是Defined。

快照（Snapshot）

这里的快照的目的不同于Raft中的压缩，它仅仅驶出为了生成一个新的Replica，可以看做是一个简单的复制操作。

  1. 在 Master 接收到快照请求后，它首先会撤回相关Chunk Server的 Lease，保证在创建快照的过程中，客户端对不会对相关的Chunk Server进行写操作或者追加操作。
  2. 当Lease收回后，Master会先将相关的改动写入日志，然后对自己管理的命名空间进行复制操作，复制产生的新记录指向原本的 Chunk。
  3. 当有客户端尝试对新的Chunk Server进行写入时，Master 会注意到这个 Chunk 的引用计数大于1（可能是一个标记）。此时，Master 会为要读取的Chunk生成一个Handle，然后通知所有持有这些 Chunk 的 Chunk Server 在本地复制并使用出新的 Chunk，然后再返回给客户端

我想GFS提供快照的原因可能是为了在一个副本损坏时，从Primary Replica或者其他副本复制数据，然后用新的节点代替损坏的节点。

垃圾回收

当GFS收到删除文件的请求时，它并不直接删除文件，而是给文件打上删除的时间戳并将其命名为掩藏文件（文件开头加”.”）。在周期性扫描过程中，当发现文件的删除时间超过设定期限后，才真正地将文件删除。Google认为其有以下优点

  • 对于大规模的分布式系统来说，这样的机制更为可靠：在 Chunk 创建时，创建操作可能在某些 Chunk Server 上成功了，在其他 Chunk Server 上失败了，这导致某些 Chunk Server 上可能存在 Master 不知道的 Replica。除此以外，删除 Replica 的请求可能会发送失败，Master 会需要记得尝试重发。相比之下，由 Chunk Server 主动地删除 Replica 能够以一种更为统一的方式解决以上的问题
  • 这样的删除机制将存储回收过程与 Master 日常的周期扫描过程合并在了一起，这就使得这些操作可以以批的形式进行处理，以减少资源损耗；除外，这样也得以让 Master 选择在相对空闲的时候进行这些操作
  • 用户发送删除请求和数据被实际删除之间的延迟也有效避免了用户误操作的问题

高可用

论文中主要探讨了三个方面的高可用，分别是Master，Chunk Server和数据完整性。

当Master崩溃时，有两种情况，一是进程崩溃但是服务器没有，这种情况下，重开一个进程即可。另一种情况是整个机器崩溃了，在GFS还有被称为Shadow Master的机器，复制Master节点的信息。当Master机器崩溃后，Shadow Master会接替Master进行服务，但是仅提供读取操作的服务，不能更改信息。

当Chunk Server崩溃时，Master会安排新的Replica代替它，从其他Replica复制原始数据。而当Chunk Server恢复时，由于数据不同步，不应该提供服务，Master就需要区别新旧Chunk Server。GFS使用版本号来标记这个信息，每分配以此Lease，版本号就会增加并同步给其他Replica，而由于Chunk Server崩溃后不能更新，我们就能从版本号上辨别新旧。

由于写操作和追加操作可能不成功，所以数据可能会损坏。GFS使用检验和检查是否损坏，每次客户端读取数据时，Chunk Server都会检查检验和，一旦发现损坏，就会向Master报告。Master则会将请求发送给其他Replica，并从其他Replica复制数据到该机器。

总结

2003年GFS的横空出世具有划时代的意义，它标志着学术上的分布式理论和一些实验性质的尝试在工业界有了大规模商用的案例，尤其还是在Google这样的公司。它的系统设计在后续的系统中被屡次参考复用，而其设计确实有独到之处，比如Master负责控制流而完全将数据流从其剥离，这样的设计不能不说是优雅。这篇论文催生了HDFS，至今仍被许多公司使用，足以可见其影响力之大。哪怕这篇论文距离今天已经有快20年的时间，GFS在Google内部迭代多次，但是其设计仍然值得每一个分布式程序员学习。