Stasis: Flexible Transactional Storage

An increasing range of applications requires robust support foratomic, durable and concurrent transactions. Databases provide thedefault solution, but force applications to interact via SQL and toforfeit control over data layout and access mechanisms. In principle,a specialized database stack could be built for each application, butsuch approaches have proven to be impractical. We argue there is agap between DBMSs and file systems that limits designers ofdata-oriented applications.Stasis is a storage framework that incorporates ideas from traditionalwrite-ahead logging algorithms and file systems. It providesapplications with flexible control over data structures, data layout,robustness and performance. Stasis enables the development ofunforeseen variants on transactional storage by generalizingwrite-ahead logging algorithms. Instead of implementing support foreach new storage system from scratch, I have extended Stasis toprovide specialized storage mechanisms to a wide variety ofapplications. It now provides cleaner semantics than similarapplication-specific approaches would, with significantly less sourcecode than would be required by multiple separate storageimplementations. In addition to the conventional write-ahead loggingalgorithms that Stasis was designed for, it now provides support forlarge objects, and for log-structured indexes. A number of otherextensions, such as distributed recovery algorithms and snapshot-basedrecovery are under development.This dissertation describes the range of data models and programarchitectures that have been commonly used in the past, and arguesthat Stasis is sufficiently general to support most storageapplications. It then turns to a description of Stasis' high-levelapplication interfaces and APIs that are designed to allowapplications to add their own transactional data structures toStasis. The performance of a number of such extensions is evaluated,showing that Stasis performs favorably relative to existing systems.The dissertation then turns to a careful definition of Stasis'recovery algorithms, and provides a novel generalization of ARIES, thede facto standard approach to transactional storage. Thegeneralization is particularly promising in the context of distributedsystems. Finally, it presents Stasis' lower-level interfaces,providing systems developers and application designers with theability to tailor high-level transactional primitives to new types ofstorage hardware and operating system primitives. To the greatestextent possible, the ideas presented within are composable, allowingStasis' simple implementation to support an unusually wide range ofstorage architectures