1Lecture 15:RecoveryWednesday, November 2nd, 20062Outline• Undo logging 17.2• Redo logging 17.3• Redo/undo 17.43Transaction ManagementTwo parts:• Recovery from crashes: ACID• Concurrency control: ACIDBoth operate on the buffer pool4RecoveryFrom which of the events below can a database actually recover ?• Wrong data entry• Disk failure• Fire / earthquake / bankrupcy / ….• Systems crashes5RecoveryPreventionType of CrashDATABASERECOVERYSystem failures:e.g. powerBuy insurance, Change jobs…Fire, theft, bankruptcy…Redundancy: e.g. RAID, archiveDisk crashesConstraints andData cleaningWrong data entryMostfrequent6System Failures• Each transaction has internal state• When system crashes, internal state is lost– Don’t know which parts executed and which didn’t• Remedy: use a log– A file that records every single action of the transaction7Transactions• Assumption: the database is composed of elements– Usually 1 element = 1 block– Can be smaller (=1 record) or larger (=1 relation)• Assumption: each transaction reads/writes some elements8Primitive Operations of Transactions• READ(X,t)– copy element X to transaction local variable t• WRITE(X,t)– copy transaction local variable t to element X• INPUT(X)– read element X to memory buffer• OUTPUT(X)– write element X to disk9ExampleSTART TRANSACTIONREAD(A,t); t := t*2;WRITE(A,t); READ(B,t); t := t*2;WRITE(B,t)COMMIT;START TRANSACTIONREAD(A,t); t := t*2;WRITE(A,t); READ(B,t); t := t*2;WRITE(B,t)COMMIT;Atomicity:BOTH A and Bare multiplied by 2108881616INPUT(B)888INPUT(A)1616161616OUTPUT(B)816161616OUTPUT(A)88161616WRITE(B,t)8881616t:=t*2888168READ(B,t)888Disk B81616WRITE(A,t)8816t:=t*2888READ(A,t)Disk AMem BMem AtActionBuffer pool DiskTransactionREAD(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t)READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t)118881616INPUT(B)888INPUT(A)1616161616OUTPUT(B)816161616OUTPUT(A)88161616WRITE(B,t)8881616t:=t*2888168READ(B,t)888Disk B81616WRITE(A,t)8816t:=t*2888READ(A,t)Disk AMem BMem AtActionCrash !Crash occurs after OUTPUT(A), before OUTPUT(B)We lose atomicity12The Log• An append-only file containing log records• Note: multiple transactions run concurrently, log records are interleaved• After a system crash, use log to:– Redo some transaction that didn’t commit– Undo other transactions that didn’t commit• Three kinds of logs: undo, redo, undo/redo13Undo LoggingLog records• <START T> – transaction T has begun• <COMMIT T> – T has committed• <ABORT T>– T has aborted• <T,X,v>– T has updated element X, and its old value was v148881616INPUT(B)888INPUT(A)<COMMIT T>COMMIT<START T><T,B,8><T,A,8>Log1616161616OUTPUT(B)816161616OUTPUT(A)88161616WRITE(B,t)8881616t:=t*2888168READ(B,t)888Disk B81616WRITE(A,t)8816t:=t*2888READ(A,t)Disk AMem BMem ATAction158881616INPUT(B)888INPUT(A)<COMMIT T>COMMIT<START T><T,B,8><T,A,8>Log1616161616OUTPUT(B)816161616OUTPUT(A)88161616WRITE(B,t)8881616t:=t*2888168READ(B,t)888Disk B81616WRITE(A,t)8816t:=t*2888READ(A,t)Disk AMem BMem ATActionCrash !WHAT DO WE DO ?168881616INPUT(B)888INPUT(A)<COMMIT T>COMMIT<START T><T,B,8><T,A,8>Log1616161616OUTPUT(B)816161616OUTPUT(A)88161616WRITE(B,t)8881616t:=t*2888168READ(B,t)888Disk B81616WRITE(A,t)8816t:=t*2888READ(A,t)Disk AMem BMem ATActionCrash !WHAT DO WE DO ?17After Crash• In the first example:– We UNDO both changes: A=8, B=8– The transaction is atomic, since none of its actions has been executed• In the second example– We don’t undo anything– The transaction is atomic, since both it’s actions have been executed18Undo-Logging RulesU1: If T modifies X, then <T,X,v> must be written to disk before OUTPUT(X)U2: If T commits, then OUTPUT(X) must be written to disk before <COMMIT T>• Hence: OUTPUTs are done early, before the transaction commits198881616INPUT(B)888INPUT(A)<COMMIT T>COMMIT<START T><T,B,8><T,A,8>Log1616161616OUTPUT(B)816161616OUTPUT(A)88161616WRITE(B,t)8881616t:=t*2888168READ(B,t)888Disk B81616WRITE(A,t)8816t:=t*2888READ(A,t)Disk AMem BMem ATAction20Recovery with Undo LogAfter system’s crash, run recovery manager • Idea 1. Decide for each transaction T whether it is completed or not– <START T>….<COMMIT T>…. = yes– <START T>….<ABORT T>……. = yes– <START T>……………………… = no• Idea 2. Undo all modifications by incomplete transactions21Recovery with Undo LogRecovery manager:• Read log from the end; cases:<COMMIT T>: mark T as completed<ABORT T>: mark T as completed<T,X,v>: if T is not completedthen write X=v to diskelse ignore<START T>: ignore22Recovery with Undo Log……<T6,X6,v6>……<START T5><START T4><T1,X1,v1><T5,X5,v5><T4,X4,v4><COMMIT T5><T3,X3,v3><T2,X2,v2>Question1 in class:Which updates areundone ?Question 2 in class:How far backdo we need toread in the log ?crash23Recovery with Undo Log• Note: all undo commands are idempotent– If we perform them a second time, no harm is done– E.g. if there is a system crash during recovery, simply restart recovery from scratch24Recovery with Undo LogWhen do we stop reading the log ?• We cannot stop until we reach the beginning of the log file• This is impracticalInstead: use checkpointing25CheckpointingCheckpoint the database periodically• Stop accepting new transactions• Wait until all current transactions complete• Flush log to disk• Write a <CKPT> log record, flush• Resume transactions26Undo Recovery with Checkpointing……<T9,X9,v9>……(all completed)<CKPT><START T2><START T3<START T5><START T4><T1,X1,v1><T5,X5,v5><T4,X4,v4><COMMIT T5><T3,X3,v3><T2,X2,v2>During recovery,Can stop at first<CKPT>transactions T2,T3,T4,T5other transactions27Nonquiescent Checkpointing• Problem with checkpointing: database freezes during checkpoint• Would like to checkpoint while database is operational• Idea: nonquiescent checkpointingQuiescent = being quiet, still, or at rest; inactiveNon-quiescent = allowing transactions to be active28Nonquiescent Checkpointing• Write a <START CKPT(T1,…,Tk)>where T1,…,Tk are all active transactions• Continue normal operation• When all of T1,…,Tk have completed, write <END CKPT>29Undo Recovery with Nonquiescent Checkpointing………………<START CKPT T4, T5, T6>…………<END CKPT>………During recovery,Can stop at first<CKPT>T4, T5, T6, pluslater transactionsearlier transactions plusT4, T5, T5later transactionsQ: why do we need <END CKPT> ?Q: why do we need
View Full Document
Unlocking...