Atomicity Through Write-Ahead Logging

Atomicity — All or Nothing via WAL

Atomicity means a transaction either applies completely or not at all — there's no such thing as "half a transfer happened." You already built a write-ahead log (WAL) for crash durability; this lesson reuses it as the mechanism for transaction atomicity, tying two ideas together: grouping writes under a transaction id, and undoing or redoing them based on whether the transaction committed.

Why WAL is the natural fit

A WAL is just an append-only sequence of log records: SET key=value, DELETE key, etc., each written to disk before (or as part of) the change being applied. Because it's ordered and durable, it's the perfect place to also record transaction boundaries:

BEGIN 1
WRITE 1 balance_a 900        -- logged with txid=1
WRITE 1 balance_b 1100       -- logged with txid=1
COMMIT 1                      -- logged with txid=1

If the process crashes between the two writes, recovery replays the log and can see that transaction 1 never reached COMMIT — so its writes must be undone, not kept.

Building the pieces

1. BEGIN — allocate/accept a transaction id and start buffering (or directly logging, tagged with that id) the writes that follow.
2. Writes tagged with a txid — every WAL record needs to carry which transaction produced it, e.g. (txid, key, old_value, new_value). Storing the old value (before-image) is what makes rollback possible without replaying the whole log from the start.
3. COMMIT — append a COMMIT <txid> marker to the WAL. Only after this record is durably written is the transaction considered "happened."
4. ROLLBACK — walk the WAL entries for that txid in reverse order and undo each one (restore the old value, or delete a key that was newly inserted). Reverse order matters if the same key was written multiple times within the transaction — you must peel changes off like a stack, not apply them in forward order.

Crash + Recover semantics

This is the payoff: after a CRASH (simulated) and RECOVER, your recovery routine scans the WAL from the beginning and reconstructs which transactions have a matching COMMIT record:

• Committed transactions (WAL shows BEGIN ... COMMIT) → replay their writes forward into the table, so the effects are restored even though the in-memory table was lost.
• Uncommitted transactions (WAL shows BEGIN with no matching COMMIT, e.g. the crash happened mid-transaction) → their writes must not appear in the recovered table. Effectively, treat them as if rolled back — just don't reapply them during replay.

This two-pass structure — first scan to classify each txid as committed or not, then a second pass (or filtered replay) that only applies committed transactions' writes in order — is exactly what real database recovery (ARIES-style, simplified) does.

Edge cases to watch

• A transaction that writes the same key twice: rollback must restore the value from before the transaction started, not the intermediate value.
• Multiple interleaved transactions in the WAL (txid 1 and txid 2 writes interleaved) — recovery must track state per key correctly by replaying entries in log order, filtered by which txids committed.
• ROLLBACK on a transaction that already committed, or committing twice, should be treated as an error rather than silently corrupting state.

Nail this and you have real crash-safe atomicity: the durability guarantee from your WAL lesson, now combined with the all-or-nothing guarantee that makes transactions trustworthy.