FAST 2021 Paper 分布式元数据论文阅读笔记整理

背景

Blob storage

• 用来存放大量的文本、图片、视频等非结构化数据

• 包含 EB 级别的数据

• 存储内容大小不一，大小几KB到几MB不等

• 要求低时延

• 使用 Haystack 和 F4

Data warehouse

• 存放用于数据分析和机器学习的数据

• 包含 EB 级别的数据

• 每次读几MB，每次写10几MB

• 要求高吞吐量

• 使用 HDFS

Haystack

【Finding a needle in Haystack: Facebook’s photo storage】

• 主要负责热数据存储。以复制的形式存储数据，以保证持久性和快速读写

• 三大组件：

  • 目录服务器：维护逻辑卷和物理卷的映射关系，维护照片 ID 到逻辑卷的映射，负责负载均衡，决定后续获取数据走CDN还是缓存。

  • 存储服务器：由大量的数据服务器存储数据。 以物理卷的形式保存数据，每个物理卷100GB，物理卷即一个物理文件。 不同存储服务器上的多个物理卷组成逻辑卷，形成副本。

  • 缓存：主要通过缓存系统响应用户请求。Web 服务器请求目录服务器时，生成http://<CDN>/<Cache>/<Machine>/<Logical Volume, Photo> 格式的 URL，Web 服务器依次请求各组件，直到获取数据。

• 主要目标：

  • 高吞吐量、低延迟

  • 容错

  • 低成本

  • 架构简单

F4

如果所有 BLOG 都用 Haystack 存，由于其三备份的实现，在EB量级下，性价比很低。因此提出分而治之的思想，将热、温分开的访问策略：用 Haystack 当做热存储去应对那些频繁访问的流量，用 F4 去响应剩下的不那么频繁访问的 BLOB流量。

根据 Facebook 的实际测试，存在访问频度的热力图，创建时间是影响其变化关键因子，而且温部数据是持续增长的。创建时间小于一天的数据的访问频次大概是创建时间一年的数据的100多倍。根据测试，提出了热数据和温数据的一个界限。

• 主要负责温数据存储，保证容错的前提下尽可能的减小有效冗余倍数，以应对日益增长的温数据存取需求。

• 采用 RS 编码进行冗余编码，利用异或编码解决跨数据中心或者地理位置的出错问题。

HDFS

• HDFS 集群的规模有限，只使用一台机器来存储和服务元数据，单个数据仓库的数据集通常大到超过单个 HDFS 集群的容量。

• 每个数据中心需要几十个 HDFS 集群来存储分析数据，效率低，每个集群都必须知道集群之间的数据放置和移动，相关的数据经常被分割到不同的集群中。

• HDFS 集群中分布数据会产生一个二维的装箱问题，将数据集打包到集群中必须考虑每个集群的容量限制和可用吞吐量。

多租户

• 多租户要求：

  • 租户间共享资源

  • 租户访问控制

  • 租户能够优化性能

• 共享资源：

  • 租户之间提供近似公平的资源共享

  • 租户之间的性能隔离

  • 在应用程序之间弹性地转移资源，以保持较高的资源利用率

  • 区分延迟敏感的请求，以避免被其他请求阻塞

• 访问控制：

  • 租户间访问控制

  • 租户内访问控制

• 优化性能：

  • 根据租户需要，针对不同程序做优化

挑战

Facebook 中的三大在离线存储系统 Haystack、F4 和 HDFS 都是各自独立构建的存储栈。存储热对象的 Haystack 系统，主要对外提供 IOPS 能力，本身对存储空间的要求不高；存储温对象的 F4 对存储空间的要求较高，有很多富裕的 IOPS 能力；不同的 HDFS 业务区别较大，有些注重存储空间而 IOPS 较为富裕，另外一些重 IOPS 而存储空间较为富裕。因此，孤立的存储系统无法最大化资源利用率。

本文方法

本文提出Tectonic，结构简单，用单个系统实现各种用例，避免资源浪费，实现IOPS和存储空间的均衡，满足EB级别，各租户间隔离，共享资源满足各租户的需求。

整体架构包括4个部分：

• Chunk Store：由 storage node 组成

• Metadata Store：由 KV store 和 Filesystem metadata layers 组成

• Client Library：负责编排

• Background services：无状态，维护集群一致性和容错。

Chunk Store

• 扁平化、分布式的对象存储，存储块的数量随存储节点的数量线性增长，可以扩展到存储 EB 级数据。

