Data Deletion System Design Interview: Discovery, Propagation, and Verification

A data deletion system design interview is difficult because one user record becomes rows, objects, search documents, caches, model features, exports, and backups. Deleting the primary database row can leave the most searchable copy intact. The design needs a discovery map, product policy, dependency-aware execution, and proof.

Google Cloud officially describes deletion across active and backup systems and cryptographic erasure. NIST SP 800-88 Rev. 2 defines media sanitization around making target-data access infeasible for a stated level of effort. These facts do not create a universal legal deadline. Retention, exceptions, and response timing remain policy and legal inputs; the workflow below is editorial system design.

For a closely related drill, use Dependency-Safe Deletion Order.

Data Deletion Interview: Quick Answer

Accept a deletion request into an immutable control ledger with subject identity, scope, policy version, authorization, and deadline. Resolve stable subject keys through a data catalog into service-specific tasks. A coordinator executes a dependency graph: revoke access, stop new processing, erase or detach active records, invalidate indexes/caches, propagate to derived stores, and register backup expiry or key destruction.

Every handler is idempotent and returns a receipt containing request, dataset, action version, counts or opaque proof, time, and verification status—never deleted content. Independent scanners or sentinel queries verify absence. The request completes only when required tasks and exceptions are accounted for.

The Core Contract

Deletion is a distributed workflow with evidence. The system must discover subject data, apply product-specific erase or detach actions, handle derived stores and backups, and verify completion without retaining the deleted payload.

Data class	Typical action	Verification	Common caveat
account profile	erase or anonymize	primary-key and search query	identity mapping aliases
user content objects	delete object and derivatives	inventory by owner/reference	shared content ownership
search/cache	invalidate and tombstone	query plus generation check	stale replica or CDN
analytics rows	delete, aggregate, or detach by policy	partition scan	weak subject keys
backups	expire set or destroy scoped key when supported	lifecycle/key receipt	restore may reintroduce data

The catalog records owner, subject-key mapping, derivatives, retention policy, handler, and verifier for each dataset.

Discover Data Before the Request Arrives

Build a data inventory from service ownership, schemas, storage metadata, event lineage, and periodic scans. Each dataset declares how a subject is identified: user ID, account ID, hashed email, device ID, object owner, or join through an identity map. Record downstream consumers so a source deletion reaches materialized views and exports.

Discovery at request time alone is unreliable because undocumented stores remain invisible. Make dataset registration part of review or deployment and compare catalog claims with observed access and storage. Unknown stores create an alert and ownership task; do not silently mark the deletion complete.

Translate Policy into a Versioned Action Plan

Authentication and authorization confirm the requester and scope. A policy engine decides erase, anonymize, detach, retain, or hold for each data class, with reason and policy version. Shared records need semantics: deleting one participant may remove their identifiers while preserving a transaction required for another account or an authorized obligation.

Freeze the plan for the request so a mid-flight policy edit does not produce an unexplained mixture. If policy changes intentionally, create a new plan version and re-evaluate outstanding tasks. Do not invent retention periods in the interview; accept them as requirements and show where they are enforced.

Propagate with Tombstones and Idempotent Tasks

First stop new writes: revoke sessions, disable pipelines, and place a subject tombstone that consumers check. Then execute service handlers using (deletion_request_id, dataset_id, action_version) as the idempotency key. A retry returns the prior receipt. Dependency edges ensure derived data is not immediately regenerated from an undeleted source.

Events carry a deletion generation. Consumers apply the highest generation and reject stale upserts. Dead-letter tasks remain visible with owner and retry schedule. Rate limits protect production, but priority and deadlines prevent a large backfill from starving individual requests.

Handle Backups and Verify Completion

Immutable backups may not support row deletion. Remove the data from active systems, prevent ordinary access, and let backup sets expire under policy; where architecture permits, destroy a narrowly scoped encryption key. Restoration procedures must reapply deletion tombstones before the restored system serves traffic.

Verification is separate from execution. Query primary keys and alternate identifiers, enumerate owned objects, search indexes, inspect cache generations, and sample derived stores. Receipts are signed or access-controlled and retained without payload. Track task completion, oldest pending request, handler failures, reappearance after restore, unowned datasets, and verification discrepancies.

Work Through a Failure Trace

Request D42 resolves one account to profile DB, object store, search, analytics, and backup tasks. A search handler times out after deleting documents; its retry returns the same receipt. A stale analytics consumer tries to recreate a row but sees deletion generation 4 and rejects the upsert. Completion waits for an independent scan and a registered backup-expiry obligation.

Data Deletion check: How is a subject mapped to every system that may hold data? Walk the trace once in event-time order, once with retries and reordering, and once after rebuilding projections from durable records. State the expected invariant after every step. If the outcome depends on message arrival order when the contract says it should not, the design is missing an identity, version, or transaction boundary. If the design intentionally permits a temporary difference, give it a watermark, maximum age, and repair owner.

Data Deletion check: Which records are erased, anonymized, detached, or retained? This trace is an interview model, not a measured production benchmark. Add a skew test concentrated on one tenant or key, a two-times-peak capacity test, and a fault injection at the acknowledgment boundary. Preserve input versions and random seeds so a failed run can be reduced and replayed.

