Database Recovery

Recovery is how a database gets back to a correct state after something goes wrong: a transaction aborts, the server crashes, or a disk dies. It is the machinery behind two ACID letters from the transactions lesson: atomicity (undo the work of transactions that did not finish) and durability (keep the work of transactions that did). Interviewers ask about it in two flavours. The theory flavour: what is write-ahead logging, what are undo and redo, what do steal and force mean, how do checkpoints help, and what are the three phases of ARIES. The practical flavour: how would you back up a production database, what is point-in-time recovery, and why is a replica not a backup. This lesson covers both, with a fully worked ARIES example.

Types of failure

Recovery techniques depend on what failed and what was lost. Storage is usually split into three kinds:

• Volatile storage: main memory (RAM) and CPU caches. Lost on power loss or crash.
• Non-volatile storage: SSDs and hard disks. Survives a crash, but a device can fail.
• Stable storage: an idealised storage that never loses data, approximated in practice by keeping several copies on independent devices (RAID, replicas, off-site backups).

The key assumption of crash recovery is fail-stop: when the system crashes, RAM is wiped but whatever was written to disk stays intact. The log is the tool that turns this into a correct state.

Buffer management: steal and force

The database does not read and write disk directly for every change. It keeps a buffer pool: an area of RAM holding copies of disk pages (fixed-size blocks, typically 8 KB in PostgreSQL and 16 KB in InnoDB). A changed page in the buffer pool that has not been written back is a dirty page.

Two policy questions decide how hard recovery is.

Steal or no-steal: may a dirty page of an uncommitted transaction be written to disk?

• Steal: yes. The buffer manager can evict ("steal") the frame for another page whenever it needs room. Good for memory use, but disk may now contain uncommitted data, so after a crash we need undo.
• No-steal: no. Uncommitted changes stay in RAM until commit. No undo is needed, but a big transaction must fit in memory.

Force or no-force: must all of a transaction's dirty pages be written to disk at commit?

• Force: yes. After commit, the data files already contain the changes, so no redo is needed. But commit becomes slow (many random writes), and hot pages are written again and again.
• No-force: no. Pages are written later, in the background. Commit is fast, but a crash may lose committed changes from RAM, so we need redo.

Write-ahead logging (WAL)

The log (also called the journal, the WAL, or in InnoDB the redo log) is an append-only file of records describing every change. Appending sequentially to one file is much faster than updating scattered data pages, which is why logging is cheap.

The write-ahead logging protocol has two rules:

1. Undo rule (before a data page is written). Before a dirty page is written to the data files, all log records describing changes to that page must already be on stable storage. This guarantees we can always undo uncommitted changes that reach disk.
2. Redo rule (before commit is acknowledged). Before a transaction is reported as committed, all its log records, including the commit record, must be on stable storage. This guarantees we can redo committed changes that never reached the data files.

   RAM                                      Disk
  +-------------------+    flush log      +------------------+
  | log buffer        | ----------------> | log file (WAL)   |
  | [..][..][..]      |  (1st, always)    | sequential       |
  +-------------------+                   +------------------+
  +-------------------+    write page     +------------------+
  | buffer pool       | ----------------> | data files       |
  | dirty pages       |  (later, only     | random writes    |
  +-------------------+   after its log)  +------------------+

To enforce rule 1, every page header stores the pageLSN: the log sequence number of the latest log record that changed it. The buffer manager may write a page only when the log has been flushed at least up to that pageLSN.

A log sequence number (LSN) is a unique, increasing identifier for each log record, often the byte offset of the record in the log.

Committing therefore costs one sequential log flush (an fsync), not a scatter of page writes. Databases further amortise this with group commit: several transactions committing at about the same moment share a single flush.

Log records

A typical update log record contains:

Written in textbook shorthand, a transfer of 100 from A (1000) to B (2000) by T1 produces:

<T1 start>
<T1, A, 1000, 900>      transaction, item, old value, new value
<T1, B, 2000, 2100>
<T1 commit>

Other record types:

