Skip to main content
← PROBLEMS / ARCHITECTURE
An end-to-end domain learning journey

Preventing Cassandra
Tombstone Accumulation.

A background job-scheduler backed by Cassandra/ScyllaDB ingests 200M short-lived tasks/day (TTL = 86400s or explicit DELETE upon completion) into PRIMARY KEY (queue_name, task_id). Workers poll SELECT * FROM tasks WHERE queue_name = 'default' LIMIT 50. Within 12 hours, queries fail with TombstoneOverwhelmingException (exceeding tombstone_failure_threshold = 100000) and p99 read latency hits 4.2 seconds. Redesign the data model, compaction strategy, and access pattern to eliminate tombstone scans.
Start the journey5 stages
Preventing Cassandra Tombstone Accumulation architecture sketch diagram
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

A background job-scheduler backed by Cassandra/ScyllaDB ingests 200M short-lived tasks/day (`TTL = 86400s` or explicit `DELETE` upon completion) into `PRIMARY KEY (queue_name, task_id)`. Workers poll `SELECT * FROM tasks WHERE queue_name = 'default' LIMIT 50`. Within 12 hours, queries fail with `TombstoneOverwhelmingException` (exceeding `tombstone_failure_threshold = 100000`) and p99 read latency hits 4.2 seconds. Redesign the data model, compaction strategy, and access pattern to eliminate tombstone scans.

From patterns to decisions.

A background job-scheduler backed by Cassandra/ScyllaDB ingests 200M short-lived tasks/day (`TTL = 86400s` or explicit `DELETE` upon completion) into `PRIMARY KEY (queue_name, task_id)`. Workers poll `SELECT * FROM tasks WHERE queue_name = 'default' LIMIT 50`. Within 12 hours, queries fail with `TombstoneOverwhelmingException` (exceeding `tombstone_failure_threshold = 100000`) and p99 read latency hits 4.2 seconds. Redesign the data model, compaction strategy, and access pattern to eliminate tombstone scans.

01
ARCHITECTURE · STAGE 01L4 · FUNDAMENTALS

Deleting the oldest rows writes.

Deleting the oldest rows writes tombstones at the start of the partition. Every LIMIT 50 scan starts at the partition head and must read through 100,000+ tombstones before finding 50 live rows.

ChoiceWhat it buysWhat it costs
Trade-off 1Raising `tombstone_failure_threshold` only masks the bug until the node OOMs.

Step 1

Describe how DELETE appends a tombstone marker in memtables/SSTables rather than erasing in place.

Step 2

Show how LIMIT 50 starts at the smallest clustering key where tombstones accumulate.

Alternative 1

Cursor-based pagination (WHERE task_id > :last_seen LIMIT 50) within short time buckets.

Failure Mode 1

Coordinator memory exhaustion and multi-second GC pauses.

-- Anti-pattern: head-of-partition polling over deleted rows
SELECT task_id, payload FROM tasks WHERE queue_name = 'default' LIMIT 50;
-- Reads 100,000+ tombstones -> TombstoneOverwhelmingException!
02
ARCHITECTURE · STAGE 02L5 · APPLIED DESIGN

Implementation & Guardrails (2).

Define tasks_by_bucket with (queue_name, hour_bucket, shard_id) partition key, TWCS 1-hour windows, default_time_to_live = 86400, and bind UNSET_VALUE in Python.

ChoiceWhat it buysWhat it costs
Trade-off 1TWCS drops whole 1-hour SSTables cleanly after 25 hours with near-zero compaction I/O.

Step 1

Create the CQL table with TWCS and gc_grace_seconds = 3600.

Step 2

Use UNSET_VALUE in cassandra-driver so omitted fields do not write cell tombstones.

Alternative 1

ScyllaDB TWCS with expired_sstable_check_frequency_seconds.

Failure Mode 1

Running UPDATE without USING TTL on an older row pins its SSTable from expiring.

CREATE TABLE scheduler.tasks_by_bucket (
    queue_name text,
    hour_bucket text, -- e.g., '2026-11-13T01'
    shard_id int,     -- 0..99
    task_id timeuuid,
    status text,
    payload blob,
    error_msg text,
    PRIMARY KEY ((queue_name, hour_bucket, shard_id), task_id)
) WITH default_time_to_live = 86400
   AND gc_grace_seconds = 3600
   AND compaction = {
     'class': 'TimeWindowCompactionStrategy',
     'compaction_window_unit': 'HOURS',
     'compaction_window_size': 1,
     'unchecked_tombstone_compaction': true
   };
03
ARCHITECTURE · STAGE 03L6 · SCALE & TRADE-OFFS

Binding None in INSERT writes.

Binding None in INSERT writes an explicit cell tombstone for error_msg. Using UNSET_VALUE skips the column entirely on the wire, writing zero tombstones.

ChoiceWhat it buysWhat it costs
Trade-off 1Zero tombstones written on insert, though `UNSET_VALUE` cannot clear an existing non-null value on an `UPDATE`.

Step 1

Import UNSET_VALUE from cassandra.query.

Step 2

Replace None with UNSET_VALUE for all optional fields on INSERT.

Alternative 1

Use separate prepared statements for rows with and without optional columns.

Failure Mode 1

Using UNSET_VALUE when you actually intended to erase a previously populated column.

from cassandra.query import UNSET_VALUE

def insert_task(session, prep_stmt, queue_name: str, hour_bucket: str, shard_id: int, task_id, payload: bytes, error_msg: str | None = None):
    # Never bind None -> writes a cell tombstone! Use UNSET_VALUE.
    err_val = error_msg if error_msg is not None else UNSET_VALUE
    session.execute(prep_stmt, (queue_name, hour_bucket, shard_id, task_id, "PENDING", payload, err_val))
04
ARCHITECTURE · STAGE 04L6 · SCALE & TRADE-OFFS

Implementation & Guardrails (4).

Inspect SSTable metadata via sstablemetadata to verify Estimated droppable tombstones and Maximum timestamp vs. Minimum timestamp do not span multiple 1-hour windows.

ChoiceWhat it buysWhat it costs
Trade-off 1Aligning late-update TTLs keeps every SSTable's expiration timestamp tightly bounded.

Step 1

Check sstablemetadata for overlapping min/max timestamps (indicates mixed TTLs or repairs mixing windows).

Step 2

Verify gc_grace_seconds (3600) + TTL (86400) has elapsed for the oldest SSTables.

Alternative 1

Reject updates to buckets older than 23 hours.

Failure Mode 1

Running nodetool repair on TWCS without subrange/incremental awareness can merge old and new windows.

# Helper to compute remaining TTL so late updates expire with the original bucket
import time

def remaining_bucket_ttl(bucket_epoch_s: int, base_ttl_s: int = 86400) -> int:
    elapsed = int(time.time()) - bucket_epoch_s
    return max(60, base_ttl_s - elapsed)
05
ARCHITECTURE · STAGE 05L7 · STAFF / PRINCIPAL

Implementation & Guardrails (5).

Maintain a durable last_processed_task_id checkpoint per (queue_name, hour_bucket, shard_id) and query WHERE task_id > :checkpoint LIMIT 50 so scans never touch prior tombstones.

ChoiceWhat it buysWhat it costs
Trade-off 1Eliminates tombstone scans for sequential readers, though out-of-order late writes before `checkpoint` are skipped.

Step 1

Store checkpoint_task_id in a tiny metadata table or Redis.

Step 2

Advance the hour_bucket pointer once the current bucket is empty and past its hour boundary.

Alternative 1

Migrate fully to Kafka/RabbitMQ for work distribution.

Failure Mode 1

Clock skew between producers creating TimeUUIDs out of order causes missed tasks if task_id > checkpoint.

-- Cursor-based scan skips all prior tombstones
SELECT task_id, payload
FROM scheduler.tasks_by_bucket
WHERE queue_name = ? AND hour_bucket = ? AND shard_id = ?
  AND task_id > ?
LIMIT 50;

Theory & Tips and Tricks

Practical heuristics & interview traps

  • 01Interview anchor: Never model a FIFO queue in an LSM-tree without time-bucketing; use TimeWindowCompactionStrategy (TWCS), partition by (bucket_id, time_slice), and align gc_grace_seconds so entire SSTables drop cleanly.
  • 02Trade-off tip: Zero tombstones written on insert, though UNSET_VALUE cannot clear an existing non-null value on an UPDATE.
  • 03Watch out for: Running nodetool repair on TWCS without subrange/incremental awareness can merge old and new windows.
Behavioral Progression · Cassandra Tombstone Accumulation Scans

Cassandra Tombstone Accumulation Scans — Normal → Load / Fault → Recovery

Send Request
1. Normal Request Ingress
Traffic: 1x baseline · Latency (p99): 4 ms
Process State
2. Core Execution & State Lookup
Traffic: 1x baseline · Latency (p99): 9 ms
Inject 10x Spike
3. Scale Spike / Failure Injection
Traffic: 10x burst · Latency (p99): 185 ms

Never model a FIFO queue in an LSM-tree without time-bucketing; use TimeWindowCompactionStrategy (TWCS), partition by (bucketid, timeslice), and align gcgraceseconds so entire SSTables drop cleanly.

Synthesis / One connected design

Putting Preventing Cassandra Tombstone Accumulation Together

Never model a FIFO queue in an LSM-tree without time-bucketing; use `TimeWindowCompactionStrategy` (TWCS), partition by `(bucket_id, time_slice)`, and align `gc_grace_seconds` so entire SSTables drop cleanly.

A candidate architecture, not a universal answer

Putting Preventing Cassandra Tombstone Accumulation Together

Step 1
Step 2
  1. Create the CQL table with TWCS and gc_grace_seconds = 3600.
  2. Use UNSET_VALUE in cassandra-driver so omitted fields do not write cell tombstones.
Inspect SSTable metadata via `sstablemetadata` to verify `Estimated droppable tombstones` and `Maximum timestamp` vs. `Minimum timestamp` do not span multiple 1-hour windows.
Interview Readiness Check

Inspect SSTable metadata via sstablemetadata to verify Estimated droppable tombstones and Maximum timestamp vs. Minimum timestamp do not span multiple 1-hour windows.

Walk through bottlenecks, back-of-the-envelope math, and failure recovery.

Practice / Explain the consequences

Make the trade-off yourself.

Practice Check

Test your understanding

Question 1 of 3

When is ACID Transaction Fundamentals the right default for a production team?

Key takeaway

Preventing Cassandra Tombstone Accumulation

Never model a FIFO queue in an LSM-tree without time-bucketing; use TimeWindowCompactionStrategy (TWCS), partition by (bucket_id, time_slice), and align gc_grace_seconds so entire SSTables drop cleanly.