Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!smu.UUCP!leff From: leff@smu.UUCP (Laurence Leff) Newsgroups: comp.doc.techreports Subject: tr-input/uklirb Message-ID: <8908192013.AA09907@smu.edu> Date: 19 Aug 89 20:13:11 GMT Sender: daemon@ucbvax.BERKELEY.EDU Organization: The Internet Lines: 324 Approved: trlist@smu.edu ============================================================================ Project 'High Performance Transaction Systems' Data Management Systems Institute (Prof. Haerder) Dept. of Computer Science Univ. of Kaiserslautern, West Germany Technical Reports (1985 - 1989) If you wish to request a copy of one of the following reports, please contact: Dr. Erhard Rahm Dept. of Computer Science Univ. Kaiserslautern P.O. Box 3049 D-6750 Kaiserslautern, West Germany E-mail: rahm@uklirb.uucp ============================================================================ A. Reuter: Load Control and Load Balancing in a Shared Database Management System, TR 129/85, March 1985 In shared DBMS, there is a need for dynamically setting a large number of operational parameters, like transaction routing tables, assignment of central resources, multiprogramming level etc. It is shown that static techniques as they are applied in current centralized DBMS are inadequate for exploiting the performance potential of a shared DBMS. We therefore plead for using dynamic load control methods for adaptive modification of the DBMS's operational parameters. After a brief survey of the state of the art in database load control, we outline an approach for load balancing in a shared system, which consists of both analytic models and heuristics. The key concepts are illustrated by a simple example, and a number of areas for future research are identified. This paper appeared in 2nd Int. Conf. on Data Engineering, pp. 188-197, 1986 ============================================================================ E. Rahm: Primary Copy Synchronization for DB-Sharing, TR 137/85, July 1985 In a database sharing (DB-Sharing) system, multiple loosely or closely coupled processors share access to a single set of databases. Such systems promise better availability and linear growth of transaction throughput at equivalent response time compared to single processor database systems. The efficiency of a DB-Sharing system heavily depends on the synchronization technique used for maintaining consistency of the shared data. A promising algorithm is the primary copy approach which will be presented in this paper. We describe the actions of the lock manager in a basic and in a more advanced version. Furthermore, it is shown how the lock managers can be enabled to deal with the so-called buffer invalidation problem that results from the existence of a database buffer in each processor. An improved version of this report appeared in INFORMATION SYSTEMS, Vol. 11, No. 4, pp. 275-286, 1986 ========================================================================= E. Rahm: A Reliable and Efficient Synchronization Protocol for Database Sharing Systems, TR 139/85, Aug. 1985 We describe how the primary copy protocol for DB-sharing can be extended to continue concurrency control after processor crashes. In particular, mechanisms are proposed to reconstruct lost lock tables and to adapt the PCA allocation. The redundancy required for reconstruction of lost lock information can be provided with nearly no extra costs during normal processing. We outline additional recovery actions which can partly be processed in parallel to permit a fast crash recovery. This paper appeared in Proc. 3rd Int. Conf. on Fault-Tolerant Computing Systems, pp. 336-347, 1987 (Springer-Verlag) ============================================================================ E. Rahm: Buffer Invalidation Problem in DB-Sharing System, TR 154/86, Feb. 1986 In the near future large transaction processing systems will have to meet high requirements concerning throughput, response times, availability and modular growth. A possible architecture for such high performance systems is DB-Sharing where multiple loosely or closely coupled processors share the common database at the disk level. Unfortunately, DB-Sharing has a buffer invalidation problem since each processor maintains a database buffer of its own and, therefore, multiple copies of a database page may reside in multiple buffers. Modification of any copy will thus invalidate all other copies. This paper provides a spectrum of solutions to this buffer invalidation problem. It turns out that the most effective solutions are feasible if synchronization and buffer control can be combined. Further sections deal with the implications of a processor crash and the use of a global database buffer in the context of buffer invalidation. A subset of this report appeared as 'Integrated Solutions to Concurrency Control and Buffer Invalidation' in Proc. 2nd Int. Conf. on Computers and Applications, pp. 410-417, 1987 ========================================================================= E. Rahm: Concurrency Control in DB-Sharing Systems, 1986 This paper gives an overview of concurrency control algorithms for data sharing (DB-Sharing). We distinguish between locking and optimistic methods and between centralized and distributed solutions. Five synchronization protocols are described in some detail and compared with each other. This paper appeared in Proc. 16th Annual Conf. of the German Computer Society GI, pp. 617-632, 1986 (Springer-Verlag) ============================================================================= T. Haerder: Handling Hot Spot Data in DB-Sharing Systems, IBM Research Report RJ 5523, 1987 We review various solutions for concurrency control on aggregate data where the operations to be synchronized commute - at least for certain value ranges. In particular, the escrow mechanism for centralized DBMS is discussed and extended. Our investigations focus on the escrow mechanism for a data sharing environment. We propose the use of global escrow services which may be called asynchronously. Such an optimistic attitude seems to be apprpriate, since rejections of escrow operations typically are rare events. The performance of the proposed scheme may be further improved by refining it to a hierarchical escrow scheme with a global escrow and distributed local escrows. This paper appeared in Information Systems, Vol. 13, No. 2, pp. 155-166, 1988 ============================================================================= E. Rahm: Performance Evaluation of Primary Copy Synchronization in Database Sharing Systems, TR 165/87, Feb. 1987 In this paper we investigate the performance of the primary copy protocol which has been proposed for concurrency and coherency control in data sharing systems. A trace-driven simulation system has been developed where the synchronization component together with buffer management and logging components have been completely implemented. Detailed simulation results are presented for two transaction loads and a varying number of processors. In addition, the performance impact of different communication costs and load distribution strategies (affinity based vs. random routing) is investigated. ======================================================================== E. Rahm: Design of Optimistic Methods for Concurrency Control in Database Sharing Systems, 1987 Optimistic methods promise less synchronization messages per transaction than locking algorithms for concurrency control in database sharing (DB- sharing) systems. We describe a new distributed protocol called broadcast validation where the validations for a transaction are simultaneously started at multiple processors by a broadcast message. Such a parallel validation scheme is prerequisite for reaching short response times and high transaction rates. The use of timestamps permits simple and fast validations as well as an integrated solution to the so-called buffer invalidation problem that is introduced by the DB-sharing architecture. Further improvements of our algorithm are proposed in order to reduce the synchronization overhead and to allow a combination with a distributed locking protocol which is advisable for applications with higher conflict probability. The communication and validation overhead of our algorithms is quantified by simple estimates. This report appeared in Proc. 7th Int. Conf. on Distributed Computing Systems, pp. 154-161, 1987 ============================================================================= T. Haerder: On Selected Performance Issues of Database Systems, 1987 Performance, data integrity, and user-friendly access to data are considered the cardinal properties of DBMS. But performance will steadily receive more attention as more interactive applications are designed and implemented for almost all domains of our life. We discuss specific performance problems of 'conventional' DBMS, DB/DC systems, and DBMS for 'non-standard' applications (e.g. engineering, office, etc.). Then, a short survey attempts to sketch the solutions achieved and the problems remaining for the most performance-critical DBMS functions/components. This paper appeared in Proc. 4th Conf. on Measurement, Modelling and Evaluation of Computer Systems, pp. 294-312, 1987 (Springer-Verlag) ============================================================================= E. Rahm: Design and Evaluation of Concurrency and Coherency Control Techniques for Database Sharing Systems, TR 182/88, May 1988 This paper provides a survey and an empirical performance evaluation of concurrency and coherency control protocols for DB-sharing. For synchronization a number of locking and optimistic protocols are discussed as well as some design alternatives like multiversion concurrency control or schemes for reduced consistency requirements. Strategies for coherency control are classified and their integration into the synchronization protocols is described. For a realistic performance comparison of the presented protocols a trace-driven simulation system for loosely coupled DB-Sharing systems has been developed. Within this system six concurrency and coherency control protocols together with buffer management and logging components have been completely implemented; a table-driven approach is pursued for distributing the transaction load among the processors. In addition to the quantitative comparison of the protocols, the performance impact of different communication costs and load distribution strategies (affinity based vs. random routing) is investigated. A discussion of the simulation results (for 4 protocols) can also be found in 'Empirical Performance Evaluation of Concurrency and Coherency Control Protocols for Data Sharing', IBM Research Report RC 14325, 1988 =========================================================================== E. Rahm, A. Thomasian: Distributed Optimistic Concurrency Control for High Performance Transaction Processing, IBM Research Report, Yorktown Heights, 1989 The performance of high-volume transaction processing systems is determined by the degree of hardware and data contention. This is especially a problem in the case of distributed systems with global transactions accessing and updating objects from multiple systems. While the conventional two-phase locking method of centralized systems can be adapted for concurrency control in distributed systems, it may restrict system throughput to very low levels. This is due to a significant increase in lock holding times and associated transaction waiting time for locks, as compared to centralized systems. Optimistic concurrency control (OCC) which is similarly extensible to distributed systems has the disadvantage of repeated transaction restarts, which is a weak point of currently proposed methods. We propose a new hybrid method based on OCC followed by locking, which is an integral part of distributed validation and two-phase commit. This advanced OCC method assures that a transaction failing its validation will not be re-executed more than once, in general. Furthermore deadlocks, which are difficult to handle in a distributed environment, are avoided by serializing lock requests. We outline implementation details and compare the performance of the new scheme with distributed two-phase locking. ========================================================================== V. Bohn: Performance Evaluation of a Distributed Database System by Means of Discrete Event Simulation, 1989 We investigate the performance behavior of locally distributed database system which use front-end processors to allocate the workload to transaction processing nodes. The performance analysis is based on a complex simulation system which is driven by page reference strings and employs discrete event handling for simulation control. Main parameters of the simulation system include the number of nodes and the multiprogramming level. Response time and throughput results are analysed as well as internal statistics (communication frequency, CPU utilization etc.) This paper appears in Proc. 3rd European Simulation Congress, Sep. 1989 ========================================================================== E. Rahm: A Framework for Workload Allocation in Distributed Transaction Systems, Sept. 1989 Ever increasing demands for high transaction rates, limitations of high-end processors, high availability and modular growth considerations are all driving forces towards distributed architectures for transaction processing. A key prerequisite to take advantage of the capacity of a distributed transaction system, however, is an effective strategy for workload allocation. The distribution of the workload should not only achieve load balancing, but also support an efficient transaction processing with a minimum of inter-system communication. To this end, dynamic - yet efficient - schemes for transaction routing have to be employed which are highly responsive to configuration changes and workload fluctuations. We develop a general framework for workload allocation in distributed transaction systems. This framework is based on a classification of distributed architectures and execution models for transaction processing which determine the optimization potential for workload distribution. The framework helps to identify key factors and alternatives in the design of appropriate allocation schemes. Furthermore, it facilitates a comparison of existing schemes and may guide the development of new, more effective protocols. =========================================================================== =========================================================================== The following reports are available in GERMAN: T. Haerder, E. Rahm: Quantitative Analysis of a Synchronization Algorithm for Data Sharing, 1985 (conference paper, simulation study of extended pass-the-buck protocol) E. Rahm: Closely Coupled Architectures for Data Sharing, 1986 (conference paper) E. Rahm: Algorithms for Efficient Load Control in Multiprocessor Database Systems, 1986 (journal paper) T. Haerder, E. Rahm: Multiprocessor Database Systems for High Performance Transaction Procesing, 1986 (journal paper, classification of distributed architectures for database management) T. Haerder, E. Rahm: High Performance Database Systems - Comparison and Evaluation of Current Architectural Approaches and their Implementation, 1987 (journal paper, comparison of 'shared disk' and 'shared nothing') K. Meyer-Wegener: Transaction Systems - Distributed Processing and Distributed Data Management, 1987 (journal paper) T. Haerder: Fault Tolerance in Transaction Processing Systems, 1987 (conference paper) E. Rahm: Optimistic Concurrency Control in Centralized and Distributed Database Systems, 1988 (journal paper) V. Bohn, T. Wagner: Cooperation between Load Control and Recovery in Data Sharing Systems, 1989 E. Rahm: The Data Sharing Approach to High Performance Transaction Processing, 1989 (journal paper, summarizes state of the art for 'shared disk' implementations) V. Bohn: Characteristics of Transaction Workloads in DB/DC Systems, 1989 (conference paper, workload characterization based on trace analysis) V. Bohn, T. Wagner: Transaction Chains - Concept and Implementation, 1989 (conference paper, implementation of 'sagas') T. Haerder, K. Meyer-Wegener: Transaction Processing in Workstation/Server Environments, 1989 T. Haerder, E. Rahm: Utilization of New Storage Architectures for High Performance Transaction Processing, 1989 (use of shared semiconductor stores in data sharing systems)