TL;DR
This paper introduces ADOC, a novel framework that automatically harmonizes data flow in Log-Structured Key-Value (LSM-KV) stores to combat "write stalls," a major performance bottleneck. By dynamically adjusting thread counts and batch sizes, ADOC significantly reduces stall duration and boosts throughput, outperforming existing auto-tuning methods and even manually optimized systems.
What Problem Does This Paper Address?
Log-structured merge-tree (LSM) based key-value (KV) stores are ubiquitous in modern systems, powering everything from NoSQL databases to time-series databases. While offering high write throughput, they suffer from a critical issue known as "write stalls" – sudden, drastic drops in performance under heavy write loads. Previous research has often attributed these stalls to specific causes like resource shortages or scheduling issues. However, this paper argues that these explanations are too narrow and fail to capture the universal nature of write stalls across different devices and workloads. The authors propose that a more general phenomenon, "data overflow," is the root cause, occurring when data flow into one component of the LSM-KV system overwhelms its processing capacity. This leads to performance degradation and system instability.
Methods
The core of this paper is the development of ADOC (Automatic Data Overflow Control), a framework designed to proactively manage data flow and prevent data overflow. ADOC operates on two key principles:
- Device Transparency: ADOC is designed to work across a wide range of storage devices (from HDDs to NVMe SSDs and persistent memory) without requiring device-specific tuning. It achieves this by monitoring internal data flow dynamics rather than relying on device-specific performance metrics.
- Portability: ADOC is implemented as a straightforward extension to the RocksDB control flow, requiring minimal code changes and not disrupting the core architecture of LSM-KV systems.
ADOC dynamically tunes two critical parameters: the number of threads and the batch size. It monitors for three types of data overflow:
- Memory Overflow (MMO): When the active memtable fills up faster than it can be flushed. ADOC addresses this by increasing the flush rate (by reducing threads) and increasing batch size.
- Level 0 Overflow (L0O): When the Level 0 to Level 1 compaction rate cannot keep up with the flush rate. ADOC increases the number of threads to improve L0-L1 compaction and reduces the flush rate.
- Redundancy Overflow (RDO): When the rate of redundant data generation exceeds the compaction rate. ADOC increases threads and decreases batch size to improve deep-level compaction.
The framework uses a time window to detect overflows and applies tuning actions based on a priority order (L0O, RDO, MMO), employing an Additive Increase/Multiplicative Decrease (AIMD) algorithm for adjustments.
Datasets
The paper primarily uses the fillrandom workload from db_bench (a tool within RocksDB) for microbenchmarking. For macrobenchmarking, they utilize the YCSB (Yahoo! Cloud Serving Benchmark) benchmark with six different workloads (A-F), each with varying data distributions and request compositions. No new benchmarks were introduced; instead, they leverage established tools and workloads to evaluate their system.
Key Insights and Ideas
- Data Overflow as a Unifying Cause: The most significant insight is the identification of "data overflow" as a general, unifying cause for write stalls, explaining phenomena that previous, more specific explanations could not.
- Limitations of Existing Studies: The paper effectively demonstrates how prior studies, while valid in their specific contexts, often oversimplify the problem by focusing on single aspects like CPU utilization or bandwidth, failing to generalize across diverse scenarios.
- Dynamic Tuning is Crucial: The research highlights that static configurations or even simple auto-tuners (like RocksDB-AT) are insufficient. Proactive, dynamic adjustment of data flow parameters is essential for optimal performance.
- Trade-offs in LSM-KV Design: The comparison with SILK reveals that achieving high performance often comes with significant memory overhead, underscoring the importance of ADOC's efficient resource utilization.
- Complementary Nature of Tuning Parameters: The study shows that tuning both thread count and batch size together leads to a more stable and effective tuning process than adjusting either parameter in isolation.
Key Results
- Significant Performance Improvement: ADOC reduces write stall duration by up to 87.9% and improves performance by up to 322.8% compared to the auto-tuned RocksDB.
- Outperforming State-of-the-Art: For synthetic write-intensive workloads, ADOC achieves up to 66% higher throughput than the manually optimized SILK.
- Comparable Performance on Real-World Workloads: ADOC achieves comparable performance to SILK on YCSB workloads, with some advantages in write-heavy scenarios.
- Reduced Memory Footprint: ADOC uses significantly less memory (22.2% less on average) compared to SILK, which relies on larger memory buffers for its performance.
- Device Agnosticism: ADOC demonstrates consistent performance improvements across various storage devices, from HDDs to NVMe SSDs and persistent memory.
Limitations and Future Work
- Tail Latency on NVMe SSDs: While ADOC generally reduces stall duration, it showed a slight elongation (1.5%) for tail latency on NVMe SSDs. This is attributed to ADOC processing more data, leading to more frequent edge cases.
- CPU Utilization: ADOC's aggressive data processing can lead to higher CPU utilization, especially on slower devices like HDDs, compared to less aggressive schemes.
- Version Compatibility: The paper notes that porting SILK to newer RocksDB versions proved challenging due to significant internal optimizations, leading to the use of an older SILK version for comparison. While ADOC was also tested on the older version, some discrepancies were observed.
The authors suggest that future work could explore more sophisticated tuning strategies and further investigate the interplay between ADOC and emerging storage technologies.
Summary updated