A tombstone is a stored deletion marker. In ScyllaDB, deleting data does not immediately erase its on-disk representation; the delete writes a tombstone that says the value was deleted. Tombstones can represent deletion of one column value, a whole row, or an entire partition. section 6.2.2 section 6.6
This marker solves an important distributed-data ambiguity: a missing value might never have been written, or it might have been deleted. By preserving that distinction, ScyllaDB can reconcile replicas correctly and propagate a missed deletion rather than restoring old data. section 6.2.2
Deleting an article title
An article can remain present while one of its cells is deleted. After inserting an article with a title, DELETE title FROM articles WHERE id = ... removes the title from query results but leaves the row and its id. The deletion is represented internally by a tombstone rather than immediate physical removal. section 6.2.1 section 6.2.2
Figure 6.4 By writing a tombstone on deletes, Scylla is able to reconcile a missed delete and ensure that deleted data is deleted.
This diagram shows why a deletion marker gives replicas the context needed to reconcile a missed delete. section 6.2.2
Tombstones remain long enough for replicas to learn about the deletion. Writes first enter a memtable and commit log, then are flushed into immutable SSTables. Because old values can remain in SSTables, compaction later merges files, keeps the newest relevant data, and can discard eligible tombstones. section 6.2.2 section 6.2.3
Tombstone cleanup requires two safeguards:
- Wait for gc_grace_seconds before garbage-collecting the tombstone; removing it too early can leave a replica with old data and no deletion marker. section 6.2.3
- Run repair within that grace period so tombstones are synchronized across nodes; otherwise old data can reappear through data resurrection. section 6.2.3 section 6.6
Keeping tombstones too long consumes unnecessary storage, while removing them too soon risks inconsistency. The grace period is therefore a practical trade-off between allowing deletion information to reach all nodes and reclaiming space through compaction. section 6.2.3
