Heart: A Scalable, High-performance ART for Persistent Memory

Abstract: Concurrent indexes for persistent memory (PM) have been extensively investigated due to the appealing features of PM, such as data persistence and DRAM-comparable performance. Among them, Adaptive Radix Tree (ART) is a widely used index that performs well on variable-sized keys. Nevertheless, existing persistent ARTs still suffer from high PM overhead as well as inefficient concurrency control. In this paper, we present Heart, a persistent ART with low latency and high scalability. Heart proposes a unified node structure for different capacities with Hashed Node and Node Decoupling to reduce the PM access overhead. To achieve high scalability, especially in write-intensive scenarios, we propose an efficient concurrency control protocol with lock-free basic operations and lock-free node split. Furthermore, Heart employs Perceivable Transformation to avoid anomalies during node expansion and shrinkage. Compared to other state-of-the-art persistent ARTs, Heart achieves up to 21.6× higher performance under YCSB workloads with high memory utilization. We also deploy Heart in DRAM and obtain up to 33.4× speedup than the original in-memory ART.