Yingjun Wu
Skip Abstract Section
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.
- MemSQL. http://www.memsql.com.Google Scholar
- MySQL. http://www.mysql.com.Google Scholar
- NuoDB. http://www.nuodb.com.Google Scholar
- Oracle Timeline. http://oracle.com.edgesuite.net/timeline/oracle/.Google Scholar
- Peloton. http://pelotondb.org.Google Scholar
- PostgreSQL. http://www.postgresql.org.Google Scholar
- J. Arulraj and et al. Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads. SIGMOD, 2016. Google ScholarDigital Library
- H. Berenson and et al. A Critique of ANSI SQL Isolation Levels. SIGMOD'95. Google ScholarDigital Library
- P. A. Bernstein and N. Goodman. Concurrency Control in Distributed Database Systems. CSUR, 13(2), 1981. Google ScholarDigital Library
- P. A. Bernstein, C. W. Reid, and S. Das. Hyder-A Transactional Record Manager for Shared Flash. In CIDR, 2011.Google Scholar
- P. A. Bernstein and et al. Concurrency Control and Recovery in Database Systems. 1987. Google ScholarDigital Library
- M. J. Cahill, U. Röhm, and A. D. Fekete. Serializable Isolation for Snapshot Databases. SIGMOD, 2008. Google ScholarDigital Library
- M. J. Carey and W. A. Muhanna. The Performance of Multiversion Concurrency Control Algorithms. TOCS, 4(4), 1986. Google ScholarDigital Library
- B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In SoCC, 2010. Google ScholarDigital Library
- T. David, R. Guerraoui, and V. Trigonakis. Everything You Always Wanted To Know About Synchronization But Were Afraid To Ask. In SOSP, 2013. Google ScholarDigital Library
- C. Diaconu and et al. Hekaton: SQL Server's Memory-Optimized OLTP Engine. SIGMOD, 2013. Google ScholarDigital Library
- K. P. Eswaran and et al. The Notions of Consistency and Predicate Locks in a Database System. Communications of the ACM, 19(11), 1976. Google ScholarDigital Library
- J. M. Faleiro and D. J. Abadi. Rethinking Serializable Multiversion Concurrency Control. VLDB, 2014. Google ScholarDigital Library
- B. Fan, D. G. Andersen, and M. Kaminsky. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In NSDI, 2013. Google ScholarDigital Library
- A. Fekete, D. Liarokapis, E. O'Neil, P. O'Neil, and D. Shasha. Making Snapshot Isolation Serializable. TODS, 30(2), 2005. Google ScholarDigital Library
- M. Grund, J. Krüger, H. Plattner, A. Zeier, P. Cudre-Mauroux, and S. Madden. HYRISE: A Main Memory Hybrid Storage Engine. VLDB, 2010. Google ScholarDigital Library
- A. Harrison. InterBase's Beginnings. http://www.firebirdsql.org/en/ann-harrison-s-reminiscences-on-interbase-s-beginnings/.Google Scholar
- S. Héman, M. Zukowski, N. J. Nes, L. Sidirourgos, and P. Boncz. Positional Update Handling in Column Stores. SIGMOD, 2010. Google ScholarDigital Library
- K. Kim, T. Wang, J. Ryan, and I. Pandis. ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads. SIGMOD, 2016. Google ScholarDigital Library
- E. Klitzke. Why uber engineering switched from postgres to mysql. https://eng.uber.com/mysql-migration/, July 2016.Google Scholar
- H.-T. Kung and J. T. Robinson. On Optimistic Methods for Concurrency Control. TODS, 6(2), 1981. Google ScholarDigital Library
- P.-Å. Larson and et al. High-Performance Concurrency Control Mechanisms for Main-Memory Databases. VLDB, 2011. Google ScholarDigital Library
- 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.Google Scholar
- J. Lee and et al. Hybrid Garbage Collection for Multi-Version Concurrency Control in SAP HANA. SIGMOD, 2016. Google ScholarDigital Library
- V. Leis, A. Kemper, and T. Neumann. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. ICDE, 2013. Google ScholarDigital Library
- D. Lomet, A. Fekete, R. Wang, and P. Ward. Multi-Version Concurrency via Timestamp Range Conflict Management. ICDE, 2012. Google ScholarDigital Library
- D. B. Lomet, S. Sengupta, and J. J. Levandoski. The Bw-Tree: AB-tree for New Hardware Platforms. ICDE, 2013. Google ScholarDigital Library
- N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. Rethinking Main memory OLTP Recovery. ICDE, 2014.Google ScholarCross Ref
- Y. Mao, E. Kohler, and R. T. Morris. Cache Craftiness for Fast Multicore Key-Value Storage. In EuroSys, 2012. Google ScholarDigital Library
- C. Mohan. ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB'90. Google ScholarDigital Library
- T. Neumann, T. Mühlbauer, and A. Kemper. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. SIGMOD, 2015. Google ScholarDigital Library
- A. Pavlo and M. Aslett. What's Really New with NewSQL? SIGMOD Rec., 45(2):45--55, June 2016. Google ScholarDigital Library
- D. P. Reed. Naming and Synchronization in a Decentralized Computer System. Ph.D. dissertation, 1978.Google Scholar
- D. P. Reed. Implementing Atomic Actions on Decentralized Data. TOCS, 1983. Google ScholarDigital Library
- V. Sikka and et al. Efficient Transaction Processing in SAP HANA Database: The End of a Column Store Myth. SIGMOD, 2012. Google ScholarDigital Library
- M. Stonebraker and L. A. Rowe. The Design of POSTGRES. SIGMOD, 1986. Google ScholarDigital Library
- M. Stonebraker and et al. The End of an Architectural Era: (It's Time for a Complete Rewrite). VLDB, 2007. Google ScholarDigital Library
- The Transaction Processing Council. TPC-C Benchmark (Revision 5.9.0). http://www.tpc.org/tpcc/spec/tpcc_current.pdf, June 2007.Google Scholar
- S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy Transactions in Multicore In-Memory Databases. In SOSP, 2013. Google ScholarDigital Library
- T. Wang, R. Johnson, A. Fekete, and I. Pandis. Efficiently Making (Almost) Any Concurrency Control Mechanism Serializable. arXiv:1605.04292, 2016.Google Scholar
- Y. Wu, C.-Y. Chan, and K.-L. Tan. Transaction Healing: Scaling Optimistic Concurrency Control on Multicores. In SIGMOD, 2016. Google ScholarDigital Library
- X. Yu, A. Pavlo, D. Sanchez, and S. Devadas. Tictoc: Time Traveling Optimistic Concurrency Control. In SIGMOD, 2016. Google ScholarDigital Library
- X. Yu and et al. Staring Into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores. VLDB, 2014. Google ScholarDigital Library
- W. Zheng, S. Tu, E. Kohler, and B. Liskov. Fast Databases with Fast Durability and Recovery Through Multicore Parallelism. In OSDI, 2014. Google ScholarDigital Library
Index Terms
- An empirical evaluation of in-memory multi-version concurrency control
Index terms have been assigned to the content through auto-classification.
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 DataMulti-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 DataThe 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 ...
Comments