Key Rotation Without Downtime: Re-Encrypting Vector Data In Place

Encryption key rotation is one of those maintenance tasks that everyone knows they should do but most teams put off because the cost of doing it wrong is catastrophic. When the data is a 2TB vector store embedded in a retrieval pipeline, the problem gets worse: you cannot just dump and reload the data, and you cannot afford to take the service offline for hours. This post walks through the engineering tradeoffs and a concrete pattern for rotating keys in place, without downtime, using envelope encryption and staged re-encryption.

Why Key Rotation Matters

Encryption keys are like passwords: the longer they live, the more exposure they accumulate. Keys get leaked through logs, backups, or compromised endpoints. Regulatory frameworks and security audits increasingly require periodic rotation. But the real reason to rotate is to limit the blast radius of a compromise. If an attacker exfiltrates a key, they can decrypt everything encrypted with it. Rotating keys ensures that even if a key is compromised, only the data encrypted under that key is at risk, and only for the period between rotation events.

For a vector store, the data is often embeddings that power semantic search. These embeddings are derived from sensitive documents, and the vectors themselves can be used to reconstruct approximate content. So the stakes are high. But the challenge is that vector data is large, binary, and tightly coupled to the index structure. You cannot simply re-encrypt a few rows; you have to touch every vector.

The Naive Approach: Dump and Reload

The simplest way to re-encrypt data is to decrypt everything, re-encrypt with a new key, and write it back. For a relational database, you might do this in a transaction. But for a vector store, this means:

1. Export all vectors to a temporary location.
2. Decrypt them with the old key.
3. Re-encrypt with the new key.
4. Delete the old data and import the new.

This approach has several problems. First, it requires enough storage to hold a second copy of the data. Second, it requires the system to be offline or in a degraded mode while the data is being rebuilt. Third, it is risky: if the import fails halfway, you have no data. Fourth, it is slow, because you are moving terabytes over the network or disk.

For a 2TB vector store, this could take hours or days depending on the hardware. During that time, the service is either down or serving stale data. For a production system, that is usually unacceptable.

Envelope Encryption: The Foundation

A better approach is to use envelope encryption. The idea is simple: you do not encrypt the data directly with the master key. Instead, you generate a unique data encryption key (DEK) for each logical unit (e.g., a table, a shard, or even a single row). The DEK is used to encrypt the data, and the DEK itself is encrypted with a key encryption key (KEK), which is the master key that you rotate.

When you rotate the KEK, you only need to re-encrypt the DEKs, not the underlying data. This is a huge win because the DEKs are tiny compared to the data. For a 2TB vector store, the DEKs might be a few kilobytes. Re-encrypting them is instant.

The tradeoff is that you need to store the DEKs somewhere, and you need to manage their lifecycle. But the benefits are clear: rotation becomes a metadata operation, not a data operation.

Here is a simplified example of how envelope encryption works in Python using the cryptography library:

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.pbkdf2 import PBKDF2HMAC
import os

def generate_dek():
    return os.urandom(32)  # 256-bit DEK

def encrypt_dek(dek, kek):
    # Use AES-KW or similar
    from cryptography.hazmat.primitives.keywrap import aes_key_wrap
    return aes_key_wrap(kek, dek)

def decrypt_dek(wrapped_dek, kek):
    from cryptography.hazmat.primitives.keywrap import aes_key_unwrap
    return aes_key_unwrap(kek, wrapped_dek)

# Example usage
kek = os.urandom(32)
dek = generate_dek()
wrapped = encrypt_dek(dek, kek)
# Store wrapped, and use dek to encrypt actual data

In practice, you would use a key management service (KMS) to handle the KEK and to perform the wrap/unwrap operations, so that the KEK never leaves the KMS boundary.

Staged Re-Encryption Without Downtime

Even with envelope encryption, you still need to re-encrypt the DEKs when you rotate the KEK. But that is a fast operation. The real challenge is when you want to re-encrypt the actual data, for example, if you suspect the DEK itself was compromised, or if you want to switch to a different encryption algorithm.

In that case, you need to re-encrypt the data in place, without taking the system offline. The pattern is called staged re-encryption, and it works like this:

1. Add a new key version to the key hierarchy. All new writes use the new key.
2. Background re-encryption job reads chunks of data, decrypts with the old key, re-encrypts with the new key, and writes back.
3. Read path handles both keys by checking a version header on each record.
4. Once all data is re-encrypted, you can retire the old key.

The key insight is that you do not need to stop the world. You can re-encrypt incrementally, chunk by chunk, while the system continues to serve reads and writes. The only requirement is that the read path must be able to handle records encrypted with either key.

For a vector store, this means each vector record (or each shard) needs to carry a key version identifier. When you read a vector, you look at the version, fetch the corresponding DEK, and decrypt. When you write a new vector, you always use the latest key version.

