Hierarchical Hashing: A Dynamic Hashing Method With Low Write Amplification and High Performance for Non-Volatile Memory
Jinquan Wang, Zhisheng Huo, Limin Xiao, Jinqian Yang, Jiantong Huo, Minyi Guo · IEEE Transactions on Computers · 2024
The hashing method is widely used as the index structure, which can be stored in NVM to improve the application performance. However, existing hashing methods may cause high extra write amplification to NVM and bring high additional storage overhead on NVM while providing low request performance. To solve these problems, we have proposed a dynamic hashing method calledHierarchical Hashing, whose basic idea is to leverage a novel hash collision resolution mechanism that can dynamically expand the size of the hash table.Hierarchical Hashingcan incur no extra write amplification to NVM when resolving hash collisions. Additionally, it can directly address all cells when resizing the hash table, thereby avoiding the additional storage overhead caused by non-addressable linked lists. Furthermore, the request performance can be improved as all cells of the hash table are addressable when resizing to resolve hash collisions. The experimental results demonstrate thatHierarchical Hashingbrings no extra write amplification to NVM and achieves nearly 90% space utilization and high request performance while providing 99% memory utilization, compared with existing representative hashing methods.