GDPR right-to-erasure when your data is replicated and embedded

A user clicks delete my account. Forty seconds later their row is gone from the primary. The DPO signs the ticket. Eleven months later a vendor audit pulls a backup, replays it into a sandbox, and the deleted user’s chat history shows up in a similarity search against an embedding index that nobody remembered to rebuild. The audit goes from clean to findings-with-fine-exposure on a single query.

GDPR Article 17 sounds like a DELETE FROM users WHERE id = ?. In a system with replicas, derived embeddings, time-travel backups, and a WAL the regulator can subpoena, it is not. This is the operator playbook for what RedDB does for you, what it does not, and the holes you have to close by hand.

The four places PII hides after `DELETE`

Before discussing tooling, name the surfaces. Every system has them; most teams have only enumerated two:

Live row — the obvious one. DELETE removes it from the table.
Replicas and read followers — async replication eventually catches up. The window is usually seconds, but during a partition it can be minutes.
Derived data — anything computed from the row that wasn’t itself the row. Embeddings are the headline case. Materialised views, denormalised search indexes, ML feature stores, downstream warehouses, cached snapshots in your CDN — all of these.
Time-travel artefacts — backups, WAL segments retained for PITR, snapshot exports shipped to a DR region. These are intended to survive deletes. That is exactly the problem.

Regulators have caught up to (3). The 2024 EDPB opinion on AI training data, the Hamburg DPA’s 2025 ruling on embedding personalisation, and the French CNIL’s guidance on vector stores all say the same thing in different words: a vector derived from personal data is personal data. You cannot point at an opaque float array and call it anonymous. If the vector lets you identify the subject through similarity search, it counts.

This is why your erasure workflow now has to traverse the derived layer, not just the source.

What RedDB does automatically

In order of how confident you should be:

Hard DELETE on the live row. The row is gone from the table. Foreign-keyed children with ON DELETE CASCADE are gone too. This is table-stakes and works.
Replication propagates the delete. Logical replication carries the tombstone to followers within the standard lag window. The replication_lag_bytes metric (see the self-host checklist) tells you when to wait. There is no separate replica-erasure command; the same WAL record that deletes on the leader deletes on the follower.
Cascading delete of embedding columns. This is the payoff for keeping the embedding on the row instead of in a second store. When the row goes, the vector goes — atomically, in the same transaction. There is no eventual job, no queue, no drift window. Compare with the multi-store shape, where you delete from Postgres and then have to remember to delete from Pinecone or Qdrant, and where a botched second call leaves the embedding behind.
Background compaction of the on-disk tombstone. The LSM compactor (see compaction notes) eventually rewrites SSTables and the deleted bytes stop existing on disk. Typical worst-case 24–48 hours under steady write load; faster under explicit reddbctl compact --tombstones.

That’s the floor. Most teams stop here, ship a “we are GDPR-compliant” page, and find out about the rest during an audit.

What still needs an operator runbook

The three surfaces RedDB does not erase automatically:

Surface 1 — Backups and WAL segments retained for PITR

Your backup policy probably retains daily snapshots for 30 days and WAL for 35 (the numbers from the DR post). For 35 days after the user clicks delete, the previous state — including their PII — is sitting in object storage.

Three strategies, in order of how regulators actually treat them:

(a) Wait it out — “deletion by expiry.” Most DPAs accept that a backup taken before the erasure request, retained for a documented and justified retention period, will eventually rotate out. You document: “user deleted at T; backups expire at T+30d; full erasure complete at T+35d.” The audit looks for the policy and the expiry receipt, not real-time scrubbing.

This is the easy answer, but only if your retention is short and bounded. If you keep yearly backups “for accounting” you are signing yourself up for surface 1 problems forever.

(b) Crypto-shredding. This is why the per-row encryption and BYOK/KMS work matters. If every tenant — or every user, if you go that far — has a distinct DEK wrapped by a CMK, deleting the CMK makes every backup of their data ciphertext-only forever. You do not need to rewrite the backups; the key to read them no longer exists.

The operator command for this looks like:

