Analysis of database performance with dynamic locking

ABSTRACT

A detailed model of a transaction processing system with dynamic locking is developed and analyzed. Transaction classes are distinguished on the basis of the number of data items accessed and the access mode (read-only/update). The performance of the system is affected by transaction blocking and restarts, due to lock conflicts that do not or do cause deadlocks, respectively. The probability of these events is determined by the characteristics of transactions and the database access pattern. Hardware resource contention due to concurrent transaction processing is taken into account by specifying the throughput characteristic of the computer system for processing transactions when there is no data contention. A solution method based on decomposition is developed to analyze the system, and also used as the basis of an iterative scheme with reduced computational cost. The analysis to estimate the probability of lock conflicts and deadlocks is based on the mean number of locks held by transactions. These probabilities are used to derive the state transition probabilities for the Markov chain specifying the transitions among the system states. The decomposition solution method and the associated iterative scheme are shown to be more accurate than previously defined methods for dynamic locking through validation against simulation results. Several important conclusions regarding the behavior of dynamic locking systems are derived from parametric studies.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Rakesh Agrawal , Michael J. Carey , Lawrence McVoy, The performance of alternative strategies for dealing with deadlocks in database management systems, IEEE Transactions on Software Engineering, v.13 n.12, p.1348-1363, December 1, 1987 [doi>10.1109/TSE.1987.233145]
• 4: Michael James Carey, Modeling and evaluation of database concurrency control algorithms, 1983
• 5: 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]
• 6: COURTOIS, P.j. Decomposability: Queueing and Computer System Applications. Academic Press, Orlando, Fla., 1977.
• 7: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 8: Peter Franaszek , John T. Robinson, Limitations of concurrency in transaction processing, ACM Transactions on Database Systems (TODS), v.10 n.1, p.1-28, March 1985 [doi>10.1145/3148.3160]
• 9: GRAY, J. N., HOMAN, R., OBERMARCK, R. L., AND KORTH, H. A straw-man analysis of waiting and deadlock. IBM Res. Center Rep. RJ 3066. IBM, San Jose, February 1981.
• 10: GRAY, J. N., HOMAN, P., SAMMER, H., GOOD, B., AND GAWLICK, D. One thousand transactions per second. In Proceedings of the IEEE COMPCON Spring 1985 (San Francisco, Calif., Feb.). IEEE, New York, 1985, pp. 96-101.
• 11: Hsu, M., AND ZHANG, B. The mean value approach to performance evaluation of cautious locking. Tech. Rep. Aiken Computation Lab., Harvard Univ., Cambridge, Mass., Feb. 1984 (to appear in ACM Trans. Datab. Syst.).
• 12: 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]
• 13: Annie W. Shum , Andrew M. Langer, The distribution of granule accesses made by database transactions, Communications of the ACM, v.25 n.11, p.831-832, Nov 1982 [doi>10.1145/358690.358714]
• 14: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 15: LIN, W. T. K., AND NOLTE, J. Communication delay and two-phase locking. In Proceedings of the 3rd International Conference on Distributed Computing Systems (Miami, Fla., Oct.) IEEE Computer Society Press, Washington, D.C., 1982, pp. 502-507.
• 16: 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]
• 17: Ross, S. M. Applied Probability Models with Optimization Applications. Holden-Day, San Francisco, Calif., 1970.
• 18: Rvu, I. K. Performance Evaluation of Concurrency Control in Database Systems. Ph.D. dissertation. Dept. Electrical Engineering-Systems, Univ. Southern California, Los Angeles, Los Angeles, Calif., 1985.
• 19: 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]
• 20: SAUER, C. H., AND MACNAIR, E.A. Simultaneous resource possession in queueing models of computers. IBM Res. Rep. RC 697 I. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., Feb. 1978.
• 21: Y. C. Tay, Locking performance in centralized databases, Academic Press Professional, Inc., San Diego, CA, 1988
• 22: Y. C. Tay , Nathan Goodman , R. Suri, Locking performance in centralized databases, ACM Transactions on Database Systems (TODS), v.10 n.4, p.415-462, Dec. 1985 [doi>10.1145/4879.4880]
• 23: 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]
• 24: THOMASIAN, A. An iterative solution to the queueing network model of a DBMS with dynamic locking. In Proceedings of the 13th Computer Measurement Group Conference (San Diego, Calif., Dec.). Computer Management Group, Inc., Phoenix, Ariz. 1982, pp. 252-26 I.
• 25: Alexander Thomasian, Performance evaluation of centralized databases with static locking, IEEE Transactions on Software Engineering, v.11 n.4, p.346-355, April 1985 [doi>10.1109/TSE.1985.232224]
• 26: 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]
• 27: THOMASIAN, A., AND RYU, |. K. On analyzing lock contention in databases. IBM Res. Rep. RC 12666. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., Mar. 1987.
• 28: Alexander Thomasian , In Kyung Ryu, A Recursive Solution Method to Analyze the Performance of Static Locking Systems, IEEE Transactions on Software Engineering, v.15 n.10, p.1147-1156, October 1989 [doi>10.1109/TSE.1989.559761]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

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

General Terms:
Design, Performance