注意
本文档适用于 Ceph 的开发版本。
PoseidonStore
关键概念和目标
作为 Crimson 的可插拔后端存储之一，PoseidonStore 仅针对高端 NVMe SSD（不考虑 ZNS 设备）。
完全为低 CPU 消耗而设计
针对不同数据类型采用混合更新策略（就地更新、异地更新），通过减少主机端 GC 来最大限度地降低 CPU 消耗。
移除像 RocksDB 这样的黑盒组件以及 BlueStore 中的文件抽象层，以避免不必要的开销（例如，数据复制和序列化/反序列化）
利用 NVMe 特性（原子大写入命令，Atomic Write Unit Normal）。利用 io_uring（新的内核异步 I/O 接口）选择性地使用中断驱动模式以提高 CPU 效率（或使用轮询模式以降低延迟）。
分片数据/处理模型
背景
就地更新和异地更新策略都有其优缺点。
日志结构存储
基于日志结构的存储系统是采用异地更新方法的一个典型例子。它从不修改已写入的数据。写入总是到日志的末尾。它实现了 I/O 顺序化。
优点
毫无疑问，一次顺序写入就足以存储数据
它自然支持事务（没有覆盖，因此存储可以回滚到以前的稳定状态）
对闪存友好（它减轻了 SSD 上的 GC 负担）
缺点
存在主机端 GC，会带来开销
I/O 放大（主机端）
更多的主机 CPU 消耗
元数据查找慢
空间开销（活动数据和未使用数据共存）
就地更新存储
就地更新策略被广泛用于传统文件系统，如 ext4 和 xfs。一旦一个块被放置在给定的磁盘位置，它就不会移动。因此，写入会到磁盘上的相应位置。
优点
较少的主机 CPU 消耗（不需要主机端 GC）
快速查找
不需要额外的日志结构空间，但存在内部碎片
缺点
发生更多的写入来记录数据（元数据和数据部分是分开的）
它不能支持事务。在一般情况下，需要某种形式的 WAL 来确保更新原子性
对闪存不友好（由于设备级 GC，给 SSD 带来更多负担）
动机和关键思想
在现代分布式存储系统中，服务器节点可以配备多个 NVMe 存储设备。事实上，一台服务器上可以连接十个或更多的 NVMe SSD。因此，由于服务器节点中可用的 CPU 资源有限，很难实现 NVMe SSD 的全部性能。在这样的环境中，CPU 往往成为性能瓶颈。因此，现在我们应该专注于最大限度地减少主机 CPU 消耗，这与 Crimson 的目标相同。
为了实现高度优化的 CPU 消耗的对象存储，我们做出了三个设计选择。
PoseidonStore 没有像 BlueStore 中的 RocksDB 这样的黑盒组件。
因此，它可以避免不必要的数据复制和序列化/反序列化开销。此外，我们可以移除运行 RocksDB 所需的不必要的文件抽象层。对象数据和元数据现在直接映射到磁盘块。消除所有这些开销将减少 CPU 消耗（例如，预分配、NVME 原子特性）。
PoseidonStore 针对不同数据大小使用混合更新策略，类似于 BlueStore。
正如我们所讨论的，就地更新和异地更新策略都有其优缺点。由于 CPU 仅在小 I/O 工作负载下成为瓶颈，我们选择就地更新来处理小 I/O，以最大限度地减少 CPU 消耗，同时选择异地更新来处理大 I/O，以避免双重写入。从长远来看，对于小数据来说，双重写入在 CPU 消耗方面可能优于主机 GC 开销。尽管它将 GC 完全留给 SSD，
PoseidonStore 利用 io_uring（新的内核异步 I/O 接口）来利用中断驱动 I/O。
像 SPDK 这样的用户空间驱动 I/O 解决方案通过避免系统调用和实现从应用程序的零拷贝访问来提供高 I/O 性能。然而，它不支持中断驱动 I/O，这只能通过内核空间驱动 I/O 实现。轮询对于低延迟有好处，但对于 CPU 效率不利。另一方面，中断对于 CPU 效率有好处，而对于低延迟不利（但随着 I/O 大小增加，情况并不那么糟糕）。请注意，像 DPDK 这样的网络加速解决方案也会过度消耗 CPU 资源进行轮询。同时使用轮询进行网络和存储处理会加剧 CPU 消耗。由于网络通常比存储快得多且优先级更高，因此轮询应仅应用于网络处理。
高端 NVMe SSD 有足够的能力来处理更多工作。此外，SSD 寿命在目前也不是一个实际问题（有足够的擦除周期限制[1]）。另一方面，对于大 I/O 工作负载，主机可以负担得起处理主机 GC。此外，当无效对象的大小较大时，主机可以更有效地对它们进行垃圾回收
观察
Ceph 中的两种数据类型
数据（对象数据）
双重写入的成本很高
存储此数据的最佳方法是就地更新
至少需要两个操作来存储数据：1）数据和 2）数据位置。尽管如此，恒定数量的操作会比异地更新更好，即使它会加剧 SSD 中的 WAF
元数据或小数据（例如，object_info_t、snapset、pg_log 和 collection）
一个对象的多个小尺寸元数据条目
存储此数据的最佳解决方案是 WAL + 使用缓存
存储元数据的有效方法是合并所有与数据相关的元数据，并通过一次写入操作存储它们，即使这需要后台刷新来更新数据分区
设计
WAL
日志、元数据和小数据存储在 WAL 分区中
WAL 分区中的空间以循环方式不断重用
必要时刷新数据以修剪 WAL
磁盘布局
数据块是元数据块或数据块
Freelist 管理空闲空间 B+ 树的根
Super block 包含数据分区的管理信息
Onode 基数树信息包含 onode 基数树的根
I/O 过程
写入
对于传入的写入，数据根据请求大小以不同方式处理；数据要么写入两次（WAL），要么以日志结构方式写入。
如果请求大小 ≤ 阈值（类似于 BlueStore 中的最小分配大小）
将数据和元数据写入 [WAL] —刷新—> 分别将它们写入 [数据区（就地更新）] 和 [元数据区]。
由于 CPU 在小 I/O 工作负载下成为瓶颈，因此使用就地更新方案。从长远来看，对于小数据来说，双重写入在 CPU 消耗方面可能优于主机 GC 开销
否则，如果请求大小 > 阈值
将数据追加到 [数据区（日志结构）] —> 将相应的元数据写入 [WAL] —刷新—> 将元数据写入 [元数据区]
对于大 I/O 工作负载，主机可以负担得起处理主机 GC。此外，当无效对象的大小较大时，主机可以更有效地对它们进行垃圾回收
请注意，可以将阈值配置为非常大的数字，以便只发生场景（1）。通过这种设计，我们可以控制整体 I/O 过程，并进行上述针对 crimson 的优化。
详细流程
我们利用 NVMe 写入命令，该命令提供原子性保证（Atomic Write Unit Power Fail）。例如，可以一次性原子写入 512 Kbytes 的数据，而无需 fsync()。
阶段 1
如果数据较小 WAL (written) --> | TxBegin A | Log Entry | TxEnd A | 使用 NVMe 原子写入命令在 WAL 上追加包含 pg_log、snapset、object_infot_t 和块分配的日志条目
如果数据较大 数据分区 (written) --> | Data blocks |
阶段 2
如果数据较小 不需要。
如果数据较大 那么，将元数据追加到 WAL。WAL --> | TxBegin A | Log Entry | TxEnd A |
读取
使用缓存的对象元数据来查找数据位置
如果未缓存，需要在检查点和对象元数据分区之后搜索 WAL，以查找最新的元数据
刷新（WAL --> 数据分区）
刷新已提交的 WAL 条目。有两个条件（1. WAL 大小接近满，2. 刷新信号）。我们可以通过批处理来减轻频繁刷新的开销，但这会导致延迟完成。
崩溃一致性
大情况
写入数据块后立即发生崩溃
数据分区 --> | Data blocks |
我们不需要关心这种情况。数据尚未分配。这些块将被重用。
写入 WAL 后立即发生崩溃
数据分区 --> | Data blocks |
WAL --> | TxBegin A | Log Entry | TxEnd A |
写入过程已完成，因此没有数据丢失或不一致状态
小情况
写入 WAL 后立即发生崩溃
WAL --> | TxBegin A | Log Entry| TxEnd A |
所有数据都已写入
比较
最佳情况（预分配）
只需要在 WAL 和数据分区上进行写入，而无需更新对象元数据（用于位置）。
最坏情况
至少需要在 WAL、对象元数据和数据块上进行三次额外的写入。
如果从 WAL 到数据分区的刷新频繁发生，基数树 onode 结构需要多次更新。为了最小化这种开销，我们可以使用批处理来最小化树上的更新（与对象相关的数据具有局部性，因为它将具有相同的父节点，因此可以最小化更新）
如果 WAL 接近满或有刷新信号，则需要刷新 WAL。
此设计的前提是 OSD 可以将最新的元数据作为单个副本进行管理。因此，追加的条目不会被读取
最佳情况或最坏情况都不会产生严重的 I/O 放大（它会产生 I/O，但 I/O 率是恒定的），不像 LSM-tree DB（所提出的设计类似于只有 level-0 的 LSM-tree）
详细设计
Onode 查找
基数树 我们的设计完全基于前缀树。Ceph 已经利用 OID 前缀的特性来拆分或搜索 OID（例如，池 ID + hash + oid）。因此，前缀树非常适合存储或搜索对象。我们的方案旨在高效地查找前缀树。
分片分区 OID 的几位（hash 的最左位）决定了对象所在的分片分区。例如，如果分区数配置为四个，则 hobject_t 中的 hash 的整个空间可以分为四个域（0x0xxx ~ 0x3xxx、0x4xxx ~ 0x7xxx、0x8xxx ~ 0xBxxx 和 0xCxxx ~ 0xFxxx）。
Ondisk onode
struct onode { extent_tree block_maps; b+_tree omaps; map xattrs; }
onode 包含用于查找的基数树节点，这意味着我们可以使用 onode 中的树节点信息来搜索对象。此外，如果数据大小较小，onode 可以嵌入数据和 xattrs。onode 是固定大小的（256 或 512 字节）。另一方面，omaps 和 block_maps 通过 onode 中的指针是可变长度的。
查找 onode 树根的位置在 Onode 基数树信息中指定，因此我们可以通过使用前缀树的根来找出对象的位置。例如，分片分区由 OID 确定，如上所述。使用 OID 的其余位和基数树，查找过程找出 onode 的位置。范围树（block_maps）包含数据块的位置，因此我们最终找出数据位置。
分配
分片分区
整个磁盘空间被划分为几个称为分片分区（SP）的数据块。每个 SP 都有自己的数据结构来管理分区。
数据分配
正如我们上面解释的，管理信息（例如，超级块、freelist info、onode 基数树 info）在每个分片分区中预分配。给定 OID，我们可以将数据块部分中的任何数据映射到 onode 中的范围树。可以通过搜索空闲空间跟踪数据结构（我们将在下面解释）来分配块。
+-----------------------------------+ | onode radix tree root node block | | (Per-SP Meta) | | | | # of records | | left_sibling / right_sibling | | +--------------------------------+| | | keys[# of records] || | | +-----------------------------+|| | | | start onode ID ||| | | | ... ||| | | +-----------------------------+|| | +--------------------------------|| | +--------------------------------+| | | ptrs[# of records] || | | +-----------------------------+|| | | | SP block number ||| | | | ... ||| | | +-----------------------------+|| | +--------------------------------+| +-----------------------------------+
空闲空间跟踪 空闲空间按每个 SP 进行跟踪。我们可以使用 XFS 中的基于范围的 B+ 树进行空闲空间跟踪。Freelist info 包含空闲空间 B+ 树的根。粒度是数据块分区中的数据块。数据块是最小且固定大小的数据单元。
+-----------------------------------+ | Free space B+tree root node block | | (Per-SP Meta) | | | | # of records | | left_sibling / right_sibling | | +--------------------------------+| | | keys[# of records] || | | +-----------------------------+|| | | | startblock / blockcount ||| | | | ... ||| | | +-----------------------------+|| | +--------------------------------|| | +--------------------------------+| | | ptrs[# of records] || | | +-----------------------------+|| | | | SP block number ||| | | | ... ||| | | +-----------------------------+|| | +--------------------------------+| +-----------------------------------+
Omap 和 xattr 在此设计中，omap 和 xattr 数据由 onode 中的 B+ 树跟踪。onode 只具有 B+ 树的根节点。根节点包含指示键 onode 存在位置的条目。因此，如果我们知道 onode，可以通过 omap B+ 树找到 omap。
碎片化
内部碎片化
我们将不同类型的数据/元数据尽可能多地打包在一个块中，以减少内部碎片化。基于范围的 B+ 树可能通过分配最适合对象的连续块来进一步减少这种情况
外部碎片化
频繁的对象创建/删除可能导致外部碎片化。在这种情况下，我们需要进行清理工作（类似于 GC）来解决这个问题。为此，我们参考 NetApp 的连续段清理，这似乎类似于 SeaStore 的方法 Countering Fragmentation in an Enterprise Storage System (NetApp, ACM TOS, 2020)
WAL
每个 SP 都有一个 WAL。写入 WAL 的数据是元数据更新、空闲空间更新和小数据。请注意，只有小于预定义阈值的数据才需要写入 WAL。较大的数据写入未分配的空闲空间，其 onode 的 extent_tree 相应更新（也更新 on-disk extent tree）。我们将 WAL 分区静态分配在数据分区之外，预先配置。
分区和 Reactor 线程
在早期开发阶段，PoseidonStore 将采用分区的静态分配。分片分区的数量是固定的，每个分区的大小也应在运行集群之前配置。但是，分区的数量可以按如下方式增长。我们将其作为未来的工作。此外，每个 reactor 线程都有一组静态的 SP。
缓存
主要有两个缓存数据结构；onode 缓存和块缓存。它看起来如下。
Onode cache: lru_map <OID, OnodeRef>;
Block cache (data and omap): Data cache --> lru_map <paddr, value>
要填充 onode 数据结构，需要使用前缀树检索目标 onode。块缓存用于缓存块内容。对于事务，对块（包括对象元数据块、数据块）的所有更新首先在内存中的块缓存中执行。将事务写入 WAL 后，脏块被刷新到各自分区中的相应位置。PoseidonStore 可以为每种类型配置缓存大小。简单的 LRU 缓存逐出策略可用于两者。
CoW/Clone
至于 CoW/Clone，克隆像其他普通对象一样有自己的 onode。
尽管每个克隆都有自己的 onode，但如果数据块没有更改，则应在原始对象和克隆之间共享数据块，以最大限度地减少空间开销。为此，需要数据块的引用计数来管理这些共享数据块。
为了处理具有引用计数的数据块，poseidon store 利用 shared_blob 来维护被引用的数据块。
如下图所示，shared_blob 通过使用引用计数来跟踪在其他 onode 之间共享的数据块。shared_blobs 由超级块中的 shared_blob_list 管理。
计划
所有 PR 都应包含单元测试以验证其最小功能。
WAL 和块缓存实现
第一步，我们将构建 WAL，包括读写 WAL 的 I/O 过程。随着 WAL 的开发，块缓存需要一起开发。此外，我们将添加一个 I/O 库，用于从 NVMe 存储读取/写入，以利用 NVMe 特性和异步接口。
基数树和 onode
首先，提交一个 PR，其中包含此文件的更详细的磁盘布局和 onode 基数树的查找策略。在设计 PR 合并后，根据上述设计进行后续实现。第二个 PR 将是关于基数树的实现，它是查找对象的关键结构。
范围树
此 PR 是用于管理 onode 中数据块的范围树。我们将构建范围树，并演示在查找对象时它是如何工作的。
omap 的 B+ 树
我们将为 omap 整理一个简单的键/值接口。这可能是一个单独的 PR。
CoW/Clone
为了支持 CoW/Clone，将添加 shared_blob 和 shared_blob_list。
集成到 Crimson 作为 I/O 接口
在此阶段，与 Crimson 交互的接口（例如 queue_transaction()、read()、clone_range() 等）应该能够正常工作。
配置
我们将详细定义 Poseidon store 配置。
压力测试环境和集成到 teuthology
我们将添加压力测试和 teuthology 套件。
脚注