Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 79 ยท Recovery

Failure Classification and Recovery Goals

Learn the three kinds of database failure, the storage types, the steal and no-force buffer policies and why every recovery system needs a log, with live simulations.

Hardware fails, software has bugs, power cords get kicked out of walls. A database that loses data every time something goes wrong would be useless, so the promise of atomicity and durability is one of the most valuable things a DBMS offers. The part of the system that keeps this promise is the recovery manager.

Before looking at how recovery works, this lesson sets the stage: what can fail, what survives each kind of failure, how the buffer manager's choices make recovery easy or hard, and why the answer to almost every question ends up being "keep a log".

Three families of failure

Transaction failure One transaction goes wrong. The system is fine.
System crash Memory is lost. Disks survive.
Media failure The disk itself is damaged.

Each needs a different remedy.

1 / 2

Classifying failures

Transaction failures. A single transaction cannot finish. There are two typical reasons. A logical error is something the transaction itself did: a division by zero, a constraint violation, bad input, an explicit ROLLBACK. A system error is a condition that the DBMS handles by killing a transaction, such as being chosen as the victim of a deadlock or exceeding a time limit. The remedy is local: undo that one transaction's changes and, if appropriate, restart it. Everyone else carries on.

System crashes. The whole server stops: power failure, operating-system panic, a bug in the DBMS, a hardware fault in memory. What is lost is everything in volatile memory, including the buffer pool with its changed but unwritten pages and the state of every running transaction. What is not lost is the disk contents. The usual assumption is fail-stop: when something goes wrong the system halts rather than silently writing garbage to disk. The remedy is restart recovery: when the server comes back, it reads the log and repairs the disk state.

Media (disk) failures. The storage itself is damaged: a head crash, a controller bug that corrupts blocks, a deleted file, a flooded data center. The log and data on that disk may be gone. The remedies are redundancy (RAID, replication to another machine) and backups plus archived logs, which let you rebuild the database and replay changes up to the failure. You will see these in Checkpoints, ARIES and Backups.

There are also failures that no recovery manager can detect: a user who deletes the wrong rows with a perfectly valid statement, or an application bug that writes wrong values. Those are fixed with backups, audit trails and careful processes, not with crash recovery.

Storage types and stable storage

Recovery theory sorts storage by how it reacts to failure:

  • Volatile storage loses its content on a crash: main memory, caches.
  • Non-volatile storage survives crashes and power cuts: magnetic disks, SSDs, tape. It can still fail from a media fault, and a write can be interrupted halfway.
  • Stable storage is an idealization: information is never lost. It cannot truly exist, but you can get close enough by writing every important block to several independent non-volatile devices in a careful order.

Why does the order matter? A disk write is not instantaneous or atomic. If power fails in the middle of writing a block, the block may contain half old and half new bytes (a torn write). To protect against that, a block is written twice. First write copy 1 and wait until it is done, then write copy 2. Each copy has a checksum, so a torn copy can be recognized. On restart:

  • If one copy fails its checksum, copy the other over it.
  • If both are valid but different, the crash came between the two writes. Copy the first to the second so the write completes.

The result is that a block ends up holding either the complete old value or the complete new value, never a mixture.

Python Stable storage with two copies and a crash at every step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the four results. Whichever step the crash interrupts, recovery produces a complete value, and a write that was interrupted before copy 1 finished simply did not happen. A database does the same for its log, which is the one file that must never be damaged, and uses simpler ideas such as checksums on log records.

Buffer management: steal and force

Disk pages are read into the buffer pool in memory, changed there, and written back later. Two choices of the buffer manager decide how much work recovery has to do.

Steal or no-steal. Steal means the buffer manager may write a modified page to disk before the transaction that changed it has committed (typically to free a frame for another page). No-steal forbids it.

Force or no-force. Force means all pages changed by a transaction are written to disk before the transaction commits. No-force lets the commit complete while changed pages are still only in memory.

The four combinations behave very differently after a crash:

Policy Uncommitted changes can be on disk? Committed changes can be missing from disk? Recovery needs
No-steal, force No No Nothing (but slow and inflexible)
No-steal, no-force No Yes Redo
Steal, force Yes No Undo
Steal, no-force Yes Yes Undo and redo

No-steal means a transaction's whole write set must fit in memory, which breaks down for big updates. Force means every commit triggers many scattered random writes to the data files, which is slow, and a popular page could be written to disk over and over. Real systems choose steal, no-force for performance, and pay for it with a recovery manager that can both undo and redo.

Python What is on disk after a crash, for each policy?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This simple model reproduces the table above. Where A shows 150 on disk, T1 never committed, so that value must be removed. Where B shows 200, T2 committed, so 250 must be put back. The recovery manager needs to know which transactions committed and what the old and new values were. Neither fact can be found by looking at the data pages alone.

Why recovery needs a log

After a crash, the data pages are an unreliable mixture: some contain committed work, some uncommitted work, some neither. Memory, where the system knew which transactions were running, has vanished. The only way out is to have written down, in advance and on stable storage, a record of what every transaction did. That record is the log: an append-only sequence of entries such as "T1 started", "T1 changed A from 100 to 150", "T2 committed".

The log is the right tool for three reasons:

  1. It is cheap to force. Appending to a log is sequential I/O, much faster than scattered page writes. Forcing only the log at commit is what makes no-force affordable.
  2. It records old and new values, so a change can be undone (for atomicity) or redone (for durability).
  3. It is the single source of truth about commits. A transaction is committed exactly when its commit record is on stable storage.

Everything in the next lessons follows from these ideas. Logging and Write-Ahead Logging shows the rules that make the log work, and Checkpoints, ARIES and Backups shows how real systems keep recovery fast and handle media failures.

What the recovery manager has to do

Every recovery scheme has two halves:

  • During normal operation, it records enough information (log records, checkpoints, backups) so recovery will be possible. This costs a little time on every transaction.
  • After a failure, it uses that information to restore the database to a state that contains all committed transactions and none of the uncommitted ones.

The trade-off is always between the overhead during normal processing and the time to recover after a crash. Frequent checkpoints speed up recovery but slow down normal work, and the other way around.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A server loses power. Which statement about the data is correct under the usual fail-stop assumption?

    A crash wipes volatile memory, including dirty buffer pages and the list of running transactions. Non-volatile disks keep what was already written to them.
  2. 2. Which buffer policy makes undo necessary after a crash?

    Steal lets pages containing uncommitted changes reach the disk, so after a crash those changes may have to be removed.
  3. 3. Why do real systems choose steal and no-force despite the extra recovery work?

    Steal removes the need to hold every dirty page in memory until commit. No-force avoids writing scattered data pages at each commit, because forcing the sequential log is enough.
  4. 4. A disk is destroyed in a fire. What protects the database?

    Media failure takes the log with it if the log is on the same device. Only independent copies of data and log can rebuild the database.

Summary

  • Failures fall into three classes: transaction failures, system crashes and media failures, each with its own remedy.
  • Volatile memory is lost in a crash; non-volatile disks survive; stable storage is approximated by writing important blocks twice and checking checksums.
  • Steal allows uncommitted changes on disk (needs undo); no-force allows committed changes to be missing from disk (needs redo).
  • Real DBMSs use steal and no-force for speed, so their recovery manager must be able to undo and redo.
  • A log of old and new values, forced to stable storage at commit, is what makes recovery possible.

Next: Logging and Write-Ahead Logging.