AdvancedDBMS & SQL · Lesson 22 of 25 · Updated ·
Database Recovery — Log-Based Recovery, Write-Ahead Logging, Checkpoints, Undo and Redo
You transfer ₹5,000 from your account to a friend's. The bank's server crashes after taking money out of your account but before adding it to your friend's. When the server restarts, the money must not have vanished. Making this work is the job of the recovery manager, and it is how a database delivers Atomicity and Durability from ACID.
1. Types of failure
| Failure | Example | What is lost |
|---|---|---|
| Transaction failure | divide by zero, constraint violation, deadlock victim | only that transaction's work |
| System crash | power cut, OS crash, database process killed | everything in main memory (RAM); the disk survives |
| Disk (media) failure | disk head crash, corrupted storage | data on that disk — needs backups and archived logs |
Recovery has two jobs after a crash:
- Undo the changes of transactions that had not committed (atomicity).
- Redo the changes of transactions that had committed but may not have reached the disk yet (durability).
Why can committed data be missing from the disk? Because databases change pages in a buffer in RAM and write them to disk later, in batches. Writing every change to disk immediately would be far too slow.
2. The log
The log (journal) is an append-only file, kept on stable storage, that records every change before it happens. Typical records:
| Record | Meaning |
|---|---|
<T1 start> | T1 began |
<T1, A, 100, 150> | T1 changed item A from old value 100 to new value 150 |
<T1 commit> | T1 committed |
<T1 abort> | T1 rolled back |
<checkpoint {T2}> | checkpoint taken; T2 was still active |
The old value makes undo possible; the new value makes redo possible.
3. Write-ahead logging (WAL)
Two rules make the log trustworthy:
- Before a changed data page is written to disk, the log records for that change must already be on disk.
- A transaction is committed only when its
<commit>record is on disk.
So at any crash, everything that might be on disk is also described in the log. "Commit" is fast: the database only forces one small, sequential log write — the data pages can follow later. PostgreSQL (its WAL), MySQL InnoDB (the redo log) and SQLite (its WAL mode) all work on this principle.
4. Deferred vs immediate update
| Deferred update | Immediate update | |
|---|---|---|
| When are data pages changed on disk? | only after commit | possibly before commit |
| Needs undo? | no (uncommitted changes never reach disk) | yes |
| Needs redo? | yes | yes |
| Log needs old values? | no | yes |
Real databases use immediate update (with undo and redo), because holding every change in memory until commit does not scale to large transactions.
5. Checkpoints
Without help, recovery would have to read the whole log since the database was created. A checkpoint periodically:
- writes all log records in memory to disk,
- writes all modified (dirty) buffer pages to disk,
- writes a
<checkpoint L>record, where L lists the transactions still active.
After a crash, transactions that committed before the last checkpoint need nothing — their changes are already on disk. Recovery only looks at the log from the last checkpoint (plus the earlier records of the transactions in L).
6. Worked example: undo and redo lists
The log at the moment of the crash (immediate update):
The rules:
- Redo list: transactions with a
<commit>after the last checkpoint. - Undo list: transactions in the checkpoint's active list, or started after it, that have no
<commit>or<abort>. - Redo goes forwards through the log (repeat the changes in the original order). Undo goes backwards (newest change first), writing the old values back.
The program below runs these rules on the log:
log = [('start', 'T1'), ('write', 'T1', 'A', 100, 150), ('start', 'T2'), ('commit', 'T1'),
('checkpoint', ['T2']),
('write', 'T2', 'B', 200, 250), ('start', 'T3'), ('write', 'T3', 'C', 300, 350),
('commit', 'T3'), ('start', 'T4'), ('write', 'T4', 'D', 400, 450)] # then: CRASH
cp = max(i for i, rec in enumerate(log) if rec[0] == 'checkpoint')
committed = {rec[1] for rec in log[cp:] if rec[0] == 'commit'}
candidates = set(log[cp][1]) | {rec[1] for rec in log[cp:] if rec[0] == 'start'}
redo = sorted(committed)
undo = sorted(candidates - committed)
print('Redo:', redo)
print('Undo:', undo)
# worst case: every write reached the disk before the crash
disk = {'A': 150, 'B': 250, 'C': 350, 'D': 450}
for rec in log: # redo forwards (from the start of the relevant records)
if rec[0] == 'write' and rec[1] in redo:
disk[rec[2]] = rec[4]
for rec in reversed(log): # undo backwards
if rec[0] == 'write' and rec[1] in undo:
disk[rec[2]] = rec[3]
print('After recovery:', disk)
Redo: ['T3']
Undo: ['T2', 'T4']
After recovery: {'A': 150, 'B': 200, 'C': 350, 'D': 400}
- T1 committed before the checkpoint: ignored. A = 150 is already safe on disk.
- T2 was active at the checkpoint and never committed: undo, B goes back to 200.
- T3 committed after the checkpoint: redo, C = 350 even if its page never reached the disk.
- T4 was running at the crash: undo, D goes back to 400.
Undo and redo are idempotent: writing "C = 350" twice gives the same result as once. That matters because the system could crash again during recovery, and then it simply starts recovery again.
7. Shadow paging and ARIES
Shadow paging is a recovery method without a log. The database keeps two page tables: the current one, which the transaction changes (copying each page before modifying it), and the shadow one, which still points to the old pages. Commit = atomically switch one pointer to the new page table. Abort or crash = keep the shadow. It needs no undo or redo, but it scatters data across the disk and makes concurrent transactions hard, so large databases rarely use it.
ARIES is the recovery algorithm behind most commercial databases. It has three passes after a crash — analysis (find dirty pages and active transactions), redo (repeat history, including the losers' changes), undo (roll back the losers) — and it logs its own undo steps so that recovery itself survives crashes.
8. Media failure and backups
The log protects against crashes, not against a dead disk. For that, databases combine a periodic full backup with the archived logs written since then: restore the backup, then redo the archived log forward to the moment of failure. This is called point-in-time recovery. Keeping the backup and the logs on a different machine or location protects against a fire or a ransomware attack on the main server.
Common mistakes
- Undoing transactions that committed. Committed transactions are always redone, never undone.
- Undoing in forward order. Undo must go backwards, so the oldest value ends up in place.
- Redoing transactions that committed before the checkpoint. Their pages were flushed at the checkpoint.
- Forgetting active transactions listed inside the checkpoint record, like T2 here.
- Thinking the log can be written after the data page. WAL requires the log first.
Quick recap
- Failures: transaction, system crash (RAM lost), media (disk lost).
- Log records hold old and new values; WAL writes the log before the data page and before reporting commit.
- Deferred update needs only redo; immediate update needs undo and redo.
- After a crash: redo committed transactions (forwards), undo uncommitted ones (backwards), starting from the last checkpoint.
- Shadow paging swaps page tables; ARIES does analysis, redo, undo; backups plus archived logs cover disk failure.