Idempotency architecture — keys, dedupe store, retry semantics, cross-service

Where the duplicates actually come from

Teams usually picture one source of duplicates - a user double-clicking Submit - and build for that. The real sources are structural, they are mostly machine-generated, and there are more of them than there are hops in the request path.

Client SDKs retry on connection resets, timeouts and 5xx by default; most cloud SDKs ship with three attempts enabled and the application never sees the first two. Reverse proxies and meshes retry independently: nginx proxy_next_upstream and an Envoy retry policy will re-dispatch a request to a different backend while the original backend is still executing it, which produces two concurrent executions rather than two sequential ones. Those layers multiply - a three-hop chain where every hop allows three attempts admits twenty-seven executions of the leaf service from one client call, which is why retry budgets exist and why the retry-side controls belong in the queue and quarantine design covered in dead-letter queue architecture. Message brokers are at-least-once by construction: an SQS visibility timeout that expires mid-processing re-delivers the message, and a Kafka consumer that rebalances before committing replays from the last committed offset. Schedulers and operators add the rest: two replicas of a cron pod firing the same job, a backfill re-run over a date range, an engineer replaying yesterday's events after a fix.

None of this is avoidable by being disciplined. A timeout is not a failure, it is an absence of information: the request may never have landed, or it may have landed, committed, moved money and lost only the acknowledgement. Choosing at-most-once - never retry - resolves the ambiguity by silently losing work, which is usually the worse bug because nothing appears in the error rate. So the system delivers at least once, and the effect has to happen at most once. That gap is what the rest of this page fills.

Natural idempotency beats imposed idempotency

Before adding keys and a dedupe store, check whether the operation can simply be written so that repeating it changes nothing. Imposed idempotency costs a durable store, a round trip on every write, a TTL policy and a class of new failure modes; natural idempotency costs a schema decision.

The distinction is absolute versus relative effects. UPDATE orders SET status='shipped' WHERE id=? is naturally idempotent - run it a hundred times and the row is shipped once. UPDATE accounts SET balance = balance + 10 is not, and no amount of care at the call site fixes that. Wherever the domain allows it, state the desired end state rather than a delta.

The second lever is who names the resource. POST /orders creates a new row per call by definition. PUT /orders/{client-generated-uuid} makes the primary key itself the dedupe mechanism: the second write collides with a uniqueness constraint that is already in the table you care about, needs no side store, and - unlike a key with a TTL - never expires. The same trick without changing the HTTP verb is a unique index on a business-meaningful tuple plus an upsert:

-- the dedupe is a constraint on the business table, not a separate system
CREATE UNIQUE INDEX ON orders (tenant_id, external_ref);

INSERT INTO orders (tenant_id, external_ref, amount_cents, status)
VALUES ($1, $2, $3, 'pending')
ON CONFLICT (tenant_id, external_ref) DO NOTHING
RETURNING id;            -- zero rows returned == this was a duplicate

Deletes deserve a note of their own. Deleting an already-deleted resource is idempotent in effect but frequently not in response: the handler returns 204 the first time and 404 the second, so a client retry that actually succeeded reports failure and the operator chases a ghost. Return the same terminal answer both times.

What natural idempotency cannot cover is any effect that is inherently incremental or external: appending to a ledger, allocating the next sequence number, sending an email, charging a card at a third party. Those need a key.

Conditional writes, compare-and-set, and preconditions

The other alternative to an idempotency key is a precondition on the write itself. If-Match: "v7" against an ETag, UPDATE ... WHERE version = 7, DynamoDB's ConditionExpression: attribute_not_exists(pk), SET key value NX in Redis, S3's If-None-Match: * - all express the same thing: apply this change only to the state I believed I was changing.

A retry of a conditional write is automatically a no-op, because the precondition no longer holds after the first one succeeded. This is where a specific bug lives: the handler treats "0 rows affected" as a failure and retries forever, when on a replay it is the correct and expected outcome. A conditional write needs a three-way branch - applied, already applied, conflicted with someone else - and the middle case is success.

Compare-and-set has an advantage a key does not: it gives you idempotency and concurrency control in the same operation. An idempotency key stops the same operation from applying twice; it does nothing about two different operations racing to overwrite each other's result, which is a lost-update bug that survives a perfectly correct dedupe layer. Where a caller can read a version, preconditions are usually the smaller design.

The related idea for exclusive work is a fencing token - a monotonically increasing number handed out with a lease so a stalled worker's late write is rejected by the storage layer rather than silently applied. That mechanism belongs to lock design and is covered in distributed lock architecture; the connection worth keeping in mind is that fencing makes a stale duplicate harmless in exactly the way a dedupe store does, but by ordering rather than by memory.