• Commit: the transaction has committed once this record is on stable storage.
• Abort: the transaction is being rolled back.
• End: all work for the transaction (including any undo) is finished; it can be forgotten.
• Compensation log record (CLR): written while undoing an update. It records the undo action itself, so that if the system crashes during recovery, the undo is not repeated. A CLR is redo-only: it is never undone.

Logging can describe changes physically (the bytes on a page), logically (the operation, such as "insert key 42 into index I") or physiologically (physical to a page, logical within it, such as "insert this record into page 17"). ARIES and most real systems use physiological logging.

Undo and redo

Recovery uses the log with two idempotent operations:

• undo(Ti): go backwards through Ti's log records and restore each item's old value.
• redo(Ti): go forwards through Ti's records and set each item to its new value.

Idempotent means doing it twice gives the same result as doing it once. This matters because the system can crash again in the middle of recovery and run it a second time.

The simple rule after a crash:

• If the log contains <Ti start> and <Ti commit> (or <Ti abort> with its undo completed): redo Ti.
• If the log contains <Ti start> but neither commit nor abort: undo Ti.

Worked example: a simple log

The log on disk after a crash:

<T1 start>
<T1, A, 1000, 900>
<T1, B, 2000, 2100>
<T1 commit>
<T2 start>
<T2, C, 700, 600>
<T3 start>
<T3, D, 50, 80>
<T3 commit>
<T2, A, 900, 950>
   ---- crash ----

Step 1. Classify. T1 and T3 have commit records: redo list = . T2 has no commit: undo list = .

Step 2. Undo T2, scanning backwards: set A back to 900, then C back to 700.

Step 3. Redo T1 and T3, scanning forwards: A = 900, B = 2100, D = 80.

Final values: A = 900, B = 2100, C = 700, D = 80.

The order matters. Note that A was written by both T1 (committed, new value 900) and T2 (uncommitted, new value 950). The textbook simple scheme does undo first, then redo, so A ends at T1's 900. ARIES does it the other way round, redo all history first, then undo the losers, which gives the same result and copes better with fine-grained locking; we will see it below.

Deferred versus immediate update

Two classic designs differ in when changes reach the database.

Deferred update (no-undo/redo)

Changes are recorded only in the log during the transaction; the database is updated only after the transaction's commit record is written.

• If a transaction fails before commit, nothing to undo: the database was never touched. Just ignore its log records.
• After commit, if a crash occurs before all changes are applied, redo from the log.
• Log records need only the new value.
• Drawback: a transaction must keep all its changes buffered until commit (this is a no-steal policy).

Immediate update (undo/redo)

Changes may be applied to the database (buffer and possibly disk) while the transaction is still running, as long as the log record is written first.

• If the transaction aborts or the system crashes before commit, undo using old values.
• If it committed but changes may not be on disk, redo using new values.
• Log records need both old and new values.
• This is what real databases do (steal/no-force).

Checkpoints

Without help, recovery would have to scan the entire log since the database was created. A checkpoint bounds the work.

Simple (consistent) checkpoint

1. Stop accepting new transactions and pause updates.
2. Flush all log records in memory to stable storage.
3. Flush all dirty buffer pages to disk.
4. Write a <checkpoint L> record, where L is the list of transactions active at that moment.
5. Resume.

After a crash, transactions that committed before the checkpoint need nothing: their changes are already on disk. Only transactions active at the checkpoint, or started after it, need attention.

Worked example: which transactions to redo and undo

time --->          checkpoint (Tc)          crash (Tf)
                        |                       |
T1  |=========|c        |                       |
T2       |==============|=======|c              |
T3                      |   |=========|c        |
T4           |==========|=======================|   (no commit)
T5                      |          |============|   (no commit)

• T1 committed before the checkpoint: ignore, its pages were flushed.
• T2 was active at the checkpoint and committed before the crash: redo (from the checkpoint onwards).
• T3 started after the checkpoint and committed: redo.
• T4 was active at the checkpoint and never committed: undo (its undo may need log records from before the checkpoint).
• T5 started after the checkpoint and never committed: undo.

Fuzzy checkpoints

