research-article

An empirical evaluation of in-memory multi-version concurrency control

Authors:

Andrew PavloAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 10, Issue 7

Pages 781 - 792

https://doi.org/10.14778/3067421.3067427

Published: 01 March 2017 Publication History

Abstract

Multi-version concurrency control (MVCC) is currently the most popular transaction management scheme in modern database management systems (DBMSs). Although MVCC was discovered in the late 1970s, it is used in almost every major relational DBMS released in the last decade. Maintaining multiple versions of data potentially increases parallelism without sacrificing serializability when processing transactions. But scaling MVCC in a multi-core and in-memory setting is non-trivial: when there are a large number of threads running in parallel, the synchronization overhead can outweigh the benefits of multi-versioning.

To understand how MVCC perform when processing transactions in modern hardware settings, we conduct an extensive study of the scheme's four key design decisions: concurrency control protocol, version storage, garbage collection, and index management. We implemented state-of-the-art variants of all of these in an in-memory DBMS and evaluated them using OLTP workloads. Our analysis identifies the fundamental bottlenecks of each design choice.

References

[1]

MemSQL. http://www.memsql.com.

[2]

MySQL. http://www.mysql.com.

[3]

NuoDB. http://www.nuodb.com.

[4]

Oracle Timeline. http://oracle.com.edgesuite.net/timeline/oracle/.

[5]

Peloton. http://pelotondb.org.

[6]

PostgreSQL. http://www.postgresql.org.

[7]

J. Arulraj and et al. Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads. SIGMOD, 2016.

Digital Library

[8]

H. Berenson and et al. A Critique of ANSI SQL Isolation Levels. SIGMOD'95.

Digital Library

[9]

P. A. Bernstein and N. Goodman. Concurrency Control in Distributed Database Systems. CSUR, 13(2), 1981.

Digital Library

[10]

P. A. Bernstein, C. W. Reid, and S. Das. Hyder-A Transactional Record Manager for Shared Flash. In CIDR, 2011.

[11]

P. A. Bernstein and et al. Concurrency Control and Recovery in Database Systems. 1987.

Digital Library

[12]

M. J. Cahill, U. Röhm, and A. D. Fekete. Serializable Isolation for Snapshot Databases. SIGMOD, 2008.

Digital Library

[13]

M. J. Carey and W. A. Muhanna. The Performance of Multiversion Concurrency Control Algorithms. TOCS, 4(4), 1986.

Digital Library

[14]

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In SoCC, 2010.

Digital Library

[15]

T. David, R. Guerraoui, and V. Trigonakis. Everything You Always Wanted To Know About Synchronization But Were Afraid To Ask. In SOSP, 2013.

Digital Library

[16]

C. Diaconu and et al. Hekaton: SQL Server's Memory-Optimized OLTP Engine. SIGMOD, 2013.

Digital Library

[17]

K. P. Eswaran and et al. The Notions of Consistency and Predicate Locks in a Database System. Communications of the ACM, 19(11), 1976.

Digital Library

[18]

J. M. Faleiro and D. J. Abadi. Rethinking Serializable Multiversion Concurrency Control. VLDB, 2014.

Digital Library

[19]

B. Fan, D. G. Andersen, and M. Kaminsky. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In NSDI, 2013.

Digital Library

[20]

A. Fekete, D. Liarokapis, E. O'Neil, P. O'Neil, and D. Shasha. Making Snapshot Isolation Serializable. TODS, 30(2), 2005.

Digital Library

[21]

M. Grund, J. Krüger, H. Plattner, A. Zeier, P. Cudre-Mauroux, and S. Madden. HYRISE: A Main Memory Hybrid Storage Engine. VLDB, 2010.

Digital Library

[22]

A. Harrison. InterBase's Beginnings. http://www.firebirdsql.org/en/ann-harrison-s-reminiscences-on-interbase-s-beginnings/.

[23]

