You deleted the key. Then it came back.

transcript

You deleted a key. The store said OK. Later, a read returns it. The deleted value is back.

Every key lives on three replicas. A, B and C. A delete isn't an erase. It writes a tombstone: a marker that says deleted. A and B get it. Quorum met. The delete succeeds. But C was down. It still holds the old value.

Tombstones pile up, so compaction drops old ones. Now A and B hold nothing. No value. No marker saying deleted.

C comes back online, still holding the old value. Repair compares replicas. C has a value. A and B have nothing. Nothing says deleted anymore. So repair copies the value back. Your deleted value is alive again. On every replica.

The fix is about time. A delete writes a tombstone, as before. Keep it longer than the longest expected outage. Every replica sees it. Only then let compaction drop it.

In a replicated store, a delete is just another write. And the tombstone must outlive the longest outage.

Full breakdown in the lecture.