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 happenedThe caller seesIs a retry safe without protection?
The request never reached the serverno answeryes: nothing happened
The server is still working on itno answer (yet)no: two copies now run
The server finished, the response was lostno answerno: 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 behaviourRequests sentPayments the client saw succeedCharges for 200 paymentsExtra charges
No idempotency670134665465 (one payment was charged 5 times)
A key, checked before the work ("naive")465200315115
A key, claimed atomically before the work5052002000

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:

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:

The cheapest fix: make the operation naturally idempotent

Before building any machinery, see whether the design can avoid needing it:

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

  1. 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.
  2. 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.
  3. 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).
  4. 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.
  5. 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:

SituationResponse
Key missing on an endpoint that requires it400 Bad Request
Key seen before, finishedthe stored response (same status and body), often with a header marking it a replay
Key seen before, the first request is still running409 Conflict (the client retries shortly)
Key seen before with a different payload422 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:

StrategyRows for 400 keysKeys claimed more than once
SELECT first, then INSERT, no constraint3,192400 (every key)
Unique constraint, INSERT OR IGNORE, the winner is whoever inserted4000

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:

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:

The pattern that holds up, described in detail in Brandur Leach's article on implementing Stripe-style idempotency keys in Postgres, has three parts:

  1. 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.
  2. 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.
  3. 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 strategyExpected balanceResultVerdict
No deduplication10,00011,098 (+1,098)duplicates
Apply the effect, then record the message id (two commits)10,00011,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,0009,011 (−989)lost updates: the id is recorded but the effect never happened, and redelivery is skipped
Effect and message id in one transaction10,00010,000correct
Naturally idempotent (set a state per message)10,00010,000correct

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

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.

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:

MeasureResult
Size on disk229 MB, about 229 bytes per key (table and index)
Load time10.7 s for one million rows
Deleting half of them by creation time3.8 s

Extrapolating that size for a 24-hour window:

Writes per secondKeys per dayStorage for 24 h
1008.6 millionabout 2 GB
1,00086.4 millionabout 20 GB
10,000864 millionabout 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

9. Things to mention in an interview

Quick recap

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

Practise this topic: System Design System Design › Distributed systems

More guides