CHAPTER 5

Database Recovery Techniques

 Database Recovery
Purpose of Database Recovery
 To bring the database into the last consistent state,
which existed prior to the failure.

 To preserve transaction properties (Atomicity,

Consistency, Isolation and Durability).

2
 Types of Failure
 The database may become unavailable for use due to:
 Transaction failure: Transactions may fail because of

incorrect input, deadlock, incorrect synchronization.

 System failure: System may fail because of

addressing error, application error, operating system

fault, RAM failure, etc.
 Media failure: Disk head crash, power disruption, etc.

3
 Transaction Log
 For recovery from any type of failure data values prior to
modification (BFIM - BeFore Image) and the new value
after modification (AFIM – AFter Image) are required.

O p e r a tio n D a ta ite m B F IM A F IM
B e g in
W rite X X = 100 X = 200
B e g in
W Y Y = 50 Y = 100
R M M = 200 M = 200
R N N = 400 N = 400
End

4
 Data Update
 In-place update: The disk version of the data item is
overwritten by the cache version.
 Immediate Update: As soon as a data item is
modified in cache, the disk copy is updated.
 Deferred Update: after a transaction ends its
execution or after a fixed number of transactions )
 Shadow update: The modified version of a data
item does not overwrite its disk copy but is written at
a separate disk location. BFIM and the AFIM can be
kept on disk; hence, it is not necessary to maintain a
log.

5
 Data Caching
 Data items to be modified are first stored into database
cache by the Cache Manager (CM) and after
modification, they are flushed (written) to the disk.
 The flushing is controlled by dirty and Pin-Unpin
bits.
 Dirty bits=1: Indicates that the data item is

modified. 0, when a page is first read from the

database disk into a cache buffer. Data are flushed
(written) to the disk only if its dirty bit is 1.
 Pin-Unpin bits: a page in cache is pinned (bit

value=1)

6
 Transaction Roll-back (Undo) and Roll-
Forward (Redo)
 To maintain atomicity, a transaction’s operations are
redone or undone.
 Undo: Restore all BFIMs on to disk (Remove all

AFIMs).
 Redo: Restore all AFIMs on to disk.

 Database recovery is achieved either by performing

only Undos or only Redos or by a combination of
the two.

7
 Write-Ahead Logging
 When in-place update (immediate or deferred) is used then
log is necessary for recovery .
 This is achieved by Write-Ahead Logging (WAL) protocol.
WAL states that:
 For Undo: Before a data item’s AFIM is flushed to the

database disk (overwriting the BFIM) its BFIM must be

written to the log and the log must be saved on a stable
store (log disk).
 For Redo: Before a transaction executes its commit

operation, all its AFIMs must be written to the log and

the log must be saved on a stable store.

8
 Checkpointing
 A [checkpoint] record is written into the log
periodically at that point when the system writes
out to the database on disk all DBMS buffers that
have been modified.
 As a consequence of this, all transactions that have
their [commit, T] entries in the log before a
[checkpoint] entry do not need to have their
WRITE operations redone in case of a system
crash, since all their updates will be recorded in
the database on disk during checkpointing.

9
 Checkpointing Cont.
 Advantages of using Checkpoints :

 It speeds up data recovery process.

 Checkpoint records in log file is used to prevent

unnecessary redo operations.

10
 Checkpointing Cont.
 The following steps defines a checkpoint operation:
1. Suspend execution of transactions temporarily.
2. Force write modified buffer data to disk.
3. Write a [checkpoint] record to the log, save the
log to disk.
4. Resume normal transaction execution.

11
 Recovery Scheme
 Deferred Update (No Undo/Redo)
 The data update goes as follows:

 A set of transactions record their updates in the

log.
 At commit point under WAL scheme, these

updates are saved on database disk.

 Before reaching commit, all transaction updates

are recorded in the local transaction workspace

(or buffers).

12
 Recovery Techniques Based on Defered
Update…
 During commit, the updates are first recorded
persistently in the log and then written to the database.
 If a transaction fails before reaching its commit point, it
will not have changed the database in any way, so
UNDO is not needed.
 It may be necessary to REDO the effect of the
operations of a committed transaction from the log,
because their effect may not yet have been recorded in
the database. Hence, deferred update is also known as
the NO-UNDO/REDO algorithm.

13
 Example

An example of
recovery using
deferred update in a
single user
environment

14
 Deferred Update with concurrent users
 This environment requires some concurrency control
mechanism to guarantee isolation property of transactions.
 In the system recovery, transactions which were recorded in the
log after the last checkpoint were redone.

15
 Example

An Example of recovery using deferred update with concurrent transaction

