Design a stock exchange order book

“Design the order book for a stock exchange: traders send buy and sell orders, and the exchange matches them.” Then: “two traders send orders for the same shares in the same microsecond. Who gets them?”

A stock exchange is where buyers and sellers of shares meet. Each buyer says the most they’ll pay, and each seller says the least they’ll accept. These are orders. An order book is where the exchange keeps every order that hasn’t traded yet. Whenever a buyer’s price reaches a seller’s price, the two trade, and the exchange’s matching engine decides who trades with whom.

The question looks like a data structure exercise, and the data structure matters. But what makes it hard is fairness. Every trader must be treated by the same rule, the rule must be exact, and the result must be the same every time. An exchange that can’t say why one order filled before another doesn’t stay an exchange for long.

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. Price-time priority. The best price trades first, and at one price, the oldest order trades first. A trade happens at the price of the resting order, the one already waiting on the book.
2. Each side of the book is a sorted map from price to a queue of orders, oldest first. The best price is the first key, so matching never looks at orders that can’t trade.
3. An index from order id to order makes cancel fast. A change keeps the order’s place in line only when it shrinks, at the same price. Anything else goes to the back of the line.
4. Order types are one field on one matching loop. Only what happens to the unfilled part differs.
5. One book is matched by one thread at a time, with a lock per stock. Every accepted request is numbered in a journal, and replaying the journal gives exactly the same trades.

We’ll build this in four stages, then run many stocks at once from many gateways.

Scope it

Before drawing anything, we ask a few questions. Each answer changes a class. Anything that doesn’t, we assume and move on.

Interviewerminute 0

Design a stock exchange.

What they are testing

Whether you scope it to the matching engine. Accounts, clearing, settlement, market data feeds and risk checks are each their own system. The red flag is drawing a dozen services and never deciding which order trades first.

Here are the questions that matter:

• Which part: accounts, matching, or market data? The order book and the matching engine. Accounts and settlement (actually moving the money and shares) are a separate ledger problem.
• How are orders ranked? By price, then by time.
• Which order types? Limit orders first, then market, immediate-or-cancel and fill-or-kill.
• How are prices given? In whole ticks, the smallest price step, such as cents.
• One stock or many? Many symbols (like AAPL), each with its own book.

These answers give us one promise that matters more than the others: no share is ever sold twice, and every trade follows price-time priority. That holds even with orders arriving at the same instant. Two smaller promises come with it. Matching is deterministic: the same orders in the same sequence always give the same trades. And matching is fast. An order touches only the prices it can trade at, never the whole book.

We leave out accounts, settlement, risk checks and market data feeds.

Go deeperThree more questions, and what each changes1 min

Question	We assume	If the answer were different
Can a trader trade with themselves?	Allowed	Self-trade prevention cancels one side before matching
Trading hours and auctions?	Continuous trading	An opening auction collects orders and finds one price
Do we check the trader can pay?	Before the engine	A risk check inside matching would slow every order

Common mistake

Prices as doubles

0.1 + 0.2 is 0.30000000000000004 in floating point. So a buyer at 0.30 and a seller at 0.1 + 0.2 never trade. Every exchange quotes prices in ticks, and stores them as whole numbers: 101.25 dollars is 10125 cents. Say this early. Interviewers listen for it.

Build it

We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram). Prices are stored in cents, but the examples use small whole numbers like 100, to keep them easy to read.

Stage 1: Two lists of orders

Interviewerminute 3

Start simple: buy and sell orders, and match them when the prices cross.

What they are testing

Whether you can get something working quickly, and then say exactly what’s wrong with it. The problems of the simple version are the requirements of the real one.

Start with the smallest thing that works. An Order has an id, a Side (buy or sell), a price, and the quantity still to fill. A Trade records who bought from whom, at what price, and how many. The OrderBook keeps two lists. A new buy walks through the sell list, and trades with anything priced at or below its limit. Whatever is left joins the buy list.

Stage 1: two lists

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JOrderBook.javaPyorder_book.pyC#OrderBook.csGoorder_book.goTSorder-book.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Which way an order goes. A buy matches against sells, and a sell against buys.
enum Side { BUY, SELL }

// Prices are whole ticks (cents here), never floating point: 0.1 + 0.2 isn't 0.3, and an
// exchange must compare prices exactly.
class Order {
    final String id;
    final Side side;
    final long price;
    long remaining;

    Order(String id, Side side, long price, long quantity) {
        this.id = id;
        this.side = side;
        this.price = price;
        this.remaining = quantity;
    }
}

// Two orders met: who bought, who sold, how many, and at what price. The price is always the
// resting order's: it was there first.
record Trade(String buyId, String sellId, long price, long quantity) {}

class OrderBook {
    private final List<Order> buys = new ArrayList<>();
    private final List<Order> sells = new ArrayList<>();

    // flaw 1: it takes the first order that crosses, not the best price: a buyer pays 105 while
    // someone is offering at 100.
    // flaw 2: every order scans the whole other side, so a busy book gets slower with every order.
    // flaw 3: nothing can be cancelled.
    List<Trade> submit(Order o) {
        List<Trade> trades = new ArrayList<>();
        List<Order> other = o.side == Side.BUY ? sells : buys;
        for (Iterator<Order> it = other.iterator(); it.hasNext() && o.remaining > 0; ) {
            Order resting = it.next();
            boolean crosses = o.side == Side.BUY ? resting.price <= o.price : resting.price >= o.price;
            if (!crosses) continue;
            long qty = Math.min(o.remaining, resting.remaining);
            trades.add(o.side == Side.BUY
                ? new Trade(o.id, resting.id, resting.price, qty)
                : new Trade(resting.id, o.id, resting.price, qty));
            o.remaining -= qty;
            resting.remaining -= qty;
            if (resting.remaining == 0) it.remove();
        }
        if (o.remaining > 0) (o.side == Side.BUY ? buys : sells).add(o);
        return trades;
    }
}

It works, but it has three problems, and we leave them in on purpose. It takes the first seller it finds, not the cheapest. With offers at 105 and then 100, a buyer at 110 pays 105, while someone was selling for 100. Every order looks through the whole other side, so the book gets slower as it fills. And an order can never be cancelled.

Stage 2: Price levels and price-time priority

Interviewerminute 6

A buyer should always get the cheapest shares first. And when two sellers ask the same price, who goes first?

What they are testing

Whether you know price-time priority. And whether you pick a structure where the best price is found at once, and the oldest order at that price is next. The red flag is one list sorted on every insert. So is a heap of single orders, which loses the order of arrival at one price.

The rule every major stock exchange uses is price-time priority. The best price trades first: the highest bid (buy price) and the lowest ask (sell price). Among orders at the same price, the one that arrived first trades first. A trader who offered a better price, or the same price sooner, has earned the trade.

That rule decides the structure. Each side of the book is a sorted map from price to a Level. Each level is a queue of orders, oldest first (FIFO: first in, first out). Bids are sorted highest first, and asks lowest first. So the best price on each side is the first key.

