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

Design a Stock Brokerage System: LLD in Java

The trading app machine coding question, solved end to end: accounts with free and blocked cash and shares, market and limit orders, pre-trade checks, an order book with price-time priority, a matching engine with partial fills, order states and cancel, settlement, portfolio and P&L, Observer for trades and watchlists, one matching thread per symbol, stop-loss as an extension, and a full Java 17 solution.

Patterns usedObserver

  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 / 21

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, 555 lines, with a small main() demo. Save it as StockBrokerage.java, then run javac StockBrokerage.java && java StockBrokerage.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Supplier;

/** A stock brokerage: pre-trade checks, a price-time order book, one matching thread per symbol. */
public class StockBrokerage {

    // ---------- the model ----------
    enum Side { BUY, SELL }

    enum OrderType { MARKET, LIMIT }

    enum Status { OPEN, PARTIALLY_FILLED, FILLED, CANCELLED, REJECTED }

    /** One fill between a buy order and a sell order, always at the resting order's price. */
    record Trade(long id, String symbol, long buyOrder, long sellOrder, String buyer, String seller,
                 long qty, long pricePaise) {}

    /** Mutable, but only ever changed on its own symbol's matching thread. */
    static final class Order {
        final long id;
        final String account;
        final String symbol;
        final Side side;
        final OrderType type;
        final long qty;
        final long limitPaise;          // 0 for a market order
        long filled;
        long tradedPaise;               // sum of qty x price over all fills, for the average price
        long reservedCash;              // buy orders: cash still blocked for this order
        Status status = Status.OPEN;
        String reason = "";

        Order(long id, String account, String symbol, Side side, OrderType type, long qty, long limitPaise) {
            this.id = id;
            this.account = account;
            this.symbol = symbol;
            this.side = side;
            this.type = type;
            this.qty = qty;
            this.limitPaise = limitPaise;
        }

        long remaining() { return qty - filled; }

        boolean isLive() { return status == Status.OPEN || status == Status.PARTIALLY_FILLED; }
    }

    /** Cash and holdings. Free can be spent; blocked is promised to open orders and cannot be used twice. */
    static final class Account {
        final String id;
        private long cash;
        private long blockedCash;
        private final Map<String, Long> shares = new HashMap<>();
        private final Map<String, Long> blockedShares = new HashMap<>();
        private final Map<String, Long> costBasis = new HashMap<>();
        private long realizedPnl;

        Account(String id, long cashPaise) {
            this.id = id;
            this.cash = cashPaise;
        }

        /** Shares that arrive from the depository before trading starts. */
        synchronized Account grant(String symbol, long qty, long costPaise) {
            shares.merge(symbol, qty, Long::sum);
            costBasis.merge(symbol, costPaise, Long::sum);
            return this;
        }

        /** The pre-trade check and the reservation are one atomic step. */
        synchronized boolean tryBlockCash(long paise) {
            if (paise > cash) return false;
            cash -= paise;
            blockedCash += paise;
            return true;
        }

        synchronized void releaseCash(long paise) {
            blockedCash -= paise;
            cash += paise;
        }

        synchronized boolean tryBlockShares(String symbol, long qty) {
            long free = shares.getOrDefault(symbol, 0L);
            if (qty > free) return false;
            shares.put(symbol, free - qty);
            blockedShares.merge(symbol, qty, Long::sum);
            return true;
        }

        synchronized void releaseShares(String symbol, long qty) {
            blockedShares.merge(symbol, -qty, Long::sum);
            shares.merge(symbol, qty, Long::sum);
        }

        /** Buyer side of a trade: blocked cash leaves, shares arrive at their cost. */
        synchronized void settleBuy(String symbol, long qty, long paise) {
            blockedCash -= paise;
            shares.merge(symbol, qty, Long::sum);
            costBasis.merge(symbol, paise, Long::sum);
        }

        /** Seller side: blocked shares leave, cash arrives, profit or loss is realised at average cost. */
        synchronized void settleSell(String symbol, long qty, long paise) {
            long held = totalShares(symbol);
            long cost = costBasis.getOrDefault(symbol, 0L);
            long costOut = cost * qty / held;
            costBasis.put(symbol, cost - costOut);
            realizedPnl += paise - costOut;
            blockedShares.merge(symbol, -qty, Long::sum);
            cash += paise;
        }

        synchronized long totalShares(String symbol) {
            return shares.getOrDefault(symbol, 0L) + blockedShares.getOrDefault(symbol, 0L);
        }

        synchronized long freeShares(String symbol) { return shares.getOrDefault(symbol, 0L); }

        synchronized long blockedShares(String symbol) { return blockedShares.getOrDefault(symbol, 0L); }

        synchronized long freeCash() { return cash; }

        synchronized long blockedCash() { return blockedCash; }

        synchronized long totalCash() { return cash + blockedCash; }

        synchronized long cost(String symbol) { return costBasis.getOrDefault(symbol, 0L); }

        synchronized long realized() { return realizedPnl; }
    }

    /** Price levels in TreeMaps, a FIFO queue per level: best price first, then earliest order first. */
    static final class OrderBook {
        final NavigableMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(Comparator.reverseOrder());
        final NavigableMap<Long, ArrayDeque<Order>> asks = new TreeMap<>();

        NavigableMap<Long, ArrayDeque<Order>> own(Side s) { return s == Side.BUY ? bids : asks; }

        NavigableMap<Long, ArrayDeque<Order>> opposite(Side s) { return s == Side.BUY ? asks : bids; }

        void rest(Order o) {
            own(o.side).computeIfAbsent(o.limitPaise, p -> new ArrayDeque<>()).addLast(o);
        }

        void remove(Order o) {
            ArrayDeque<Order> level = own(o.side).get(o.limitPaise);
            if (level == null) return;
            level.remove(o);
            if (level.isEmpty()) own(o.side).remove(o.limitPaise);
        }

        /** Cash a market buy of qty would spend right now, for the part the book can fill. */
        long sweepCost(long qty) {
            long left = qty;
            long cost = 0;
            for (Map.Entry<Long, ArrayDeque<Order>> level : asks.entrySet()) {
                for (Order o : level.getValue()) {
                    long q = Math.min(left, o.remaining());
                    cost += q * level.getKey();
                    left -= q;
                    if (left == 0) return cost;
                }
            }
            return cost;
        }

        List<String> depth() {
            List<String> out = new ArrayList<>();
            asks.descendingMap().forEach((p, q) -> out.add(line("ASK", p, q)));
            out.add("    ----------------");
            bids.forEach((p, q) -> out.add(line("BID", p, q)));
            return out;
        }

        private static String line(String side, long price, ArrayDeque<Order> level) {
            long sum = 0;
            for (Order o : level) sum += o.remaining();
            return "    " + side + " " + money(price) + " x " + sum + " (" + level.size()
                    + (level.size() == 1 ? " order)" : " orders)");
        }
    }

    /** Observer: trade prints, price alerts, watchlists, a market data feed. */
    interface MarketListener { void onTrade(Trade t); }

    /** A watchlist is an observer that filters by symbol and speaks only when the price moves. */
    static final class Watchlist implements MarketListener {
        final String owner;
        final Set<String> symbols = ConcurrentHashMap.newKeySet();
        private final Map<String, Long> last = new ConcurrentHashMap<>();

        Watchlist(String owner, String... symbols) {
            this.owner = owner;
            this.symbols.addAll(List.of(symbols));
        }

        @Override
        public void onTrade(Trade t) {
            if (!symbols.contains(t.symbol())) return;
            Long before = last.put(t.symbol(), t.pricePaise());
            if (before == null || before != t.pricePaise()) {
                System.out.println("    [" + owner + " watchlist] " + t.symbol() + " now "
                        + money(t.pricePaise()));
            }
        }
    }

    // ---------- the matching engine: one per symbol, one thread each ----------
    /** Owns one symbol's book. Every change runs on its single thread, so the book needs no locks. */
    final class SymbolEngine {
        final String symbol;
        final OrderBook book = new OrderBook();
        final ExecutorService thread;
        volatile long lastPricePaise;

        SymbolEngine(String symbol) {
            this.symbol = symbol;
            this.thread = Executors.newSingleThreadExecutor(r -> {
                Thread t = new Thread(r, "match-" + symbol);
                t.setDaemon(true);
                return t;
            });
        }

        <T> CompletableFuture<T> run(Supplier<T> work) { return CompletableFuture.supplyAsync(work, thread); }

        /** Check and block, match against the other side, then rest a limit remainder in the book. */
        Order accept(Order o) {
            Account a = accounts.get(o.account);
            if (o.side == Side.BUY) {
                long need = o.type == OrderType.LIMIT ? o.limitPaise * o.qty : book.sweepCost(o.qty);
                if (need == 0) return reject(o, "no sellers in the book");
                if (!a.tryBlockCash(need)) return reject(o, "insufficient funds: needs " + money(need));
                o.reservedCash = need;
            } else {
                if (o.type == OrderType.MARKET && book.bids.isEmpty()) return reject(o, "no buyers");
                if (!a.tryBlockShares(symbol, o.qty)) {
                    return reject(o, "insufficient shares: " + a.freeShares(symbol) + " free");
                }
            }
            match(o);
            if (o.remaining() > 0) {
                if (o.type == OrderType.LIMIT) book.rest(o);
                else finish(o, Status.CANCELLED, "market remainder cancelled");
            }
            return o;
        }