# Schedule the per-tenant CMK for deletion in your KMS.
# Use the longest pending-window your KMS allows so accidental
# triggers are recoverable, but make the window expiry mechanical.
aws kms schedule-key-deletion \
  --key-id "$TENANT_CMK_ARN" \
  --pending-window-in-days 7

# Record the scheduled deletion against the erasure ticket.
reddbctl audit log \
  --event "erasure.crypto-shred.scheduled" \
  --tenant "$TENANT_ID" \
  --cmk "$TENANT_CMK_ARN" \
  --completion-at "$(date -d '+7 days' --iso-8601)"

Crypto-shredding is the only approach that handles backups and WAL segments and DR replicas in one operation. It is also the one regulators have started naming approvingly in guidance (CNIL 2024, ICO 2025). Cost: you must have built per-subject DEK separation up-front. Retrofitting it is months of work.

(c) Backup rewrite. Restore each backup, run the delete, re-snapshot, encrypt, ship to the same object-store path. Possible. Slow. Expensive. Most teams who try this once switch to (b).

Surface 2 — Derived embeddings that aren’t a column on the row

The atomic-delete-via-cascade story only works if the embedding lives on the row. If you copied embeddings into:

a separate vector store (Pinecone, Qdrant, Weaviate, pgvector in a different cluster),
a feature store keyed by user_id,
a search index that retained the chunked text,
a downstream warehouse fact table,

…then DELETE FROM users does nothing to those copies. You need an explicit fan-out.

The pattern is an erasure outbox. Same row, same transaction:

BEGIN;

DELETE FROM users WHERE id = $1;

INSERT INTO erasure_outbox (subject_id, surfaces, requested_at)
VALUES (
  $1,
  ARRAY['vector_store_v2', 'feature_store', 'warehouse_pii_dim', 'cdn_cache'],
  now()
);

COMMIT;

A worker drains the outbox and issues the surface-specific delete to each downstream system. The outbox row is only removed once each surface has confirmed (or returned 404, which counts). The DPO dashboard joins erasure_outbox against the ticketing system: any subject older than the legally-binding deadline (30 days in the EU, 45 in California, less under many sectoral rules) and not fully fanned-out is the on-call’s problem.

The transaction guarantees you cannot delete the live row without enqueueing the downstream sweep. The opposite mistake — sweeping downstream and forgetting to delete locally — is impossible because the delete and the enqueue are in the same WAL record.

Surface 3 — Embeddings as PII even when the row is gone

This is the surface most teams discover during their first regulator inquiry. You followed the cascade pattern, the embedding column went with the row, you can prove it. Then the auditor asks: “what about the embedding’s position in the index? You have an HNSW graph. Nearest-neighbour queries against the index still return useful information about the deleted subject for some hours until compaction rebuilds the graph.”

HNSW graphs are an interesting case. Deleting a vector marks the node as soft-deleted; queries skip it; but the graph topology — the links — were chosen partly because of that vector’s position. The information leakage from this is microscopic and academic. Regulators have not asked about it in any case we’ve heard of. But it is the kind of thing a determined auditor will raise, so:

The reddbctl index rebuild --tombstone-aware vec_index_users command (current RedDB) fully reconstructs the graph from live vectors. Run it monthly or after any bulk erasure event.
Document the rebuild cadence in your DPIA so it does not become a finding.

A complete erasure runbook

Stitching it together, this is what a production erasure looks like end-to-end:

-- T+0: subject requests erasure via support portal.
-- Ticket system writes a row to erasure_requests with a 30-day SLA.

BEGIN;

-- 1. Hard delete from primary, cascading to chunks + embedding column.
DELETE FROM users WHERE id = $subject_id;

-- 2. Enqueue downstream fan-out. Same transaction = no drift.
INSERT INTO erasure_outbox (subject_id, surfaces, requested_at)
VALUES ($subject_id, ARRAY['vector_store_external', 'warehouse', 'cdn'], now());

-- 3. Audit log entry that satisfies Article 30 record-keeping.
INSERT INTO audit_log (event, subject_id, actor, at)
VALUES ('erasure.requested', $subject_id, $support_agent_id, now());

COMMIT;

# T+seconds: replication catches up. Watch the metric.
reddbctl metric replication_lag_bytes --threshold 0 --wait 60s