Turn the Requirements into Verification

Write these five questions beside the diagram: How is a subject mapped to every system that may hold data? Which records are erased, anonymized, detached, or retained? How do retries and dependency order work? What does deletion mean for caches, indexes, analytics, and backups? How is completion verified without storing sensitive copies? Each question must point to a record, transition, test, and observable signal. If one can be answered only with 'the service handles it,' the contract is still incomplete.

Data Deletion check: How do retries and dependency order work? Build a deterministic fixture with five to ten timestamped inputs. Include an identical retry, a conflicting reuse of an ID, a late or stale input, a worker failure after durable work but before acknowledgment, and a rebuild of the serving projection. Expected results must be written independently of the implementation. Verify the authoritative state, the serving state through a named watermark, and every emitted correction or rejection reason.

Data Deletion check: What does deletion mean for caches, indexes, analytics, and backups? Then add property checks. Applied logical IDs remain unique; versions never move backward; reserved or consumed value obeys the topic's invariant; a rebuild through the same input boundary produces the same digest; and an unauthorized reader cannot cross its scope. Generate reordered deliveries around the boundary instead of testing only the happy sequence. A passing fixture proves these declared cases, not production throughput or every network failure.

Data Deletion check: How is completion verified without storing sensitive copies? For fault testing, stop a worker immediately before and after its commit, duplicate queue delivery, delay one partition, and make the read projection unavailable. The runbook should say whether intake pauses, work accumulates durably, readers serve a last-known-good generation, or the request fails closed. Record the recovery point and compare the rebuilt digest before switching traffic. This is concrete evidence that the recovery story matches the write contract.

Capacity, Operations, and Recovery

Data Deletion check: How is a subject mapped to every system that may hold data? Estimate the durable write rate, average and peak payload, partition skew, retention volume, read or query shape, and acceptable lag. Convert those assumptions into partitions, worker concurrency, storage tiers, and backpressure. Numbers are sizing inputs, not universal facts. Say which limit fails first and what the user sees when it does.

Data Deletion check: Which records are erased, anonymized, detached, or retained? Operate from contract metrics: accepted-versus-applied counts, duplicate/conflict rate, oldest pending work, authoritative-versus-serving divergence, retry exhaustion, and p95/p99 latency. Alert on sustained error-budget consumption and correctness gaps rather than raw traffic. Keep a runbook that can pause intake or rollout, drain work, rebuild a named projection through watermark W, verify a checksum, and switch readers to the new generation.

Data Deletion check: How do retries and dependency order work? Use least privilege between producers, workers, control plane, data plane, and investigators. Encrypt transit and storage, rotate credentials, audit high-risk actions, and avoid placing secrets or unnecessary personal data in operational logs. Security controls support the data contract; they do not replace idempotency or verification.

Misleading Answers and Better Follow-Ups

Data Deletion check: What does deletion mean for caches, indexes, analytics, and backups? A weak answer names Kafka, Redis, and a database before defining truth. Another says “exactly once” without identifying the idempotency key, persistence boundary, or replay behavior. A third adds a cache but cannot explain invalidation or rebuild. Replace each slogan with one invariant, one linearization point, and one counterexample.

Data Deletion check: How is completion verified without storing sensitive copies? Ask the interviewer to change a requirement: permit temporary staleness, add multiple regions, require a correction after finalization, or remove a dependency. Explain which state transition, key, and monitor changes. That is more useful than redrawing the same boxes at a larger scale.

Data Deletion check: How is a subject mapped to every system that may hold data? Separate three evidence classes in the answer. Official documentation supports the cited product or protocol behavior. The proposed architecture, thresholds, and sequencing are inference from the stated requirements. This prevents a sensible design choice from being presented as an external fact.

A 45-Minute Interview Plan

Spend the first five minutes clarifying actors, scale, correctness, retention, and failure expectations. Use the next eight to define the authoritative records, IDs, versions, and invariants. Draw the write path and its acknowledgment boundary for ten minutes, then the read or serving path for five.

Use ten minutes for the title-specific failure trace, including one retry, one stale or late event, and one recovery. Reserve the final seven minutes for sizing, skew, access control, monitors, and trade-offs. Keep a short list of assumptions visible. When the interviewer changes one, update the affected contract before changing components.

End with the source of truth, the permitted temporary inconsistency, and the repair procedure. A compact design that can be replayed and verified is stronger than a large architecture with undefined states.

Final Takeaway

For a data deletion system design interview, lead with this thesis: Deletion is a distributed workflow with evidence. The system must discover subject data, apply product-specific erase or detach actions, handle derived stores and backups, and verify completion without retaining the deleted payload. Define the evidence boundary, run a concrete race or failure trace, and show how the system detects and repairs divergence.

Sources and Further Reading

• Google Cloud data deletion process
• NIST SP 800-88 Rev. 2
• NIST Privacy Framework

Official sources support only the cited mechanism. Architecture recommendations, capacity figures, and interview sequencing are editorial inference.