WAL Recovery: Reconstruct History, Then Remove Losers

After a crash, “whatever is on disk” is not necessarily a committed database. Some committed updates may exist only in the durable log; some uncommitted updates may already be on data pages. Recovery must distinguish those cases.

This module assumes you understand pages, dirty buffers, and LSN ordering. You will trace a crash snapshot through analysis, redo, and undo, explain why the phases have different selection rules, and recognize the boundary between this one-pass exercise and an engine that can survive later crashes.

Derive the two jobs from the storage policy

Suppose T1 changes a byte from 0 to 4 and commits. Under no-force, commit need not flush that page. If the machine crashes before the page write, the disk still contains 0. Recovery needs the after-image 4: this is redo.

Now T2 changes the byte from 4 to 9 but does not commit. Under steal, its dirty page may already have been written. A crash may therefore leave 9 on disk. Recovery needs the before-image 4: this is undo.

Policy choice	What can be wrong after a crash?	Information needed
No-force	A committed update is absent from the page	Redo / after-image
Steal	An uncommitted update is present on the page	Undo / before-image

For this logging design, durable log records must precede the corresponding page writes. A durable commit acknowledgment also requires the commit record and preceding transaction log to be durable. Writing a commit marker only to RAM proves neither property. These are the core log/data ordering ideas in PostgreSQL's WAL introduction. PostgreSQL's full transaction-visibility implementation is not the before-image undo simulator implemented here.

Name the evidence precisely

An LSN orders log records, not wall-clock timestamps. A page LSN identifies the latest logged page change represented by a consistent page image. It does not mean “the transaction committed.” One page can contain bytes touched by several transactions.

The input log is already sorted by increasing LSN and consists only of durable records. The exercise supplies 32-byte pages and fixed-range replacements. Missing pages begin with 32 zero bytes and LSN=0. A transaction with a commit record is a winner; any other transaction is a loser, including one with an abort request but no completed rollback.

Before-images must be truthful, and conflicting writes must be isolated. If T1 writes 0→7, T2 writes 7→9 and commits while T1 is still unresolved, blindly undoing T1 can destroy T2's 9. The recovery routine cannot repair a history whose isolation protocol allowed that overwrite. The locking module explains one way to prevent such histories.

Three passes, three questions

Analysis: which transactions finished successfully?

Read the whole supplied log and collect committed transaction IDs. Do this before undo decisions; an update early in the log may have a commit much later. Begin records help describe a history but are not required by the exercise's analysis. Transaction IDs are never reused.

Full ARIES analysis reconstructs more state, including dirty-page information. Here “analysis” means only the winner set; do not invent checkpoints or a dirty page table that the interface does not supply.

Redo: which historical page writes are missing?

Scan updates forward. Apply an update's after-image only if:

record.LSN > page.LSN

Then set pageLSN to the record LSN. Check this per page, not against one global “latest LSN.” A page at LSN 20 tells you nothing about another page at LSN 3.

Redo considers both winners and losers. Its task is to reconstruct the recorded page history before undo removes the incomplete transactions. Skipping all loser updates might appear simpler, but would change the prescribed algorithm and make the phase explanation depend on where pages happened to have been flushed.

Undo: which reconstructed changes must disappear?

Scan the entire log backward. For every loser update, copy its before-image back into the specified byte range. Ignore winner updates. Why backward? A transaction may modify the same byte multiple times, and each before-image undoes only the corresponding step, not the entire transaction.

In this exercise, after either a redo or an undo, assign the original update's LSN to the page. This is a deliberately simplified output convention; its limits matter, as shown below.

A complete crash trace

Page P contains two bytes of interest, x and y. All other bytes remain zero. The durable log is:

LSN	Transaction	Record
1	T1	begin
2	T1	P.x: 0 → 4
3	T1	commit
4	T2	begin
5	T2	P.x: 4 → 7
6	T2	P.x: 7 → 9
7	T3	begin
8	T3	P.y: 0 → 6
9	T3	commit

