Idempotency and deduplication

intermediateCommon atStripeAnthropicAmazonUberRead firstHash mapsAPI designPractise in the Sandbox →

An operation is idempotent if doing it twice has the same effect as doing it once. Networks make clients retry, so any operation with side effects needs a way to recognise a repeat. Give each logical request an idempotency key, remember the first result under that key, and replay it for every retry with the same payload. A lookup is O(1) in a hash map or unique index; the cost is storing keys for as long as retries can arrive.

The idea in plain words

You press “Pay” and the spinner hangs. Did the payment go through? The client has three possibilities and can’t tell them apart:

1. The request never reached the server.
2. The server did the work, but the response got lost.
3. The server crashed halfway.

The only safe move is to retry. But a naive retry in case 2 charges twice. Idempotency turns “retry” from dangerous into boring.

Some operations are idempotent by nature. SET status = 'shipped' twice is the same as once. DELETE /orders/7 twice leaves the order deleted. Others are not: balance += 500, “send an email”, “create a charge”. For those, the server needs memory of what it has already done.

That memory is keyed by something the client controls and sends with every attempt: an idempotency key, usually a random UUID created once per user intent (one click of “Pay”), reused on every retry of that intent.

At-least-once + dedupe = effectively once

Message queues (SQS, Kafka, Pub/Sub) promise at-least-once delivery: a message may arrive twice, especially after a consumer crash before it acknowledged. “Exactly-once” in practice means at-least-once delivery plus an idempotent or deduplicating consumer. Same idea, other side of the wire.

See it

Turn on drop responses, send, then retry: the server replays the stored response and money moves once. Now change the amount and retry with the same key: refused. Click Send twice at once to see a concurrent duplicate get 409. Finally untick server honors keys and repeat: the side-effect list shows the double charge.

Idempotency keys: retry without double charging

sandbox

Idempotency-Keyamount (¢)todrop responsesserver honors keys

Send POST /v1/transfersSend twice at onceNew key↺ Reset

server key store

(empty)

side effects (money moved)

(none)

log (newest first)

Turn on "drop responses", send, then retry. Then change the amount and retry with the same key.

The status codes follow the IETF Idempotency-Key header draft: 400 when a required key is missing, 409 when a request with that key is still in flight, 422 when a key is reused with a different payload. Stripe returns its own idempotency_error type for the mismatch case but the behaviour is the same.

When to reach for it

The problem says…	Why idempotency fits
“clients retry”, “the network may drop responses”, “timeouts”	Retries are only safe if the server recognises a repeat.
“charge”, “transfer”, “refund”, “send”, “create” (any non-repeatable side effect)	These are not idempotent by nature; they need a key.
“messages may be delivered more than once” / “at-least-once”	The consumer must dedupe by message id or sequence number.
“webhooks”	Providers redeliver until you return 2xx. Store the event id you processed.
“the same event from several redundant sources”	Dedupe by a natural id carried in the event.

How it works

The server side of an idempotency key

1. Read the key from the request header. Compute a fingerprint of the request (method, path, canonical body).
2. Atomically claim the key: insert a row (key, fingerprint, status=in_flight) with a unique constraint. If the insert fails, a row exists: go to step 3. Otherwise go to step 4.
3. Existing key. Different fingerprint: reject (422). Still in flight: reject (409, retry later). Done: return the stored status and body, and do nothing else.
4. New key. Validate, then execute the side effect, then store the response under the key in the same transaction as the side effect where possible.
5. Expire keys after a retention window (Stripe: at least 24 hours) so storage doesn’t grow forever.

Two decisions in that list matter in interviews:

• What gets stored. Stripe saves the result of the first request that started executing, including 500 errors, so a retry gets the same answer. Requests that fail validation before execution, or that hit a concurrent conflict, store nothing, so the client can fix the request and reuse the key.
• Why compare payloads. A key reused with a different body is almost always a client bug (a reused variable, a copy-paste). Silently replaying the old result would hide it; executing the new body would defeat the point of the key.

