The performance of multiversion concurrency control algorithms

ABSTRACT

A number of multiversion concurrency control algorithms have been proposed in the past few years. These algorithms use previous versions of data items in order to improve the level of achievable concurrency. This paper describes a simulation study of the performance of several multiversion concurrency control algorithms, investigating the extent to which they provide increases in the level of concurrency and also the CPU, I/O, and storage costs resulting from the use of multiple versions. The multiversion algorithms are compared with regard to performance with their single-version counterparts and also with each other. It is shown that each multiversion algorithm offers significant performance improvements despite the additional disk accesses involved in accessing old versions of data; the nature of the improvement depends on the algorithm in question. It is also shown that the storage overhead for maintaining old versions that may be required by ongoing transactions is not all that large under most circumstances. Finally, it is demonstrated that it is important for version maintenance to be implemented efficiently, as otherwise the cost of maintaining old versions could outweigh their concurrency benefits.

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. Bayer , H. Heller , A. Reiser, Parallelism and recovery in database systems, ACM Transactions on Database Systems (TODS), v.5 n.2, p.139-156, June 1980 [doi>10.1145/320141.320146]
• 3: 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]
• 4: Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983 [doi>10.1145/319996.319998]
• 5: BRYANT, R. SIMPAS--A simulation language based on PASCAL. Tech. Rep. 390, Computer Sciences Dept., Univ. of Wisconsin-Madison, June 1980.
• 6: Michael James Carey, Modeling and evaluation of database concurrency control algorithms, 1983
• 7: CAREV, M. Multiple versions and the performance of optimistic concurrency control. Tech. Rep. 517, Computer Sciences Dept., Univ. of Wisconsin-Madison, Oct. 1983.
• 8: 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
• 9: CHAN, A., AND GRAY, R. Implementing distributed read-only transactions. IEEE Trans. So{tw. Eng~ SE-11, 2 (Feb. 1985).
• 10: CHris, A., DAVAL, U., AND HSU, M. Providing database management capabilities for mission critical applications. Paper presented at the International Workshop on High-Performance Transaction Processing Systems (Asilomar, Calif., Sept.). IEEE, New York, 1985.
• 11: Arvola Chan , Stephen Fox , Wen-Te K. Lin , Anil Nori , Daniel R. Ries, The implementation of an integrated concurrency control and recovery scheme, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582386]
• 12: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 13: DuBOURD,EU, D. Implementation of distributed transactions. In Proceedings of the 6th Berkeley Workshop on Distributed Data Management and Computer Networks. 1982.
• 14: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 15: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 16: 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]
• 17: Ming-Yee Lai , W. Kevin Wilkinson, Distributed Transaction Management in Jasmin, Proceedings of the 10th International Conference on Very Large Data Bases, p.466-470, August 27-31, 1984
• 18: 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
• 19: LIN, W., AND NOLTE, J. Performance of distributed concurrency control. In Distributed Database Control and Allocation. Final Tech. Rep., vol. 2, Computer Corporation of America, Cambridge, Mass., 1983.
• 20: LIVNY, M., KHOSHAFIAN, S., AND BORAL, H. Multi-disk management algorithms. Paper presented at the International Workshop on High-Performance Transaction Processing Systems (Asilomar, Calif., Sept.). 1985. (Also MCC Tech. Rep., Microelectronics and Computer Technology Corporation, Austin, Tex., Dec. 1985.)
• 21: Christos H. Papadimitriou , Paris C. Kanellakis, On Concurrency Control by Multiple Versions, ACM Transactions on Database Systems (TODS), v.9 n.1, p.89-99, March 1984 [doi>10.1145/348.318588]
• 22: Peter Peinl , Andreas Reuter, Empirical Comparison of Database Concurrency Schemes, Proceedings of the 9th International Conference on Very Large Data Bases, p.97-108, October 31-November 02, 1983
• 23: REED, D. Naming and synchronization in a decentralized computer system. Ph.D. dissertation, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, Mass., 1978.
• 24: 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]
• 25: Daniel Roland Ries, The effects of concurrency control on the performance of database management systems., 1979
• 26: 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]
• 27: 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]
• 28: John Timothy Robinson, Design of concurrency controls for transaction processing systems, 1982
• 29: ROOME, W. A content-addressabIe intelligent store. Bell Syst. Tech. J. 61, 9 (Nov. 1982).
• 30: Robert G. Sargent, Statistical analysis of simulation output data, Proceedings of the 4th symposium on Simulation of computer systems, p.39-50, August 10-12, 1976, Boulder, Colorado, United States
• 31: Richard E. Stearns , Daniel J. Rosenkrantz, Distributed database concurrency controls using before-values, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582330]
• 32: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Simulation

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

General Terms:
Algorithms, Design, Experimentation, Performance