ACM SIGMOD Anthology TODS dblp.uni-trier.de

Locking Performance in Centralized Databases.

Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985)
@article{DBLP:journals/tods/TayGS85,
  author    = {Y. C. Tay and
               Nathan Goodman and
               Rajan Suri},
  title     = {Locking Performance in Centralized Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {4},
  year      = {1985},
  pages     = {415-462},
  ee        = {http://doi.acm.org/10.1145/4879.4880, db/journals/tods/TayGS85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

An analytic model is used to study the performance of dynamic locking. The analysis uses only the steady-state average values of the variables. The solution to the model is given by a cubic, which has exactly one valid root for the range of parametric values that is of interest. The model's predictions agree well with simulation results for transactions that require up to twenty locks. The model separates data contention from resource contention, thus facilitating an analysis of their separate effects and their interaction. It shows that systems with a particular form of nonuniform access, or with shared locks, are equivalent to systems with uniform access and only exclusive locks.

Blocking due to conflicts is found to impose an upper bound on transaction throughput; this fact leads to a rule of thumb on how much data contention should be permitted in a system. Throughput can exceed this bound if a transaction is restarted whenever it encounters a conflict, provided restart costs and resource contention are low. It can also be exceeded by making transactions predeclare their locks. Raising the multiprogramming level to increase throughput also raises the number of restarts per completion. Transactions should minimize their lock requests, because data contention is proportional to the square of the number of requests. The choice of how much data to lock at a time depends on which part of a general granularity curve the system sees.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Versions of this Paper

References

[1]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121 BibTeX
[2]
R. Balter, P. Berard, Paul Decitre: Why Control of the Concurrency Level in Distributed Systems is More Fundamental Than Deadlock Management. PODC 1982: 183-193 BibTeX
[3]
Forest Baskett, K. Mani Chandy, Richard R. Muntz, Fernando G. Palacios: Open, Closed, and Mixed Networks of Queues with Different Classes of Customers. J. ACM 22(2): 248-260(1975) BibTeX
[4]
Catriel Beeri, Ron Obermarck: A Resource Class Independent Deadlock Detection Algorithm. VLDB 1981: 166-178 BibTeX
[5]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[6]
Michael J. Carey: Modeling and Evaluation of Database Concurrency Control Algorithms. Ph.D. thesis, College of Engineering, University of California, Berkeley 1983
BibTeX
[7]
Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118 BibTeX
[8]
Donald D. Chamberlin, Raymond F. Boyce, Irving L. Traiger: A Deadlock-Free Scheme for Resource Locking in a Data-Base Environment. IFIP Congress 1974: 340-343 BibTeX
[9]
A. Chesnais, Erol Gelenbe, Isi Mitrani: On the Modeling of Parallel Access to Shared Data. Commun. ACM 26(3): 196-202(1983) BibTeX
[10]
...
[11]
Peter J. Denning, Jeffrey P. Buzen: The Operational Analysis of Queueing Network Models. ACM Comput. Surv. 10(3): 225-261(1978) BibTeX
[12]
Peter J. Denning, Kevin C. Kahn, Jacques Leroudier, Dominique Potier, Rajan Suri: Optimal Multiprogramming. Acta Inf. 7: 197-216(1976) BibTeX
[13]
Cory Devor, C. Robert Carlson: Structural locking mechanisms and their effect on database management system performance. Inf. Syst. 7(4): 345-358(1982) BibTeX
[14]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[15]
...
[16]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[17]
Jim Gray: A Transaction Model. ICALP 1980: 282-298 BibTeX
[18]
Jim Gray, Pete Homan, Henry F. Korth, Ron Obermarck: A Straw Man Analysis of the Probability of Waiting and Deadlock in a Database System. Berkeley Workshop 1981: 125 BibTeX
[19]
Keki B. Irani, Hing-Lung Lin: Queuing Network Models for Concurrent Transaction Processing in a Database System. SIGMOD Conference 1979: 134-142 BibTeX
[20]
Werner Kießling, G. Landherr: A Quantitative Comparison of Lockprotocols for Centralized Databases. VLDB 1983: 120-130 BibTeX
[21]
...
[22]
Stephen S. Lavenberg: A Simple Analysis of Exclusive and Shared Lock Contention in a Database System. SIGMETRICS 1984: 143-148 BibTeX
[23]
Wen-Te K. Lin, Jerry Nolte: Performance of Two Phase Locking. Berkeley Workshop 1982: 131-160 BibTeX
[24]
Debasis Mitra: Probabilistic Models and Asymptotic Results for Concurrent Processing with Exclusive and Non-Exclusive Locks. SIAM J. Comput. 14(4): 1030-1051(1985) BibTeX
[25]
Robert J. T. Morris, Wing Shing Wong: Performance Analysis of Locking and Optimistic Concurrency Control Algorithms. Perform. Eval. 5(2): 105-118(1985) BibTeX
[26]
Rudolf Munz, G. Krenz: Concurrency in Database Systems - A Simulation Study. SIGMOD Conference 1977: 111-120 BibTeX
[27]
Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX
[28]
Daniel R. Ries: The Effects of Concurrency Control on the Performance of a Distributed Data Management System. Berkeley Workshop 1979: 75-112 BibTeX
[29]
In Kyung Ryu, Alexander Thomasian: Analysis of Database Performance with Dynamic Locking. J. ACM 37(3): 491-523(1990) BibTeX
[30]
...
[31]
...
[32]
...
[33]
...
[34]
...
[35]
Y. C. Tay, Rajan Suri, Nathan Goodman: A Mean Value Performance Model for Locking in Databases: The No-Waiting Case. J. ACM 32(3): 618-651(1985) BibTeX
[36]
...
[37]
...
[38]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX

Referenced by

  1. Shalab Goel, Bharat K. Bhargava, Sanjay Kumar Madria: An Adaptable Constrained Locking Protocol for High Data Contention Environments. DASFAA 1999: 321-328
  2. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
  3. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  4. Vigyan Singhal, Alan Jay Smith: Analysis of Locking Behavior in Three Real Database Systems. VLDB J. 6(1): 40-52(1997)
  5. Markos Zaharioudakis, Michael J. Carey, Michael J. Franklin: Adaptive, Fine-Grained Sharing in a Client-Server OODBMS: A Callback-Based Approach. ACM Trans. Database Syst. 22(4): 570-627(1997)
  6. Alexander Thomasian: A Performance Comparison of Locking Methods with Limited Wait Depth. IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
  7. Alexander Thomasian: Checkpointing for Optimistic Concurrency Control Methods. IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
  8. Michael J. Carey, Michael J. Franklin, Markos Zaharioudakis: Fine-Grained Sharing in a Page Server OODBMS. SIGMOD Conference 1994: 359-370
  9. Jayant R. Haritsa: Approximate Analysis of Real-Time Database Systems. ICDE 1994: 10-19
  10. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
  11. Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
  12. Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992)
  13. B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 17(1): 163-199(1992)
  14. Axel Mönkeberg, Gerhard Weikum: Performance Evaluation of an Adaptive and Robust Load Control Method for the Avoidance of Data-Contention Thrashing. VLDB 1992: 432-443
  15. Paul M. Bober, Michael J. Carey: Multiversion Query Locking. VLDB 1992: 497-510
  16. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: An Approach to Eliminate Transaction Blocking in Locking Protocols. PODS 1992: 223-235
  17. Alexander Thomasian: Thrashing in Two-Phase Locking Revisited. ICDE 1992: 518-526
  18. Philip S. Yu, Hans-Ulrich Heiss, Daniel M. Dias: Modeling and Analysis of a Time-Stamp History Based Certification Protocol for Concurrency Control. IEEE Trans. Knowl. Data Eng. 3(4): 525-537(1991)
  19. Mukesh Singhal: Analysis of the Probability of Transaction Abort and Throughput of Two Timestamp Ordering Algorithms for Database Systems. IEEE Trans. Knowl. Data Eng. 3(2): 261-266(1991)
  20. Michael J. Carey, Rajiv Jauhari, Miron Livny: On Transaction Boundaries in Active Databases: A Performance Perspective. IEEE Trans. Knowl. Data Eng. 3(3): 320-336(1991)
  21. Hans-Ulrich Heiss, Roger Wagner: Adaptive Load Control in Transaction Processing Systems. VLDB 1991: 47-54
  22. Alexander Thomasian: Performance Limits of Two-Phase Locking. ICDE 1991: 426-435
  23. Tadashi Ohmori, Masaru Kitsuregawa, Hidehiko Tanaka: Scheduling Batch Transactions on Shared-Nothing Parallel Database Machines: Effects of Concurrency and Parallelism. ICDE 1991: 210-219
  24. Axel Mönkeberg, Gerhard Weikum: Conflict-driven Load Control for the Avoidance of Data-Contention Thrashing. ICDE 1991: 632-639
  25. Pyung-Chul Kim, Hwan-Ik Choi, Yoon-Joon Lee, Myung-Joon Kim: Design and Implementation of the Multiuser Index-based Data Access System. DASFAA 1991: 156-164
  26. Bruno Ciciani, Daniel M. Dias, Philip S. Yu: Analysis of Replication in Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 2(2): 247-261(1990)
  27. Asit Dan, Daniel M. Dias, Philip S. Yu: The Effect of Skewed Data Access on Buffer Hits and Data Contention an a Data Sharing Environment. VLDB 1990: 419-431
  28. B. R. Badrinath, Krithi Ramamritham: Performance Evaluation of Semantics-based Multilevel Concurrency Control Protocols. SIGMOD Conference 1990: 163-172
  29. Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287
  30. Michael J. Carey, Sanjay Krishnamurthi, Miron Livny: Load Control for Locking: The 'Half-and-Half' Approach. PODS 1990: 72-84
  31. Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36
  32. Tadashi Ohmori, Masaru Kitsuregawa, Hidehiko Tanaka: Concurrency Control of Bulk Access Transactions on Shared Nothing Parallel Database Machines. ICDE 1990: 476-485
  33. Asit Dan, Daniel M. Dias, Philip S. Yu: Database Buffer Model for the Data Sharing Environment. ICDE 1990: 538-544
  34. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared-Nothing Parallel Database Machine. IEEE Trans. Knowl. Data Eng. 1(4): 530-543(1989)
  35. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared Nothing Parallel Database Machine. ICDE 1989: 149-158
  36. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  37. William Perrizo, Min Luo, Donald A. Varvel: Ordering Accesses to Improving Transaction Processing Performance. ICDE 1988: 58-63
  38. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
  39. Rong Sun, Gomer Thomas: Performance Results in Multiversion Timestamp Concurrency Control with Predeclared Writesets. PODS 1987: 177-184
  40. Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley: A Queueing Network Model for a Distributed Database Testbed System. ICDE 1987: 62-71
  41. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:58 2008