R3 — Idempotency: making a retried operation take effect exactly once

Prerequisite: R0. This section assumes the three guarantees, the difference between exactly-once delivery, processing and effect, and the duplicates-versus-loss asymmetry.

flowchart TD
  R["Request arrives with key"] --> I["INSERT key ON CONFLICT DO NOTHING"]
  I -->|"row returned: we own it"| P1["Phase 1: local txn + recovery_point"]
  I -->|"conflict: key exists"| S{"Stored state?"}
  S -->|finished| RET["Return stored response verbatim"]
  S -->|"started, lease valid"| C409["409 Conflict"]
  S -->|"different request hash"| C422["422 — client bug"]
  P1 --> EXT["Call rail / PSP (cannot roll back)"]
  EXT --> P2["Phase 2: record outcome"]
  P2 --> FIN["Mark finished, store response"]
  EXT -->|"crash or timeout"| REC["Lease expires, recovery worker<br/>resumes from recovery_point"]
  REC --> Q["Query rail by end-to-end reference"]
  Q --> FIN

Exactly-once effect is what payments require, and you get it by making the operation idempotent at its boundary and deduplicating retries against a durable record. This is how that is actually built.

Scenario 4 is the argument for this section in one picture: 2 cannot replay to 3.1 alone, so 3.2 and 3.3 receive the message a second time. Whether that is harmless or catastrophic is decided entirely by what follows.

The mechanism

The client generates a key (a UUID) and sends it with the request. The server stores that key immediately, in the same database it will write the business record to, and uses a unique constraint on it. Concurrent duplicates then collide at the database rather than racing through your code.

CREATE TABLE idempotency_keys (
  client_id      bigint NOT NULL,      -- keys are unique per client, not globally
  key            text   NOT NULL,      -- client-supplied, untrusted
  request_hash   bytea  NOT NULL,      -- reject same key, different body
  endpoint       text   NOT NULL,
  state          text   NOT NULL,      -- started | finished
  recovery_point text,                 -- which phase completed
  response_code  int,
  response_body  jsonb,
  locked_at      timestamptz,          -- lease, not a lock
  created_at     timestamptz NOT NULL,
  PRIMARY KEY (client_id, key)
) PARTITION BY RANGE (created_at);

The lifecycle. On arrival: insert the key, or find it. If found and finished, return the stored response verbatim — not a freshly computed one, because the world may have changed since. If found and still started and locked recently, return 409. If the request body hash differs from the stored one, reject: the client reused a key for a different payment.

Atomic phases. Split the handler into phases, each one a local transaction that also advances recovery_point. Between phases you may call a rail or a PSP, which cannot be rolled back. If the process dies mid-flight, a recovery worker picks the key up and resumes from the last recorded phase. This is the part most candidates miss: idempotency is not one wrapper, it is a small state machine with a resume path.

Transient failures are not results. A 429 or a 503 should not be stored as the final response, or the client can never retry successfully.

The timeout-after-debit case. You debited, then the rail timed out. Never blind-retry. Query the rail by your own reference, or mark the payment indeterminate and let reconciliation settle it. Every payment request carries an end-to-end reference precisely so this lookup is possible.

Scope the key, or it is a security hole. The primary key is effectively (client_id, key). If keys are global, one client can present another's key and receive their stored response — a data leak dressed as a cache hit. Reject a key whose stored client_id does not match the caller, with 404 rather than 403, so keys cannot be enumerated.

Winning the race without a distributed lock. Let the database arbitrate:

INSERT INTO idempotency_keys
       (client_id, key, request_hash, endpoint, state, locked_at, created_at)
VALUES ($1, $2, $3, $4, 'started', now(), now())
ON CONFLICT (client_id, key) DO NOTHING
RETURNING client_id, key;

Rows returned means you own the request — proceed. Nothing returned means it exists: load it and branch on state. No Redis, no lock service, no clock skew.

Leases, not locks. locked_at is a lease with a short expiry. A process that dies mid-request leaves the lease to expire, after which a recovery worker (or the next retry) may take over from recovery_point. Without the lease you get either permanently stuck keys or two workers in the same phase.

Response matrix worth memorising.

Synthetic versus natural keys. Client-facing APIs take a client-generated UUID. Internal service-to-service calls should derive the key deterministically — hash(payment_id + step_name) — so no coordination or storage is needed on the caller's side and a replayed command is inherently safe.