An incoming buy looks at the lowest ask. If its limit reaches that price, it fills against that level’s orders, from the front. When this level is empty, it moves to the next. It stops at the first price it can’t reach, without looking at anything beyond it.

Here is a book, and a new buy for 10 shares with a limit of 102:

Bids, highest first	Asks, lowest first
99: Ana 5, Ben 3	101: Eve 2, Fay 6
98: Cy 4	102: Gus 5
97: Dee 10	105: Hal 1

The buy takes Eve’s 2 shares at 101, then Fay’s 6 at 101. The 101 level is now empty, so it moves to 102 and takes 2 of Gus’s 5. That’s 10 shares. Gus keeps 3 on the book, and Hal at 105 is never looked at.

Stage 2: a buy walks the asks

Scroll or pinch to zoom, drag to pan

The trade happens at the resting order’s price. Eve asked 101, and the buyer was willing to pay 102, so the trade is at 101. The resting order set its price first, and the incoming order accepted it. The buyer keeps the difference: an incoming order never trades at a worse price than the best one on the book.

Stage 2: sorted levels

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JOrderBook.javaPybook_side.pyC#OrderBook.csGoorder_book.goTSbook-side.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// All resting orders at one price, oldest first. A LinkedHashMap keeps arrival order and, from
// stage 3, removes any order by id in constant time.
class Level {
    final long price;
    final LinkedHashMap<String, Order> orders = new LinkedHashMap<>();

    Level(long price) { this.price = price; }
}

class OrderBook {
    // Each side is sorted best price first: the highest bid and the lowest ask. Finding the best
    // level is O(log n) in the number of prices, not in the number of orders.
    private final TreeMap<Long, Level> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, Level> asks = new TreeMap<>();

    // Price-time priority: the best price trades first, and at one price, the oldest order. The
    // trade happens at the resting order's price, the one that was already on the book.
    List<Trade> submit(Order o) {
        List<Trade> trades = new ArrayList<>();
        TreeMap<Long, Level> opposite = o.side == Side.BUY ? asks : bids;
        while (o.remaining > 0 && !opposite.isEmpty()) {
            Level best = opposite.firstEntry().getValue();
            if (!crosses(o, best.price)) break;
            Iterator<Order> it = best.orders.values().iterator();
            while (o.remaining > 0 && it.hasNext()) {
                Order resting = it.next();
                long qty = Math.min(o.remaining, resting.remaining);
                trades.add(o.side == Side.BUY
                    ? new Trade(o.id, resting.id, best.price, qty)
                    : new Trade(resting.id, o.id, best.price, qty));
                o.remaining -= qty;
                resting.remaining -= qty;
                if (resting.remaining == 0) it.remove();
            }
            if (best.orders.isEmpty()) opposite.pollFirstEntry();
        }
        if (o.remaining > 0) rest(o);
        return trades;
    }

    Long bestBid() { return bids.isEmpty() ? null : bids.firstKey(); }

    Long bestAsk() { return asks.isEmpty() ? null : asks.firstKey(); }

    static boolean crosses(Order o, long price) { return o.side == Side.BUY ? price <= o.price : price >= o.price; }

    private void rest(Order o) {
        (o.side == Side.BUY ? bids : asks).computeIfAbsent(o.price, Level::new).orders.put(o.id, o);
    }
}

Go deeperHow to keep the price levels2 min

Java uses a TreeMap, and C# a SortedDictionary. Python, Go and TypeScript keep a sorted array of prices, searched with binary search, beside a map from price to level. All give the best price straight away, and adding a new price costs a logarithmic search.

	Heap of orders	Sorted map of levels (our choice)	Array indexed by tick
Best price	Top of the heap	First key	A pointer kept to the best
Time order at a price	Needs a tie-breaker	The level’s queue	The level’s queue
Cancel	Slow: find and remove	Fast with an index by id	Fast with an index by id
Depth for a screen	Take out and put back	Walk the first few keys	Walk from the best tick
Memory	One entry per order	One entry per live price	Every tick in the price band

Real matching engines often use the array. Prices stay close to the market, and tick sizes are fixed, so a few thousand slots cover the day. The sorted map is the clearest to write in an interview, and behaves the same way.

Stage 3: Cancel and modify

Interviewerminute 13

Traders cancel far more orders than they fill. How do you cancel fast? And if someone changes the quantity of their order, do they keep their place in line?

What they are testing

Whether you index orders by id, instead of searching the book. And whether you know the priority rule for changes. The red flag is keeping the order’s place when it grows, because that lets a trader jump the queue.

On a real exchange, most orders are cancelled, not filled, often more than ninety percent. So cancel must not search the book. The book keeps an index, resting, from order id to the order. Cancel looks the order up, removes it from its level, and removes the level if it’s now empty. Filling an order completely removes it from the index too, so cancelling a filled order correctly returns false.

Modify follows one fairness rule. An order that shrinks at the same price keeps its place: asking for fewer shares can only help the people behind it. Anything else, a new price or a bigger quantity, would take shares that the people behind it were there first to claim. So it becomes a cancel plus a new order at the back of the line. A new price can also reach the other side and trade at once, which is why modify returns trades.

Stage 3: what a modify does

Scroll or pinch to zoom, drag to pan

Stage 3: an index for cancel

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JOrderBook.javaPyorder_book.pyC#OrderBook.csGoorder_book.goTSorder-book.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class OrderBook {
    private final TreeMap<Long, Level> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, Level> asks = new TreeMap<>();
    // Every resting order by id, so cancel finds it without searching the book.
    private final Map<String, Order> resting = new HashMap<>();

    List<Trade> submit(Order o) {
        List<Trade> trades = match(o);
        if (o.remaining > 0) rest(o);
        return trades;
    }

    boolean cancel(String id) {
        Order o = resting.remove(id);
        if (o == null) return false;  // never existed, already filled, or already cancelled
        TreeMap<Long, Level> side = sideOf(o.side);
        Level level = side.get(o.price);
        level.orders.remove(id);
        if (level.orders.isEmpty()) side.remove(o.price);
        return true;
    }

    // Lowering the quantity at the same price keeps the order's place in line: it asks for less,
    // so nobody behind it is worse off. Anything else, a new price or more quantity, would jump
    // ahead of people who were there first, so it's a cancel and a new order at the back.
    List<Trade> modify(String id, long price, long quantity) {
        Order o = resting.get(id);
        if (o == null) return List.of();
        if (price == o.price && quantity <= o.remaining) {
            if (quantity == 0) cancel(id);
            else o.remaining = quantity;
            return List.of();
        }
        cancel(id);
        return submit(new Order(id, o.side, price, quantity));
    }

    Long bestBid() { return bids.isEmpty() ? null : bids.firstKey(); }

    Long bestAsk() { return asks.isEmpty() ? null : asks.firstKey(); }

    private List<Trade> match(Order o) {
        List<Trade> trades = new ArrayList<>();
        TreeMap<Long, Level> opposite = sideOf(o.side == Side.BUY ? Side.SELL : Side.BUY);
        while (o.remaining > 0 && !opposite.isEmpty()) {
            Level best = opposite.firstEntry().getValue();
            if (!crosses(o, best.price)) break;
            Iterator<Order> it = best.orders.values().iterator();
            while (o.remaining > 0 && it.hasNext()) {
                Order r = it.next();
                long qty = Math.min(o.remaining, r.remaining);
                trades.add(o.side == Side.BUY ? new Trade(o.id, r.id, best.price, qty) : new Trade(r.id, o.id, best.price, qty));
                o.remaining -= qty;
                r.remaining -= qty;
                if (r.remaining == 0) {
                    it.remove();
                    resting.remove(r.id);
                }
            }
            if (best.orders.isEmpty()) opposite.pollFirstEntry();
        }
        return trades;
    }

    private TreeMap<Long, Level> sideOf(Side s) { return s == Side.BUY ? bids : asks; }

    static boolean crosses(Order o, long price) { return o.side == Side.BUY ? price <= o.price : price >= o.price; }

    private void rest(Order o) {
        sideOf(o.side).computeIfAbsent(o.price, Level::new).orders.put(o.id, o);
        resting.put(o.id, o);
    }
}

