BROWSE
Detail
Conference Paper
BucketLSM: What, After All, Is the I/O Bottleneck Behind L0 Key-Range Overlap in LSM-Based KV Stores?
Cited - time in 
Share 
Share
- Authors
- Jaewan Park, Kyungwook Min, Sungjin Byeon, Taewan Noh, Hyungi Park, Xubin He, Hongyeon Kim, Youngjae Kim
- Issue Date
- 2026-05
- Citation
- International Symposium on Cluster, Cloud and Internet Computing (CCGrid) 2026, pp.100-100
- Publisher
- IEEE
- Language
- English
- Type
- Conference Paper
- Abstract
- LSM-tree-based key-value stores serve as the storage backbone for a wide range of cloud services, where write throughput and read latency directly determine quality of service. These systems adopt an append-only write strategy that buffers writes in memory and flushes them to disk as separate files, achieving high write throughput at the cost of accumulating multiple versions of the same key across files. A background process called compaction periodically merges these files to eliminate redundant entries and sustain read efficiency. However, at Level-0 (L0)—where flushed files first land on disk—files are allowed to have arbitrarily overlapping key ranges. This overlap forces L0–L1 compaction to merge nearly all files from both levels as a single coarse-grained task, fundamentally limiting compaction parallelism. When L0–L1 compaction cannot keep pace with incoming writes, L0 files accumulate, triggering severe write stalls and read latency spikes. This paper presents BucketLSM, an LSM architecture that partitions L0 into non-overlapping buckets to unlock scalable compaction parallelism. BucketLSM splits MemTables at flush time according to bucket boundaries, creating structurally independent compaction units. Key mechanisms include (i) BucketFlush for boundary-aligned file generation, (ii) BucketCompaction for fine-grained priority-based scheduling, and (iii) Dynamic Bucket Rebalancing to adapt boundaries under shifting workloads. Evaluated on RocksDB v10.6, BucketLSM achieves up to 2.6× throughput improvement over the original RocksDB, reduces write stalls by up to 16.7× compared to baseline RocksDB, and improves read performance under high write pressure—all without requiring additional hardware.
- Keyword
- Log-Structured Merge-Tree (LSM-tree), Key- Value Store, Compaction Parallelism, Write Stall, Fine-Grained Compaction
- KSP Keywords
- Cloud service, Fine grained(FG), I/O bottleneck, Key-value Store, LSM-tree, Log-structured merge-tree, Non-overlapping, Priority-Based, Throughput Improvement, Tree-based, Write strategy