Design a Stock Exchange

Design the core of an electronic stock exchange. Brokerage firms connect over persistent sessions and send buy and sell orders, amendments and cancels for a few thousand listed stocks. The exchange matches buyers with sellers, confirms each fill back to both sides, and publishes a live market data feed of quotes and trades that thousands of firms consume.

Everything is judged on fairness and determinism: orders must be processed in the exact sequence they arrived, the same input must always produce the same trades, and no trade may ever be lost or duplicated. Members also care about latency in microseconds, and volume spikes sharply at the opening and closing auctions and on news.

In 45 minutes, cover requirements and sizing, the order path from gateway to match, how the order book works, how you achieve both durability and low latency, and how market data is distributed.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Commerce & Payments · problem 34 of 70

Ask before you design. Try answering each yourself, then compare.

1. Which order types?
   Typical answer

   Limit and market orders, plus cancel and cancel/replace. Stop orders and auctions are follow-ups.

2. Who connects to us?
   Typical answer

   Member brokerage firms over dedicated lines using a FIX or binary protocol; retail investors reach us only through brokers.

3. What volume?
   Typical answer

   About 500 million order messages a day across ~5,000 symbols, peaking above 250,000 messages per second at the open.

4. What latency target?
   Typical answer

   Gateway-in to acknowledgement under ~100 microseconds at the median and under 1 ms at p99, inside the data centre.

5. Do we handle clearing and settlement?
   Typical answer

   No. We send trade records to a clearing house; settlement happens there.

6. What availability?
   Typical answer

   Trading hours only, but an outage during hours is very serious: fail over within seconds with no lost or duplicated trades.

7. Does the system run across regions?
   Typical answer

   One primary data centre with a hot standby in a second site; members co-locate near the primary.

Requirements

Functional

• Accept new, cancel and cancel/replace orders for limit and market types, with acknowledgements.
• Match orders per symbol with price-time priority; report fills to both sides.
• Apply pre-trade risk checks per member (credit limits, max order size, price collars).
• Publish market data: top of book, depth updates and trades, in sequence.
• Send trade records to clearing and keep an auditable record of every message.

Non-functional

• Deterministic, fair sequencing: a total order of events per symbol, replayable exactly.
• Order-to-ack latency ~100 µs median, under 1 ms p99 inside the data centre.
• Sustain 250,000+ messages per second at peak with headroom for 3x microbursts.
• No lost or duplicated orders or trades; failover to standby within seconds.
• Market data delivered to all subscribers at the same time from the same source.

Out of scope

• Clearing, settlement and custody.
• Broker-side apps for retail investors.
• Surveillance analytics (consume the audit stream later).

Back-of-the-envelope estimates

• Order flow: 500 M messages over a 6.5-hour session ≈ 21,000 per second on average; the open and close concentrate flow, so plan for 250,000 per second sustained and short bursts near 1 M per second.
• Per engine: a single-threaded matching loop on an in-memory book handles a few million simple operations per second, so one core per group of symbols is plenty; the busiest symbol, perhaps 5% of flow, gets its own core.
• Journal: ~200 bytes per message ≈ 100 GB per day, ~25 TB per year over ~250 trading days, kept 7 years for audit (~175 TB).
• Market data: each order event produces one or more book updates, ~20 outbound messages per inbound message counting all subscriber feeds; multicast keeps that one packet per update on the wire regardless of subscriber count.
• Latency budget: ~100 µs total: a few µs in the gateway, ~10 µs for risk, ~20 µs for sequencing and replication, a few µs to match, and the rest in the network.

The latency budget, not the volume, drives the design: no database, no locks and no cross-machine call on the critical path except the replication of the input sequence.

API

Session (FIX / binary over TCP, one per member connection):
  NewOrder      {clOrdId, symbol, side, qty, type: LIMIT|MARKET, price?, timeInForce}
  Cancel        {clOrdId, origClOrdId}
  CancelReplace {clOrdId, origClOrdId, qty, price}
  <- ExecReport {clOrdId, orderId, status: NEW|PARTIAL|FILLED|CANCELED|REJECTED,
                 lastQty, lastPx, leavesQty, seqNo}
Market data (UDP multicast per symbol group, with TCP replay service):
  BookUpdate {seq, symbol, side, price, qtyAtLevel}   Trade {seq, symbol, price, qty}

Members tag each order with their own unique clOrdId; the gateway rejects duplicates per session, which makes reconnect-and-resend safe without double orders.

Data model

Event journal (the source of truth): an append-only, sequenced log of every inbound command and every outbound event, (seq, timestamp, session, type, payload), partitioned by symbol group and replicated synchronously to the standby before an order is acknowledged. Everything else can be rebuilt by replaying it.

