CONCURRENCY-CONTROL - METHODS, PERFORMANCE, AND ANALYSIS

Standard locking (two-phase locking with on-demand lock requests and b locking upon lock conflict) is the primary concurrency control (CC) me thod for centralized databases. The main source of performance degrada tion with standard locking is blocking, whereas transaction (txn) rest arts to resolve deadlocks have a secondary effect on performance. We p rovide a performance analysis of standard locking that accurately esti mates its performance degradation leading to thrashing. We next introd uce two sets of methods to cope with its performance limitations. Rest art-oriented locking methods selectively abort txns to increase the le vel of concurrency for active txns with respect to standard locking in high-contention environments. For example, the running-priority metho d aborts blocked txns based on the essential blocking principle, which only allows blocking by active txns. The wait-depth-limited (WDL) met hod further minimizes wasted processing by basing abort decisions on t he progress made by a txn. Restart waiting serves as a load-control me chanism by deferring the restart of an aborted txn until conflicting t xns have left the system. These two methods have performance superior to other restart-oriented methods and standard locking in high-content ion environments. In two-phase processing methods an aborted txn may c ontinue its first phase of execution in ''virtual'' mode, that is, wit hout requesting any locks, prefetching data for its second execution p hase. The second execution phase is shorter since no disk I/O is requi red, resulting in a lower effective degree of txn concurrency and less data contention. This method is effective provided access invariance prevails; that is, txns access the same set of objects in the second p hase as they did in the first. The optimistic die method is appropriat e for the first phase and the optimistic kill method for further phase s. Lock preclaiming instead of the optimistic kill method in the secon d phase prevents further restarts, which is a weak point of the optimi stic CC method due to the quadratic effect, that is, the probability o f failed validation increases as the square of txn size. Several two-p hase processing methods are described and shown to outperform restart- oriented locking methods in high-contention environments provided adeq uate hardware resources are available. This tutorial reviews CC method s based on standard locking, restart-oriented locking methods, two-pha se processing methods including optimistic CC, and hybrid methods (com bining optimistic CC and locking) in centralized systems. Its main goa ls are as follows: (i) succinctly specify CC methods of interest; (ii) describe models for performance evaluation of CC methods, including n ew models that alleviate some of the shortcomings of models used in ea rlier studies; (iii) compare the performance of CC methods; (iv) list insights gained from analytic and simulation studies; (v) review metho ds to relieve the level of lock contention: special methods for indice s and aggregate data; modified txn structures; and relaxed levels of c onsistency for queries; (vi) survey performance evaluation studies of CC methods; (vii) illustrate the applicability of basic analytic metho ds to evaluating the performance of CC methods; and (viii) suggest are as of further investigation.