Jungle: Towards Dynamically Adjustable Key-Value Store by Combining LSM-Tree and Copy-On-Write B+-Tree


Jung-Sang Ahn, Mohiuddin Abdul Qader, Woon-Hak Kang, Hieu Nguyen, Guogen Zhang, and Sami Ben-Romdhane, eBay Inc.


Designing key-value stores based on log-structured merge-tree (LSM-tree) encounters a well-known trade-off between the I/O cost of update and that of lookup as well as of space usage. It is generally believed that they cannot be improved at the same time; reducing update cost will increase lookup cost and space usage, and vice versa. Recent works have been addressing this issue, but they focus on probabilistic approaches or reducing amortized cost only, which may not be helpful for tail latency that is critical to server applications. This paper suggests a novel approach that transplants copy-on-write B+-tree into LSM-tree, aiming at reducing update cost without sacrificing lookup cost. In addition to that, our scheme provides a simple and practical way to adjust the index between update-optimized form and space-optimized form. The evaluation results show that it significantly reduces update cost with consistent lookup cost.

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.

@inproceedings {234727,
author = {Jung-Sang Ahn and Mohiuddin Abdul Qader and Woon-Hak Kang and Hieu Nguyen and Guogen Zhang and Sami Ben-Romdhane},
title = {Jungle: Towards Dynamically Adjustable {Key-Value} Store by Combining {LSM-Tree} and {Copy-On-Write} {B+-Tree}},
booktitle = {11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19)},
year = {2019},
address = {Renton, WA},
url = {https://www.usenix.org/conference/hotstorage19/presentation/ahn},
publisher = {USENIX Association},
month = jul,