Idempotency Across Transactions and Races

  • Idempotency
  • Distributed Systems

Idempotency is a rather uninteresting concept until you receive that first duplicate order.

For many years I held a pretty basic model in mind - if an API consumer sends an Idempotency-Key header, we keep it somewhere and ensure the same request never creates the same thing more than once.

It’s not entirely wrong, but it’s not the whole story either.

The header itself is the easiest part. The hard part is what the key is allowed to mean, what it is bound to, what to do if the payload changes slightly and what to do in case of two identical requests coming simultaneously.

I came across this problem while building an order creation API. Imagine something like:

POST /orders

Let’s assume that the above endpoint creates a trading order in some brokerage system. In case of a timeout, the client might want to retry. However, if the system has already created the order and the response got lost somewhere between our systems, retrying would create another order.

This applies to any payments, brokerage, billing or any other money-related system, where “try again” cannot mean “do it again”.

The retry problem

A normal POST endpoint is not safe to retry. For our brokerage service, let’s assume the client sends:

POST /orders
Idempotency-Key: retry-abc

{
  "instrument": "US0378331005",
  "side": "buy",
  "amount": "100.00",
  "currency": "EUR"
}

The server creates an order and returns 201 Created.

But what happens if this response does not make it back to the client? Maybe the load balancer drops the connection. Maybe the client has a timeout of 2 seconds. Maybe mobile internet does mobile internet stuff.

So the client does the right thing and repeats the request with the same key. Two possible worlds exist:

  • We have not received the first request, so we need to generate the order.
  • We have received the first request and generated the order, so we need to return it.

The client does not know which of these two worlds we are living in.

That’s the entire idea behind idempotency: shift the ambiguity to the server since it is the only entity able to solve the problem correctly.

The easy version

The first version people usually reach for is this:

CREATE TABLE idempotency_keys (
  id TEXT PRIMARY KEY,
  idempotency_key TEXT NOT NULL UNIQUE,
  created_at TIMESTAMPTZ NOT NULL
);

then in the endpoint:

if key already exists:
  return existing order

create order
store key
return order

It seems perfect until somewhere around the five-minute mark (or thirty, if you are taking a smoke).

That’s when the doubts come up.

What will happen if two different customers have the same key? What will happen if one customer uses the same key to send two different requests? What happens if the initial request contains amount = 100.00 and the retry contains amount = 50.00? What happens if two identical requests arrive at the same time, and both pass the “does this key exist?” test but before one of them writes the row?

A single idempotency key is insufficient to describe the situation.

An idempotency key is locally significant, in the context of the path, method, and request shape.

The behavior I care about

For an order creation endpoint, I would expect such semantics:

  • Client A, same key, same endpoint, same payload: create order, return order
  • Client A, same key, different payload: fail with message “invalid idempotency key”
  • Client A, same key, different endpoint: fail with message “invalid idempotency key”
  • Client B, same key: unrelated
  • Concurrent retries: single request wins, other requests return result of the winning request
  • Validation failure: do not mark idempotency key as used

And the latter is more important than it might seem.

When a client sends a wrong request with an idempotency key and we mark the idempotency key as used, then client can’t fix the request and resend it because we already have marked this key as used with some other payload. IMO, it’s bad for API.

I want to use idempotency key only after successful domain operation.

Give the key a memory

A better designed table will look as follows:

CREATE TABLE request_replays (
  id TEXT PRIMARY KEY,
  client_id TEXT NOT NULL,
  request_key TEXT NOT NULL,
  method TEXT NOT NULL,
  path TEXT NOT NULL,
  request_hash TEXT NOT NULL,
  response_body JSONB NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  expires_at TIMESTAMPTZ NOT NULL,

  CONSTRAINT uq_request_replays_client_key
    UNIQUE (client_id, request_key)
);

The names are not important, rather, the schema is.

  • client_id scopes the key. This means that two clients can both use abc123 and they are distinct keys for us.
  • method and path make sure there is no reuse of the key across multiple endpoints. The key used for POST /orders would never work for POST /withdrawals.
  • request_hash ties the key to the payload. Same key and different body means that you have a new request attempting to reuse a retry token.
  • response_body stores the domain object or response which should be returned on replay. In case of order creation, it will be our order.
  • expires_at makes sure that the table does not become infinite. Idempotency is usually about the retry window. The window is usually 24 hours for most APIs.

Fingerprinting the body

The request hash should be boring and predictable. The problem is hashing raw JSON strings. These two requests are identical:

{ "side": "buy", "amount": "100.00" }

{ "amount": "100.00", "side": "buy" }

Raw string hashing will make them distinct since the order of keys is different. That’s why I like the canonical format:

def fingerprint(body):
    normalized = remove_nulls(body)
    canonical = json_dumps(normalized, sort_keys=True, compact=True)
    return sha256(canonical)

There are some hidden decisions here. Keys ordering makes the order of object elements irrelevant. Null stripping makes these two equal:

{ "amount": "100.00", "limit_price": null }
{ "amount": "100.00" }

This is how many JSON APIs treat optional elements. If our API behaves differently when null is explicitly stated compared to not being there at all, then we don’t strip nulls. The idea is not that null stripping is universally correct. The idea is that the rule should be explicit.

Order of list elements is still important. These are not identical:

{ "legs": ["buy", "sell"] }
{ "legs": ["sell", "buy"] }

That is what we usually want.

First request

On the first valid request, the flow is roughly:

read idempotency key from header
compute request fingerprint

validate request
create order
store replay record with the order response

commit
return order

The storing of the replay record needs to be done in the same transaction as the order creation itself.

It is the one aspect where mistakes can easily creep in.

  • When we do order creation and the storing of the replay record fails, the client may retry and create another order because he is not aware of the retry key.
  • In case we do the storing of the replay record first and fail at order creation, the client can retry and receive a false “order processed” response.

Both the rows have to commit or neither will.

Replay

When the same request comes back later:

find replay record by (client_id, request_key)

if not found:
  continue as a new request

if method or path differs:
  reject

if request_hash differs:
  reject

return stored response_body

This is why it makes sense to store the response. We don’t need to infer the response from the current state of the database.

It can be important when the order was modified after being created. It could transition from new to accepted. It might have been enriched through some workflow logic. The response schema may have fields that are true at creation time only.

Replaying the create request needs to return what the initial successful request created and not what the order looks like right now.

There are scenarios when returning current state is acceptable. But it needs to be done intentionally as a product decision. I usually prefer returning the original creation response because it has the simplest retry semantics.

When two requests race

A tricky scenario is when two identical requests come in at once. Each one has:

client_id = cli_123
request_key = retry-abc
request_hash = same hash

Request A starts creating the order. Request B starts creating the order too.

If the application does only “check then insert”, both can pass the check and write the replay row at the same time.

This is why the database has to be part of the solution. Unique constraint on (client_id, request_key) acts as the lock: one request succeeds in inserting the replay row. The other fails to insert it due to the constraint violation.

But when it happens, the losing side should not throw a database error and crash. It should read the winning side row and perform the same replay rules:

try:
  create order
  insert replay row
  commit
  return order

except unique_violation on (client_id, request_key):
  winner = read replay row from primary database

  if winner.path != path or winner.method != method:
    reject

  if winner.request_hash != request_hash:
    reject

  return winner.response_body

there are two little things to keep in mind about it:

  1. catch only the unique constraint you expect. In case the order insert fails due to any other database constraint, it is not an idempotency replay and should bubble up.
  2. read the winning side row from the primary database, not a read replica. While in the race condition, the winning row may not be available in the replica yet. It is precisely the worst time to check eventually consistent copy (don’t ask me how I know this :sob:)

Failed requests

I don’t keep any failed validation responses.

In case of failure due to account being disabled, market being disabled, instrument not being tradable or an invalid amount, the key goes unused. Client can correct the request and resend with the same key.

However, there is another pattern where you keep all responses, even 4xx. It’s a legitimate pattern, particularly useful for guaranteeing “same key, same response” at the HTTP level.

For internal APIs of products, I often go with just keeping successful domain creation. This way, no validation failure pollutes a key. However, this choice must be made explicitly, since clients will base their retry logic on your behavior.

Status codes

It does not matter too much to me which HTTP status code is returned in case of payload mismatch; either 409 Conflict or 422 Unprocessable Entity could be justified.

  • 409 says the key conflicts with an operation that is already in progress.
  • 422 says the server cannot process the request because the key was previously used for a different request payload.

Pick one and make the error message dull:

Idempotency key already used with a different request payload

That way the client will know exactly what they did wrong.

Easy mistakes

The design is simple, but there are a couple of points that can be easily overlooked.

  • Don’t make the key global, instead localize it per client or tenant.
  • Don’t compare the raw request bodies instead canonicalize them first.
  • Don’t keep the replay row outside the domain transaction.
  • Don’t treat every database consistency violation as an idempotency conflict.
  • Don’t read the winning row from the replica when there is a race.
  • Don’t allocate the key before the validation unless that is intentional and failed requests are meant to use up keys.
  • Don’t retain the replay rows indefinitely unless there is a specific reason. Replay rows should be treated as transient retry states, they are not business data.

None of these are difficult on their own, but these problems happen because we think of idempotency as a middleware rather than a component of the write model. I have learned the hard way.