Interview patterns · Design 8

Duplicates and idempotency

Why retries create duplicate payments, orders and messages, and how idempotency keys, dedup tables and idempotent consumers make "exactly once" effectively true.

AdvancedInterview priority: High45 min
On this page
  1. The problem: the retry that charged twice
  2. Signals that you are facing it
  3. The idea: make doing it twice the same as doing it once
  4. The toolbox
  5. Worked numbers: how big is the dedup store?
  6. Exactly once: what is actually promised
  7. When not to bother
  8. Which case studies use it
  9. In the interview
  10. Quiz

The problem: the retry that charged twice

A customer taps Pay $40 on a train. The phone sends the request, the server charges the card, and the reply is lost when the train enters a tunnel. After 10 seconds the phone gives up with a timeout.

The phone now faces a question it cannot answer: did the payment happen? A request over a network has three outcomes, not two: success, failure, and unknown. A timeout is "unknown". If the phone retries, the customer may pay twice. If it doesn't, the customer may think the order failed when it went through.

A lost reply, a retry, and a double charge

This is not a rare edge case. At 1,000 payments a second, a 0.1% timeout rate is one ambiguous payment every second. And timeouts are not the only source of duplicates: a user double-clicks the button, a load balancer retries an upstream that was slow, a queue redelivers a message after a worker crash, a partner resends a webhook because your 200 arrived late.

Every distributed system has to pick: retry and risk duplicates, or don't retry and risk losing work. The answer is almost always "retry, and make duplicates harmless". This lesson is about the second half.

Signals that you are facing it

In an interview, listen for any of these:

  • Money or inventory moves: payments, transfers, refunds, orders, seat or room bookings, stock reservations.
  • Retries anywhere: a mobile client on a flaky network, a service-to-service call with a retry policy, a client SDK that retries on 5xx.
  • A message queue or event stream: SQS, RabbitMQ, Kafka and most brokers deliver at least once, meaning every message arrives one or more times.
  • Webhooks: Stripe, GitHub and most providers retry deliveries until you return 2xx, so you will receive some twice.
  • The requirement says "exactly once" or "never charge twice", "never send two notifications".

The idea: make doing it twice the same as doing it once

An operation is idempotent if performing it several times has the same effect as performing it once. Setting status = 'shipped' is idempotent; balance = balance - 40 is not. Deleting order 17 is idempotent; "append a row" is not.

Idempotency is about the effect on the system, not the response. Deleting an already-deleted order may return 404 the second time, and that's fine: the state is the same.

The core equation of this lesson:

at-least-once delivery + idempotent processing = effectively exactly-once

The network can't deliver exactly once (the sender can never be sure the receiver got it, so it must resend), but the receiver can make the second copy a no-op. That's what everyone means, precisely or not, when they say "exactly once".

An idempotency key turns the retry into a replay

HTTP builds this into its methods. GET, PUT and DELETE are defined as idempotent; POST and PATCH are not. A PUT /users/7 with the full new profile can be retried freely. A POST /payments cannot, which is exactly why payment APIs add an idempotency key to it.

The toolbox

Five techniques, from cheapest to most involved. Real systems use several.

1. Make the operation naturally idempotent

The best duplicate is one that can't do harm. Rewrite relative changes as absolute ones, or make them conditional:

  • SET balance = 60 instead of balance = balance - 40 (only safe if one writer owns the value).
  • Conditional writes with a version: UPDATE orders SET status='paid', version=8 WHERE id=17 AND version=7. The retry finds version 8 and updates zero rows. This is also called optimistic concurrency control.
  • State machines: "move order 17 from pending to paid" is a no-op if it is already paid.

2. Unique constraints on a natural key

If the business already has a unique identifier, let the database enforce it. One shipment per order: UNIQUE (order_id) on shipments. One payment per invoice: UNIQUE (invoice_id). The second insert fails with a constraint violation, and you treat that as "already done". This is cheap and very reliable, because the database checks it atomically.

3. Idempotency keys (for APIs)

When there is no natural key ("pay $40" could legitimately happen twice), the client creates one. It generates a random ID (a UUID) for each logical operation, sends it in a header such as Idempotency-Key, and reuses the same value on every retry of that operation. Stripe, Adyen, PayPal and many other payment APIs work this way.