        boolean cancel(Order o) {
            if (!o.isLive()) return false;
            book.remove(o);
            finish(o, Status.CANCELLED, "cancelled by the user");
            return true;
        }

        private void match(Order in) {
            NavigableMap<Long, ArrayDeque<Order>> other = book.opposite(in.side);
            while (in.remaining() > 0 && !other.isEmpty()) {
                long price = other.firstKey();
                boolean crosses = in.side == Side.BUY ? price <= in.limitPaise : price >= in.limitPaise;
                if (in.type == OrderType.LIMIT && !crosses) break;
                ArrayDeque<Order> level = other.get(price);
                Order resting = level.peekFirst();
                long qty = Math.min(in.remaining(), resting.remaining());
                if (in.side == Side.BUY) settle(in, resting, qty, price);
                else settle(resting, in, qty, price);
                if (resting.remaining() == 0) level.pollFirst();
                if (level.isEmpty()) other.remove(price);
            }
        }

        /** Move cash and shares between both accounts, update both orders, tell the listeners. */
        private void settle(Order buy, Order sell, long qty, long price) {
            long paise = qty * price;
            accounts.get(buy.account).settleBuy(symbol, qty, paise);
            buy.reservedCash -= paise;
            accounts.get(sell.account).settleSell(symbol, qty, paise);
            fill(buy, qty, paise);
            fill(sell, qty, paise);
            lastPricePaise = price;
            Trade t = new Trade(tradeIds.incrementAndGet(), symbol, buy.id, sell.id, buy.account,
                    sell.account, qty, price);
            for (MarketListener l : listeners) l.onTrade(t);
        }

        private void fill(Order o, long qty, long paise) {
            o.filled += qty;
            o.tradedPaise += paise;
            if (o.remaining() == 0) finish(o, Status.FILLED, "");
            else o.status = Status.PARTIALLY_FILLED;
        }

        /** A final state: give back whatever this order still has blocked. */
        private void finish(Order o, Status status, String reason) {
            Account a = accounts.get(o.account);
            if (o.side == Side.BUY) {
                a.releaseCash(o.reservedCash);
                o.reservedCash = 0;
            } else {
                a.releaseShares(symbol, o.remaining());
            }
            o.status = status;
            o.reason = reason;
        }

        private Order reject(Order o, String reason) {
            o.status = Status.REJECTED;
            o.reason = reason;
            return o;
        }
    }

    // ---------- the brokerage facade ----------
    private final Map<String, Account> accounts = new ConcurrentHashMap<>();
    private final Map<String, SymbolEngine> engines = new ConcurrentHashMap<>();
    private final Map<Long, Order> orders = new ConcurrentHashMap<>();
    private final List<MarketListener> listeners = new CopyOnWriteArrayList<>();
    private final AtomicLong orderIds = new AtomicLong();
    private final AtomicLong tradeIds = new AtomicLong();

    Account open(String id, long cashPaise) {
        Account a = new Account(id, cashPaise);
        if (accounts.putIfAbsent(id, a) != null) throw new IllegalArgumentException("account exists: " + id);
        return a;
    }

    void list(String symbol) { engines.putIfAbsent(symbol, new SymbolEngine(symbol)); }

    void subscribe(MarketListener l) { listeners.add(l); }

    /** Validate the shape here; the money checks run on the symbol's thread, next to the book. */
    CompletableFuture<Order> place(String accountId, String symbol, Side side, OrderType type, long qty,
                                   long limitPaise) {
        if (!accounts.containsKey(accountId)) throw new IllegalArgumentException("no account " + accountId);
        SymbolEngine e = engines.get(symbol);
        if (e == null) throw new IllegalArgumentException("not listed: " + symbol);
        if (qty <= 0) throw new IllegalArgumentException("quantity must be positive");
        if (type == OrderType.LIMIT && limitPaise <= 0) throw new IllegalArgumentException("price needed");
        Order o = new Order(orderIds.incrementAndGet(), accountId, symbol, side, type, qty,
                type == OrderType.LIMIT ? limitPaise : 0);
        orders.put(o.id, o);
        return e.run(() -> e.accept(o));
    }

    /** Cancel goes through the same queue as orders, so it can never overtake its own order. */
    CompletableFuture<Boolean> cancel(String accountId, long orderId) {
        Order o = orders.get(orderId);
        if (o == null || !o.account.equals(accountId)) {
            throw new IllegalArgumentException("no order " + orderId);
        }
        SymbolEngine e = engines.get(o.symbol);
        return e.run(() -> e.cancel(o));
    }