The fingerprint is the building block that makes “same request?” a cheap string compare:

Python

fingerprint.py

import hashlib
import json
from typing import Any


def canonical(payload: Any) -> str:
    """1. One spelling per meaning: sorted keys, no whitespace, UTF-8 kept as-is."""
    return json.dumps(payload, sort_keys=True, separators=(",", ":"), ensure_ascii=False)


def fingerprint(method: str, path: str, payload: Any) -> str:
    """2. Hash what the client asked for, including *which* endpoint, so a key reused
    on another endpoint or with another body is detected as a mismatch."""
    raw = f"{method.upper()} {path}\n{canonical(payload)}"
    return hashlib.sha256(raw.encode("utf-8")).hexdigest()


if __name__ == "__main__":
    a = fingerprint("post", "/v1/transfers", {"amount": 500, "to": "acct_9", "meta": {"x": 1, "y": 2}})
    b = fingerprint("POST", "/v1/transfers", {"meta": {"y": 2, "x": 1}, "to": "acct_9", "amount": 500})
    c = fingerprint("POST", "/v1/transfers", {"amount": 5000, "to": "acct_9", "meta": {"x": 1, "y": 2}})
    assert a == b          # 3. same request, different key order: same fingerprint
    assert a != c          # 4. different amount: a retry with this key must be refused
    assert len(a) == 64
    print("ok")

TypeScript

fingerprint.ts

import assert from "node:assert/strict";
import { createHash } from "node:crypto";

type Json = null | boolean | number | string | Json[] | { [k: string]: Json };

/** 1. One spelling per meaning: object keys sorted recursively, no whitespace. */
export function canonical(v: Json): string {
  if (Array.isArray(v)) return `[${v.map(canonical).join(",")}]`;
  if (v !== null && typeof v === "object") {
    const keys = Object.keys(v).sort(); // code-unit order, same as Python for ASCII keys
    return `{${keys.map((k) => `${JSON.stringify(k)}:${canonical(v[k])}`).join(",")}}`;
  }
  return JSON.stringify(v);
}

/** 2. Hash the endpoint too, so a key reused elsewhere is caught as a mismatch. */
export function fingerprint(method: string, path: string, payload: Json): string {
  const raw = `${method.toUpperCase()} ${path}\n${canonical(payload)}`;
  return createHash("sha256").update(raw, "utf8").digest("hex");
}

const a = fingerprint("post", "/v1/transfers", { amount: 500, to: "acct_9", meta: { x: 1, y: 2 } });
const b = fingerprint("POST", "/v1/transfers", { meta: { y: 2, x: 1 }, to: "acct_9", amount: 500 });
const c = fingerprint("POST", "/v1/transfers", { amount: 5000, to: "acct_9", meta: { x: 1, y: 2 } });
assert.equal(a, b); // 3. key order doesn't matter
assert.notEqual(a, c); // 4. a different amount must be refused under the same key
assert.equal(a.length, 64);
console.log("ok");

C#

fingerprint.cs

using System.Security.Cryptography;
using System.Text;
using System.Text.Json;

var a = Fp.Fingerprint("post", "/v1/transfers", """{"amount":500,"to":"acct_9","meta":{"x":1,"y":2}}""");
var b = Fp.Fingerprint("POST", "/v1/transfers", """{ "meta": {"y":2, "x":1}, "to":"acct_9", "amount":500 }""");
var c = Fp.Fingerprint("POST", "/v1/transfers", """{"amount":5000,"to":"acct_9","meta":{"x":1,"y":2}}""");
if (a != b) throw new Exception("3. key order must not matter");
if (a == c) throw new Exception("4. a different amount must give a different fingerprint");
if (a.Length != 64) throw new Exception("sha-256 hex is 64 chars");
Console.WriteLine("ok");

