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

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

3.2 点查找
如图 3 红色箭头所示, 点查找操作先在索引内部节点中查找给定键, 确定键所在的叶节点地址和元数据地址
(①②③). 当查找到达叶节点的上一层内部节点时, 根据该内部节点存储的叶节点的模型参数计算出目标键在叶
节点 block 数组中的位置和对应的块元数据地址. 由于避免了局部查找, 每层内部节点的查找只需要访问 32 B 的
数据, 提升了缓存命中率, 每个内部节点中只需访问一个 PM 块, 节省了 PM 带宽资源. 在叶节点查找键的过程中,
首先读取块元数据中的指纹 (④). 如果存在匹配的指纹, 则继续在叶节点 block 中比较该位置处的键 (⑤). 如果元
数据的指纹匹配失败, 则跳过叶节点的访问, 直接进入溢出缓存中继续查找 (⑥⑦). 与 APEX 和 PLIN 相比, 当键
在叶节点中不存在时, PLTree 只会产生 1 个缓存行的 DRAM 访问. 而在 APEX 和 PLIN 中, 无论键是否存在于叶
节点, 都必须先在叶节点中进行查找, 并产生至少 1 个 PM 块的访问. 通过设置块元数据, PLTree 可以充分利用
DRAM 高带宽特性, 减少 PM 访问次数, 合理利用有限的 PM 带宽资源.
如图 2 红色箭头所示, 当进入溢出缓存中查找键时, PLTree 首先使用 SIMD 指令在缓存元数据中逐层查找是
否存在匹配的指纹 (❶❷). 如果存在指纹匹配, 则继续在溢出缓存中对应的 entry 中从右至左比较指纹匹配的键
(❸), 若键相同直接返回结果, 无需继续向左和向下层继续查找, 因为后面的即使存在相同的键也是旧数据. 当键
存在时, 溢出缓存中查找操作最少只需进行一个缓存行的 DRAM 读取和一个 PM 块访问. 当键不存在时, 溢出缓
存中的查找开销为 N 个缓存行的 DRAM 访问 (N 为溢出缓存的层数), 而不会产生额外的 PM 访问.

3.3 插入更新
如图 3 红色箭头所示, 与查找操作的相同, 插入更新操作需要先在内部节点中定位键所在的叶节点以及对应
的元数据 (⑧⑭⑨). 在叶节点中, 使用原地更新和日志式插入的方式将键值对写入预测的 block 中. 在此过程中, 如
果溢出缓存中已经存在与待插入键重复的数据, 在后续查询操作中, 这些重复数据将会被视为过期或旧数据.
PLTree 对分布不均匀的真实工作负载进行了优化: 避免了插入数据之前在溢出缓存对键进行唯一性检查. 因为在
PLTree 中, 只需确保关键字在叶节点中是唯一的, 允许溢出缓存中的键存在重复. 因此, 在插入键值对之前, 只需
要在叶节点的 block 中进行键的唯一性检查, 而无需继续在溢出缓存中查找该键. 具体的做法是, 在插入键值对之
前, 先在块元数据和叶节点中查找键是否存在 (⑩⑪). 如果键已存在, 则会在 block 中原地更新键值对的值, 由于值
的大小为 8 B, 在写入时采用 8 B 原子写入 PM, 并使用内存屏障 SFENCE 指令 [39] 隔离后续的写指令, 因此程序崩
溃时不会出现中间状态. 如果键在 block 中不存在, 就以追加的方式将键值对写入到 block 的空闲槽位中 (⑫), 并
将键的指纹加入块元数据的指纹数组之中. 键值对采用先写入值 (8 B) 再写入键 (8 B) 的方式持久化, 使用
SFENCE 指令隔离后续的写指令, 确保系统崩溃发生在值写入和键写入之间时, 槽位中的键仍为空闲标志, 避免无
效键值对的写入. 上述插入方式避免了额外的 PM 访问, 因为键的唯一性检查只在叶节点中进行.
当叶节点产生由冲突导致的溢出时, APEX 和 PLIN 每次只往溢出缓存中写入一个 16 B 大小的键值对 (写放
大为 16, 一个 PM 块 256 B/键值对大小 16 B). 针对 PM 中由数据访问粒度不匹配引发的写放大问题, PLTree 进行
了优化: 在叶节点 block 产生溢出时选择将整个 block 的数据批量地写入到溢出缓存中 (⑲), 当 PLTree 叶节点中
某个 block 中的数据全部写入溢出缓存第 0 层的同一个 entry 时, 写放大最小可降低至 1.07 (一个 PM 块 256 B/
block 中的数据 240 B). 通过批量写入数据的方式, 能够根据 PM 的特性, 减小 PM 中的写放大. 此外, 每次批量写
入还可以均摊数据持久化和内存屏障指令带来的开销, 从而提升系统的性能表现.
批量写入完成后, 需要通过设置空闲标志将叶节点中 block 槽位标记为空闲, 并清除对应块元数据中的指纹
数据. 在批量写入缓存和将 block 槽位设置为空闲时, 即使发生系统崩溃, 也不会影响索引的一致性. 这是因为
PLTree 支持存储关键字重复的数据, 可以分为两种情况讨论: (1) 批量写入溢出缓存时发生系统崩溃. 此时可能有
一部分键值对已经被写入溢出缓存中, 在叶节点 block 中的键值对未被改变, 因此系统恢复后, 叶节点中的数据仍
旧存在, 对查找操作没有影响. 写入溢出缓存中的部分键值对会被当做旧的数据, 下一次批量写入时, 键重复的旧
数据会被覆盖. (2) 将叶节点 block 槽位设置为空闲时系统崩溃. 此时 block 中的键值对已经全部写入溢出缓存, 叶
节点 block 中可能存在部分键值对未被置空, 由于此时 block 中的键值对已经全部写入溢出缓存, 系统恢复后, 并