Idempotency key service

Design an idempotency-key service that makes mutating API calls (e.g. "charge this card", "create this order") safe under client retries, where the SAME key may arrive concurrently from a retry storm. Constraints: a payment must execute its side effect at most once even if 5 duplicate requests land within milliseconds, the client must get a consistent response across all duplicates, and a request that crashed mid-execution must be safely retryable. Describe the key store, how concurrent duplicates are coordinated, and what the second-arriving request sees.