Locking Granularity Revisited.

@article{DBLP:journals/tods/RiesS79,
  author    = {Daniel R. Ries and
               Michael Stonebraker},
  title     = {Locking Granularity Revisited},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {2},
  year      = {1979},
  pages     = {210-227},
  ee        = {http://doi.acm.org/10.1145/320071.320078, db/journals/tods/RiesS79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Locking granularity refers to the size and hence the number of locks used to ensure the consistency of a database during multiple concurrent updates. In an earlier simulation study we concluded that coarse granularity, such as area or file locking, is to be preferred to fine granularity such as individual page or record locking.

However, alternate assumptions than those used in the original paper can change that conclusion. First, we modified the assumptions concerning the placement of the locks on the database with respect to the accessing transactions. In the original model the locks were assumed to be well placed. Under worse case and random placement assumptions when only very small transactions access the database, fine granularity is preferable.

Second, we extended the simulation to model a lock hierarchy where large transactions use large locks and small transactions use small locks. In this scenario, again under the random and worse case lock placement assumptions, fine granularity is preferable if all transactions accessing more than 1 percent of the database use large locks.

Finally, the simulation was extended to model a "claim as needed" locking strategy together with the resultant possibility of deadlock. In the original study all locks were claimed in one atomic operation at the beginning of a transaction. The claim as needed strategy does not change the conclusions concerning the desired granularity.

Copyright © 1979 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

References

[1]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX

[2]

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

[3]

...

[4]

Edward G. Coffman Jr., M. J. Elphick, Arie Shoshani: System Deadlocks. ACM Comput. Surv. 3(2): 67-78(1971) BibTeX

[5]

...

[6]

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

[7]

Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger: Granularity of Locks in a Large Shared Data Base. VLDB 1975: 428-451 BibTeX

[8]

...

[9]

...

[10]

...

[11]

Philip P. Macri: Deadlock Detection and Resolution in a CODASYL Based Data Management System. SIGMOD Conference 1976: 45-49 BibTeX

[12]

Rudolf Munz, G. Krenz: Concurrency in Database Systems - A Simulation Study. SIGMOD Conference 1977: 111-120 BibTeX

[13]

Daniel R. Ries, Michael Stonebraker: Effects of Locking Granularity in a Database Management System. ACM Trans. Database Syst. 2(3): 233-246(1977) BibTeX

[14]

...

[15]

...

[16]

Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

[17]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX

Referenced by

1. Vigyan Singhal, Alan Jay Smith: Analysis of Locking Behavior in Three Real Database Systems. VLDB J. 6(1): 40-52(1997)
2. Ming-Syan Chen, Philip S. Yu: Optimal Design of Multiple Hash Tables for Concurrency Control. IEEE Trans. Knowl. Data Eng. 9(3): 384-390(1997)
3. Suh-Yin Lee, Ruey-Long Liou: A Multi-Granularity Locking Model for Concurrency Control in Object-Oriented Database Systems. IEEE Trans. Knowl. Data Eng. 8(1): 144-156(1996)
4. Ming-Syan Chen, Philip S. Yu, Tao-Heng Yang: On Coupling Multiple Systems With A Global Buffer. IEEE Trans. Knowl. Data Eng. 8(2): 339-344(1996)
5. Edward Omiecinski, Liehuey Lee, Peter Scheuermann: Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering. IEEE Trans. Knowl. Data Eng. 6(2): 248-257(1994)
6. Omran A. Bukhres: Performance Comparisons of Distributed Deadlock Detection Algorithms. ICDE 1992: 210-217
7. Sivarama P. Dandamudi, Siu-Lun Au: Locking Granularity in Multiprocessor Database Systems. ICDE 1991: 268-277
8. Yin-Fu Huang, Yeh-Hao Chin: A New Methodology to Evaluate Locking Protocols. IEEE Trans. Knowl. Data Eng. 2(4): 431-435(1990)
9. Tobin J. Lehman, Bruce G. Lindsay: The Starburst Long Field Manager. VLDB 1989: 375-383
10. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
11. Edward Omiecinski: Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File. ICDE 1988: 589-596
12. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
13. Amit P. Sheth, Anoop Singhal, Ming T. Liu: Performance Analysis of Resiliency Mechanisms in Distributed Datbase Systems. ICDE 1987: 419-428
14. Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley: A Queueing Network Model for a Distributed Database Testbed System. ICDE 1987: 62-71
15. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
16. K. H. Pun, Geneva G. Belford: Optimal Granularity and Degree of Multiprogramming in a Distributed Database System. ICDE 1986: 13-20
17. Alle IJbema, Henk M. Blanken: Estimating Bucket Accesses: A Practical Approach. ICDE 1986: 30-37
18. John T. Robinson: A Fast General-Purpose Hardware Synchronisation Mechanism. SIGMOD Conference 1985: 122-130
19. Thomas W. Page Jr., Matthew J. Weinstein, Gerald J. Popek: Genesis: A Distributed Database Operating System. SIGMOD Conference 1985: 374-387
20. Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121
21. Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118
22. Haran Boral, David J. DeWitt: A Methodology for Database System Performance Evaluation. SIGMOD Conference 1984: 176-185
23. Peter Peinl, Andreas Reuter: Empirical Comparison of Database Concurrency Schemes. VLDB 1983: 97-108
24. Werner Kießling, G. Landherr: A Quantitative Comparison of Lockprotocols for Centralized Databases. VLDB 1983: 120-130
25. Walter H. Kohler, Kenneth C. Wilner, John A. Stankovic: An Experimental Comparison of Locking Policies in a Testbed Database System. SIGMOD Conference 1983: 108-119
26. Michael J. Carey: An Abstract Model of Database Concurrency Control Algorithms. SIGMOD Conference 1983: 97-107
27. Michael J. Carey: Granularity Hierarchies in Concurrency Control. PODS 1983: 156-165
28. Walter H. Kohler: A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems. ACM Comput. Surv. 13(2): 149-183(1981)
29. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
30. J. R. Jordan, J. Banerjee, R. B. Batman: Precision Locks. SIGMOD Conference 1981: 143-147
31. Michael Stonebraker: Retrospection on a Database System. ACM Trans. Database Syst. 5(2): 225-240(1980)