Design a Stock Exchange

A stock exchange matches buy orders and sell orders for securities. Participants (brokers) send orders. The exchange decides which orders trade against each other, at what price, and publishes the result. The design is unusual because correctness and determinism matter more than horizontal scale: a single ordered stream of events per symbol must be processed exactly once, in a fixed order, with very low and predictable latency.

Requirements

Functional

• Place a limit order (buy or sell a quantity at a price or better) and a market order (trade immediately at the best available prices).
• Cancel an existing order.
• Match orders using price-time priority: the best price wins; at equal prices, the earlier order wins.
• Publish executions (fills) to the parties involved and publish market data (order book levels and trades) to all subscribers.
• Support a list of symbols, on the order of a few thousand.

Non-functional

• Latency. Order-to-acknowledgement in the range of tens to hundreds of microseconds inside the matching path; low variance (tail latency) matters as much as the average.
• Throughput. Tens of thousands to hundreds of thousands of orders per second for the whole exchange, with bursts at market open and close.
• Correctness. No lost, duplicated, or reordered orders. Every fill is exact, and every participant sees a consistent history.
• Availability. Failover within seconds, with no loss of accepted orders. The market is only open for set hours, so maintenance windows exist.
• Fairness and auditability. Strict ordering by arrival, and a complete, immutable log of every event for regulators.

Estimation

Assumptions: 2,000 symbols, 1 billion orders per day, a 6.5-hour trading day (23,400 seconds).

• Average order rate: 1,000,000,000 / 23,400 ≈ 43,000 orders per second.
• Peak, assuming 10x at open and close: about 430,000 orders per second.
• Each order event is roughly 100 bytes. Daily log volume: 1,000,000,000 × 100 B = 100 GB per day for orders alone. Cancels, fills, and market data multiply this by a small factor, so the event log is on the order of a few hundred GB per day.
• Market data fan-out: if one order changes the book and is sent to 1,000 subscribers, 430,000 × 1,000 = 430 million messages per second at peak. This is why market data uses multicast or heavy batching rather than per-subscriber unicast.

Conclusion: the matching workload for one symbol fits on one CPU core, because matching one order takes a few microseconds. The hard parts are latency, ordering, and fan-out, not raw volume.

What the numbers imply

• Matching one order takes a few microseconds, so one core handles on the order of 100,000 or more orders per second. A busy symbol at, say, 5 percent of 430,000 is about 21,000 per second, leaving 5x headroom, so no symbol needs to be split, and none can be (price-time priority needs a single order).
• 430,000 per second across 2,000 symbols means a few symbol groups per core; 8 to 16 engine cores cover the whole exchange, so scale is small and the budget goes to latency and replication.
• A few hundred GB of log per day is written sequentially; a snapshot every minute or so keeps replay bounded: replaying 1 minute at 100,000 events per second is 6 million events, a few seconds at about 1 million events per second replay speed.

API design

Participants connect over persistent, authenticated sessions. Real exchanges typically use the binary FIX-family or proprietary protocols; the logical operations are:

time_in_force states how long the order stays active: for example, day (until the end of the session), good-till-cancelled, or immediate-or-cancel (fill what is possible now and cancel the rest). leaves_quantity is the quantity of the order still unfilled. Level 2 market data lists the aggregate quantity at each price level of the book, as opposed to level 1, which carries only the best bid and ask. client_order_id is chosen by the client and used to detect duplicate submissions after reconnects. Every outbound message carries a sequence number so a receiver can detect gaps and request retransmission.

Data model

The primary state is in memory. Durable state is an append-only event log.

• Order book (per symbol, in memory): two sides, bids and asks. Each side is a sorted map from price to a FIFO queue of resting orders at that price. Bids are sorted highest first, asks lowest first.
• Order index: order_id -> (side, price, position) for O(1) lookup on cancel.
• Event log (durable): an append-only sequence of (sequence_number, event_type, payload). Events are inputs (new order, cancel), never derived state.
• Reference and account data (relational database): symbols, participants, credit limits, positions. Used by risk checks and by post-trade processes, not by the matching loop.
• Trade history (columnar or time-series store): for reporting and audit, populated asynchronously from the event log.

