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

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

此外, 可以发现在 4 个真实数据集上, APEX 的插入操作性能较传统结构索引 DPTree 和 NBTree 弱, 主要是
因为 APEX 面对真实数据集时叶节的冲突增加, APEX 在插入操作时需要进行额外的 PM 和缓存访问, 以检查键
在叶节点和 stash 中是否已经存在. 并且每次向 stash 插入数据时只写入 16 B 数据, 导致 16 倍的 PM 写放大. 而
DPTree 采用了分层的结构, 新插入的数据先写入 DRAM 驻留的缓冲树中, 之后再通过后台线程批量写入持久化
树中, 从而提高了写入性能. 对于范围查找, PLTree 在所有数据集上性能均优于其他索引, 在 uniform 数据集上
PLTree 相对于 DPtree/APEX/uTree/FPTree 性能分别提高了 4.3 倍/3.5 倍/10.4 倍/5.8 倍. 这是因为 PLTree 相较于
B+树结构持久索引具有更大的叶节点, 范围查找时可以在连续的地址范围内顺序访问 PM, 从而具有更高 PM 带
宽利用率. 而 DPTree 需要搜索多个树并组合结果, 影响了范围查找性能. uTree 的范围查找性能最低, 因为 uTree
将每个记录都存储在链表节点中, 遍历它们会导致许多缓存未命中.

4.4 多线程测试
本节的实验测试了索引在不同负载上的多线程可扩展性, 实验中线程从 1 个线程扩展到 28 个线程, 所有的线
程被固定在物理核心上运行, 每个线程独立使用一个物理核心.
图 7−图 10 展示了单个操作的并发性能, 包括 100% 的点查询/插入/范围查询/删除操作. 实验结果表明, 在不
同的负载下, PLTree 在所有的数据集上都表现出了良好的多线程可扩展性, 随着线程数量增加, PLTree 的吞吐量
也相应地增加, 且增加的趋势呈现线性或近似线性. 在 4 个真实数据集上, PLTree 的单项操作负载的并发性能均
优于其他索引, 这是因为: 首先, PLTree 通过拟合数据集的分布, 采用基于模型的搜索, 提高了 CPU 缓存利用率;
其次, PLTree 采用轻量级并发控制, 减少了同步开销; 第三, PLTree 利用 DRAM 中的元数据来加速查找, 避免了不
必要的 PM 访问, 从而减少了有限的 PM 带宽争用, 保证了高性能; 最后, PLTree 采用了批量写入和追加写入的方
式将数据写入溢出缓存, 降低了 PM 的写放大, 提高了 PM 带宽的利用率. 另外与单线程实验的情况一样, 在
uniform 数据集上, PLTree 的点查询和删除操作并发性与 APEX 性能相近.
80 80 80 80 150 PLTree
吞吐量 (MOPS) 60 60 60 60 100 DPtree
APEX
40
40
40
40
50
uTree
20
20
20
20
FPTree
0
10
20
20
10
20
10
20
10
0
(b) face
(a) osm 30 0 0 10 20 30 0 0 (c) genome 30 0 0 (d) planet 30 0 0 (e) uniform 30 NBTree
图 7 多线程点查询操作吞吐量, 横坐标为线程数, 纵坐标为吞吐量
40 40 50 30 50 PLTree
吞吐量 (MOPS) 30 0 30 0 40 0 20 0 40 0 DPtree
30
30
APEX
20
20
20
20
10
uTree
10
10
10
10
FPTree
20
20
10
10
20
0
10
10
20
(b) face
(a) osm 30 0 10 20 30 0 (c) genome 30 0 (d) planet 30 0 (e) uniform 30 NBTree
图 8 多线程插入操作吞吐量, 横坐标为线程数, 纵坐标为吞吐量

15 10 15 30 PLTree
吞吐量 (MOPS) 10 5 5 10 5 10 5 20 DPtree
APEX
10
uTree
FPTree
0
0
10
20
0
20
10
10
10
20
20
(a) osm 30 0 0 10 20 30 0 0 (c) genome 30 0 0 (d) planet 30 0 (e) uniform 30
(b) face
图 9 多线程范围查询操作吞吐量, 横坐标为线程数, 纵坐标为吞吐量

图 11−图 13 展示了混合负载的并发性能. 实验结果表明, 混合负载测试中, PLTree 在所有的数据集上展现
了最佳的性能和可扩展性. 随着负载中插入操作比例的增加, 其他的索引的扩展性变差, 而 PLTree 仍然保持最