谷歌技术探究之GFS

原 作者 李兆龙 | 发表于 | 分类于 2018级

文章目录

引言

GFS可以说是当今云计算的鼻祖，直至今日借鉴其思想的HDFS仍旧活跃在我们的视线当中，我们实在是有必要去好好的学习下相关的知识的，这篇文章是在学习了《The Google File System》这篇论文以后的一点理解和总结,以及对于6.824相关课程资料的结合。因为掺杂了个人的理解有些地方可能并不准确，还望有不同见解的朋友能不吝赐教。

GFS的主要设计预期

  • 系统由廉价的普通机器组成，所以失效是一种常态。
  • 系统存储一定数量的大文件，预期会有几百万文件，文件的大小通常在100MB或者以上。
  • 工作负载主要由两种读操作构成，大规模的流式读取和小规模的随机读取。
  • 工作负载还有写操作，一般是大规模的、顺序的、数据追加方式的写操作，所以系统支持原子的数据追加操作。
  • 在高吞吐量和低延时之间GFS选择前者。

GFS架构

在这里插入图片描述

我们可以看到处理GFS client以外还有GFS master和GFS chunkserver。

一般而言整个集群中存在一个master，当然这个一个指的不是一台机器，而是一个集群，其中的机器负责主master的容错，和负载均衡。还存在着许多的GFS chunkServer，其中存储着真正的文件内容，如上图所属，这些机器都是普通的运行着Linux的机器，所以资源允许的话可以很容易的把Chunk服务器和客户端都放在同一台机器上，集中式的设计显然大大降低了复杂度。

GFS master负责维护整个集群所有的元数据，包括名字空间、访问控制信息、文件和Chunk的映射信息、以及当前Chunk的位置信息。这里值得一提的是除了当前Chunk的位置信息以外其他的元数据使用操作日志组织，Master服务器在灾难恢复时，通过重演操作日志把文件系统恢复到最近的状态，所以只有当操作日志完成的时候才返回client信息。并且还维护着大量的集群活动，比如chunk lease的管理，孤儿chunk的回收，和chunk server的心跳包通信等。

GFS chunkserver存放着文件的真实内容，当然一般会有三份备份，一般把文件组织为多个拥有固定大小的chunk块，且Master 在创建 Chunk 时会为它们赋予一个唯一的 64 位 Handle（句柄），并把它们移交给 Chunk Server。

chunk相关

这部分有两点值得一提，一个是chunk的尺寸，一个是chunk的位置信息。

首先是chunk的尺寸，我们前面说过GFS一般把文件组织为多个拥有固定大小的chunk块，就像Linux中的文件系统一样，且在master存储着相关的信息。但是显然在GFS中我们不能把其大小设置的向单机文件系统一样大，最终选择了64MB，有如下原因：

  1. 减少与客户端的通信需求，因为客户端只需要一次通信就可以获取chunk的信息，客户端可以轻松缓存下来这些信息，这可以使得单点master出现瓶颈的机会减少。
  2. 采用较大的Chunk尺寸，客户端能够对一个块进行多次操作，这样就可以通过与Chunk服务器保持较长时间的TCP连接来减少网络负载。
  3. 选用较大的Chunk尺寸减少了Master节点需要保存的元数据的数量，Master服务器只需要不到64个字节的元数据就能够管理一个64MB的Chunk。这就允许我们把元数据全部放在内存中，这意味着只需要付出很小的代价增大单点master的内存大小就可以存下大量的数据信息。

当然这样的设计也会出现问题，最为有争议的就是两点内部碎片和热点问题。

碎片的问题论文中并没有给出解决方案，毕竟操作系统中也有类型的问题（伙伴系统的内部碎片）。但是后者给出了解决方案，问题出现在几个Chunk服务器被数百个客户端的并发请求访问导致系统局部过载，一种通用的解决方案就是增大复制参数或者错开批处理队列系统程序的启动时间。

还有一点就是chunk的位置信息，因为这个信息也是元数据之一，但是却不像其他的元数据一样会进行持久化。Master服务器只是在启动的时候轮询Chunk服务器以获取这些信息，通过周期性的心跳包来检测chunkserver，这样可以确保master的信息是最新的。