Go deeperRemoving an order from the middle of a level1 min

How fast this is depends on the queue. Java keeps each level as a LinkedHashMap by id, and C# keeps the LinkedListNode, so removal is immediate. Python, Go and TypeScript use a list, and search just that one level, which usually holds a handful of orders.

Stage 4: Order types and market depth

Interviewerminute 18

Traders also want market orders, orders that must fill immediately or not at all, and a screen showing the best few prices. Where does each go?

What they are testing

Whether the order types become a field the matching loop respects, instead of new copies of the loop. And whether you see that fill-or-kill has to be checked before matching, since a trade can’t be undone.

Every order now carries a TimeInForce, which says what happens to the part that doesn’t fill right away:

• GTC, good till cancelled: the rest waits on the book. This is the limit order we’ve had so far.
• IOC, immediate or cancel: trade what’s possible now, and drop the rest.
• FOK, fill or kill: fill the whole quantity now, or do nothing at all.

All three use the same matching loop. Only the end differs: GTC puts the rest on the book, IOC drops it. FOK is the one that can’t be fixed afterwards, because trades already reported can’t be taken back. So before matching, the book adds up what’s available at prices the order can reach, and stops counting once it’s enough. If it falls short, the order is refused with no trades.

A market order says “any price”. It’s a limit order with the worst possible price: the maximum for a buy, and zero for a sell, so it reaches every level. It’s always IOC. A market order waiting on the book at “any price” would be an offer anyone could take at an absurd price.

Depth is what the trading screen shows: the first few levels of a side, each with its price and the total quantity there. With levels kept sorted, it’s a walk over the first few keys.

Stage 4: order types and depth

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JOrderBook.javaPyorder_book.pyC#TimedOrderBook.csGoorder_book.goTStimed-order-book.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// How long an order may wait. GTC rests on the book until filled or cancelled. IOC takes what it
// can right now and drops the rest. FOK fills completely right now, or does nothing at all.
enum TimeInForce { GTC, IOC, FOK }

// Prices are whole ticks (cents here), never floating point: 0.1 + 0.2 isn't 0.3, and an
// exchange must compare prices exactly. remaining counts down as the order fills.
class Order {
    final String id;
    final Side side;
    final long price;
    final long quantity;
    final TimeInForce tif;
    long remaining;

    Order(String id, Side side, long price, long quantity, TimeInForce tif) {
        this.id = id;
        this.side = side;
        this.price = price;
        this.quantity = quantity;
        this.tif = tif;
        this.remaining = quantity;
    }

    static Order limit(String id, Side side, long price, long quantity) {
        return new Order(id, side, price, quantity, TimeInForce.GTC);
    }

    // A market order is a limit order at the worst possible price, so it crosses every level, and
    // IOC, so it never rests on the book at that absurd price.
    static Order market(String id, Side side, long quantity) {
        return new Order(id, side, side == Side.BUY ? Long.MAX_VALUE : 0, quantity, TimeInForce.IOC);
    }
}

// One row of the market data screen: a price and the total quantity resting there.
record Depth(long price, long quantity) {}

// One symbol's book. Bids are sorted highest first and asks lowest first, so the best price on
// each side is always the first key. `resting` finds any order by id, so a cancel never searches.
class OrderBook {
    private final TreeMap<Long, Level> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, Level> asks = new TreeMap<>();
    private final Map<String, Order> resting = new HashMap<>();

    // FOK checks first, because a fill can't be undone. Then match. What is left of a GTC order
    // rests on the book; IOC and FOK leftovers are dropped.
    List<Trade> submit(Order o) {
        if (o.tif == TimeInForce.FOK && fillable(o) < o.quantity) return List.of();
        List<Trade> trades = match(o);
        if (o.remaining > 0 && o.tif == TimeInForce.GTC) rest(o);
        return trades;
    }

    // An empty price level is removed too, so the first key is always a real price.
    boolean cancel(String id) {
        Order o = resting.remove(id);
        if (o == null) return false;
        TreeMap<Long, Level> side = sideOf(o.side);
        Level level = side.get(o.price);
        level.orders.remove(id);
        if (level.orders.isEmpty()) side.remove(o.price);
        return true;
    }

    // Shrinking an order keeps its place in the queue. A new price or a bigger size is a cancel and
    // a new order, so it goes to the back of the line, as on real exchanges.
    List<Trade> modify(String id, long price, long quantity) {
        Order o = resting.get(id);
        if (o == null) return List.of();
        if (price == o.price && quantity <= o.remaining) {
            if (quantity == 0) cancel(id);
            else o.remaining = quantity;
            return List.of();
        }
        cancel(id);
        return submit(Order.limit(id, o.side, price, quantity));
    }

    Long bestBid() { return bids.isEmpty() ? null : bids.firstKey(); }

    Long bestAsk() { return asks.isEmpty() ? null : asks.firstKey(); }

    // The top levels of one side, best first, as a trading screen shows them.
    List<Depth> depth(Side side, int levels) {
        List<Depth> out = new ArrayList<>();
        for (Level l : sideOf(side).values()) {
            if (out.size() == levels) break;
            out.add(new Depth(l.price, l.orders.values().stream().mapToLong(o -> o.remaining).sum()));
        }
        return out;
    }

    // How much of this order could trade right now, stopping once it's enough. FOK needs the
    // answer before matching, because a fill can't be undone.
    private long fillable(Order o) {
        long total = 0;
        for (Level l : sideOf(o.side == Side.BUY ? Side.SELL : Side.BUY).values()) {
            if (!crosses(o, l.price) || total >= o.quantity) break;
            for (Order r : l.orders.values()) total += r.remaining;
        }
        return total;
    }

