面向非易失性内存的持久索引数据结构研究综述

doi:10.11959/j.issn.2096-0271.2021062

大数据 ›› 2021, Vol. 7 ›› Issue (6): 78-88.doi: 10.11959/j.issn.2096-0271.2021062

面向非易失性内存的持久索引数据结构研究综述

王永锋, 陈志广

中山大学计算机学院，广东广州 510006

出版日期:2021-11-15 发布日期:2021-11-01
作者简介:王永锋（1998- ），男，中山大学计算机学院博士生，主要研究方向为存储系统、分布式系统
陈志广（1984- ），男，博士，中山大学计算机学院副教授，主要研究方向为大数据存储与处理、并行与分布式计算、高性能计算与超级计算机。在并行文件系统、大规模并行I/O优化、大数据分析处理方面取得了关键技术突破
基金资助:
国家重点研发计划资助项目(2018YFB0203904);国家自然科学基金资助项目(61872392);国家自然科学基金资助项目(61832020);国家自然科学基金资助项目(U1811461);广州市珠江科技新星资助项目(201906010008);广东省自然科学基金资助项目(2018B030312002)

A survey of persistent index data structures on non-volatile memory

Yongfeng WANG, Zhiguang CHEN

School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China

Online:2021-11-15 Published:2021-11-01
Supported by:
The National Key Research and Development Program of China(2018YFB0203904);The National Natural Science Foundation of China(61872392);The National Natural Science Foundation of China(61832020);The National Natural Science Foundation of China(U1811461);Pearl River S ＆ T Nova Program of Guangzhou(201906010008);Guangdong Natural Science Foundation(2018B030312002)

摘要/Abstract

摘要：

随着非易失性内存从理论走向实用，现代存储系统的设计与实现将迎来颠覆性变革。针对传统存储设备设计的存储系统并不能充分利用非易失性内存带来的性能红利。为了构建高吞吐、低时延、大规模的存储系统，迫切需要设计与非易失性内存硬件特性相匹配的持久索引数据结构，从而进一步提升性能。从持久索引数据结构出发，分别对B+-Tree和哈希表在非易失性内存上的设计和优化进行分析，比较其优缺点，并展望了该方向的机遇与面临的挑战。

关键词: 存储系统, 非易失性内存, 持久索引数据结构, 性能优化

Abstract:

With non-volatile memory becoming commercially available, the design and implementation of traditional storage systems need a fundamental change since they can not fully utilize the performance of non-volatile memory.To build a highthroughput, low-latency, large-scale storage system, there is an urgent need for efficient persistent index data structures that adapt to the characteristics of non-volatile memory.In terms of persistent index data structures, the optimizations applied for B+-Tree and Hash Table on non-volatile memory were summarized, and the pros and cons among these schemes were compared.And the future research directions with the challenges and opportunities that need to be resolved were showed.

Key words: storage system, non-volatile memory, persistent index data structure, performance optimization

中图分类号:

TP311

王永锋, 陈志广. 面向非易失性内存的持久索引数据结构研究综述[J]. 大数据, 2021, 7(6): 78-88.

Yongfeng WANG, Zhiguang CHEN. A survey of persistent index data structures on non-volatile memory[J]. Big Data Research, 2021, 7(6): 78-88.

图/表 2

表1

表2

参考文献 32

[1]	RAOUX S , BURR G , BREITWISCH M J ,et al. Phase-change random access memory:a scalable technology[J]. IBM Journal of Research and Development, 2008,52(4): 465-479.
[2]	KAWAHARA T . Scalable spin-transfer torque RAM technology for normallyoff computing[J]. IEEE Design ＆ Test of Computers, 2011,28(1): 52-63.
[3]	DéVELOPPEMENT Y . Intel and Micron produce breakthrough memory technology[R]. 2021.
[4]	陈游旻, 李飞, 舒继武 . 大数据环境下的存储系统构建：挑战、方法和趋势[J]. 大数据, 2019,5(4): 27-40.
	CHEN Y M , LI F , SHU J W . Building storage systems in big data era:challenges,methods and trends[J]. Big Data Research, 2019,5(4): 27-40.
[5]	LIU H K , CHEN D , JIN H ,et al. A survey of non-volatile main memory technologies:state-of-the-arts,practices,and future directions[J]. Journal of Computer Science And Technology, 2021,36(1): 4-32.
[6]	LERSCH L , HAO X , OUKID I ,et al. Evaluating persistent memory range indexes[J]. Proceedings of the VLDB Endowment, 2019,13(4): 574-587.
[7]	HU D K , CHEN Z W , WU J B ,et al. Persistent memory Hash indexes:an experimental evaluation[J]. Proceedings of the VLDB Endowment, 2021,14(5): 785-798.
[8]	邓镇龙, 陈志广 . 面向非易失内存的MPI-IO接口优化[J]. 大数据, 2021,7(2): 172-181.
	DENG Z L , CHEN Z G . An optimization of MPI-IO interface for non-volatile memory[J]. Big Data Research, 2021,7(2): 172-181.
