Predictive Transaction Scheduling for Alleviating Lock Thrashing

To improve the performance for high-contention workloads, modern main-memory database systems seek to design efficient lock managers. However, OLTP engines adopt the classic FCFS strategy to process operations, where the generated execution order does not take current and future conflicts into consideration. In this case, lock dependencies will happen more frequently and thus resulting in high transaction waiting time, referred to as lock thrashing, which is proved to be the main bottleneck of lock-based concurrency control mechanisms. In this paper, we present a transaction scheduler that generates efficient execution order to alleviate the lock thrashing issue. To proactively resolve conflicts, LOTAS predicts which data will be accessed by following operations through building Markov-based prediction graphs. Then LOTAS uses the information to schedule transactions by judging whether a transaction needs to be deferred to acquire locks. Experimental results demonstrate that LOTAS can significantly reduce the lock waiting time and improves the throughput up to 4.8x than the classic FCFS strategy under highly contended workloads.