Concept 15: Idempotency & Payment Gateways — Exactly-Once Money in an At-Least-Once World

System Design Bible — File 15 Difficulty: ★★★★☆ Prerequisites: File 03 (Rate Limiting — retries, backoff, and the retry-storm problem), File 07 (Message Queues — delivery guarantees, why exactly-once delivery is impossible, the Two Generals Problem), File 08 (Consensus & Replication — fencing tokens, the unreliable network), File 10 (Microservices — Sagas, the transactional outbox, the dual-write problem), File 11 (Databases — ACID, transactions, unique constraints, isolation), plus the fundamentals unpacked in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

This file sits at the intersection of two things: a mathematical property (idempotency) and the highest-stakes workload in software (moving money). Four ideas make everything else in the file obvious. Read them slowly — every later section leans on them.

0.1The ambiguous failure: a timeout tells you nothing#

Here is the single fact that creates this entire file. Your service calls another service — say, "charge this card $50" — and the call times out. What happened? There are exactly three possibilities, and you cannot distinguish them:

From your side, all three look identical: silence. This is File 08 §0.2's "you can never be sure whether a silent node is dead or just unreachable," now with money attached, and it is provably unfixable — File 07 §5.2's Two Generals Problem showed that no finite number of messages over an unreliable channel can create certainty on both sides. No amount of engineering removes the ambiguity; the network is physically capable of losing any message, including the acknowledgement.

Now feel the dilemma. After the timeout, you have two choices, and both are wrong:

This dilemma — retry and risk duplication, or give up and risk loss — is the entire motivation for idempotency. Hold this: a timeout is not "it failed"; a timeout is "I don't know," and with money, "I don't know" is unacceptable in both directions.

0.2Retries are mandatory, so duplicates are mandatory#

Given §0.1, you might think "fine, we'll just be very careful and never retry payments." That position collapses immediately, because retries happen whether you code them or not, at every layer of the stack:

So the honest system-design position, and the one to state in an interview, is: duplicate requests are not an edge case; they are a permanent, load-bearing feature of any distributed system. The choice you actually get to make is not "duplicates or no duplicates" — it's "do duplicates cause duplicate effects, or not." Making the answer "not" is idempotency's job. Hold this: you cannot prevent duplicate requests; you can only make duplicate requests harmless.

0.3What makes money special: irreversibility and the ledger mindset#

Most data bugs are quietly fixable. A stale cache entry expires; a wrong denormalized copy gets re-synced; a lost analytics event is a rounding error. Money is different in three ways that shape every design decision in this file:

Money movements are side effects on systems you don't control. When you write a row to your database, you can roll it back (File 11's transactions). When you tell a card network to move $50, the movement happens inside banks — external systems with their own state, their own timelines, and no concept of your transaction. There is no ROLLBACK for a charge; there is only a second, compensating movement (a refund), which is itself a new operation that can fail, takes days to land on the customer's statement, and may cost you fees. This is precisely why File 10's Sagas (sequences of local transactions with explicit compensations) exist — cross-system money flows are the canonical saga.