The server keeps a table of keys:

CREATE TABLE idempotency_keys (
    account_id    BIGINT       NOT NULL,
    idem_key      VARCHAR(64)  NOT NULL,
    request_hash  CHAR(64)     NOT NULL,        -- SHA-256 of the request body
    status        VARCHAR(16)  NOT NULL,        -- 'started' or 'done'
    response_code INT,
    response_body JSONB,
    created_at    TIMESTAMPTZ  NOT NULL DEFAULT now(),
    PRIMARY KEY (account_id, idem_key)          -- keys are scoped per account
);

Insert first: the unique key decides who does the work

The flow, step by step:

  1. Insert first, don't read first. INSERT … ON CONFLICT DO NOTHING. If the row was inserted, this request owns the key and continues. If it wasn't, someone already has it.
  2. Existing row, status done: compare the request hash. Same body: return the saved response exactly. Different body: return an error (Stripe uses 400 here; 422 is also common), because the client reused a key for a different operation.
  3. Existing row, status started: another copy is running right now. Return 409 Conflict and let the client retry shortly. Never run the work twice in parallel.
  4. Do the work, then save the response and set done.
  5. Expire keys after a window (Stripe keeps them for at least 24 hours), so the table doesn't grow forever.
def create_payment(account_id: int, key: str, body: dict) -> tuple[int, dict]:
    h = sha256(json.dumps(body, sort_keys=True).encode()).hexdigest()
    with db.transaction():
        inserted = db.execute(
            "INSERT INTO idempotency_keys (account_id, idem_key, request_hash, status) "
            "VALUES (%s, %s, %s, 'started') ON CONFLICT DO NOTHING",
            account_id, key, h).rowcount == 1
    if not inserted:
        row = db.query_one("SELECT request_hash, status, response_code, response_body "
                           "FROM idempotency_keys WHERE account_id = %s AND idem_key = %s",
                           account_id, key)
        if row.request_hash != h:
            return 422, {"error": "idempotency key reused with a different request"}
        if row.status == "started":
            return 409, {"error": "request with this key is still in progress"}
        return row.response_code, row.response_body          # replay

    # We own the key. Pass a derived key downstream so the processor dedups too.
    try:
        charge = processor.charge(body["amount"], body["card"], idempotency_key=f"{account_id}:{key}")
    except CardDeclined as e:                        # a final answer: store it, so retries replay it
        code, resp = 402, {"error": "card_declined", "reason": e.reason}
        db.execute("UPDATE idempotency_keys SET status = 'done', response_code = %s, "
                   "response_body = %s WHERE account_id = %s AND idem_key = %s",
                   code, json.dumps(resp), account_id, key)
        return code, resp
    code, resp = 201, {"payment_id": charge.id, "status": charge.status}
    with db.transaction():
        db.execute("INSERT INTO payments (id, account_id, amount) VALUES (%s, %s, %s)",
                   charge.id, account_id, body["amount"])
        db.execute("UPDATE idempotency_keys SET status = 'done', response_code = %s, "
                   "response_body = %s WHERE account_id = %s AND idem_key = %s",
                   code, json.dumps(resp), account_id, key)
    return code, resp

Notice what the code does not do: it doesn't SELECT to check whether the key exists and then INSERT. Two copies arriving together would both see "not found" and both charge. The unique primary key is the lock.

Also notice the call to the processor sits between two transactions. A database transaction can't include a call to another company's API. If the server crashes after charging but before marking done, the key stays started. A final failure such as a hard card decline is stored as done with its error response, so a retry replays the decline instead of getting 409 until the recovery job runs. Only timeouts and unknown outcomes leave the key started. Two things make the crash case safe: the derived key sent to the processor (a retry of the charge returns the same charge instead of a new one), and a recovery job that finds keys stuck in started for more than a few minutes and finishes or rolls them back by asking the processor what happened.

4. The idempotent consumer (dedup table)

Queues give the same problem on the consuming side. A worker applies a message, crashes before acknowledging it, and the broker delivers it again.

Redelivery, the dedup table, and the side effect that escapes it

The fix is a processed_messages (message_id PRIMARY KEY) table, sometimes called an inbox. The worker inserts the message ID and applies the change in the same database transaction. A duplicate hits the primary key, the transaction rolls back, and the worker acknowledges the message and moves on. Because the dedup record and the effect commit together, there is no window where one exists without the other.

