Idempotency keys

Lesson 3 taught you to retry gently. But a retry after a lost response is exactly what charged 22 customers twice in Lesson 1. This lesson makes the retry itself safe.

By the end you'll be able to make a non-idempotent operation, a charge, safe to retry with an idempotency key, including the hard cases: two copies arriving at the same moment, and your server crashing halfway through. You'll build it in labs/payflow/src/idempotency.ts.

Some operations are safe to repeat, some aren't

Kleppmann defines it in one line: a function f is idempotent if f(x) = f(f(x)). Incrementing a counter isn't. Adding an element to a set is^[1]. His notes show a Twitter profile following a negative number of people, probably from a retried "unfollow", then add: "consider the act of deducting £1,000 from your bank account balance. The database operation is essentially the same"^[1].

HTTP itself says a client shouldn't automatically retry a non-idempotent request like POST "unless it has some means to know" that it's safe^[2]. POST /checkout is exactly the request we need to retry, so we give it that means.

The idea: name the operation, not the attempt

The client generates a unique ID for the checkout (a random ID such as crypto.randomUUID(), as Stripe suggests^[3]) and sends it with the request, and with every retry of that request. AWS calls it a "unique caller-provided client request identifier". The server remembers which IDs it has already handled, and for a repeat it must "deliver a semantically equivalent response", meaning the same answer as the first time, not an error like "already exists"^[4]. Why not an error? Because the caller would then have to work out whether its own request created the thing. That's the unknown outcome from Lesson 1 again.

Mental model: a cloakroom ticket. You hand over your coat and get ticket #41. If you come back three times with #41, you get the same coat back three times; the attendant doesn't hang up three coats. The ticket names the coat, not your visit. The model breaks in two places, and those two places are this lesson's hard part. First, two people can walk up with ticket #41 at the same instant. Second, the attendant can faint halfway through hanging the coat up. The ticket alone doesn't tell you whether the coat made it onto a hook.

Watch one key absorb a lost response, a double click and a crash. Press ▶, use the chapters, or turn on 🔇 narration.

The server side: a table and five cases

The memory lives in your database, next to your orders. (In the diagrams, k1 is short for a real key such as client-key-o1.) lib/db.ts already creates the table:

CREATE TABLE idempotency_keys (
  key          TEXT PRIMARY KEY,          1
  fingerprint  TEXT NOT NULL,             2
  status       TEXT NOT NULL,             3  -- 'in_flight' | 'done'
  response     TEXT,                      4
  locked_at    INTEGER NOT NULL           5
);

1. The primary key is the whole trick. The database guarantees that only one row per key can exist. So "insert the key" is an atomic claim: of two concurrent requests, exactly one insert succeeds.
2. What was asked. A string computed from the parameters (fingerprint() sorts the keys, so {a,b} equals {b,a}). Store it as is or hash it; the tests only compare fingerprints your own store wrote. AWS returns "a validation error indicating a parameter mismatch" in that case^[4].
3. Where the work is. in_flight while someone is working on it, done once the response is saved.
4. The first answer, as JSON, replayed to every retry.
5. When the claim was made, and your fencing token. A very old in_flight lock means the worker probably died^[5]. "Probably" matters: see fencing below.

Every request goes through one decision. This is the contract of IdempotencyStore.run(key, params, work):

Compare-and-set means an UPDATE … WHERE locked_at = <the old value>: it succeeds only if nobody changed the row since you read it, so of two retries that both see a stale lock, only one takes over.

The two error answers are the canonical meaning of these codes for the rest of the course:

That's why isRetryable in your Lesson 3 src/retry.ts treats ConflictError as retryable and MismatchError as not: the tests demanded it, and now you know the reason.

Why not "SELECT, then INSERT"?

The tempting version is: look the key up; if it isn't there, do the work and insert it. Together the steps have a gap, and a double click lands right in it:

AWS solves this by recording the token and the change it makes in one database operation: "An ACID server-side operation needs to be an 'all or nothing' or atomic process"^[4]. That works when the change lives in your own database. Ours doesn't: the charge happens at PayCo, and no transaction of ours can include it. So we follow Brandur Leach's design for this case^[5]: make the claim atomic, do the outside work, then save the answer. INSERT … ON CONFLICT(key) DO NOTHING, followed by checking .changes === 1, is the smallest atomic claim SQLite gives you.

An honest limit of this lab. node:sqlite is synchronous and the lab runs in one process, so nothing can run between your SELECT and your INSERT unless you await in between. A SELECT-then-INSERT claim, or a takeover without compare-and-set, therefore can't race here, and no test can catch it. In production, with several server processes sharing one database, both race exactly as the diagram shows. Write the atomic version anyway: it's the one that survives the move.

Keys must go all the way down

Now the faint attendant. Our shop claims k1, calls PayCo, PayCo charges, and then our process dies before saving the response. The row sits in_flight forever. After lockMs, a retry takes it over and runs the work again. That calls PayCo a second time.

The only thing that makes this safe is the step below us. The charge to PayCo is what Brandur Leach calls a foreign state mutation: "we've pushed data into a system beyond our own boundaries and we shouldn't lose track of it"^[5]. Our database can't roll it back. So the shop sends its own idempotency key to PayCo, derived from the order, such as charge:o1. lib/provider.ts honours it like Stripe does: the same key returns the original charge, not a new one.

