Idempotency under retry — the claim is the answer, not the lock

The idea

The claim is the answer, not the lock

A client calls charge() and the connection drops before the response arrives. It cannot know whether the charge went through, so it retries with the same idempotency key. Two requests for that key are now in flight together. The guard most people reach for checks a map, decides the key is new, charges, and writes the outcome — a check-then-act race. That's E1's territory, except the window here is not one field and one instruction. It's a whole gateway call, seconds wide, and nothing the caller does closes it, because the caller cannot make its own two calls atomic.

This lesson's own demo puts a size on that window. Forty threads submit the same idempotency key at once against a gateway that takes 15 milliseconds to answer, run three times for 45 rounds total. A ledger that reads containsKey and only later writes put reaches the gateway 40 of 40 threads, in every single round, no exceptions. A ledger built around ledger.claim(key) reaches the gateway exactly once, in every one of the same 45 rounds. Neither number is luck: 15 milliseconds is wide enough that forty threads finish reading the map long before the first of them finishes writing to it.

So the atomicity has to live inside that one method, claim(key). A ConcurrentHashMap.putIfAbsent hands ownership to exactly one caller, however many arrive together — but that's only half the answer, because the winner's receipt doesn't exist yet. A second caller needs somewhere to wait, not a boolean to interpret. A plain seen flag collapses "already done" and "in progress, wait for it" into one bit, so a caller arriving mid-charge either fires a second charge or invents a receipt nobody recorded. The fix needs three answers, not two: own it, read it, or wait for it, backed by a latch. The write before countDown() and the read after await() handle visibility, solved separately from ownership, and the wait stays bounded, because nothing here blocks forever.

Reach for a claim, not a flag, whenever a retry, the client's or the gateway's own, can hit the same operation twice.

Worked walkthrough

NOTES — one method, two calls, and the difference between them

Run it first

