Crash Recovery: Trusting Only What Checks Out

Replaying a log assumes the log is intact. A crash in the middle of an append breaks that assumption: a record can be torn, with only its first bytes on disk, and disks occasionally flip bits. After this lesson your RECOVER verifies each record, applies the valid prefix of the log, and throws away the rest, so that new writes continue from a log that can be trusted.

What a crash can leave behind

Suppose records 1 to 3 were fully written and the power failed while record 4 was being appended. The log now ends with part of a line:

1 SET a 4b1c8d0e 1
2 SET b 07a2f9c1 2
3 SET c 9d3e5a42 3
4 SET d 6f0

Replaying line 4 as if it were whole would store garbage, or crash on a half-written number. Yet records 1 to 3 are good, and the unfinished write was never acknowledged to a client, so dropping it loses nothing a client was promised.

Verifying a record

A record is good only if all of these hold:

1. it has the four mandatory fields (lsn, op, key, crc) and the lsn is made of digits
2. op is SET or DEL, the checksum is exactly 8 lowercase hex digits, and a SET has a value
3. the line equals what format_record would produce from those fields. Recomputing the whole line and comparing it also catches a wrong checksum, a changed value, a leading zero in the lsn and trailing junk, with one check instead of many

Then one more test that no single record can pass or fail alone: the LSN must continue. The first record must be LSN 1 and each following record exactly one more than the last good one. A missing record in the middle makes the next one look wrong even though its own checksum is fine.

Recovery

1. Start from an empty store.
2. Walk the log from the start. For each line: verify it and check the LSN. If good, apply it.
3. At the first bad line stop. That record and everything after it are discarded; cut them out of the log, so that the log is again a valid prefix.
4. Set the next LSN to one more than the last good one, clear the crashed state, and report OK recovered=<good> discarded=<bad>.

Why stop rather than skip? Later records may depend on the one that was lost (record 5 could update a key record 4 created). Once something cannot be trusted, nothing after it can be applied with confidence. Why cut the log? If the damaged tail stayed, the next write would be appended after garbage, and the following recovery would stop at the garbage and lose every new record.

The simulator's commands

TEAR <n> simulates the torn write: it removes the last n characters of the last log line (more than the line has leaves an empty line). CORRUPT <lsn> simulates bit rot: it appends an x to the line of that record. An empty log is ERR log is empty for TEAR; a record that is not in the log is ERR no such record for CORRUPT; a bad argument is ERR usage: <COMMAND> <n>.

RECOVER replaces REPLAY from now on for damaged logs. REPLAY still trusts the log blindly, so do not use it after TEAR or CORRUPT.

Common mistakes

• Skipping a bad record and carrying on. Everything after it is suspect.
• Not truncating the log, so the next append sits behind garbage.
• Not checking the LSN sequence. Checksums alone cannot see a missing record.
• Verifying only the checksum field and not the format (for example a SET with an empty value).

Your exercise

The starter has the commands and the record format. You write parse_line (verify one line) and recover. The mistake to avoid: applying records after the first damaged one.