面向非易失内存的异构索引-刘睿诚，张俊晨，罗永平，金培权.pdf

上善若水

172

17页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(3):832−848 [doi: 10.13328/j.cnki.jos.006456] http://www.jos.org.cn

面向非易失内存的异构索引

∗

刘睿诚

1,2

张俊晨

1,2

罗永平

1,2

金培权

1,2

(中国科学技术大学计算机科学与技术学院, 安徽合肥 230026)

(中国科学院电磁空间信息重点实验室(中国科学技术大学), 安徽合肥 230026)

通信作者: 金培权, E-mail: jpq@ustc.edu.cn

摘要: 非易失内存(non-volatile memory, NVM)为数据存储与管理带来新的机遇, 但同时也要求已有的索引结构

针对 NVM 的特性进行重新设计. 围绕 NVM 的存取特性, 重点研究了树形索引在 NVM 上的访问、持久化、范围

查询等操作的性能优化, 并提出了一种上下两层结构的异构索引 HART. 该索引结合了 B+树与 Radix 树的特点,

同时利用了 Radix 结点搜索快以及 B+树范围查询性能好的优点. 对整体架构进行了精心设计, 改进了 Radix 树的

路径压缩策略, 设计了 NVM 写友好的结点结构, 并将 Radix 树叶结点集中存储和链接. 同时在仿真 NVM 设备以

及傲腾真实 NVM 平台上进行了实验, 对比了 HART 的不同衍生变种的性能, 并与多个 NVM 索引进行了对比. 结

果表明, HART 的写性能和点查询性能优于现有的类 B+树索引, 范围查询性能优于基于 Radix 的 WOART 索引, 具

有较好的综合性能.

关键词: 非易失内存; 索引; 两层结构; 读写优化; AR T 树

中图法分类号: TP311

中文引用格式: 刘睿诚, 张俊晨, 罗永平, 金培权. 面向非易失内存的异构索引. 软件学报, 2022, 33(3): 832–848.

http://www.jos.org.cn/1000-9825/6456.htm

英文引用格式: Liu RC, Zhang JC, Luo YP, Jin PQ. Heterogeneous Index for Non-Volatile Memory. Ruan Jian Xue Bao/ Journal of

Software, 2022, 3 3(3): 832−848 (in Chinese). http://www.jos.org.cn/1000-9825/6456.htm

Heterogeneous Index for No n-volatile Memory

LIU Rui-Cheng

1,2

, ZHANG Jun-Chen

1,2

, LUO Yong-Ping

1,2

, JIN Pei-Quan

1,2

(School of Computer Science and Technology, Univ ersity of S cience and Technology of China, Hefei 230026 , China)

(Key Laboratory of Electromagnetic Space Information (University of Sci ence and Technology of China), Chinese Academy of Sciences,

Hefei 230026, China)

Abstra ct : Non-vol atile memory (NVM) introduces new opportuniti es to data storage and management, but it also requires existing indices

to be revisited according to the properties of NVM. This study, based on the access characteristics of NVM, focuses on the performance

optimization of the access, persist ence, r ange query, and other operations of tr ee indexes on NVM. A two-layer h eterogeneous index called

HART is presented. HART takes advantage of the high range query performance of the B+-tree and the fast node search speed of the

Radix tree. The index structure is redesigned and the strategy of path compression for the Radix tree is improved. Moreover, a

write-efficient node is proposed for NVM and the Radix leaf nodes together with a link are stored. The experiments are conducted on both

simulated NVM and real Intel Optane persistent memory modules and different variants of HART are compared to several existing NVM

indices. The results show that HART achieves better performance for point queries and writes than existing B+tree-like indices. In

addition, it outperforms the existing Radix-tree-based WOART index in range query performance. As a result, HART can deliver high

overall performance.

∗ 基金项目: 国家自然科学基金(62072419)

刘睿诚和张俊晨在本文工作中有同等贡献.

本文由“数据库系统新型技术”专题特约编辑李国良教授、于戈教授、杨俊教授和范举教授推荐.

收稿时间: 2021-0 6-30; 修改时间: 2021-07-31; 采用时间: 2021-09-13; jos 在线出版时间: 2021-10-21

刘睿诚等: 面向非易失内存的异构索引

833

Key words: non-volatile memory; index; t wo-layer stru cture; read/writ e opti mization; ART tree

非易失内存(non-volatile memory, NVM)是近年来继闪存(Flash memory)后出现的新型存储介质. 它不仅

