More Web Proxy on the site http://driver.im/

research-article

Contention-aware lock scheduling for transactional databases

Authors:

Barzan Mozafari,

Grant SchoenebeckAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 11, Issue 5

Pages 648 - 662

https://doi.org/10.1145/3187009.3177740

Published: 01 January 2018 Publication History

Abstract

Lock managers are among the most studied components in concurrency control and transactional systems. However, one question seems to have been generally overlooked: "When there are multiple lock requests on the same object, which one(s) should be granted first?"

Nearly all existing systems rely on a FIFO (first in, first out) strategy to decide which transaction(s) to grant the lock to. In this paper, however, we show that the lock scheduling choices have significant ramifications on the overall performance of a transactional system. Despite the large body of research on job scheduling outside the database context, lock scheduling presents subtle but challenging requirements that render existing results on scheduling inapt for a transactional database. By carefully studying this problem, we present the concept of contention-aware scheduling, show the hardness of the problem, and propose novel lock scheduling algorithms (LDSF and bLDSF), which guarantee a constant factor approximation of the best scheduling. We conduct extensive experiments using a popular database on both TPC-C and a microbenchmark. Compared to FIFO---the default scheduler in most database systems---our bLDSF algorithm yields up to 300x speedup in overall transaction latency. Alternatively, our LDSF algorithm, which is simpler and achieves comparable performance to bLDSF, has already been adopted by open-source community, and was chosen as the default scheduling strategy in MySQL 8.0.3+

References

[1]

Contention-aware transaction scheduling arriving in InnoDB to boost performance. http://mysqlserverteam.com/contention-aware-transaction-scheduling-arriving-in-innodb-to-boost-performance/.

[2]

Db2 documentation. https://www.ibm.com/support/knowledgecenter/en/SSEPEK_12.0.0/perf/src/tpc/db2z_lockcontention.html.

[3]

Mysql source code. https://github.com/mysql/mysqlserver/blob/5.7/storage/innobase/lock/lockOlock.cc.

[4]

Overview of teradata database locking. http://info.teradata.com/HTMLPubs/DB_TTU_16_00/index.html#page/General_Reference%2FB035-1091-160K%2Fmtg1472241438567.html.

[5]

Postgres documentation. https://github.com/postgres/postgres/blob/master/src/backend/storage/lmgr/README.

[6]

Sql server, lock manager, and relaxed fifo. https://blogs.msdn.microsoft.com/psssql/2009/06/02/sql-server-lock-manager-and-relaxed-fifo/.

[7]

R. Abbott and H. Garcia-Molina. Scheduling real-time transactions. SIGMOD Rec., pages 71--81, 1988.

Digital Library

[8]

R. K. Abbott and H. Garcia-Molina. Scheduling real-time transactions: A performance evaluation. TODS, pages 513--560, 1992.

Digital Library

[9]

B. Adelberg, B. Kao, and H. Garcia-Molina. Database support for efficiently maintaining derived data. In EDBT, pages 223--240, 1996.

Digital Library

[10]

R. Agrawal, M. J. Carey, and L. W. McVoy. The performance of alternative strategies for dealing with deadlocks in database management systems. TSE, pages 1348--1363, 1987.

Digital Library

[11]

D. V. Aken, A. Pavlo, G. J. Gordon, and B. Zhang. Automatic database management system tuning through large-scale machine learning. In SIGMOD, pages 1009--1024, 2017.

Digital Library

[12]

S. Altmeyer, S. M. Sundharam, and N. Navet. The case for fifo real-time scheduling. Technical report, 2016.

[13]

R. F. Aranha, V. Ganti, S. Narayanan, C. Muthukrishnan, S. Prasad, and K. Ramamritham. Implementation of a real-time database system. Information Systems, pages 55--74, 1996.

Digital Library

[14]

C. Bector, Y. P. Gupta, and M. C. Gupta. V-shape property of optimal sequence of jobs about a common due date on a single machine. Computers & operations research, pages 583--588, 1989.

[15]

P. A. Bernstein and N. Goodman. Concurrency control in distributed database systems. ACM Computing Surveys, pages 185--221, 1981.

Digital Library

[16]

D. P. Bovet and M. Cesati. Understanding the Linux kernel. 2005.

Digital Library

[17]

X. Cai. V-shape property for job sequences that minimize the expected completion time variance. EJOR, 1996.

[18]

M. J. Carey and M. Stonebraker. The performance of concurrency control algorithms for database management systems. In VLDB, pages 107--118, 1984.

