QFS [VLDB‘13] 论文阅读笔记

原论文：The Quantcast File System (VLDB’13)

QFS简介及技术要点

QFS（Quantcast File System）是由Quantcast开发的一个高效、可扩展的分布式文件系统，旨在提供与Hadoop分布式文件系统（HDFS）兼容的替代方案。QFS是用C++编写的，并且与Hadoop MapReduce插件兼容。它相对于HDFS提供了多项效率改进，包括通过纠删码机制而不是副本策略来节省50%的磁盘空间，写入吞吐量提高一倍，更快的名字节点，支持通过并发追加特性进行更快的排序和日志记录，比hadoop fs命令行客户端更快的本地命令行客户端，以及全局反馈指导的I/O设备管理。QFS自2011年以来已经在生产环境中得到广泛应用。

QFS的一些关键技术要点：

纠删码：QFS使用Reed-Solomon纠删码代替传统的三重复制策略，通过默认的6+3配置（每六个数据块加三个奇偶校验块），实现了与3x复制相当的或更好的容错能力，同时大幅减少了所需的存储空间。
存储效率：QFS通过纠删码节省了50%的存储空间，这意味着在现有的集群上可以存储两倍的数据量，或者在新建集群时节省50%的存储成本。
性能提升：QFS提供了更高的写入吞吐量，因为它需要写入的原始数据量减少了一半。此外，QFS还提供了更快的名字节点和命令行客户端。
并发追加特性：QFS支持通过高可扩展的并发追加特性进行分布式排序和日志记录，这对于大数据处理工作负载来说是一个重要的优化。
设备管理：QFS实现了全局反馈指导的I/O设备管理，通过集中监控设备队列大小来避免慢速设备的影响。
兼容性：QFS与Hadoop插件兼容，可以从HDFS轻松迁移数据到QFS，只需执行hadoop distcp命令即可。
生产环境应用：Quantcast自2011年以来一直在生产环境中使用QFS，并依赖于多个QFS实例来存储日志数据、MapReduce输入/输出数据以及其他类型的数据。
未来发展：QFS的开发路线图包括实现高可用性的名字节点、增强的联邦能力和安全认证。

QFS的设计和实现针对大数据工作负载进行了优化，特别是在处理大规模、顺序的数据块方面。作为一个开源项目，QFS不仅为使用Hadoop的组织提供了一个高效的存储解决方案，而且还为那些通过其他方式读取和写入大型数据块的环境提供了潜在的好处。

原论文阅读

1. INTRODUCTION

大数据处理的挑战：处理大数据本质上是一项大规模的冒险活动，它可以为组织创造巨大的机会，但也需要大量的硬件资源，这反过来又需要大量的资本和运营投资。
Hadoop和HDFS的局限性：Apache Hadoop通过采用数据局部性原则来最大化硬件的使用，但由于集群内部的数据传输速度较慢，Hadoop努力将数据处理代码发送到数据所在的位置，而不是移动数据。Hadoop分布式文件系统（HDFS）采用了3-副本策略来实现容错，但这使得存储开销很大。
硬件进步带来的优化可能性：随着硬件技术的发展，如10 Gbps网络的普及和核心网络交换机带宽的提升，以及其他硬件资源的进步，为文件系统提供了新的优化可能性。
QFS的设计选择：QFS放弃了数据局部性原则，依靠更快的网络将数据传输到需要的地方，并优化了存储效率。QFS采用了Reed-Solomon纠删码机制代替3-副本策略，通过默认的6+3配置，实现了与3-副本策略相当的或更好的容错能力，同时节省了50%的存储空间。
QFS的性能优势：QFS不仅在存储空间上节省了一半，而且写入速度提高了一倍。此外，QFS还提供了更快的名字节点、C++编写的客户端库、支持分布式排序和日志记录的并发追加特性、比Hadoop fs更快的命令行客户端，以及全局反馈指导的I/O设备管理。
QFS的兼容性和开源：QFS与Hadoop插件兼容，可以从HDFS轻松迁移数据到QFS。QFS完全开源，并在Apache许可下提供。

2. QFS ARCHITECTURE

在这里插入图片描述

2.1 Erasure Coding and Striping

在这里插入图片描述

