Design an Idempotency Key Store

Design the platform service that lets any of a company's write APIs be safely retried. A client attaches an idempotency key to a mutating request (for example, 'create order' or 'charge card'); if the same key arrives again — because the client timed out and retried — the API must not perform the effect twice and must return the original response.

Operating context. Many internal services call this store on their write path, so its latency is added to theirs. Retries frequently arrive concurrently (a client fires a second attempt while the first is still running), and network partitions mean a first request may have committed even though the client never saw the reply. The store must fence those races so an operation runs exactly once, and it must remember the outcome long enough to answer late retries. Keys are scoped per caller/endpoint so two unrelated callers can reuse the same key string.

Out of scope. The business logic of the wrapped operations themselves, distributed transactions across multiple downstream services, client SDK retry policy, and long-term audit archival. Assume other teams own those.

What to produce. A high-level architecture covering: the key lifecycle (first-seen, in-flight, completed) and the state machine behind it, how concurrent duplicates with the same key are fenced to a single in-flight execution, how a completed response is stored and replayed, how a reused key carrying a different request body is detected and rejected, the storage/partitioning and retention model, and how the system behaves when a request crashes mid-flight or the store is briefly unreachable. Sketch the components and flow; we will probe specifics in checkpoints.