RFC-0136：Fxfs

RFC-0136：Fxfs
状态已接受
区域
  • 存储
说明

对新 Fuchsia 文件系统的简要概览。
Gerrit 更改
作者
审核人
提交日期（年-月-日）2021-09-30
审核日期（年-月-日）2021-10-13

修改此 RFC

修改 RFC 元数据

摘要

Fxfs 是存储团队正在开发的一种新的 Fuchsia 文件系统。此提案概述了 Fxfs 的动机和更高级别的设计决策。

设计初衷

Fuchsia 现有的可变文件系统 Minfs 存在一些限制，这意味着我们很难在未来添加所需的功能并实现性能目标。Fxfs 正在开发中，有望取代 Minfs 来实现这些目标。

有些功能几乎肯定需要，例如：

  • 完整的读写 mmap 支持
  • 支持扩展属性
  • 严格的配额超限处置方式
  • 文件系统通知（特别是 inotify 支持）
  • 文件锁定（特别是 flock 支持）

我们可能最终还需要其他功能：

  • 内置加密功能 - 文件级加密
  • 快照支持
  • 文件克隆
  • 支持多个音量
  • 压缩支持

我们还希望实现与其他操作系统相当的文件系统性能。在所有考虑因素中，这可能是最难实现的一点，也是需要花费最多精力的一点。

所有文件系统都需要考虑以下基本文件系统目标：

  • 低写入放大率有助于最大限度地减少闪存磨损。
  • 高效的空间使用率 - 例如，最大限度地减少小文件的浪费。
  • 迁移的简易性。

实现这些目标所需的大部分工作将在存储堆栈和内核的其他位置完成，本文档不会介绍这些工作；此 RFC 仅侧重于文件系统实现 Fxfs。

虽然 Fxfs 非常适合在闪存设备上运行，但其设计中没有任何内容会阻止其在旋转存储设备上使用，我们预计 Fxfs 在旋转存储设备上也能正常运行。

利益相关方

辅导员：

审核者：abarth@google.com、brettw@google.com、palmer@google.com

已咨询：

我们咨询了 Fuchsia 的安全团队，以解决与加密相关的问题。

共同化：

本地存储团队对 Fxfs 进行了详细的设计审核。

设计

日志结构合并树

您可以在 Wikipedia 上找到有关日志结构合并 (LSM) 树的概览。Fxfs 使用 LSM 树来提供在 Fxfs 中使用的持久性键值数据结构。

LSM 树具有一些吸引人的属性：

  • 写入设备的层是不可变的，这意味着：
    • 访问这些层时不需要锁定。
    • 限制某些类别的 bug - 如果不修改图层，则损坏图层的可能性会更小。
    • 可能更易于调试问题 - 如果各层没有变化，则活动部件更少。
    • 这样可以更轻松地支持压缩，并且可以在后台应用更积极的压缩来节省空间。
  • 变更以批量方式按顺序写入，而不是零散写入，这是一种更适合闪存的写入模式，可减少写入放大并避免不必要的擦除周期。这种写入模式也恰好适合旋转存储设备。
  • 快照支持比其他支持更容易失效。
  • 允许将写入所需的工作推迟到空闲时间（许多设备都有相当长的空闲时间）。这在实践中意味着，可以在设备未被使用时（即最方便的时间）进行压缩。
  • 压缩可以在后台完成，从而节省时间来处理更重要的事情。
  • 重写元数据是一项经过充分测试的集成文件系统操作，可简化格式迁移。在压缩期间，可以写出完全不同的图层格式。

不过，也有一些缺点：

  • 空间管理难度更大 - 所有操作都需要元数据空间，即使是删除操作也是如此，因此需要谨慎预留空间。请注意，支持快照的其他文件系统也会出现此问题，因此它并非 LSM 树独有的问题。
  • 如果图层数量较多，读取速度会变慢。我们可以采取一些缓解措施来解决此问题，例如使用 Bloom 过滤器，而压缩会通过合并层来降低此成本。