Order book (in memory, per symbol): for each side, price levels kept sorted, each a FIFO queue of resting orders (orderId, member, remainingQty, entrySeq), plus a hash from order id to its node for O(1) cancel. Prices are integer ticks.

Risk state (in memory, per member): open exposure, credit limits and per-symbol position, loaded at start of day from the reference database and updated by fills.

Post-trade stores (off the critical path): trades and order history in a relational or columnar database, written by a consumer of the journal for clearing files, member reports and audit queries.

High-level design

Entering an order. A member's trading system sends a NewOrder over its session to an order gateway, which validates the message, checks the client order id is unique for the session, and stamps an arrival time. Pre-trade risk checks the order against that member's credit limit and price collars using in-memory state, and rejects immediately if it fails.

Sequencing. Accepted orders go to the sequencer for their symbol group. The sequencer assigns the next sequence number and appends the command to the event journal, which replicates it to the standby site before the order proceeds. This single ordering point is what makes the market fair and replayable.

Matching. The matching engine, one thread owning a set of symbols with their books in memory, takes commands in sequence order. A buy limit order is compared with the lowest ask; while prices cross it fills against the oldest order at the best price, then any remainder rests on the book. Each fill and book change becomes an output event.

Results out. Execution reports go back through the gateway to both members. The market data publisher turns book changes and trades into sequenced multicast packets that all subscribers receive at once, with a replay service for gaps. A post-trade consumer reads the journal and writes trades and orders to the post-trade database and the clearing house. A standby engine consumes the same journal and keeps identical books, ready to take over.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

The order book and price-time priority

Each side of the book is a sorted map from price to a FIFO queue of resting orders. A buy at 100.50 checks the best ask: while the best ask is at or below 100.50 and quantity remains, fill against the head of that level's queue, then move to the next level. Leftover quantity rests at 100.50, at the back of its queue. Keep a hash from order id to its queue node so cancels are O(1). Best price lookups are O(1) with a pointer to the top level; inserting a new level is O(log n) with a tree or O(1) with an array indexed by tick offset around the current price. Amending price or increasing quantity loses time priority; decreasing quantity keeps it.

Deterministic engine and fast failover

Make the matching engine a pure state machine: its output depends only on the ordered input commands, with no clocks, randomness or external calls inside. Timestamps come from the sequencer and are part of the input. Then durability comes from journalling the input, not the book: replay the journal and you get the same books and the same trades. A hot standby consumes the replicated journal in lockstep, so on failure it already holds identical books; promotion is a matter of switching which instance publishes output, gated by sequence numbers so no event is emitted twice. Periodic snapshots of the books shorten cold restarts.

Low latency on the critical path

Keep each book owned by one pinned CPU core so there are no locks or context switches. Pass messages between gateway, risk, sequencer and engine through pre-allocated ring buffers rather than queues that allocate memory. Avoid garbage-collection pauses by reusing objects or using a language without a GC. Replicate the journal with kernel-bypass networking to a nearby standby and acknowledge once it has the entry in memory, writing to local disk asynchronously; two copies in memory on separate machines is the durability promise. Measure with hardware timestamps at every hop and watch the p99 more than the median.

Market data distribution

Thousands of subscribers need the same updates at the same time, and fairness rules forbid giving some firms an earlier view. Publish over UDP multicast so one packet reaches every subscriber on the network, split into channels by symbol group. Every packet carries a sequence number; a subscriber that sees a gap requests the missing range from a TCP replay service or rejoins from a periodic full-book snapshot channel. Offer two feeds: top of book for most consumers, and full depth for those who need it. Slow subscribers do not slow the publisher, since multicast does not wait.

Failure modes

• If the primary matching engine fails, the standby, which has applied the same journal, is promoted within seconds and resumes from the next sequence number.
• If a gateway fails, members reconnect to another gateway and resend unacknowledged orders; duplicate client order ids are rejected, so nothing is entered twice.
• If a subscriber misses multicast packets, it detects the sequence gap and recovers from the replay service or a snapshot.
• If the post-trade database falls behind, trading continues; the consumer catches up from the journal, which is the source of truth.
• If the market becomes disorderly (a runaway algorithm), circuit breakers halt the symbol and the engine cancels or rejects orders until reopening.

Core algorithm in code

import bisect
from collections import deque