• 以 chunk 为单位，多个 chunk 组成 block，多个 block 组成 file。对 block 或 file 等更高层次的抽象不敏感的，这些抽象是由客户端库使用元数据存储构造的。将数据存储与文件系统分离，简化了在一个存储集群上为不同租户提供良好性能的问题。这种分离意味着存储节点的读写可以专门针对租户的性能需求，而无需更改文件系统管理。

• 使用 XFS 作为底层文件系统，每个 chunk 与 XFS 中的文件一一对应

• 每个存储节点有 36 个硬盘用于存储块，1TB 的 SSD 用于存储 XFS 元数据和缓存热块。

• 根据租户需要调整存储容量、容错性和性能之间的平衡，使用 RS 编码或复制，块存储在不同的故障域中，由后台服务修复损坏或丢失的块，以保持耐久性。

Metadata Store

将文件系统元数据分解为三层：

• Name layer：实现目录到它的子目录或文件的映射

• File layer：实现文件到 block 列表的映射

• Block layer：实现 block 和 chunk 列表之间的映射

使用 ZippyDB 作为 Metadata Store 之下的 KV 存储，以实现可伸缩性和操作简单性，三层元数据都以 KV 的形式存储到 KV 存储中。

• 可线性扩展、高可用

• 分片是复制的基本单位

• 分片内部是通过 Paxos 来做多副本之间的数据一致性。每个分片的 Paxos 组中的每个副本都可提供读服务，读可以有多种配置，用户如果想获得最高的一致性，可以配置为只从 primary 读。follower 会维护跟 primary 的 log lag，如果超过一定的阈值，就拒绝提供读服务。客户端会维护数据的版本，从 secondary 读的话会带上该数据版本，若secondary 上的数据比客户端的版本更旧，就拒绝提供读服务。

• 单个存储节点使用 SSD 上的 RocksDB 作为单机引擎

• 每个分片上的 Paxos 组中的每个副本都可提供读服务

• 不提供跨分片的事务

• ZippyDB 只提供单个 Shard 内的事务，Tectonic 在单个目录或文件上操作的一致性完全依赖于 ZippyDB 的分布式事务。Tectonic 并不提供跨目录的 move 操作的原子性，也需要业务自己去保证在两个目录之间做 move 操作时不会有其他的并发操作。

分布式 KV 做分片操作的基本单位并不是整个 key，而是 key 的部分前缀。例如 Name layer 中，并不是按照<dir_id, subdirname>整个 key 做分片，而是根据 dir_id 做分片，这样一个目录下的所有元素都位于同一个分片下面，便于做 list dir 等操作或目录内的元数据操作。相应地，同一个文件下面所有的block 的元数据也都位于同一个分片下面。

map 关系是扩展的。在做 KV 抽象时，如果 value 是一个列表，并不是将整个列表作为 value，而是将列表中的每个元素作为一个单独的 KV，同时将真正的 key 作为当前元素的 key 的前缀。这样做的好处是如果 key 对应的内容被修改时，并不需要将整个 value 都读出来。例如一个文件系统中，某个目录下面可能会有百万个文件，如果通过非扩展的方式，那么需要将巨大的一个 value 读出来、修改、写入，这会显著降低文件系统的性能。在扩展模式下，只需要更改某个特定的 KV 对即可。

对每层进行哈希分区，避免热点。在文件系统中，目录操作经常在元数据存储中引起热点。尤其对于数据仓库工作负载，相关数据被分组到目录中，可能在短时间内读取同一目录中的许多文件，导致对该目录的重复访问。Tectonic 的元数据分层方法将名称层与文件和块层分开，自然避免了目录和其他层中的热点。例如，在名称层中，单个目录的直接目录列表总是存储在单个分片中。但是同一目录的两个子目录的列表可能在不同的分片上。在块层，块定位器信息在分片之间哈希，独立于块的目录或文件。在 Tectonic 中，大约有2/3的元数据操作都是针对文件的，Block layer 使用哈希划分的方式来划分分片可以使得热点均匀分散在 ZippyDB 的所有分片中。

缓存密封的对象元数据以减少读负载。Tectonic 允许块、文件和目录被密封，指它的当前孩子元素列表以及元数据无法被修改，并不影响它的孙子元素，只防止在目录的当前层添加对象。密封的文件系统对象的内容不能更改，它们的元数据可以缓存到元数据节点和客户端，而不影响一致性。

Client Library

将 Metadata Store 与 Chunk Store 联系起来，对外提供文件系统功能。

