When a database crashes, it can't trust whatever partial state was on disk -- it replays its write-ahead log (WAL) to reconstruct exactly what should have happened. The rule that makes this correct: redo only committed transactions. Anything a transaction did before crashing without reaching COMMIT must be thrown away, as if it never happened.

But there's a second, easy-to-miss failure mode: the crash itself can happen mid-write, physically tearing the very last log entry in half, or leaving garbage bytes at the tail that happen to still look structurally valid. Naive "redo everything with a COMMIT" logic has no way to distinguish a torn/garbage entry from a real one -- and blindly replaying corrupted data is worse than replaying nothing at all.

make_entry(txn, op, **fields) is done for you -- every log entry in this exercise is built through it, and it bakes in what a real WAL writer does: your fields, plus a checksum computed over them. Implement replay(log):

• Walk the log validating each entry's checksum, IN ORDER.
• The moment one entry's checksum doesn't match its own content (or is missing), STOP -- discard that entry AND every entry physically after it in the log, even ones that look perfectly valid on their own.
• Among the entries that passed validation, redo only the SET/DELETE operations belonging to transactions that reached COMMIT (same rule as before).

Example

log = [
    make_entry(1, "BEGIN"),
    make_entry(1, "SET", key="x", value=1),
    make_entry(1, "COMMIT"),
    make_entry(2, "BEGIN"),
    make_entry(2, "SET", key="y", value=2),
    # crash -- txn 2 never committed
]
replay(log)  # -> {"x": 1}   (y is NOT in the result)

Constraints

• Validate checksums strictly in log order. Stop at the FIRST invalid entry -- don't skip past it and keep checking later entries; discard the entire remainder of the log from that point on.
• An entry with no "checksum" key at all is just as invalid as one with the wrong checksum -- don't crash with a KeyError, treat it as the truncation point.

Real-world grounding

• Postgres's WAL redo machinery, including per-record CRC validation that stops replay at the first invalid record: xlog.c (search XLogReaderValidatePageHeader / record_crc)
• SQLite's write-ahead log, including its own per-frame checksum: wal.c (search walChecksumBytes)

Real recovery is a lot more involved -- checkpoints so you don't replay the entire history of the database (see this course's Checkpointing exercise), physical (page-level) rather than logical logging in Postgres's case -- but "redo committed, verify every record, stop at the first torn one" is the rule underneath all of it.