[9]	杨青霖, 吴桂勇, 张广艳 . 分布式存储系统中的数据高效缓存方法[J]. 大数据, 2021,7(2): 147-157.
	YANG Q L , WU G Y , ZHANG G Y . An approach to buffering data efficiently in distributed storage systems[J]. Big Data Research, 2021,7(2): 147-157.
[10]	YANG J , KIM J , HOSEINZADEH M ,et al. An empirical guide to the behavior and use of scalable persistent memory[J]. arXiv preprint,2020,arXiv:1908.03583v1.
[11]	KADEKODI R , LEE S K , KASHYAP S ,et al. SplitFS:reducing software overhead in file systems for persistent memory[C]// Proceedings of the 27th ACM Symposium on Operating Systems Principles. New York:ACM Press, 2019: 494-508.
[12]	HARIA S , HILL M D , SWIFT M M . MOD:minimally ordered durable datastructures for persistent memory[C]// Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems. New York:ACM Press, 2020: 775-788.
[13]	VENKATARAMAN S , TOLIA N , RANGANATHAN P ,et al. Consistent and durable data structures for non-volatile byte-addressable memory[C]// Proceedings of the 9th USENIX Conference on File and Storage Technologies. Carlsbad:USENIX Association, 2011.
[14]	YANG J , WEI Q S , CHEN C ,et al. NVTree:reducing consistency cost for NVM-based single level systems[C]// Proceedings of the 13th USENIX Conference on File and Storage Technologies. Carlsbad:USENIX Association, 2015: 167-181.
[15]	CHEN S M , JIN Q . Persistent B+-trees in non-volatile main memory[J]. Proceedings of the VLDB Endowment, 2015,8(7): 786-797.
[16]	OUKID I , LASPERAS J , NICA A ,et al. FPTree:a hybrid SCM-DRAM persistent and concurrent B-Tree for storage class memory[C]// Proceedings of the 2016 International Conference on Management of Data. New York:ACM Press, 2016: 371-386.
[17]	ARULRAJ J , LEVANDOSKI J , MINHAS U F ,et al. BzTree:a high-performance latch-free range index for non-volatile memory[J]. Proceedings of the VLDB Endowment, 2018,11(5): 553-565.
[18]	WANG T , LEVANDOSKI J , LARSON P . Easy lock-free indexing in non-volatile memory[C]// Proceedings of the 2018 IEEE 34th International Conference on Data Engineering. Piscataway:IEEE Press, 2018: 461-472.
[19]	HWANG D , KIM W H , WON Y ,et al. Endurable transient inconsistency in byte-addressable persistent B+tree[C]// Proceedings of the 16th USENIX Conference on File and Storage Technologies. Carlsbad:USENIX Association, 2018: 187-200.
[20]	CHEN Y M , LU Y Y , FANG K D ,et al. uTree:a persistent B+-tree with low tail latency[J]. Proceedings of the VLDB Endowment, 2020,13(12): 2634-2648.
[21]	LIU J H , CHEN S M , WANG L J . LB+Trees:optimizing persistent index performance on 3DXPoint memory[J]. Proceedings of the VLDB Endowment, 2020,13(7): 1078-1090.
[22]	LEE S K , LIM K H , SONG H ,et al. WORT:write optimal radix tree for persistent memory storage systems[C]// Proceedings of the 15th USENIX Conference on File and Storage Technologies. Carlsbad:USENIX Association, 2017: 257-270.
[23]	LEE S K , MOHAN J , KASHYAP S ,et al. Recipe:converting concurrent DRAM indexes to persistent-memory indexes[C]// Proceedings of the 27th ACM Symposium on Operating Systems Principles. New York:ACM Press, 2019: 462-477.
[24]	PAN W , XIE T , SONG X J . HART:a concurrent hash-assisted radix tree for DRAM-PM hybrid memory systems[C]// Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium. Piscataway:IEEE Press, 2019: 921-931.
[25]	ZHOU X J , SHOU L D , CHEN K ,et al. DPTree:differential indexing for persistent memory[J]. Proceedings of the VLDB Endowment, 2019,13(4): 421-434.
[26]	MA S N , CHEN K , CHEN S M ,et al. ROART:range-query optimized persistent ART[C]// Proceedings of the 19th USENIX Conference on File and Storage Technologies. Carlsbad:USENIX Association, 2021: 1-16.
[27]	ZUO P F , HUA Y . A write-friendly and cache-optimized hashing scheme for non-volatile memory systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2018,29(5): 985-998.
[28]	ZUO P F , HUA Y , WU J . Write-optimized and high-performance hashing index scheme for persistent memory[C]// Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation. Carlsbad:USENIX Association, 2018: 461-476.
[29]	CHEN Z Y , HUA Y , DING B ,et al. Lockfree concurrent level hashing for persistent memory[C]// Proceedings of the 2020 International Conference on Advanced Technologies for Communications.[S.l.:s.n.], 2020: 799-812.
[30]	NAM M , CHA H , CHOI Y R ,et al. Write-optimized dynamic hashing for persistent memory[C]// Proceedings of the 17th USENIX Conference on File and Storage Technologies. Boston:USENIX Association, 2019: 31-44.
[31]	LU B T , HAO X P , WANG T Z ,et al. Dash:scalable hashing on persistent memory[J]. Proceedings of the VLDB Endowment, 2020,13(8): 1147-1161.
[32]	ZOU X M , WANG F , FENG D ,et al. HMEH:write-optimal extendible hashing for hybrid DRAM-NVM memory[C]// Proceedings of the 36th International Conference on Massive Storage Systems and Technology.[S.l.:s.n.], 2020:11.

