research-article

High-performance concurrency control mechanisms for main-memory databases

Authors:

Per-Åke Larson,

Cristian Diaconu,

Craig Freedman,

Jignesh M. Patel,

Mike ZwillingAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 5, Issue 4

Pages 298 - 309

https://doi.org/10.14778/2095686.2095689

Published: 01 December 2011 Publication History

Abstract

A database system optimized for in-memory storage can support much higher transaction rates than current systems. However, standard concurrency control methods used today do not scale to the high transaction rates achievable by such systems. In this paper we introduce two efficient concurrency control methods specifically designed for main-memory databases. Both use multiversioning to isolate read-only transactions from updates but differ in how atomicity is ensured: one is optimistic and one is pessimistic. To avoid expensive context switching, transactions never block during normal processing but they may have to wait before commit to ensure correct serialization ordering. We also implemented a main-memory optimized version of single-version locking. Experimental results show that while single-version locking works well when transactions are short and contention is low performance degrades under more demanding conditions. The multiversion schemes have higher overhead but are much less sensitive to hotspots and the presence of long-running transactions.

References

[1]

D. Agrawal, A. J. Bernstein, P. Gupta, S. Sengupta: Distributed Multi-Version Optimistic Concurrency Control with Reduced Rollback, Distributed Computing, 1987.

[2]

D. Agrawal, S. Sengupta: Modular Synchronization in Multiversion Databases: Version Control and Concurrency Control, SIGMOD, 1989.

Digital Library

[3]

Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, Patrick E. O'Neil: A Critique of ANSI SQL Isolation Levels. SIGMOD, 1995.

Digital Library

[4]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5.

Digital Library

[5]

Paul M. Bober, Michael J. Carey: Multiversion Query Locking, VLDB, 1992.

Digital Library

[6]

Paul M. Bober, Michael J. Carey: On Mixing Queries and Transactions via Multiversion Locking, ICDE, 1992.

Digital Library

[7]

Mihaela A. Bornea, Orion Hodson, Sameh Elnikety, Alan Fekete: One-Copy Serializability with Snapshot Isolation under the Hood. ICDE, 2011.

Digital Library

[8]

Albert Burger, Vijay Kumar, Mary Lou Hines: Performance of Multiversion and Distributed Two-Phase Locking Concurrency Control Mechanisms in Distributed Databases, Information Sciences, 96(1), 1997.

Digital Library

[9]

Michael J. Cahill, Uwe Röhm, Alan David Fekete: Serializable Isolation for Snapshot Databases. TODS, 34(4), 2009.

Digital Library

[10]

IBM solidDB, information available at http://www.ibm.com/.

[11]

Michael J. Carey: Multiple Versions and the Performance of Optimistic Concurrency Control. Tech. Rep. 517, Computer Sciences Dept., Univ. of Wisconsin-Madison, 1983.

[12]

Michael J. Carey, Waleed A. Muhanna: The Performance of Multiversion Concurrency Algorithms, TODS, 4(4), 1985.

[13]

Theo Härder, Erwin Petry: Evaluation of a Multiple Version Scheme for Concurrency Control, Information Systems, 12(1), 1987.

[14]

IBM SolidDb Performance on Intel Systems, white paper at http://download.intel.com/business/software/testimonials/downloads/xeon5500/ibm.pdf.

[15]

Ryan Johnson, Ippokratis Pandis, Anastasia Ailamaki: Improving OLTP Scalability using Speculative Lock Inheritance. PVLDB, 2(1), 2009.

Digital Library

[16]

Vijay Kumar (Ed.): Performance of Concurrency Control Mechanisms in Centralized Database Systems. Prentice-Hall 1996, ISBN 0-13-065442-6.

Digital Library

[17]

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. TODS, 6(2), 1981.

Digital Library

[18]

Sanjay Kumar Madria, Mohammed Baseer, Vijay Kumar, Sourav S. Bhowmick: A Transaction Model and Multiversion Concurrency Control for Mobile Database Systems, Distributed and Parallel Databases, 22(2-3), 2007.

Digital Library

[19]

Ippokratis Pandis, Ryan Johnson, Nikos Hardavellas, Anastasia Ailamaki: Data-Oriented Transaction Execution. PVLDB, 3(1), 2010.

