《數(shù)據(jù)庫系統(tǒng)》教學課件

《數(shù)據(jù)庫系統(tǒng)》教學課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),教學,課件 Crash RecoveryJianlin FengSchool of SoftwareSUN YAT-SEN UNIVERSITYcourtesy of Joe Hellerstein for some slidesReview:The ACID propertiesn nA Atomicity:All actions in the Xact(transaction)happen,or none happen.n nC Consistency:If each Xact is consistent,and the DB starts consistent,it ends up consistent.n nI Isolation:Execution of one Xact is isolated from that of other Xacts.n nD Durability:If an Xact commits,its effects persist.nThe Recovery Manager guarantees Atomicity&Durability.MotivationnAtomicity:qTransactions may abort(“Rollback”).nDurability:qWhat if DBMS stops running?(Causes?)crash!Desired state after system restarts:T1&T3 should be durable.T2,T4&T5 should be aborted(effects should not be seen).T1T2T3T4T5AbortCommitCommitAssumptionsnConcurrency control is in effect.qStrict 2PL,in particular.nUpdates are happening“in place”.qi.e.,data is overwritten on(deleted from)the disk.nAtomic Writes:writing a page to disk is an atomic action.qIn practice,additional details are needed to deal with non-atomic writes.Buffer Management Policy Plays a Key RolenShall we allow“dirty pages”in the buffer pool caused by an Xact T to be written to disk before T commits?qIf so,a second Xact T can“steal”a frame from T.qIn contrast,No-Steal.nWhen an Xact T commits,must we ensure that all the“dirty pages”of T are immediately forced to disk?qIf so,we say that a“force”approach is used.qIn contrast,No-Force.Variants of Buffer Management PolicyForceNo ForceNo StealStealNo REDONo UNDO UNDONo REDO UNDOREDONo UNDOREDOForceNo ForceNo StealStealSlowestFastestPerformanceImplicationsLogging/RecoveryImplicationsPreferred Policy:Steal/No-ForcenSTEAL(why enforcing Atomicity is hard)nTo steal frame F:Current page in F(say P)is written to disk;some Xact holds lock on P.nWhat if the Xact with the lock on P aborts?nMust remember the old value of P at steal time(to support UNDOing the write to page P).nNO FORCE(why enforcing Durability is hard)qWhat if system crashes before an updated page is written to disk?qWrite as little as possible,in a convenient place,at commit time,to support REDOing modifications.Basic Idea:LoggingnRecord REDO and UNDO information,for every update,in a log.qSequential writes to log(put it on a separate disk).qMinimal information(difference)written to log,so multiple updates fit in a single log page.nLog:An ordered list of REDO/UNDO actionsqLog record contains:qand additional control info(which well see soon).The Write-Ahead Logging(WAL)Protocol#1 Must force the log record for an update to disk before the corresponding data page gets to disk.qThis rule helps guarantee Atomicity.qThis allows us to implement Steal policy.#2 Must write all log records for an Xact to disk before commit.qI.e.transaction is not committed until all of its log records including its“commit”record are written to disk.qThis rule helps guarantee Durability.qThis allows us to implement No-Force policy.nExactly how is logging(and recovery!)done?qWell look at the ARIES algorithms from IBM.WAL&the LognEach log record has a unique Log Sequence Number(LSN).qLSNs is always increasing.nEach data page contains a pageLSN.qThe LSN of the most recent log record for an update to that page.nSystem keeps track of flushedLSN.qThe max LSN flushed so far.nWAL:Before page i is written to disk,log must satisfy:pageLSNi flushedLSN,i.e.,the log record identified by pageLSNi must have been written to disk for page i is written to disk.LSNspageLSNsRAMflushedLSNpageLSNLog recordsflushed to disk“Log tail”in RAMflushedLSNDBLog RecordsprevLSN is the LSN of the previous log record written by this Xact(so records of an Xact form a linked list backwards in time)Possible log record types:nUpdate,Commit,AbortnCheckpoint(for log maintainence)nCompensation Log Records(CLRs)qfor UNDO actionsnEnd(end of commit or abort)LSNprevLSNXIDtypelengthpageIDoffsetbefore-imageafter-imageLogRecord fields:updaterecordsonlyOther Log-Related Data StructuresnTwo in-memory tables:nTransaction TableqOne entry per currently active Xact.nentry removed when Xact commits or abortsqContains XID,status(running/committing/aborting),and lastLSN(most recent LSN written by Xact).nDirty Page Table:qOne entry per dirty page currently in buffer pool.qContains recLSN-the LSN of the log record which first caused the page to be dirty.An ExampleThe Big Picture:Whats Stored WhereData pageseachwith apageLSNXact TablelastLSNstatusDirty Page TablerecLSNflushedLSNRAMLSNprevLSNXIDtypelengthpageIDoffsetbefore-imageafter-imageLogRecordsLOGMaster recordLSNof most recent checkpoint record DBNormal Execution of an XactnSeries of reads&writes,followed by commit or abort.nStrict 2PL.nSTEAL,NO-FORCE buffer management,with Write-Ahead Logging.Transaction CommitnWrite commit record to log.nAll log records up to Xacts commit record are flushed to disk.qGuarantees that flushedLSN lastLSN.qNote that log flushes are sequential,synchronous writes to disk.qMany log records per log page.nCommit()returns.nWrite end record to log.Simple Transaction AbortnFor now,consider an explicit abort of an Xact.qNo crash involved.nWe want to“play back”the log in reverse order,UNDOing updates.qGet lastLSN of Xact from Xact table.qWrite an Abort log record before starting to rollback operations qCan follow chain of log records backward via the prevLSN field.qWrite a“CLR”(compensation log record)for each undone operation.Abort,cont.nTo perform UNDO,must have a lock on data!qNo problem!nBefore restoring old value of a page,write a CLR:qYou continue logging while you UNDO!qCLR has one extra field:undonextLSNnPoints to the next LSN to undo(i.e.the prevLSN of the record were currently undoing).qCLR contains REDO infoqCLRs never Undone nUndo neednt be idempotent(1 UNDO wont happen)nBut they might be Redone when repeating history(=1 UNDO guaranteed)nAt end of all UNDOs,write an“end”log record.CheckpointingnUsually,we can not keep log around for all time.nPeriodically,the DBMS creates a checkpointqMinimizes recovery time after crash.Write to log:nbegin_checkpoint record:Indicates when the checkpoint began.nend_checkpoint record:Contains current Xact table and dirty page table.Afuzzy checkpoint:qOther Xacts continue to run;so these tables accurate only as of the time of the begin_checkpoint record.qNo attempt to force dirty pages to disk;effectiveness of checkpoint limited by oldest unwritten change to a dirty page.nStore LSN of most recent checkpoint record in a safe place(master record).Crash Recovery:Big PictureStart from a checkpoint(found via master record).Three phases.Need to do:Analysis-Figure out which Xacts committed since checkpoint,which failed.REDO all actions.(repeat history)UNDO effects of failed Xacts.Oldest log rec.of Xact active at crashSmallest recLSN in dirty page table after AnalysisLast chkptCRASHAR URecovery:The Analysis PhasenRe-establish knowledge of state at checkpoint.qvia transaction table and dirty page table stored in the checkpointnScan log forward from the most recent checkpoint.qEnd record:Remove Xact from Xact table.qAll Other records:Add Xact to Xact table,set lastLSN=LSN,change Xact status on commit record.qalso,for Update records:If page P not in Dirty Page Table(DPT),Add P to DPT,set its recLSN=LSN.nAt the end of AnalysisqXact table says which xacts were active at time of crash.qDPT says which dirty pages might not have been written to disk.Phase 2:The REDO PhasenWe Repeat History to reconstruct state at crash:qReapply all updates(even of aborted Xacts!),redo CLRs.nScan forward from log record containing smallest recLSN in DPT.nFor each update log record or CLR with a given LSN,REDO the action unless:qAffected page is not in the DPT,orqAffected page is in DPT,but has recLSN LSN,orqpageLSN(in DB)LSN.(this last case requires I/O)nTo REDO an action:qReapply logged action.qSet pageLSN to LSN.No additional logging,no forcing!Phase 3:The UNDO PhasenA Nave solution:qThe xacts in the Xact Table are losers.qFor each loser,perform simple transaction abort.qProblems?Phase 3:The UNDO PhaseToUndo=lastLSNs of all Xacts in the Xact Table a.k.a.“l(fā)osers”Repeat:qChoose(and remove)largest LSN among ToUndo.qIf this LSN is a CLR and undonextLSN=NULLnWrite an End record for this Xact.qIf this LSN is a CLR,and undonextLSN!=NULLnAdd undonextLSN to ToUndo qElse this LSN is an update.Undo the update,write a CLR,add prevLSN to ToUndo.Until ToUndo is empty.NOTE:This is simply a performance optimization on the nave solution to do it in one backwards pass of the log!Example of Recoverybegin_checkpoint end_checkpointupdate:T1 writes P5update T2 writes P3T1 abortCLR:Undo T1 LSN 10T1 Endupdate:T3 writes P1update:T2 writes P5CRASH,RESTARTLSN LOG 00 05 10 20 30 40 45 50 60Xact TablelastLSNstatusDirty Page TablerecLSNflushedLSNToUndoprevLSNsRAMExample:Crash During Restart!begin_checkpoint,end_checkpointupdate:T1 writes P5update T2 writes P3T1 abortCLR:Undo T1 LSN 10,T1 Endupdate:T3 writes P1update:T2 writes P5CRASH,RESTARTCLR:Undo T2 LSN 60CLR:Undo T3 LSN 50,T3 endCRASH,RESTARTCLR:Undo T2 LSN 20,T2 endLSN LOG00,05 10 20 3040,45 50 60 7080,85 90Xact TablelastLSNstatusDirty Page TablerecLSNflushedLSNToUndoundonextLSNRAMAdditional Crash IssuesnWhat happens if system crashes during Analysis?During REDO?nHow do you limit the amount of work in REDO?qFlush asynchronously in the background.qWatch“hot spots”!nHow do you limit the amount of work in UNDO?qAvoid long-running Xacts.Summary of Logging/RecoverynRecovery Manager guarantees Atomicity&Durability.nUse WAL to allow STEAL/NO-FORCE w/o sacrificing correctness.nLSNs identify log records;linked into backwards chains per transaction(via prevLSN).npageLSN allows comparison of data page and log records.Summary(Contd.)nCheckpointing:A quick way to limit the amount of log to scan on recovery.nRecovery works in 3 phases:qAnalysis:Forward from checkpoint.qRedo:Forward from oldest recLSN.qUndo:Backward from end to first LSN of oldest Xact alive at crash.nUpon Undo,write CLRs.nRedo“repeats history”:Simplifies the logic!