Every discrepancy is visible and adversarial. A customer will notice a double charge on their statement (and their bank offers them a formal weapon for it — the chargeback, §2.4). A finance team will notice when your database says you earned $1,000,000 but the bank deposited $999,950. Payment systems are therefore held to a standard no other system is: the books must balance, to the cent, provably. This is why serious payment systems are built as ledgers — append-only records of every money movement, never updated in place, where the current balance is derived by summing entries rather than stored as a mutable number. (You've met this idea twice: File 07's event log as source of truth, and File 11's WAL. An accounting ledger is the 700-year-old original.)

Sub-Concept: Double-Entry Bookkeeping. The ledger discipline banks have used since the 15th century, and the one payment engineers adopted wholesale. Every movement of money is recorded as two entries that must sum to zero: a debit from one account and a matching credit to another. "Customer pays merchant $50" is never one row — it's customer_cash −50 and merchant_receivable +50, written atomically in one database transaction (File 11's atomicity doing real work). Why it matters: money can now never be created or destroyed by a bug, only misplaced — and misplacements are mechanically detectable, because the invariant sum(all entries) = 0 is checkable at any moment. A single-entry system ("just update the balance column") can silently drift; a double-entry system can only be loudly wrong. Benefit: every discrepancy is detectable and traceable to the exact entry. Cost: more rows, more modeling discipline, and balances are computed rather than read. Mitigation: materialized running balances (File 04's materialized-view idea), rebuilt from entries whenever in doubt.

**Hold this: money operations are irreversible side effects on external systems, so "undo" means compensate, and correctness means the ledger balances — not "the request succeeded."**

0.4Idempotency, precisely: f(f(x)) = f(x)#

The term comes from mathematics. An operation f is idempotent if applying it twice (or twenty times) produces the same result as applying it once: f(f(x)) = f(x). The absolute-value function is idempotent — abs(abs(-5)) = abs(-5) = 5. Multiplication by zero is idempotent. Addition of one is not: (x+1)+1 ≠ x+1.

Translate to systems, and a sharp line appears through every operation you've ever written:

Notice what the examples reveal: the difference is whether the operation carries its own intended end-state (idempotent) or describes an increment relative to current state (not). And notice the trap: a payment is irreducibly increment-shaped — "move $50" is a step by nature; you cannot rephrase "charge the customer" as a destination. So payments can never be made idempotent by rewording the operation. Instead, we make them idempotent by remembering which requests we've already performed — attaching a unique identity to each intent and refusing to execute the same intent twice. That's the idempotency key (§2.1), and it's the heart of this file. Hold this: idempotency is either natural (the operation states a destination) or manufactured (the system deduplicates intents by identity) — and payments always need the manufactured kind.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

Idempotency, in system design, is the property that performing the same operation multiple times has exactly the same effect as performing it once — so that retries, duplicate deliveries, and impatient double-clicks are harmless rather than harmful. For operations that aren't naturally idempotent (anything that creates, increments, or moves), idempotency is manufactured by giving each logical operation a unique identity (an idempotency key) and having the server execute each identity at most once, returning the recorded result of the first execution to every subsequent duplicate.

A payment gateway is the service that sits between a merchant's application and the banking system — it accepts a charge request over an API, speaks the card networks' protocols on your behalf, shields you from handling raw card data (§2.5), and returns a result. Stripe, Adyen, Braintree, PayPal, and Razorpay are gateways. The gateway is where your clean HTTP world meets the decades-old, batch-oriented, multi-party world of banks — and it's the boundary across which the ambiguous failures of §0.1 hurt the most.

The analogy that holds: a hotel receptionist with a guest ledger. You walk up and say "check me in for room 412." The receptionist doesn't just hand over a key — she first checks the ledger. If your name is already written next to 412, she says "you're already checked in" and hands you the same key again (she does not check you in twice and bill you twice). If your name isn't there, she writes it down first, then hands you the key. The ledger is what makes "check me in," said five times by a confused, jet-lagged guest, cost exactly one night. The idempotency key is your name; the key-store is her ledger; and the crucial detail — she writes before she acts — is the exact ordering that §5 will show the server must follow.

1.2"The Why" — The Three Walls That Forced This to Exist#

Wall 1 — The network is unreliable, and this is permanent physics, not a bug backlog. §0.1 in one line: any request can produce a timeout that means "maybe." The Fallacies of Distributed Computing (File 08) start with "the network is reliable" precisely because every generation of engineers re-learns that it isn't. For read operations, ambiguity is cheap — read again. For money, ambiguity is a customer charged twice or an order lost. Something architectural must convert "maybe" into a safe retry, because nothing can convert "maybe" into certainty (Two Generals, File 07).

**Wall 2 — Correct reliability engineering requires retries, and retries multiply effects.** Everything this bible teaches about resilience — client backoff (File 03), queue redelivery (File 07), LB failover re-sends (File 01), crash-recovery job re-runs — works by re-executing things. Reliability machinery and payment safety are therefore in direct tension: the machinery that guarantees your request is eventually processed is the same machinery that threatens to process it more than once. Idempotency is the reconciliation of that tension — it's what lets you keep aggressive retries (great for availability) without duplicate effects (fatal for money). Recall File 07's most important sentence: "at-least-once delivery + idempotent consumers = effectively-once processing." This file is that sentence, industrialized.

Wall 3 — Money crosses trust and system boundaries, where distributed transactions don't reach. A checkout spans your database, the gateway, the card networks, and two banks. There is no ACID transaction (File 11) across those parties, and 2PC (File 04) is unavailable — the bank does not join your transaction. So the atomicity you're used to ("either everything committed or nothing did") simply does not exist at the payments boundary, and must be replaced by a weaker but achievable discipline: idempotent steps + recorded state + compensations + reconciliation — each step safe to repeat, every transition recorded, mistakes undone by explicit counter-operations, and the whole thing audited against the bank's version of the truth (§6.4).

1.3What It Solves — And the Price It Charges#

Every row has a price — that's Rule 5, and it's the point. The headline trade: idempotency converts a correctness problem you cannot solve (exactly-once delivery) into an engineering problem you can (at-most-once execution per recorded intent), and charges you a durable state store plus discipline at every boundary.

2The Recursive Sub-Concept Tree#

Every term the rest of the file uses, from scratch.

2.1Sub-Concept: The Idempotency Key#

An idempotency key is a client-generated unique identifier attached to a single logical operation — one checkout, one transfer, one refund — that travels with every retry of that operation. Typically a UUID (Universally Unique Identifier — a 128-bit random number, e.g. f81d4fae-7dec-..., with enough randomness that two independently generated UUIDs will never collide in practice; File 04 met them as cross-shard unique IDs), sent as an HTTP header (Idempotency-Key: f81d4fae-..., per Stripe's convention and the IETF draft standard that copied it).

Three properties make a key correct, and each is a real design decision:

**It identifies the intent, not the attempt. The key must be generated once per logical operation** and reused across every retry of that operation. Generate it when the user lands on the checkout page (or when your worker first picks up the job) — not inside the HTTP call, where a retry loop would mint a fresh key per attempt and defeat the whole mechanism. This is the #1 implementation bug in the wild: a beautifully built server-side dedupe store, fed by a client that generates a new UUID inside its retry wrapper. Every retry looks like a new intent; the customer gets charged once per timeout.

**It is generated by the client,** because only the client knows where one intent ends and another begins. The server sees two identical-looking POST /charge {amount: 50} requests and cannot know whether that's one intent retried or a customer legitimately buying the same item twice in a row. The key is the client telling it which.

It must be scoped and stored deliberately. Scope keys per account/merchant (so two tenants' random collisions can't cross-contaminate — File 03's rate-limit-key scoping lesson, replayed) and retain them long enough to outlive any plausible retry horizon — Stripe prunes after 24 hours; systems with slower retry sources (nightly batch jobs, mobile clients that come back online days later) need longer.

2.2Sub-Concept: Delivery Semantics Recap — and Where "Exactly-Once" Actually Lives#

File 07 §5 covered this in full; here is the load-bearing recap. At-most-once = never duplicated, may be lost (unacceptable for money — a lost payment is a lost order or an un-recorded debt). At-least-once = never lost, may be duplicated (the correct default for money — duplicates are survivable if the consumer is idempotent). Exactly-once delivery = provably impossible over an unreliable network (Two Generals). What is achievable is **exactly-once *effect***: at-least-once delivery + deduplication by operation identity + atomic record-of-completion. Every payment system on earth is built on that formula. When an interviewer says "make this payment exactly-once," the senior move is to say: "exactly-once delivery is impossible; I'll give you at-least-once delivery with idempotent execution, which yields exactly-once effect — and here's the key protocol that does it."

2.3Sub-Concept: The Payments Cast — Gateway, Processor, Networks, Acquirer, Issuer#

The word "gateway" hides a chain of distinct parties. Naming them precisely is a credibility signal, and the failure modes of §0.1 exist between every adjacent pair:

So "charge the card" really means: merchant → gateway → processor → network → issuer, a decision flows back along the same path, and days later money physically moves issuer → network → acquirer → merchant in a batch called settlement (§2.4). Six parties, five network boundaries, each boundary an independent source of the §0.1 ambiguity — which is why idempotency has to exist at every hop, not just yours.

2.4Sub-Concept: The Payment Lifecycle — Authorization, Capture, Settlement, Refund, Void, Chargeback#

A card payment is not one event; it's a state machine whose stages exist for good reasons:

2.5Sub-Concept: PCI DSS & Tokenization — Why Card Numbers Never Touch Your Servers#

PCI DSS (Payment Card Industry Data Security Standard) is the card networks' mandatory security standard for anyone who stores, processes, or transmits card numbers — hundreds of controls, annual audits, and severe liability on breach. Full compliance is a permanent, expensive engineering program, so the entire industry converged on one move: never let the card number touch your systems at all.

The mechanism is tokenization: the customer's browser/app sends the raw card number directly to the gateway (via the gateway's own JavaScript/SDK — the number travels from the user's device to Stripe's servers without passing through yours), and the gateway returns a token — an opaque reference like tok_a1b2c3 that means "card #4242... as stored in our vault." Your servers only ever see, store, and charge the token. A stolen token is useless to an attacker (it only works via your gateway account), so your PCI scope collapses to nearly nothing. Benefit: you get to build a payment system without becoming a card-security company. Cost: deep vendor coupling — your saved cards live in the gateway's vault, which makes switching gateways a genuine migration project (some gateways support vault export; negotiate this before integrating). Mitigation for the coupled: network tokens and multi-gateway vault services exist precisely to loosen this lock-in.

2.6Sub-Concept: The Dual-Write Problem (recap from File 10, because payments is where it bites hardest)#

You must do two things when a payment succeeds: write your database ("order 42 is paid") and produce a side effect elsewhere (call the gateway, or publish an order-paid event). Two systems, no shared transaction — so a crash between them leaves you half-done in one of two terrible ways: DB says paid but gateway never charged (you ship for free), or gateway charged but DB never recorded it (customer pays for nothing). File 10 §5.4's transactional outbox is the standard fix — write the business change and a row describing the pending side effect in one local ACID transaction, then have a relay execute the side effect (idempotently, with a key stored in the outbox row — so even the relay's own crash-retries are safe). §6.1 traces this end-to-end.

2.7Sub-Concept: The Payment State Machine#

Because a payment is a multi-day, multi-party process (§2.4), your system must model it as an explicit state machine — a single record per payment whose status column moves through defined transitions:

 CREATED ──► PENDING ──► AUTHORIZED ──► CAPTURED ──► SETTLED
                │             │              │
                ▼             ▼              ▼
             FAILED         VOIDED        REFUNDED (partial/full)

Two disciplines make the state machine load-bearing rather than decorative. (1) Transitions are guarded: an update is written as UPDATE payments SET status='CAPTURED' WHERE id=42 AND status='AUTHORIZED' — the WHERE clause makes illegal jumps (capturing a failed payment, refunding twice) structurally impossible, and — see it? — makes the transition naturally idempotent: running it twice matches zero rows the second time. This is §4.4's compare-and-swap pattern hiding in plain SQL. (2) Every transition is recorded with its external references (the gateway's charge ID, timestamps, raw responses), because when reconciliation (§6.4) finds a discrepancy three days later, this record is the only forensic evidence you have.

