NEHASH: high-concurrency extendible hashing for non-volatile memory

Tao CAI; Pengfei GAO; Dejiao NIU; Yueming MA; Tianle LEI; Jianfei DAI

doi:10.1631/FITEE.2200462

Your Location：

Home >

Browse articles >

NEHASH: high-concurrency extendible hashing for non-volatile memory

Special Feature on Design and Application of New Storage Systems | Updated：2023-05-31

- NEHASH: high-concurrency extendible hashing for non-volatile memory
- NEHASH：面向非易失性内存的高并发可扩展哈希
- Frontiers of Information Technology & Electronic Engineering Vol. 24, Issue 5, Pages: 703-715(2023)
- Affiliations：
  
  School of Computer Science and Communication Engineering, Jiangsu University, Zhenjiang 212013, China
- Author bio：
  
  ‡ Corresponding author
- Funds：
- DOI：10.1631/FITEE.2200462
  CLC： TP333
- Received：14 October 2022，
  
  Revised：2023-01-04，
  
  Accepted：04 January 2023，
  
  Published：0 May 2023
- Accepted：
Scan QR Code
Tao CAI, Pengfei GAO, Dejiao NIU, et al. NEHASH: high-concurrency extendible hashing for non-volatile memory[J]. Frontiers of Information Technology & Electronic Engineering, 2023, 24(5): 703-715.
DOI：

Tao CAI, Pengfei GAO, Dejiao NIU, et al. NEHASH: high-concurrency extendible hashing for non-volatile memory[J]. Frontiers of Information Technology & Electronic Engineering, 2023, 24(5): 703-715. DOI： 10.1631/FITEE.2200462.

摘要

可扩展哈希是管理越来越庞大的文件系统元数据的有效方式，但其存在并发度较低和缺乏针对非易失内存（NVM）的优化等问题。本文设计了基于惰性扩展的多层哈希目录，以提高哈希目录管理的并发度和效率；设计了基于组的哈希桶管理算法，通过缩小哈希桶大小，提高哈希键管理的效率，从而提高动态可扩展哈希的性能；利用动态随机存取存储器（DRAM）和NVM各自的优势设计了面向NVM的分层存储策略；并在英特尔傲腾持久内存（Intel Optane DC Persistent Memory）及其驱动的基础上，实现了面向NVM高并发可扩展哈希的原型，称为NEHASH。使用雅虎云服务基准测试工具（YCSB）与缓存行意识的可扩展哈希（CCEH）、级别哈希（level hashing）、布谷鸟哈希（cuckoo hashing）等进行比较，结果显示NEHASH最高能提高16.5%的读吞吐率和19.3%的写吞吐率。

Abstract

Extendible hashing is an effective way to manage increasingly large file system metadata

but it suffers from low concurrency and lack of optimization for non-volatile memory (NVM). In this paper

a multilevel hash directory based on lazy expansion is designed to improve the concurrency and efficiency of extendible hashing

and a hash bucket management algorithm based on groups is presented to improve the efficiency of hash key management by reducing the size of the hash bucket

thereby improving the performance of extendible hashing. Meanwhile

a hierarchical storage strategy of extendible hashing for NVM is given to take advantage of dynamic random access memory (DRAM) and NVM. Furthermore

on the basis of the device driver for Intel Optane DC Persistent Memory

the prototype of high-concurrency extendible hashing named NEHASH is implemented. Yahoo cloud serving benchmark (YCSB) is used to test and compare with CCEH

level hashing

and cuckoo hashing. The results show that NEHASH can improve read throughput by up to 16.5% and write throughput by 19.3%.

关键词

Keywords

references

Chen RH , Shen ZY , Ma CL , et al. , 2016 . NVMRA: utilizing NVM to improve the random write operations for NAND-flash-based mobile devices . Softw Pract Exper , 46 ( 9 ): 1263 - 1284 . https://doi.org/10.1002/spe.2378 https://doi.org/10.1002/spe.2378

Chen YM , Lu YY , Yang F , et al. , 2020 . FlatStore: an efficient log-structured key-value storage engine for persistent memory . Proc 25 th Int Conf on Architectural Support for Programming Languages and Operating Systems , p. 1077 - 1091 . https://doi.org/10.1145/3373376.3378515 https://doi.org/10.1145/3373376.3378515

Chou CC , Jung J , Reddy ALN , et al. , 2020 . Virtualize and share non-volatile memories in user space . CCF Trans High Perform Comput , 2 ( 1 ): 16 - 35 . https://doi.org/10.1007/s42514-020-00019-8 https://doi.org/10.1007/s42514-020-00019-8

Dadmal UD , Vinkare RS , Kaushik PG , et al. , 2017 . 3D X point technology . IETE Zonal Seminar "Recent Trends in Engineering & Technology , p. 13 - 17 .

Debnath B , Haghdoost A , Kadav A , et al. , 2015 . Revisiting hash table design for phase change memory . ACM SIGOPS Oper Syst Rev , 49 ( 2 ): 18 - 26 . https://doi.org/10.1145/2883591.2883597 https://doi.org/10.1145/2883591.2883597

Fagin R , Nievergelt J , Pippenger N , et al. , 1979 . Extendible hashing—a fast access method for dynamic files . ACM Trans Database Syst , 4 ( 3 ): 315 - 344 . https://doi.org/10.1145/320083.320092 https://doi.org/10.1145/320083.320092

Fan ZQ , Wu FG , Park D , et al. , 2017 . Hibachi: a cooperative hybrid cache with NVRAM and DRAM for storage arrays . Proc 33 rd Int on Conf Massive Storage Systems and Technology .

Hu J , Chen JX , Zhu YF , et al. , 2021 . Parallel multi-split extendible hashing for persistent memory . Proc 50 th Int Conf on Parallel Processing , Article 48 . https://doi.org/10.1145/3472456.3472500 https://doi.org/10.1145/3472456.3472500

Huang TC , Chang DW , 2016 . TridentFS: a hybrid file system for non-volatile RAM, flash memory and magnetic disk . Softw Pract Exper , 46 ( 3 ): 291 - 318 . https://doi.org/10.1002/spe.2299 https://doi.org/10.1002/spe.2299

Intel , 2019 . Intel ® Optane TM Persistent Memory . https://www.intel.‍com/content/www/us/en/architecture-and-technology/optane-dc-persistent-memory.html https://www.intel.‍com/content/www/us/en/architecture-and-technology/optane-dc-persistent-memory.html [ Accessed on Mar. 5, 2022 ].

Kuan K , Adegbija T , 2019 . MirrorCache: an energy-efficient relaxed retention L1 STTRAM cache . Great Lakes Symp on VLSI , p. 299 - 302 . https://doi.org/10.1145/3299874.3318022 https://doi.org/10.1145/3299874.3318022

Kwon Y , Fingler H , Hunt T , et al. , 2017 . Strata: a cross media file system . Proc 26 th ACM Symp on Operating Systems Principles , p. 460 - 477 . https://doi.org/10.1145/3132747.3132770 https://doi.org/10.1145/3132747.3132770

Li J , Lam C , 2011 . Phase change memory . Sci China Inform Sci , 54 ( 5 ): 1061 - 1072 . https://doi.org/10.1007/s11432-011-4223-x https://doi.org/10.1007/s11432-011-4223-x

Liu YB , Li HB , Lu YT , et al. , 2020 . HasFS: optimizing file system consistency mechanism on NVM-based hybrid storage architecture . Cluster Comput , 23 ( 10 ): 2501 - 2515 . https://doi.org/10.1007/s10586-019-03023-y https://doi.org/10.1007/s10586-019-03023-y

Lu BT , Hao XP , Wang TZ , et al. , 2020 . Dash: scalable hashing on persistent memory . Proc VLDB Endow , 13 ( 8 ):‍ 1147 - 1161 . https://doi.org/10.14778/3389133.3389134 https://doi.org/10.14778/3389133.3389134

Nam M , Cha H , Choi YR , et al. , 2019 . Write-optimized dynamic hashing for persistent memory . Proc 17 th USENIX Conf on File and Storage Technologies , p. 31 - 44 .

Oukid I , Lasperas J , Nica A , et al. , 2016 . FPTree: a hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory . Int Conf on Management of Data , p. 371 - 386 . https://doi.org/10.1145/2882903.2915251 https://doi.org/10.1145/2882903.2915251

Pagh R , Rodler FF , 2004 . Cuckoo hashing . J Algorithms , 51 ( 2 ): 122 - 144 . https://doi.org/10.1016/j.jalgor.2003.12.002 https://doi.org/10.1016/j.jalgor.2003.12.002

Wang L , Wang HH , 2010 . A new self-adaptive extendible hash index for flash-based DBMS . IEEE Int Conf on Information and Automation , p. 2519 - 2524 . https://doi.org/10.1109/ICINFA.2010.5512045 https://doi.org/10.1109/ICINFA.2010.5512045

Zheng SA , 2019 . Ziggurat: a tiered file system for non-volatile main memories and disks . Proc 17 th USENIX Conf on File and Storage Technologies , p. 207 - 219 .

Zou XM , Wang F , Feng D , et al. , 2020 . HMEH: write-optimal extendible hashing for hybrid DRAM-NVM memory . Proc 36 th Int Conf on Mass Storage Systems and Technologies .

Zuo PF , Hua Y , 2017 . A write-friendly hashing scheme for non-volatile memory systems . Proc 33 rd Int Conf on Massive Storage Systems and Technology .

Zuo PF , Hua Y , Wu J , 2018 . Write-optimized and high-performance hashing index scheme for persistent memory . Proc 13 th USENIX Symp on Operating Systems Design and Implementation , p. 461 - 476 .

Zuo PF , Zhou QH , Sun JZ , et al. , 2022 . RACE: one-sided RDMA-conscious extendible hashing . ACM Trans Storage , 18 ( 2 ): 11 . https://doi.org/10.1145/3511895 https://doi.org/10.1145/3511895

Views

137

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
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.

⁰