Build an Idempotent API Endpoint

Problem

Design and implement an idempotent payment processing API endpoint. When a client submits a payment request, network failures may cause the client to retry the request. Without idempotency, the customer could be charged multiple times for the same purchase.

Requirements

1. Idempotency Key: Accept an Idempotency-Key header (a UUID generated by the client) that uniquely identifies a request.
2. Exact-Once Processing: If the same idempotency key is sent again, return the original response without reprocessing.
3. Concurrent Requests: If two requests with the same idempotency key arrive simultaneously, only one should be processed; the other should wait and return the same result.
4. Key Expiration: Idempotency keys should expire after 24 hours to prevent unbounded storage growth.
5. Error Handling: Differentiate between retryable errors (network timeout to payment provider) and non-retryable errors (invalid card). Only retryable errors should allow a subsequent request with the same key to be reprocessed.

Constraints

• The endpoint processes real payments (cannot be processed twice).
• Multiple application server instances run behind a load balancer (the retry may hit a different server).
• The idempotency key storage must be shared across all instances.
• Response time should not increase by more than 10ms due to idempotency checks.
• The system must handle 500 payment requests per second.

What to Design

• The idempotency key storage schema and lookup strategy
• The locking mechanism for concurrent duplicate requests
• The request lifecycle with idempotency checks
• How error responses are cached (or not)
• The client-side implementation of idempotency keys