The consumer side is the same problem. An event consumer needs an inbox: insert the message ID into a processed-messages table in the same transaction as the effect. If the insert conflicts, you have seen it; drop it.

Commit offsets after, never before.

Never put a non-transactional side effect in the middle of a phase.

Good practices

• TTL. Keep keys at least as long as the client's maximum retry window and the rail's return window — hours, not minutes. Reap afterwards, or the table becomes your largest.
• Side effects you cannot roll back. Emails, webhooks and notifications belong after the commit, driven off the durable record, and should carry their own idempotency key downstream.
• How to test it. Fire the same request 100 times concurrently and assert exactly one ledger effect. Then kill the process between each phase and assert the recovery path completes it once. If you have done this in production, say so — it is a strong concrete detail.

The phase state machine

The handler in this example has five steps: Handler1 → External system 1 → Handler2 → External system 2 → Handler3. The request is fulfilled only when Handler3 commits. Three columns on the key row carry all the state.

The rule that makes external calls safe: record intent before the call, record outcome after it. Two commits bracket every external call, so a crash is always interpretable.

Derived keys matter here: K1 = hash(request_key + "ext1") and K2 = hash(request_key + "ext2") are deterministic, so a resumed attempt presents the same key the dead attempt used, and the external system treats it as a replay rather than a second instruction.

Diagram 1 — happy path

sequenceDiagram
  autonumber
  participant C as Client
  participant S as Payment service
  participant DB as Database
  participant E1 as External system 1
  participant E2 as External system 2

  C->>S: POST /payments with Idempotency-Key K
  S->>DB: INSERT key K, state=started, locked_at=now, recovery_point=null
  DB-->>S: row inserted, this attempt owns the request
  S->>DB: TXN Handler1 work + recovery_point=H1_DONE + locked_at=now
  S->>DB: TXN recovery_point=EXT1_SENT, derived key K1, attempt=1
  S->>E1: call, Idempotency-Key K1
  E1-->>S: 200, result R2
  S->>DB: TXN store R2 + recovery_point=EXT1_DONE + locked_at=now
  S->>DB: TXN Handler2 work using R2 + recovery_point=H2_DONE + locked_at=now
  S->>DB: TXN recovery_point=EXT2_SENT, derived key K2, attempt=1
  S->>E2: call, Idempotency-Key K2
  E2-->>S: 200, result R3
  S->>DB: TXN store R3 + recovery_point=EXT2_DONE + locked_at=now
  S->>DB: TXN Handler3 work + state=finished + response stored + locked_at=NULL
  S-->>C: 201 Created, response body

In words. The insert is the admission control: because (client_id, key) is the primary key, exactly one concurrent attempt gets a row back and owns the request. Every phase is its own transaction that commits the business work and the new recovery_point together — so there is no window where work exists without a marker, or a marker without work. locked_at is refreshed at each boundary, which is what tells a watching recovery worker that the owner is alive rather than wedged. Before each external call the server commits EXT_SENT with the derived key; after the call it commits the outcome. The response body is written only in the final transaction, alongside state=finished, so nothing can return a result for a request that is not actually complete. Clearing locked_at at the end is hygiene: a finished row needs no lease.

Diagram 2 — client retries before the request is fulfilled

sequenceDiagram
  autonumber
  participant C as Client
  participant A as Server instance A
  participant DB as Database
  participant B as Server instance B
  participant E1 as External system 1

  C->>A: POST with key K
  A->>DB: INSERT K, state=started, locked_at=t0
  DB-->>A: inserted, A owns it
  A->>DB: TXN Handler1 + recovery_point=H1_DONE + locked_at=t1
  A->>E1: call with K1, slow response
  Note over C: client's HTTP timeout fires, it retries
  C->>B: POST with the same key K
  B->>DB: INSERT K ON CONFLICT DO NOTHING
  DB-->>B: no row returned, the key already exists
  B->>DB: SELECT state, request_hash, locked_at, response
  DB-->>B: started, hash matches, locked_at=t1 is fresh
  B-->>C: 409 Conflict + Retry-After, no work done
  E1-->>A: 200, result R2
  A->>DB: EXT1_DONE, then Handler2, EXT2, Handler3
  A->>DB: TXN state=finished + response stored + locked_at=NULL
  A-->>C: 201 Created
  C->>B: a later retry with key K
  B->>DB: SELECT
  DB-->>B: finished + stored response
  B-->>C: 201 with Idempotency-Replay true, byte-identical body