S. Héman, M. Zukowski, N. J. Nes, L. Sidirourgos, and P. Boncz. Positional Update Handling in Column Stores. SIGMOD, 2010.

Digital Library

[24]

K. Kim, T. Wang, J. Ryan, and I. Pandis. ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads. SIGMOD, 2016.

Digital Library

[25]

E. Klitzke. Why uber engineering switched from postgres to mysql. https://eng.uber.com/mysql-migration/, July 2016.

[26]

H.-T. Kung and J. T. Robinson. On Optimistic Methods for Concurrency Control. TODS, 6(2), 1981.

Digital Library

[27]

P.-Å. Larson and et al. High-Performance Concurrency Control Mechanisms for Main-Memory Databases. VLDB, 2011.

Digital Library

[28]

J. Lee, M. Muehle, N. May, F. Faerber, V. Sikka, H. Plattner, J. Krueger, and M. Grund. High-Performance Transaction Processing in SAP HANA. IEEE Data Eng. Bull., 36(2), 2013.

[29]

J. Lee and et al. Hybrid Garbage Collection for Multi-Version Concurrency Control in SAP HANA. SIGMOD, 2016.

Digital Library

[30]

V. Leis, A. Kemper, and T. Neumann. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. ICDE, 2013.

Digital Library

[31]

D. Lomet, A. Fekete, R. Wang, and P. Ward. Multi-Version Concurrency via Timestamp Range Conflict Management. ICDE, 2012.

Digital Library

[32]

D. B. Lomet, S. Sengupta, and J. J. Levandoski. The Bw-Tree: AB-tree for New Hardware Platforms. ICDE, 2013.

Digital Library

[33]

N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. Rethinking Main memory OLTP Recovery. ICDE, 2014.

[34]

Y. Mao, E. Kohler, and R. T. Morris. Cache Craftiness for Fast Multicore Key-Value Storage. In EuroSys, 2012.

Digital Library

[35]

C. Mohan. ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB'90.

Digital Library

[36]

T. Neumann, T. Mühlbauer, and A. Kemper. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. SIGMOD, 2015.

Digital Library

[37]

A. Pavlo and M. Aslett. What's Really New with NewSQL? SIGMOD Rec., 45(2):45--55, June 2016.

Digital Library

[38]

D. P. Reed. Naming and Synchronization in a Decentralized Computer System. Ph.D. dissertation, 1978.

[39]

D. P. Reed. Implementing Atomic Actions on Decentralized Data. TOCS, 1983.

Digital Library

[40]

V. Sikka and et al. Efficient Transaction Processing in SAP HANA Database: The End of a Column Store Myth. SIGMOD, 2012.

Digital Library

[41]

M. Stonebraker and L. A. Rowe. The Design of POSTGRES. SIGMOD, 1986.

Digital Library

[42]