Stopping everything to flush the buffer pool is unacceptable on a busy system. A fuzzy checkpoint does not flush pages and does not stop transactions. It writes a BEGIN_CHECKPOINT record, then an END_CHECKPOINT record containing two tables captured at that moment:

• Transaction table (active transaction table, ATT): each active transaction, its status, and its lastLSN (most recent log record).
• Dirty page table (DPT): each dirty page in the buffer pool and its recLSN: the LSN of the first log record that made it dirty, which is the earliest record that might need to be redone for that page.

Pages are flushed continuously in the background, so the dirty page table stays small. PostgreSQL and InnoDB both use fuzzy-style checkpoints that spread page writes over time (PostgreSQL's checkpoint_completion_target, InnoDB's continuous flushing).

ARIES

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics, published by IBM researchers in 1992) is the reference design for recovery in steal/no-force systems. Its three principles:

1. Write-ahead logging with LSNs on every page.
2. Repeating history during redo: after a crash, redo every logged change, including those of transactions that will later be undone, to bring the database back to exactly its state at the crash.
3. Logging changes during undo: every undo writes a CLR, so undo is never repeated if the system crashes during recovery.

Recovery runs three phases:

 log: ...[begin ckpt]...[end ckpt]................... crash
             |                                         |
 1. Analysis |------------ scan forward -------------->|
             rebuild transaction table, dirty page table
 2. Redo  |---------------- scan forward ------------->|
          from the smallest recLSN in the dirty page table
 3. Undo  |<--------------- scan backward -------------|
          undo losers newest-first, writing CLRs

• Analysis: start at the last checkpoint. Load the ATT and DPT from END_CHECKPOINT, then scan forward. Add transactions as they appear, update their lastLSN, mark commits, remove transactions at their END record. Add a page to the DPT (with recLSN = this LSN) the first time an update to it appears and it is not already there. At the end, transactions still in the ATT without a commit are losers.
• Redo: start at the smallest recLSN in the DPT. For each update or CLR record, redo it unless one of these holds:
  • the page is not in the DPT (it was flushed and not dirtied again), or
  • the record's LSN is less than the page's recLSN (the change was on disk before the page was re-dirtied), or
  • the page's on-disk pageLSN is greater than or equal to the record's LSN (the change is already on the page). This last check requires reading the page. When redoing, set the page's pageLSN to the record's LSN.
• Undo: collect the lastLSN of every loser into a set ToUndo. Repeatedly take the largest LSN in the set:
  • If it is an update: undo it, write a CLR whose undoNextLSN is the update's prevLSN, and add that prevLSN to ToUndo (if there is one; if not, write an END record for the transaction).
  • If it is a CLR: add its undoNextLSN to ToUndo (or write END if it is null). Nothing is undone, since CLRs are never undone.

Worked ARIES example

The log, with four pages P1 to P4 holding items A to D:

LSN  prevLSN  Tx   Record
---  -------  ---  -----------------------------------------
10   -        T1   UPDATE P1: A 10 -> 20
20   -        T2   UPDATE P2: B 5 -> 7
30                 BEGIN_CHECKPOINT
40                 END_CHECKPOINT
                     ATT: T1 (lastLSN 10), T2 (lastLSN 20)
                     DPT: P1 (recLSN 10), P2 (recLSN 20)
50   10       T1   UPDATE P3: C 1 -> 2
60   50       T1   COMMIT
70   20       T2   UPDATE P1: A 20 -> 30
80   60       T1   END
90   -        T3   UPDATE P4: D 0 -> 9
100  70       T2   UPDATE P3: C 2 -> 4
                   ---- crash ----

State of the data files on disk at the crash: P3 was written to disk by the background writer after LSN 50, so its on-disk pageLSN is 50 (C = 2). No other page was written after it was dirtied; P1, P2 and P4 have on-disk pageLSNs older than any record above (A = 10, B = 5, D = 0).

Phase 1: Analysis. Start at BEGIN_CHECKPOINT (30), load the tables at 40, and scan forward.

Result: losers = T2 (lastLSN 100) and T3 (lastLSN 90). T1 is a winner and already finished. DPT = P1: 10, P2: 20, P3: 50, P4: 90.

