The Interview Book · Careers

26System Design

“Design a matching engine.” Forty-five minutes, a whiteboard, no other words. The candidate who spends five minutes asking how many instruments, how many messages a second at peak, what latency at the ninety-ninth percentile, and what happens when the process dies has already done better than the one who began with the order book’s data structure. System-design interviews at trading firms ask for the systems the series builds: a matching engine and exchange simulator (One Quant Book 10, chapter 26), feed handlers and order gateways (Book 13), market-data distribution, backtesters (Book 7 and Book 15) and risk services. What is scored is the method and the numbers, not a single right architecture.

26.1 The method

Definition 26.1 (System-design interview, capacity estimate)

A system-design interview asks the candidate to design a system from a one-line description within a fixed time, and assesses how requirements are established, how the design is sized, how its components and interfaces are chosen, and how it fails. A capacity estimate is the back-of-envelope calculation of the load a design must carry (messages a second at peak, bytes a day, memory, connections) from stated assumptions, used to choose between designs.

Method 26.2 (Answering a design question)

Requirements: functions (what it must do), scale (instruments, users, messages a second at peak and on average), latency (median and tail), correctness (ordering, exactly-once), availability (what may be lost on failure, how fast to recover).
Capacity: a capacity estimate for messages, bandwidth, memory and storage, with the peak-to-average ratio stated.
Interfaces: the messages in and out, and their sequencing.
Core design: the data structures and the threading model of the critical path first.
Failure: what happens when each component dies, when a consumer is slow, when the network drops packets.
Numbers again: check the design against the capacity estimate and the latency budget.

Example 26.3 (Sizing a feed)

Suppose (assumptions to be stated as such) 200 000 messages a second on average over a 6.5-hour session and 64 bytes a message: $200\,000 \times 23\,400 \times 64 \approx 300$ gigabytes a day to capture. At a peak of one million messages a second the payload alone is 512 megabits a second, and with 42 bytes of Ethernet, IPv4 and UDP headers ( $14 + 20 + 8$ ) per message sent singly, 848 megabits: comfortably inside 10 gigabits, but not inside 1.

26.2 The order book and the matching engine

The matching engine is the question asked most. Its core is a price-time priority book: price levels on each side in sorted order, a first-in-first-out queue of orders within each level, and an index from order identifier to its position so that a cancel costs constant time (Listing 26.1). Around the core sit the pieces that make it an exchange: a sequencer that stamps every inbound message with a single order, a journal that writes the sequenced input to durable storage before or while it is processed, the market-data publisher and the order-entry gateways (Figure 26.1).

    template <typename Opp>
    void match(Opp& opp, std::uint64_t id, std::int64_t price, std::int64_t& qty, bool buy,
               std::vector<Fill>& out) {
        while (qty > 0 && !opp.empty()) {
            auto lvl = opp.begin();
            if (buy ? lvl->first > price : lvl->first < price) break;  // no longer crosses
            auto& q = lvl->second;
            while (qty > 0 && !q.empty()) {
                auto& maker = q.front();
                const std::int64_t n = std::min(qty, maker.qty);
                out.push_back({maker.id, id, lvl->first, n});
                qty -= n;
                if ((maker.qty -= n) == 0) {
                    index_.erase(maker.id);
                    q.pop_front();
                }
            }
            if (q.empty()) opp.erase(lvl);
        }
    }

Listing 26.1. The matching loop of a price-time book: consume the best opposite level in time order while the incoming order crosses. The chapter’s test compares every fill and best price with a brute-force book on 200 random order streams. code/interviews/26-system-design/cpp/iv_book.hpp

**Figure 26.1.** A matching engine as a replicated state machine: the sequencer gives every inbound message one order and journals it; the engine is a deterministic function of the sequenced input, so a replica replaying the journal reaches the same state and can take over (One Quant Book 13, chapter 24).