static class Fp
{
    // 1. One spelling per meaning: object keys sorted (ordinal), no whitespace.
    static void Write(JsonElement e, StringBuilder sb)
    {
        switch (e.ValueKind)
        {
            case JsonValueKind.Object:
                sb.Append('{');
                var props = e.EnumerateObject().OrderBy(p => p.Name, StringComparer.Ordinal).ToList();
                for (int i = 0; i < props.Count; i++)
                {
                    if (i > 0) sb.Append(',');
                    sb.Append(JsonSerializer.Serialize(props[i].Name)).Append(':');
                    Write(props[i].Value, sb);
                }
                sb.Append('}');
                break;
            case JsonValueKind.Array:
                sb.Append('[');
                int n = 0;
                foreach (var item in e.EnumerateArray()) { if (n++ > 0) sb.Append(','); Write(item, sb); }
                sb.Append(']');
                break;
            default:
                sb.Append(e.GetRawText()); // numbers, strings, true/false/null as written
                break;
        }
    }

    // 2. Hash the endpoint too, so a key reused elsewhere is caught as a mismatch.
    public static string Fingerprint(string method, string path, string json)
    {
        using var doc = JsonDocument.Parse(json);
        var sb = new StringBuilder($"{method.ToUpperInvariant()} {path}\n");
        Write(doc.RootElement, sb);
        return Convert.ToHexString(SHA256.HashData(Encoding.UTF8.GetBytes(sb.ToString()))).ToLowerInvariant();
    }
}

Consumer-side dedupe with sequence numbers

If each sender numbers its messages 1, 2, 3, … and resends until acknowledged (like TCP), the receiver only needs one number per sender: the highest sequence it has applied. Anything at or below it is a duplicate.

1. seq <= last: a redelivery. Acknowledge again, change nothing.
2. seq > last + 1: something in between is missing. Refuse, so the sender resends in order.
3. seq == last + 1: apply the effect and advance last, atomically.

Python

Inbox.deliver.py

from dataclasses import dataclass, field


@dataclass
class Inbox:
    """At-least-once delivery, exactly-once effect, O(1) memory per sender.
    Each sender numbers its messages 1, 2, 3, ... and resends until acknowledged."""
    applied_upto: dict[str, int] = field(default_factory=dict)   # sender -> high-water mark
    total: int = 0                                               # the state we protect

    def deliver(self, sender: str, seq: int, delta: int) -> str:
        last = self.applied_upto.get(sender, 0)
        if seq <= last:                       # 1. seen before: re-ack, change nothing
            return "duplicate"
        if seq > last + 1:                    # 2. a gap: refuse so the sender resends in order
            return "gap"
        self.total += delta                   # 3. apply the effect and advance the mark
        self.applied_upto[sender] = seq       #    together (one transaction in a real DB)
        return "applied"


if __name__ == "__main__":
    box = Inbox()
    wire = [("a", 1, 10), ("a", 2, 5), ("a", 2, 5), ("b", 1, 7), ("a", 4, 1), ("a", 1, 10), ("a", 3, 2)]
    results = [box.deliver(*m) for m in wire]
    assert results == ["applied", "applied", "duplicate", "applied", "gap", "duplicate", "applied"]
    assert box.total == 10 + 5 + 7 + 2          # redeliveries had no effect
    assert box.applied_upto == {"a": 3, "b": 1}
    print("ok")

TypeScript

Inbox.deliver.ts

import assert from "node:assert/strict";

type Outcome = "applied" | "duplicate" | "gap";

/** At-least-once delivery, exactly-once effect, O(1) memory per sender.
 *  Each sender numbers its messages 1, 2, 3, ... and resends until acknowledged. */
export class Inbox {
  readonly appliedUpto = new Map<string, number>(); // sender -> high-water mark
  total = 0; // the state we protect

  deliver(sender: string, seq: number, delta: number): Outcome {
    const last = this.appliedUpto.get(sender) ?? 0;
    if (seq <= last) return "duplicate"; // 1. seen before: re-ack, change nothing
    if (seq > last + 1) return "gap"; // 2. refuse so the sender resends in order
    this.total += delta; // 3. apply the effect and advance the mark together
    this.appliedUpto.set(sender, seq);
    return "applied";
  }
}

