Checkpointing: Keeping the Log Short

A write-ahead log solves durability, and creates a new problem: it only grows. After a year of writes, recovery would replay a year of history, and the file would fill the disk. A checkpoint fixes both: it saves the current state to a place that does not need the log, and then the log can be emptied. After this lesson CHECKPOINT snapshots the store, RECOVER starts from the snapshot, and only the records written since are replayed.

What a checkpoint is

At the moment of a checkpoint the store holds the result of every record up to some LSN N. A checkpoint:

1. copies the store to the snapshot (in a real engine: writes all dirty pages to the database file and syncs it)
2. remembers N, the checkpoint LSN
3. empties the log, because every record in it is now reflected in the snapshot

The LSN counter does not go back. After a checkpoint at LSN 5 the next record is LSN 6. If numbering restarted, an old record and a new one could not be told apart.

SET a 1          lsn 1
SET b 2          lsn 2
CHECKPOINT       snapshot {a=1, b=2}, checkpoint lsn = 2, log emptied
SET c 3          lsn 3     <- the first record of the new log

Recovery with a checkpoint

1. Start from a copy of the snapshot (empty if there has never been a checkpoint).
2. Read the log. The first record must have LSN checkpoint + 1 and each following one exactly one more; verify checksums exactly as in the last lesson.
3. Apply the good records, cut the first bad record and everything after it out of the log, and set the next LSN to one past the last good one (the checkpoint LSN if the log is empty).

The cost of recovery is now the size of the log since the last checkpoint, not the size of history. That is why databases checkpoint on a schedule or when the log reaches a size limit (SQLite WAL mode checkpoints after about 1,000 pages by default).

The ordering that keeps it safe

A real checkpoint must make the snapshot durable before the log is truncated. If the log were emptied first and the process died before the snapshot reached disk, both would be gone. The simulator performs the steps as one atomic action, so only the order in your head matters here, but it is the single most important rule of the real thing.

Commands

• CHECKPOINT prints OK checkpoint lsn=<N> keys=<keys saved> where N is the LSN of the last record written so far (0 if none). ERR database is down if crashed.
• STATS prints lsn=<last LSN handed out> log=<records in the log> checkpoint=<checkpoint LSN>.
• RECOVER as described. Everything else from the previous lessons works unchanged.

Common mistakes

• Resetting the LSN counter at a checkpoint.
• Recovering from an empty store and ignoring the snapshot: the data from before the checkpoint disappears.
• Expecting LSN 1 first. After a checkpoint the first log record is checkpoint + 1; a record with another number means damage.
• Truncating the log but forgetting the snapshot lsn, so recovery cannot validate the sequence.

Your exercise

The starter has the log, parse_line, the damage simulators and the other commands, with the old recovery (empty store, LSN 1) still in place. You write checkpoint and the new recover. The mistake to avoid: starting recovery from nothing instead of from the snapshot.