Cited By
View all- Leis V(2024)LeanStore: A High-Performance Storage Engine for NVMe SSDsProceedings of the VLDB Endowment10.14778/3685800.368591517:12(4536-4545)Online publication date: 1-Aug-2024
Lock-Free Buffer Managers Do Not Require Delayed Memory Reclamation
Article No.: 1, Pages 1 - 3
Abstract
High-performance data systems running on modern many-core CPUs should not require readers to acquire physical locks. There exist multiple synchronization schemes that allow this, but they all require a solution for concurrent memory reclamation. In this paper, we show that one can eschew such a scheme when a few basic requirements are fulfilled. We exploit this insight in our high-performance buffer manager implementation in LeanStore, which as a consequence got simpler, more robust, and more performant.
References
[1]
Adnan Alhomssi, Michael Haubenschild, and Viktor Leis. 2023. The Evolution of LeanStore. In BTW(LNI, Vol. P-331). 259–281.
[2]
Adnan Alhomssi and Viktor Leis. 2021. Contention and Space Management in B-Trees. In CIDR. www.cidrdb.org.
[3]
Adnan Alhomssi and Viktor Leis. 2023. Scalable and Robust Snapshot Isolation for High-Performance Storage Engines. Proc. VLDB Endow. 16, 6 (2023), 1426–1438.
[4]
Jan Böttcher, Viktor Leis, Jana Giceva, Thomas Neumann, and Alfons Kemper. 2020. Scalable and robust latches for database systems. In DaMoN.
[5]
Nathan Grasso Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010. A practical concurrent binary search tree. In PPoPP. 257–268.
[6]
Sang Kyun Cha, Sangyong Hwang, Kihong Kim, and Keunjoo Kwon. 2001. Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems. In VLDB. 181–190.
[7]
Gabriel Haas and Viktor Leis. 2023. What Modern NVMe Storage Can Do, And How To Exploit It: High-Performance I/O for High-Performance Storage. Proc. VLDB Endow. 16, 9 (2023).
[8]
Alex Kogan and Erez Petrank. 2011. Wait-free queues with multiple enqueuers and dequeuers. In PPoPP. 223–234.
[9]
Viktor Leis, Michael Haubenschild, Alfons Kemper, and Thomas Neumann. 2018. LeanStore: In-Memory Data Management beyond Main Memory. In ICDE.
[10]
Viktor Leis, Michael Haubenschild, and Thomas Neumann. 2019. Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method. IEEE Data Eng. Bull. 42, 1 (2019), 73–84.
[11]
Viktor Leis, Florian Scheibner, Alfons Kemper, and Thomas Neumann. 2016. The ART of practical synchronization. In DaMoN.
[12]
Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012. Cache craftiness for fast multicore key-value storage. In EuroSys. 183–196.
[13]
Maged M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. In SPAA. 73–82.
[14]
Maged M. Michael. 2004. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Trans. Parallel Distributed Syst. 15, 6 (2004), 491–504.
[15]
Maged M. Michael and Michael L. Scott. 1996. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In PODC. 267–275.
[16]
Ori Shalev and Nir Shavit. 2006. Split-ordered lists: Lock-free extensible hash tables. J. ACM 53, 3 (2006), 379–405.
Index Terms
- Lock-Free Buffer Managers Do Not Require Delayed Memory Reclamation
Index terms have been assigned to the content through auto-classification.
Recommendations
Automatic memory reclamation for lock-free data structures
OOPSLA '15Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual'' in the sense that the developer has to ...
Transactional lock-free execution of lock-based programs
Special Issue: Proceedings of the 10th annual conference on Architectural Support for Programming Languages and Operating SystemsThis paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2023
28 pages
ISBN:9798400707834
DOI:10.1145/3596225
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part 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 components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 July 2023
Check for updates
Badges
Best Paper
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SiMoD '23
Acceptance Rates
Overall Acceptance Rate 2 of 8 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 95Total Downloads
- Downloads (Last 12 months)52
- Downloads (Last 6 weeks)10
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
Cited By
View all- Leis V(2024)LeanStore: A High-Performance Storage Engine for NVMe SSDsProceedings of the VLDB Endowment10.14778/3685800.368591517:12(4536-4545)Online publication date: 1-Aug-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format