# T+minutes: outbox worker fans out.
# Each surface's DELETE is idempotent; 404 is success.
# Outbox row removed only when every surface returns success.

# T+24-48h: LSM compaction rewrites SSTables, on-disk bytes gone.
reddbctl compact --tombstones --table users  # optional acceleration

# T+7d: crypto-shred CMK if per-subject keys.
aws kms schedule-key-deletion --key-id "$SUBJECT_CMK" --pending-window-in-days 7

# T+30d: snapshot retention boundary. Last snapshot containing the
# subject expires. Erasure complete by policy.

# T+monthly: HNSW graph rebuild absorbs any soft-deleted vectors.
reddbctl index rebuild --tombstone-aware vec_index_users

The DPO sees a single dashboard: erasure ticket id, T+0, current surface status, completion ETA against the 30-day legal deadline.

What’s automatic vs. operator-driven (the cheat sheet)

Surface	RedDB does	You have to do
Live row	`DELETE` cascades to children and embedding column	—
Replicas / followers	Tombstone replicated via WAL	Verify `replication_lag_bytes` returns to 0 before closing ticket
On-disk tombstone	Compaction reclaims bytes on standard schedule	(Optional) `reddbctl compact --tombstones` to accelerate
Backups (snapshot)	Expire on retention schedule	Document policy; consider crypto-shredding for tighter SLA
WAL retained for PITR	Expires with the segment	Crypto-shred for sub-retention-window deletion
External vector store	—	Fan out via `erasure_outbox`
Warehouse / feature store	—	Fan out via `erasure_outbox`
HNSW graph topology	Soft-deletes from query results	Monthly rebuild with `--tombstone-aware`
Audit log of the erasure itself	Append-only event	Keep this — Article 30 requires it

The right way to read this table: anything in the “you have to do” column is the audit-finding column if you forget it. None of it is hard. All of it is operationally invisible to anyone who hasn’t asked.

Three things that aren’t in scope (yet)

Honesty matters. RedDB does not currently:

Surface a single reddbctl erase --subject ... command that drives the whole pipeline. That’s a roadmap item — the integration points are too tenant-specific (which downstream surfaces, which KMS, which ticketing system) to ship a default that doesn’t lie. For now, the runbook above is the contract.
Encrypt the audit log itself per subject. The audit row stating we erased subject X at time T is itself technically PII. Most DPAs accept this under Article 17(3)(b)/(e) (compliance with legal obligation and defence of legal claims). We aren’t applying crypto-shredding to the audit log; you shouldn’t either.
Sync the rebuild across regions atomically. If you maintain HNSW indexes in two regions, the rebuild runs region-by-region. The leakage window between regions is on the order of the rebuild duration (minutes to hours). Document it.

When to start

The fastest way to fall behind on Article 17 is to leave it for the audit. Ten engineering hours now — schema for the outbox, a worker, a dashboard, a runbook — costs less than ten hours of legal time after a single inquiry, even before any potential penalty.

The harder change — per-subject DEKs so that crypto-shredding is on the table — is months of work and only worth it if you sell to buyers who will ask. If you do not yet have those buyers, the policy-expiry approach (a) above is enough. The day a regulated buyer says we need crypto-shred, you start. Not before.

The one thing everyone should do today: write the outbox table and the fan-out worker. Cascading the embedding column on DELETE is the cheapest piece of Article 17 alignment you will ever buy, and most teams already structured their schema to support it without realising they were halfway there.

TL;DR

Article 17 is no longer just DELETE FROM users. Embeddings derived from PII are PII.
Keeping the embedding on the row turns the hardest erasure surface into a CASCADE.
Replicas erase by WAL; on-disk bytes by compaction; backups by retention or crypto-shred.
External surfaces (vector stores, warehouses, feature stores) need an erasure outbox driven in the same transaction as the delete.
HNSW graph topology is a tiny leakage surface; monthly tombstone-aware rebuild closes it.
Crypto-shredding via per-tenant or per-subject CMKs is the only single-step approach for backups and WAL. It only works if you architected for it.
The audit log of the erasure itself is allowed to persist under Article 17(3).

The four places PII hides after DELETE