The book itself is not stored in a database. It is rebuilt by replaying the event log (this is event sourcing), and periodic snapshots bound the replay time.

A simple representation: a TreeMap<Integer, ArrayDeque<Order>> per side (price to a FIFO queue) gives O(log P) insertion at a new price level (P = number of price levels) and O(1) appends at an existing level. Prices are stored as integers (for example, multiples of the minimum price increment, called the tick size, or cents) because floating point cannot represent decimal prices exactly.

High-level design

flowchart LR
    C["Clients / brokers"] --> GW["Gateway"]
    GW --> RM["Risk checks"]
    RM --> SEQ["Sequencer"]
    SEQ --> LOG[("Event log")]
    SEQ --> ME["Matching engine (primary)"]
    SEQ --> MEB["Matching engine (hot standby)"]
    ME --> OUT["Outbound events"]
    OUT --> GW
    OUT --> MD["Market data publisher"]
    MD --> SUB["Subscribers"]
    LOG --> RPT["Reporting / audit / settlement"]

Component responsibilities:

• Gateway. Terminates client sessions, authenticates, validates message format, rate limits per participant, deduplicates on client_order_id, and routes execution reports back to the right session.
• Risk checks. Pre-trade checks (available credit, position limits, price sanity bands). Performed before the order enters the matching path so a rejected order never occupies a sequence number.
• Sequencer. Assigns a strictly increasing sequence number to every inbound event and writes it to the event log. It defines the single total order of events. All downstream components consume events in that order.
• Matching engine. A deterministic state machine. Given the same ordered input events, it always produces the same fills and the same book. It is single-threaded per symbol (or per group of symbols).
• Market data publisher. Converts book changes and trades into sequence-numbered public messages and distributes them.
• Reporting and settlement. Consume the event log to produce trade reports, audit trails, and clearing files. They are off the latency-critical path.

Order flow

sequenceDiagram
    participant C as Client
    participant G as Gateway
    participant R as Risk
    participant S as Sequencer
    participant M as Matching engine
    participant D as Market data
    C->>G: NewOrder (buy 100 @ 50)
    G->>R: validate and check limits
    R->>S: accepted order
    S->>S: assign sequence number, append to log
    S->>M: event #1042
    M->>M: match against best asks
    M-->>G: ExecutionReport (fills, or resting)
    G-->>C: ExecutionReport
    M-->>D: trade and book update
    D-->>D: publish to subscribers

Deep dive

1. The order book and matching algorithm

Matching a limit buy at price p against the ask side:

1. While the order has remaining quantity and the lowest ask price is at most p: take the oldest order at the lowest ask level, trade min(remaining, resting quantity) at the resting order's price, and update both quantities.
2. Remove fully filled resting orders and empty price levels.
3. If quantity remains, insert the remainder into the bid side at price p, at the back of the queue for that price.

A market order is the same loop with no price limit; any unfilled remainder is cancelled (or rejected) rather than rested.

Cancel uses the order index to find the price level, then removes the order from that queue. An ArrayDeque makes mid-queue removal O(n) in the level size; production books use intrusive doubly linked lists or slot arrays with tombstones to make it O(1).

