What you'll learn: By the end of this lesson you will be able to define idempotent, commutative and associative operations precisely, say which of them a retry and a reordered message each need, classify everyday operations (increment, set, max, add to a set, remove from a set), build state that merges safely using per-node entries and operation ids, design a replay-safe request handler with an idempotency key, and run a Java lab that checks the three laws on thousands of generated cases.
A lift call button is idempotent: pressing it five times is the same as pressing it once. A kettle with "add one scoop of coffee" is not: five presses, five scoops. Sugar then milk or milk then sugar gives the same cup, so those steps commute; socks then shoes does not.
Networks retry, so messages arrive twice, and they reorder, so messages arrive out of turn. An operation that tolerates both lets a system stay simple under failure. This lesson gives the vocabulary and the designs. It builds on consistency models and the quorum register, and leans on message queues for the delivery side.
Verified against RFC 9110, the Stripe API reference, version 08 of the IETF idempotency-key draft, Almeida's CRDT survey and the Kafka 4.2 producer configuration page, read on 2026-11-08. Lab run on Java 25.0.3.
The core idea
| Property | Meaning | What it protects against |
|---|---|---|
| Idempotent | Applying it twice has the same effect as once | Duplicate delivery, retries |
| Commutative | a then b equals b then a |
Reordering |
| Associative | Grouping does not matter: (a, b), c equals a, (b, c) |
Merging partial results in any shape |
A merge function that has all three properties makes replicas converge no matter how states are delivered: late, twice, or out of order. Almeida's survey of conflict-free replicated data types (CRDTs) states the condition for state-based designs: the states form a join-semilattice, whose join (least upper bound) is idempotent, commutative and associative, and such designs work over networks with message loss, duplication and reordering. The same survey warns that "CRDTs are types with commutative operations" is a misconception, and that a counter's increment, being non-idempotent, cannot be reused as a state-based type unchanged.
Three illustrations run through the lesson: a minimal example (a deposit delivered twice, in the lab), a realistic example (ShopStream's payment retry and cart merge) and a failure example (last-writer-wins on a timestamp tie).
Idempotence: by nature and by bookkeeping
Some operations are idempotent by their nature. "Set the price to 3.49", "delete order 7" and "add milk to this set" change nothing the second time. RFC 9110 section 9.2.2 defines an idempotent method as one where the intended effect on the server of several identical requests is the same as for one, and lists PUT, DELETE and the safe methods (GET, HEAD, OPTIONS, TRACE) as idempotent. It says a client should not automatically retry a non-idempotent request unless it knows the request is idempotent or the original was never applied, and a proxy must not.
POST /payments is not idempotent by nature, so it needs bookkeeping: an idempotency key. The client generates a unique key per intended operation and sends it on every attempt. Stripe's API reference documents the contract for its API v1:
- The key goes in an
Idempotency-Keyheader, up to 255 characters; Stripe suggests V4 UUIDs. - The first request's status code and body are saved after the endpoint starts executing, and a retry with the same key returns the saved response, including
500errors. - If a retry's parameters differ from the original, the request is rejected.
- A request that fails validation, or conflicts with one still running, saves nothing and can be retried.
- Keys can be removed after at least 24 hours, and a reused key after that starts a new request.
The IETF draft for an Idempotency-Key header field (version 08, an active Internet-Draft, not an RFC) proposes the same shape: a string value, a 422 when the key is reused with a different payload, a 409 when the first request is still processing and a 400 when a required key is missing, all as SHOULD.
Figure 1. An idempotency key across a retry. How to read this: the stored fingerprint of the request is what lets the server tell a true retry from a different request that reuses the key. The retry costs a lookup, not a second charge.
Commutativity, and why the two are different
Idempotence and commutativity are independent. Classify the operations you meet:
| Operation | Idempotent | Commutative | Note |
|---|---|---|---|
balance += 5 |
No | Yes | A duplicate is counted twice |
price = 3.49 |
Yes | No | Two different sets: the last one applied wins |
max(a, b) |
Yes | Yes | A merge with all three laws |
set.add(x) |
Yes | Yes | Union |
set.remove(x) and set.add(x) |
Yes each | No | Order decides the result |
| Last-writer-wins by (timestamp, node id) | Yes | Yes | Valid merge, but discards one concurrent write |
Two consequences follow. A commutative but non-idempotent operation (+= 5) needs deduplication: Almeida notes that because operations are not in general idempotent, operation-based designs depend on exactly-once delivery from the messaging layer. And an idempotent but non-commutative operation (= value) needs an order, which is what timestamps, versions and a single writer provide.
Figure 2. From a risky operation to a safe design. How to read this: take the first branch that matches. Each box is one of the designs in the lab.
Four designs
- Choose a merge that has the laws. Take the maximum, or the union of two sets.
- One slot per node (single writer). A grow-only counter keeps one count per node; each node only ever changes its own entry, and merge takes the larger entry per node; the value is the sum. Merging a state with itself changes nothing, which is exactly what a summed duplicate would break. A counter that can go down is two of these, one for increments and one for decrements.
- Operation ids. Store each delta under its unique id. Applying the same id again finds it present and does nothing.
- Tags for add and remove. In an observed-remove set every add gets a unique tag, and a remove records only the tags it has seen. An add concurrent with a remove has a tag the remove never saw, so the add wins. Almeida calls this the add-wins set, and points out that its outcome can match no sequential execution: two replicas that each add one element and remove the other end with both present.
Build it
Goal. Check the three laws on generated cases, see the naive designs fail and watch a replay-safe handler run each key once.
Setup. From examples/backend:
./gradlew :labs:idempotent-commutative-ops:check --console=plain
./gradlew -q :labs:idempotent-commutative-ops:runThe first command runs 22 tests. The second prints the six experiments below. The code is in examples/backend/labs/idempotent-commutative-ops/, with a seeded generator (SplitMix64) written for the lab and no test library beyond JUnit.
How it works. Mergeable<T> has one method, merge. The tests build 2,000 random states per type from the seeded generator and check that a.merge(a) equals a, that a.merge(b) equals b.merge(a) and that merging is associative. A second test feeds three replicas the same states duplicated and shuffled, and checks that all three end identical. The failing designs are in the lab too: NaiveAccount, and NaiveLwwRegister, which orders by timestamp alone. The handler's core is one line:
Stored stored = store.computeIfAbsent(key, k -> {
ran[0] = true;
return new Stored(fingerprint, action.get());
});computeIfAbsent runs the action at most once per key even with concurrent callers; a test with 16 threads and one key checks that.
Expected output, captured from a real run (Java 25.0.3, 2026-11-08):
Idempotent and commutative operations: six small experiments (generator seed 20261108)
1. The same message delivered twice
plain balance += 5, delivered twice -> balance 10 (should be 5)
delta stored under its operation id -> balance 5
2. A grow-only counter: order and duplicates do not matter
replica 1 receives a, b, c -> {a=3, b=2, c=4} value 9
replica 2 receives c, a, c (again), b -> {a=3, b=2, c=4} value 9
same state on both replicas -> true
if merge added instead of taking the max -> value 13 after c arrives twice (should be 9)
3. An observed-remove set: a concurrent add wins
replica B removes milk -> []
replica C adds milk again (tag c:1) -> [milk]
B merged with C -> [milk]
C merged with B -> [milk]
4. Last-writer-wins: a tie needs a tie-break
timestamp only, blue.merge(green) -> blue
timestamp only, green.merge(blue) -> green
(timestamp, node id), either order -> green and green
5. A replay-safe handler
first request, key pay-001 -> receipt-1 replayed=false
retry, same key, same request -> receipt-1 replayed=true
same key, different amount -> rejected: idempotency key pay-001 was already used with a different request
charges actually made -> 1
6. The three laws on 2000 generated cases per type (violations found)
type idempotent commutative associative
GCounter 0 0 0
PNCounter 0 0 0
GSet 0 0 0
MaxRegister 0 0 0
LwwRegister (ts, node id) 0 0 0
OrSet 0 0 0
OpLedger 0 0 0
NaiveLwwRegister (ts only) 0 473 -| Experiment | What it shows |
|---|---|
| 1 | A duplicate doubles a plain increment; a delta stored under its id counts once |
| 2 | Any order and any duplicates give one state; summing instead of taking the max breaks it |
| 3 | The remove saw only tag a:1; the concurrent add c:1 survives, in both merge orders |
| 4 | On a timestamp tie the two replicas disagree; adding the node id as a tie-break fixes it |
| 5 | One charge, a replayed retry, and a rejected reuse of the key |
| 6 | Zero violations for the safe designs; 473 of 2,000 generated pairs break commutativity for the naive register |
Break it. In GCounter.merge replace Math::max with Long::sum: the counter tests fail, because a state merged with itself doubles. Drop the node tie-break in LwwRegister: its law test fails. Remove removedTags from OrSet.merge: its law test fails. These three were run and failed as stated.
Stretch. Give the handler an in-progress state and return a conflict to a retry that arrives during the first request; add expiry to the key store and test what a retry after expiry does.
What the model leaves out. Durable storage, real networks, a request still running when its retry arrives (the lab makes the second caller wait), expiry of stored keys and cleanup of OR-set tags. Passing these checks on generated cases is strong evidence for the laws on those generators, not a proof for every state.
Replay-safe handlers and delivery
Message brokers commonly deliver at least once, so a consumer sees duplicates. Kafka's producer option enable.idempotence, true by default in the 4.2 documentation, makes the producer ensure that exactly one copy of each message is written in the stream when retries happen. That removes duplicates a producer's retries would create in the log; it does not make a consumer's side effects (a charge, an email) safe, so the consumer needs its own key. The rule: at-least-once delivery plus an idempotent handler gives effectively-once processing of the effect.
Store the key with the result in the same transaction as the side effect, or a crash between them leaves one without the other. Decide how long to keep keys: longer than the longest retry any client or queue can make.
Figure 4. The states of one key. How to read this: the lab implements the two main states and makes a concurrent retry wait instead of returning a conflict. A real service decides what the in-progress retry gets; the IETF draft suggests a 409.
The other side of this topic
In the browser the same laws appear as a disabled submit button, a request id sent with each click and optimistic updates that must merge with the server's answer. The Frontend System Design track covers that (no link: not published yet).
In practice: a payment retry and a cart that merges
This is the realistic example, an educational scenario on ShopStream. Nothing in it describes a real company, and every figure is illustrative.
This is a realistic scenario, not a case history.
The situation
A shopper's checkout call times out. The app retries, and the payment service charges twice. Separately, a redelivered "reserve stock" event decrements stock twice, and the cart, edited on a phone and a laptop, loses items when one device's copy overwrites the other.
Starting architecture
Figure 3. Two places duplicates arrive: client retries and broker redelivery. How to read this: the payment path is protected by a key lookup. The broker path delivers at least once, so the stock service must be safe to repeat.
Options considered
| Option | Behaviour | Cost | Risk |
|---|---|---|---|
| A. Forbid retries | No duplicates | Users see failures | Lost sales, still duplicates from the broker |
| B. Idempotency key plus a key store | One charge per key | A table and a retention rule | Keys expiring before a late retry |
| C. Stock as reservation records under unique ids, cart as an add-wins set | Safe under duplicates and reordering | Metadata that grows | Needs cleanup |
The decision
B for payments and C for stock and carts. The client creates one key per checkout attempt and reuses it for retries. The payment service stores key, request fingerprint and result in the same transaction as the charge record, and returns the stored result on a repeat. Stock records each reservation under its event id, so a redelivered event finds its id and does nothing. The cart is an observed-remove set, so two devices' edits merge by union and an add concurrent with a remove survives (the cost: a remove that races an add on the other device loses, because the add wins; the CAP lesson shows the same trade-off with a plain union).
Rollout and verification
In staging, inject duplicate and shuffled deliveries and assert the invariants: one charge per key, stock equals the sum of distinct reservations, carts converge. Metrics: replays per hour, key conflicts (same key, different payload) and key-store size.
The 2 a.m. failure
A queued retry fires after the key store has pruned its entry: the key is new, so the payment runs again and the shopper is charged twice. Detection: a reconciliation query finding two charges with one order id. Mitigation: refund the duplicate; the lasting fix is to keep keys longer than the longest retry any component can make and to bound retries in the queue.
Architect's notes
- Ask for each write: what happens if it arrives twice, and what if it arrives after the next one?
- Prefer a merge with the three laws to coordination where the data allows it.
- Fingerprint the request. A key without a fingerprint lets a bug reuse a key silently.
- Key retention must outlast the longest retry.
- Idempotence is about the effect, not the response: a retry may return a stored result and still be correct.
Common mistakes
- Treating
POSTretries as safe. - Deduplicating in memory only, so a restart forgets every key.
- Storing the key and the side effect in separate transactions.
- Ordering by timestamp alone and getting different winners on ties.
- Summing states on merge instead of taking the per-node maximum.
- Assuming the broker's idempotence covers the consumer's side effects.
Key takeaways
- Idempotent means a repeat changes nothing; commutative means order does not matter; both are needed when messages repeat and reorder.
- A merge that is idempotent, commutative and associative makes replicas converge.
- Increments are commutative but not idempotent; overwrites are idempotent but not commutative.
- Idempotency keys add idempotence by bookkeeping: store the result and a fingerprint, replay on a repeat, reject a reused key with a different request.
- Per-node entries, operation ids and add tags are the standard ways to make state mergeable.
- At-least-once delivery plus an idempotent handler gives effectively-once effects.
- Last-writer-wins needs a total order, and it discards one concurrent write.
Practice exercises
Exercise 1 (30 min). Classify five operations from a food-delivery app (add tip, set address, cancel order, add item to cart, mark delivered) as idempotent and commutative or not, and say how you would repair each failure.
Exercise 2 (45 min). In the lab, add a two-phase set to the generators and find, with the tests, a case where an element cannot be added again after removal.
Exercise 3 (1 hour). Add an "in progress" state to the handler and decide what a retry gets during it. Write the test.
Exercise 4 (1 hour). Choose a key retention time for a queue that retries for 3 days with backoff, and justify it.
Exercise 5 (2 hours). Replace LwwRegister with a register that keeps both concurrent values and test the three laws on it.
Related reading
- Consistency Models and Quorum Reads and Writes.
- CAP Theorem and PACELC: the cart merge.
- Message Queues and Distributed Transactions.
- ShopStream: payments and ledger.
- IDs, Clocks and Ordering.
Official documentation
- IETF, RFC 9110: HTTP Semantics, section 9.2.2, idempotent methods and retries.
- Stripe, Idempotent requests: key header, saved responses, parameter comparison.
- IETF httpapi working group, The Idempotency-Key HTTP Header Field (Internet-Draft, version 08).
- Almeida, Approaches to Conflict-free Replicated Data Types (2024).
- Apache Kafka, Producer configs:
enable.idempotence.