\documentstyle[fullpage,10pt]{article}
\title{Alternative System R Checkpointing}
\author{Greg Hudson}
\begin{document}
\maketitle

The System R database manager requires that no low-level RSS
operations be going on when a checkpoint takes place, but it does
allow the system to be in the middle of a high-level transaction when
a checkpoint takes place.  This allows for more frequent checkpoints,
but complicates the crash recovery mechanism.  Quiescing the system at
the transaction level would simplify the crash recovery mechanism, but
would force less frequent checkpoints due to the delay caused by a
checkpoint.

The actual System R database manager will checkpoint in the middle of
transactions, as long as no low-level storage operations are going on.
When a checkpoint occurs, it writes out a record listing all of the
transactions going on at the time of the checkpoint.  If there is a
crash after the checkpoint, the crash recovery procedure can look at
the checkpoint record and the log entries written since the checkpoint
to determine what operations need to be done and undone.

The recovery mechanism must deal with five different possibilities for
transactions starting and ending before or after the checkpoint, as
dicussed on page 7-115 of the Gray paper.  One of these cases is
especially complicated: if a transaction began before the checkpoint,
and ended after the checkpoint, the recovery mechanism must undo the
transaction back to the last transaction save point and then redo the
transaction to the commit point.

If the checkpoint mechanism instead quiesced the system at the
transaction level, preventing any new transactions from taking place
until the checkpoint finishes, then the recovery mechanism doesn't
have to worry about transactions taking place when the last commit
took place.  There does not need to be a commit record; the recovery
mechanism need simply scan through the log for committed transactions
since the last checkpoint, and redo those transactions.  Transactions
which started after the commit point but were not committed need not
be addressed, since the shadow files will be in the correct state with
regard to those transactions.  This plan eliminates the need for
transaction save points; indeed, the recovery mechanism will not need
to use undo facilities at all, only redo facilities.

Unfortunately, this plan also makes checkpoints a very expensive
operation, one which can cause a long outage.  Quiescing the system at
the transaction level requires blocking new transactions for an
uncontrolled length of time, because there is no limit on transaction
time.  For some applications, where transactions are normally very
short, this won't be noticeable under normal conditions, but for other
applications, such as when transactions commonly involve expensive
operations such as searching and sorting, quiescing the system at the
transaction level will be prohibitively expensive.

\end{document}

