Designing a Stock Exchange: Order Matching Engines, Order Books, and Low-Latency Trade Execution at Scale

A stock exchange is one of the most demanding distributed systems ever built. Latency is measured in nanoseconds. Throughput peaks at millions of messages per second. Correctness is legally mandated, with regulators requiring bit-for-bit replay of every trade for years after execution. A single out-of-order message can trigger erroneous trades worth hundreds of millions of dollars.

Most distributed systems tolerate occasional inconsistency in exchange for availability. An exchange cannot. Two participants submitting orders simultaneously must receive a deterministic, agreed-upon outcome. The system must be fast enough that neither participant can gain an unfair advantage by virtue of where their server sits.

This is not a CRUD application that happens to handle money. It is a real-time, deterministic, fault-tolerant state machine operating at the boundary of what commodity hardware can do.

The Core Components

A modern exchange has four distinct subsystems:

1. The order gateway - accepts incoming orders from participants, validates them, and forwards to the matching engine
2. The matching engine - the central sequencer; applies orders against the order book and produces executions
3. The market data publisher - broadcasts order book state and trade confirmations to all participants
4. The clearing and settlement system - confirms trades, moves positions, and handles obligations

The matching engine is the heart of the system. Everything else is plumbing around it.

Order Book Data Structure

An order book holds all resting orders at each price level for a given instrument. A buy order that does not immediately match becomes a resting bid. A sell order becomes a resting ask.

The canonical data structure is a sorted map of price levels, where each level contains a queue of orders.

interface Order {
  orderId: string;
  side: "buy" | "sell";
  price: number; // in ticks; avoid floating point entirely
  quantity: number;
  timestamp: bigint; // nanoseconds since epoch
  participantId: string;
}

interface PriceLevel {
  price: number;
  orders: Order[]; // FIFO queue within the level
  totalQuantity: number;
}

class OrderBook {
  // Bids sorted descending (highest price first)
  private bids: Map<number, PriceLevel> = new Map();
  // Asks sorted ascending (lowest price first)
  private asks: Map<number, PriceLevel> = new Map();

  private sortedBidPrices: number[] = [];
  private sortedAskPrices: number[] = [];

  getBestBid(): PriceLevel | undefined {
    if (this.sortedBidPrices.length === 0) return undefined;
    return this.bids.get(this.sortedBidPrices[0]);
  }

  getBestAsk(): PriceLevel | undefined {
    if (this.sortedAskPrices.length === 0) return undefined;
    return this.asks.get(this.sortedAskPrices[0]);
  }

  addOrder(order: Order): void {
    const levels = order.side === "buy" ? this.bids : this.asks;
    let level = levels.get(order.price);
    if (!level) {
      level = { price: order.price, orders: [], totalQuantity: 0 };
      levels.set(order.price, level);
      this.insertSortedPrice(order.side, order.price);
    }
    level.orders.push(order);
    level.totalQuantity += order.quantity;
  }

  removeTopOrder(side: "buy" | "sell"): Order | undefined {
    const levels = side === "buy" ? this.bids : this.asks;
    const prices =
      side === "buy" ? this.sortedBidPrices : this.sortedAskPrices;
    if (prices.length === 0) return undefined;

    const topPrice = prices[0];
    const level = levels.get(topPrice)!;
    const order = level.orders.shift();
    if (order) {
      level.totalQuantity -= order.quantity;
      if (level.orders.length === 0) {
        levels.delete(topPrice);
        prices.shift();
      }
    }
    return order;
  }

  private insertSortedPrice(side: "buy" | "sell", price: number): void {
    const arr =
      side === "buy" ? this.sortedBidPrices : this.sortedAskPrices;
    // Bids: descending. Asks: ascending.
    const comparator =
      side === "buy"
        ? (a: number, b: number) => b - a
        : (a: number, b: number) => a - b;

    let lo = 0;
    let hi = arr.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (comparator(arr[mid], price) < 0) hi = mid;
      else lo = mid + 1;
    }
    arr.splice(lo, 0, price);
  }
}

In production, the price array is pre-allocated as a fixed-size array of tick slots covering the expected price range. O(1) access by tick index replaces binary search. The sorted-array approach above is readable; the tick-array approach is what you ship.

Matching Algorithms

Price-Time Priority (FIFO)

The dominant algorithm in equity markets. An incoming order matches against the best available price. At equal prices, earlier orders have priority. This is simple, deterministic, and easy to audit.

