Atomicity: All or Nothing, Even Through a Crash

ROLLBACK handles a transaction you abandon on purpose. Atomicity has to hold when you do not get the chance: the process is killed, the power fails, a write to disk is cut in half. After restart, a transaction must have happened completely or not at all, never partly. The tool that makes this possible is the write-ahead log you met in the earlier lessons, now with transaction ids on every record.

What goes in the log

Every change is described in the log before it is applied. Each record carries the id of the transaction that made it:

1 SET a 1
1 SET b 2
1 COMMIT
2 SET a 99
2 SET c 7

Transaction 1 wrote two keys and then committed. Transaction 2 wrote two keys and the log ends: it never reached COMMIT. A transaction exists, as far as the future is concerned, if and only if its COMMIT record is in the log. Writing that one record is the instant the transaction happens; everything before it is provisional. ROLLBACK writes an ABORT record instead (after reversing the writes in memory, newest first, with the undo log from the BEGIN, COMMIT, ROLLBACK lesson).

What a crash destroys

The log is durable; the in-memory store is not. A CRASH in this lesson throws away the store, the open transaction and the undo entries, and keeps only the log. Whatever the store looked like, including half of transaction 2's writes, is gone.

Recovery: redo the committed, ignore the rest

Recovery rebuilds the store from nothing using only the log:

1. Find the committed transactions: scan once and collect every txid that has a COMMIT record.
2. Redo them: scan again from the start, and apply, in log order, only the SET and DEL records whose txid is in that set.

Records of transactions without a COMMIT (still running at the crash, or aborted) are simply never applied. That is how a half-finished transfer disappears: it was never promoted to existence. No undo pass is needed, because the crashed in-memory state was discarded wholesale. Replaying in log order also gets overwrites right: if two committed transactions wrote the same key, the later one wins.

After recovery the next transaction id must be larger than any id in the log, or two different transactions would share an id and a future recovery could mistake one for the other.

The last record may be half written

A crash can hit while the last record is being written, leaving only a prefix of it on disk. Records end with a newline, so the rule is: a record without its newline never happened. Recovery cuts the log back to just after the last newline and counts the dropped bytes. This is where atomicity shows its teeth: if the cut-off record was a COMMIT, its transaction is no longer committed, and all of its writes are ignored, even though every one of them is intact in the log.

2 SET b 2
2 COMMIT        <- crash while writing this line: only "2 COMM" reached the disk

Recovery sees 2 SET b 2 and no commit, so b does not exist.

The commands

All writes need a transaction: BEGIN (prints OK txid=<n>), SET, DEL, COMMIT, ROLLBACK; GET and DUMP read. LOG prints the records. CRASH simulates the failure; while down, everything except LOG, TEAR and RECOVER is refused. TEAR <bytes> (only after a crash) removes bytes from the end of the log, simulating a torn write. RECOVER rebuilds the store and prints OK committed=<n> ignored=<m> torn=<bytes>, where ignored counts transactions that wrote something but did not commit.

Common mistakes

• Replaying every record, committed or not. The uncommitted writes come back and atomicity is gone.
• Replaying only the last committed transaction, or ignoring log order. Overwrites must resolve in log order.
• Trusting a record that has no trailing newline.
• Logging after applying. A crash in between loses a change that was already visible.

Your exercise

The starter handles parsing, CRASH, TEAR and printing. You write write_key, commit, rollback and recover. The mistake to avoid: applying the writes of a transaction you have not yet seen commit.