CS Fundamentals Trainer · Guides
Idempotency and exactly-once effects: keys, retries and deduplication
Why a timeout makes retries, and so duplicates, unavoidable; naturally idempotent designs; idempotency keys and the race in check-then-act (465 extra charges against none); foreign calls and recovery points; the outbox and the inbox; and what keeping the keys costs.
30 min read
A customer taps "Pay", the request leaves the phone, and nothing comes back. Did the payment happen? The phone cannot know. The request might never have arrived, it might still be running, or it might have finished and the answer got lost on the way back. The only safe-looking move is to send it again, and that is exactly the move that can charge the customer twice.
Every system that talks over a network has to resolve this, and the resolution has a name: make the operation idempotent, so that doing it twice has the same effect as doing it once. This guide covers what that means, how to build it correctly (the obvious implementation has a race that I reproduce), what to do when the work involves another system you cannot roll back, how it applies to queue consumers, and what it costs to keep.
A note on measurements. The numbers in this guide come from a small experiment that I ran for it: a real HTTP server on localhost, SQLite and Python 3.13, with the full code in the appendix. The scenario is deliberately tight (a client that gives up after 50 ms against a handler that takes 30 to 120 ms) so that retries happen often. In production they are rarer, but they are never zero, and rare events at scale happen every day.
1. Why retries are unavoidable, and why they hurt
A request over a network can fail in three ways, and the caller sees the same thing in all of them: a timeout, or a dropped connection, and no answer.
| What really happened | The caller sees | Is a retry safe without protection? |
|---|---|---|
| The request never reached the server | no answer | yes: nothing happened |
| The server is still working on it | no answer (yet) | no: two copies now run |
| The server finished, the response was lost | no answer | no: the work is done twice |
A caller cannot tell these apart, so it has two options: give up (and risk a lost operation) or retry (and risk a duplicate). Mature systems retry, because most failures are transient, and so they need the server to make the second case harmless. Retries come from more places than your own code: HTTP clients, mobile SDKs, proxies and load balancers, queue brokers redelivering a message, and users pressing the button again.
Messaging systems describe the same problem as delivery guarantees: at-most-once (never duplicate, may lose), at-least-once (never lose, may duplicate) and exactly-once. Exactly-once delivery across an unreliable network cannot be guaranteed by anyone: the sender can never be sure the receiver got the message, which is the old Two Generals problem. What you can have is exactly-once effect, and it is built from two parts:
at-least-once delivery (retry until acknowledged) + idempotent processing (a repeat changes nothing) = exactly-once effect
Everything below is about the second half.
The damage, measured
In my experiment 200 payments of 100 each were sent to a server that charges a card (simulated by a delay of 30 to 120 ms and a database insert). The client waits 50 ms and retries up to five times, 20 payments at a time:
| Server behaviour | Requests sent | Payments the client saw succeed | Charges for 200 payments | Extra charges |
|---|---|---|---|---|
| No idempotency | 670 | 134 | 665 | 465 (one payment was charged 5 times) |
| A key, checked before the work ("naive") | 465 | 200 | 315 | 115 |
| A key, claimed atomically before the work | 505 | 200 | 200 | 0 |
Two things stand out. Without protection every one of the 200 payments was charged, but the client was told it succeeded for only 134: 66 payments were charged and reported as failures, which is the worst combination, because the next thing a user does is try again. And the middle row shows that having an idempotency key is not enough. Having it implemented correctly is, and section 4 shows the difference.
2. What idempotent means (and what it does not)
An operation is idempotent if performing it once or many times leaves the system in the same state. In arithmetic, abs(abs(x)) == abs(x). In APIs:
set balance to 50is idempotent;add 10 to the balanceis not.set status to "paid"is idempotent;send a receipt emailis not.create user 7 with this data(client chooses the id) is idempotent;create a user(server picks the id) is not.
HTTP builds this into its method semantics. RFC 9110 defines GET, HEAD, OPTIONS, PUT and DELETE as idempotent (and the first three as also safe, meaning read-only). POST and PATCH are not, which is exactly why those are the methods that need extra help. Three clarifications avoid common confusions:
- Idempotent means the effect repeats harmlessly, not that the response is identical. The second
DELETE /orders/7may return 404 because the order is already gone, and it is still idempotent: the system ends in the same state. - Idempotent is not the same as safe.
PUTchanges state; it just changes it to the same thing every time. - "The method is idempotent" is a promise made by whoever writes the server. HTTP does not enforce it. A
PUThandler that also appends a log row, increments a counter or sends an email is no longer idempotent in any sense you care about.
The cheapest fix: make the operation naturally idempotent
Before building any machinery, see whether the design can avoid needing it:
- Let the client choose the identifier.
PUT /payments/9f3c…creates payment9f3c…or finds that it exists. The identifier is the idempotency key, and a unique constraint on it does the rest. - Set states instead of changing amounts.
UPDATE orders SET status = 'paid' WHERE id = ?can run ten times.UPDATE accounts SET balance = balance - 100cannot. - Use compare-and-set.
UPDATE orders SET status = 'shipped' WHERE id = ? AND status = 'paid'succeeds once; the second run affects zero rows, which you can treat as "already done". This is the same idea as the expected version in an event store. - Upsert instead of insert.
INSERT … ON CONFLICT DO NOTHINGorDO UPDATEturns "create" into "ensure".
Naturally idempotent operations are the best kind: no key table, no expiry, no extra round trip. The rest of this guide is for the operations that cannot be made so, such as charging a card, creating something whose identifier the server must choose, or sending a message.
3. Idempotency keys
When an operation cannot be naturally idempotent, you make it so with a key: a unique value that identifies one logical operation, which the client sends with every attempt of it. The server remembers what happened for each key and, when the key shows up again, returns the remembered result instead of doing the work again.
Diagram: One logical operation, one key, several attempts
The rules of the protocol
- One key per logical operation, reused on every retry. A new key per attempt defeats the whole mechanism. The key is created when the user's intent is created (the click, the order draft), not when the HTTP call is made. A client library that retries internally must generate the key before its first attempt.
- The client generates it. A random UUID (version 4) has enough entropy. Stripe suggests V4 UUIDs or another random string and allows keys up to 255 characters; the IETF draft recommends a UUID as well. Do not use sensitive data such as an email address as a key.
- The server stores the key together with a fingerprint of the request. If the same key arrives with a different body, that is a bug in the client (or an attack), and the right answer is an error, not silently replaying the old result. Stripe compares the parameters and errors if they differ; the AWS Builders' Library says the service returns a validation error for a different request under the same identifier. Amazon deliberately prefers a caller-supplied identifier over a hash of the parameters, because two identical requests can both be intentional (two identical servers launched on purpose).
- A repeated key returns the stored response. Not an error such as "already exists": that pushes the problem back to the caller, who cannot tell whether their request created the thing. The AWS article makes the same point and asks for a response that is semantically equivalent to the first one.
- Scope keys. A key is unique per caller (per account or per API credential), not globally. Otherwise one customer can collide with, or replay, another's.
The responses to use
The IETF Idempotency-Key header draft (draft-ietf-httpapi-idempotency-key-header, version 08 when I read it on 26 October 2026; it is still an Internet-Draft and not yet an RFC) is a good reference for the status codes, and it matches what Stripe and others do in spirit:
| Situation | Response |
|---|---|
| Key missing on an endpoint that requires it | 400 Bad Request |
| Key seen before, finished | the stored response (same status and body), often with a header marking it a replay |
| Key seen before, the first request is still running | 409 Conflict (the client retries shortly) |
| Key seen before with a different payload | 422 Unprocessable Content |
The draft targets POST and PATCH, the methods that are not idempotent by definition. It treats the key as a structured-field string, says keys must not be reused with a different payload, and lets a service expire them according to a published policy.
The A2 part of my experiment shows these in action: the first call returns 201 {'charge': 1}, the same call again returns 200 {'charge': 1} (the same charge, replayed), and the same key with a different body returns 422.
4. Implementing it correctly: claim first
Here is the implementation almost everyone writes first:
def charge(key, request):
row = db.query("SELECT response FROM idempotency WHERE key = %s", key)
if row:
return row.response # seen it: replay
result = do_the_work(request) # slow, maybe 100 ms
db.execute("INSERT INTO idempotency (key, response) VALUES (%s, %s)", key, result)
return result
It looks right and it has a race: two requests with the same key that arrive close together (exactly what a retry after a timeout is) both run the SELECT, both find nothing, and both do the work. The first one has not recorded its result yet when the second one checks.
I measured it. Eight threads presented the same key at the same moment, 400 times:
| Strategy | Rows for 400 keys | Keys claimed more than once |
|---|---|---|
SELECT first, then INSERT, no constraint | 3,192 | 400 (every key) |
Unique constraint, INSERT OR IGNORE, the winner is whoever inserted | 400 | 0 |
The fix is to stop checking and start claiming: let the database decide who wins, using a unique constraint, before doing the work.
CREATE TABLE idempotency_keys (
account_id bigint NOT NULL,
key text NOT NULL,
fingerprint text NOT NULL, -- hash of method, path and body
state text NOT NULL, -- 'started' | 'done'
locked_at timestamptz, -- when a worker took it (see below)
status_code int,
response jsonb,
created_at timestamptz NOT NULL DEFAULT now(),
PRIMARY KEY (account_id, key)
);
def charge(account, key, request):
fp = sha256(canonical(request))
claimed = db.execute("""
INSERT INTO idempotency_keys (account_id, key, fingerprint, state, locked_at)
VALUES (%s, %s, %s, 'started', now())
ON CONFLICT DO NOTHING""", account, key, fp).rowcount == 1
if not claimed: # someone has this key
row = db.query("SELECT * FROM idempotency_keys WHERE account_id=%s AND key=%s", account, key)
if row.fingerprint != fp: return 422, {"error": "key used with a different request"}
if row.state == "started": return 409, {"error": "still being processed"} # Retry-After
return row.status_code, row.response # replay
with db.transaction(): # the work and the key's result commit together
result = do_the_work(request) # writes to the same database
db.execute("""UPDATE idempotency_keys SET state='done', status_code=201, response=%s
WHERE account_id=%s AND key=%s""", result, account, key)
return 201, result
Three details matter here:
- The claim is one atomic statement.
INSERT … ON CONFLICT DO NOTHING(Postgres) orINSERT OR IGNORE(SQLite) either inserts the row or reports that it did not. There is no window between "check" and "act". - The work and the "done" marker commit in one transaction, so there is no state where the work happened but the key says it did not (the retry would redo it) or the key says it did but the work is missing. The AWS article puts it exactly: recording the token and performing the mutations must be a single all-or-nothing operation. This is only possible when the work is in the same database as the key table.
- "Still running" is a real state. A retry can arrive while the first attempt is in flight, which is the common case when the client timed out because the server is slow. The simplest answer is
409with aRetry-After, and the client's retry loop handles it. The alternative is to make the second request wait on the first (a row lock withSELECT … FOR UPDATE) and return its result; that is friendlier but holds a connection and a thread.
My third experiment row is this design: 200 payments, 505 requests sent (the extra ones are retries and 409s), 200 acknowledged, exactly 200 charges.
What if the first attempt crashes?
A crash between the claim and the commit leaves a key stuck in started. If the work was in the same transaction as the key update, the work rolled back too, so it is safe to try again, but the key still says started and a retry would get 409 forever. The usual fix is a lease: record locked_at, and treat a started row older than some timeout (longer than the slowest legitimate request) as abandoned, so a retry may take it over. Make the takeover itself atomic (UPDATE … SET locked_at = now() WHERE key = … AND locked_at < now() - interval '30 seconds', and check the row count), for the same reason as the claim.
5. When the work is not in your database
Charging a card, sending an email, calling a partner's API: these are foreign state mutations, and your database transaction cannot roll them back. The neat design of section 4 breaks, because there are now two systems, and a crash can happen between them:
- Call the card network first and then commit: a crash after the call leaves a charge with no record. A retry charges again.
- Commit first and then call: a crash after the commit leaves a record saying "done" for something that never happened.
The pattern that holds up, described in detail in Brandur Leach's article on implementing Stripe-style idempotency keys in Postgres, has three parts:
- Split the request into atomic phases and store a recovery point (a named checkpoint) in the key row at the end of each phase. A retry reads the recovery point and resumes instead of starting over.
- Commit before you reach outside. The phase that records "about to call the card network" is committed first. As Brandur puts it, atomic phases should be safely committed before initiating any foreign state mutation, so a retry can see that the call was at least attempted.
- Give the outside call its own idempotency key, derived from yours (for example,
"charge-" + key), so that if your retry repeats the call, the other system recognises it and does not charge twice. Most payment providers support exactly this.
Diagram: Recovery points around a foreign call
If the provider has no idempotency support, you cannot make the call exactly-once yourself. You are left with choosing a failure mode (accept a rare duplicate, or accept a rare "unknown" and settle it by reconciliation: ask the other system what actually happened, usually by a lookup on a reference you sent), which is also what finance teams do as a final safety net regardless.
Messages as outgoing side effects: the outbox
Publishing an event after a database change has the same two-systems problem. The transactional outbox solves the first half: write the event to an outbox table in the same transaction as the state change, and let a separate relay publish the rows to the broker. That gives at-least-once publishing, because the relay can crash after publishing and before marking the row as sent. Which means the consumers must deduplicate. That is the next section.
6. Queue consumers and the inbox
A broker that guarantees at-least-once delivery will redeliver a message when the consumer does not acknowledge it in time or crashes before doing so. So every consumer sees duplicates. The question is where in the processing order the duplicate check sits.
I simulated 10,000 "credit 1" messages with a consumer that crashes 10% of the time at the worst possible moment, and the broker redelivers until the message is acknowledged:
| Consumer strategy | Expected balance | Result | Verdict |
|---|---|---|---|
| No deduplication | 10,000 | 11,098 (+1,098) | duplicates |
| Apply the effect, then record the message id (two commits) | 10,000 | 11,098 (+1,098) | duplicates: the crash falls between the two, so the id was never recorded |
| Record the message id, then apply the effect (two commits) | 10,000 | 9,011 (−989) | lost updates: the id is recorded but the effect never happened, and redelivery is skipped |
| Effect and message id in one transaction | 10,000 | 10,000 | correct |
| Naturally idempotent (set a state per message) | 10,000 | 10,000 | correct |
The lesson is the same as in section 4: whatever makes the operation "exactly-once" has to be atomic with the operation. The standard form is an inbox (or processed-messages) table with the message id as primary key:
BEGIN;
INSERT INTO processed_messages (message_id) VALUES ($1) ON CONFLICT DO NOTHING; -- 0 rows? already done
-- only if a row was inserted:
UPDATE accounts SET balance = balance + $2 WHERE id = $3;
COMMIT;
This works when the effect lives in the same database as the inbox. When the effect is outside it, you are back in section 5: make the effect naturally idempotent, or pass a derived key to the system that does it.
What brokers do and do not give you
- Amazon SQS FIFO queues deduplicate sends within a 5-minute interval, using either an explicit deduplication id or a SHA-256 hash of the message body. A retry of the send inside the window adds no duplicate. After the window, a resend is a new message.
- Kafka has an idempotent producer (available since version 0.11): the broker assigns each producer an id and deduplicates its sends with sequence numbers, so a producer retry cannot write a message twice to the log. Kafka also has transactions, which let a consumer-processor-producer pipeline write its outputs and its consumed offsets atomically, and consumers using the
read_committedisolation level see only committed transactional messages. For an external system, Kafka's documentation points to storing the offsets together with the data, so that both are updated or neither is.
Read these guarantees carefully: they protect the broker's own log against duplicates caused by its retries. They do not know about your business operation. If a user clicks twice and your API publishes two different messages, both are delivered, and no broker feature will merge them. The idempotency key on your API (section 3) is what catches that, and the inbox (this section) is what catches redelivery. You need to put each where it belongs.
7. How long to keep keys, and what they cost
A dedupe table grows with every write, so it needs a retention window: long enough to cover the longest realistic retry, short enough to afford.
- Stripe's v1 API says keys can be removed automatically once they are at least 24 hours old, and that a key reused after pruning produces a new request. SQS FIFO's window is 5 minutes. Your window is the longest delay you expect between a first attempt and its last retry, including a mobile app that comes back online hours later and a job queue backed up for a day.
- What happens after expiry is a duplicate, so add a backstop that does not expire: a unique constraint on a natural business key (for example, one payment per order and attempt number), or a state machine that cannot go from "paid" to "paid".
What does it cost? I loaded one million rows, each a 36-character UUID key with a 120-byte stored response, into SQLite with a primary-key index:
| Measure | Result |
|---|---|
| Size on disk | 229 MB, about 229 bytes per key (table and index) |
| Load time | 10.7 s for one million rows |
| Deleting half of them by creation time | 3.8 s |
Extrapolating that size for a 24-hour window:
| Writes per second | Keys per day | Storage for 24 h |
|---|---|---|
| 100 | 8.6 million | about 2 GB |
| 1,000 | 86.4 million | about 20 GB |
| 10,000 | 864 million | about 200 GB |
So at high volumes the key store is a real component to be sized, partitioned and expired: partition the table by day and drop whole partitions rather than running big deletes, or keep keys in a store with built-in expiry (a key-value store with a TTL). If you use a TTL store such as Redis for the claim, remember that the "work plus key" atomicity of section 4 is then gone, because the work and the key live in different systems, and you are back to the situation of section 5.
8. Common mistakes
- A new key for each retry. Then nothing is ever recognised as a repeat. The key belongs to the operation.
- The server generating the key. The client needs it before the first attempt, so the server cannot make it up after the fact.
- Check-then-act instead of claim-first. It passes every test that sends requests one at a time. It fails the one case that matters.
- Recording the result after the work in a separate commit. A crash in between means a done operation with no record, or a record of an operation that did not happen.
- Using a hash of the request body as the key. It stops two legitimate, identical requests (two coffees at the same price) from both being served. Use a random key, and use the hash only as a fingerprint to detect misuse.
- Not scoping keys per account, so one caller can collide with or replay another's.
- Replying "already exists" instead of the original response. The caller still does not know whether the operation worked.
- Forgetting the in-flight case: no
409or wait, so a quick retry starts a second copy. - No expiry, and one day the key table is the biggest table in the database. Or an expiry shorter than your retries, which brings the duplicates back.
- Calling an external system inside the database transaction and assuming a rollback will undo it.
- Trusting a broker's "exactly-once" label to cover your database and your side effects.
- Retrying everything blindly. Retries need a limit, backoff and jitter, and a circuit breaker. Idempotency makes them safe; it does not make them free. See the resilience guide.
9. Things to mention in an interview
- The problem: timeouts are ambiguous (lost request, in flight, lost response), so clients must retry, so servers must tolerate duplicates.
- "Exactly-once" is at-least-once plus idempotent processing; exactly-once delivery is not available over an unreliable network.
- First choice: natural idempotency (client-chosen ids, set not add, compare-and-set, upsert).
- Idempotency keys: per operation, client-generated, scoped per account, stored with a request fingerprint; replay the stored response;
409/422/400for in-flight, mismatch and missing. - The race in check-then-act, and claim first with a unique constraint, with the work and the result in one transaction.
- Side effects outside the database: recovery points, commit before the foreign call, a derived key for the downstream call, reconciliation if there is no key support.
- Consumers: the inbox table in the same transaction as the effect; the outbox on the producing side; why "record then effect" loses data and "effect then record" duplicates it.
- Retention: window versus cost, partitioned tables, and a natural-key unique constraint as a backstop after expiry.
Quick recap
- A timeout does not say what happened. Retries are necessary, so duplicates must be harmless: exactly-once effect = at-least-once + idempotent processing.
- In the experiment, without protection 200 payments produced 665 charges and 66 payments were charged yet reported as failed; a key checked before the work still produced 115 extra charges; a key claimed atomically produced none.
- Prefer naturally idempotent designs. Otherwise use a client-generated key per operation, stored with a fingerprint, scoped per account, replaying the stored response, with
409while in flight and422for a mismatch. - Claim first with a unique constraint; commit the work and the "done" marker together. A lease handles crashed owners.
- For foreign calls, commit a recovery point before them and give them a derived key. For queues, put the inbox record and the effect in one transaction: recording first lost 989 updates and recording second duplicated 1,098 in the test.
- Keys cost about 230 bytes each in my test (about 20 GB per day at 1,000 writes a second), so set a window, partition and expire them, and keep a natural-key constraint as a backstop.
Appendix: the experiment code
Python 3.13 and the standard library only (SQLite 3.45). Run python3 idem.py for all parts or python3 idem.py a b c d for chosen ones. The numbers in the text come from these runs; timings will vary by machine, but the counts for parts B and C and the sizes for part D are stable.
"""Experiments for the idempotency guide. Standard library only: a real HTTP server on localhost, SQLite, threads."""
import hashlib, json, os, random, sqlite3, threading, time, uuid
from concurrent.futures import ThreadPoolExecutor
from http.server import BaseHTTPRequestHandler, ThreadingHTTPServer
import urllib.request, urllib.error, socket
DB = "/var/tmp/g3/idem.db"
def conn():
c = sqlite3.connect(DB, timeout=30, isolation_level=None) # autocommit: each statement is its own transaction unless we BEGIN
c.execute("PRAGMA journal_mode=WAL"); c.execute("PRAGMA busy_timeout=30000")
return c
def reset():
for f in (DB, DB + "-wal", DB + "-shm"):
if os.path.exists(f): os.remove(f)
c = conn()
c.execute("CREATE TABLE charges (id INTEGER PRIMARY KEY, payment TEXT NOT NULL, amount INTEGER NOT NULL)")
c.execute("CREATE TABLE idem (key TEXT PRIMARY KEY, fingerprint TEXT NOT NULL, state TEXT NOT NULL, response TEXT)")
c.close()
MODE = "none"
RECEIVED = 0
LOCK = threading.Lock()
class H(BaseHTTPRequestHandler):
protocol_version = "HTTP/1.1"
def log_message(self, *a): pass
def reply(self, code, body, headers=()):
raw = json.dumps(body).encode()
self.send_response(code); self.send_header("Content-Type", "application/json")
self.send_header("Content-Length", str(len(raw)))
for k, v in headers: self.send_header(k, v)
self.end_headers()
try: self.wfile.write(raw)
except (BrokenPipeError, ConnectionResetError): pass # the client gave up; the work was done anyway
def do_POST(self):
global RECEIVED
with LOCK: RECEIVED += 1
body = self.rfile.read(int(self.headers["Content-Length"]))
req = json.loads(body); key = self.headers.get("Idempotency-Key")
fp = hashlib.sha256(body).hexdigest()
c = conn()
def do_work():
time.sleep(random.uniform(0.03, 0.12)) # talking to the card network
if MODE == "none" or key is None:
do_work()
cur = c.execute("INSERT INTO charges (payment, amount) VALUES (?, ?)", (req["payment"], req["amount"]))
return self.reply(201, {"charge": cur.lastrowid})
if MODE == "naive": # check, then act, then remember
row = c.execute("SELECT response FROM idem WHERE key=?", (key,)).fetchone()
if row: return self.reply(200, json.loads(row[0]), [("Idempotent-Replayed", "true")])
do_work()
cur = c.execute("INSERT INTO charges (payment, amount) VALUES (?, ?)", (req["payment"], req["amount"]))
resp = {"charge": cur.lastrowid}
c.execute("INSERT OR REPLACE INTO idem VALUES (?,?,?,?)", (key, fp, "done", json.dumps(resp)))
return self.reply(201, resp)
# MODE == "atomic": claim the key first, with a unique constraint deciding who wins
try:
c.execute("INSERT INTO idem (key, fingerprint, state) VALUES (?,?,'started')", (key, fp))
except sqlite3.IntegrityError:
f2, state, resp = c.execute("SELECT fingerprint, state, response FROM idem WHERE key=?", (key,)).fetchone()
if f2 != fp: return self.reply(422, {"error": "this key was used with a different request"})
if state == "started": return self.reply(409, {"error": "still being processed"}, [("Retry-After", "1")])
return self.reply(200, json.loads(resp), [("Idempotent-Replayed", "true")])
do_work()
c.execute("BEGIN IMMEDIATE") # the charge and the key's result commit together
cur = c.execute("INSERT INTO charges (payment, amount) VALUES (?, ?)", (req["payment"], req["amount"]))
resp = {"charge": cur.lastrowid}
c.execute("UPDATE idem SET state='done', response=? WHERE key=?", (json.dumps(resp), key))
c.execute("COMMIT")
return self.reply(201, resp)
def post(port, payment, key, timeout, body_extra=None):
data = json.dumps({"payment": payment, "amount": 100, **(body_extra or {})}).encode()
req = urllib.request.Request(f"http://127.0.0.1:{port}/charge", data=data, method="POST",
headers={"Content-Type": "application/json", **({"Idempotency-Key": key} if key else {})})
try:
with urllib.request.urlopen(req, timeout=timeout) as r: return r.status, json.loads(r.read())
except urllib.error.HTTPError as e: return e.code, json.loads(e.read())
except (socket.timeout, TimeoutError, urllib.error.URLError, ConnectionError): return None, None
def client(port, payment, use_key, timeout=0.05, attempts=5):
key = str(uuid.uuid4()) if use_key else None # ONE key per payment, reused on every retry
sent = 0
for i in range(attempts):
sent += 1
st, _ = post(port, payment, key, timeout)
if st in (200, 201): return sent, True
time.sleep(0.02 * (i + 1)) # timeout or 409: wait a little and retry
return sent, False
def run_mode(mode, n=200):
global MODE, RECEIVED
MODE = mode; RECEIVED = 0; reset(); random.seed(7)
srv = ThreadingHTTPServer(("127.0.0.1", 0), H); srv.daemon_threads = True
threading.Thread(target=srv.serve_forever, daemon=True).start()
port = srv.server_address[1]
t0 = time.time()
with ThreadPoolExecutor(20) as ex:
res = list(ex.map(lambda i: client(port, f"order-{i}", mode != "none"), range(n)))
time.sleep(0.3) # let abandoned requests finish on the server
srv.shutdown()
c = conn()
charges = c.execute("SELECT COUNT(*) FROM charges").fetchone()[0]
paid = c.execute("SELECT COUNT(DISTINCT payment) FROM charges").fetchone()[0]
worst = c.execute("SELECT MAX(n) FROM (SELECT COUNT(*) n FROM charges GROUP BY payment)").fetchone()[0]
print(f" {mode:7s} {n} payments, {sum(s for s, _ in res)} requests sent ({RECEIVED} reached the handler), "
f"{sum(1 for _, ok in res if ok)} acknowledged, {charges} charges for {paid} payments "
f"-> {charges - paid} extra charges (worst payment charged {worst}x) [{time.time()-t0:.1f}s]")
def part_a():
print("A. a real HTTP server, a client with a 50 ms timeout, 5 attempts, 200 payments, 20 at a time")
for m in ("none", "naive", "atomic"): run_mode(m)
def part_a2():
print("A2. same key, different body, and the key being retried after completion")
global MODE; MODE = "atomic"; reset()
srv = ThreadingHTTPServer(("127.0.0.1", 0), H); srv.daemon_threads = True
threading.Thread(target=srv.serve_forever, daemon=True).start(); port = srv.server_address[1]
print(" first call ", post(port, "order-1", "k1", 2))
print(" same again ", post(port, "order-1", "k1", 2))
print(" other body ", post(port, "order-1", "k1", 2, {"amount_note": "x"}))
srv.shutdown()
def part_b(keys=400, threads=8):
print(f"B. {threads} threads present the same key at the same moment, {keys} keys")
for variant in ("select-then-insert, no constraint", "unique constraint, INSERT OR IGNORE"):
for f in (DB, DB + "-wal", DB + "-shm"):
if os.path.exists(f): os.remove(f)
c = conn()
c.execute("CREATE TABLE claims (key TEXT" + (" PRIMARY KEY" if "unique" in variant else "") + ", who INTEGER)"); c.close()
for k in range(keys):
bar = threading.Barrier(threads)
def worker(w):
cc = conn(); bar.wait()
if "unique" in variant:
cur = cc.execute("INSERT OR IGNORE INTO claims VALUES (?,?)", (f"k{k}", w))
won = cur.rowcount == 1
else:
if cc.execute("SELECT 1 FROM claims WHERE key=?", (f"k{k}",)).fetchone() is None:
cc.execute("INSERT INTO claims VALUES (?,?)", (f"k{k}", w))
cc.close()
ts = [threading.Thread(target=worker, args=(w,)) for w in range(threads)]
[t.start() for t in ts]; [t.join() for t in ts]
c = conn()
rows = c.execute("SELECT COUNT(*) FROM claims").fetchone()[0]
dup = c.execute("SELECT COUNT(*) FROM (SELECT key FROM claims GROUP BY key HAVING COUNT(*)>1)").fetchone()[0]
print(f" {variant:36s}: {rows} rows for {keys} keys; {dup} keys claimed more than once")
def part_c(n=10_000, crash=0.10, seed=3):
print(f"C. at-least-once delivery of {n} 'credit 1' messages; the consumer crashes {crash:.0%} of the time at the worst moment")
def run(strategy):
random.seed(seed)
for f in (DB, DB + "-wal", DB + "-shm"):
if os.path.exists(f): os.remove(f)
c = conn()
c.execute("CREATE TABLE acct (id INTEGER PRIMARY KEY, balance INTEGER)"); c.execute("INSERT INTO acct VALUES (1, 0)")
c.execute("CREATE TABLE seen (msg INTEGER PRIMARY KEY)"); c.execute("CREATE TABLE st (msg INTEGER PRIMARY KEY, paid INTEGER)")
deliveries = 0
for m in range(n):
while True: # the broker redelivers until the consumer acks
deliveries += 1
boom = random.random() < crash
if strategy == "effect, then record": # two separate commits; crash between them
if c.execute("SELECT 1 FROM seen WHERE msg=?", (m,)).fetchone(): break
c.execute("UPDATE acct SET balance=balance+1 WHERE id=1")
if boom: continue
c.execute("INSERT INTO seen VALUES (?)", (m,)); break
if strategy == "record, then effect": # crash between them loses the effect for good
if c.execute("SELECT 1 FROM seen WHERE msg=?", (m,)).fetchone(): break
c.execute("INSERT INTO seen VALUES (?)", (m,))
if boom: continue
c.execute("UPDATE acct SET balance=balance+1 WHERE id=1"); break
if strategy == "same transaction":
c.execute("BEGIN IMMEDIATE")
if c.execute("SELECT 1 FROM seen WHERE msg=?", (m,)).fetchone(): c.execute("COMMIT"); break
c.execute("UPDATE acct SET balance=balance+1 WHERE id=1"); c.execute("INSERT INTO seen VALUES (?)", (m,))
if boom: c.execute("ROLLBACK"); continue # crash before commit: nothing happened
c.execute("COMMIT"); break
if strategy == "no dedupe at all":
c.execute("UPDATE acct SET balance=balance+1 WHERE id=1")
if boom: continue
break
if strategy == "set a state (naturally idempotent)":
c.execute("INSERT OR REPLACE INTO st VALUES (?, 1)", (m,))
if boom: continue
break
bal = c.execute("SELECT balance FROM acct").fetchone()[0]
if strategy.startswith("set a state"): bal = c.execute("SELECT COUNT(*) FROM st WHERE paid=1").fetchone()[0]
print(f" {strategy:38s}: expected {n}, got {bal} ({bal - n:+d}), {deliveries} deliveries")
for s in ("no dedupe at all", "effect, then record", "record, then effect", "same transaction", "set a state (naturally idempotent)"): run(s)
def part_d(rows=1_000_000):
print(f"D. what a dedupe table costs: {rows:,} keys (36-character UUID) with a 120-byte stored response")
for f in (DB, DB + "-wal", DB + "-shm"):
if os.path.exists(f): os.remove(f)
c = conn(); c.execute("CREATE TABLE idem (key TEXT PRIMARY KEY, created INTEGER, response TEXT)")
resp = "x" * 120
c.execute("BEGIN")
t = time.time()
c.executemany("INSERT INTO idem VALUES (?,?,?)", ((str(uuid.UUID(int=random.getrandbits(128), version=4)), i, resp) for i in range(rows)))
c.execute("COMMIT"); c.execute("PRAGMA wal_checkpoint(TRUNCATE)")
size = os.path.getsize(DB)
print(f" {size/1e6:.0f} MB on disk = {size/rows:.0f} bytes per key (table + primary-key index), loaded in {time.time()-t:.1f}s")
for rps in (100, 1_000, 10_000):
per_day = rps * 86_400
print(f" at {rps:>6,} writes/s kept for 24 h: {per_day:>13,} keys ~ {per_day * size / rows / 1e9:6.1f} GB")
# deleting an expired day: a range delete by created
c.execute("CREATE INDEX idem_created ON idem (created)")
t = time.time(); c.execute("DELETE FROM idem WHERE created < ?", (rows // 2,)); print(f" deleting half of them by created: {time.time()-t:.2f}s")
if __name__ == "__main__":
import sys
parts = sys.argv[1:] or ["a", "a2", "b", "c", "d"]
for p in parts: globals()["part_" + p]()
Sources
- IETF, The Idempotency-Key HTTP Header Field (Internet-Draft, httpapi working group): status codes 400, 409 and 422, key uniqueness, expiry and fingerprints.
- Stripe, Idempotent requests: key length, 24-hour pruning, parameter comparison, and what is saved.
- Amazon Builders' Library, Making retries safe with idempotent APIs (the client request identifier, atomic recording, semantically equivalent responses).
- Brandur Leach, Implementing Stripe-like Idempotency Keys in Postgres (recovery points, atomic phases, foreign state mutations).
- Amazon SQS Developer Guide, Exactly-once processing in Amazon SQS (the 5-minute deduplication interval).
- Confluent, Kafka message delivery guarantees (idempotent producer, transactions,
read_committed, offsets stored with data). - Chris Richardson, Transactional outbox and Idempotent consumer.
- IETF, RFC 9110: HTTP Semantics, section 9.2 (safe and idempotent methods).
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly), chapter 11, "Stream Processing", on exactly-once and idempotence in stream processing.
Practise this topic: System Design System Design › Distributed systems