Quasi-dynamic two-phase locking

ABSTRACT

Among the plethora of concurrency control algorithms that have been proposed and analyzed, two-phase locking (2PL) has been adapted as the industry de facto standard concurrency control. In accord, current research in concurrency control is focusing on enhancing the scalability of 2PL performance in highly concurrent and contentious environments. This is especially needed in future on-line transaction processing systems, where thousand Transaction Per Second performance will be required.Static locking (SL) and dynamic locking (DL) are two famous adaptations of 2PL that are used under different degrees of data contention. In this paper, we offer our observation that 2PL is indeed a family of methods, of which SL and DL are extreme case members. Further, we argue for and verify the existence of other 2PL member methods that, under variable conditions, outperform SL and DL. We propose two novel schemes which we categorize as quasi-dynamic two-phase locking on account of their behavior in comparison with dynamic/static two-phase locking. We present a simulation study of the performance of the proposed schemes and their comparison to dynamic and static locking methods.

REFERENCES

• 1: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 2: Rakesh Agrawal , Michael J. Carey , David J. DeWitt, Deadlock detection is cheap, ACM SIGMOD Record, v.13 n.2, p.19-34, January 1983 [doi>10.1145/984523.984524]
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 5: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 6: Peter A. Franaszek , John T. Robinson , Alexander Thomasian, Concurrency control for high contention environments, ACM Transactions on Database Systems (TODS), v.17 n.2, p.304-345, June 1992 [doi>10.1145/128903.128906]
• 7: Abdelsalam Helal , Tung-Hui Ku , Ramez Elmasri , Sourav Mukherjee, Adaptive transaction scheduling, Proceedings of the second international conference on Information and knowledge management, p.704-713, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170462]
• 8: Meichun Hsu , Bin Zhang, Performance evaluation of cautious waiting, ACM Transactions on Database Systems (TODS), v.17 n.3, p.477-512, Sept. 1992 [doi>10.1145/132271.132275]
• 9: S. Kawazu, I. S. Minami, and K. Teranaka. Two-phase deadlock detection algorithm in distributed databases. In Proceedings of the Int'l Conf.~ on Very Large Data Bases (IEEE), New York, 1979.
• 10: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 11: R. J. Ramirez and N. Santoro. Distributed control of updates in multiple-copy data bases: A time optimal algorithm, in Proc. tth Berkeley Workshop Distributed Data Management and Computer Networks, august 1979.
• 12: Daniel R. Ries , Michael Stonebraker, Effects of locking granularity in a database management system, ACM Transactions on Database Systems (TODS), v.2 n.3, p.233-246, Sept. 1977 [doi>10.1145/320557.320566]
• 13: Daniel R. Ries , Michael R. Stonebraker, Locking granularity revisited, ACM Transactions on Database Systems (TODS), v.4 n.2, p.210-227, June 1979 [doi>10.1145/320071.320078]
• 14: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]
• 15: In Kyung Ryu , Alexander Thomasian, Performance Analysis of Dynamic Locking with the No-Waiting Policy, IEEE Transactions on Software Engineering, v.16 n.7, p.684-698, July 1990 [doi>10.1109/32.56095]
• 16: Amit P. Sheth and Ming T. Liu. integrating locking and optimistic concurrency control in distributed database systems. In Proceedings of the 6th International Conference on Distributed Computing Systems, May 1986.
• 17: Alexander Thomasian , In Kyung Ryu, A decomposition solution to the queueing network model of the centralized DBMS with static locking, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.82-92, August 29-31, 1983, Minneapolis, Minnesota, United States [doi>10.1145/800040.801397]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
adaptability, data contention, pre-declaration, resource contention, two-phase locking