WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems

Authors: 

Se Kwon Lee, UNIST (Ulsan National Institute of Science and Technology); K. Hyun Lim, Hongik University; Hyunsub Song, Beomseok Nam, and Sam H. Noh, UNIST (Ulsan National Institute of Science and Technology)

Abstract: 

Recent interest in persistent memory (PM) has stirred development of index structures that are efficient in PM. Recent such developments have all focused on variations of the B-tree. In this paper, we show that the radix tree, which is another less popular indexing structure, can be more appropriate as an efficient PM indexing structure. This is because the radix tree structure is determined by the prefix of the inserted keys and also does not require tree rebalancing operations and node granularity updates. However, the radix tree as-is cannot be used in PM. As another contribution, we present three radix tree variants, namely, WORT (Write Optimal Radix Tree), WOART (Write Optimal Adaptive Radix Tree), and ART+CoW. Of these, the first two are optimal for PM in the sense that they only use one 8-byte failure-atomic write per update to guarantee the consistency of the structure and do not require any duplicate copies for logging or CoW. Extensive performance studies show that our proposed radix tree variants perform considerable better than recently proposed B-tree variants for PM such NVTree, wB+Tree, and FPTree for synthetic workloads as well as in implementations within Memcached.

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.

Presentation Audio

BibTeX
@inproceedings {201600,
author = {Se Kwon Lee and K. Hyun Lim and Hyunsub Song and Beomseok Nam and Sam H. Noh},
title = {{WORT}: Write Optimal Radix Tree for Persistent Memory Storage Systems},
booktitle = {15th {USENIX} Conference on File and Storage Technologies ({FAST} 17)},
year = {2017},
isbn = {978-1-931971-36-2},
address = {Santa Clara, CA},
pages = {257--270},
url = {https://www.usenix.org/conference/fast17/technical-sessions/presentation/lee-se-kwon},
publisher = {{USENIX} Association},
}