../../../.toolchain/jdk-21/bin/javac.exe -Xlint:all -d out src/*.java
../../../.toolchain/jdk-21/bin/java.exe -cp out Main

javac -Xlint:all prints nothing and exits 0. Real output, one run of three, all identical:

1. the naive ledger: containsKey, decide, charge, put -- two calls, not one
   gateway calls per round: 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
   exactly one charge in 0 of 15 rounds (min 40, max 40)

2. InMemoryCheckoutLedger: claim() is one call, atomicity and visibility separated
   gateway calls per round: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
   exactly one charge in 15 of 15 rounds (min 1, max 1)

Run three times, 45 rounds total for each ledger. The naive one reached the gateway 40 of 40 threads, in every single round, no exceptions. The claim-based one reached it exactly once, in every one of the 45 rounds. Neither number is a guess.

Why the naive one is not "occasionally wrong" — it is reliably wrong at this size

BrokenLedger.claim reads !settled.containsKey(key), then later writes settled.put(key, receipt) once the gateway call returns (15ms of sleep here, standing in for a real network round trip). Forty threads are released off one latch, so all forty read containsKey before any of them has had time to finish the gateway call and write. There is no window to get lucky in. The window is the entire 15ms, and forty threads take microseconds to walk through it. That is the point this lesson exists to make: an idempotency guard's check-then-act window is not one CPU instruction wide, the way a lost counter increment is.

It is as wide as the slow thing on the other end of the call. So the naive version does not fail sometimes. It fails every time a real crowd hits it. ConcurrentHashMap being thread-safe did not help, because thread safety of the collection was never the problem. The problem is that "check" and "act" are two calls on two different mental steps, and nothing stops a second thread from doing its own check between them.

If this reads like E1 or E2's territory, that is the seam worth being precise about. E1 asks whether two threads can reach a field: yes, settled can. E2 asks which primitive fits the shape of the update: a single field write would take volatile, a counter would take an atomic. Neither answer fits here, because there is no single field whose old value determines its new one. What has to be atomic here is a decision that spans an entire operation with a network call inside it: "has anyone already promised to do this?" The fix is not a primitive at all. It is a type, CheckoutClaim, that makes the third answer sayable: "someone is doing it, wait."

Receipt.java

Four fields, always constructed together through original or asDuplicate. There is no setter and no way to build a Receipt that reports success for a charge that never happened. asDuplicate keeps amountCents and attempts from the owner's receipt — a duplicate is being told the answer, not given a new one.

CheckoutClaim.java — a type because a boolean cannot hold three answers

owned() alone would tell a caller whether it is the owner. It says nothing about what a non-owner should do next, and "wait for the owner" versus "read what's already there" are different actions with different code paths. Collapsing them into boolean alreadyCharged is exactly the shape of bug this ledger exists to prevent. A caller that arrives while the owner is mid-charge reads alreadyCharged == false, since nothing has settled yet, decides charging is safe, and the customer is billed twice.

InMemoryCheckoutLedger.java, the two lines that matter

Settlement existing = byKey.putIfAbsent(idempotencyKey, fresh); — the entire atomicity story. One call, one decision, null to exactly one caller. Compare this to BrokenLedger in Main.java: same map type, same thread-safety guarantee on the collection, and it still fails, because containsKey then put is two calls regardless of what is between them.

receipt = outcome; failure = cause; settled.countDown(); inside Settlement.publish is the entire visibility story, and a different mechanism on purpose. putIfAbsent already decided who the owner is by the time this line runs. What this line does is make the owner's answer observable to threads calling await() on another core. The write happens before the countdown, and every awaitOutcome reads the field only after await() returns true. Miss this half, and the map stays correctly exclusive while the receipt a waiter reads is stale or null. That is a bug a single-threaded test cannot see, because there is only one thread to observe from.

The bounded wait, settled.await(limit.toMillis(), TimeUnit.MILLISECONDS), exists because the owner's charge can throw, hang, or take longer than expected. A waiter that blocks forever would turn one bad gateway call into every caller for that key being stuck. So awaitOutcome throws rather than returning silently on timeout — a caller finds out its request went unanswered instead of hanging indefinitely.

CheckoutService.java

Five statements, and the concurrency is confined to the first one: ledger.claim(idempotencyKey). After that call returns, this thread either owns the key or it does not. Owning it means everything downstream is ordinary sequential code, because nobody else is working on this key. Not owning it means the only legal move is claim.outcome(). There is no third path where a non-owner calls the gateway on the chance that it might still be needed.

The corpus's own numbers, for scale

corpus/notification-service ships the same shape at production size, with retries, channel selection and an observer list added. Its DECISION_LOG.md records a deliberately broken variant whose claim is !byKey.containsKey(key): the stress suite catches it on repetition 1 with expected: <1> but was: <202>. Same bug, same fix, a different amount of surrounding machinery.

Worked source

The 7 files of the worked design

Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.

• worked/src/CheckoutClaim.java 39 lines
• worked/src/CheckoutLedger.java 27 lines
• worked/src/CheckoutService.java 37 lines
• worked/src/InMemoryCheckoutLedger.java 148 lines
• worked/src/PaymentGateway.java 6 lines
• worked/src/Receipt.java 17 lines
• worked/src/Main.java 165 lines

worked/src/CheckoutClaim.java39 lines

/**
 * One caller's standing with respect to one idempotency key, for exactly as long as that key is
 * being decided.
 *
 * <p>A {@code boolean alreadyCharged} cannot represent this. There are three situations a caller
 * can be in, not two: nobody has touched this key, so this caller must do the charge; somebody
 * already finished it, so this caller reads the recorded receipt; or somebody is charging it
 * right now, so this caller must wait for that answer rather than deciding anything itself. A
 * boolean collapses the second and third case into one, and the caller that arrives while the
 * charge is still in flight either fires a second one or fabricates a receipt nobody wrote.
 */
public interface CheckoutClaim {

    /**
     * @return true if this caller owns the key and must perform the charge, then call exactly
     *         one of {@link #settle} or {@link #abandon}. False means this caller lost the race
     *         and its only move is {@link #outcome()}.
     */
    boolean owned();

    /** Record the terminal result. Owner only. */
    void settle(Receipt receipt);

    /**
     * Give the key back unsettled, because the charge failed in a way nothing here anticipated.
     * Owner only. A key that was abandoned was never consumed, so a later call may try again.
     */
    void abandon(RuntimeException cause);

    /**
     * The terminal receipt for this key, waiting for it if it is not decided yet.
     *
     * @return the owner's receipt — a fresh copy marked as a duplicate for anyone who did not
     *         win the claim
     * @throws IllegalStateException if the wait exceeds the ledger's limit, or the owner
     *                                abandoned the key
     */
    Receipt outcome();
}

worked/src/CheckoutLedger.java27 lines

import java.util.Optional;

