LOW LEVEL DESIGN · MACHINE CODING · HARD · 23 OF 42

Design a Payment Gateway: Idempotency and State Machine LLD in Java

The payments machine coding question, solved end to end: a payment as a strict state machine, idempotency keys so a retry storm charges once, routing to processors with failover on timeouts but never on declines, refunds that can never exceed the charge, a ledger, webhooks as observers, and a full Java 17 solution.

Patterns usedStateStrategyObserver

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 16

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 256 lines, with a small main() demo. Save it as PaymentGateway.java, then run javac PaymentGateway.java && java PaymentGateway.

import java.util.ArrayList;
import java.util.EnumSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/** A payment gateway: payments as a state machine, idempotent requests, processor failover, refunds. */
public class PaymentGateway {

    // ---------- the model ----------
    enum Method { CARD, UPI, NETBANKING }

    enum Status { CREATED, PROCESSING, SUCCEEDED, FAILED, PARTIALLY_REFUNDED, REFUNDED }

    /** The only legal moves. Anything else is a bug and throws. */
    static final Map<Status, Set<Status>> NEXT = Map.of(
            Status.CREATED, EnumSet.of(Status.PROCESSING),
            Status.PROCESSING, EnumSet.of(Status.SUCCEEDED, Status.FAILED),
            Status.SUCCEEDED, EnumSet.of(Status.PARTIALLY_REFUNDED, Status.REFUNDED),
            Status.PARTIALLY_REFUNDED, EnumSet.of(Status.PARTIALLY_REFUNDED, Status.REFUNDED),
            Status.FAILED, EnumSet.noneOf(Status.class),
            Status.REFUNDED, EnumSet.noneOf(Status.class));

    record Entry(String paymentId, String kind, long cents) {}

    static final class Payment {
        final String id;
        final String merchant;
        final long amountCents;
        final Method method;
        private Status status = Status.CREATED;
        private long refundedCents;
        private String processor;
        private final List<String> history = new ArrayList<>();

        Payment(String id, String merchant, long amountCents, Method method) {
            this.id = id;
            this.merchant = merchant;
            this.amountCents = amountCents;
            this.method = method;
            history.add(status.name());
        }

        synchronized void move(Status next) {
            if (!NEXT.get(status).contains(next)) {
                throw new IllegalStateException(id + ": cannot go " + status + " -> " + next);
            }
            status = next;
            history.add(next.name());
        }

        synchronized Status status() { return status; }

        synchronized List<String> history() { return List.copyOf(history); }
    }

    record Result(String paymentId, Status status, String processor) {}

    // ---------- processors and routing ----------
    interface Processor {
        String name();

        boolean supports(Method m);

        /** Returns true when the bank approves. Throws when the processor itself is down. */
        boolean charge(String paymentId, long cents);
    }

    static final class FakeProcessor implements Processor {
        private final String name;
        private final Set<Method> methods;
        volatile boolean down;
        final AtomicInteger charges = new AtomicInteger();

        FakeProcessor(String name, Set<Method> methods) {
            this.name = name;
            this.methods = methods;
        }

        @Override public String name() { return name; }

        @Override public boolean supports(Method m) { return methods.contains(m); }

        @Override
        public boolean charge(String paymentId, long cents) {
            if (down) throw new IllegalStateException(name + " timed out");
            charges.incrementAndGet();
            return cents <= 10_000_00;                 // the fake bank declines anything over 10,000.00
        }
    }

    interface RoutingStrategy { List<Processor> route(Payment p, List<Processor> all); }

    /** Processors that support the method, in priority order; the next one is the failover. */
    static final class PriorityRouting implements RoutingStrategy {
        @Override
        public List<Processor> route(Payment p, List<Processor> all) {
            List<Processor> out = new ArrayList<>();
            for (Processor x : all) if (x.supports(p.method)) out.add(x);
            return out;
        }
    }

    interface Webhook { void send(String merchant, String paymentId, Status status); }

