Details

Autor(en) / Beteiligte

• Zhang, Bowen
• Zheng, Shengan
• Nie, Liangxu
• Qi, Zhenlin
• Chen, Hongyi
• Huang, Linpeng
• Mei, Hong

Titel

Revisiting PM-Based B ^+-Tree With Persistent CPU Cache

Ist Teil von

• IEEE transactions on parallel and distributed systems, 2024-05, Vol.35 (5), p.796-813

Ort / Verlag

New York: IEEE

Erscheinungsjahr

2024

Quelle

IEEE Electronic Library Online

Beschreibungen/Notizen

• 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<inline-formula><tex-math notation="LaTeX">^+</tex-math> <mml:math><mml:msup><mml:mrow/><mml:mo>+</mml:mo></mml:msup></mml:math><inline-graphic xlink:href="zheng-ieq3-3372621.gif"/> </inline-formula>-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 11× higher throughput and 43× lower 99% tail latency than state-of-the-art persistent B<inline-formula><tex-math notation="LaTeX">^+</tex-math> <mml:math><mml:msup><mml:mrow/><mml:mo>+</mml:mo></mml:msup></mml:math><inline-graphic xlink:href="zheng-ieq4-3372621.gif"/> </inline-formula>-Trees under YCSB workloads.