Range Tombstones: Deleting Many Keys at Once

Range Tombstones: Deleting Many Keys at Once

Point tombstones (from the last lesson) solve "delete one key," but they don't scale to operations like "drop every key with this prefix" or "expire everything older than X" — writing a tombstone per key would mean a delete of a million keys costs a million writes. Range tombstones solve this: a single record that says "every key in [start, end) is deleted as of this sequence number," regardless of how many keys that turns out to be, known or unknown, at write time.

The record shape

RANGE_TOMB start end seq

covering start <= key < end — note the half-open interval: start is inclusive, end is exclusive. This convention (shared with the LSM tree's SSTable block boundaries and with things like RocksDB's DeleteRange) matters for a concrete reason: half-open ranges compose cleanly. Two adjacent ranges [a, m) and [m, z) partition the keyspace with no gap and no overlap at m — an inclusive-inclusive convention can't do that without off-by-one special casing.

Applying a range tombstone to a read

A key k is killed by a range tombstone (start, end, ts) if:

start <= k < end   AND   entry.seq < ts   AND   ts <= snapshot

Two conditions to keep straight:

• The comparison is on the entry's seq being older than the tombstone's seq (entry.seq < ts) — a range tombstone only shadows writes that happened before it. A PUT issued after the range-delete "resurrects" that key, because it has a higher seq than the tombstone.
• The tombstone itself is subject to the snapshot rule too — ts <= snapshot — an old scan taken before the delete happened shouldn't see the delete's effects at all, symmetric with how point tombstones work.

This means checking whether a key is visible now requires checking it against every applicable point tombstone and every applicable range tombstone that covers it, then taking the entry with the highest seq that survives all of them — reusing the exact "collapse to max visible seq" pattern from every earlier lesson in this chapter.

Why range tombstones need separate storage from point data

A range tombstone doesn't have "a key" in the normal sorted-key sense — it covers a span of keys that may not even exist yet. Real systems (RocksDB) store range tombstones in a separate meta-block per SSTable rather than inline in the regular key-value stream, and a read has to consult both: the sorted point entries and the (usually much smaller) list of range tombstones whose span might overlap the query. This is why the RANGE_TOMB records in the exercise are parsed and checked independently from ENTRY/POINT_TOMB — that separation mirrors the real on-disk layout, not just a convenience for parsing.

Correctness pitfalls

• Exclusive end boundary. A range tombstone [c, e) does not cover e itself — a very common off-by-one bug is to write start <= k <= end, which silently deletes one key too many.
• Compaction must merge range tombstones like any other data, and — just like point tombstones — a range tombstone can only be dropped once you're certain no older shadowed data exists below it in any level, and once no active snapshot could still need it.
• Cost model: a single range tombstone can shadow an unbounded number of keys cheaply, but it also means a read touching that range has to check against it explicitly — a compactor that lets too many range tombstones accumulate can create a different kind of read amplification (scanning past a "wall" of deleted, un-reclaimed key ranges), which is exactly the pathology RocksDB's DeleteRange documentation warns about under adversarial usage.