Preconditions run out when there is no existing resource identity to condition on, when the caller cannot see a version, or when the effect happens in a system you do not control. That is the remaining territory, and it is where keys are mandatory.

Reading the diagram - what each box is responsible for

The top strip is the request path, and the ordering in it is load-bearing. The client mints the key, not the gateway and not the service, because only the client knows which attempts constitute one logical operation; a server looking at two byte-identical requests cannot tell a retry from a customer legitimately buying the same thing twice. The gateway validates and scopes the key rather than trusting it. The dedupe store answers exactly one question atomically - has this key been claimed - and the business handler is the only box that produces the effect the key is protecting.

The middle row is where correctness is decided rather than where traffic flows. Retry policy is upstream context you inherit: its total budget dictates the TTL below it. Conflict handling covers the same key arriving with a different payload, which is a client bug and must be rejected rather than replayed. Cross-service propagation is the part most implementations skip, and skipping it is why an idempotent service composed with another idempotent service is not idempotent. TTL and eviction looks like storage hygiene and is actually the published deadline after which retrying is unsafe.

The lower rows are the admission that the mechanism is not airtight. Observability exists because a broken idempotency layer is silent - it fails by doing extra work successfully. Audit and reconcile is the backstop for the residual ambiguity that no dedupe store can remove, such as a claim written just before the process died mid-call to a third party.

The dedupe store is a consistency problem, not a cache

The store has to support one primitive: atomic insert-if-absent, linearizable per key. A unique-index insert in a relational database, SET key value NX PX ttl in Redis, a conditional PutItem in DynamoDB. What it must not be is a read followed by a write - two concurrent retries both read absent, both proceed, and the system executes twice under a layer whose entire purpose was preventing that. The read-then-write version passes every single-threaded test you will write for it.

Two properties are easy to lose by accident. Durability: a Redis instance without persistence, or one that fails over to a replica that had not received the last few writes, loses claims, and every lost claim is a duplicate that will not appear in any error metric. Read-your-writes: routing dedupe lookups to a read replica with 200 ms of lag reopens the same window, and it reopens it precisely for the fast client retries that arrive inside the lag. A cache with memory-pressure eviction is not a dedupe store; eviction there is a silent correctness failure rather than a performance event.

The upside is that the workload is friendly. Every operation touches exactly one key, so the store shards trivially by key hash and never needs a cross-key transaction - unless you deliberately co-locate it with the business tables to get atomicity, which is the subject of the next section but one. Size it honestly: at 2,000 mutating requests per second with 24-hour retention, that is about 173 million live records, and at roughly 400 bytes each - key, request fingerprint, status, timestamps, a pointer to the stored response - about 69 GB before indexes. Storing full response bodies inline multiplies that by whatever your median payload is, which is the usual reason to cap stored bodies at a few kilobytes and keep larger ones by reference.

And note the standing tax: an idempotency layer adds a round trip to every mutating request, including the overwhelming majority that are not duplicates. That is the price, and it is why the natural and conditional-write options above are worth exhausting first.

Recording the key and doing the work are two different events

This is the part that separates an implementation that works from one that works during the incident it was built for. There are only two naive orderings and both are wrong.

Do the work, then record the key: a crash in between leaves the effect applied and no record of it, so the retry executes a second time. This is the classic double-charge, reintroduced by the layer meant to prevent it. Record the key, then do the work: a crash in between leaves a key claiming an operation that never happened, and every subsequent retry is rejected as a duplicate. That failure is worse in practice, because a duplicate is visible and a silently dropped operation is not.

So the record must be two-phase, and the key's lifecycle is a state machine rather than a boolean:

The middle state is the honest representation of "I do not know yet", and the two acceptable answers to a retry that lands on it are to hold the request briefly until the winner records an outcome, or to return a retryable conflict immediately. Falling through and executing recreates the race; returning a failure is worse still, because a false negative is exactly what convinces a client to start the operation over under a fresh key.

Claims also get stuck. A worker that dies after claiming leaves a row that blocks its own operation forever, so a claim needs an owner and an expiry - effectively a lease - plus a sweeper that resolves anything older than the lease. Resolving means asking the downstream what actually happened using the reference stored with the claim, not blindly re-executing; re-execution at sweeper time is how a stuck-claim cleanup job becomes a duplicate generator.

-- phase 1: claim. The unique constraint, not the SELECT, is what makes this safe.
INSERT INTO idem_keys (scope, key, req_fingerprint, state, owner, lease_expires_at)
VALUES ($scope, $key, $fp, 'claimed', $worker, now() + interval '60 seconds')
ON CONFLICT (scope, key) DO NOTHING
RETURNING id;

-- zero rows -> we lost the race. Read the existing row and branch on state:
--   claimed          -> 409 retry-after, or block on the winner
--   completed        -> replay the stored response
--   failed-terminal  -> replay the stored rejection
--   (a mismatched request fingerprint is a 422, never a replay)

