Byte-addressable persistent memory (PM) has been widely studied in the past few years. Recently, the emerging eADR technology further incorporates CPU cache into the persistence domain. The persistent CPU cache is promising to optimize the write performance of PM-based storage systems and facilitate the design of concurrent crash-consistent data structures. In this paper, we propose Spash, a highly scalable persistent hash index for PM systems with persistent CPU cache. Spash fully exploits the benefits of persistent CPU cache to implement a durable linearizable index with low PM access overhead and high concurrency. Spash employs a fine-grained extendible hash architecture and a metadata-free segment design to minimize the number of PM accesses. Moreover, Spash adopts adaptive in-place updates and compacted-flush insertions, which dramatically conserve scarce PM write bandwidth by absorbing a large amount of PM write in the persistent CPU cache. Furthermore, Spash proposes a two-phase concurrency protocol and a collaborative staged doubling mechanism, which leverage the persistent CPU cache and hardware transactional memory to achieve lock-free concurrency and durable linearizability. Spash outperforms the other state-of-the-art persistent hash indexes in YCSB workloads by up to 19.6×.

Persistent memory (PM) promises near-DRAM performance as well as data persistence. Recently, a new feature called eADR is available for PM-equipped platforms to guarantee the persistence of CPU cache. The emergence of eADR presents unique opportunities to build lock-free data structures and unleash the full potential of PM. In this paper, we propose NBTree, a lock-free PM-friendly B$^+$-Tree, to deliver high scalability and low PM overhead. To our knowledge, NBTree is the first persistent index designed for PM systems with persistent CPU cache. To achieve lock-free, NBTree uses atomic primitives to serialize index operations. Moreover, NBTree proposes five novel techniques to enable lock-free accesses during structural modification operations (SMO), includingthree-phase SMO,sync-on-write,sync-on-read,cooperative SMO, andshift-aware search. To reduce PM access overhead, NBTree employs a decoupled leaf node design to absorb the metadata accesses in DRAM. Moreover, NBTree devises a cache-crafty persistent allocator and adoptslog-structured insertandin-place update/deleteto enhance the access locality of write operations, absorbing a substantial amount of PM writes in persistent CPU cache. Our evaluation shows that NBTree achieves up to 11× higher throughput and 43× lower 99% tail latency than state-of-the-art persistent B$^+$-Trees under YCSB workloads.

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.