实验室博士生李鹏飞的论文“FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems”被The 48th International Conference on Very Large Data Bases (VLDB 2022)作为长文全文录用。

高效的索引结构对于提升内存系统的性能非常重要，尤其是最近提出的学习索引结构获得了巨大的性能提升。但是现有的学习索引方案由于模型和数据结构的依赖性，在可扩展和并发的系统中引入了过多的资源竞争，使得插入大量数据后性能下降，且无法在不阻塞其他操作的情况下高效地支持并发重训练。因此现有的学习索引方案不适用于可扩展的并发内存系统。

博士生李鹏飞在华宇教授的指导下为并发内存系统设计了细粒度的可扩展学习索引方案，称为FINEdex。为了减少多线程之间的资源竞争，FINEdex使用自适应的学习算法得到了互相独立的模型，并采用平坦的数据结构level bin来处理新插入的数据。在并发的环境中能够快速搜索并修改任意模型而不影响其他模型的使用，且level bin置于每个训练数据之后而非整个模型共享，从而减少了数据之间的依赖。对于动态的数据分布，FINEdex通过两种粒度的重训练算法在运行中学习新的数据分布规律，同时不影响其他操作的正常执行。在系统及真实的工作负载上的测试结果表明，相较于最先进的学习索引方案，FINEdex可以在不受重训练延迟影响的情况下提升约1.8倍的扩展性能。

该研究工作得到了国家自然科学基金（62125202）项目的资助。

图1 FINEdex的整体结构图

图2 FINEdex在不同情景下的插入性能