但是为什么不进行持久化呢，我的理解是这样的，因为Chunk服务器加入集群、离开集群、更名、失效、以及重启的时候都会修改这些信息，而这些事件在集群较大的时候是很频繁的，但是如果我们不进行持久化，选择启动的时候轮询Chunk服务器，之后定期轮询更新的方式会大大简化这个模型，且没有什么正确性的问题。

一致性模型

GFS has a relaxed consistency model that supports our highly distributed applications well but remains relatively simple and efficient to implement.
GFS支持一个宽松的一致性模型，这个模型能够很好的支撑我们的高度分布的应用，同时还保持了相对简单且容易实现的优点。

一致性模型是我认为在这篇论文中最重要，也是最不好理解的一个部分。

在考虑分布式存储系统的时候我们首先要考虑的就是数据一致性问题，从这里也可以看出数据库侧重于可用性还是强数据一致。对于GFS来说我们不需要担心命名空间上的问题，也就是目录，文件之类的创建删除，因为是一个集中式的架构，这些都可以在master上加锁解决并发修改问题，GFS也确实是这样做的。问题出现在数据的并发修改。一般把文件的状态分为以下状态：

  • 存在客户端读取到的数据不一样，那么数据是“不一致（Inconsistent）”。
  • 所有客户端，无论从哪个副本读取，读到的数据都一样，我们认为数据是”一致（consistent）“的。
  • 如果对文件的数据修改之后，状态是一致的，并且客户端能够看到写入操作全部的内容，那么这个region是“已定义的（defined）”

所以一个文件的状态取决于修改的操作是否成功，可以分为以下几种情况：

  1. 如果一次写入操作成功且没有与其他并发的写入操作发生重叠，可以是append操作或者是没有冲突的一般写入，那这部分的文件是确定的（同时也是一致的）
  2. 如果有若干个写入操作并发地执行成功，那么这部分文件会是一致的但会是不确定的，因为写入的时候会有写入的偏移量，所以会导致数据脏掉了，没有办法读到每一次的全部数据。
  3. 失败的写入就是不一致的

论文中对于各种情况的总结是这样的：
在这里插入图片描述

那么如何理解这些状态呢，首先我们要明确写入操作只有两种情况，一个是指定偏移量的写入和追加写入，首先我们明确后者是可以保证原子的，因为没有指定偏移量，所以可以有master来指定多个原子写入的顺序，返回实际的偏移量，所以可以实现defined && consistent。但是指定偏移量的写入在客户端指定了偏移量，所以master会认为是有效的，直接写入，这导致实际写入的数据是乱的（undefined），但是多个客户端又确实可以看到相同的数据（consistent）。

还好在GFS中基本都是append的操作，所以这并不会有什么太大的问题。而且GFS中保证append是原子的，我们在执行append的时候不需要指定偏移量，只需要指定写入数据，GFS保证写入操作至少一次（at least once）是成功执行的。值得一提的是append操作会造成数据的重复和数据的填充，分别在以下情况：

  • 在每次append操作中，主Chunk（涉及到lease的分配）会检查这次记录追加操作是否会使Chunk超过最大尺寸（64MB）。如果超过了最大尺寸，主Chunk首先将当前Chunk填充到最大尺寸。
  • append操作如果在某个chunk上失败了客户端就要重新操作，但是这会使得不同副本包含相同的数据，GFS并不保证Chunk的所有副本在字节级别是完全一致的。

那么我们该如何解决这些问题呢？答案就是Writers在每条写入的记录中都包含了额外的信息，比如chenksum，Reader可以利用Checksum识别和抛弃额外的填充数据。相同的数据可以使用唯一标识符来进行过滤。

这么多的写入优化，这也可以看出GFS真的很侧重于append操作了。

这就是GFS一致性模型及其相关。更多的可参考[6]。

系统的交互过程

这是一个非常重要的部分，描述了master和chunkserver交互中的一些细节，因为GFS的设计是集中式的，所以难免会有master的瓶颈问题，所以需要最大程度的减少与master的交互。同时还会说说chunck lease和快照功能。

租约（lease）

