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

數(shù)據(jù)庫系統(tǒng)教學課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),教學,課件 Transactions Introductionand Concurrency ControlJianlin FengSchool of SoftwareSUN YAT-SEN UNIVERSITYcourtesy of Joe Hellerstein for some slidesConcurrency Control and RecoverynConcurrency ControlqProvide correct and highly available data access in the presence of concurrent access by many users.nRecoveryqEnsures database is fault tolerant,and not corrupted by software,system or media failureq24x7 access to mission critical datanA boon to application authors!qExistence of CC&R allows applications to be written without explicit concern for concurrency and fault tolerance.Query Optimizationand ExecutionRelational OperatorsFiles and Access MethodsBuffer ManagementDisk Space ManagementDBThese layers must consider concurrencycontrol and recovery(Transaction,Lock,Recovery Managers)Structure of a DBMSTransactions and Concurrent Execution nTransaction(“xact”):DBMSs abstract view of a user program(or activity)qA sequence of reads and writes of database objects.qBatch of work that must commit or abort as an atomic unitnTransaction Manager controls execution of xacts.nUsers program logic is invisible to DBMS!qArbitrary computation possible on data fetched from the DBqThe DBMS only sees data read/written from/to the DB.nChallenge:provide atomic xacts to concurrent users!qGiven only the read/write interface.A Sample Transaction1:Begin_Transaction2:get(K1,K2,CHF)from terminal3:Select BALANCE Into S1 From ACCOUNT Where ACCOUNTNR=K1;4:S1:=S1-CHF;5:Update ACCOUNT Set BALANCE=S1 Where ACCOUNTNR=K1;6:Select BALANCE Into S2 From ACCOUNT Where ACCOUNTNR=K2;7:S2:=S2+CHF;8:Update ACCOUNT Set BALANCE=S2 Where ACCOUNTNR=K2;9:Insert Into BOOKING(ACCOUNTNR,DATE,AMOUNT,TEXT)Values(K1,today,-CHF,Transfer);10:Insert Into BOOKING(ACCOUNTNR,DATE,AMOUNT,TEXT)Values(K2,today,CHF,Transfer);12:If S10 Then Abort_Transaction11:End_TransactionConcurrency:Why bother?nThe latency argumentqResponse time:the average time taken to complete an xact.nA short xact could get stuck behind a long xact,leading to unpredictable delays in response time.nThe throughput argumentqThroughput:the average number of xacts completed in a given time.nOverlapping I/O and CPU activity reduces the amount of time disks and CPU are idle.ACID properties of Transaction Executionsn nA A tomicity:qAll actions in the Xact happen,or none happen.n nC C onsistency:qIf the DB(Database)starts consistent,it ends up consistent at end of Xact.n nI I solation:qExecution of one Xact is isolated from that of other Xacts.n nD D urability:qIf an Xact commits,its effects persist.Implications of Atomicity and DurabilitynA transaction ends in one of two ways:qcommit after completing all its actionsn“commit”is a contract with the caller of the DBqabort(or be aborted by the DBMS)after executing some actions.nOr system crash while the xact is in progress;treat as abort.nAtomicity means the effect of aborted xacts must be removednDurability means the effects of a committed xact must survive failures.nDBMS ensures the above by logging all actions:qUndo the actions of aborted/failed xacts.qRedo actions of committed xacts not yet propagated to disk when system crashes.Transaction ConsistencynXacts preserve DB consistencyqGiven a consistent DB state,produce another consistent DB statenDB consistency expressed as a set of declarative Integrity Constraints qCREATE TABLE/ASSERTION statementsnXacts that violate ICs are abortedqThats all the DBMS can automatically check!Isolation(Concurrency)nDBMS interleaves actions of many xactsqActions=reads/writes of DB objectsnUsers should be able to understand an xact without considering the effect of other concurrently executing xacts.nEach xact executes as if it were running by itself.qConcurrent accesses have no effect on an xacts behaviorqNet effect must be identical to executing all xacts for some serial order.Schedule of Executing TransactionsnA schedule isqa list of actions(READ,WRITE,ABORT,or COMMIT)from a set of xacts,qand the order in which two actions of an xact T appears in a schedule must be the same as the order in which they appear in T.nA complete schedule isqA schedule that contains either an abort or a commit for each xact.A Schedule Involving Two Transactions:An Incomplete ScheduleSerial SchedulenSerial scheduleqEach xact runs from start to finish,without any intervening actions from other xacts.nan example:T1;T2.Serializable SchedulenTwo schedules are equivalent if:qThey involve the same actions of the same xacts,qand they leave the DB in the same final state.nA serializable schedule over a set S of xacts is qa schedule whose effect on any consistent database instance is guaranteed to be identical to that of some complete serial schedule over the set of committed xacts in S.A Serializable Schedule of Two TransactionsThe result of this schedule is equivalent to the result of the serial schedule:T1;T2.Important Points of SerializabilitynExecuting xacts serially in different orders may produce different results,qbut all are presumed to be acceptable;qthe DBMS makes no guarantees about which of them will be the outcome of an interleaved execution.nUncommitted xacts can appear in a serializable schedule S,but their effects are cancelled out by UNDO.Conflicting ActionsnNeed an easier check for equivalence of schedulesqUse notion of“conflicting”actionsnAnomalies with interleaved execution are simply caused by conflicting actions.nTwo actions are said conflict if:qThey are by different xacts,qthey are on the same object,qand at least one of them is a write.qThree kinds of conflicts:Write-Read(WR)conflict,Read-Write(RW)and Write-Write(WW)conflicts.Conflicts:Anomalies with Interleaved ExecutionnReading Uncommitted Data(WR Conflicts,“dirty reads”):nUnrepeatable Reads(RW Conflicts):T1:R(A),W(A),R(B),W(B),AbortT2:R(A),W(A),CommitT1:R(A),R(A),W(A),CommitT2:R(A),W(A),CommitConflicts(Continued)nOverwriting Uncommitted Data(WW Conflicts):T1:W(A),W(B),CommitT2:W(A),W(B),CommitSchedules Involving Aborted XactsnSerializability relies on UNDOing aborted xacts completely,which may be impossible in some situations.An Unrecoverable Schedule:T2 has already committed,and so can not be undone.Recoverable SchedulenIn a recoverable schedule,xacts commit only after(and if)all xacts whose changes they read commit.qIf xacts read only the changes of committed xacts,not only is the schedule recoverable,qbut also can avoid cascading aborts.Conflict Serializable SchedulesnTwo schedules are conflict equivalent if:qThey involve the same set of actions of the same xacts,qand they order every pair of conflicting actions of two committed xacts in the same way.nSchedule S is conflict serializable if:qS is conflict equivalent to some serial schedule.nNote,some serializable schedules are NOT conflict serializable.qA price we pay to achieve efficient enforcement.Conflict Serializability IntuitionnA schedule S is conflict serializable if:qYou can transform S into a serial schedule by swapping consecutive non-conflicting operations of different xacts.nExample:R(A)R(B)W(A)W(B)R(A)W(A)R(B)W(B)R(A)R(B)W(A)W(B)R(A)W(A)R(B)W(B)Serializable Schedule That is Not Conflict Serializable This schedule is equivalent to the serial schedule:T1;T2;T3.However it is not conflict quivalent to the serial schedule because the writes of T1 and T2 are ordered differently.Dependency GraphnWe use a dependency graph,also called a precedence graph,to capture all potential conflicts between the xacts in a schedule.nThe dependency graph for a schedule S contains:qA node for each committed xactqAn edge from Ti to Tj if an action of Ti precedes and conflicts with one of Tjs actions.nTheorem:Schedule is conflict serializable if and only if its dependency graph is acyclic.Example of Dependency GraphTwo-Phase Locking(2PL)nThe most common scheme for enforcing conflict serializability.n“Pessimistic”qSets locks for fear of conflictqThe alternative scheme is called Optimistic Concurrency Control.Two-Phase Locking(2PL)rules:qAn xact must obtain a S(shared)lock before reading,and an X(exclusive)lock before writing.qAn xact cannot request additional locks once it releases any lock.SXSXLockCompatibilityMatrixTwo-Phase Locking(2PL),cont.2PL guarantees conflict serializabilitytime#locks heldrelease phaseacquisition phaseBut,does not prevent Cascading Aborts.Strict 2PLnProblem:Cascading AbortsnExample:rollback of T1 requires rollback of T2!nStrict Two-phase Locking(Strict 2PL)protocol:Same as 2PL,except:Locks released only when an xact completes i.e.,either:(a)the xact has committed(commit record on disk),or (b)the xact has aborted and rollback is complete.T1:R(A),W(A),R(B),W(B),AbortT2:R(A),W(A)Strict 2PL(continued)#locks heldacquisition phasetimerelease all locks at end of xactNext.nA few examplesLock_X(A)Read(A)Lock_S(A)A:=A-50Write(A)Unlock(A)Read(A)Unlock(A)Lock_S(B)Lock_X(B)Read(B)Unlock(B)PRINT(A+B)Read(B)B:=B+50Write(B)Unlock(B)Non-2PL,A=1000,B=2000,Output=?Lock_X(A)Read(A)Lock_S(A)A:=A-50Write(A)Lock_X(B)Unlock(A)Read(A)Lock_S(B)Read(B)B:=B+50Write(B)Unlock(B)Unlock(A)Read(B)Unlock(B)PRINT(A+B)2PL,A=1000,B=2000,Output=?Lock_X(A)Read(A)Lock_S(A)A:=A-50Write(A)Lock_X(B)Read(B)B:=B+50Write(B)Unlock(A)Unlock(B)Read(A)Lock_S(B)Read(B)PRINT(A+B)Unlock(A)Unlock(B)Strict 2PL,A=1000,B=2000,Output=?Venn Diagram for SchedulesAll SchedulesAvoid Cascading AbortSerialView SerializableConflict Serializable Which schedules does Strict 2PL allow?All SchedulesAvoid Cascading AbortSerialView SerializableConflict SerializableLock ManagementnLock and unlock requests handled by Lock Manager.nLM keeps an entry for each currently held lock.nEntry contains:qList of xacts currently holding lockqType of lock held(shared or exclusive)qQueue of lock requestsLock Management(Contd.)nWhen lock request arrives:qDoes any other transaction hold a conflicting lock?nIf no,grant the lock.nIf yes,put requestor into wait queue.nLock upgrade:qA transaction with shared lock can request to upgrade to exclusive.Lock_X(A)Lock_S(B)Read(B)Lock_S(A)Read(A)A:=A-50Write(A)Lock_X(B)ExampleDeadlocksnDeadlock:Cycle of transactions waiting for locks to be released by each other.nWays of dealing with deadlocks:qpreventionqdetectionqavoidancenMany systems just punt and use TimeoutsqWhat are the dangers with this approach?Deadlock PreventionnCommon technique in operating systemsnStandard approach:resource orderingqScreen Network Card PrinternWhy is this problematic for Xacts in a DBMS?Deadlock DetectionnCreate and maintain a“waits-for”graphnPeriodically check for cycles in graphDeadlock Detection(Continued)Example:T1:S(A),S(D),S(B)T2:X(B),X(C)T3:S(D),S(C),X(A)T4:X(B)T1T2T4T3Deadlock AvoidancenAssign priorities based on timestamps.nSay Ti wants a lock that Tj holds Two policies are possible:Wait-Die:If Ti has higher priority,Ti waits for Tj;otherwise Ti aborts.Wound-wait:If Ti has higher priority,Tj aborts;otherwise Ti waits.nWhy do these schemes guarantee no deadlocks?nImportant detail:If a transaction re-starts,make sure it gets its original timestamp.-Why?Locking GranularitynHard to decide what granularity to lock(tuples vs.pages vs.tables).nwhy?Multiple-Granularity LocksnShouldnt have to make same decision for all transactions!nData“containers”are nested:TuplesTablesPagesDatabasecontainsSolution:New Lock Modes,ProtocolnAllow Xacts to lock at each level,but with a special protocol using new“intent”locks:nStill need S and X locks,but before locking an item,Xact must have proper intent locks on all its ancestors in the granularity hierarchy.vIS Intent to get S lock(s)at finer granularity.vIX Intent to get X lock(s)at finer granularity.vSIX mode:Like S&IX at the same time.Why useful?TuplesTablesPagesDatabaseMultiple Granularity Lock ProtocolnEach Xact starts from the root of the hierarchy.nTo get S or IS lock on a node,must hold IS or IX on parent node.qWhat if Xact holds S on parent?SIX on parent?nTo get X or IX or SIX on a node,must hold IX or SIX on parent node.nMust release locks in bottom-up order.Protocol is correct in that it is equivalent to directly settinglocks at the leaf levels of the hierarchy.TuplesTablesPagesDatabaseLock Compatibility MatrixvIS Intent to get S lock(s)at finer granularity.vIX Intent to get X lock(s)at finer granularity.vSIX mode:Like S&IX at the same time.ISIXSIXISIXSIXSXSX-TuplesTablesPagesDatabaseExamples 2 level hierarchynT1 scans R,and updates a few tuples:qT1 gets an SIX lock on R,then get X lock on tuples that are updated.nT2 uses an index to read only part of R:qT2 gets an IS lock on R,and repeatedly gets an S lock on tuples of R.nT3 reads all of R:qT3 gets an S lock on R.qOR,T3 could behave like T2;can use lock escalation to decide which.qLock escalation dynamically asks for coarser-grained locks when too manylow level locks acquiredIS IXSIXISIXSIX SXSXTuplesTablesJust so youre aware:Optimistic CCnBasic idea:let all transactions run to completionqMake tentative updates on private copies of dataqAt commit time,check schedules for serializabilityqIf you cant guarantee it,restart transactionelse“install”updates in DBMSnPros&ConsqNo waiting or lock overhead in serializable casesqRestarted transactions waste work,slow down othersnOCC a loser to 2PL in traditional DBMSsqPlays a secondary role in some DBMSsnGeneralizations:qMulti-version and Timestamp CC manage the multiple copies in a permanent wayJust So Youre Aware:Indexesn2PL on B+-tree pages is a rotten idea.qWhy?nInstead,do short locks(latches)in a clever wayqIdea:Upper levels of B+-tree just need to direct traffic correctly.Dont need to be serializably handled!qDifferent tricks to exploit thisnNote:this is pretty complicated!Just So Youre Aware:PhantomsnSuppose you query for sailors with rating between 10 and 20,using a B+-treeqTuple-level locks in the Heap FilenI insert a Sailor with rating 12nYou do your query againqYikes!A phantom!qProblem:Serializability assumed a static DB!nWhat we want:lock the logical range 10-20qImagine that lock table!nWhat is done:set locks in indexes cleverlySummarynCorrectness criterion for isolation is“serializability”.qIn practice,we use“conflict serializability,”which is somewhat more restrictive but easy to enforce.nTwo Phase Locking and Strict 2PL:Locks implement the notions of conflict directly.qThe lock manager keeps track of the locks issued.qDeadlocks may arise;can either be prevented or detected.nMulti-Granularity Locking:qAllows flexible tradeoff between lock“scope”in DB,and locking overhead in RAM and CPUnMore to the storyqOptimistic/Multi-version/Timestamp CCqIndex“l(fā)atching”,phantomsCrash 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!