recentpopularlog in

jabley : persistent   5

BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory
Storing a database (rows and indexes) entirely in non-volatile memory
(NVM) potentially enables both high performance and fast
recovery. To fully exploit parallelism on modern CPUs, modern
main-memory databases use latch-free (lock-free) index structures,
e.g. Bw-tree or skip lists. To achieve high performance NVMresident
indexes also need to be latch-free. This paper describes the
design of the BzTree, a latch-free B-tree index designed for NVM.
The BzTree uses a persistent multi-word compare-and-swap operation
(PMwCAS) as a core building block, enabling an index design
that has several important advantages compared with competing
index structures such as the Bw-tree. First, the BzTree is latch-free
yet simple to implement. Second, the BzTree is fast - showing
up to 2x higher throughput than the Bw-tree in our experiments.
Third, the BzTree does not require any special-purpose recovery
code. Recovery is near-instantaneous and only involves rolling back
(or forward) any PMwCAS operations that were in-flight during failure.
Our end-to-end recovery experiments of BzTree report an average
recovery time of 145 µs. Finally, the same BzTree implementation
runs seamlessly on both volatile RAM and NVM, which greatly
reduces the cost of code maintenance.
paper  filetype:pdf  storage  persistent  nvm  data-store  comp-sci 
february 2018 by jabley

Copy this bookmark:





to read