APLI:一种基于持久化内存的高性能学习索引

APLI:a High-performance Learned Index for Persistent Memory

持久化内存(Persistent Memory,PM)已成为容量有限的DRAM的最有潜力的补充或者替代品.学习索引(Learned Index,LI)作为一种感知数据分布的索引结构,在大数据集上能够以较小的内存使用量展现远优于B+树的性能而被广泛关注.最近,一些研究者尝试将学习索引部署在持久化内存中,然而现有的持久化学习索引存在读写性能次优化、结构扩展性不足、动态负载性能不统一等问题.为此,本文在深入分析了持久化内存和学习索引特性的基础上,提出了一种自适应的持久化学习索引结构APLI.APLI由两部分组成:1)高效的混合介质的持久化学习索引树(EPL-Tree),提供稳定的读写性能和结构扩展;2)轻量级的哈希表(SW-Table),用于快速感知负载变化并提升热点访问的性能.在持久化内存真实设备上的评估表明,相比现有的持久化索引结构,APLI读写性能最高分别提升3.2倍和3.3倍,而且拥有更稳定的结构扩展性能.另外,APLI能在较小的DRAM空间占用前提下,实现各种负载场景下的稳定高性能访问.

Persistent memory(PM)has emerged as the most promising complement or alternative to limited and expensive DRAM.Recently,learned indexes exploit data distribution and have shown great potential for some workloads,so some researchers experimentally deployed them in PM.However,there are obvious limitations to these persistent learned index structures.First,their design for PM is sub-optimal;Second,their scalability is terrible.Third,they do not take dynamic workloads into account.In this paper,we propose a novel persistent learned index-APLI based on an in-depth analysis of persistent memory and learned index.APLI consists of two components:an efficient PM-optimized learned index tree(EPL-Tree)and a lightweight workload-aware hash table(SW-Table).EPL-Tree delivers stable high read/write performance and scalability in growing data volumes,and SW-Table can quickly sense workload changes and improve the performance of skewed workloads.Evaluation on real PM devices shows that compared with the state-of-the-art persistent index structures,APLI not only improves read and write performance by 3.2 times and 3.3 times respectively but also has better scalability performance.In addition,APLI achieves stable high performance for various workloads with a smaller DRAM occupation.