Shard-based LSM tree design cuts write stalls and boosts speed
DiaLSM: Towards Write-Stall-Free Performance via Shard-based LSM-tree
Databases
Summary
Writing data fast is hard when too many changes build up, causing delays called write stalls. The authors show that trying to handle all writes in one lane causes these stalls. They design a new method called DiaLSM that splits the work into several smaller lanes (shards) so if one gets busy, others keep going. This design reduces slowdowns and makes writing much faster. They tested DiaLSM on a popular database system and showed it speeds up writes and lowers delays better than other methods.
What this means in practice
- •For database engineers: Improve storage engines by implementing shard-based write processing to reduce delays during heavy write workloads.
- •For cloud service operators: Deploy databases with enhanced throughput and reduced write wait times to improve cloud storage responsiveness.
Authors
Hongsu Byun, Safdar Jamil, Honghyeon Yoo, Sungyong Park, Myungcheol Lee, Xubin He, Zhichao Cao, Youngjae Kim
Abstract
Log-Structured Merge-tree (LSM) aims to achieve high write throughput, but is known to experience the write stall problems when subjected to sustained write pressure. We quantify the occurrence probability and average duration of write stalls in LSM using a queuing model in the write--flush--compaction pipeline, moving beyond existing empirical analysis. The proposed model demonstrates that a monolithic LSM with a single pipeline cannot eliminate write stalls, revealing that internal sharding within the LSM offers an opportunity for fundamental write stall mitigation. To break this structural bottleneck, we propose DiaLSM, an internally shard-based LSM architecture. Instead of forcing all writes through one pipeline, DiaLSM splits the write--flush--compaction path into multiple independent shards and employs dynamic fallback redirection, allowing writes to proceed even when some shards stall. Implemented on RocksDB, DiaLSM achieves up to 2.4x higher throughput, 94% lower stalls, and significantly lower latency than state-of-the-art methods ADOC and Sub-Compaction, as demonstrated by db_bench, YCSB, and Sysbench OLTP evaluations.