Note that the DPT says P3 is dirty from LSN 50, although it was actually flushed. Analysis cannot know that without reading the page; the redo phase's pageLSN check will catch it.

Phase 2: Redo. Start at the smallest recLSN = 10, scan forward over update records.

After redo, the database looks exactly as it did at the moment of the crash, including the losers' changes: A = 30, B = 7, C = 4, D = 9. This is "repeating history".

Phase 3: Undo. ToUndo = . Always take the largest.

Final state: A = 20, B = 5, C = 2, D = 0.

Check it against intuition: T1 committed, so its changes (A 10 to 20, C 1 to 2) survive. T2 and T3 never committed, so B is back to 5, A loses T2's 30, C loses T2's 4, and D is back to 0. Correct.

What if the system crashes again during undo, say right after LSN 140 is written? On the next restart, analysis finds T2 with lastLSN 140, a CLR. Redo repeats the CLRs (110, 140) along with everything else. Undo starts from 140, sees it is a CLR, and jumps straight to its undoNextLSN, 20. The updates already undone are never undone twice, and the amount of undo work is bounded.

How real systems map to this

• PostgreSQL has WAL with redo only. Because of MVCC, an uncommitted transaction's row versions can stay in the table; they are invisible because the commit log (pg_xact) marks the transaction as aborted or in progress. So there is no undo phase. To survive torn pages (a page only half-written when power fails), PostgreSQL writes a full copy of each page into the WAL the first time it is modified after a checkpoint (full_page_writes).
• MySQL InnoDB has a redo log (for durability) and undo logs (for rollback and MVCC), close to the ARIES design. It protects against torn pages with the doublewrite buffer: pages are first written to a separate area, then to their real location.
• SQLite offers a rollback journal (the original page contents are saved before changing the database file; on recovery they are copied back) or a WAL mode (new pages are appended to a -wal file and checkpointed into the main file later). You can switch with PRAGMA journal_mode=WAL;.

Shadow paging

Shadow paging is an alternative to logging. The database keeps a page table mapping logical page numbers to disk blocks.

1. When a transaction starts, the current page table is copied; the copy on disk is the shadow page table and is never modified during the transaction.
2. When the transaction modifies a page, it writes the new version to a fresh disk block and points its current page table entry at it. The old block is untouched.
3. To commit, flush the new pages, write the current page table to disk, and then atomically switch a single root pointer from the shadow table to the current table.
4. To abort, or after a crash before the switch, simply discard the current table: the shadow table still describes the old, consistent database.

  Shadow table (on disk, unchanged)     Current table (in use)
  +----+---------+                      +----+---------+
  | p1 | block 4 |                      | p1 | block 9 |  <- new copy
  | p2 | block 5 |                      | p2 | block 5 |  <- shared
  +----+---------+                      +----+---------+

  Disk: block 4 = old p1, block 5 = p2, block 9 = new p1
  Commit: flush block 9 and the current table, then switch the
  root pointer from the shadow table to the current table.

Pure shadow paging is rare in general-purpose databases today, but the idea of copy-on-write with an atomic root switch appears in LMDB, in the CouchDB storage engine, and in file systems such as ZFS and Btrfs.

Backups

Crash recovery handles RAM loss. It does nothing when the disk is gone or when someone runs DELETE FROM orders without a WHERE clause and commits it. That is the job of backups.

Two numbers frame any backup plan:

• RPO (recovery point objective): how much data you can afford to lose, measured in time. "RPO 5 minutes" means at most the last 5 minutes of changes may be lost.
• RTO (recovery time objective): how long you can afford to be down while restoring.

Kinds of backup

Worked example: full backup on Sunday, then daily backups, failure on Thursday morning.

• Incremental scheme: restore Sunday full, then Monday, Tuesday and Wednesday incrementals, in that order (4 pieces).
• Differential scheme: restore Sunday full, then Wednesday's differential (2 pieces). Wednesday's differential contains all changes Monday to Wednesday.

Backups can also be logical or physical:

• Logical: SQL statements or rows, e.g. pg_dump (PostgreSQL) or mysqldump (MySQL). Portable across versions and platforms, easy to restore a single table, but slow for large databases.
• Physical: copies of the data files, e.g. pg_basebackup (PostgreSQL) or Percona XtraBackup and MySQL Enterprise Backup (MySQL). Fast for large databases, restores the whole cluster, tied to the same major version.

Point-in-time recovery (PITR)

Backups taken once a day give an RPO of up to a day. Point-in-time recovery combines a physical base backup with the continuous stream of log records to restore the database to any moment, for example "one second before the bad DELETE".

 Sun 00:00            Wed 14:31:59        Wed 14:32:00
 base backup  --->  replay archived log ---> STOP     (bad DELETE)
 [full copy]        [WAL / binlog files]     recovery target

• PostgreSQL: take a base backup with pg_basebackup, archive every WAL segment with archive_command (or a tool such as pgBackRest or WAL-G), then restore the base backup and set recovery_target_time so replay stops at the chosen moment.
• MySQL: restore a full backup, then replay the binary log (mysqlbinlog --stop-datetime=... piped into mysql) up to the moment before the mistake.

With continuous log archiving, the RPO becomes the time since the last archived log segment, often seconds to a minute.

Backup rules that matter in practice

• Test restores regularly. A backup that has never been restored is a hope, not a backup.
• Follow 3-2-1: three copies of the data, on two different kinds of media, with one copy off-site (another region or account).
• Protect backups from the same blast radius: separate credentials, and immutable or write-once storage so ransomware or a compromised admin account cannot delete them.
• Encrypt backups, and keep the keys somewhere you can still reach after a disaster.

Replication is availability, not backup

Replication keeps one or more copies (replicas) of the database continuously up to date by shipping the log from the primary. It is excellent for high availability: if the primary dies, a replica can be promoted within seconds or minutes, and replicas can serve read traffic. Replication is covered in NoSQL and distributed databases.

But replication faithfully copies every change, including mistakes:

 primary:  DROP TABLE orders;   -- 10:00:00.000
 replica:  DROP TABLE orders;   -- 10:00:00.040  (40 ms later)

Within milliseconds, every replica has lost the table too. Bugs that corrupt data, accidental deletes, and malicious changes all replicate. Only a backup taken before the mistake (ideally with PITR) can bring the data back.

Some teams run a delayed replica (PostgreSQL recovery_min_apply_delay, MySQL SOURCE_DELAY, formerly MASTER_DELAY) that deliberately lags by, say, one hour, giving a window to stop it before a mistake is applied. It helps, but it is a complement to backups, not a replacement.

Interview questions

Q1. What is write-ahead logging?

WAL is the rule that a change must be recorded in the log, and the log flushed to stable storage, before the changed data page is written to disk, and that all of a transaction's log records, including the commit record, must be flushed before the commit is acknowledged. The first rule makes undo possible, the second makes redo possible. Because the log is appended sequentially, commit costs one fast sequential flush instead of many random page writes.

Q2. What are steal and force policies?

Steal means the buffer manager may write a dirty page of an uncommitted transaction to disk; no-steal forbids it. Force means all of a transaction's dirty pages are written to disk at commit; no-force means they can be written later. Steal plus no-force is fastest and is what most databases use, but it requires both undo (for stolen uncommitted pages) and redo (for unforced committed pages).

Q3. Why do we need both undo and redo?

Undo removes the effects of transactions that did not commit but whose changes reached disk, which happens under a steal policy. Redo reapplies changes of committed transactions that had not reached disk, which happens under no-force. With steal and no-force, both cases occur after a crash.

Q4. What is a checkpoint and why is it needed?

A checkpoint records a point from which recovery can start, so the system does not need to scan the whole log. A simple checkpoint flushes all dirty pages and records the active transactions; a fuzzy checkpoint records the active transaction table and the dirty page table without stopping work. Checkpoints also let old log segments be recycled.

Q5. What is the difference between deferred and immediate update?

