In a replicated wide-column store whose replicas repair each other, why must a delete outlive replica repair, and what happens if its tombstone is purged too early?

## The setting This problem belongs to stores where **several replicas each hold a copy** of the data and **repair** them against each other — comparing what each replica holds and copying whatever is newest to the replicas missing it. The mechanics of that repair (anti-entropy trees, read repair, stored hints for down nodes) are a subject of their own. Here the question is how deletes survive it. ## Why tombstones must be kept at all A delete is recorded as a **tombstone** with a timestamp. During repair: - replica A has the **row** (it missed the delete); - replicas B and C have the **tombstone**, newer than the row. Repair sees a newer tombstone and spreads it to A. The delete wins. This works **only because the tombstone still exists** on B and C. ## How resurrection happens Now suppose B and C have **purged** the tombstone during compaction before A was repaired: 1. A still holds the row. 2. B and C hold nothing for that key — neither row nor tombstone. 3. Repair sees data on A and **absence** on B and C. Absence is indistinguishable from "never received it". 4. Repair copies the row from A to B and C. 5. The deleted row is **back** on every replica. The same happens if a replica stays offline longer than the tombstone lifetime and then rejoins. ## The rule: a delete must outlive repair Stores in this model keep tombstones for a configurable **grace period** before compaction may purge them. Safety requires: | condition | why | |---|---| | grace period longer than the maximum interval between successful full repairs | every replica sees the tombstone before it can vanish | | repair actually completes on schedule | a failing repair job silently breaks the guarantee | | a replica down longer than the grace period is rebuilt, not rejoined | its stale data would otherwise be treated as live | | hints or queued writes older than the grace period must be discarded, not replayed | replaying them could reintroduce old data | ## The trade-off in the grace period - **Longer** grace: safer against slow repairs and long outages, but tombstones pile up, costing disk and read time. - **Shorter** grace: less tombstone overhead, but repair must run more often and more reliably. Tables that never delete explicitly and only age data out through one uniform time-to-live sometimes use a shorter grace period — a decision to make deliberately. ## Why the other model does not face this within a cluster In stores where **each key range is served by one server** and redundancy comes from a replicated storage layer beneath it, there is no peer reconciliation of rows inside the cluster: one server applies every delete. Once a major compaction has rewritten a range's files, no older data for it remains, so delete markers can be dropped then. Cross-cluster copies, where used, receive the delete as a replicated mutation. ## Interview angle Tell the story of the missed delete step by step, state the rule — tombstones must outlive the repair cycle — and name the operational duties it creates: repair on schedule, rebuild long-absent replicas.