LI-Tree：一个基于非易失性内存和轻量级 B+树的学习索引_王中华_PingCAP.pdf
免费下载
小 型 微 型 计 算 机 系 统
Journal of Chinese Computer Systems
收稿日期：2021-10-12 基金项目：国家自然科学基金创新研究群体项目（No.61821003)资助；国家自然科学基金面上项目（No.62072196)资助；深
圳市科技计划基础研究面上项目（JCYJ20190809095001781）资助。 作者简介：王中华，女，1994 年生，博士研究生，研究方向为大数据存储、键值存
储系统、非易失性内存和学习索引等；舒碧华，男，1996 年生，硕士研究生，研究方向为大数据存储、键值存储系统、非易失性内存和学习索引等；陈
书宁，男，1994 年生，公司员工，研究方向为键值存储系统、分布式存储等；刘瀚阳，男，1996 年生，公司员工，研究方向为键值存储系统、分布式存
储等；崔秋，男，1994 年生，公司员工，研究方向为大数据存储、键值存储系统、非易失性内存和学习索引等；万继光，男，1972 年生，博士，教授，
研究方向为大数据存储、键值存储系统、文件系统、分布式存储和智能化存储等；
LI-Tree：一个基于非易失性内存和轻量级 B+树的学习索引
王中华
1
，舒碧华
1
，陈书宁
2
，刘瀚阳
2
，崔 秋
2
，万继光
1,3
1
（武汉光电国家研究中心, 华中科技大学计算机学院，教育部信息存储系统重点实验室 武汉 430074）
2
（北京平凯星辰科技发展有限公司 北京 100192）
3
（深圳华中科技大学研究院 深圳 518000）
E-mail：wangzhonghua@hust.edu.cn
摘 要：大数据背景下剧增的数据给经典的内存索引技术带来了巨大挑战，为了实现对海量数据的高性能索引，工业界和学术
界分别从设备和结构角度推出了高性能大容量的非易失型内存(Non-Volatile Memory, NVM)和受机器学习启发的学习索引
(Learned Index, LI)。然而目前基于 NVM 的学习索引结构的相关研究非常稀少，在如何结合 NVM 和 LI 来高效地索引海量数据
方面还有许多问题需要解决。本文提出了一种基于 NVM 的新型智能索引结构 LI-Tree，充分发挥了两者的优势。具体的，LI-Tree
可分为三层：由机器学习模型组成的能够提高 LI-Tree 单点性能的模型层、由静态数组构成的减少 NVM 写的数据索引层和由一
系列轻量级 B+树组成以避免模型层插入时频繁重训练的数据层。在真实设备上评估表明，LI-Tree 相比传统 B+树，插入、查询
和删除性能分别提高了 70%、30%和 130%。另外，LI-Tree 与学习索引结构 ALEX, PGM-Index 和 XIndex 对比，插入性能分别提升
了 80%，130%和 150%。
关键词：非易失内存；索引结构；学习索引；B+树；键值存储
中图分类号：TP392 文献标识码：A
LI-Tree
：
A Learned Index based on Non-Volatile Memory and Lightweight B+ Trees
WANG Zhong-hua
1
, SHU Bi-hua
1
, CHEN Shu-ning
2
, LIU Han-yang
2
, CUI Qiu
2
, and WAN Ji-guang
1,3
1
(Wuhan National Laboratory for Optoelectronics, School of Computer Science & Technology in Huazhong University of Science and Technology, and Key
Laboratory of Information Storage System Ministry of Education of China, Wuhan, 430074)
2
(PingCAP©, Beijing, 100192)
3
(Research Institute of Huazhong University of Science and Technology in Shenzhen, Shenzhen, 518000)
Abstract：The dramatic growth of data volumes in the era of big data poses challenges to in-memory indexing techniques in terms of
both devices and data structures. Commercial Non-Volatile Memory (NVM) devices are now available as the supplement of or
alternative for memory, and the new Learned Index (LI) data structures are proposed for indexing massive data in read-heavy scenarios.
However, naively applying LI on NVMs is not efficient due to the heavy retraining overhead for LI when data size growing. In this work,
we present the LI-tree, an NVM-oriented learned index structure that maximizes LI's write performance while fully exploiting LI's read
performance. Specifically, the LI-Tree consists of three layers: a model layer composed of machine learning models that target on
improve point query performance, a data index layer consists of static arrays to reduce NVM write operations, and a data layer that uses
lightweight B+ trees to alleviate the training overhead of the other two layers for insert operations. Evaluation results on real NVM
devices show that LI-Tree improves the performance of insert, query, and delete operations by 70%, 30%, and 130%, respectively,
compared to the traditional B+ tree. LI-Tree improves the insert performance by 80%, 130%, and 150% when compared to ALEX,
PGM-Index, and XIndex, respectively.
Key words：Non-Volatile Memory, Indexing Structure, Learned Index, B+ tree, Key-Value Storage
1 引言
数字时代下，急剧增长的数据量对存储系统提出了更高
的容量、性能和成本挑战
[1]
。然而，对存储系统性能至关重
要的经典内存索引结构却无法满足当前的需求
[2]
。一方面，
传统 DRAM 内存面临着容量和能耗等方面的问题
[3]
，另一方
面，经典范围索引结构经过多年发展，其结构弊端明显且优
化空间有限
[4]
。
在设备方面，为了进一步逼近性能、价格与容量的博弈
极限， 工 业 界 推 出 了 新 型 非 易失性内存 (Non-Volatile
Memory, NVM)
[5]
，它拥有堪比固态驱动器 (Solid State
2
小 型 微 型 计 算 机 系 统
1
由于 APEX(参考文献
[13]
)的代码难以获取，因此本文无法进行对比测试。
Drive, SSD)的容量和接近 DRAM 的性能。除此，NVM 还具备
按字节寻址、快速访问、掉电非易失、静态功耗低等优良特
性，是构建下一代存储索引结构的重要存储介质
[6]
。然而 NVM
也存在一些缺点，例如读写不对称
[7]
、非易失性带来的一致
性问题等
[8][9]
。所以基于 DRAM 设计的索引结构无法直接部署
到 NVM 使用，尤其是 NVM 支持超大容量，而传统的面向 DRAM
的索引结构基本无法在大数据量下支持较高性能的索引性
能
[10]
。
在软件方面，大数据背景下大放异彩的机器学习模型为
海 量 数 据 索 引 提 供 了新 思 路 - 学 习 索 引 结 构 (Learned
Index, LI)
[11]
。现在绝大多数键值存储系统中，将存储其中
的键值对(Key-Value)按关键字排序是后续高效处理数据的
前提，因此键值对在存储系统中的地址与其关键字存在一对
一映射。B+树及其派生的索引结构
[14][15]
通过从根节点到叶节
点的跳转来实现这个映射关系，所以与数据量正相关的树高
度很大程度上决定了映射性能在海量数据下的低效性
[16]
。哈
希索引虽然可以通过计算直接实现关键字到地址的映射，但
是牺牲了关键字之间的有序性。LI 的思想是利用机器学习
模型
[17][18]
来实现这个映射，该模型既可以通过计算在常量级
别的时间复杂度内预测出一个关键字的位置又保留了关键
字之间的有序性。
为了构建适应海量数据的索引结构，现在有两种优化改
进方向，一是对传统索引结构进行适应 NVM 的优化，二是基
于 DRAM 的非传统的学习索引的性能优化。学习索引对大量
数据的优秀性能和非易失、大容量的 NVM 的结合是天然适配
的，然而两者的简单结合很难获得收益
[12]
。据我们调查，目
前基于 NVM 的 LI 研究
1
非常稀缺
[13]
，在如何结合 NVM 和 LI
来高效地索引海量数据方面还有许多问题需要解决。在对
NVM 硬件性质、传统索引结构性能和 LI 结构优势深入研究
后，本文设计了一种基于 NVM 的智能索引结构 LI-Tree，它
充分利用学习索引的快速索引性能，通过学习索引降低 B+
树的高度来提高结构的查找性能，并且设计结构扩展算法来
保证 LI-Tree 在数据量不断增长的情况下仍能保持良好的
性能。
本文的主要贡献如下：
1) 对 NVM 设备特性、传统 B+树索引结构和当前 LI 索
引结构进行大量实验，分析利弊，为设计更为高效的索引架
构奠定基础。
2) 针对 1)中分析的结果，设计了一种新的基于 NVM
的索引结构 LI-Tree，使用学习模型降低 B+树索引结构高度，
从而提高索引性能。此外，为了在数据不断增长的前提下保
证索引性能，本文还为 LI-Tree 设计了扩展算法将其访问路
径维持在一个较低的高度。
3) 在真实的 NVM 产品上实现了 LI-Tree 索引结构，同
时将现有的几种代表性索引结构也移植到 NVM 上，并将它们
与 LI-Tree 进行了详细的对比和分析，验证了 LI-Tree 的高
效性。
2 相关工作
本节首先介绍了当前国内外在学习索引结构方面的相
关研究，及其结构对性能的影响。然后介绍了大量基于 NVM
的索引结构的相关研究工作，并着重阐述了优化方向和优化
效果。
2.1 学习索引结构的相关工作
最初对学习索引进行初步尝试的 Kraska 等人
[11]
将常见
的范围索引 B+树看作是一个模型，它的输入是一个 key，输
出是 key 对应的 value 在排序数组中的位置，这个位置是
value 所在内存块或磁盘页中第一个 key 的位置。作为一个
探索性工作，它仅支持只读负载。
为了更适用于真实负载，许多工作试图对学习索引进行
支持写操作优化。FITing-Tree
[19]
将已排序的数组按照范围
划分为多个段，查找时使用 B+树来索引到段，每个分段中
使用线性函数来拟合数据分布。同时每个段内预留缓冲区来
容纳写入数据，缓冲区写满时，对数据进行重排序和重训练。
ALEX
[20]
使用类似 B+树的结构，在节点中使用线性模型索引。
同时，通过在已排序的数据数组中预留槽来支持写操作，当
没有足够的预留插槽时，重新建立排序数组和重训练模型。
PGM-index
[21]
使用类似 LSM-tree 的方式来保存数据，但只在
最后底层存储数据，并在该层维护一个学习索引模型，而其
余层被用作写缓冲区，最后一层合并数据时更新索引模型。
此外，为了减少频繁重训练的代价，PMG-index 还使用了高
效的重训练方案。XIndex
[22]
使用分段线性拟合的策略建立学
习索引，每个分段内使用缓冲区来支持写操作，缓冲区满时
进行重排序和重训练，另外，XIndex 还使用一些锁机制来
保证学习索引的并发写。Dabble
[23]
使用 K-Means 算法将数据
划分为互不相交的 K 个区域，在每个区域内，使用一个双层
神经网络模型拟合函数位置。同时，Dabble 使用 LSM-tree
方式来延迟数据更新。
除了上面这些使用机器学习方式完全取代传统 B+树方
案，还有些工作使用机器学习作为传统数据结构的辅助。
IFB-Tree
[24]
在建立 B+树索引时判断每个节点是否是插值友
好的，即节点中所有数据使用插值搜索的误差都小于阈值，
如果是则在节点中使用插值搜索，否则使用传统 B 树节点。
综上所述，当前 LI 主要是针对支持写操作或者并行写
操作的优化，主要的支持机制有三种：建立写缓冲区法，预
留排序空间法和插值法。然而，写缓冲区法存在缓冲区内查
找慢和缓冲区写满后数据重排序和模型重训练开销的问题
[22]
；预留空间法中索引密度与重训练频繁存在博弈，当索引
密度大时重训练频繁，当索引密度小时，空间浪费严重；插
值法虽然一定程度上加快了查找，但并没有改变 B+树随数
据量变大导致访问路径变长的缺陷。
2.2 基于 NVM 的索引结构优化的相关工作
为了更好的将 NVM 应用于存储系统，提升数据查询和空
of 13
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论