Idempotency keys

Deep dive

How it works

In: client key + request · Out: first result, replayed for every retry · State: one row per key (fingerprint, state, response) · Cost: one unique-index insert, one indexed read per retry

1. Client creates key once per user intent and persists it locally before the first attempt; retries reuse it (with backoff).
2. Server computes fingerprint = SHA-256(method, path, canonical body).
3. Claim: insert (tenant, key, fingerprint, state='started', locked_until=now()+lease).
   • Inserted → this request owns the key: go to 4.
   • Conflict → read the row (FOR UPDATE):
     • fingerprint differs → 422.
     • state='done' → return the stored status and body.
     • state='started' and lease valid → 409 "in progress" (client retries later).
     • state='started' and lease expired → take over (the previous worker crashed); continue from its recovery point.
4. Execute in atomic phases. Local database effects go in the same transaction as advancing the key's recovery_point. Calls to external systems (PSP, bank) carry a key derived from ours (<key>:authorize) so they are idempotent too, and their result is recorded before moving on.
5. Finish: in the same transaction as the last effect, set state='done', store response code and body, clear the lease.
6. Expire rows after the retention window (e.g. 24 h-7 d) with a batched delete on created_at.

Code

CREATE TABLE idempotency_keys (
  tenant_id      bigint      NOT NULL,
  key            text        NOT NULL CHECK (length(key) BETWEEN 1 AND 255),
  fingerprint    bytea       NOT NULL,                 -- SHA-256 of the canonical request
  state          text        NOT NULL DEFAULT 'started' CHECK (state IN ('started', 'done')),
  recovery_point text        NOT NULL DEFAULT 'start',  -- last completed atomic phase
  locked_until   timestamptz,
  lock_version   bigint      NOT NULL DEFAULT 0,        -- fencing token for takeovers
  response_code  int,
  response_body  bytea,
  created_at     timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (tenant_id, key)
);
CREATE INDEX ON idempotency_keys (created_at);

-- 1. Claim (own transaction, committed immediately so concurrent requests see it).
INSERT INTO idempotency_keys (tenant_id, key, fingerprint, locked_until)
VALUES ($1, $2, $3, now() + interval '60 seconds')
ON CONFLICT (tenant_id, key) DO NOTHING
RETURNING lock_version;                                 -- a row back = we own it

-- 2. On conflict: inspect.
SELECT fingerprint, state, recovery_point, locked_until, lock_version, response_code, response_body
FROM idempotency_keys WHERE tenant_id = $1 AND key = $2 FOR UPDATE;

-- 3. Take over an expired lease (only if nobody else did in between).
UPDATE idempotency_keys SET locked_until = now() + interval '60 seconds', lock_version = lock_version + 1
WHERE tenant_id = $1 AND key = $2 AND state = 'started' AND locked_until < now() AND lock_version = $3
RETURNING lock_version, recovery_point;

-- 4. Each atomic phase commits its effects together with the recovery point, fenced by lock_version.
UPDATE idempotency_keys SET recovery_point = 'charge_created'
WHERE tenant_id = $1 AND key = $2 AND lock_version = $3;      -- 0 rows: we lost the lease, roll back

-- 5. Finish.
UPDATE idempotency_keys SET state = 'done', response_code = $4, response_body = $5, locked_until = NULL
WHERE tenant_id = $1 AND key = $2 AND lock_version = $3;

-- 6. Retention (run in small batches).
DELETE FROM idempotency_keys WHERE ctid IN (
  SELECT ctid FROM idempotency_keys WHERE created_at < now() - interval '24 hours' LIMIT 10000);

Decision logic after a failed claim:

pub enum Row<'a> { Started { fp: &'a [u8; 32], lease_expired: bool }, Done { fp: &'a [u8; 32], code: u16, body: &'a [u8] } }

pub enum Decision<'a> { TakeOver, Replay { code: u16, body: &'a [u8] }, InProgress409, Mismatch422 }

