Optimizing B+-Tree for Byte-Addressable Non-Volatile Memory
In recent years, the next-generation non-volatile memory (NVM) technologies have emerged with DRAM-like byte addressability and disk-like durability. Computer architects have proposed to use them to build persistent memory that blurs the conventional boundary between volatile memory and non-volatile storage.
I was involved in this research when I was a research intern at Singapore University of Technology and Design (SUTD) where I was part of the ASSET Research Group. The goal of this research was to optimize B+-trees for persistent memory. We developed two variants of B+-trees namely Circ-Tree and Crab-Tree.
Circ-Tree
A conventional B+-tree node is a linear structure in which key-value (KV) pairs are maintained from the zero offset of a node. These KV pairs are shifted in a unidirectional fashion for insertions and deletions. Inserting and deleting one KV pair may inflict a large amount of write amplifications due to shifting existing KV pairs. This badly impairs the performance of in-NVM B+-tree.
We propose a novel circular design for B+-tree. With regard to NVM's byte-addressability, our Circ-Tree embraces tree nodes in a circular structure without a fixed base address, and bidirectionally shifts KV pairs for insertions and deletions to minimize write amplifications. We have implemented a prototype for Circ-Tree and conducted extensive experiments. Experimental results show that Circ-Tree significantly outperforms two state-of-the-art in-NVM B+-tree variants, i.e., NV-tree and FAST+FAIR, by up to 1.6× and 8.6×, respectively, in terms of write performance. The end-to-end comparison by running YCSB to KV stores built on NV-tree, FAST+FAIR, and Circ-Tree reveals that Circ-Tree yields up to 29.3 and 47.4 percent higher write performance, respectively, than NV-tree and FAST+FAIR.
Crab-Tree
ARM processors have incorporated architectural supports to utilize NVM. In this work, we consider tailoring the important B+-tree for NVM operated by a 64-bit ARMv8 processor. We first conduct an empirical study of performance overheads in writing and reading data for a B+-tree with an ARMv8 processor, including the time cost of cache line flushes and memory fences for crash consistency as well as the execution time of binary search compared to that of linear search. We hence identify the key weaknesses in the design of B+-tree with ARMv8 architecture. Accordingly, we develop a new B+-tree variant, namely, crash recoverable ARMv8-oriented B+-tree (Crab-tree). To insert and delete data at runtime, Crab-tree selectively chooses one of two strategies, i.e., copy on write and shifting in place, depending on which one causes less consistency cost to performance. Crab-tree regulates a strict execution order in both strategies and recovers the tree structure in case of crashes. We have evaluated Crab-tree in Raspberry Pi 3 Model B+ with emulated NVM. Experiments show that Crab-tree significantly outperforms state-of-the-art B+-trees designed for persistent memory by up to 2.6x and 3.2x in write and read performances, respectively, with both consistency and scalability achieved.
Publications
- Wang, C., Brihadiswaran, G., Jiang, X., & Chattopadhyay, S. (2021). Circ-Tree: A B+-Tree Variant with Circular Design for Persistent Memory. IEEE Transactions on Computers.
- Wang, C., Chattopadhyay, S., & Brihadiswaran, G. (2020). Crab-tree: A Crash Recoverable B+-tree Variant for Persistent Memory with ARMv8 Architecture. ACM Transactions on Embedded Computing Systems (TECS).
- Wang, C., Chattopadhyay, S., & Brihadiswaran, G. (2019). Crash recoverable ARMv8-oriented B+-tree for byte-addressable persistent memory. In Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems (pp. 33-44).