Towards Efficient Extendible Perfect Hashing for Hybrid PM-DRAM Memory

Hashing is a widely used and efficient indexing mechanism for key-value storage. The emergence of persistent memory (PM) has further enhanced hash indexes by providing non-volatility and DRAM-like performance. However, current research on PM-based hash indexes primarily focuses on hardware-specific persistence optimizations or write performance optimization, while neglecting the critical aspect of read performance. Our study reveals that hash collisions significantly impair the read performance of hash indexes on PM. Thus, perfect hashing, which eliminates collisions, has the potential to improve read performance. Nevertheless, due to PM’s high access latency, the data movement overhead during hash table expansion and the random accesses introduced by perfect hashing itself present performance bottlenecks. In this paper, we propose EEPH+, an efficient perfect hashing scheme for PM that effectively eliminates hash collisions to enhance read performance. EEPH+ employs three techniques to alleviate the aforementioned bottlenecks and improve performance: an extendible hashing technique to reduce the data movement overhead during hash table expansion, a hybrid PM–DRAM layout where the index structure resides in DRAM combined with a complement move algorithm to minimize the random accesses inherent to perfect hashing, and a batching & prefetching scheme to facilitate the parallel execution of hash computations and data accesses across multiple searches, thereby further boosting read performance. We compare EEPH+ with the state-of-the-art hash indexes on PM by conducting comprehensive experiments on several real-world read-intensive and read-skew workloads. The experimental results confirm the superiority of our EEPH+, which outperforms state-of-the-art hash indexes by up to 3.6 × in read throughput and 3.14 × in 99th percentile latency.