Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions

Download: pdf.

“Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions” by Atul Adya. Ph.D. dissertation, MIT, (Cambridge, MA, USA), Mar. 1999. Also as Technical Report MIT/LCS/TR-786.

Abstract

Current commercial databases allow application programmers to trade off consistency for performance. However, existing definitions of weak consistency levels are either imprecise or they disallow efficient implementation techniques such as optimism. Ruling out these techniques is especially unfortunate because commercial databases support optimistic mechanisms. Furthermore, optimism is likely to be the implementation technique of choice in the geographically distributed and mobile systems of the future.

This thesis presents the first implementation-independent specifications of existing ANSI isolation levels and a number of levels that are widely used in commercial systems, e.g., Cursor Stability, Snapshot Isolation. It also specifies a variety of guarantees for predicate-based operations in an implementation-independent manner. Two new levels are defined that provide useful consistency guarantees to application writers; one is the weakest level that ensures consistent reads, while the other captures some useful consistency properties provided by pessimistic implementations. We use a graph-based approach to define different isolation levels in a simple and intuitive manner.

The thesis describes new implementation techniques for supporting different weak consistency levels in distributed client-server environments. The mechanisms are based on optimism and make use of multipart timestamps. A new technique is presented that allows multipart timestamps to scale well with the number of clients and servers in our system; the technique takes advantage of loosely synchronized clocks for removing old information in multipart timestamps.

This thesis also presents the results of a simulation study to evaluate the performance of our optimistic schemes in data-shipping client-server systems The results show that the cost of providing serializability relative to mechanisms that provide lower consistency guarantees is negligible for low-contention workloads; furthermore, even for workloads with moderate to high-contention workloads, the cost of serializability is low. The simulation study also shows that our mechanisms based on multipart timestamps impose very low CPU, memory, and network costs while providing strong consistency guarantees to read-only and executing transactions.

Download: pdf.

BibTeX entry:

@phdthesis{adya99:_weak_consis,
   author = {Atul Adya},
   title = {Weak Consistency: A Generalized Theory and Optimistic
	Implementations for Distributed Transactions},
   school = {MIT},
   type = {{Ph.D.}},
   address = {Cambridge, MA, USA},
   month = mar,
   year = {1999},
   note = {Also as Technical Report MIT/LCS/TR-786}
}