Data storage is one of the fundamental systems in computer architecture. There are a variety of data structures to implement data indexing at a high speed in a computer system. B+-Tree, a data structure designed for disks and single-core processors proposed in the 1970s, is currently still indispensable in many databases and file systems. One of the promising data storage devices to transplant and deploy B+-Tree is non-volatile memory (NVM), which has attracted wide attention in recent years, as it has both DRAM-like byte-addressability and disk-like data persistency. In order to maintain crash consistency of B+-Tree in the NVM storage devices, architectural supports from CPU suppliers (such as Intel’s cache line flush instructions, i.e., clflush/clflushopt/clwb) are used to ensure that modified data from the processor’s cache blocks persists into the NVM. This operation incurs high performance overhead so that reducing such overhead is the focus.
To solve this overhead problem, Assistant Professor Wang Chundong’s research group at SIST has designed three new B+-Tree variants to significantly improve the performance of B+-Tree on the promising non-volatile memory with the premise of maintaining data persistency and consistency.
The first B+-Tree variant: Circ-Tree
Wang Chundong’s research group and their collaborators designed the Circ-Tree which fundamentally changes the classic linear B+-Tree node structure into a circular one. This design substantially reduces the use of cache line flush instructions and in turn the performance overhead brought by them. The experimental results showed that the Circ-Tree achieves a 1.6x better performance than the current NV-Tree designed for NVM, and an 8.6x better performance than another structure, FAST-FAIR. The results were published in an article entitled “Circ-Tree: A B+-Tree Variant with Circular Design for Persistent Memory” in IEEE Transactions on Computers.
The second B+-Tree variant: Crab-Tree
Strong store dependencies exist between data value and its address (namely key value pairs, KV pairs) in a sorted B+-Tree node. For x86 architecture processors with total store ordering (TSO) structure, consecutive stores of key and value in one KV pair retain their writing order, while for non-TSO structure that is deployed in ARM architecture processors, an additional memory fence must be called to preserve the writing order, which increases time in data storage. Accordingly, the Crab-Tree was developed to reduce consistency cost by selectively choosing one of two strategies: copying in write progress or shifting in place to insert and delete KV pairs at runtime. Experiments showed that the Crab-Tree greatly outperformed the state-of-the-art B+-Trees designed for persistent memory by up to 3.2x and 2.6x in read and write speed, respectively, with both consistency and scalability achieved. The research was published in an article entitled “Crash Recoverable ARMv8-Oriented B+-Tree for Byte-Addressable Persistent Memory” in ACM Transactions on Embedded Computing Systems
The third B+-Tree variant: Isle-Tree
The Isle-Tree was proposed to avoid shifts of numerous KV pairs when inserting a new KV pair into a sorted node. Each cache line of the Isle-Tree’s leaf node is sorted while the node is unsorted. For most insertions/deletions, the Isle-Tree flushes only one cache line of KV pairs. Experiments showed that the Isle-Tree achieved high performance for all insertions, deletions and searches. Related research was published in an article entitled “Isle-Tree: A B+-Tree with Intra-Cache Line Sorted Leaves for Non-volatile Memory” in IEEE International Conference on Computer Design (ICCD ’20).
The first author of these papers is Prof. Wang Chundong. These studies were supported by ShanghaiTech University, Singapore University of Technology and Design, and Singapore Ministry of Education.
Paper Links:
Circ-Tree： https://ieeexplore.ieee.org/document/9312478/
Crab-Tree: https://dl.acm.org/doi/pdf/10.1145/3316482.3326358
Isle-Tree: https://ieeexplore.ieee.org/abstract/document/9283524
Figure 1. The circular structure of the Circ-Tree’s leaf node
Figure 2. A comparison of six trees on inserting and searching 1 million keys for the Circ-Tree
Figure 3. A comparison of insertion, search and deletion performance with 1 million keys for the Crab-Tree
Figure 4. Design of the Isle-Tree
Figure 5. A comparison among seven B+-Tree variants for insertion and search for the Isle-Tree