    List<String> portfolio(String accountId) {
        Account a = accounts.get(accountId);
        List<String> out = new ArrayList<>();
        out.add("  " + accountId + ": cash " + money(a.freeCash()) + " free, " + money(a.blockedCash())
                + " blocked, realised P&L " + money(a.realized()));
        for (String s : new TreeSet<>(engines.keySet())) {
            long held = a.totalShares(s);
            if (held == 0) continue;
            long cost = a.cost(s);
            long last = engines.get(s).lastPricePaise;
            long value = held * last;
            out.add("    " + s + " " + held + " shares, avg " + money(cost / held) + ", last " + money(last)
                    + ", value " + money(value) + ", unrealised " + money(value - cost));
        }
        return out;
    }

    long totalCash() {
        long sum = 0;
        for (Account a : accounts.values()) sum += a.totalCash();
        return sum;
    }

    long totalShares(String symbol) {
        long sum = 0;
        for (Account a : accounts.values()) sum += a.totalShares(symbol);
        return sum;
    }

    /** Blocked cash and shares must equal exactly what the live orders still need. */
    boolean reservationsMatch() {
        Map<String, Long> cashNeeded = new HashMap<>();
        Map<String, Long> sharesNeeded = new HashMap<>();
        for (Order o : orders.values()) {
            if (!o.isLive()) continue;
            if (o.side == Side.BUY) cashNeeded.merge(o.account, o.reservedCash, Long::sum);
            else sharesNeeded.merge(o.account + "|" + o.symbol, o.remaining(), Long::sum);
        }
        for (Account a : accounts.values()) {
            if (a.blockedCash() != cashNeeded.getOrDefault(a.id, 0L)) return false;
            for (String s : engines.keySet()) {
                if (a.blockedShares(s) != sharesNeeded.getOrDefault(a.id + "|" + s, 0L)) return false;
            }
        }
        return true;
    }

    void shutdown() throws InterruptedException {
        for (SymbolEngine e : engines.values()) {
            e.thread.shutdown();
            e.thread.awaitTermination(5, TimeUnit.SECONDS);
        }
    }

    static String money(long paise) {
        String sign = paise < 0 ? "-" : "";
        long p = Math.abs(paise);
        return String.format("%s%,d.%02d", sign, p / 100, p % 100);
    }

    static Order show(CompletableFuture<Order> f) {
        Order o = f.join();
        String price = o.type == OrderType.LIMIT ? " @ " + money(o.limitPaise) : "";
        String avg = o.filled > 0 ? ", avg " + money(o.tradedPaise / o.filled) : "";
        String why = o.reason.isEmpty() ? "" : " (" + o.reason + ")";
        System.out.println("  #" + o.id + " " + o.account + " " + o.side + " " + o.type + " " + o.qty + price
                + " -> " + o.status + " " + o.filled + "/" + o.qty + avg + why);
        return o;
    }

    /** Even a read of the book is a task on the symbol's thread, so it never sees a half-done match. */
    void printBook(String symbol) {
        SymbolEngine e = engines.get(symbol);
        e.run(e.book::depth).join().forEach(System.out::println);
    }

