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

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

将叶节点中局部搜索范围限制在 1 个 PM 块内.

2.3 溢出缓存
在面对分布不均匀的真实负载时, 学习索引往往无法很好地适应数据的分布, 这会导致叶节点中出现大量冲
突, 进而降低读写性能. 特别是在 PM 中, 性能下降更为明显. 使用 face 数据集 [26] 进行测试时, 发现在 APEX 和
PLIN 中初始化加载 1 亿个数据后, 约 30%–50% 的数据会被写入溢出缓存, 从而导致大部分操作在访问叶节点之
后, 需要额外访问溢出缓存. 因此, 在面对用线性模型难以拟合的真实负载时, 溢出缓存将成为持久化学习索引的
性能瓶颈. 为了解决面对真实数据负载时持久化学习索引拟合数据分布不佳导致的性能问题, 本文受到先前的工
作 [12,20,36] 启发, 采用了一种类似 LSM 树 (log-structured merge tree) [36] 的分层日志式的写优化结构来存储由于冲突
而溢出的数据, 优化大量数据写入溢出缓存时的性能.
溢出缓存只有在产生数据溢出的情况下才会创建, 并根据溢出的数据量动态创建新的缓存数据层. 如图 2 右
所示, 缓存结构中的每一层都包含一个地址按 256 B 对齐的条目 (entry) 数组, 每向下一层, 该数组的长度扩大一
倍. 每个 entry 可以存储 48 个键值对, 其中存储的键无序且允许存在重复. 在缓存结构每一层中, 为每个 entry 设置
了一个 8 B 的 size 字段, 用于记录该 entry 中已经写入键值对的有效数量. 一旦某个 entry 完成批量写入操作, 其对
应的 size 会被更新, 上一层对应 entry 的 size 则被置为 0. 其中 size 字段通过 8 B 原子写操作写入到 PM 中, 以确
保崩溃一致性.

图 2 元数据结构 (左) 和溢出缓存结构 (右)

不同于 LSM, 缓存结构在每个层级的 entry 数组中采用哈希表进行索引. 哈希值冲突的键会被放置于同一个
entry 中. 由于 entry 数组的长度设置为 2 的幂次方, 因此在第 n 层, 需要使用键哈希值的低 n+1 比特来确定 entry
在数组中的位置. 在第 n 层中查找键时, 需对哈希值的低 n+1 比特位进行左右翻转以确定实际存储的 entry. 因为
条目数组中的 entry 按照键哈希值低 n+1 比特左右翻转后的顺序排列. 如图 2 右所示, 在第 2 层需要使用键哈希值
的 0–2 比特位进行索引, 二进制数 000 经过左右翻转后为 000, 代表键在 entry 数组中位置为 0; 二进制数 100 经过
翻转后为 001, 代表键在 entry 数组中位置为 1. entry 数组中这种比特位翻转排序方式确保了上一层同一 entry 中
的数据能够被尽量写入下一层地址连续的两个 entry 之中. 举例来说, 如图 2 右所示, 当第 1 层的 entry10 满时, 其
中的数据会被写入第 2 层的 entry010 和 entry110 中. 这样可以使数据能够批量写入连续的内存空间, 充分利用持
久化内存顺序写具有较高性能的特点, 提高写入带宽的利用利率, 优化写入性能.
此外, 在将数据写入下一层 (n+1 层) entry 时, 需要先计算第 n+1 层的 entry 中是否有足够的空闲位置. 若有充
足空间, 第 n 层的数据会以日志追加的方式从左到右写入 n+1 层的 entry 中, 确保新数据始终位于 entry 中右侧.
当 n+1 层 entry 空间不足时, 需要将第 n+1 层 entry 中的数据批量写入 n+2 层, 若下层空间仍然不够, 则继续按照
上述方法递归执行. 在这一过程中, 上层 entry 中重复的键值对将会被清理, 只保留最新的键值对, 再将其批量写入
下一层. 实验研究表明 [37] , 对于超过 256 B 的访问, 使用非临时写入指令具有更低的延时. 因此, 为了提高批量写入
的性能, 每次向下层写入数据时, 均采用非临时写入指令进行批量写入.

2.4 元数据
PLTree 在 DRAM 中存储了叶节点中每个 block 以及对应的溢出缓存中键的指纹信息和每个 block 的锁信息.
如图 2 左所示, 元数据分为块元数据和缓存元数据, 具体结构如下所述.