-- phase 2: effect + completion in ONE transaction
BEGIN;
  INSERT INTO orders (...) VALUES (...);
  UPDATE idem_keys SET state='completed', resp_status=201, resp_body=$body
   WHERE scope=$scope AND key=$key;
COMMIT;                  -- crash before this leaves a claim the sweeper resolves

Atomicity: one transaction, or an outbox

Everything above assumes the dedupe write and the business write can commit together. Whether they can is the single biggest architectural constraint on the design, and there are three cases.

Same database. Put the key row and the business rows in one transaction, as in the snippet above. A crash anywhere rolls back both, the retry sees no claim and executes cleanly, and there is no window at all. This is the only genuinely easy case and it is worth distorting the storage layout to get it - keeping the dedupe table in the service's own database rather than a shared Redis is usually the right trade even though Redis is faster.

Dedupe in one system, business data in another. Redis for keys and Postgres for orders is a dual write, and no ordering of two non-transactional writes is safe - you are choosing which failure you prefer. If the split is forced, claim first and then push the uniqueness down into the data you are actually writing: carry the idempotency key into the business table as a column with a unique constraint, so the authoritative dedupe happens at the same commit as the effect and the fast store in front of it becomes an optimisation rather than the source of truth.

The effect is at a third party. A payment rail, a mail provider, a cloud control-plane API - none of these join your transaction. Persist the claim, including the request, before calling out; pass your key into the provider's own idempotency mechanism if it has one; and store the provider's reference the instant you have it. Recovery is then a query by your own key rather than a guess.

Publishing an event after the write is the same dual-write problem in different clothing, and the standard answer is the transactional outbox - write the event into the same transaction as the state change and relay it asynchronously, as described in transactional outbox architecture. Note that the outbox fixes the producer and not the consumer: relays are at-least-once, so downstream handlers still need their own dedupe.

What a completed key is allowed to mean

A retry that lands on a completed key gets the stored response - the same status code and body the first attempt produced - and not a recomputed one, because a recomputed answer describes the resource as it is now rather than what the original call did, and the caller cannot tell those apart. That much is settled, and is worked through request by request in the payments treatment. The decisions that are actually contested are which outcomes may complete a key at all, and how the request fingerprint is computed.

Terminal versus transient outcomes

Completing a key is irreversible from the client's point of view: it pins one answer to that key for the life of the record. So only outcomes that would be identical if re-evaluated are allowed to complete it. A 2xx qualifies. So does a deliberate business rejection - insufficient funds, failed validation, a policy decline - and replaying that rejection is correct, because a retry must not get a fresh evaluation that now succeeds because a balance was topped up in between.

A 500, a timeout inside your own handler, or a connection failure to a downstream does not qualify, and recording one as terminal is a bug with a long tail. The key is now poisoned: the client retries exactly as designed, receives the same 500 forever, and neither waiting nor fixing the downstream helps, because the answer is being served from your dedupe table rather than from the system that recovered. Transient failures release the claim instead of completing it. The production tell is a stored response with a 5xx status - that row should not be able to exist, and it is worth an assertion rather than a dashboard.

Fingerprinting without manufacturing conflicts

The guard against a client reusing one key for two different operations is a stored hash of the request, and the answer on mismatch is a conflict (422 or 409): not a replay, which would be a lie, and not an execution, which would be a duplicate. The trap is hashing raw bytes. JSON object key order, header order, whitespace, a client-injected trace identifier, a retry-attempt counter - each changes the bytes without changing the operation, so a byte hash rejects legitimate retries with a 422, intermittently, which is close to the worst debugging shape available. Hash a canonical projection instead: an explicit allowlist of the fields that define the operation, sorted, with numbers and casing normalized, and nothing else in it.

Two smaller decisions round the record out. Cap what you store - response bodies past a few kilobytes belong behind a pointer, and anything sensitive in a stored body silently inherits the retention window of the dedupe table, which is longer than anyone intended. And mark replays: a header such as Idempotency-Replayed: true costs nothing and turns the dedupe hit rate into a per-client metric. A client sitting at a 40% replay rate has a broken retry configuration; a client at 0% is almost certainly minting a new key per attempt, which is the most common way this feature ships without working at all.

The effects you cannot roll back

The dedupe row commits or it does not. The email does not. Every non-transactional side effect in a handler - email, SMS, push, webhook delivery, an external charge, a metric increment, a file written to object storage - sits outside the atomicity the previous sections were built on, and it is where "we have idempotency" quietly stops being true.

