Crash Recovery

Failure Model

Events can be: desired (things that are supposed to happen) and undesired

Undesired events can be:

  • expected - we know that they may occur so we guard against them
    • system crashes: memory lost, CPU halts, etc
  • unexpected
    • everything else

Memory Hierarchy

Recall that

  • we may be operating on things in memory that have not been flushed to disk yet
  • suppose the power is cut - this means these changes are lost
  • if only a part of transaction was written to disk - the database is left in inconsistent state

Operations

Under this model we define the following operations:

  • input($x$) load block containing $x$ into memory
  • output($x$) flush the block containing $x$ to disk
  • read(database object $x$, variable $t$)
    • load $x$ to memory if not already there (input($x$))
    • write value from $x$ to $t$
  • write(database object $x$, variable $t$)
    • input($x$) if $x$ not in memory
    • replace value of $x$ by $t$ (in memory) - no output to disk yet
    • read and write operate on variables and buffers in memory


Unfinished Transaction

This is the key problem we want to address

Example

  • suppose we have two database items $A$ and $B$ and constraint $A = B$
  • $T_1 = A \leftarrow A \times 2; B \leftarrow B \times B$
  • on low level:
    • (1) read($A, t$); $t \leftarrow t \times 2$;
    • (2) write($A, t$);
    • (3) read($B, t$); $t \leftarrow t \times 2$;
    • (4) write($B, t$);
    • (5) output($A$)
    • (6) output($B$)

suppose a crash happens between (5) and (6)

  • when we get the database back to work, it's not in a consistent state:
  • $A \ne B$:
    • the new results of $A$ was written to disk and it contains 16
    • the new results of $B$ was not written to disk and it contains 8
    • the constraint is not satisfied

Usually deal with it with Database Transaction Log (e.g. Undo/Redo Logging)


See also

Sources