    // ---------- the service ----------
    private final Map<String, CompletableFuture<Result>> idempotency = new ConcurrentHashMap<>();
    private final Map<String, Payment> payments = new ConcurrentHashMap<>();
    private final List<Entry> ledger = new CopyOnWriteArrayList<>();
    private final List<Webhook> webhooks = new CopyOnWriteArrayList<>();
    private final List<Processor> processors;
    private final RoutingStrategy routing;
    private final AtomicLong ids = new AtomicLong();

    PaymentGateway(List<Processor> processors, RoutingStrategy routing) {
        this.processors = List.copyOf(processors);
        this.routing = routing;
    }

    void subscribe(Webhook w) { webhooks.add(w); }

    /**
     * Same merchant + idempotency key = same payment, even if the request arrives ten times at once.
     * The first caller does the work; everyone else waits for and returns the same result.
     */
    Result pay(String merchant, String key, long cents, Method method) {
        CompletableFuture<Result> mine = new CompletableFuture<>();
        CompletableFuture<Result> existing = idempotency.putIfAbsent(merchant + ":" + key, mine);
        if (existing != null) return existing.join();
        try {
            mine.complete(process(merchant, cents, method));
        } catch (RuntimeException e) {
            mine.completeExceptionally(e);
            throw e;
        }
        return mine.join();
    }

    private Result process(String merchant, long cents, Method method) {
        if (cents <= 0) throw new IllegalArgumentException("amount must be positive");
        Payment p = new Payment("pay_" + ids.incrementAndGet(), merchant, cents, method);
        payments.put(p.id, p);
        p.move(Status.PROCESSING);
        for (Processor proc : routing.route(p, processors)) {
            try {
                boolean ok = proc.charge(p.id, cents);
                synchronized (p) { p.processor = proc.name(); }
                if (ok) {
                    p.move(Status.SUCCEEDED);
                    ledger.add(new Entry(p.id, "charge", cents));
                } else {
                    p.move(Status.FAILED);                 // a decline is final: do not try another processor
                }
                publish(p);
                return new Result(p.id, p.status(), proc.name());
            } catch (IllegalStateException down) {
                // processor unreachable: fail over to the next one
            }
        }
        p.move(Status.FAILED);
        publish(p);
        return new Result(p.id, Status.FAILED, "none");
    }

    /** Refunds never exceed what was charged, even when two refund calls race. */
    Status refund(String paymentId, long cents) {
        Payment p = payments.get(paymentId);
        if (p == null) throw new IllegalArgumentException("no payment " + paymentId);
        synchronized (p) {
            long left = p.amountCents - p.refundedCents;
            if (cents <= 0 || cents > left) {
                throw new IllegalArgumentException("refund " + cents + " exceeds remaining " + left);
            }
            p.refundedCents += cents;
            p.move(p.refundedCents == p.amountCents ? Status.REFUNDED : Status.PARTIALLY_REFUNDED);
            ledger.add(new Entry(p.id, "refund", -cents));
        }
        publish(p);
        return p.status();
    }

    long balance(String paymentId) {
        long sum = 0;
        for (Entry e : ledger) if (e.paymentId().equals(paymentId)) sum += e.cents();
        return sum;
    }

    private void publish(Payment p) {
        Status s = p.status();
        for (Webhook w : webhooks) w.send(p.merchant, p.id, s);
    }

    // ---------- demo ----------
    public static void main(String[] args) throws InterruptedException {
        FakeProcessor alpha = new FakeProcessor("alpha", EnumSet.of(Method.CARD, Method.UPI));
        FakeProcessor beta = new FakeProcessor("beta", EnumSet.allOf(Method.class));
        PaymentGateway gw = new PaymentGateway(List.of(alpha, beta), new PriorityRouting());
        List<String> events = new CopyOnWriteArrayList<>();
        gw.subscribe((m, id, s) -> events.add(id + " " + s));

        Result r1 = gw.pay("shop", "order-1", 2_499_00, Method.CARD);
        System.out.println("order-1: " + r1);

        // A retry storm: the same request 10 times at once is charged exactly once.
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        Set<String> seen = ConcurrentHashMap.newKeySet();
        int before = alpha.charges.get();
        for (int i = 0; i < 10; i++) {
            pool.submit(() -> {
                go.await();
                seen.add(gw.pay("shop", "order-2", 799_00, Method.UPI).paymentId());
                return null;
            });
        }
        go.countDown();
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);
        int charged = alpha.charges.get() - before;
        System.out.println("order-2 sent 10 times: payment ids " + seen + ", charged " + charged + " time");
        if (seen.size() != 1 || charged != 1) throw new AssertionError("double charge");

