Submit Order (Prevent Double-Charge) — a worked solution

Typical clarifications to surface:

• Is the charge synchronous or does it settle async? Assume a synchronous authorize+capture against a PSP (Stripe/Adyen) on the request path — that is the hard case (a foreign state mutation inside the request). Async settlement only moves the same problem to a webhook.
• Who mints the idempotency key — client or server? Client. This is not a style choice: the retry we must survive is the one where the client never saw the first response, so only the client can re-supply the same key. A server-minted key regenerates and the dedup fails.
• How long must a key be honored (the dedup window)? Long enough to cover the client's entire retry horizon (including an app relaunch hours later) and aligned with the PSP's window. Default 24h (Stripe's).
• Exactly-once, or effectively-once? There is no true exactly-once across two systems. We guarantee at-most-one charge + at-most-one order, and at-least-once side-effects with idempotent consumers (effectively-once).
• What is the natural key of an order? Is a duplicate defined by the idempotency key alone, or also by (user, cart-hash)? We use the idempotency key as the dedup identity and keep a request fingerprint to reject key-reuse-with-different-body.
• Single region? Yes — the money tier is CP and single-region here. Multi-region residency is out of scope for this focused problem.

Assumptions to state:

• 5M orders/day, ~58/s average, 20× flash-sale peak (~1,160 orders/s).
• Payment provider p99 ~2s; dual-provider (Stripe primary, Adyen fallback).
• Dedup window 24h; keys are v4 UUIDs minted at payment-sheet open.
• Client retries: full-jitter exponential backoff, ≤3 attempts in 30s.

• Submit an order (POST /orders) with a client-minted Idempotency-Key. The server authorizes+captures payment and records the order. Must be idempotent: any number of retries of the same key ⇒ one charge, one order, one response.
• Replay safety: a repeated key returns the original response (status + body), including a repeated error, without re-executing.
• Concurrent-duplicate safety: two in-flight requests with the same key ⇒ one proceeds, the other gets 409 in-progress (retriable), never a second charge.
• Resume a half-finished intent: if the process crashed after charging but before recording the order, the next retry (or the reconciler) drives it to completion — no second charge.
• Reject key misuse: the same key with a different request body ⇒ 422, never the wrong cached order.
• Cancel / refund an order idempotently (same key discipline, refund-scoped provider key).
• Deliver side-effects exactly-once-effectively: receipt email, fulfillment, inventory decrement — driven from the committed order via an outbox, with idempotent consumers.

Out of scope (deliberately): catalog, search, cart, recommendations, fraud scoring, tax/shipping calculation, a waiting room. This problem is only the double-charge-safe submit.

• Correctness (the top invariant): at-most-one charge and at-most-one order per idempotency key, under arbitrary retries, crashes, and a single-node failure at any step. This dominates every other property.
• Availability: 99.9% on the confirm path. A brief write outage (failover) is acceptable because idempotency makes the client's retry safe.
• Latency: confirm p99 5–10s (payment-provider-dominated); an idempotent replay p99 < 50ms (one indexed row read); concurrent-duplicate rejection < 30ms.
• Durability: RPO=0 on orders and charges (sync replication) — a lost committed order is a real double-charge exposure on the retry. Orders retained 7+ years (financial). Idempotency keys retained for the 24h dedup window.
• Consistency: the order + idempotency-response + outbox commit is ONE SERIALIZABLE transaction. The dedup authority is the SQL DB, never a cache.
• Overload behavior: a retry storm must be shed, not passed through — accepted traffic bounded to ~1.2× steady-state; excess returns 429 Retry-After (key preserved).

Anchor: a large merchant on a flash-sale / Black-Friday peak, where checkout is bursty and retries spike exactly when the payment provider is stressed.

Per-tier QPS (formulas, then numbers — 5M orders/day, 20× peak, 1.3 attempts/order):

• Order rate: ordersPerDay / 86400 ≈ 58/s avg; at 20× peak ≈ 1,160 orders/s.
• Submit attempts (API-facing, incl. retries): ordersQpsPeak × retriesPerOrder ≈ ~1,500/s at peak. This is what the gateway + order-svc actually receive.
• Retry-storm ceiling (the shed target): ordersQpsPeak × retryStormMultiplier ≈ ~5,800/s worst case during a downstream blip. The gateway's retry budget caps accepted traffic near 1.2× steady (~1,800/s) and sheds the rest — this number is the thing we are defending against, not provisioning for.
• Payment charges (deduped): equals the order rate — ~1,160/s at peak. Dedup means retries do NOT multiply provider calls.
• In-flight charges (Little's law): chargesQpsPeak × p99_seconds ≈ 1,160 × 2 ≈ ~2,320 concurrent provider calls — the connection-pool + timeout budget must cover this.
• Async side-effects: ordersQpsPeak × fanoutPerOrder ≈ ~4,640 events/s through Kafka. Trivial at RF=3.

Bytes economics — explicitly checked: every payload here is JSON < 10KB (an order, a charge, an event). There is no large-body / direct-to-storage concern — do NOT import upload/CDN patterns from image or video canonicals. Service tiers correctly sit in the data path.

Storage:

• Idempotency keys (24h window): ordersPerDay × 1KB ≈ ~5 GB for the window (key + request_hash + cached response). Across 8 shards, sub-GB each. With two live daily partitions, ~10 GB/shard ceiling.
• Orders (7yr): ordersPerDay × 365 × 7 × 2KB ≈ ~26 TB raw across 8 sharded primaries. Fine.
• Order events (Kafka, 7-day retention): ~4,640/s × 1KB × 7d ≈ ~2.8 TB — trivial for a 3-broker cluster.

Architectural flip points (where the shape changes, not just the numbers):

• Redis-only dedup breaks the instant it evicts. A cache with a TTL and an eviction policy will, under memory pressure, silently drop a key that a delayed retry still references — and double-charge. The dedup authority MUST be durable (SQL). Redis is legitimate only as an optional fast in-flight lock, never as the record of truth.
• The dedup window must be ≥ the client's max retry horizon. If a key can be reaped before the last possible retry arrives (e.g. an app relaunched next morning), you get a second charge. Sizing the window is a correctness knob, not a cost knob — align it with the PSP (24h).
• Single-shard commit is a hard requirement. Sharding by hash(user_id) keeps a user's retries and their order on one shard so the claim and the order commit are one local transaction. If order and idempotency ever land on different shards, you have re-created the cross-store dual-write you were trying to avoid.

POST /orders
Content-Type: application/json
Authorization: Bearer <session>
Idempotency-Key: 73c8e8e0-3a2d-4f5b-8d2e-1c2b3a4d5e6f   # client-minted v4 UUID, one per Pay intent

{
  "cart_id": "c_9931",
  "amount_cents": 48200,
  "currency": "usd",
  "payment_token": "pm_card_visa_xxxx"
}

201 Created
{ "order_id": "o_ab12cd", "charge_id": "ch_3Pxyz...", "status": "confirmed" }

# --- the same key, replayed after a dropped response: returns the ORIGINAL 201, no re-charge ---

409 Conflict
{ "error": "request_in_progress" }   # a sibling with the same key is mid-flight; retry after a short delay

422 Unprocessable Entity
{ "error": "idempotency_key_reused_with_different_body" }   # request fingerprint mismatch

504 Gateway Timeout + Retry-After
# order-svc contract: client retries on 504 with the SAME key → resumes / returns cached 201 within 24h

429 Too Many Requests + Retry-After
# retry-budget shed at the gateway during a storm — key preserved, back off and retry

POST /orders/:order_id/cancel
Idempotency-Key: 8a2f4c6e-1b3d-4e5f-9a7b-2c4d6e8f0a1b

200 { "order_id": "o_ab12cd", "status": "canceled", "refund_status": "pending" }

Response-caching rule (matches Stripe): the first request's status + body is cached for the key and replayed for both success and error (including a 500). Not cached: validation failures (400/422) and 409 concurrent-conflicts — those never began execution, so they are safely retriable rather than sticky.

idempotency_keys (Postgres, sharded by hash(user_id), partitioned by key_date) — Brandur's shape:

PK (user_id, key, key_date). key_date is a pure function of the key, so a retry always targets the same live partition and still conflicts on insert. A daily DROP PARTITION reaper bounds the table to the dedup window (two live partitions cover 24h across midnight).

orders (Postgres, same shard, same txn):

UNIQUE (idem_key) — the belt-and-braces guarantee that one key ⇒ at most one order row, even if the application logic is bypassed.

outbox (Postgres, same shard, same txn): (outbox_id, topic, payload jsonb, created_at) — the CDC relay reads here and publishes to Kafka, then advances the WAL slot.

Database choice — recommended: sharded Postgres. ACID across orders + idempotency_keys + outbox in ONE transaction; a UNIQUE constraint as the last-line dup defense; SERIALIZABLE isolation for the commit phase; mature ops tooling. Why not Redis for dedup? It is not durable — eviction under memory pressure drops a key a delayed retry still needs, and the retry double-charges. Why not DynamoDB? Conditional writes work for the claim, but the order+outbox+idempotency atomicity wants a real multi-row transaction; TransactWriteItems caps at 100 items / 4MB and complicates the outbox. Why not Spanner/CockroachDB? Fine if you need geo-distributed serializable writes, but +50% write latency and 3× cost — the commit is single-shard by construction, so the cost isn't warranted.

The load-bearing flow (submit):

1. Client mints one Idempotency-Key at payment-sheet open and re-sends it on every retry (full-jitter backoff, capped attempts).
2. API Gateway rejects a keyless POST /orders (400), rate-limits per user, and applies a retry budget — during a storm it sheds excess as 429 Retry-After so amplification can't reach origin. It forwards the key unchanged.
3. Order Service runs the recovery-point state machine over Postgres:

• Claim the key in its own txn (ON CONFLICT DO NOTHING RETURNING). If the row is finished, return the cached response — done, no charge. If it's freshly locked_at, return 409. Else resume from its recovery_point.
• started → charge the Payment Provider, forwarding the key (the one foreign state mutation) → advance to charge_created.
• charge_created → one SERIALIZABLE txn: INSERT order + INSERT outbox + UPDATE the idempotency row to finished with the cached response → return 201.

1. CDC Relay (Debezium) tails the WAL, publishes order.confirmed from the outbox to Kafka; the Fulfillment Worker consumes it and does receipt + fulfillment idempotently (keyed on order_id).
2. Reconciler sweeps any idempotency row stuck below finished past its lock timeout and drives it to completion or refunds it — the backstop for a client that charged and never came back.

Data flow on the first successful submit: Client → Gateway → Order Service → (claim started) → Payment Provider (charge) → (SERIALIZABLE commit: order + outbox + finished) → 201. Async tail: WAL → CDC → Kafka → Fulfillment.

Data flow on a duplicate retry: Client → Gateway → Order Service → orders-db (row is finished) → return the cached 201. No charge, no order, ~50ms.

Data flow on a concurrent duplicate: two requests race the claim; the ON CONFLICT loser (or a fresh locked_at) sees the row locked → 409 in-progress; the client retries after a short delay and then hits the finished path.

Data flow on crash recovery: Order Service died at charge_created. Next retry loads the row, re-calls the provider with the same key (provider replays the original charge — no second charge), commits the order, marks finished, returns 201.

Multi-region posture (scoped out but stated): single-region CP money tier. If residency forces a second region, partition orders by region-of-origin with no cross-region locks; the idempotency claim stays local to the order's home region.

1. Double-charge under a retry storm (the headline). User mashes "Pay" 3× in 200ms. All three carry the same client key (minted at sheet-open). The Postgres ON CONFLICT claim serializes them: the first creates the started row and proceeds; the second and third either find a fresh locked_at (→ 409, retriable) or, once the first finishes, find recovery_point='finished' and return the cached 201. Exactly one charge, one order. The naive path that double-charges: charging the provider before claiming the key (all three charge), or deduping in Redis (an eviction between attempts drops the record and the retry charges again). The rule: claim in a durable store before the foreign mutation; the foreign mutation forwards the same key so the provider dedups too.

2. Charged-but-no-order (the atomicity gap). There is no transaction across Stripe and Postgres. If the provider charges and then the commit fails (deadlock, primary failover), the row is stuck at charge_created. Recovery is built into the state machine: the next retry resumes from charge_created, re-calls the provider with the same key (which replays the original charge for 24h — no second charge), commits the order, and marks finished. If the client never retries, the reconciler sweeps the stuck row (older than the lock timeout) and completes it — or refunds via a refund-scoped key if the order can no longer be honored. The invariant: no key stays below finished past a bounded window without either an order or a refund.

3. Dedup window sizing (the subtle correctness knob). The key is remembered for a window (24h). If a retry arrives after the key is reaped — an app relaunched the next morning, a delayed mobile retry — the server treats it as brand-new and charges again. So the window must be ≥ the client's maximum retry horizon and ≥ the payment provider's own window (Stripe = 24h), and the two should be aligned: if Stripe forgets the charge key before you forget yours (or vice-versa), the "provider dedups my resume" guarantee breaks. Bound growth with a daily partition drop; because key_date is derived from the key, a retry inside the window always lands in a live partition. Too short ⇒ double-charge; too long ⇒ table bloat and a slow claim (see failure scenario idempotency-table-bloat).

4. Same key, different body (misuse + attack). A client bug (or an attacker replaying a captured key) sends the same key with a different cart. If the server blindly returned the cached response, the second user would get the first user's order — a correctness and security hole. Defense: store a request fingerprint (SHA-256 of the canonicalized body) on claim; on reuse, compare. Match ⇒ serve the cached response. Mismatch ⇒ 422, and never execute or serve the wrong order. The key is scoped per-user (unique (user_id, key)), so a stolen key cannot cross accounts. This mirrors Stripe returning an error when parameters don't match the original request.

5. Retry-storm collapse (keeping retries cheap and bounded). The provider 503s for 60s; every client retries; the API sees ~5× amplification. Three layers keep it from melting: (a) client full-jitter backoff (sleep = random(0, min(cap, base·2^n))) with a hard attempt cap — full jitter flattens the synchronized spike that plain backoff leaves; (b) gateway retry budget — accept ~1.2× steady-state and shed the rest as 429 Retry-After, so a 50%-failure self-amplification (~3.5×) can't pass through and prevent recovery (Google SRE "Handling Overload"); (c) the idempotent replay is cheap — a repeated key is one indexed row read, not a re-charge, so even the retries that do get through cost almost nothing. Add a circuit breaker + dual provider so recovery is graceful. The elegance: idempotency and retry-budgeting reinforce each other — because replays are safe and cheap, aggressive client retries are tolerable; because retries are budgeted, the provider gets room to recover.

What we accepted (vs. the stronger alternative):

• Effectively-once, not exactly-once. True exactly-once across Stripe + Postgres is impossible (no distributed txn). We guarantee at-most-one-charge + at-most-one-order + at-least-once idempotent side-effects. The residual "charged-but-no-order" window is closed by recovery-point resume + reconciler, not by a magic 2PC.
• A synchronous charge on the request path (confirm p99 5–10s). The alternative — accept the order, charge async — trades a slow confirm for a "your order may fail after the fact" UX and a webhook that re-introduces the same idempotency problem. For this focused problem the synchronous charge is the honest hard case.
• Single-region money tier. Multi-region active-active writes need cross-region locks or CRDTs on the order/charge — prohibitive. A region failover is a ~30s write outage; idempotency makes the client's retry safe across it.
• Dedup authority in SQL, not Redis. We pay a Postgres round-trip on the claim (vs. a sub-ms Redis SET) to get durability. The whole problem exists because the fast-but-lossy option double-charges; the latency is worth it.
• Async side-effects (receipt/fulfillment) via the outbox. There's a ~5s gap between 201 and the receipt email. Acceptable: the user has the order_id in the response; the email is a side-effect delivered at-least-once by an idempotent consumer.

What breaks at 10× scale (hypothetical ~12K orders/s sustained):

• Single-shard claim contention — hot users or a mis-chosen shard key concentrate claims; move to more shards, keep hash(user_id) so one intent stays local.
• SERIALIZABLE serialization failures (40001) rise under contention — bounded application retries with backoff; keep the commit txn short (three inserts, no external calls inside it — the charge is outside the txn by construction).
• Idempotency partition churn — daily drops become large; move to hourly partitions or a shorter window if (and only if) it still covers the client + PSP retry horizons.
• CDC relay throughput — Debezium ~10K events/s/replica; at 12K orders × 4 fan-out = 48K events/s you need ~5 relays, or a Kafka-native outbox log.

Trace catalogue

The simulator authors 6 problem-specific traces — the journeys a senior engineer expects to walk when reviewing this design. The load-bearing insight across the first four: the path is nearly identical (Client → Gateway → Order Service → Orders DB / Payment Provider); what differs is the durable state the idempotency claim finds — that is idempotency in one sentence:

• submit-order:happy-path-first-attempt — the baseline write. Client → Gateway → Order Service → (claim started) → Payment Provider (charge) → (SERIALIZABLE order + outbox + finished) → 201. Budget ~2.5s (provider-dominated).
• submit-order:duplicate-retry-replay — the load-bearing dedup. A repeated key: Client → Gateway → Order Service → orders-db (row finished) → return the cached 201, no re-charge. Budget ~50ms.
• submit-order:concurrent-duplicate-inflight — two identical requests race the claim; one proceeds, the other sees a fresh locked_at → 409 in-progress; client backs off. Budget ~30ms.
• submit-order:crash-recovery-resume — Order Service died at charge_created. The retry resumes: load row → re-call provider (cached charge, same key, no second charge) → commit order → finished. Budget ~1.5s. (The same-key-different-body → 422 fingerprint case ships as the key-reuse-wrong-body failure scenario below.)
• submit-order:async-fulfillment-outbox — the exactly-once-effectively side-effect. orders-db WAL → CDC → Kafka → Fulfillment Worker (idempotent receipt + fulfilled_at WHERE NULL). Budget ~5s.
• submit-order:reconcile-charged-no-order — the abandoned-intent backstop. Reconciler sweeps a stuck charge_created row (client never retried) → completes the order, or refunds via a refund-scoped key. Budget ~60s.

Failure scenarios we model

6 chaos scenarios, each grounded in a cited real-world precedent:

• double-submit-network-blip (process) — the response to a successful POST is dropped; the client retries; the design must produce one charge and one order. Stripe's idempotency rationale is the canonical precedent.
• payment-provider-blip-retry-storm (deps) — provider 503 for 60s → client retry amplification ~5× → gateway retry-budget shed + client full-jitter backoff hold the line (AWS "Timeouts, retries, and backoff with jitter"; Google SRE "Handling Overload").
• charged-but-no-order-commit (data) — provider charged, then the Postgres commit failed (deadlock / primary failover). Recovery-point resume + reconciler close the gap with no second charge (Brandur recovery points).
• idempotency-window-expiry-double-charge (process) — a delayed retry arrives after the 24h dedup window reaped the key → a second charge. Mitigation: window ≥ max client retry horizon AND aligned with the PSP's 24h window.
• key-reuse-wrong-body (correctness) — a key is reused for a different cart (bug or attacker replay); the request-fingerprint mismatch must return 422 and never serve the first order — mirrors Stripe's parameter-mismatch error.
• idempotency-table-bloat (process) — the daily partition-drop reaper fails for days; idempotency_keys grows unbounded; the unique-index probe on the claim slows every confirm. Page on idempotency_keys.size_gb per shard.