.png){kind=icon}
.png){kind=icon}
Return
Revisiting PM-Based B+ -Tree With Persistent CPU Cache
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2024.3372621.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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), 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 cache-crafty 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 11x higher throughput and 43x lower 99% tail latency than state-of-the-art persistent B+-Trees under YCSB workloads.
Keywords:
B+ -Tree
EADR
lock-free
persistent CPU cache
persistent memory
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W