The message ID must be stable across redeliveries: the producer's event ID, not something the broker assigns per delivery attempt.

5. Sequence numbers and versions

When messages come from one ordered source, you don't need to remember every ID: remember the highest one applied. Kafka's idempotent producer works this way: each producer gets an ID and numbers its messages per partition, and the broker drops any message whose sequence it has already written. On the consumer side, store the last processed offset (or an entity version) in the same transaction as the result, and skip anything at or below it. This costs one number per partition or entity, not one row per message.

Comparing the tools

TechniqueGood atWeak atUse when
Naturally idempotent writesFree; no extra storageNot every operation can be rewrittenState updates, status changes
Unique constraint on a business keyAtomic, simple, permanentNeeds a natural key; one databaseOne shipment per order, one booking per seat
Idempotency key tableWorks for any API call; replays the exact responseExtra write per request; keys expirePublic APIs that create things: payments, orders
Dedup table in the consumerExact, atomic with the effectGrows with message volume; same database as the effectQueue consumers writing to a database
Sequence numbers / versionsOne number per stream, not per messageNeeds a single ordered sourceKafka partitions, per-entity event streams

Worked numbers: how big is the dedup store?

A payments API takes 2,000 requests per second on average and keeps keys for 24 hours.

  • Keys per day: 2,000 × 86,400 ≈ 173 M.
  • Each row: key 36 bytes, account ID 8, hash 32, status and timestamps ~20, saved response ~500 bytes ≈ 600 bytes, plus index overhead, call it 800.
  • Total: 173 M × 800 bytes ≈ 140 GB live at any time.

That fits comfortably in a sharded relational database, especially if the table is partitioned by day so expiring a day is a cheap DROP PARTITION instead of 173 M deletes. Each request adds two writes (insert, then mark done), so 2,000 requests/s become 4,000 key writes/s on top of the business writes. Shard by account_id so the key lives next to the account's data and can share its transaction.

A queue consumer is a different story. At 50,000 messages per second, keeping every message ID for 7 days (a typical Kafka retention, so replays are covered) is 50,000 × 604,800 ≈ 30 billion IDs. At 16 bytes each plus index overhead, that is over 1 TB just to remember what you've seen. This is why high-volume streams use sequence numbers per partition or versions per entity instead of per-message dedup tables, or keep IDs only for a short window and accept that a replay older than the window must be handled by natural idempotency.

Exactly once: what is actually promised

Vendors use the phrase for something narrower than it sounds. Know the boundaries:

SystemWhat it guaranteesWhere it stops
SQS standard queueAt least once; occasional duplicatesYour consumer must dedup
SQS FIFO queueDrops duplicates sent with the same deduplication ID within 5 minutesA retry after 5 minutes is a new message; consumers can still see redeliveries after a visibility timeout
Kafka idempotent producerNo duplicate writes from producer retries, per partition, while the producer session livesSays nothing about consumers
Kafka transactions ("exactly-once semantics")Read from Kafka, process, write to Kafka and commit offsets atomicallyThe moment you write to a database or call an API, you are back to at-least-once unless that sink is idempotent
Flink with checkpointsExactly-once state updates inside the job; exactly-once output with transactional or idempotent sinksExternal calls made from inside the job

The honest summary: exactly-once processing is achievable inside one boundary that can commit atomically (one database, or Kafka with its transactions). Across boundaries, it is at-least-once plus idempotency at every receiver.

When not to bother

  • Reads. GET requests are already idempotent; retry them freely.
  • Writes that are already idempotent. A full PUT of a profile, "set status to archived", an upsert keyed by a natural ID.
  • Low-stakes, high-volume events such as page views or analytics clicks. A dedup table per click costs more than the occasional double count. Dedup approximately later in a batch job, or accept the error.
  • When a unique constraint already does it. Don't build a key service for "one review per user per product": UNIQUE (user_id, product_id) is enough.

Which case studies use it

Related concepts: message queues, circuit breakers and retries.

In the interview

Your turn: a bank transfer API

