🚀 go-pugleaf

  
============================================================================
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)