CLC number: TP333
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2023-01-04
Cited: 0
Clicked: 2023
Citations: Bibtex RefMan EndNote GB/T7714
Tao CAI, Pengfei GAO, Dejiao NIU, Yueming MA, Tianle LEI, Jianfei DAI. NEHASH: high-concurrency extendible hashing for non-volatile memory[J]. Frontiers of Information Technology & Electronic Engineering, 2023, 24(5): 703-715.
@article{title="NEHASH: high-concurrency extendible hashing for non-volatile memory",
author="Tao CAI, Pengfei GAO, Dejiao NIU, Yueming MA, Tianle LEI, Jianfei DAI",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="24",
number="5",
pages="703-715",
year="2023",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2200462"
}
%0 Journal Article
%T NEHASH: high-concurrency extendible hashing for non-volatile memory
%A Tao CAI
%A Pengfei GAO
%A Dejiao NIU
%A Yueming MA
%A Tianle LEI
%A Jianfei DAI
%J Frontiers of Information Technology & Electronic Engineering
%V 24
%N 5
%P 703-715
%@ 2095-9184
%D 2023
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2200462
TY - JOUR
T1 - NEHASH: high-concurrency extendible hashing for non-volatile memory
A1 - Tao CAI
A1 - Pengfei GAO
A1 - Dejiao NIU
A1 - Yueming MA
A1 - Tianle LEI
A1 - Jianfei DAI
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 24
IS - 5
SP - 703
EP - 715
%@ 2095-9184
Y1 - 2023
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2200462
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%.
[1]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.
[2]Chen YM, Lu YY, Yang F, et al., 2020. FlatStore: an efficient log-structured key-value storage engine for persistent memory. Proc 25th Int Conf on Architectural Support for Programming Languages and Operating Systems, p.1077-1091.
[3]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.
[4]Dadmal UD, Vinkare RS, Kaushik PG, et al., 2017. 3D X point technology. IETE Zonal Seminar "Recent Trends in Engineering & Technology, p.13-17.
[5]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.
[6]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.
[7]Fan ZQ, Wu FG, Park D, et al., 2017. Hibachi: a cooperative hybrid cache with NVRAM and DRAM for storage arrays. Proc 33rd Int on Conf Massive Storage Systems and Technology.
[8]Hu J, Chen JX, Zhu YF, et al., 2021. Parallel multi-split extendible hashing for persistent memory. Proc 50th Int Conf on Parallel Processing, Article 48.
[9]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.
[10]Intel, 2019. Intel® OptaneTM Persistent Memory. https://www.intel.com/content/www/us/en/architecture-and-technology/optane-dc-persistent-memory.html [Accessed on Mar. 5, 2022].
[11]Kuan K, Adegbija T, 2019. MirrorCache: an energy-efficient relaxed retention L1 STTRAM cache. Great Lakes Symp on VLSI, p.299-302.
[12]Kwon Y, Fingler H, Hunt T, et al., 2017. Strata: a cross media file system. Proc 26th ACM Symp on Operating Systems Principles, p.460-477.
[13]Li J, Lam C, 2011. Phase change memory. Sci China Inform Sci, 54(5):1061-1072.
[14]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.
[15]Lu BT, Hao XP, Wang TZ, et al., 2020. Dash: scalable hashing on persistent memory. Proc VLDB Endow, 13(8):1147-1161.
[16]Nam M, Cha H, Choi YR, et al., 2019. Write-optimized dynamic hashing for persistent memory. Proc 17th USENIX Conf on File and Storage Technologies, p.31-44.
[17]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.
[18]Pagh R, Rodler FF, 2004. Cuckoo hashing. J Algorithms, 51(2):122-144.
[19]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.
[20]Zheng SA, 2019. Ziggurat: a tiered file system for non-volatile main memories and disks. Proc 17th USENIX Conf on File and Storage Technologies, p.207-219.
[21]Zou XM, Wang F, Feng D, et al., 2020. HMEH: write-optimal extendible hashing for hybrid DRAM-NVM memory. Proc 36th Int Conf on Mass Storage Systems and Technologies.
[22]Zuo PF, Hua Y, 2017. A write-friendly hashing scheme for non-volatile memory systems. Proc 33rd Int Conf on Massive Storage Systems and Technology.
[23]Zuo PF, Hua Y, Wu J, 2018. Write-optimized and high-performance hashing index scheme for persistent memory. Proc 13th USENIX Symp on Operating Systems Design and Implementation, p.461-476.
[24]Zuo PF, Zhou QH, Sun JZ, et al., 2022. RACE: one-sided RDMA-conscious extendible hashing. ACM Trans Storage, 18(2):11.
Open peer comments: Debate/Discuss/Question/Opinion
<1>