Idempotency, and the myth of exactly-once delivery

This idea appears in more problems on this site than any other: payments, the job scheduler, notifications, ad billing, Ticketmaster, Robinhood. Getting the vocabulary right is worth a lot, because "we'll use exactly-once" is a phrase that reveals a candidate has not thought it through.

1. Why exactly-once delivery cannot exist

The sender transmits a message and waits for an acknowledgement. The acknowledgement does not arrive. The sender cannot distinguish between three cases:

1. The message never arrived.
2. The message arrived and was processed; the ack was lost.
3. The message arrived and is still being processed.

No protocol resolves this ambiguity, because resolving it would require a reliable message — which is the thing being attempted. This is the two generals problem, and it is a proof of impossibility, not an engineering gap.

Given that, you have exactly two choices:

• At-most-once: never retry. Some messages are lost.
• At-least-once: always retry until acknowledged. Some messages arrive twice.

For anything that matters, you choose at-least-once. Duplicates are the price of not losing data, and the entire discipline is about making duplicates harmless.

2. What "exactly-once" actually means when a vendor says it

Systems that advertise exactly-once — Kafka, Flink — deliver exactly-once processing semantics, which is a different and achievable claim:

Messages may be delivered more than once, but their effect on state is applied exactly once.

They achieve it by making state updates and offset commits atomic: either both happen or neither does. On restart, the replayed messages re-derive the same state rather than adding to it. That is a real, valuable guarantee — but it holds only inside the system's own transactional boundary. The moment you call an external API, send an email, or charge a card, you are back to at-least-once and you own the deduplication.

3. The four mechanisms

Mechanism 1 — naturally idempotent operations

The cheapest solution is to make the operation itself repeat-safe.

NOT idempotent                        Idempotent
────────────────────────────────────────────────────────────────
balance = balance + 100               balance = 500
counter++                             SET value = 42
INSERT INTO orders ...                INSERT ... ON CONFLICT DO NOTHING
list.append(x)                        set.add(x)
DELETE the first matching row         DELETE WHERE id = 'abc123'

The pattern: absolute assignment over relative mutation, and addressed operations over positional ones. Where you can express the operation this way, you need nothing else.

Mechanism 2 — the idempotency key

When the operation is inherently a mutation, attach a deterministic key and claim it atomically.

CREATE TABLE idempotency_keys (
  key           TEXT PRIMARY KEY,      -- the unique constraint IS the mechanism
  request_hash  BYTEA NOT NULL,
  state         TEXT  NOT NULL,        -- 'in_progress' | 'completed'
  response      JSONB,
  created_at    TIMESTAMPTZ NOT NULL DEFAULT now()
);

def execute(key: str, request):
    h = sha256(canonical(request))
    try:
        db.execute("INSERT INTO idempotency_keys (key, request_hash, state) "
                   "VALUES (%s, %s, 'in_progress')", (key, h))
    except UniqueViolation:
        row = db.fetch_one("SELECT * FROM idempotency_keys WHERE key = %s", (key,))
        if row.request_hash != h:
            raise KeyReusedWithDifferentBody(key)   # a client bug: fail LOUDLY
        if row.state == 'completed':
            return row.response                      # replay the original answer
        raise ConcurrentRequest(retry_after=1)       # someone else holds it

    result = do_the_work(request)
    with db.transaction():                           # same transaction as the effect
        persist(result)
        db.execute("UPDATE idempotency_keys SET state='completed', response=%s "
                   "WHERE key=%s", (result, key))
    return result

Four rules, each of which is a real bug if violated:

• The key must be deterministic. The same logical intent must produce the same key on every retry, from any node. A random UUID generated per attempt defeats the entire mechanism — generate it on the client, before the first attempt, or derive it from the business facts (hash(user, event, entity, time_bucket)).
• Let the database enforce uniqueness. SELECT then INSERT has a race window. A single INSERT with a unique constraint does not.
• Hash the request body. The same key with different parameters is a client bug; returning the original response silently would apply the wrong operation. Reject it explicitly.
• in_progress is a real state. Two concurrent requests with the same key must not both proceed. The second gets a retryable error, not a second execution.

