A design-collaboration platform in the mould of Canva stores 600 TB of customer files in object storage, all encrypted under one data key per bucket. Enterprise customers now require that their files be encrypted under keys they can revoke. How do you migrate to per-tenant keys without downtime or a 600 TB rewrite on day one?

The sequence

1. Introduce a key hierarchy. Each tenant gets a key-encryption key (KEK) held in the key management service, optionally backed by the customer's own key. Data is encrypted by data keys (DEKs); each DEK is wrapped by the tenant KEK. Revoking a KEK makes every DEK, and so every object, unreadable.
2. Write new objects the new way. New uploads get a DEK wrapped by the tenant KEK, with the wrapped DEK stored in object metadata. Existing objects stay readable under the old bucket key; readers check the metadata to know which scheme applies.
3. Rewrite old objects lazily and in the background. Read, decrypt under the bucket key, encrypt under a new DEK and write back, in tenant priority order (enterprise customers first). Each object's metadata flips only after the new copy is verified.
4. Throttle the rewrite. 600 TB through a 5 Gbit/s sustained link (about 600 MB/s) is 600,000,000 MB / 600 MB/s = 1,000,000 s, about 12 days of continuous transfer, in practice several weeks with throttling, plus egress and request costs.
5. Retire the bucket key only when a scan shows zero objects still referencing it, then disable and finally destroy it after a holding period.

Where data can diverge

A new copy and an old one both exist during rewrite, and a concurrent write to the object can be lost if the rewriter overwrites a newer version. Use conditional writes (an ETag precondition) so the rewrite fails if the object changed. A second risk is orphaned copies: backups, versions and replicas under the old key keep the data readable after "migration". Include versioned objects and replicated buckets in the scan.

The point of no return

Destroying the bucket key. Before that, rollback is reading under the old key. After it, any object not yet migrated is gone.

The rollback at each stage

Steps 1 and 2 are reversible by ignoring the metadata. Step 3 is reversible per object by keeping the old ciphertext until verification; it costs temporary storage of up to the size of the tenant's data.

How long it really takes

The mechanism is weeks; the long part is the backups and the versioned objects, plus customers who ask for their keys months later. State a deadline for old-key retirement and put it in the contract.

The shortcut that does not work

Re-wrapping alone, the cheap operation that makes KEK rotation fast, does not help here, because the old scheme had no per-tenant DEK to re-wrap: the one bucket key encrypted everyone's data. Re-encryption of the data is unavoidable the first time.

When this is overkill

If fewer than a handful of tenants need it, give them a dedicated bucket with its own key rather than a platform-wide hierarchy.

Common weak answers

• "Rotate the bucket key." It still covers all tenants.
• "Encrypt a copy and delete the original at the end." The deletion must cover every version.