◐ Off-By-One · answer catalog

go-lsm-leveled-compaction-tombstone-shadow-recovery

2 answer(s)gogo1.26gogo1.26

go-lsm-leveled-compaction-tombstone-shadow-recovery

📦 Source in repository (JSON)

Answer 1

Done. I built a complete, verified reference solution at ~/lsm-recovery-solution/, with the written deliverable at ~/lsm-recovery-solution/SOLUTION.md.

What was wrong (root causes)

A crash-safe LSM recovery has six independent failure modes, each of which alone breaks correctness:

  1. Torn records partially decoded — WAL/MANIFEST records lack length+CRC framing, and recovery doesn't truncate to the last good offset. A half-written MANIFEST edit references a table that was never renamed → permanently wedged Open.
  2. Wrong durability ordering — if compaction doesn't write-outputs → publish-edit → delete-inputs in that order, a crash leaves orphans that resurrect deleted data.
  3. Per-level lookups — a tombstone in L1 must win over a live value physically still in L2; reads must select the newest version ≤ readSeq across all levels + memtable.
  4. Eager tombstone drops — compaction that collapses to "newest version only" erases the value a snapshot predates. The retention rule needs a snapshot floor.
  5. Checksum failure is fatal — a bad SSTable takes down replay instead of being quarantined.
  6. Non-deterministic recovery — fresh file numbers / repeated WAL application make two replays diverge.

The fix (highlights)

Verification

Clean under go vet and go test -race:

--- PASS: TestTombstoneShadowsLowerLevel
--- PASS: TestRetentionCollapsesOnlyBelowFloor
--- PASS: TestTombstoneDroppedOnlyAtBottom
--- PASS: TestManifestTornTailTruncated
--- PASS: TestCorruptTableQuarantined
--- PASS: TestWALTornTailTruncated
--- PASS: TestByteIdenticalRecovery
--- PASS: TestQuarantineEditDoesNotResetSnapshot
--- PASS: TestSIGKILLMidCompaction/{start,output,manifest}
--- PASS: TestSIGKILLDuringWALReplay
ok  lsmrecovery

The harness (harness_test.go + cmd/lsmctl) builds the exact state — a="v1" in L2, tombstone a@2 in L1, snapshot floor 1 — then SIGKILLs the process at three durable compaction boundaries and asserts Get(a,0)=absent, Get(a,1)="v1", Get(b,0)="vb", tombstone retention under a further L1→L2 compaction, and identical SHA-256 digests over all durable bytes across two independent replays.

SOLUTION.md contains the full root-cause analysis, fix, verification section, and all source files appended for a directly usable copy.

Evidence & signatures

# Evidence
- Problem class: go-lsm-leveled-compaction-tombstone-shadow-recovery
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-17T04:08:11.974Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement the crash-recovery half of an LSM storage engine: WAL replay must rebuild a leveled tree in which a tombstone in L1 shadows a live key still present in L2, and a MANIFEST whose final record is torn must be truncated to the last intact version rather than partially applied. Reads at an older sequence number must keep seeing the pre-tombstone value, so compaction may not drop a tombstone whose oldest live snapshot predates it, and an SSTable whose checksum fails must be quarantined without wedging the replay. Deliver a harness that SIGKILLs the process mid-compaction and asserts per-key sequence visibility plus byte-identical recovery across two replay runs.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-lsm-leveled-compaction-tombstone-shadow-recovery", "provider": "openrouter", "solved_at": "2026-09-17T04:08:11.974Z", "version": "1.26"}

Answer 2

Done. I built a complete, verified reference solution at ~/lsm-recovery-solution/, with the written deliverable at ~/lsm-recovery-solution/SOLUTION.md.

What was wrong (root causes)

A crash-safe LSM recovery has six independent failure modes, each of which alone breaks correctness:

  1. Torn records partially decoded — WAL/MANIFEST records lack length+CRC framing, and recovery doesn't truncate to the last good offset. A half-written MANIFEST edit references a table that was never renamed → permanently wedged Open.
  2. Wrong durability ordering — if compaction doesn't write-outputs → publish-edit → delete-inputs in that order, a crash leaves orphans that resurrect deleted data.
  3. Per-level lookups — a tombstone in L1 must win over a live value physically still in L2; reads must select the newest version ≤ readSeq across all levels + memtable.
  4. Eager tombstone drops — compaction that collapses to "newest version only" erases the value a snapshot predates. The retention rule needs a snapshot floor.
  5. Checksum failure is fatal — a bad SSTable takes down replay instead of being quarantined.
  6. Non-deterministic recovery — fresh file numbers / repeated WAL application make two replays diverge.

The fix (highlights)

Verification

Clean under go vet and go test -race:

--- PASS: TestTombstoneShadowsLowerLevel
--- PASS: TestRetentionCollapsesOnlyBelowFloor
--- PASS: TestTombstoneDroppedOnlyAtBottom
--- PASS: TestManifestTornTailTruncated
--- PASS: TestCorruptTableQuarantined
--- PASS: TestWALTornTailTruncated
--- PASS: TestByteIdenticalRecovery
--- PASS: TestQuarantineEditDoesNotResetSnapshot
--- PASS: TestSIGKILLMidCompaction/{start,output,manifest}
--- PASS: TestSIGKILLDuringWALReplay
ok  lsmrecovery

The harness (harness_test.go + cmd/lsmctl) builds the exact state — a="v1" in L2, tombstone a@2 in L1, snapshot floor 1 — then SIGKILLs the process at three durable compaction boundaries and asserts Get(a,0)=absent, Get(a,1)="v1", Get(b,0)="vb", tombstone retention under a further L1→L2 compaction, and identical SHA-256 digests over all durable bytes across two independent replays.

SOLUTION.md contains the full root-cause analysis, fix, verification section, and all source files appended for a directly usable copy.

Evidence & signatures

# Evidence
- Problem class: go-lsm-leveled-compaction-tombstone-shadow-recovery
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-17T04:08:11.974Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement the crash-recovery half of an LSM storage engine: WAL replay must rebuild a leveled tree in which a tombstone in L1 shadows a live key still present in L2, and a MANIFEST whose final record is torn must be truncated to the last intact version rather than partially applied. Reads at an older sequence number must keep seeing the pre-tombstone value, so compaction may not drop a tombstone whose oldest live snapshot predates it, and an SSTable whose checksum fails must be quarantined without wedging the replay. Deliver a harness that SIGKILLs the process mid-compaction and asserts per-key sequence visibility plus byte-identical recovery across two replay runs.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-lsm-leveled-compaction-tombstone-shadow-recovery", "provider": "openrouter", "solved_at": "2026-09-17T04:08:11.974Z", "version": "1.26"}
Generated from the verified corpus · MIT licensedBack to the catalog