A tombstone is a deleted record in a replica of a distributed data store. The tombstone is necessary, as distributed data stores use eventual consistency, where only a subset of nodes where the data is stored must respond before an operation is considered to be successful.
Contents
Motivation
If information is deleted in an eventually-consistent distributed data store, the "eventual" part of the eventual consistency causes the information to ooze through the node structure, where some nodes may be unavailable at time of deletion. But a feature of eventual consistency causes a problem in case of deletion, as a node that was unavailable at that time will try to "update" the other nodes that no longer have the deleted entry, assuming that they have missed an insert of information. Therefore, instead of deleting the information, the distributed data store makes out of the information to be deleted a tombstone, which does not appear anymore to the user.
Removal of tombstones
In order not to fill the data store with trash information, there is a policy to remove tombstones completely. For this, the system checks the age of the tombstone and will remove it after a prescribed time has elapsed. In Apache Cassandra, this elapsed time is set with the GCGraceSeconds parameter.
Consequences
Because of the delayed removal, the deleted information will appear as empty, after the content of some columns of a number of records has been deleted. After a compaction, the unused columns will be removed from these records.