大数据组件 HDFS 即 GFS 开源实现，用于存储非结构化数据 。上层还有 HBase（Big Table）用于存储结构化数据。再上层就是 MapReduce 计算框架。

GFS 这是这门课里有关如何构建大型存储系统的众多案例学习的第一篇。GFS论文也涉及到很多本课程常出现的话题，例如并行性能、容错、复制和一致性。

GFS论文笔记

背景

  1. 为什么构建分布式存储系统如此困难？

    • 需要大量机器并行来获得高性能 → 数据分割放置，即分片（Sharding）
    • 故障成为常态 → 容错（fault tolerance）
    • 容错的实现 → 复制（replication）
    • 复制造成的问题 → 不一致性（inconsistency）
    • 要得到一致性需要复杂网络交互 → 低性能（Low Performance）

    由此陷入了一个循环。

  2. 不好的设计

    • 首先通过一个简单的例子引入并行产生的问题：

      只有一个服务器S1，客户端C1发起写请求将X设置成1，同时客户端C2发起写请求将X设置成2。C1和C2的写请求都执行完毕之后，客户端C3 和 C4发送读取X的请求，这两个客户端看到的结果是什么？由于不知道请求执行顺序，并不能预测结果。

    • 现实中为了容错，会构建多副本服务器，接下来讲了个糟糕的多副本服务器设计。

      两台服务器，磁盘上都存储了完全一致的key-value表单。完全一致意味着每一个写请求都必须在两台服务器上执行，而读请求只需要在一台服务器上执行。

      C1、C2 同时写 S1、S2，随后如果有C3、C4从S1、S2读，由于不知道两个服务器上写的顺序是否一致，有可能C3、C4读到不一样的数据。

      进行改进，刚开始都只读S1，S1寄了再读S2，在这个转换的前后还是有可能出现读的数据不一致问题。

      当然还可以继续改进，但是会提升系统复杂性降低性能。需要在好的一致性和一些小瑕疵行为之间追求一个平衡。

GFS 详解

在此之前应该先看 GFS 论文，能加深理解。

设计目标和特征

  • GFS设计目标
    • 大型的，快速的文件系统。（Big, Fast）
    • 全局有效，适合各种上层应用。（Global）
    • 文件分片，为了获得大容量和高速的特性。（Sharding）
    • 故障自动恢复。（Automatic Recovery）
  • GFS 其他特征

    • 只在一个数据中心运行，并没有将副本保存在世界各地。（Single Data Center）

    • 不面向普通的用户，Google内部使用的系统（Internal Use）

    • 在各个方面对大型的顺序文件读写做了定制。（Big Sequential Access）

      为TB级别的文件而生，并且GFS只会顺序处理，不支持随机访问，它有点像批处理的风格。GFS并没有花费过多的精力来降低延迟，它的关注点在于巨大的吞吐量上，所有单次操作都涉及到MB级别的数据。

    • 论文提出了一个当时非常异类的观点：存储系统具有弱一致性也是可以的。GFS并不保证返回正确的数据，目标是提供更好的性能。

      尽管GFS可能会返回错误的数据，但是可以在应用程序中做一些补偿。例如论文中提到，应用程序应当对数据做校验和，并明确标记数据的边界，这样应用程序在GFS返回不正确数据时可以恢复。

    • GFS 使用单个Master节点并能够很好的工作。在一些学术论文中，一般都是容错的、多副本、自动修复的多个Master节点共同分担工作。

GFS Master 节点

GFS中Master是Active-Standby模式，所以只有一个Master节点在工作。Master节点保存了文件名和存储位置的对应关系。除此之外，还有大量的Chunk服务器，可能会有数百个，每一个Chunk服务器上都有1-2块磁盘。这些Chunk每个是64MB大小，一个文件由多个 chunk 组成。

