An Adaptable Constrained Locking Protocol for High Data Contention Environments.

@inproceedings{DBLP:conf/dasfaa/GoelBM99,
  author    = {Shalab Goel and
               Bharat K. Bhargava and
               Sanjay Kumar Madria},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {An Adaptable Constrained Locking Protocol for High Data Contention
               Environments},
  booktitle = {Database Systems for Advanced Applications, Proceedings of the
               Sixth International Conference on Database Systems for Advanced
               Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
  publisher = {IEEE Computer Society},
  year      = {1999},
  isbn      = {0-7695-0084-6},
  pages     = {321-328},
  ee        = {db/conf/dasfaa/GoelBM99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Multiversions of data are used in database systems to increase concurrency and to provide efficient recovery. Data versions improves the concurrency by allowing the concurrent execution of "non-conflicting" read-write lock requests on different versions of data in an arbitrary fashion. A transaction that accesses a data item version which is later diagnosed to lead to an incorrect execution, is aborted. This act is reminiscent of the validation phase in the optimistic concurrency control schemes. Various performance studies suggest that these schemes perform poorly in high data contention environments where the excessive transaction aborts result due to the failed validation.

We propose an adaptable constrained two-version two-phase locking (C2V2PL) scheme in which these "non-conflicting" requests are allowed only in a constrained manner. C2V2PL schemes assumes that a lock request failing to satisfy the specific constraints will lead to an incorrect execution and hence, must be either rejected or blocked. This eliminates the need for a separate validation phase. When the contention for data among the concurrent transactions is high, the C2V2PL scheduler in aggressive state rejects such lock requests. The deadlock free nature of C2V2PL scheduler adapts to the low data contention environments by accepting the lock request that have failed the specific constraints but contrary to the assumption, will not lead to an incorrect execution. Thus improving the performance due to reduced transaction aborts in this conservative state.

Copyright © 1999 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD DiSC

• 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/DISC001 or /cdrom

ACM SIGMOD 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 DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Online Edition: IEEE Computer Society 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)

[2]

Divyakant Agrawal, Soumitra Sengupta: Modular Synchronization in Multiversion Databases: versionControl and Concurrency Control. SIGMOD Conference 1989: 408-417

[3]

Paul M. Bober, Michael J. Carey: On Mixing Queries and Transactions via Multiversion Locking. ICDE 1992: 535-545

[4]

Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983)

[5]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents

[6]

Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980)

[7]

Arvola Chan, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: The Implementation of an Integrated Concurrency Control and Recovery Scheme. SIGMOD Conference 1982: 184-191

[8]

Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Concurrency Control for High Contention Environments. ACM Trans. Database Syst. 17(2): 304-345(1992)

[9]

Peter C. J. Graham, Ken Barker: Effective Optimistic Concurrency Control in Multiversion Object Bases. ISOOMS 1994: 313-328

[10]

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

[11]

...

[12]

Sanjay Kumar Madria, Bharat K. Bhargava: System Defined Prewrites for Increasing Concurrency in Databases. ADBIS 1997: 18-22

[13]

Sanjay Kumar Madria, Bharat K. Bhargava: On the Correctness of a Transaction Model for Mobile Computing. DEXA 1998: 573-583

[14]

Peter Peinl, Andreas Reuter, Harald Sammer: High Contention in a Stock Trading Database: A Case Study. SIGMOD Conference 1988: 260-268

[15]

Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83

[16]

Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985)

[17]

Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993)

[18]

William E. Weihl: Distributed Version Management for Read-Only Actions. IEEE Trans. Software Eng. 13(1): 55-64(1987)