Without checkpoints, crash recovery for a long-running database would mean replaying its ENTIRE write-ahead log from the very first entry ever written. A checkpoint periodically snapshots current state directly into the log; recovery then only needs to start from the LATEST checkpoint's snapshot and replay whatever committed transactions came after it -- everything before the checkpoint is trusted as-is, never re-examined.

Like this course's WAL Crash Recovery exercise, every entry carries a checksum -- a crash can tear a checkpoint write just as easily as an ordinary SET/DELETE, and a torn checkpoint is exactly as untrustworthy as any other torn entry.

make_entry(**fields) and find_latest_valid_checkpoint(log) are done for you. The latter walks the whole log and returns (start_state, start_index) for the LATEST checkpoint whose own entry passes checksum validation -- skipping a torn checkpoint in favor of the previous good one, the same way a torn ordinary entry gets skipped during tail replay.

Implement replay_with_checkpoint(log):

• Get (state, start_index) from find_latest_valid_checkpoint(log), and take tail = log[start_index:].
• Validate tail's entries in order, exactly the way WAL Crash Recovery does: stop at (and discard) the first invalid entry and everything physically after it.
• Among the entries that passed validation, apply SET/DELETE for transactions that reached COMMIT, starting from state, and return it.

Example

log = [
    make_entry(op="CHECKPOINT", state={"x": 100, "y": 200}),
    make_entry(txn=1, op="BEGIN"),
    make_entry(txn=1, op="SET", key="y", value=999),
    make_entry(txn=1, op="COMMIT"),
]
replay_with_checkpoint(log)  # -> {"x": 100, "y": 999}

Constraints

• Only entries AFTER the latest VALID checkpoint are ever examined for committed-ness or replayed.
• If there's no valid checkpoint at all, this must behave exactly like WAL Crash Recovery starting from an empty state.
• A torn entry in the tail truncates replay right there, same rule as WAL Crash Recovery -- don't skip past it and keep going.

Real-world grounding

• Postgres's checkpointing (bounds how far back WAL redo has to start from): src/backend/access/transam/xlog.c (search CreateCheckPoint)

Real checkpoints are more involved than a full-state snapshot written inline -- they typically flush dirty pages to disk and record a WAL position (not the state itself) to resume from -- but "bound replay to what's after the last known-GOOD point, and never trust a torn write of any kind" is exactly what this exercise implements.