Google File System

写在前面

最近没什么论文好看,于是乎又翻阅起了分布式存储系统的老祖宗GFS。开始愈发理解之前的领导花总说的:常读常新。

之前也阅读过GFS的论文,但总是一带而过,很多问题没有想的特别清楚。于是,趁着这次阅读,将我对于GFS的理解总结下来,希望有所帮助。

再次阅读GFS,给我最大的感触是:许多的问题,只能这么做,而且最好就这么做,也充分体会到了简洁优雅的系统设计给我带来的冲击。

背景

GFS是Google为其内部应用设计的分布式存储系统。Google可能是这个星球上最大的数据工厂了。如何高效可靠地存储如此大规模的数据成为一个很棘手的问题。纵观Google的内部应用,数据访问有以下特点:

  1. 数据集庞大,包括数据总量和单个文件都比较大,如应用常常产生数GB大小的单个文件;
  2. 数据访问特点多为顺序访问,比较常见的场景是数据分析,应用程序会顺序遍历数据文件,产生顺序读行为;
  3. 多客户端并发追加场景很常见,极少有随机写行为;
  4. 文件一旦写入完成,一般接下来都是读访问,基本不会再修改,所谓的一次写入,多次读取,例如互联网上的网页存储。

GFS是Google针对其数据访问模式而设计的分布式存储系统。

特点

GFS具备以下特点:

  • 高度扩展性,单个GFS集群文件系统可扩展至几千个节点,数PB的容量;
  • 高可靠性,GFS运行在普通x86服务器上,但GFS通过多副本等机制保证可靠性;
  • 满足POSIX语义,应用程序无需任何修改即可使用GFS。

架构

GFS系统主要存储文件系统两类数据:

  • 文件元数据:包括file system namespace(目录结构、文件元数据等)、文件存储位置信息等;
  • 文件数据:文件在磁盘上的存储格式

在GFS中,文件被切割为固定大小的Chunk然后分散存储,典型的Chunk大小为64MB。Chunk也是数据复制的基本单位,每个Chunk默认复制三份存放在不同的地方(机架、机器、磁盘)。

Google File System

元数据节点

也称为Master。存储系统元数据信息,主要包括namespace、文件chunk信息以及chunk多副本位置信息。Master是系统的中心节点,所有客户端的元数据访问,如列举目录下文件,获取文件属性等操作都是直接访问Master。除此之外,还承担了系统诸多的管理工作,我们会在后面详细说明。

数据节点

是文件chunk的存储位置。每个数据节点挂载多个磁盘设备并将其格式化为本地文件系统(如XFS)。将客户端写入数据以Chunk为单位存储,存储形式为本地文件。

客户端

提供类POSIX文件接口,应用程序使用客户端与GFS交互。

整个系统的架构特别清晰,功能划分很明确。系统的复杂性在于各种异常处理,而异常又是分布式系统的常态。

Master

Master最主要的两个任务是管理file system Namespace信息和文件的Chunk位置信息。

文件系统元数据

文件系统的元数据主要是文件系统的目录树,在GFS中存储为B+树。树上的每个叶子节点代表普通文件,而中间节点则代表目录文件。根节点是文件系统的根目录。

Master主要存储文件元数据信息,包括:id、文件大小、创建时间、文件的chunk信息等。在论文中说明单个文件的元数据信息不超过64字节。Master会将这些元数据信息进行持久化存储。

Master启动时会将所有元数据加载至内存中,优点是元数据操作速度很快,缺点是限制了文件系统的可扩展性,如64GB内存的服务器最多可支持的文件数量约为 64GB/64B = 10亿。但由于GFS应用场景是大文件,所以这个问题对于他们来说并不严重。

另外,由于元数据的重要性,Master会将文件元数据持久化存储。每一次元数据的更新操作都会先写日志,再应用到内存的B+树,这样即使出现断电等异常,也不会丢失更新。系统重启时,会重放日志在内存中构建B+树。

