Model a deletion graph, but don't execute it
Modeling deletion as a dependency graph sounds good in theory: identify which systems are upstream of others and determine the order in which to delete customer data.
Trying to enforce that ordering in real-world workflows quickly becomes a nightmare. It adds unnecessary complexity and creates points of failure throughout the dependency graph.
However, mapping the graph is still useful: it exposes failure modes, highlights where deletion-aware access controls are required, and helps prioritize next steps for your deletion program.
The naive solution
Imagine a system where customer personal data flows through several services.
Customer Accounts shares personal data with Ordering and Notifications. Ordering also passes personal data to Search and Notifications, while Analytics consumes data from Ordering, Search, and Notifications.
When a customer asks us to delete their data, what order should be followed for deletion?
We could follow the flow of data:
- Delete the Customer Account
- Then delete from Ordering
- Then delete from Search and Notifications
- Finally from Analytics after all its upstreams have deleted the customer.
It sounds reasonable, and it stops personal data from flowing back into downstream systems after they’ve fulfilled the deletion requests.
But there’s an important assumption hiding here: data-flow dependencies aren’t deletion-order dependencies. Sometimes they share direction; sometimes deletion must run opposite to the data flow.
Analytics consumes data from multiple upstream systems, but does it actually have to wait for all of them to finish deleting before it can start? The graph shows the relationships exist, but doesn’t show which ones require ordering.
And even if we knew, enforcing the order across a live graph runs into two problems: keeping the graph accurate, and keeping one failure from blocking everything else.
The graph is never stable
The first problem with making the graph part of the deletion workflow is keeping it accurate.
In a large organization, the graph becomes stale almost as soon as you build it.
New consumers appear. Services are split apart. Data flows change. Caches and derived stores are introduced. Pipelines are rewritten.
Deprecations are particularly problematic. If a decommissioned service is still in the graph, an ordered workflow can wait indefinitely for a completion signal that will never arrive, silently blocking every downstream deletion.
Under strictly ordered execution, every dependency change must be immediately discovered and incorporated into the graph, or deletions stall.
Automation can improve completeness and freshness of the inventory, but it doesn’t eliminate the underlying problem: the inventory itself becomes another system that must be maintained, validated, and trusted.
A map that’s 90% accurate still produces a useful list of remediation work. An orchestrator that’s 90% accurate can stall every request that routes through the stale 10%. Discovery tolerates staleness; strictly ordered execution doesn’t.
One failure shouldn’t block everything else
Suppose Customer Accounts has a deletion problem. Under the naive plan, Ordering can’t start until Customer Accounts succeeds, Search can’t start until Ordering succeeds, and so on.
At scale, a single unhealthy service, queue, database, or deletion implementation becomes a bottleneck for the entire deletion process. One team’s incident turns into missed compliance deadlines, such as GDPR’s one month or CCPA’s 45 days (without valid extensions), across every downstream system, for every affected request.
A better model is to treat deletion as asynchronous. The request propagates to every system, and each does its own work. Some delete immediately. Others take longer, fail temporarily, and retry.
Deletion doesn’t need to behave like a single distributed transaction where every system commits together. Systems should make progress independently where they safely can.
When strict deletion ordering is actually required
Ordering is required when deleting in the wrong order would break an invariant: a rule the system enforces to stay consistent, such as “every order must reference an existing customer.” Two patterns come up most often.
Referential integrity
Within a single database, this is familiar: if orders reference a customer and there’s no cascading delete, the orders must be removed first.
The same pattern exists across services. Suppose Ordering holds a hard reference to each customer account, and Customer Accounts refuses to delete an account while orders still reference it. Data flows from Customer Accounts to Ordering, but deletion has to run the other way. Ordering must delete its records first, or de-identify them where retention rules require keeping order history, before the account becomes eligible for deletion. Step 1 of the naive plan would fail.
Represent this explicitly as an ordering constraint. Ordering deletes asynchronously, and the account becomes eligible for deletion once those references are gone.
The ordering exists because of the invariant, not because of the data flow.
In-flight work
A different class of ordering constraint occurs when in-flight work requires the source state to remain available while it executes.
The required sequence might be:
- Stop new jobs or orders
- Complete or cancel in-flight work
- Delete source data
Without that ordering, a queued job could execute after the source has been deleted and recreate data that was supposed to be removed, or fail because the referenced state no longer exists.
Strict ordering isn’t the only solution. A worker can sometimes be made deletion-aware and reject or discard work for data that is subject to deletion. In that case, the invariant is enforced locally rather than making the entire deletion workflow wait.
Model the constraints, enforce them locally
A graph used for orchestration should distinguish data-flow dependencies from the much smaller set that impose deletion ordering.
In the example, customer data reaches every system, but the only real constraint may be that Ordering deletes before Customer Accounts.
Every edge that does impose ordering should record why: the invariant that breaks if deletion happens in the wrong order.
When strict ordering is required, enforce it as close as possible to the system that owns the invariant. That may be cascading deletes in a database, or a service that refuses to delete a parent while dependents exist.
A central orchestrator can coordinate genuine cross-system ordering constraints, but it shouldn’t turn every dependency into a global workflow.
Enforce ordering where the invariant lives. Keep everything else asynchronous.
Prevent deleted data from coming back
Asynchronous deletion introduces race conditions, which I cover in more detail in “Deleted and back again: mitigating unintended data resurrection”.
Search deletes a customer’s data, but Ordering may not have processed the deletion yet, so it continues working normally and sends that data back to Search, which stores it again.
Strict ordering could help prevent this by making Search wait for Ordering. The more robust fix is to make Ordering deletion-aware. Once a customer is subject to deletion, Ordering can filter its exports and reject API requests for that customer. This approach also covers retries and replays, which deletion ordering alone doesn’t.
Downstream systems shouldn’t have to wait for upstream systems to delete. Upstream systems should stop sending data that’s subject to deletion.
That changes the question from “What order should these systems delete in?” to “What guarantees does each system need while deletion is in progress?”
Asynchronous doesn’t mean fire-and-forget
Once deletion is asynchronous, a request will spend time completed in some systems and pending in others. That’s expected, because systems differ in processing time, retry behavior, and availability.
But that means the program needs to distinguish deletion that’s in progress and on track for its deadline from deletion that’s stalled, failed, or unverified.
That requires every system to report on where each request stands:
- Accepted: the system received the request
- Processed: the system ran its deletion
- Verified: the organization can prove deletion or de-identification
A system that accepts a deletion request but never processes it hasn’t deleted anything. A system that processes it but can’t produce evidence leaves an auditability gap.
This distinction matters beyond engineering. A request isn’t complete until every system has reached Verified or has a documented exception, and the response to the individual shouldn’t say otherwise. Verified state is also what lets the organization demonstrate compliance, not just assert it.
Use the graph to find the work
Mapping the graph is still worthwhile, because it tells you where the work is.
If your privacy program maintains a data map or record of processing activities, you already have most of this graph. What those artifacts usually lack is what deletion depends on: which flows impose ordering, where data can flow back after deletion, which retention exceptions apply to each system, and how each system proves it deleted. Adding those fields turns a compliance inventory into a deletion remediation plan.
For each dependency, ask:
| Question | Gap it reveals | Typical fix |
|---|---|---|
| Does this dependency impose a deletion invariant? | Ordering constraints | Enforce locally where the invariant lives; otherwise model an explicit constraint |
| Can data flow after deletion begins? | Resurrection paths | Make data transfers deletion-aware and add durable deletion state |
| Can queued or in-flight work outlive the source data? | In-flight races | Drain queues, or make workers reject work for data subject to deletion |
| How do we know deletion completed? | Verification gaps | Report accepted, processed, and verified states per system |
| Who owns the dependency? | Operational gaps | Assign an owner; build shared tooling where many systems have the same gap |
| Is data shared with a processor or third party? | Recipient gaps | Propagate deletion requests to recipients and track their confirmation |
The output isn’t a graph you can hand to an orchestration team. It’s a list of prioritized engineering work. For a privacy program, that’s the real value of the graph: a structured way to find owners, invariants, verification gaps, and remediation priorities.
Distributed deletion should be asynchronous by default. Enforce ordering only where correctness requires it, as close to the invariant as possible, and make every system that receives personal data robust to deletion happening somewhere else at the same time.
Model the deletion graph. Don’t execute it.
Posts in this series
- Why data deletion is still an unsolved infrastructure problem
- Why deletion means different things in different systems
- Gaps in data deletion verification and auditability
- Deletion is not always deletion: retention exceptions and competing obligations
- Deleted and back again: mitigating unintended data resurrection
- (Current post) Model a deletion graph, but don’t execute it