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

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


                 不会产生数据的丢失, block     与溢出缓存中重复数据将在下一次数据从               block  批量写入溢出缓存时合并.
                    溢出缓存采用分层的结构来存储批量写入的数据. 为了减小写放大, 当一层中某个条目数据写满时, 该条目数
                 据会批量移入下一层        (如图  2  中❹❺). 批量写入前会合并键重复的数据, 并删除旧数据. 批量写入完成后, 更新与
                 条目对应的缓存元数据指纹信息. 随着数据的插入, 溢出缓存中的层数将会增加. 如果溢出缓存层数过多, 将导致
                 查找性能和范围查找性能下降. PLTree 通过扩展叶节点来解决性能下降的问题. 然而, 频繁地调整叶节点也会带
                 来大量的开销. 为了避免这种开销, 在叶节点插入数据时通过计算叶节点溢出缓存的平均层数                             (avgLevel=levelnum/
                 size, levelnum  为叶节点中溢出缓存层数的总和, size 为     block  数组长度) 来判断是否需要进行叶节点扩展. 只有当
                 叶节点中溢出缓存的平均层数超过一定阈值时, 才考虑对叶节点进行扩展. 在节点扩展时会对叶节点中的键重复
                 的数据以及标记为删除的数据进行清理以减轻冗余数据带来的存储开销.

                 3.4   删 除
                    如图  3  红色箭头所示, 删除操作以键值对插入的方式进行. 当需要删除数据时, 首先在内部节点查找定位到包
                 含目标键的叶节点       block (⑬⑭⑮). 然后, 在该  block  中检查键是否存在: 若存在, 则将对应的值标记为已删除; 若
                 不存在, 则将键和删除标志作为键值对插入到               block  中  (⑯). 在后续执行查找操作时, 若找到的键值对中值被标记
                 为删除, 则直接返回查找失败. 当         block  满时, 其中标记为删除的数据会随着其他有效数据一起被批量写入溢出缓
                 存中. 溢出缓存中标记为删除的数据会在节点扩展时被清除, 以减轻出现大量删除操作时, 溢出缓存中过多的冗余
                 数据导致的索引性能下降和额外存储开销.

                 3.5   范围查找
                    如图   3  红色箭头所示, 范围查找首先使用查询范围的最小键执行查找操作, 定位键所在的起始叶节点
                 (⑰②③). 然后, 根据模型定位      block  数组中第一个存储大于等于该键的           block  位置  (⑩), 并向后查找  (⑱). 叶节点
                 之间以链表结构相连, 如果当前叶节点的查找结束, 则会继续查找下一个叶节点, 直到链表末尾或查找范围结束.
                    叶节点中的范围查找从叶节点中指定的起始                 block  开始顺序遍历   block  数组, 并在  block  及其关联的溢出缓
                 存中查找符合查找范围的键值对并添加至结果集合. 当访问每个                     block  时, 首先读取其中的数据, 并将查询结果加
                 入结果集合. 然后继续进入        block  对应的溢出缓存中逐层逆序读取         entry  数组中的有效数据, 同样将符合条件的数
                 据合并到结果集中. 访问完一个          block  及其对应溢出缓存后更新查找结果集合, 具体包括如下操作: 合并相同键的
                 键值对, 移除标记为删除的键值对, 以及在集合大小超出查找范围时删除多余的键值对.

                 3.6   索引恢复
                    当系统重启或发生崩溃导致           DRAM  中的元数据丢失时, PLTree 采用延迟恢复策略按需重建元数据. 具体的
                 做法是设置了全局的索引版本字段             global_v. 在恢复过程中, 首先将该字段加       1, 然后通过遍历叶节点的链表来更
                 新指向叶节点的槽位中的字段           v. 如果索引不是正常关闭, 则需要在遍历叶节点时检查                 fptr 指向的父节点槽位中
                 字段  child  指针是否正确指向自身, 如果不正确, 则更新          child  指针. 在后续的索引查询过程中, 通过比较存储在块
                 元数据中的索引版本字段         v  和槽位中的字段    v  是否相同, 来确定是否重建元数据.

                 3.7   并发操作
                    在并发读写过程中, 应尽量减少对           PM  的访问. 例如先前的方法      [24] 使用了存储在  PM  中的版本锁. 当写操作获
                 取锁时可能遭遇阻塞并且需要频繁读取锁状态. 读操作为了确保数据的一致性, 需要两次读取锁的版本号. 这都会
                 增加不必要的     PM  带宽消耗. 此外, 完成写操作后更新锁版本也可能带来额外的                  PM  写操作. 另外, 驻留在    PM  中
                 的锁在系统崩溃时也有可能导致树永远持有锁, 处于不一致的状态.
                    PLTree 采用了轻量级的乐观锁        (optimistic locking) 实现高并发的读写操作. 如图   2  左所示, 在块元数据中, 为
                 每个  block  和相应的溢出缓存存储了       1 bit 锁  (lock  字段) 和  31 bits 版本信息  (version  字段). 写操作线程使用比较
                 并交换   (compare and swap, CAS) 指令原子地设置目标   block  的锁. PLTree 采取了同步锁定目标     block  和溢出缓存
                 的策略, 这样即使在系统崩溃的情况下, 也能确保障数据的完整性与一致性. 当写线程成功获取锁时, 此时只有一
   424   425   426   427   428   429   430   431   432   433   434