Idempotency for an endpoint that takes money

Fourteen customers were charged twice in one afternoon. The payment provider had been slow rather than down, the mobile client had a fifteen-second timeout, and the charge took eighteen — so the client gave up, retried, and the server did the whole thing again. Every part of that is correct behaviour by something.

The symptom

mysql> SELECT customer_id, COUNT(*), GROUP_CONCAT(id), MAX(created_at)
    -> FROM charges
    -> WHERE created_at > '2020-07-14 14:00:00'
    -> GROUP BY customer_id, amount_cents
    -> HAVING COUNT(*) > 1;

| customer_id | COUNT(*) | ids           | max(created_at)     |
|        4471 |        2 | 88104,88131   | 2020-07-14 14:22:31 |
|        8812 |        2 | 88109,88144   | 2020-07-14 14:23:02 |
... 14 rows

-- and the gap between each pair: 15 to 17 seconds.

Fifteen seconds is the client’s timeout, which is the entire diagnosis. The pairs cluster in the twenty minutes the gateway was slow and stop when it recovered.

Why it happens

A timeout is a statement about the client’s patience and says nothing about the server. Three things are indistinguishable from the client’s side: the request never arrived, the request was processed and the response was lost, and the request is still being processed right now.

The client cannot resolve that ambiguity by waiting longer — it can only decide whether retrying is safe, and for a charge it is not. So the server has to make it safe, because the server is the only participant that knows what happened.

The fix

A key the client generates

// the client generates it ONCE, before the first attempt,
// and reuses it for every retry of the same logical operation

POST /api/charges
Idempotency-Key: 9c1f4a7e-3b2d-4f81-a6e0-11d0c8b3f204
Content-Type: application/json

{ "amount_cents": 4900, "currency": "GBP", "card_token": "tok_..." }

The key has to come from the client, because the server cannot tell two identical requests apart from one request sent twice — the payload is the same either way. A customer legitimately buying the same thing twice in a minute is a different operation with a different key, and only the client knows which it is.

Generating it per operation rather than per attempt is the part that has to be documented, because the natural instinct when writing a retry loop is to generate a fresh key each time — which reproduces the original bug with extra steps.

The unique index arbitrates; a SELECT does not

CREATE TABLE idempotent_requests (
  id              BIGINT AUTO_INCREMENT PRIMARY KEY,
  idempotency_key VARCHAR(64) NOT NULL,
  route           VARCHAR(128) NOT NULL,
  request_hash    CHAR(64) NOT NULL,
  state           ENUM('in_progress','complete') NOT NULL,
  response_status SMALLINT UNSIGNED NULL,
  response_body   MEDIUMTEXT NULL,
  created_at      DATETIME(6) NOT NULL,
  UNIQUE KEY uk_key_route (idempotency_key, route)
) ENGINE=InnoDB;

// racy. passes every test written with one worker.
if (! IdempotentRequest::where('idempotency_key', $key)->exists()) {
    IdempotentRequest::create([...]);
}

// the database decides, which is the only thing that can
try {
    $record = IdempotentRequest::create([
        'idempotency_key' => $key,
        'route'           => 'charges.store',
        'request_hash'    => hash('sha256', $request->getContent()),
        'state'           => 'in_progress',
        'created_at'      => now(),
    ]);
} catch (QueryException $e) {
    if (! $this->isDuplicateKey($e)) {
        throw $e;
    }

    return $this->handleReplay($key);
}

The check-then-act version is the one everybody writes first and it fails under exactly the conditions this exists to handle: two retries arriving concurrently both pass the check. The unique index is the only arbiter that works, and distinguishing a duplicate-key error from every other query error deserves a named method rather than a string match — the driver error code is stable and the message is not.

Scoping the key to the route is what stops a client reusing one key across two endpoints and getting the wrong cached response. Two customers cannot collide because a UUID is a UUID, and a client that generates sequential keys is a client that will collide with itself.

Storing the response, so a retry gets the same answer

// do the work and record the outcome in ONE transaction
DB::transaction(function () use ($record, $request) {
    $charge = $this->gateway->charge(
        $request->cardToken(),
        $request->money()
    );

    $response = new ChargeResource($charge);

    $record->update([
        'state'           => 'complete',
        'response_status' => 201,
        'response_body'   => $response->toJson(),
    ]);
});

Returning the stored response rather than a 409 is what a retrying client actually needs — it asked for a charge and it gets the charge, which is the same answer it would have got had the first response arrived. A conflict status forces the client to have a second code path for a situation it cannot distinguish from success.

