Concurrency Control: Methods, Performance, and Analysis.
Alexander Thomasian:
Concurrency Control: Methods, Performance, and Analysis.
ACM Comput. Surv. 30(1): 70-119(1998)@article{DBLP:journals/csur/Thomasian98,
author = {Alexander Thomasian},
title = {Concurrency Control: Methods, Performance, and Analysis},
journal = {ACM Comput. Surv.},
volume = {30},
number = {1},
year = {1998},
pages = {70-119},
ee = {db/journals/csur/Thomasian98.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Standard locking (two-phase locking with on-demand lock requests and blocking
upon lock conflict) is the primary concurrency control (CC) method for centralized
databases. The main source of performance degradation with standard locking is
blocking, whereas transaction (txn) restarts to resolve deadlocks have a secondary
effect on performance. We provide a performance analysis of standard locking that
accurately estimates its performance degradation leading to thrashing. We next
introduce two sets of methods to cope with its performance limitations. Restart-oriented
locking methods selectively abort txns to increase the level of concurrency
for active txns with respect to standard locking in high-contention environments.
For example, the running-priority method aborts blocked txns based on the
essential blocking principle, which only allows blocking by active txns.
The wait-depth-limited (WDL) method further minimizes wasted processing by basing abort
decisions on the progress made by a txn. Restart waiting serves as a load-control
mechanism by deferring the restart of an aborted txn until conflicting txns have
left the system. These two methods have performance superior to other restart-oriented
methods and standard locking in high-contention environments. In two-phase
processing methods an aborted txn may continue its first phase of execution
in "virtual" mode, that is, without requesting any locks, prefetching data for its
second execution phase. The second execution phase is shorter since no disk I/O is
required, resulting in a lower effective degree of txn concurrency and less data
contention. This method is effective provided access invariance prevails; that is,
txns access the same set of objects in the second phase as they did in the first. The
optimistic die method is appropriate for the first phase and the optimistic kill
method for further phases. Lock preclaiming instead of the optimistic kill method
in the second phase prevents further restarts, which is a weak point of the
optimistic CC method due to the quadratic effect, that is, the probability of failed
validation increases as the square of txn size. Several two-phase processing
methods are described and shown to outperform restart-oriented locking methods
in high-contention environments provided adequate hardware resources are
available. This tutorial reviews CC methods based on standard locking, restart-oriented
locking methods, two-phase processing methods including optimistic CC,
and hybrid methods (combining optimistic CC and locking) in centralized
systems.
Its main goals are as follows: (i) succinctly specify CC methods of interest; (ii)
describe models for performance evaluation of CC methods, including new models
that alleviate some of the shortcomings of models used in earlier studies; (iii)
compare the performance of CC methods; (iv) list insights gained from analytic and
simulation studies; (v) review methods to relieve the level of lock contention:
special methods for indices and aggregate data; modified txn structures; and
relaxed levels of consistency for queries; (vi) survey performance evaluation studies
of CC methods; (vii) illustrate the applicability of basic analytic methods to
evaluating the performance of CC methods; and (viii) suggest areas of further
investigation.
Copyright © 1998 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.
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
Citation Page
References
- [Agrawal et al. 1994]
- Divyakant Agrawal, Amr El Abbadi, A. E. Lang:
The Performance of Protocols Based on Locks with Ordered Sharing.
IEEE Trans. Knowl. Data Eng. 6(5): 805-818(1994)
- [Agrawal etal. 1987a]
- Rakesh Agrawal, Michael J. Carey, Miron Livny:
Concurrency Control Performance Modeling: Alternatives and Implications.
ACM Trans. Database Syst. 12(4): 609-654(1987)
- [Agrawal e tal. 1987b]
- Rakesh Agrawal, Michael J. Carey, Lawrence W. McVoy:
The Performance of Alternative Strategies for Dealing with Deadlocks in Database Management Systems.
IEEE Trans. Software Eng. 13(12): 1348-1363(1987)
- [Ammann eta l. 1997]
- Paul Ammann, Sushil Jajodia, Indrakshi Ray:
Applying Formal Methods to Semantic-Based Decomposition of Transactions.
ACM Trans. Database Syst. 22(2): 215-254(1997)
- [Badrinath and Ramamithram 1992]
- B. R. Badrinath, Krithi Ramamritham:
Semantics-Based Concurrency Control: Beyond Commutativity.
ACM Trans. Database Syst. 17(1): 163-199(1992)
- [Barghouti and Kaiser 1991]
- Naser S. Barghouti, Gail E. Kaiser:
Concurrency Control in Advanced Database Applications.
ACM Comput. Surv. 23(3): 269-317(1991)
- [Bayer 1986]
- Rudolf Bayer:
Consistency of Transactions and Random Batch.
ACM Trans. Database Syst. 11(4): 397-404(1986)
- [Bernstein and Goodman 1981]
- Philip A. Bernstein, Nathan Goodman:
Concurrency Control in Distributed Database Systems.
ACM Comput. Surv. 13(2): 185-221(1981)
- [Bernstein et al. 1987]
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents - [Bestavros and Braoudakis 1995]
- Azer Bestavros, Spyridon Braoudakis:
Value-cognizant Speculative Concurrency Control.
VLDB 1995: 122-133
- [Bober and Carey 1992]
- Paul M. Bober, Michael J. Carey:
On Mixing Queries and Transactions via Multiversion Locking.
ICDE 1992: 535-545
- [Boksenbaum et al. 1987]
- Claude Boksenbaum, Michèle Cart, Jean Ferrié, Jean-François Pons:
Concurrent Certifications by Intervals of Timestamps in Distributed Database Systems.
IEEE Trans. Software Eng. 13(4): 409-419(1987)
- [Breitbart et al. 1987]
- Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz:
Overview of Multidatabase Transaction Management.
VLDB J. 1(2): 181-239(1992)
- [Burger and Thanisch 1994]
- Albert Burger, Peter Thanisch:
Branching Transactions: A Transaction Model for Parallel Database Systems.
BNCOD 1994: 121-136
- [Carey and Livny ]
- Michael J. Carey, Miron Livny:
Conflict Detection Tradeoffs for Replicated Data.
ACM Trans. Database Syst. 16(4): 703-746(1991)
- [Carey et al. 1991a]
- 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)
- [Carey et al. 1991b]
- Michael J. Carey, Michael J. Franklin, Miron Livny, Eugene J. Shekita:
Data Caching Tradeoffs in Client-Server DBMS Architectures.
SIGMOD Conference 1991: 357-366
- [Cellary et al. 1988]
- ...
- [Ceri and Pelagatti 1984]
- Stefano Ceri, Giuseppe Pelagatti:
Distributed Databases: Principles and Systems.
McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
- [Chesnais et al. 1983]
- A. Chesnais, Erol Gelenbe, Isi Mitrani:
On the Modeling of Parallel Access to Shared Data.
Commun. ACM 26(3): 196-202(1983)
- [Date 1983]
- C. J. Date:
An Introduction to Database Systems, Volume II.
Addison-Wesley 1983, ISBN 0-201-14474-3
- [Elmagarmid 1992]
- Ahmed K. Elmagarmid (Ed.):
Database Transaction Models for Advanced Applications.
Morgan Kaufmann 1992, ISBN 1-55860-214-3
Contents - [Farrag and Ozsu 1989]
- Abdel Aziz Farrag, M. Tamer Özsu:
Using Semantic Knowledge of Transactions to Increase Concurrency.
ACM Trans. Database Syst. 14(4): 503-525(1989)
- [Franaszek and Robinson 1985]
- Peter A. Franaszek, John T. Robinson:
Limitations of Concurrency in Transaction Processing.
ACM Trans. Database Syst. 10(1): 1-28(1985)
- [Franaszek et al. 1993]
- ...
- [Franaszek et al. 1990]
- Peter A. Franaszek, John T. Robinson, Alexander Thomasian:
Access Invariance and Its Use in High Contention Environments.
ICDE 1990: 47-55
- [Franaszek et al. 1991a]
- ...
- [Franaszek et al. 1991b]
- ...
- [Franaszek et al. 1992]
- Peter A. Franaszek, John T. Robinson, Alexander Thomasian:
Concurrency Control for High Contention Environments.
ACM Trans. Database Syst. 17(2): 304-345(1992)
- [Galler and Bos 1983]
- ...
- [Garcia-Molina 1983]
- Hector Garcia-Molina:
Using Semantic Knowledge for Transaction Processing in Distributed Database.
ACM Trans. Database Syst. 8(2): 186-213(1983)
- [Garcia-Molina and Salem 1987]
- Hector Garcia-Molina, Kenneth Salem:
Sagas.
SIGMOD Conference 1987: 249-259
- [Gray 1993]
- Jim Gray (Ed.):
The Benchmark Handbook for Database and Transaction Systems (2nd Edition).
Morgan Kaufmann 1993, ISBN 1-55860-292-5
Contents - [Gray and Reuter 1992]
- Jim Gray, Andreas Reuter:
Transaction Processing: Concepts and Techniques.
Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents - [Haerder 1984]
- Theo Härder:
Observations on optimistic concurrency control schemes.
Inf. Syst. 9(2): 111-120(1984)
- [Harder and Rothermel 1993]
- Theo Härder, Kurt Rothermel:
Concurrency Control Issues in Nested Transactions.
VLDB J. 2(1): 39-74(1993)
- [Hsu and Zhang 1992]
- Meichun Hsu, Bin Zhang:
Performance Evaluation of Cautious Waiting.
ACM Trans. Database Syst. 17(3): 477-512(1992)
- [Hsu and Zhang 1995]
- ...
- [Huang et al. 1991]
- Jiandong Huang, John A. Stankovic, Krithi Ramamritham, Donald F. Towsley:
Experimental Evaluation of Real-Time Optimistic Concurrency Control Schemes.
VLDB 1991: 35-46
- [Irani and Lin 1979]
- Keki B. Irani, Hing-Lung Lin:
Queuing Network Models for Concurrent Transaction Processing in a Database System.
SIGMOD Conference 1979: 134-142
- [Jagadish and Shmueli 1992]
- H. V. Jagadish, Oded Shmueli:
Proclamation-Based Model for Cooperating Transactions.
VLDB 1992: 265-276
- [Jenq et al. 1989]
- 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)
- [Johnson and Shasha 1993]
- Theodore Johnson, Dennis Shasha:
The Performance of Current B-Tree Algorithms.
ACM Trans. Database Syst. 18(1): 51-101(1993)
- [Khoshafian and Buckiewicz 1995]
- ...
- [Kleinrock 1975]
- ...
- [Korth and Speegle 1994]
- Henry F. Korth, Gregory D. Speegle:
Formal Aspects of Concurrency Control in Long-Duration Transaction Systems Using the NT/PV Model.
ACM Trans. Database Syst. 19(3): 492-535(1994)
- [Krishnakumar and Bernstein 1994]
- Narayanan Krishnakumar, Arthur J. Bernstein:
Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System.
ACM Trans. Database Syst. 19(4): 586-625(1994)
- [Kumar 1995]
- ...
- [Kung and Robinson 1981]
- H. T. Kung, John T. Robinson:
On Optimistic Methods for Concurrency Control.
ACM Trans. Database Syst. 6(2): 213-226(1981)
- [Langer and Shum 1982]
- A. M. Langer, Annie W. Shum:
The Distribution of Granule Accesses Made by Database Transactions.
Commun. ACM 25(11): 831-832(1982)
- [Lazowska et al. 1984]
- ...
- [Li and Naughton 1988]
- Kai Li, Jeffrey F. Naughton:
Multiprocessor Main Memory Transaction Processing.
DPDS 1988: 177-187
- [Lynch et al. 1994]
- Nancy A. Lynch, Michael Merritt, William E. Weihl, Alan Fekete:
Atomic Transactions.
Morgan Kaufmann 1993, ISBN 1-55860-104-X
- [Massey 1986]
- William A. Massey:
A Probabilistic Analysis of a Database System.
SIGMETRICS 1986: 141-146
- [Mehrotra et al. 1997]
- Sharad Mehrotra, Henry F. Korth, Abraham Silberschatz:
Concurrency Control in Hierarchical Multidatabase Systems.
VLDB J. 6(2): 152-172(1997)
- [Menasce and Nakanishi 1982]
- Daniel A. Menascé, Tatuo Nakanishi:
Optimistic versus pessimistic concurrency control mechanisms in database management systems.
Inf. Syst. 7(1): 13-27(1982)
- [Moenkeberg and Weikum 1992]
- 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
- [Mohan 1992]
- C. Mohan:
Less Optimism About Optimistic Concurrency Control.
RIDE-TQP 1992: 199-204
- [Mohan and Levine 1992]
- C. Mohan, Frank E. Levine:
ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging.
SIGMOD Conference 1992: 371-380
- [Mohan et al. 1992a]
- C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz:
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.
ACM Trans. Database Syst. 17(1): 94-162(1992)
- [Mohan et al. 1992b]
- C. Mohan, Hamid Pirahesh, Raymond A. Lorie:
Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions.
SIGMOD Conference 1992: 124-133
- [Montgomery 1978]
- ...
- [Morris and Wong 1985]
- Robert J. T. Morris, Wing Shing Wong:
Performance Analysis of Locking and Optimistic Concurrency Control Algorithms.
Perform. Eval. 5(2): 105-118(1985)
- [Moss 1985]
- ...
- [O'Neil 1986]
- Patrick E. O'Neil:
The Escrow Transactional Method.
ACM Trans. Database Syst. 11(4): 405-430(1986)
- [O'Neil et al. 1995]
- ...
- [Ozsu 1994]
- M. Tamer Özsu:
Transaction Models and Transaction Management in Object-Oriented Database Management Systems.
NATO ASI OODBS 1993: 147-184
- [Peinl et al. 1988]
- Peter Peinl, Andreas Reuter, Harald Sammer:
High Contention in a Stock Trading Database: A Case Study.
SIGMOD Conference 1988: 260-268
- [Potier and LeBlanc 1980]
- Dominique Potier, Ph. Leblanc:
Analysis of Locking Policies in Database Management Systems.
Commun. ACM 23(10): 584-593(1980)
- [Pu and Leff 1991]
- Calton Pu, Avraham Leff:
Replica Control in Distributed Systems: An Asynchronous Approach.
SIGMOD Conference 1991: 377-386
- [Rahm 1993]
- Erhard Rahm:
Empirical Performance Evaluation of Concurrency and Coherency Control Protocols for Database Sharing Systems.
ACM Trans. Database Syst. 18(2): 333-377(1993)
- [Ramamritham 1993]
- Krithi Ramamritham:
Real-Time Databases.
Distributed and Parallel Databases 1(2): 199-226(1993)
- [Ramamritham and Chrisanthis 1996]
- ...
- [Reuter 1985]
- Andreas Reuter:
The Transaction Pipeline Processor.
HPTS 1985: 0-
- [Robinson 1982a]
- John T. Robinson:
Design of Concurrency Controls for Transaction Processing Systems.
Ph.D. thesis, Carnegie Mellon University 1982
- [Robinson 1982b]
- ...
- [Robinson 1984]
- John T. Robinson:
Separating Policy from Correctness in Concurrency Control Design.
Softw., Pract. Exper. 14(9): 827-844(1984)
- [Rosenkrantz et al. 1978]
- 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)
- [Ryu and Thomasian 1987]
- In Kyung Ryu, Alexander Thomasian:
Performance Analysis of Centralized Databases with Optimistic Concurrency Control.
Perform. Eval. 7(3): 195-211(1987)
- [Ryu and Thomasian 1988]
- ...
- [Ryu and Thomasian 1990a]
- In Kyung Ryu, Alexander Thomasian:
Analysis of Database Performance with Dynamic Locking.
J. ACM 37(3): 491-523(1990)
- [Ryu and Thomasian 1990b]
- In Kyung Ryu, Alexander Thomasian:
Performance Analysis of Dynamic Locking with the No-Waiting Policy.
IEEE Trans. Software Eng. 16(7): 684-698(1990)
- [Salem et al. 1994]
- Kenneth Salem, Hector Garcia-Molina, Jeannie Shands:
Altruistic Locking.
ACM Trans. Database Syst. 19(1): 117-165(1994)
- [Samaras et al. 1995]
- George Samaras, Kathryn Britton, Andrew Citron, C. Mohan:
Two-Phase Commit Optimizations in a Commercial Distributed Environment.
Distributed and Parallel Databases 3(4): 325-360(1995)
- [Shasha et al. 1995]
- Dennis Shasha, François Llirbat, Eric Simon, Patrick Valduriez:
Transaction Chopping: Algorithms and Performance Studies.
ACM Trans. Database Syst. 20(3): 325-363(1995)
- [Singhal 1991]
- Mukesh Singhal:
Performance Analysis of the Basic Timestamp Ordering Algorithm via Markov Modeling.
Perform. Eval. 12(1): 17-41(1991)
- [Singhal and Smith 1997]
- Vigyan Singhal, Alan Jay Smith:
Analysis of Locking Behavior in Three Real Database Systems.
VLDB J. 6(1): 40-52(1997)
- [Skarra and Zdonik 1989]
- Andrea H. Skarra, Stanley B. Zdonik:
Concurrency Control and Object-Oriented Databases.
Object-Oriented Concepts, Databases, and Applications 1989: 395-421
- [Srinivasan and Carey 1993]
- V. Srinivasan, Michael J. Carey:
Performance of B+ Tree Concurrency Algorithms.
VLDB J. 2(4): 361-406(1993)
- [Tay 1987]
- ...
- [Tay 1990]
- ...
- [Tay et al. 1985a]
- Y. C. Tay, Nathan Goodman, Rajan Suri:
Locking Performance in Centralized Databases.
ACM Trans. Database Syst. 10(4): 415-462(1985)
- [Tay et al. 1985b]
- 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)
- [Thomasian 1982]
- ...
- [Thomasian 1985]
- Alexander Thomasian:
Performance Evaluation of Centralized Databases with Static Locking.
IEEE Trans. Software Eng. 11(4): 346-355(1985)
- [Thomasian 1992]
- Alexander Thomasian:
Performance of Locking Policies with Limited Wait Depth.
SIGMETRICS 1992: 115-127
- [Thomasian 1993]
- Alexander Thomasian:
Two-Phase Locking Performance and Its Thrashing Behavior.
ACM Trans. Database Syst. 18(4): 579-625(1993)
- [Thomasian 1994]
- Alexander Thomasian:
Fractional Data Allocation Method for Distributed Databases.
PDIS 1994: 168-175
- [Thomasian 1995a]
- Alexander Thomasian:
Performance Analysis of Locking Methods with Limited Wait Depth.
Perform. Eval. 34(2): 69-89(1998)
- [Thomasian 1995b]
- Alexander Thomasian:
Checkpointing for Optimistic Concurrency Control Methods.
IEEE Trans. Knowl. Data Eng. 7(2): 332-339(1995)
- [Thomasian 1996a]
- ...
- [Thomasian 1996b]
- Alexander Thomasian:
A More Realistic Locking Model and its Analysis.
Inf. Syst. 21(5): 409-430(1996)
- [Thomasian 1997]
- Alexander Thomasian:
A Performance Comparison of Locking Methods with Limited Wait Depth.
IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
- [Thomasian 1998]
- Alexander Thomasian:
Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing.
IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
- [Thomasian and Nicola 1993]
- Alexander Thomasian, Victor F. Nicola:
Performance Evaluation of a Threshold Policy for Scheduling Readers and Writers.
IEEE Trans. Computers 42(1): 83-98(1993)
- [Thomasian and Rahm 1990]
- ...
- [Thomasian and Ryu 1983]
- ...
- [Thomasian and Ryu 1986]
- ...
- [Thomasian and Ryu 1989]
- Alexander Thomasian, In Kyung Ryu:
A Recursive Solution Method to Analyze the Performance of Static Locking Systems.
IEEE Trans. Software Eng. 15(10): 1147-1156(1989)
- [Thomasian and Ryu 1991]
- Alexander Thomasian, In Kyung Ryu:
Performance Analysis of Two-Phase Locking.
IEEE Trans. Software Eng. 17(5): 386-402(1991)
- [Weihl 1988]
- William E. Weihl:
Commutativity-Based Concurrency Control for Abstract Data Types.
IEEE Trans. Computers 37(12): 1488-1505(1988)
- [Weikum 1991]
- Gerhard Weikum:
Principles and Realization Strategies of Multilevel Transaction Management.
ACM Trans. Database Syst. 16(1): 132-180(1991)
- [Weikum et al. 1994]
- Gerhard Weikum, Christof Hasse, Alex Moenkeberg, Peter Zabback:
The COMFORT Automatic Tuning Project, Invited Project Review.
Inf. Syst. 19(5): 381-432(1994)
- [Yu et al. 1993]
- Philip S. Yu, Daniel M. Dias, Stephen S. Lavenberg:
On the Analytical Modeling of Database Concurrency Control.
J. ACM 40(4): 831-872(1993)
Copyright © Wed Dec 9 20:20:34 2009
by Michael Ley (ley@uni-trier.de)