    // Price first, then time: take the best price level, and in it the oldest order, until the
    // incoming order is filled or no longer crosses.
    private List<Trade> match(Order o) {
        List<Trade> trades = new ArrayList<>();
        TreeMap<Long, Level> opposite = sideOf(o.side == Side.BUY ? Side.SELL : Side.BUY);
        while (o.remaining > 0 && !opposite.isEmpty()) {
            Level best = opposite.firstEntry().getValue();
            if (!crosses(o, best.price)) break;
            Iterator<Order> it = best.orders.values().iterator();
            while (o.remaining > 0 && it.hasNext()) {
                Order r = it.next();
                long qty = Math.min(o.remaining, r.remaining);
                trades.add(o.side == Side.BUY ? new Trade(o.id, r.id, best.price, qty) : new Trade(r.id, o.id, best.price, qty));
                o.remaining -= qty;
                r.remaining -= qty;
                if (r.remaining == 0) {
                    it.remove();
                    resting.remove(r.id);
                }
            }
            if (best.orders.isEmpty()) opposite.pollFirstEntry();
        }
        return trades;
    }

    private TreeMap<Long, Level> sideOf(Side s) { return s == Side.BUY ? bids : asks; }

    // A buy crosses a sell priced at or below it; a sell crosses a buy priced at or above it.
    static boolean crosses(Order o, long price) { return o.side == Side.BUY ? price <= o.price : price >= o.price; }

    private void rest(Order o) {
        sideOf(o.side).computeIfAbsent(o.price, Level::new).orders.put(o.id, o);
        resting.put(o.id, o);
    }
}

In C# and TypeScript, these changes live in a TimedOrderBook subclass of the stage 3 book. In Java, Python and Go, the book itself changes.

Go deeperThe same buy as GTC, IOC and FOK1 min

Take the book from stage 2 again, and a buy for 20 shares with a limit of 102. At 101 and 102 there are 2 + 6 + 5 = 13 shares.

• GTC: it buys all 13, and the other 7 rest on the book as the new best bid at 102.
• IOC: it buys all 13, and the other 7 are dropped. Nothing rests.
• FOK: before matching, the book counts 13 available, which is less than 20. The order is refused, with no trades, and the book is exactly as it was.

A market buy for 20 would go further. After 101 and 102, it would take Hal’s 1 share at 105. Then it would stop with 6 unfilled, and drop them, because it’s IOC.

This is enough for a mid-level answer. Matching by price, then time, using sorted levels. Cancel through an index by id. And order types as a field. The rest of the page is what makes it a senior answer.

The full design

Here is everything together, including the Exchange that we add next. Gateways call the exchange. The exchange finds the symbol’s book. The book matches against sorted levels, and returns trades.

Stock exchange: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>stock-exchange· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JAction.java
• JCommand.java
• JDepth.java
• JExchange.java
• JLevel.java
• JOrder.java
• JOrderBook.java
• JSide.java
• JTimeInForce.java
• JTrade.java

JAllInOne.java

AllInOne.javasrc/Action.javasrc/Command.javasrc/Depth.javasrc/Exchange.javasrc/Level.javasrc/Order.javasrc/OrderBook.javasrc/Side.javasrc/TimeInForce.javasrc/Trade.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

// Which way an order goes. A buy matches against sells, and a sell against buys.
enum Side { BUY, SELL }

// Prices are whole ticks (cents here), never floating point: 0.1 + 0.2 isn't 0.3, and an
// exchange must compare prices exactly. remaining counts down as the order fills.
class Order {
    final String id;
    final Side side;
    final long price;
    final long quantity;
    final TimeInForce tif;
    long remaining;

    Order(String id, Side side, long price, long quantity, TimeInForce tif) {
        this.id = id;
        this.side = side;
        this.price = price;
        this.quantity = quantity;
        this.tif = tif;
        this.remaining = quantity;
    }

    static Order limit(String id, Side side, long price, long quantity) {
        return new Order(id, side, price, quantity, TimeInForce.GTC);
    }

    // A market order is a limit order at the worst possible price, so it crosses every level, and
    // IOC, so it never rests on the book at that absurd price.
    static Order market(String id, Side side, long quantity) {
        return new Order(id, side, side == Side.BUY ? Long.MAX_VALUE : 0, quantity, TimeInForce.IOC);
    }
}

// Two orders met: who bought, who sold, how many, and at what price. The price is always the
// resting order's: it was there first.
record Trade(String buyId, String sellId, long price, long quantity) {}

// One symbol's book. Bids are sorted highest first and asks lowest first, so the best price on
// each side is always the first key. `resting` finds any order by id, so a cancel never searches.
class OrderBook {
    private final TreeMap<Long, Level> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, Level> asks = new TreeMap<>();
    private final Map<String, Order> resting = new HashMap<>();

    // FOK checks first, because a fill can't be undone. Then match. What is left of a GTC order
    // rests on the book; IOC and FOK leftovers are dropped.
    List<Trade> submit(Order o) {
        if (o.tif == TimeInForce.FOK && fillable(o) < o.quantity) return List.of();
        List<Trade> trades = match(o);
        if (o.remaining > 0 && o.tif == TimeInForce.GTC) rest(o);
        return trades;
    }

    // An empty price level is removed too, so the first key is always a real price.
    boolean cancel(String id) {
        Order o = resting.remove(id);
        if (o == null) return false;
        TreeMap<Long, Level> side = sideOf(o.side);
        Level level = side.get(o.price);
        level.orders.remove(id);
        if (level.orders.isEmpty()) side.remove(o.price);
        return true;
    }

    // Shrinking an order keeps its place in the queue. A new price or a bigger size is a cancel and
    // a new order, so it goes to the back of the line, as on real exchanges.
    List<Trade> modify(String id, long price, long quantity) {
        Order o = resting.get(id);
        if (o == null) return List.of();
        if (price == o.price && quantity <= o.remaining) {
            if (quantity == 0) cancel(id);
            else o.remaining = quantity;
            return List.of();
        }
        cancel(id);
        return submit(Order.limit(id, o.side, price, quantity));
    }

    Long bestBid() { return bids.isEmpty() ? null : bids.firstKey(); }

    Long bestAsk() { return asks.isEmpty() ? null : asks.firstKey(); }

    // The top levels of one side, best first, as a trading screen shows them.
    List<Depth> depth(Side side, int levels) {
        List<Depth> out = new ArrayList<>();
        for (Level l : sideOf(side).values()) {
            if (out.size() == levels) break;
            out.add(new Depth(l.price, l.orders.values().stream().mapToLong(o -> o.remaining).sum()));
        }
        return out;
    }