        alpha.down = true;
        Result r3 = gw.pay("shop", "order-3", 1_200_00, Method.CARD);
        System.out.println("alpha down, order-3 failed over: " + r3.processor() + " " + r3.status());
        alpha.down = false;

        Result r4 = gw.pay("shop", "order-4", 15_000_00, Method.CARD);
        System.out.println("order-4 over the bank limit: " + r4.status() + " (no retry on a decline)");

        System.out.println("refund 1,000.00: " + gw.refund(r1.paymentId(), 1_000_00));
        try {
            gw.refund(r1.paymentId(), 2_000_00);
        } catch (IllegalArgumentException e) {
            System.out.println("refund 2,000.00: " + e.getMessage());
        }
        System.out.println("refund the rest: " + gw.refund(r1.paymentId(), 1_499_00)
                + ", ledger balance " + gw.balance(r1.paymentId()));
        try {
            gw.payments.get(r4.paymentId()).move(Status.SUCCEEDED);
        } catch (IllegalStateException e) {
            System.out.println("illegal move: " + e.getMessage());
        }
        System.out.println("history of " + r1.paymentId() + ": " + gw.payments.get(r1.paymentId()).history());
        System.out.println("webhooks sent: " + events.size());
    }
}

Notes

Requirements

Fix the scope. A merchant charges an amount by card, UPI or net banking. We route the charge to a processor that supports the method and fail over if that processor is down. Merchants can refund fully or in parts and get a notification on every change. Two rules matter more than everything else: a retried request must never charge twice, and refunds must never exceed what was charged. Card verification and currency exchange are out of scope.

Requirements
  • merchant charges an amount
  • by card, UPI or net banking
  • route to a processor that
  • supports the method
  • fail over if a processor is down
  • full and partial refunds
  • tell the merchant on change
  • a retry must never charge twice
  • refunds never exceed the charge
  • out of scope: 3-D Secure, FX

State machine

Start with the payment's life. Created moves to processing when we call a processor. Processing ends as succeeded or failed, and failed is final. A succeeded payment can be partially refunded, possibly several times, and finally fully refunded. Write these legal moves down as a table from each status to the set of next statuses. Any move not in the table throws, so a bug can never mark a failed payment as paid.

In code, the table is a map from status to an enum set, and one synchronized move method checks it before changing anything. The method also appends to a history list, so support staff can see exactly how a payment got where it is. Putting the rules in data instead of scattered if statements means adding a new state, like disputed, is one line in the table.

Payment states
  • CREATED -> PROCESSING
  • PROCESSING -> SUCCEEDED
  • -> FAILED (final)
  • SUCCEEDED -> PARTIALLY_REFUNDED
  • -> REFUNDED
  • PARTIALLY_REFUNDED
  • -> PARTIALLY_REFUNDED
  • -> REFUNDED (final)
  • anything else: throw
Payment.move()
static final Map<Status, Set<Status>>
  NEXT = Map.of(CREATED,
    EnumSet.of(PROCESSING), ...);

synchronized void move(Status next) {
  if (!NEXT.get(status).contains(next))
    throw new IllegalStateException(..)
  status = next;
  history.add(next.name());
}

Idempotency

Now the most important idea. A merchant sends a charge, we process it, and the network drops our reply. The merchant cannot tell whether it worked, so it retries. Without protection the customer pays twice. The fix is an idempotency key: the merchant sends its own unique id, like its order number, with every request. We remember the key with its result, and any retry with the same key gets the original result back instead of a new charge.