3Deep-Dive Mechanics — The Life of a Card Payment#

3.1The Full Flow, End to End#

Trace one $50 checkout through every party. This is the diagram to reproduce on a whiteboard:

 CUSTOMER'S BROWSER                YOUR BACKEND                    GATEWAY (Stripe-like)         BANKS
 ──────────────────                ────────────                    ─────────────────────         ─────
 1. Checkout page loads
    → backend creates payment row (status=CREATED)
    → generates IDEMPOTENCY KEY K for this checkout        ◄─ key = one per INTENT (§2.1)
 2. Card form (gateway's JS SDK)
    card number ──────────────────────────────────────────► 3. tokenize: card → tok_a1b2c3
    (raw PAN NEVER touches your servers — §2.5)   ◄──────────  returns token to browser
 4. "Pay" clicked:
    POST /pay {token, K} ────────► 5. load payment row; status=CREATED? proceed
                                   6. write K to key-store (state=IN_FLIGHT)  ◄─ §5's protocol
                                   7. POST /v1/charges
                                      Idempotency-Key: K
                                      {amount:5000, currency:usd,
                                       source: tok_a1b2c3} ──► 8. gateway checks ITS key-store for K
                                                                  (dedupe at the gateway hop too!)
                                                               9. AUTH request ──► network ──► ISSUER:
                                                                  funds? fraud? → APPROVED, hold $50
                                                              10. charge ch_9f8e recorded
                                   11. response {id: ch_9f8e,  ◄── status: authorized}
                                   12. ONE DB TXN: payment row → AUTHORIZED (guarded CAS, §2.7)
                                       + ledger entries (double-entry, §0.3)
                                       + outbox row: "publish order-paid" (§2.6)
                                       + key-store: K → COMPLETED + saved response (§5)
 13. ◄─ 200 {order confirmed}      14. later: CAPTURE (on shipment) — its own idempotency key!
                                   15. T+1..3 days: SETTLEMENT batch lands at your acquirer;
                                       nightly RECONCILIATION compares gateway reports vs your ledger (§6.4)

Read the failure windows off the diagram — each numbered gap is a place a crash or timeout creates the §0.1 ambiguity:

3.2Why Every Hop Needs Its Own Idempotency#

Notice the diagram contains three separate dedupe layers: the browser→backend hop (your key-store), the backend→gateway hop (the gateway's key-store, fed by the same K), and gateway→networks (the networks have their own transaction-ID dedupe within the ISO 8583 protocol). This is not redundancy for its own sake — each hop has its own independent timeout ambiguity, so each hop needs its own at-most-once guarantee. Idempotency doesn't compose automatically across hops; it must be plumbed: your backend passing its key K through to the gateway (rather than minting a new one per gateway attempt) is what stitches hop 2's guarantee to hop 1's. The interview phrase: "idempotency keys must propagate end-to-end through the call chain; a fresh key at any hop reopens the duplicate window at that hop."

4Idempotency Strategies — Exhaustive Breakdown#

There are five distinct ways to make an operation idempotent. They form a ladder from "free" to "full protocol," and real systems use several at once — one per layer. Rule 4 treatment for each.

4.1Natural Idempotency (design the operation as a destination)#

What it is. Phrase the operation so repetition is inherently harmless — state the end-state, not the increment (§0.4).

How it works. Replace step-shaped operations with destination-shaped ones: SET status='CANCELLED' not toggle status; PUT /users/42/address {…} (store exactly this) not POST /users/42/addresses (add another); "set subscription plan to Pro" not "upgrade one tier." Worked example: a driver-location service (File 12's geo template) that receives POST /drivers/7/move {dx: 0.01} will corrupt positions under redelivery; rephrased as PUT /drivers/7/location {lat: 40.7, lon: -74.0}, ten redeliveries land on the identical final state.

Why it works. The operation carries its own target, so executing it is assignment, and assignment is mathematically idempotent — no memory of past requests needed at all.

Pros. Zero infrastructure, zero storage, zero latency cost; immune to every duplicate source simultaneously; no key lifecycle to get wrong. Cons. Many operations cannot be phrased this way — anything that creates ("new order") or accumulates ("charge $50," "append a message") is irreducibly a step. Also subtly loses information under reordering: two concurrent PUTs means last-writer-wins, which may not be the newest data (File 08's LWW hazard — mitigate with a version check, §4.4). Complexity. O(0). That's the whole appeal. When to use it. Always, wherever the domain allows — it's the first question to ask of every endpoint ("can this be a PUT?"). It is not sufficient for payments, which are step-shaped by nature (§0.4) — for those, continue down the ladder.

4.2Unique-Constraint Deduplication (let the database refuse the duplicate)#

What it is. Put a unique index (File 11 §5: an index the database enforces uniqueness through — a second insert with the same value is rejected with a constraint-violation error) on a column that identifies the operation, and let the insert itself be the dedupe check.

How it works. The orders table gets UNIQUE(checkout_id) (or UNIQUE(idempotency_key)). Processing = INSERT order (checkout_id, …). First execution inserts; any duplicate — from a retry, a redelivered queue message, a double-click — hits the unique constraint and errors; the handler catches that specific error and treats it as success, fetching and returning the existing row. Worked example: a queue consumer (File 07) handling order-placed events at-least-once — INSERT INTO shipments (order_id, …) with UNIQUE(order_id); a redelivered event's insert bounces off the constraint; the consumer says "already shipped, ACK" and moves on.

Why it works. It piggybacks on the database's own concurrency control (File 11 §4): unique enforcement inside the storage engine is atomic even under concurrent racing inserts — two simultaneous duplicates cannot both succeed, with zero application-level locking. You are reusing the most battle-tested mutual exclusion on earth.

Pros. Tiny to implement (one index, one catch-block); race-proof by construction; no separate key-store — the business table is the dedupe record, so it can never drift out of sync with the data it protects. Cons. Only dedupes the insert itself — it does not protect the side effects around it (the gateway call before the insert happened twice anyway), does not store the original response to replay (the duplicate gets "already exists," not the full receipt the first caller got — fine for internal consumers, not for a public API), and requires the operation to map naturally onto one row in one table. Complexity. O(1) per operation; one index's write overhead (File 11 §5.3). When to use it. The default for internal, queue-driven consumers — File 07's idempotent-consumer advice, made concrete. Insufficient alone for a public payment API, where clients need response replay and multi-step protection → §4.3.

4.3The Idempotency-Key Protocol (remember every intent and its outcome)#

What it is. The full manufactured-idempotency machine of §2.1: a durable key-store mapping each client-supplied key → the operation's state (IN_FLIGHT / COMPLETED / FAILED) → the saved response, consulted before executing and written before and after the side effect. This is what Stripe's API does, and what §5 dissects line by line.

How it works (compressed — §5 has the full treatment). On request: look up the key. Never seen → atomically claim it (insert IN_FLIGHT), execute the operation, save the response into the key record, return. Seen and COMPLETED → return the saved response verbatim, executing nothing. Seen and IN_FLIGHT → another attempt is mid-execution right now; don't execute a duplicate and don't lie — return "in progress, retry shortly" (HTTP 409 Conflict or 425).

Why it works. It converts "has this been done?" — unanswerable across a network (§0.1) — into "is this key in my store?", answerable with one indexed local read. The atomic claim (unique constraint under the hood — §4.2 reused as a building block!) serializes racing duplicates; the saved response makes retries observationally identical to the first call, which is the strongest form of idempotency: the client literally cannot tell it was a duplicate.

Pros. Protects the entire handler including external side effects, not just one insert; replays full responses (public-API grade); handles concurrent duplicates correctly; composable across hops by propagating the key (§3.2). Cons. A durable store on the write path of every protected endpoint (+1 read +2 writes per request; the store must be as available as the API — it's a new critical dependency); key-lifecycle discipline pushed onto every client (§2.1's intent-vs-attempt trap); recovery logic needed for keys stuck IN_FLIGHT after a crash (§5.3); retention policy questions (24h? 7d?). Complexity. O(1) per request; storage O(requests × retention window). When to use it. Any externally exposed, non-idempotent, high-stakes write — every payment API, transfer API, order-creation API. This is the industry-standard answer, and "I'd implement Stripe-style idempotency keys" is the expected sentence in the interview.

4.4Conditional Writes / Optimistic Concurrency (compare-and-swap)#

What it is. Make each write conditional on the state it expects to be transforming, so a stale or repeated write matches nothing and becomes a no-op. The database form: UPDATE … WHERE status='AUTHORIZED' (§2.7). The HTTP form: ETag/If-Match — the server tags each resource version with an opaque ETag ("entity tag" — a version fingerprint returned in a response header); the client sends its edit with If-Match: <that etag>; the server applies the write only if the resource's current ETag still matches, else rejects with 412 Precondition Failed. Both are the compare-and-swap (CAS) idea: change X to Y only if it's currently X. (File 11 §4.3 called this optimistic locking.)

How it works — worked example. Capture flow: UPDATE payments SET status='CAPTURED', captured_at=now() WHERE id=42 AND status='AUTHORIZED'. First execution: 1 row updated → proceed to call the gateway's capture. Redelivered duplicate: 0 rows updated → the handler sees rows_affected = 0, concludes "already past this state," skips the side effect, ACKs. The state machine's guard is the dedupe.

Why it works. Idempotency here comes from state, not memory: instead of remembering request identities (§4.3), the system inspects where the entity already is. Repetition is harmless because the precondition only holds once.

Pros. No key-store, no client cooperation needed; doubles as lost-update protection (§File 11 §4.1) against concurrent different writers, which key-based dedupe doesn't address at all; trivially expressed in SQL or in DynamoDB conditional writes. Cons. Requires a modeled state machine — it protects transitions of an existing entity, so it can't dedupe creation (nothing exists to compare against — that's §4.2/4.3's job); no response replay; and "0 rows updated" is ambiguous between "duplicate" and "genuinely wrong state," so handlers must distinguish by reading the current state. Complexity. O(1); zero extra storage. When to use it. Every state transition in the payment state machine, unconditionally — it belongs underneath the key protocol as the second line of defense. Key dedupes the request; CAS guards the transition; both together survive bugs in either.

4.5Fencing Tokens (idempotency's cousin: rejecting the stale actor)#

What it is. File 08 §11.2 introduced these for split-brain; payments has the same disease. A fencing token is a monotonically increasing number issued with a lease/lock, which every downstream write must carry; the downstream rejects any write bearing a smaller token than the largest it has seen.

How it works — the payment version of the nightmare. Worker A holds the lease to process payout batch 7 and pauses for a 40-second GC (File 13's GC-pause villain, striking again). The lease expires; worker B acquires it with token 34 (A had 33) and processes the batch. A wakes, believing it still holds the lease, and fires its writes — carrying the stale token 33. The payments service, having seen 34, rejects everything token-33. Without fencing, A and B both process batch 7: not a duplicate request (different requests entirely!) but a duplicated effect from two actors both believing they're the only one.

Why it works. Monotonic tokens impose a total order on lease-holders; "reject smaller" mechanically silences every zombie from the past. It's CAS (§4.4) applied to actors instead of entities.

Pros. Closes the class of duplicates that keys can't see (two distinct actors, distinct requests, same logical work); cheap — one integer compare downstream. Cons. Requires a token-issuing lock service with strong consistency (etcd/ZooKeeper — File 08 §10.2), and every downstream must enforce the check (one non-checking service reopens the hole). Complexity. O(1) per write; one consensus-backed counter. When to use it. Whenever exclusive processing is assumed — payout batch jobs, subscription-renewal sweeps, any "exactly one worker owns this shard of work" design (File 04's partition ownership). If your design says "the lock guarantees only one worker," the interviewer's next sentence is a GC pause, and your answer is fencing tokens.

4.6Comparison Table & Decision Rule#

Decision rule, in one breath: "Design destination-shaped (natural) wherever the domain allows; dedupe creation with a unique constraint; expose money-moving APIs behind the full idempotency-key protocol with response replay; guard every state transition with a conditional write; and fence any worker that believes it holds an exclusive lease. These aren't alternatives — they're layers, and a production payment system runs all five simultaneously."

5The Idempotency-Key Protocol — A Full Implementation#

§4.3 named it; now build it, because the correctness lives entirely in the ordering details, and interviewers probe exactly those.

5.1The Key-Store Schema and the Happy Path#

CREATE TABLE idempotency_keys (
  key            TEXT      NOT NULL,
  account_id     BIGINT    NOT NULL,          -- scope per tenant (§2.1)
  request_hash   TEXT      NOT NULL,          -- fingerprint of the request body (§5.4)
  state          TEXT      NOT NULL,          -- IN_FLIGHT | COMPLETED | FAILED
  response_code  INT,
  response_body  JSONB,                       -- the saved receipt to replay
  locked_at      TIMESTAMPTZ,                 -- for stuck-key recovery (§5.3)
  created_at     TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (account_id, key)               -- the unique constraint IS the atomic claim
);

 request(K) arrives
     │
     ▼
 INSERT (K, IN_FLIGHT, hash) ── success? ──► EXECUTE the operation
     │                                          │  (gateway call, DB writes...)
     │ unique-violation                         ▼
     ▼                                       UPDATE key: COMPLETED + response  ─► return response
 SELECT existing record
     ├─ COMPLETED + same hash ──► return SAVED response (execute NOTHING)
     ├─ COMPLETED + different hash ──► 422: key reused for a DIFFERENT request (§5.4)
     └─ IN_FLIGHT ──► 409/425: "original still processing — retry with backoff"

The two orderings that carry all the correctness: claim before execute (insert IN_FLIGHT first, so a concurrent duplicate arriving mid-execution finds the claim and cannot start a second execution — the receptionist writes in the ledger before handing over the key, §1.1), and record outcome before acknowledging (save the response, then return it, so a crash after the side effect still leaves a completed record for replay... almost — see §5.3 for the honest version).

5.2Concurrent Duplicates: Why IN_FLIGHT Must Block, Not Execute#

Two identical requests race in (double-click, 40 ms apart). Request 1 wins the insert and starts executing. What does request 2 get? Not execution (that's the double-charge). Not the response (it doesn't exist yet). The only honest answer is "in progress — come back": a 409 Conflict with Retry-After (File 03 §2.4's communicative-rejection discipline). The client's retry a second later finds COMPLETED and receives the replayed response. Some implementations instead hold request 2's connection open waiting on request 1 (long-polling the key record) — friendlier to naive clients, but it ties up server resources per duplicate and risks thundering-herd pileups on a slow charge; the 409-and-retry contract is the more scalable default. Trade-off stated: fail-fast-and-retry costs client sophistication; wait-for-result costs server capacity under pileup.

5.3The Crash Windows — and the Recovery Point Pattern#

Walk every crash location, because this is the interviewer's favorite dig:

5.4The Request Fingerprint: Same Key, Different Body#

A client bug reuses key K with a different amount ($50 first, $70 retry — someone "fixed" the cart mid-retry). If you replay the $50 response, the client believes $70 was charged. So the store keeps a hash of the canonical request body (request_hash), and a key-match with a body-mismatch is rejected loudly (422 Unprocessable): "this key was already used for a different request." Never silently pick either interpretation — a mismatch means the client's intent-tracking is broken, and the only safe move is to surface it. **Detail that separates read-about-it from built-it: hash the canonicalized body (sorted keys, normalized whitespace), or innocent serialization differences between retry paths will false-positive the mismatch.**

5.5Storage Choice and Retention#

The key-store must be durable and strongly consistent — a lost claim silently reopens the duplicate window, so RAM-only Redis (File 02: volatile) is disqualified as the only store; the standard answer is the same relational DB as the payment data (the unique constraint and, crucially, the ability to update the key record inside the same ACID transaction as the business write — closing even the §5.3 window for DB-local effects), with Redis optionally layered as a read-through cache for hot key lookups. Retain keys past the longest plausible retry horizon: Stripe prunes at 24h; if you have batch jobs that retry nightly or mobile clients offline for days, size accordingly — and remember that after pruning, a very-late retry becomes a new operation, which is exactly a double charge with extra steps. Retention is a correctness parameter, not a cleanup detail.

6End-to-End Payment Correctness — Outbox, Sagas, Webhooks & Reconciliation#

The key protocol makes one hop safe. A payment system is many hops over many days; four more mechanisms complete the picture.

6.1The Transactional Outbox on the Payment Path#

The dual-write of §2.6, resolved concretely: when the charge succeeds (§3.1 step 12), one ACID transaction writes the payment-state transition, the double-entry ledger rows, the key-record completion, and an outbox row ("publish payment.succeeded", "schedule fulfillment"). A relay reads the outbox and executes each row's side effect — carrying an idempotency key stored in the outbox row itself, so the relay's crash-retries are deduplicated downstream. The event reaches Kafka (File 07) at-least-once; every consumer applies §4.2's unique-constraint dedupe. The pattern in one line: atomic intent capture, asynchronous idempotent execution — the only reliable way to couple a database write to an external effect.

6.2The Purchase Saga#

A marketplace order — reserve inventory, charge payment, create shipment — is File 10 §5.2's saga verbatim, with the payments-specific sharpening: order the steps so the irreversible one comes as late as possible. Reserve inventory first (cheap to compensate: release), charge last-but-one, and treat post-charge failures with compensations that are themselves idempotent (the refund carries its own idempotency key — §2.4's warning). If the charge succeeds but shipment creation fails permanently, the compensation chain runs: refund (keyed), release inventory (CAS-guarded), order → FAILED (state-machine transition). Every arrow in the saga is one of §4's five strategies; the saga is just their composition.

6.3Webhooks: The Gateway Calls You — At-Least-Once, Of Course#

Payments are asynchronous by nature (3-D Secure customer authentication, bank transfers that take days, disputes that arrive weeks later), so the gateway pushes events to you via webhooks — HTTP POSTs from the gateway to an endpoint you register (payment.succeeded, charge.refunded, charge.dispute.created). Three disciplines, each mapping to a file you've read:

6.4Reconciliation: The Last Line of Defense#

Everything above reduces the probability of drift; nothing reduces it to zero (you built idempotency because the network lies — the same network carries your webhooks). So every serious payment system runs reconciliation: a nightly batch that takes the processor's settlement report (the file listing every transaction the bank believes happened, with amounts and fees) and diffs it, row by row, against your ledger. Three discrepancy classes, three responses: in their report, not your ledger → your step-12 write was lost; ingest the missing charge (this is the §3.1 crash-window's final safety net). In your ledger, not their report → you believe in a charge that never settled; investigate, likely mark failed and remediate the order. Amount/fee mismatches → currency conversion or fee-schedule drift; correct the ledger with an explicit adjusting entry (never edit history — §0.3's append-only discipline). Benefit: bounded drift — any inconsistency survives at most one reconciliation cycle. Cost: a real batch subsystem (File 11's OLAP-flavored work), file-format plumbing per processor, and an operational team habit. The senior framing: idempotency prevents the mistakes you anticipated; reconciliation catches the ones you didn't. A payment system without reconciliation isn't wrong yet — it's wrong and doesn't know it.

7Pros, Cons & Trade-offs#

Benefits (with the WHY for each)#

Retries become free, so availability machinery gets un-handcuffed. With idempotency everywhere, clients can back off and retry aggressively, LBs can re-send on failover, queues can redeliver — all the File 01/03/07 resilience patterns run at full strength, because re-execution can no longer double an effect. Without it, every retry decision is a correctness gamble and teams respond by not retrying, trading correctness risk for availability loss.

**Exactly-once effect despite impossible exactly-once delivery.** The formula (at-least-once + keyed dedupe + atomic completion records) delivers the guarantee users actually care about — "I was charged once" — without violating the Two Generals impossibility. You're not beating the theorem; you're relocating the problem to where it's solvable (local atomic state).

Ambiguity gets a recovery path instead of a support ticket. Timeouts and crash windows resolve mechanically — replay the saved response, query the gateway by key, resume from the recovery point, or let reconciliation sweep it — rather than by an engineer spelunking logs at 2 a.m. to decide whether to refund someone.

Auditability falls out for free. The key-store + state machine + double-entry ledger means every money movement has a full forensic trail: which intent, which attempts, which transitions, which external IDs. Finance, compliance, and dispute-response all consume this.

Costs & Trade-offs (be rigorous)#

A durable store on your hottest write path. Every protected request costs a key-store read plus two writes, and the store must match the API's availability — you've added a critical dependency to checkout. Mitigation: same-DB placement (§5.5) folds it into transactions you're already paying for; cache reads in Redis.

**Correctness now depends on client discipline. Key-per-intent (not per-attempt) is a contract enforced by convention, and every SDK, partner, and internal team must honor it. One client generating keys inside its retry loop silently re-enables double charges — and your server-side dashboards look perfect. Mitigation:** ship SDKs that manage keys correctly by default; make keys required, not optional, on money endpoints (Stripe made them optional; several gateways now mandate them — mandatory is the safer design).

Recovery paths are code you rarely exercise and must trust completely. Stuck-key sweepers, recovery points, webhook-vs-poll races — these run in the tails of the distribution, which means they're under-tested by default. Mitigation: chaos-style fault injection on the payment path in staging (kill the worker between gateway-call and record — File 10's chaos engineering, pointed at money), and reconciliation as the backstop that catches what testing missed.

Eventual consistency is forced on you by settlement physics. Your API says "succeeded" in 800 ms; the money is real in 2 days; disputes arrive in 60 days. Product and finance must both be designed around a truth that changes over weeks — "paid" is a spectrum, not a boolean. Mitigation: the explicit state machine, surfaced honestly in internal tooling.

Vendor coupling via the vault. Tokenization (§2.5) puts your saved cards inside the gateway; leaving means migrating the vault. Mitigation: negotiate data portability up front; consider network tokens / multi-processor orchestration layers if switching-risk matters at your scale.

The senior rule: Make every hop idempotent, every transition guarded, every intent recorded — and then still run reconciliation, because the discipline above protects you from the failures you modeled, and the nightly diff against the bank protects you from the ones you didn't. In payments, defense in depth isn't a virtue; it's the design.

8Interview Diagnostic Framework (Symptom → Solution)#

9Real-World Engineering Scenarios#

9.1Stripe — The Idempotency-Key Standard, and Recovery Points#

Stripe's API is why the header is called Idempotency-Key across the industry (their design, publicly documented in engineering posts by Brandur Leach, became the IETF draft standard).

9.2Uber — Exactly-Once Effect in a High-Volume Payment Platform#

Uber's payments platform (publicly described in their engineering blog) processes money events for rides and eats at enormous volume, across flaky mobile networks — the worst-case duplicate environment.

9.3Square — Idempotency as a Public API Contract for Every Developer#

Square (Block) exposes payments to millions of small-business integrations — the long tail of developers least likely to handle edge cases — and their API design shows how you make idempotency unavoidable.

10Interview Gotchas & Failure Modes#

Classic Questions (and the crisp answers)#

"How do you prevent double charges?" Layered: client mints one idempotency key per checkout intent and reuses it across retries; server atomically claims the key before executing (unique constraint = the claim), saves and replays the first response; the key propagates to the gateway so its dedupe covers the backend→gateway hop; state transitions are CAS-guarded underneath; reconciliation catches whatever slips. Never one mechanism — layers.

"The payment provider call timed out. Walk me through it." Three indistinguishable realities: never arrived, succeeded-but-response-lost, still running (§0.1). Because I sent an idempotency key, I retry with the same key — the provider's dedupe makes this safe in all three cases. Alternative: query charge-by-key first, then act. What I never do: blind-retry without a key (case 2 = double charge) or silently give up (case 1 = lost order).

"Exactly-once payment processing — possible?" Delivery: no (Two Generals — no finite handshake certifies both sides). Effect: yes — at-least-once delivery + dedupe on a recorded operation identity + atomic completion record. Say "exactly-once effect, not exactly-once delivery" and you've passed the question.

"Why must the client generate the key? Why can't the server dedupe on request content?" Two identical {amount: 50} requests are ambiguous to the server: one intent retried, or two genuine purchases? Only the client knows where an intent boundary lies. Content-hash dedupe guesses, and both wrong guesses are bad (blocked legitimate purchase / permitted double charge). The key is the client declaring the boundary.

"What if the same key arrives with a different request body?" Reject loudly (422) via the stored request fingerprint (§5.4). Replaying the old response deceives the client about what happened; executing the new body double-charges. A mismatch means the client is broken — surface it, never guess.

"Where does the idempotency record get stored, and why not Redis?" Durable, strongly consistent, and ideally transactional with the payment data — the relational DB, so the key-completion and the business write commit atomically. Redis-only fails on durability (a lost claim silently reopens the duplicate window); use it only as a cache in front.

"Charge succeeded but you crashed before recording it. Recover." Sweeper finds the stuck IN_FLIGHT key → queries the gateway by key → adopts the truth (record the charge, or fail the key). Meanwhile the gateway's webhook independently delivers charge.succeeded (dedupe by event ID, CAS the state machine), and if both nets miss, nightly reconciliation diffs the settlement report against the ledger. Three nets, in that order.

"Why auth-then-capture instead of charging immediately?" Auth verifies and reserves without moving money; capture takes it when you've earned it (shipment). Buys you free cancellation (void the auth — no refund, no fees), fraud-review time between auth and capture, and correct behavior for delayed fulfillment. Cost: holds expire, so slow fulfillment needs re-auth logic.

Failure Modes & Mitigations#

Key-per-attempt (the classic). Client mints the UUID inside its retry wrapper; every timeout retry is a "new" operation; server-side dedupe is perfect and useless. → Mitigation: SDKs that own key lifecycle; code review rule: key generation must live at intent creation, never inside retry loops; canary-test by injecting timeouts and counting charges.

Key-store pruned before the last retry. 24h retention, but a mobile client comes back online after a weekend and replays its queued request — now a fresh operation, i.e., a double charge with a three-day fuse. → Mitigation: retention ≥ the longest client retry horizon; expire client-side retry queues before the server prunes; or make late retries query-by-key first.

Dedupe check and business write in separate transactions. SELECT key → not found → do work → INSERT key has a race: two duplicates both pass the SELECT. → Mitigation: the insert is the check (unique constraint, §4.2) — claim atomically, never look-then-leap.

Webhook applied as increments, out of order. refunded processed before succeeded leaves the state machine in a lie. → Mitigation: webhooks are hints — fetch current object state from the gateway, CAS toward it (§6.3).

Compensation double-fires. The saga's refund step gets redelivered and refunds twice — the fix became the bug. → Mitigation: compensations carry their own idempotency keys; refund amount validated against remaining refundable balance (a CAS on the ledger).

Zombie worker after lease expiry. GC pause outlives the lock; two workers process the payout batch; no request was duplicated, so keys never noticed. → Mitigation: fencing tokens enforced by every downstream (§4.5).

Silent drift with no detector. Everything "works," but fee changes / lost webhooks / a rare crash window accumulate cents of divergence for months. → Mitigation: double-entry ledger + nightly reconciliation with alerting on any non-zero diff; treat reconciliation breaks with incident-level seriousness — each one is a correctness bug with a paper trail.

11Whiteboard Cheat Sheet#

╔══════════════════════════════════════════════════════════════════════════════╗
║  IDEMPOTENCY & PAYMENT GATEWAYS — BOARD DUMP                                 ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ WHY: timeout = {never arrived | worked, ack lost | still running} — you      ║
║      CANNOT tell (Two Generals, File 07). Retries are MANDATORY (users, SDKs,║
║      LBs, queues, crash-recovery) ⇒ duplicates are a FEATURE of the system.  ║
║      ⇒ can't prevent duplicate REQUESTS; make duplicate EFFECTS impossible.  ║
║ MONEY: no ROLLBACK on external systems — only COMPENSATE (refund).           ║
║        ledger must balance ⇒ double-entry (2 rows, sum=0, append-only).      ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ IDEMPOTENT: f(f(x))=f(x).  SET x=100 ✔ | x=x−50 ✘ | DELETE ✔ | INSERT ✘      ║
║   destination-shaped ✔ / step-shaped ✘. Payments = steps ⇒ MANUFACTURE it:   ║
║   remember intents by identity, execute each at most once.                   ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ THE 5 STRATEGIES (LAYERS, not alternatives):                                 ║
║  1 NATURAL      make it a PUT/SET             free       │ not for create/$  ║
║  2 UNIQUE CONSTR INSERT is the dedupe check   1 index    │ no resp replay    ║
║  3 IDEMPOTENCY KEY claim→execute→save resp    key-store  │ ★ money APIs ★    ║
║  4 CAS/CONDITIONAL UPDATE..WHERE status=X     free       │ guards transitions║
║  5 FENCING TOKEN  reject stale lease-holders  consensus  │ zombie workers    ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ KEY PROTOCOL:  key = CLIENT-minted UUID, per INTENT (checkout), NOT per      ║
║   attempt (#1 real-world bug!). scope per account. TTL ≥ retry horizon.      ║
║   INSERT(K, IN_FLIGHT) ─uniq-violation?─► COMPLETED→replay saved response    ║
║        │ ok                               IN_FLIGHT→409 retry-later          ║
║        ▼                                  diff request_hash→422 (never guess)║
║   EXECUTE → UPDATE(K, COMPLETED, response) → return                          ║
║   claim BEFORE execute; record BEFORE ack. store = durable SQL (not Redis).  ║
║   crash windows: sweeper finds stuck IN_FLIGHT → QUERY GATEWAY BY KEY.       ║
║   multi-step handler → RECOVERY POINTS (resume, don't guess). [Stripe]       ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ PAYMENT FLOW: merchant→GATEWAY→processor→NETWORK(Visa)→ISSUER(customer bank) ║
║   money later: issuer→network→ACQUIRER(merchant bank), batch SETTLEMENT T+1-3║
║ LIFECYCLE: AUTH(hold, no money)→CAPTURE(take it)→SETTLE(days) | VOID pre-cap ║
║   REFUND post-cap (a NEW op — needs its OWN key!) | CHARGEBACK = bank-forced ║
║ PCI: tokenize — card→gateway JS directly, you store tok_… only. vault=lock-in║
║ KEY PROPAGATES END-TO-END: your K → gateway header → network txn IDs.        ║
║   fresh key at any hop = duplicate window reopened at that hop.              ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ SYSTEM GLUE:  OUTBOX  = biz write + intent row in ONE txn; relay executes    ║
║                         with key stored IN the row (dual-write, solved)      ║
║               SAGA    = irreversible step LAST; compensations keyed          ║
║               WEBHOOK = verify HMAC + dedupe event ID + fetch-state-then-CAS ║
║                         (never apply in arrival order)                       ║
║               RECONCILE = nightly diff: ledger vs settlement report.         ║
║                         idempotency stops modeled failures;                  ║
║                         reconciliation catches the unmodeled. NON-OPTIONAL.  ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ MAGIC SENTENCE: "exactly-once DELIVERY is impossible; at-least-once delivery ║
║   + keyed idempotent execution = exactly-once EFFECT."                       ║
╚══════════════════════════════════════════════════════════════════════════════╝

12One-Sentence Summary for an Interviewer#

"A payment system lives with a network that can only ever say 'maybe' — a timeout is indistinguishable from success-with-lost-ack (Two Generals), and retries are mandatory at every layer, so duplicate requests are a permanent feature, and the design goal becomes making duplicate effects impossible: the client mints an idempotency key per intent (never per attempt — the classic bug), the server atomically claims the key before executing (a unique constraint is the claim), saves and replays the first response so retries are observationally identical, and propagates the key end-to-end to the gateway so every hop's timeout is safely retryable; underneath, every payment is an explicit state machine with CAS-guarded transitions (UPDATE … WHERE status='AUTHORIZED' makes illegal and duplicate transitions match zero rows), creation is deduped by unique constraints, exclusive workers carry fencing tokens against GC-pause zombies, the DB-write-plus-side-effect pair goes through a transactional outbox, cross-service purchases run as sagas whose compensations (refunds) carry their own keys, webhooks are verified (HMAC), deduped (event ID), and treated as hints to fetch-then-CAS rather than facts to apply in order — and because all of that only stops the failures you modeled, you keep a double-entry ledger and run nightly reconciliation against the bank's settlement reports, which is the honest last line of defense; the magic sentence is that **exactly-once delivery is impossible but exactly-once effect is engineering: at-least-once delivery plus keyed, recorded, idempotent execution.**"

End of File 15. Next → File 16: Geospatial Systems (geohash, quadtrees, S2, and "find the 10 nearest drivers in 5 ms") — the index a B-tree can't build, where the trick is folding two dimensions into one sortable key. Prompt me to continue.