Concurrency Control for High Contention Environments.

@article{DBLP:journals/tods/FranaszekRT92,
  author    = {Peter A. Franaszek and
               John T. Robinson and
               Alexander Thomasian},
  title     = {Concurrency Control for High Contention Environments},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {2},
  year      = {1992},
  pages     = {304-345},
  ee        = {http://doi.acm.org/10.1145/128903.128906, db/journals/tods/FranaszekRT92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Future transaction processing systems may have substantially higher levels of concurrency due to reasons which include: (1) increasing disparity between processor speeds and data access latencies, (2) large numbers of processors, and (3) distributed databases. Another influence is the trend towards longer or more complex transactions. A possible consequence is substantially more data contention, which could limit total achievable throughput. In particular, it is known that the usual locking method of concurrency control is not well suited to environments where data contention is a significant factor.

Here we consider a number of concurrency control concepts and transaction scheduling techniques that are applicable to high contention environments, and that do not rely on database semantics to reduce contention. These include access invariance and its application to prefetching of data, approximations to essential blocking such as wait depth limited scheduling, and phase dependent control. The performance of various concurrency control methods based on these concepts are studied using detailed simulation models. The results indicate that the new techniques can offer substantial benefits for systems with high levels of data contention.

Copyright © 1992 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-2 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

Online Edition: ACM Digital Library

References

[1]

Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) 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]

Deborah DuBourdieux: Implementation of Distributed Transactions. Berkeley Workshop 1982: 81-94 BibTeX

[4]

Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985) BibTeX

[5]

Dieter Gawlick, David Kinkade: Varieties of Concurrency Control in IMS/VS Fast Path. IEEE Database Eng. Bull. 8(2): 3-10(1985) BibTeX

[6]

Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992) BibTeX

[7]

...

[8]

...

[9]

Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX

[10]

Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92 BibTeX

[11]

Andreas Reuter: The Transaction Pipeline Processor. HPTS 1985: 0- BibTeX

[12]

John T. Robinson: Design of Concurrency Controls for Transaction Processing Systems. Ph.D. thesis, Carnegie Mellon University 1982
BibTeX

[13]

In Kyung Ryu, Alexander Thomasian: Performance Analysis of Centralized Databases with Optimistic Concurrency Control. Perform. Eval. 7(3): 195-211(1987) BibTeX

[14]

In Kyung Ryu, Alexander Thomasian: Performance Analysis of Dynamic Locking with the No-Waiting Policy. IEEE Trans. Software Eng. 16(7): 684-698(1990) BibTeX

[15]

...

[16]

Alexander Thomasian: Performance Limits of Two-Phase Locking. ICDE 1991: 426-435 BibTeX

[17]

...

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. Alexander Thomasian: A Performance Comparison of Locking Methods with Limited Wait Depth. IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
5. Kjetil Nørvåg, Olav Sandstå, Kjell Bratbergsengen: Concurrency Control in Distributed Object-Oriented Database Systems. ADBIS 1997: 9-17
6. Alexander Thomasian: Checkpointing for Optimistic Concurrency Control Methods. IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
7. Alexander Thomasian: On a More Realistic Lock Contention Model and Its Analysis. ICDE 1994: 2-9
8. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
9. Alexander Thomasian: Thrashing in Two-Phase Locking Revisited. ICDE 1992: 518-526