Master节点用来管理文件和Chunk的信息，而Chunk服务器用来存储实际的数据。两类数据的管理问题几乎完全隔离开了。

  • Master 节点主要保存两个表单：

    • 文件名 → Chunk Handle（或者叫 ID）数组的对应。（磁盘中有备份）
    • Chunk ID → Chunk数据的对应。Chunk数据又包括：

      • 这个chunk及其副本所在Chunk服务器的列表。（磁盘中无备份，因为每次 Master 重启都会与所有 chunk 服务器通信得到此数据）

      • Chunk当前的版本号。（磁盘中一般有备份，需看GFS 如何工作）

      • 哪个Chunk服务器持有主Chunk。（磁盘中无备份，因为可以等租约到期重新分配）

        所有对于Chunk的写操作都必须在主Chunk（Primary Chunk）上顺序处理，主Chunk是Chunk的多个副本之一，具体见论文的租约部分。

      • 主Chunk的租约过期时间，只能在特定的租约时间内担任主Chunk。（磁盘中无备份）

    以上 Master 中的数据都存在其内存中，读数据都在内存读。

    为了不丢失数据，有部分会存在硬盘里（以上已标出），而且Master会在磁盘上存储log，每次有数据变更时磁盘的log中追加一条记录，并生成CheckPoint（类似于备份点）。写磁盘速率有限，所以要尽量少。维护 log 而不是数据库的原因是 log 都是追加写入，速度更快。

    Master节点故障重启时，会从log中的最近一个checkpoint开始恢复，再逐条执行从Checkpoint开始的log，最后恢复自己之前的状态。

GFS 读文件

  1. 客户端想读文件，需要将文件名和从文件某个位置读取的**偏移量（offset）**发送给 Master。
  2. Master节点会从自己的file表单中查询文件名，得到Chunk Handle的数组。因为每个Chunk是64MB，所以偏移量除以64MB就可以从数组中得到对应的**Chunk **Handle。
  3. Master再从Chunk表单中找到存有Chunk的服务器列表，并将列表返回给客户端。
  4. 客户端可以从这些Chunk服务器中挑选一个来读取数据。GFS论文说，客户端会选择一个网络上最近的服务器。
  5. 客户端会缓存Chunk和服务器的对应关系。当再次读取相同Chunk数据时，就不用一次次的去向Master请求相同的信息。
  6. 客户端与选出的Chunk服务器通信，将Chunk Handle和偏移量发送给那个Chunk服务器。
  7. Chunk服务器本身是 Linux 文件系统，Chunk文件会按照Handle 命名。它根据文件名找到对应的Chunk文件，之后从文件中读取对应的数据段，并将数据返回给客户端。

如果客户端想读取的文件超过了 Chunk 边界，GFS 通过一个库将这个请求转换为多个对 Master 的请求，Master 回应这几个 Chunk 的位置。

总之就是应用程序只需要确定文件名和数据在整个文件中的偏移量，GFS库和Master节点共同协商将这些信息转换成Chunk，此过程对客户端透明。

GFS 写文件