interface Trade {
  aggressorOrderId: string;
  restingOrderId: string;
  price: number;
  quantity: number;
  sequenceNumber: bigint;
  timestamp: bigint;
}

class MatchingEngine {
  private book: OrderBook;
  private sequence: bigint = 0n;

  constructor(book: OrderBook) {
    this.book = book;
  }

  submit(incoming: Order): Trade[] {
    const trades: Trade[] = [];

    if (incoming.side === "buy") {
      while (incoming.quantity > 0) {
        const bestAsk = this.book.getBestAsk();
        if (!bestAsk || bestAsk.price > incoming.price) break;

        const resting = bestAsk.orders[0];
        const fillQty = Math.min(incoming.quantity, resting.quantity);

        trades.push({
          aggressorOrderId: incoming.orderId,
          restingOrderId: resting.orderId,
          price: resting.price, // resting order's price wins
          quantity: fillQty,
          sequenceNumber: ++this.sequence,
          timestamp: process.hrtime.bigint(),
        });

        resting.quantity -= fillQty;
        incoming.quantity -= fillQty;

        if (resting.quantity === 0) {
          this.book.removeTopOrder("sell");
        }
      }
    }
    // Mirror logic for sell side

    if (incoming.quantity > 0) {
      this.book.addOrder(incoming);
    }

    return trades;
  }
}

The resting order’s price determines the execution price. This protects the resting participant from slippage and is the regulatory baseline for most markets.

Pro-Rata Matching

Used in derivatives markets, particularly for options and futures on fixed-income instruments. Instead of first-in-first-out within a price level, all orders at the best price receive a proportional share of the incoming quantity.

function proRataMatch(incoming: Order, level: PriceLevel): Trade[] {
  const trades: Trade[] = [];
  let remaining = incoming.quantity;

  const totalAtLevel = level.totalQuantity;
  const allocations: { order: Order; allocated: number }[] = [];

  // First pass: calculate proportional allocation (floor)
  let totalAllocated = 0;
  for (const resting of level.orders) {
    const raw = (resting.quantity / totalAtLevel) * incoming.quantity;
    const allocated = Math.floor(raw);
    allocations.push({ order: resting, allocated });
    totalAllocated += allocated;
  }

  // Second pass: distribute remainder to largest fractional parts
  let leftover = incoming.quantity - totalAllocated;
  const sorted = [...allocations].sort(
    (a, b) =>
      b.order.quantity / totalAtLevel - a.order.quantity / totalAtLevel
  );
  for (let i = 0; i < leftover; i++) {
    sorted[i % sorted.length].allocated += 1;
  }

  for (const { order, allocated } of allocations) {
    if (allocated === 0) continue;
    trades.push({
      aggressorOrderId: incoming.orderId,
      restingOrderId: order.orderId,
      price: level.price,
      quantity: allocated,
      sequenceNumber: 0n, // assigned by engine
      timestamp: 0n,
    });
    remaining -= allocated;
  }

  return trades;
}

Pro-rata encourages participants to post large resting orders to capture a bigger share of flow. It also complicates queue management significantly: a partial fill changes every participant’s allocation for the next aggressor.

Algorithm Tradeoffs

Dimension	Price-Time (FIFO)	Pro-Rata
Dominant market	Equities, FX spot	Options, fixed-income futures
Queue incentive	First-mover advantage	Size advantage
Order management complexity	Low (cancel/replace is well-defined)	High (size changes affect relative priority)
Latency sensitivity	Extreme (microseconds matter for queue position)	Moderate (proportional share is stable)
Auditability	Straightforward	Complex (remainder distribution is a source of disputes)
Latency advantage of colocation	Very high	Moderate
Fragmentation risk	Low	Higher (many small partial fills)

Hybrid algorithms exist: a “top-of-book” FIFO allocation for a fixed percentage of the incoming quantity, with pro-rata for the remainder. These are common in markets that want to reward both speed and size.

Low-Latency Architecture

Why the Kernel Is the Enemy

A typical Linux network stack adds 50-100 microseconds of overhead to a packet. For an exchange operating at nanosecond precision, this is unacceptable. Two techniques eliminate the kernel from the data path:

Kernel bypass networking (RDMA / DPDK): Instead of going through the OS network stack, the NIC writes packet data directly into application memory. The matching engine polls that memory region in a busy-wait loop. CPU cores dedicated to this loop never sleep and never yield.

