−This is the original diagram on PDF page 4, printed page 3, of Malcolm Featonby's Making retries safe with idempotent APIs. It illustrates an API contract that keeps the same identifier after losing a response. It concerns request deduplication, one application of the broader concept. © Amazon Web Services.
The article favors an explicit caller-provided identifier over assuming that matching request bodies mean matching intentions. A customer may legitimately order the same item and quantity twice. Caller scope, reuse of a key with different content, and record retention all affect what the API recognizes as the same operation. AWS article.
There are two design choices here. An operation can specify the desired state directly, or it can remain an additive operation whose repeated requests are controlled by records. The latter requires the effect and its record to be handled atomically. A local database transaction alone cannot cover an external payment service's effect. Whether to reuse a response is another part of the API contract.
Idempotence is a property of repeated effects; deduplication is a technique for recognizing an operation already seen. Within its retained records and other stated assumptions, deduplication can help provide idempotent behavior. Expired records and effects in other systems require further guarantees. An “exactly once” claim likewise needs to identify whether it concerns delivery, execution, or a business effect.
What stays the same in each context
Context | What repeats | What is compared
Algebra | Multiplication of the same element | The element itself
Function composition | Applying a function to its previous result | The function value
Stateful programs | Applying the same command again under the stated conditions | The chosen observable state
HTTP | Retransmitting the same request | The intended server effect
APIs with request keys | Processing the same operation identifier again | Contracted business effects and response behavior
As this algebraic property is used in communication and business processing, the scope of equality and the mechanism that provides it become part of the explanation. Specifying the repeated operation and the observed effect makes the guarantee clear. Preventing duplicate orders is one application; request keys and stored results are chosen mechanisms for providing it.
+This diagram is from Malcolm Featonby's Making retries safe with idempotent APIs. The caller has not received the first response, so it retries with the same identifier while the service checks processing state in StateStore.
A customer may intentionally order the same item and quantity twice, so hashing the request body alone would collapse two legitimate orders into one. Instead, the caller supplies an explicit request key—reusing it when retrying the same operation and generating a new key for a separate order. The server scopes each key to the authenticated caller, rejects payload mismatches under the same key, and defines the retention window for stored records. AWS article.
This Python 3 example makes sequential calls on one thread in one process. The server supplies an authenticated caller identifier as owner; key and item are already validated strings. One dictionary entry stores the order contents and number together, and records remain in the dictionary for the run.
requests = {}
def create_order(owner, key, item):
identity = (owner, key)
if identity in requests:
previous_item, order_id = requests[identity]
if previous_item != item:
raise ValueError("KEY_REUSED_WITH_DIFFERENT_REQUEST")
return order_id
order_id = len(requests) + 1
requests[identity] = (item, order_id)
return order_id
first = create_order("alice", "request-1", "book")
retry = create_order("alice", "request-1", "book")
another = create_order("alice", "request-2", "book")
print(first, retry, another) # 1 1 2
The same caller, key, and item return the existing order number; a new key creates a separate order for the same item. Calling create_order("alice", "request-1", "pen") with changed contents under the same key raises ValueError. The (owner, key) pair separates keys belonging to different callers.
Because this example uses an in-memory dictionary, both orders and retry records vanish when the process exits. Production servers must also handle concurrent requests and crash recovery, which requires atomic commitment.
Suppose the server checks for a key before processing, then saves the order and key separately. Two concurrent requests can both see “no record” and each create an order. The server could also stop just after saving the order. It must commit the identifying record and the order effect as one atomic operation. The record's states and the API contract then express whether an attempt is still running, whether it can run again after failure, and how to return a previous success result.
The request key identifies the same operation while its record is retained. After the server deletes the record, it may lack the information to distinguish an old key from a new request. If the caller changes the key, the retry may also look like a separate operation. Both the retention period and the caller's key-use rule bound the guarantee.
A local database transaction commits the order and processing record in that database together. Reprocessing an external payment follows the identifiers and contract provided by the payment service. Idempotence describes a repeated effect; deduplication identifies an operation already attempted. An “exactly once” claim must say whether it covers message delivery, code execution, or the business effect.
The law also applies when replicas merge state
Shapiro, Preguiça, Baquero, and Zawirski's 2011 paper Conflict-free Replicated Data Types distinguishes sending state for merging from sending operations for application. Its state-based model uses commutative, associative, and idempotent merging together with monotonic state updates. Idempotence here helps when a state is transmitted more than once. Paper §§2.1–2.4.
[Image]
(Original source)
These are Figures 1 and 2 on PDF page 3. On the left, a replica transmits its state and the receiver merges it. On the right, a replica transmits an operation and the receiver applies it. The set example below shows a merge operation suitable for the left-hand model.
def merge(left, right):
return left | right
local = {"a"}
remote = {"b"}
combined = merge(local, remote)
assert merge(combined, remote) == combined
assert merge(local, remote) == merge(remote, local)
print(sorted(combined)) # ['a', 'b']
This is Python 3 set union. Merging the same remote state again leaves the result unchanged. Commutativity covers a change in merge order, and associativity covers how several states are grouped. To explain convergence, we also need the conditions that updates grow the state by adding elements and that each replica eventually transmits its updates.
The same paper's operation-based model assumes causal ordering and exactly-once delivery. Apply an “increment by 1” operation message twice, for example, and the value increments twice. The delivery assumptions for operation messages differ from the duplicate-tolerant merge in the state-based model. Paper §§2.3–2.4.
What each context compares
Context | What repeats | Result compared
Algebra | Multiplication of the same element | The element itself
Function composition | Applying the same function to its previous result | The function value
A program that changes state | Reapplying the same command | The state chosen for observation
HTTP | Retransmitting the same request | Its intended effect on the server
An API with request keys | Reprocessing the same operation identifier | Contracted business effect and returned result
State-based replication | Merging the same state again | The merged state
Mathematicians compare an operation's result; clients and servers compare effects after a retry; designers of replicated systems compare states after repeated merges. Naming that scope shows how storing request keys, specifying a state, and merging sets each provide idempotent behavior.