为了避免日志过大而引发启动缓慢问题,Master会定期进行日志回收,原理是:将当前内存状态冻结并持久化存储到磁盘上,称为Checkpoint;然后,回收该时刻之前的所有日志。若系统此时重启,只需要:1. 将Checkpoint加载入内存;2. 重放Checkpoint点之后的日志即可在内存中重构最新状态。

Chunk管理

大文件会被切割成Chunk(64MB)存储,每个文件至少存储为一个chunk,于是,小文件的chunk大小就会小于64MB。每个Chunk有全局唯一标识符。文件元数据中存储了file id至chunk映射关系。

由于Chunk以多副本方式存储,Master还需要维护Chunk位置信息。Chunk的位置信息ChunkServer周期性汇报,Master只在内存中维护该信息,无需持久化。

核心问题

数据一致性

GFS定义了几种一致性:

defined:状态已定义,从客户端角度来看,客户端完全了解已写入集群的数据,例如,客户端串行写入且成功,此时的状态是defined,如下图1;
consistent:客户端来看chunk多副本的数据完全一致,但不一定defined,如下图2,一般发生在多客户端并发更新时
unconsistent:多副本数据不一致,如下图3;
undefined:数据未定义,如下图4

且论文中写明了各种情况下的状态:

Google File System

下面分别从over-write和append两个场景来阐述:

串行Over-Write

over-write由客户端指定文件更新offset。当客户端是串行更新时,客户端自己知道写入文件范围以及写入数据内容,且本次写入在数据服务器的多副本上均执行成功。因此,本次写结果对于客户端来说就是明确的,且多副本上数据一致,故而结果是defined。如下图:

Google File System

并行Over-Write

并行写入时多个客户端由于写入范围可能交叉而形成交织写。这时候,由于单个客户端无法决定写入顺序(只有主副本才能决定谁先写谁后写),因此,即使写入成功,客户端仍无法确定在并发写入时交叉部分最终写入结果,但是因为写入成功,所以多副本数据必然一致。如下图:

Google File System

图中红色部分代表并发追加的部分,这部分数据由于无法确定谁先谁后执行,因此结果不确定。但由于跟新成功,因此,副本间数据是一致的,这就是consistent but undefined。

无论是穿行还是并行over-write,一旦失败,多个chunk副本上的数据可能都不一致了,其次,客户端从不同的副本上读出的数据也不一样(可能某些副本成功而某些副本失败),因此,必然也是undefined,也是inconsistent。

append

客户端append操作无需指定offset,由chunk主副本根据当前文件大小决定写入offset,在写入成功后将该offset返回给客户端。因此,客户端能够根据offset确切知道写入结果,无论是串行写入还是并发写入,其行为是defined。如下:

Google File System

append失败

假设上面的append经历了一次重试,那可能实际chunk的布局如下:

Google File System

由于第一次写失败(错误可能发生在任意一个副本),导致了多副本之间从50至80的数据可能不一致。但接下来重试成功,从80至110之间的数据一致,因此,其状态是interspersed with inconsistent。

GFS 租约

GFS是一种强一致性性协议,要实现强一致性,就必须要在chunk多副本之间选择出一个主副本,由主副本来协调客户端的写入,保证多副本之间维持一个全局统一的更新顺序,GFS使用了租约。

租约(Lease)是由GFS中心节点Master分配给chunk的某个副本的锁。持有租约的副本方可处理客户端的更新请求,客户端更新数据前会从Master获取该chunk持有租约的副本并向该副本发送更新请求。

租约本质上是一种有时间限制的锁:租约的持有者(chunk的某个副本)需要定期向Master申请续约。如果超过租约的期限,那么该租约会被强制收回并重新分配给其他副本。