    // How much of this order could trade right now, stopping once it's enough. FOK needs the
    // answer before matching, because a fill can't be undone.
    private long fillable(Order o) {
        long total = 0;
        for (Level l : sideOf(o.side == Side.BUY ? Side.SELL : Side.BUY).values()) {
            if (!crosses(o, l.price) || total >= o.quantity) break;
            for (Order r : l.orders.values()) total += r.remaining;
        }
        return total;
    }

    // Price first, then time: take the best price level, and in it the oldest order, until the
    // incoming order is filled or no longer crosses.
    private List<Trade> match(Order o) {
        List<Trade> trades = new ArrayList<>();
        TreeMap<Long, Level> opposite = sideOf(o.side == Side.BUY ? Side.SELL : Side.BUY);
        while (o.remaining > 0 && !opposite.isEmpty()) {
            Level best = opposite.firstEntry().getValue();
            if (!crosses(o, best.price)) break;
            Iterator<Order> it = best.orders.values().iterator();
            while (o.remaining > 0 && it.hasNext()) {
                Order r = it.next();
                long qty = Math.min(o.remaining, r.remaining);
                trades.add(o.side == Side.BUY ? new Trade(o.id, r.id, best.price, qty) : new Trade(r.id, o.id, best.price, qty));
                o.remaining -= qty;
                r.remaining -= qty;
                if (r.remaining == 0) {
                    it.remove();
                    resting.remove(r.id);
                }
            }
            if (best.orders.isEmpty()) opposite.pollFirstEntry();
        }
        return trades;
    }

    private TreeMap<Long, Level> sideOf(Side s) { return s == Side.BUY ? bids : asks; }

    // A buy crosses a sell priced at or below it; a sell crosses a buy priced at or above it.
    static boolean crosses(Order o, long price) { return o.side == Side.BUY ? price <= o.price : price >= o.price; }

    private void rest(Order o) {
        sideOf(o.side).computeIfAbsent(o.price, Level::new).orders.put(o.id, o);
        resting.put(o.id, o);
    }
}

// All resting orders at one price, oldest first. A LinkedHashMap keeps arrival order and, from
// stage 3, removes any order by id in constant time.
class Level {
    final long price;
    final LinkedHashMap<String, Order> orders = new LinkedHashMap<>();

    Level(long price) { this.price = price; }
}

// How long an order may wait. GTC rests on the book until filled or cancelled. IOC takes what it
// can right now and drops the rest. FOK fills completely right now, or does nothing at all.
enum TimeInForce { GTC, IOC, FOK }

// One row of the market data screen: a price and the total quantity resting there.
record Depth(long price, long quantity) {}

// The two kinds of request the journal records.
enum Action { SUBMIT, CANCEL }

// One accepted request, numbered. The journal of these is the exchange's source of truth:
// replaying it in sequence order rebuilds every book and every trade exactly.
record Command(long seq, String symbol, Action action, String id, Side side, long price, long quantity, TimeInForce tif) {}

// Many gateways send orders at once. Matching must see one symbol's orders one at a time, in a
// single agreed order, or two orders can both take the same resting quantity. So each symbol's
// book has its own lock: orders for different symbols never wait for each other. The sequence
// number is taken under that lock too, so sequence order is exactly the order the book saw.
class Exchange {
    // One symbol's book and its trades. Its monitor is that symbol's lock.
    private static final class Book {
        final OrderBook book = new OrderBook();
        final List<Trade> trades = new ArrayList<>();
    }

    private final ConcurrentHashMap<String, Book> books = new ConcurrentHashMap<>();
    private final AtomicLong sequence = new AtomicLong();
    private final ConcurrentLinkedQueue<Command> journal = new ConcurrentLinkedQueue<>();

    List<Trade> submit(String symbol, Order o) {
        Book b = books.computeIfAbsent(symbol, s -> new Book());
        synchronized (b) {
            journal.add(new Command(sequence.incrementAndGet(), symbol, Action.SUBMIT, o.id, o.side, o.price, o.quantity, o.tif));
            List<Trade> trades = b.book.submit(o);
            b.trades.addAll(trades);
            return trades;
        }
    }

    boolean cancel(String symbol, String id) {
        Book b = books.computeIfAbsent(symbol, s -> new Book());
        synchronized (b) {
            journal.add(new Command(sequence.incrementAndGet(), symbol, Action.CANCEL, id, null, 0, 0, null));
            return b.book.cancel(id);
        }
    }

    List<Trade> trades(String symbol) {
        Book b = books.computeIfAbsent(symbol, s -> new Book());
        synchronized (b) {
            return List.copyOf(b.trades);
        }
    }

    // Two symbols add to the queue at the same time, so entries can land slightly out of order.
    // Sorting by sequence number gives the one true order.
    List<Command> journal() {
        return journal.stream().sorted(Comparator.comparingLong(Command::seq)).toList();
    }

    // After a crash, or on a standby machine: the same commands in the same order give the same
    // books and the same trades, because matching depends on nothing else.
    static Exchange replay(List<Command> commands) {
        Exchange e = new Exchange();
        for (Command c : commands) {
            if (c.action() == Action.SUBMIT) e.submit(c.symbol(), new Order(c.id(), c.side(), c.price(), c.quantity(), c.tif()));
            else e.cancel(c.symbol(), c.id());
        }
        return e;
    }
}

Read onlyJava 21Every file builds in CI11 files225 lines

Explorer

• Pyall_in_one.py
• stock_exchange
• Py_book.py
• Pyaction.py
• Pybook_side.py
• Pycommand.py
• Pycommon.py
• Pydepth.py
• Pyexchange.py
• Pylevel.py
• Pyorder.py
• Pyorder_book.py
• Pyside.py
• Pytime_in_force.py
• Pytrade.py

Pyall_in_one.py

all_in_one.pystock_exchange/_book.pystock_exchange/action.pystock_exchange/book_side.pystock_exchange/command.pystock_exchange/common.pystock_exchange/depth.pystock_exchange/exchange.pystock_exchange/level.pystock_exchange/order.pystock_exchange/order_book.pystock_exchange/side.pystock_exchange/time_in_force.pystock_exchange/trade.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI14 files290 lines

Explorer

• C#AllInOne.cs
• src
• C#Command.cs
• C#CommandType.cs
• C#Depth.cs
• C#Exchange.cs
• C#Order.cs
• C#OrderBook.cs
• C#Side.cs
• C#TimedOrderBook.cs
• C#TimeInForce.cs
• C#Trade.cs

C#AllInOne.cs

AllInOne.cssrc/Command.cssrc/CommandType.cssrc/Depth.cssrc/Exchange.cssrc/Order.cssrc/OrderBook.cssrc/Side.cssrc/TimedOrderBook.cssrc/TimeInForce.cssrc/Trade.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI11 files237 lines

Explorer

• Goall_in_one.go
• Goaction.go
• Gobook_side.go
• Gocommand.go
• Godepth.go
• Goexchange.go
• Golevel.go
• Goorder.go
• Goorder_book.go
• Goside.go
• Gosymbol_book.go
• Gotime_in_force.go
• Gotrade.go