The following sketch implements price-time priority for one symbol with integer prices:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    static final class Order {
        final long id;
        int qty;

        Order(long id, int qty) {
            this.id = id;
            this.qty = qty;
        }

        @Override
        public String toString() {
            return "Order[id=" + id + ", qty=" + qty + "]";
        }
    }

    record Fill(long restingId, int price, int qty) {}

    static final class Book {
        // Bids: the highest price is the best bid. Asks: the lowest price is the best ask.
        final TreeMap<Integer, Deque<Order>> bids = new TreeMap<>(java.util.Comparator.reverseOrder());
        final TreeMap<Integer, Deque<Order>> asks = new TreeMap<>();

        /** Matches a buy limit order and returns the fills in execution order. */
        List<Fill> buy(long id, int price, int qty) {
            var fills = new ArrayList<Fill>();
            while (qty > 0 && !asks.isEmpty()) {
                Map.Entry<Integer, Deque<Order>> level = asks.firstEntry();
                int askPrice = level.getKey();
                if (askPrice > price) {
                    break;
                }
                var queue = level.getValue();
                while (qty > 0 && !queue.isEmpty()) {
                    var front = queue.peekFirst();
                    int traded = Math.min(qty, front.qty);
                    front.qty -= traded;
                    qty -= traded;
                    fills.add(new Fill(front.id, askPrice, traded));
                    if (front.qty == 0) {
                        queue.pollFirst();
                    }
                }
                if (queue.isEmpty()) {
                    asks.remove(askPrice);
                }
            }
            if (qty > 0) {
                bids.computeIfAbsent(price, k -> new ArrayDeque<>()).addLast(new Order(id, qty));
            }
            return fills;
        }

        void sellRest(long id, int price, int qty) {
            asks.computeIfAbsent(price, k -> new ArrayDeque<>()).addLast(new Order(id, qty));
        }
    }

    public static void main(String[] args) {
        var book = new Book();
        book.sellRest(1, 101, 50);
        book.sellRest(2, 101, 30);
        book.sellRest(3, 102, 40);
        var fills = book.buy(4, 101, 100);
        System.out.println("fills: " + fills);
        System.out.println("resting bids: " + book.bids);
        System.out.println("remaining asks: " + book.asks);
    }
}

fills: [Fill[restingId=1, price=101, qty=50], Fill[restingId=2, price=101, qty=30]]
resting bids: {101=[Order[id=4, qty=20]]}
remaining asks: {102=[Order[id=3, qty=40]]}

The buy of 100 at 101 consumes orders 1 and 2 (time priority within the level), cannot trade against the 102 ask, and rests the remaining 20 as a bid.

2. Determinism and the sequencer

Two matching engines given the same event sequence must reach the same state. This requires that the engine has no non-deterministic inputs: no wall-clock reads inside matching logic (timestamps come from the sequencer), no iteration over hash maps with random ordering, and no multi-threaded interleaving within a symbol.

Determinism gives three things:

• Replication by replay. A hot standby consumes the same sequenced stream and maintains an identical book. On primary failure, the standby is promoted with no state transfer.
• Recovery. Restart from the latest snapshot and replay the log after it.
• Audit. Any historical state can be reconstructed.

Alternatives for ordering:

Exchanges usually partition by symbol: orders for different symbols never interact, so each symbol group has its own sequencer, engine, and log. Cross-symbol operations (such as participant-level risk limits) are handled in the risk layer, before sequencing.

3. Low latency and single-threaded design

A matching engine avoids the costs that dominate a typical service:

• One thread per engine, pinned to a core. No locks in the matching path. Concurrency is achieved by partitioning symbols, not by sharing a book across threads.
• Everything in memory. No database read or write on the critical path.
• Preallocated, cache-friendly structures. Avoid heap allocation during matching so the Java garbage collector has little to do on the critical path (object pools, primitive arrays, and a low-pause collector such as ZGC reduce pauses).
• Inter-thread communication via ring buffers. A single-producer, single-consumer ring buffer (as in the LMAX Disruptor pattern) passes events between the gateway, sequencer, and engine without locks.
• Journaling off the critical path. The log write can proceed in parallel with matching, but the engine must not release an execution report externally until the event is durable (or replicated to the standby), or a failover could lose a fill the client already saw.

Durability versus latency is the central trade-off. Waiting for a disk write costs microseconds to milliseconds. Replicating the event to the standby's memory over a fast network can be faster than a disk sync, so the common design is to acknowledge after the standby has received the event.

Concrete choices. Replication acknowledgement: the engine releases a fill after the standby confirms receipt in memory, typically tens to hundreds of microseconds in the same data center, versus milliseconds for an fsync per event; group commit (batch several events per disk write) keeps the disk copy asynchronous but bounded. Alternative: Raft across three nodes gives stronger guarantees (a majority has the event) at the cost of a leader round trip per batch; exchanges accept it or use primary plus synchronous standby plus asynchronous disk journal. Consistency model: a single total order per symbol (strict serializability for that symbol); no ordering promised across symbols. Order book structure alternative: sorted array or price-indexed array of levels (prices are bounded integers near the market) gives faster, more cache-friendly access than a tree, since most activity is near the best price.

