Tombstones and compaction scope
What this concept is
A tombstone records a deletion so older versions do not become visible. Whether it may be removed depends on which history and readers the compaction covers. Full-history compaction with no snapshots has a simpler contract than merging a subset of immutable runs.
Why it matters here
The reference compact function sees every record and replaces that entire history. It can emit only live values. Applying the same function to just the newest run can erase the only evidence that an older value was deleted.
Concrete example
Old run R0 contains put(a,old); newer run R1 contains delete(a). Searching newest-first returns absent. Compacting only R1 to an empty run and retaining R0 makes a=old visible again. Full compaction of R0 and R1 can omit a because no older copy remains in this model. A snapshot that still needs old would change the contract again.
Common confusion / misconception
Empty bytes is a value; it is not a tombstone. A truthiness filter drops legitimate zero-length values. Likewise, first value wins is incorrect for this ordered log: the final complete update determines visibility.
How to use it
Write the compaction input set, excluded older runs, snapshot assumptions and replacement scope. For the reference full-history case, replay once, emit one put per surviving key in sorted byte order, and check equal recovered state plus compact(compact(log)) == compact(log). Rebuild offsets; a correct old offset can now address unrelated bytes.
Check yourself
Does equal current state prove that every historical snapshot remains valid? Can a Bloom filter make dropping a required tombstone safe? Explain why neither follows.
Mini drill or application
Construct two runs with two keys, one delete and one empty value. Show the incorrect visible state after partial compaction drops both. Repair by preserving required tombstones and treating empty values explicitly.
Read this only if stuck
Use Database Internals on LSM compaction and LevelDB implementation notes on deletion markers and overlapping levels. Read the marker-retention argument; historical numeric tuning examples are not current performance promises.