Page 436 - 《软件学报》2025年第5期
P. 436
2336 软件学报 2025 年第 36 卷第 5 期
个 PM 块的. 同时, PLTree 是一棵平衡树, 所以查找所有内部节点时的遍历路径长度相同. 由于 PLTree 内部节点
的高度较扁平, 各个数据集上的内部节点高度相差不大, 因此数据分布对内部节点的查找性能负面影响较小. 相比
之下, APEX 的内部节点平均访问延时约为 PLTree 的 2.2–8.8 倍, 并且内部节点的访问延时受到数据分布的影响.
这是因为 APEX 是一棵非平衡树, 构建索引时内部节点的高度受到键局部分布影响. 尽管 APEX 内部节点中无需
进行局部搜索, 但当键的局部分布难以拟合时, 内部节点的遍历路径增加将影响内部节点的查找性能.
B+树类持久化内存索引的内部节点遍历平均延时最长, 约为 PLTree 的 105–283 倍. 虽然它们都将内部节点
存储在 DRAM 中以加速访问, 但与学习型索引相比, B+树类结构的索引内部节点遍历路径更长, 并且需要在内部
节点中进行局部搜索来查找子节点的指针, 这导致了更多的 CPU 缓存行未命中, 从而影响了查找性能.
为了验证消除内部节点的局部搜索是否能够提升性能, 我们设计了消融实验: 在构建索引时, 保留了内部节点
的局部搜索. 叶节点和内部节点的划分误差与原索引相同, 都设置为 256. 在内部节点中使用二分法进行局部搜索,
其他数据结构的设计与原索引保持一致. 经过 1 亿次查找后, 记录了内部节点的平均读取延时. 如图 16 所示,
PLTree-local 代表经过修改后的索引, 即保留了内部节点的局部搜索. 实验结果显示, 消除内部节点的局部搜索后,
PLTree 的内部节点性能显著提升. 在 osm/face/genome/planet/uniform 数据集上, 查找性能分别提升了 34.7 倍/27.6
倍/19.5 倍/26.6 倍/10.3 倍.
此外, 我们还观察到, PLTree-local 内部节点的查找性能受到数据分布的影响, 在难以拟合的数据集中, 内部节
点的查找延时更长. 以 osm 数据集为例, PLTree-local 内部节点的平均延时约为 105 ns, 而 PLTree 不会受数据分布
影响, 在所有的数据集上内部节点查找平均仅需 3 ns. 这说明通过两阶段索引构建消除内部节点中的局部搜索能
够在提升性能的同时消除数据分布对索引内部节点查找性能的负面影响.
4.6.2 块元数据的影响
本节分析了元数据结构对性能的影响. 为了进行对比, 我们在关闭块元数据加速后, 分别在单线程和 28 线程
环境下执行了 1 亿次查找操作. 如图 17 所示, PLTree-n 代表关闭了块元数据加速的索引. 通过观察吞吐量, 我们发
现关闭块元数据加速后, 索引的性能下降. 这是因为关闭块元数据加速后, 无论查找的目标键在叶节点中是否存
在, 都必须先对叶节点进行访问. 而对于冲突较大的叶节点, 这会产生更多额外的 PM 访问. 然而, 当使了块元数据
加速后, 如果叶节点中不存在键, 只需进行一个缓存行的 DRAM 访问, 跳过了叶节点的访问. 这避免了 PM 带宽的
消耗, 并且在多线程情况下, 还能避免有限的 PM 带宽争用, 提高了吞吐量.
6 150 PLTree
吞吐量 (MOPS) 4 2 吞吐量 (MOPS) 100 PLTree-n
50
0
osm face genome planet uniform 0 osm face genome planet uniform
(a) 单线程查找操作吞吐量 (b) 28 线程查找操作吞吐量
图 17 对比关闭块元数据加速时在不同数据集上查找操作的吞吐量
4.6.3 溢出缓存的影响
为了评估溢出缓存结构设计的有效性, 我们设计了对比实验, PLTree-ff 使用树结构的持久化内存索引
Fast&Fair 替代文中提出的溢出缓存, 并在单线程和 28 线程环境下分别测试了 1 亿次查找和 1 亿次插入操作的吞
吐量. 如图 18 所示, 实验结果表明, 采用本文中提出的溢出缓存能够有效提升索引的查找和插入性能. PLTree 溢
出缓存采用缓存元数据加速了查找, 使得当键存在于溢出缓存时, 最少仅需读取一个 PM 块即可完成查找. 而在
Fast&Fair 中查找键时, 可能需要访问多个 PM 块. 插入过程中, 为确保键的唯一性, PLTree-ff 必须先查找 Fast&Fair
以避免重复的键, 而 PLTree 避免了在溢出缓存中对键进行唯一性检查, 从而在插入数据前减少了不必要的 PM 访
问, 节约了 PM 带宽. 此外, 在 Fast&Fair 叶节点插入键值对时, 会产生写放大, 而 PLTree 溢出缓存采用日志形式批
量写入数据, 避免了 PM 的写放大, 提高了 PM 带宽利用率.