pub fn decide<'a>(row: Row<'a>, fp: &[u8; 32]) -> Decision<'a> {
    match row {
        Row::Started { fp: f, .. } | Row::Done { fp: f, .. } if f != fp => Decision::Mismatch422,
        Row::Done { code, body, .. } => Decision::Replay { code, body },
        Row::Started { lease_expired: true, .. } => Decision::TakeOver,   // then run statement 3
        Row::Started { .. } => Decision::InProgress409,
    }
}

Complexity and constants

• One primary-key insert per new request, one indexed read per retry: order of 0.1-1 ms on a local PostgreSQL, negligible next to a payment call.
• Storage: key + 32-byte fingerprint + response body; order of 1 KB per key. At 100 requests/s and 24 h retention: about 8.6 M rows, order of 10 GB with bodies.

Efficiency

Cost: the bound is durable-write latency, not compute. A claim is one unique-index insert and a retry is one primary-key read: order of 0.1-1 ms on a local PostgreSQL. A row is a 32-byte fingerprint plus the response, order of 1 KB per key.

Levers

• Two commits per request — short lock, claim visible at once — claim alone, then last effect, state='done' and response together — when work calls external systems.
• Cheap duplicate path — one primary-key read — look up before validation or downstream calls — when retries are common.
• Pointer instead of body — smaller rows — large responses.
• Partition by created_at, drop whole partitions — no dead tuples for vacuum — high volume with short retention.
• Redis SET key value NX EX ttl claim — faster but lost on failover — only where a rare duplicate is tolerable.

Naive → standard → state of the art

• Naive: SELECT, then INSERT, no expiry · concurrent duplicates both run, table grows without bound
• Standard: unique-constraint claim, stored response, batched expiry · order of 0.1-1 ms per request
• State of the art: lease + fencing token + recovery points, partitioned expiry · one extra commit per request, safe takeover after a crash

Implementation notes

• Scope keys per tenant or API credential, so two clients' UUIDs can never collide into each other's responses.
• What gets stored: the final response, including server errors once execution has started (Stripe replays 500s too). Do not store a key at all if the request fails validation before execution started; the client may fix and retry with the same key.
• Fingerprint over a canonical form (sorted JSON keys, normalized numbers), excluding volatile headers.
• Lease length must exceed the worst-case execution time including external calls; the lock_version fencing token makes a slow, lease-expired worker unable to commit after another took over.
• Recovery points (Brandur Leach's "atomic phases"): split work at each foreign call; on takeover, resume after the last recorded phase. Because the foreign calls carry derived idempotency keys, repeating the in-flight call is safe.
• Queues: for at-least-once consumers, insert the message id in a processed table in the same transaction as the side effect; a unique violation means "already done, ack it".
• Client side: generate the key before the first attempt and persist it with the pending operation, so an app restart retries with the same key.

Pitfalls

• SELECT-then-INSERT check: two concurrent requests both see "no row" and both execute.
• Claim inside the same long transaction as the work: other requests block on the uncommitted unique index entry until it finishes, and a rollback erases the claim; commit the claim first.
• Replaying a stored success for a request with different parameters (no fingerprint check).
• New key per retry (generated inside the retry loop): idempotency silently disabled.
• Retention shorter than the client's retry horizon (offline mobile clients retrying the next day).
• Not propagating idempotency downstream: your service is idempotent, but the PSP call it makes on takeover charges again.

Variants and alternatives

In production

Payments: Stripe (Idempotency-Key header on POST requests), Adyen (Idempotency-Key header), PayPal (PayPal-Request-Id). Cloud: AWS EC2 API (ClientToken, docs). Messaging and data pipelines: Kafka idempotent producer (enable.idempotence, docs), SQS FIFO queues (MessageDeduplicationId, docs). Trading: FIX order entry (ClOrdID).

Implementations

Sources

• Stripe API reference, Idempotent requests. docs
• Brandur Leach, Implementing Stripe-like Idempotency Keys in Postgres, brandur.org, 2017. post · code
• IETF HTTPAPI Working Group, The Idempotency-Key HTTP Header Field, Internet-Draft (draft-ietf-httpapi-idempotency-key-header). draft
• Fielding, Nottingham, Reschke, HTTP Semantics, RFC 9110 §9.2.2 (idempotent methods), 2022. RFC