Abstract
Key-value stores underpin a wide range of applications due to their simplicity and efficiency. Log-Structured Merge Trees (LSM-trees) dominate as their underlying structure, excelling at handling rapidly growing data. Recent research has focused on optimizing LSM-tree performance under static workloads with fixed read-write ratios. However, real-world workloads are highly dynamic, and existing workload-aware approaches often struggle to sustain optimal performance or incur substantial transition overhead when workload patterns shift. To address this, we propose ElasticLSM, which removes traditional LSM-tree structural constraints to allow more flexible management actions (i.e., compactions and write stalls) creating greater opportunities for continuous performance optimization. We further design Arce, a lightweight compaction decision engine that guides ElasticLSM in selecting the optimal action from its expanded action space. Building on these components, we implement ArceKV, a full-fledged key-value store atop RocksDB. Extensive evaluations demonstrate that ArceKV outperforms state-of-the-art compaction strategies across diverse workloads, delivering around 3x faster performance in dynamic scenarios.
The Problem: Structural Rigidity in LSM-Trees
Log-Structured Merge Trees (LSM-trees) are the engine behind heavyweights like RocksDB, Cassandra, and TiDB. They excel at writes by buffering data in memory and flushing it to disk as sorted runs, which are later merged (compacted) to keep reads efficient.
However, most LSM-trees are "rigid." They rely on fixed level capacities and specific compaction triggers (e.g., "compact when Level 0 has 4 files"). This works for static workloads, but real-world data access is highly dynamic—shifting from write-heavy to read-heavy throughout the day. Existing "workload-aware" systems often struggle with the transition problem: they either adapt too slowly (lazy) or cause massive latency spikes by trying to reorganize data too aggressively (greedy).
Methods: ElasticLSM and Arce
The authors propose two primary innovations to break this rigidity:
- ElasticLSM: This design removes traditional constraints on level capacities and run counts. It treats the LSM-tree as a flexible collection of sorted runs. Crucially, it allows for Multi-level Compactions, where runs from non-adjacent levels can be merged in a single operation if the workload demands it.
- Arce (Adaptive Runtime Compaction Engine): Since the action space is now huge, Arce uses a Windowed-State Cost Model. It calculates an Effectiveness Score for compaction candidates by weighing the Short-term Penalty (background CPU/IO cost leading to write stalls) against the Long-term Benefit (speeding up future reads by reducing the total number of sorted runs).
To keep this efficient, Arce identifies "Dominating Compactions"—candidates that reduce the most runs in the shortest time—pruning the search space so decisions take only about 30 microseconds. It also runs a parallel simulation every million operations to tune its internal parameters to the current workload.
Key Insights and Ideas
- Focus on the Transition, Not the Destination: Traditional systems try to reach a "target" structure optimized for a specific workload. ArceKV argues that how you get there matters more. By optimizing every individual compaction step for the current workload, you avoid the "performance valleys" typical of structural transitions.
- Decoupling Stalls from Structure: In standard LSMs, write stalls are a hard-coded reaction to file counts. ArceKV treats write stalls as a tunable parameter that the system can adjust dynamically based on whether it needs to "pay down" its compaction debt or prioritize throughput.
- The Power of Pruning: By mathematically defining "dominating" compactions (those on the "left frontier" of the time-vs-benefit plot), the authors turned a computationally intractable optimization problem into a lightweight runtime engine.
Key Results
- Superior Throughput: ArceKV delivered 2.17x to 2.92x better average performance than Tiering and LazyLeveling strategies in dynamic scenarios.
- Industrial Dominance: It outperformed industrial-grade databases significantly, showing over 10x speedup compared to Cassandra and WiredTiger, and performing 3x better than Pebble.
- Rapid Adaptation: In tests where workloads shifted abruptly (e.g., from 98% writes to 98% reads), ArceKV stabilized and reached peak performance much faster than reinforcement learning-based approaches like Ruskey.
- Low Overhead: Despite the continuous simulation and complex scoring, the background decision-making adds only ~2% CPU overhead.
Limitations and Future Work
While ArceKV shows significant gains, the authors noted that more advanced encoding techniques for range filters could further bridge the gap in pure range-lookup-heavy scenarios. Additionally, while space amplification is well-controlled (comparable to Leveling), ArceKV is not yet explicitly optimized for environments where disk space is the primary bottleneck. Future iterations could also incorporate more granular metrics for specific hardware, such as ZNS SSDs or disaggregated memory architectures.
Summary updated