Retries can arrive at the same moment, so a plain check-then-insert is not enough. We store a future, not a result. Each request creates an empty future and calls put-if-absent on a concurrent map. Exactly one request wins and does the real work; the other nine find the winner's future and wait on it. When the work finishes, all ten return the same payment id, and the processor is called exactly once.

Why idempotency keys
  • merchant sends pay(order-2)
  • network drops our response
  • merchant retries pay(order-2)
  • without a key: charged twice
  • with a key: same payment back
  • key = merchant + their order id
  • stored with the result
  • for 24 hours or more
pay(merchant, key, ...)
var mine = new CompletableFuture<>();
var old = idem.putIfAbsent(
            merchant + ":" + key, mine);
if (old != null) return old.join();
try {
  mine.complete(process(...));
} catch (RuntimeException e) {
  mine.completeExceptionally(e);
  throw e;
}
return mine.join();

Strategy: routing

Which processor handles a payment is a business choice: the cheapest fee, the best success rate for this bank, a rule for a big merchant. So routing is a strategy that returns an ordered list of processors that support the method. The first is the primary, the rest are failovers. Each processor is behind a small interface with a name, the methods it supports and a charge call, which also makes them easy to fake in tests.

RoutingStrategy
interface RoutingStrategy {
  List<Processor> route(Payment p,
      List<Processor> all);
}
PriorityRouting: supports method,
  in priority order
later: cheapest fee, best success
  rate per bank, per-merchant rules

Flow: charge

Here is the rule that separates a good answer from a dangerous one. If a processor is unreachable, try the next one. But if the bank answers declined, stop: the customer's card said no, and retrying elsewhere looks like fraud and can annoy the customer. Mark the payment failed. And if a call times out after it may have reached the bank, do not blindly retry; ask the processor for the outcome later.

The failover rule
  • processor unreachable or 5xx:
  • try the next processor
  • bank says declined:
  • stop, mark FAILED
  • another route would just
  • annoy the customer or look
  • like card testing
  • unknown result after timeout:
  • ask the processor later

Ledger

Every movement of money becomes an entry in an append-only ledger: plus the amount for a charge, minus for each refund. You never edit or delete an entry; a mistake is fixed with a new opposite entry. The balance of a payment is just the sum of its entries, so the status and the money can always be checked against each other. Amounts are whole paise in a long, never a double.

Ledger
record Entry(String paymentId,
             String kind, long cents)

charge 2,499.00  -> +249900
refund 1,000.00  -> -100000
refund 1,499.00  -> -149900
balance                 0

append-only: the history is the
  source of truth for money

Refunds

Refunds have their own race. Two support agents refund the same order at the same moment, each for the full amount. If each checks the remaining amount and then subtracts, both pass and we pay back double. So the check, the update, the state change and the ledger entry happen together inside one lock on that payment. The second agent sees nothing left and gets a clear error.

refund(paymentId, cents)
synchronized (p) {
  long left = p.amount - p.refunded;
  if (cents <= 0 || cents > left)
    throw: exceeds remaining
  p.refunded += cents;
  p.move(refunded == amount
         ? REFUNDED
         : PARTIALLY_REFUNDED);
  ledger.add(refund entry);
}

Observer: webhooks

Merchants learn about changes through webhooks, which are just the Observer pattern over the network. After every status change we publish an event to each subscriber. In a real system the body is signed so the merchant knows it came from us, failed deliveries are retried with backoff for a day, and each event carries an id so the merchant can safely ignore duplicates. The merchant can also poll the payment at any time.

Webhooks
  • observer list of Webhook
  • sent after every status change
  • real systems:
  • sign the body (HMAC)
  • retry with backoff for a day
  • include an event id so the
  • merchant can ignore repeats
  • the merchant can always poll
  • GET /payments/{id} too

Concurrency

Check every shared field. Idempotency is a concurrent map of futures. Status changes go through one synchronized method, and a refund does its check and update under the same payment lock. The ledger here is a copy-on-write list; in production it is a database table. Calls to processors happen with no lock held, because a slow bank must never block other payments.

