Deletes and tombstones

By design, distributed databases like Astra DB Serverless handle data deletion in a way that ensures consistency and fault-tolerance across all replicas. There are few cases where data is immediately deleted. Instead, the database marks deleted records with a tombstone that is propagated to the replicas before being dropped permanently during compaction.

Immediate deletion

Data is immediately and permanently deleted when an operation removes a table because there are no rows on which to mark the tombstones. Such operations include deleting keyspaces and dropping collections and tables. Use caution when running these commands because the data cannot be recovered except by restoring from a backup.

Tombstone lifecycle

At a high level, Astra creates a tombstone when data is deleted from a keyspace that has a replication factor (RF) greater than 1. For Astra, all keyspaces have a RF of 3. However, deletion doesn’t exclusively occur through DELETE commands; there are many operations that generate tombstones. For example:

Using the CQL DELETE command.
Expiring data with time-to-live (TTL).
INSERT or UPDATE operations with a null value.
UPDATE operations on a collection column (map, set, or list), which generate tombstones differently for frozen and non-frozen collections.

Functionally, all deletes are processed as writes of tombstones:

If the deletion targets an existing record, the database marks the record with a tombstone.
If the deletion targets a non-existing record, the database still writes a tombstone, even though there is no true record to mark for deletion.

The tombstones go through the write path, and are written to SSTables on one or more nodes. Eventually, the tombstones are dropped during compaction, which is when the record is actually removed from the database.

Grace period

To allow time for deletes to distribute to replicas, tombstones have a built-in expiration known as the grace period.

When the grace period expires, the tombstone is dropped during the next compaction, if it no longer marks any deleted data in another SSTable. If a client writes a new update to the tombstoned record during the grace period, the database overwrites the tombstone with the new record.

If a node is down when a delete occurs, the grace period allows time for the node to recover and repair before the tombstone expires.

To prevent read failure due to conflicting data between replicas, the coordinator node defaults to the most recent record (last write wins). For example, if one node has a tombstone and another node has an older value for the same record, then the reconciled record will use the tombstone.

Avoid excessive tombstones

An excessive number of tombstones in a table can negatively affect application performance and read latency. The presence of many tombstones can indicate issues with the data model or the application’s query patterns.

Zombie records and missed deletes in distributed databases

When a node receives a delete for data that it stores locally, the node marks the specified record with a tombstone, and then it attempts to propagate the tombstone to replica nodes. If a replica node is unresponsive at that time, the replica doesn’t receive the tombstone, and it retains the unflagged, pre-delete version of the record.

Once a tombstone expires, it is dropped during compaction, and the database has no memory that the record ever existed. If a tombstone is written and dropped on all other nodes before an unresponsive node recovers, then the database perceives the retained record on the recovered node as a missed write and propagates it to the rest of the cluster. Deleted records that reappear in a database are called zombies.

To prevent zombies, repair operations run regularly as part of the Astra managed service offering. You don’t need to manually attempt repair; however, you should still manage tombstones properly for performance reasons.

If a node is down when a delete occurs, and the grace period expires before the node recovers, the node misses the tombstone and reintroduces the deleted data back into the cluster.

Expiring data with TTL

In addition to INSERT, UPDATE, and DELETE operations, columns can be marked with a time-to-live (TTL). When this time limit expires, the database marks the record with a tombstone. The tombstone is propagated to other nodes and eventually cleaned up like other tombstoned records.

Tombstone types

Tombstones can be marked on different parts of a partition depending on the type of delete operation:

Partition tombstones: Deletes an entire partition
Row tombstones: Deletes an entire row
Range tombstones: Deletes a range of rows
ComplexColumn tombstones: Deletes from a collection column (map, list, set)
Cell tombstones: Deletes a specific value in one column of one row
TTL tombstones: Deletes from expired TTLs