Fencing: when "probably died" is wrong

A stale lock doesn't prove the worker died. It may just have been slow: a long garbage-collection pause, a slow PayCo call. Then the old worker wakes up after a retry took over, and two things can go wrong. It saves its response over the new owner's, or, if its work failed, it deletes the new owner's claim and lets a third request in. Martin Kleppmann's fix is a fencing token: "you need to include a fencing token with every write request to the storage service", and the storage rejects writes carrying an older token^[6].

In the lab, the token is the locked_at value you wrote, at the claim or at the takeover. Every later write checks it:

save:     UPDATE … SET status='done', response=?
          WHERE key=? AND status='in_flight' AND locked_at=<mine>
          0 rows changed → I lost the lock → throw ConflictError
release:  DELETE … WHERE key=? AND status='in_flight' AND locked_at=<mine>

Two tests in test:04 play the slow worker: one whose save comes too late, one whose work fails after a takeover. The fencing only helps if lockMs is longer than any honest run of the work, so set it above your whole deadline plus PayCo's timeout. Otherwise you take over live workers by design.

A design choice. If the work throws, our store deletes its claim so a retry can run the work again. That's only safe because the work is itself idempotent downstream (the charge:o1 key). Stripe chooses differently; the reference sheet compares the two.

What the lab shows

npm run l4 sends 100 checkouts from a phone to the shop over a network that loses 20% of responses. The phone makes up to 5 attempts. The shop's charge deliberately has no PayCo key here, so the only protection is the shop's own key handling:

  version       charges   double-charged orders   client gave up   calls
  no-key            132                      24                0     132
  key-per-try       132                      24                0     132
  same-key          100                      0                0     132

Look at the middle row. A fresh key on every attempt is exactly as bad as no key at all: each retry looks like a brand-new checkout. This is the most common idempotency bug in practice. Generate the key once, when the user starts the operation, and store it with the pending action so retries (even after an app restart) send it again.

Keys don't live forever: once a key is pruned, a reused key is a new request, so your retry window must be shorter than your retention window. Stripe keeps keys "for at least 24 hours" and says to "limit retries of an unresolved operation to the first 24 hours"; if the outcome is still unknown after that, "don't retry with either the old key or a new one", reconcile instead^[7]. AWS ties retention to "the lifetime of the resource, plus an interval"^[4].

Two client rules follow from the same Stripe page. On a 409, "wait and retry with that key and the same parameters. A new key can start a second operation." And to change the parameters after an unknown outcome (the user edits the cart after a timeout), "first establish that the original operation didn't succeed and isn't still executing", then use a new key^[7].

Your turn: src/idempotency.ts

Implement IdempotencyStore.run, then run npm run test:04. The 12 tests cover each case in the decision diagram, a restart, the end-to-end crash and the two fencing cases. If node:sqlite is new to you, this is all of it you need:

const st = db.prepare('UPDATE t SET a = ? WHERE k = ?');  // compile once, with ? placeholders
st.run(1, 'k1').changes        // run a write: how many rows it changed (0 or 1 here)
db.prepare('SELECT * FROM t WHERE k = ?').get('k1')   // first row, or undefined
  as { a: number } | undefined                        // rows come back untyped: cast them

Before you start, fill in the core below from memory. It's the claim and the first three checks; the take-over and the release on error are yours to write.

const claimed = this.db.prepare(`
  INSERT INTO idempotency_keys
    (key, fingerprint, status, locked_at)
  VALUES (?, ?, 'in_flight', ?)
  ON CONFLICT(key) DO `)
  .run(key, fp, now). === 1;

if (!claimed) {
  const row = /* SELECT … WHERE key = ? */;
  if (row.fingerprint !== fp)                       // HTTP 
    throw new MismatchError();
  if (row.status === '')
    return JSON.parse(row.response);
  if (now - row.locked_at < this.lockMs)            // HTTP 
    throw new ConflictError();
  // stale: take over with compare-and-set …
}

Practice: from memory

No scrolling up.

Predict the store

cd labs/payflow
npm run test:04            # all 12 green
npm run l4                 # uses YOUR IdempotencyStore

Read or watch next

Primary source: Making retries safe with idempotent APIs, Malcolm Featonby, Amazon Builders' Library. It's how AWS designs this for EC2: client request tokens, semantically equivalent responses, and parameter mismatches.

• Making retries safe with idempotent APIs📄 Article · ~15 min · Amazon Builders' Library (now redirects to builder.aws.com)Read for why a repeat should get the same answer and not "already exists", and for the atomic recording of the token with the change.
• Implementing Stripe-like Idempotency Keys in Postgres📄 Article · ~30 min · Brandur LeachThe production-grade version of this lesson: locked_at, 409s, and "recovery points" that let a retry resume a multi-step request where it stopped. Lesson 6 uses a simpler route to the same goal.
• Idempotent requests📄 Docs · ~3 min · Stripe API referenceA real contract in a few paragraphs: key format, what's saved, parameter comparison, 24-hour pruning.
• Distributed Systems lecture series▶ Playlist · Martin KleppmannThe theory under this lesson (Slide 90). No high-trust video on idempotency keys themselves was found.

💬 Stuck on the take-over case, or unsure what your endpoint's key scope should be? Ask me in the terminal. Paste your failing test output or your draft contract.