Limitations of Concurrency in Transaction Processing.

@article{DBLP:journals/tods/FranaszekR85,
  author    = {Peter A. Franaszek and
               John T. Robinson},
  title     = {Limitations of Concurrency in Transaction Processing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {1},
  year      = {1985},
  pages     = {1-28},
  ee        = {http://doi.acm.org/10.1145/3148.3160, db/journals/tods/FranaszekR85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Given the pairwise probability of conflict p among transactions in a transaction processing system, together with the total number of concurrent transactions n, the effective level of concurrency E(n,p) is defined as the expected number of the n transactions that can run concurrently and actually do useful work. Using a random graph model of concurrency, we show for three general classes of concurrency control methods, examples of which are (1) standard locking, (2) strict priority scheduling, and (3) optimistic methods, that (1) E(n, p) <= n(1 - p/2)^n-1, (2) E(n, p) <= (1 - (1 - p)ⁿ)/p, and (3) 1 + ((1 - p)/p)ln(p(n - 1) + 1) <= E(n, p) <= 1 + (l/p)ln(p(n - 1) + 1). Thus, for fixed p, as n -> infinity, (1) E -> 0 for standard locking methods, (2) E <= 1/p for strict priority scheduling methods, and (3) E -> infinity for optimistic methods. Also found are bounds on E in the case where conflicts are analyzed so as to maximize E.

The predictions of the random graph model are confirmed by simulations of an abstract transaction processing system. In practice, though, there is a price to pay for the increased effective level of concurrency of methods (2) and (3): using these methods there is more wasted work (i.e., more steps executed by transactions that are later aborted). In response to this problem, three new concurrency control methods suggested by the random graph model analysis are developed. Two of these, called (a) running priority and (b) older or running priority, are shown by the simulation results to perform better than the previously known methods (1)-(3) for relatively large n or large p, in terms of achieving a high effective level of concurrency at a comparatively small cost in wasted work.

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

References

[1]

Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985) BibTeX

[2]

Michael J. Carey: Modeling and Evaluation of Database Concurrency Control Algorithms. Ph.D. thesis, College of Engineering, University of California, Berkeley 1983
BibTeX

[3]

...

[4]

...

[5]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[6]

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX

[7]

A. M. Langer, Annie W. Shum: The Distribution of Granule Accesses Made by Database Transactions. Commun. ACM 25(11): 831-832(1982) BibTeX

[8]

Chin-Hwa Lee: Queueing Analysis of Global Locking Synchronization Schemes for Multicopy Databases. IEEE Trans. Computers 29(5): 371-384(1980) BibTeX

[9]

Wen-Te K. Lin: Performance Evaluation of Two Concurrency Control Mechanisms in a Distributed Database System. SIGMOD Conference 1981: 84-92 BibTeX

[10]

David B. Lomet: Process Structuring, Synchronization, and Recovery Using Atomic Actions. Language Design for Reliable Software 1977: 128-137 BibTeX

[11]

Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX

[12]

...

[13]

Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX

[14]

...

Referenced by

1. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
2. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
3. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control Algorithms for Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
4. Alexander Thomasian: A Performance Comparison of Locking Methods with Limited Wait Depth. IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
5. Alexander Thomasian: Checkpointing for Optimistic Concurrency Control Methods. IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
6. Alexander Thomasian: On a More Realistic Lock Contention Model and Its Analysis. ICDE 1994: 2-9
7. V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
8. Jayant R. Haritsa, Michael J. Carey, Miron Livny: Value-Based Scheduling in Real-Time Database Systems. VLDB J. 2(2): 117-152(1993)
9. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
10. Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992)
11. Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Concurrency Control for High Contention Environments. ACM Trans. Database Syst. 17(2): 304-345(1992)
12. 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
13. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: An Approach to Eliminate Transaction Blocking in Locking Protocols. PODS 1992: 223-235
14. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control for Epsilon-Serializability. ICDE 1992: 506-515
15. Alexander Thomasian: Thrashing in Two-Phase Locking Revisited. ICDE 1992: 518-526
16. 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)
17. Hans-Ulrich Heiss, Roger Wagner: Adaptive Load Control in Transaction Processing Systems. VLDB 1991: 47-54
18. Wei-hsing Wang, Eugene Pinsky, Meichun Hsu: Modeling Hot Spots In Database Systems. PODS 1991: 82-91
19. Alexander Thomasian: Performance Limits of Two-Phase Locking. ICDE 1991: 426-435
20. Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Wait Depth Limited Concurrency Control. ICDE 1991: 92-101
21. Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990)
22. Michael J. Carey, Sanjay Krishnamurthi, Miron Livny: Load Control for Locking: The 'Half-and-Half' Approach. PODS 1990: 72-84
23. Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36
24. Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Access Invariance and Its Use in High Contention Environments. ICDE 1990: 47-55
25. Alok N. Choudhary: Cost of Distributed Deadlock Detection: A Performance Study. ICDE 1990: 174-181
26. Lubomir Bic, Robert L. Hartmann: AGM: A Dataflow Database Machine. ACM Trans. Database Syst. 14(1): 114-146(1989)
27. 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)
28. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared Nothing Parallel Database Machine. ICDE 1989: 149-158
29. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
30. Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987)
31. Jerre D. Noe, David B. Wagner: Measured Performance of Time Interval Concurrency Control Techniques. VLDB 1987: 359-367
32. Akhil Kumar, Michael Stonebraker: Performance Evaluation of an Operating System Transaction Manager. VLDB 1987: 473-481
33. Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley: A Queueing Network Model for a Distributed Database Testbed System. ICDE 1987: 62-71
34. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
35. Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121