Transaction Scheduling: From Conflicts to Runtime Conflicts
Open Access
- 26 May 2023
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (1) , 1-26
Abstract
This paper studies how to improve the performance of main memory multicore OLTP systems for executing transactions with conflicts. A promising approach is to partition transaction workloads into mutually conflict-free clusters, and distribute the clusters to different cores for concurrent execution. We show that if transactions in each cluster are properly scheduled, transactions that are traditionally considered conflicting can be executed without conflicts at runtime. In light of this, we propose to schedule transactions and reduce runtime conflicts, instead of partitioning based on the conventional notion of conflicts. We formulate the transaction scheduling problem to minimize runtime conflicts, and show that the problem is NP-complete. This said, we develop an efficient scheduling algorithm to improve parallelism. Moreover, for transactions that are not packed in batches, we show that runtime conflict analysis also helps reduce conflict penalties, by proposing a proactive deferring method. Using standard and enhanced benchmarks, we show that on average our scheduling and proactive deferring methods improve the throughput of existing partitioners and concurrency control protocols by 131% and 109%, respectively, up to 294% and 152%.Keywords
This publication has 29 references indexed in Scilit:
- The full story of 1000 coresThe VLDB Journal, 2022
- Performance of OLTP via Intelligent Scheduling2018
- ERMIA2016
- High-performance ACID via modular concurrency control2015
- Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems2015
- Speedy transactions in multicore in-memory databases2013
- SWORD2013
- Benchmarking cloud serving systems with YCSB2010
- Low overhead concurrency control for partitioned main memory databases2010
- Formal Aspects of Serializability in Database Concurrency ControlIEEE Transactions on Software Engineering, 1979