Lock-free queues: Threads communicating via shared memory cannot use mutexes - acquiring a lock can stall a thread for microseconds. Instead, single-producer single-consumer ring buffers use atomic compare-and-swap operations.

// Conceptual lock-free ring buffer (production version would be in C++ / Rust)
class RingBuffer<T> {
  private buffer: (T | undefined)[];
  private head: number = 0; // written by producer
  private tail: number = 0; // written by consumer
  private mask: number;

  constructor(capacityPow2: number) {
    const size = 1 << capacityPow2;
    this.mask = size - 1;
    this.buffer = new Array(size);
  }

  // Producer thread only
  tryPush(item: T): boolean {
    const next = (this.head + 1) & this.mask;
    if (next === this.tail) return false; // full
    this.buffer[this.head] = item;
    // Memory fence required before updating head in real implementation
    this.head = next;
    return true;
  }

  // Consumer thread only
  tryPop(): T | undefined {
    if (this.tail === this.head) return undefined; // empty
    const item = this.buffer[this.tail];
    this.buffer[this.tail] = undefined;
    this.tail = (this.tail + 1) & this.mask;
    return item;
  }
}

In practice, the matching engine is single-threaded. There is no synchronization within the engine itself. The gateway reads from a lock-free input queue, the engine processes sequentially, and results are written to a lock-free output queue consumed by the market data publisher. Sequence numbers are trivially monotonic because there is only one writer.

Sequence Numbering

Every event the matching engine emits carries a monotonically increasing sequence number. This number is the spine of the entire system. Clients use it to detect gaps in their market data feed. The clearing system uses it to correlate executions. Regulators use it to replay the exact state of the order book at any point in time.

class SequenceNumberGenerator {
  private current: bigint = 0n;

  next(): bigint {
    return ++this.current;
  }

  current_value(): bigint {
    return this.current;
  }
}

interface MatchingEngineEvent {
  sequenceNumber: bigint;
  timestamp: bigint; // hardware timestamp from NIC, not OS clock
  type: "order_added" | "order_cancelled" | "trade_executed" | "order_expired";
  payload: Order | Trade;
}

The sequence number must never reset, even across restarts. Persistent storage of the last emitted sequence number is a hard requirement. In practice this is written to a memory-mapped file on a separate storage device before each event is published.

Market Data Distribution

Multicast over TCP

The exchange publishes market data to potentially thousands of subscribers simultaneously. Sending individual TCP connections to each subscriber would saturate the exchange’s network interface. Multicast UDP solves this: the exchange sends one packet, the network fabric delivers it to all subscribers in a multicast group.

The tradeoff is that UDP is unreliable. Subscribers must implement gap detection using sequence numbers and request retransmission for missing packets via a separate TCP retransmit channel.

The ITCH protocol (used widely in equity markets) defines this binary format. Messages are fixed-width, tightly packed, and carry no field names - every byte is predetermined.

// Simplified ITCH-style binary encoder
function encodeOrderAdded(
  order: Order,
  seqNum: bigint,
  buffer: DataView,
  offset: number
): number {
  buffer.setUint8(offset, 0x41); // 'A' = Add Order
  offset += 1;
  buffer.setBigUint64(offset, seqNum, false); // big-endian
  offset += 8;
  buffer.setFloat64(offset, order.price, false);
  offset += 8;
  buffer.setUint32(offset, order.quantity, false);
  offset += 4;
  buffer.setUint8(offset, order.side === "buy" ? 0x42 : 0x53); // 'B' or 'S'
  offset += 1;
  // Participant ID: 4 bytes, space-padded
  const pid = order.participantId.padEnd(4).slice(0, 4);
  for (let i = 0; i < 4; i++) {
    buffer.setUint8(offset + i, pid.charCodeAt(i));
  }
  offset += 4;
  return offset;
}

The total wire size for an Add Order message in this format is 26 bytes. At 1 million messages per second, that is 26 MB/s per subscriber group before multicast replication. Actual production feeds compress further with delta encoding across sequential messages.

Production Considerations

Deterministic Replay

Every action the matching engine takes must be reproducible from a stored log. This means the engine must be a pure function of its input stream. It cannot call Date.now() internally. It cannot make random choices without a seeded, deterministic PRNG. It cannot depend on system state that was not part of the input sequence.