Goall_in_one.go

all_in_one.goaction.gobook_side.gocommand.godepth.goexchange.golevel.goorder.goorder_book.goside.gosymbol_book.gotime_in_force.gotrade.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI13 files390 lines

Explorer

• TSall-in-one.ts
• src
• TSbook-side.ts
• TScommand.ts
• TSdepth.ts
• TSexchange.ts
• TSorder-book.ts
• TSorder.ts
• TSside.ts
• TStime-in-force.ts
• TStimed-order-book.ts
• TStrade.ts

TSall-in-one.ts

all-in-one.tssrc/book-side.tssrc/command.tssrc/depth.tssrc/exchange.tssrc/order-book.tssrc/order.tssrc/side.tssrc/time-in-force.tssrc/timed-order-book.tssrc/trade.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI11 files293 lines

Three ideas hold it together:

• Price-time priority is the structure, not a check. Sorted levels with FIFO queues mean the matching loop can only take the next fair order. There’s no rule to forget.
• The book is pure. It has no clock, no threads and no input or output, so it’s easy to test, and replays exactly. A market order is built as a limit order with the right settings, by a small factory method.
• The journal is the truth. Books and trades can always be rebuilt from the numbered requests, stored as Commands. Gateways call one object, safely, from many threads (Facade).

Stress it

So far, one stock and one caller. Now orders for thousands of stocks arrive from many gateways at once.

Two buys for the last 100 shares

Interviewerminute 23

Orders for thousands of stocks arrive from many gateways at once. Two gateways send a buy for the last 100 shares at the same moment. Walk me through what happens. And if the machine crashes, how do you rebuild the books?

What they are testing

Whether you keep matching one at a time per book, while letting different books run in parallel. And whether you see that the sequence of accepted orders is the real state of the exchange. The red flags: a lock per order, one global lock, or a sequence number taken outside the lock.

The Exchange holds one book per symbol, and is what gateways call.

Two orders, one resting quantity. Both buys look at the best ask, both see 100 shares, and both take them. The shares are sold twice, the resting order’s remaining quantity goes negative, and two trades are reported for one order. It’s a check and a change that must be one step, as always. But here the step is the whole match: it may read and change dozens of orders across several levels.

The clearly correct fix: one book is matched by one thread at a time. Each symbol’s book has its own lock, held for the whole submit or cancel. Orders for one stock are matched strictly one after another. That’s what price-time priority means anyway: there must be one agreed order of arrival. Orders for different stocks take different locks, and run in parallel. So a busy stock never slows a quiet one.

The better fix adds a journal you can replay. Each accepted request becomes a Command (submit or cancel, with every detail of the order), and gets a sequence number. The commands, in sequence order, are the journal. Matching depends on nothing but the commands and their order. There’s no clock, and no randomness. So replaying the journal on an empty exchange rebuilds every book and every trade exactly. That’s how an exchange recovers from a crash. It’s also how a standby machine stays ready to take over. This is the Command pattern used for what it’s best at: a request as data, so it can be recorded, numbered and run again.

Stage 5: the exchange

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

The sequence number must be taken under the book’s lock. Suppose gateway A took number 7, and gateway B took number 8, but B reached the book first. Replay would run A first, and produce different trades. So take the number and record the command while holding the book’s lock. Then the sequence order, for each symbol, is exactly the order the book processed.

Sequence: two buys for the last shares

Scroll or pinch to zoom, drag to pan

• Color key
• Facade

Option	How	Correct?	Cost
1. A lock per book (our choice)	One lock held for each whole match	Yes	One stock’s orders go one at a time, as they must
2. One lock for the exchange	Simplest	Yes	Every stock waits for every other
3. A lock per order or level	Lock what you touch	No	A match touches many; deadlocks and half-done trades
4. A thread per book with a queue	Gateways add to a queue; one thread empties it	Yes	The usual shape in real engines; more machinery
5. Lock-free compare-and-set	Retry on conflict	Hard	Changes to many orders don’t fit one atomic step

JExchange.javaPyexchange.pyC#Exchange.csGoexchange.goTSexchange.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The two kinds of request the journal records.
enum Action { SUBMIT, CANCEL }

// One accepted request, numbered. The journal of these is the exchange's source of truth:
// replaying it in sequence order rebuilds every book and every trade exactly.
record Command(long seq, String symbol, Action action, String id, Side side, long price, long quantity, TimeInForce tif) {}

// Many gateways send orders at once. Matching must see one symbol's orders one at a time, in a
// single agreed order, or two orders can both take the same resting quantity. So each symbol's
// book has its own lock: orders for different symbols never wait for each other. The sequence
// number is taken under that lock too, so sequence order is exactly the order the book saw.
class Exchange {
    // One symbol's book and its trades. Its monitor is that symbol's lock.
    private static final class Book {
        final OrderBook book = new OrderBook();
        final List<Trade> trades = new ArrayList<>();
    }

    private final ConcurrentHashMap<String, Book> books = new ConcurrentHashMap<>();
    private final AtomicLong sequence = new AtomicLong();
    private final ConcurrentLinkedQueue<Command> journal = new ConcurrentLinkedQueue<>();

    List<Trade> submit(String symbol, Order o) {
        Book b = books.computeIfAbsent(symbol, s -> new Book());
        synchronized (b) {
            journal.add(new Command(sequence.incrementAndGet(), symbol, Action.SUBMIT, o.id, o.side, o.price, o.quantity, o.tif));
            List<Trade> trades = b.book.submit(o);
            b.trades.addAll(trades);
            return trades;
        }
    }

    boolean cancel(String symbol, String id) {
        Book b = books.computeIfAbsent(symbol, s -> new Book());
        synchronized (b) {
            journal.add(new Command(sequence.incrementAndGet(), symbol, Action.CANCEL, id, null, 0, 0, null));
            return b.book.cancel(id);
        }
    }

    List<Trade> trades(String symbol) {
        Book b = books.computeIfAbsent(symbol, s -> new Book());
        synchronized (b) {
            return List.copyOf(b.trades);
        }
    }

    // Two symbols add to the queue at the same time, so entries can land slightly out of order.
    // Sorting by sequence number gives the one true order.
    List<Command> journal() {
        return journal.stream().sorted(Comparator.comparingLong(Command::seq)).toList();
    }

    // After a crash, or on a standby machine: the same commands in the same order give the same
    // books and the same trades, because matching depends on nothing else.
    static Exchange replay(List<Command> commands) {
        Exchange e = new Exchange();
        for (Command c : commands) {
            if (c.action() == Action.SUBMIT) e.submit(c.symbol(), new Order(c.id(), c.side(), c.price(), c.quantity(), c.tif()));
            else e.cancel(c.symbol(), c.id());
        }
        return e;
    }
}