const box = new Inbox();
const wire: [string, number, number][] = [["a", 1, 10], ["a", 2, 5], ["a", 2, 5], ["b", 1, 7], ["a", 4, 1], ["a", 1, 10], ["a", 3, 2]];
assert.deepEqual(wire.map(([s, q, d]) => box.deliver(s, q, d)),
  ["applied", "applied", "duplicate", "applied", "gap", "duplicate", "applied"]);
assert.equal(box.total, 10 + 5 + 7 + 2); // redeliveries had no effect
assert.deepEqual(Object.fromEntries(box.appliedUpto), { a: 3, b: 1 });
console.log("ok");

C#

Inbox.deliver.cs

var box = new Inbox();
(string, long, long)[] wire = [("a", 1, 10), ("a", 2, 5), ("a", 2, 5), ("b", 1, 7), ("a", 4, 1), ("a", 1, 10), ("a", 3, 2)];
var results = wire.Select(m => box.Deliver(m.Item1, m.Item2, m.Item3)).ToArray();
Outcome[] expected = [Outcome.Applied, Outcome.Applied, Outcome.Duplicate, Outcome.Applied, Outcome.Gap, Outcome.Duplicate, Outcome.Applied];
if (!results.SequenceEqual(expected)) throw new Exception(string.Join(",", results));
if (box.Total != 10 + 5 + 7 + 2) throw new Exception("redeliveries must have no effect");
if (box.AppliedUpto["a"] != 3 || box.AppliedUpto["b"] != 1) throw new Exception("high-water marks");
Console.WriteLine("ok");

enum Outcome { Applied, Duplicate, Gap }

/// At-least-once delivery, exactly-once effect, O(1) memory per sender.
/// Each sender numbers its messages 1, 2, 3, ... and resends until acknowledged.
class Inbox
{
    public Dictionary<string, long> AppliedUpto { get; } = []; // sender -> high-water mark
    public long Total { get; private set; }                     // the state we protect

    public Outcome Deliver(string sender, long seq, long delta)
    {
        long last = AppliedUpto.GetValueOrDefault(sender);
        if (seq <= last) return Outcome.Duplicate; // 1. seen before: re-ack, change nothing
        if (seq > last + 1) return Outcome.Gap;    // 2. refuse so the sender resends in order
        Total += delta;                            // 3. apply the effect and advance the mark
        AppliedUpto[sender] = seq;                 //    together (one DB transaction)
        return Outcome.Applied;
    }
}

Store the effect and the dedupe record together

If you apply the effect, then crash before recording the key (or the high-water mark), the retry applies it again. If you record first and crash before applying, the retry is skipped and the effect is lost. Put both in one database transaction. When the side effect is in another system (calling a card network), you need recovery points: Brandur Leach’s design stores progress per key (“started”, “charge created”, “finished”) so a retry resumes from the last completed step.

What it costs

Approach	Memory	Lookup	Handles out-of-order?
Key → stored response, unique index	O(keys in retention window)	O(1) hash / O(log n) B-tree	yes
Set of processed message ids	O(ids in window)	O(1)	yes
High-water mark per sender	O(senders)	O(1)	no: needs in-order delivery per sender
Bloom filter of seen ids	tiny, fixed	O(k) hashes	yes, but false positives drop real messages

The retention window is a trade-off between storage and safety. It must be longer than the longest realistic retry horizon (client backoff, queue redelivery delay). Expire keys with a TTL index or a periodic sweep; see TTL and expiry.

Variations you’ll meet