In words. The retry never reaches any handler. ON CONFLICT DO NOTHING returns no row, which is the signal that someone else owns this request, and the branch is decided entirely by what is on the row. state=started with a fresh locked_at means an attempt is genuinely in flight, so the correct answer is 409 with a Retry-After — not 200, because there is no result yet, and not 500, because nothing has failed. Two variants matter: if request_hash differs from the stored one the answer is 422, since the client has reused a key for a different payment and processing it would be the worst possible outcome. And once A finishes, the same retry path finds state=finished and returns the stored response verbatim with a replay marker — the client cannot tell which attempt did the work, which is the entire point.

Diagram 3 — timeout while talking to External system 2

sequenceDiagram
  autonumber
  participant C as Client
  participant S as Payment service
  participant DB as Database
  participant E2 as External system 2

  Note over S,DB: state=started, recovery_point=H2_DONE, lease held
  S->>DB: TXN recovery_point=EXT2_SENT, derived key K2, attempt=1
  S->>E2: call with Idempotency-Key K2
  Note over S,E2: no response inside the timeout, outcome genuinely unknown
  S->>E2: probe, GET status by K2 or by our end-to-end reference
  E2-->>S: no answer, or "unknown"
  S->>DB: TXN leave recovery_point=EXT2_SENT, record attempt + last_attempt_at, locked_at=NULL
  S-->>C: 202 Accepted, or 409 with the payment id
  Note over DB: row survives as the instruction to resume

In words. A timeout is not a failure — it is an absence of information, and the difference is money. The server must not tell the client the payment failed, because E2 may have applied it, and it must not tell the client it succeeded, because E2 may not have. recovery_point stays at EXT2_SENT, which is exactly the marker that says "an instruction may be out there with key K2". One cheap probe is worth trying inline; if it also comes back unknown, the attempt stops. Releasing the lease (locked_at=NULL) is deliberate — it invites the next actor, a retry or the recovery worker, to take over immediately instead of waiting out the lease. Handler3 must not run: the request is not fulfilled, and marking it finished would leave the books claiming an outcome nobody has confirmed. If E2 honours idempotency keys, a bounded inline retry with the same K2 is safe and often resolves it; if E2 offers neither keys nor a status query, the request is parked as indeterminate and reconciliation settles it against E2's statement.

Diagram 4 — an incomplete request resumed on a client retry

sequenceDiagram
  autonumber
  participant C as Client
  participant S as Server instance C
  participant DB as Database
  participant E2 as External system 2

  C->>S: retry POST with key K
  S->>DB: INSERT K ON CONFLICT DO NOTHING
  DB-->>S: no row, key exists
  S->>DB: SELECT state, request_hash, recovery_point, locked_at
  DB-->>S: started, hash matches, recovery_point=EXT2_SENT, locked_at stale
  S->>DB: UPDATE SET locked_at=now WHERE state='started' AND locked_at < now - lease RETURNING recovery_point
  DB-->>S: 1 row, takeover won
  Note over S: resume at EXT2_SENT, never re-run Handler1 or Handler2
  S->>E2: probe by K2
  alt E2 already applied it
    E2-->>S: found, result R3
    S->>DB: TXN store R3 + recovery_point=EXT2_DONE
  else E2 never received it
    E2-->>S: not found
    S->>E2: call again with the same key K2
    E2-->>S: 200, result R3
    S->>DB: TXN store R3 + recovery_point=EXT2_DONE
  end
  S->>DB: TXN Handler3 + state=finished + response stored + locked_at=NULL
  S-->>C: 201 Created, the final response

In words. This is the payoff for everything above. The retry finds a started row whose lease has expired, which means the previous owner is dead. Takeover is a single conditional UPDATE that stamps a new locked_at only if the row is still started and still stale, and returns the row — if two retries arrive together, exactly one gets a row and the other gets zero and answers 409. The new owner reads recovery_point and resumes from there: Handler1 and Handler2 are not re-run, because their markers say they committed, and re-running them would double their effects. EXT2_SENT is ambiguous by construction, so the resumer probes first and only calls again with the identical derived key K2, which makes a second delivery a no-op on E2's side. Handler3 then runs, the response is stored, state becomes finished and the lease is cleared, and this retry — not the original request — returns the successful response to the client.