/**
 * The record of what has been decided about each idempotency key.
 *
 * <p>Not {@code contains(key)} plus {@code put(key, receipt)}. That pair is the bug: reading
 * "is this key known?", deciding it is not, charging, and later writing the outcome is a
 * check-then-act that spans the whole of a gateway call, and no care taken by the caller can
 * make its own two separate calls into one atomic one. So the atomicity lives in here, behind
 * one method, and the interface makes the wrong thing unaskable — there is no way to find out
 * whether a key is taken without taking it.
 */
public interface CheckoutLedger {

    /**
     * Atomically claim {@code idempotencyKey}. Exactly one caller is ever told
     * {@code owned() == true} for the life of the key, however many arrive at once and however
     * many arrive while the owner is still working.
     */
    CheckoutClaim claim(String idempotencyKey);

    /**
     * @return the terminal receipt for this key, or empty if the key is unknown or still being
     *         decided. A key nobody has settled has no outcome to report.
     */
    Optional<Receipt> find(String idempotencyKey);
}

worked/src/CheckoutService.java37 lines

import java.util.Objects;

/**
 * The whole point of this lesson in five lines. Everything about retrying, waiting and
 * publishing the answer lives behind {@link CheckoutLedger#claim}; this class does not know a
 * lock exists.
 */
public final class CheckoutService {

    private final CheckoutLedger ledger;
    private final PaymentGateway gateway;

    public CheckoutService(CheckoutLedger ledger, PaymentGateway gateway) {
        this.ledger = Objects.requireNonNull(ledger, "ledger");
        this.gateway = Objects.requireNonNull(gateway, "gateway");
    }

    public Receipt charge(String idempotencyKey, long amountCents) {
        CheckoutClaim claim = ledger.claim(idempotencyKey);
        if (!claim.owned()) {
            // Somebody else owns this key. Wait for their answer and hand it back — never a
            // second gateway call, and never a receipt this thread invented.
            return claim.outcome();
        }
        try {
            gateway.charge(idempotencyKey, amountCents);
            Receipt receipt = Receipt.original(idempotencyKey, amountCents);
            claim.settle(receipt);
            return receipt;
        } catch (RuntimeException failure) {
            // The key was never consumed, so give it back rather than leaving anyone waiting on
            // a claim that will never settle.
            claim.abandon(failure);
            throw failure;
        }
    }
}

worked/src/InMemoryCheckoutLedger.java148 lines

import java.time.Duration;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;

/**
 * The in-process ledger. One {@link ConcurrentHashMap}, and the one call to
 * {@code putIfAbsent} is the whole of the atomicity this class needs.
 *
 * <p>Two different problems get two different fixes here, on purpose.
 *
 * <p><b>Atomicity</b> — deciding who owns the key — is {@link ConcurrentMap#putIfAbsent}. It
 * hands {@code null} to exactly one caller per key, however many arrive together, and that is
 * all it does: the winner's receipt does not exist yet, so there is nothing to publish at this
 * point.
 *
 * <p><b>Visibility</b> — getting the winner's answer to everyone waiting on it — is a
 * {@link CountDownLatch} plus a {@code volatile} field. The write happens before
 * {@code countDown()}; every waiter reads it after {@code await()} returns. A candidate who
 * wires the map correctly and then hands the receipt across through a plain field has solved
 * half of this, and it is not the half that shows up in a quick test — it is the half that
 * shows up under load, when a reader can observe the winner's write "eventually" instead of in
 * time.
 *
 * <p>{@code computeIfAbsent} is not used here even though it looks shorter: its mapping
 * function runs while the map's bin lock for that key is held, and the charge — a slow gateway
 * call — would run inside it, serialising every other key that happens to hash near this one.
 * The map is touched for the one instant that has to be atomic; the charge happens outside it.
 * No lock of any kind is held while the gateway is called anywhere in this file.
 *
 * <p>The wait a loser does is bounded. An unbounded {@code await()} turns one wedged gateway
 * call into a wedged caller, and this ledger's whole contract is that no method blocks forever.
 */
public final class InMemoryCheckoutLedger implements CheckoutLedger {

    private final ConcurrentMap<String, Settlement> byKey = new ConcurrentHashMap<>();
    private final Duration waitLimit;

    public InMemoryCheckoutLedger(Duration waitLimit) {
        if (waitLimit == null || waitLimit.isNegative() || waitLimit.isZero()) {
            throw new IllegalArgumentException("wait limit must be positive, got " + waitLimit);
        }
        this.waitLimit = waitLimit;
    }