Why is this correct? Under the book’s lock, one match reads and changes the resting orders, and finishes, before the next match starts. The second buy sees the quantity the first one left, so no share is sold twice. And since each command is numbered inside the same lock, the journal holds the book’s commands in the exact order the book ran them.

What does it cost? One stock’s orders go one at a time, which price-time priority needs anyway. Different symbols may record their commands slightly out of numeric order, so the journal is sorted by number when read. Commands for different symbols never affect each other, so their relative order doesn’t change any trade.

Go deeperHow each language does it1 min

In Java, Python, C# and Go, gateways run on their own threads, so each book’s lock is needed. TypeScript runs one callback at a time, and submit has no await inside it. So each order is matched completely before the next starts, and no lock is needed. That’s option 4 in miniature. Real engines are single-threaded per book on purpose. A thread that never waits for a lock is the fastest way to match.

How you’d prove it works

The book is pure, so most tests are a few orders and an expected list of trades. Tiny books whose answer is obvious test the priority rules. The tests that matter:

• With asks at 105 and then 100, a buy at 110 trades at 100: the best price, and the resting price.
• At one price, the older order fills first.
• A large buy walks several levels, and rests the rest at its limit.
• Orders that don’t cross both rest, and the best bid and ask are right.
• Cancel works once, and the cancelled order can’t trade.
• Reducing an order keeps its place. Growing it sends it behind newer orders.
• IOC and market orders never rest, and a market order takes the best price, however high.
• FOK fills completely or not at all, and leaves the book untouched when refused.
• Depth adds up each level, best first.
• Eight gateways send 400 orders each for two symbols, with cancels mixed in. No order fills more than its size, and replaying the journal gives exactly the same trades.

Go deeperThe tests in five languages2 min

The last test fails in Java, Python and Go if the book’s lock is removed: orders fill beyond their size, or the replayed trades differ. Replay is a strong test, because it checks determinism and the journal at once.

JMain.javaPyexample.pyC#Program.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

static Order buy(String id, long price, long qty) { return Order.limit(id, Side.BUY, price, qty); }

static Order sell(String id, long price, long qty) { return Order.limit(id, Side.SELL, price, qty); }

@Test
void theBestPriceTradesFirstAtTheRestingPrice() {
    OrderBook book = new OrderBook();
    book.submit(sell("s1", 105, 10));
    book.submit(sell("s2", 100, 10));
    List<Trade> trades = book.submit(buy("b1", 110, 10));
    assertEquals(List.of(new Trade("b1", "s2", 100, 10)), trades);  // 100, not the first-listed 105
    assertEquals(Long.valueOf(105), book.bestAsk());
}

@Test
void atOnePriceTheOldestOrderTradesFirst() {
    OrderBook book = new OrderBook();
    book.submit(sell("early", 100, 5));
    book.submit(sell("late", 100, 5));
    assertEquals("early", book.submit(buy("b", 100, 5)).get(0).sellId());
}

@Test
void aLargeOrderWalksTheBookAndRestsTheRest() {
    OrderBook book = new OrderBook();
    book.submit(sell("s1", 100, 3));
    book.submit(sell("s2", 101, 3));
    book.submit(sell("s3", 103, 3));
    List<Trade> trades = book.submit(buy("b", 101, 10));
    assertEquals(List.of(new Trade("b", "s1", 100, 3), new Trade("b", "s2", 101, 3)), trades);
    assertEquals(Long.valueOf(101), book.bestBid());  // 4 left, resting at its limit
    assertEquals(Long.valueOf(103), book.bestAsk());
}

@Test
void ordersThatDontCrossRest() {
    OrderBook book = new OrderBook();
    assertTrue(book.submit(buy("b", 99, 5)).isEmpty());
    assertTrue(book.submit(sell("s", 101, 5)).isEmpty());
    assertEquals(Long.valueOf(99), book.bestBid());
    assertEquals(Long.valueOf(101), book.bestAsk());
}

@Test
void cancelRemovesARestingOrderOnce() {
    OrderBook book = new OrderBook();
    book.submit(sell("s1", 100, 5));
    assertTrue(book.cancel("s1"));
    assertFalse(book.cancel("s1"));
    assertNull(book.bestAsk());
    assertTrue(book.submit(buy("b", 100, 5)).isEmpty());
}

@Test
void reducingKeepsPriorityAndRepricingLosesIt() {
    OrderBook book = new OrderBook();
    book.submit(sell("a", 100, 10));
    book.submit(sell("b", 100, 10));
    book.modify("a", 100, 4);  // smaller: keeps its place
    assertEquals("a", book.submit(buy("x", 100, 4)).get(0).sellId());
    book.submit(sell("c", 100, 10));
    book.modify("b", 100, 20);  // bigger: to the back, behind c
    assertEquals("c", book.submit(buy("y", 100, 1)).get(0).sellId());
}

@Test
void iocAndMarketOrdersNeverRest() {
    OrderBook book = new OrderBook();
    book.submit(sell("s", 100, 5));
    List<Trade> ioc = book.submit(new Order("i", Side.BUY, 100, 8, TimeInForce.IOC));
    assertEquals(5, ioc.get(0).quantity());
    assertNull(book.bestBid());  // the other 3 were dropped
    book.submit(sell("s2", 120, 5));
    assertEquals(120, book.submit(Order.market("m", Side.BUY, 2)).get(0).price());
}

@Test
void fillOrKillIsAllOrNothing() {
    OrderBook book = new OrderBook();
    book.submit(sell("s1", 100, 3));
    book.submit(sell("s2", 101, 3));
    assertTrue(book.submit(new Order("f1", Side.BUY, 101, 7, TimeInForce.FOK)).isEmpty());
    assertEquals(List.of(new Depth(100, 3), new Depth(101, 3)), book.depth(Side.SELL, 5));  // untouched
    assertEquals(2, book.submit(new Order("f2", Side.BUY, 101, 6, TimeInForce.FOK)).size());
}

@Test
void depthSumsEachLevelBestFirst() {
    OrderBook book = new OrderBook();
    book.submit(buy("a", 99, 5));
    book.submit(buy("b", 99, 2));
    book.submit(buy("c", 98, 4));
    book.submit(buy("d", 97, 1));
    assertEquals(List.of(new Depth(99, 7), new Depth(98, 4)), book.depth(Side.BUY, 2));
}

