Multiversion concurrency control in objectbased systems

Abstract

Current approaches to enhancing concurrency in database systems have focused on developing new transaction models that typically demand changes to either the atomicity, consistency, or isolation properties of the transactions themselves. Indeed much of this work has been insightful but most of these attempts suffer from being either computationally infeasible or requiring the transaction designer be sufficiently knowledgeable to determine, a priori, how the application semantics must interface with the transaction model (see (Wei88) or (Wei91) for examples). Our approach exploits an object-oriented world and is different than others because the transaction designer is not expected to have intimate application knowledge; this load is placed on the transaction system which must determine, by static analysis, how to maintain database consistency. We adopt an extremely aggressive approach whereby each transaction is given its own copy (version) of all of the objects it needs to execute so it can proceed withoutinterruption from other processes running on the same system. This dissertation describes an overall architectural model to facilitate multiversion objects that are explicitly designed to enhance concurrency. The reader should be aware that version management has been used in the object literature in several ways, most commonly dealing with design issues, but our goal here is related to concurrency control and reliability so care must be taken to ensure the reader is not misled by this overloading of terminology. Within the context of concurrency the key aspects addressed by this thesis are: (1) A new correctness criterion is described that emits more histories than conflict serializability and is computationally tractable; (2) An architectural model is developed to support multiversioning that provides the well-known ACID transaction properties; (3) An optimistic concurrency control algorithm that functions on this architecture is described and demonstrated to be correct with respect to the new correctness criterion; (4) The algorithm is enhanced to examine the history of past versions with the goal of inserting a committing transaction at a time earlier in the sequence when it would have been valid if other, later transactions, had not completed before this one attempted to commit; and (5) Based on static analysis information, algorithms are developed to modify the compiler to generate reconciliation procedures automatically from the initial transaction specification.