Idempotency, Ledgers, and Reconciliation

Payment systems retry: clients resend after timeouts, brokers redeliver messages, and operators replay files. This lesson shows how to make a retried operation take effect once, how to record money movements so that they always balance, and how to compare two sets of records. All examples run in memory in one process; a production system keeps the same structures in a database with unique constraints and transactions.

Idea	What it gives
Idempotency key	A retry returns the first result instead of repeating the effect
`computeIfAbsent` / `putIfAbsent`	Atomic "first caller wins" in a `ConcurrentHashMap`
At-least-once plus deduplication	The effect of "exactly once" processing
Double-entry ledger	Every movement debits one account and credits another by the same amount
Immutable journal	History is appended, never edited; corrections are new entries
Sealed state machine	The compiler checks that every payment state is handled
Reconciliation	A list of differences between two ledgers

Amounts are long minor units (cents), as in Money, BigDecimal, and Rounding.

Example 1: an idempotency key

An operation is idempotent when running it twice has the same effect as running it once. A client attaches an idempotency key, a unique id it generates per logical request, and the server stores the result under that key. A retry with the same key gets the stored result and causes no second charge.

Java

import java.util.HashMap;
import java.util.Map;

public class IdempotencyKey {
    record ChargeResult(String chargeId, long amount) {}

    static final Map<String, ChargeResult> results = new HashMap<>();
    static int charges = 0;

    static ChargeResult charge(String idempotencyKey, long amount) {
        ChargeResult previous = results.get(idempotencyKey);
        if (previous != null) return previous;
        charges++;
        ChargeResult r = new ChargeResult("ch_" + charges, amount);
        results.put(idempotencyKey, r);
        return r;
    }

    public static void main(String[] args) {
        System.out.println(charge("key-A", 500));
        System.out.println(charge("key-A", 500));   // client retry after a timeout
        System.out.println(charge("key-B", 500));   // a different request
        System.out.println("charges executed = " + charges);
    }
}

Output

ChargeResult[chargeId=ch_1, amount=500]
ChargeResult[chargeId=ch_1, amount=500]
ChargeResult[chargeId=ch_2, amount=500]
charges executed = 2

A real service also stores a fingerprint of the request body and rejects a reuse of the key with a different body, since that is a client bug rather than a retry. Keys expire after a retention window, after which a retry is treated as new.

Example 2: the race in check-then-act

Example 1 is correct for one thread. With concurrent retries, two threads can both see "no result" and both charge. A ConcurrentHashMap (see Concurrent Collections) does not fix this by itself, because get followed by put is two operations. The example forces the bad interleaving with a CyclicBarrier: all threads finish the check before any of them acts.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class CheckThenActRace {
    static final ConcurrentHashMap<String, String> results = new ConcurrentHashMap<>();
    static final AtomicInteger charges = new AtomicInteger();

    public static void main(String[] args) throws Exception {
        int threads = 8;
        CyclicBarrier afterCheck = new CyclicBarrier(threads);
        List<Thread> list = new ArrayList<>();
        for (int i = 0; i < threads; i++) {
            Thread t = new Thread(() -> {
                try {
                    String previous = results.get("key-A");   // check
                    afterCheck.await();                        // everyone has checked
                    if (previous == null) {                    // act
                        int n = charges.incrementAndGet();
                        results.put("key-A", "ch_" + n);
                    }
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            });
            list.add(t);
            t.start();
        }
        for (Thread t : list) t.join();
        System.out.println("charges executed = " + charges.get());
        System.out.println("more than one charge: " + (charges.get() > 1));
    }
}

Output

charges executed = 8
more than one charge: true

Without the barrier the race is rare, which is why it passes tests and then charges a customer twice in production. The barrier makes the window wide so the failure is repeatable.

Example 3: an atomic idempotent handler

ConcurrentHashMap.computeIfAbsent runs the mapping function at most once per absent key; other updates to that key (and possibly to other keys in the same bin) wait until it finishes. Storing a CompletableFuture instead of the result keeps the critical section short: the first caller installs the future and does the work outside the map, and every other caller waits on the same future (see Executors and CompletableFuture).

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

public class IdempotentHandler {
    record ChargeResult(String chargeId, long amount) {}

    private final ConcurrentHashMap<String, CompletableFuture<ChargeResult>> inFlight = new ConcurrentHashMap<>();
    final AtomicInteger charges = new AtomicInteger();

    ChargeResult handle(String key, long amount) {
        CompletableFuture<ChargeResult> mine = new CompletableFuture<>();
        CompletableFuture<ChargeResult> existing = inFlight.putIfAbsent(key, mine);
        if (existing != null) return existing.join();       // a retry: wait for the first result
        try {
            ChargeResult r = new ChargeResult("ch_" + charges.incrementAndGet(), amount);
            mine.complete(r);
            return r;
        } catch (RuntimeException e) {
            inFlight.remove(key, mine);                      // allow a retry after a failure
            mine.completeExceptionally(e);
            throw e;
        }
    }

    public static void main(String[] args) throws Exception {
        IdempotentHandler h = new IdempotentHandler();
        int threads = 8;
        CountDownLatch start = new CountDownLatch(1);
        Set<String> ids = ConcurrentHashMap.newKeySet();
        List<Thread> list = new ArrayList<>();
        for (int i = 0; i < threads; i++) {
            Thread t = new Thread(() -> {
                try { start.await(); } catch (InterruptedException e) { return; }
                ids.add(h.handle("key-A", 500).chargeId());
            });
            list.add(t);
            t.start();
        }
        start.countDown();
        for (Thread t : list) t.join();
        System.out.println("charges executed = " + h.charges.get());
        System.out.println("distinct charge ids returned = " + ids.size());

        ConcurrentHashMap<String, Integer> simple = new ConcurrentHashMap<>();
        AtomicInteger calls = new AtomicInteger();
        for (int i = 0; i < 3; i++) simple.computeIfAbsent("k", k -> calls.incrementAndGet());
        System.out.println("computeIfAbsent calls = " + calls.get() + ", value = " + simple.get("k"));
    }
}

Output

charges executed = 1
distinct charge ids returned = 1
computeIfAbsent calls = 1, value = 1

putIfAbsent returns null to exactly one caller, which then owns the work. On failure the entry is removed with remove(key, value), which removes only if the key still maps to that same future, so a later retry can run. computeIfAbsent is the shorter form when the computation is fast and must not call back into the same map.

Example 4: at-least-once delivery plus deduplication

Message brokers usually guarantee at-least-once delivery: a message is redelivered until the consumer acknowledges it, so a crash between processing and acknowledging produces a duplicate. "Exactly once" processing is built as at-least-once delivery plus a consumer that records processed message ids and skips repeats. The record of ids and the effect must be updated together; here they share one lock.

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DedupConsumer {
    record Message(String id, String account, long amount) {}

    private final Set<String> processed = new HashSet<>();
    private long balance;
    private int duplicates;

    synchronized void onMessage(Message m) {
        if (!processed.add(m.id())) {   // add returns false if already present
            duplicates++;
            return;
        }
        balance += m.amount();
    }

    public static void main(String[] args) {
        DedupConsumer c = new DedupConsumer();
        List<Message> delivered = List.of(
                new Message("m1", "acc-1", 100),
                new Message("m2", "acc-1", 250),
                new Message("m2", "acc-1", 250),   // redelivered after a lost ack
                new Message("m3", "acc-1", -50),
                new Message("m1", "acc-1", 100));  // redelivered again
        delivered.forEach(c::onMessage);
        System.out.println("delivered = " + delivered.size());
        System.out.println("duplicates skipped = " + c.duplicates);
        System.out.println("balance = " + c.balance);
    }
}

Output

delivered = 5
duplicates skipped = 2
balance = 300

In a database the same idea is a table of processed ids with a unique constraint, written in the same transaction as the effect. If the two are written separately, a crash between them produces either a lost message or a double effect.

Example 5: a double-entry ledger

In double-entry bookkeeping every transaction is a set of postings (entries against accounts) whose amounts sum to zero: a debit to one account is matched by a credit to another. Money is never created or destroyed inside the ledger, so the sum of all balances is always zero, which gives a cheap invariant check.

Java

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class DoubleEntry {
    record Posting(String account, long amount) {}      // + debit, - credit
    record Transaction(String id, List<Posting> postings) {
        Transaction {
            postings = List.copyOf(postings);
            long sum = postings.stream().mapToLong(Posting::amount).sum();
            if (sum != 0) throw new IllegalArgumentException(id + " unbalanced by " + sum);
        }
    }

    private final Map<String, Long> balances = new TreeMap<>();

    void post(Transaction t) {
        for (Posting p : t.postings()) balances.merge(p.account(), p.amount(), Long::sum);
    }

    public static void main(String[] args) {
        DoubleEntry ledger = new DoubleEntry();
        ledger.post(new Transaction("t1", List.of(
                new Posting("cash", 10_000), new Posting("customer:alice", -10_000))));
        ledger.post(new Transaction("t2", List.of(               // alice pays bob 30.00, fee 0.50
                new Posting("customer:alice", 3_050),
                new Posting("customer:bob", -3_000),
                new Posting("revenue:fees", -50))));
        System.out.println(ledger.balances);
        System.out.println("sum of balances = "
                + ledger.balances.values().stream().mapToLong(Long::longValue).sum());
        try {
            new Transaction("t3", List.of(new Posting("cash", 100), new Posting("customer:bob", -99)));
        } catch (IllegalArgumentException e) {
            System.out.println("rejected: " + e.getMessage());
        }
    }
}

Output

{cash=10000, customer:alice=-6950, customer:bob=-3000, revenue:fees=-50}
sum of balances = 0
rejected: t3 unbalanced by 1

The sign convention here is debit positive, credit negative, so a customer liability account carries a negative balance (alice's account shows the bank owes her 69.50). Real ledgers fix the convention per account type; the zero-sum rule holds either way. A TreeMap keeps the printed order stable.

Example 6: an immutable journal and corrections by reversal

A journal is the append-only list of transactions; balances are derived from it. Entries are never edited or deleted, because auditors must see what was recorded and when. A mistake is corrected by a reversal, a new transaction with the opposite postings, followed by the correct one.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Journal {
    record Posting(String account, long amount) {}
    record Entry(long seq, String txId, String reason, List<Posting> postings) {
        Entry { postings = List.copyOf(postings); }
    }

    private final List<Entry> entries = new ArrayList<>();

    synchronized Entry append(String txId, String reason, List<Posting> postings) {
        Entry e = new Entry(entries.size() + 1, txId, reason, postings);
        entries.add(e);
        return e;
    }

    synchronized Entry reverse(long seq, String reason) {
        Entry original = entries.get((int) seq - 1);
        List<Posting> opposite = original.postings().stream()
                .map(p -> new Posting(p.account(), -p.amount())).toList();
        return append(original.txId() + "-rev", reason + " (reverses #" + seq + ")", opposite);
    }

    synchronized List<Entry> view() { return Collections.unmodifiableList(new ArrayList<>(entries)); }

    Map<String, Long> balances() {
        Map<String, Long> b = new TreeMap<>();
        for (Entry e : view()) for (Posting p : e.postings()) b.merge(p.account(), p.amount(), Long::sum);
        return b;
    }

    public static void main(String[] args) {
        Journal j = new Journal();
        j.append("t1", "transfer", List.of(new Posting("alice", 5_000), new Posting("bob", -5_000)));
        j.reverse(1, "wrong amount");
        j.append("t1-fix", "transfer", List.of(new Posting("alice", 500), new Posting("bob", -500)));
        j.view().forEach(System.out::println);
        System.out.println("balances = " + j.balances());
        try {
            j.view().clear();
        } catch (UnsupportedOperationException e) {
            System.out.println("journal view is read-only");
        }
    }
}

Output

Entry[seq=1, txId=t1, reason=transfer, postings=[Posting[account=alice, amount=5000], Posting[account=bob, amount=-5000]]]
Entry[seq=2, txId=t1-rev, reason=wrong amount (reverses #1), postings=[Posting[account=alice, amount=-5000], Posting[account=bob, amount=5000]]]
Entry[seq=3, txId=t1-fix, reason=transfer, postings=[Posting[account=alice, amount=500], Posting[account=bob, amount=-500]]]
balances = {alice=500, bob=-500}
journal view is read-only

The journal keeps all three entries, so the history shows the error, the reversal, and the fix. The sequence number gives a total order that replays produce identically. view returns a copy wrapped as unmodifiable, so callers cannot change the journal (see Immutability and Defensive Copying).

Example 7: a payment state machine with sealed types

A payment moves through states such as created, authorized, captured, refunded, and failed. Modelling each state as a record in a sealed interface (see Records and Sealed Types) lets a switch with patterns (see Pattern Matching) list every state without a default, so adding a state breaks compilation until every transition is handled. Illegal transitions throw; repeated events that are already applied return the current state, which makes the transition function idempotent.

Java

public class PaymentStateMachine {
    sealed interface State permits Created, Authorized, Captured, Refunded, Failed {}
    record Created(long amount) implements State {}
    record Authorized(long amount, String authCode) implements State {}
    record Captured(long amount) implements State {}
    record Refunded(long amount) implements State {}
    record Failed(String reason) implements State {}

    sealed interface Event permits Authorize, Capture, Refund, Decline {}
    record Authorize(String authCode) implements Event {}
    record Capture() implements Event {}
    record Refund() implements Event {}
    record Decline(String reason) implements Event {}

    static State apply(State s, Event e) {
        return switch (s) {
            case Created c -> switch (e) {
                case Authorize a -> new Authorized(c.amount(), a.authCode());
                case Decline d -> new Failed(d.reason());
                case Capture x -> throw illegal(s, e);
                case Refund x -> throw illegal(s, e);
            };
            case Authorized a -> switch (e) {
                case Capture x -> new Captured(a.amount());
                case Authorize x -> a;                       // duplicate event: no change
                case Decline x -> throw illegal(s, e);
                case Refund x -> throw illegal(s, e);
            };
            case Captured c -> switch (e) {
                case Refund x -> new Refunded(c.amount());
                case Capture x -> c;                         // duplicate event: no change
                default -> throw illegal(s, e);
            };
            case Refunded r -> {
                if (e instanceof Refund) yield r;
                throw illegal(s, e);
            }
            case Failed f -> throw illegal(s, e);
        };
    }

    static IllegalStateException illegal(State s, Event e) {
        return new IllegalStateException(s.getClass().getSimpleName() + " cannot handle "
                + e.getClass().getSimpleName());
    }

    public static void main(String[] args) {
        State s = new Created(2_000);
        Event[] events = {new Authorize("A1"), new Authorize("A1"), new Capture(),
                new Capture(), new Refund(), new Capture()};
        for (Event e : events) {
            try {
                s = apply(s, e);
                System.out.println(e.getClass().getSimpleName() + " -> " + s);
            } catch (IllegalStateException ex) {
                System.out.println(e.getClass().getSimpleName() + " rejected: " + ex.getMessage());
            }
        }
    }
}

Output

Authorize -> Authorized[amount=2000, authCode=A1]
Authorize -> Authorized[amount=2000, authCode=A1]
Capture -> Captured[amount=2000]
Capture -> Captured[amount=2000]
Refund -> Refunded[amount=2000]
Capture rejected: Refunded cannot handle Capture

The outer switch has no default, so the compiler proves every state is covered. The inner switch for Captured uses default to group the illegal events; that trades the exhaustiveness check for brevity, and the other inner switches list every event to keep it.

Example 8: reconciling two ledgers

Reconciliation compares two independent records of the same activity, for example the internal ledger and a bank or exchange statement, and lists every difference. Each side is indexed by transaction id; the result has three kinds of break: missing on one side, missing on the other, and amount mismatch.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Reconciliation {
    record Line(String txId, long amount) {}

    sealed interface Break permits MissingInBank, MissingInLedger, AmountMismatch {}
    record MissingInBank(Line ledger) implements Break {}
    record MissingInLedger(Line bank) implements Break {}
    record AmountMismatch(String txId, long ledger, long bank) implements Break {}

    static List<Break> reconcile(List<Line> ledger, List<Line> bank) {
        Map<String, Line> l = ledger.stream().collect(Collectors.toMap(Line::txId, Function.identity()));
        Map<String, Line> b = bank.stream().collect(Collectors.toMap(Line::txId, Function.identity()));
        TreeSet<String> ids = new TreeSet<>(l.keySet());
        ids.addAll(b.keySet());
        List<Break> breaks = new ArrayList<>();
        for (String id : ids) {
            Line x = l.get(id), y = b.get(id);
            if (y == null) breaks.add(new MissingInBank(x));
            else if (x == null) breaks.add(new MissingInLedger(y));
            else if (x.amount() != y.amount()) breaks.add(new AmountMismatch(id, x.amount(), y.amount()));
        }
        return breaks;
    }

    public static void main(String[] args) {
        List<Line> ledger = List.of(new Line("t1", 1_000), new Line("t2", 2_500),
                new Line("t3", 700), new Line("t5", 90));
        List<Line> bank = List.of(new Line("t1", 1_000), new Line("t2", 2_450),
                new Line("t4", 300), new Line("t5", 90));
        List<Break> breaks = reconcile(ledger, bank);
        breaks.forEach(System.out::println);

        Map<String, Long> counts = new TreeMap<>(breaks.stream()
                .collect(Collectors.groupingBy(br -> br.getClass().getSimpleName(), Collectors.counting())));
        System.out.println("breaks by type = " + counts);
        long ledgerTotal = ledger.stream().mapToLong(Line::amount).sum();
        long bankTotal = bank.stream().mapToLong(Line::amount).sum();
        System.out.println("totals ledger=" + ledgerTotal + " bank=" + bankTotal
                + " difference=" + (ledgerTotal - bankTotal));
    }
}

Output

AmountMismatch[txId=t2, ledger=2500, bank=2450]
MissingInBank[ledger=Line[txId=t3, amount=700]]
MissingInLedger[bank=Line[txId=t4, amount=300]]
breaks by type = {AmountMismatch=1, MissingInBank=1, MissingInLedger=1}
totals ledger=4290 bank=3840 difference=450

Comparing totals alone hides breaks that cancel out; line-level matching finds each one. Iterating over a sorted set of ids gives a stable report. Production reconciliation also matches on fuzzy keys (amount and date when ids differ), tolerates timing differences across a cut-off, and stores each break with its resolution.

Interview points

Idempotency key: client-generated id per logical request; the server stores the result and returns it on retry; reuse with a different body is rejected.
get then put on a ConcurrentHashMap is a race; use putIfAbsent or computeIfAbsent so one caller wins.
Store a CompletableFuture per key so concurrent retries wait for the first result instead of running the work.
"Exactly once" in practice is at-least-once delivery plus deduplication, with the dedup record and the effect committed atomically.
Double entry: postings in a transaction sum to zero; total of all balances is zero.
Journals are append-only; corrections are reversals plus new entries.
Sealed state types make transition handling exhaustive; duplicate events should be no-ops.
Reconciliation reports missing-on-each-side and amount mismatches per line, not only total differences.

Summary

A retry with the same idempotency key returns the stored result and causes no new effect.
A CyclicBarrier between check and act reproduces the double-charge race on every run.
putIfAbsent returns null to exactly one caller; remove(key, value) clears a failed attempt.
Deduplication keeps a set of processed message ids updated with the effect under one lock or transaction.
A transaction whose postings do not sum to zero is rejected at construction.
Balances are derived from the journal, so the journal is the source of truth.
Reconciliation iterates sorted ids from both sides and classifies each difference.