GDPR Data Deletion in Microservices: Propagating Erasure Requests

What GDPR data deletion across microservices involves

Under GDPR's right to erasure, deleting a person's data in a microservice system is a distributed workflow, not a single DELETE statement. A user ID removed from the accounts database can still sit in a Redis cache, a search index, a nightly warehouse snapshot, application logs, a Kafka topic, and the systems of an email or payments processor. Each copy has its own storage engine, its own retention behaviour and often its own team. Erasure is only complete when every one of those copies is gone or no longer identifies the person.

This guide is for backend and platform engineers whose systems hold personal data in more than one store.

Start with a personal data inventory

You cannot delete data from a store nobody knows about. Before building any deletion machinery, map which services hold which subject identifiers. Include derived copies such as denormalized read models, embeddings, exports and aggregates keyed by user. Assign a named owner to each store, because a store without an owner will not get a deletion handler.

When this approach fits

This design applies when several services hold personal data, or when personal data is replicated asynchronously between stores. A monolith with one database and few derived copies may need far less machinery: a transaction plus cache invalidation can be enough.

How an erasure coordinator and event-driven deletion work

When many services hold personal data, one component has to own the request. The erasure coordinator is the only entry point for erasure. It verifies the requester's identity before doing anything else, because deleting the wrong person's data is itself a breach. It then writes the request to its own database with a stable request ID and the subject identifier.

In the same transaction, it writes an outbox row. A relay process publishes that row as an ErasureRequested event. The outbox ensures the request is never recorded without the event going out, and the event never goes out without a recorded request. Writing to the database and the broker separately can leave the two out of step.

Each consuming service deletes or pseudonymizes its records for that subject. It then sends back a completion message carrying the request ID, or a failure message with a reason. The coordinator tracks one status per service:

• pending: event published, no response yet
• completed: service confirmed erasure
• failed: service reported an error that needs retry or human attention
• timed out: no response within the agreed deadline, escalated rather than assumed done

The acknowledgment step is the point of the design. A fire-and-forget broadcast tells you the event was sent, not that anyone acted on it. You cannot show a regulator that a consumer which was down, misconfigured or never subscribed actually deleted anything.

The whole flow is eventually consistent. Between publication and acknowledgment, some services still hold the data. That window should be bounded by the timeout and kept as short as practical.

Copy Requester
     |
     | erasure request
     v
+-----------------------------+      +------------------------------+
| Erasure Coordinator         |      | Coordinator DB               |
| 1. verify identity          |----->| erasure_request row (req ID) |
| 2. record request + outbox  |      | outbox row (same tx)         |
| 4. track per-service status |      +--------------+---------------+
+-----------------------------+                     | 3. relay
     ^                                              v
     |                               +------------------------------+
     |                               | Message broker               |
     |                               | ErasureRequested{req ID}     |
     |                               +----+----------+----------+---+
     |                                    v          v          v
     |                               +--------+ +--------+ +--------+
     |                               | Orders | | Billing| | Search |
     |                               | delete | | pseudo | | delete |
     |                               +----+---+ +----+---+ +----+---+
     |  completed / failed + req ID       |          |          |
     +------------------------------------+----------+----------+

 Per-service status: pending -> completed | failed | timed out (escalate)
 Until every service acks, some still hold the data (eventually consistent)

The coordinator verifies identity, then records the request and an outbox row in one transaction. A relay publishes ErasureRequested, and each service acknowledges completion or failure. The coordinator tracks the status of each service.

Implementing the request log, outbox and idempotent handlers

Start with two tables owned by the coordinator. The request log, erasure_request, holds request_id (a UUID), a pseudonymous subject_ref, received_at, deadline_at and status. The per-service table, erasure_task, is keyed on (request_id, service_name) and stores state, attempts, last_attempt_at, confirmed_at and outcome_code. When a request arrives, insert the request row, one task row per registered data holder, and an outbox row carrying the event payload, all in a single transaction. A relay then publishes outbox rows to the broker. This avoids the dual-write problem: you can never record a request without also publishing it, and you can never publish an event that has no request behind it.

