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

Yongfeng WANG; Zhiguang CHEN

doi:10.11959/j.issn.2096-0271.2021062

您当前的位置：

首页 >

文章列表页 >

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

STUDY | 更新时间：2024-06-03

- A survey of persistent index data structures on non-volatile memory
- Big data research Vol. 7, Issue 6, Pages: 78-88(2021)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2021062
  CLC： TP311
- Online First：2021-11，
  
  Published：15 November 2021
- 稿件说明：
移动端阅览
Yongfeng WANG, Zhiguang CHEN. A survey of persistent index data structures on non-volatile memory[J]. Big data research, 2021, 7(6): 78-88.
DOI：

Yongfeng WANG, Zhiguang CHEN. A survey of persistent index data structures on non-volatile memory[J]. Big data research, 2021, 7(6): 78-88. DOI： 10.11959/j.issn.2096-0271.2021062.

摘要

随着非易失性内存从理论走向实用，现代存储系统的设计与实现将迎来颠覆性变革。针对传统存储设备设计的存储系统并不能充分利用非易失性内存带来的性能红利。为了构建高吞吐、低时延、大规模的存储系统，迫切需要设计与非易失性内存硬件特性相匹配的持久索引数据结构，从而进一步提升性能。从持久索引数据结构出发，分别对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.

关键词

Keywords

references

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 .

KAWAHARA T . Scalable spin-transfer torque RAM technology for normallyoff computing [J ] . IEEE Design ＆ Test of Computers , 2011 , 28 ( 1 ): 52 - 63 .

DÉVELOPPEMENT Y . Intel and Micron produce breakthrough memory technology [R ] . 2021 .

陈游旻 , 李飞 , 舒继武 . 大数据环境下的存储系统构建：挑战、方法和趋势 [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 .

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 .

LERSCH L , HAO X , OUKID I , et al . Evaluating persistent memory range indexes [J ] . Proceedings of the VLDB Endowment , 2019 , 13 ( 4 ): 574 - 587 .

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 .

邓镇龙 , 陈志广 . 面向非易失内存的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 .

杨青霖 , 吴桂勇 , 张广艳 . 分布式存储系统中的数据高效缓存方法 [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 .

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 .

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 .

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 .

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 .

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 .

CHEN S M , JIN Q . Persistent B+-trees in non-volatile main memory [J ] . Proceedings of the VLDB Endowment , 2015 , 8 ( 7 ): 786 - 797 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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.

Views

840

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A polymorphic cooperative compression strategy for IoT time series data based on NVM

Challenges and technical development of storage systems in the era of large language models

System performance optimization practice for big data scenarios

Research on key technologies for efficient storage and access of turbulent big data

Research on performance optimization for large-scale sparse computation over many-core heterogenous supercomputer

Related Author

Qiangqiang NI

Zeyu HUANG

Jianfei DAI

Dejiao NIU

Tianle LEI

Tao CAI

FENG Yangyang

SHU Jiwu

Related Institution

Department of Computer Science and Technology, Tsinghua University

China Mobile Information Technology Center

Beihang University

China Mobile Information Technology Co., Ltd.

School of Computer Science, Northwestern Polytechnical University

Postal code：100079
Tel：（010）53879208、53859533 Email：bdr@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：273162 Visits Today：68

⁰