Page 438 - 《软件学报》2025年第5期
P. 438

2338                                                       软件学报  2025  年第  36  卷第  5  期


                 PLTree 进在行  1  亿次查询时, 每次查询过程中访问元数据所需的平均缓存行数, 以及内部节点、叶节点和溢出缓
                 存对应的    PM  块的平均访问数. 在所有数据集上元数据的平均仅产生约                  1  个缓存行的访问, 内部节点       PM  块平均
                 访问数与内部节点的高度有关, 每一层产生              1  个  PM  块的访问. 除去内部节点的      PM  访问, 在  uniform  数据集上,
                 PM  的访问主要集中在叶节点, 平均约为           1  个  PM  块. 在真实数据集上, 叶节点和溢出缓存的        PM  块平均访问数之
                 和接近   1  个  PM  块, 这说明  PLTree 的索引设计在面对真实数据集时, 能够有效地减少不必要的                PM  访问, 充分利
                 用模型搜索的优势, 使索引的在真实数据集上的               PM  块访问数尽量接近在合成数据集上的访问数.

                                                  表 5 PLTree 索引信息统计

                                统计信息            osm        face    genome     planet    uniform
                                 block数       13 386 188  13 400 613  13 344 913  13 360 928  13 333 695
                               溢出缓存数           1 588 894  1 638 007  2 220 666  1 580 603  17
                            溢出缓存数/block数       11.87%    12.22%    16.64%     11.83%   0.001 3‰
                          元数据平均访问数 (缓存行)        1.080     1.114     1.025     1.002      1.000
                          内部节点PM块平均访问数           3         2          2         3         2
                           叶节点PM块平均访问数          0.566     0.428     0.385     0.670      1.000
                          溢出缓存PM块平均访问数          0.504     0.659     0.693     0.372    3.370×10 −6

                 4.9   索引恢复性能测试
                    在本节中, 我们在不同索引中分别加载             1  百万至  1  亿个键值对, 模拟索引崩溃并进行恢复操作, 评估各索引的
                 恢复速度. NBTree 没有提供索引恢复的实现, 故未参与此次对比. PLTree 和               APEX  采用了延迟恢复策略. 因此, 针
                 对这两者的实验包含了数据恢复和性能恢复两部分. 其中性能恢复时间为索引执行查询时性能恢复稳定的时间.
                 表  6  展示了在  planet 数据集上索引的恢复性能, PLTree/uTree/FPtree/DPTree 的索引恢复时间随着数据量的增加而
                 增加, 这是因为它们需要遍历叶节点来恢复索引. uTree/FPtree/DPTree 在恢复时需要在内存中重建内部节点, 增加
                 了恢复时间. 其中     uTree 在恢复时需要遍历键值对组成的链表, 缓存利用率较低, 恢复时间最长. 而                    PLTree 通过学
                 习数据的分布可以构建更大的数据节点, 叶节点数较少, 且恢复时无需重建内部节点, 因此可以获得较快的索引恢
                 复速度. APEX  在恢复时只需读取日志并重做或撤销崩溃时进行的结构修改操作, 因此索引恢复时间和数据量无
                 关. 另外  APEX  的性能恢复时间要比       PLTree 快, 这是因为与   APEX  相比  PLTree 在性能恢复时需要重建叶节点中
                 的块元数据, 因此牺牲了一定的性能恢复时间.

                                                   表 6 索引恢复时间 (s)

                   键值对数量        PLTree (索引恢复/性能恢复)      APEX (索引恢复/性能恢复)       uTree    FPTree   DPTree
                      1M             0.000 12/0.132          0.025 9/0.129     0.170    0.019     0.018
                     10M             0.001 85/0.621          0.027 5/0.495     1.688    0.229     0.035
                     50M             0.011 4/2.042           0.027 9/1.870     8.235    1.226     0.151
                     100M            0.025 2/4.395           0.027 3/2.279     16.379   2.479     0.295

                 5   总 结

                    本文提出了一种      DRAM/PM  混合架构的持久化学习索引           PLTree, 优化了真实数据负载下的读写性能. PLTree
                 利用模型搜索来提高在        PM  上的查找性能, 并采用了两阶段的索引构建方法, 通过消除学习索引内部节点中的局
                 部搜索, 减少   PM  的访问次数, 同时减轻了数据分布对索引访问性能的影响. 根据学习索引面对真实数据集时的特
                 点, 合理利用   DRAM  中的元数据加速持久化学习索引查询, 避免了额外的                 PM  访问. 针对持久化内存的特性, 设计
                 了写入优化的分层溢出缓存, 存储叶节点中由于冲突导致的溢出数据, 提升了在真实数据负载中索引的写入性能.
                 实验结果显示     PLTree 在处理真实数据时, 牺牲了一定的存储空间以换取更高的读写性能. 本文提出索引设计能够
                 在一定程度减轻这一问题, 但是在面对更大的数据规模时可能会导致一定的空间开销增长. 作为未来的优化方向,
   433   434   435   436   437   438   439   440   441   442   443