Delivery is at-least-once, so every consumer must be idempotent. Each service keeps a processed_erasure table keyed on request_id. The handler deletes the subject's data and inserts that key in one local transaction. On redelivery, it finds the key, skips the work and re-sends its confirmation. A lost acknowledgment then costs only a duplicate message.

The coordinator scans for tasks past their timeout and retries them with exponential backoff and jitter. After a fixed number of attempts, it moves the task to a dead-letter state and pages a human. A request closes only when every task is confirmed. A dead-lettered task keeps the request open.

For the audit trail, record IDs, timestamps, service names and outcome codes. Never record the deleted fields themselves.

Finally, run end-to-end tests against synthetic subjects seeded into every service. Assert that each store is empty, each task is confirmed, and replayed events change nothing.

Copy-- Coordinator-owned tables (PostgreSQL). subject_ref is pseudonymous: no names or emails.
CREATE TABLE erasure_request (
  request_id  uuid PRIMARY KEY,
  subject_ref text NOT NULL,
  received_at timestamptz NOT NULL DEFAULT now(),
  deadline_at timestamptz NOT NULL,
  status      text NOT NULL DEFAULT 'open' CHECK (status IN ('open', 'closed'))
);
CREATE TABLE erasure_task (
  request_id      uuid NOT NULL REFERENCES erasure_request (request_id),
  service_name    text NOT NULL,
  state           text NOT NULL DEFAULT 'pending'
                  CHECK (state IN ('pending', 'sent', 'confirmed', 'dead_letter')),
  attempts        int  NOT NULL DEFAULT 0,
  last_attempt_at timestamptz,
  confirmed_at    timestamptz,
  outcome_code    text,  -- e.g. 'DELETED', 'NO_DATA'; never the erased values
  PRIMARY KEY (request_id, service_name)
);
CREATE TABLE outbox (
  id           bigserial PRIMARY KEY,
  topic        text  NOT NULL,
  payload      jsonb NOT NULL,
  created_at   timestamptz NOT NULL DEFAULT now(),
  published_at timestamptz  -- set by the relay after the broker accepts the event
);

-- Intake: request, one task per registered data holder, and the event commit together or not at all.
-- data_holder(service_name) is the registry of services that hold personal data.
BEGIN;
INSERT INTO erasure_request (request_id, subject_ref, deadline_at)
VALUES ('3f6d2b1e-9c4a-4e7b-8a21-5d0c9e7f1a42', 'subj_8f3a', now() + interval '30 days');
INSERT INTO erasure_task (request_id, service_name)
SELECT '3f6d2b1e-9c4a-4e7b-8a21-5d0c9e7f1a42', service_name FROM data_holder;
INSERT INTO outbox (topic, payload)
VALUES ('erasure.requested', jsonb_build_object(
  'request_id', '3f6d2b1e-9c4a-4e7b-8a21-5d0c9e7f1a42', 'subject_ref', 'subj_8f3a'));
COMMIT;

This PostgreSQL example creates the coordinator's request log, per-service task table and outbox, then records an erasure request and its outbox event in one transaction to avoid dual writes.

Deletion, anonymization and legally required retention

The right to erasure is not absolute. GDPR exempts data that a controller must keep to meet a legal obligation, so an invoice that tax law requires you to retain survives the request. What changes is the purpose: the retained record may only be used for that obligation, and it must be deleted when the retention period ends. Each retained category needs a documented legal basis and an expiry date, not a vague "we might need it."

Define the outcome per field, not per service. A billing service can delete a marketing preference, pseudonymize a customer ID and keep an invoice line intact:

Hard deletes break more than foreign keys. Cascading deletes can remove rows other subjects depend on. Monthly revenue aggregates stop reconciling, and historical reports silently change when someone reruns them. Replacing identifiers with a stable pseudonym keeps the structure, and the totals, intact.

