Logging and conflict-serializabilityCSE 444 section, July 15, 2010Today• Logging and recovery exercises• Identifying conflict-serializable schedulesWhy do we need to recover a DB?Why use log-based recovery?Helps satisfy 2 of the ACID constraints:• Atomicity– How does log-based recovery keep TXen atomic?– How is this done in an undo log?– In a redo log?• Durability– How does logging ensure that TXen persist?When to use log-based recoveryWhen it helps:• When the DBMS program crashes• When the computer loses powerWhen it doesn’t help:• When the disk crashes (both data, log corrupt)• On user error (database is still consistent)Our undo log notation• <START T> – Transaction T has begun• <COMMIT T> – T has committed• <ABORT T>– T has aborted• <T, X, v> - Update record– T has updated element X, and its old value was vAn undo logging problemGiven this undo log, when can each data item be output to disk?• A: after 2• B: after 3• C: after 5, before 12• D: after 7• E: after 8, before 12• F: after 10• G: after 111<START T1>2<T1, A, a>3<T1, B, b>4<START T2>5<T2, C, c>6<START T3>7<T3, D, d>8<T2, E, e>9<START T4>10<T4, F, f>11<T3, G, g>12<COMMIT T2>Undo logging problem, continuedAfter writing these log entries, the DBMS crashes. What does it do when it restarts?• Scan for transactions toundo: T1, T3, T4• G, F, D, B, A reverted(in that order)• <ABORT> written forT1, T3, T41<START T1>2<T1, A, a>3<T1, B, b>4<START T2>5<T2, C, c>6<START T3>7<T3, D, d>8<T2, E, e>9<START T4>10<T4, F, f>11<T3, G, g>12<COMMIT T2>What if it was a redo log?Now, <T,X,v> means X’s new value is v!… so now when can we output each item?• C, E: after 12• Others: never(given log available)1<START T1>2<T1, A, a>3<T1, B, b>4<START T2>5<T2, C, c>6<START T3>7<T3, D, d>8<T2, E, e>9<START T4>10<T4, F, f>11<T3, G, g>12<COMMIT T2>Redo log problem, continuedHow do we recover from this redo log?• Scan for transactions toredo: only T2• C and E rewritten1<START T1>2<T1, A, a>3<T1, B, b>4<START T2>5<T2, C, c>6<START T3>7<T3, D, d>8<T2, E, e>9<START T4>10<T4, F, f>11<T3, G, g>12<COMMIT T2>Why add (non-quiescent) checkpoints?Undo log recovery with checkpointsThe DBMS crashes with this undo log.What do we do to recover?– Which log entries are read?From end to 9: <START CKPT>– Which transactions are undone?None; all have committed– Which data do we change?None; no transactions to undo1<START T1>2<T1, A, a>3<T1, B, b>4<START T2>5<T2, C, c>6<START T3>7<T3, D, d>8<COMMIT T1>9<START CKPT (T2, T3)>10<T2, E, e>11<START T4>12<T4, F, f>13<T3, G, g>14<COMMIT T3>15<COMMIT T2>16<END CKPT>17<COMMIT T4>Redo log recovery with checkpointsThis similar log is a REDO log.How do we recover this one?– Which log entries are read?From end to 9: <START CKPT>Then from 4: <START T2> down to end– Which transactions are redone?T2, T3, T4– Which data do we change?C c, D d, E e, F f, G gLines 15, 16 swapped1<START T1>2<T1, A, a>3<T1, B, b>4<START T2>5<T2, C, c>6<START T3>7<T3, D, d>8<COMMIT T1>9<START CKPT (T2, T3)>10<T2, E, e>11<START T4>12<T4, F, f>13<T3, G, g>14<COMMIT T3>15<END CKPT>16<COMMIT T2>17<COMMIT T4>Today• Logging and recovery exercises• Identifying conflict-serializable schedulesSchedules and conflictsFor some transaction T1:– r1(X) means “T1reads the data element X”– w1(X) means “T1writes the data element X”Two actions from T1, T2conflict iff:• one or both is a write, and• they act on the same elementTwo actions both from T1also conflictExample 1: find all conflictsw3(A)r1(A)w1(B)r2(B)w3(C)r2(C)The precedence graph• Recall: T1must precede T2iff an action from T1conflicts with a later action from T2– Ignore conflicting actions from the same transaction• Precedence graph shows the precedence relationsExample 1: precedence graphw3(A)r1(A)w1(B)r2(B)w3(C)r2(C)1 2 3ACBAB CIs it conflict serializable?• YES: if no cycles in the precedence graph– Any transaction order which follows the precedences shown is an equivalent serial schedule• NO: if there are cycles in the precedence graphExample 1: conflict serializable?w3(A)r1(A)w1(B)r2(B)w3(C)r2(C)1 2 3ACBAB CNo cycles: YES, conflict serializableOnly serial equivalent schedule: T3, T1, T2Example 1: serial equivalentw3(A)r1(A)w1(B)r2(B)r2(C)Only serial equivalent schedule: T3, T1, T2w3(A)w3(C)r1(A)w1(B)r2(B)r2(C)w3(C)w3(C)Example 2: find non-self conflictsr1(A)r2(A)r1(B)r2(B)r3(A)r4(B)w1(A)w2(B)Example 2: precedence graphr1(A)r2(A)r1(B)r2(B)r3(A)r4(B)w1(A)w2(B)AB1 2 3BB4AAExample 2: conflict serializable?r1(A)r2(A)r1(B)r2(B)r3(A)r4(B)w1(A)w2(B)AB1 2 3BB4AACycle between T1and T2:NO, not conflict
View Full Document
Unlocking...