Idempotency & Exactly-Once Semantics

Networks are unreliable. Disks fail. Processes crash. The machine gun of distributed systems is the retry — and retries mean your code will run more than once. Idempotency is how you make that safe.

Why this matters

When a client sends a request, three outcomes are possible:

1. The request arrives, the server processes it, the response arrives. ✓
2. The request never arrives (lost in transit). The client retries — safe.
3. The request arrives, the server processes it, the response is lost. The client retries — and now the operation runs twice.

Case 3 is the dangerous one. A timeout doesn't tell you whether the operation succeeded. Every network call can silently end with you holding a completed operation and no acknowledgment. The client's only rational response is to retry.

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: POST /charge $100
    S->>S: charge applied
    Note over S,C: response lost in network
    S--xC: 200 OK (never arrives)
    Note over C: timeout — did it work?
    C->>S: POST /charge $100 (retry)
    S->>S: charge applied AGAIN
    S-->>C: 200 OK
    Note over C: customer charged twice

This is not a corner case. Stripe's public engineering posts note that retries are a core assumption of their API, not an edge case. Every serious distributed system — payment processors, message brokers, workflow engines — must answer: "what happens when this runs twice?"

The Two Generals problem: why exactly-once delivery is a myth

The Two Generals Problem (Akkoyunlu et al., 1975) proves that two parties communicating over an unreliable channel cannot agree with certainty on whether a message was received. Any acknowledgment can itself be lost; any protocol that tries to confirm delivery requires another round-trip, which can itself fail — infinitely. There is no finite protocol that guarantees exactly-once message delivery over an unreliable network.

This is a fundamental theoretical result, not an engineering gap. It applies to TCP, HTTP, gRPC, Kafka — all of them. What they can offer is:

• At-most-once: fire and forget; if it fails, it's lost. Low durability.
• At-least-once: retry until acknowledged; may deliver multiple times.
• Effectively exactly-once: at-least-once delivery plus an idempotent operation or a dedup filter.

The key insight: stop trying to fix the delivery layer and fix the operation instead.

What idempotency means precisely

An operation f is idempotent if:

f(f(x)) = f(x)   for all x

Applying it a second time produces the same result as the first. Concretely:

Operation	Idempotent?	Why
SET balance = 100	Yes	Applying twice leaves balance at 100
INCREMENT balance by 10	No	Applying twice leaves balance at 20 instead of 10
DELETE resource WHERE id = 42	Yes	Second delete finds nothing, same end state
INSERT OR IGNORE INTO ...	Yes	Duplicate insert is a no-op
INSERT INTO ... (no conflict clause)	No	Second insert raises a unique violation or inserts a duplicate
HTTP PUT /users/42 { name: "Alice" }	Yes	Same body, same state
HTTP POST /charges { amount: 100 }	No (by default)	Each POST creates a new charge

The design implication: prefer set-based operations over delta-based ones wherever possible. "Set the user's name to Alice" is inherently idempotent; "append Alice to the name" is not. The more your data model looks like a CRDT (Conflict-free Replicated Data Type), the less idempotency infrastructure you need to bolt on.

HTTP methods and idempotency

The HTTP spec (RFC 9110) is explicit about which methods are idempotent:

Method	Idempotent	Safe (no side effects)
GET	Yes	Yes
HEAD	Yes	Yes
PUT	Yes	No
DELETE	Yes	No
POST	No	No
PATCH	No (usually)	No

PUT replaces a resource with a specific representation — same body applied twice yields the same state. DELETE removes a resource — a second delete on a non-existent resource should return 404 but the system state is the same. POST creates a new resource by design: two identical POST /charges create two charges.

This is why the charge example requires extra work — and why idempotency keys exist.

Idempotency keys: the Stripe model

The canonical approach for non-idempotent operations like POST /charge:

1. The client generates a unique key (a UUID or similar) before the first attempt.
2. The client sends it on every attempt: Idempotency-Key: 550e8400-e29b-41d4-a716-446655440000.
3. The server checks the key against a dedup store before executing.
   • If the key is new: execute the operation, store (key → result).
   • If the key is seen: return the stored result without re-executing.
