IF3140 –ManajemenBasis Data Recovery System

1 IF3140 ManajemenBasis DataRecovery SystemSEMESTER I TAHUNAJARAN2021/2022 Tim PengajarIF3140 Semester 1 2021/20221 SumberSilberschatz, Korth, Sudarshan: Database System Concepts , 7thEdition Chapter 19: Recovery System Tim PengajarIF3140 Semester 1 2021/20222 ObjectivesStudents are able to: Explain kinds of failures that can happen in a database System Explain stable storage and Recovery task Explain when and why rollback is needed and how logging assures proper rollback Write a backup plan for a database Tim PengajarIF3140 Semester 1 2021/20223 Outline Tim PengajarIF3140 Semester 1 2021/20224 Failure ClassificationStorage StructureRecovery and AtomicityLog-Based RecoveryShadow PagingRemote Backup SystemsFailure Classification Logical errors: transaction cannot complete due to some internal error condition System errors.

2 The database System must terminate an active transaction due to an error condition ( , deadlock)Transaction failure Fail-stop assumption: non-volatile storage contents are assumed to not be corrupted by System crash Database systems have numerous integrity checks to prevent corruption of disk data System crash Destruction is assumed to be detectable: disk drives use checksums to detect failuresDisk failureFailure ExampleActions taken after a failureto recover the database contents to a state that ensures atomicity, consistency and durabilityActions taken during normal transaction processingto ensure enough information exists to recover from failuresSuppose transaction Titransfers $50 from account Ato account Bsubtract 50 from A add 50 to B Recovery AlgorithmStorage Structure Does not survive System crashesVolatile storage: Survives System crashes But may still fail, losing dataNonvolatile storage.

3 A mythical form of storage that survives all failures Approximated by maintaining multiple copies on distinct nonvolatile mediaStable storage:Stable-Storage Implementation Successful completion Partial failure Total failureBlock transfer can result in Write the information onto the first physical block. Then, write the same information onto the second physical block. The output is completed only after the second write successfully storage media from failure during data transferProtecting Storage Media From FailureRecovery:If either copy is detected to have an error, overwrite itIf both have no error but are different, overwrite the second blockFind inconsistent blocks:Expensive solution: Compare the two copies of every disk blockBetter solution.

4 Record in-progress disk writes on non-volatile storageData Access10 Tim Pengajar IF3140 Semester 1 2020/2021 MemoryDiskABBufferPhysical BlocksBuffer BlocksInput(A)Output(B)XYWorking area of T1 Working area of T2X1X2Y1 Read(X)Write(Y) Recovery and AtomicityLOG-BASED RECOVERYMECHANISMSIN DETAILLESS USED ALTERNATIVE: SHADOW-COPYANDSHADOW-PAGING11 Tim PengajarIF3140 Semester 1 2021/2022 Suppose transaction Titransfers $50 from account Ato account Bsubtract 50 from A add 50 to B Log-Based Recovery A sequence of log records The logis kept on stable storage A log <Ti start> log recordWhen transaction Tistarts <Ti, X, V1, V2>log record Before Tiexecutes write(X)

5 <Ticommit> log record When TifinishesImmediate database modificationDeferred database modificationTransaction T10transfers $50 from account Ato account BValue of A =1000 and B = 2000<T10start> < T10, A, 1000, 950> < T10, B, 2000, 2050> < T10commit>Immediate Database ModificationUpdate log record must be written beforedatabase item is written can take place at any time order can be different from the order in which they are writtenOutput of updated blocks: A transaction is said to have committed when its commit log record is output to stable storage Writes performed by a transaction may still be in the buffer when the transaction commits, and may be output laterTransaction Commit.

