Design a shared idempotency service that lets many upstream teams safely retry mutating operations without executing them twice. Callers attach a client-chosen idempotency key to a request; your service guarantees that the first attempt for a key runs the underlying operation and every later attempt with the same key returns the identical stored result instead of re-running it.

The service sits in front of high-value, non-repeatable actions (think charging a wallet, placing an order, sending money). It is called by dozens of internal services whose message pipelines are at-least-once — so duplicate deliveries are normal, not exceptional, and two duplicates for the same key can arrive milliseconds apart on different machines and even different regions.

Operating context. Roughly 40,000 idempotent requests/sec at steady state across ~50 caller services, with a tenfold burst during peak sale events. A meaningful slice — assume 5–15% — of incoming requests are retries/duplicates of a key already seen. Records must be retained for a 24-hour replay window (some clients retry slowly via dead-letter queues), after which they expire. Callers run in three regions (two active, one warm) and a small fraction of duplicate pairs land in different regions. A record is a key plus a stored response body, on the order of a few KB each; expect billions of live keys during a big event.

Out of scope. The business logic behind each operation (you only mediate exactly-once execution, you do not implement the charge itself), authentication of callers, the client SDK internals, per-tenant rate limiting, and analytics/reporting on duplicate rates. Assume other teams own those.

What to produce. A high-level architecture covering: the request path for a first-seen key versus a duplicate key, the idempotency-key data model and how you partition it, the first-writer-wins concurrency mechanism (including the in-flight state so a second caller does not double-execute while the first is still running), TTL-based expiry and response replay, how you cope with at-least-once producers and cross-region duplicates, and the storage-engine choice with a rough cost/footprint justification. Sketch the major components and the request flow between them; we will probe the concurrency and cross-region edges during checkpoints.