提供单写多读的语义，元数据中维护的有一个写令牌，当执行写入时，查看写令牌是否匹配，避免了多写的复杂性。

Background services

• 维护元数据层之间的一致性

• 修复丢失的数据来维持持久性

• 跨存储节点重新平衡数据：rebalancer，识别需要移动的块，以响应硬件故障、存储容量增加、机架损耗等事件

• 发布关于文件系统使用情况的统计数据

• garbage collector：在删除对象时对其进行标记，而不实际删除，但可能导致不一致

• repair service：协调系统中每个磁盘的块列表到磁盘到块映射来处理实际的数据移动。为了水平扩展，修复服务工作基于每个磁盘的每个块层分片上

共享资源

• 资源分类

  • 临时资源：需求随时变化的资源，包括存储 IOPS 能力、元数据查询能力。这些资源需要细粒度的实时自动化管理，以确保公平共享、租户彼此隔离、资源利用率高。

  • 非临时资源：存储容量，按租户粒度进行管理，每个租户都有一个预定义的严格隔离的容量配额，分配给不同租户的空间没有自动弹性，租户之间的存储容量重新配置需要手动完成。

• 在租户之间和租户内部分配临时资源，临时资源在每个租户中以应用程序组的粒度进行管理，避免租户间工作负载和性能需求不同，减少了管理多租户的开销。

  • 将应用程序分组，称为 TrafficGroups，组内应用对资源和延迟的需求相似，租户负责为他们的每个应用程序选择适当的 TrafficGroup。

  • 将 TrafficGroup 按照对延迟需求进行分级 TrafficClasses，分为延迟敏感应用程序、普通应用程序和后台应用程序（Gold、Silver、Bronze）。

  • 空闲资源在租户内部按照 TrafficClass 优先级进行分配。

通过以上方法保证隔离和高资源利用率，每个租户获得集群的临时资源的一个有保证的配额，该配额在租户的 TrafficGroups 之间进行细分。每个 TrafficGroup 获得其有保证的资源配额，该配额提供租户之间的隔离以及 TrafficGroup 之间的隔离。空闲资源根据 TrafficClass 优先级分配。租户内的任何临时剩余资源都可以在自己的 TrafficGroup 共享，根据 TrafficClass 分配。如果租户内还有剩余资源，也可以将其以同样的方式分享给其他租户的 TrrafficGroup，这样可以保证空闲的资源优先被同一租户的 TrafficGroup 使用，然后再分配给其他租户。

• 全局资源共享：采用速率限制器管理全局资源，通过分布式的计数器追踪最近一个时间窗口中每个租户和 TrafficGroup 上资源需求，实现了一个改进的漏桶算法进行限流管理。传入的请求会增加桶的计数器，之后 client library 检查自己的 TrafficGroup 中的空闲容量，之后检查同一租户中的其他 TrafficGroup，最后检查其他租户。在整个过程中，遵循 TrafficClass 优先级。如 client 发现存在空闲容量，则将请求转发到后端。否则，根据超时时间决定请求被延迟或拒绝。确保了近似的全局公平共享和隔离。

• 本地资源共享：元数据和存储节点也需要对资源进行管理，避免出现本地热点。节点通过一个加权轮循(WRR)调度器提供公平共享和隔离，当 TrafficGroup 超过其资源配额时，该调度器会暂时跳过。另外，存储节点需要确保小的 IO 请求(例如，blob 存储操作)不会因为大的、突发的 IO 请求而出现高延迟。为了防止 Gold 请求被存储节点上 Bronze 的请求阻塞，存储节点使用三种优化来确保高 TrafficClass 请求的低延迟。

  • WRR 调度器提供了一种贪婪的优化，对于来自较低 TrafficClass 的请求，如果在较高 TrafficClass 请求之后有足够的时间完成请求，则可以将其转向较高 TrafficClass。

  • 限制了每个磁盘上运行的非 Gold  IO 的数量。如果有未完成的 Gold 请求，并且非 Gold 请求已达到限制，则非 Gold 请求将被阻止。

  • 磁盘本身重新安排 IO 请求，如果 Gold 请求在磁盘上挂起的时间达到了一个阈值，就会停止调度非 Gold 请求到磁盘上。

• 确保高等级 TrafficClass 请求的低延迟：

  • 如果低等级请求在高等级请求后有充足时间完成，则先处理高等级请求

  • 限制非高等级请求数量

  • 磁盘对请求重新排列，高等级请求挂起时间达到阈值，则先处理高等级请求

访问控制

• 租户间访问控制

  • 遵循通用的安全原则，防止租户访问另一个租户的数据