Thread safety checklist
  • idempotency: ConcurrentHashMap
  • of CompletableFuture
  • payment state: synchronized move
  • refund: check + update in one
  • lock on the payment
  • ledger: CopyOnWriteArrayList
  • (a table in real life)
  • processor calls: no lock held
  • ids: AtomicLong

Extensibility

Now the follow-ups. Card verification adds a requires-action state between processing and success. Authorise now and capture later adds an authorised state. Chargebacks add a disputed state. A new payment method is a new processor class, and smarter routing is a new strategy. For durability, the idempotency record, the payment and the ledger entry are written in one database transaction, so a crash can never leave them disagreeing.

Extension points
  • 3-D Secure: REQUIRES_ACTION
  • state between PROCESSING
  • auth then capture: AUTHORIZED
  • state, capture within 7 days
  • disputes: DISPUTED state
  • new method: a new Processor
  • smart routing: a new strategy
  • durability: idempotency keys and
  • ledger in one DB transaction

Testing

The full code is below the player. The demo charges an order, then sends the same request ten times from ten threads and shows one payment id and one processor charge. It takes the first processor down and shows failover, sends an amount the bank declines and shows no retry, refunds in two parts while rejecting a refund that is too large, and prints the payment's full history.

Run it
order-1: pay_1 SUCCEEDED via alpha
order-2 sent 10 times: [pay_2],
  charged 1 time
alpha down: order-3 via beta
order-4 over limit: FAILED
refund 2,000.00: exceeds remaining
refund the rest: REFUNDED, balance 0
illegal: cannot go FAILED->SUCCEEDED
history: CREATED, PROCESSING,
  SUCCEEDED, PARTIALLY_REFUNDED,
  REFUNDED

Say it like this

Here is the short version to say out loud. A payment is a state machine with a table of legal moves. Every request carries an idempotency key, and one put-if-absent of a future means even a retry storm charges once. Routing fails over on timeouts but never on declines. Refunds lock the payment so they can never exceed the charge, and every movement of money is an entry in an append-only ledger.

In the interview
  • "A Payment is a state machine
  • with a table of legal moves.
  • Requests carry idempotency
  • keys; one putIfAbsent of a
  • Future means a retry storm
  • charges once. Routing fails over
  • on timeouts, never on declines.
  • Refunds lock the payment, and
  • every movement is in a ledger."

Interview questions

How do you stop a retried request from charging the customer twice?

Require an idempotency key per request, scoped to the merchant. The gateway stores the key with a future for the result using putIfAbsent; the first request does the work and every retry, even a concurrent one, waits for and returns the same result.

Why store a CompletableFuture instead of the finished result?

Retries can arrive while the first request is still running. If only finished results were stored, a concurrent retry would find nothing and charge again. Storing the future at the start lets later requests wait on the work in progress.

When should the gateway try another processor?

Only when the processor is unreachable or errors before reaching the bank. A decline is the bank saying no, so retrying elsewhere is wrong and looks like card testing. An ambiguous timeout is resolved by asking the processor for the outcome, not by charging again.

Why use a state machine for payments?

A payment has a small set of legal moves, and money bugs come from illegal ones, such as marking a failed payment as paid. A table of allowed transitions checked in one guarded method makes every illegal move throw.

How do you stop two refunds from paying back more than was charged?

Do the check of the remaining amount, the update, the state change and the ledger entry together under one lock on that payment, or in one database transaction with a row lock. The second refund then sees the reduced remaining amount.

What is the ledger for, if the payment already has a status?

The ledger is an append-only list of money movements: charges positive, refunds negative. It is the audit trail, it reconciles against processor reports, and the balance of a payment must always match its status.

How are merchants told about payment changes?

Webhooks, which are the Observer pattern over HTTP. Each event is signed, carries an event id so duplicates can be ignored, and failed deliveries are retried with backoff. Merchants can also poll the payment by id.

What changes when this runs on many servers?

The idempotency key becomes a unique row in the database, inserted in the same transaction as the payment and its ledger entry, so two servers racing on one key cannot both create a payment.