The transaction is what stops a crash between the work and the record leaving a key claimed and a charge made with no way to report it. This only works because the charge itself is recorded in the same database; a charge that exists only at the gateway needs the gateway’s own idempotency key, which every payment provider offers for exactly this reason.

The request in flight, which is the case people forget

private function handleReplay(string $key): Response
{
    $prior = IdempotentRequest::where('idempotency_key', $key)
        ->where('route', 'charges.store')
        ->firstOrFail();

    if ($prior->state === 'complete') {
        return response($prior->response_body, $prior->response_status)
            ->header('Idempotent-Replay', 'true');
    }

    // still running. the first attempt has not finished.
    return response()->json([
        'error' => ['code' => 'request_in_progress'],
    ], 409)->header('Retry-After', '2');
}

A retry arriving while the first attempt is still running is the common case rather than an edge case — the client timed out because the operation was slow, so the operation is probably still going. Returning a 409 with a Retry-After tells the client to wait rather than to give up, which is the only correct answer.

An in_progress record left behind by a crashed process blocks that key forever unless something reaps it. A sweep marking anything older than a few minutes as failed is required, and choosing that threshold means knowing the longest the operation can legitimately take.

-- on a timer, every minute
UPDATE idempotent_requests
SET state = 'complete', response_status = 500,
    response_body = '{"error":{"code":"request_abandoned"}}'
WHERE state = 'in_progress'
  AND created_at < NOW(6) - INTERVAL 5 MINUTE;

The same key with a different body

// a client bug, or a key reused deliberately — and it must not
// silently return the wrong response
if (! hash_equals($prior->request_hash, hash('sha256', $request->getContent()))) {
    return response()->json([
        'error' => [
            'code'    => 'idempotency_key_reused',
            'message' => 'This key was used with a different request body.',
        ],
    ], 422);
}

Without this check a client that reuses a key for a different charge gets the previous charge’s response and believes the second one succeeded — which is a silent failure that loses money in the other direction. Storing a hash rather than the body keeps the table small and is sufficient for the comparison.

Normalising the body before hashing is worth thinking about: a client that reorders JSON keys between retries produces a different hash for an identical request. Hashing the parsed and re-encoded canonical form solves it and costs a decode per request.

Scope and expiry

scope     per key, per route. NOT per customer — a key is
          already unique, and scoping by customer means a
          stolen key can be replayed against another account.

expiry    24 hours. no reasonable client retries later.
          and the table has to be pruned, or it grows forever.

which endpoints  anything non-idempotent by nature:
                 POST that creates, POST that charges,
                 POST that sends. not GET, not PUT, not DELETE
                 — those are idempotent already, by definition.

The observation that PUT and DELETE are already idempotent is worth making because it narrows the work considerably: a well-designed API needs this on a handful of endpoints rather than everywhere. An endpoint that needs it is frequently an endpoint that would have been a PUT with a client-generated id, which is the other way of solving the same problem.

Pruning is a scheduled delete and is easy to forget until the table has forty million rows and the unique index no longer fits in memory. Twenty-four hours of a busy endpoint is a manageable size; a year of it is not.

Verifying it worked

# the same request, twice, concurrently
$ for i in 1 2; do
>   curl -s -o /dev/null -w '%{http_code} ' 
>     -H 'Idempotency-Key: test-9c1f4a7e' 
>     -X POST https://staging/api/charges -d @charge.json &
> done; wait
201 409

# sequentially, after the first completes
$ curl -s -D- -H 'Idempotency-Key: test-9c1f4a7e' 
    -X POST https://staging/api/charges -d @charge.json | head -3
HTTP/2 201
idempotent-replay: true

$ mysql -Nse 'SELECT COUNT(*) FROM charges WHERE ...'
1

The concurrent case is the one worth automating, because it is the one the check-then-act version passes in a sequential test and fails in production. Running two requests in parallel and asserting on one charge is a test that would have caught the original bug.

The Idempotent-Replay header is not required by anything and is worth sending: it turns “did my retry work” into something visible in a client log, and it makes the mechanism testable from the outside.

What this costs

A table, a header clients must send, and documentation somebody has to read. The header is the awkward part — an endpoint that requires it rejects every existing client, and one that accepts requests without it protects nobody. The path that worked was accepting both for a release, logging how many arrived without a key, and requiring it once the number reached zero.

The deeper cost is that this only covers the boundary it is applied to. A charge that succeeds at the gateway and fails to record locally is still a double charge on a retry, because the local record is what the key checks against — which is why the gateway’s own idempotency key has to be used as well, derived from the same value. Two layers of the same mechanism is more machinery than it sounds and it is the only arrangement that is actually correct.