首先我们知道chunk为了负载均衡和容错是需要有副本的，这个副本数一般是三个，那么如何使它们之间的数据一致呢？答案就是使用lease机制来保持多副本之间顺序一致。Master节点为Chunk的一个副本建立一个租约，我们把这个副本叫做主Chunk。主Chunk对Chunk的所有更改操作进行序列化，所有的副本都遵从这个序列进行修改操作。也就是说实际的写入顺序取决于得到lease的主chunk。你也许会说不使用租约的话也可以达到类似目的呀，这其实是为了减少主节点的负担[5]。

一次正常的写入的具体执行过程如下：
在这里插入图片描述

  1. 客户端询问哪一个chunkserver持有租约，回复附带着副本的位置，如果没有的话，master选择一个副本建立租约。
  2. master节点返回主chunk的标识和副本的标识，客户端进行缓存（这样的过程显然可能会出现读到过期的数据），减少于master的交互。只有在主Chunk不可用，或者主Chunk回复信息表明它已不再持有租约的时候，才会从新向master请求。
  3. 客户机把数据推送到所有的副本上，客户机可以以任意的顺序推送数据。
  4. 当所有的副本都确认接收到了数据，客户机发送写请求到主Chunk服务器。主Chunk为接收到的所有操作分配连续的序列号，这些操作可能来自不同的客户机。
  5. 把写请求发送到所有的副本，都以主chunk的顺序执行。
  6. 所有的二级副本回复主Chunk，它们已经完成了操作。
  7. 主chunk回复客户端完成写入，就算有一个失败也会回复客户端写入失败，client处理这样的错误的方法就是多执行几遍，再重新执行之前会把【3,7】之间的步骤多执行几遍。

这里有一点很有意思，就是数据流和控制流分离。也就是上图所述，数据流并不像控制流一样之间从客户端传递到主chunk，数据是以管道的方式，顺序的沿着一个精心选择的Chunk服务器链推送。目标是充分利用每台机器的带宽，避免网络瓶颈和高延时的连接，最小化推送所有数据的延时。

我们可以想象如果不是这样的话会怎样，也就是数据流和控制流都发送到master，然后由master同步到副本，这应该就是一般来说最常见的了，也就是主从复制模型，这样的话吞吐量瓶颈就局限在了主chunkserver上了，而GFS中机器都是一样的，显然有很多的带宽都被浪费了，所以这是很有必要的。为了充分利用每台机器的带宽，数据沿着一个Chunk服务器链顺序的推送，而不是以其它拓扑形式分散推送（例如，树型拓扑结构）。线性推送模式下，每台机器所有的出口带宽都用于以最快的速度传输数据，而不是在多个接受者之间分配带宽。

快照

快照用于迅速的创建一个数据集的拷贝，使用了cow（copy-on-write）技术。当Master节点收到一个快照请求，它首先取消作快照的文件的所有Chunk的租约。因为在没有写之前只是读，两个标识指向了同一个文件，即引用计数为2，取消chunk租约的这个措施保证了后续对这些Chunk的写操作都必须与Master交互以找到租约持有者。这就给Master节点一个率先创建Chunk的新拷贝的机会。在快照操作之后，当客户机第一次想写入数据到Chunk C，它首先会发送一个请求到Master节点查询当前的租约持有者。Master节点注意到Chunke C的引用计数超过了1，master不会立即回复请求，而是重新创建一个句柄，而且创建副本并不会经过网络，是在本地创建的。

副本选择

chunk副本的选择希望实现两个目标，即最大化数据可靠性和可用性和最大化网络带宽利用率，这也意味着副本的选取不能全部放在一个机架中，因为只在多台机器上放置只能预防硬盘损坏或者机器失效带来的影响，以及最大化每台机器的网络带宽利用率。如果机架出现问题还是没有用，所以副本一般存放在多个机架上，当然响应的需要付出通信的代价。

一般副本有如下三个用途：

  1. Chunk创建
  2. 重新复制
  3. 重新负载均衡

首先在创建的时候需要考虑在哪里放置空的副本，所以会考虑以下几个因素：

  1. 在平均使用率低的chunk服务器上存储。
  2. 限制在每个Chunk服务器上”最近”的Chunk创建操作的次数。因为在创建操作后一般伴随着大量的写入。