对比项	研究工作	主要贡献	缺点
非易失内存模拟器上的B/B+Tree	CDDS B-Tree^[13]	提出使用clflush和mfence保证持久性	需要后台线程进行垃圾回收
	NV-Tree^[14]	提出了选择性持久化，仅维护核心数据的崩溃一致性，另外放松叶子节点的顺序约束，允许无序存放	叶子节点的无序性会影响范围查询的性能
	wB+-Tree^[15]	使用8 byte原子写实现崩溃一致性，无须日志	节点分裂需要写入重做日志，带来额外写入开销
	FPTree^[16]	将可重建的内部节点放到内存中，并使用硬件事务内存降低并发事务的开销	由于内存中的数据会丢失，需要较长时间进行崩溃后重建
	BzTree^[17]	使用PMwCAS实现B-Tree，降低了无锁编程的难度	PMwCAS操作带来较多的性能开销
	FAST＆FAIR^[19]	无须任何日志，基于可容忍的瞬间不一致实现崩溃一致性，无须额外写入	需要依赖特定的内存模型和硬件特性
傲腾内存上的B/B+Tree	uTree^[20]	通过存放于内存的叶子节点，避免在非易失性内存上进行操作导致的长尾时延	需要占用较多的内存
傲腾内存上的B/B+Tree	LB+Trees^[21]	减少CacheLine写，无须日志保证崩溃一致性	需要硬件特性（硬件事务内存）实现事务并发

对比项	研究工作	优点	缺点
静态哈希	Path-Hashing^[27]	独特的哈希表结构大大减少了额外写	不能保证崩溃一致性，没有实现并发
	Level-Hashing^[28]	哈希表扩容的复杂度为O(1/3N)，对一般的静态哈希扩容实现了常数级别的优化	在更新键值对和进行扩容时需要写日志，有额外的开销
	CLevel-Hashing^[29]	完全使用无锁算法实现，同时无须任何日志	存在脏读现象，无法支持更高级别的隔离性
动态哈希	CCEH^[30]	实现了无须日志即可保证崩溃一致性的可扩展哈希	没有针对非易失内存做更多特定的优化
	Dash^[31]	使用更轻量的原子变量和版本号实现优化的并发，并使用指纹减少额外的读取	段分裂时仍然需要通过日志保证崩溃一致性
	HMEH^[32]	将目录层放到DRAM，优化读写性能，同时无须日志即可保证崩溃一致性	仍然需要锁来实现并发

面向非易失性内存的持久索引数据结构研究综述

A survey of persistent index data structures on non-volatile memory

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 32

相关文章 6

Metrics

推荐阅读 0

[1]	林清音, 陈志广. 基于更新热点感知的LSM-Tree查询优化[J]. 大数据, 2023, 9(1): 126-140.
[2]	胡正丁, 薛巍. 面向异构众核超级计算机的大规模稀疏计算性能优化研究[J]. 大数据, 2020, 6(4): 40-55.
[3]	陈游旻, 李飞, 舒继武. 大数据环境下的存储系统构建：挑战、方法和趋势[J]. 大数据, 2019, 5(4): 27-40.
[4]	魏星达, 陈榕, 陈海波. 基于RDMA高速网络的高性能分布式系统[J]. 大数据, 2018, 4(4): 3-14.
[5]	李鑫, 陈璇, 黄志球. 面向大数据应用的混合内存架构特征分析[J]. 大数据, 2018, 4(3): 61-80.
[6]	肖利民, 霍志胜. 大数据存储系统I/O性能优化技术研究进展[J]. 大数据, 2017, 3(6): 65-84.