The Cassandra Tombstone Incident: Why Deletes Can Destroy Read Latency

In a relational database, running DELETE removes a row. The disk space is eventually reclaimed, and subsequent SELECT statements are completely unaware the row ever existed.

In a distributed, append-only database like Apache Cassandra, running DELETE is actually an INSERT. You insert a marker called a tombstone. If you do not understand the physics of tombstones, deleting data will eventually destroy your read path.

Situation

In 2023, an application team deployed a new feature that introduced soft-deletes and TTL (Time-To-Live) updates on a heavy user notification table in the 36-node cluster. The table handled ~30k read QPS and ~50k write/delete QPS.

Within four hours of the deployment, p99 read latency on that table skyrocketed from 4ms to 2,800ms. Clients started timing out. The Cassandra system.log was flooded with WARN: Read 5000 tombstones in <keyspace>.<table>, followed quickly by catastrophic TombstoneOverwhelmingException errors, causing coordinator nodes to forcefully drop queries and sever client connections.

The Problem

Cassandra uses a Log-Structured Merge-Tree (LSM) storage engine. SSTables on disk are immutable. You cannot go into a locked 10 GB file and erase a row.

Instead, when you execute a DELETE or a TTL expires, Cassandra writes a tombstone—a marker asserting that the data is dead. When a read query requests data for a partition, Cassandra must merge the live data from various SSTables with the tombstones. If the read query has to scan past 5,000 tombstones to find 10 live rows, the database burns massive amounts of CPU and JVM memory holding those tombstones during the merge process.

To protect the JVM from running out of memory (OOM), Cassandra implements hard guardrails: tombstone_warn_threshold (warns at 1,000 scanned tombstones) and tombstone_failure_threshold (aborts the query at 100,000).

The application team had introduced an anti-pattern. They were inserting rows with column-level null values (which Cassandra interprets as point tombstones) and performing massive range scans across partitions littered with deleted records.

The Tombstone Lifecycle and Resurrection

You might ask: “Why doesn’t Cassandra just delete the tombstones during compaction?”

Because Cassandra is a distributed system, nodes can be offline. If Node A misses a DELETE, Node B and C record the tombstone. If Node B and C purge the tombstone immediately, and Node A comes back online, Node A will stream the old, live data back to Node B and C during repair. The deleted data comes back from the dead. We call this Zombie Resurrection.

flowchart TD
    App[Client Executes DELETE] --> Insert[Cassandra Inserts Tombstone]
    
    Insert --> Wait[Wait for gc_grace_seconds — Default: 10 Days]
    
    subgraph "The 10-Day Anti-Entropy Window"
        Wait --> Repair[Run nodetool repair — Synchronize Tombstone across Replicas]
    end
    
    Repair --> Compaction[Background Compaction]
    
    Compaction --> Eval{Is Tombstone Older — than gc_grace_seconds?}
    Eval -->|No| Keep[Keep Tombstone in new SSTable]
    Eval -->|Yes| Purge[Safely Purge Tombstone — Reclaim Disk Space]
    
    %% Zombie Path
    Wait -.->|Repair Skipped — Missed| EarlyPurge[Premature Purge]
    EarlyPurge -.-> OfflineNode[Offline Node returns]
    OfflineNode -.-> Zombie[Zombie Data Resurrected]

To prevent this, Cassandra forces tombstones to live on disk for gc_grace_seconds (default 10 days) to give you time to run a full cluster repair (nodetool repair). Purging isn’t automatic once that window passes, though: a tombstone is only eligible for removal once gc_grace has elapsed and every SSTable fragment covering that partition — across all overlapping SSTables, not just one — gets compacted together in the same compaction. A tombstone sitting in an SSTable that a compaction doesn’t happen to touch stays on disk indefinitely past its grace period, which is exactly why STCS tables with wide, unevenly-sized SSTables can accumulate purge-eligible-but-unpurged tombstones for a long time.

In Practice

The playbook executes a two-phase remediation plan.

Short-Term Emergency: By the time the incident was fully diagnosed and the fix was ready to ship — several days after the initial deployment, not the same afternoon the alerts fired — the oldest tombstones from the offending feature were already past the point a shorter grace period would purge them. The read path was still choking on tombstones that couldn’t be purged because they were newer than 10 days. For this specific table (which we repaired daily), we safely lowered gc_grace_seconds to 3 days (259200 seconds). We then triggered user-defined compactions (nodetool compact -s) to force the merging of SSTables and the purging of expired tombstones, dropping p99 latency back to 10ms.

Long-Term Fix: We redesigned the CQL data model with the application team. We banned inserting null into columns. We shifted from point-deletes to whole-row deletes, and redesigned queries to avoid scanning across wide ranges of recently deleted data.

Where It Breaks

Design Choice	Tradeoff	Mitigation
Dropping gc_grace_seconds to 0	Setting it to 0 allows immediate purging of tombstones during compaction. If a node is down for 1 minute during a delete, that data will resurrect as a zombie.	Only lower gc_grace_seconds if you have absolute confidence in your automated anti-entropy repair frequency.
High TTL Workloads on STCS	Size-Tiered Compaction Strategy rarely compacts the largest, oldest SSTables, meaning tombstones get trapped forever, inflating disk usage.	Use Time-Window Compaction Strategy (TWCS) for TTL data, allowing Cassandra to drop entire SSTables without scanning tombstones.
Column-Level Deletes	Deleting 50 columns in a row creates 50 tombstones.	Delete the entire row, which creates exactly 1 range tombstone.

Modern Cassandra Context: Cassandra 5.0 Guardrails

Cassandra 4.1 introduced dynamic Guardrails that can be configured per-keyspace. Rather than waiting for a TombstoneOverwhelmingException to crash a replica, operators can now enforce strict tombstone_warn_threshold and tombstone_failure_threshold limits directly at the coordinator level, rejecting badly designed queries before they saturate the storage engine’s read path. Additionally, Cassandra 5.0’s Unified Compaction Strategy (UCS) reduces the number of overlapping SSTables a given partition’s fragments tend to accumulate across, which in practice means fewer partitions get stuck waiting on a wide compaction to become tombstone-purge eligible.

What to Do Next

• Problem: Deleting data in Cassandra inserts tombstones. Reading past thousands of tombstones causes JVM memory exhaustion and massive read latencies.
• Solution: Avoid column-level deletes, stop inserting null values, and ensure your data model does not rely on range-scanning across deleted records.
• Proof: Lowering gc_grace_seconds (with adequate repair) and forcing compaction purges tombstones and instantly restores read performance.
• Action: Run nodetool tablestats and check the Tombstones per read metric. If the max value is routinely over 1,000, you have a data modeling emergency.