Digital Library

[19]

S. Chakravarthy, D.-K. Hong, and T. Johnson. Real-time transaction scheduling: A framework for synthesizing static and dynamic factors. RTSS, pages 135--170, 1998.

Digital Library

[20]

B.-C. Choi, S.-H. Yoon, and S.-J. Chung. Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. EJOR, pages 964--974, 2007.

[21]

J. Cipar, Q. Ho, J. K. Kim, S. Lee, G. R. Ganger, G. Gibson, K. Keeton, and E. P. Xing. Solving the straggler problem with bounded staleness. In HotOS, pages 22--22, 2013.

Digital Library

[22]

A. DasGupta. Finite sample theory of order statistics and extremes. In Probability for Statistics and Machine Learning, pages 221--248. 2011.

[23]

L. Daynès, O. Gruber, and P. Valduriez. Locking in oodbms client supporting nested transactions. In ICDE, pages 316--323, 1995.

Digital Library

[24]

D. E. Difallah, A. Pavlo, C. Curino, and P. Cudre-Mauroux. Oltp-bench: An extensible testbed for benchmarking relational databases. PVLDB, 7(4):277--288, 2013.

Digital Library

[25]

J. Du and J. Y.-T. Leung. Scheduling tree-structured tasks with restricted execution times. Information processing letters, pages 183--188, 1988.

Digital Library

[26]

J. Du and J. Y.-T. Leung. Scheduling tree-structured tasks on two processors to minimize schedule length. SIDMA, pages 176--196, 1989.

Digital Library

[27]

A. C. Dusseau, R. H. Arpaci, and D. E. Culler. Effective distributed scheduling of parallel workloads. ACM SIGMETRICS Performance Evaluation Review, pages 25--36, 1996.

Digital Library

[28]

S. Eilon and I. Chowdhury. Minimising waiting time variance in the single machine problem. Management Science, pages 567--575, 1977.

Digital Library

[29]

B. Eisenberg. On the expectation of the maximum of iid geometric random variables. Statistics & Probability Letters, pages 135--143, 2008.

[30]

A. Feldmann, M.-Y. Kao, J. Sgall, and S.-H. Teng. Optimal online scheduling of parallel jobs with dependencies. In STOC, pages 642--651, 1993.

Digital Library

[31]

K. B. Ferreira, P. G. Bridges, R. Brightwell, and K. T. Pedretti. The impact of system design parameters on application noise sensitivity. Cluster computing, pages 117--129, 2013.

Digital Library

[32]

P. Franaszek and J. T. Robinson. Limitations of concurrency in transaction processing. TODS, 1985.

Digital Library

[33]

L. George and P. Minet. A fifo worst case analysis for a hard real-time distributed problem with consistency constraints. In ICDCS, pages 441--448, 1997.

Digital Library

[34]

A. Guinet and M. Solomon. Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time. IJPR, pages 1643--1654, 1996.

[35]

L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In SODA, pages 142--151, 1996.

Digital Library

[36]

J. R. Haritsa, M. J. Canrey, and M. Livny. Value-based scheduling in real-time database systems. VLDBJ, pages 117--152, 1993.

Digital Library

[37]

J. R. Haritsa, M. J. Carey, and M. Livny. Data access scheduling in firm real-time database systems. RTSS, pages 203--241, 1992.

Digital Library

[38]

J. R. Haritsa, M. Livny, and M. J. Carey. Earliest deadline scheduling for real-time database systems. In RTSS, pages 232--242, 1991.

[39]

C. He, J. Y.-T. Leung, K. Lee, and M. L. Pinedo. Improved algorithms for single machine scheduling with release dates and rejections. 4OR, pages 41--55, 2016.

[40]

D. Hong, T. Johnson, and S. Chakravarthy. Real-time transaction scheduling: a cost conscious approach. 1993.

[41]

J. A. Hoogeveen and A. P. Vestjens. Optimal on-line algorithms for single-machine scheduling. In International Conference on Integer Programming and Combinatorial Optimization, pages 404--414, 1996.

Digital Library

[42]

W. Horn. Single-machine job sequencing with treelike precedence ordering and linear delay penalties. SIAP, pages 189--202, 1972.

[43]

J. Huang. Real-time transaction processing: design, implementation, and performance evaluation. PhD thesis, University of Massachusetts, 1991.

Digital Library

[44]

