CubeFS 大视野｜万亿级元数据路由设计与优化

文件系统就是管理文件的组织及访问的系统。

文件系统一直是发展统一的。从出生至今，无论单机文件系统还是分布式文件系统，都使用两种最基础的概念 inode 和 dentry（可参阅前序文章，CubeFS 大视野 | 分布式文件系统的历史演进）。

首先应意识到各现实的文件系统没有高级、低级之分，只有实际场景的功能选择；比如早期万行代码的 ext2 文件系统依然在使用，如要支持大文件、校验、容灾、快照等功能就需要选择 xfs、Btrfs、ZFS 等等。

本文主要探讨 CubeFS 服务于多租户、多名字空间、海量文件时，元数据的高效路由方案（可参阅前序文章，CubeFS存储技术揭秘-元数据管理）

目前 CubeFS 是基于 Inode Range 路由方案。每个 Volume 由 Master 分配多个 MP，Volume 之间的 MP 相互独立，每个 MP 管理该 Volume 下的固定一段 inode，关键在于每个 MP 还需对应一个 Raft Group。

图 1，CubeFS inode 分区

图 2，CubeFS dentry 分区

可优点化

• 在单集群大规模 Volume 场景下，集群中会存在大量的 MP 以及其 Raft Group。

• 目前大目录限制了 2000W 的 dentry，因为单分区下子目录的 dentry 树无法分裂，虽然该文件数量满足大多数场景，但如果在对象存储这类扁平化平铺元数据场景下，不能满足超大规模目录项，从而引发场景使用限制及性能问题。

• 对 S3 场景的元数据路径查找，需要逐层查找，效率较低。

• 数据聚合簇极小。每个 MP 只能聚合自身管理的 inode 下相应 Volume 的小 IO。

图 3，Key Range 分区方案

分布实例

假设集群中存在如下 3 个 Shard，Range = Space + InodeID：

表 1，Key Range Shard 分布

元数据路由分布如下：

表 2，Key Range 元数据路由分布

• Key Range 分区模式下，写入的 Key 和 Shard Key 相同，即通过范围索引。

• 按照 Space + Inode 拼接目录项名作为 Shard Key；相邻的文件就会落于同一个 Shard 上，以此实现目录 lookup/readdir 等操作的亲和性，同时尽可能避免同一目录下的跨分区的事务操作。

• 父目录的元数据和其下 dentry 项存放在同一 Shard 上，能保持 readdir 等操作的局部性。

• 不同 Space 有不同的 Shard Key 前缀，因此可以实现不同 Space Shard 的独立性。

优缺点

优点

1. Key Range 分区方案是分层管理模式。底层的 Shard 扩容与上层 Space 没有关联，即是说 Raft Group 数量只跟集群数据规模有关，和上层租户数量无关。

2. 支持目录亲和性放置策略，单目录下的文件可以组织到一个或多个相邻 Shard 分区上，提升 lookup/readdir 性能。

3. 多 Space 数据可共享同一个 Shard，提升跨 Space 级的小 IO 聚合簇能力。

4. 支持元数据扁平化组织，即 1 次查找即可获取相应元数据；也可扩展为上述的层级命名空间结构用于支持文件系统目录树语义。

5. 保持二级索引全局有序，可实现类似：where a >= 10、where b like "123*" 等局部搜索语义，无需遍历所有分区数据。

缺点

采用 Key Range 分区在集群初始化时默认只有 1 个 Shard 分区，需要通过不断分裂来进行扩展，冷启动时可能会成为瓶颈。

预分区

自然的 Range 分区虽具有数据局部放置性特点，但无法兼顾数据负载的均衡性。即集群初始化后还需要依赖数据写入来进行分裂、扩容，在冷启动、数据迁移场景会引入读写瓶颈。

引入分区预分裂方案即预创建分区；为 Space 创建特定的 Range 前缀来实现不同 Space 数据的预分配和打散。

比如集群初始化时预创建以下分区：

表 3，预分区 Shard 分布

Range Prefix 为固定前缀，Space 的分布如下：

表 4，预分区的 Space 分布

文件系统关键流程

文件查找

比如查找 表 2 中已有文件 space1/b/f2。

• 先查找根目录 space1/1，在 shard 1 中获取 (space1/1, b) 对应的元数据，得到 space1/b 的 InodeID 为 3。

• 接下来查找目录 space1/b 下 (space1/3, f2) 元数据，得到 space1/b/f2 InodeID 5。

• 最后在 shard 2 中查找 space1/5 的元数据，即目标文件对应的 Inode。

文件创建

创建操作，主要涉及两个元数据变更：

• 为创建新的文件 inode 元数据

• 更新其父目录的元数据（dentry，links，mtime 等）。

由以上路由规则，子文件/目录的 dentry 项和其父目录元数据基本保持在同一个分区中；因此可使用分区插入更新原语，类似：

对于超大规模目录，该目录的 dentry 项可能会跨多个相邻分区；更新操作如需跨分区，则通过分布式事务保证原子性和强一致性。

文件删除

删除和创建流程一致，均可通过单分区上的更新原语。

目录列举

单目录列举只需在一个分区内即可获取到所有子文件/子目录的 dentry 元数据；可通过递归列举子目录。若还需文件的 inode 元数据，则可向各文件所在的分区发起读取请求。

