OLIVER SCOTT
Projects / Development · Systems

Limit order book matching engine

data structuresbenchmarkingtesting
AbstractA matching engine is the core of every exchange and every market-making simulator. I wrote a price-time priority limit order book that handles limit, market and cancel messages, tested it with targeted cases and a 20,000-message random test of invariants, and benchmarked it on one million messages: 449,575 messages a second with a median latency of 1.18 µs, in pure Python.
450k/smessages processed
1.18 µsmedian latency per message
6.06 µs99th percentile (p99.9 26.38 µs)
692ktrades in the benchmark

01Design

  • Prices are integer ticks, so there are no floating-point comparisons in matching.
  • Each side is dict[price → deque[Order]] plus a sorted list of active prices. Best bid and ask are O(1); a new level is a bisect insert.
  • Cancels are O(1) lazy deletes: the order is flagged dead and skipped when matching reaches it, and empty levels are cleaned from the top.
def _match(self, o, limit):
    while o.qty > 0:
        self._clean(opp)                       # drop dead orders at the top
        p = px[0] if o.side == "B" else px[-1]   # best opposite price
        if limit is not None and crosses_limit(p): break
        for m in queue_at(p):                # FIFO within the level
            n = min(o.qty, m.qty); o.qty -= n; m.qty -= n
            fills.append(Trade(o.oid, m.oid, p, n))

02Testing

  • Priority: a buy for 8 against asks of 5 @ 100 and 5 + 5 @ 101 fills 5 @ 100 then the older 3 @ 101.
  • Non-crossing orders rest; cancels are idempotent; market orders sweep levels.
  • A 20,000-message random test asserts after every message that the book never crosses and traded volume never exceeds submitted volume.

03Benchmark

Latency histogram
Fig. 1 Latency per message over one million messages (60% limit, 30% cancel, 10% market). The long tail comes from market orders sweeping several levels and from level clean-up.

Pure Python is a deliberate baseline. Real engines run in C++ or Rust with preallocated memory and price-indexed arrays; that port is the next project, and this version becomes its correctness oracle.

04What I'd do next

  • C++ port with intrusive linked lists and a price-indexed array; target over 10M messages/s.
  • Replay an ITCH-style feed and reconstruct the book.