当chunk的有效副本数少于指定的复制数的时候会触发重新复制，这里有一个优先级的概念：

  1. Chunk现有副本数量和复制因数相差多少。例如，丢失两个副本的Chunk比丢失一个副本的Chunk有更高的优先级。
  2. 优先重新复制活跃（live）文件的Chunk而不是最近刚被删除的文件的Chunk（删除的文件在一段时间内没有被真实删除，只是改了名字而已）。
  3. 为了最小化失效的Chunk对正在运行的应用程序的影响，master会提高阻塞客户机程序处理流程的Chunk的优先级。在出现错误的时候尽快复制。

这里的复制遵循创建时的策略。还有一点就是负载均衡，Master服务器周期性地对副本进行重新负载均衡：它检查当前的副本分布情况，然后移动副本以便更好的利用硬盘空间、更有效的进行负载均衡。

容错机制

master

master的高可用依赖于副本存储信息，Master服务器所有的操作日志和checkpoint文件都被复制到多台机器上，只有当数据写入到本地磁盘和所有的副本服务器上的时候才会返回给客户端写入完成，所以这可以使得master在宕机的时候快速恢复。

且GFS中还有一些特殊的服务器，我们称为“Shadow Master”，也就是“影子服务器”，这些“影子”服务器在“主”Master服务器宕机的时候提供文件系统的只读访问。它们是影子，而不是镜像，所以它们的数据可能比“主”Master服务器更新要慢，通常是不到1秒。影子服务器可以通过读取 Master 操作日志的某个备份来让自己的状态与 Master 同步，而且和master一样，“影子”Master服务器在启动的时候也会从Chunk服务器轮询数据，也会定期的和chunk服务器握手。

chunk

每个Chunk都被复制到不同机架上的不同的Chunk服务器上。用户可以为文件命名空间的不同部分设定不同的复制级别。缺省是3。当有Chunk服务器离线了，或者通过Chksum校验发现了已经损坏的数据，Master节点通过克隆已有的副本保证每个Chunk都被完整复制。

FAQ

在文章的最后部分回答下6.824提出的一些问题：

Q： 为什么是3个备份？
在这里插入图片描述

答：N个客户机同时向N个不同的文件中写入数据。每个客户机以每次1MB的速度连续写入1GB的数据。上图显示了整体的写入速度和它们理论上的极限值。理论上的极限值是67MB/s，因为我们需要把每一byte写入到16个Chunk服务器中的3个上，而每个Chunk服务器的输入连接速度是12.5MB/s。这也许是使用三个副本的原因。

Q：除了数据可用，三备份方案给我们带来了什么？

答：load balancing for reads to hot files. 对于热点文件的负载均衡。

Q：GFS主要支持追加（append）、改写（overwrite）操作比较少。为什么这样设计

答：由需求而定，论文中给出的原因是“大量的数据符合这些特性”。

Q：gfs有时会出现重复记录或者padding记录，为什么？

答：首先列出出现的场景

  • padding：
    1.append操作时如果last chunk的剩余空间不满足当前写入量大小，需要把last chunk做padding，然后告诉客户端写入下一个chunk。
    2.append操作失败的时候，需要把之前写入失败的副本padding对齐到master
  • 重复：
    append操作失败的时候不会回滚已经成功的副本写入，会使得客户端重试，此时便出现重复。

那么为什么要出现padding和重复数据呢？我给出的答案是使得设计更为简单和效率上的权衡，以重复距离，如果不支持重复，我们需要支持回滚策略，且在全部生效前对外界不可见，类似于分布式事务，复杂性是很高的，且效率不高，相当于选择了强一致性。如果支持重复的话可以使用其他的方法，比如checksum来使得重复对应用层不可见，且更为简单。padding也是，如果不支持的话，原本的数据就会被分开，增加master的开销和读取开销。

Q： 假设服务一千万个文件，每个文件1GB，master中存储元数据大概占多少内存？

答：1GB/64MB =16，总共需要16×0000000×64 B = 10GB

Q：如果chunkserver下线后过一会重新上线，gfs如何处理？

答：这里涉及到一个过期状态的检测，具体可以参考[7]4.5。master会检测新上线的master是否是最新的，如果不是的话，会重新执行复制，并在后面的垃圾清理中去掉这个过期的副本。如果是最新的话就不会发生什么了。检测的机制是使用lease的版本号。