值得注意的是，即使选择了 LSM 树，如果发现混合方法有意义，我们仍然可以选择使用可变持久层格式。

Fxfs 的 LSM 树实现对应的 API 需要一个合并函数，用于指定如何合并记录。

Fxfs 的内存中层由高效且并发友好的数据结构（目前为跳跃列表）表示。

对象存储

Fxfs 由对象存储区的层次结构组成。对象存储提供由对象 ID（64 位无符号整数）键控的类文件 API。支持简单命名空间功能（即目录支持或类似功能），但不是强制性的；可以使用对象存储，只需使用对象 ID 引用对象即可。对象存储空间将其元数据保留在持久性键值数据结构（LSM 树）中。元数据包含典型的文件信息，例如对象的大小和映射到设备偏移量的范围。

Fxfs 的 LSM 树使用对象存储区来存储其持久层，这会产生循环依赖关系：对象存储区使用 LSM 树来存储其元数据，然后 LSM 树使用对象存储区来存储其持久层。为解决此问题，对象存储区按层次结构排列：

  1. 根父级商店

    根父对象存储区由仅限内存的 LSM 树提供支持，因此不依赖于对象存储区。

    根父级商店仅包含根商店的层文件和日志文件（稍后讨论）。请注意，LSM 树仅包含元数据（例如，扩展区信息），并且只有该信息会永久驻留在内存中。

  2. 根存储区

    根存储区使用根父存储区来存储其持久层文件。

    根存储区包含支持文件系统的所有其他对象，例如分配器和超级块使用的对象。

  3. 儿童商店

    子存储区使用根存储区来存储其持久层文件。它们会存储用户数据。子商店可以有很多，但它们只能使用根商店作为其父商店，这会将层次结构限制为三级。请注意，如果需要，我们可以支持更深层次的对象存储层次结构。

物体

  • 对象由一个 64 位无符号整数标识，该整数在存储对象的存储区中是唯一的，因此若要在文件系统中唯一标识一个对象，您需要指定存储区。

  • 零已预留，用于表示无效的对象 ID。

  • 对象支持多个属性，这些属性通过 64 位属性 ID 进行索引，该 ID 在对象内是唯一的。属性具有类似文件的 API，因此可以在属性内的任意偏移量处读取和写入任意数量的数据。最初，Fxfs 将仅公开对对象（即文件内容）的单个属性的访问权限。稍后，可能会使用其他属性来支持扩展属性。属性可以是稀疏的。

  • 有两种模式可用于写入对象：写入时复制模式（与 Minfs 相同）和覆盖模式。在写入时复制模式下，对已分配的块的任何写入操作都将涉及写入新分配的块、更新元数据以指向新块，然后释放旧块。覆盖模式会覆盖现有块，因此不需要更新相同的元数据。大多数对象将使用写入时复制模式写入，并且这是最初向外部用户公开的唯一模式。

日志

Fxfs 的日志有两个用途：

  1. 它支持事务：能够以原子方式将突变应用于多个文件系统对象。
  2. 在断电时快速持久保存更改。如果没有此功能，在内存层刷新之前，任何更改都不会持久存在，但出于性能和写入放大原因，最好尽可能延迟此操作（具体取决于内存限制）。

对内存中数据结构的所有更改都必须通过日志进行。与 Minfs 的日志不同，该日志是逻辑日志，而不是物理日志。这可大幅减少日志占用的空间量，因为插入记录只需几个字节即可表示，而 Minfs 中数据结构的变化可能涉及多个块。

请注意，Fxfs 的日志（与 Minfs 的日志类似）不包含数据。不过，Fxfs 的日志确实包含以 COW 模式写入的数据的校验和，并且 Fxfs 会在日志重放期间验证自上次已知设备刷新以来写入的数据的这些校验和，这意味着 Fxfs 可以检测到被中断的 COW 写入，并将文件内容恢复到上次完全写入的版本。Minfs 没有此数据校验和功能。

