Value-cognizant speculative concurrency control for real-time databases

摘要

Speculative Concurrency Control (SCC) is a new concurrency control approach, especially suited for real-time databases. SCC capitalizes on the availability of unused resources in the system to ensure that serializable executions are discovered and adopted as early as possible, thus increasing the likelihood of the timely commitment of transactions with strict timing constraints. Using SCC, several shadow transactions execute on behalf of a given uncommitted transaction so as to protect against the hazards of blockages and restarts, which are characteristics of Pessimistic and Optimistic Concurrency Control algorithms, respectively. We describe the basic Order-Based SCC (SCC-OB) algorithm and demonstrate its excessive (exponential) use of shadowing. Next, we present SCC-kS, a more practical class of SCC algorithms that operate under a limited resources assumption. SCC-kS does not allow more than k shadows to execute on behalf of any given uncommitted transaction in the system. SCC-kS allows the system to constrain the level of speculation that each transaction is allowed to perform. This provides a straightforward mechanism for trading resources for timeliness. SCC-kS is proved correct by showing that it only admits serializable histories. Next, SCC with Deferred Commit (SCC-DC) is proposed. SCC-DC is a value-cognizant protocol because it utilizes information about transactions, such as deadline and criticalness, to improve timeliness through the controlled deferment of transaction commitments. We conclude our paper with an evaluation of the performance of SCC algorithms. We present simulation results, which show that SCC-based algorithms provide significant performance gains over other widely used concurrency control protocols for real-time databases.