纠删码的作用：纠删码使QFS不仅能够减少存储量，还能加速MapReduce工作负载中常见的大量顺序写入模式。此外，纠删码对于快速运行大型作业并在不重新执行Map任务的情况下容忍硬件故障至关重要。
Reed-Solomon编码：QFS使用Reed-Solomon 6+3编码，即每六个数据块加上三个奇偶校验块。这种编码方式在物理存储上的表现是，原始数据被条带化分布在六个数据块和三个奇偶校验块上。
数据条带化过程：QFS客户端将数据条带（通常是64 KB大小）收集到六个1 MB的缓冲区中。当缓冲区填满时，客户端计算出额外的三个奇偶校验块，并将这九个块发送到九个不同的分块服务器上，通常是一个本地服务器和另外八个位于不同机架上的服务器。
读取和重建数据：当客户端需要读取数据时，它会请求包含原始数据的六个分块。如果一个或多个分块无法检索到，客户端将获取足够的奇偶校验数据来执行Reed-Solomon算法并重建原始数据。可以容忍同时丢失三个分块；如果任意六个分块保持可读，则请求成功。
故障组：为了最大化数据可用性，集群必须被划分为故障组。每个故障组代表具有共享物理依赖性的机器，例如电源电路或机架交换机，因此它们更有可能同时故障。在创建使用Reed-Solomon 6+3编码的文件时，元数据服务器会尝试将九个分块分配到九个不同的故障组中。

2.2 Failure Groups

故障组的定义：故障组是指具有共享物理依赖性的机器的集合，例如连接到同一电源电路或机架交换机的服务器。这些机器因此更有可能同时发生故障。
故障组的作用：在创建使用Reed-Solomon编码的文件时，QFS的元数据服务器会尝试将数据和奇偶校验块分配到不同的故障组中，以提高数据的容错能力。
故障组的数量：Reed-Solomon 6+3编码需要至少九个故障组来保证数据的可用性。即使有一个故障组离线，系统仍然能够保持完整的九个数据和奇偶校验块用于写入。随着故障组数量的增加，系统能够更好地处理更多的故障，并且能够更均匀地分布数据，减少单个故障组过快填满的风险。
故障组的划分：在较大的集群中，通常使用机架作为故障组。对于较小的设置，每台机器可以作为自己的故障组。故障组的概念有助于QFS在集群中更有效地分配数据，同时在发生故障时提供更好的数据保护。

2.3 Metaserver

元数据服务器的作用：QFS的元数据服务器负责维护整个文件系统的目录和文件结构，但不存储数据本身。它为每个文件维护一个块列表，这些块存储数据并记录它们在集群中的物理位置。元数据服务器处理客户端请求，代表客户端创建和修改目录和文件结构，指引客户端到块服务器，并管理文件系统的整体健康状态。
内存中的元数据：为了性能，元数据服务器将其所有数据保存在RAM中。当客户端修改文件和目录时，元数据服务器会原子性地记录这些变化，同时更新内存和事务日志。
定期快照：元数据服务器定期通过fork操作来转储整个文件系统映像到一个检查点。在Linux系统上，由于fork操作的写时复制（copy-on-write）行为，这一过程使用额外的RAM较少。
容错和恢复：在服务器崩溃的情况下，元数据服务器可以从最后的检查点和随后的事务日志中重新启动。当前实现中，元数据服务器是单点故障，但对于Quantcast的批处理工作负载来说，这不是问题，因为它可以容忍更多的停机时间。
高可用性计划：QFS计划实现高可用性元数据服务器解决方案，使QFS能够在实时环境中保证可用性。
块分配策略：元数据服务器根据集群中所有I/O设备的队列大小和可用空间动态决定分配新块的位置，以保持磁盘均匀填充和繁忙。它主动避免有问题的磁盘，这些磁盘通常具有较大的I/O队列。
空间重新平衡和重新复制：QFS持续重新平衡文件，以在所有设备上保持预定义的平衡度量。重新平衡过程在磁盘填充超过上限阈值时发生，并将块移动到空间利用率低于下限阈值的设备上。
维持冗余：元数据服务器持续监控冗余并重新创建丢失的数据。对于复制的块，这意味着复制一个健康的副本。对于纠删码的块，这意味着读取六个相应的块并运行Reed-Solomon编码（对于丢失的奇偶校验块）或解码（对于丢失的原始数据块）。
块驱逐：驱逐是将块服务器上的数据重新创建到其他地方的请求，以便可以安全地关闭其机器，例如进行维修或升级。元数据服务器通过RS恢复加速驱逐过程，允许快速关闭机器，以牺牲更大的网络负载为代价。
休眠：对于快速维护（例如操作系统内核升级），块不会被淘汰。相反，元数据服务器被告知块服务器目录正在休眠。这将设置一个30分钟的窗口，在这段时间内，元数据服务器不会尝试复制或恢复正在升级的服务器上的数据。

2.4 Chunk server

分块服务器的职责：每个分块服务器在本地文件系统上以文件形式存储分块（Chunks）。分块服务器接受来自客户端的连接，以便读写数据。它在读取过程中验证数据的完整性，并在永久性I/O错误或校验和不匹配的情况下启动数据恢复。
写入验证和恢复：对于复制文件，分块服务器还协调同步写入到串联的副本分块服务器。它在本地写入数据的同时将数据转发到下一个分块服务器，并只有在其余的串联服务器成功写入后才报告写入成功。

