ROART: Range-query Optimized Persistent ART

Authors: 

Shaonan Ma and Kang Chen, Tsinghua University; Shimin Chen, SKL of Computer Architecture, ICT, CAS, and University of Chinese Academy of Sciences; Mengxing Liu, Jianglang Zhu, Hongbo Kang, and Yongwei Wu, Tsinghua University

Abstract: 

With the availability of commercial NVM devices such as Intel Optane DC PMM, it is time to start thinking about applying the existing persistent data structures in practice. This paper considers three practical aspects, which have significant influences on the design of persistent indexes, including functionality, performance and correctness.

We design a new persistent index, ROART, based on adaptive radix tree (ART), taking all these practical aspects into account. ROART (i) proposes a leaf compaction method to reduce pointer chasing for range queries, (ii) minimizes persistence overhead with three optimizations, i.e., entry compression, selective metadata persistence and minimally ordered split, and (iii) designs a fast memory management to prevent memory leaks, and eliminates the long recovery time by proposing an instant restart strategy. Evaluations show that ROART outperforms the state-of-the-art radix tree by up to 1.65x and B+-Trees by 1.17∼8.27x respectively.

FAST '21 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {264808,
author = {Shaonan Ma and Kang Chen and Shimin Chen and Mengxing Liu and Jianglang Zhu and Hongbo Kang and Yongwei Wu},
title = {{ROART}: Range-query Optimized Persistent {ART}},
booktitle = {19th USENIX Conference on File and Storage Technologies (FAST 21)},
year = {2021},
isbn = {978-1-939133-20-5},
pages = {1--16},
url = {https://www.usenix.org/conference/fast21/presentation/ma},
publisher = {USENIX Association},
month = feb
}

Presentation Video