Chapter 17: Coping with System FailuresIntegrity or correctness of dataIntegrity or consistency constraintsDefinition:PowerPoint PresentationSlide 6Transaction: collection of actions that preserve consistencyBig assumption:Correctness (informally)How can constraints be violated?We will not consider:ExerciseChapter 17 Recovery ManagementSlide 14Our failure modelSlide 16Slide 17Is this model reasonable?Second order of business:Operations:Slide 21Key problem Unfinished transactionSlide 23Slide 24Slide 25Slide 26One “complication”Slide 28Undo logging rulesRecovery rules: Undo loggingSlide 31Slide 32Redo logging (deferred modification)Redo logging rulesRecovery rules: Redo loggingSlide 36Recovery is very, very SLOW !Solution: Checkpoint (simple version)Example: what to do at recovery?Comparison of undo and redo logging Key drawbacks:Solution: undo/redo logging!RulesRecovery process:Slide 44Non-quiescent checkpointExamples what to do at recovery time?ExampleNonquiescent checkpointReal world actionsSolutionSlide 51Media failure (loss of non-volatile storage)Example 1 Triple modular redundancyExample #2 Redundant writes, Single readsExample #3: DB Dump + LogWhen can log be discarded?SummaryChapter 17 1Chapter 17:Coping with System Failures(Slides by Hector Garcia-Molina,http://www-db.stanford.edu/~hector/cs245/notes.htm)Chapter 17 2Integrity or correctness of data•Would like data to be “accurate” or“correct” at all times EMPNameWhiteGreenGrayAge5234211Chapter 17 3Integrity or consistency constraints•Predicates data must satisfy•Examples:- x is key of relation R- x  y holds in R- Domain(x) = {Red, Blue, Green}is valid index for attribute x of R- no employee should make more thantwice the average salaryChapter 17 4Definition:•Consistent state: satisfies all constraints•Consistent DB: DB in consistent stateChapter 17 5Observation: DB cannot be consistent always!Example: a1 + a2 +…. an = TOT (constraint)Deposit $100 in a2: a2  a2 + 100TOT  TOT + 100Chapter 17 6 a2 TOT..50..1000..150..1000..150..1100Example: a1 + a2 +…. an = TOT (constraint)Deposit $100 in a2: a2  a2 + 100TOT  TOT + 100Chapter 17 7Transaction: collection of actions that preserve consistency Consistent DBConsistent DB’TChapter 17 8Big assumption:If T starts with consistent state + T executes in isolation T leaves consistent stateChapter 17 9Correctness (informally)•If we stop running transactions,DB left consistent•Each transaction sees a consistent DBChapter 17 10How can constraints be violated?•Transaction bug•DBMS bug•Hardware failuree.g., disk crash alters balance of account•Data sharinge.g.: T1: give 10% raise to programmers T2: change programmers  systems analystsChapter 17 11We will not consider:•How to write correct transactions•How to write correct DBMS•Constraint checking & repairThat is, solutions studied here do not need to know constraintsChapter 17 12Exercise•Given a consistency constraint–0 <= A <=B•Which of the transactions preserves consistency?–A := A+B; B := A+B–B := A+B; A := A+B–A := B+1; B := A+1Chapter 17 13Chapter 17 Recovery Management•First order of business:Failure ModelChapter 17 14Events Desired Undesired Expected UnexpectedChapter 17 15Our failure model processormemory diskCPUMDChapter 17 16Desired events: see product manuals….Undesired expected events:System crash- memory lost- cpu halts, resetsUndesired Unexpected: Everything else!that’s it!!Chapter 17 17Examples:•Disk data is lost•Memory lost without CPU halt•CPU implodes wiping out universe….Undesired Unexpected: Everything else!Chapter 17 18Is this model reasonable?Approach: Add low level checks + redundancy to increase probability model holdsE.g., Replicate disk storage (stable store) Memory parity CPU checksChapter 17 19Second order of business:Storage hierarchyMemory DiskxxChapter 17 20Operations:•Input (x): block with x  memory•Output (x): block with x  disk•Read (x,t): do input(x) if necessary t  value of x in block•Write (x,t): do input(x) if necessary value of x in block  tChapter 17 21Exercise•Consider transaction–A := A+B; B := A+B•Assume initially A=5 and B=10•Add read- and write-actions to the computation •Show the effects of the steps on main memory and diskChapter 17 22Key problem Unfinished transactionExample Constraint: A=B T1: A  A  2 B  B  2Chapter 17 23T1: Read (A,t); t  t2Write (A,t);Read (B,t); t  t2Write (B,t);Output (A);Output (B);A: 8B: 8A: 8B: 8memorydisk161616failure!Chapter 17 24•Need atomicity: execute all actions of a transaction or none at allChapter 17 25One solution: undo logging (immediatemodification)due to: Hansel and Gretel, 782 AD•Improved in 784 AD to durable undo loggingChapter 17 26T1: Read (A,t); t  t2 A=BWrite (A,t);Read (B,t); t  t2Write (B,t);Output (A);Output (B);A:8B:8A:8B:8memorydisklog Undo logging (Immediate modification)1616<T1, start><T1, A, 8><T1, commit>16<T1, B, 8>16Chapter 17 27One “complication”•Log is first written in memory•Not written to disk on every actionmemoryDBLogA: 8 16B: 8 16Log:<T1,start><T1, A, 8><T1, B, 8>A: 8B: 816BAD STATE# 1Chapter 17 28One “complication”•Log is first written in memory•Not written to disk on every actionmemoryDB LogA: 8 16B: 8 16Log:<T1,start><T1, A, 8><T1, B, 8><T1, commit>A: 8B: 816BAD STATE# 2<T1, B, 8><T1, commit>...Chapter 17 29Undo logging rules(1) For every action generate undo log record (containing old value)(2) Before x is modified on disk, logrecords pertaining to x must beon disk (write ahead logging: WAL)(3) Before commit is flushed to log, all writes of transaction must bereflected on diskChapter 17 30Recovery rules: Undo logging(1) Let S = set of transactions with <Ti, start> in log, but no<Ti, commit> (or <Ti, abort>) record in log(2) For each <Ti, X, v> in log, in reverse order (latest  earliest) do:- if Ti  S then - write (X, v) - output (X)(3) For each Ti  S do- write <Ti, abort> to logChapter 17 31Exercise•Consider the following undo-log records by two transactions T and U:–<START T>; <T, A, 10>; <START U>, <U, B, 20>; <T, C, 30>; <U, D, 40>; <COMMIT U>; <T, E, 50>; <COMMIT T>–Suppose there is a crash and the last log record on disk is <T, E, 50>.–Describe the actions of the recovery manager.–What if the last log record on disk is <COMMIT,