Logging and recovery: WAL, checkpoints, undo and redo

Part of the free LogicWiz SQL & Databases course, Module 16: Inside the DBMS. The queries and practice run in the app on real Postgres.

Kabir's UPI payment shows "Success", and one second later the bank's server loses power. When it comes back, is the money moved, half moved, or lost? The answer lives in a file called the log.

You'll learn to

• Explain the write-ahead logging rule and why it gives atomicity and durability
• Decide which transactions to undo and which to redo after a crash
• Use a checkpoint to limit how much of the log recovery reads

Learn

Why recovery is needed

Changes are made to pages in a memory buffer and written to disk later. A crash can strike at the worst moment:

• A transaction committed, but its changed pages were still in memory. Durability says the change must survive: we must redo it.
• A transaction was half done, and some of its changed pages already reached disk. Atomicity says it must vanish completely: we must undo it.

To do either, the DBMS needs a record of every change. That record is the log.

The write-ahead log (WAL)

The log is an append-only file of records, each with a log sequence number (LSN):

• <T1 start>, <T1 commit>, <T1 abort>
• <T1, A, 1000, 900>: T1 changed A from 1000 (old value, for undo) to 900 (new value, for redo).

The WAL rule has two parts:

1. A change's log record reaches disk before the changed data page does.
2. A transaction counts as committed only when its commit record is on disk.

Writing the log is fast (one file, appended in order). The data pages can then be written whenever is convenient.

Undo in action: ROLLBACK

BEGIN;
UPDATE accounts SET balance = balance - 5000 WHERE account_id = 1;
SELECT balance AS during FROM accounts WHERE account_id = 1;
ROLLBACK;

SELECT balance AS after_rollback FROM accounts WHERE account_id = 1;

ROLLBACK is an undo you ask for. After a crash, the DBMS does the same thing by itself for every transaction that had not committed.

A log at the moment of the crash

Then the crash. Redo T3 (committed after the checkpoint); undo T2 and T4 (never committed), newest record first: LSN 12, 9, then 4. Final values: A = 900, B = 2000, C = 400.

Checkpoints: where recovery starts

Without help, recovery would read the whole log since the database was born. A checkpoint limits that:

1. Write every changed (dirty) page in memory to disk.
2. Write a <checkpoint> record listing the transactions active right now.

After a crash:

• Transactions that committed before the checkpoint need nothing: their pages are on disk.
• Those that committed after it are redone.
• Those that never committed are undone, even their records from before the checkpoint (like T2's write at LSN 4).

Recovery lists, from a log table

-- redo: committed after the last checkpoint
SELECT txn AS redo
FROM wal_log
WHERE kind = 'commit'
  AND lsn > (SELECT MAX(lsn) FROM wal_log WHERE kind = 'checkpoint');

-- undo: started but never committed
SELECT txn AS undo FROM wal_log WHERE kind = 'start'
EXCEPT
SELECT txn FROM wal_log WHERE kind = 'commit'
ORDER BY undo;

The log is just rows, so the recovery decisions are just queries: T3 to redo, T2 and T4 to undo.

Two classic mistakes. (1) Thinking a checkpoint means "ignore everything before it": a transaction active at the checkpoint may have older records that still need undo. (2) Undoing in the wrong direction: undo goes backwards from the newest record, so each item ends at the old value of the earliest loser write.

Exams name the strategies. Deferred update (no page reaches disk before commit): only redo, no undo. Immediate update (pages may reach disk before commit): undo and redo. In buffer terms: steal (uncommitted pages may be written) needs undo; no-force (committed pages need not be written at commit) needs redo. Real systems use steal/no-force with the ARIES algorithm: analysis, redo (repeat history), then undo the losers. Postgres's WAL is in the pg_wal folder.

In one line

WAL: log before data, commit = commit record on disk; after a crash redo what committed (after the checkpoint), undo what didn't, newest record first.

Interview corner

What is write-ahead logging?

Every change is first written to an append-only log, and a page may reach disk only after its log records have. A transaction is committed once its commit record is flushed. After a crash the log is replayed to redo committed work and undo uncommitted work, which gives atomicity and durability without writing every data page at commit.

Why do databases take checkpoints?

To bound recovery time and log size. A checkpoint flushes dirty pages and records which transactions are active, so recovery can start from it instead of the start of the log, and older log segments can be recycled. Postgres takes one every few minutes (checkpoint_timeout) or when enough WAL has been written.

How do ACID atomicity and durability map to undo and redo?

Atomicity is guaranteed by undo: uncommitted changes that reached disk are rolled back using old values from the log. Durability is guaranteed by redo: committed changes that were still in memory are reapplied using new values from the log.