Determinism is the design’s key property: if the engine’s output depends only on its sequenced input (no clocks read, no hash-map iteration order, no thread interleavings inside a partition), recovery is replay and a standby replica is a copy. Scaling is by partition: instruments are divided among engine threads or machines, each with its own book, which works because orders on different instruments do not interact (a spread order across two partitions needs a coordinating component).

26.3 Market data and the backtester

A market-data service fans out one feed to many consumers. Its design questions are sequencing (every message numbered per channel), recovery (a snapshot channel and a retransmission service, One Quant Book 10, chapter 26), and slow consumers, which must never slow the publisher: each consumer gets its own queue, and a consumer that falls too far behind is disconnected or switched to snapshots (Figure 26.2).

**Figure 26.2.** A market-data service: sequenced incremental updates for everyone, a snapshot and retransmission path for consumers that miss messages or fall behind, and a separate queue per consumer so that none can slow the publisher.

A backtester (One Quant Book 7, chapter 17, and One Quant Book 15, chapter 11) is an event loop over a merged stream of recorded events, with a simulated clock, a fill model for orders against the recorded book, latencies applied to both directions, and the strategy code called through the same interface it uses in production. Its design questions are reproducibility (seeded randomness, versioned data and code), realism (queue position, latency, fees) and speed (partitioning by day or instrument).

26.4 The risk service and the question of state

A pre-trade risk service sits on the order path (One Quant Book 11, chapter 27): every order is checked against limits (size, price collar, position, credit) before it leaves, so its state (positions, open orders, limits) must be current and its latency small. The interview questions are where the state lives (in the gateway’s process for speed, in a central service for a firm-wide view, usually both with the central view as the authority), how it is kept consistent (the gateway reserves against a limit before sending and releases on cancel or fill), and what happens when it fails: a risk check that cannot run must block orders (fail closed), and a kill switch must work when everything else does not.

26.5 Worked answers

Example 26.4 (A latency budget)

“The desk wants tick-to-order under 10 microseconds at the 99th percentile. Split the budget.” Write the path and give each stage a number: network card to application 1.5 (kernel bypass), feed decode 0.5, book update 1.0, strategy 3.0, pre-trade risk 1.0, order encode 0.5, application to wire 2.0: 9.5 microseconds, leaving 0.5 of margin. Then the point the interviewer is waiting for: these are percentiles, and percentiles do not add. If each of seven stages independently has a 1% chance of a slow path, the chance that at least one is slow on a given message is $1 - 0.99^7 \approx 6.8\%$ , so a budget of per-stage 99th percentiles says little about the end-to-end 99th percentile. Measure end to end, on the real path, with hardware timestamps, and budget the tail (cache misses, interrupts, a page fault) explicitly (Chapter 25).

26.6 Question bank

Interview question 26.1 ★ developer • market maker

A feed averages 200 000 messages a second over a 6.5-hour session, 64 bytes each. How much storage does a day of capture take?

Solution

Solution of Interview question 26.1.

$200\,000 \times 23\,400 \times 64 \approx 2.995 \times 10^{11}$ bytes, about 300 gigabytes a day uncompressed, some 75 terabytes a year of 250 days. Compression reduces it by a factor that is worth measuring on the data rather than assuming.

What the interviewer is looking for: a clean chain with units and a year’s extrapolation.

Interview question 26.2 ★ developer • proprietary firm

At a peak of one million 64-byte messages a second, what bandwidth does the feed need? Is a 1-gigabit link enough? A 10-gigabit one?

Solution

Solution of Interview question 26.2.

$10^6 \times 64 \times 8 = 512$ megabits a second of payload; with 42 bytes of Ethernet, IPv4 and UDP headers ( $14 + 20 + 8$ ) per message sent alone, 848 megabits. A 1-gigabit link is marginal at best (and bursts inside the second are higher); 10 gigabits leaves room. Batching several messages per packet cuts the header overhead.

What the interviewer is looking for: payload versus wire bytes, and bursts shorter than a second.

Interview question 26.3 ★ developer • crypto firm

You are asked to design a matching engine for a new venue. List the questions you ask in the first five minutes.

Solution

Solution of Interview question 26.3.

