Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 623-629.DOI: 10.11772/j.issn.1001-9081.2020091451

Special Issue: 第37届CCF中国数据库学术会议(NDBC 2020)

• The 37th CCF National Database Conference (NDBC 2020) • Previous Articles     Next Articles

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

TANG Chen1, HUANG Guorui2, JIN Peiquan1   

  1. 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).

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

汤晨1, 黄国锐2, 金培权1   

  1. 1. 中国科学技术大学 计算机科学与技术学院, 合肥 230001;
    2. 中国人民解放军 31002部队, 北京 100081
  • 通讯作者: 金培权
  • 作者简介:汤晨(1999-),男,安徽合肥人,硕士研究生,主要研究方向:面向新型存储的数据库技术;黄国锐(1974-),男,安徽太和人,高级工程师,博士,主要研究方向:大数据、云计算;金培权(1975-),男,浙江东阳人,副教授,博士,CCF高级会员,主要研究方向:基于新型存储的数据库技术、大数据存储与管理。
  • 基金资助:
    国家自然科学基金资助项目(61672479,62072419)。

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

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

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

CLC Number: