7. Timestamps and tombstones

Two mechanisms, deeply connected, and between them responsible for most of the surprises Cassandra has in store. This chapter is the counterpart to MVCC and vacuum in the PostgreSQL guide: the concurrency model, and the garbage it leaves behind.

Last-write-wins

Cassandra has no locks, no transactions, and no version chains. When two replicas hold different values for the same cell, the winner is decided by one rule:

The cell with the highest timestamp wins. If the timestamps tie, the larger value wins, compared as raw bytes.

That is the entire conflict-resolution algorithm. It is deterministic — every replica, given the same set of versions, independently reaches the same answer, with no communication. That property is what lets replicas converge without coordinating.

The timestamp is microseconds since the Unix epoch, assigned by default by the coordinator at write time.

SELECT name, writetime(name), ttl(name) FROM users WHERE id = 1;
--  name  | writetime(name)   | ttl(name)
--  Alice | 1755689234123456  | null

-- You can set it explicitly
INSERT INTO users (id, name) VALUES (1, 'Alice') USING TIMESTAMP 1755689234123456;

Consequence 1: clock skew is a correctness problem

If node A’s clock is five seconds ahead of node B’s, a write coordinated by A gets a timestamp five seconds in the future. A later, genuinely newer write coordinated by B has a lower timestamp — and loses. The newer value is silently discarded.

There is no error, no warning, and nothing in the logs. The data is just wrong.

Run NTP on every node, monitor it, and alert on drift. This is not routine sysadmin hygiene in Cassandra; it is a data-integrity requirement. chrony is the usual choice, and drift above a few tens of milliseconds is worth investigating.

Consequence 2: writes are not ordered by arrival

Two clients write to the same cell at nearly the same moment. Whichever write carries the higher timestamp wins, regardless of which arrived first, which replica it reached first, or which one the client believes succeeded.

There is no “the second write wins.” There is only “the higher timestamp wins.”

Consequence 3: no read-modify-write

   T1: SELECT balance → 100
   T2: SELECT balance → 100
   T1: UPDATE balance = 90    ts=1000
   T2: UPDATE balance = 90    ts=1001    ← wins

Both deductions happened. One survives. There is no conflict detection because there is no conflict to detect — both writes were valid, and one had a later timestamp.

Options, in order of preference: make the data immutable (write events, not state); use counters if you only need increments (chapter 11); use a lightweight transaction if you genuinely need compare-and-set and can afford it.

Consequence 4: USING TIMESTAMP is a loaded gun

Setting a timestamp far in the future makes a value permanently unbeatable — every subsequent normal write loses to it, including deletes. The only repair is another write with an even higher timestamp, which you must construct by hand.

This has happened to real clusters, usually via a bulk-import script that used seconds instead of microseconds, or vice versa. Be careful with the units: microseconds.

Tombstones: the delete that is a write

Cassandra never modifies data on disk. So how does it delete?

It writes a marker. A DELETE inserts a tombstone: a special cell that says “everything for this key with a lower timestamp is gone.”

DELETE FROM users WHERE id = 1;

   SSTable 1 (old)                    SSTable 4 (new)
   ┌──────────────────────────┐       ┌──────────────────────────┐
   │ id=1 name='Alice' ts=1000│       │ id=1  TOMBSTONE  ts=5000 │
   │ id=1 email='a@b' ts=1000 │       └──────────────────────────┘
   └──────────────────────────┘

   A read merges both and finds the tombstone is newer.
   It returns nothing.
   Both files still exist. The disk usage went UP.

A delete makes your data larger. Every read of that key still reads the old data and the tombstone, merges them, and discards the result.

Why it has to work this way

The tombstone is not an implementation quirk. It is load-bearing.

Suppose delete simply removed the data locally. Node A processes the delete; node B is down and misses it. Node B comes back. Now A has nothing and B has the row — and a read repair sees A missing data that B has, so it helpfully copies the row back to A. The deleted data returns.

The tombstone is what makes the deletion a fact that can be replicated. B receives the tombstone, learns the row is deleted, and both nodes agree.

The kinds of tombstone

Kind	Created by	Covers
Cell tombstone	DELETE col FROM t WHERE ...	one cell
Row tombstone	DELETE FROM t WHERE <full PK>	one row
Range tombstone	DELETE FROM t WHERE pk=? AND ck>?	a clustering range
Partition tombstone	DELETE FROM t WHERE <partition key>	a whole partition
TTL expiry	a cell’s TTL elapsing	one cell
Null insert	INSERT ... VALUES (?, null)	one cell — surprise!

Two of those deserve emphasis.

Range and partition tombstones are efficient. One marker covers a great deal of data. If you must delete in bulk, deleting a whole partition is dramatically cheaper than deleting its rows one at a time.

Writing null creates a tombstone. This one catches everyone:

INSERT INTO users (id, name, email, phone) VALUES (?, ?, ?, null);

That is not “leave phone unset.” It is a delete of the phone cell, and it writes a tombstone. An ORM or a driver helper that binds every column of an object, with unset fields as null, generates tombstones on every single write.

The fix is to mark parameters unset rather than null:

from cassandra.query import UNSET_VALUE
session.execute(stmt, (id, name, email, UNSET_VALUE))

Or prepare a statement listing only the columns you are actually setting. This alone has rescued clusters that were mysteriously accumulating billions of tombstones.

TTL expiry also creates tombstones. A table with default_time_to_live is continuously generating them as data ages out. That is fine and intended — but it means a TTL’d table is a table with a permanent tombstone workload, and the compaction strategy needs to suit it (chapter 8).

gc_grace_seconds

Tombstones cannot be removed immediately. If they were, a node that was down during the delete would come back holding the original data, and read repair would resurrect it.

So a tombstone is kept for gc_grace_seconds — default 864,000 seconds, which is ten days — before compaction is allowed to drop it.

   day 0   DELETE → tombstone written
     │
     │     tombstone is kept and returned in merges,
     │     replicated, and repaired to every replica
     │
   day 10  gc_grace_seconds elapses
     │     compaction may now drop the tombstone AND the data
     ▼     it shadows — but only if it can prove all the shadowed
           data is in the same compaction

Ten days is the window in which repair must run, and this is the rule that ties everything together:

You must run repair on every table at least once every gc_grace_seconds.

If you do not, some replica may never learn about the deletion before the tombstone is discarded elsewhere — and the deleted data comes back. Chapter 10 is about repair.

Zombie rows

Deleted data that returns. The mechanism:

   day 0   DELETE row X.  Nodes A and B get the tombstone.
           Node C is down and misses it.
   day 3   Node C comes back. It still holds row X.
   day 11  gc_grace passes. Compaction on A and B drops the tombstone.
           Now A and B have nothing; C has row X and no tombstone.
   day 12  A read at QUORUM hits A and C. C has data, A does not.
           Read repair concludes A is missing data and copies it over.

           Row X is back. Permanently.

Prevention is repair inside the grace window. There is no cure afterwards except deleting the data again.

Should you lower gc_grace_seconds?

Ten days is conservative, and shortening it reduces tombstone accumulation. It is also the safety margin for the entire zombie problem.

Lower it only if you can honestly say yes to all of these: repair completes reliably in well under the new window, you monitor and alert on repair failures, and you understand that a node down longer than the window must be rebuilt from scratch, not simply restarted.

A common compromise is 3 days on tombstone-heavy tables with daily repair, and the default elsewhere.

ALTER TABLE events WITH gc_grace_seconds = 259200;   -- 3 days

Setting it to 0 is only safe for tables where a resurrection is genuinely harmless and every write is immutable — for example, a table written once with a TTL and never explicitly deleted from, where the same row would simply be rewritten identically. It is a sharp tool.

When tombstones destroy read performance

A read must merge tombstones before it can discard them. If a partition contains 100,000 tombstones and 10 live rows, the read processes 100,010 items to return 10.

Cassandra warns, and then defends itself:

tombstone_warn_threshold: 1000
tombstone_failure_threshold: 100000

