JZUS - Journal of Zhejiang University SCIENCE

Frontiers of Information Technology & Electronic Engineering

Accepted manuscript available online (unedited version)

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

Share this article to： More <<< Previous Paper \|Next Paper >>>

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,in press.https://doi.org/10.1631/FITEE.2200462

@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",
year="in press",
publisher="Zhejiang University Press & Springer",
doi="https://doi.org/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
%P 703-715
%@ 2095-9184
%D in press
%I Zhejiang University Press & Springer
doi="https://doi.org/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
SP - 703
EP - 715
%@ 2095-9184
Y1 - in press
PB - Zhejiang University Press & Springer
ER -
doi="https://doi.org/10.1631/FITEE.2200462"

Abstract
Chinese Summary
Academic Network
Reviewer Comment

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

NEHASH:面向非易失性内存的高并发可扩展哈希

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

关键词组：可扩展哈希；非易失内存（NVM）；高并发

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

Reference

[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 25^th 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 33^rd 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 50^th 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^® Optane^TM 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 26^th 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 17^th 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 17^th 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 36^th 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 33^rd 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 13^th 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>

- Go to

NEHASH:面向非易失性内存的高并发可扩展哈希

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

Reference