Mechanism 3 — fencing tokens

Idempotency keys stop duplicates. They do not stop a stale actor: a process that was the leader, paused (GC, VM migration), lost its lease, and then woke up and acted anyway. Its request is not a duplicate — it is a legitimate-looking request from someone who no longer has authority.

Scheduler A: acquires lease, fence = 33
             [ 12-second GC pause ]
             lease expires
Scheduler B: acquires lease, fence = 34, dispatches job J
Scheduler A: wakes up, still believes it is leader, dispatches job J with fence = 33
Resource:    highest fence seen is 34.  33 < 34  ->  REJECT.

UPDATE job_runs SET status = 'dispatched', fence = :f
WHERE job_id = :id AND (fence IS NULL OR fence < :f);
-- Zero rows updated -> a newer authority already owns this. Drop silently.

The fence must come from a monotonic source that survives failover — etcd's ModRevision, ZooKeeper's zxid, or a database sequence. A lock alone is never sufficient, because a lock only holds while your process is healthy, and a paused process is precisely the case where it is not.

Mechanism 4 — the transactional outbox

The dual-write problem: you must update the database and publish an event. Two systems, no shared transaction. A crash between them leaves them permanently inconsistent.

BEGIN;
  INSERT INTO ledger_entries (...) VALUES (...);              -- the state change
  INSERT INTO outbox (topic, payload) VALUES ('payment.captured', '{...}');
COMMIT;
-- A relay polls `outbox`, publishes to Kafka, marks rows sent.
-- Publishing is at-least-once, so consumers must still be idempotent — but the
-- database and the event stream can no longer DISAGREE about what happened.

The outbox does not eliminate duplicates; it eliminates divergence. Consumers still need mechanism 1 or 2. Change-data-capture (Debezium reading the write-ahead log) is the same idea with the polling removed.

4. Choosing a key

Situation	Key
Client-initiated request	Client-generated UUID, created before the first attempt, reused across retries
Scheduled job	hash(job_id, scheduled_run_time, attempt_group) — deterministic across nodes
Event-driven consumer	The upstream event's ID, propagated end to end
Notification	hash(user, event_type, entity, time_bucket) — the bucket defines "the same notification"
Payment to an external rail	Your key, passed through to the provider so their side also deduplicates

The last row generalises into an important principle: propagate the key across trust boundaries. An idempotency guarantee that stops at your process boundary does not protect against a retry that reaches the payment network twice.

5. Retention, and the failure it causes

Idempotency records cannot be kept forever, and expiring them too early reopens the window.

• 24 hours is the common minimum (Stripe's window), covering ordinary client retries.
• Days to weeks for high-value or slow-settling operations, where a retry may follow a long outage.
• Forever, in compacted form, for anything auditable — store just the key and outcome hash after the full record expires.

A key that expires while a client is still retrying produces a duplicate charge with no trace of why. Size the retention against your worst retry window, not your typical one.

6. What to say in an interview

"There's no such thing as exactly-once delivery — the two generals problem means a sender can never distinguish a lost message from a lost acknowledgement. So I use at-least-once delivery with an idempotent consumer, which produces an exactly-once effect.

Concretely: a deterministic idempotency key generated by the client before its first attempt, claimed with a unique constraint so the database does the mutual exclusion rather than my application racing on a check-then-insert, with the request body hashed so key reuse with different parameters fails loudly, and an in_progress state so concurrent retries don't both execute. Where the operation crosses a trust boundary I propagate the key downstream so the provider deduplicates too.

That covers duplicates. For a stale leader acting after failover I need fencing tokens — a monotonic term number from etcd that the resource checks — because a lock only holds while my process is healthy, and a GC-paused process is exactly the case where it isn't. And where I have to write state and publish an event, a transactional outbox keeps the two from diverging."