Rolling Back the Losers After a Crash

Why this stage exists

Row-level undo made two sessions safe on one leaf, as long as nothing crashes. Now look at what a commit logs. Session 1 inserts row 1 and stays open; session 2 inserts row 2 into the same leaf and commits. Session 2's commit logs that leaf, and the leaf holds both rows.

After a crash, redo replays session 2's commit, page image and all, so row 1 comes back too, and nothing remembers that it was never committed: session 1's undo records lived in memory.

So the undo record must reach the log in the same commit as the page it describes.

Undo pages, only when needed

A commit now starts by looking at the other sessions. Each one with a transaction open gets its undo records written to undo pages, ordinary pages of type 6, allocated like any page and chained from the file header: bytes 28–31 hold the first undo page, 0 when there is none. Then the commit logs every page changed since it was last logged, whoever changed it: its own, the other transactions' and the undo pages. Everything a crash could replay now comes with the undo that takes it back.

A transaction that ends without committing, by ROLLBACK, by 01303 or at the end of the program, frees its own undo pages once its records are applied, and then does the same two steps: the other open transactions' undo goes to undo pages, and every page changed since it was last logged is logged. So undo status after one session rolls back beside another's open transaction shows pages=1 or more.

With one session there is never another transaction open at a commit or a rollback, so no undo page is ever written and the log holds exactly what it held before.

A page that a commit logged is logged until it changes again. It may go to the database file whenever the pool needs its frame, even with an uncommitted row on it: if a crash follows, the log has the undo for that row. A page an open transaction changed since it was last logged is still held in memory, as section 33 always said.

Recovery in two passes

Recovery used to be redo only: replay every committed page image. Now it has a second pass:

1. Redo. Replay the committed page images, as before. Pages come back exactly as they were logged, uncommitted rows included.
2. Undo. Read the undo pages. A transaction whose records are there never committed, because a commit frees its own undo pages. Roll each one back exactly as ROLLBACK does, newest record first, by key, and free its undo pages.

Then sync and empty the log. The line gains one field:

[WAL] Recovery: records=8 replayed=2 discarded=0 rolled_back=1
Welcome to droid!

The undo pass changes pages in memory only, and they reach the file at the end. A crash in the middle of it, at the fail-point mid_undo, leaves the log as it was, and the next open does the same work again.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 83.

What you should see when done

$droid --db r.db
Welcome to droid!
>create table a (id int primary key, v varchar(20));
Create table statement executed successfully
>@1 begin;
@1| Begin statement executed successfully
>@1 insert into a (id, v) values (1, 'loser');
@1| Insert statement executed successfully (1 rows)
>@2 insert into a (id, v) values (2, 'winner');
@2| Insert statement executed successfully (1 rows)
>undo status
[UNDO] records=1 pages=1 oldest_view=0 purgeable=0
>.crash
$droid --db r.db
[WAL] Recovery: records=8 replayed=2 discarded=0 rolled_back=1
Welcome to droid!
>select * from a;
id | v
2 | winner
(1 rows)
[EXEC] rows_examined=1
>.exit
exiting.. good bye!

Common bugs in this stage

• Spilling only the committing transaction's undo. It is the other transactions' undo that the log needs; the committing one's is about to be dropped.
• Logging only the committing transaction's pages. A page another transaction changed and nobody logged must not be left behind once its undo is in the log.
• Undoing by page image. The loser's rows may have moved since; take them back by key.
• Forgetting to free undo pages after a commit, a rollback or the undo pass: the file grows and the pages are accounted for nowhere.
• Writing during the undo pass. Keep its changes in memory until the end, so a crash in it changes nothing.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: a per-page "logged" flag next to the dirty flag in each frame; undo pages as a linked list of page numbers per session.
• C++: a std::set<uint32_t> of pages changed since they were last logged, cleared as a commit logs them.
• Rust: serialise each undo record with its kind, table, key and row length in front; a Vec<u32> of undo pages per transaction.
• Zig: write records into the undo page with std.mem.writeInt and a running offset; start a new page when the next record does not fit.