    @Override
    public CheckoutClaim claim(String idempotencyKey) {
        Settlement fresh = new Settlement();
        Settlement existing = byKey.putIfAbsent(idempotencyKey, fresh);
        // The whole race, resolved in one call: existing is null for exactly one caller, no
        // matter how many called claim() at the same instant.
        return existing == null
                ? new Held(idempotencyKey, fresh, true)
                : new Held(idempotencyKey, existing, false);
    }

    @Override
    public Optional<Receipt> find(String idempotencyKey) {
        Settlement settlement = byKey.get(idempotencyKey);
        return settlement == null ? Optional.empty() : Optional.ofNullable(settlement.recorded());
    }

    /** One key's outcome and the latch that publishes it to whoever did not win the claim. */
    private static final class Settlement {

        private final CountDownLatch settled = new CountDownLatch(1);
        private volatile Receipt receipt;
        private volatile RuntimeException failure;

        /** Written before the countdown, so a waiter that gets past await() can see it. */
        void publish(Receipt outcome, RuntimeException cause) {
            receipt = outcome;
            failure = cause;
            settled.countDown();
        }

        Receipt recorded() {
            return receipt;
        }

        Receipt awaitOutcome(String key, Duration limit) {
            try {
                if (!settled.await(limit.toMillis(), TimeUnit.MILLISECONDS)) {
                    throw new IllegalStateException(
                            "waited " + limit.toMillis() + "ms for " + key + " to settle and it has not");
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                throw new IllegalStateException("interrupted waiting for " + key, e);
            }
            RuntimeException cause = failure;
            if (cause != null) {
                throw new IllegalStateException(
                        "the caller that owned " + key + " failed: " + cause.getMessage(), cause);
            }
            return receipt;
        }
    }

    /** One caller's view of one key. Ownership is per caller; the settlement is shared. */
    private final class Held implements CheckoutClaim {

        private final String key;
        private final Settlement settlement;
        private final boolean owner;

        private Held(String key, Settlement settlement, boolean owner) {
            this.key = key;
            this.settlement = settlement;
            this.owner = owner;
        }

        @Override
        public boolean owned() {
            return owner;
        }

        @Override
        public void settle(Receipt receipt) {
            requireOwner();
            settlement.publish(receipt, null);
        }

        @Override
        public void abandon(RuntimeException cause) {
            requireOwner();
            // Unclaim first, then wake the waiters: a caller that retries this key after seeing
            // the failure must find it free, and a waiter that arrives during the removal simply
            // joins the settlement that is about to report the failure. Nobody is stranded.
            byKey.remove(key, settlement);
            settlement.publish(null, cause);
        }

        @Override
        public Receipt outcome() {
            Receipt settled = settlement.awaitOutcome(key, waitLimit);
            return owner ? settled : settled.asDuplicate();
        }

        private void requireOwner() {
            if (!owner) {
                throw new IllegalStateException("only the owner of " + key + " may settle it");
            }
        }
    }
}

worked/src/PaymentGateway.java6 lines

/** The slow, unreliable thing on the other end of a charge. */
public interface PaymentGateway {

    /** Actually moves money. Takes real time, and must never run twice for one purchase. */
    void charge(String idempotencyKey, long amountCents);
}

worked/src/Receipt.java17 lines

/**
 * What one checkout settles to. The four fields always arrive together — there is no partially
 * built receipt anywhere in this lesson, on purpose: a value that could be half-written is a
 * value somebody will read half-written.
 */
public record Receipt(String idempotencyKey, long amountCents, boolean duplicate, int attempts) {

    /** The one receipt the caller that actually reached the gateway gets. */
    public static Receipt original(String idempotencyKey, long amountCents) {
        return new Receipt(idempotencyKey, amountCents, false, 1);
    }

    /** What every later caller for the same key gets: the same facts, marked as a replay. */
    public Receipt asDuplicate() {
        return new Receipt(idempotencyKey, amountCents, true, attempts);
    }
}

worked/src/Main.java165 lines

import java.time.Duration;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Two ledgers, the same crowd, the same slow gateway. The only difference is whether "is this
 * key taken" and "take this key" are one call or two.
 */
public final class Main {

    private static final int CROWD = 40;
    private static final int ROUNDS = 15;
    private static final long GATEWAY_DELAY_MS = 15;