租约中有一个问题值得思考:假如副本A1、A2、A3(A1是主副本),在写的过程中A3掉线,此时还能继续写么?
可能解决方案:

  • 客户端在重试N次后依然写失败,启动数据恢复,在数据恢复过程中该chunk不可写入,此时需要由应用去处理不可写情况(GFS做法);
  • master对此种情况时分配一个新的chunk写入,原不可写chunk后续无法被再写入。(QFS的做法?不确定,待调研,此做法可能导致chunk大小不再固定为64MB,可能会带来其他麻烦)
  • 降低要求,写入A1、A2即可,后面等master数据恢复将副本3再恢复出来(Oceanbase的做法貌似,待看看代码)。

关键流程

数据写入

Google File System

  1. 客户端向Master查询待写入的chunk的副本信息,
  2. Master返回副本列表,第一项为主副本,即当前持有租约的副本;
  3. 客户端向多副本推送待写入数据,这里的推送是指将数据发送至chunk多副本,chunkserver会缓存这些数据,此时数据并不落盘;
  4. 客户端向主副本发起Sync请求;
  5. 主副本将数据写入本地的同时通知其他副本将数据写入各自节点,此时数据方才落盘;
  6. 主副本等待所有从副本的sync响应;
  7. 主副本给客户端返回写入成功响应

这里需要说明的是客户端的数据吸入被拆成了数据推送和sync两个子命令,这是因为:

  • 数据推送过程,客户端可以根据网络拓扑情况进行推送路径优化:客户端可以选择距离自己最近的副本推送数据,然后再由该副本选择下一个距离自己最近的副本进行数据推送,直到数据被扩散至所有副本,由于该过程仅仅是将数据推送给chunkserver并保存在内存缓冲区中,因此,无需保证数据推送顺序;
  • sync是将上面推送的数据落盘,需要保证多副本上数据写入序列的一致性,否则大家各人执行各人的,会出现副本之间数据不一致,该指令必须由主副本来确定数据更新顺序然后将该顺序通知给其他从副本。

数据读取

chunk副本位置的选取

GFS中chunk以多副本存储,以提高数据可靠性。因此,副本位置的选取是一个比较关键的问题,一个好的副本位置定义算法满足下面特性:

  1. 保证足够的可靠性,例如,不能将所有副本存放在同一个磁盘或者物理机器上;
  2. 保证写入高效性,多副本位置尽量靠近,降低写入延迟,提高读写性能

GFS在论文中说明了创建chunk时副本位置的选择算法:

  1. 选择存储空间利用率最低的节点和磁盘;
  2. 选择最近一段时间内新建chunk数量较少的节点和磁盘;
  3. 将多个副本分散在不同的rack上。

1和3比较容易理解,2是为了保证一个节点/磁盘不会被频繁新建chunk(新建完接下来就是数据写入了),否则很容易沦为热点,导致磁盘IO和网络带宽被占满,影响效率。

Snapshot

Snapshot是对系统当前状态进行的一次拍照。用户可以在任意时刻回滚到快照的状态。GFS使用COW技术实现Snapshot。

COW原理是如果被Snapshot的文件有更新操作时,就将文件的要被更新的chunk复制一份,然后对复制的chunk进行更新,而原来的chunk作为快照数据被保留,以后要恢复到该快照时,直接将该chunk读出即可。

当GFS的Master节点收到Snapshot请求时:

  1. 回收Snapshot请求覆盖的文件chunks上的租约,这样,接下来客户端要对文件修改时,就必须向Master申请,而此时master就可以对chunk进行复制;
  2. Master在日志中记录本次Snapshot操作,然后在内存中执行Snapshot动作,具体是将被Snapshot的文件或目录的元数据复制一份,被复制出的文件与原始文件指向相同的chunk;
  3. 假如客户端申请更新被Snapshot的文件内容,那么找到需要更新的Chunk,向其多个副本发送拷贝命令,在其本地创建出Chunk的副本Chunk’,之所以本地创建是因为可以避免跨节点之间的数据拷贝,节省网络带宽;
  4. 客户端收到Master的响应后,表示该Chunk已经COW结束,接下来客户端的更新流程与正常的没有区别。

Google File System

参考

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>