日志以单个不断增长的文件的形式存在。突变会以流式传输到文件。随着树的压缩，日志文件开头的区段可以释放，这意味着日志将具有稀疏前缀。所有对象的大小均为 64 位，我们需要支持的写入速率意味着在我们的生命周期内，环绕不会成为问题。为了应对设备可以随意重新排序写入操作这一事实，系统将在每个 4 KiB 块的末尾放置一个校验和。在重放时，重放将在日志中第一个校验和不匹配的块处结束。一个块的校验和用作下一个块的种子，这应有助于防止意外接受用于不同偏移量的块或来自之前 Fxfs 实例的残留块。

在重放日志时，会遇到一个难题，即如何了解超级块未涵盖的日志文件的范围。为了解决此问题，日志将使用覆盖模式运行并预分配区段。在重放期间，日志流中的任何范围都用于读取日志文件中的后续偏移量。

超级块

Fxfs 的超级块不仅仅是块，但它们与传统超级块的用途类似，因此使用相同的名称。超级块以对象形式存在于根对象存储区中。与其他对象不同，它们的首个扩展区放置在设备上的固定位置（所有其他对象的位置不受限制）。超级块的第一部分包含一个序列化结构，其中包含与其他文件系统类似的信息（例如块大小、重要对象的对象编号等）。之后，超级块会包含根父对象存储区（在写入超级块时）中包含的所有记录。超级块的写入方式与日志的写入方式相同：每个 4 KiB 块的末尾都有一个校验和。

有两个超级块。在装载期间，系统会选择序列号最新的超级块。

装载文件系统涉及以下步骤：

  1. 读取具有最新序列号的超级块。
  2. 将日志中的所有突变应用于内存层。
  3. 读取层信息并初始化 LSM 树持久层。

分配器

分配器使用 LSM 树来存储引用计数的范围（这可以有效地视为持久存储 <device-range> => <reference-count>。最初，Fxfs 将仅支持引用计数为 1，但未来，Fxfs 可能会支持文件克隆或扩展区共享，从而导致引用计数大于 1。

目录

对象存储区通过以 <object-id><child-name> => <child-object-id><child-type> 的形式存储记录来支持目录。此信息记录在用于其他对象元数据的同一树中。

压缩

最初，压缩将由释放日志空间的需求驱动。系统最初会选择合理的政策，并根据需要进行调整；无论我们采取何种措施，都不会与格式相关联，因此可以轻松更改。

文件名编码

Fxfs 用于文件名的具体编码目前尚未指定，但我们注意到，所选编码将至少与 UTF-8 兼容，而 UTF-8 是用于 FIDL 字符串和 Rust 字符串的编码。Fxfs 区分大小写，且不执行任何标准化。如果出现兼容性问题，可能需要更改此设置。

文件系统限制

  • 文件大小限制为 2^63 字节（64 位有符号整数的最大值）。在内部，Fxfs 可以表示最大为 2^64 字节的文件大小，但现有的文件系统 API 限制了这一点（例如，有符号的 off_t 类型）。
  • 目录大小没有具体限制，但在实践中会受到磁盘大小和 inode 数量的限制。
  • 每个卷大约可以有 2^64 个 inode。实际上，这更可能受到磁盘大小的限制。
  • Fxfs 大致可以支持 2^64 个卷。实际上，此值更可能受磁盘大小和其他资源（例如加载卷时的内存）的限制。
  • Fxfs 支持纳秒级的时间戳，其中包含 2^64 位秒和 2^32 位纳秒，可表示未来很长时间内的 UNIX 纪元时间戳。

Fsck

Fxfs 具有 fsck 的基本实现，可验证分配和对象引用计数。我们将在不久的将来开展更多工作，以扩大 fsck 的覆盖范围。

Minfs

