Paper Info
Title
Towards the design of efficient hash-based indexing scheme for growing databases on non-volatile memory
Abstract
The index is a fundamental component in data intensive systems to accelerate data retrieval operations. In the design of Non-Volatile Memory (NVM) based indexes, the hash-based structure is one of the most promising candidates since it can take full advantages of byte-addressable property of NVM to perform query operations with constant time complexity. However, we found that the basic operation, “rehash operation”, may incur a large number of write activities on NVM, which is harmful to the endurance of NVM, and will cause drastic performance degradation. Additionally, range query operations cannot be efficiently conducted on hash-based indexes. In this paper, we first investigate how to design an NVM-friendly hash-based structure with the considerations of endurance and performance issues. Then, we propose a novel indexing scheme called “Bucket Hash”, which can significantly reduce the overhead caused by rehash operations and range query operations. We evaluate the proposed Bucket Hash using YCSB workloads. Compared with existing indexes, Bucket Hash achieves 40% reduction on average in the number of NVM writes, meanwhile gaining 30% improvement on timing performance.
Year
DOI
Venue
2020
10.1016/j.future.2019.07.035
Future Generation Computer Systems
Keywords
Field
DocType
Hashing data structures,Non-volatile memory,Index schemes
Computer science,Data retrieval,Range query (data structures),Search engine indexing,Non-volatile memory,Hash function,Time complexity,Computer engineering,Distributed computing
Journal
Volume
ISSN
Citations 
105
0167-739X
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Zhulin Ma112.74
Edwin H.-M. Sha2131897.35
Qingfeng Zhuge3396.27
Weiwen Jiang49516.21
Runyu Zhang515.44
Shouzhen Gu6114.32