tombstone

Name

tombstone — tombstone — a marker that records a deletion without performing one

Synopsis

tombstone [--grace SECONDS] [--no-compact] [--hard] KEY
delete(k) := write(k, ⊥, version_now)

Description

tombstone records the deletion of a key by writing a marker instead of freeing the storage the key occupied. The bytes remain on disk. Reads learn to step over them. Replicas receive the marker the way they receive any other write, because to this system a deletion is not a removal, it is an insertion with an unusual payload.

The marker carries the newest version and therefore outranks the value it buries. It propagates until every replica agrees the key is dead, at which point it waits out a grace period on the assumption that some node has not yet heard. Only after that, and only if compaction runs, are the bytes reclaimed. The word for a deletion that has not reclaimed anything is: normal.

The alternative — erasing the value outright — is worse. A replica that never received the delete sees an empty slot, mistakes it for the oldest version of all, and helpfully copies its own live value back. The record walks again. The tombstone exists so the absence has a version number and can win an argument.

Options

--grace SECONDS

Withhold reclamation until this many seconds pass. Defaults to longer than anyone will remember to check on it.

--no-compact

Retain the marker indefinitely. Documented as optional. Observed as the default.

--hard

Actually remove the bytes. Accepted, logged, ignored. There is no hard delete, only a marker you have decided to trust.

--forget

Erase the record and every copy of it, per legal request. Returns 0. See BUGS.

--count

Report storage reclaimed by deletions to date. Prints 0 bytes. The count has never moved.

Exit Status

0

marker written; the key is dead on this replica

0

marker written; a stale replica has not been informed and disagrees

75

compaction deferred, grace period has not elapsed (EX_TEMPFAIL)

137

the record was observed alive after deletion; it walked again

History

The deletion-marker sense is native to replicated and log-structured data stores. Apache Cassandra names them tombstones and clears them during compaction only after gc_grace_seconds, historically 864000 (ten days), a window that also throttles read performance while it lasts. Microsoft Active Directory kept deleted objects as tombstone entries governed by a tombstoneLifetime, 60 days by default and later 180. Conflict-free replicated data types such as the OR-Set retain tombstones deliberately, so that a concurrent add elsewhere cannot silently revive a removed element.

Bugs

--forget returns 0 while the value persists across three backups, two replicas, and a marker whose grace period has not elapsed. The right to erasure has been filed here since GDPR took effect.

Under sustained deletes, tombstones outnumber live rows and every read walks the graveyard before finding anything. Reported as slow. Closed as working to specification.

A marker compacted on one node and pending on another yields a record that is simultaneously deleted and present, depending on which replica answers. See heisenbug.

See Also

idempotent(3), bitrot(5), heisenbug(1). The living exhibit demonstrates the word in motion:

▸ operate tombstone

Author

Maintained by the stale replica, which never received the delete and, in a spirit of helpfulness, gossiped your record back to life. It reports zero bytes reclaimed and considers the matter settled.