Concurrency control for high contention environments

ABSTRACT

Future transaction processing systems may have substantially higher levels of concurrency due to reasons which include: (1) increasing disparity between processor speeds and data access latencies, (2) large numbers of processors, and (3) distributed databases. Another influence is the trend towards longer or more complex transactions. A possible consequence is substantially more data contention, which could limit total achievable throughput. In particular, it is known that the usual locking method of concurrency control is not well suited to environments where data contention is a significant factor. Here we consider a number of concurrency control concepts and transaction scheduling techniques that are applicable to high contention environments, and that do not rely on database semantics to reduce contention. These include access invariance and its application to prefetching of data, approximations to essential blocking such as wait depth limited scheduling, and phase dependent control. The performance of various concurrency control methods based on these concepts are studied using detailed simulation models. The results indicate that the new techniques can offer substantial benefits for systems with high levels of data contention.

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: 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: DuBouRDIEU, D.J. Implementation of distributed transactions. In Proceedings of the 6tb Berkeley Workshop on Distributed Data Management and Computer Networks, ACM/IEEE, 1982, pp. 81-94
• 4: 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]
• 5: GAWLIBK, D., AND KINKADE, D. Varieties of concurrency control in IMS/VS fast path IEEE Database Eng. 4 (1985), 63-70.
• 6: Hsu, M., AND ZHANG, B. Performance evaluation of cautious waiting Res. Rep., Aiken Computation Laboratory, Harvard Univ., Aug. 1987 (submitted for publication).
• 7: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 8: MALHOTRA, A., MARKOWITZ, H. M., AND PAZEL, D. P. Conmstent copy: a new database facility. Rep. RC9630, IBM Research Div., T. J. Watson Research Center, Yorktown Heights, N Y., 1982
• 9: Patrick E. O'Neil, The Escrow transactional method, ACM Transactions on Database Systems (TODS), v.11 n.4, p.405-430, Dec. 1986 [doi>10.1145/7239.7265]
• 10: Andreas Reuter, Concurrency on high-traffic data elements, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588126]
• 11: REUTER, A. The transaction pipeline processor. Presented at the International Workshop on High Performance Transactzon Systems (Pacific Grove, Calif, Sept. 1985).
• 12: ROmNSON, J. T Design of concurrency controls for transaction processing systems~ Ph.D. thesis, Tech. Rep. CMU-CS-82-114, Carnegie Mellon Univ , 1982.
• 13: In Kyung Ryu , Alexander Thomasian, Performance analysis of centralized databases with optimistic concurrency control, Performance Evaluation, v.7 n.3, p.195-211, August 1, 1987 [doi>10.1016/0166-5316(87)90040-X]
• 14: 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]
• 15: Y. C. Tay, Locking performance in centralized databases, Academic Press Professional, Inc., San Diego, CA, 1988
• 16: Alexander Thomasian, Performance Limits of Two-Phase Locking, Proceedings of the Seventh International Conference on Data Engineering, p.426-435, April 08-12, 1991
• 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: Transaction processing

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
concurrency control, transaction processing