重命名

rename 操作分为同目录、跨目录：

• 同目录 rename 操作，由于 inodeID 保持不变，只需单分片更新原语即可。

• 跨目录 rename 操作，由分布式事务保障强一致性。

硬链接

海量数据场景文件 inode 和 dentry 大概率不在同分区，则需要通过分布式事务保证原子性和一致性。

• 操作文件 inode 分区，将文件元数据的 link++

• 在父目录分区中新增 dentry 项

第二个阶段可用分区更新原语：

软链接

• 创建新的文件的 inode，内容指向原文件

• 在父目录分区中新增 dentry 项，可用分区更新原语

分区分裂与迁移

分裂

• 随着同一分区的数据不断写入，当分区数据达到一定阈值（默认 1G）或触发服务器资源告警时会进行分裂。

• 分裂时要进行数据分布和热点探识，决策出分裂点。比如 [a, z) 分区中数据分布中位线在 d 附近，则将分裂为 [a, d) 和 [d, z) 两个分区。

• 分裂策略上设定优先级，优先 Space 之间进行分裂，其次再在 Space 内部进行分裂。

• Range 段内分裂决策可以通过两种方法计算：

  通过迭代器进行整体数据统计，遍历出数据中位点，决策出 SplitKey 的位置（参考 CockroachDB 和 TiKV Size Split 做法）。

  另一种则是近似计算，依赖底层 KV 引擎的实现。比如采用 RocksDB 时，定义相应的 table property collector 在每个 SST File 创建时收集其分布和大小，可近似统计出相近范围内的数据，用于 SplitKey 的判断和决策。

• 多分区数据存储在同一个 Rocksdb 实例上，分裂时按照数据量和热点进行分割；申请新的分区并修改相应范围即可完成分裂操作，无需迁移数据。

迁移

当服务节点上分区数量较多、负载较高时会触发迁移操作，数据迁移以分区为粒度。

• 在分区 Raft Group 添加新目标节点

• 以快照方式传输全量数据，并应用 WAL 同步增量数据

• 触发 Raft 切主，移除旧节点并完成数据清理

合并

对于数据量下降的分区，可通过定期巡检触发分区合并。

• 合并前选择相邻的 Range 分区进行，将多个相邻的 Range 迁移到同一组节点上

• 合并时只需修改分区 Range 范围合并为一个即可

• 合并后再删除旧 Range 及其下的数据

分布实例

假设集群中存在如下 3 个 Shard，Range = hash(Space + InodeID)：

表 5，Hash Range Shard 分布

元数据路由分布如下：

表 6，Hash Range 元数据路由分布

• Hash 分区模式，同目录下的元数据和 dentry 项均在同一个分区，实现数据的局部放置。
  

• Hash 分区模式支持预分区，有更好的数据均衡性。

优缺点

优点：

1. 大部分优点与优化【方案一】相似，但实现和管理更加简单。

2. 同目录的元数据都在同一分区。

3. 数据分区分裂更加简单；Range 由 Hash 组成，分裂时按照中位数一分为二即可。

缺点：

1. 单一 Hash 分区导致大目录 dentry 项只会存在于一个分区上，无法进行分裂。

2. 海量 Space 场景下，单个分区会承担集群种几乎所有 Space 的元数据，导致每个分区都有海量 Space 数据上报问题。

定制 Hash 分区

针对【缺点・ 2】，可为某类 Space 指定 Hash 分区，将该 Space 打散到固定一些分区上，进而优化分区数据上报过多的问题。

表 7，定制 Hash Range 元数据路由分布

分布实例

假设集群中存在如下 3 个 Shard，Range = {hash(space + InodeID), hash(name)}：

表 8，组合 Hash Range Shard 分布

元数据路由分布如下：

表 9，组合 Hash Range 元数据路由分布

优缺点

优点：

1. 较之【方案二】，对超大目录可分裂为多个相邻的分区，解除大目录存储限制。

缺点：

1. 当触发分区分裂时需要判断分裂点，即按照 Key1 还是 Key2 分裂。

2. 二级索引不支持全局有序，某些条件查询需要查询二级索引所在的所有节点分区。

工程化的文件系统依然有不断迭代优化空间，本文针对 CubeFS 现状，在普通业务、大规模 Space 场景下对元数据路由的探讨。【方案三】组合 Hash 分区，通过预分区和定制 Hash Key 方式提供数据均衡与局部性放置；可分裂的二级索引保证超大目录的平铺使用场景。在某些特殊使用场景该方案依然不够完善，欢迎阅者分享并一起探讨。

参考文献

2、CubeFS 大视野 | 分布式文件系统的历史演进

3、CubeFS存储技术揭秘-元数据管理

作者介绍

Jie Shen，CubeFS Maintainer，当前在 CubeFS 项目参与 Blobstore 的设计与研发。

CubeFS 于2019年开源并在 SIGMOD 发表工业界论文，目前是云原生计算基金会 (CNCF) 托管的孵化阶段开源项目。作为新一代云原生分布式存储平台，兼容 S3、POSIX、HDFS 等协议，支持多副本和纠删码引擎，提供多租户，多 AZ 部署、跨区域复制等特性；适用于大数据、AI、容器平台、数据库及中间件存算分离，数据共享、数据保护等广泛场景。