M. Stonebraker and et al. The End of an Architectural Era: (It's Time for a Complete Rewrite). VLDB, 2007.

Digital Library

[43]

The Transaction Processing Council. TPC-C Benchmark (Revision 5.9.0). http://www.tpc.org/tpcc/spec/tpcc_current.pdf, June 2007.

[44]

S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy Transactions in Multicore In-Memory Databases. In SOSP, 2013.

Digital Library

[45]

T. Wang, R. Johnson, A. Fekete, and I. Pandis. Efficiently Making (Almost) Any Concurrency Control Mechanism Serializable. arXiv:1605.04292, 2016.

[46]

Y. Wu, C.-Y. Chan, and K.-L. Tan. Transaction Healing: Scaling Optimistic Concurrency Control on Multicores. In SIGMOD, 2016.

Digital Library

[47]

X. Yu, A. Pavlo, D. Sanchez, and S. Devadas. Tictoc: Time Traveling Optimistic Concurrency Control. In SIGMOD, 2016.

Digital Library

[48]

X. Yu and et al. Staring Into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores. VLDB, 2014.

Digital Library

[49]

W. Zheng, S. Tu, E. Kohler, and B. Liskov. Fast Databases with Fast Durability and Recovery Through Multicore Parallelism. In OSDI, 2014.

Digital Library

Cited By

Hou JZhao ZWang ZLu WJin GWen DDu X(2024)AeonG: An Efficient Built-in Temporal Support in Graph DatabasesProceedings of the VLDB Endowment10.14778/3648160.364818717:6(1515-1527)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.14778/3648160.3648187
Hui YYu MQi HGan YLi TLi YRen XMa SLu XWang Y(2024)On the Feasibility and Benefits of Extensive EvaluationProceedings of the ACM on Management of Data10.1145/36771372:4(1-24)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677137
Camacho-Rodríguez JAgrawal AGruenheid AGosalia APetculescu CAguilar-Saborit JFloratou ACurino CRamakrishnan R(2024)LST-Bench: Benchmarking Log-Structured Tables in the CloudProceedings of the ACM on Management of Data10.1145/36393142:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639314
Show More Cited By

An empirical evaluation of in-memory multi-version concurrency control
1. Information systems
  1. Data management systems

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 ...
Transaction Repair for Multi-Version Concurrency Control
SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data

The optimistic variants of Multi-Version Concurrency Control (MVCC) avoid blocking concurrent transactions at the cost of having a validation phase. Upon failure in the validation phase, the transaction is usually aborted and restarted from scratch. The ...
Multi-version Speculative Concurrency Control with Delayed Commit

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 10, Issue 7

March 2017

132 pages

ISSN:2150-8097

Editors:
Peter Boncz
CWI
,
Ken Salem
University of Waterloo

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 March 2017

Published in PVLDB Volume 10, Issue 7

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

79
Total Citations
View Citations
1,185
Total Downloads

Downloads (Last 12 months)149
Downloads (Last 6 weeks)15

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hou JZhao ZWang ZLu WJin GWen DDu X(2024)AeonG: An Efficient Built-in Temporal Support in Graph DatabasesProceedings of the VLDB Endowment10.14778/3648160.364818717:6(1515-1527)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.14778/3648160.3648187
Hui YYu MQi HGan YLi TLi YRen XMa SLu XWang Y(2024)On the Feasibility and Benefits of Extensive EvaluationProceedings of the ACM on Management of Data10.1145/36771372:4(1-24)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677137
Camacho-Rodríguez JAgrawal AGruenheid AGosalia APetculescu CAguilar-Saborit JFloratou ACurino CRamakrishnan R(2024)LST-Bench: Benchmarking Log-Structured Tables in the CloudProceedings of the ACM on Management of Data10.1145/36393142:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639314
Clark JDonaldson AWickerson JRigger M(2024)Validating Database System Isolation Level Implementations with Version Certificate RecoveryProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650080(754-768)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650080
Blelloch GWei YLee IChabbi MSteuwer M(2024)VERLIB: Concurrent Versioned PointersProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638501(200-214)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638501
Yang XZhang YChen HLi FWang BFang JSun CWang YBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)PolarDB-MP: A Multi-Primary Cloud-Native Database via Disaggregated Shared MemoryCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653377(295-308)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3653377
Wang XPeng YHuang H(2024)Gria: an efficient deterministic concurrency control protocolFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-023-2605-z18:4Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11704-023-2605-z
Zhao HLi JLu WZhang QYang WZhong JZhang MLi HDu XPan A(2024)RCBench: an RDMA-enabled transaction framework for analyzing concurrency control algorithmsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00821-033:2(543-567)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00778-023-00821-0
Zhang SSoto JMarkl V(2024)A survey on transactional stream processingThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00814-z33:2(451-479)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00778-023-00814-z
Oh JYoo SNam HMin CWon YNaor DGoel A(2023)CJFSProceedings of the 21st USENIX Conference on File and Storage Technologies10.5555/3585938.3585949(167-181)Online publication date: 21-Feb-2023
https://dl.acm.org/doi/10.5555/3585938.3585949
Show More Cited By

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.

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