和闪存一样具有掉电数据不丢失的优点, 还支持像 DRAM 一样按字节存取. 同时, 非易失内存的存储密度一

般高于 DRAM, 因此可以提供比 DRAM 更高的容量, 解决当前 DRAM 密度低容量小的问题. 目前, 学术界和

工业界针对不同类型的非易失内存开展了大量研究, 包括自旋转移力矩存储器(shared transistor technology

random access memory)

[1]

、阻变式存储器(resistive random access memory)

[2]

、磁性存储器(magnetoresistive

random access memory)

[3]

以及相变存储器(phase change memory)

[4,5]

等. 特别是 Intel 凭借与 Micron 共同研发的

3D XPoint 技术

[6]

提升了晶粒的存储密度, 于 2019 年 4 月推出了第一款商用的非易失内存——傲腾持久化内

存( Intel optane DC persi stent memory), 极大地促进了非易失内存相关的研究和应用.

在数据库系统领域, 新型非易失内存技术的引入降低了数据库系统部分数据的持久化代价以及存储在持

久化介质上数据的访问代价, 这使得需要持久化的数据的快速存取成为可能. 数据库索引作为数据库提供高

吞吐的必要组件, 比起在外存持久化, 更适合持久化在非易失内存上. 目前, 对于非易失内存上的索引已经有

较多的工作, 包括 B+树

[7−9]

、跳表

[10]

、Radix 树

[11−14]

、日志结构合并树(log-structure merge tree, LSM-Tree)

[15]

、

散列表

[16−19]

等方面的优化. B+树是传统关系数据库系统中普遍使用的索引结构, 因此非易失内存上的索引也

大都以它为基础. 跳表、散列表和 LSM-Tree 则主要应用在键值(key -value)数据库系统中, 以优化点查询或者

解决键值数据库中的高写吞吐需求为主要目标. 本文研究的异构索引是针对传统数据库应用领域,因此也以

B+树为基础, 暂不考虑目前键值数据库领域中的索引结构. 另一方面, 虽然 B+树具有平衡、多叉、有序、支

持范围查询、高空间填充度等优点, 但它在查询时需要进行大量的键值对比, 会引入大量的缓存行读取操作,

影响查询性能. 因此, 本文考虑引入不需要键值对比操作即可快速定位记录地址的 Radix 树来优化 B+树的结

构, 最终构建一种新的综合 Radix 树和 B+ 树优点以及 NVM 特性的异构索引.

总体而言, 本论文的主要贡献如下:

(1) 针对 Ra dix 树与 B+树在非易失内存上的性能表现差异, 提出了结合这两种索引特点的异构索引

HART (hy brid adaptive radix tree). HART 是以 ART (adaptive radix tree )作为内部搜索树、B+树作为子

树与数据存储层的异构索引. 我们通过设计 NVM 写友好的结点, 将内存分布离散的叶子集中在一

起存储, 利用局部性原理提升 NVM 与高速缓存的访问效率. 同时, 采用底层持久化链表使得 HART

获得与 B+树类型索引相当的范围查询性能. 此外, HART 通过改进 ART 树的路径压缩策略使得底层

数据具备可恢复性, 同时增大了缓存行访问时的有效信息量.

(2) 我们同时在仿真 NV

M 设备以及傲腾真实 NVM 平台上进行了实验, 对比了 HART 的不同衍生变种

的性能, 并与多个 NVM 索引进行了对比. 结果表明: HART 的范围查询性能与 B+树类索引相近; 在

完全均匀稀疏的分布下, 写性能与纯 NVM 索引相当, 但读性能则大幅优于其他索引.

本文第 1 节介绍国内外相关工作. 第 2 节讨论面向非易失内存的异构索引 HART 的详细设计. 第 3 节给

出实验结果. 第 4 节总结全文工作并展望未来研究方向.

1 相关工作

如何利用好新型非易失内存的特性设计出新型索引, 达到快速查询、更新持久化介质上的数据, 一直是

国内外索引研究的热点. 本节将按照时间顺序, 分别从 B+树与 Radix 树两方面介绍国内外的 NVM 索引研究

现状.

1.1 基于B+树的NVM索引研究

目前, NVM 上的索引研究大致可分为两类: 面向纯 NVM 的索引结构以及面向 DRAM+NVM 混合内存的

索引结构. 下面分别进行阐述.

在面向纯 NVM 的索引方面, 2011 年提出的 CDDS-Tree

[20]

是首个针对新型非易失内存技术下的 B+树索引,

of 17

免费下载

软件学报计算机技术

关注

评论