ALPHA: A Scalable Lock-Free Partitioned Hash Index for Persistent Memory on NUMA Architectures

Hash indexes are widely used in modern dataintensive applications to support efficient query performance. While persistent memory (PM) provides larger capacity and byteaddressability, we identify that PM-based hash indexes suffer from scalability bottlenecks under high concurrency. This stems from NUMA access imposing significant costs, exacerbating the inherently request-agnostic I/O issues in concurrent read/write operations. To this end, we present ALPHA, a highly scalable hash index designed for persistent memory. The key idea with ALPHA lies in exploiting the natural hash-based data access features of hash indexes to reduce I/O irrelevant to data requests. We propose a NUMA-friendly framework to reduce the negative impacts of remote access through the cross-thread delegation mechanism. To further improve throughput, we use two techniques to address read and write issues of the PM-oriented hash index. First, we propose a novel two-layer hash structure to minimize PM access by filtering unnecessary key retrievals during data reads. Second, we devise a partition-based finegrained data access mechanism that enables lock-free concurrent writes without excessive PM write overheads. Our comprehensive experimental evaluation shows that ALPHA outperforms state-of-the-art PM-based hash indexes by up to 22.17 × in throughput while reducing tail latency by up to 97.1 %.