DELETE and Tombstones
What you'll learn: How distributed key-value stores handle deletion without immediately removing data, using special markers called tombstones.
The Problem with Distributed Deletion
In a distributed key-value store, data is often replicated across multiple nodes for fault tolerance. When you delete a key on one node, how do other nodes learn about it? You can't just remove the data immediately—if another node was temporarily offline, it might still have the old value and could re-propagate it later, causing the "deleted" data to reappear like a zombie!
What Are Tombstones?
A tombstone is a special marker that says "this key was deleted at timestamp X." Instead of erasing data on DELETE, the system writes a tombstone value. This marker then replicates to all nodes, just like a regular PUT operation would.
Think of it like a gravestone in a cemetery—it marks where something once existed but is no longer alive. The actual data might still physically exist on disk temporarily, but the tombstone tells everyone "treat this as deleted."
How It Works
- Client issues
DELETE("user:123") - System writes a tombstone for
user:123with a timestamp - Tombstone propagates to replicas
GET("user:123")now returns "not found" because the tombstone indicates deletion- Later, a background compaction process physically removes both the tombstone and old data
This ensures all nodes eventually agree on deletion—even those that were temporarily unavailable.
Key Takeaway: Distributed key-value stores use tombstone markers to safely propagate deletions across replicas, with eventual physical cleanup through compaction processes.