In deferred update the database is modified only after commit, so recovery never needs undo, only redo, and log records need only new values. In immediate update changes may reach the database before commit, so recovery needs both undo and redo and log records hold old and new values. Real systems use immediate update for performance.

Q6. Describe the three phases of ARIES.

Analysis scans forward from the last checkpoint to rebuild the active transaction table and dirty page table, identifying loser transactions and where redo must start. Redo scans forward from the smallest recLSN and reapplies every change not already on disk, repeating history. Undo rolls back losers by processing their records from the newest LSN backwards, writing a compensation log record for each undo.

Q7. What is a compensation log record?

A CLR is written for every undo action during rollback or recovery. It records the change the undo made and an undoNextLSN pointing to the next record of that transaction still to be undone. If the system crashes during recovery, CLRs are redone but never undone, so work already undone is not repeated and undo always makes progress.

Q8. Why does ARIES redo the changes of loser transactions?

Repeating history restores the database to the exact state at the crash, including page structures such as B+ tree splits. Undo can then be done logically per record using the same code as a normal rollback, and it works with fine-grained (row-level) locking where several transactions modified the same page. It also makes redo independent of transaction outcome, which simplifies it.

Q9. What is the pageLSN used for?

Every page stores the LSN of the latest log record applied to it. The buffer manager uses it to enforce WAL, flushing the log up to pageLSN before writing the page. During redo, if a page's pageLSN is at least a record's LSN, that change is already on the page and is skipped, which makes redo idempotent.

Q10. What is shadow paging?

Shadow paging writes modified pages to new locations and keeps the old page table (the shadow) untouched until commit, when a root pointer is switched atomically to the new table. Abort and crash recovery just discard the new table, so no log is needed. Its drawbacks are page-table copying overhead, data fragmentation and garbage collection, which is why logging dominates.

Q11. Explain full, incremental and differential backups.

A full backup copies everything. An incremental backup copies changes since the last backup of any kind, so a restore needs the full backup plus every incremental in order. A differential copies changes since the last full backup, so a restore needs the full backup plus only the latest differential. Incrementals are smaller to take; differentials are simpler to restore.

Q12. What is point-in-time recovery?

PITR restores a physical base backup and then replays archived log records (PostgreSQL WAL or MySQL binary log) up to a chosen moment, such as just before an accidental delete. It gives an RPO of seconds and lets you recover from logical errors, not just hardware failures.

Q13. Is replication a backup?

No. Replication copies every committed change to replicas almost immediately, including accidental deletes, buggy updates and malicious changes. It provides availability against hardware failure, while backups with PITR let you go back in time to before a mistake. A production system needs both.

Q14. How does PostgreSQL recover without an undo phase?

PostgreSQL's MVCC never overwrites rows in place; an update writes a new tuple version. After a crash, WAL redo restores all changes, and versions created by transactions that did not commit are simply invisible because the transaction status log marks them as aborted. VACUUM later removes those dead versions.

Q15. What are RPO and RTO?

RPO, the recovery point objective, is the maximum acceptable data loss measured in time. RTO, the recovery time objective, is the maximum acceptable downtime. They drive the design: an RPO of seconds needs continuous log archiving or synchronous replication, and a short RTO needs standby replicas and rehearsed failover.

Key takeaways

• Failures range from a single transaction abort to a system crash, disk failure or human error; each needs a different tool.
• Steal and no-force make databases fast but require undo and redo; that combination is the norm.
• Write-ahead logging: log before data page, log flushed before commit; pageLSN enforces it.
• Recovery classifies transactions: committed ones are redone, unfinished ones are undone; undo and redo must be idempotent.
• Checkpoints bound recovery work; fuzzy checkpoints record the transaction table and dirty page table without pausing.
• ARIES: analysis, redo from the smallest recLSN repeating history, undo losers newest-first with CLRs.
• Shadow paging avoids logs with copy-on-write and an atomic root switch but fragments data.
• Backups (full, incremental, differential) plus archived logs give point-in-time recovery; test restores.
• Replication is for availability and copies mistakes instantly; it is never a substitute for backups.

Next lesson

Continue with Query processing and optimization.