Tech Report CS-95-22

On the use of Asynchrony in achieving Extensibility and High Performance in an object Storage System

David E. Langworthy

July 1995


An object store provides persistence for an object-oriented database or a special-purpose application such as CAD or hypermedia. In this thesis we examine the architecture of an object store in light of the following developments: the cost of network latency is increasing rapidly in relation to other I/O costs, users demand increased availability without the added cost of redundancy, and new application domains require specialized secondary search structures for high performance.

We determined that these problems could not be solved within any existing object store architecture: solving all of them required fundamental changes in the design of the object store. We present a novel architecture which takes advantage of asynchrony to alleviate latency problems, increase availability, and enable extensibility. We analyze the performance of our prototype to demonstrate the feasibility of such an approach.

Our asynchronous cache-coherency protocol in combination with client disk caching greatly reduces the cost of network latency. However, without the correct invalidation protocol, an unacceptable number of aborts results. We experimentally evaluate several invalidation protocols and introduce a new protocol that provides both low network overhead and fewer aborts.

We introduce a recovery algorithm that improves on the popular and efficient write-ahead logging. No-undo, no-redo write-ahead logging requires no updates to the database partition during recovery, reducing recovery to a single analysis scan of the log. The redos are applied on demand as the objects are read or asynchronously after recovery.

Our novel architecture allows new secondary storage structures to extend the client interface. The new structure is encapsulated in a storage class. The storage class abstraction integrates the new structure with transaction management to provide semantically consistent atomic transactions.

(complete text in pdf or gzipped postscript)