Write-Ahead Log: Log First, Then Change

A process can die at any instant: a kernel panic, a power cut, kill -9. Whatever the database was holding in memory is gone, and a data page that was half written is garbage. A write-ahead log (WAL) is the standard answer. Before any change is made, a short description of it is appended to a log file; after a crash, reading the log tells the database exactly what it was doing. After this lesson your key-value store logs every write first, and can rebuild its memory from the log alone.

Why a log

Updating data in place means writing to scattered locations and a crash in the middle leaves a mixture of old and new. Appending to the end of a log is different: it is sequential (fast on any disk) and each record is small. The rule that gives the technique its name:

The log record for a change must reach the log before the change is made to the data.

If the process dies between the two steps, the log has a record of a change memory never saw, and recovery can redo it. If the order were reversed, memory could have a change that no log record explains and that nothing can reconstruct.

A record, byte for byte

Each record is one line of the log:

<lsn> <op> <key> <crc> [<value>]

1 SET name 8a345f3e Alice
2 SET city 9354d180 New York
3 DEL name 8f9c161e

The checksum is the standard CRC-32 (the one in zip, gzip and PNG) of the text lsn|op|key|value, for example 1|SET|name|Alice, and 3|DEL|name| for a delete (the value is empty). The starter provides the CRC function and format_record, which builds the whole line. You are asked to use them in the right place, not to write a checksum.

The write path

1. Take the next LSN.
2. Append the record to the log (append_record). This is the write-ahead step.
3. Only then change the in-memory store.
4. Reply.

DEL of a key that does not exist prints NOT_FOUND and writes nothing: a log should record only changes that happened.

Losing memory, then replaying

CRASH throws away the in-memory store, as if the process had died; the log survives. Until it is rebuilt, SET, DEL, GET and DUMP answer ERR database is down. REPLAY rebuilds it: start from an empty store, read the log from the first record, apply each in order (a SET stores, a DEL removes), and continue the LSN counter from the last record, so the next write continues at the next number. It prints OK replayed=<n>. Replaying twice gives the same store, because applying SET/DEL in the same order is deterministic.

Commands

SET <key> <value>, DEL <key>, GET <key>, DUMP (every key=value, sorted by key, or (empty)), LOG (the records, or (empty log)), CRASH, REPLAY. Usage errors print ERR usage: ....

Common mistakes

• Changing memory first. The tests cannot see the order directly, but the next two lessons depend on it.
• Logging a DEL for a missing key.
• Checksumming the wrong text. Use format_record; it checksums lsn|op|key|value.
• Replaying without clearing the store, or forgetting to move the LSN counter past the replayed records.

Your exercise

The starter has the record format, CRC-32, the commands and the down state. You write append_record (log a write and return its LSN) and replay. The mistake to avoid: applying a write to memory before it is in the log.