In practice, hardware timestamps from the NIC are included in the input message, and the matching engine uses those timestamps, not wall clock reads.

The stored log is an append-only sequence of input messages with their sequence numbers and hardware timestamps. Replaying the log through the matching engine must produce byte-identical output every time. This is tested continuously in parallel with the live system by running a shadow engine on a recorded log.

Fault Tolerance and Failover

A matching engine that fails mid-session is a catastrophe. The standard approach is a primary/backup pair running in lockstep:

1. The primary engine processes each message and produces output events.
2. Before publishing output events to the market data feed, the primary sends the output to the backup over a dedicated low-latency link.
3. The backup acknowledges receipt.
4. The primary publishes.

If the primary fails, the backup has already received and applied every event. It can take over without gap. The failover time must be faster than the market data gap detection timeout at clients (typically 100-200 milliseconds).

This two-copy acknowledgment step adds latency to every message. It is the primary architectural tension in exchange design: durability requires coordination, and coordination adds latency.

Regulatory Audit Trails

Regulators require a complete, immutable record of every order submitted, every modification, every cancellation, and every trade. The log must be tamper-evident, timestamped with hardware-clock precision, and stored for a minimum of several years depending on jurisdiction.

This log is separate from the operational replay log. It includes rejected orders (which never touch the matching engine) and all order gateway-level events. It is written to a write-once storage tier immediately on receipt, before any processing.

interface AuditRecord {
  recordType:
    | "order_received"
    | "order_accepted"
    | "order_rejected"
    | "order_cancelled"
    | "trade_confirmed";
  gatewaySequenceNumber: bigint; // assigned at receipt, before engine processing
  matchingEngineSequenceNumber: bigint | null; // null if rejected before matching
  participantId: string;
  sessionId: string;
  hardwareTimestamp: bigint; // NIC timestamp in nanoseconds
  softwareTimestamp: bigint; // OS timestamp for cross-reference
  payload: Record<string, unknown>;
  checksum: string; // SHA-256 of prior record + this record's fields
}

The checksum chain makes the log tamper-evident. Inserting, deleting, or modifying any record breaks the chain from that point forward. In production, the chain is verified during off-hours as part of daily reconciliation.

Colocation and Network Architecture

Latency between the participant and the exchange is a competitive dimension. Exchanges offer colocation: rack space in the same data center, connected via direct cross-connect cables instead of public internet. A cross-connect can achieve round-trip latency under 1 microsecond between the participant’s gateway server and the exchange’s matching engine.

Within the data center, network topology matters. The matching engine’s NIC connects to a top-of-rack switch. Collocated participants connect to the same switch. Every additional hop (another switch, a router) adds 5-10 microseconds.

The exchange must also guarantee that all collocated participants receive market data with equal latency. This means the multicast feed is delivered through a switch with hardware-level multicast replication, not software copying. All ports in the multicast group receive the packet simultaneously, not sequentially.

Monitoring at Nanosecond Precision

Standard application performance monitoring is useless here. A 1-millisecond p99 latency is not a story about microservices behavior. It is a potential regulatory event.

Production monitoring for a matching engine tracks:

• Order-to-acknowledgment latency (gateway receipt to engine sequence number assignment) in nanoseconds, sampled at 100% of messages
• Matching throughput (messages per second, with 10-microsecond resolution)
• Order book depth at each price level, exported every 100 milliseconds
• Gap detection rate on the market data feed (non-zero is an incident)
• Hardware timestamp drift between primary and backup engines (sudden drift indicates NIC or network issue)

The observability infrastructure itself cannot use the kernel network stack - the overhead would affect the measurements. Metrics are written to a shared-memory ring buffer and read by a separate process that handles export over a non-latency-critical path.

Closing

The stock exchange is where the requirements that other distributed systems trade away become non-negotiable. You cannot sacrifice consistency for availability. You cannot introduce non-determinism and call it acceptable. You cannot tolerate a latency tail because the tail is someone’s legal right to a fair market.

The core insight is that the matching engine is a state machine, not a service. It accepts a totally ordered input sequence and produces a totally ordered output sequence. Everything around it - the gateways, the market data publishers, the audit logs - exists to maintain that total order faithfully under network failures, hardware failures, and the physics of light traveling through fiber.

Build the state machine first. Make it deterministic. Make it fast enough that the coordination overhead of durability does not dominate. Everything else follows from those constraints.