@Test
void concurrentOrdersMatchExactlyAsTheJournalReplays() throws Exception {
    Exchange exchange = new Exchange();
    Map<String, Long> sizes = new ConcurrentHashMap<>();
    List<Thread> threads = new ArrayList<>();
    for (int t = 0; t < 8; t++) {
        int gateway = t;
        Thread th = new Thread(() -> {
            Random random = new Random(gateway);
            for (int i = 0; i < 400; i++) {
                String id = gateway + "-" + i;
                long qty = 1 + random.nextInt(10);
                sizes.put(id, qty);
                Side side = random.nextBoolean() ? Side.BUY : Side.SELL;
                String symbol = i % 2 == 0 ? "ACME" : "GLOBEX";
                exchange.submit(symbol, Order.limit(id, side, 99 + random.nextInt(3), qty));
                if (i % 7 == 0) exchange.cancel(symbol, gateway + "-" + (i - 3));
            }
        });
        th.start();
        threads.add(th);
    }
    for (Thread th : threads) th.join();
    Exchange replayed = Exchange.replay(exchange.journal());
    for (String symbol : List.of("ACME", "GLOBEX")) {
        List<Trade> trades = exchange.trades(symbol);
        assertFalse(trades.isEmpty());
        Map<String, Long> filled = new HashMap<>();
        for (Trade tr : trades) {
            filled.merge(tr.buyId(), tr.quantity(), Long::sum);
            filled.merge(tr.sellId(), tr.quantity(), Long::sum);
        }
        filled.forEach((id, qty) -> assertTrue(qty <= sizes.get(id)));  // nothing overfilled
        assertEquals(trades, replayed.trades(symbol));
    }
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
A buy below the best ask	Rests; no trade	submit
A buy that crosses several levels	Fills best first, rests the rest at its limit	match
Two orders at one price	The older fills first	the level’s queue
Cancel a filled or unknown order	Returns false	resting index
Cancel twice	The second returns false	resting index
The last order at a price is removed	The level is removed, so the best price moves on	cancel, match
Modify to a smaller size, same price	Keeps its place	modify
Modify to a new price that crosses	Trades at once	modify via submit
IOC with nothing to match	No trades, nothing rests	submit
FOK with not enough available	No trades at all; the book is untouched	fillable
A market order on an empty side	No trades; it never rests	IOC
Two gateways racing for the last shares	One fills, the other rests	the book’s lock
A crash	Replay the journal	replay

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
Priority	Price, then time; trade at the resting price	Pro-rata and other ways of sharing
The book	A sorted map of price levels, each a FIFO queue	The memory-hungry speed of a tick array
Cancel	An index by id	Nothing: it’s cheap and essential
Modify	Keep priority only when smaller at the same price	Letting traders grow orders in place
Order types	A time-in-force field on one matching loop	Separate classes per order type
Concurrency	A lock per book; sequence numbers under it	Parallel matching inside one book
Recovery	A numbered journal that replays to the same trades	Storing the books themselves

Go deeperGenuinely different designs, and when to pick them2 min

A single-threaded engine per group of symbols. Real exchanges, such as the LMAX design, run each group of books on one thread. It reads commands from a ring buffer, with no locks at all. The journal is written before matching, and copied to a standby machine, which replays the same commands. It’s the fastest design there is. It’s option 4 from the table, taken seriously.

An array of levels indexed by tick. Say the tick size is fixed, and prices stay within a band. Then an array slot per tick gives constant-time access to any level, and the best price is a moving pointer. It’s faster than a tree, and uses more memory.

Event sourcing everything. The journal already is event sourcing for the books. Extending it, so trades, cancels and market data are all worked out from the journal, gives a perfect record of everything, which regulators require.

How to spend 45 minutes

• 0 to 3. Scope to matching. Price-time priority. Order types. Prices in ticks.
• 3 to 5. The promises. Name “no share sold twice, fair order” as the hard one.
• 5 to 23. Two lists and their problems. Sorted levels with queues. Cancel with an index, and the modify rule. Then time in force, and depth. Code submit and its matching loop.
• 23 to 25. Walk through the full diagram.
• 25 to 31. The race for the last shares, a lock per book, the journal, and the sequence number under the lock.
• 31 to 45. Stop orders or another extension, then your own questions.

If time is short, describe the order types in a sentence, and spend the time on the matching loop and the lock. Those decide this question for most interviewers.

Follow-up questions

Interviewerminute 31

Add stop orders: sell if the price falls to 95. Where do they live?

What they are testing

Whether you keep stops out of the book, since they aren’t offers to trade yet, and trigger them from trades. And whether you see that triggered stops must go through the same sequence as any order, or replay breaks.

Most extensions fit into one place:

Extension	What changes	Touches matching?
Stop orders	A trigger map beside the book, checked after each trade	No
Iceberg orders	Show part of the size; refill from the hidden part, at the back of line	Slightly
Self-trade prevention	Before trading with your own order, cancel one of them	One check
Market data feed	Each trade and level change becomes an event for subscribers	No
Opening auction	Collect orders, then find the one price that trades the most	A separate step
Pro-rata matching	A level splits a fill by size instead of by time	The level only

Go deeperAdding stop orders, step by step2 min

A stop order says “if the price falls to 95, sell”. Until then, it isn’t an offer to trade.

1. Keep stops out of the book. If a stop rested in the book, others could trade with it before it was triggered. So stops wait in their own sorted map, by trigger price, beside the book.
2. Check the triggers after each trade. The last trade’s price is the market price. After each match, the book looks at the stops whose trigger that price has crossed. Because the map is sorted, this looks only at stops that fire, never at the rest.
3. A triggered stop becomes a normal order. That’s usually a market order (sell at any price). Or a limit order, if the trader set a limit too.
4. Submit it as a new command, in sequence. It goes into the journal with its own number, like any order from a gateway. That’s what makes replay trigger it at exactly the same moment. If the book just matched it quietly inside the current match, replay would still work, but the journal would no longer show what happened.
5. Watch for chains. A triggered stop’s trade can move the price again, and trigger more stops. Each one is a new command, handled in turn, so the chain is processed in a clear order rather than all at once.

The matching loop doesn’t change. Stops are a layer that watches trades, and feeds new orders in.

Go deeperFour more follow-up questions2 min

Interviewer asksHow fast is this?

An order costs a logarithmic lookup for its price level, plus a constant amount for each order it fills. Cancel is a hash lookup. In memory, that’s a few microseconds per order. Real engines get under a microsecond by using arrays and one thread per book, with no locks.

Interviewer asksWhat if the gateway sends the same order twice?

Order ids are unique per trader, so the exchange keeps the ids it has seen, and refuses a repeat. The book’s resting index already refuses a second cancel. A submit needs the same check before matching, or a network retry would buy the shares twice.

Interviewer asksWhy is the trade at the resting price, not the midpoint?

The resting order made a firm offer at its price, and the incoming order chose to accept it. Trading at the incoming order’s limit would punish it for being willing to pay more. Trading at the midpoint would give the resting order a price it never asked for. Every major exchange uses the resting price.

Interviewer asksHow do you publish the book to traders?

Every trade and every change to a level is an event: price, side, and new total quantity. Subscribers apply the changes to their own copy of the depth. The engine never waits for them: events go to a queue after matching, in sequence order, so a slow subscriber can’t slow the book.

Further reading

• Command pattern, requests as data that can be recorded and replayed
• Design a movie ticket booking system, another design where two people race for the same thing
• Design a task scheduler, another engine ordered by priority, then time