form) the page containing the old and new states for each updated datum.
This mechanism (called physical recording ) guarantees that each single
operation can be undone and that the pair of do
undo operations is idem-
potent, i.e. if needed, can be re-executed an arbitrary number of times
without changing the final database state.
Physical recording is managed by reducing operations of arbitrary com-
plexity to simple operations, i.e. operations on objects of a single class that
may cause a simple state transition for a single object in the class. This
recording technique is efficient when (possibly complex) computations
usually cause limited changes in the system's state. If, on the other hand,
quite simple operations can cause significant changes in the system's state
(i.e. require recording a huge number of old state
new state pairs), this
recording mechanism turns out to be inadequate.
A different approach (see, for example, Alvisi and Marzullo (1998)) to the
problem of saving computation states and recovering after a failure is called
logical recording . It mainly consists in a different way of representing
complex operations, which are expressed in terms of the external events
that trigger the state transition (the cause of an operation), thus reducing
the need to store large amounts of information when significant changes
take place in the system's state. Complex operations are recorded by simply
describing how they are invoked, i.e. they are represented by their name,
together with the set of actual parameters in the invocation of the operation,
and a reference to the object on which the operation is invoked.
The undo and redo functions must be idempotent, i.e. the same operation
can be undone or redone an arbitrary number of times, always producing the
same correct state (i.e. the state before or after the operation was executed).
This property is especially important in case the recovery process fails: it
allows the repetition of the restart procedure an arbitrary number of times
without affecting its final outcome.
The following features characterize the RECAP framework:
Physical recording of an application's stable states.
Physical and logical recording of state transitions.
State recovers after a crash.
redo of operations that cause state transitions.
The test application implements the classical Tower of Hanoi puzzle. We are
given three pegs, let's call them source , auxiliary and destination . Initially,
a number of discs (usually 8 or 10) are stacked in decreasing size on the
source peg, giving it a tower.
The objective is to transfer the entire tower to peg destination , moving
only one disc at a time and never a larger one onto a smaller. Discs can be