Section 9: Trust, Then Verify - Deep Dive: Proving Completeness

Executive Summary: A ledger full of green ticks proves only that 1,200 services said "done". This section covers the four ways an erasure can fail without anyone noticing: data in a service nobody registered, a service that never answers, a service that answers falsely, and data that comes back after it was deleted. Each one gets a control: discovery scanners, the escalation ladder, canary subjects with verification probes, and a 60 MB tombstone Bloom filter at every ingestion path. Lena's reco-legacy straggler shows the ladder working with days to spare, and a five-metric dashboard turns "we think it's complete" into something you can measure.

The interviewer taps the whiteboard where Lena's request reads COMPLETED. "Your ledger says done. How do you know it's true?"

Don't flinch; this is where a Staff answer separates itself. "Every service acked" is a claim about the ledger, not about the data. An erasure can fail in four ways that leave the ledger looking perfect. Here's each one and how you catch it.

Failure One: Unknown Data

The registry lists 1,200 personal-data holders out of roughly 4,000 services. Broadcasting to all 1,200 (the broadcast choice from Section 3) guarantees full coverage of the registry. It guarantees nothing about service 1,201, the one a team shipped last quarter without a privacy.yaml. The registry is necessary, but it isn't sufficient.

So I add three controls, working at different points in time:

• Discovery scanners run continuously over warehouse tables, database schemas and blob-store metadata. They classify columns and fields that look like personal data (emails, phone numbers, device IDs, our own u_ account IDs) and flag any store whose owning service isn't registered.
• A launch gate in design review: a new service that stores user data can't launch without a manifest.
• A CI check that flags a pull request adding a new storage dependency to a service with no privacy.yaml.

The number that matters is coverage = registered holders ÷ discovered holders. Any gap is a list of named services with owners, not a vague worry.

"Why not trust teams to register?" Because self-declaration fails exactly when it matters: in a reorg, under a launch deadline, in an acquisition. Meta took this further in its published deletion framework, DELF ("DELF: Safeguarding deletion correctness in Online Social Networks", USENIX Security 2020). There, developers annotate data types with deletion semantics and the system checks those annotations. Flip trigger: if our schemas carried enforced annotations like that, the scanners would drop from primary detector to backstop.

Quick check before moving on: