Idempotency key storage and concurrency

Design the idempotency layer for a public payments API that handles ~50M write requests/day. Clients pass an Idempotency-Key header on POSTs; the same key with the same body must return the original response, and the same key with a different body must be rejected. Keys expire after 24h. Cover the storage, the concurrency control when two requests with the same key arrive simultaneously, and how you keep the recorded response consistent with the side effect that was actually performed.