Tombstone
A marker recording that a record was deleted, so the deletion propagates through queues, replicas and indexes instead of the record silently reappearing.
In a distributed system you cannot always delete something everywhere at once. A tombstone is a small note saying 'this item was deleted at this time'. It travels through the pipeline like any other change, so every copy, cache and search index learns to drop the item.
Without tombstones, a deleted document can come back from an old copy and keep showing up in AI answers.
Putting a 'withdrawn' slip in a library card catalogue rather than just pulling the book, so branch libraries know to remove their copies too.
Assuming a delete API call means the data is gone. Vector stores often soft-delete; caches, replicas and backups still hold the content until compaction, TTL or a restore procedure deals with them.
Tombstones appear at several layers. In Kafka, a record with a key and null value on a compacted topic tells consumers and compaction to delete that key; it stays for delete.retention.ms (24 h default) so slow consumers still see it. In Cassandra and LSM stores, tombstones shadow older values until compaction purges them. In vector indexes, deletes are usually soft: HNSW graphs mark nodes deleted and skip them at query time, Lucene-based engines mark docs in a live-docs bitmap until segment merge, Qdrant flags points and its vacuum optimizer rebuilds segments past a deleted-ratio threshold, and pgvector leaves dead tuples until VACUUM.
In a RAG pipeline: the source delete becomes an event, the Document registry marks the document deleted with a timestamp and its chunk ids, the index deletes those ids, and the Semantic cache invalidates answers that cited them. Soft-deleted vectors still cost RAM and degrade graph quality until Compaction & soft delete. For legal erasure (GDPR Art. 17, one month to respond), you need proof that every copy, including backups' restore path, honours the deletion.
Deletes as events (Kafka tombstones or explicit op: d), registry deleted_at + chunk ids, delete by id (never by fuzzy filter), purge semantic-cache entries by cited doc id, nightly orphan reconciliation, compaction/vacuum on a deleted-ratio threshold, and a restore runbook that replays registry deletions before serving.
Legal matter workspace, a client invokes erasure for 2,300 documents. Events flow: DMS delete → tombstones on docs topic → registry marks deleted_at and lists 31k chunk ids → Qdrant deletes the points (soft) → semantic cache entries citing those ids are purged → nightly reconciliation confirms zero remaining ids. Qdrant's vacuum rebuilds the segment once deleted points pass its threshold, removing them physically. The erasure report lists each document, chunk count and deletion timestamp, plus the backup restore procedure that replays the registry's deletions.
Trace a delete end to end: "Source delete → tombstone event → registry deleted_at with chunk ids → index delete → cache invalidation → reconciliation check. Index deletes are soft, so I watch the deleted ratio and compaction. For erasure I make restores replay deletions." Expect: "what happens if you restore last week's backup?" Deleted docs come back unless restore is followed by replaying registry deletions.
Numbers worth knowing
- Kafka tombstone retention
- delete.retention.ms = 24 h defaultcompacted topics; raise if consumers can lag longer
- GDPR erasure response window
- one month (extendable by two)GDPR Art. 12(3)
- Vector-index deleted ratio before compaction
- ~10–20%typical vacuum thresholds (e.g. Qdrant default 0.2)
How to decide
| When | Do this |
|---|---|
| Consumers can be offline longer than 24 h | Raise delete.retention.ms above the max outage, or tombstones are compacted away unseen. |
| Deleted ratio in the index passes ~20% | Trigger compaction or rebuild; recall and RAM suffer. |
| Legal erasure applies | Registry proof per chunk, cache purge, and restore-replay procedure. |
Cost maths
Soft-deleted vectors cost RAM until compacted: 20% deleted in a 60 GB index = 12 GB wasted ≈ $60/month at ~$5/GB-month (illustrative). The bigger cost is the incident: an erasure failure under GDPR can draw fines of up to 4% of global annual turnover (Art. 83).
Operating it
- Deleted ratio above 15% on any shard: schedule compaction
- Orphan chunks found by reconciliation: fix the delete path
- Erasure requests above ~100/month: automate the erasure report from the registry
- Orphan chunks (index ids with no active registry row): alert on any non-zero
- Deleted ratio per index segment/shard: alert above 15%
- Tombstone consumer lag vs delete.retention.ms: alert at 50% of retention
When it goes wrong
Two months after a firm offboarded a client and deleted their files, the research assistant quoted one of that client's memos.
A lawyer recognised the memo; an audit query found 4,800 chunks with no active registry row.
The vector cluster had been restored from a pre-deletion snapshot during an upgrade; nothing replayed deletions after restore.
Restore runbook now deletes every chunk not active in the registry before traffic; reconciliation pages on any orphan; the semantic cache was flushed.
Related terms
Sources
- Apache Kafka documentation (log compaction) — Apache Software Foundation, 2025docs
- Efficient and robust approximate nearest neighbor search using HNSW graphs — Malkov & Yashunin, 2016paper
- Debezium documentation — Debezium, 2025docs
Check yourself
Three questions. Every option is explained once you answer.