从应用程序的角度来看，写文件和读文件的接口非常类似，它们都是调用GFS的库，即细节对客户端隐藏。

  1. 客户端调用写文件借口，告知文件名、buffer中的数据。实际上是先向Master节点发送请求：我想向这个文件名对应的文件追加数据，请告诉我文件中最后一个Chunk的位置。
    • 如果 Master 发现这是新文件，会创建新的 Chunk Handle和新的 Chunk 数据，并分配三个 Chunk 服务器。
  2. Master 找到主 Chunk，如果没有，需要先指定一个最新的副本为主Chunk。版本号与 Master 一致的即为最新副本。
    • 读文件可以从任何最新的Chunk副本读，但是写文件必须通过Chunk的主副本（Primary Chunk）来写入。
    • Master 指定 Primary Chunk 即租约过程，租约有个期限（60秒），到期后即失去主 Chunk 身份。租约的作用就是将与客户端交互、更新Chunk的能力授权给主 Chunk 服务器，客户端不需要再与 Master 交互。租约可以确保没有多个 主 Chunk 出现。
    • Master 每次指定新的主Chunk后，就会版本号加一并写入磁盘，然后通知 Chunk 服务器谁主谁备，并告知最新的版本号（先写磁盘还是先通知Robert教授也不是很清楚），Chunk 服务器更新版本号并保存到磁盘。写入磁盘是为了故障恢复。
    • Master 为何不直接将 Chunk 最大版本号作为最新版本号？因为有可能拥有最新版本号的 Chunk 故障未恢复。Master 定期询问 Chunk 持有的版本号，如果没找到和 Master 一致的版本号，Master 会等待不响应客户端请求。
    • Master 可能在租约时崩溃，重启后有Chunk上报一个比本地更大的版本号，Master 会知道租约时发生了错误，选这个最大的版本号作为最新版本号。
  3. 接下来客户端直接与Primary Chunk 服务器交互，且会缓存 Primary 信息。客户端将数据发给Primary Chunk 服务器，主 Chunk 链式发送给其他备服务器，Chunk 服务器先将数据写到临时位置，此时还不会立即追加到文件中。直到所有 Chunk 服务器返回 ACK 确认有了数据，客户端才会通知主 Chunk 服务器，通知所有服务器追加写入Chunk末尾。
    • 主 Chunk 开始收到数据后立即发送给最近的 Chunk 服务器，形成发送链。
  4. 追加命令执行后，Chunk 服务器会返回yes 给主 Chunk，全都收到后主 Chunk 通知客户端写入成功，如果有 Chunk 服务器失败没返回 yes，主 Chunk 返回客户端写入失败，客户端应重新发起整个过程。
    • 部分 Chunk 写入成功，无需进行处理，重新发起后继续追加，允许冗余数据。
    • Master 发现无法联系到 Primary，会等待租约到期再指定新的 Primary，防止出现多个 Primary的**脑裂（split-brain）**情况

GFS 一致性

由于可能有追加数据失败问题，客户端重新发起写入（如B），注意写入C都是在相同的偏移量处。也可能客户端故障未重新写入（如D），在三个 Chunk Server 对应 Chunk 上的数据可能是如图所示：

此时客户端读文件可能会读到不同的结果。应用程序需要容忍读取数据的乱序。如果应用程序不能容忍乱序，应用程序要么可以通过在文件中写入序列号，这样读取的时候能自己识别顺序，或者对于特定的文件不要并发写入。

如果想要将GFS升级成强一致系统，举一些你需要考虑的事情：

  • 让Primary来探测重复的请求，确保B不会在文件中出现两次。
  • 不允许Secondary忽略Primary的请求而没有任何补偿措施，例如永久故障时将Secondary移除。
  • 两阶段提交（Two-phase commit）。直到Primary确信所有的Secondary都能执行数据追加之前，Secondary 不能响应写请求。
    1. Primary向Secondary发请求，要求其执行某个操作，并等待Secondary回复，这时Secondary并不实际执行操作。
    2. 所有Secondary都回复说可以执行，Primary才回复好的，所有Secondary执行这个操作。
  • Primary在确认所有的Secondary收到了请求之前崩溃，一个Secondary会接任成为新的Primary，需要显式的与其他Secondary进行同步，以确保操作历史的结尾是相同的。
  • Secondary之间可能会有差异，要么需要将所有的读请求都发送给Primary，要么Secondary也要一个租约系统，就像Primary一样，这样就知道Secondary在哪些时间可以合法的响应客户端。

和 GFS 允许副本不一致不同，在lab2和lab3中设计的系统，其中的副本是同步的，需要完成以上所有特性。

GFS 它最严重的局限可能在于，它只有一个Master节点，会带来以下问题：

  • Master会耗尽内存来存储文件表单。
  • Master CPU 和写磁盘能力有限。
  • 应用程序发现很难处理GFS奇怪的语义，即上面说的副本数据不一致问题。
  • GFS论文中，Master节点的故障切换不是自动的。