16
Deferred Update with concurrent users
Cont.
 Two tables are required for implementing this
protocol:
 Active table: All active transactions are entered in
this table.
 Commit table: Transactions that have been
committed are entered in this table.

 During recovery, all transactions of the commit table

are redone and all transactions of active tables are
ignored since none of their AFIMs reached the
database.

17
Recovery Techniques Based on Immediate
Update
 Undo/redo Algorithm
 In this algorithm AFIMs of a transaction are
flushed to the database disk under WAL before it
commits.
 However, these operations are typically recorded
in the log on disk by force writing before they are
applied to the database, making recovery still
possible.
 For this reason the recovery manager undo all
transactions during recovery.

18
Recovery Techniques Based on Immediate Update
Cont.
 If a transaction fails after recording some changes in
the database but before reaching its commit point, the
effect of its operations on the database must be
undone; that is, the transaction must be rolled back.
 In the general case of immediate update, both undo
and redo may be required during recovery.
 This technique, known as the UNDO/REDO
algorithm, requires both operations.

19
Recovery Techniques Based on Immediate
Update Cont.

 Undo/Redo Algorithm (Single-user environment)

 Note that at any time there will be one transaction in
the system and it will be either in the commit table
or in the active table.
 The recovery manager performs:

 Undo of a transaction if it is in the active

table.
 Redo of a transaction if it is in the commit

table.

20
UNDO/REDO Recovery Based on Immediate
Update with Concurrent Execution
 Use two lists of transactions maintained by the
system: the committed transactions since the last
checkpoint and the active transactions.
 Undo all the write_item operations of the active
(uncommitted) transactions, using the UNDO
procedure.
 Redo all the write_item operations of the committed
transactions from the log, in the order in which they
were written into the log.

21
 Shadow Paging
 Does not require the use of a log in a single user environment.
 In a multiuser environment, a log may be needed for the
concurrency control method..
 AFIM and BFIM are stored in two different places on the disk.

X Y
X' Y'

Database

X and Y: Shadow copies of data items

X' and Y': Current copies of data items
22
 Shadow Paging Cont.
 To manage access of data items by concurrent
transactions, two directories (current and shadow) are
used.
 The directory arrangement is illustrated below. Here a page
is a data item.

An example of
shadow paging

23
 Shadow Paging Cont.
 To recover from a failure during transaction
execution, it is sufficient to free the modified
database pages and to discard the current directory.
 The state of the database before transaction
execution is available through the shadow directory,
and that state is recovered by reinstating the shadow
directory.
 Committing a transaction corresponds to discarding
the previous shadow directory.

24
 Recovery in Multidatabase system
 Here, transaction commits only when all these multiple
nodes agree to commit individually the part of the transaction
they were executing.

 If any one of these nodes fails or cannot commit the part of

the transaction, then the transaction is aborted.

 Each node recovers the transaction under its own recovery

protocol.

25
 Recovery in multidatabase system(cont…)
 A global recovery manager or coordinator is needed to
maintain information needed for recovery
 The coordinator usually follows a Two-phase commit
protocol :
 Phase1: the coordinator sends a “prepare for commit”
message to each participant to get ready for committing the
transaction
 Each participating DB receiving that message will force

write log records to disk and send “ready to commit” or

“OK” signal to the coordinator .
 If the coordinator does not receive reply from a DB within

certain time out interval, it assumes a “not ok” response

26
 Recovery in Multidatabase system Cont.
 Phase 2:If all participating databases reply ok, the
transaction is successful and the coordinator sends a
commit signal to the participating DBs
 Each participating DB completes transaction commit

by writing a [commit] for the transaction in the log

 If one or more of the participating DB or the

coordinator have a “not OK” response, the T has

failed and the coordinator sends a message to rollback
or Undo the local effect of the transaction to each
participating DB.

27
 Exercise

 Consider the log records shown on the next slide by transactions T1,
T2, T3 and T4 with initial values of B=15, C=50, D=40 and E=25.
Using deferred update, show the final values of B, C, D and E after
recovery from failure if the crash occurred after the indicated point.

B C D E
15 50 40 25

28
 Initial values
Continued …
B C D E
[Start_transaction,T1] 15 50 40 25
[write_item,T1,B,12]
[write_item,T1,D,10]
[commit T1]
[checkpoint]
Final values after recovery
[Start_transaction,T3]
[write_item,T3,E,30] B C D E
[commit T3] ? ? ? ?
[Start_transaction,T4]
[write_item,T4,B,18]
[commit T4]
[Start_transaction,T2]
[write_item,T2,C,28]
Crash 29
Thank You!