Page 423 - 《软件学报》2025年第5期

张志国 等: PLTree: 一个高性能持久化内存学习索引 2323

问. 叶节点中的数据被划分为地址按 256 B 对齐的块, 将叶节点内的局部查找限制在一个 PM 块内完成. (2) 实现
了索引的并发操作, 并使用 DRAM 存储元数据来维护叶节点和溢出缓存结构中键的指纹信息, 加速查询操作, 避
免了频繁的 PM 访问, 节约有限的 PM 带宽. (3) 设计了写优化的分层缓存结构, 以解决真实数据负载下索引写入
性能下降的问题. 在叶节点中为每个块动态设置了一个分层溢出缓存. 当块满时, 将其中的数据批量写入溢出缓
存, 减小写放大. 此外, 针对索引的插入操作进行了优化. PLTree 中支持存储键重复的数据, 插入数据时键唯一性
检查仅在叶节点层面进行. 一旦完成叶节点的查询, 就不再查询溢出缓存, 避免了额外的 PM 访问, 从而提高索引
写入性能. (4) 在真实的 PM 设备上实现了 PLTree, 并进行了全面的对比和分析. 将 PLTree 与其他先进的持久化内
存索引进行了比较, 以验证索引设计的先进性.

1 相关工作

1.1 持久化内存索引
为了提升索引在 PM 上的性能, 之前的工作从多个角度提出了优化方案: (1) 不同的数据存储方式. 一些索引
(如 BzTree [14] , Dash [18] 等) 选择将索引完全存储在 PM 中, 便于索引的恢复, 但在索引操作时 (如元数据的更新) 可
[8]
[6]
能会产生额外 PM 的读写开销. 而另一些索引 (如 FPTree , NBTree , uTree [13] 等) 采用了 DRAM/PM 混合存储模
式, 只将关键数据持久化, 将频繁访问的索引结构放于 DRAM 中, 从而减少了 PM 的访问开销. 然而, 这种方式需
要在恢复时重构索引, 牺牲了一部分恢复性能, 并需要设计复杂的恢复策略以实现快速恢复. (2) 数据结构的优化.
文献 [5−7,14] 采用了无序的叶节点存储数据, 叶节点中数据以日志形式追加写入, 无需保证叶节点内记录的有序
性, 避免了数据移动的开销, 但查找时需要在叶节点内线性遍历, 影响搜索性能. 文献 [9,11] 通过记录键在无序叶
节点内的排序顺序改善搜索性能. 文献 [6−8,11,12,18] 在索引中存储了键的指纹, 使用 1 字节指纹作为键的摘要信
息加速搜索, 避免不必要的数据探测操作. 文献 [10] 采用了叶节点压缩方法, 减少了根到叶的路径长度和遍历开
销. 文献 [17] 根据 Optane DC 持久化内存硬件特性, 将叶节点大小的设置为 256 B 的倍数以提高带宽利用率. 文
献 [15,17,18] 通过限制探测距离, 确保查找性能. 文献 [12,20] 设计了分层的数据结构, 数据先存入 DRAM 缓存结
构, 之后再批量写入 PM, 优化写入性能. (3) 其他. 文献 [7,10,18] 使用 SIMD 指令增加并行处理能力, 加速读操作.
文献 [10−13,19] 通过对内存分配进行优化降低了持久化开销.
近期研究 [1,24,25] 尝试运用学习索引替代传统索引结构, 利用数据的分布特点构建基于持久化内存的学习索引.
其中, APEX 和 APLI 采用 DRAM/PM 混合架构. APEX 是 ALEX [28] 的持久化版本, 针对 PM 进行了改进. 它将叶节
点视为哈希表, 将叶节点模型视为哈希函数, 通过探测和存储 (probe-and-stash) 解决叶节点中多个键预测位置相同
时引发的冲突. 在叶节点中查找时, APEX 将数据的探测距离限制在 16 个槽位 (slot) 内, 若未找到目标键则继续搜
索溢出桶. 为减少数据移动产生的持久化开销, APEX 采用间隔数组 (gapped array) 存储插入数据, 并将频繁访问
的元数据存储在 DRAM 中, 以减少额外 PM 访问. APLI 则采用链表将数据节点 (256 B) 存储在 PM 中, 并使用存
储在 DRAM 中的 ALEX 索引结构作为上层节点来索引数据节点中的最小键. 同时, 它还在 DRAM 中设置了一个
哈希表用于存储热点数据, 以加速热点数据的访问. PLIN 是一个纯 PM 架构的学习索引, 它采用了 PGM [29] 的索引
构建方法, 根据 PM 介质访问粒度将数据节点划分为多个 256 B 的块, 并为每个块动态设置了树结构的溢出缓存
[4]
(Fast&Fair ), 在块中预留空间, 以块内无序的方式存储新加入的数据, 避免数据的移动开销. PLIN 将叶节点中的
查找操作限制在一个 PM 块内, 以减少额外的 PM 访问.

1.2 学习索引
学习索引根据数据分布构建, 其构建过程实际上是通过机器学习模型来近似数据-位置的累积分布函数
(cumulative distribution function, CDF). 学习索引模型中存储了键到位置的映射关系, 理想的情况下通过模型推断
能够使索引查找复杂度到达 O(1). 然而, 单个模型通常难以很好地拟合复杂的数据分布, 因此学习索引一般需要
训练多个机器学习模型, 组成与 B+树类似的树形结构来实现 CDF 的拟合: 上层模型接收键作为输入用于选择下
一层模型, 逐层缩小查找范围直到找到叶节点, 接着通过叶节点模型来预测输入键在叶节点中的估计位置. 为了保