Minfs 的一些限制指导了我们对 Fxfs 的设计选择：

  • 支持多线程。Minfs 是单线程的。追溯性地添加多线程支持比在开始时实现它要困难得多。Fxfs 是多线程的。
  • Minfs 使用简单的物理日志，但会产生显著的写入放大效应。Fxfs 使用逻辑日志。
  • Minfs 对目录大小和 inode 数量有硬性限制。Fxfs 的限制主要基于磁盘大小。
  • 不断改进 Minfs 的格式非常困难，因为所有更改都必须向后兼容，并且必须仔细考虑迁移。Fxfs 仍然需要迁移，但由于压缩会触发元数据的完全重写，因此某些格式更改会更简单。

实现

Fxfs 的原型设计已进行了一段时间，它已存在于源代码树中 (//src/storage/fxfs)，并且有多种选项可用于替代 Minfs。目前，Minfs 仍将是默认的可变文件系统。更改默认值的决定不在本 RFC 的讨论范围内。

语言

Fxfs 使用 Rust。我们认为，Rust 具有以下一些令人信服的优势：

  • 内存安全 - 减少崩溃和安全问题，这在涉及多个线程时尤其有用。
  • 良好的异步支持 - 文件系统受益于高并行性，而 Rust 的异步支持使这一点比其他语言容易得多。

性能

我们之所以追求 Fxfs，一个重要原因是想提高可变文件系统的性能。我们用于评估效果的基准是独立开发的。这些基准的确切性质不在本 RFC 的讨论范围内。

向后兼容性

Fxfs 最初将作为 Minfs 的替代方案存在，但支持有限（不适合生产），用于从 Minfs 迁移。

我们可能会考虑在未来支持更强大的迁移功能。

安全注意事项

最初，Fxfs 可以与 Zxcrypt 搭配使用，以实现卷级加密（就像 Minfs 一样），因此这方面应该不会有太大变化。Fxfs 是用 Rust 开发的，从理论上讲，这应该可以降低一些安全风险。

Fxfs 内置加密功能需要全面考虑安全性方面的问题，这不在本 RFC 的讨论范围内。

隐私注意事项

不适用

测试

Fxfs 使用与 Minfs 相同的全面文件系统测试套件。在适当的情况下，还会提供专门针对 Fxfs 的其他单元测试和集成测试。

文档

Fxfs 应该可以与 Minfs 互换，因此无需额外的外部文档；我们的 API 不会发生变化。此 RFC 本身是记录 Fxfs 高级设计的主要制品。

缺点、替代方案和未知因素

开发新的文件系统是一项重大任务。虽然我们已成功实现一个在功能和性能方面接近 Minfs 的原型，但 Fxfs 距离投入生产还有一段距离。

在开始此项目之前，我们考虑了其他策略，例如移植现有的开源文件系统，或使用现有文件系统的设计。以下是一些注意事项：

  • 与其他操作系统相比，Fuchsia 的文件系统接口非常不同，因此移植并非易事。
  • 一些现有的开源文件系统存在许可障碍。
  • 代码库与大多数 Fuchsia 代码库（C++ 不常见，测试实践也不同）不一致，并且会一直保持不一致。
  • 选择现有设计会限制格式的演变；为支持新功能要求而进行的格式更改可能会导致格式分叉，并/或在向上游推送更改时产生开销。
  • 我们需要完成的许多性能工作实际上并不在文件系统实现中，因此无论如何，开发新的文件系统都不能说是实现性能目标的关键路径。
  • 现有文件系统具有演变历史记录。重新实现现有设计通常涉及选择要支持的功能集，这会导致兼容性有限。
  • 如果对 Minfs 进行增量更改以达到所需状态，由于我们很可能需要支持迁移，因此可能需要更长时间。

不过，我们已选择支持外部贡献者参与 F2fs 的移植工作，目标是让 Fuchsia 能够与多种不同的文件系统良好搭配使用。

在先技术和参考资料

LSM 树并非新事物，已广泛应用于各种应用中，但在较小规模的文件系统中使用 LSM 树的示例有限。

Fxfs 设计的其他方面（例如逻辑日志格式和多卷支持）可以在其他文件系统中找到。