Building an Order Matching Engine in Python: A Reference Implementation You Can Try to Break
An order matching engine is the small, strict core of every exchange: it takes orders in, pairs buyers with sellers, and emits trades. If it lets a bid sit above an ask or replays the same orders into different trades, nothing downstream can fix it.
Production engines are usually written in Go, Rust, Java or C++. The crypto exchange build guide listed first in the sources recommends Go for the core matching engine and Rust for ultra-low-latency paths. So why Python? It’s the fastest way to pin down the rules (who fills first, what happens to an IOC remainder, how self-trade prevention interacts with fill-or-kill). A small, readable implementation with property-based tests becomes the spec and the test oracle for the fast one.
In this tutorial we build that reference engine and then try to break it:
- Integer prices in ticks (no floats).
- A limit order book: sorted price levels plus FIFO queues.
- Matching with market, limit, IOC, FOK and post-only orders, partial fills and cancels.
- Self-trade prevention (STP).
- A deterministic journal and replay.
- Hypothesis state-machine tests for the invariants, plus two planted bugs.
- A benchmark in orders/sec, with Python’s limits stated plainly.
Stack: Python 3.13.18, sortedcontainers 2.4.0, hypothesis 6.170.14, pytest 9.2.0. Every output block below is pasted from a real run. This is an engineering exercise, not trading or financial advice.
What is a matching engine?
A matching engine keeps a limit order book of resting buy orders (bids) and sell orders (asks). A new order trades against the opposite side if prices allow; the remainder rests or is canceled, depending on the order type.
The common rule is price-time priority. Coinbase’s documentation for its exchange matching engine puts it in one line: orders are executed “in price-time priority as received by the matching engine.” The best price trades first; among orders at the same price, the oldest trades first. The trade prints at the resting (maker) order’s price, so an aggressive buyer who bids above the best ask still pays the ask.
Here is the shape of what we’re building:
| Component | Job | Data structure |
|---|---|---|
| Book side | Price levels, best price first | SortedDict keyed by integer price |
| Price level | Orders at one price, oldest first | OrderedDict of order id to order |
| Order index | Find an order for cancel in O(1) | dict of order id to order |
| Engine | Validate, match, emit events | single-threaded loop |
| Journal | Every input command, in order | list of dicts (JSON lines on disk) |
Step 1. Prices are integers (ticks), never floats
Exchanges define a tick size for each market, for example 0.01. Inside the engine, a price is an integer count of ticks and a quantity is an integer count of lots. Python’s own tutorial explains why: most decimal fractions “cannot be represented exactly as binary fractions,” so 0.1 is stored as a nearby binary value. In a matching engine that turns into prices that compare unequal and quantities that never quite reach zero:
from decimal import Decimal from engine.ticks import to_ticks print("0.1 + 0.2 == 0.3 ->", 0.1 + 0.2 == 0.3) print("0.07 * 100 ->", 0.07 * 100) print("int(0.29 * 100) ->", int(0.29 * 100)) total = 0.0 for _ in range(10): total += 0.1 # ten fills of 0.1 lots print("10 x (total += 0.1) ->", total) print("sum([0.1] * 10) ->", sum([0.1] * 10)) print("Decimal('0.29') / 0.01 ->", Decimal("0.29") / Decimal("0.01")) print("to_ticks('0.29','0.01')->", to_ticks("0.29", "0.01")) try: to_ticks("0.295", "0.01") except ValueError as e: print("to_ticks('0.295',...) ->", e) 0.1 + 0.2 == 0.3 -> False 0.07 * 100 -> 7.000000000000001 int(0.29 * 100) -> 28 10 x (total += 0.1) -> 0.9999999999999999 sum([0.1] * 10) -> 1.0 Decimal('0.29') / 0.01 -> 29 to_ticks('0.29','0.01')-> 29 to_ticks('0.295',...) -> 0.295 is not a multiple of tick size 0.01 int(0.29 * 100) giving 28 is the classic bug: a price of 0.29 silently becomes 0.28. Note the two sums too. Since Python 3.12, sum() uses Neumaier summation for floats, so sum([0.1] * 10) returns 1.0, while the += you’d write when accumulating fills still drifts. The result depends on how you add things up, which an engine must never allow.
The fix is to parse decimal strings at the edge with Decimal, convert to ticks, and reject anything that is not an exact multiple of the tick size:
from decimal import Decimal def to_ticks(price: str, tick_size: str) -> int: """Convert a decimal price string to an integer number of ticks. Rejects prices that are not an exact multiple of the tick size, instead of silently rounding them. """ p, t = Decimal(price), Decimal(tick_size) ticks, rem = divmod(p, t) if rem != 0: raise ValueError(f"{price} is not a multiple of tick size {tick_size}") return int(ticks) def from_ticks(ticks: int, tick_size: str) -> str: return str(ticks * Decimal(tick_size)) The engine itself then refuses non-integer prices (100.5 is rejected with bad_price; there’s a test for that).
Step 2. The limit order book: sorted levels plus FIFO queues
The obvious first version is one list per side, re-sorted after every insert. I kept it in the repo (naive.py) as a baseline and a cross-check. It’s slow for structural reasons. The Python docs list list.insert, del l[k] and l.pop(k) as O(n - k), so taking the best order from the front with pop(0) moves the whole list. Even bisect.insort doesn’t save you: the docs note that its O(log n) search “is dominated by the slow O(n) insertion step.” Sorting is adaptive (already-sorted input takes O(n) comparisons), so re-sorting after one append is linear rather than O(n log n). It’s still linear in the depth of the book, on every order.
The structure that matches the problem is two-level:
- Price levels in a
SortedDict. Its documentation lists__setitem__,__delitem__andpeekitemas O(log n). For bids we passoperator.negas the key function, so index 0 is always the best price on either side. - A FIFO queue per level, so time priority is the insertion order.
- An order index (
dict), so a cancel finds its order without scanning.
For the FIFO queue I benchmarked three candidates, because the access pattern is awkward: consume from the front, append to the back, delete from the middle on cancel.
"""Why PriceLevel uses OrderedDict: consume a FIFO queue from the front while new orders arrive at the back.""" import time from collections import OrderedDict, deque def run(make, pop_front, n=50_000): q = make() for i in range(n): q[i] = i t0 = time.perf_counter() for i in range(n, 2 * n): # steady state: one fill at the front, one new order at the back pop_front(q) q[i] = i return time.perf_counter() - t0 def dict_pop_front(d): del d[next(iter(d))] def od_pop_front(d): d.popitem(last=False) print(f"dict : {run(dict, dict_pop_front):.3f}s") print(f"OrderedDict : {run(OrderedDict, od_pop_front):.3f}s") dq = deque(range(50_000)) t0 = time.perf_counter() for i in range(2_000): dq.remove(25_000 + i) # cancel from the middle of the queue print(f"deque.remove x2000 (middle): {time.perf_counter() - t0:.3f}s") od = OrderedDict.fromkeys(range(50_000)) t0 = time.perf_counter() for i in range(2_000): del od[25_000 + i] print(f"OrderedDict del x2000 : {time.perf_counter() - t0:.3f}s") dict : 1.011s OrderedDict : 0.034s deque.remove x2000 (middle): 1.176s OrderedDict del x2000 : 0.000s The first line surprised me. A plain dict keeps insertion order and del d[k] is O(1) on average, so it looks like a perfect queue, yet here it was about 30 times slower than OrderedDict.popitem(last=False), presumably because CPython has to skip the deleted slots at the front to find the first live entry. deque is fast at both ends, but remove() from the middle behaved like a linear scan in this test, a cost every cancel would pay. The collections docs describe OrderedDict as “designed to be good at reordering operations,” and it handles all three operations here. So a level is an OrderedDict:
from collections import OrderedDict from operator import neg from sortedcontainers import SortedDict from .model import Order class PriceLevel: """All resting orders at one price, oldest first (time priority).""" __slots__ = ("orders", "volume") def __init__(self) -> None: self.orders: OrderedDict[int, Order] = OrderedDict() self.volume = 0 class BookSide: """One side of the book: price levels kept sorted best-first.""" def __init__(self, is_bid: bool) -> None: # Bids: highest price first. Asks: lowest price first. self.levels: SortedDict = SortedDict(neg) if is_bid else SortedDict() def best(self) -> tuple[int, PriceLevel] | None: return self.levels.peekitem(0) if self.levels else None def add(self, order: Order) -> None: level = self.levels.get(order.price) if level is None: level = self.levels[order.price] = PriceLevel() level.orders[order.id] = order # appended at the back: FIFO level.volume += order.remaining def remove(self, order: Order) -> None: level = self.levels[order.price] del level.orders[order.id] # O(1), unlike list.remove() level.volume -= order.remaining if not level.orders: del self.levels[order.price] def depth(self) -> list[tuple[int, int]]: return [(p, lvl.volume) for p, lvl in self.levels.items()] Each level also caches its total volume, so market-data snapshots don’t have to walk the orders.
Step 3. The matching loop and order types
Orders and enums are plain dataclasses (engine/model.py in the repo). The heart of the engine is the loop that walks the opposite side best-first:
def _match(self, taker: Order, book: BookSide, events: list[dict]) -> bool: """Walk the opposite side best-first. Returns True if STP stopped the taker.""" while taker.remaining: best = book.best() if best is None or not self._price_ok(taker, best[0]): return False price, level = best maker = next(iter(level.orders.values())) # oldest order at best price if maker.owner == taker.owner and taker.stp is not STP.NONE: if taker.stp in (STP.EXPIRE_MAKER, STP.EXPIRE_BOTH): self._expire(maker, book, events) if taker.stp in (STP.EXPIRE_TAKER, STP.EXPIRE_BOTH): return True continue q = min(taker.remaining, maker.remaining) events.append({"type": "trade", "price": price, "qty": q, "maker": maker.id, "taker": taker.id, "taker_side": taker.side.value}) taker.remaining -= q maker.remaining -= q level.volume -= q if maker.remaining == 0: book.remove(maker) del self.resting[maker.id] return False Three details matter. The trade prints at price, the maker’s level. next(iter(level.orders.values())) is always the oldest order at the best price: price-time priority in one line. And a partially filled maker keeps its place at the front of the queue.
What happens before and after the loop depends on the order type:
| Order | Before matching | Remainder after matching |
|---|---|---|
| Limit GTC | validate | rests on the book |
| Limit IOC | validate | canceled |
| Limit FOK | dry-run: can the whole quantity fill now? If not, cancel everything | none (all or nothing) |
| Post-only | if it would trade on arrival, cancel it | rests on the book |
| Market | no price limit, never rests | canceled |
Binance’s API docs define the same time-in-force values: GTC stays on the book until canceled, IOC fills “as much as it can before the order expires,” and FOK expires “if the full order cannot be filled upon execution.” Binance’s post-only type, LIMIT_MAKER, is “rejected if the order immediately matches and trades as a taker.” This engine does the same.
The full engine is under 200 lines:
engine/engine.py (full source)import hashlib import json from .book import BookSide from .model import Kind, Order, Side, STP, TIF class MatchingEngine: """Single-threaded price-time priority matching engine. Every input command is appended to a journal before it is applied. The engine reads no clocks and no randomness, so replaying the journal reproduces the exact same events and the exact same book. """ def __init__(self) -> None: self.bids = BookSide(is_bid=True) self.asks = BookSide(is_bid=False) self.resting: dict[int, Order] = {} self.next_id = 1 self.journal: list[dict] = [] # ---- public API ------------------------------------------------- def process(self, cmd: dict) -> list[dict]: self.journal.append(cmd) if cmd["op"] == "new": return self._new(cmd) if cmd["op"] == "cancel": return self._cancel(cmd["id"]) return [{"type": "rejected", "reason": "unknown_op"}] def best_bid(self) -> int | None: b = self.bids.best() return b[0] if b else None def best_ask(self) -> int | None: a = self.asks.best() return a[0] if a else None def snapshot(self) -> dict: def side(s: BookSide): return [[p, [[o.id, o.owner, o.remaining] for o in lvl.orders.values()]] for p, lvl in s.levels.items()] return {"bids": side(self.bids), "asks": side(self.asks), "next_id": self.next_id} def state_hash(self) -> str: raw = json.dumps(self.snapshot(), separators=(",", ":")) return hashlib.sha256(raw.encode()).hexdigest()[:16] # ---- commands --------------------------------------------------- def _new(self, cmd: dict) -> list[dict]: try: side, kind = Side(cmd["side"]), Kind(cmd.get("kind", "limit")) tif, stp = TIF(cmd.get("tif", "gtc")), STP(cmd.get("stp", "expire_taker")) owner, qty = cmd["owner"], cmd["qty"] except (KeyError, ValueError): return [{"type": "rejected", "reason": "bad_command"}] price, post_only = cmd.get("price"), cmd.get("post_only", False) is_int = lambda x: isinstance(x, int) and not isinstance(x, bool) err = None if not is_int(qty) or qty <= 0: err = "bad_qty" elif kind is Kind.LIMIT and (not is_int(price) or price <= 0): err = Source：https://dev.to/kate_steeleeee/how-to-build-an-order-matching-engine-in-python-price-time-priority-replay-and-hypothesis-tests-bdaRelated posts
Indexing a villa against itself: a median-of-ratios holiday price index in pandas
Synthetic Checks & SLOs for the Paths Nobody Clicks
Why a Mac Writing Helper Needs Two Permissions, and Why It Still Refuses Password Fields
Decoding iPhone HEIC photos in the browser: a 4-step fallback chain and what it costs
How to Stand Out When Every Application Looks the Same
