Scavenger+: Revisiting Space-Time Tradeoffs in Key-Value Separated LSM-trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909743605350400 |
|---|---|
| author | Zhang, Jianshun Wang, Fang Ou, Jiaxin Wang, Yi Zhao, Ming Qiu, Sheng Huang, Junxun Li, Baoquan Fang, Peng Feng, Dan |
| author_facet | Zhang, Jianshun Wang, Fang Ou, Jiaxin Wang, Yi Zhao, Ming Qiu, Sheng Huang, Junxun Li, Baoquan Fang, Peng Feng, Dan |
| contents | Key-Value Stores (KVS) based on log-structured merge-trees (LSM-trees) are widely used in storage systems but face significant challenges, such as high write amplification caused by compaction. KV-separated LSM-trees address write amplification but introduce significant space amplification, a critical concern in cost-sensitive scenarios. Garbage collection (GC) can reduce space amplification, but existing strategies are often inefficient and fail to account for workload characteristics. Moreover, current key-value (KV) separated LSM-trees overlook the space amplification caused by the index LSM-tree. In this paper, we systematically analyze the sources of space amplification in KV-separated LSM-trees and propose Scavenger+, which achieves a better performance-space trade-off. Scavenger+ introduces (1) an I/O-efficient garbage collection scheme to reduce I/O overhead, (2) a space-aware compaction strategy based on compensated size to mitigate index-induced space amplification, and (3) a dynamic GC scheduler that adapts to system load to make better use of CPU and storage resources. Extensive experiments demonstrate that Scavenger+ significantly improves write performance and reduces space amplification compared to state-of-the-art KV-separated LSM-trees, including BlobDB, Titan, and TerarkDB. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13935 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scavenger+: Revisiting Space-Time Tradeoffs in Key-Value Separated LSM-trees Zhang, Jianshun Wang, Fang Ou, Jiaxin Wang, Yi Zhao, Ming Qiu, Sheng Huang, Junxun Li, Baoquan Fang, Peng Feng, Dan Databases Key-Value Stores (KVS) based on log-structured merge-trees (LSM-trees) are widely used in storage systems but face significant challenges, such as high write amplification caused by compaction. KV-separated LSM-trees address write amplification but introduce significant space amplification, a critical concern in cost-sensitive scenarios. Garbage collection (GC) can reduce space amplification, but existing strategies are often inefficient and fail to account for workload characteristics. Moreover, current key-value (KV) separated LSM-trees overlook the space amplification caused by the index LSM-tree. In this paper, we systematically analyze the sources of space amplification in KV-separated LSM-trees and propose Scavenger+, which achieves a better performance-space trade-off. Scavenger+ introduces (1) an I/O-efficient garbage collection scheme to reduce I/O overhead, (2) a space-aware compaction strategy based on compensated size to mitigate index-induced space amplification, and (3) a dynamic GC scheduler that adapts to system load to make better use of CPU and storage resources. Extensive experiments demonstrate that Scavenger+ significantly improves write performance and reduces space amplification compared to state-of-the-art KV-separated LSM-trees, including BlobDB, Titan, and TerarkDB. |
| title | Scavenger+: Revisiting Space-Time Tradeoffs in Key-Value Separated LSM-trees |
| topic | Databases |
| url | https://arxiv.org/abs/2508.13935 |