2.5 Interoperability

与Hadoop的兼容性：QFS与Hadoop插件兼容，这意味着在Hadoop环境中运行QFS只需要设置适当的绑定到客户端库。QFS实现了Hadoop的FileSystem接口及其C++等效接口，允许Hadoop应用程序无缝地使用QFS作为其存储系统。
数据迁移：从HDFS到QFS的数据迁移是一个简单的过程，可以通过运行一个简单的MapReduce作业来完成，例如使用Hadoop的distcp实用程序。
独立于Hadoop：虽然QFS与Hadoop兼容，但它并不依赖于Hadoop。QFS可以在其他上下文环境中使用，例如作为其他大数据处理系统的存储层。
开源组件：QFS的开源分发包括FUSE绑定、命令行工具和C++/Java API，这些可以在非Hadoop环境中使用，以实现与QFS的互操作性。

3. QFS IMPLEMENTATION

3.1 Direct I/O for MapReduce Workloads

直接I/O的使用：QFS默认使用直接I/O来确保数据确实是以大块连续写入的。这样可以避免内核根据多种本地因素选择块大小，这可能从全局角度来看不是最优的。
确保数据连续性：QFS使用底层主机文件系统的预留空间特性来确保数据很可能以连续的方式写入。尽管内核仍然管理磁盘布局，但QFS通过这种方式优化了数据的物理存储。
预测RAM使用：使用直接I/O可以使得RAM的使用变得可预测。这样，分布式节点（主要运行chunk servers、sorter processes和MapReduce JVMs）的内存占用可以固定，从而可以在避免发生磁盘页面置换（paging）带来风险(可能造成突然性的性能瓶颈和降低集群吞吐量）的情况下，配置它们最大限度地使用可用RAM。
减少缓冲区缓存的RAM使用：直接I/O通过避免缓冲区缓存，减少了因缓冲区缓存而产生的可变RAM使用。这样，元数据服务器可以根据全局I/O设备队列大小的实时知识进行块分配决策，而不会因为缓冲区缓存而延迟。
元数据服务器的决策：QFS的元数据服务器基于全局知识对它管理的所有I/O设备的队列大小进行块分配决策。使用直接I/O可以缩短反馈循环，并保持其大小确定性和反馈驱动的决策及时性。
性能问题的影响：如果启用了缓冲区缓存，当元数据服务器得知特定机器上的I/O变慢时，已经有大量数据被传递到缓冲区缓存中，这将延长性能问题的存在时间。

3.2 Scalable Concurrent Append

并发追加操作：QFS实现了一种并发追加操作，它能够扩展到支持数万个并发客户端同时向同一文件写入。
客户端声明：客户端首先声明它将要写入的块的最大大小，元数据服务器将其指向一个也被其他客户端写入的分块服务器。
动态分块：元数据服务器根据需要创建新的分块，以保持分块大小和同时写入者的数量受到限制，并考虑局部性。
分块中的间隙：由于客户端请求的大小并不总能够精确地加起来等于64 MB，因此创建的分块可能会有间隙。但是，客户端代码知道如何顺序地读取这些逻辑文件。
复制文件的并发追加：目前并发追加功能仅针对复制（而非纠删码）文件实现。

3.3 Metaserver Optimization

B+树表示：元数据服务器使用B+树来表示文件系统元数据，以最小化随机内存访问。这与常规文件系统使用B+树来最小化随机磁盘访问的原因类似。
节点类型：B+树包含四种类型的节点：内部节点、文件或目录属性节点（i-node）、目录条目和分块信息。所有树中的键都是16字节的整数，包括一个4位的节点类型、一个64位的键，该键保存i-node号（目录ID），以及一个60位的子键，保存文件中分块位置的哈希或目录名称的哈希。
键的构造：键的构造方式使得目录条目节点紧随目录属性节点之后，以优化目录列表，而分块信息节点紧随文件属性节点之后，以优化打开和读取文件。使用目录条目名称哈希来避免使用i-node号进行线性搜索，从而优化查找效率。
内存分配：元数据服务器使用自己的池分配器为元数据节点分配内存，以避免许多小的操作系统分配所带来的性能和空间开销。它根据需要使用操作系统分配新的内存池，并且从不释放内存，使得进程占用的内存可以随着文件系统的大小增长，但不会缩小。
线性哈希表：元数据服务器使用排序线性哈希表来根据分块ID查找分块信息，这是分块服务器需要进行的操作。哈希表的实现能够在保持空间、RAM访问和CPU开销最小化的同时，提供从几个条目到五亿条目的常量插入、查找和删除时间。

3.4 Client

并发I/O访问：QFS客户端库被设计为允许从单个客户端并发地对多个文件进行I/O访问。
协议状态机：客户端库由非阻塞的、运行直至完成的协议状态机组成，用于处理各种任务。这些状态机管理与分块服务器和元数据服务器的通信，以及基本的读写、写追加和RS编码读写等操作。
插件式编码：RS编码的读写状态机是作为基本读写状态机的插件实现的，这为将来实现其他编码方案简化了实现。
高度可扩展的应用程序：客户端库的状态机可以直接用于创建高度可扩展的应用程序。例如，Quantsort基数排序器就是直接使用写追加状态机实现的。
元数据操作：文件系统元数据操作，如移动、重命名、删除、状态查询或列表操作，需要与元数据服务器通信，并且由QFS客户端库序列化处理。这些操作会阻塞调用线程，直到元数据服务器响应。
元操作的串行化：由于客户端只能与一个元数据服务器通信，所以并行元数据操作不会更快执行，反而可能为元数据服务器带来不必要的高争用。
客户端实例：如果需要，可以在每个应用程序或操作系统任务进程中创建多个QFS客户端实例。
属性缓存：QFS客户端库实现了文件和目录属性缓存，以减少因冗余属性查找操作而对元数据服务器的负载。
缓冲策略：使用读预取和写延迟策略保持磁盘和网络I/O在合理大小。默认的读预取和写延迟参数基于数据条带大小，以保持磁盘I/O请求在大约1MB左右。
缓冲区优化：缓冲区实现利用了内核中的散布-聚集优化，以最小化缓冲区复制。

4. QFS CLIENT PROTOCOLS

写入协议（复制文件）：
1. 客户端请求元数据服务器分配一个块，指定文件ID和文件内块位置。
2. 元数据服务器创建一个块写租约（如果不存在相应的读租约）。
3. 元数据服务器创建一个新块，并基于机架、主机和负载约束选择分块服务器，然后向选定的分块服务器转发分配请求。
4. 所有分块服务器响应后，元数据服务器返回一个选定的分块服务器列表给客户端。
5. 客户端请求选定的分块服务器分配一个写入ID。
6. 客户端计算数据校验和，并将数据及校验和发送给选定分块服务器列表中的第一位服务器（写主服务器）。
7. 写主服务器接收数据，验证数据校验和、写入ID和写租约。如果成功，它发出相应的块写入操作，将数据转发给托管下一个副本的分块服务器（如果有），并等待其返回写入状态。此过程在所有托管块副本的分块服务器上重复。
8. 写主服务器从同步复制链中的最后一个分块服务器接收到写入状态后，将状态转发给客户端。
9. 如果成功，客户端将状态返回给调用者；否则，从第1步开始重试写入。
读取协议（复制文件）：
1. 客户端获取给定文件ID在文件指定位置托管块副本的分块服务器列表。
2. 客户端获取一个块读取租约。
3. 客户端选择一个托管副本的分块服务器，并对此服务器发出读取请求。
4. 分块服务器从磁盘获取数据，验证校验和，并将响应返回给客户端。
5. 客户端验证数据校验和，如果成功，则将响应返回给调用者。否则，如果有其他可用的分块服务器，客户端会使用另一个分块服务器重试读取。
写入协议（条带化文件，无论是否使用纠删码）：
1. 客户端计算数据和恢复块数据。每个块对应一个单独的条带。
2. 对于每个块，使用上面描述的复制文件写入协议。所有块写入并行发出。如果所有副本（复制因子为1时为单个副本）在写入过程中丢失，客户端可以取消块。元数据服务器将在客户端放弃写租约后安排块恢复。
读取协议（条带化文件，无论是否使用纠删码）：
1. 客户端使用复制文件写入协议并行发出对适当块和条带的读取请求。
2. 如果读取成功，客户端组装响应并返回数据给调用者。如果某个读取失败，客户端发出对奇偶校验条带的读取，并在成功的情况下重新计算丢失的数据。
可靠的并发写入追加协议

并发写入追加协议在高层次上与复制文件的写入协议相似。主要区别在于，当多个写入者向一个块追加数据时，客户端并不知道数据最终会进入哪个块。这个决定最终被推迟到元数据服务器。在正常情况下，同步复制链中的第一个分块服务器（写入主服务器）会做出这个决定并通知元数据服务器。如果写入主服务器不可用，元数据服务器将做出这个决定。在写入追加过程中，每个分块服务器在内存中保存每个客户端/写入ID的最后请求状态。如果发生超时（分块服务器故障或通信中断），客户端可以通过查询同步复制链中的剩余分块服务器来恢复最后一次追加操作的状态。