非易失性内存友好的线性哈希索引——NVM-LH

doi:10.11772/j.issn.1001-9081.2020091451

计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 623-629.DOI: 10.11772/j.issn.1001-9081.2020091451

所属专题：第37届CCF中国数据库学术会议(NDBC 2020)

• 第37届CCF中国数据库学术会议(NDBC 2020) • 上一篇下一篇

非易失性内存友好的线性哈希索引——NVM-LH

汤晨¹, 黄国锐², 金培权¹

1. 中国科学技术大学计算机科学与技术学院, 合肥 230001;
2. 中国人民解放军 31002部队, 北京 100081

收稿日期:2020-09-07 修回日期:2020-10-30 出版日期:2021-03-10 发布日期:2020-12-04
通讯作者: 金培权
作者简介:汤晨(1999-),男,安徽合肥人,硕士研究生,主要研究方向:面向新型存储的数据库技术;黄国锐(1974-),男,安徽太和人,高级工程师,博士,主要研究方向:大数据、云计算;金培权(1975-),男,浙江东阳人,副教授,博士,CCF高级会员,主要研究方向:基于新型存储的数据库技术、大数据存储与管理。
基金资助:
国家自然科学基金资助项目（61672479，62072419）。

NVM-LH: non-volatile memory-friendly linear hash index

TANG Chen¹, HUANG Guorui², JIN Peiquan¹

1. School of Computer Science and Technology, University of Science and Technology of China, Hefei Anhui 230001, China;
2. Unit 31002, Chinese People's Liberation Army, Beijing 100081, China

Received:2020-09-07 Revised:2020-10-30 Online:2021-03-10 Published:2020-12-04
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61672479, 62072419).

摘要/Abstract

摘要： 非易失性内存（NVM）因其大容量、持久化、按位存取和读延迟低等特性而受到人们的关注，但它同时也具有写次数有限、读写速度不均衡等缺点。针对传统线性哈希索引直接在NVM上实现时会导致大量的随机写操作这一问题，提出了一种新的NVM友好的线性哈希索引NVM-LH。NVM-LH通过存储数据时的缓存行对齐实现了缓存友好性，同时提出了无日志的数据一致性保证策略。此外，NVM-LH还通过优化分裂和删除操作来减少NVM写操作。实验结果表明，NVM-LH在空间利用率上比CCEH高30%，在NVM写次数上比CCEH减少了15%左右，表现了更好的NVM友好性。

关键词: 非易失性内存, 动态哈希, 线性哈希, 缓存行友好性, 数据一致性

Abstract: Non-Volatile Memory (NVM) attracts people's attention because of its large capacity, persistence, bit addressability and low read latency. However, it also has some disadvantages, such as limited writes and asymmetric reading and writing speed. When the traditional linear hash index is implemented directly on NVM, it will lead to a great number of random write operations. To solve this problem, a new NVM-friendly linear hash index called NVM-LH (NVM-oriented Linear Hashing) was proposed. The cache friendliness was achieved by NVM-LH through the cache line alignment during storing data. And a log-free data consistency guaranteeing strategy was presented in NVM-LH. In addition, the split and delete operations were optimized in NVM-LH to minimize the NVM write operations. Experimental results show that NVM-LH outperforms the state-of-the-art NVM-aware hash index CCEH (Cacheline-Conscious Extendible Hashing) in terms of space utilization (30% higher) and NVM write number (about 15% lower), showing better NVM-friendliness.

Key words: Non-Volatile Memory (NVM), dynamic hashing, linear hashing, cache line friendliness, data consistency

中图分类号:

TP392

汤晨, 黄国锐, 金培权. 非易失性内存友好的线性哈希索引——NVM-LH[J]. 计算机应用, 2021, 41(3): 623-629.

TANG Chen, HUANG Guorui, JIN Peiquan. NVM-LH: non-volatile memory-friendly linear hash index[J]. Journal of Computer Applications, 2021, 41(3): 623-629.

参考文献

[1] 金培权, 郝行军, 岳丽华. 面向新型存储的大数据存储架构与核心算法综述[J]. 计算机工程与科学,2013,35(10):12-24. (JIN P Q,HAO X J,YUE L H. A survey on storage architectures and core algorithms for big data management on new storages[J]. Computer Engineering and Science,2013,35(10):12-24.)
[2] 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. Berkeley:USENIX Association,2019:31-44.
[3] SUN Y,HUA Y,JIANG S,et al. SmartCuckoo:a fast and cost-efficient hashing index scheme for cloud storage systems[C]//Proceedings of the 2017 USENIX Annual Technical Conference. Berkeley:USENIX Association,2017:553-565.
[4] SUN Y,HUA Y,CHEN Z,et al. Mitigating asymmetric read and write costs in cuckoo hashing for storage systems[C]//Proceedings of the 2019 USENIX Annual Technical Conference. Berkeley:USENIX Association,2019:329-343.
[5] ZUO P,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.
[6] ZUO P,HUA Y,WU J. Write-optimized and high-performance hashing index scheme for persistent memory[C]//Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation. Berkeley:USENIX Association,2018:461-476.
[7] ZUO P,HUA Y,WU J. Level hashing:a high-performance and flexible-resizing persistent hashing index structure[J]. ACM Transactions on Storage,2019,15(2):No. 13.
[8] LITWIN W. Linear hashing:a new tool for file and table addressing[C]//Proceedings of the 6th International Conference on Very Large Data Bases. Piscataway:IEEE,1980:212-223.
[9] DEBNATH B,HAGHDOOST A,KADAV A,et al. Revisiting hash table design for phase change memory[J]. ACM SIGOPS Operating Systems Review,2016,49(2):18-26.
[10] YANG J, WEI Q, CHEN C, et al. NV-Tree:reducing consistency cost for NVM-based single level systems[C]//Proceedings of the 13th USENIX Conference on File and Storage Technologies. Berkeley:USENIX Association,2015:167-181.
[11] 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. Berkeley:USENIX Association,2017:257-270.
[12] ZHANG X,FENG D,HUA Y,et al. A write-efficient and consistent hashing scheme for non-volatile memory[C]//Proceedings of the 47th International Conference on Parallel Processing. New York:ACM,2018:No. 87.
[13] 罗永平, 金培权. DRAM+NVM混合内存架构下的连接算法优化[J]. 计算机学报,2020,43(6):1069-1085.(LUO Y P,JIN P Q. Optimizing join algorithms for NVM+DRAM-based hybrid memory architecture[J]. Chinese Journal of Computers,2020,43(6):1069-1085.)
[14] YANG L, JIN P, WAN S. BF-Join:an efficient hash join algorithm for DRAM-NVM-based hybrid memory systems[C]//Proceedings of the 2019 IEEE International Conference on Parallel and Distributed Processing with Applications,Big Data and Cloud Computing,Sustainable Computing and Communications,Social Computing and Networking. Piscataway:IEEE,2019:875-882.
[15] CHEN Z,HUA Y,DING B,et al. Lock-free concurrent level hashing for persistent memory[C]//Proceedings of the 2020 USENIX Annual Technical Conference. Berkeley:USENIX Association,2020:799-812.
[16] WANG T, LEVANDOSKI J, LARSON P A. Easy lock-free indexing in non-volatile memory[C]//Proceedings of the 34th IEEE International Conference on Data Engineering. Piscataway:IEEE,2018:461-472.

非易失性内存友好的线性哈希索引——NVM-LH

NVM-LH: non-volatile memory-friendly linear hash index

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics