Per-row encryption with zero-downtime key rotation

Most “field-level encryption” stories fall apart at rotation time. The cryptography is fine. The operations aren’t. Rotating a master key shouldn’t require a maintenance window, a feature freeze, or a frantic Slack thread when read latency triples because every row in a hot table is being decrypt-then-re-encrypt’d while traffic still hits it.

The vault layer in RedDB is built so rotation is a background operation that runs at whatever pace you tell it to, on a live table, with no read-path stall and no application changes. This post is the internals. If you operate the system, the second half is the one you want.

The envelope

Every encrypted row carries a small envelope alongside its ciphertext. Three fields:

+----+-----------------+------------+
| g  | iv (12 bytes)   | ciphertext |
+----+-----------------+------------+
  ^
  generation byte (or short int)

g — the master key generation this row was encrypted under. One byte is plenty; we use a 16-bit int to leave room.
iv — a per-row, never-reused initialisation vector. AES-GCM, so 12 bytes.
ciphertext — the encrypted payload, with the GCM auth tag appended.

The envelope is stored as one opaque column. Application code never touches it directly; the SQL layer wraps reads and writes with vault_decrypt(col) and vault_encrypt(col) calls that look up the right key by generation.

The crucial property: the row knows which key it needs. No central index, no separate “which-key-for-which-row” table. That’s what makes rotation cheap.

The master key set

The master key set is versioned, not replaced. Conceptually:

generation │ key material (32 bytes)        │ state
─────────────────────────────────────────────────────
1          │ <kek-1, wrapped by KMS root>   │ retired
2          │ <kek-2, wrapped by KMS root>   │ active-read
3          │ <kek-3, wrapped by KMS root>   │ active-write

Three states matter:

active-write — the generation new writes use. Exactly one at a time.
active-read — generations that are still permitted on the read path. Many can be active-read.
retired — generation is gone. Any row still tagged with it is unreadable (this is by design — see “destroying a generation” below).

The actual key material is wrapped by your KMS root and only unwrapped into a process-local cache. The wrapped form is what we store and replicate; the cache holds unwrapped keys with a short TTL so a KMS access revocation propagates.

Reads pick the right generation

A read is straightforward:

Fetch the row. Parse the envelope header.
Look up generation g in the key cache. If absent, ask KMS to unwrap it; populate the cache.
Verify the GCM tag, decrypt, return plaintext.

Cost: a 16-bit read of g, a map lookup (hot), and one AES-GCM decrypt. The expensive part — KMS round-trip — only happens on cache miss, which is essentially never in steady state because the working set of live generations is tiny (usually 1–3).

If the generation is retired, the read errors with a typed KeyRevoked and the row is returned as encrypted bytes plus the generation number — useful for forensics and for the “I told you to retire it” conversation.

Writes always use the latest

Writes are simpler still: encrypt under whichever generation is active-write, write the envelope, done. There is no read-modify-write on the encryption path. Inserts and updates are symmetric.

The application gets identical SQL whether the column is vaulted or not:

insert into customers (id, email_vault)
values ($1, vault_encrypt($2));

select id, vault_decrypt(email_vault) as email
from customers
where id = $1;

vault_encrypt is a stable function that picks the current active-write generation per call. vault_decrypt reads the envelope’s embedded generation, so the same query works across rows encrypted under different generations — which is the whole point.

Rotation, online

Rotation is three steps and the third one is the only slow one.

Step 1 — provision a new generation. Generate kek-N+1, wrap with the KMS root, store it as retired initially so it isn’t picked up by anything. This is one round-trip to KMS and a single SQL write.

Step 2 — promote. Atomically:

Move the current active-write to active-read.
Move the new generation from retired to active-write.

From this instant, every new write uses the new generation. Every old row remains readable because its old generation is now active-read. The application sees nothing. No restart, no flush, no schema change. Read latency does not change. p99 does not move.

If you stop here, you have a partially-rotated table. That’s actually fine — rotation is monotonic and incremental. Many compliance regimes only require “new writes use the new key from date X.” If yours does, you’re done.

