Idempotency

Press a button that sets the volume to 20 several times, and the volume stays at 20. Press a button that raises it by 1, and the value changes each time. Idempotence, often called idempotency in an API context, is the property of an operation whose first result remains unchanged when the operation is applied again.

Server developers often use the term when preventing duplicate payments or storing request keys, but mathematicians used it much earlier to describe repeated operations. The same name appears in function composition, HTTP retries, and merging the state of replicas. In each setting, the question is what gets repeated and which result we compare.

A name from powers

In §25 of Linear Associative Algebra, Benjamin Peirce uses the word idempotent and says that, unless otherwise specified, it means A² = A. He also defines nilpotent for an object that becomes zero when raised to a power. The names describe whether repeated multiplication yields the original element or zero. Benjamin Peirce was the father of Charles Sanders Peirce.

(Original source)

The image shows printed page 8, PDF page 20, of a public-domain scan of the 1882 edition. Its preface records that lithographed copies were distributed in 1870. The passage mentions higher powers before taking the square as the default, so the 1870 distribution and the 1882 edition quoted here are identified separately. Edition record, preface.

Apply a function to its own result

Now put function composition in place of multiplication. A function f from a set to itself is idempotent if f(f(x)) = f(x) for every input x. Feed the first result back into the same function, and that result holds.

For integer absolute value, the first calculation has already removed a negative sign, so the next calculation returns the same value. Squaring takes 2 to 4, then 4 to 16.

def square(x):
    return x * x

assert abs(abs(-3)) == abs(-3)
assert square(square(2)) != square(2)
print(abs(-3), square(2), square(square(2)))  # 3 4 16

This runs in Python 3. Repeated calls to square(2) each return 4; that shows determinism, the same result for the same input. To check idempotence, feed that 4 into the next calculation. Reusing an input and applying an operation to its previous result are different tests.

This also connects to fixed points. A value y with f(y) = y is a fixed point. Every value produced by an idempotent function is immediately one: with y = f(x), we have f(y) = f(f(x)) = f(x) = y. Once the function produces a result, further applications leave it there.

A calculation that settles only after several repetitions has a different property. On nonnegative integers, repeated application of h(n) = n // 2 takes 8 through 8 → 4 → 2 → 1 → 0 → 0. It eventually reaches a fixed point, but the first result, 4, differs from the second, 2. A function is not idempotent across its whole domain merely because one input eventually stabilizes or another input happens to be a fixed point.

For a binary operation, compare what happens when both operands are the same. Set union satisfies A ∪ A = A. This has a different form from feeding a function its previous result, yet both laws say that repeating the same object in the operation makes no further change.

Which program state do we compare?

A volume-setting command transforms a state s into another state. Write that command as T, and we can ask whether T(T(s)) = T(s).

Both rows start at volume 5 and apply the same command twice within that row. This diagram was drawn to compare the resulting states.

def set_volume(state):
    return {**state, "volume": 20}

def increase_volume(state):
    return {**state, "volume": state["volume"] + 1}

initial = {"volume": 5}
assert set_volume(set_volume(initial)) == set_volume(initial)
assert increase_volume(increase_volume(initial)) != increase_volume(initial)
print(set_volume(initial), increase_volume(increase_volume(initial)))

These functions return new dictionaries instead of operating a volume control. Both compute a new value from their input, but only set_volume is idempotent. A command that writes to a real device can cause a side effect and still be idempotent with respect to the volume we observe.

One Boolean negation gives a different value from two. Squaring also leaves 0 and 1 unchanged but fails the idempotence law at 2. A single output, or a few inputs where the law happens to hold, cannot establish the property over the full domain.

In a real program, we must also choose the state under observation. If the program records each button press separately from the volume, repeated setting may preserve the volume while changing that larger record each time. HTTP later chose the request's “intended effect” as its comparison for a related reason.

When other commands intervene

Idempotence describes reapplying the same operation. The order of different operations is a question of commutativity. Commands to set the volume to 20 and to 50 are each idempotent, but the final volume depends on which runs last.

Composing idempotent operations does not always produce another idempotent operation. On pairs of integers, let F(x, y) = (x, x) and G(x, y) = (y + 1, y). Applying either F or G twice has the same result as applying it once. Yet repeating a sequence of F followed by G changes the pair again:

If two idempotent operations also commute, their composition is idempotent: expand two applications of the composition, put equal operations together by changing their order, and apply each idempotence law. When a retry repeats a whole workflow, its combined effect needs its own check.

Another user can change the state between attempts. A client sets the volume to 20, another user changes it to 50, and then the first client retries its earlier command: the volume returns to 20. The setting command remains idempotent, but preserving the other user's change requires a separate mechanism, such as a version condition or concurrency control.

Retrying when no response arrives

A client sends an order request to a server and receives no response. The connection may have failed before the server received the request, or the server may have saved the order and the response may have disappeared on its way back. Sending the request again can create the order in the first case; if the server also creates a new order in the second case, there will be two.

In §3.2 of their 1984 paper Implementing Remote Procedure Calls, Birrell and Nelson use call identifiers and sequence numbers to distinguish duplicate call packets. A caller retransmits a packet to obtain a response, and the receiver decides whether to execute the same call again. Early RPC design treated those as separate actions. Paper and publication record, paper PDF.

On the web, §9.1 of RFC 2068, the 1997 HTTP/1.1 specification, distinguishes safe methods from idempotent ones. It separates a client's request to retrieve information from a request whose effect does not accumulate when sent again. The distinction helps a client decide which requests it can retry automatically after a broken connection. RFC 2068 §§8.1.4 and 9.1.

RFC 7231 in 2014 and RFC 9110 in 2022 retain the distinction. The table describes method semantics; server implementers must make their code preserve those effects across repeated requests. RFC 7231 §4.2.

RFC 5789 defined PATCH for partial modification in 2010 and explains that a particular PATCH request can be constructed to be idempotent. Assigning the value 20 and adding 1 to the current value have different effects when repeated, even though both are partial modifications. For changes dependent on a base version, it recommends conditions such as a strong ETag with If-Match. RFC 5789 §2.

A first DELETE can return 204 and a later DELETE 404 while the intended deletion effect remains the same. RFC 9110 allows per-request logs or history and notes that responses may differ. The client compares the server effect intended by the request. RFC 9110 §9.2.2.

Another user may change a resource between two GET requests, so their responses can differ too. Whether a response can be stored and reused depends separately on cacheability and freshness rules. That is why safety, idempotence, and cacheability have separate names. RFC 9110 §§9.2.1 and 9.2.3.

Request keys distinguish attempts at one order

If a server creates a new order every time a client says to add one, a retry creates another order. The client and server first need a rule for which requests count as attempts at the same operation.

(Original source)

This diagram appears on PDF page 4, printed page 3, of Malcolm Featonby's Making retries safe with idempotent APIs. The caller has not received the first response, so it retries with the same identifier; the service checks processing state in StateStore. © Amazon Web Services.

A customer can deliberately order the same item and quantity twice. If the server merges orders solely because their request bodies have the same hash, it loses that intention. Here the caller supplies an identifier: it reuses the key for the same operation and chooses a new one for a separate order. The server defines the caller and key scope, how it handles different content under one key, and how long it retains the record. AWS article.

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.

(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

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.