class OrderBook:
    """Limit order book for one symbol with price-time priority.

    Each side keeps a sorted list of price levels and, per level, a FIFO queue of resting
    orders. An incoming order matches against the best opposite price first and, within a
    price, the oldest order first. Prices are integer ticks (cents), never floats. A real
    engine is single-threaded per symbol and fed by a sequencer, so no locks are needed."""
    def __init__(self, symbol):
        self.symbol = symbol
        self.levels = {"B": {}, "S": {}}        # side -> price -> deque[[oid, qty]]
        self.prices = {"B": [], "S": []}        # sorted ascending
        self.index = {}                         # oid -> (side, price)
        self.seq = 0

    def _best(self, side):
        p = self.prices[side]
        if not p:
            return None
        return p[-1] if side == "B" else p[0]

    def _rest(self, oid, side, price, qty):
        if price not in self.levels[side]:
            self.levels[side][price] = deque()
            bisect.insort(self.prices[side], price)
        self.levels[side][price].append([oid, qty])
        self.index[oid] = (side, price)

    def _drop_level(self, side, price):
        del self.levels[side][price]
        self.prices[side].remove(price)

    def submit(self, oid, side, qty, price=None):
        other = "S" if side == "B" else "B"
        trades = []
        while qty > 0:
            best = self._best(other)
            if best is None:
                break
            if price is not None and ((side == "B" and best > price) or (side == "S" and best < price)):
                break                           # limit price not marketable any more
            queue = self.levels[other][best]
            maker = queue[0]
            fill = min(qty, maker[1])
            self.seq += 1
            trades.append((self.seq, self.symbol, best, fill, oid if side == "B" else maker[0],
                           maker[0] if side == "B" else oid))
            qty -= fill
            maker[1] -= fill
            if maker[1] == 0:
                queue.popleft()
                del self.index[maker[0]]
                if not queue:
                    self._drop_level(other, best)
        if qty > 0 and price is not None:
            self._rest(oid, side, price, qty)   # remainder of a limit order rests
        return trades                           # remainder of a market order is cancelled

    def cancel(self, oid):
        if oid not in self.index:
            return False
        side, price = self.index.pop(oid)
        queue = self.levels[side][price]
        for i, (o, _) in enumerate(queue):
            if o == oid:
                del queue[i]
                break
        if not queue:
            self._drop_level(side, price)
        return True

    def depth(self, side, n=3):
        ps = self.prices[side][::-1] if side == "B" else self.prices[side]
        return [(p, sum(q for _, q in self.levels[side][p])) for p in ps[:n]]


def show(trades):
    for seq, sym, px, qty, buyer, seller in trades:
        print("   trade #%d %s %d @ %.2f  buyer=%s seller=%s" % (seq, sym, qty, px / 100, buyer, seller))


book = OrderBook("ACME")
book.submit("s1", "S", 300, 10050)
book.submit("s2", "S", 200, 10050)              # same price, later: behind s1
book.submit("s3", "S", 500, 10075)
book.submit("b1", "B", 400, 10000)
book.submit("b2", "B", 100, 10025)
print("bids", book.depth("B"), "asks", book.depth("S"))
print("buy 450 limit 100.50 (fills s1 fully, then part of s2):")
show(book.submit("b3", "B", 450, 10050))
print("cancel s3:", book.cancel("s3"), "| cancel s3 again:", book.cancel("s3"))
print("market sell 600 sweeps the bids best price first:")
show(book.submit("m1", "S", 600))
print("bids", book.depth("B"), "asks", book.depth("S"))

Trade-offs

• Single-threaded matching per symbol gives determinism and microsecond latency but caps throughput per symbol at one core.
• Acknowledging after replication to the standby's memory gives low latency but relies on two machines not failing together, unlike a disk fsync per order.
• A central sequencer gives a fair total order but is a single point that must be made highly available and very fast.
• Multicast market data is fair and scales to any number of subscribers but needs gap detection and a replay service because UDP can drop packets.
• Keeping risk checks in memory at the gateway is fast but means limits for a member that trades across gateways must be partitioned or synchronised.

What a strong answer shows

• Puts a single sequencer per symbol group in front of matching and explains why it gives fairness and replay.
• Describes the order book data structures and price-time priority correctly, including cancel complexity.
• Gets durability from a replicated input journal rather than a database on the critical path.
• Explains deterministic replay as the basis for hot standby failover.
• Designs market data with multicast, sequence numbers and gap recovery.
• Keeps risk checks, post-trade processing and storage placed sensibly relative to the latency budget.

Mistakes to avoid

• Storing the order book in a database and matching with SQL queries.
• Running several threads that lock the same book, losing determinism and latency.
• Using floating-point prices.
• Forgetting that a failover must not re-emit or lose trades.
• Pushing market data over individual TCP connections to every subscriber from the engine.

Follow-ups to expect

• How would you run the opening auction? (Collect orders without matching, then compute the single price that maximises matched volume.)
• How do you add stop orders? (Hold them off-book and inject them as market or limit orders when a trade crosses the trigger.)
• How would you shard across more symbols? (Assign symbol groups to engines; rebalance only between sessions.)
• How do you prevent a member from flooding the gateway? (Per-session message rate throttles and order-to-trade ratio limits.)
• How would you prove an engine bug did not change results? (Replay the day's journal through both versions and diff outputs.)

Practice next