Instruments and order types; peak and average message rates, and the number of participants and sessions; latency targets (median, 99th and 99.9th percentile); matching rules (price-time or pro-rata, auctions, self-trade prevention); what market data is published (depth, full order-by-order); durability and failover requirements (what may be lost, how fast to recover); regulatory records and clock requirements.

What the interviewer is looking for: requirements before design, including tails and failure.

Interview question 26.4 ★ developer • market maker

Which operations must an order book support, and with which complexities, for a matching engine?

Solution

Solution of Interview question 26.4.

Add a limit order, cancel by identifier, modify (usually cancel and replace, losing priority unless only the size falls), match an incoming order, and read the best price and the depth. With a sorted map of levels, a FIFO list per level and a hash index by identifier: add at a new level $O(\log L)$ and at an existing one $O(1)$ , cancel $O(1)$ , best price $O(1)$ , matching $O(1)$ per fill (Chapter 21).

What the interviewer is looking for: the operation set and the data-structure trio behind the complexities.

Interview question 26.5 ★★ developer • market maker

Estimate the memory for full-depth books of 10 000 instruments with five million live orders, 48 bytes an order, and up to 1 000 price levels a side at 16 bytes a level.

Solution

Solution of Interview question 26.5.

Orders: $5 \times 10^6 \times 48 = 240$ megabytes. Levels: $10\,000 \times 2 \times 1\,000 \times 16 = 320$ megabytes. About 560 megabytes (534 MiB), which fits in memory easily but not in cache: the design question becomes locality (keep each instrument’s hot levels together, pre-allocate order records in pools) rather than capacity.

What the interviewer is looking for: the arithmetic and the conclusion that locality, not size, matters.

Interview question 26.6 ★★ developer • crypto firm

How do you make a matching engine recoverable after a crash with no lost or duplicated orders? What must be true of the engine’s code for your answer to work?

Solution

Solution of Interview question 26.6.

Sequence every inbound message and journal the sequenced input durably before acknowledging (or replicate it to a standby that acknowledges); on restart, load the last snapshot and replay the journal from it. Gateways retransmit unacknowledged messages with their client identifiers, and the engine discards duplicates it has already sequenced. It works only if the engine is deterministic: its output is a function of the sequenced input alone, with no wall-clock reads, no iteration over unordered containers, and no concurrency inside a partition (One Quant Book 13, chapter 24).

What the interviewer is looking for: sequencing, journaling, replay, duplicate suppression and determinism.

Interview question 26.7 ★★ developer • proprietary firm

Design a service that distributes one market-data feed to fifty internal consumers, some of them slow.

Solution

Solution of Interview question 26.7.

One publisher sequences updates per channel and sends them by multicast or, inside the firm, through a shared-memory or messaging bus; each consumer has its own queue so that a slow one never blocks the publisher. A consumer that detects a gap requests a retransmission or joins the snapshot channel and resumes from the snapshot’s sequence number; a consumer too far behind is disconnected and must resynchronise (Figure 26.2). Monitor per-consumer lag.

What the interviewer is looking for: sequencing, isolation of slow consumers, and a recovery path.

Interview question 26.8 ★★ developer, researcher • systematic fund

Design a backtester for intraday strategies on recorded order-book data. What makes its results reproducible and believable?

Solution

Solution of Interview question 26.8.

An event loop over the merged, time-ordered recorded events; a simulated clock that the strategy reads through the same interface as in production; latencies applied to data and to orders; a fill model that respects queue position and the recorded trades; fees and rebates. Reproducible: data versions, code versions and random seeds recorded with each run. Believable: validated against live fills of the same strategy (simulation–production parity, One Quant Book 15, chapter 12), with the fill model’s assumptions stated.

What the interviewer is looking for: event-driven structure, fill-model realism, and reproducibility.

Interview question 26.9 ★★ developer • market maker

Write the matching loop of a price-time priority book for limit orders, and say how you would test it.

Solution

Solution of Interview question 26.9.