4. The client always retries with the same key, so duplicates are absorbed.

sequenceDiagram
    participant C as Client
    participant S as API Server
    participant D as Dedup Store
    participant DB as Payment DB

    C->>S: "POST /charge\nIdempotency-Key: abc123"
    S->>D: GET abc123
    D-->>S: (nil — key not seen)
    S->>DB: INSERT INTO charges ...
    DB-->>S: charge_id = 9876
    S->>D: SET abc123 = {charge_id: 9876, status: 200}
    S-->>C: 200 OK {charge_id: 9876}

    Note over C: network hiccup on next call
    C->>S: "POST /charge\nIdempotency-Key: abc123 (retry)"
    S->>D: GET abc123
    D-->>S: {charge_id: 9876, status: 200}
    S-->>C: 200 OK {charge_id: 9876} (from cache)
    Note over S: no duplicate charge created

Who generates the key? The client — because the client is the party that needs to retry. The key must survive a client restart, so it should be a persistent UUID stored client-side before the first request is sent, not generated on-the-fly after a failure.

What gets stored? The full HTTP response (status code + body). On a repeat, the server returns this verbatim. The client sees the same charge ID, the same amount — it cannot tell from the response whether it was a fresh execution or a cached one.

The atomicity problem. What if two requests with the same key arrive simultaneously? Without care, both get "key not found" and both execute. The fix is an atomic check-and-set:

-- PostgreSQL example
INSERT INTO idempotency_keys (key, status, response_body)
VALUES ('abc123', 'processing', NULL)
ON CONFLICT (key) DO NOTHING;
-- If we inserted 0 rows, another request is processing or complete.

Or in Redis:

SET dedup:abc123 "processing" NX EX 86400
-- NX = only set if Not eXists. Atomic.

The first request wins the write; concurrent duplicates detect the conflict and either wait for the result or return a 409 (some APIs distinguish "duplicate request still in-flight" from "duplicate request completed").

Dedup tables and processed-message IDs

In message-driven architectures, the consumer is responsible for deduplication. The pattern:

1. Each message carries a message ID (set by the producer or broker).
2. The consumer, before processing, checks a processed-messages table.
3. If the ID is present: skip (already processed).
4. If absent: process + insert the ID in the same transaction.

-- consumer pseudo-code (inside a DB transaction)
BEGIN;
  INSERT INTO processed_messages (message_id, processed_at)
  VALUES ($1, now())
  ON CONFLICT (message_id) DO NOTHING;

  IF rows_affected = 0 THEN
    ROLLBACK;  -- already processed
    RETURN;
  END IF;

  -- apply the business logic
  UPDATE accounts SET balance = balance + $amount WHERE id = $account_id;
COMMIT;

The critical detail: the "mark processed" and "apply effect" steps happen in the same atomic transaction. If the process crashes between processing and marking, the message is redelivered and the dedup check prevents double-application. This consumer-side pattern is known as the idempotent consumer. It is often paired with the transactional outbox pattern on the producer side — together they achieve end-to-end exactly-once semantics — but the two halves are independent: the consumer-side dedup table is distinct from the producer-side outbox table.

Idempotent producers: Kafka's model

Kafka offers idempotent producers (enabled since Kafka 0.11) at the broker level. The mechanism:

• Each producer is assigned a Producer ID (PID) by the broker on startup.
• The producer attaches a sequence number to each message batch sent to a partition.
• The broker tracks the last sequence number seen per (PID, partition) pair.
• If it receives a batch with a sequence number it has already committed, it acknowledges without writing again.
• If it receives a batch with a sequence number that's too high (a gap), it rejects — the producer must retransmit in order.

sequenceDiagram
    participant P as Producer (PID=42)
    participant B as Broker

    P->>B: batch seq=0 (records A, B, C)
    B->>B: write, last_seq[42] = 0
    B-->>P: ack

    Note over P,B: ack lost — producer retries
    P->>B: batch seq=0 (records A, B, C)
    B->>B: seq=0 already seen — duplicate!
    B-->>P: ack (no re-write)
    Note over B: exactly-once effect at broker

