Towards the design of efficient hash-based indexing scheme for growing databases on non-volatile memory

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.