Write-Ahead Log

Everything so far dies with the process. The oldest, simplest durability mechanism is the write-ahead log: before you touch the in-memory map, append a record describing the change to a log. The invariant that gives the log its name:

No state change becomes visible in memory before its log record is written.

Crash at any moment and the log still holds a complete history. On restart, replay the records in order and you reconstruct exactly the map you lost.

Why append-only?

• Sequential I/O. Appends only ever touch the file's tail. On spinning disks sequential writes are ~100x faster than random ones; SSDs narrow the gap but still reward sequential patterns (and their flash wears out slower under them).
• Trivial recovery. Records are already in time order. Replay = read from the start, apply each record. No pointers to chase, nothing to rebalance.
• Corruption is bounded. A crash mid-write can only garble the final record. Real logs frame each record with a length prefix and a CRC32 checksum (size, type, key, value, crc) so replay knows where the last valid record ends. This exercise keeps records as plain command lines, but the framing idea is worth remembering.

What must be logged

Both kinds of mutation. PUTs are obvious. Forgetting to log deletes causes the classic resurrection bug: you PUT a, DELETE a, crash, replay — and a is back from the dead, because the log only remembered its birth. So a delete appends its own record — in this exercise the record reads DEL a — and replay applies it by removing the key.

Note what replay does with overwrites: a log holding PUT a 1, PUT a 2, PUT a 3 replays to a single key a=3. The log keeps full history; only the newest value survives in the map. (Shrinking that history is compaction's job, later in the course.)

fsync: the durability dial

An append lands in the OS page cache first; only fsync forces it to stable storage. Every real store exposes the trade-off:

• fsync every write (Redis appendfsync always): nothing acked is ever lost; ~100 ops/s on an HDD.
• fsync periodically (Redis everysec, Postgres synchronous_commit=off): fast, loses the last moments of writes on a crash.
• Group commit: batch many concurrent writers into one fsync — most of the durability at a fraction of the cost.

This is the D in ACID, and it is a dial, not a boolean. Our log lives in memory (a list), so you implement append + replay; fsync stays conceptual.

Your exercise

Implement PUT, DELETE, GET, LOG-DUMP, CRASH, REPLAY, LIST. The grader-caught mistakes, from the real tests: (1) the log token — LOG-DUMP prints DEL age, not DELETE age: the command is spelled DELETE, its log record is spelled DEL; (2) resurrection — after PUT a 1, PUT b 2, DELETE a, PUT c 3, CRASH, REPLAY, the hidden test expects LIST to print exactly b=2 and c=3; if deletes are not logged and replayed, a=1 comes back; (3) the empty marker — LIST on an empty map prints (empty) in this lesson (the first lesson's exercise printed nothing; conventions differ per exercise — follow this one's); (4) CRASH clears only the map, never the log: GET k right after prints <nil>, then REPLAY restores it and GET k prints v.