Parallelism and concurrency control performance in distributed database machines

ABSTRACT

While several distributed (or 'shared nothing') database machines exist in the form of prototypes or commercial products, and a number of distributed concurrency control algorithms are available, the effect of parallelism on concurrency control performance has received little attention. This paper examines the interplay between parallelism and transaction performance in a distributed database machine context. Four alternative concurrency control algorithms are considered, including two-phase locking, wound-wait, basic timestamp ordering, and optimistic concurrency control. Issues addressed include how performance scales as a function of machine size and the degree to which partitioning the database for intra-transaction parallelism improves performance for the different algorithms. We examine performance from several perspectives, including response time, throughput, and speedup, and we do so over a fairly wide range of system loads. We also examine the performance impact of certain important overhead factors (e.g., communication and process initiation costs) on the four alternative concurrency control algorithms.

REFERENCES

• Agra87a: 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]
• Agra87b: 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]
• Alex88: W. Alexander , G. Copeland, Process and dataflow control in distributed data-intensive systems, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.90-98, June 01-03, 1988, Chicago, Illinois, United States
• Bada79: Badal, D., "Correctness of Concurrency Control and Implications in Distributed Databases," Proc. COMPSAC '79 Conf., Chicago, IL,, Nov. 1979.
• Balt82: 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]
• Bern80: Bemstein, P., and Goodman, N., 'q'imestamp-Based Algorithms for Concurrency Control in Distributed Database Systems," Proc. 6th VLDB Conf., Mexico City, Mexico, Oct. 1980.
• Bern81: 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]
• Bhar82: Bhargava, B., "Performance Evaluation of the Optimistic Approach to Distributed Database Systems and its Comparison to Locking," Proc. 3rd lnt'l. Conf. on Dist. Comp. Sys., Miami, FL, October 1982.
• Bhid88: Anupam Bhide , Michael Stonebraker, A Performance Comparison of Two Architectures for Fast Transaction Processing, Proceedings of the Fourth International Conference on Data Engineering, p.536-545, February 01-05, 1988
• Bora88: Boral, H., "Parallelism and Data Management," Proc. 3rd Int'l Conf. on Data and Knowledge Bases, Jerusalem, Israel, June 1988.
• Borr88: A. Borr, High performance SQL through low-level system integration, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.342-349, June 01-03, 1988, Chicago, Illinois, United States
• Care88: Michael J. Carey , Miron Livny, Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication, Proceedings of the 14th International Conference on Very Large Data Bases, p.13-25, August 29-September 01, 1988
• Care89: Carey, M., and Livny, M., Conflict Detection Trade. offs for Replicated Data, Tech. Rep. No. 826, Comp. Sci. Dept., Univ. of Wisconsin, Madison, Feb. 1988.
• Ceri82: Ceri S., and Owicki, S., "On the Use of Optimistic Methods for Concurrency Control in Distributed Databases," Proc. 6th Berkeley Workshop on Dist. Data Mgmt. and Comp. Networks, Feb. 1982.
• DeWi86: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• DeWi88: D. J. DeWitt , S. Ghanderaizadeh , D. Schneider, A performance analysis of the gamma database machine, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.350-360, June 01-03, 1988, Chicago, Illinois, United States
• Gall82: Bruce Irving Galler, Concurrency control performance issues, 1982
• Garc79: Hector Garcia-Molina, Performance of update algorithms for replicated data in a distributed database., 1979
• Gray79: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• Jenq89: B. Paul Jenq , Brian Twichell , Tom Keller, Locking Performance in a Shared Nothing Parallel Database Machine, Proceedings of the Fifth International Conference on Data Engineering, p.149-158, February 06-10, 1989
• Khos88: Khoshafian, S., and Valduriez, P., "Parallel Execution Strategies for Declustered Databases," in Database Machines and Knowledge Base Machines, M. Kitsuregawa and H. Tanaka, eds., Kluwer Academic Press, 1988.
• Kohl85: Kohler, W., and Jenq, B., Performance Evaluation of Integrated Concurrency Control and Recovery Algorithms Using a Distributed Transaction Processing Testbed, Tech. Rep. No. CS-85-133, Dept. of Elec. and Comp. Eng., Univ. of Massachusetts, Amherst, 1985.
• Lai88: Lai, M., Wilkinson, W., and Lanin, V., "Distributing the Optimistic Multiversioning Page Manager in the JASMIN Database Machine," in Database Machines and Knowledge Base Machines, M. Kitsuregawa and H. Tanaka, eds., Kluwer Academic Press, 1988.
• Lazo86: Edward D. Lazowska , John Zahorjan , David R. Cheriton , Willy Zwaenepoel, File access performance of diskless workstations, ACM Transactions on Computer Systems (TOCS), v.4 n.3, p.238-268, Aug. 1986 [doi>10.1145/6420.6423]
• Li87: V. O. K. Li, Performance models of timestamp-ordering concurrency control algorithms in distributed databases, IEEE Transactions on Computers, v.36 n.9, p.1041-1051, Sept. 1987
• Lin83: Wen-Te K. Lin , Jerry Nolte, Basic Timestamp, Multiple Version Timestamp, and Two-Phase Locking, Proceedings of the 9th International Conference on Very Large Data Bases, p.109-119, October 31-November 02, 1983
• Livn88: Livny, M., DeNet User's Guide, Version 1.0, Comp. Sci. Dept., Univ. of Wisconsin, Madison, 1988.
• Mena78: Menasce, D., and Muntz, R., "Locking and Deadlock Detection in Distributed Databases," Proc. 3rd Berkeley Workshop on Dist. Data Mgmt. and Comp. Networks, Aug. 1978.
• Noe87: Jerre D. Noe , David B. Wagner, Measured Performance of Time Interval Concurrency Control Techniques, Proceedings of the 13th International Conference on Very Large Data Bases, p.359-367, September 01-04, 1987
• Oszu85: M. T. Ozsu, Modeling and analysis of distributed database concurrency control algorithms using an extended petri net formalism, IEEE Transactions on Software Engineering, v.11 n.10, p.1225-1240, Oct. 1985 [doi>10.1109/TSE.1985.231870]
• Reed83: David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
• Ries78: Ries, D., and Epstein, R., Evaluation of Distribution Criteria for Distributed Database Systems, ERL Memo. No. UCB/ERL M78/22, Univ. of California, Berkeley, May 1978.
• Ries79: Ries, D., "The Effects of Concurrency Control on the Performance of a Distributed Data Management System," Proc. 4th Berkeley Workshop on Dist. Data Mgmt. and Comp. Networks, Aug. 1979.
• Rose78: 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]
• Schl81: Schlageter, G., "Optimistic Methods for Concurrency Control in Distributed Database Systems," Proc. 7th VLDB Conf., Cannes, France, Sept. 1981.
• Sinh85: Mukul K. Sinha , P. D. Nandikar , S. L. Mehndiratta, Timestamp based certification schemes for transactions in distributed database systems, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.402-411, May 1985, Austin, Texas, United States
• Ston79: Stonebraker, M., "Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES," IEEE Trans. on Softw. Eng. SE-5, 3, May 1979.
• Ston86: Stonebraker, M., "The Case for Shared Nothing," Database Eng. 9, 1, March 1986.
• Tand88: CORPORATE Tandem Performance Group, A benchmark of non-stop SQL on the debit credit transaction, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.337-341, June 01-03, 1988, Chicago, Illinois, United States
• Tera85: Teradata DBC/1012 Data Base Computer Systems Manual, Release 13, Teradata Corp. Document No. C10-0001- 00, Feb. 1985.
• Thom79: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• Trai82: Irving L. Traiger , Jim Gray , Cesare A. Galtieri , Bruce G. Lindsay, Transactions and consistency in distributed database systems, ACM Transactions on Database Systems (TODS), v.7 n.3, p.323-342, Sept. 1982 [doi>10.1145/319732.319734]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Experimentation, Languages, Measurement, Performance, Reliability