• Natural keys. Sometimes the payload already has a unique business id (order_id, invoice_id, a webhook event.id). A unique constraint on it is the cheapest dedupe of all.
• Conditional writes. “Update only if version is still 41” (compare-and-set, If-Match ETags). A retry of an already-applied update fails the condition harmlessly.
• Making the operation itself idempotent. Turn “add 5 credits” into “set credits for grant G to 5”, or “append entry with id E” where E is unique. Idempotent by construction beats remembering.
• Scope of keys. Per account or global? Stripe scopes keys to the account. A global key space risks collisions between tenants; a per-user one needs the user in the lookup.
• Exactly-once processing in streams (Kafka transactions, Flink checkpoints) combines offsets and output in one atomic commit: the same “store the effect and the marker together” rule.

Pitfalls

• Generating the key on each attempt. The key must be created once per user intent and reused across retries. A new UUID per HTTP call dedupes nothing.
• Check-then-insert races. if key not in store: execute() lets two concurrent retries both pass the check. Claim the key with an atomic insert or a lock.
• Replaying for a different payload. Always compare a fingerprint; reject mismatches.
• Expiring keys too soon. A retry arriving after expiry is treated as new and executes again.
• Caching transient failures forever. Decide which outcomes are final. Validation errors usually shouldn’t burn the key; a 500 after execution started usually should be replayed, not retried blindly.
• Assuming GET is the only safe retry. PUT and DELETE are idempotent by HTTP semantics only if you implement them that way.

In the interview

• Ask: Can clients retry? Who generates the key? How long can a retry arrive after the original? Are keys per customer or global? What should a reused key with different data do?
• Say the invariant out loud: “For each key there is at most one execution. Every later request with the same key and payload gets the first response.”
• Name the race: “Two retries can arrive at once, so claiming the key has to be atomic. I’ll insert an in-flight marker first.”
• Separate the cases: duplicate (replay), conflict (reject), in flight (409), expired (treat as new).
• Follow-ups to expect: key expiry, refunds that share the key space with charges, crash between side effect and record, distributed storage for keys (see distributed thinking).

Check yourself

Check yourself

pick one

A mobile app generates a fresh UUID idempotency key inside its HTTP helper, right before each network call, including retries. What happens when a response is lost and the helper retries?

AThe server replays the first responseBThe server executes the request again, because it sees a new keyCThe server returns 409 ConflictDThe server returns 422 because the payload is identical

Check yourself

pick one

Your handler does: look up key; if absent, call the payment network, then insert the key with the response. Two copies of a request arrive within 5 ms. What can go wrong?

ANothing; the second lookup will see the keyBBoth lookups can miss before either insert, so the payment executes twiceCThe second request always gets 422DThe unique index makes the payment network reject the duplicate

Check yourself

pick one

A consumer keeps only the highest applied sequence number per sender. Messages from one sender can arrive out of order. Is that enough?

AYes, a high-water mark handles any orderBNo: if 3 arrives before 2 and you apply 3, then 2 looks like a duplicate and is lostCYes, as long as the mark is stored in a databaseDNo, because high-water marks need O(n) memory

Practice on your own

Classic exercises, not gym questions:

• Make a webhook receiver idempotent: dedupe by event id, and make the side effect and the “processed” record atomic with SQLite.
• Write a canonical JSON function and prove two payloads with different key order and whitespace hash the same.
• Turn “increment counter” into an idempotent operation by changing the data model rather than adding a dedupe store.
• Simulate a lossy channel with random drops and duplicates, and show a sender with retries plus a sequence-number receiver ends with each message applied once.

Go deeper

• Brandur Leach, Designing robust and predictable APIs with idempotency (Stripe blog): why keys, how clients retry with backoff and jitter.
• Brandur Leach, Implementing Stripe-like idempotency keys in Postgres: atomic phases, recovery points and the in-flight lock.
• Stripe API reference, Idempotent requests: what is stored, 24-hour retention, parameter comparison.
• IETF draft, The Idempotency-Key HTTP Header Field: the 400 / 409 / 422 semantics.

Related

Ledgers and double entryThe entries an idempotent request must post exactly once.

TTL and expiryRetention windows for stored keys.

Event-driven systemsAt-least-once delivery and idempotent consumers.

API designDesigning endpoints that are safe to retry.