# Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads

arXiv: https://arxiv.org/abs/2308.07013 · HTML: https://mlsanity.com/paper/2308.07013/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 71 references that are in the map.
- First posted on arXiv 14 Aug 2023.

## Builds on (most cited first, 10 of 10)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [AsterixDB: A Scalable, Open Source BDMS](https://mlsanity.com/paper/1407.0454/) (2014)
- [Endure: A Robust Tuning Paradigm for LSM Trees Under Workload Uncertainty](https://mlsanity.com/paper/2110.13801/) (2021)
- [Constructing and Analyzing the LSM Compaction Design Space (Updated Version)](https://mlsanity.com/paper/2202.04522/) (2022)
- [On Performance Stability in LSM-based Storage Systems (Extended Version)](https://mlsanity.com/paper/1906.09667/) (2019)
- [An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version)](https://mlsanity.com/paper/1910.08185/) (2019)
- [Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems (Extended Version)](https://mlsanity.com/paper/2004.10360/) (2020)
- [Proteus: A Self-Designing Range Filter](https://mlsanity.com/paper/2207.01503/) (2022)

## Built on by (most cited first, 6 of 6)

- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)
- [CAMAL: Optimizing LSM-trees via Active Learning](https://mlsanity.com/paper/2409.15130/) (2024)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Zero-Indexing Internet Search Augmented Generation for Large Language Models](https://mlsanity.com/paper/2411.19478/) (2024)
- [Smart Compaction: Predicting Compaction Utility from Lakehouse Table Metadata](https://mlsanity.com/paper/2608.08639/) (2026)

## Abstract (arXiv)

LSM-trees are widely adopted as the storage backend of key-value stores. However, optimizing the system performance under dynamic workloads has not been sufficiently studied or evaluated in previous work. To fill the gap, we present RusKey, a key-value store with the following new features: (1) RusKey is a first attempt to orchestrate LSM-tree structures online to enable robust performance under the context of dynamic workloads; (2) RusKey is the first study to use Reinforcement Learning (RL) to guide LSM-tree transformations; (3) RusKey includes a new LSM-tree design, named FLSM-tree, for an efficient transition between different compaction policies -- the bottleneck of dynamic key-value stores. We justify the superiority of the new design with theoretical analysis; (4) RusKey requires no prior workload knowledge for system adjustment, in contrast to state-of-the-art techniques. Experiments show that RusKey exhibits strong performance robustness in diverse workloads, achieving up to 4x better end-to-end performance than the RocksDB system under various settings.