Cited By
View all- Wang YJin PWan S(2020)HotKey-LSM: A Hotness-Aware LSM-Tree for Big Data Storage2020 IEEE International Conference on Big Data (Big Data)10.1109/BigData50022.2020.9377736(5849-5851)Online publication date: 10-Dec-2020
Splaying Log-Structured Merge-Trees
Pages 1839 - 1841
Abstract
Modern persistent key-value stores typically use a log-structured merge-tree (LSM-tree) design, which allows for high write throughput. Our observation is that the LSM-tree, however, has suboptimal performance during read-intensive workload windows with non-uniform key access distributions. To address this shortcoming, we propose and analyze a simple decision scheme that can be added to any LSM-based key-value store and dramatically reduce the number of disk I/Os for these classes of workloads. The key insight is that copying a frequently accessed key to the top of an LSM-tree ("splaying'') allows cheaper reads on that key in the near future.
References
[1]
B. H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. CACM, 13(7): 422--426, 1970.
[2]
N. Dayan, M. Athanassoulis, and S. Idreos. Monkey: Optimal Navigable Key-Value Store. In SIGMOD, 2017.
[3]
Facebook. RocksDB. https://github.com/facebook/rocksdb.
[4]
P. E. O'Neil, E. Cheng, D. Gawlick, and E. J. O'Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4): 351--385, 1996.
[5]
D. D. Sleator and R. E. Tarjan. Self-Adjusting Binary Search Trees. Journal of the Association for Computing Machinery, 32 (3): 652--686, 1985.
Index Terms
- Splaying Log-Structured Merge-Trees
Recommendations
LSM-Trees and B-Trees: The Best of Both Worlds
SIGMOD '19: Proceedings of the 2019 International Conference on Management of DataLSM-Trees and B-Trees are the two primary data structures used as storage engines in modern key-value (KV) stores. These two structures are optimal for different workloads; LSM-Trees perform better on update queries, whereas B-Trees are preferable for ...
On Integration of Appends and Merges in Log-Structured Merge Trees
ICPP '19: Proceedings of the 48th International Conference on Parallel ProcessingAs widely used indices in key-value stores, the Log-Structured Merge-tree (LSM-tree) and its variants suffer from severe write amplification due to frequent merges in compactions for write-intensive applications. To address the problem, we first propose ...
OnionDisk: A Log-Structured Write-Optimal Virtual Block Device
APSys '24: Proceedings of the 15th ACM SIGOPS Asia-Pacific Workshop on SystemsThe random write performance is critical for a wide range of applications in the cloud. To accelerate such applications, researchers have proposed to realize a log structure in the file system (e.g., F2FS) to support out-of-place updates, so that random ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2018
1874 pages
ISBN:9781450347037
DOI:10.1145/3183713
- General Chairs:
- Gautam Das,
- Christopher Jermaine,
- Philip Bernstein
Copyright © 2018 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 May 2018
Check for updates
Author Tags
Qualifiers
- Abstract
Conference
SIGMOD/PODS '18
Sponsor:
Acceptance Rates
SIGMOD '18 Paper Acceptance Rate 90 of 461 submissions, 20%;
Overall Acceptance Rate 785 of 4,003 submissions, 20%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 424Total Downloads
- Downloads (Last 12 months)16
- Downloads (Last 6 weeks)4
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Wang YJin PWan S(2020)HotKey-LSM: A Hotness-Aware LSM-Tree for Big Data Storage2020 IEEE International Conference on Big Data (Big Data)10.1109/BigData50022.2020.9377736(5849-5851)Online publication date: 10-Dec-2020
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in