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

LSM-trees are widely adopted as the storage backends of key-value stores. However, optimizing the system performance under dynamic workloads has not been sufficiently studied 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 design 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, that facilitates efficient transitions between different compaction policies, which addresses the key bottleneck for 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 across diverse workloads, achieving up to 4x better end-to-end performance than the RocksDB system under various settings.