Locking performance in centralized databases

ABSTRACT

An analytic model is used to study the performance of dynamic locking. The analysis uses only the steady-state average values of the variables. The solution to the model is given by a cubic, which has exactly one valid root for the range of parametric values that is of interest. The model's predictions agree well with simulation results for transactions that require up to twenty locks. The model separates data contention from resource contention, thus facilitating an analysis of their separate effects and their interaction. It shows that systems with a particular form of nonuniform access, or with shared locks, are equivalent to systems with uniform access and only exclusive locks. Blocking due to conflicts is found to impose an upper bound on transaction throughput; this fact leads to a rule of thumb on how much data contention should be permitted in a system. Throughput can exceed this bound if a transaction is restarted whenever it encounters a conflict, provided restart costs and resource contention are low. It can also be exceeded by making transactions predeclare their locks. Raising the multiprogramming level to increase throughput also raises the number of restarts per completion. Transactions should minimize their lock requests, because data contention is proportional to the square of the number of requests. The choice of how much data to lock at a time depends on which part of a general granularity curve the system sees.

REFERENCES

• 1: Rakesh Agrawal , Michael J. Carey , Miron Livny, Models for studying concurrency control performance: alternatives and implications, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.108-121, May 1985, Austin, Texas, United States
• 2: R. Balter , P. Berard , P. Decitre, Why control of the concurrency level in distributed systems is more fundamental than deadlock management, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.183-193, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806696]
• 3: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 4: BEERI, C., AND OBERMARCK, R. A resource class independent deadlock detection algorithm. In Proceedings of the International Conference on Very Large Data Bases (Cannes, France, Sept. 1981), pp. 166-178.
• 5: 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]
• 6: Michael James Carey, Modeling and evaluation of database concurrency control algorithms, 1983
• 7: Michael J. Carey , Michael Stonebraker, The Performance of Concurrency Control Algorithms for Database Management Systems, Proceedings of the 10th International Conference on Very Large Data Bases, p.107-118, August 27-31, 1984
• 8: CHAMBERLIN, D. D., BO~CE, R. F., AND TRAIGER, I.L. A deadlock-free scheme for resource allocation in a database environment. In Info. Proc. 74, North-Holland, Amsterdam, 1974, 340-343.
• 9: A. Chesnais , E. Gelenbe , I. Mitrani, On the modeling of parallel access to shared data, Communications of the ACM, v.26 n.3, p.196-202, March 1983 [doi>10.1145/358061.358073]
• 10: Joao Eduardo De Rezende Dantas, Performance analysis of distributed database systems, 1980
• 11: Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
• 12: DENNING, P. J., KAHN, K. C., LEROUDIER, J., POTIER, D., AND SURI, R. Optimal multiprogramming. Acta In}:. 7, 2 (1976), 197-216.
• 13: DEVOR, C., AND CARLSON, C.a. Structural locking mechanisms and their effect on database management system performance. Inf. Syst. 7, 4 (1982), 345-358.
• 14: 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]
• 15: GALLER, B. I., AND BOS, L. A model of transaction blocking in databases. Performance Eval. 3 (1983), 95-122.
• 16: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 17: Jim Gray, A Transaction Model, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.282-298, July 14-18, 1980
• 18: GRAY, J., HOMAN, P., KORTH, H., AND OBERMARCK, R. A straw man analysis of the probability of waiting and deadlock in a database system. Tech. Rep. RJ3066, IBM Research Lab., San Jose, Calif., Feb. 1981.
• 19: Keki B. Irani , Hing-Lung Lin, Queueing network models for concurrent transaction processing in a database system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582116]
• 20: Werner Kießling , G. Landherr, A Quantitative Comparison of Lockprotocols for Centralized Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.120-130, October 31-November 02, 1983
• 21: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 22: Stephen S. Lavenberg, A simple analysis of exclusive and shared lock contention in a database system, Proceedings of the 1984 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.143-148, January 1984
• 23: LIN, W. K., AND NOLTE, J. Performance of two phase locking. In Proceedings of the 6th Berkeley Workshop on Distributed Data Management and Computer Networks (Berkeley, Calif., Feb. 1982), pp. 131-160.
• 24: MITRA, D. Probabilistic models and asymptotic results for concurrent processing with exclusive and non-exclusive locks. SIAM J. Comput. To be published.
• 25: MORRIS, R. J. T., AND WONG, W.S. Performance analysis of locking and optimistic concurrency control algorithms. Tech. Rep., AT&T Bell Lab.
• 26: R. Munz , G. Krenz, Concurrency in database systems: a simulation study, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509421]
• 27: D. Potier , Ph. Leblanc, Analysis of locking policies in database management systems, Communications of the ACM, v.23 n.10, p.584-593, Oct. 1980 [doi>10.1145/359015.359021]
• 28: Daniel Roland Ries, The effects of concurrency control on the performance of database management systems., 1979
• 29: Rvu, I. K., AND THOMASIAN, A. Analysis of database performance with dynamic locking. In preparation.
• 30: SEVClK, K.C. Comparison of concurrency control methods using analytic models. In in{o. Proc. 83, R. E. A. Mason, Ed. North-Holland, Amsterdam, 1983, pp. 847-858.
• 31: SHUM, A. W., AND SP|RAKIS, P.G. Performance analysis of concurrency control methods in database systems. Performance 81, F. J. Kylstra, Ed. North-Holland, Amsterdam, 1981, pp. 1- 19.
• 32: SURI, R., AND DIEHL, G.W. A variable buffer-size model and its use in analyzing closed queuing networks with blocking. Submitted for publication.
• 33: Yong Chiang Tay, A mean value performance model for locking in databases, 1984
• 34: TAY, Y. C., GOODMAN, N., AND SUm, R. Performance evaluation of locking in databases: A survey. Tech. Rep. TR 17-84, Aiken Computation Lab., Harvard Univ., Cambridge, Mass., Oct. 1984.
• 35: Y. C. Tay , Rajan Suri , Nathan Goodman, A mean value performance model for locking in databases: the no-waiting case, Journal of the ACM (JACM), v.32 n.3, p.618-651, July 1985 [doi>10.1145/3828.3831]
• 36: THOMAS|AN, A. An iterative solution to the queuing network model of a DBMS with dynamic locking. In Proceedings of the 13th Computer Measurement Group Conference (San Diego, Calif., Dec. 1982), pp. 252-261.
• 37: 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]
• 38: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Centralized networks**
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Deadlock avoidance
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Measurement, Performance, Theory, Verification