J. Huang, B. Mozafari, G. Schoenebeck, and T. Wenisch. A top-down approach to achieving performance predictability in database systems. In SIGMOD, 2017.

Digital Library

[45]

J. Huang, B. Mozafari, and T. Wenisch. Statistical analysis of latency through semantic profiling. In EuroSys, 2017.

Digital Library

[46]

T. Ibaraki, T. Kameda, and N. Katoh. Cautious transaction schedulers for database concurrency control. TSE, pages 997--1009, 1988.

Digital Library

[47]

G. C. Kamath. Bounds on the expectation of the maximum of samples from a gaussian. URL http://www.gautamkamath.com/writings/gaussian_max.pdf, 2015.

[48]

B. Kao and H. Garcia-Molina. An overview of real-time database systems. In Real Time Computing, pages 261--282. 1994.

[49]

A. M. Krieger and M. Raghavachari. V-shape property for optimal schedules with monotone penalty functions. Computers & operations research, pages 533--534, 1992.

Digital Library

[50]

J. Lee and S. H. Son. Performance of concurrency control algorithms for real-time database systems., 1996.

[51]

J. P. Lehoczky. Scheduling communication networks carrying real-time traffic. In RTSS, pages 470--479, 1998.

Digital Library

[52]

J. K. Lenstra, A. R. Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of discrete mathematics, pages 343--362, 1977.

[53]

H. Leontyev and J. H. Anderson. Tardiness bounds for fifo scheduling on multiprocessors. In ECRTS, pages 71--71, 2007.

Digital Library

[54]

Q. Lin, P. Chang, G. Chen, B. C. Ooi, K.-L. Tan, and Z. Wang. Towards a non-2pc transaction management in distributed database systems. In SIGMOD, pages 1659--1674, 2016.

Digital Library

[55]

C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. JACM, pages 46--61, 1973.

Digital Library

[56]

P. P. Macri. Deadlock detection and resolution in a codasyl based data management system. In SIGMOD, pages 45--49, 1976.

[57]

D. P. Mitchell and M. J. Merritt. A distributed algorithm for deadlock detection and resolution. In PODC, pages 282--284, 1984.

Digital Library

[58]

B. Mozafari, C. Curino, A. Jindal, and S. Madden. Performance and resource modeling in highly-concurrent OLTP workloads. In SIGMOD, 2013.

Digital Library

[59]

B. Mozafari, C. Curino, and S. Madden. DBSeer: Resource and performance prediction for building a next generation database cloud. In CIDR, 2013.

[60]

B. Mozafari, J. Ramnarayan, S. Menon, Y. Mahajan, S. Chakraborty, H. Bhanawat, and K. Bachhav. Snappydata: A unified cluster for streaming, transactions, and interactive analytics. In CIDR, 2017.

[61]

R. R. Muntz and E. G. Coffman Jr. Preemptive scheduling of real-time tasks on multiprocessor systems. JACM, pages 324--338, 1970.

Digital Library

[62]

J. Pei, X. Liu, P. M. Pardalos, W. Fan, and S. Yang. Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times. Annals of Operations Research, pages 175--195, 2017.

[63]

F. Petrini, D. J. Kerbyson, and S. Pakin. The case of the missing supercomputer performance: Achieving optimal performance on the 8,192 processors of asci q. In Supercomputing, 2003 ACM/IEEE Conference, pages 55--55, 2003.

Digital Library

[64]

C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In WADS, pages 86--97, 1995.

Digital Library

[65]

K. Ramamritham. Real-time databases. Distributed and parallel databases, pages 199--226, 1993.

Digital Library

[66]

R. Rastogi, S. Seshadri, P. Bohannon, D. Leinbaugh, A. Silberschatz, and S. Sudarshan. Improving predictability of transaction execution times in real-time databases. RTSS, pages 283--302, 2000.

Digital Library

[67]

A. J. Ruiz-Torres and G. Centeno. Scheduling with flexible resources in parallel workcenters to minimize maximum completion time. Computers & operations research, pages 48--69, 2007.

[68]

L. Sha, R. Rajkumar, and J. P. Lehooczky. Concurrency control for distributed real-time databases. SIGMOD Rec., 1988.

Digital Library

[69]

J. B. Sidney. Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Operations Research, pages 283--298, 1975.

Digital Library

[70]

W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, pages 59--66, 1956.

[71]

J. A. Stankovic, M. Spuri, K. Ramamritham, and G. C. Buttazzo. Deadline scheduling for real-time systems: EDF and related algorithms. 2012.

