Idempotency Keys
Track: Data consistency. 6 stages. Languages: Go, Python, JavaScript, Rust.
Say you send a payment request, but the reply never arrives. Did it work or not? If you just send the request again, you might charge the same card twice. An idempotency key fixes this: you tag the request with a key, and the server promises that a repeat request with the same key gets back the exact same result, without doing the work again, even if two copies of the request arrive at the exact same moment.
Build Execute(key, now, op). The first time it sees a key, it runs op (the real work) and remembers the result. A later call with the same key returns that same result, without running op again. Example: Execute("pay-1", 0, chargeCard) runs chargeCard and returns 42. Call Execute("pay-1", 5, chargeCard) again, and it returns 42 right away, without calling chargeCard a second time.
A saved result does not last forever. Build New(ttl, capacity): ttl is how long, in time units, a result stays usable before it goes stale, and capacity is the most results you keep at once. Once a result goes stale, or you remove it yourself with Purge(now), the next call with that key runs the real work again and remembers a new result. Example, with ttl = 50: Execute("a", 0, work) runs work and returns 1. Execute("a", 10, work) is still inside the 50-unit limit, so it returns 1 again without running work. Execute("a", 60, work) is 60 units after the first call, past the 50-unit limit, so it runs work again and returns a new result, say 2.
Many copies of the same request can also arrive at the exact same time, from different callers. Only one of them should actually run the work. Every other one should wait for that first call and then share its result. Example: 10 callers all call Execute("pay-2", 0, chargeCard) at once, before any of them has finished. chargeCard must still run only once. The other 9 callers get back the same result the one real call produced, not 9 separate charges.
Time here is never read from a real clock. Every call gives you now itself, a plain number that only goes up. Your code just compares the numbers you are given.
Implement New(ttl, capacity), Execute(key, now, op) -> (result, wasReplay) (wasReplay is true when you returned a saved result instead of running op), and Purge(now) using your language's own names. Standard library only. Your code will be called from many callers at once, so it must be safe for that. For help with the ideas, read the notes. New to code that many callers run at the same time? Read Many callers at once first.
Where it is used
- Stripe's payment API takes an
Idempotency-Keyheader. If a network error hides the answer, the client sends the same request with the same key, and Stripe returns the saved result instead of charging the card twice. Stripe may forget a key after 24 hours, like yourttl. - Amazon EC2 takes a client token when you start servers, so a retried request does not start a second set of servers.
- A webhook receiver often gets the same event twice. It can use the event's id as the key, so it handles each event only once.
Stages
ik1: hello, the first call runs the work (very easy)
A fresh key's first call runs op once and returns its result. wasReplay must be false. Example: Execute("a", 0, work) -> the result work returns, wasReplay = false.
The tester will verify: the first Execute call for a key runs op exactly once and reports wasReplay=false.
ik2: a repeat call reuses the saved result (easy)
Call Execute three times for the same key, all before it goes stale. The 2nd and 3rd calls must return the first result without running op again. Example, ttl = 50: Execute("a", 0, work) -> 1, wasReplay=false. Execute("a", 1, work) and Execute("a", 2, work) both -> 1, wasReplay=true.
The tester will verify: across the 3 calls, op runs exactly once, and the later 2 calls report wasReplay=true with the first result.
ik3: many callers at once, only one does the work (medium)
16 callers call Execute for the same brand new key at the exact same time, each one's op taking a couple of milliseconds. Only one of them may actually run op. The other 15 must wait and share its result.
The tester will verify: across all 16 calls, op's run count is exactly 1, and every caller gets the same result.
ik4: an old result goes stale and runs again (medium)
Every stage builds with ttl = 50. A call for a key still inside its 50-unit limit must reuse the saved result. Once that limit passes, or Purge removes it, the same key must run the work again. Example: Execute("a", 0, work) runs (result 1). Execute("a", 10, work) replays it. Purge(60) removes it. Execute("a", 60, work) runs again with a new result. Execute("a", 70, work) replays that new result.
The tester will verify: the now=60 call runs op again and returns a new result, and the now=70 call replays it.
ik5: stress: capacity plus a long run of calls (hard)
Every stage builds with capacity = 4. Once the ledger holds 4 results and a 5th fresh key arrives, the oldest result is removed, and that key may run again on its next call. On top of that, a long run of mixed Execute and Purge calls across 8 keys must match our solution exactly, call by call. In this run, every call has a later now than the call before it, so the oldest result is always the one that arrived first. Example: fill 4 distinct keys, then call Execute again on the first one. It runs again instead of replaying, because it was pushed out to make room for the others.
The tester will verify: every result, every wasReplay flag, and every run count across the whole run matches our solution.
ik6: Make repeat calls fast (L2, hard)
Make Execute fast for the common case: a call that lands on a saved, fresh result. Keep every answer correct. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.
The tester will verify: your code takes at most 1.5 times as long as our solution in the same language and returns correct answers.
Rules
- Standard library only. No third-party packages.
- Use the
nowvalue you are given for timing. Never read the real clock. - Many callers may call your code at once. Keep it safe for that, and make sure only one caller per key ever runs the real work.