基于大页内存的学习索引内存分配策略_官嘉林.pdf

文章编号：1000-5641(2023)02-0073-09基于大页内存的学习索引内存分配策略官嘉林1,朱艳1,吴庭亮1,陈艳2,张敬伟1（1.桂林电子科技大学 广西可信软件重点实验室,广西 桂林541004;2.桂林航天工业学院 计算机科学与工程学院,广西 桂林541004）摘要:大数据时代,数据信息的不断膨胀给数据的快速存取带来了巨大挑战.因此,设计一种高效的索引结构具有重要意义.ALEX(updatable adaptive learned index)是一种利用机器学习模型代替传统 B-树索引结构的学习索引,具有较好的时间、空间性能,但存在频繁的缺页中断问题.为解决此问题,进一步提升ALEX 性能,在 ALEX 基础上提出了一种基于大页内存的内存预分配策略,较好地降低了内存缺页中断率,提升了 ALEX 性能.在内存分配阶段,采用预分配策略;在内存回收阶段,则采用延迟释放策略.在Longitudes 数据集上的实验表明,该策略具有良好的效果.关键词:学习索引;大页内存;数据存取中图分类号:TP392文献标志码:ADOI:10.3969/j.issn.1000-5641.2023.02.009A memory allocation strategy for learned index based on huge pagesGUAN Jialin1,ZHU Yan1,WU Tingliang1,CHEN Yan2,ZHANG Jingwei1（1.Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin,Guangxi541004,China;2.School of Computer Science and Engineering,Guilin University of AerospaceTechnology,Guilin,Guangxi541004,China）Abstract:In the era of big data and with the continuous expansion of data,there are significant challengeswith efficient access to data.Hence,designing an efficient index structure is of great significance.ALEX(updatable adaptive learned index)is a learned index that uses a machine learning model to replace thetraditional B-tree index structure.Although it offers good time and space performance,it suffers fromfrequent page faults.In order to solve this problem and further improve the performance of ALEX,amemory pre-allocation strategy based on huge pages is proposed,on the basis of ALEX,that can helpreduce the rate of memory page faults and improve the overall performance of ALEX.In the memoryallocation phase,the pre-allocation strategy is adopted,and the memory free phase adopts a delayed releasestrategy.Experiments on the Longitudes dataset show that this strategy offers good performance.Keywords:learned index;huge pages;data access 0 引言数据的快速存取具有重要意义,是支持和加快数据分析、数据挖掘等技术的重要技术基石.特别是随着当前大数据时代的到来,数据爆发式增长,达到千万亿字节(PB)级甚至数百 PB 级别,如何对 收稿日期:2021-09-09基金项目:国家自然科学基金(U1711263);广西自然科学基金(2018GXNSFAA281199,2020GXNSFAA159117);广西高校中青年教师基础能力提升项目(2018KY0651)通信作者:陈艳,女,高级实验师,研究方向为计算机软件技术与智能算法.E-mail: 第 2 期华东师范大学学报(自然科学版)No.22023 年 3 月Journal of East China Normal University(Natural Science)Mar.2023这些海量数据进行快速存取更具有重要的意义.对于当前金融科技的发展,同样如此.随着网上购物、移动支付等金融服务的快速发展,交易流水不再是以传统金融系统中较小量的大额交易记录为主导,转而以大量的较小额交易流水为主.如何快速存取这些交易流水信息,是当前关键的技术重点和难点.索引技术是常见的用于加速数据存取的重要技术1,由于其能产生较好的效果,因此存在大量关于索引技术的研究,出现了大量的、广泛应用于各大工业生产环境的索引结构,如 B-树、跳跃表、哈希索引、布隆过滤器等.过去的几十年里,大量的研究者针对索引结构的研究主要集中在内存效率、CPU 效率和缓存命中率,并取得了良好的效果2-6.然而,有研究表明,当前商用数据库中,索引结构仍然占据了服务器内存全部空间的 55%,极大地浪费了服务器的内存资源7;并且,随着数据规模的急剧增大,内存甚至可能无法容纳索引数据,从而将索引放到外存中,增加了服务器的 I/O(input/output)负担.O(logN)O(1)O(N)O(1)此外,B-树、跳跃表等索引结构均为通用性解决方案,不能很好地利用数据的分布特性,在很多场景下未必是最优解.例如,考虑当前有连续的、按时间戳排序的 100 万条交易数据流水,若采用 B-树或跳跃表进行索引,需要 的时间复杂度;但如果以时间戳为键进行偏移计算,则时间复杂度降低为 ,并且索引内存空间占用也从 降低为 .显然,数据分布特性能带来巨大的收益.机器学习能够对历史数据和行为进行分析,很好地利用了数据的分布特性.近年来,随着机器学习技术的快速发展,已经被广泛地运用到多个领域.如何借助机器学习的技术对传统的数据库系统进行优化,成为当前数据库领域的研究热点8.2018 年,Kraska 等9在 2018 年 SIGMOD(Special InterestGroup on Management of Data)会议上首次提出了学习索引(learned index)的概念,把索引结构看成机器学习模型,对数据分布特性进行学习,从而生成“定制化”的索引结构,能极大地提高数据的存取效率,同时,还能降低内存开销.当前,学习索引的研究和发展仍处在较初级阶段,具有广泛的发展前景.本文基于当前热门的支持动态更新的自适应索引框架进行优化.本文的主要工作有以下 3 个方面.(1)对 ALEX(updatable adaptive learned index)缺页问题进行了分析,并通过实验进行了验证.(2)针对 ALEX 缺页问题,提出了一种基于大页内存技术的内存预分配策略,此策略能极大地降低缺页中断率,从而产生良好的效果.(3)在真实数据集上进行的实验,证明了本文大页内存策略的效果优于原始的 ALEX.本文后续内容:第 1 章介绍相关技术研究和现状;第 2 章对 ALEX 存在的问题进行分析;第 3 章介绍基于大页内存的内存预分配策略;第 4 章对实验进行详细介绍;第 5 章总结全文,并对未来工作进行规划.1 相关技术研究和现状 1.1学习索引Kraska 等9提出了利用机器学习模型替换传统的索引结构的学习索引结构.他们认为,B-树索引结构可认为是一种模型,模型的输入为键,输出为该键对应的记录的位置;并且 B-树只索引内存块或磁盘页中的第一个键,这一特性既能减少索引键的数量,且不会对性能产生影响.这使得 B+树可看作是一棵回归树:将键映射为具有最大误差界限(error bound)的位置,如果记录存在,则可以在误差范围内找到.因此,可用其他具有相同特性的模型进行替换,如线性回归模型、神经网络模型等.然而,实际的数据分布不一定严格遵循特定的规律,故可以把数据的键和对应的记录在有序数组中的位置74华东师范大学学报(自然科学版)2023 年建模为累积分布函数(cumulative distribution function,CDF).相应公式为p=F(Kkey)N.(1)pF(Kkey)P(X Kkey)KkeyX KkeyN式(1)中:是预测的位置;是累计分布函数,用于估计概率 ,其中,表示第K 个键,表示小于第 K 个键的概率之和;是所有键的个数.基于以上思想,Kraska 等9提出了学习索引框架(learning index framework,LIF)和递归模型索引(recursive model index,RMI).LIF 能够学习并自动生成高效的 C+代码.RMI 模型类似于 B-树,是由多个模型组成的分层模型结构,由上层模型预测结果产生下层模型预测结果,直到最后一层模型,输入记录的预测位置.RMI 分层模型如图 1 所示，其中“数字.数字”表示的是“第某层模型.此层模型中的第某个”.实验结果表明,Kraska 等9提出的学习索引结构能在存储空间减少 2 个数量级的情况下,时间性能却能提高 1.5 3 倍,证明了学习索引的优势.模型 1.1模型 2.2模型 2.3模型 2.1模型 3.2模型 3.1模型 3.3模型 3.4.位置键图 1 RMI 分层模型Fig.1 Staged models in RMI 然而,Kraska 等9提出的学习索引模型存在着一些难以应用到实际生产环境的问题,如:(1)其在数据划分上采用均等划分,未考虑到数据之间的相关性;(2)不支持数据的插入操作,只能作用于读负载,这大大地减少了其应用的场景.1.2支持数据动态更新的学习索引针对索引更新问题,目前已有研究人员提出了一些解决办法.Ding 等10在 2020 年 SIGMOD 会议上提出了一种新的内存索引ALEX,利用间隙数组(gapped array)支持数据动态更新的自适应学习索引.ALEX 继承了 RMI 的层级结构,但修改了叶子结点模型(RMI 的最后一层模型)的数据结构,把有序数组变成了一个自定义结点结构,并把二分查找修改为了指数查找(exponential search).ALEX 结构见图 2 所示.与 Kraska 等9提出的学习索引结构相比,ALEX 空间占用仅为其 1/3000,而查找性能却提高了 2.7 倍,同时提供了数据插入能力;与 B+树相比,ALEX 将空间性能降低了 5 个数量级,而查找性能亦提高了 3.5 倍,且插入性能也略优于 B+树10.此外,Li 等11提出的 ASLM(adaptive single layer model),放弃了层次化思路,采用贪心策略划分数据,再分配到合适的子模型;Wu 等12提出的 LIPP(learned index with precise positions),通过适当拓展树结构,消除模型在叶结点中预测的位置偏差,从而得到精确的位置,他们同时提出了一种基于FMCD(fastest minimum confict degree)算法的动态调整策略,确保了索引的高度.2 缺页中断分析 2.1A