4. Market data distribution

Market data must reach all subscribers at the same time to be fair, and in order.

• The publisher assigns each message a sequence number per feed.
• Distribution uses multicast within the exchange's network so one send reaches all subscribers. Multicast is unreliable, so a separate retransmission service answers gap requests by sequence number, and a snapshot service provides the current book so a late joiner can synchronize and then apply incremental updates.
• Incremental updates (level-by-level changes) are sent instead of full books.

Public-facing distribution (websites, retail apps) is done by a separate tier that consumes the feed and applies conflation (collapsing several updates to the same price into the latest one) and fan-out over WebSockets, so slow consumers cannot affect the core.

5. Failover

The standby engine lags the primary by at most a few events. On failure detection (heartbeats and a lease held via a coordination service such as leader election with fencing), the standby takes over at the last event it processed. Clients reconnect and reconcile using message sequence numbers: the gateway resends any execution reports the client did not acknowledge. A fencing token or epoch number prevents a slow old primary from continuing to emit fills after the new one is promoted.

Bottlenecks and scaling

• Single hot symbol. One symbol cannot be split across cores without breaking price-time priority. Mitigation: dedicated hardware for the busiest symbols; keep the matching loop minimal.
• Market open and close bursts. Handle with gateway-level queues and per-participant rate limits; auction sessions (opening and closing auctions) collect orders for a period and match them once at a single price, which converts a burst into a batch.
• Fan-out. Multicast and conflation, as above.
• Log growth. Roll segments daily; archive to object storage; snapshots bound replay time.
• Gateways. Stateless apart from session state; scaled horizontally, with consistent routing of a session to the same gateway.

Failure modes

• Primary engine crashes. The standby, at most a few events behind, is promoted after detection (heartbeat timeout of about 1 second, then lease fencing). Clients see a pause of seconds. Accepted orders are safe because acknowledgements were released only after replication. In-flight unacknowledged orders are resent by clients and deduplicated on client_order_id.
• Split brain. Two engines both think they are primary: prevented by an epoch in every message; downstream components reject lower epochs.
• Gateway fails. Sessions reconnect elsewhere and reconcile by sequence number; orders are unaffected since they are not yet sequenced.
• Market data gap. Receivers detect a sequence gap and request retransmission; too large a gap forces a snapshot resync. Two redundant feeds (A and B) let receivers arbitrate and fill gaps from the other.
• Slow consumer. Public fan-out conflates and eventually disconnects it; the core never waits.
• Degradation. Under overload, rate limit per participant and reject rather than queue unboundedly, since stale orders are worse than rejected ones; circuit breakers halt trading if state is uncertain.
• At 10x (4.3 million orders per second peak). Add more symbol groups and engines, each with its own sequencer; hot symbols get dedicated cores; fan-out grows to billions of messages per second, so conflation and tiered distribution become mandatory.

Trade-offs and follow-up questions

• Why not a database for the book? Transactional row updates per order are orders of magnitude too slow and add variable latency. The database is used for reference data and reporting.
• Why not scale matching horizontally for one symbol? Price-time priority requires a single total order of orders for that symbol.
• How are duplicate orders prevented after a reconnect? client_order_id deduplication at the gateway plus sequence numbers on messages.
• What if the sequencer fails? Promote a replica that has the same log; use an epoch number so the old sequencer's late writes are rejected.
• How is fairness verified? The log is the source of truth: replaying it must reproduce the same fills.
• Follow-ups: support for stop orders and iceberg orders (extra order types stored outside the visible book and triggered by price events); circuit breakers that halt trading on rapid price moves; post-trade clearing and settlement, which run asynchronously against the log.
• What if replication to the standby is slow? Latency rises for every order; either accept it or fail over to a healthy standby. Never release fills before durability.
• What if the log disk fills? Alert well ahead; halting is safer than continuing without a journal.
• How do you handle a fat-finger order? Pre-trade risk checks in the gateway (price bands, max size, credit) run in microseconds before sequencing.
• What about the tail latency? Pin threads, limit GC pauses by preallocation, isolate cores, and monitor p99.99, not the mean.