Modeling and Analysis of a Time-Stamp History Based Certification Protocol for Concurrency Control

Abstract

Concurrency control (CC) can profoundly affect the performance of transaction processing (TP) systems, particularly at high levels of data contention. In optimistic concurrency control (OCC) schemes, the performance is sensitive to the transaction abort rate. The abort probability can be significantly reduced by back-shifting the time-stamp for certification from the time of requesting a commit in order to reduce read-write conflicts. In this paper, we consider a variant of the interval timestamp approach using (limited) time-stamp history information to derive the back-shifted time-stamp dynamically. We develop an analytic model to quantify the performance improvement by comparison with the basic time-stamp certification scheme. Since the committed conflicting transaction may itself be back-shifted, the analytic model needs to estimate the distribution of the backshift of the certification time-stamp in order to determine the probability of successfully back-shifting a transaction requesting commit. We show how this relatively complex protocol can be analyzed using a few simple approximations, validate the analysis through simulations, and determine the range of parameter values for which this approach is most beneficial. © 1991 IEEE