A bank's mobile app calls POST /transfers {from, to, amount}. Clients retry up to 5 times over 2 minutes on timeouts, and some users tap the button twice. The transfer debits one account and credits another in the same database, then publishes a TransferCompleted event to Kafka that a notification service consumes to send a push message. Design the duplicate protection end to end.

Compare with our answer
  • The app generates an idempotency key when the user opens the confirm screen (not per tap, not per retry) and sends it on every attempt.
  • The server inserts (account_id, key, request_hash, 'started') first; the debit, the credit and marking the key done with the response all commit in one transaction, since everything is in one database.
  • A concurrent duplicate gets 409; a later one gets the saved response; a different body with the same key is rejected.
  • The event is written with a transactional outbox (same transaction) rather than published directly, so it can't be lost or published for a rolled-back transfer; it carries the transfer ID as its event ID.
  • The notification consumer dedups on the event ID (a short-window dedup table is fine) and accepts that a crash between sending and recording can rarely send two pushes.

A strong answer mentions: one key per logical transfer, created before the first attempt · insert-first, not check-then-insert · the effect and the key in one transaction · 409 for in-flight duplicates and request-hash checks · an event ID carried downstream · a named, accepted residual risk for the push message.

Your turn: spot the bugs

A team adds idempotency to their order API. The client wraps the call in a retry loop that does key = uuid4() and then post("/orders", body, headers={"Idempotency-Key": key}) on each attempt. The server does if redis.get(key): return saved then creates the order, then redis.set(key, response). Redis runs with allkeys-lru and one asynchronous replica. Customers still get duplicate orders. Find every bug.

Compare with our answer
  • The key is generated inside the retry loop, so every retry has a new key and nothing is ever recognised. Generate it once per logical order, before the loop.
  • Check-then-act race: two concurrent attempts both see no key and both create orders. Claim the key atomically first (SET key started NX EX 86400, or a unique insert).
  • The key is saved after the order is created and outside its transaction: a crash in between leaves an order with no key, and the retry creates another.
  • allkeys-lru can evict keys under memory pressure, silently turning retries into new orders.
  • Asynchronous replication: a failover can lose recently written keys.
  • No request hash: a reused key with a different body would replay the wrong order.

A strong answer mentions: key generated once outside the retry loop · atomic claim instead of get-then-set · key stored with the order in one transaction · eviction and failover risks of Redis as the only store · comparing a request hash.

Idempotency on one page
  • A request has three outcomes: success, failure, unknown. Retrying the unknown creates duplicates.
  • Idempotent = doing it twice has the same effect as once (effect, not response). GET, PUT, DELETE are; POST, PATCH are not.
  • Exactly-once = at-least-once delivery + idempotent processing. True only inside one atomic boundary.
  • Cheapest first: absolute or conditional writes (WHERE version = 7) → unique constraints on business keys → idempotency keys → dedup tables → sequence numbers.
  • Idempotency key: client creates one per logical operation; server inserts first (ON CONFLICT DO NOTHING), 409 while started, replay when done, reject a different body.
  • Store the key with the data, in the same transaction; pass a derived key to downstream APIs; a recovery job finishes stuck started keys.
  • Consumer: insert message ID + apply effect in one transaction; ID must come from the producer.
  • Window must exceed the latest possible duplicate. 2,000 req/s × 24 h ≈ 173 M keys ≈ 140 GB.
  • Side effects outside the transaction (email, push, third-party APIs) stay at-least-once: pass keys downstream, reconcile, or accept duplicates.
Check what stuck

1. A mobile app retries POST /orders when it gets a timeout. Where should the idempotency key be generated?

2. Two copies of the same payment request, with the same key, reach two servers within a millisecond. Which approach prevents a double charge?

3. A worker consumes "reserve stock" messages from an at-least-once queue and updates a Postgres table. What makes redeliveries harmless?

4. A team claims their pipeline is exactly-once because it uses Kafka transactions. The consumer writes to Kafka, then sends each customer an SMS. What is true?

5. A payments API keeps 24 hours of idempotency keys at 2,000 requests per second, about 800 bytes per key with indexes. Roughly how much storage is that?

6. Idempotency keys are stored only in Redis with allkeys-lru and one async replica. What is the main risk?

7. A server crashes after the card processor charged the card but before it marked the key done. The client retries. What should happen?

8. Which operation is already idempotent without any extra machinery?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.