The rule is to keep those effects out of the critical section and drive them from committed state rather than from the request. Write the intent inside the transaction, let a relay pick it up after commit, and give the consumer a dedupe key derived from the business event - notify:order:{order_id}:confirmation - rather than a fresh UUID per delivery attempt, which dedupes nothing. Providers do not dedupe on your behalf; two calls with the same content are two emails.

Non-determinism inside the response is the same problem in miniature. If the first execution mints a UUID, reads now(), or generates a token, those values are part of the answer the client already has. Regenerating them on replay returns a different object under the same key, which is indistinguishable from a duplicate to anyone reading logs. Capture generated values at first execution, store them with the response, replay them.

Metrics deserve an explicit decision, because the default is wrong in the worst moment: if a replayed request increments the same business counter as a real one, dashboards double-count during exactly the network incident that is generating the replays. Count replays separately.

Idempotency does not compose across services

Service A is idempotent. Service B is idempotent. The composition A-then-B is not, and assuming otherwise is the most common way a correct implementation produces duplicates in production.

The mechanism is straightforward once stated. A retry of A re-executes everything in A up to the point it failed. If A calls B and then C, and the failure happened after B succeeded, the retry will call B a second time. Whether that is safe depends entirely on whether B receives the same key it received the first time. A key minted inside A's handler with uuid4() is different on every attempt, so B sees two distinct operations and dutifully performs both.

Downstream keys therefore have to be derived, not generated: key_B = hash(parent_key, "charge"), key_C = hash(parent_key, "reserve-inventory"). Derivation needs no shared state - any attempt, on any replica, after any restart, reconstructs the same value. The same rule governs fan-out: one client retry re-drives every downstream call, and each of them needs its own stable, distinct key.

Two cases do not fit the pattern. A downstream that is simply not idempotent - a partner API, a legacy endpoint, a mainframe - has to be wrapped: write a local ledger row keyed by your derived key before the call, and reconcile afterwards by querying the partner with your reference. And partial application, where two of three steps committed and the third is permanently failing, is not an idempotency problem at all: repeating the operation will never undo the first two, so you need compensation, which is the territory of the saga pattern.

Message-driven paths need one extra caution. Consumers are at-least-once because the offset or acknowledgement is committed after processing, so redelivery after a crash is normal operation rather than an anomaly. Dedupe on a business identifier carried in the payload, never on the broker's delivery identifier, which changes on every redelivery. Messages that keep failing regardless of dedupe belong in a dead-letter queue rather than in an infinite retry loop.

TTL is a contract, not storage hygiene

Keys are retained for a bounded window and then collected, because otherwise the store grows forever. But the moment of expiry is a correctness cliff. After it, the key is a stranger: a retry carrying it is treated as a brand-new operation and executed for real. The retention window is therefore the client's retry deadline, and it should be documented as such.

Which means the number has to be derived rather than copied. Twenty-four hours is a widespread default and it is fine when clients retry over seconds and minutes. It is wrong when a failed batch job is re-run by an engineer the next morning, or when a partner's queue drains after a two-day outage - in both cases the retry lands after expiry and the effect happens twice. Set the TTL longer than the maximum total retry budget, including exponential backoff, jitter, and the human-initiated replays nobody put in the budget.

For anything where a duplicate is unacceptable rather than merely annoying, do not rely on the TTL at all. A uniqueness constraint on business-meaningful columns - (tenant_id, external_ref), (account_id, statement_period) - never expires, costs an index, and catches the late retry the dedupe store has already forgotten. The key store protects the fast path; the constraint protects forever.

Then give clients somewhere to go after the deadline: an endpoint that answers "did operation X happen" by business reference. Without it, a client whose retry window has closed has exactly two options, retry blindly or give up, and both are wrong. Expire by age with enough headroom that the store never evicts under pressure, and alert on store size rather than letting the cache make correctness decisions for you.

Failure modes worth a test each

Every one of these has shipped in a system whose owners believed idempotency was handled, and none of them show up in an error rate - a broken idempotency layer fails by successfully doing extra work.

Two of these are worth building a deliberate drill around rather than a unit test: kill the process between claim and commit and confirm the sweeper resolves rather than re-executes, and fire two identical requests concurrently against a warm system to confirm one of them sees the in-progress state. Both pass trivially in a single-threaded test and both are exactly what production supplies.

Related pages

Idempotency keys as an API-level contract - header conventions, the client-side key lifecycle, and the concurrency vignettes - are covered in idempotency keys: safe retries, exactly-once effect, atomic dedup. The payments-specific treatment, including deterministic key derivation from a signed mandate and the duplicate-payment hazard that idempotency cannot catch, is in idempotency keys in agent payments. For the surrounding machinery: the transactional outbox for the dual-write problem, sagas for compensating a partially applied operation, distributed locks and fencing tokens for exclusive work, and dead-letter queues for the retries that must eventually stop.