    // ---------- demo ----------
    public static void main(String[] args) throws Exception {
        StockBrokerage b = new StockBrokerage();
        b.list("ACME");
        b.list("ZETA");
        b.open("MAKER", 0).grant("ACME", 500, 500L * 95_00).grant("ZETA", 1_000, 1_000L * 45_00);
        b.open("TRADER", 0).grant("ACME", 50, 50L * 98_00);
        b.open("FUND", 60_000_00);
        b.open("RETAIL", 10_000_00);
        b.open("SMALL", 1_000_00);
        b.open("T0", 25_000_00);
        b.open("T1", 25_000_00);
        b.open("T2", 1_000_00);
        b.open("T3", 1_000_00);
        b.subscribe(t -> {
            if (t.symbol().equals("ACME")) {
                System.out.println("    trade " + t.id() + ": " + t.buyer() + " buys " + t.qty() + " from "
                        + t.seller() + " @ " + money(t.pricePaise()));
            }
        });
        b.subscribe(new Watchlist("FUND", "ACME"));
        long cash0 = b.totalCash();
        long acme0 = b.totalShares("ACME");
        long zeta0 = b.totalShares("ZETA");

        System.out.println("1) Sellers build the ask side (same price: earlier order first)");
        show(b.place("MAKER", "ACME", Side.SELL, OrderType.LIMIT, 100, 101_00));
        show(b.place("MAKER", "ACME", Side.SELL, OrderType.LIMIT, 100, 102_00));
        show(b.place("MAKER", "ACME", Side.SELL, OrderType.LIMIT, 200, 103_00));
        Order traderAsk = show(b.place("TRADER", "ACME", Side.SELL, OrderType.LIMIT, 50, 101_00));
        b.printBook("ACME");

        System.out.println("2) Limit buy 120 @ 101.00: takes MAKER's 100 first, then 20 of TRADER's 50");
        show(b.place("FUND", "ACME", Side.BUY, OrderType.LIMIT, 120, 101_00));
        System.out.println("  TRADER's ask is now " + traderAsk.status + " " + traderAsk.filled + "/50");

        System.out.println("3) A bid that does not cross rests in the book");
        Order retailBid = show(b.place("RETAIL", "ACME", Side.BUY, OrderType.LIMIT, 50, 99_00));
        b.printBook("ACME");

        System.out.println("4) Market buy 250 sweeps three price levels");
        show(b.place("FUND", "ACME", Side.BUY, OrderType.MARKET, 250, 0));
        b.printBook("ACME");

        System.out.println("5) Market sell 30 hits the best bid: a partial fill for RETAIL");
        show(b.place("FUND", "ACME", Side.SELL, OrderType.MARKET, 30, 0));
        System.out.println("  RETAIL's bid is now " + retailBid.status + " " + retailBid.filled + "/50");

        System.out.println("6) Cancels");
        long freeBefore = b.accounts.get("RETAIL").freeCash();
        System.out.println("  cancel RETAIL #" + retailBid.id + ": " + b.cancel("RETAIL", retailBid.id).join()
                + ", now " + retailBid.status + ", released " + money(b.accounts.get("RETAIL").freeCash()
                - freeBefore));
        System.out.println("  cancel it again: " + b.cancel("RETAIL", retailBid.id).join() + " (already "
                + retailBid.status + ")");
        b.printBook("ACME");

        System.out.println("7) Pre-trade checks reject what the account cannot pay for");
        show(b.place("SMALL", "ACME", Side.BUY, OrderType.LIMIT, 100, 103_00));
        show(b.place("SMALL", "ACME", Side.SELL, OrderType.LIMIT, 10, 103_00));
        show(b.place("MAKER", "ACME", Side.SELL, OrderType.LIMIT, 150, 104_00));

        System.out.println("8) Four client threads on two symbols at once");
        show(b.place("MAKER", "ZETA", Side.SELL, OrderType.LIMIT, 1_000, 50_00));
        ExecutorService clients = Executors.newFixedThreadPool(4);
        List<Future<?>> jobs = new ArrayList<>();
        for (String acct : List.of("T0", "T1")) {
            jobs.add(clients.submit(() -> {
                for (int k = 0; k < 25; k++) {
                    b.place(acct, "ZETA", Side.BUY, OrderType.LIMIT, 20, 50_00).join();
                }
                return null;
            }));
        }
        for (String acct : List.of("T2", "T3")) {
            jobs.add(clients.submit(() -> {
                for (int k = 0; k < 50; k++) {
                    Order o = b.place(acct, "ACME", Side.BUY, OrderType.LIMIT, 10, 90_00).join();
                    b.cancel(acct, o.id).join();
                }
                return null;
            }));
        }
        for (Future<?> j : jobs) j.get(10, TimeUnit.SECONDS);
        clients.shutdown();
        for (String id : List.of("T0", "T1", "T2", "T3")) {
            Account a = b.accounts.get(id);
            System.out.println("  " + id + ": ZETA " + a.totalShares("ZETA") + ", cash " + money(a.freeCash())
                    + " free, " + money(a.blockedCash()) + " blocked");
        }

        System.out.println("9) Portfolio and P&L at the last traded price");
        for (String id : List.of("FUND", "MAKER", "RETAIL")) b.portfolio(id).forEach(System.out::println);

        System.out.println("10) Invariants");
        boolean cashOk = b.totalCash() == cash0;
        boolean sharesOk = b.totalShares("ACME") == acme0 && b.totalShares("ZETA") == zeta0;
        boolean reservedOk = b.reservationsMatch();
        System.out.println("  total cash " + money(b.totalCash()) + " conserved: " + cashOk);
        System.out.println("  ACME " + b.totalShares("ACME") + ", ZETA " + b.totalShares("ZETA")
                + " shares conserved: " + sharesOk);
        System.out.println("  blocked funds match live orders: " + reservedOk + ", trades: "
                + b.tradeIds.get());
        b.shutdown();
        if (!cashOk || !sharesOk || !reservedOk) throw new AssertionError("books do not balance");
    }
}

Notes

Requirements

Fix the scope. Users have accounts with cash and shares. They place market or limit orders to buy or sell. Before an order is accepted we check they have enough cash or shares, and we block that amount at once. Each stock has its own order book, matched by best price and then by time. Orders can fill partly and can be cancelled. Users see a portfolio with profit and loss. Margin, options and short selling are out of scope.

