View
227
Download
0
Category
Preview:
Citation preview
7/30/2019 Last Trans
1/21
Recovery
A recovery scheme can restore the database to the consistent
state that existed before the failure. It must minimize the time
for which the database is not usable after a crash.
We study two approaches:
log-based recovery, and
shadow-pagingWe assume (initially) that transactions run serially, that
is, one after the other.
7/30/2019 Last Trans
2/21
7/30/2019 Last Trans
3/21
A transaction creates a log record prior to modifying the database.
The log records allow the system to undo changes made by atransaction in the event that the transaction must be aborted.
They also allow the system to redo changes made by a transaction
if the transaction has committed.
If a transaction does not modify the database until it has
committed, it is said to use the deferredmodification
technique.
Ifdatabase modifications occur while the transaction is still
active, the transaction is said to use theimmediatemodification
technique.
7/30/2019 Last Trans
4/21
Deferred Database Modification
This scheme ensures atomicity despite failures byrecording all modifications to log, but deferring all thewrites to after partial commit.
Assume that transactions execute serially
Transaction starts by writing record to log.
A write(X) operation results in a log record being written, where Vis the new value forX.
The write is not performed onXat this time, but isdeferred.
When Tipartially commits, is written to thelog
Finally, log records are used to actually execute thepreviously deferred writes.
7/30/2019 Last Trans
5/21
Immediate Database Modification Example
Log Write Output
To, B, 2000, 2050
A = 950B = 2050
C= 600
BB, BCBA
Note: BXdenotes block containingX.
7/30/2019 Last Trans
6/21
Recovery procedure has two operationsinstead of one:
undo(Ti) restores the value of all data items updated by Tito their old values,going backwards from the last log record for Ti
redo(Ti) sets the value of all data items updated by Tito the new values, goingforward from the first log record for Ti
Both operations must be idempotent
Idempotent: property of an operation they can be appliedmultiple times without changing the result.
When recovering after failure: Transaction Tineeds to be undone if the log contains the record , but
does not contain the record .
Transaction Tineeds to be redone if the log contains both the record and the record .
Undo operations are performed first, thenredo operations.
7/30/2019 Last Trans
7/21
Immediate DB Modification Recovery Example
Below we show the log as it appears at three instances of time.
(a)(b)
Recovery actions in each case above are:(a) undo (T
0
): B is restored to 2000 and A to 1000.(b) undo (T1) and redo (T0): C is restored to 700, and thenA and B are
set to 950 and 2050 respectively.(c) redo (T0) and redo (T1): A and B are set to 950 and 2050
respectively. Then Cis set to 600
7/30/2019 Last Trans
8/21
Checkpoints
Problems in recovery procedure as discussed earlier :
1. searching the entire log is time-consuming2. we might unnecessarily redo transactions which have
already
3. output their updates to the database.
Streamline recovery procedure by periodicallyperforming check pointing
1. Output all log records currently residing in main
memory onto stable storage.2. Output all modified buffer blocks to the disk.
3 Write a log record < checkpoint> onto stable storage.
7/30/2019 Last Trans
9/21
During recovery we need to consider only the mostrecent transaction Ti that started before thecheckpoint, and transactions that started after Ti.
Scan backwards from end of log to find the mostrecent record
Continue scanning backwards till a record is found.
Need only consider the part of log following abovestart record. Earlier part of log can be ignored duringrecovery, and can be erased whenever desired.
For all transactions (starting from Tior later) with no, execute undo(Ti). (Done only in case of
immediate modification.) Scanning forward in the log, for all transactions
starting from Tior later with a ,execute redo(Ti).
7/30/2019 Last Trans
10/21
Example of Checkpoints
T1 can be ignored (updates already output to disk due
to checkpoint) T2 and T3 redone.
T4 undone
Tc Tf
T1
T2
T3
T4
checkpoint system failure
7/30/2019 Last Trans
11/21
Shadow Paging
Alternative to log-based recovery; this scheme is useful iftransactions execute serially
Idea: maintain two page tables during the lifetime of a transactionthe currentpage table, and the shadowpage table
Store the shadow page table in nonvolatile storage, such that stateof the database prior to transaction execution may be recovered.Shadow page table is never modified during execution
To start with, both the page tables are identical. Only current pagetable is used for data item accesses during execution of thetransaction.
Whenever any page is about to be written for the first time, a copyof this page is made onto an unused page. The current page tableis then made to point to the copy, and the update is performed onthe copy
7/30/2019 Last Trans
12/21
Example of Shadow Paging
Shadow and current page tables after write to page 4
7/30/2019 Last Trans
13/21
To commit a transaction :
1. Flush all modified pages in main memory to disk
2. Output current page table to disk
3. Make the current page the new shadow page table
keep a pointer to the shadow page table at a fixed (known) location ondisk.
to make the current page table the new shadow page table, simply updatethe pointer to point to current page table on disk
Once pointer to shadow page table has been written,transaction is committed.
No recovery is needed after a crash new transactions canstart right away, using the shadow page table.
Pages not pointed to from current/shadow page table should befreed (garbage collected).
7/30/2019 Last Trans
14/21
Commit overhead is high (many pages need to be flushed)
Data gets fragmented (related pages get separated)
After every transaction completion, the database pages containing
old versions of modified data need to be garbage collected and put
into
the list of unused pages
Hard to extend algorithm to allow transactions to run concurrently
recovery is trivial(perfect)
7/30/2019 Last Trans
15/21
Advantages of shadow-paging over log-
based schemes no overhead of writing
log records; recovery is trivial(perfect)
Disadvantages :
7/30/2019 Last Trans
16/21
Lock-Based Protocols
A lock is a mechanism to control concurrentaccess to a data item
Data items can be locked in two modes
1. Exclusive (X) mode: read/write
2. Shared (S) mode: read
Lock requests are made to concurrency-
control manager. Transaction can proceed
only after request is granted.
7/30/2019 Last Trans
17/21
Lock-compatibility matrix
A transaction may be granted a lock on an item ifthe requested lock is compatible with locks alreadyheld on the item by other transactions
Any number of transactions can hold shared lockson an item
No other transaction may hold any lock on the itemif any transaction holds an exclusive lock on theitem
If a lock cannot be granted, the requestingtransaction must wait till all incompatible locks heldby other transactions have been released.
7/30/2019 Last Trans
18/21
Lock-Based Protocols
Examplelock-S(A);
read (A);
unlock(A);
lock-S(B);
read (B);
unlock(B);
display(A+B)
Locking as above is not sufficient to guarantee serializability
IfA and B get updated between the read ofA and B, the displayed sum would be
wrong. A locking protocol is a set of rules followed by all transactions while requesting
and releasing locks. Locking protocols restrict the set of possible schedules.
7/30/2019 Last Trans
19/21
Pitfalls of Lock-Based Protocols
Deadlock
Neither T3 nor T4 can make progress executing lock-S(B) causes T4 to waitfor T3 to release its lock on B, while executing lock-X(A) causes T3 to wait forT4 to release its lock onA.
7/30/2019 Last Trans
20/21
Starvation A transaction may be waiting for an X-lock on an item, while a
sequence of other transactions request and are granted an S-lock
on the same item.
Concurrency control manager can be designed to prevent starvation.
7/30/2019 Last Trans
21/21
Recommended