Rotating Tenant Data Encryption Keys Without Downtime

Key rotation fails when it is treated as a single switch instead of an interval during which two keys are simultaneously valid, and this page builds the interval. It is a focused part of Per-Tenant Encryption & Key Management: how to start writing under a new key immediately while old data catches up in the background.

Problem Framing

Rotation is required by every serious compliance framework and by ordinary prudence: a key that has been in use for years has been in more memory dumps, more backups and more support sessions than anyone can enumerate. The naive approach — decrypt everything, re-encrypt everything, then swap — requires a maintenance window proportional to the tenant's data size, which for the largest tenants means the longest outage.

Two facts make a zero-downtime rotation possible. First, with envelope encryption the expensive payload never has to change: only the small wrapped data key needs re-wrapping under the new tenant key. Second, decryption can be version-aware — each row records which key version wrapped it, so a reader can pick the right key without any global coordination.

That turns rotation into three overlapping states rather than an event: both keys readable, new key written, old key retired only when the backfill confirms nothing references it. The dangerous simplification is retiring the old key on a timer instead of on evidence; the safe version retires it on a count of zero.

Three states, no window. Retirement is gated on a measured zero rather than on elapsed time.

Step-by-Step Guide

1. Make readers version-aware before creating the new key

Deploy the reader change first. If a new key appears before every replica can read it, some requests fail — and the failure looks exactly like a corruption incident, which is a bad way to spend an afternoon.

// reader.ts
export async function unwrapAnyVersion(kms: Kms, tenantId: string, row: EnvelopeRow, aad: Uint8Array) {
  const keyId = keyIdFor(tenantId, row.keyVersion);        // resolves v1 or v2 alike
  try {
    return await kms.unwrap(keyId, row.wrappedDk, aad);
  } catch (err) {
    if (isDisabledKey(err)) throw new RetiredKeyError(tenantId, row.keyVersion);
    throw err;
  }
}

Distinguishing "key disabled" from "authentication failed" matters operationally: the first means rotation retired something too early, the second means a real integrity problem.

2. Create the new key version and enable it for reads only

// begin-rotation.ts
export async function beginRotation(kms: Kms, tenantId: string) {
  const v2 = await kms.createKeyVersion(tenantId);         // readable immediately
  await db.query(
    `UPDATE tenant_key_state
     SET    read_versions = read_versions || $2::int[], rotation_started_at = now()
     WHERE  tenant_id = $1`,
    [tenantId, [v2.version]],
  );
  return v2.version;                                        // write version unchanged for now
}

Leaving the write version alone for one deploy cycle gives a clean rollback: if anything is wrong, remove the new version from read_versions and nothing has been written under it.

3. Flip the write version, then backfill in bounded batches

New rows immediately use the new key; old rows are re-wrapped by a job that touches a bounded number of rows per transaction so it never holds a long-running snapshot.

-- One backfill batch: re-wrap at most 500 rows, newest first so hot data converts early.
WITH batch AS (
  SELECT id FROM patient_note
  WHERE  tenant_id = $1 AND key_version = $2
  ORDER  BY updated_at DESC
  LIMIT  500
  FOR UPDATE SKIP LOCKED
)
SELECT id, body_wrapped_dk, body_nonce FROM patient_note WHERE id IN (SELECT id FROM batch);

// backfill.ts — re-wrap only; ciphertext and nonce are never touched
export async function rewrapBatch(kms: Kms, client: PoolClient, tenantId: string, from: number, to: number) {
  const rows = await selectBatch(client, tenantId, from);
  for (const row of rows) {
    const aad = fieldAad(tenantId, 'patient_note', 'body', row.id);
    const raw = await kms.unwrap(keyIdFor(tenantId, from), row.body_wrapped_dk, aad);
    const wrapped = await kms.wrap(keyIdFor(tenantId, to), raw, aad);
    raw.fill(0);
    await client.query(
      `UPDATE patient_note SET body_wrapped_dk = $1, key_version = $2
       WHERE id = $3 AND key_version = $4`,          // guard: skip if another worker won
      [wrapped, to, row.id, from],
    );
  }
  return rows.length;
}

The AND key_version = $4 guard makes the job safe to run concurrently and safe to re-run after a crash — both properties you want when the job may take days on the largest tenant.

4. Track progress as data, so "are we done?" is a query

CREATE OR REPLACE VIEW rotation_progress AS
SELECT tenant_id,
       count(*) FILTER (WHERE key_version = 1) AS remaining_v1,
       count(*) FILTER (WHERE key_version = 2) AS done_v2,
       round(100.0 * count(*) FILTER (WHERE key_version = 2) / nullif(count(*), 0), 2) AS pct
FROM   patient_note
GROUP  BY tenant_id;

Exporting pct per tenant as a gauge turns a multi-day background job into something an on-call engineer can reason about at a glance, and makes a stalled backfill visible within one scrape interval.

5. Retire the old version only on a measured zero

// retire.ts
export async function retireOldVersion(kms: Kms, tenantId: string, oldVersion: number) {
  const { rows } = await db.query(
    `SELECT sum(remaining) AS remaining FROM (
       SELECT count(*) AS remaining FROM patient_note   WHERE tenant_id = $1 AND key_version = $2
       UNION ALL
       SELECT count(*)             FROM message_body    WHERE tenant_id = $1 AND key_version = $2
       UNION ALL
       SELECT count(*)             FROM attachment_meta WHERE tenant_id = $1 AND key_version = $2
     ) t`, [tenantId, oldVersion]);
  if (Number(rows[0].remaining) !== 0) throw new Error('backfill incomplete — refusing to retire');

  await kms.disableKeyVersion(tenantId, oldVersion);
  await kms.scheduleKeyVersionDeletion(tenantId, oldVersion, { pendingWindowDays: 30 });
  await audit.write('tenant.key_version_retired', { tenantId, oldVersion });
}

Every encrypted table must appear in that union. A table added after rotation started, and missed here, is how a key gets deleted while rows still depend on it — which is unrecoverable data loss rather than an incident.

A large tenant's backfill measured in days, not minutes, and entirely invisible to its users because nothing in the request path waits for it.

Verification

Three checks: readers handle both versions, the backfill converges, and retirement is genuinely blocked while rows remain.

// rotation.spec.ts
it('reads rows written under either key version', async () => {
  const v1Row = await seal({ tenantId: 'acme', version: 1, value: 'old' });
  const v2Row = await seal({ tenantId: 'acme', version: 2, value: 'new' });
  expect(await open(v1Row)).toBe('old');
  expect(await open(v2Row)).toBe('new');
});

it('refuses to retire while any row still references the old version', async () => {
  await seal({ tenantId: 'acme', version: 1, value: 'straggler' });
  await expect(retireOldVersion(kms, 'acme', 1)).rejects.toThrow(/backfill incomplete/);
});

it('is idempotent — a re-run converts nothing and errors on nothing', async () => {
  const first = await rewrapBatch(kms, client, 'acme', 1, 2);
  const second = await rewrapBatch(kms, client, 'acme', 1, 2);
  expect(second).toBe(0);
  expect(first).toBeGreaterThan(0);
});

-- Standing check: no tenant is stuck mid-rotation.
SELECT tenant_id, remaining_v1, pct
FROM   rotation_progress
WHERE  remaining_v1 > 0
  AND  tenant_id IN (SELECT tenant_id FROM tenant_key_state
                     WHERE rotation_started_at < now() - interval '14 days');
-- expected: no rows

The ordering of the four deploys is the part most worth internalising, because three of the four failure modes below are simply this sequence performed out of order.

Only the last column is unrecoverable, which is why the retirement gate is a query rather than a calendar entry.

Failure Modes & Gotchas

Symptom: decryption fails across a fleet immediately after creating the new key. Cause: the key was created before every replica ran version-aware reader code. Fix: deploy readers first, then create the key; treat the two as separate releases.
Symptom: the backfill never finishes on the largest tenant. Cause: batches are ordered by primary key on a table with continuous writes, so the job chases its own tail. Fix: filter strictly on key_version — which shrinks monotonically — rather than on a position, and let SKIP LOCKED handle contention.
Symptom: rows become permanently undecryptable after retirement. Cause: a table was added to the encryption scheme after the retirement query was written, so its remaining rows were never counted. Fix: derive the table list from the same registry that drives encryption, and fail if any table lacks a key_version column.
Symptom: database load spikes during backfill. Cause: unbounded batch size or no pacing between batches. Fix: cap at a few hundred rows per transaction, add a small delay, and drive the rate from replication lag rather than from a fixed constant.

FAQ

How often should tenant keys be rotated? Annually is the common baseline and satisfies most frameworks; quarterly is defensible for high-sensitivity data. What matters far more than the interval is that rotation is routine — a rehearsed, automated, observable process — because the rotation that actually matters is the emergency one after a suspected compromise, and that is not the moment to discover the backfill job has never run at scale.

Does rotation re-encrypt the actual data? Not with envelope encryption: only the wrapped data key changes, so the work is proportional to row count rather than to payload size. Re-encrypting the payloads themselves is a different operation, needed only if the record's own data key is suspected compromised or if you are migrating cipher suites — and it is far more expensive, since every ciphertext and nonce must be rewritten.

What if a tenant demands their key be destroyed immediately? That is crypto-shredding, not rotation, and it is deliberately irreversible: disable the key, clear cached data keys, and schedule deletion with the provider's pending window. Do not run it as part of a rotation, and do not skip the pending window — the whole value of that window is that an offboarding triggered by mistake can still be undone. The surrounding workflow is described in Tenant Offboarding & Data Retention Workflows.