Thread by @LeaKissner

It's time to kick off an entire session about data deletion at #PEPR21 (It's hard!) with "Deletion Framework: How Facebook Upholds its Commitments Towards Data Deletion" from Benoît Reitz, Facebook

That's right, come one come all, this is @Facebook' data deletion framework.

We can't expect people to write their own data deletion logic.
* They often don't know how to do it well and write bugs
* The deletion logic and data definition may drift apart over time

So we get annotations that people put on their storage

Annotations example. There are multiple different types of edges, like "deep" saying when a post is deleted, the comments should also be deleted.

If it's a "shallow" edge, it should delete the association but not the object (e.g. a post is deleted but not the whole user)

We take the annotations and generate code
* Deletion code written by storage team
* Other deletion logic is entirely around following edges and telling storage to delete

How do we walk the graph to delete?
* DFS
* we need to be re-entrant (can restart if something crashes so we don't lose data)
* consistent

[ There are many diagrams here showing what happens in the persistent stack and the logs as the deletion actions happen see the video. ]

[ It's very fancy ]

[ But I also spilled tea on my keyboard ]

Scheduling deletions in the future
* enable ephemerality -- e.g. "stories should go away in N hours" or "when you delete your account it should be hard-deleted in 30 days" or "financial data should go away in N years"
* supports custom TTL logic
* processes 160B events/day

[ Diagram showing how these move through the system, including retries]

Scheduling
* deletions run in two phases: sync (synchronously in the web request) and async (offline)
* sync is used to hide the rest of the subgraph quickly. Async does the full cleanup more slowly

For example, sync delete the post. The comments say "you can read the comments if you can read the post". Post is gone, so no one can read the comments.

Can't delete everything sync because it's too much, can't guarantee. [ retries are a thing! And backups! ]

Eventual completion
* deletions encounter infra issues
* also bugs
* might get dropped by dependencies
* or halfway through scheduling
etc.

So completion of deletions is monitored [I left a question about monitoring of data store directly]

If there's an issue you can get orphaned data, need to clean that up retroactively. How: object re-deletion. Look for edges that come from objects that don't exist any more and try deleting again.

Restoration: we log restoration logs before any delete we issue. Just in case there's a bug somewhere in the deletion system, you can fix it.

Graph indexed, different from the data store backups, can restore just a subgraph. Encrypt the backups with a key and throw away the key.

Preventing data loss
* static analysis on the deletion graph
* dynamic checks based on deletion constraints
* predictions on the edges' deletion behaviours

Happy path: measure that reliability
Measure how much goes through the gaps
Then measure the reliability of the safety net

Bonus points for an orthogonal way to measure success and a second safety net

Conclusion
* Deletion is a hard problem
* The happy path isn't enough. You need safety nets for the failures.
* We need to make it easier for developers to do the right thing than the wrong things.

Q: This relies on a graph structure to work. What happens when FB acquires a company whose data isn't a graph?
A: Slowly push them to move towards our system and build the integration so we can ship deletion to them.

In the meantime we have a verification framework for everything which isn't covered by our deletion framework.

Q: How long does this deletion system take to run?
A: As of last week, 60% within one day of the scheduled deletion, 4 9s by 14 days [99.99%] (but we have 90 days)

Q: How about data to train ML models? What if it's in a slightly different shape somewhere else?
A: Train them often so you don't have to keep copies of data around, but I'm not the expert on this.