Transcription
CompSci 516Database SystemsLecture 16Transactions –RecoveryInstructor: Sudeepa RoyDuke CS, Fall 2018CompSci 516: Database Systems1
Announcements Keep working on your project– Midterm report due on Monday, 11/05 HW2 deadline extended– Friday Nov 2, 5PM– No further extensions – finish early!Duke CS, Fall 2018CompSci 516: Database Systems2
Reading Material [GUW]– Chapter 17.2.1-17.2.4 (UNDO)– Chapter 17.3.1-17.3.4 (REDO – next lecture)– Lecture slides will be sufficient for examsAcknowledgement:A few of the following slides have been created adapting theinstructor material of the [RG] book provided by the authorsDr. Ramakrishnan and Dr. Gehrke.Duke CS, Fall 2018CompSci 516: Database Systems3
Last Lecture Dynamic Database Phantom Problem Multiple-granularity locks Alternatives timestamp-based (not lockbased) approaches to CC– Optimistic: validation tests– Timestamp: RT(O) & WT(O) on each object O– Multiversion: multiple versions of each object Owith different WT and RTDuke CS, Fall 2018CompSci 516: Database Systems4
TodayRecovery STEAL/ NO STEAL FORCE/NO FORCE UNDO log REDO log– to be continued in the next 1-2 lectureDuke CS, Fall 2018CompSci 516: Database Systems5
Transaction RecoveryandLogsDuke CS, Fall 2018CompSci 516: Database Systems6
Review: The ACID properties A tomicity:All actions in the transaction happen, or nonehappen. C onsistency:If each transaction is consistent, and the DB startsconsistent, it ends up consistent. I solation:Execution of one transaction is isolated from that ofother transactions. D urability:If a transaction commits, its effects persist. Which property did we cover in CC?Duke CS, Fall 2018CompSci 516: Database Systems7
Review: The ACID properties A tomicity:All actions in the transaction happen, or nonehappen. C onsistency:If each transaction is consistent, and the DB startsconsistent, it ends up consistent. I solation:Execution of one transaction is isolated from that ofother transactions. D urability:If a transaction commits, its effects persist. Which property did we cover in CC? : IsolationDuke CS, Fall 2018CompSci 516: Database Systems8
Review: The ACID properties A tomicity:happen. All actions in the transaction happen, or noneC onsistency:If each transaction is consistent, and the DB startsconsistent, it ends up consistent. I solation:Execution of one transaction is isolated from that ofother transactions. D urability:If a transaction commits, its effects persist. Next: The Recovery Manager guarantees Atomicity & Durability. Recall that Consistency is programmer’s responsibilityDuke CS, Fall 2018CompSci 516: Database Systems9
Motivation: A & D Atomicity:– Transactions may abort (“Rollback”). Durability:– What if DBMS stops running? (power failure/crash/error/fireflood etc.) Desired Behavior after system restarts:– T1, T2 & T3 should be durable.– T4 & T5 should be aborted (effectsnot seen).Duke CS, Fall 2018crash!T1T2T3T4T5CompSci 516: Database Systems10
Recovery: A & D Atomicity– by ”undo”ing actions of “aborted transactions” Durability– by making sure that all actions of committedtransactions survive crashes and system failure– i.e. by “redo”-ing actions of “committedtransactions”Duke CS, Fall 2018CompSci 516: Database Systems11
DB Architecture for TransactionsQueryProcessorTransactionmanagerLog managerBuffermanagerRecoverymanagerData Tr. mgr. issues signalsLog– to log mgr. to store log records– to buffer mgr. about when it should copy buffer to disk– to query processor to execute queries/operations that comprise the transaction Log mgr.– maintains log, deals with buffer mgr. since first log appears in buffer then is written to disk Recovery mgr.– If there is a crash, it is activated– examines the log and repairs data if necessary Note: access to the disk is through the buffer mgr.Duke CS, Fall 2018CompSci 516: Database Systems12
Assumptions Concurrency control is in effect Updates are happening “in place”.– i.e. data is overwritten on (deleted from) the disk. Simple schemes to guarantee Atomicity &Durability (next):– NO STEAL– FORCEDuke CS, Fall 2018CompSci 516: Database Systems13
Handling the Buffer Pool Force every write todisk?– Poor response time– But provides durability Steal buffer-poolframes fromuncommittedtransactions?Force– If not, poor throughput– If so, how can weensure atomicity?Duke CS, Fall 2018No StealNo ForceCompSci 516: Database SystemsStealTrivialDesired14
What if we do “Steal” and “NO Force” STEAL(why enforcing Atomicity is hard)– To steal frame F: Current page in F (say P) is written todisk; some transaction holds lock on P What if the transaction with the lock on P aborts? Must remember the old value of P at steal time (to supportUNDOing the write to page P) NO FORCE(why enforcing Durability is hard)– What if system crashes before a modified page iswritten to disk?– Write as little as possible, in a convenient place, atcommit time, to support REDOing modifications.Duke CS, Fall 2018CompSci 516: Database Systems15
Basic Idea: Logging Record REDO and UNDO information, forevery update, in a log– Sequential writes to log (put it on a separatedisk)– Minimal info (diff) written to log, so multipleupdates fit in a single log page Log: An ordered list of REDO/UNDO actions– Log record may contain: Tr.ID, pageID, offset, length, old data, new data Duke CS, Fall 2018CompSci 516: Database Systems16
Different types of logs UNDO REDO UNDO/REDOGUW 17.2, 17.3, 17.4(Lecture material will be sufficient forHWs and Exams) ARIES– an UNDO/REDO log implementationNext lecture, [RG ]18,and a research paper (optional)Duke CS, Fall 2018CompSci 516: Database Systems17
Recall: Log Records A file opened for appending only Log blocks are created and updated in themain memory first– then written to diskDuke CS, Fall 2018CompSci 516: Database Systems18
UNDO loggingDuke CS, Fall 2018CompSci 516: Database Systems19
UNDO logging Make repair to the database by undoing theeffect of transactions that have not finished– i.e. uncommitted transactions before a crash oraborted transactionsDuke CS, Fall 2018CompSci 516: Database Systems20
Types of UNDO log records START T : transaction T has begun COMMIT T : T has completed successfully, no more changes willbe made– Note that seeing COMMIT T does not automatically ensure that changeshave been written to disk, has to be enforced by log manager ABORT T : transaction T could not complete successfully– job of the transaction mgr to ensure that changes by T never appear on diskor are cancelled T, X, v : update record for UNDO log– T has changed object X, and its former value was v– This change normally happened in memory after a WRITE, not afterOUTPUT to disk– NOTE: we only record the old value, not the new value– since UNDO log, while undoing, replace with old valueDuke CS, Fall 2018CompSci 516: Database Systems21
UNDO logging rules1. (U1) If T modifies X, then log record T, X, v must be written to disk before the new value ofX is written to disk–so that the update can be undone using v if there is acrash2. (U2) If T commits, COMMIT T must be writtento disk after all database elements changed by Tare written to disk–but as soon thereafter as possibleDuke CS, Fall 2018CompSci 516: Database Systems22
Order of write to disk for UNDO log Summarizing two rules:1. First, the log records indicating changed DBelements should be writtenfor each element,not as a group2. Second, the changed values of the DB elementsshould be written3. Finally, the COMMIT log record should be writtenDuke CS, Fall 2018CompSci 516: Database Systems23
initially A 8, B 8ActionDuke CS, Fall 2018T tEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T CompSci 516: Database Systems24
initially A 8, B 8ActionREAD(A,t)Duke CS, Fall 2018T8EXAMPLE: UNDO LOGMem A8Mem BDisk ADisk BLog88 START T 88CompSci 516: Database Systems25
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888Duke CS, Fall 2018CompSci 516: Database Systems26
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688Duke CS, Fall 2018CompSci 516: Database Systems T,A,8 27
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)81688Duke CS, Fall 20188CompSci 516: Database Systems T,A,8 28
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: t*21616888Duke CS, Fall 2018CompSci 516: Database Systems T,A,8 29
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: t*21616888WRITE(B,t)16161688Duke CS, Fall 2018CompSci 516: Database Systems T,A,8 T,B,8 30
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: t*21616888WRITE(B,t)16161688 T,A,8 T,B,8 FLUSH LOGDuke CS, Fall 2018CompSci 516: Database Systems31
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: t*21616888WRITE(B,t)16161688161616168 T,A,8 T,B,8 FLUSH LOGOUTPUT(A)Duke CS, Fall 2018CompSci 516: Database Systems32
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOGDuke CS, Fall 2018CompSci 516: Database Systems33
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T Duke CS, Fall 2018CompSci 516: Database Systems34
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog88 START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOGDuke CS, Fall 2018CompSci 516: Database Systems35
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOGDuke CS, Fall 2018CompSci 516: Database Systems36
Recovery usingUNDO logging first simple (look at entire log) then “checkpointing” (no need to look at entire log)Duke CS, Fall 2018CompSci 516: Database Systems37
Recovery with UNDO log Scan from the end If COMMIT T is found in log– all changes by T have been written to disk – OK START T found but no COMMIT T – some changes might be written, some not– Changes by T on disk have to be UNDONEUNDO: order of writing to disk1. START T 2. T, A, 10 (old value 10)3. A 12 (new value 12)4. COMMIT T Recall rule 1:– “If T modifies X, then log record T, X, v must be written to disk beforethe new value of X is written to disk”– v was previous value of X– For each such change on disk, there will be a log record on disk as well– Reset value of X to v in recoveryDuke CS, Fall 2018CompSci 516: Database Systems38
Recovery with UNDO log Travel backward 1.– scan the log from the end toward the startRemember whether you have seen COMMIT T or ABORT T for all TSuppose T, X, v is encounteredIf COMMIT T has been seen, do nothing–2.nothing to undo, new value already writtenUNDO: order of writing to disk1. START T 2. T, A, 10 (old value 10)3. A 12 (new value 12)4. COMMIT T Otherwise,a) T is incomplete or abortedb) Change the value of X to v3. If ABORT T not founda) write ABORT T b) flush the logc) resume normal operationDuke CS, Fall 2018CompSci 516: Database Systems39
initially A 8, B 8ActionTEXAMPLE: UNDO LOGMem AMem BDisk ACrash example 1Disk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOG Crash after final flush COMMIT T already on disks All log records by T are ignored by the recovery managerDuke CS, Fall 2018CompSci 516: Database Systems40
initially A 8, B 8ActionTCrash example 2, Step 1EXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOG Crash before final flush COMMIT T not on disk Go backward, first T, B, 8 found, set B 8 on diskDuke CS, Fall 2018CompSci 516: Database Systems41
initially A 8, B 8ActionTCrash example 2, Step 2EXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOG Crash before final flush COMMIT T not on diskGo backward, first T, B, 8 found, set B 8 on diskThen T, A, 8 is found, set A 8 on diskDuke CS, Fall 2018CompSci 516: Database Systems42
initially A 8, B 8ActionTCrash example 2, Step 3EXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOG Crash before final flush COMMIT T not on diskGo backward, first T, B, 8 found, set B 8 on diskThen T, A, 8 is found, set A 8 on disk START T found. Nothing else can be found in the log for T. Write ABORT T Duke CS, Fall 2018CompSci 516: Database Systems43
initially A 8, B 8ActionTCrash example 3EXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOG Crash before FIRST flush T, A, 8 , T, B, 8 , COMMIT T not on disk By rule U1, A and B not changed on disk - do nothingDuke CS, Fall 2018CompSci 516: Database Systems44
initially A 8, B 8ActionTCrash example 3EXAMPLE: UNDO LOGMem AMem BDisk ADisk BLog START T READ(A,t)8888t: t*216888WRITE(A,t)161688READ(B,t)816888t: UT(B)1616161616 T,A,8 T,B,8 FLUSH LOG COMMIT T FLUSH LOG Crash before FIRST flush T, A, 8 , T, B, 8 , COMMIT T not on disk By rule U1, A and B not changed on disk - do nothingDuke CS, Fall 2018CompSci 516: Database SystemsDoes this UNDO method workif T changes A twice?A 16A 24?45
Checkpointing for UNDO logDuke CS, Fall 2018CompSci 516: Database Systems46
Checkpointing Motivation So far, recovery requires every log record to be examined If we have seen COMMIT T , no need to examine logrecords of T– all changes already on disk Still, we may not be able to truncate log after onetransaction committed– log records of other active transactions might be lost– always need to scan until the start of the log Explicitly checkpoint the log periodically– We can stop scanning the log after certain pointsDuke CS, Fall 2018CompSci 516: Database Systems47
Checkpointing process1. Stop accepting new transactions2. Wait until all currently active transactions commit or abort,and have written COMMIT or ABORT log record3. Flush log to disk4. Write a checkpointing log record CKPT , flush the log again5. Resume accepting transactionsDuke CS, Fall 2018CompSci 516: Database Systems48
Recovery using Checkpointingfor UNDO logLog records START T1 T1, A, 5 START T2 T2, B, 10 T2, C, 15 T1, D, 20 COMMIT T1 suppose,want to ckpt hereDo not accept new transaction Finish T1, T2– they committed Then write CKPT on log Then can accept new transaction– Here T3 COMMIT T2 CKPT START T3 T3, E, 25 T3, F, 30 Duke CS, Fall 2018CompSci 516: Database Systems49
Recovery using Checkpointingfor UNDO logLog records START T1 T1, A, 5 suppose, wantto ckpt here START T2 T2, B, 10 T2, C, 15 When we reach CKPT , we know that noneed to examine prior log records Restoration of the database is complete– CKPT is the earliest (last) log record read by therecovery manager COMMIT T2 CKPT START T3 T3, E, 25 – Restore F to 30– Restore E to 25– in backward direction T1, D, 20 COMMIT T1 T3 is the only incomplete transaction Drawback: no transaction can be accepteduntil all the active ones commit and CKPTcompletes T3, F, 30 CRASHDuke CS, Fall 2018CompSci 516: Database Systems50
Nonquiescent Checkpointing Avoids stalling the system and continues accepting newtransactions– “quiescent” in a state or period of inactivity or dormancy1.Write START CKPT(T1, , Tk) and flush the log–2.Checkpointing continues until all of T1, . Tk aborts or commits–3.T1, Tk are active transactions (have not committed and have notwritten their changes to disk)but do not prohibit other new transactions to startWhen all of T1, , Tk have completed, write END CKPT andflush the log againDuke CS, Fall 2018CompSci 516: Database Systems51
Example: Nonquiescent Checkpointingfor UNDO logLog records START T1 T1, A, 5 START T2 suppose,want to ckpt here T2, B, 10 START CKPT(T1, T2) T2, C, 15 START T3 START CKPT(T1, T2) – since T1, T2 are only active transactions atthat point– END CKPT after both committed START T3 during checkpointing T1, D, 20 COMMIT T1 T3, E, 25 COMMIT T2 END CKPT T3, F, 30 Duke CS, Fall 2018CompSci 516: Database Systems52
Log records START T1 Recovery with NonquiescentCheckpointing for UNDO log – find all incomplete transaction as we go– restore values for those transactions (undo) T1, A, 5 START T2 T2, B, 10 T2, C, 15 START T3 COMMIT T1 T3, E, 25 COMMIT T2 END CKPT T3, F, 30 Duke CS, Fall 2018If END CKPT is met first– all incomplete transactions started after START CKPT . – scan until that START CKPT - can stop at that point– can delete log records prior to START CKPT. once ENDCKPT is written to disk START CKPT(T1, T2) T1, D, 20 Scan log from the end (as before) If START CKPT (T1,.,Tk) is met first– crash occurred during the checkpoint– incomplete transactions either started after START CKPT. or among T1, , Tk– Scan backward– until the earliest START tr of all these transactions trCompSci 516: Database Systems(HERE T3)(HERE T1, T2)UNDO: order of writing to disk1. START T 2. T, A, 10 (old value 10)3. A 12 (new value 12)4. COMMIT T 53
Log recordsRecovery with NonquiescentCheckpointing for UNDO log START T1 T1, A, 5 START T2 T2, B, 10 START CKPT(T1, T2) T2, C, 15 START T3 T1, D, 20 COMMIT T1 T3, E, 25 COMMIT T2 END CKPT First T3, F, 30 found– restore F to 30 (undo change by T3) END CKPT found– All incomplete transactions started aftercorresponding START CKPT. T3, E, 25 found– restore E to 25 (undo change by T3) No other records to restore until START CKPT Stop there – no further changes T3, F, 30 CRASHDuke CS, Fall 2018CompSci 516: Database Systems54
Log records START T1 T1, A, 5 Recovery with NonquiescentCheckpointing for UNDO log – no END CKPT found– but START CKPT(T1, T2) found– also COMMIT T1 found START T2 T2, B, 10 START CKPT(T1, T2) T2, C, 15 START T3 T3, E, 25 CRASHDuke CS, Fall 2018T3 and T2 incomplete transactions– T1 already committed T1, D, 20 COMMIT T1 Scan backwardScan until the earliest of START T2 and START T3 – here START T2 Along the way backward–––––restore E to 25 (undo change by T3)restore C to 15 (undo change by T2)restore B to 10 (undo change by T2)in this orderthen stop at START T2 CompSci 516: Database Systems55
Problems with UNDO logging We cannot commit T
Dr. Ramakrishnan and Dr. Gehrke. Duke CS, Fall 2018 CompSci 516: Database Systems. Last Lecture Dynamic Database Phantom Problem . Duke CS, Fall 2018 CompSci 516: Database Systems 12 Data Log Buffer manager R
