Performance limits of two-phase locking

Abstract

A novel mean-value analysis method for two-phase locking (2PL) is presented which extends previous work to the important case of variable size transactions. The system performance expressed as the fraction of blocked transactions (β) is determined by solving a cubic equation in β whose coefficients are functions of a single parameter (α), which determines the degree of lock contention in the system. In fact, α is proportional to the mean number of lock requests per transaction (ηc) and additionally the mean waiting time (W1) for a lock held by an active transaction. For α < 0.226 the performance of the system is determined by the smallest root of the cubic and the system is thrashing otherwise, i.e., a large fraction of the transactions in the system are blocked. Validation of the analytic solution against simulation results shows that the analysis is quite accurate up to the point beyond which the system thrashes. It is shown that the variability of transaction size has a major effect on the degree of lock contention, since both ηc and W1 are affected by this distribution. A theoretical justification for Tay's rule of thumb that ηc should be smaller than 0.7 to avoid thrashing is provided. It is shown that 2PL is susceptible to a cusp catastrophe. Sources of instability are identified, and methods for load control to avoid thrashing are suggested.