Ask the questions that change the code. Do we run the matching ourselves? Yes, so the order book is in scope. At what price does a trade happen? At the price of the order that was already resting in the book. What if a market order finds too few sellers? Fill what is there and cancel the rest. Can a user sell shares already promised to another open order? No, they are blocked. And money is a long number of paise, never a double.

Requirements
  • accounts hold cash and shares
  • market and limit, buy and sell
  • check cash or shares first
  • and block them at placement
  • order book per stock
  • match: best price, then oldest
  • partial fills, cancel an order
  • portfolio with profit and loss
  • trade and price notifications
  • out of scope: margin, options
Clarify first
  • are we the exchange too?
  • yes, we match in-house
  • trade at whose price?
  • the resting order price
  • market order with thin book?
  • fill what is there, cancel rest
  • can a seller sell shares
  • already in an open order?
  • no, they are blocked
  • money type?
  • long paise, never double

Entities

Now the entities. An account places orders. Each stock has an order book with two sides, bids for buyers and asks for sellers. A side is a set of price levels, and each level is a queue of orders at that exact price. When a buy meets a sell, the engine creates a trade, which fills a part of both orders. Notice the user is not a class here; login and profile belong to other services.

Class diagram

Turn them into types. Side, order type and status are enums. A trade is a fact that never changes, so it is a Java record. The order is mutable: it counts how much has been filled, how much cash it still has blocked, and its status. That sounds risky, but there is a rule that makes it safe: an order is only ever changed on the matching thread of its own stock. We will come back to that rule.

Types
enum Side { BUY, SELL }
enum OrderType { MARKET, LIMIT }
enum Status { OPEN, PARTIALLY_FILLED,
  FILLED, CANCELLED, REJECTED }
record Trade(id, symbol, buyOrder,
  sellOrder, buyer, seller, qty, price)
class Order {
  final qty, limitPaise; // 0 if market
  long filled, reservedCash;
  Status status;
}

Pre-trade checks

Each account splits cash and shares into two buckets: free and blocked. A buy order checks there is enough free cash and moves it to blocked in one atomic step, so a second order cannot spend the same money. A sell order does the same with shares. Checking first and blocking later would let two orders pass the same check. Blocked amounts go back to free when an order is cancelled, or leave the account when it trades.

Account.tryBlockCash()
synchronized boolean tryBlockCash(long p) {
  if (p > cash) return false;
  cash -= p;
  blockedCash += p;
  return true;
}

limit buy 50 @ 99.00: block 4,950.00
sell 150 with 100 free: REJECTED
total = free + blocked, never changes
  except by trades

Order book

Here is the order book. Each side is a tree map from price to a queue of orders. Asks are sorted lowest first, because a buyer wants the cheapest seller. Bids are sorted highest first, because a seller wants the richest buyer. Inside one price, the queue keeps arrival order, so the first order to arrive is the first to trade. That rule is called price-time priority, and the tree map plus a queue gives it to us almost for free.

Price-time priority
NavigableMap<Long, ArrayDeque<Order>>
  bids = new TreeMap<>(reverseOrder());
  asks = new TreeMap<>();

ASK 103.00 x 200 (1 order)
ASK 102.00 x 100 (1 order)
ASK 101.00 x 150 (2 orders)
-----
firstKey(): best price, O(log n)
peekFirst(): oldest order there

Matching engine

The matching loop is short. While the incoming order still wants shares and the other side is not empty, look at the best opposite price. A limit order stops when that price no longer crosses its limit; a market order never stops on price. Take the oldest order at that level, trade the smaller of the two remaining amounts, at the resting price. Drop the resting order when it is done, and drop the level when it is empty.

match(incoming)
while (in.remaining() > 0
       && !other.isEmpty()) {
  long price = other.firstKey();
  if (limit order && !crosses) break;
  Order rest = level.peekFirst();
  long q = min(in.remaining(),
               rest.remaining());
  settle(buy, sell, q, price);
  if (rest done) level.pollFirst();
  if (level empty) other.remove(price);
}

Flow: partial fills

Walk one order. Two sellers rest at one hundred and one rupees: the maker with a hundred shares, then a trader with fifty, who arrived later. A fund buys a hundred and twenty at that price. The engine blocks the cash, then fills the maker's hundred first, because that order is older, and takes twenty of the trader's fifty. The fund is filled. The trader is partially filled, and thirty shares stay in the book, still in their place in the queue.

Two sellers at 101.00
  • MAKER sells 100 at 101.00
  • TRADER sells 50 at 101.00
  • (arrived later)
  • FUND buys 120 at 101.00:
  • 100 from MAKER: FILLED
  • 20 from TRADER: 20 of 50
  • TRADER: PARTIALLY_FILLED,
  • 30 still rests in the book

Flow: market order

