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

王永锋; 陈志广

doi:10.11959/j.issn.2096-0271.2021062

您当前的位置：

首页 >

文章列表页 >

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

研究 | 更新时间：2024-06-03

- 面向非易失性内存的持久索引数据结构研究综述
- A survey of persistent index data structures on non-volatile memory
- 大数据 2021年7卷第6期页码：78-88
- 作者机构：
- 作者简介：
  
  [ "王永锋（1998- ），男，中山大学计算机学院博士生，主要研究方向为存储系统、分布式系统" ]
  [ "陈志广（1984- ），男，博士，中山大学计算机学院副教授，主要研究方向为大数据存储与处理、并行与分布式计算、高性能计算与超级计算机。在并行文件系统、大规模并行I/O优化、大数据分析处理方面取得了关键技术突破" ]
- 基金信息：
  
  国家重点研发计划资助项目;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);广东省自然科学基金资助项目;The Natural Science Foundation of Guangdong Province(2018B030312002)
- DOI：10.11959/j.issn.2096-0271.2021062
  中图分类号： TP311
- 网络首发：2021-11，
  
  纸质出版：2021-11-15
- 稿件说明：
移动端阅览
王永锋, 陈志广. 面向非易失性内存的持久索引数据结构研究综述[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.
王永锋, 陈志广. 面向非易失性内存的持久索引数据结构研究综述[J]. 大数据, 2021,7(6):78-88. DOI： 10.11959/j.issn.2096-0271.2021062.

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.

浏览量

840

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向NVM的IoT时序数据多态协作压缩策略

大模型时代下的存储系统挑战与技术发展

面向大数据场景的系统性能优化实践

面向湍流大数据的高效存储与访问关键技术研究

面向异构众核超级计算机的大规模稀疏计算性能优化研究