Information Technology Reference
In-Depth Information
transactions should be accepted into the system as soon as possible after a system
crash.
It is possible to implement the undo pass of recovery in such a way that individual
transactions are rolled back in the same manner as in normal transaction processing,
and the undo actions can be executed concurrently with new transactions. In this
method, one or more processes or threads are created to execute the undo passes of
the transactions to be rolled back.
The method will work only if the necessary X locks are first acquired for all of the
backward-rolling transactions. In read-write locking (for the read-write transaction
model), this is easily done by looking at the log records written for the WŒx;
u
;
v
actions. In key-range locking, however, the delete action DŒx;
v
must also log the
next key y of key x, so that a commit-duration X lock on it could be acquired from
the information in the log.
An alternative to acquiring the locks is to use the
C
OMMIT
-LSN
mechanism during
the undo pass of recovery. Here, the undo pass is executed in the original manner, in
a single backward scan of the log and without acquiring any locks. In the analysis
pass of recovery, the
C
OMMIT
-LSN
is set to the
LSN
of the begin-transaction log record
of the oldest active transaction.
New transactions, which have to acquire locks in the normal way, are allowed to
enter the system as soon as the undo pass begins, but a new transaction is allowed
to access page p only if
P
AGE
-LSN
.p/ is less than the
C
OMMIT
-LSN
.If
P
AGE
-LSN
.p/
is greater than the
C
OMMIT
-LSN
, the new transaction must wait for the undo pass of
recovery to finish.
Example 9.7
Assume that transaction T performs an action DŒx;
v
on leaf page p
of a B-tree, where the least key y in the database resides in the page, p
0
,nextto
page p. Then some other transaction commits, and after flushing the log the system
crashes.
As T was active at the time of the crash and had updated page p,wehave
P
AGE
-LSN
.p/ >
C
OMMIT
-LSN
. Hence any new transaction T
0
allowed to the system
during the undo pass is denied access to page p until the undo pass has been
completed.
But assume that page p
0
had no uncommitted updates at the time of the crash, so
that
P
AGE
-LSN
.p
0
/<
C
OMMIT
-LSN
. Recall that when transaction T accessed the page
p
0
so as to determine the key y next to key x, the page p
0
was only read-latched and
not updated.
In the undo pass, the transactions that were active at the time of the crash are
allowed to roll back without holding any locks. Thus, T will roll back and perform
the undo action D
1
Œx;
v
without holding the commit-duration X lock on the next
key y.
A new transaction T
0
can now access page p
0
and perform actions such as IŒx
0
,
DŒy,andRŒx
0
;
z
,wherey>x
0
z
low-key
.p
0
/. If done before T completes
its rollback, these actions were not permitted by the key-range locking protocol
during normal processing. However, none of these actions exhibits an isolation
anomaly.
t