A market order has no price, so how much cash do we block? We walk the asks on the engine thread and add up what two hundred and fifty shares would cost right now. Because nothing else can touch the book in between, that number is exact. The order then sweeps three levels: thirty at one hundred and one, a hundred at one hundred and two, and a hundred and twenty at one hundred and three. If the book runs dry, the rest is cancelled and its cash released.

Market buy 250
before: 101.00 x 30, 102.00 x 100,
        103.00 x 200
block = book.sweepCost(250)
      = 25,590.00, on the same thread
fills: 30 + 100 + 120, avg 102.36
after:  103.00 x 80

thin book: fill what is there,
  cancel the rest, release cash

Order states

An order is open while it rests untouched, partially filled once some of it trades, and filled when nothing is left. Cancelled and rejected are the other final states. Cancel is allowed only on a live order: remove it from its price level, set it to cancelled, and release whatever it still has blocked. A second cancel simply returns false. The cancel request goes through the same queue as orders, so it can never overtake the order it is cancelling.

States and cancel
  • OPEN: resting, nothing filled
  • PARTIALLY_FILLED: some filled
  • FILLED: final, leftover cash
  • released
  • CANCELLED: final, the rest of
  • the cash or shares released
  • REJECTED: failed the checks
  • cancel a live order: true
  • cancel it again: false

Settlement

Every trade settles into both accounts. The buyer's blocked cash goes down by quantity times price, and their shares go up. The seller's blocked shares go down and their free cash goes up by the same amount. Cash only moves from one account to another, and so do shares, so the totals across all accounts never change. A buyer who bid one hundred and one but traded at one hundred keeps the difference; it is released when the order finishes.

settle(buy, sell, qty, price)
paise = qty * price;
buyer.settleBuy(sym, qty, paise);
  // blocked cash out, shares in
buy.reservedCash -= paise;
seller.settleSell(sym, qty, paise);
  // blocked shares out, cash in
fill(buy, qty); fill(sell, qty);
lastPrice = price;
notify listeners

Observer

Trades and price changes go out through the Observer pattern. After each trade the engine calls every market listener. A watchlist is just a listener that keeps a set of symbols and speaks only when one of their prices moves. A market data feed, trade confirmations and risk alerts are more listeners, and the engine never knows they exist. In production these calls go onto a queue, so a slow listener cannot slow down matching.

Observer
interface MarketListener {
  void onTrade(Trade t);
}
listeners: CopyOnWriteArrayList

Watchlist implements MarketListener
  symbols: a concurrent set
  speaks only when the price moves
also: market data feed, trade
  confirmations, risk alerts

Portfolio and P&L

The portfolio view needs two kinds of profit and loss. Each account keeps a cost basis per stock. When shares are sold, the average cost of those shares leaves the basis, and the difference from the sale price is realised profit or loss. For what is still held, the value at the last traded price minus the remaining cost is the unrealised profit or loss. Our fund sold thirty below cost, so it realised a small loss.

FUND after the demo
  • bought 370 ACME, cost 37,710.00
  • sold 30 at 99.00
  • cost out: 37,710 x 30 / 370
  • realised P&L: -87.56
  • holds 340, avg 101.91
  • last trade 99.00
  • value 33,660.00
  • unrealised P&L: -992.44

Concurrency

Now the big concurrency choice. We could lock the book, but price-time priority means orders for one stock must be handled one at a time anyway, so locks add cost and bugs while giving no parallel work. Instead each symbol gets one thread with a queue. The book has no locks, and the same input always produces the same trades, so you can replay an order log after a crash. Different symbols run in parallel on different threads, which is how we scale.

Check every shared field. The book and its orders belong to one symbol thread. Accounts are shared, because one user can trade two stocks at once on two threads, so each account method is short and synchronized. Settlement updates the buyer, then the seller, never holding both locks, so there is no deadlock. Cancels use the order queue, ids come from atomic counters, listeners sit in a copy-on-write list, and trades are immutable records.

Why one thread per symbol
  • matching is in order by nature:
  • price-time is a single queue
  • locks per level: hard, and
  • still one at a time
  • one thread: no locks in the book,
  • no races, cache friendly
  • same input, same trades:
  • replay from an order log
  • scale: spread symbols over
  • threads or machines
Thread safety checklist
  • book and orders: one thread
  • per symbol, nothing shared
  • accounts: shared by symbols,
  • small synchronized methods
  • one account lock at a time:
  • no deadlock possible
  • cancel: same queue as orders
  • orders map: ConcurrentHashMap
  • ids: AtomicLong
  • listeners: CopyOnWriteArrayList
  • trades: immutable records

Extensibility

