Recovery
Recovery
P.J. Mc.Brien
Imperial College London
P.J. Mc.Brien (Imperial College London) Recovery 1 / 28
REDO and UNDO
DBMS Architecture
disc
data manager
buffer
manager
memory
recovery manager
scheduler
transaction manager
read✲
write
✛
write✲
read
✛
read ✻ write
❄
flush
fetch ❄
read
write
begin
abort
commit❄
execute
❄
result
reject
delay
✻
P.J. Mc.Brien (Imperial College London) Recovery 2 / 28
REDO and UNDO
Recovery Manager (RM)
protect the DBMS against failures
system failures loss of volatile storage
1 committed transactions written to disc
2 uncommitted transactions not written to disc
OR
3 sufficient information such that (1) and (2) may be met by a
recovery
media failures loss of stable storage
P.J. Mc.Brien (Imperial College London) Recovery 3 / 28
REDO and UNDO
Enhanced Data Manager Architecture
data
disc
log
disc
data manager
cache
manager
memory
log data
recovery manager recover✛
read✲
write
✻ ✻
write✲
read
✛
read
✻
write
❄
flush
fetch ❄
read
write
begin
abort
commit
❄
Need to cache log as well
P.J. Mc.Brien (Imperial College London) Recovery 4 / 28
REDO and UNDO
Need to REDO
data
disc
b56
b34
b67
log
disc
data manager
cache
manager
memory
log data
recovery manager
scheduler
b1, r1[b56], w1[b56], r1[b34], w1[b34], c1
read✲
write
✻ ✻
❄
✻
✲
✛
✻
❄❄
LOG b1
REDO w1[b56, cash=84340.45]
REDO w1[b34, cash=18900.67]
LOG c1
REDO required if committed transactions not in stable storage
must write all REDO to log before commit of transaction
P.J. Mc.Brien (Imperial College London) Recovery 5 / 28
REDO and UNDO
Need to UNDO
data
disc
b56
b34
b67
log
disc
data manager
cache
manager
memory
log data
recovery manager
scheduler
b1, r1[b56], w1[b56]
read✲
write
✻ ✻
❄
✻
✲
✛
✻
❄❄
LOG b1
UNDO w1[b56, cash=94340.45]
UNDO w1[b34, cash=8900.67]
LOG c1
UNDO required if non-committed transactions in stable storage
Must flush UNDO to log before corresponding write to data
P.J. Mc.Brien (Imperial College London) Recovery 6 / 28
REDO and UNDO
Quiz 1: Contents of Data Disc After a Transaction
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
branch 1
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
branch 2
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
branch 3
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
branch 4
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
What must the contents of the branch table on the data disc be
after the transaction commits?
A
4
B
1 or 4
C
1 , 3 or 4
D
1 , 2 , 3 or 4
P.J. Mc.Brien (Imperial College London) Recovery 7 / 28
REDO and UNDO
Quiz 2: Contents of Log Disc After a Transaction
Data Disc Before Transaction
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
Data Disc At Commit Time
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
What must be on the log disc after commit time?
A
REDO r56
REDO r34
UNDO r56
UNDO r34
B
REDO r56
UNDO r34
C
UNDO r34
D
REDO r56
P.J. Mc.Brien (Imperial College London) Recovery 8 / 28
REDO and UNDO Logs
Before and after images
before image
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
⇓
w1[b56]
⇓
branch
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
after image
before image allows RM to
undo w1[b56]
after image allows RM to
redo w1[b56]
P.J. Mc.Brien (Imperial College London) Recovery 9 / 28
REDO and UNDO Logs
Database Logs
LOG b1
REDO w1[b56, cash=84340.45]
REDO w1[b34, cash=18900.67]
LOG c1
LOG b1
UNDO w1[b56, cash=94340.45]
UNDO w1[b34, cash=8900.67]
LOG c1
LOG b1
UNDO w1[b56, cash=94340.45]
REDO w1[b56, cash=84340.45]
UNDO w1[b34, cash=8900.67]
REDO w1[b34, cash=18900.67]
LOG c1
P.J. Mc.Brien (Imperial College London) Recovery 10 / 28
REDO and UNDO Logs
What must a complete REDO/UNDO log contain?
Must contain
REDO information for each update
UNDO information for each update
commit of each transaction
Might contain
begin of each transaction
can be inferred from first REDO/UNDO
presence useful to stop search of UNDO records
abort of each transaction
can be inferred from lack of commit
presence useful to indicate UNDO already done
P.J. Mc.Brien (Imperial College London) Recovery 11 / 28
REDO and UNDO Logs
Rules for log and data updates
write ahead logging (WAL)
Redo rule
commit → flush log of transaction to disc
never respond to scheduler before log written
Undo rule:
flushing uncommitted data → flush log of operations
P.J. Mc.Brien (Imperial College London) Recovery 12 / 28
REDO and UNDO Recovery Procedure
Basic Recovery Procedure
initial
state
⇒ wv[o1], cv , wx[o2], wy[o1], cy, wz[o2] ⇒
final
state
1 UNDO → Scan back through the log
Collect set of committed transactions C = {v, y}
Collect set of incomplete transactions I = {x, z}
Perform UNDO for any transaction in I = wz [o2], wx[o2]
2 REDO → Scan forward through the log
Perform REDO for any transaction in C = wv[o1], wy [o1]
final
state
⇒ UNDO(wz[o2]),UNDO(wx[o2]),REDO(wv[o1]),REDO(wy[o1]) ⇒
recovered
state
P.J. Mc.Brien (Imperial College London) Recovery 13 / 28
REDO and UNDO Recovery Procedure
Example of Recovery
Log
LOG b4
LOG b1
UNDO w1[b56, cash=94340.45]
REDO w1[b56, cash=84340.45]
LOG b2
UNDO w2[b34, cash=10900.67]
REDO w2[b34, cash=8900.67]
UNDO w2[b67, cash=34005.00]
REDO w2[b67, cash=36005.25]
LOG b7
LOG c2
UNDO w1[b34, cash=8900.67]
REDO w1[b34, cash=18900.67]
UNDO w7[b67, cash=36005.25]
REDO w7[b67, cash=37005.25]
LOG c7
LOG c4
Disc Before Recovery
branch
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
Disc After Recovery
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 37005.25
P.J. Mc.Brien (Imperial College London) Recovery 14 / 28
REDO and UNDO Recovery Procedure
Omitting the REDO Log
If no REDO records kept
must flush committed transactions to data disc
1 C = ∅,D = ∅
2 Scan the log backwards from the end.
3 commit entry → add to C
4 undo entry for member of C → add object to D without making
changes to the data.
5 perform undo entry for object not of member D
P.J. Mc.Brien (Imperial College London) Recovery 15 / 28
REDO and UNDO Recovery Procedure
Omitting the Undo Log
If no UNDO records kept
transaction must never write uncommitted data
add fix command between RM and CM to stop CM flushing data
commit is followed by flush or unfix of fixed objects
Omitting UNDO and REDO
atomic commit → out of place updating
P.J. Mc.Brien (Imperial College London) Recovery 16 / 28
REDO and UNDO Recovery Procedure
Quiz 3: Contents of Disc Before Commit if no UNDO log
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
branch 1
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
branch 2
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
branch 3
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
branch 4
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
What must the contents of the branch table on disc be before the
transaction commits?
A
1
B
1 or 4
C
4
D
1 , 2 , 3 or 4
P.J. Mc.Brien (Imperial College London) Recovery 17 / 28
REDO and UNDO Recovery Procedure
Quiz 4: Contents of Disc After Commit if no REDO log
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
branch 1
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
branch 2
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
branch 3
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
branch 4
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
What must the contents of the branch table on disc be after the
transaction commits?
A
1
B
1 or 4
C
4
D
1 , 2 , 3 or 4
P.J. Mc.Brien (Imperial College London) Recovery 18 / 28
Checkpointing Definition
Checkpointing
. . . , wx[o1] ⇒
random
state
⇒ cp ⇒ known
state
⇒ wy[o1], . . .
Forces the database into some known state
Recovery limited to only look back to checkpoint (or a ‘bit’ before!)
speeds the recovery operation
limits the size of log
The more consistent this known state
the easier it is to recover
the longer it takes to perform the checkpoint
P.J. Mc.Brien (Imperial College London) Recovery 19 / 28
Checkpointing Types of Checkpointing
Commit Consistent Checkpoint
Generating a Commit Consistent Checkpoint
1 Stop accepting new transactions
2 Finish existing transactions.
3 Flush all dirty data cache objects to disc.
4 Write a checkpoint to stable log.
recovery now only needs to scan back to cp in log ✔
possible long hold-up at checkpoint ✖
P.J. Mc.Brien (Imperial College London) Recovery 20 / 28
Checkpointing Types of Checkpointing
Cache Consistent Checkpoint
Generating a Cache Consistent Checkpoint
1 Suspend all transactions
2 Flush all dirty cache objects to disc
3 Write a checkpoint + active transactions to stable log
Recovery from Cache Consistent Checkpoint records
1 perform UNDOs of non-committed transactions back to cp
2 perform UNDO of non-committed transactions before cp if they
were active at cp
3 perform REDOs of committed transactions after cp
could still have delay whilst flushing cached objects
P.J. Mc.Brien (Imperial College London) Recovery 21 / 28
Checkpointing Types of Checkpointing
Worksheet: Cache Consistent Checkpoint
LOG b7
UNDO w7[b67, cash=34005.25]
REDO w7[b67, cash=37005.25]
LOG b2
UNDO w2[b34, cash=10900.67]
REDO w2[b34, cash=8900.67]
LOG b6
UNDO w6[a101, rate=5.25]
REDO w6[a101, rate=6.00]
LOG b1
UNDO w1[b56, cash=94340.45]
REDO w1[b56, cash=84340.45]
LOG a7
LOG cp{1, 2, 6}
…
…
UNDO w6[a119, rate=5.50]
REDO w6[a119, rate=6.00]
LOG c6
UNDO w2[b67, cash=34005.00]
REDO w2[b67, cash=36005.25]
LOG b8
LOG c2
UNDO w1[b34, cash=8900.67]
REDO w1[b34, cash=18900.67]
LOG b9
UNDO w9[b67, cash=36005.00]
REDO w9[b67, cash=20000.00]
LOG c9
P.J. Mc.Brien (Imperial College London) Recovery 22 / 28
Checkpointing Types of Checkpointing
Fuzzy Checkpointing
Generating a Fuzzy Checkpoint
1 Suspend all transactions
2 Flush any dirty cache objects to disc not flushed in previous cp
3 Write a checkpoint + active transactions to stable log
Recovery from Fuzzy Checkpoint records
Recovery works like cache consistent checkpoint, but working with
penultimate cp
1 perform UNDOs of non-committed transactions back to
penultimate cp
2 perform UNDO of non-committed transactions before penultimate
cp if they were active at cp
3 perform REDOs of committed transactions after penultimate cp
P.J. Mc.Brien (Imperial College London) Recovery 23 / 28
Media Failures
Media Failures: Mirroring (RAID-1)
data
disc1
log
disc1
data
disc2
log
disc2
cache
manager
read✲
write
✻
❄
✻
❄
Keep more than one active copy of data and log
Writes sent to both
Read from either
P.J. Mc.Brien (Imperial College London) Recovery 24 / 28
Media Failures
Media Failures: Dumping
data
disc
log
disc
data
tape
log
tape
cache
manager
read✲
write
✻
dump ✻
✻
dump ✻
‘tape’ might also be a external file server, removable HD, etc.
To use normal OS backup procedure
DBMS must not be still running
raw partition must not be used
P.J. Mc.Brien (Imperial College London) Recovery 25 / 28
Media Failures
Checkpoints and Dumps
Dump must do a checkpoint
Restore involves:
1 copy tape to disc
2 undo transactions active at the archive time
3 redo transactions that committed after the archive
commit consistent checkpoint obvious choice
P.J. Mc.Brien (Imperial College London) Recovery 26 / 28
Media Failures
Media Failures: Archive Database
active
data
disc
log
disc1
archive
data
disc
log
disc2
cache
manager
read✲
write
✻
❄
✻
❄
mirror log, but only have one active database
periodically archive updates onto archive database
failure of active database disc involves restore of archive database
using logs
P.J. Mc.Brien (Imperial College London) Recovery 27 / 28
Media Failures
THE END
Content of the course is what has been presented in the lectures
Revise by reviewing worksheets and courseworks
2011 exam papers onwards set to current syllabus
Older exam questions mostly apply, but there is more emphasis on
RA and SQL, less on concurrency.
P.J. Mc.Brien (Imperial College London) Recovery 28 / 28
REDO and UNDO
Logs
Recovery Procedure
Checkpointing
Definition
Types of Checkpointing
Media Failures