The Staff Engineer Data Deletion Interview: Tombstones, Backups, and Proof

Your deletion API returns success. The profile disappears from the primary database. Then a delayed indexing job republishes it, or a disaster-recovery restore brings it back a month later. A data deletion interview becomes interesting at that boundary: what evidence lets you say the information is gone, and which copies remain outside that claim?

For senior and staff engineers, this is a useful system-design practice problem because it connects ownership, asynchronous processing, storage semantics, and recovery. Start with a concrete service that stores customer profiles, uploaded documents, and searchable extracts. Follow one deletion request through every copy. The architecture and practice rubric below are illustrative proposals, not a description of any employer's assessment criteria.

1. Define what deleted means before drawing the pipeline

Ask who can request deletion, which account or document is in scope, and whether shared resources belong to other users. Distinguish an account closure from removing one uploaded file. A request should authenticate the caller, verify their authority over the target, and resolve a stable internal identifier. An email address alone is a poor deletion key when an address can change or be reused.

Separate visibility, removal, and retained exceptions

Propose separate milestones: ordinary access is blocked; active stores and derived copies are cleared; retained recovery copies reach their approved disposition. Give each milestone its own deadline and evidence. A user-facing status such as “active copies removed; backup expiry pending” communicates a narrower, testable promise than a single completion flag. Ask the interviewer which milestone the product needs to expose.

Storage expiration does not automatically enforce that access boundary. DynamoDB's TTL documentation says expired items are typically deleted within a few days and can still be updated while awaiting deletion. Its documented query filters exclude expired items from results. For a strict access deadline, propose an explicit serving check and scheduled cleanup rather than treating the background TTL process as a precise timer.

Resolve retention exceptions with the appropriate policy owner. The UK ICO's erasure guidance describes circumstances in which erasure does not apply and separately addresses backups. That is jurisdiction-specific guidance, currently marked under review, not a universal deadline. In the design, represent an approved exception with its scope, owner, review date, and access restrictions. Do not let an engineer's storage preference silently become the retention policy.

2. Make deletion a durable workflow with a write barrier

Draw a small coordinator around an authoritative deletion record. Store a request identifier, target identifier, target generation, policy version, accepted time, and per-destination progress. A repeated request should return the existing operation or safely converge on the same result. Record acceptance durably before acknowledging it, so a coordinator crash cannot turn a successful response into forgotten work.

Stop resurrection before removing the original

For this practice design, put the target into a deleting state and persist its cleanup work in the same database transaction, using an outbox or equivalent durable handoff. All mutation paths must enforce that state at commit: uploads, imports, background processors, and administrative tools. A worker that checked the state before doing expensive work must check again when it attaches its result. Explain how that final write is serialized against deletion; a cached check leaves a race.

Assign each account incarnation a generation or use identifiers that are never recycled. Otherwise, a delayed deletion for an old account can erase a newly created account with the same key. Conversely, a delayed update for the old generation must fail when deletion has advanced the authoritative state. This is a proposed invariant: once deletion is accepted, no writer may publish new content for that generation.

Change capture can distribute removal, but its event shape matters. The Debezium PostgreSQL connector normally follows a row delete event with a same-key, null-valued tombstone for Kafka compaction. Configure and test the full path: a transformation that drops the relevant event can leave a sink unchanged. Treat the business deletion operation, the database delete event, and the compaction tombstone as distinct records with distinct purposes.

Give every destination an explicit obligation

Maintain an inventory of destinations and owners: primary tables, replicas, object versions, search documents, vector chunks, caches, exports, and external processors. Keep a durable mapping from a target to its derived identifiers, or a reliable way to enumerate them after the original is removed. Deleting that mapping too early can strand copies. A destination joins the workflow only with a defined handler, retry behavior, and verification method.

Workers can report attempted, verified, retrying, or blocked states. An unavailable destination remains pending. A genuine retention block receives an accountable exception rather than endless retries. Limit concurrency per store, preserve retryable work, and reserve capacity for the foreground service. These choices make deletion operate as a maintained product capability instead of an occasional script.

3. Trace the actual semantics of each storage system

Explain deletion using the systems in your diagram. A successful command can mean that a name is hidden, a row version is obsolete, or an asynchronous task started. None of those outcomes alone inventories every copy. The interview answer becomes stronger when you identify precisely what each acknowledgment establishes and what remains to verify.

Database rows and search documents

PostgreSQL's vacuuming documentation explains that an update or delete does not immediately remove the old row version because other transactions may still need it. Standard vacuum removes dead versions and makes space reusable; it generally does not return that space to the operating system. A row missing from a fresh query therefore establishes a different property from sanitizing storage media. Keep those claims separate in your completion criteria.

