TRIAD: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores

Authors: 

Oana Balmau, Diego Didona, Rachid Guerraoui, and Willy Zwaenepoel, EPFL; Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka, Nutanix

Abstract: 

We present TRIAD, a new persistent key-value (KV) store based on Log-Structured Merge (LSM) trees. TRIAD improves LSM KV throughput by reducing the write amplification arising in the maintenance of the LSM tree structure. Although occurring in the background, write amplification consumes significant CPU and I/O resources. By reducing write amplification, TRIAD allows these resources to be used instead to improve user-facing throughput.

TRIAD uses a holistic combination of three techniques. At the LSM memory component level, TRIAD leverages skew in data popularity to avoid frequent I/O operations on the most popular keys. At the storage level, TRIAD amortizes management costs by deferring and batching multiple I/O operations. At the commit log level, TRIAD avoids duplicate writes to storage.

We implement TRIAD as an extension of Facebook’s RocksDB and evaluate it with production and synthetic workloads. With these workloads, TRIAD yields up to 193% improvement in throughput. It reduces write amplification by a factor of up to 4x, and decreases the amount of I/O by an order of magnitude.

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 {203155,
author = {Oana Balmau and Diego Didona and Rachid Guerraoui and Willy Zwaenepoel and Huapeng Yuan and Aashray Arora and Karan Gupta and Pavan Konka},
title = {{TRIAD}: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores},
booktitle = {2017 {USENIX} Annual Technical Conference ({USENIX} {ATC} 17)},
year = {2017},
isbn = {978-1-931971-38-6},
address = {Santa Clara, CA},
pages = {363--375},
url = {https://www.usenix.org/conference/atc17/technical-sessions/presentation/balmau},
publisher = {{USENIX} Association},
}