Full Text:   <263>

Summary:  <5>

CLC number: TP333

On-line Access: 2023-05-31

Received: 2022-10-14

Revision Accepted: 2023-05-31

Crosschecked: 2023-01-04

Cited: 0

Clicked: 249

Citations:  Bibtex RefMan EndNote GB/T7714




Pengfei GAO


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2023 Vol.24 No.5 P.703-715


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

Author(s):  Tao CAI, Pengfei GAO, Dejiao NIU, Yueming MA, Tianle LEI, Jianfei DAI

Affiliation(s):  School of Computer Science and Communication Engineering, Jiangsu University,Zhenjiang 212013,China

Corresponding email(s):   caitao@ujs.edu.cn, 1306943800@qq.com

Key Words:  Extendible hashing, Non-volatile memory (NVM), High concurrency

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",
publisher="Zhejiang University Press & Springer",

%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

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

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%.


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


Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2023 Journal of Zhejiang University-SCIENCE