At the crash, the persisted page is x=7, y=0, pageLSN=5. It contains T2's first uncommitted write but misses T3's committed write. T2 and T3 update disjoint byte ranges, so this is compatible with the declared isolation assumptions.

Analysis marks T1 and T3 as winners, T2 as a loser. Now redo:

Update LSN	Decision	Page afterward
2	Skip: 2 ≤ 5	x=7, y=0, LSN=5
5	Skip: 5 ≤ 5	x=7, y=0, LSN=5
6	Apply: 6 > 5	x=9, y=0, LSN=6
8	Apply: 8 > 6	x=9, y=6, LSN=8

Undo ignores T3, restores x=7 for T2's LSN 6, then x=4 for T2's LSN 5. It leaves y=6 intact. The exercise returns x=4, y=6, pageLSN=5.

That final LSN intentionally exposes the simplification: pageLSN=5 no longer means that this output is a faithful prefix of the original page-write history. Do not lift this undo bookkeeping rule into a live engine.

Idempotent redo is not restartable rollback

On a page whose LSN accurately describes its durable writes, replaying the same redo pass again skips already-applied updates. This is the useful idempotence property of the redo comparison.

It does not by itself prove that an engine can safely mix old rollback history, new transactions, and future crashes. Consider:

1. T1 commits x=4.
2. T2 writes x=9, then aborts and restores x=4.
3. T3 commits x=12.
4. The engine crashes and blindly undoes every transaction without a commit.

Undoing T2 again restores its old before-image 4 over T3's committed 12. The problem is not solved by adjusting a comparison operator. Recovery needs durable evidence that rollback happened and must replay that history in the right order.

ARIES records compensating page changes with compensation log records (CLRs). They receive new LSNs, can be redone, and are not themselves undone. It also tracks where rollback should resume after another crash. The original ARIES paper, section 3 explains the role of CLRs and their undo-next links. The capstone adopts fresh-LSN compensation and a rollback-complete marker, while making each recovery call atomic so it need not implement interrupted-undo traversal.

Translate the exercise into code

Make a new map and deep-copy every page's data slice. Copying only the Page struct still aliases the caller's bytes. Analysis builds a transaction-ID set; redo uses a helper that materializes a missing zero page; undo traverses the log by descending index.

A page retrieved from map[uint32]Page is a struct value. After changing its LSN, write the struct back to the map. Otherwise the bytes might change through the slice while the metadata silently remains old.

Let L be the number of records, B the total bytes moved by redo/undo, and P the number of pages copied or created. The passes cost O(L+B+32P) time and require an output page map plus transaction metadata. There is no need to sort an input whose contract already gives LSN order.

Reconstruct and check

1. Repeated writes. A loser writes a byte 4→7→9. Undo in forward order writes 4, then 7. What invariant has it broken?

Answer: Each undo must see the state left by the next update's reversal. Reverse order gives 9→7→4. A before-image is a local inverse, not a transaction snapshot.

2. Already persisted loser. An uncommitted update has LSN 12 and its page already has LSN 12. Is there any work left?

Answer: Redo skips that record, but undo still applies its before-image. The redo condition says the write is present, not that the transaction won.

3. Two pages. P has LSN 20 and Q has LSN 3. A committed update at LSN 10 targets Q. Can the engine skip it because 20 is larger?

Answer: No. Compare 10 with Q's 3, so apply it. Page-local evidence cannot be replaced by a global maximum.

4. Recovery boundary. Why is an abort marker not a substitute for a rollback-complete marker?

Answer: The decision to abort can be durable before its page changes have been undone. Treating that decision as completion could leave loser data behind. Conversely, repeating a completed undo over later work can erase a winner.

Before implementing, reproduce the full trace with a blank table. Afterward, check that input pages remain unchanged and that undo preserves committed bytes in a different range of the same page.