• 租户内访问控制

  • 基于令牌的授权机制：令牌表明可以访问哪些资源

  • 逐层生成令牌，由下一层进行验证

性能优化

数据仓库写优化：数据仓库工作负载中的常见模式是只写入一次数据，随后多次读取，优先考虑降低写入时间。图3a

• 以 chunk 大小写入，并通过 RS 编码，减少数据的写入量，节省网络带宽以及磁盘IO。

• 异步写入，降低文件写入延迟，由于文件关闭之后才进行读，因此可以保证一致性。

• 通过 quorum writes 减小尾延迟。quorum 模型：假设总共有 N 个数据副本，写时更新 k 个副本，读时读取 N-k+1个副本。 将写的部分负载转移到了读上。在写数据之前发送预订请求，然后将数据块写入到第一个接受预订的节点，避免将数据传输到缺乏资源的节点或超过资源限制的节点。例如，要编写 RS(9,6) 编码的块，客户机库向不同故障域的19个存储节点发送预订请求，比写所需的多4个节点。客户端库将数据和奇偶校验块写入响应预约请求的前15个存储节点。

Blob 存储优化，将许多 blob 存储在日志结构文件中来管理 blob 存储元数据的大小，在日志结构文件中，新的 blob 被追加到文件的末尾。使用从 blob ID 到文件中 blob 位置的映射来定位 blob。图3b、c

• 降低写入延迟：利用 partial block quorum appends 来保证持久、低延迟、一致性的 blob 写。采用三副本的机制，当进行写入时，根据 quorum 的方式写入数据，一旦副本写入到多数磁盘上时，Client Library 确认写成功。为了保证数据数据一致性，block 只能够由创建它的写入器执行追加写操作。

• 提高存储效率：直接对小块进行 RS 编码追加，会导致大量的小 IO，从而导致 IO 效率低。采用三副本机制进行块追加，直到块密封后，进行重编码，即用一次大 IO 替代多次小 IO，从而减少 IO 延迟。

实际部署

EB 级别多租户集群：1250pb 的存储，107亿个文件，150亿个块组成，占快照时集群容量的70%

共享 IOPS 和带宽：含两个租户，blob 存储和数据中心。Blob 存储请求通常较小，受 IOPS 的限制，而数据仓库请求通常较大，受带宽的限制。无论是IOPS还是带宽都不能很好地反映磁盘 IO 的使用情况。使用磁盘时间度量给定磁盘繁忙的频率。如表3，显示了三个每日峰值的数据仓库和 blob 存储的规范化磁盘时间需求，数据仓库的峰值需求都超过了它的供应，而 blob 存储有多余的磁盘时间。通过 Tectonic 对资源进行整合，可以将 blob 存储的剩余磁盘时间用于数据仓库的存储负载峰值，图4a、b。

元数据热点：元数据操作的瓶颈资源是每秒查询(QPS)，实际部署中，每个分片提供 10KQPS。图4c，显示了 Name、File 和 Block 层在集群中元数据分片的 QPS。Name 和 Block 层中的所有元数据分片都低于这个限制。

• 三天的时间中，只有1% Name 层元数据分片达到 QPS 限制，元数据请求中少量未处理的部分，Tectonic 通过回退机制，重新为这部分请求提供了服务，可以成功地处理来自数据仓库的元数据负载的巨大峰值。

• 采用哈希分区的方法，避免了峰值的叠加，如：数据仓库作业经常读取许多名称类似的目录，如果这些目录是范围分区的，则会导致极端的负载峰值。

• 与数据仓库协同设计，减少元数据热点。例如，计算引擎通常使用协调器列出目录中的文件，并将这些文件分发给工人，工人并行地打开和处理文件。如果这样处理，在 Tectonic 中会导致向单个目录分片发送大量的几乎同时的打开文件请求，导致热点。Tectonic 采用协调器将文件 ID 和名称返回给工人，工人直接通过文件 ID 打开文件，无需再次查询。

总结

对Facebook存储系统进行介绍，之前采用多个子系统独自构建存储栈，不同子系统资源需求不同，导致资源没有充分利用。提出Tectonic，用单个系统实现各种用例，避免资源浪费，实现IOPS和存储空间的均衡，满足EB级别，租户间隔离，共享资源等的需求。包括4个部分：Chunk Store，由存储节点组成；Metadata Store，由 KV 存储和文件系统元数据层组成；Client Library，负责编排；Background services，维护集群一致性和容错。详细介绍了各种组件的实现方法。