Interviewers will stretch it. A stop-loss order does not sit in the visible book. It waits in a separate map keyed by its trigger price, and after each trade the engine checks whether the last price crossed it. If so, it becomes a market order on the same thread, which keeps everything in order. Immediate-or-cancel and fill-or-kill are rules about the remainder. Fees go to a fee account, so cash is still conserved.

Extension points
  • stop-loss: held off the book,
  • keyed by trigger price; when
  • last price crosses, it becomes
  • a market order on that thread
  • IOC, fill-or-kill: rules in
  • accept() for the remainder
  • fees: a fee account, so cash
  • is still conserved
  • self-trade check in match()
  • cancel in O(1): id to node map

Testing

The full code is below the player. The demo builds an ask side, fills a limit buy across two sellers with a partial fill, sweeps three levels with a market buy, partly fills a resting bid with a market sell and cancels the rest. Three orders are rejected for missing cash or shares. Four client threads then trade two symbols at once, and the final check proves total cash and shares are unchanged and blocked amounts match the live orders.

Run it
buy 120 @ 101: 100 MAKER, 20 TRADER
TRADER ask: PARTIALLY_FILLED 20/50
market buy 250: FILLED, avg 102.36
market sell 30: RETAIL bid 30/50
cancel bid: released 1,980.00
buy 100 @ 103: needs 10,300.00
MAKER sell 150: only 100 free
4 threads, 2 symbols: all settled
total cash conserved: true
shares conserved: true
blocked matches live orders: true

Follow-ups

Expect follow-ups. Why not lock the book? It works, but matching is sequential anyway. What if one stock is very busy? Give that symbol its own core. What if the server crashes? Rebuild the books by replaying the order log. Why tree maps over two heaps? Levels are easy to find and remove for cancels and depth. How much to block for a market buy when you are only a broker? Use a price band above the last price.

Follow-ups to expect
  • why not one lock on the book?
  • correct, but no gain
  • a hot stock is too busy?
  • one core per hot symbol
  • server crashes?
  • replay the order log
  • why TreeMap and not a heap?
  • removing a level is easy
  • how big a market buy block?
  • sweep cost, or a price band

Say it like this

Here is the short version to say out loud. Accounts block cash or shares when an order is placed, so nothing is spent twice. Each stock has a book of tree maps with a queue per price. The engine matches best price first, then oldest, trades at the resting price, and settles both accounts. Each symbol has one matching thread, so the book needs no locks, and trades go out to observers.

In the interview
  • "Accounts block cash or shares
  • when an order is placed. Each
  • stock has a book of TreeMaps
  • with FIFO queues per price.
  • The engine matches best price
  • then time, at the resting price,
  • and settles both accounts. One
  • thread per symbol; trades go
  • out to observers."

Interview questions

How do you implement price-time priority in an order book?

Keep each side as a sorted map from price to a FIFO queue of orders: asks lowest price first, bids highest first. The best price is the first key, and inside a price the oldest order is at the head of the queue, so it trades first.

At what price does a trade happen when a buy at 103 meets a sell resting at 101?

At 101, the price of the resting order. The order already in the book set the price, and the incoming order gets that price or better, so a buyer never pays more than the best ask.

Why block funds when an order is placed instead of checking at trade time?

Without blocking, two open orders could both pass the cash check and later both trade, spending the same money twice. Moving cash or shares from free to blocked in one atomic step makes each rupee or share promised to one order only.

How much cash do you block for a market buy order?

Inside the matching engine you can walk the asks and block the exact sweep cost, because nothing changes the book between the check and the match. A broker that routes to an outside exchange usually blocks quantity times last price plus a safety band.

Why is one thread per symbol the common choice for matching?

Price-time priority means orders for one stock must be applied one after another, so locks give no parallel speedup but add cost and bugs. One thread per symbol needs no locks, is deterministic, can be rebuilt by replaying the order log, and different symbols still run in parallel.

How does cancel work, and what if the cancel arrives while the order is matching?

Cancel goes through the same per-symbol queue as orders, so it runs only after the order has finished matching. If the order is still live it is removed from its level, marked CANCELLED and its blocked remainder is released; otherwise the cancel returns false.

How do you compute realised and unrealised P&L?

Keep a cost basis per stock. On a sale, remove the average cost of the sold shares and book the difference from the sale amount as realised P&L. Unrealised P&L is the held quantity times the last traded price minus the remaining cost basis.

How would you add stop-loss orders?

Keep them off the visible book in a map keyed by trigger price. After each trade, the engine checks whether the last price crossed any trigger; triggered stops become market or limit orders processed on the same symbol thread, which keeps their order deterministic.

How do you prove the system never creates or loses money or shares?

Every trade moves cash from buyer to seller and shares from seller to buyer in equal amounts, so totals across all accounts must stay constant. A check sums free plus blocked cash and shares, and also confirms blocked amounts equal what live orders still need.