Step 3 — background re-encrypt. A worker scans the table, decrypts each row under its old generation, re-encrypts under the new one, and writes it back as a normal update. We use SKIP LOCKED so the worker never blocks an application write, and a rate-limit knob (rows-per-second) so the worker can be tuned to fit available IO headroom.

-- worker query, roughly
with batch as (
  select id from customers
  where vault_generation(email_vault) < (select current_active_write_generation())
  order by id
  limit 1000
  for update skip locked
)
update customers c
   set email_vault = vault_reencrypt(c.email_vault)
  from batch b
 where c.id = b.id;

vault_reencrypt decrypts under the embedded generation and re-encrypts under the current active-write. It’s a single round-trip to the vault layer, no application code involved.

Once the worker finishes, every row carries the latest generation. The old generation can be moved from active-read to retired, and the wrapped key can be deleted from KMS. Now rotation is complete.

What “zero downtime” actually means

Specifically:

No read-path stall — reads of old rows during the worker pass go through the normal decrypt path with the old key, which is still active-read.
No write-path serialisation — writes during the worker pass land under the new generation and don’t conflict with the worker’s updates beyond the usual row locks.
No application changes — generation handling is below the SQL layer.
No required maintenance window — the only “instantaneous” operation is the generation promotion in step 2, which is a single-row update on the key-set table.

What it does cost:

IO during the background pass. A re-encrypt is approximately one logical read + one logical write per row, plus WAL.
Cache memory for any live generation. Trivial.
KMS unwrap calls when a new generation appears or a cache TTL expires. Small.

The knob to leave alone

The vault has a rotation.aggressive flag that forces a full synchronous re-encrypt scan inside the transaction that promotes the new generation. It exists because the test suite needs to deterministically produce a fully-rotated table to assert on. It is catastrophic on a real workload:

It serialises every row in the table behind the promotion transaction.
It holds locks long enough that anything touching the table will queue.
On a multi-terabyte table it will not complete inside any reasonable transaction timeout, and you will get to find out what your client-side retry behaviour does when a 4-hour transaction aborts.

We’ve thought about removing it. Strong opinion: if you find yourself reaching for rotation.aggressive on a production cluster, the actual answer is to let the background worker run and check back in a few hours.

Destroying a generation

Real revocation — “make this key materially impossible to use, even by an operator with database root” — is the same dance from the opposite direction:

Move the doomed generation to retired in the key-set table.
Delete the wrapped key from KMS.
Any row still tagged with that generation is now permanently undecryptable.

Step 3 is the bit you actually want for incident response: even a leaked database backup is useless without the KMS-resident master key. The envelopes are still there; they just can’t be unwrapped.

This is also how erasure works for compliance — for a “forget this user” request that crosses replicas, backups, and WAL archives, the cleanest path is per-tenant generations: retire and destroy the tenant’s generation and every replica, backup, and WAL segment containing that tenant’s ciphertext becomes cryptographically inert in one step. We’ll write that up separately.

Where this lives in the architecture

The vault layer sits between SQL parsing and the storage engine. From the SQL layer’s point of view, encrypted columns are just bytes with two helpful functions. From the storage engine’s point of view, there’s no encryption at all — it sees opaque blobs.

That separation is what makes the system honest about its threat model. We protect against backup theft, replica theft, and KMS-tier revocation. We do not protect against a compromised database process — the unwrapped keys are in memory by design while the system is serving traffic. If your threat model includes “operator with database root reads decrypted rows,” you need a different layer of the stack (typically client-side encryption, where the database never sees plaintext or unwrapped keys).

The shorter version

Each row carries a generation byte.
Master keys are versioned, never replaced.
Reads use the row’s generation; writes use the current active-write.
Rotation is: provision, promote, then background re-encrypt at your own pace.
The synchronous-re-encrypt flag exists for the test suite. Leave it alone.

The follow-ups in this series will cover per-tenant key isolation, BYOK and KMS integration patterns (and the failure modes nobody writes about), and GDPR right-to-erasure when your data is replicated, embedded, and backed up.