Build an LSM-tree storage engine (LevelDB / RocksDB style) (11 scenes)
Scene 09

Tombstones — deletes that can come back

A delete is just a record that says 'absence' (a tombstone), and compaction may only drop it when no deeper level can possibly still hold the live record it is shadowing — get this wrong and the deleted key resurrects on the next read.

Previously

We've only put records in. Deletes are records too — and where they LIVE on the staircase, and how long, decides whether your delete actually sticks.

Scene 09

Tombstones — deletes that can come back

  1. Watch
  2. Try it
  3. Predict
  4. Capture
step 1PUT k=v1flushed to L1step 2DELETE ktombstone in L0step 3L0→L1 compaction (na…tombstone dropped — no …step 4L1 still has k=v1older file beneath was …step 5GET kno tombstone, hits v1 —…step 6verdictnaive rule resurrected …L1L1/000003.s…k=v1a=5Step 1/6 — flushed to L1
What to watch for

Six storyboard steps with the NAIVE rule (the last is the verdict). Watch the tombstone get dropped at step 3 and the older live record resurrect at step 5.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

Compaction tombstone rule
the line between 'safe to drop' and 'resurrection bug'
def can_drop_tombstone(t, compaction_inputs, level):
    if level == BOTTOM_LEVEL: return True   # nothing deeper
    for deeper_level in levels_below(level):
        if deeper_level.has_overlapping(t.key):
            return False                   # older live may exist
    return True
 
# the WRONG rule (naive — used in scene's storyboard):
def naive_can_drop(t, inputs):
    return not any(r.key == t.key for r in inputs)
Range tombstone (variant)
delete a key range without writing per-key tombstones
# RocksDB DeleteRange — one record covers many keys:
range_tombstone = (begin_key, end_key, seqno)
# stored in a separate meta-block per SSTable
# read path: check both per-key tombstones AND range tombstones
# subject to the SAME retention rule across levels.
 
# LevelDB has no DeleteRange; it must DELETE each key individually.
Sources

Where this sits in Build an LSM-tree storage engine (LevelDB / RocksDB style)

Scene 09 of 11, in the Sharp edges act — Tombstones, blocks, and the canvas.. Deletes are records. Drop a tombstone before all older live records are gone, and the deleted key resurrects. Same trap as Bitcask, restated for levels.

Up next. Reads, writes, deletes — all sorted out. But every read so far has touched a whole SSTable. Real systems read BLOCKS, cache them in RAM, and squeeze them with compression. That's the production reality.

All 11 scenes in Build an LSM-tree storage engine (LevelDB / RocksDB style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build an LSM-tree storage engine (LevelDB / RocksDB style) builds on the one before it.All 11 Build an LSM-tree storage engine (LevelDB / RocksDB style) scenes