Q：应用怎么知道 Chunk 中哪些是填充数据或者重复数据？

答：要想检测填充数据，应用可以在每个有效记录之前加上一个魔数（Magic Number）进行标记，或者用校验和保证数据的有效性。应用可通过在记录中添加唯一 ID 来检测重复数据，这样应用在读入数据时就可以利用已经读入的 ID 来排除重复的数据了。

Q：GFS 是怎么确定最近的 Replica 的位置的？

答：论文中有提到 GFS 是基于保存 Replica 的服务器的 IP 地址来判断距离的。在 2003 年的时候，Google 分配 IP 地址的方式应该确保了如果两个服务器的 IP 地址在 IP 地址空间中较为接近，那么它们在机房中的位置也会较为接近。

Q：Master 不会成为性能瓶颈吗？

答：这其实是论文中一直在讨论的问题，GFS通过client缓存，加大数据块等方法减少与master的交互，以论文中的实验数据来看，对于大文件的读取和小文件的操作master都不是瓶颈。

Q：为什么要将数据流和控制流分开？如果不分开，如何实现追加流程？

答：为了更有效的使用每台机器的带宽。不分开的话就是上面我所说的正常的数据复制，会使得主chunk成为吞吐量的瓶颈。

Q：为什么原子记录追加操作是至少一次（At Least Once），而不是确定一次（Exactly Once）？

答：这个问题其实可以看做是gfs有时会出现重复记录或者padding记录，为什么？这个问题，原因就是性能和正确性的权衡，也就是我们所说的是否选择强一致性。而且至少一次我们也可以通过其他的方法来保证对于客户端看到的数据来说是正确的。

最后一个问题是6.824中留给学生的一个问题：

Describe a sequence of events that result in a client reading stale data from the Google File System.
描述一个客户端会从GFS读取到落后数据的时间序列。

答：

  1. 客户端缓存的元数据可能使得读取数据读到了过期数据，因为chunkserver可能下线，并在上线后发现丢失了最新更新，已经不再是这个文件的chunkserver，但是客户端缓存并没有同步更新。[7] 4.5，2.7.1
  2. “影子服务器”，论文中明确提到会有1秒左右的延迟。[7] 5.1.3

下面是6.824对于GFS的小总结：

GFS使用的比较重要的容错技术

  • 操作日志、检查点。
  • chunk之间的主备备份。
  • 我们将会在其他系统中也看到这里

哪些在GFS中工作很好

  • 巨大的顺序读写操作
  • 追加写入
  • 巨大的吞吐量
  • 数据之间的容错

哪些在GFS中做的不怎么好

  • master服务器的容错
  • 小文件（master服务器的瓶颈）
  • 多个客户端并发的向同一份文件更新操作（除了追加）

总结

Google的这一系列论文都很优秀，对于我们而言我们要学习的是其设计理念，是对于容错，一致性，和性能的考虑。就这篇文章而言，对我来说感触最深有这几点，数据流与控制流的分离，针对于特化操作（append）的优化（就事论事），性能和强一致性的权衡，即抛弃一致性而选择设计的简洁与性能。GFS论文的发表催生了后来的HDFS，这也才有了Hadoop的产生，可以说Google亲手开启了大数据时代的大门，对于我们而言着一系列文章实在是值得学习的。

这篇文章其实是让我感到最五味成杂的一篇文章，在写下这篇文章之前已经看了4遍，前三遍都是不得要领，还花了快二十个小时，每次看完都觉得收效甚微，心里实在是不怎么好受，遂放弃去做了别的事情。终于在6.824的第三课中重拾勇气，再次带着问题读了一遍，才算是有所收获，并写下了这篇文章。好好学吧，路漫漫其修远兮，吾将上下而求索。

在这里插入图片描述

参考:

  1. 博文《Google File System 总结》
  2. 博文《GFS小结》
  3. 博文《GFS阅读总结》
  4. 博文《gfs原理》
  5. 博文《Lease(租约)以及在GFS文件系统中的作用》
  6. 知乎 https://www.zhihu.com/question/20485173
  7. 论文《The Google File System》