Persistence + Undoability = Transactions

Authors: Scott M. Nettles and Jeannette M. Wing

Appears in Proceedings of Hawaii International Conference on Systems Science 25, January 1992. Also CMU-CS-91-173, August 1991.

The full text of this paper is here (in PostScript).


Persistence means objects live potentially forever. Undoability means that any change to a program's store can potentially be undone. In our design and implementation of support for single-threaded nested transactions in Standard ML of New Jersey (SML/NJ), we provide persistence and undoability as orthogonal features and combine them in a simple and elegant manner.

We provide support for persistence through an SML interface that lets users manipulate a set of persistent roots and provides a save function that causes all data reachable from the persistent roots to be moved into the persistent heap. We implement the interface through simple extensions to SML's generational garbage collector and maintain the persistent heap using CMU's Recoverable Virtual Memory system.

We provide support for undoability through an SML interface that exports two functions: checkpoint, which checkpoints the current store, and restore, which undoes all changes made to the previously checkpointed store. The implementation takes advantage of the simple runtime representation of data in SML and, as for persistence, extends the existing garbage collector scheme. SML's ``mostly'' functional nature allows us to implement this abstraction without undue performance penalty. Finally, we combine these capabilities to support single-threaded nested transactions by defining a higher-order function {\em transact} that guarantees the permanence of effects of committed transactions. We succinctly define transact completely in terms of the interfaces for persistence and undoability. Unlike other transaction-based programming languages like Argus or Avalon/C++, we need not add new control structures; moreover, we handle aborts of nested or top-level transactions using SML's exception mechanism.

  • Venari project home page.