Tombstone (database)
A marker indicating that a key has been deleted, instead of physically removing the data right away. Necessary in append-only and distributed systems so the deletion can propagate correctly before the old data is finally cleaned up.
Why: in an LSM tree you can't "remove" from an immutable SSTable — instead you write a tombstone that overshadows the old value on read. In distributed systems (Cassandra) the tombstone must also be replicated to all nodes before the data may be removed, otherwise a node that missed the deletion could "resurrect" the dead data (a zombie). That's why there's a grace period (gc_grace_seconds) before compaction clears away both data and tombstone. Problem: too many tombstones (e.g. in queue-like workloads) slow down reads dramatically — a classic Cassandra pitfall. Related to compaction and anti-entropy.