This is producer-to-broker idempotency only, scoped to a single producer session. If the producer restarts without a transactional.id configured, it gets a new PID and historical deduplication is lost — the broker treats it as a brand-new producer.

Kafka's exactly-once semantics (EOS) combines idempotent producers with transactions and a stable transactional.id. On restart, a transactional producer receives the same PID with an incremented epoch — the epoch increment fences any zombie instance of the old producer and preserves deduplication continuity across sessions. A transactional producer can also atomically write to multiple partitions and commit consumer offsets in a single atomic operation. The consumer reads only committed messages (isolation level read_committed). The effect is exactly-once processing within the Kafka pipeline — but this requires the entire pipeline to be Kafka-to-Kafka; any external side effect (writing to a DB, calling an API) still requires consumer-side handling.

The general production pattern: at-least-once + idempotent consumer

This is the real-world standard:

at-least-once delivery
+
idempotent consumer (dedup table or idempotent operation)
=
effectively exactly-once processing effect

It works because the delivery layer (Kafka, SQS, RabbitMQ, HTTP retry) guarantees the message eventually arrives at least once, while the consumer layer absorbs duplicates harmlessly — either the operation is naturally idempotent, or a dedup check makes it so. The observable effect — the database state, the charge created, the email sent — happens exactly once. Messages may be delivered multiple times, but the effect is not.

flowchart TD
    PUB[Producer] -->|"publish message\n(at-least-once)"| QUEUE[(Message Queue)]
    QUEUE -->|"deliver (possibly 2x)"| CON[Consumer]
    CON --> DEDUP{Already\nprocessed?}
    DEDUP -->|yes| SKIP[Skip — no-op]
    DEDUP -->|no| PROC[Apply effect]
    PROC --> MARK["Mark processed\n(same transaction)"]
    MARK --> ACK[Ack message]
    style QUEUE fill:#a855f7,color:#fff
    style DEDUP fill:#ffaa00,color:#0a0a0f
    style PROC fill:#15803d,color:#fff
    style MARK fill:#0e7490,color:#fff

Fencing and ordering

Idempotency solves "don't apply twice." But retries can also arrive out of order, which creates a different class of problem.

Consider: a client sends "set balance to $100" (version=3), gets a timeout, then sends "set balance to $0" (version=4, a refund). If the original request's retry arrives at the server after the refund has already been applied, the server sees: set→$0 (version=4), then set→$100 (retry, version=3). Without a guard, the account ends up at $100 — the refund is silently undone.

The solution is fencing — attach a monotonically increasing token or version number. The server rejects operations whose token is lower than the last applied token for that resource.

client sends: PATCH /accounts/42 {balance: 100} version=3
server checks: current_version = 3 → apply, set version=4
client sends: PATCH /accounts/42 {balance: 0}  version=4  (refund)
server checks: current_version = 4 → apply, set version=5
late retry arrives: PATCH /accounts/42 {balance: 100} version=3
server checks: current_version = 5 > 3 → reject (409 Conflict)

The version number in this example is a client-supplied optimistic concurrency control (OCC) token — it works only when clients are honest and track versions correctly. In distributed locks, true fencing tokens are issued by the lock service itself (a monotonically increasing counter the client cannot forge), which provides a stronger guarantee: a stale lock holder is rejected even if it tries to submit a higher version number. The ordering principle is the same — reject tokens lower than the last committed one — but the trust model differs. See distributed locks for the lock-service variant.

Combine idempotency key (no duplicates) + fencing token (no stale out-of-order writes) and you cover the full retry surface.

Idempotency window and storage cost

Dedup stores are not infinite. Every key must have a TTL, and the window length is a real trade-off. Set it too short and a client that retries after expiry finds a server that has forgotten the key, causing re-execution — exactly the double-charge scenario you built this to prevent. Set it too long and storage grows without bound.

Back-of-the-envelope for a payment API at 10k TPS:

10,000 requests/sec × 86,400 sec/day = 864M keys/day

Key storage per entry:
  - Idempotency key (UUID):  36 bytes
  - Response body (JSON):   ~200 bytes
  - Metadata (timestamps):   ~28 bytes
  Total: ~264 bytes/entry

