Making POST /payments Safe to Retry

Your mobile app calls POST /payments {order_id, amount_cents}. Support tickets show customers charged twice after the app retried on a network timeout. The payments service is stateless behind a load balancer and writes to Postgres before calling the card processor.

1. Design an idempotency-key mechanism: what the client sends, what the server stores, and the exact sequence of steps on first request, on a retry after success, and on a retry that arrives while the first attempt is still running.
2. Two clients (different merchants) accidentally generate the same key. How do you prevent a collision?
3. A retry arrives with the same key but amount_cents changed from 4200 to 4300. What should the server return and why?