The background job can be as simple as a cron job that processes a batch of records at a time. You need to track progress, for example, by a watermark column or by scanning the index in chunks. The job should be idempotent, so if it crashes, it can resume from where it left off.

Here is a conceptual outline of the background job in Python:

import psycopg2

def reencrypt_batch(cursor, batch_size):
    cursor.execute("""
        SELECT id, encrypted_vector, key_version
        FROM vectors
        WHERE key_version = %s
        LIMIT %s
    """, (old_version, batch_size))
    rows = cursor.fetchall()
    for row in rows:
        id, encrypted_vector, _ = row
        vector = decrypt_with_old_key(encrypted_vector)
        new_encrypted = encrypt_with_new_key(vector)
        cursor.execute("""
            UPDATE vectors
            SET encrypted_vector = %s, key_version = %s
            WHERE id = %s
        """, (new_encrypted, new_version, id))
    return len(rows)

# Main loop
while True:
    processed = reencrypt_batch(cursor, 1000)
    if processed == 0:
        break
    conn.commit()

Handling Writes During Rotation

One subtlety is handling writes that happen while the re-encryption job is running. If a record is updated, the new version should be written with the latest key. If a record is deleted, it is gone. The tricky part is when a record is updated while the background job is reading it. To avoid conflicts, you can use optimistic locking: the UPDATE statement includes a condition that the key_version is still the old version, so if the record was already re-encrypted, the update is skipped.

Alternatively, you can process records in a way that is atomic: read, decrypt, re-encrypt, and update in a single transaction with a row lock. This ensures that no other transaction can modify the record while you are re-encrypting it.

In practice, the background job should be low-priority and throttled so it does not compete with production traffic. You can use a rate limiter or process during off-peak hours.

Key Versioning and the Read Path

The read path must be able to handle multiple key versions. This is typically implemented by storing a key version number alongside the encrypted data. When you read a record, you fetch the version, then look up the corresponding DEK in a local cache or from the KMS.

You also need to handle the case where the DEK is not available (e.g., if the KMS is down). In that case, you may need to fail the read or use a cached copy. The safest approach is to cache DEKs in memory for a short period, but ensure they are not persisted in plaintext.

Here is an example of a read path that handles multiple versions:

def decrypt_vector(encrypted_vector, key_version):
    if key_version == current_version:
        dek = get_current_dek()
    else:
        dek = get_old_dek(key_version)
    return aes_decrypt(encrypted_vector, dek)

Audit and Compliance Considerations

Key rotation is not just a technical exercise; it is often a compliance requirement. You need to be able to prove that you rotated keys at a certain time, and that all data was re-encrypted. This means you need an audit trail.

You should log every rotation event, including the key ID, the version, the timestamp, and the scope (which data was affected). You should also log the progress of the re-encryption job, so you can demonstrate that the rotation completed.

One common practice is to use a separate audit log that is append-only and tamper-evident. You can use a simple log file or a dedicated audit table in your database. The important thing is that the audit trail is not stored in the same place as the data, so that a compromise of the data does not allow an attacker to alter the logs.

Real-World Patterns and Pitfalls

Teams that have implemented this pattern report several pitfalls. The first is performance degradation during re-encryption. Re-encrypting 2TB of data will consume I/O and CPU, and if you do it too aggressively, it can impact query latency. The solution is to throttle the job and run it in the background with low priority.

The second pitfall is the risk of data corruption. If the process crashes halfway through a batch, you may end up with partially written records. To mitigate this, you should use transactions and write the new encrypted vector only after successfully reading and decrypting the old one.

A third pitfall is key management complexity. If you use a KMS, you need to ensure that the KMS is highly available and that you have a backup of the key material. If the KMS is down, you cannot decrypt any data, which is a availability risk.

Finally, you need to consider the case where the vector store is not a simple table but a distributed index. In that case, the re-encryption job needs to coordinate across shards, and you need to ensure that all replicas are updated consistently.

When Not to Use This Pattern

Envelope encryption and staged re-encryption are not always the right answer. If your data is small (e.g., a few gigabytes), it might be simpler to just dump and reload. If your data is ephemeral and can be regenerated, you might not need to re-encrypt at all. And if you are using a managed vector database that does not expose raw storage, you are limited to the vendor's rotation mechanism.

But for a self-hosted, sovereign infrastructure where you control the keys, this pattern gives you the flexibility to rotate keys on demand without downtime.

Conclusion

Key rotation for large vector stores is a real engineering challenge, but it is solvable with the right architecture. Envelope encryption decouples the master key from the data, making rotation a metadata operation. Staged re-encryption allows you to re-encrypt data incrementally without downtime. Key versioning ensures that the read path can handle mixed states during the transition. And a robust audit trail keeps you compliant.

If you are building a sovereign AI infrastructure, where data sovereignty and security are paramount, investing in a solid key management and rotation strategy is not optional. It is a core part of your system's resilience.

When you design your next vector store, think about key rotation from day one. It will save you a lot of pain later.