RFC-0136:Fxfs | |
---|---|
状态 | 已接受 |
区域 |
|
说明 | 全新 Fuchsia 文件系统的简要概览。 |
Gerrit 更改 | |
作者 | |
审核人 | |
提交日期(年-月-日) | 2021-09-30 |
审核日期(年-月-日) | 2021-10-13 |
摘要
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 进行了详细的设计审核。
设计
日志结构化合并树
如需了解日志结构化合并 (LSM) 树的概览,请访问 Wikipedia。Fxfs 使用 LSM 树提供在 Fxfs 中使用的永久性键值对数据结构。
LSM 树具有一些吸引人的特性:
- 写入设备的图层是不可变的,这意味着:
- 访问这些图层时无需锁定。
- 限制某些类的 bug - 如果图层未被修改,则更少机会损坏它们。
- 可能更容易调试问题 - 如果图层不发生变化,则可减少可变因素。
- 更易于支持压缩,并且可以在后台应用更激进的压缩以节省空间。
- 系统会以批量(而非逐个)方式顺序写出更改,这对闪存来说是一种更有利的写入模式,可减少写入放大并避免不必要的擦除周期。这种写入模式对旋转存储设备也非常友好。
- 与其他方式相比,此方法更容易失去快照支持。
- 允许将写入所需的工作推迟到空闲时间(许多设备都有较长的空闲时间)。这在实践中意味着,当设备处于闲置状态时(这时最方便),可以进行压缩。
- 压缩可以在后台执行,从而节省时间来处理更重要的事情。
- 重写元数据是一项经过充分实践的集成文件系统操作,可以简化格式迁移。在压缩期间,可以写出完全不同的图层格式。
但也有一些缺点:
- 空间管理更困难 - 所有操作都需要元数据空间,即使是删除操作,因此需要谨慎预留空间。请注意,支持快照的其他文件系统也会出现此问题,因此它并非 LSM 树所独有。
- 如果图层数量较多,读取速度会变慢。我们可以采用一些缓解措施来解决此问题,例如布卢姆过滤器,并且压缩会通过合并层来降低此费用。
值得注意的是,即使选择了 LSM 树,如果我们发现混合方法有用,仍然可以选择使用可变的持久层格式。
Fxfs 的 LSM 树实现的 API 需要一个合并函数,该函数决定了如何合并记录。
Fxfs 的内存层由高效且支持并发的数据结构(目前是跳表)表示。
对象存储区
Fxfs 由对象存储区的层次结构组成。对象存储区提供一个按对象 ID(一个 64 位无符号整数)键值对的类似文件的 API。支持简单的命名空间功能(例如目录支持或类似功能),但不是强制性的;您可以使用对象存储空间,只使用对象 ID 引用对象。对象存储区会将其元数据存储在持久键值数据结构(LSM 树)中。元数据包含典型的文件信息,例如对象大小和映射到设备偏移量的范围。
Fxfs 的 LSM 树使用对象存储区来存储其永久层,这会形成循环依赖项:对象存储区使用 LSM 树来存储其元数据,然后 LSM 树使用对象存储区来存储其永久层。为解决此问题,对象存储区按层次结构进行排列:
根父级存储区
根父级对象存储区由纯内存 LSM 树提供支持,因此不依赖于对象存储区。
根父级存储区仅包含根存储区的层文件和日志文件(稍后会介绍)。请注意,LSM 树仅包含元数据(例如 extent 信息),并且只有这些信息会永久驻留在内存中。
根存储区
根存储区使用根父级存储区来存储其永久层文件。
根存储区包含用于支持文件系统的所有其他对象,例如分配器和超块使用的对象。
子商店
子存储区使用根存储区来存储其永久层文件。它们会存储用户数据。子存储区可以有很多,但它们只能将根存储区用作父级,这会将层次结构限制为三级。请注意,如果需要,我们可以支持更深层次的对象存储分层结构。
物体
对象由一个 64 位无符号整数标识,该整数在存储对象的存储区中是唯一的,因此,若要在文件系统中唯一标识对象,您需要指定存储区。
零已被保留,用于表示无效的对象 ID。
对象支持多个属性,这些属性由在对象中唯一的 64 位属性 ID 编入索引。属性具有类似文件的 API,您可以在属性中的任意偏移量读取和写入任意数量的数据。最初,Fxfs 仅会公开对对象的单个属性(即文件内容)的访问权限。日后,我们可能会使用其他属性来支持扩展属性。属性可以是稀疏的。
写入对象时,有两种模式可用:写时复制模式(与 Minfs 相同)和覆盖模式。在写时复制模式下,对已分配的块的任何写入都将涉及写入新分配的块、更新元数据以指向新块,然后释放旧块。覆盖模式会覆盖现有分块,因此无需更新相同的元数据。大多数对象将使用写时复制模式写入,并且这将是最初向外部用户公开的唯一模式。
日志
Fxfs 的日志有以下两种用途:
- 它支持事务:能够将更改原子地应用于多个文件系统对象。
- 以便在断电时快速保留更改。如果不这样做,则在内存层被刷新之前,所有更改都不会保留,但出于性能和写入放大原因,最好尽可能延迟执行此操作(具体取决于内存限制)。
对内存数据结构的所有更改都必须通过日志进行。与 Minfs 的日志不同,该日志是逻辑日志,而不是物理日志。这大大减少了日志占用的空间量 - 一个插入记录可以由几个字节表示,而对 Minfs 中数据结构的更改可能涉及多个块。
请注意,Fxfs 的日志(如 Minfs 的日志)不包含数据。不过,Fxfs 的日志确实包含以 COW 模式写入的数据的校验和,并且 Fxfs 会在日志重放期间对自上次已知设备刷新以来写入的数据进行这些校验和验证,这意味着 Fxfs 可以检测到损坏的 COW 写入,并将文件内容还原为上次完全写入的版本。Minfs 不具备此数据校验功能。
日志以单个不断增长的文件的形式存在。系统会将更改流式传输到文件。随着树的压缩,日志文件开头的 extent 可以释放,这意味着日志将具有稀疏前缀。所有对象的大小都是 64 位,并且我们需要支持的写入速率意味着在我们的生命周期内,封装不会成为问题。为了解决设备可以自由重新排序写入的问题,系统会在每个 4 KiB 分块的末尾放置一个校验和。在重放时,重放将在日志中第一个校验和不匹配的块结束。一个分块的校验和将用作下一个分块的种子,这应可防止意外接受要用于其他偏移量或来自 Fxfs 上一个实例的残留块。
重放日志时,需要了解超块未涵盖的日志文件的 extent,这是一个难题。为了解决此问题,日志将使用覆盖操作模式并预分配 extent。在重放期间,日志流中的任何 extent 都用于读取日志文件中的后续偏移量。
超级块
Fxfs 的超块不仅仅是块,它们的用途与传统超块类似,因此使用相同的名称。超块以对象的形式存在于根对象存储区中。与其他对象不同,其第一个范围位于设备上的固定位置(所有其他对象的位置没有限制)。超块的第一部分包含一个序列化结构,其中包含与其他文件系统中类似的信息(例如块大小、重要对象的对象编号等)。之后,超块包含根父级对象存储区(在写入超块时)中包含的所有记录。超级块的写入方式与日志的写入方式相同:每个 4 KiB 分块的末尾都有一个校验和。
有两个超块。在挂载期间,系统会选择序列号最新的超块。
装载文件系统涉及以下步骤:
- 读取具有最新序列号的超块。
- 将日志中的所有更改应用于内存层。
- 读取图层信息并初始化 LSM 树永久性图层。
分配器
分配器使用 LSM 树来存储引用计数的 extent(这实际上可以视为持久存储 <device-range> => <reference-count>
)。最初,Fxfs 仅支持引用计数为 1,但未来,Fxfs 可能会支持文件克隆或范围共享,这将导致引用计数大于 1。
目录
对象存储区通过以以下形式存储记录来支持目录:<object-id><child-name> => <child-object-id><child-type>
。这些信息会记录在用于其他对象元数据的同一树中。
压缩
最初,压缩将由日志中释放空间的需求驱动。我们会先选择合理的政策,并根据需要进行调整;我们所做的一切都不会受到格式限制,因此可以轻松更改。
文件名编码
Fxfs 用于文件名的具体编码目前未指定,但请注意,所选编码至少与 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 不会发生变化。本文档本身就是记录 Fxfs 高级设计的主要工件。
缺点、替代方案和未知情况
开发新的文件系统是一项重大任务。虽然我们设法实现了一个在功能和性能方面接近 Minfs 的原型,但 Fxfs 还需要经过一些改进才能投入生产。
在着手实施此项目之前,我们考虑了其他策略,例如移植现有的开源文件系统或使用现有文件系统的设计。我们考虑了以下因素:
- 与其他操作系统相比,Fuchsia 的文件系统接口非常不同,因此移植并非易事。
- 某些现有的开源文件系统存在许可问题。
- 这些代码库与 Fuchsia 的大多数代码库不一致,并且将保持这种不一致状态(C++ 并不常见,测试做法也不同)。
- 选择现有设计会对格式演变施加一些限制;为了支持新功能要求而进行的格式更改可能会涉及分叉格式,并且/或者会因将更改推送到上游而产生开销。
- 我们需要完成的许多性能工作实际上并不在文件系统实现中,因此无论如何,开发新文件系统都不是实现我们性能目标的关键路径。
- 现有文件系统具有演变历史。重新实现现有设计通常需要选择我们要支持的一组功能,这会导致兼容性受限。
- 由于我们很可能需要支持迁移,因此对 Minfs 进行增量更改以达到所需状态可能需要更长时间。
尽管如此,我们还是选择支持外部贡献者移植 F2fs,目的是让 Fuchsia 能够与多个不同的文件系统良好配合。
在先技术和参考文档
LSM 树并不新,在各种应用中都广泛使用,但在小规模文件系统中的使用示例有限。
其他文件系统中也包含 Fxfs 设计的其他方面,例如逻辑日志格式和多卷支持。