Range Tombstones: Deleting Many Keys at Once

A point tombstone deletes one key. But what if you need to delete a million keys — say, DELETE FROM events WHERE day = '2024-01-15'?

You could write a million point tombstones. That's a million WAL records, a million memtable entries, a million compaction overhead. Painful and wasteful.

The fix: a range tombstone (RocksDB's DeleteRange, also called range delete marker). One record that says "all keys in [start, end) with seq < this tombstone's seq are dead."

The Format

record_type:  kTypeRangeDeletion
seq:          monotonic
start_key:    bytes
end_key:      bytes (exclusive)

One record, regardless of how many keys it affects.

Read Path with Range Tombstones

For a point read of key k at snapshot snap:

1. Walk the SSTables newest-first.
2. For each SSTable, check both:
   • The data blocks (any point version of k?)
   • The range tombstones (does any one cover k with seq <= snap?)
3. If the value version's seq is smaller than the covering range tombstone's seq, the value is dead.

This means range tombstones must be separately indexed so a point lookup doesn't scan all of them. RocksDB stores a per-SSTable range-tombstone meta-block with its own interval tree.

Compaction with Range Tombstones

During compaction:

• A range tombstone covers any point version with smaller seq whose key falls in the range. Drop the covered point versions.
• The range tombstone itself propagates until it reaches the bottommost level OR no older covered versions exist below.
• Multiple range tombstones can be merged (consolidated) if they overlap.

Write Cost vs Point Tombstones

For bulk deletes, range tombstones are 100-1000x cheaper.

When to Use Them

• TRUNCATE: drop the whole table → one range tombstone covering all keys.
• Time-based partitioning: drop all data for a date.
• Index rebuilds: drop all keys with a prefix.

Caveats

Range tombstones complicate the read path. RocksDB had subtle correctness bugs with range tombstones for years before stabilizing. They're worth the complexity only for bulk-delete workloads.

Cassandra calls them "range tombstones" too and has similar warnings: misuse can cause "tombstone overwhelm" warnings during range scans because the engine must consult them on every read.

Summary

Range tombstones are an optimization, not a default. Use point tombstones for individual deletes; reach for range tombstones when you need to delete many contiguous keys.