Locking Performance in Centralized Databases.

@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}
}

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Conference Versions of this Paper

• Y. C. Tay, Rajan Suri, Nathan Goodman: A Mean Value Performance Model for Locking in Databases: The Waiting Case. PODS 1984: 311-322 BibTeX
• Y. C. Tay, Rajan Suri: Choice and Performance in Locking for Databases. VLDB 1984: 119-128 BibTeX

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