Design and performance analysis of locking algorithms for distributed databases
S.-C. Shyu · University of Southern California Digital Library · 2015
Numerous performance models have been proposed for locking algorithms in centralized database systems, but few have been developed for distributed ones. Existing results on distributed locking usually ignore the deadlock problem so as to simplify the analysis. In this thesis, a new performance model for static locking in distributed database systems is developed. A queueing model is used to approximate static locking in distributed database systems without deadlocks. Then a random graph model is proposed to find the deadlock probability and restart probability of each transaction. Finally, the above two models are integrated, so that given the transaction arrival rate, the response time and the effective throughput can be calculated. The results are very general, so they can be applied to other systems with deadlocks. The analytical results are validated by simulation results. The deadlock problem is intrinsic to locking systems. Efficiently resolving deadlocks is crucial to the performance of locking systems. From the simulation, we verify that most deadlocks are of length two and that the deadlock probability is very small. However, we found that although deadlock does not occur often, once it occurs, the system of performance drops dramatically, unless it is resolved quickly. This is because the resource held by the deadlocked transactions are not released and this further blocks more transactions. Therefore, an efficient abortion-free distributed deadlock detection/resolution algorithm (ABF) is proposed in this thesis. The most important feature of ABF is that when a deadlock cycle is detected, it is resolved by reordering the wait-for relations between pairs of transactions. Therefore, no transaction abortions are necessary to resolve deadlock cycles. This results in less messages, smaller transaction response time and better fairness. The correctness of this abortion-free algorithm is proved. The algorithm ABF is then extended to distinguish Read/Write locks and transaction classes. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)