Digital Library

[72]

B. Tian, J. Huang, B. Mozafari, and G. Schoenebeck. Contention-aware lock scheduling for transactional databases. Technical Report, https://web.eecs.umich.edu/~mozafari/php/data/uploads/lock-schd-report.pdf, 2017.

[73]

D. Towsley and S. Panwar. On the optimality of minimum laxity and earliest deadline scheduling for real-time multiprocessors. In Workshop on Real Time, pages 17--24, 1990.

[74]

S.-M. Tseng, Y.-H. Chin, and W.-P. Yang. Scheduling real-time transactions with dynamic values: a performance evaluation. In Workshop on Real-Time Computing Systems and Applications, pages 60--67, 1995.

Digital Library

[75]

Ö. Ulusoy and G. G. Belford. Real-time transaction scheduling in database systems. Information Systems, pages 559--580, 1993.

Digital Library

[76]

V. Vani and M. Raghavachari. Deterministic and random single machine sequencing with variance minimization. Operations Research, pages 111--120, 1987.

[77]

M. Xiong, Q. Wang, and K. Ramamritham. On earliest deadline first scheduling for temporal consistency maintenance. RTSS, pages 208--237, 2008.

Digital Library

[78]

D. Y. Yoon, B. Mozafari, and D. P. Brown. Dbseer: Pain-free database administration through workload intelligence. PVLDB, 8(12):2036--2039, 2015.

Digital Library

[79]

R. Zajcew, P. Roy, D. L. Black, C. Peak, P. Guedes, B. Kemp, J. LoVerso, M. Leibensperger, M. Barnett, F. Rabii, et al. An osf/1 unix for massively parallel multicomputers. In USENIX Winter, pages 449--468, 1993.

Cited By

Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Xing JHsu KXia YCai YLi YZhang YChen A(2024)Occam: A Programming System for Reliable Network ManagementProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650086(148-162)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650086
Zhang CZhang SChen TZhang RLiu K(2023)An Optimized Solution for Highly Contended Transactional WorkloadsDependable Software Engineering. Theories, Tools, and Applications10.1007/978-981-99-8664-4_23(402-418)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-8664-4_23
Show More Cited By

Contention-aware lock scheduling for transactional databases
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Contention-aware lock scheduling for transactional databases

Lock managers are among the most studied components in concurrency control and transactional systems. However, one question seems to have been generally overlooked: "When there are multiple lock requests on the same object, which one(s) should be ...
An efficient lock-aware transactional memory implementation
ICOOOLPS '09: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems

Transactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the ...
Transactional lock-free execution of lock-based programs
Special Issue: Proceedings of the 10th annual conference on Architectural Support for Programming Languages and Operating Systems

This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access ...

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 11, Issue 5

January 2018

274 pages

ISSN:2150-8097

Editors:
Jian Pei
Simon Fraser University
,
Sihem Amer-Yahia
University of Grenoble Alpes, CNRS

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 January 2018

Published in PVLDB Volume 11, Issue 5

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
90
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Xing JHsu KXia YCai YLi YZhang YChen A(2024)Occam: A Programming System for Reliable Network ManagementProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650086(148-162)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650086
Zhang CZhang SChen TZhang RLiu K(2023)An Optimized Solution for Highly Contended Transactional WorkloadsDependable Software Engineering. Theories, Tools, and Applications10.1007/978-981-99-8664-4_23(402-418)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-8664-4_23
Bang TMay NPetrov IBinnig C(2022)The full story of 1000 coresThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-022-00742-431:6(1185-1213)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s00778-022-00742-4
Vandevoort BKetsman BKoch CNeven F(2021)Robustness against read committed for transaction templatesProceedings of the VLDB Endowment10.14778/3476249.347626814:11(2141-2153)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476268
Sheng YTomasic AZhang TPavlo ABordawekar RShmueli O(2019)Scheduling OLTP transactions via learned abort predictionProceedings of the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management10.1145/3329859.3329871(1-8)Online publication date: 5-Jul-2019
https://dl.acm.org/doi/10.1145/3329859.3329871
Lissandrini MBrugnara MVelegrakis Y(2018)Beyond macrobenchmarksProceedings of the VLDB Endowment10.14778/3297753.329775912:4(390-403)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.14778/3297753.3297759
Yoon DChowdhury MMozafari BDas GJermaine CBernstein P(2018)Distributed Lock Management with RDMAProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196890(1571-1586)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196890

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