Pseudonymized data is still personal data. A pseudonymous ID joined with a retained postcode, timestamp and order value can often single out one person, especially in a small customer base. Check which retained fields can be combined across services before you assume a record is anonymous.

The privacy or legal team should approve these rules and own changes to them. Engineers implement the table but should not decide the legal basis themselves.

Copy# erasure-policy/billing-service.yaml
# Per-field erasure rules for the billing service.
# Owned by the privacy/legal team; engineers implement, they do not edit legal_basis.
service: billing
policy_version: 3
approved_by: privacy-team@example.com   # required before deploy
approved_on: 2026-09-15

fields:
  - path: customers.email
    action: delete                 # no retention basis
  - path: customers.phone
    action: delete
  - path: customers.marketing_opt_in
    action: delete

  - path: invoices.customer_id
    action: pseudonymize           # stable keyed hash keeps invoice joins valid
    method: hmac_sha256
    key_ref: vault://billing/erasure-pseudonym-key  # placeholder; key stored outside the DB
    note: Still personal data. Do not treat as anonymous.

  - path: invoices.amount
    action: retain
    legal_basis: tax record-keeping obligation
    purpose_limit: tax and audit use only
    retain_until: invoice_date + RETENTION_PERIOD  # period set by legal team per jurisdiction
  - path: invoices.vat
    action: retain
    legal_basis: tax record-keeping obligation
    purpose_limit: tax and audit use only
    retain_until: invoice_date + RETENTION_PERIOD
  - path: invoices.billing_address
    action: retain
    legal_basis: required content of a legal invoice
    purpose_limit: tax and audit use only
    retain_until: invoice_date + RETENTION_PERIOD

# Fields that, combined with the pseudonym, may re-identify a person.
# Review before exporting retained data to analytics or other services.
reidentification_risk: [invoices.billing_address, invoices.invoice_date, invoices.amount]

A per-field erasure policy for a billing service that records whether each field is deleted, pseudonymized or retained, with the legal basis, purpose limit, expiry and privacy-team approval kept alongside the rule.

Crypto shredding for immutable logs, event streams and backups

Some stores cannot delete a single record: an event-sourced stream whose history is the source of truth, an append-only audit log, or a backup archive you cannot edit. Crypto shredding handles these. Each subject's personal fields are encrypted with a per-subject key held in a key store. When an erasure request arrives, you destroy the key, and every copy of that ciphertext becomes unreadable at once, including copies in replicas and backups. Use it only for these stores. It is not a way to skip deletion in databases that support it.

Key granularity sets what you can erase. A single key per subject can only erase everything about that subject. Keys per subject per purpose let you erase marketing data while keeping invoice data you are legally required to retain. The trade-off is more keys to manage.

The key store becomes a hard dependency. If it is unavailable, reads and writes of personal data fail. If it is lost without a backup, all personal data is lost. Field-level encryption also adds a key lookup and a decrypt to every access, so you need key caching, and the cache must respect revocation.

Whether ciphertext with a destroyed key counts as erased is a legal judgment. Confirm it with counsel.

Copyimport os
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

class KeyStore:
    """In-memory stand-in for a real key store, keyed per subject per purpose."""
    def __init__(self):
        self._keys = {}  # (subject_id, purpose) -> 256-bit key

    def get_or_create(self, subject_id, purpose):
        if (subject_id, purpose) not in self._keys:
            self._keys[(subject_id, purpose)] = AESGCM.generate_key(bit_length=256)
        return self._keys[(subject_id, purpose)]

    def get(self, subject_id, purpose):
        return self._keys.get((subject_id, purpose))  # None once shredded

    def shred(self, subject_id, purpose):
        # Destroying the key makes every copy of the ciphertext unreadable,
        # including copies already written to the event log and backups.
        self._keys.pop((subject_id, purpose), None)

def encrypt_field(store, subject_id, purpose, value):
    nonce = os.urandom(12)  # unique nonce per encryption
    aad = f"{subject_id}:{purpose}".encode()  # binds ciphertext to its key scope
    key = store.get_or_create(subject_id, purpose)
    return nonce + AESGCM(key).encrypt(nonce, value.encode(), aad)