6 Immediate Database Modification ExampleBCoutput before T1 commitsBAoutput after T0 commitsLogWriteOutput<T0start> <T0,A, 1000, 950> <T0,B, 2000, 2050> <T0commit> <T1start> <T1, C, 700, 600> <T1commit>A= 950B= 2050C= 600BB , BCBAC oncurrency Control and RecoveryAll concurrent transactions share a single disk buffer and a single logA buffer block can have data items updated by one or more transactionsWe assume strict two-phase , the updates of uncommitted transactions should not be visible to other transactionsLog records of different transactions may be interspersed in the logRecovering from Failure Contains the record <Tistart>, But does not contain either the record <Ticommit> or <Tiabort>.

7 TransactionTineeds to be undone Contains the records <Tistart> And contains the record <Ti commit> or <Tiabort>Transaction Tineeds to be redoneRecovering from Failure Contains the record <Tistart>, But does not contain either the record <Ticommit> or <Tiabort>.TransactionTineeds to be undone Contains the records <Tistart> And contains the record <Ti commit> or <Tiabort>Transaction Tineeds to be redoneundo(Ti) --restores the value of all data items updated by Tito their old values, going backwards from the last log record for Ti Each time a data item X is restored to its old value V a special log record <Ti, X, V> is written out.

8 When undo of a transaction is complete, a log record <Tiabort> is written (Ti) --sets the value of all data items updated by Ti to the new values, going forward from the first log record for Ti No logging is done in this caseImmediate DB Modification Recovery Example<T0 start> <T0, A, 1000, 950> <T0, B, 2000, 2050> Recovery action: undo T0-Log <T0, B, 2000>-Restore B to 2000-Log <T0, A, 1000>-Restore A to 1000-Log <T0abort> <T0 start> <T0, A, 1000, 950> <T0, B, 2000, 2050> <T0 commit> <T1 start> <T1, C, 700, 600> Recovery action: redo T0and undo T1-Set A to 950-Set B to 2050-Log <T1, C, 700>-Restore C to 700-Log <T1abort> <T0 start> <T0, A, 1000, 950> <T0, B, 2000, 2050> <T0 commit> <T1 start> <T1, C, 700, 600> <T1 commit> Recovery action.

9 Redo T0and redo T1-Set A to 950-Set B to 2050-Set C to 600 CheckpointsOutput all log records currently residing in main memory onto stable all modified buffer blocks to the a log record < checkpoint L> onto stable storage where Lis a list of all transactions active at the time of Recovery procedure by periodically performing checkpointingAll updates are stopped while doing checkpointingCheckpoints On RecoveryDuring Recovery we need to consider only the most recent transaction Tithat started before the checkpoint , and transactions that started after Ti. Scan backwards from end of log to find the most recent < checkpoint L> record Only transactions that are in Lor started after the checkpoint need to be redone or undone Transactions that committed or aborted before the checkpoint already have all their updates output to stable earlier part of the log may be needed for undo operations Continue scanning backwards till a record <Tistart> is found for every transaction Tiin L.

10 Parts of log prior to earliest <Tistart> record above are not needed for Recovery and can be erased whenever of CheckpointsT1can be ignoredT2and failuretctft1t2t3t4 Recovery AlgorithmSo far: we covered key conceptsNow: we present the components of the basic Recovery algorithmLater: we present extensions to allow more concurrencyRecovery AlgorithmLogging(during normal operation) <Tistart> at transaction start <Ti, Xj, V1, V2> for each update <Ticommit> at transaction endTransaction rollback (during normal operation) Scan log backwards from the end, and for each log record of Tiof the form <Ti, Xj, V1, V2> Perform the undo by writing V1 to Xj, Write a log record <Ti, Xj, V1> such log records are called compensation log records Once the record <Tistart> is found stop the scan and write the log record <Tiabort> Recovery Algorithm Recovery from Failure replay updates of alltransactions, whether they committed, aborted, or are incompleteRedo phase undo all incomplete transactionsUndo phaseRecovery Algorithm Recovery from FailureRedo phaseUndo phaseFind last <checkpointL> record.