Course contentsShow
← Computer Science
Lesson 1731 of 2,87239. NoSQL and Modern DatabasesFree lesson

DELETE and Tombstones

How key deletion works in distributed systems using tombstone markers and eventual cleanup.

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

  1. Client issues DELETE("user:123")
  2. System writes a tombstone for user:123 with a timestamp
  3. Tombstone propagates to replicas
  4. GET("user:123") now returns "not found" because the tombstone indicates deletion
  5. 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.