MLR : A Recovery Method for Multi-Level Systems
Abstract:
A multi-level system using locks permits restrictive
low level locks of a sub-transaction to be replaced with less restrictive
high level locks when sub-transactions commit, enhancing concurrency.
In a multi-level system, subtransactions can be undone via high level compensation
actions rather than by restoring a prior lower level state. MLR
(Multi-Level Recovery) aims at recovery by using a single
log. Whenever a subtransaction commits, its undo record
is logged for compensating the subtransaction at the high level at the
time of recovery.
Layered Architecture:
-
Each layer realizes a set of abstract states,
each represented by a number of lower layer states.
-
Each layer sees state transitions in the form of
atomic operations provided by the next lower layers and uses them
to provide atomic operations to the next higher layer.
For example, consider a object oriented system, which
contains an object manager layer built over page layer which is further
built over OS layer. The functions provided by the OS layer
such as memory an I/O manipulation functions, etc., are used by page layer
and further the functions provided by page layer such as read page, write
page, etc., are used by object layer.
Multi-Level Transactions:
A multi-level transaction can be viewed as an abstraction
of subtransactions. For example, if we want to update
an object, then first we have to retrieve its page number, fetch
the page, update the object within the page and write back
the page. Each thing here is a subtransaction. Thus, updating
an object is a multi-level transaction which can be viewed as number
of subtransactions.
Considering another example of multi-level
transaction, we can view the transfer of money from one account (say A)
into another bank account (say B). This can be simply viewed as two
subtransactions, first deducting amount from A and then adding the
amount at B. The subtransaction of deducting amount
from A can further viewed as a series of subtransactions, viz., getting
the corresponding page, checking whether there is sufficient amount,
modifying the amount, writing back the page. Similarly, adding the
amount to B can also be viewed as a series of subtransactions.
Multi-Level Systems:
-
A multi-level system exploits the layers of abstraction
common in most systems to enhance concurrency.
-
A layer can be defined as a level of multi-level
system and it can choose among which of the lower layer states that realize
a desired a higher layer state.
-
Concurrency control and recovery are concerned with
the highest level.
-
Concurrency control need only ensure the high level
serializability.
The lowest layer directly provides abstractions upon
which succeeding layers can be built. Each level provides a system
of services to the implementor. A layer can be defined by the implementor
as a level. Such layers are said to be Multi-Level Transaction
Layers. The implementor can also ignore these services and use recoverable
abstractions at lower levels. These layers are said to be Nested Transaction
Layers and these are not levels.
Each operation say OPi+1
in level Li+1 can be viewed as a set of OPi
s in Level Li.
Compensation Transactions:
-
An operation OPi+1-1 is said
to be inverse operation of OPi+1, that is it undoes all
the effects of OPi+1.
-
An OPi+1-1 can
be viewed as a set of OPi-1 s for all
OPi s which comprise OPi+1.
-
A compensation transaction consists of these inverse
operations.
Concurrency Control in ML Systems:
-
Strict 2PL is used at each level for concurrency
control.
-
The locks acquired at each level are sufficient
for both serializability and execution of inverse operations at that level,
if needed for recovery.
-
Low level locks LOCKi s are not
released until the high level OPi+1 is completed and the high
level locks LOCKi+1s are acquired.
Recovery:
Recovery is done to ensure the following properties
to the system state.
-
Operation Consistency (OC) - states that
an operation has either been executed and all its results are reflected
in the system state or it is not executed and none of its results are reflected
in the system state.
-
Determinable Execution (DE) - states that
an operation if logged as part of a committed transaction and if
is not reflected in the system state, then a redo operation is performed
for that operation. Similarly, if it is a part of an aborted transaction
in the logs, then an undo operation is to be performed to purge the
system state of the effects of this aborted transaction.
Higher Level Undo Recovery is
performed in ML systems which is explained as follows. For this ,
this lower levels of the system are recovered before higher levels.
Recovery prior to Li will be responsible for guaranteeing that:
-
all logged operations have been executed, hence
that operations are DE
-
all lower level interrupted transactions have been
rolled back, and hence the system is Li OC
-
only OPj s, for j > i are in need
of undo and those are indicated on the log as incompletely executed subtransactions.
The process of recovery in ML systems can be better
understood from the following figure.
First, the redo for all the operations are
done to reflect all the logged operations. Then, where an abort/crash
occurred, from there, first the operations at lowest level which are interrupted
are undone. In the above figure, after OP03, now
there are no interrupted transactions at level L0. At
Level L1, OP12 is interrupted. To undo
it, OP03 at level L0 is undone as it is a subtransaction
of it. This is undone by executing a compensation transaction for
OP03. Now, there are no interrupted operations at
level L1. Now, the recovery procedure goes to L2.
Like this, the lower levels are recovered before higher levels.
Logging for MLR Recovery
Forward Operations:
-
MLR logs forward operations of transactions.
-
As each transaction completes, a log record is added
to the transaction chain of records.
-
When subtransaction commits, its commit record links
it to the log records of its parent transaction.
-
When writing a commit log record for a transaction
or a subtransaction, its inverse opearation is also maintained in
the UNDO field of the operation part, which can be used for recovery.
For example, the following figure shows the
log records for two parallelly active sutransactions. One subtransaction
has committed and becomes linked with the parent(top level) transaction.
The other has not yetr committed and hence is distinguishable from an active
top level transaction.
Interrupted Transactions:
-
MLR rolls back interrupted transactions (that
cannot finish normally) at all levels in the same way.
-
The constituent (completed) subtransactions
of each transaction are compensated.
-
Undo Recovery process is logged with compensation
log records.
-
During rollback, a transaction's chain of log records
is scanned backwards and each opearation is undone using compensation opearation
stored in the undo part of the log record and a Compensation Log
Record (CLR) is written.
-
CLR's are never undone. The pointer to be next undone
is copied into the CLR. This permits undo recovery to proceed from the
point where it left off should a crash occur during recovery.
Undoing Completed Subtransactions:
-
For a completed subtransaction, a seperate compensate
transaction is initiated.
-
CLR is written containing the details of the compensation
transaction as part of the parent log record.
References
David b. Lomet
MLR : A Recovery Method for Multi-Level Systems
In Proceedings of the ACM SIGMOD 1992
Page created by
Sree Hari Nagaralu
(hari@cse.iitb.ernet.in)
Kommuri Naga Kishore
(nagas@cse.iitb.ernet.in)