Database recovery is what happens between "the machine lost power" and "the database is open again, with every committed transaction present and no uncommitted change visible". Interviewers probe it because it is where atomicity and durability are actually implemented, and because it explains why the write-ahead log, checkpoints and the buffer pool policies exist at all. For a Backend or AI engineer it explains real operational numbers: why a restart after a crash can take minutes, why checkpoint settings affect both latency spikes and recovery time, and why "committed" means "the log is on stable storage", not "the data page is on disk". This page is the recovery-focused companion to storage-internals-and-wal.html, which covers pages, the buffer pool and the log itself.
Buffer pool policy What it means What recovery must then do
-------------------------------------------------------------------------------------------
NO-STEAL dirty pages of an UNCOMMITTED txn nothing to undo on disk, but a
may never be written to disk big txn must fit in memory
STEAL the pool may evict such a page to UNDO: erase uncommitted changes
make room that already reached disk
FORCE at commit, write every page the txn nothing to redo, but commit does
changed to the data files many random writes
NO-FORCE at commit, only the log is flushed; REDO: reapply committed changes
data pages are written lazily that were not on disk yet
Most engines use STEAL + NO-FORCE: best runtime performance, hardest recovery.
The log is what makes it safe: UNDO info for stolen pages, REDO info for unforced pages.Two independent policy choices decide what the recovery code must do. Steal lets the buffer manager evict a dirty page belonging to a transaction that has not committed yet, which keeps large transactions from being limited by memory but means the data file can contain changes that must be erased after a crash. No-force lets a transaction commit by flushing only its (small, sequential) log records, which is far cheaper than flushing every modified data page, but means committed changes may exist only in the log after a crash. Steal creates the need for undo; no-force creates the need for redo. Engines that pick the fast runtime combination pay for it with a recovery procedure, and the log is the mechanism that pays the bill.
LSN txn type page before after prevLSN
1 T1 UPDATE A 100 150 -
2 T2 UPDATE B 200 250 -
3 T1 COMMIT - - - 1
4 -- CHECKPOINT dirty pages {A:1, B:2} active txns {T2}
5 T2 UPDATE C 300 350 2
...
pageLSN = LSN of the last log record applied to that page (stored IN the page)
flushedLSN = highest LSN safely on stable log storage
WAL rule 1 (undo safety): before a dirty page is written to disk, all log records up to
its pageLSN must already be on the log disk
WAL rule 2 (redo safety): a transaction is committed only after its COMMIT record
(and everything before it) is on the log diskEach log record carries enough information to redo the change (the after image, or an operation that reproduces it) and to undo it (the before image, or an inverse operation), plus the transaction id and a link to that transaction's previous record so its history can be walked backwards. The pageLSN stored inside every data page is the key to idempotent redo: recovery compares it to a record's LSN and applies the record only if the page has not seen it yet. Rule 1 guarantees that if a stolen page reached disk, the log to undo it exists; rule 2 guarantees that anything a client was told is committed can be redone. Violate either rule and recovery cannot be correct, which is why "write-ahead" is in the name. Real engines generally log physiological records (physical to a page, logical within it) rather than SQL statements.
log: ... [1][2][3] [CHECKPOINT: dirty pages={A:1,B:2}, active={T2}] [5][6][7] CRASH
^
| fuzzy checkpoint: written WHILE transactions keep running
Sharp checkpoint: stop, flush all dirty pages, then record (simple, causes a stall)
Fuzzy checkpoint: just record the dirty page table + active txn table; pages are
flushed in the background over time (what real engines do)
Where does redo start? at the smallest recLSN in the dirty page table
(the LSN that first dirtied a page that may not be on disk)
Cost dial: frequent checkpoints --> short recovery, more background write I/O
rare checkpoints --> long recovery, more WAL retained, bursty I/OWithout a checkpoint, recovery would have to read the log from the beginning of time. A checkpoint records where it is safe to start: the set of pages that might be dirty (the dirty page table, each with the LSN that first dirtied it) and the set of transactions that were active. A fuzzy checkpoint does not stop the world; it snapshots those two tables and lets a background writer continue to flush pages, so recovery still needs the scan to start slightly before the checkpoint, at the oldest dirtying LSN. The knobs are engine specific (PostgreSQL checkpoint_timeout and max_wal_size, InnoDB redo log capacity), but they all set the same trade-off between recovery time and steady-state write I/O.
oldest recLSN last checkpoint end of log (crash)
log ---------------|----------------------|------------------------------|
^ ^ ^
REDO starts here-+ ANALYSIS starts ---+ ...and scans forward to here
1. ANALYSIS scan forward from the checkpoint
rebuild: dirty page table (which pages may be stale on disk)
transaction table (who was active at the crash = "losers")
2. REDO scan forward from the oldest recLSN: "repeat history"
reapply every logged change (winners AND losers) whose LSN is newer than the
page's pageLSN; skip the rest. Database now equals its exact state at the crash.
3. UNDO roll back every loser, newest change first, following prevLSN links
for each undone change write a Compensation Log Record (CLR)
CLRs are redo-only and point past the record they undo (undoNextLSN), so a crash
DURING recovery does not undo the same change twiceARIES (Algorithms for Recovery and Isolation Exploiting Semantics, from IBM Research) is the textbook design behind this, and several engines, SQL Server among them, use a recovery scheme of this shape; other engines differ in details. Its central idea is repeat history: redo everything, including work of transactions that will be rolled back, so that undo can run against a state that is exactly what the crashed system had, which makes fine-grained locking and partial rollbacks safe. Analysis decides what is needed, redo restores the crash-time state, undo removes losers. Recording undo work as CLRs is what makes recovery restartable: if the machine crashes again in the middle of recovery, the next attempt simply redoes those CLRs and continues undoing where it left off, without undoing anything twice. The toy simulation in the last section implements the three passes on three pages and four transactions.
PostgreSQL InnoDB (MySQL) SQL Server
undo of no undo pass: MVCC keeps redo log replayed, then analysis / redo / undo
losers old row versions in the heap, incomplete txns rolled back phases from the
uncommitted xids are simply using UNDO LOGS transaction log
invisible; VACUUM cleans up
redo start last checkpoint's redo point from the checkpoint LSN from the checkpoint /
oldest active LSN
torn pages full_page_writes (full page doublewrite buffer page checksums / torn
image in WAL after checkpoint) page detectionThe textbook algorithm is a model, not a description of every engine. PostgreSQL's multi-version heap means aborted changes never overwrite the previous version, so crash recovery is essentially a redo pass and uncommitted row versions are just ignored until vacuumed. InnoDB keeps old versions in undo logs, so after redo it must roll back transactions that had not committed. SQL Server follows the analysis/redo/undo structure and additionally offers accelerated database recovery to shorten the undo phase. When answering in an interview, state the general structure and then name the engine before claiming specific behaviour.
COMMIT record is on stable log storage. Data pages may still be only in memory.pageLSN; redo applies a record only if the page's LSN is smaller, which makes redo idempotent, so recovery can safely be run repeatedly.DELETE. Those need backups and point-in-time recovery, and replication is not a backup.fsync; volatile disk caches without power-loss protection can break it.pageLSN.pageLSN first.pageLSN, restoring exactly the crash-time state, including the losers' changes.A toy ARIES-style engine in Python: three pages, a buffer pool with steal + no-force, a log that is flushed at commit and before a page write, a checkpoint, a crash that discards memory and the unflushed log tail, and the three recovery passes. Save as wal_toy.py and run python3 wal_toy.py.
# Toy ARIES-style recovery: steal + no-force, WAL rule, analysis / redo / undo.
# Pages hold a single integer value plus a pageLSN. Disk survives the crash; memory does not.
class DB:
def __init__(self):
self.disk = {"A": (100, 0), "B": (200, 0), "C": (300, 0)} # page -> (value, pageLSN)
self.log_disk = [] # WAL records that reached stable storage
self.log_buf = [] # WAL records still only in memory
self.pool = {} # buffer pool: page -> [value, pageLSN]
self.lsn = 0
self.last_lsn = {} # txn -> its most recent LSN (prevLSN chain)
def _log(self, **rec):
self.lsn += 1
rec["lsn"] = self.lsn
self.log_buf.append(rec)
return self.lsn
def flush_log(self, upto=None):
keep = []
for r in self.log_buf:
(self.log_disk if upto is None or r["lsn"] <= upto else keep).append(r)
self.log_buf = keep
def _get(self, p):
if p not in self.pool:
self.pool[p] = list(self.disk[p])
return self.pool[p]
def update(self, txn, page, new):
pg = self._get(page)
lsn = self._log(type="UPDATE", txn=txn, page=page, before=pg[0], after=new,
prev=self.last_lsn.get(txn))
self.last_lsn[txn] = lsn
pg[0], pg[1] = new, lsn
def commit(self, txn):
lsn = self._log(type="COMMIT", txn=txn, prev=self.last_lsn.get(txn))
self.flush_log() # force the LOG at commit (not the data pages)
def flush_page(self, page): # STEAL: allowed even if the txn is uncommitted
value, plsn = self.pool[page]
self.flush_log(upto=plsn) # WAL rule: log up to pageLSN first
self.disk[page] = (value, plsn)
def checkpoint(self):
dpt = {p: v[1] for p, v in self.pool.items() if tuple(v) != self.disk[p]}
active = sorted(t for t, l in self.last_lsn.items() if not self._done(t))
self._log(type="CHECKPOINT", dirty=dpt, active=active)
self.flush_log()
def _done(self, t):
return any(r["type"] in ("COMMIT", "ABORT_END") and r["txn"] == t
for r in self.log_disk + self.log_buf)
def crash(self):
self.pool, self.log_buf = {}, [] # RAM and unflushed log tail are lost
def recover(db):
log = db.log_disk
print("--- ANALYSIS ---")
start, dpt, losers = 0, {}, set()
for r in log:
if r["type"] == "CHECKPOINT":
dpt, losers = dict(r["dirty"]), set(r["active"])
start = r["lsn"]
for r in log:
if r["lsn"] <= start:
continue
if r["type"] == "UPDATE":
losers.add(r["txn"]); dpt.setdefault(r["page"], r["lsn"])
elif r["type"] == "COMMIT":
losers.discard(r["txn"])
print("scan from checkpoint LSN", start, "| dirty page table:", dpt, "| losers:", sorted(losers))
print("--- REDO (repeat history, winners AND losers) ---")
redo_from = min(dpt.values()) if dpt else start
for r in log:
if r["type"] not in ("UPDATE", "CLR") or r["lsn"] < redo_from:
continue
val, plsn = db.disk[r["page"]]
if plsn >= r["lsn"]:
print(f"LSN {r['lsn']:>2} {r['type']:<6} page {r['page']}: skip (pageLSN {plsn} >= {r['lsn']}, already on disk)")
else:
db.disk[r["page"]] = (r["after"], r["lsn"])
print(f"LSN {r['lsn']:>2} {r['type']:<6} page {r['page']}: redo -> {r['after']}")
print("--- UNDO (roll back losers, newest first, writing CLRs) ---")
todo = sorted((r for r in log if r["type"] == "UPDATE" and r["txn"] in losers),
key=lambda r: -r["lsn"])
nxt = max(r["lsn"] for r in log) + 1
for r in todo:
db.disk[r["page"]] = (r["before"], nxt)
print(f"undo LSN {r['lsn']:>2} (txn {r['txn']}) page {r['page']} -> {r['before']} [CLR written as LSN {nxt}]")
nxt += 1
db = DB()
db.update("T1", "A", 150) # LSN 1
db.update("T2", "B", 250) # LSN 2
db.commit("T1") # LSN 3 (log flushed, page A NOT written: no-force)
db.checkpoint() # LSN 4 (A and B are dirty)
db.flush_page("B") # steal: T2 is uncommitted, page B still goes to disk
db.update("T2", "C", 350) # LSN 5 (only in memory + log buffer)
db.update("T3", "A", 175) # LSN 6 (in the log buffer only)
db.commit("T3") # LSN 7 (log flushed -> T3 is durable)
db.update("T4", "C", 999) # LSN 8 (log buffer only: lost in the crash)
print("BEFORE CRASH disk:", {p: v[0] for p, v in db.disk.items()})
print("stable log :", [(r['lsn'], r['type'], r.get('txn')) for r in db.log_disk])
db.crash()
print("*** CRASH *** (buffer pool and unflushed log tail lost)")
print("disk after crash:", {p: v[0] for p, v in db.disk.items()})
print()
recover(db)
print()
print("AFTER RECOVERY disk:", {p: v[0] for p, v in db.disk.items()})
print("expected: A=175 (T1, T3 committed), B=200 (T2 undone), C=300 (T2 undone, T4 never logged)")Real output from running the script above (Python 3):
BEFORE CRASH disk: {'A': 100, 'B': 250, 'C': 300}
stable log : [(1, 'UPDATE', 'T1'), (2, 'UPDATE', 'T2'), (3, 'COMMIT', 'T1'), (4, 'CHECKPOINT', None), (5, 'UPDATE', 'T2'), (6, 'UPDATE', 'T3'), (7, 'COMMIT', 'T3')]
*** CRASH *** (buffer pool and unflushed log tail lost)
disk after crash: {'A': 100, 'B': 250, 'C': 300}
--- ANALYSIS ---
scan from checkpoint LSN 4 | dirty page table: {'A': 1, 'B': 2, 'C': 5} | losers: ['T2']
--- REDO (repeat history, winners AND losers) ---
LSN 1 UPDATE page A: redo -> 150
LSN 2 UPDATE page B: skip (pageLSN 2 >= 2, already on disk)
LSN 5 UPDATE page C: redo -> 350
LSN 6 UPDATE page A: redo -> 175
--- UNDO (roll back losers, newest first, writing CLRs) ---
undo LSN 5 (txn T2) page C -> 300 [CLR written as LSN 8]
undo LSN 2 (txn T2) page B -> 200 [CLR written as LSN 9]
AFTER RECOVERY disk: {'A': 175, 'B': 200, 'C': 300}
expected: A=175 (T1, T3 committed), B=200 (T2 undone), C=300 (T2 undone, T4 never logged)Read the output against the scenario. T1 and T3 committed, so their changes to page A must survive (100 became 150, then 175), and page A was never written to disk before the crash, so only redo can bring it back (no-force). T2 never committed, yet its change to page B did reach disk (steal), so undo must restore 200. T2's change to C only existed in memory and the log, so redo brings it back first and undo then removes it. T4 never had its log record flushed, so as far as the database is concerned it never happened. The redo pass skipped LSN 2 because page B's on-disk pageLSN already showed it applied.
-- PostgreSQL (cannot be run in the sandbox; no output is shown)
-- Inspect the checkpoint and WAL position on a running server:
SELECT pg_current_wal_lsn();
CHECKPOINT; -- force a checkpoint now (needs privileges)
-- Related settings to read, not to change casually:
SHOW checkpoint_timeout;
SHOW max_wal_size;
SHOW full_page_writes;
-- After an unclean shutdown the server log reports "database system was not properly shut down;
-- automatic recovery in progress", then the redo start/end positions.Q: What steps does a database take to recover after a crash?
A: It locates the last checkpoint, then in the ARIES model runs analysis to rebuild which pages may be stale and which transactions were still active, redo to reapply logged changes so the database matches its exact crash-time state, and undo to roll back the transactions that never committed. The result is that every committed transaction is present and no uncommitted change is visible. The exact mechanics differ by engine; for example PostgreSQL's MVCC heap makes the undo step largely unnecessary, since uncommitted row versions are simply invisible.
Q: Explain the analysis, redo and undo phases and why redo also replays losers.
A: Analysis scans forward from the checkpoint to build the dirty page table and the set of loser transactions. Redo repeats history for every record whose LSN is newer than the page's pageLSN, including changes from transactions that will be rolled back, because that reproduces the precise crash-time state that the undo information was recorded against. Undo then rolls back the losers newest-first and logs compensation records so a crash during recovery does not repeat work.
Q: What is a checkpoint and what does it buy you?
A: A checkpoint records the dirty page table and active transactions (and flushes dirty pages in the background) so recovery can start from a recent point instead of the beginning of the log, and so older log can be recycled. It trades recovery time against write I/O: frequent checkpoints shorten recovery and generate more background writes, rare ones save writes but lengthen recovery and retain more log. Fuzzy checkpoints avoid stalling transactions, which is why real engines use them.
Q: What is the write-ahead rule and why does it exist?
A: Log records describing a change must reach stable storage before the changed data page does, and the commit record must be durable before commit is acknowledged. The first makes undo possible for a stolen page and the second makes redo possible for a page that was never flushed. It works because log writes are sequential and cheap while data page writes are random, so the design pays a small sequential cost at commit and defers the expensive writes.
Q: What do steal and no-force mean, and what does each imply for recovery?
A: Steal lets the buffer manager write dirty pages of uncommitted transactions to disk, which frees memory but means undo is needed. No-force lets commit skip flushing data pages, which makes commits fast but means redo is needed. Steal + no-force gives the best runtime performance and requires both undo and redo, whereas no-steal + force would need neither but forces big transactions into memory and makes every commit do many random writes.
Follow-up: What happens if the server crashes again during recovery?
A: Recovery is designed to be restartable. Redo is idempotent because the pageLSN test skips already applied records, and every undo step is logged as a redo-only compensation record that points past the record it undid, so the next run redoes the compensation records and continues undoing from where it stopped instead of undoing the same change twice.
Follow-up: Does recovery protect against a corrupted disk or an accidental DELETE?
A: No. Crash recovery restores consistency after a server or power failure using the local log and data files. Disk loss needs a backup or a replica, and a bad DELETE that was committed is a committed transaction, so it also replicates. For that you need point-in-time recovery: a base backup plus archived WAL replayed up to just before the mistake.
Follow-up: Why not just force all pages at commit and skip the redo machinery?
A: Force turns every commit into many random writes to scattered pages (table pages, index pages, and more), which is far slower than one sequential log flush, and it still would not be atomic if the crash happened halfway through writing those pages, so you would need a log or shadow paging anyway. The log-based approach makes commit cost roughly one flush and gets atomicity from the log.
Recovery mechanics turn into capacity and availability numbers. Restart time after a crash is bounded by how much log lies between the last checkpoint and the crash, so a system with a strict recovery-time objective tunes checkpoint spacing and WAL size, and pairs it with a hot standby so failover does not depend on a long local recovery at all. The same log is the backbone of replication (a standby continuously replays the primary's WAL, which is redo running forever) and of point-in-time recovery, so backup design, replica lag and crash behaviour are all consequences of one component. It also explains why durability settings matter when designing ingest paths: relaxing the commit flush is a legitimate choice for metrics or derived data but never for orders or payments, and why a disk or virtualization layer that lies about flushes silently invalidates the whole guarantee. For an AI backend that stores documents, embeddings and job state in PostgreSQL, this is what lets you treat the database as the durable source of truth and rebuild derived stores (caches, search indexes, vector indexes) from it after failures.
Steal + no-force with a write-ahead log buys fast commits and flexible memory use, and the price is a recovery procedure, a log that is written in addition to the data pages, and a knob (checkpoint frequency) that trades recovery time against steady-state I/O and latency spikes. Aggressive checkpointing shortens crash recovery but increases write amplification and, in PostgreSQL, full-page images in the log; lazy checkpointing does the opposite. Relaxing durability (asynchronous commit, delayed log flush) is faster but can lose the most recent commits after a crash, which is wrong for money or orders. And nothing here replaces backups: crash recovery restores the last consistent state of one machine, not lost disks, corrupted files, or human mistakes, so you still need base backups with archived logs, tested restores, and replication for availability.