程序代写代做代考 concurrency Hive cache database Recovery

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