Listing 26.1: while the incoming order has quantity and the best opposite level crosses its limit, fill against the level’s orders in time order at the resting price, removing filled makers from the queue and the index and empty levels from the map; any remainder rests at its limit behind earlier orders. Test it against a deliberately naive book (scan every resting order for the best price and earliest time) on random order streams, comparing every fill and the best prices after each event, as the chapter’s C++ test does for 200 streams, and check invariants (the resting book never crossed).

What the interviewer is looking for: correct price-time logic and a differential test against a brute force.

Interview question 26.10 ★★★ developer, risk • bank

Design the pre-trade risk check for a firm with order gateways in three data centres. Where does the state live, how is it kept consistent, and what happens when the risk service is down?

Solution

Solution of Interview question 26.10.

Each gateway holds the state it needs to check an order locally in microseconds (its share of limits, its open orders and fills), reserving against a limit before sending and releasing on cancel or fill; a central service holds the firm-wide positions and limits, allocates limit shares to the gateways, and reconciles with the drop copies of the venues. If the central service is down, gateways continue within their allocated shares and then stop: fail closed. A kill switch at each gateway and at the venues’ cancel-on- disconnect is independent of all of it (One Quant Book 11, chapter 27).

What the interviewer is looking for: local fast state with central authority, reservation, and fail-closed behaviour.

Interview question 26.11 ★★★ developer • crypto firm

Your matching engine handles 10 000 instruments; the peak is three million messages a second and one thread handles one million. How many partitions do you run at no more than half load, and what breaks when an order spans two partitions?

Solution

Solution of Interview question 26.11.

At half load a thread carries 500 000 messages a second, so $3\,000\,000/500\,000 = 6$ partitions, about 1 667 instruments each if load were even. It is not: assign instruments by measured load, not by count, and keep hot instruments on their own partitions. An order that spans partitions (a spread between two instruments) cannot be matched atomically by either: route such instruments to one partition, or use a coordinator that reserves both legs, at a cost in latency.

What the interviewer is looking for: the division, load balancing by activity, and the cross-partition problem.

Interview question 26.12 ★★★ developer • proprietary firm

Design failover for the matching engine so that a standby takes over within a second of the primary’s death with no lost acknowledged order.

Solution

Solution of Interview question 26.12.

Run the standby as a replica consuming the same sequenced input (from the sequencer or the journal) in lock step, so that it holds the same state at every sequence number. Acknowledge an order only when the sequenced message is on the standby as well (or in a replicated journal), so no acknowledged order is lost. Detect the primary’s death by heartbeats with a sub-second timeout; the standby finishes processing its queued input, then takes over the gateways’ sessions; clients reconnect and resend unacknowledged messages, which the sequencer deduplicates. Fence the old primary so that it cannot resume after a partition.

What the interviewer is looking for: a replicated state machine, the acknowledgement rule, fencing and deduplication.

Interview question 26.13 ★★★ developer, risk • multi-manager fund

A real-time risk service revalues 100 000 accounts of 50 positions each; on each of 1 000 price ticks a second, about 1% of all positions are affected. How many position updates a second is that, and how do you design for it?

Solution

Solution of Interview question 26.13.

$100\,000 \times 50 \times 0.01 \times 1\,000 = 5 \times 10^7$ position updates a second. Do not revalue on every tick: index positions by instrument so that a tick touches only its holders, revalue incrementally with sensitivities (delta and gamma) between full revaluations, batch ticks into short intervals (the risk decision rarely needs every tick), and partition accounts across workers; aggregate per account and per firm in trees.

What the interviewer is looking for: the rate and the incremental, indexed, batched design that avoids it.

Sources and further reading

One Quant Book 7, chapter 17; One Quant Book 10, chapters 1 and 26; One Quant Book 11, chapter 27; One Quant Book 13, chapters 18–24; One Quant Book 15, chapter 11.
The series’ exchange simulator, firm.exchsim, and its protocol document (code/firm/exchsim/PROTOCOL.md), as a worked design of a venue.

Terms defined in this chapter

System-design interview, capacity estimate

See all 2333 terms in the glossary