go-lsm-memtable-wal-crash-recovery
Done. The solution is complete and verified at ~/lsm/ (full writeup: SOLUTION.md, quick reference: README.md).
Root cause: Naive implementations break crash safety in eight classic ways — acknowledging before fsync (lost acknowledged writes), mutating the memtable before/independently of the WAL (divergent state), trusting raw record lengths (garbage/replayed torn tails), no CRC (torn bytes parsed as valid records), tombstone-less deletes (resurrected keys after flush), reading a flushed memtable in place (torn reads), deleting the WAL before its SST is durable (lost generations), and map-order-dependent recovery (non-byte-identical restarts).
The fix (~/lsm, Go 1.26, stdlib only, ~2,700 lines):
- wal.go — length-prefixed records [u32 len][u32 crc32c][payload], fsync-before-ack (AppendSync), and ReplayWal: a pure function of file bytes that validates CRC/lengths (bounds-checked, no panic/alloc amplification) and truncates the torn tail, making every future restart byte-identical.
- memtable.go — sorted skip list with tri-state lookups (NotFound|Found|Deleted); Delete inserts tombstones that survive flush and mask older Puts in older layers.
- store.go — oldest-first WAL segments, newest-first layer merge (active → immutable snapshot → SSTs), rotation under one lock, and WAL deleted only after the SST is durably renamed — reads during flush stay snapshot-consistent.
- harness.go — crash-injection harness: a worker subprocess that applies ops with fsync-ack, leaves a controlled residue (partial header / torn payload / no-fsync full record), then dies by SIGKILL; VerifyCrashRecovery re-opens twice and asserts State.Bytes() byte-identical and equal to an in-memory oracle.
Verification (all green, go vet clean):
- go test -count=1 ./... → ok lsm 1.097s — all 25 tests + every subtest pass.
- go test -race on the concurrency+crash suites → PASS.
- Matrix kills at every record boundary × {clean, 5 torn sizes, 3 partial-header sizes, no-sync}, a 12-round shared-dir crash-loop with mid-round torn truncation, ~600 tiny-threshold flush-rotation windows, and mid-file CRC corruption — each asserting byte-identical key-state across two independent restarts, stably across -count=3 repeated runs.
# Evidence - Problem class: go-lsm-memtable-wal-crash-recovery - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-03T16:30:28.258Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an LSM memtable (sorted in-memory structure) with a write-ahead log where every Put/Delete is appended as a length-prefixed, CRC32C-checksummed record and fsynced before the mutation is acknowledged. On startup the WAL must be replayed to reconstruct the exact last-durable state, truncating any torn tail record, and a Delete must mask older Puts of the same key while reads during background memtable-to-SST flush stay consistent. Include a crash-injection harness that kills the process at arbitrary record boundaries and asserts byte-identical key-state across restarts.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lsm-memtable-wal-crash-recovery", "provider": "openrouter", "solved_at": "2026-09-03T16:30:28.258Z", "version": "1.26"}Done. The solution is complete and verified at ~/lsm/ (full writeup: SOLUTION.md, quick reference: README.md).
Root cause: Naive implementations break crash safety in eight classic ways — acknowledging before fsync (lost acknowledged writes), mutating the memtable before/independently of the WAL (divergent state), trusting raw record lengths (garbage/replayed torn tails), no CRC (torn bytes parsed as valid records), tombstone-less deletes (resurrected keys after flush), reading a flushed memtable in place (torn reads), deleting the WAL before its SST is durable (lost generations), and map-order-dependent recovery (non-byte-identical restarts).
The fix (~/lsm, Go 1.26, stdlib only, ~2,700 lines):
- wal.go — length-prefixed records [u32 len][u32 crc32c][payload], fsync-before-ack (AppendSync), and ReplayWal: a pure function of file bytes that validates CRC/lengths (bounds-checked, no panic/alloc amplification) and truncates the torn tail, making every future restart byte-identical.
- memtable.go — sorted skip list with tri-state lookups (NotFound|Found|Deleted); Delete inserts tombstones that survive flush and mask older Puts in older layers.
- store.go — oldest-first WAL segments, newest-first layer merge (active → immutable snapshot → SSTs), rotation under one lock, and WAL deleted only after the SST is durably renamed — reads during flush stay snapshot-consistent.
- harness.go — crash-injection harness: a worker subprocess that applies ops with fsync-ack, leaves a controlled residue (partial header / torn payload / no-fsync full record), then dies by SIGKILL; VerifyCrashRecovery re-opens twice and asserts State.Bytes() byte-identical and equal to an in-memory oracle.
Verification (all green, go vet clean):
- go test -count=1 ./... → ok lsm 1.097s — all 25 tests + every subtest pass.
- go test -race on the concurrency+crash suites → PASS.
- Matrix kills at every record boundary × {clean, 5 torn sizes, 3 partial-header sizes, no-sync}, a 12-round shared-dir crash-loop with mid-round torn truncation, ~600 tiny-threshold flush-rotation windows, and mid-file CRC corruption — each asserting byte-identical key-state across two independent restarts, stably across -count=3 repeated runs.
# Evidence - Problem class: go-lsm-memtable-wal-crash-recovery - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-03T16:30:28.258Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an LSM memtable (sorted in-memory structure) with a write-ahead log where every Put/Delete is appended as a length-prefixed, CRC32C-checksummed record and fsynced before the mutation is acknowledged. On startup the WAL must be replayed to reconstruct the exact last-durable state, truncating any torn tail record, and a Delete must mask older Puts of the same key while reads during background memtable-to-SST flush stay consistent. Include a crash-injection harness that kills the process at arbitrary record boundaries and asserts byte-identical key-state across restarts.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lsm-memtable-wal-crash-recovery", "provider": "openrouter", "solved_at": "2026-09-03T16:30:28.258Z", "version": "1.26"}