Cassandra tombstones and the range-scan timeout

What it is

In Cassandra and ScyllaDB, a delete does not remove data. It writes a tombstone, a marker recording that a cell, a row, or a range of rows was deleted at a particular timestamp. The actual data disappears later, during compaction, and only after a grace period called gc_grace_seconds (default 864,000 seconds, which is ten days).

Tombstones are commonly confused with two other things. They are not a performance optimisation of the delete path, though they are cheap to write. And they are not garbage that a background process eventually tidies up in the ordinary sense; they are load-bearing data whose premature removal causes deleted rows to come back to life.

The interview-relevant consequence: a read that scans a partition must merge every tombstone it encounters into its result, in memory, before returning anything. A partition holding a million tombstones and ten live rows costs a million rows of work to return ten. That is why the classic symptom is a query that used to be fast and is now timing out, on a table whose live row count has not changed.

The problem it solves

Cassandra has no coordinator with a global view and no read-before-write on the delete path. Replicas take writes independently and reconcile later. If a delete simply removed the local copy, this happens:

Node A and Node B both hold row X.
A delete arrives; A applies it, B is down and misses it.
B comes back. Anti-entropy repair compares A and B, sees that B has X and A does not, and helpfully copies X back to A.

The row is resurrected, permanently, with no error anywhere. A tombstone prevents this because it is a write with a timestamp, and last-write-wins reconciliation resolves tombstone(t=200) against row(t=100) correctly: the deletion wins and propagates.

gc_grace_seconds exists for the same reason. The tombstone must survive long enough for repair to carry it to every replica that holds the data. Purge it earlier and a replica that never learned about the delete will resurrect the row at the next repair. This is the single most important operational rule in Cassandra: you must run a full repair on every table more often than gc_grace_seconds, or you will get zombie data.

Mechanics

The five kinds of tombstone

They differ enormously in cost, and knowing the difference is the depth signal.

Kind	Written by	Cost
Cell tombstone	`UPDATE t SET c = null` or deleting one column	One marker per cell
Row tombstone	`DELETE FROM t WHERE pk = ? AND ck = ?`	One marker per row
Range tombstone	`DELETE FROM t WHERE pk = ? AND ck < ?`	One marker covering an open interval, cheap to write, expensive to reason about
Partition tombstone	`DELETE FROM t WHERE pk = ?`	One marker shadowing an entire partition, the cheapest of all
TTL expiry	`USING TTL`, or a default TTL on the table	One tombstone per expired cell, generated silently, at scale

The last row is the ambush. A table with default_time_to_live generates tombstones continuously without anyone issuing a DELETE, and teams who carefully avoid deletes are often manufacturing tombstones by the million through TTLs.

Setting a column to null in an UPDATE is also a delete. UPDATE users SET middle_name = null WHERE id = ? writes a cell tombstone. Applications that serialise a whole object and write every field, nulls included, generate a tombstone per null field per write, forever. That pattern, usually introduced by an ORM or a naive mapper, is a common cause of an inexplicably tombstone-heavy table.

Why reads pay for them

A read for a slice of a partition must produce the correct merged view across every SSTable that could contain relevant data, plus the memtable. Tombstones cannot be skipped, because a tombstone in one SSTable may shadow a live cell in another, and the reader cannot know which without examining both. So the coordinator's iterator walks tombstones, holds them in memory, and applies them.

Cassandra therefore has two guard rails, both configured in cassandra.yaml:

tombstone_warn_threshold: 1000       # log a WARN when a read scans this many
tombstone_failure_threshold: 100000  # abort the query with TombstoneOverwhelmingException

The corresponding log line is the fingerprint of this problem, and being able to quote its shape is worth doing:

WARN  Read 12 live rows and 148230 tombstone cells for query
      SELECT * FROM events.by_user WHERE user_id = 8842 LIMIT 100
      (see tombstone_warn_threshold)

Twelve live rows, 148,230 tombstones. That ratio is the diagnosis, and it is printed for you.

The queue anti-pattern

The canonical way to create this problem:

-- The wrong shape. Cassandra used as a work queue.
CREATE TABLE jobs (
    queue_name text,
    job_id     timeuuid,
    payload    text,
    PRIMARY KEY (queue_name, job_id)
) WITH CLUSTERING ORDER BY (job_id ASC);

-- Consumers do this, forever:
SELECT * FROM jobs WHERE queue_name = 'ingest' LIMIT 10;
DELETE FROM jobs WHERE queue_name = 'ingest' AND job_id = ?;

Every consumed job leaves a row tombstone at the head of the partition. The SELECT starts at the beginning of the clustering order and walks forward, which means it walks through every tombstone ever created before it reaches a live row. After a day at 100 jobs per second, that is 8.6 million tombstones in front of the first live row. Reads slow, then hit tombstone_warn_threshold, then hit tombstone_failure_threshold and start throwing. The table has ten live rows.