    public static void main(String[] args) throws Exception {
        System.out.println("1. the naive ledger: containsKey, decide, charge, put -- two calls, not one");
        int[] naiveCharges = new int[ROUNDS];
        for (int round = 0; round < ROUNDS; round++) {
            naiveCharges[round] = oneRound(new BrokenLedger());
        }
        report(naiveCharges);

        System.out.println();
        System.out.println("2. InMemoryCheckoutLedger: claim() is one call, atomicity and visibility separated");
        int[] claimCharges = new int[ROUNDS];
        for (int round = 0; round < ROUNDS; round++) {
            claimCharges[round] = oneRound(new InMemoryCheckoutLedger(Duration.ofSeconds(5)));
        }
        report(claimCharges);
    }

    /** CROWD threads submit the SAME idempotency key at the same instant. Returns gateway calls. */
    private static int oneRound(CheckoutLedger ledger) throws InterruptedException {
        AtomicInteger gatewayCalls = new AtomicInteger();
        PaymentGateway gateway = (key, amount) -> {
            gatewayCalls.incrementAndGet();
            sleepQuietly(GATEWAY_DELAY_MS);
        };
        CheckoutService service = new CheckoutService(ledger, gateway);

        CountDownLatch ready = new CountDownLatch(1);
        CountDownLatch done = new CountDownLatch(CROWD);
        ExecutorService pool = Executors.newFixedThreadPool(CROWD, daemonThreads());
        try {
            for (int i = 0; i < CROWD; i++) {
                pool.submit(() -> {
                    try {
                        ready.await();
                        service.charge("order-77", 2_599);
                    } catch (InterruptedException interrupted) {
                        Thread.currentThread().interrupt();
                    } catch (RuntimeException fromGateway) {
                        // a losing thread that raced a failure; not exercised by this demo
                    } finally {
                        done.countDown();
                    }
                });
            }
            ready.countDown();
            done.await(20, TimeUnit.SECONDS);
        } finally {
            pool.shutdownNow();
        }
        return gatewayCalls.get();
    }

    private static void report(int[] chargesPerRound) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int roundsWithExactlyOne = 0;
        StringBuilder line = new StringBuilder();
        for (int charges : chargesPerRound) {
            min = Math.min(min, charges);
            max = Math.max(max, charges);
            if (charges == 1) {
                roundsWithExactlyOne++;
            }
            line.append(charges).append(' ');
        }
        System.out.println("   gateway calls per round: " + line.toString().trim());
        System.out.println("   exactly one charge in " + roundsWithExactlyOne + " of " + chargesPerRound.length
                + " rounds (min " + min + ", max " + max + ")");
    }

    private static void sleepQuietly(long millis) {
        try {
            Thread.sleep(millis);
        } catch (InterruptedException interrupted) {
            Thread.currentThread().interrupt();
        }
    }

    private static ThreadFactory daemonThreads() {
        return runnable -> {
            Thread thread = new Thread(runnable);
            thread.setDaemon(true);
            return thread;
        };
    }

    /**
     * The variant the decision log calls the bug itself: {@code containsKey} then {@code put},
     * on a genuinely concurrent map. The map's own thread safety does not help, because the
     * defect is two calls with a decision between them, not the collection underneath.
     */
    private static final class BrokenLedger implements CheckoutLedger {

        private final ConcurrentHashMap<String, Receipt> settled = new ConcurrentHashMap<>();

        @Override
        public CheckoutClaim claim(String idempotencyKey) {
            boolean isNew = !settled.containsKey(idempotencyKey);   // read
            return new BrokenClaim(idempotencyKey, isNew);          // decide -- and somebody
                                                                     // writes settled later
        }

        @Override
        public Optional<Receipt> find(String idempotencyKey) {
            return Optional.ofNullable(settled.get(idempotencyKey));
        }

        private final class BrokenClaim implements CheckoutClaim {

            private final String key;
            private final boolean owner;

            BrokenClaim(String key, boolean owner) {
                this.key = key;
                this.owner = owner;
            }

            @Override
            public boolean owned() {
                return owner;
            }

            @Override
            public void settle(Receipt receipt) {
                settled.put(key, receipt);
            }

            @Override
            public void abandon(RuntimeException cause) {
                // nothing was ever reserved, so there is nothing to give back
            }

            @Override
            public Receipt outcome() {
                // A caller that arrives before the owner has written anything has nothing to
                // read. There is no honest answer here, which is the point: this method cannot
                // exist correctly on top of containsKey()+put(), only approximately.
                Receipt found = settled.get(key);
                return found == null ? new Receipt(key, 0, true, 0) : found.asDuplicate();
            }
        }
    }
}