Revisiting PM-based B+-Tree with Persistent CPU Cache

Abstract: 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 lockfree, NBTree uses atomic primitives to serialize index operations. Moreover, NBTree proposes five novel techniques to enable lockfree accesses during structural modification operations (SMO), including three-phase SMO, sync-on-write, sync-on-read, cooperative SMO, and shift-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 cachecrafty persistent allocator and adopts log-structured insert and in-place update/delete to 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.