LI-Tree:一个基于非易失性内存和轻量级B+树的学习索引
2023-05-23王中华舒碧华陈书宁刘瀚阳万继光
小型微型计算机系统 2023年6期
王中华,舒碧华,陈书宁,刘瀚阳,崔 秋,万继光
1(华中科技大学 武汉光电国家研究中心,武汉 430074)
2(北京平凯星辰科技发展有限公司,北京 100192)
1 引 言
数字时代下,急剧增长的数据量[1]对存储系统提出了更高的容量、性能和成本挑战[2].然而,对存储系统性能至关重要的经典内存索引结构却无法满足当前的需求[3].一方面,传统DRAM内存面临着容量和能耗等方面的问题[4],另一方面,经典范围索引结构经过多年发展,其结构弊端明显且优化空间有限[5].
在设备方面,为了进一步逼近性能、价格与容量的博弈极限,工业界推出了新型非易失性内存(Non-Volatile Memory,NVM)[6],它拥有堪比固态驱动器(Solid State Drive,SSD)的容量和接近DRAM的性能.除此,NVM还具备按字节寻址、快速访问、掉电非易失、静态功耗低等优良特性,是构建下一代存储索引结构的重要存储介质[7].然而NVM也存在一些缺点,例如读写不对称[8]、非易失性带来的一致性问题等[9,10].所以基于DRAM设计的索引结构无法直接部署到NVM使用,尤其是NVM支持超大容量,而传统的面向DRAM的索引结构基本无法在大数据量下支持较高性能的索引性能[11].
在软件方面,大数据背景下大放异彩的机器学习模型为海量数据索引提供了新思路-学习索引结构(Learned Index,LI)[12].现在绝大多数键值存储系统中,将存储其中的键值对(Key-Value)按关键字排序是后续高效处理数据的前提,因此键值对在存储系统中的地址与其关键字存在一对一映射.B+树及其派生的索引结构[13,14]通过从根节点到叶节点的跳转来实现这……
登录APP查看全文
