Approximation for the mean value performance of locking algorithms for distributed database systems: A partitioned database

Concurrent access to databases must be synchronized for correct execution of transactions and preservation of data consistency. This is usually achieved through use of concurrency control algorithms, amongst which locking algorithms are the most popular both in the literature and in practice. Several analytic methods have been developed for predicting the performance of centralized database systems employing locking algorithms for concurrency control, but very few exist for distributed database systems. This paper proposes a method to approximate the mean value of various performance parameters in distributed database systems using locking for concurrency control. The main contribution of this approach is its ability to model the interaction between resource and data contention and the resulting effect on system performance. System performance is evaluated at a point where the interaction between these two factors is in equilibrium (stable state) and both the data and resource contention equations are simultaneously satisfied. The model involves the solution of a set of simultaneous polynomial equations whose order is dependent on several problem parameters such as the number of nodes and number of locks requested per transaction. These equations are solved by an iterative procedure to evaluate approximate values of relative throughput, utilization of servers and transaction response time. The small computational requirements of the analytical model permit sensitivity analysis on network parameters, and can thus be effectively used by system designers to evaluate choices of communication line speeds, processor capacity, database sizes, etc. The analytic approximations have been extensively verified against simulations for networks with up to 20 nodes. The input traffic was varied from light loads (about 5% utilization of the channels and processors) to heavy loads (about 65% utilization of the processors and channels). The discrepancies between the analytic approximation and the simulation were quite small (2-8%).