def decrypt_field(store, subject_id, purpose, blob):
    key = store.get(subject_id, purpose)
    if key is None:
        return None  # key destroyed: treat the field as erased, not as an error
    aad = f"{subject_id}:{purpose}".encode()
    return AESGCM(key).decrypt(blob[:12], blob[12:], aad).decode()

store = KeyStore()
event = {  # appended to an immutable stream; only ciphertext is stored
    "email": encrypt_field(store, "subj-1042", "marketing", "ana@example.com"),
    "billing_address": encrypt_field(store, "subj-1042", "invoicing", "1 Example St"),
}
store.shred("subj-1042", "marketing")  # erasure request scoped to marketing
print(decrypt_field(store, "subj-1042", "marketing", event["email"]))            # None
print(decrypt_field(store, "subj-1042", "invoicing", event["billing_address"]))  # still readable

A minimal crypto-shredding sketch using AES-GCM with keys scoped per subject per purpose, where destroying the marketing key makes the email in an immutable event unreadable while legally retained invoicing data stays decryptable.

Preventing resurrection of erased data

Erasure is not a single event. A record you deleted today can return through several ordinary paths:

• Event replays. Rebuilding a projection from a topic re-applies every historical CustomerCreated event, including those for subjects you erased.
• Backup restores. A database restored to last Tuesday brings back everyone erased since then.
• Late-arriving events. A mobile client or partner queue delivers an update after the erasure completed, and the handler upserts a fresh record.
• Resyncs. A nightly import from a CRM, payment processor or other upstream system reintroduces the subject if that system has not yet processed the erasure.

The common fix is a suppression list: a small, durable set of erased subject identifiers that every ingestion path, replay job and restore procedure checks before writing. A match means the record is dropped or re-deleted, and the action is logged.

Keep the list minimal. It should hold no names, emails or other attributes. Store a keyed hash of the identifier, such as an HMAC with a secret held in your key management system. Ingestion code can then test membership without the list exposing who was erased. Because the list is itself personal data, record a documented justification for keeping it: it exists to make the erasure effective. Also define its retention, for example as long as any backup or replayable stream could still contain the subject.

Write the check into your restore runbooks. A restore must reapply every erasure recorded after the backup was taken before the system serves traffic. Without that step, backup expiry gives no protection during the retention window, because each restore undoes past erasures.

When to avoid this design, alternatives, and impact on cost and engineering time

The full design is overkill for a single datastore, where a transactional delete plus a backup-restore procedure covers the requirement. It is also more than you need for a small system with a few services owned by one team, or when requests arrive rarely enough that a scripted runbook is cheaper to maintain. Skip crypto shredding unless personal data actually sits in immutable stores. Per-subject keys bring key rotation, key backup, and a key service on the read path, and each of those can fail in its own way.

Most of the build cost is up front: the coordinator, a handler in every service, key management, and test infrastructure that seeds a synthetic subject and checks that every store is empty afterward. The benefit grows with request volume. No one has to hunt through other teams' systems for each request, fewer stores get missed, and an audit becomes a query against the request log.

Illustrative estimate (assumed numbers, not a benchmark): monthly manual cost = requests × teams involved × hours per team. With 40 requests, 6 teams and 0.5 hours each, that comes to 120 engineer-hours a month. Compare that figure against the one-time build cost plus ongoing maintenance.

The data inventory goes out of date as new stores are added. To keep it current, make deletion part of launch criteria: a new store cannot ship until it registers a handler and passes the synthetic erasure test in CI.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to gdpr data deletion microservices, this is where it helps:

Saves time

• Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
• One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
• Reviewers see the exact diff and the list of affected services up front, so approval is a decision rather than an investigation.

Saves cost

• Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
• Less duplicated configuration to maintain: one shared definition inherited by many services.
• Per-service approve/reject means a bad shared value can be refused where it would break something, before it is live.
• OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.