NVB-tree: Failure-Atomic B+-tree for Persistent Memory
Kibeom Jin · Scholarworks@UNIST (Ulsan National Institute of Science and Technology) · 2017
Emerging non-volatile memory has opened new opportunities to re-design the entire system software stack and it is expected to break the boundaries between memory and storage devices to enable storage-less systems.Traditionally, B-tree has been used to organize data blocks in storage systems.However, B-tree is optimized for disk-based systems that read and write large blocks of data.When byte-addressable non-volatile memory replaces the block device storage systems, the byteaddressability of NVRAM makes it challenge to enforce the failure-atomicity of B-tree nodes.In this work, we present NVB-tree that addresses this challenge, reducing cache line flush overhead and avoiding expensive logging methods.NVB-tree is a hybrid tree that combines the binary search tree and the B+-tree, i.e., keys in each NVB-tree node are stored as a binary search tree so that it can benefit from the byte-addressability of binary search trees.We also present a logging-less split/merge scheme that guarantees failure-atomicity with 8-byte memory writes.Our performance study shows that NVB-tree outperforms the state-of-the-art persistent index -wB+-tree by a large margin.