Design a key management service

Generate, store, rotate and use encryption keys at 3,000 operations a second with strict audit.

Problem 070 of 100Infrastructure and platformL61 Nov 2026

Concepts this design leans on

Encryption and key management — Keys that encrypt keys, rotation, and hardware that never gives up a secret.
Authentication and authorization — Proving who you are, and checking what you may do, on every request.
Replication — Keeping copies so reads scale and a dead machine loses nothing.
Rate limiting — Token buckets, sliding windows, and enforcing them across many servers.
Observability: metrics, logs and traces — The three signals that explain why a request was slow.

01The design, in the six-step framework

1. Requirements

The reported variants: "a key vault", "a key-pair system handling 3,000 keys per second", "a key management service". Design a KMS that other services use to encrypt data without ever holding master keys themselves.

Functional

Create and manage keys: symmetric for data encryption, asymmetric key pairs for signing and TLS; each with versions and a rotation policy.
Operations that never export the key: encrypt, decrypt, sign, verify, and generate a data key wrapped by a master key (envelope encryption).
Access control per key and per operation, by service identity; every use audited.
Rotation without downtime: new versions encrypt, all versions decrypt until retired.
Out of scope: certificate authority workflows, user password storage.

Non-functional

Scale: 1 million keys, 3,000 key-pair generations a second at peak, 500,000 envelope operations a second.
Latency: an encrypt or decrypt call under 10 ms p99; key-pair generation under 50 ms.
Security: master keys never leave hardware security modules in plaintext; a compromised application server cannot extract a key.
Availability: 99.999 percent for decrypt, since every service's data depends on it; reads must survive a region loss.

Back of the envelope

An HSM does ~10,000 symmetric ops/s and ~100 to 500 RSA-2048 key generations/s: 3,000 key pairs/s needs 6 to 30 HSMs, or elliptic-curve keys (10× faster) where the client allows

500,000 envelope ops/s cannot all hit HSMs; with data keys cached by callers for 5 minutes, HSM calls drop to tens of thousands/s

Audit: 500,000 ops/s × 300 bytes = 150 MB/s of audit log, kept 7 years = 33 PB; must be compressed and tiered

2. Core entities

Key: key id, type (AES-256, EC-P256, RSA-2048), purpose, owner, rotation period, state (enabled, disabled, scheduled for deletion), primary version.
KeyVersion: key id, version, created at, state, the key material encrypted under a root key, HSM cluster id.
Policy: key id, principal (service identity), allowed operations, conditions.
AuditEvent: key id, version, operation, principal, request id, time, result; append-only.

3. API

POST /keys with type, purpose, rotation; POST /keys/{id}/rotate; PUT /keys/{id}/policy.
POST /keys/{id}/encrypt and /decrypt with ciphertext carrying the version; POST /keys/{id}/sign and /verify.
POST /keys/{id}/generate-data-key returns a plaintext data key plus the same key wrapped by the master key; the caller encrypts data locally and stores only the wrapped key.
GET /keys/{id}/public for public halves; GET /audit?key=&from=&to=.

4. High-level design

A service authenticates with mutual TLS and its workload identity; the gateway applies per-principal rate limits.
The front end loads the key's metadata and policy (cached), checks the principal may perform the operation, and routes to an HSM cluster that holds the key's version material.
The HSM performs the operation; for envelope encryption it generates a data key and returns it in plaintext over the secure channel plus wrapped under the master key.
Every operation is written to the audit log asynchronously but durably (the front end does not return until the event is queued in a replicated buffer).

5. Deep dives

How does envelope encryption give 500,000 operations a second without 500,000 HSM calls?

Callers never encrypt data with the master key. They ask for a data key, use it locally for many records or a whole file, and store the wrapped data key next to the ciphertext. Decrypting later means one KMS call to unwrap the data key, then local work. The SDK caches plaintext data keys for a bounded time and number of uses (say 5 minutes or 10,000 records), so a service doing 50,000 writes a second makes a few HSM calls a minute. The master key, held in the HSM, only ever wraps and unwraps 32-byte keys, which is the cheap operation. This is the design that makes the throughput number possible, and the cache bounds are the security trade to state (encryption and key management).

How are 3,000 key pairs a second generated, and where does the private half live?

Generation is the expensive HSM operation. Pool it: a background job keeps a buffer of pre-generated key pairs per HSM cluster, encrypted under a root key, so a request takes one from the pool and records ownership; the pool is refilled at the HSM's sustainable rate across enough clusters. For callers that accept elliptic-curve keys, generation is ten times cheaper than RSA, so the API nudges them there. A private key is either kept in the HSM and used only through sign and decrypt calls (highest assurance, lower throughput), or exported wrapped under a customer master key for use in the caller's own secure environment; the policy on the key says which, and export is audited. Never return a private key in plaintext over the API.

How does rotation work without re-encrypting everything?

Rotation creates a new version and makes it primary: new encrypts use it, and ciphertext carries the version id so decrypt picks the right one. Old versions stay enabled for decrypt until an explicit retirement, after a re-encryption campaign the data owner runs at their pace (the KMS offers a re-encrypt call that unwraps with the old version and wraps with the new one without exposing the data key). Rotation is thus a metadata change, instantaneous and reversible; the slow part belongs to data owners. The root keys that wrap key versions rotate rarely and are split across multiple HSM administrators with a quorum (k of n smart cards) to perform ceremonies.

How is the service made both highly available and tamper-evident?

Key metadata is replicated across regions, and each key version's material is present in HSM clusters in at least two regions, so a region loss leaves decrypt available; the front ends are stateless and run everywhere. Authorization is enforced at the front end from cached policies with a short TTL, with revocations pushed immediately. The audit log is append-only, hash-chained per key so a deleted or altered event breaks the chain, and shipped to a separate account that KMS operators cannot write to. Observability covers anomaly alerts: a principal suddenly decrypting a thousand times its usual rate is paged on, because that is what exfiltration looks like.

6. What a strong answer sounds like

Start from the HSM throughput numbers and derive envelope encryption and key-pair pooling from them.
Be precise about what never leaves the HSM, what is cached where and for how long, and why that is acceptable.
Explain versioned rotation as a metadata flip plus an owner-driven re-encryption.
Make the audit log tamper-evident and independent, and mention rate-anomaly alerts.
Follow-ups to expect: customer-managed keys (the wrapping key lives in the customer's HSM), deletion with a waiting period (scheduled deletion, recoverable for days, then crypto-shredding by destroying the version), and performance isolation (per-principal quotas so one tenant cannot starve another's decrypts).

02Where this question was reported

IGotAnOffer · TPM: 'key pair system which can handle 3,000 keys per second'
PracHub · 'Design key management service', Hard
Blind · Round 1: design a key vault
PracHub · Design key management service, rated Hard (aggregator)