The WAL records memtable inserts before they are durable in SSTables. After crash, reopen the log, redo entries since the last checkpoint, and rebuild in-memory state. ARIES formalizes this as analysis, redo, undo phases in larger systems.
Recovery Pass
Scan WAL sequentially, validate checksums, apply idempotent redo to memtable, then mark checkpoint.
c
Loading…
Checksum failure stops replay to avoid corruption spread
Checkpoint truncates WAL for faster restart
Idempotent redo safe if partially applied before crash
Test by killing process mid-write then restarting
Working Through the Exercise
Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest
Why for this exercise
You will implement WAL replay that restores memtable contents after simulated crash. This exercise asks you to skip records before the checkpoint LSN and verify recovered key set.
Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.
Write a C program that recovers an 8-key key-value store by replaying its write-ahead log after a crash.
Input (stdin):
First line: "checkpoint n": checkpoint is the highest LSN already durable in an SSTable; n is the number of WAL records
Next n lines: "lsn key old_value new_value committed crc"
committed=1 means the record's transaction committed before the crash; committed=0 means it was still in flight
crc is the record's stored CRC-32 over a 16-byte little-endian encoding of (lsn:2, key:2, old_value:2, new_value:2, committed:4, lsn-upper-bits, key-upper-bits): see the starter's record_crc()
Recovery rules (scan records in LSN order, stop at the first bad record):
CRC mismatch: print "CORRUPT LSN=<l>" and STOP: a torn write means everything after is untrusted; later records are NOT examined