864M entries × 264 bytes ≈ 228 GB/day  (24-hour window, 10k TPS)

Practical reduction: trim the window to 1 hour (covers nearly all retries).
  10,000 × 3,600 × 264B ≈ 9.5 GB — fits comfortably in a single Postgres table.

228 GB (full 24-hour window) is beyond what most single-node Redis deployments are provisioned for, but well within a Redis Cluster or a Postgres table with a btree index on (key, expires_at). A 1-hour window drops this to ~9.5 GB — manageable on a single node.

Most real systems use a DB table (Postgres/MySQL with a TTL sweep) rather than Redis for idempotency keys, because they need durability — losing the dedup record means potential double-execution. Redis is fine for short-lived dedup (SQS-style minutes-window); Postgres or DynamoDB is the safe choice for 24-hour API-level keys.

The right TTL is the maximum time a client will retry a single request. Stripe's API v1 documentation specifies a 24-hour window (Stripe's newer API v2 extends this to 30 days). SQS's deduplication window for FIFO queues is fixed at 5 minutes — a short window that works for async messaging but would be inadequate for API-level idempotency.

Concrete example: the payment charge

This is the motivating example. See the payment system design for the full architecture, but the idempotency layer specifically looks like:

1. Client (mobile app) generates idempotency key k = UUID().
   Stores k in local persistence before the first request.

2. Client sends:
   POST /v1/charges
   Idempotency-Key: k
   { customer_id: 42, amount: 1000, currency: "usd" }

3. Server (atomically):
   a. Try INSERT INTO idempotency_keys (key, status) VALUES (k, 'processing')
      ON CONFLICT DO NOTHING.
   b. If conflict: fetch and return stored response. Done.
   c. If inserted: proceed to charge the card via the payment network.
   d. UPDATE idempotency_keys SET status='complete', response=<result> WHERE key=k.

4. Client retries on timeout with the same k → step 3b returns stored result.

There's a crash scenario worth spelling out: the server dies after step 3c but before 3d. The next request with the same key finds it stuck in status='processing'. You have a few options — return a 202 and let the client poll, detect the crashed state by checking whether the charge exists in the payment DB and reconstruct the stored response, or return a 500 and let the client retry with the same key until the record reaches complete. The important constraint regardless: never delete or change the result associated with a key once written. The stored result is the contract.

Concrete example: webhook delivery

Webhooks are the inverse: your system is the at-least-once deliverer; your customer's server is the consumer. Webhook providers (Stripe, GitHub, Twilio) send each event with a unique event ID in the payload:

{
  "id": "evt_1234567890",
  "type": "payment.succeeded",
  "data": { ... }
}

The receiving server should check if evt_1234567890 is already in its processed-events table before doing anything. If yes, return 200 immediately — that signals the sender to stop retrying. If no, process the event and insert the ID in the same transaction, then return 200. Without this, a transient 500 from the customer's server triggers a retry, and the payment-confirmation email sends twice.

Failure modes

Key collision

Two different logical operations are accidentally assigned the same idempotency key. Operation B returns operation A's stored result — silently wrong. Keys must be scoped to a specific operation type and resource. Best practice: namespace the key (charge:UUID rather than a bare UUID). UUIDs v4 carry 122 bits of entropy, so collision probability is negligible in practice.

Non-deterministic operations

If a "re-execution" path exists that produces a different result — the operation reads the current time, calls a random number generator, or makes a third-party API call — the cached response and a fresh execution would diverge. The server must store and replay the original result, never re-execute. Operations that call external services (fraud check, third-party API) must either store their results or be replayed from cache.

Expiring the dedup record too early

If the idempotency key TTL is shorter than the client's retry window, a late retry looks like a new request. The server executes again — silent double-execution. This failure is particularly nasty because it only affects slow-to-retry clients and happens silently.

Partial failure — storing result before effect completes

If the server stores (key → success) before the operation is fully committed to the primary DB, then crashes, the client gets "success" but the effect didn't happen. Write the result to the dedup store inside the same transaction as the primary operation, or only after the primary operation commits.

Concurrent duplicates