Digital Library

[20]

Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions, TODS, 9(1), 1984.

Digital Library

[21]

PostgreSQL 8.4.2 Documentation, Ch. 13 Concurrency Control, available from www.postgresql.org.

[22]

Oracle TimesTen In-Memory Database, information available at http://www.oracle.com.

[23]

SQL Server 2008 Books Online: Isolation Levels in the Database Engine, available at http://msdn.microsoft.com/en-us/library/ms189122.aspx.

[24]

Telecommunication Application Transaction Processing (TATP) Benchmark Description, available at http://tatpbenchmark.sourceforge.net/.

[25]

Robert Tarjan: Depth-First Search and Linear Graph Algorithms, SIAM J. of Computing, 1(2), 1972.

[26]

Alexander Thomasian: Concurrecy control: Methods, Performance and Analysis, ACM Computing Surveys, 30(1), 1998.

Digital Library

[27]

http://www.cs.wisc.edu/~sblanas/proofsketch.pdf

Cited By

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
https://dl.acm.org/doi/10.14778/3685800.3685915
Kobus TKokoci?ski MWojciechowski PDhulipala LSun Y(2024)Jiffy: A Lock-free Skip List with Batch Updates and Snapshots (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673410(5-7)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673410
Huang KWang TZhou QMeng Q(2023)The Art of Latency Hiding in Modern Database EnginesProceedings of the VLDB Endowment10.14778/3632093.363211717:3(577-590)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632117
Show More Cited By

Index Terms

High-performance concurrency control mechanisms for main-memory databases

Recommendations

Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data

Multi-Version Concurrency Control (MVCC) is a widely employed concurrency control mechanism, as it allows for execution modes where readers never block writers. However, most systems implement only snapshot isolation (SI) instead of full ...
Low overhead concurrency control for partitioned main memory databases
SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data

Database partitioning is a technique for improving the performance of distributed OLTP databases, since "single partition" transactions that access data on one partition do not need coordination with other partitions. For workloads that are amenable to ...
On the Design and Implementation of High-Performance Transaction Processing in Main-Memory Databases

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 5, Issue 4

December 2011

120 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 December 2011

Published in PVLDB Volume 5, Issue 4

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

123
Total Citations
View Citations
931
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
https://dl.acm.org/doi/10.14778/3685800.3685915
Kobus TKokoci?ski MWojciechowski PDhulipala LSun Y(2024)Jiffy: A Lock-free Skip List with Batch Updates and Snapshots (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673410(5-7)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673410
Huang KWang TZhou QMeng Q(2023)The Art of Latency Hiding in Modern Database EnginesProceedings of the VLDB Endowment10.14778/3632093.363211717:3(577-590)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632117
Kraft PLi QZhou XBailis PStonebraker MZaharia MYu X(2023)Epoxy: ACID Transactions across Diverse Data StoresProceedings of the VLDB Endowment10.14778/3611479.361148416:11(2742-2754)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611484
Alhomssi ALeis V(2023)Scalable and Robust Snapshot Isolation for High-Performance Storage EnginesProceedings of the VLDB Endowment10.14778/3583140.358315716:6(1426-1438)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583157
Raza AChrysogelos PAnadiotis AAilamaki A(2023)One-shot Garbage Collection for In-memory OLTP through Temporality-aware Version StorageProceedings of the ACM on Management of Data10.1145/35886991:1(1-25)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588699
Hu TWang TZhou Q(2022)Online schema evolution is (almost) free for snapshot databasesProceedings of the VLDB Endowment10.14778/3565816.356581816:2(140-153)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.14778/3565816.3565818
Helt JSharma AAbadi DLloyd WFaleiro J(2022)C5Proceedings of the VLDB Endowment10.14778/3561261.356126216:1(1-14)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.14778/3561261.3561262
Freitag MKemper ANeumann T(2022)Memory-optimized multi-version concurrency control for disk-based database systemsProceedings of the VLDB Endowment10.14778/3551793.355183215:11(2797-2810)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551832
Lee LXie SMa YChen S(2022)Index checkpoints for instant recovery in in-memory database systemsProceedings of the VLDB Endowment10.14778/3529337.352935015:8(1671-1683)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.14778/3529337.3529350
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents