Probabilistic Models of Database Locking

Locking, although essential in concurrent database processing, also impairs concurrency, and the latter efl~ct is quantified here. The difficult feature in locking is the interference phenomenon, by which we mean that if a particular item in the database is locked, which is true in our model for all constituent items of all transactions undergoing processing, then all arriving transactions requiring this particular item are blocked. The interference phenomenon is exactly modeled and exact formulas for equilibrium database performance, such as mean concurrency and throughput, and efficient algorithms for their computation are obtained. Formulas for large databases are derived and proved to be asymptouc; this formula is insightful, and found to fit well to exact solutions. The probabilistic model is a Markov process with combinatorial quantities as transition rates. This model is tractable because of the time reversibility of the equilibrium Markov process. In a database with Nitems and p transaction classes, the probabilistic model has O(N p) states, time reversibility reduces the calculations to evaluating the sum of O(N p) terms, the recurrence formulas that are derived here require O(Np) multiplications, and, finally, the asymptotic formula requires negligible computation.