1Chapter 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 salary2Chapter 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 + 1003Chapter 17 7Transaction: collection of actions that preserve consistencyConsistent 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 DB4Chapter 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 programmersT2: 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 needto know constraintsChapter 17 12Exercise• Given a consistency constraint– 0 <= A <=B• Which of the transactions preservesconsistency?– A := A+B; B := A+B– B := A+B; A := A+B– A := B+1; B := A+15Chapter 17 13Chapter 17 Recovery Management• First order of business:Failure ModelChapter 17 14Events Desired Undesired Expected UnexpectedChapter 17 15Our failure model processormemory diskCPUMD6Chapter 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 checks7Chapter 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 thecomputation• Show the effects of the steps on mainmemory and disk8Chapter 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 noneat all9Chapter 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# 110Chapter 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 logrecord (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, allwrites 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 log11Chapter 17 31Exercise• Consider the following undo-log records by twotransactions 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 ondisk is <T, E, 50>.– Describe the actions of the recovery manager.– What if the last log record on disk is <COMMIT, U>?Chapter 17 32What if failure during recovery?No problem! ✏ Undo idempotentChapter 17 33Redo logging (deferred modification)T1: Read(A,t); t t×2; write (A,t); Read(B,t); t t×2; write (B,t);Output(A); Output(B)A: 8B: 8A: 8B: 8memoryDB LOG1616<T1, start><T1, A, 16><T1, B, 16><T1, commit>output1612Chapter 17 34Redo logging rules(1) For every action, generate redo logrecord (containing new value)(2) Before X is modified on disk (DB),all log records for transaction thatmodified X (including commit) must be on disk(3) Flush log at commitChapter 17 35(1) Let S = set of transactions with<Ti, commit> in log(2) For each <Ti, X, v> in log, in forward order (earliest → latest) do:- if Ti ∈ S then Write(X, v) Output(X) optionalRecovery rules: Redo loggingChapter 17 36Exercise• Consider the following redo-log records by twotransactions 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 ondisk is <T, E, 50>.– Describe the actions of the recovery manager.– What if the last log record on disk is <COMMIT,