From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees

Authors: 

Yifan Dai, Yien Xu, Aishwarya Ganesan, and Ramnatthan Alagappan, University of Wisconsin - Madison; Brian Kroth, Microsoft Gray Systems Lab; Andrea Arpaci-Dusseau and Remzi Arpaci-Dusseau, University of Wisconsin - Madison

Abstract: 

We introduce BOURBON, a log-structured merge (LSM) tree that utilizes machine learning to provide fast lookups. We base the design and implementation of BOURBON on empirically-grounded principles that we derive through careful analysis of LSM design. BOURBON employs greedy piecewise linear regression to learn key distributions, enabling fast lookup with minimal computation, and applies a cost-benefit strategy to decide when learning will be worthwhile. Through a series of experiments on both synthetic and real-world datasets, we show that BOURBON improves lookup performance by 1.23x-1.78x as compared to state-of-the-art production LSMs.

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 {258965,
author = {Yifan Dai and Yien Xu and Aishwarya Ganesan and Ramnatthan Alagappan and Brian Kroth and Andrea Arpaci-Dusseau and Remzi Arpaci-Dusseau},
title = {From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees},
booktitle = {14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20)},
year = {2020},
isbn = {978-1-939133-19-9},
pages = {155--171},
url = {https://www.usenix.org/conference/osdi20/presentation/dai},
publisher = {{USENIX} Association},
month = nov,
}
Artifact Evaluated

Presentation Video