Cassandra's documentation names queues as an explicit anti-pattern for precisely this reason, and the fix is not tuning: it is a different data model or a different database. Kafka, SQS or Pulsar are built for this shape.

A worked example: diagnosis and repair

An events table for an activity feed. Partition key user_id, clustering key event_time descending, default_time_to_live of 30 days. Reads of a heavy user's recent events start timing out after four months in production.

Diagnose.

# 1. Confirm the ratio from the logs.
$ grep -c "tombstone cells" /var/log/cassandra/system.log
2841

# 2. Get the partition-level statistics. The percentile columns are what matter.
$ nodetool tablehistograms events by_user
Percentile   SSTables  Write(µs)  Read(µs)  Partition Size  Cell Count
50%              3.00      35.43    124.00            1916          42
95%             10.00      51.01   9887.00          454826       11864
99%             14.00      73.46  74502.00         3379391      182785
Max             17.00     126.93 186563.00        14530764      924000

# 3. Confirm which partitions are the problem.
$ nodetool tablestats events.by_user | grep -E 'tombstone|partition'
    Compacted partition maximum bytes: 14530764
    Average live cells per slice (last five minutes): 38.0
    Average tombstones per slice (last five minutes): 41208.0

Forty-one thousand tombstones per slice against thirty-eight live cells. Read latency at p99 is 74 ms against 124 microseconds at p50, a spread of nearly 600x, which is the shape of a scan cost rather than a lookup cost.

Root causes, in this case two.

First, the compaction strategy is SizeTieredCompactionStrategy, the default. STCS compacts SSTables of similar size together, which means an old SSTable containing expired data may not be compacted for a very long time, so TTL tombstones and the data they shadow linger. For time-series data with a uniform TTL, TimeWindowCompactionStrategy groups data by time window and can drop an entire expired SSTable without compacting it at all.

Second, the read pattern. SELECT ... WHERE user_id = ? ORDER BY event_time DESC LIMIT 50 is fine, but a query without an explicit upper bound on event_time scans from the start of the clustering range and encounters the oldest, most tombstoned region first.

Repair.

-- 1. Switch to TWCS with a window matched to the TTL. A 30-day TTL with
--    1-day windows means an entire SSTable becomes fully expired and is
--    dropped wholesale, without a compaction pass over its contents.
ALTER TABLE events.by_user
  WITH compaction = {
    'class': 'TimeWindowCompactionStrategy',
    'compaction_window_unit': 'DAYS',
    'compaction_window_size': 1
  }
  AND gc_grace_seconds = 259200;   -- 3 days, NOT the 10-day default:
                                   -- safe only because we repair every 24h,
                                   -- which must be verified before changing it

-- 2. Bound the read so it never scans the old region.
SELECT * FROM events.by_user
 WHERE user_id = ?
   AND event_time > ?      -- explicit lower bound, e.g. now - 7 days
 ORDER BY event_time DESC
 LIMIT 50;

If the partitions are already unbounded in size, the deeper fix is bucketing the partition key: PRIMARY KEY ((user_id, day), event_time). That caps partition size by construction, keeps tombstones confined to a bucket, and lets whole buckets age out. It costs the application a small amount of work (query the last N day-buckets, merge client-side) and it is the correct Cassandra data model for unbounded time series.

nodetool garbagecollect can force removal of already-purgeable tombstones, and nodetool compact on a single table will do it more aggressively, but both are treatments rather than cures: they run once and the model regenerates the problem.

Production evidence

The Apache Cassandra documentation names distributed queues and queue-like datasets as an anti-pattern specifically because of tombstone accumulation on range scans, and the tombstone_warn_threshold and tombstone_failure_threshold settings exist in cassandra.yaml because this failure was common enough to warrant a built-in circuit breaker.

TimeWindowCompactionStrategy was contributed to Cassandra (CASSANDRA-9666) to replace the earlier DateTieredCompactionStrategy for exactly this class of time-series-with-TTL workload, and the ability to drop a fully expired SSTable without compacting it is its headline property.

ScyllaDB, which is API-compatible and written in C++, inherits the same data model and the same tombstone semantics, and their documentation and engineering blog treat tombstone management as a primary operational topic. Their per-shard architecture improves the constant factors on the read path; it does not change the asymptotics, which is a useful thing to say if someone offers Scylla as the fix.

DataStax's production guidance, and essentially every Cassandra operations write-up, converges on the same three rules: run repair more often than gc_grace_seconds, keep partitions bounded (a widely used rule of thumb is under about 100 MB and under about 100,000 rows), and do not model deletes as a first-class access pattern.

The debate

The alternative to managing tombstones is to stop deleting. Three shapes:

Immutable append with a bucketed partition key. Never delete; let whole buckets expire via TTL and TWCS, so expiry drops SSTables rather than scanning tombstones. This is the idiomatic Cassandra answer for time series and it is the one I would pick by default.

Soft delete with a status column. Never write a tombstone; write status = 'deleted' and filter on read. This trades tombstone cost for permanently growing storage and a filter on every read, and it does not satisfy a GDPR erasure request, which is a real constraint for many teams.

Use a different store for the delete-heavy access pattern. If the workload is a queue, use a queue. If it is mutable relational data with frequent deletes, Cassandra is the wrong engine and no amount of compaction tuning fixes a modelling mismatch.

My position: Cassandra's write path is optimised for immutable, append-only, time-ordered data with a known query pattern, and every tombstone problem I have seen traces back to using it for something else. Model to avoid deletes; use TTL with TWCS when data must expire; bucket partition keys so nothing grows unbounded; and treat frequent deletes as a signal that this table belongs in a different store. Lowering gc_grace_seconds is a legitimate tool and it is the last one I would reach for, because it trades a performance problem for a correctness risk and the correctness risk is silent.

Tombstone tuning is the wrong focus when the real problem is partition size. A 14 GB partition is a problem whether or not it contains tombstones: it cannot be repaired efficiently, it cannot be compacted without a large disk and memory spike, and it makes one node hot regardless of your compaction strategy.

Follow-up Q&A

"Why did our Cassandra range query start timing out?" Almost certainly tombstone accumulation in the scanned range. Confirm it from the logs (the WARN prints live rows and tombstone cells for the exact query) and from nodetool tablehistograms, comparing p50 and p99 read latency and partition size. Then find the source: explicit deletes, TTL expiry, or null writes from the application. The fix is at the data model layer (bucket the partition key, bound the read range) and at the compaction layer (TWCS for TTL'd time series), not at the tuning layer.

"What happens if you set gc_grace_seconds to zero?" Tombstones become purgeable at the next compaction, so deleted data can be removed almost immediately, and any replica that missed the delete will resurrect the row at the next repair or read repair. It is only safe when the data is written and deleted within a single node's view, or when the table is single-replica, both of which are unusual. The defensible version is to lower it to a value comfortably above your verified full-repair cycle time, for example three days when you repair daily, and to alert if a repair cycle is missed.

"You have a table where every row is deleted after being read. What is the right design?" Not this database. That is a queue, and Cassandra's own documentation names it as an anti-pattern. If it must live in Cassandra, do not delete: use a TTL with TWCS so expiry drops SSTables, and bound reads with an explicit time range so consumers never scan the expired region. Better, put the queue in Kafka or SQS and keep Cassandra for the durable record.

"How do you tell a range tombstone from a million row tombstones?" By cost profile. A range tombstone is one marker covering an interval, so it is cheap to store and it shadows efficiently; a million row tombstones are a million markers the reader must merge. Deleting with an inequality on the clustering key (DELETE ... WHERE pk = ? AND ck < ?) creates the former, and deleting rows one at a time in a loop creates the latter. If your application deletes in a loop, rewriting it to a single range delete is often a large win for the same logical operation.

"Does ScyllaDB solve this?" It improves it and does not solve it. The shard-per-core architecture and C++ implementation give much better tail latency and more predictable compaction, so the same tombstone load hurts less. The semantics are identical: tombstones still exist, gc_grace_seconds still governs purging, repair is still mandatory, and a scan over a million tombstones is still a scan over a million tombstones. Offering "switch to Scylla" as the fix for a modelling problem is the wrong answer, and saying why is a good signal.

Common misconceptions

The biggest is that tombstones are cleaned up automatically and therefore not your problem. They are removed only when a compaction includes every SSTable that could contain the shadowed data, and only after gc_grace_seconds. Under SizeTieredCompactionStrategy, an old SSTable may wait a very long time for a compaction partner of similar size, so tombstones can persist far beyond the grace period.

The second is that only DELETE creates tombstones. TTL expiry and writing null both do, silently and at scale, and both are far more common in practice than explicit deletes.

The third is that raising tombstone_failure_threshold fixes the timeouts. It removes the circuit breaker that was protecting the node from an out-of-memory event. The threshold is a symptom detector, and disabling a symptom detector is not a fix.

Interview delivery note

Say this: "A delete in Cassandra writes a tombstone rather than removing data, because replicas reconcile by last-write-wins and a silent removal would let repair resurrect the row. Reads have to merge every tombstone in the scanned range in memory, so a partition with a million tombstones and ten live rows costs a million rows of work. The log line prints the ratio directly. The fix is at the data model: bucket the partition key, bound the read range, and use TimeWindowCompactionStrategy so expired SSTables get dropped rather than compacted. And the rule underneath all of it is that you must repair every table more often than gc_grace_seconds, or you get zombie data."

The depth signal is connecting gc_grace_seconds to the repair schedule and explaining resurrection. Many candidates know that deletes create tombstones. Far fewer can explain why the grace period exists, and that explanation is what shows you understand the replication model rather than the trivia.

The Staff & Team Lead Interview Reference