For the search sink, an asynchronous bulk task needs a verified outcome. Elasticsearch's delete-by-query API works from a starting snapshot and can encounter version conflicts when documents change. Successful earlier deletions are not rolled back after later failures. Inspect failures and conflicts, retry appropriately, and verify absence after the required search visibility boundary. Your write barrier prevents an old indexing job from recreating a document after the sweep.

Object versions and compacted logs

Amazon S3's versioned deletion documentation provides a concrete trap: a simple delete inserts a delete marker instead of permanently removing existing versions. Permanent removal targets version IDs. Your handler must account for every relevant version and any separate replicas or derivatives in its inventory. An ordinary download returning “not found” does not demonstrate that historical versions are gone.

Immutable retention changes the possible outcome. S3 Object Lock documentation states that compliance mode protects a version against deletion during its retention period, including by the account's root user. Legal holds are separate and remain until removed. Surface protected versions as retained exceptions with their governing policy. A simple delete marker must never be mistaken for evidence that a protected version was erased.

Kafka's log-compaction design explains that tombstones are themselves eventually removed and that sufficiently lagging consumers can miss them. Do not assume a stale sink will discover every deletion when it reconnects. Define a maximum recoverable lag and rebuild stale sinks from a current authoritative snapshot when necessary. Preserve the separate deletion journal for the recovery window your design actually supports.

4. Make backup restoration respect later deletions

A restore is another writer. In the proposed design, restore a backup into an isolated environment, identify its recovery point, and apply all relevant subsequent deletion records before opening access. Rebuild derived stores from the sanitized state. Keep the deletion journal available independently of the backup being restored; restoring both data and deletion history to the same old point would erase the evidence needed to prevent resurrection.

Retain that journal long enough to cover the oldest supported backup, delayed consumers, exports, and permitted replay paths. Protect its identifiers and limit its contents: a deletion record should not preserve the document body it exists to remove. Define when entries can expire and who owns that decision. An indefinite tombstone registry can itself become an unnecessary store of identifying information.

The ICO's backup discussion says that fulfilling applicable erasure requests requires steps for backups as well as live systems. Where immediate overwriting is unavailable, it discusses keeping backup data beyond use until replacement under an established schedule and being clear with individuals about what happens. Treat a restricted recovery workflow and eventual expiry as explicit, reviewed controls, not an automatic exemption for backups.

Evaluate cryptographic erasure at the right granularity

If you propose destroying encryption keys, draw the key hierarchy. A shared key may cover unrelated customers, while plaintext caches, exported data keys, or differently encrypted copies can fall outside its protection. For this design, require an inventory of those paths before accepting key destruction as sufficient evidence. The encryption boundary must match the deletion boundary you promised.

AWS KMS documentation describes a mandatory waiting period of 7–30 days for key deletion, with possible additional scheduling time, and warns that scheduling deletion might not immediately affect previously encrypted data keys. Distinguish temporary loss of KMS access from irreversible destruction. NIST SP 800-88 Rev. 2 defines sanitization in terms of making access to target data infeasible at a specified level of effort. The engineering implication is to evaluate the complete recovery path rather than equating an API status with that outcome.

5. Prove completion with observations and failure drills

Give the coordinator evidence it can reconcile: destination identity, handler version, attempt time, verified scope, result, and outstanding exception. Verify through the real serving path as well as maintenance credentials. A zero-result search cannot prove that an unknown export does not exist, so maintain the destination inventory and test its coverage when adding integrations. Keep audit receipts free of deleted payloads.

Illustrative capacity calculation: assume 100,000 requests each require six independently tracked cleanup operations. That is 600,000 operations. At a sustained aggregate capacity of 2,000 operations per second, with no new arrivals or retries, processing has a theoretical floor of 300 seconds, or five minutes. This arithmetic excludes discovery, throttling, search visibility, retention blocks, and backup expiry. Measure the oldest unfinished request and per-destination backlog to find the actual bottleneck.

Illustrative practice rubric: score each dimension from zero to two, where zero means omitted, one means named, and two means explained with a failure test. This is an author's rehearsal tool, not a validated hiring score or predictor of interview outcomes.

• Contract: can you distinguish blocked access, active removal, and recovery-copy disposition?
• Concurrency: can you reject an upload that began before deletion but finishes afterward?
• Coverage: can you find object versions and derived chunks after removing the source row?
• Recovery: can you restore an older backup without reopening deleted records?
• Evidence: can you explain why a failed destination keeps the operation pending?

Rehearse with a partner who changes one condition at a time: pause the search consumer, duplicate a request, crash the coordinator after acceptance, or restore last month's backup. Explain which invariant still holds, what evidence is missing, and who receives the unresolved work. A defensible deletion design gives every completion claim a scope, a recovery story, and an observation that could prove it wrong.