LSM tombstones: deleted is not yet reclaimed

12 October 2026 / Primary-source review

A successful delete can hide a key while its old value still occupies storage. Reclaiming that space too early can break snapshot reads or expose an older value again. Visibility, durability and reclamation need separate evidence.

Why an absent key needs a record

In LevelDB, sorted tables contain values and deletion markers. The marker tells a lookup not to accept an obsolete value in an older table. Compaction merges files and can discard obsolete versions; a deletion marker can be removed when deeper levels cannot contain an older value it must hide. [1]

Consider an upper table containing DELETE k and a lower table containingk = old. Removing only the marker would make the obsolete value eligible again. This two-record counterexample explains why counting tombstones is not enough to decide which bytes are garbage. It is an illustration, not an observed incident.

The same distinction matters for Bloom filters: membership in a file is not proof that a key is live in the database.

Three completion questions

Visibility: Does the intended read view still return the key?
Durability: Will the deletion survive the failure model being tested?
Reclamation: Have obsolete versions and unneeded files actually been removed?

RocksDB's synchronous-write option controls persistence of a write. Ordinary asynchronous acknowledgement is not the same promise after a machine crash.[3] Conversely, a persisted deletion marker does not imply that older SST contents have been rewritten. Recording the instruction and completing the cleanup are distinct events.

RocksDB snapshots preserve a sequence-number view and do not survive database restarts. They are not volume snapshots or independent backup copies.[2] The following invented trace assumes ordinary, non-transactional snapshot semantics and no concurrent writes:

One key, two views. Sequence numbers are ordering labels, not elapsed time.
Event	Latest view	Snapshot S at 10
10: put k = old; create S	old	old
11: delete k	absent	old
Compact while S exists	absent	old must remain readable
Release S	absent	view no longer available

The old value must remain available for S, but releasing S does not itself execute compaction or prove a byte count was reclaimed. Read the table as a correctness requirement, not as a prediction of file layout or cleanup time.

Range deletion is not a faster erase command

RocksDB's DeleteRange records a tombstone for a half-open interval: the start is included and the end excluded. It avoids issuing a separate delete for every key, but does not synchronously wipe the underlying values. Its design separates logical deletion from background cleanup.[4]

Likewise, an instruction to compact needs a defined scope. RocksDB documents options that can skip bottommost-level files and options controlling whether manual compaction waits to avoid write stalls. A returned compaction call is not a universal certificate that every obsolete byte was rewritten. Inspect the selected range, options, status and retained readers.[7]

Lethe treats deletion delay as a design target

Sarkar and colleagues' Lethe paper defines delete persistence latency as the delay from inserting a tombstone to removing the invalidated entries through compaction. FADE uses deletion age and file metadata to schedule cleanup; KiWi organizes pages around both a lookup key and a secondary deletion attribute. The latter addresses cases such as time-based expiration in data sorted by ID.[5, sections 3-4]

Its evaluation is a synthetic, RocksDB-based experiment, not a fleet study. The reported default setup uses 1 KB entries, a 1 MB buffer and a 1 GB load; WAL is disabled and compactions take priority over writes. Delete thresholds are fractions of experiment runtime. These choices limit transfer to a durable, latency-sensitive service. We reviewed the updated manuscript, including its methodology; we did not reproduce its performance measurements.[5, section 5]

A 2026 optimization, and its safety boundary

RocksDB now documents an iterator-based optimization that adds a range tombstone over a verified run of point deletions, allowing later scans to skip them. The original markers remain until ordinary cleanup. The project reports availability from version 11.3.0, with min_tombstones_for_range_conversion defaulting to zero, meaning disabled. This is a versioned feature, not a recommendation to enable it without workload testing. [6]

The subtlety is visibility across levels. A compaction looking at only some files can miss live keys between apparent consecutive deletions. Converting that local sequence into a range would delete those keys too. The documented optimization therefore requires a suitable global read view and applies safety guards. Faster scanning still does not prove physical erasure. [6]

An investigation checklist, not a tuning recipe

For a delete-heavy service, record the exact engine build, write options, compaction policy and active readers before comparing runs. Keep the same initial data, key ordering, deletion fraction and foreground load. Compare runs with a retained snapshot and with it released, using copies of test data.

Measure separate endpoints: read visibility, recovery after the specified fault, obsolete-file removal and allocated filesystem bytes. Add foreground latency percentiles, bytes read and written by compaction, and the age of outstanding deletions. A successful lookup check cannot substitute for these other observations. This is our proposed validation protocol, not a completed benchmark.

Finally, database cleanup says nothing by itself about copies in backups, replicas, filesystem snapshots or remapped flash. Establish those boundaries separately; see SSD sanitization evidence and discard versus zeroing. No media-sanitization or compliance guarantee follows from this review.

Corpus: LSM tombstone, range tombstone, delete persistence latency.

Primary sources

Sources reviewed 12 October 2026. No copied figures, hardware experiment or new performance result. Source works retain their own rights.