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

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


                 使用均匀分布从数据集中选取键, 在读/写负载中, 每个键被读取/写入的概率相同. 在进行测试之前, 先预先加载                               1
                 亿个键值对来构建索引. 范围查找从一个随机键开始, 并扫描后续的                     100  条记录. 由于  DPTree 没有实现删除操作,
                 NBTree 没有实现范围查找操作, 所以在相应的测试中不将               DPTree 和  NBTree 加入对比.

                 4.2   参数选择
                    本节将研究分段误差, 叶节点         block  大小以及溢出缓存     entry  大小的设置对索引性能的影响.

                 4.2.1    分段误差设置
                    在使用自底向上的方法构建学习索引的布局时, 分段误差的大小会直接影响键空间的划分粒度, 从而影响树
                 的高度和   PM  访问次数. 当分段误差较小时, 键空间会被划分得更加细致, 导致更多的节点和更高的树高, 进而增
                 加了  PM  的访问次数. 相反, 当分段误差较大时, 分区粒度过粗, 叶节点中的线性模型不能很好地拟合数据分布, 可
                 能会引发更多的冲突, 并且更多的数据会写入溢出缓存. 因此, 在选择分段误差时需要综合考虑这两个方面的因素.
                    为了探究不同分段误差对          PLTree 索引性能的影响, 我们使用       5  个数据集进行了单线程实验, 并比较了不同分
                 段误差下的查找和插入吞吐量. 实验中使用              1  亿个键构建了不同分段误差的索引, 并进行了             1  亿次查找和插入操
                 作, 记录了操作吞吐量. 图      4  实验结果显示, 随着分段误差的增大, 所有数据集的查找和插入吞吐量逐渐上升. 当分
                 段误差分别大于      256 (图  4(a)) 和  128 (图  4(b)) 时, 所有数据集上的查找操作和插入操作的吞吐量逐渐收敛. 这是因
                 为随着分段误差的增大, 索引每层中的节点数量减少, 从而在遍历过程中缓存命中率提高, 同时索引高度逐步减
                 小, 从而减少了    PM  的访问. 此外, 在查找操作中采用了存储在           DRAM  中的指纹数据加速溢出缓存的查找, 溢出缓
                 存的每一层只会产生一个缓存行的            DRAM  访问, 当溢出缓存层中不存在键时则跳过该层               PM  访问, 每次在溢出缓
                 存查找最多只会产生一次         PM  访问, 因此索引查找性能受到溢出缓存的影响较小. 对于插入操作, 由于只需在叶节
                 点数据块中原地更新和插入键值对, 只有在数据块满时, 才会将数据批量写入溢出缓存, 避免了溢出缓存的频繁写
                 入, 插入操作的性能主要受索引高度的影响. 当误差继续增大时索引的高度不再增加, 因此随着分段误差增大读写
                 性能逐渐收敛. 根据实验结果, 我们选择将索引构建的分段误差大小设置为                       256.

                                          5                  3              osm
                                         吞吐量 (MOPS)  3       吞吐量 (MOPS)  2  face
                                                                            genome
                                                                            planet
                                                                            uniform
                                          1
                                           0 128 256 384 512
                                              分段误差           1 0 128 256 384 512
                                                                  分段误差
                                           (a) 查找操作吞吐量        (b) 插入操作吞吐量
                           图 4 使用不同分段误差构建的索引在不同数据集上进行查找和插入操作时的吞吐量

                 4.2.2    叶节点中  block  大小和溢出缓存中  entry  大小对性能的影响
                    为了研究叶节点中       block  和溢出缓存中   entry  的大小设置对索引性能的影响, 我们在          4  个真实数据集上进行
                 了单线程性能测试. 比较了数据结构在不同大小设置下                  (同时修改元数据大小以匹配          block  和  entry  的不同大小设
                 置), 进行  1  亿次查找和插入操作时的吞吐量. 根据图           5(a) 和图  5(b) 的结果, 我们发现将叶节点      block  大小设置为
                 256 B  时, 可以获得最高的读写吞吐量. 由于真实数据集键空间的局部难以拟合, 较小的                      block  更容易因冲突导致
                 数据频繁写入溢出缓存, 从而增加查找路径长度及查找时间. 对于插入操作, 较小的                         block  更加容易被写满引起频
                 繁的溢出缓存写入, 降低了性能. 当         block  大小超过  256 B  时, 读写性能开始下降. 这是因为块元数据需存储更多指
                 纹信息, 可能导致     DRAM  缓存未命中的概率增加. 另外, 由于指纹大小为               8 bits, 不同键存在相同指纹的概率为
                 1/256, 因此当  block  增大时, 可能出现不同的键具有相同的指纹信息, 导致读写操作可能需要在叶节点访问不止一
                 个  PM  块来查找目标键.
                    根据图   5(c) 和图  5(d) 的结果, 我们发现将溢出缓存中        entry  的大小设置为  768 B  时, 大部分的数据集上索引
                 的读写吞吐量达到最高点. 当         entry  较小时, 由于溢出缓存每一层的数据容纳能力有限, 溢出缓存的层数较多, 在查
                 找键时需要访问更多的缓存行, 增加了缓存未命中的概率. 同样, 在插入操作时, 若                      entry  较小可能会导致数据频繁
   426   427   428   429   430   431   432   433   434   435   436