A background recovery worker does exactly the same thing on a schedule, sweeping rows that are started, stale and older than a threshold. Whichever gets there first, the outcome is identical; a client retry that arrives after the worker has finished simply sees finished and receives the stored response.

Correctness checks worth stating aloud

• No phase runs twice. Work and its recovery_point commit in one transaction, so a resumer can always tell what is done.
• No external call is issued without a durable marker preceding it, and every call carries a deterministic derived key, so at-least-once delivery to E1 and E2 produces exactly-once effect there.
• Only one actor owns a request at a time, enforced by the insert and by the conditional takeover UPDATE — never by an application-level lock.
• The client never sees partial state. The only three answers are the stored final response, 409 while in flight, or 422 for a mismatched body.
• Unknown is never reported as failed. A timeout leaves the request resumable and, if unresolvable, hands it to reconciliation rather than guessing.

Generating and storing keys

The client owns key generation, and that is the whole problem. The server cannot generate the key, because the client needs to present the same value on a retry — if the server minted it, a retry after a lost response would arrive with no key at all. So the key is client-supplied, and you must assume clients will supply anything: 1, order-123, a reused batch number, an empty string.

The single most common client bug is generating the key inside the retry loop, which produces a fresh key per attempt and defeats the entire mechanism.

How a client should generate one

• Default to a random UUID (v4), or UUIDv7 when you also want time-ordered index locality on the server side.
• Generate it once per logical operation, before the first attempt, and persist it alongside the pending request in the client's own store. A client that crashes and restarts must be able to recover the same key.
• Where a natural identity exists — a payroll file row, an invoice — derive the key deterministically instead: uuid5(namespace, client_ref + operation + value_date). This needs no client-side storage and makes a resubmitted file inherently safe, which is exactly what corporate batch channels want.
• One key per operation, never per session or per batch. Do not encode timestamps, do not reuse a key with a different body, and do not use a business identifier that can legitimately repeat.

Uniqueness is per client, not global. This is the design point people get wrong. Keys come from mutually unaware clients, so two tenants will eventually send req-001 on the same day. A global unique constraint would make the second one collide, and — far worse — a collision means returning tenant A's stored response to tenant B. Treat the key as data inside a tenant's namespace. The schema at the top of this section already carries that decision: PRIMARY KEY (client_id, key), with the key stored as text because clients supply it.

The composite key gives you three things at once: no cross-tenant collisions, no cross-tenant information leakage, and a natural alignment if you later shard by client, since a tenant's keys live with that tenant's data.

Whether to include the endpoint in the scope.

Prefer the first. A client reusing one key for two different operations has a bug, and surfacing it beats silently accommodating it.

Store it where the effect is. The key record must commit in the same transaction as the business write. Putting keys in Redis or DynamoDB while the payment lands in Postgres recreates the dual-write problem you were trying to solve: the key says done, the payment never happened. If a separate store is unavoidable — a distributed front door, multi-region — use a conditional write with a fencing token and accept that reconciliation is now part of the design rather than a nicety.

Operating the key table — it is one of the highest-write tables you own

• Partition by day and drop old partitions instead of running mass deletes.
• Keep a partial index on unfinished keys for the recovery worker.
• Cap stored response bodies (a few KB, or store a pointer) so the table does not become your blob store.
• Prefer time-ordered keys or a surrogate bigint for physical ordering, because fully random primary keys cause index page splits and write amplification at payment volumes.
• Validate the key itself: enforce a maximum length and a restricted charset at the edge, and reject anything else with 400. It is an untrusted client-supplied string that becomes a database key — treat it like one.

What to say in the interview

"The boundary is at-least-once, so I make the effect idempotent rather than trying to make delivery unique. The client supplies a key, it's unique per client rather than globally, and the key record commits in the same transaction as the work. Multi-step operations get phases with a recovery point, so a crash resumes instead of restarting — and where the outcome is genuinely unknown, I record it as indeterminate and let reconciliation settle it rather than retrying blindly."