DSA, Database System & Operating System — Transaction Processing, Concurrency Control & Recovery, NEC licence examination syllabus (Nepal Engineering Council).
Log-Based Recovery
Deferred versus immediate modification, and how the log is actually organised on disk.
🌍 Where this lives: the log is not only a recovery mechanism — it is the most reused data structure in modern infrastructure. Streaming replication ships WAL records to a standby, so a replica is just a server permanently in recovery. Change-data-capture tools (Debezium) read the same log to publish every row change to Kafka. Point-in-time recovery replays archived WAL to a chosen instant. And Kafka itself is only a log. Learning this topic teaches you a structure you will meet again in replication, event sourcing and audit systems. Search "the log: what every software engineer should know" — Jay Kreps' essay is the canonical read.
Log record types
<T, START> T has begun
<T, X, old_value, new_value> T changed data item X
<T, COMMIT> T completed successfully
<T, ABORT> T was rolled back
<CHECKPOINT L> a checkpoint; L = active txns
Additional records real systems use:
<T, X, new_value> REDO-ONLY (deferred modification)
<T, X, old_value> UNDO-ONLY (compensation)
<CLR: T, X, old> compensation log record — logs
the undo work itself, so a crash
during recovery does not redo it
EVERY RECORD IS IDENTIFIED BY AN LSN (log sequence number), a
monotonically increasing position in the log. PostgreSQL
exposes it directly:
SELECT pg_current_wal_lsn(); → 0/1055AD50
^^^ ^^^^^^^^
file byte offset
Because LSNs increase, they double as a global clock: "page
42 has LSN 0/1055AD50" means "this page reflects every change
up to that log position". Recovery uses that to skip pages
that are already current.
THE LOG IS WRITTEN SEQUENTIALLY AND NEVER MODIFIED. Records
are appended; nothing is ever edited in place. That property
is what makes it cheap, and it is why the same structure works
for replication and change capture.
Deferred versus immediate modification
Two strategies, distinguished by WHEN the database is actually
changed.
DEFERRED MODIFICATION (NO-UNDO/REDO)
· the database is NOT touched until the transaction commits
· all changes accumulate in the log (and in memory)
· log records need only the NEW value
· at commit: write <T,COMMIT>, then apply the changes
RECOVERY: REDO committed transactions.
NO UNDO EVER — an uncommitted transaction never
touched the database, so there is nothing to
undo.
✔ simplest recovery
✗ a transaction cannot read its own uncommitted writes
without extra machinery
✗ large transactions must buffer everything
IMMEDIATE MODIFICATION (UNDO/REDO)
· the database is changed as the transaction proceeds
· log records carry BOTH old and new values
· dirty pages may reach disk before commit (STEAL)
RECOVERY: REDO committed transactions,
UNDO uncommitted ones.
✔ no limit on transaction size; reads see own writes
✗ recovery must do both passes
THE FOUR COMBINATIONS, and which real systems pick:
UNDO needed? REDO needed?
STEAL + NO-FORCE yes yes ← everyone
STEAL + FORCE yes no
NO-STEAL + NO-FORCE no yes ← deferred
NO-STEAL + FORCE no no ← slowest
The no-undo/no-redo corner sounds ideal and is unusable: it
forbids writing uncommitted pages AND requires flushing every
page at commit.
WORKED COMPARISON — the same transaction under both schemes.
T1: A = 1000 → 700, B = 500 → 800. Crash after
<T1,COMMIT> is written but before pages are flushed.
DEFERRED:
log: <T1,START> <T1,A,700> <T1,B,800> <T1,COMMIT>
disk at crash: A=1000, B=500 (untouched)
recovery: REDO → A=700, B=800 ✔
no undo required
IMMEDIATE:
log: <T1,START> <T1,A,1000,700> <T1,B,500,800> <T1,COMMIT>
disk at crash: possibly A=700 already, B=500
recovery: REDO both → A=700, B=800 ✔
(redo is idempotent, so re-applying A=700 is harmless)
Now crash BEFORE <T1,COMMIT>:
DEFERRED: disk untouched → do nothing. ✔
IMMEDIATE: disk may hold A=700 → UNDO → A=1000. ✔
That final line is the whole difference: immediate
modification needs the old value, deferred does not.
Worked recovery — a full log trace
GIVEN this log at the moment of a crash (immediate
modification, checkpoint present):
1 <T1, START>
2 <T1, A, 100, 150>
3 <T1, COMMIT>
4 <T2, START>
5 <T2, B, 200, 250>
6 <CHECKPOINT {T2}>
7 <T3, START>
8 <T3, C, 300, 350>
9 <T2, B, 250, 275>
10 <T2, COMMIT>
11 <T4, START>
12 <T4, D, 400, 450>
13 <T3, C, 350, 380>
⟵ CRASH
STEP 1 — find the last checkpoint: record 6, active = {T2}.
STEP 2 — ANALYSIS, scanning forward from record 6:
start with UNDO = {T2} (from the checkpoint's list)
record 7 <T3,START> → UNDO = {T2, T3}
record 10 <T2,COMMIT> → move T2 to REDO
UNDO = {T3}, REDO = {T2}
record 11 <T4,START> → UNDO = {T3, T4}
end of log.
REDO = {T2}
UNDO = {T3, T4}
T1 committed BEFORE the checkpoint, so its changes are
already on disk — it appears in neither list. That is
exactly what the checkpoint buys.
STEP 3 — REDO, forward from the checkpoint:
record 9 B := 275 (T2 is in REDO)
T2's earlier change at record 5 is before the checkpoint
and already on disk, but many implementations redo from
the checkpoint's redo_lsn regardless — idempotent, so
harmless.
STEP 4 — UNDO, backward from the end:
record 13 <T3,C,350,380> → C := 350
record 12 <T4,D,400,450> → D := 400
record 8 <T3,C,300,350> → C := 300
stop when every transaction in UNDO has had its START
record reached.
Write <T3,ABORT> and <T4,ABORT>.
FINAL VALUES:
A = 150 (T1, committed before the checkpoint)
B = 275 (T2, redone)
C = 300 (T3, fully undone)
D = 400 (T4, fully undone)
CHECK: every committed transaction's effect is present; no
uncommitted transaction left a trace. ✔
THE TWO PLACES STUDENTS LOSE MARKS:
1. undoing FORWARDS. C would end at 350 instead of 300.
2. forgetting that the checkpoint's active list SEEDS the
undo set — T2 must be in it at the start of analysis,
even though its START record is before the checkpoint.
Note that undo must scan back past the checkpoint. T3's first change is at record 8, which is after the checkpoint, but a transaction active at the checkpoint (like T2, had it not committed) would have records before it. That is why the checkpoint bounds redo but not necessarily undo — a detail most summaries omit.
The log on disk, in a real system
wal.sql
-- Measured on PostgreSQL 18.
-- ===== the settings that define durability =====
SHOW wal_level; -- replica
SHOW synchronous_commit; -- on → COMMIT waits for fsync
SHOW fsync; -- on → actually flush to the device
SHOW full_page_writes; -- on → guard against torn pages
SHOW checkpoint_timeout; -- 5min
SHOW max_wal_size; -- 1GB-- ===== the current log position =====
SELECT pg_current_wal_lsn();
-- pg_current_wal_lsn
-- --------------------
-- 0/1055AD50
-- ===== where recovery WOULD start right now =====SELECT checkpoint_lsn, redo_lsn, timeline_id
FROM pg_control_checkpoint();-- checkpoint_lsn | redo_lsn | timeline_id
-- ---------------+------------+-------------
-- 0/10320650 | 0/103205F8 | 1
--
-- redo_lsn is the recovery start point stored in the control
-- file. The distance from redo_lsn to the current LSN is
-- exactly how much log a crash right now would have to
-- replay — a directly measurable recovery-time estimate.
SELECT pg_size_pretty(
pg_wal_lsn_diff(pg_current_wal_lsn(),
(SELECT redo_lsn FROM pg_control_checkpoint())))
AS replay_on_crash;
-- The smaller this number, the faster a crash recovery.
-- Lowering checkpoint_timeout shrinks it, at the cost of
-- more background I/O.
-- ===== WHY full_page_writes exists — the TORN PAGE problem =
-- A PostgreSQL page is 8 KB; a disk sector is 512 B or 4 KB.
-- A power failure mid-write can leave a page half-old and
-- half-new — a state no log record describes, because the
-- record assumes the page was internally consistent.
--
-- The fix: the first time a page is modified after a
-- checkpoint, write the ENTIRE page image into the WAL.
-- Recovery can then restore the whole page rather than
-- patching a corrupt one.
--
-- The cost: WAL volume grows substantially right after each
-- checkpoint. That is why WAL is much larger than the data
-- actually changed — the 1,830 kB measured for 5,000 small
-- rows includes full-page images.
MEASURING AMPLIFICATION PROPERLY — compare WAL against the
TABLE size, not against the raw payload:
CREATE TABLE amp (id serial primary key, payload text);
SELECT pg_current_wal_lsn() AS l0 \gset
INSERT INTO amp (payload)
SELECT repeat('x',200) FROM generate_series(1,5000);
SELECT pg_wal_lsn_diff(pg_current_wal_lsn(), :'l0') AS wal_bytes,
pg_size_pretty(pg_relation_size('amp')) AS table_size;
MEASURED RESULT:
wal_bytes | wal_pretty | table_size | amplification
-----------+------------+------------+---------------
1679048 | 1640 kB | 1184 kB | 1.38
→ 1.38× : the log is 38% larger than the table it built.
WHERE THE EXTRA 38% GOES:
· per-record headers (~24 bytes each)
· the B-tree index on the primary key — every index change
is logged too
· full-page images for pages first touched since the last
checkpoint
Note the first figure earlier in this topic (1,830 kB) was
measured on a table that already held rows and had a
checkpoint boundary inside the window, so it carried more
full-page images. Amplification is not a fixed constant: it
depends on how many pages are being touched for the first
time since the last checkpoint. Measure it on your own
workload rather than quoting a number.
WRITE AMPLIFICATION is the standing cost of durability, and it
is why:
· WAL archiving needs more storage than the data change rate
· replication bandwidth exceeds the change rate
· a bulk load runs faster with wal_level = minimal, which
skips some logging — at the price of breaking replication
and point-in-time recovery
THE ENGINEERING LESSON: the knobs that make durability cheaper
each remove a specific guarantee.
synchronous_commit = off → may lose the last few commits
full_page_writes = off → a torn page becomes unrecoverable
fsync = off → the log cannot be trusted AT ALL,
so recovery is meaningless
Turning fsync off is not "slightly less safe"; it removes the
foundation the whole algorithm rests on.
🌍 Go further: the same log powers three features beyond recovery, and recognising that is the real payoff of this topic. Streaming replication ships WAL to a standby that is permanently in recovery mode. Logical decoding turns WAL records back into row-level change events — the basis of Debezium and every CDC pipeline. Point-in-time recovery replays archived WAL to an arbitrary instant, which is the only defence against "someone ran DELETE without a WHERE". Search "PostgreSQL logical decoding CDC" and "WAL archiving PITR setup".
💡 Exam angle: list the log record types and know that a record carries <T, X, old, new> for immediate modification but only the new value for deferred. The deferred versus immediate comparison is a standard question — deferred needs REDO only, immediate needs both, and the reason is the STEAL/NO-FORCE buffer policies. The guaranteed computational question is a full recovery trace: find the last checkpoint, seed the undo set from its active list, build REDO and UNDO by scanning forward, then redo forward and undo backward. Practise it until the direction is automatic.
Syllabus points
Deferred & immediate update
Checkpoints
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Transaction Processing, Concurrency Control & Recovery