NVLH: Crash-Consistent Linear Hashing for Non-Volatile Memory
Hu Wan, Fuyang Li, Zimeng Zhou, Kaisheng Zeng, Jianhua Li, Chun Jason Xue · 2018
Linear hashing is a dynamic hashing scheme widely used in modern database systems. However, linear hashing is considered to be difficult and complicated to maintain crash consistency in disk-oriented systems. Without consistency support, linear hashing indexes might need to be rebuilt after a database crash in the case of unwritten changes, thereby degrading performance. This paper revisits linear hashing in the context of fast, byte-addressable non-volatile memory (NVM) and presents NVLH, a novel crash-consistent NVM-resident linear hashing. The proposed linear hashing is persistent and can guarantee persistent data consistency across power failures and crashes. Preliminary experiments show that NVLH improves performance significantly compared to persistent double hashing.