WARN  Read 10 live rows and 98234 tombstone cells for query
      SELECT * FROM ks.job_queue WHERE queue_id = ? LIMIT 100
      (see tombstone_warn_threshold)

ERROR Scanned over 100000 tombstones during query; query aborted

That ERROR is Cassandra refusing to let one query take the node down with an out-of-memory failure. It is a symptom, and raising the threshold is not the fix — it just moves the crash.

# Which tables are accumulating tombstones?
nodetool tablestats my_keyspace | grep -Ei "table:|tombstone"
#   Average tombstones per slice (last five minutes): 12043.0
#   Maximum tombstones per slice (last five minutes): 98234

# Per-SSTable tombstone ratio
sstablemetadata /var/lib/cassandra/data/ks/tbl-*/nb-*-Data.db | grep -i droppable
#   Estimated droppable tombstones: 0.68

The queue anti-pattern

The single most common way to destroy a Cassandra cluster, and it is worth walking through because the failure is so counter-intuitive.

CREATE TABLE job_queue (
  queue_id text,
  job_id   timeuuid,
  payload  text,
  PRIMARY KEY ((queue_id), job_id)
);

-- worker loop
SELECT * FROM job_queue WHERE queue_id = 'default' LIMIT 10;
DELETE FROM job_queue WHERE queue_id = 'default' AND job_id = ?;

It works beautifully in testing. In production it degrades and then dies.

   hour 1     100 jobs processed  →  100 tombstones at the front of
                                     the partition
   hour 24    10,000 jobs         →  10,000 tombstones
   day 3      500,000 jobs        →  500,000 tombstones

   Every SELECT starts at the beginning of the partition —
   which is now half a million tombstones deep — and reads
   through all of them to find 10 live rows.

   day 5      queries start timing out
   day 10     gc_grace passes; some tombstones finally drop,
              but new ones arrive faster
   day 11     tombstone_failure_threshold hit; reads throw errors

Every element of Cassandra’s design conspires here: deletes write data, reads merge everything, the clustering order puts the oldest (most deleted) rows first, and the grace period keeps the evidence for ten days.

Do not build queues on Cassandra. Use a queue — Kafka, SQS, RabbitMQ, Pulsar. If you must, bucket aggressively by time, use TTLs instead of explicit deletes, and never read from the head of a long-lived partition.

Patterns that avoid tombstones

Use TTLs instead of DELETE, with TWCS. With time-window compaction (chapter 8), an entire SSTable whose data has fully expired is dropped as a whole file — no merging, no tombstone scanning, no compaction work at all. This is by far the cleanest expiry mechanism Cassandra has.

Delete whole partitions, not rows. One partition tombstone instead of a million cell tombstones.

Bucket by time and drop old buckets. Instead of deleting rows from events_by_user, partition by (user_id, month) and let old months expire by TTL.

Never write null. Use unset. Audit your ORM.

Model as immutable events. Append new rows with new timestamps and read the latest, rather than updating and deleting in place. Storage is cheap; tombstones are not.

Do not use collections for large mutable sets. Overwriting an entire non-frozen collection writes a range tombstone first:

UPDATE users SET tags = {'a','b'} WHERE id = 1;   -- tombstone + writes
UPDATE users SET tags = tags + {'c'} WHERE id = 1; -- just a write ✓

Prefer the + and - forms.

What to take from this chapter

• Highest timestamp wins, in microseconds, deterministically on every replica. That is the whole conflict model.
• Clock skew silently corrupts data. NTP is a correctness requirement. Monitor drift.
• No read-modify-write. Model immutably, or use counters, or pay for LWT.
• A delete is a write. Tombstones are what make deletion replicable.
• Writing null creates a tombstone. Use unset values. Check your ORM.
• gc_grace_seconds is 10 days, and it means repair must complete within that window or deleted data comes back as zombies.
• Tombstone-heavy partitions destroy read performance and eventually cause query failures.
• Do not build queues on Cassandra. Prefer TTL + TWCS, partition-level deletes, and immutable models.

Next: compaction — the process that eventually cleans all of this up.