Two requests with the same key arrive simultaneously — aggressive client-side retry parallelism is the usual cause. Without atomic check-and-set, both see "key not found" and both execute. The fix is the atomic INSERT ... ON CONFLICT DO NOTHING or Redis SET NX described above.

flowchart TD
    R1[Request 1\nsame key] --> ATOMIC{Atomic\nINSERT NX}
    R2[Request 2\nsame key] --> ATOMIC
    ATOMIC -->|"inserted: wins"| EXEC[Execute + store result]
    ATOMIC -->|"conflict: loses"| WAIT[Wait or return 409]
    EXEC --> DONE[Return fresh result]
    WAIT --> DONE2[Return cached result]
    style ATOMIC fill:#ff6b1a,color:#0a0a0f
    style EXEC fill:#15803d,color:#fff
    style WAIT fill:#ffaa00,color:#0a0a0f

Storage choices for idempotency state

Store	TTL support	Durability	Latency	Notes
Redis (standalone)	Native TTL	Limited (AOF/RDB)	<1ms	Fast but can lose keys on crash if persistence lags
Redis Cluster	Native TTL	As above	<1ms	Shards across nodes; same durability caveat
Postgres table	Background sweep or partial index on expires_at	Strong (WAL)	1–5ms	Preferred when losing a key == double-charge
DynamoDB	Native TTL attribute	Strong (with global tables)	1–5ms	Good if you're already on AWS; auto-managed TTL
Cassandra	Native TTL (per-cell)	Tunable	1–5ms	Good if you're already at Cassandra scale

For payment idempotency keys specifically: use a durable store. The asymmetry is severe — a lost key causes a double-charge; a slightly slow key lookup costs milliseconds.

Relation to other patterns

Exactly-once in the context of message queues: see the distributed message queue design — Kafka's idempotent producer and consumer EOS are practical implementations of the at-least-once + idempotent consumer pattern.

Exactly-once in distributed transactions: when an operation spans multiple services, each sub-operation must be idempotent, because the saga coordinator may retry individual steps. The Saga pattern uses compensating transactions — operations that undo a completed step — which are themselves required to be idempotent.

Idempotency in payment systems: the payment system design treats idempotency keys as a first-class concern: the payment API, the ledger writes, and the downstream webhook delivery all require distinct idempotency mechanisms stacked at each layer.

Fencing and distributed locks: distributed locks use fencing tokens to prevent stale lock holders from issuing writes — the same ordering guarantee that prevents out-of-order retries from corrupting state.

Things to discuss in an interview

• Natural vs. engineered idempotency: can you redesign the operation to be naturally idempotent (set-based), or do you need to layer on a dedup store?
• Who generates the idempotency key: always the client, always before the first attempt, always persisted.
• Atomic check-and-set: the single most common implementation bug is a non-atomic "check then set."
• TTL sizing: match the retry window, not some arbitrary number. Justify it.
• Durability of the dedup store: losing a dedup record is as bad as losing the original data.
• Exactly-once semantics in Kafka vs. HTTP APIs: different mechanisms, same underlying principle.

Things you should now be able to answer

• Why can't you guarantee exactly-once delivery over an unreliable network?
• What is the difference between exactly-once delivery and exactly-once processing effect?
• Why must the client, not the server, generate the idempotency key?
• Why does SET balance = 100 behave differently from INCREMENT balance by 10 under retries?
• How does Kafka's idempotent producer work, and what does it not protect against?
• What happens if the dedup record TTL is shorter than the client's retry window?
• How do you atomically prevent two concurrent requests with the same idempotency key from both executing?

Further reading

• RFC 9110, Section 9.2: "Idempotent Methods" — the HTTP specification's definition.
• Kleppmann, Designing Data-Intensive Applications, Chapter 9: "Consistency and Consensus" — Two Generals, linearizability, and exactly-once semantics.
• Bernhardt, "The Incomplete Guide to Exactly-Once Delivery" — a widely-cited blog post on why exactly-once delivery is harder than it appears.
• Kafka Documentation: "Exactly-Once Semantics" — covers idempotent producers and transactions.
• Stripe Engineering: "Designing robust and predictable APIs with idempotency" — the canonical public writeup of the Stripe model.