How to Build an Order Matching Engine in Python: Price-Time Priority, Replay and Hypothesis Tests

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__ and peekitem as O(log n). For bids we pass operator.neg as 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 = "bad_price"  # integer ticks only, never float
        elif kind is Kind.MARKET and (price is not None or post_only or tif is TIF.GTC):
            err = "bad_market_order"
        elif post_only and tif is not TIF.GTC:
            err = "post_only_must_be_gtc"
        if err:
            return [{"type": "rejected", "reason": err}]

        order = Order(id=self.next_id, owner=owner, side=side, kind=kind, tif=tif,
                      price=price, qty=qty, remaining=qty, post_only=post_only, stp=stp)
        self.next_id += 1
        events = [{"type": "accepted", "id": order.id}]
        book = self.asks if order.side is Side.BUY else self.bids

        if order.post_only and self._would_take(order, book):
            order.remaining = 0
            events.append({"type": "canceled", "id": order.id, "qty": qty,
                           "reason": "post_only_would_take"})
            return events
        if order.tif is TIF.FOK and self._fillable(order, book) < order.qty:
            order.remaining = 0
            events.append({"type": "canceled", "id": order.id, "qty": qty,
                           "reason": "fok_not_fillable"})
            return events

        stp_stopped = self._match(order, book, events)

        if order.remaining:
            if order.kind is Kind.LIMIT and order.tif is TIF.GTC and not stp_stopped:
                (self.bids if order.side is Side.BUY else self.asks).add(order)
                self.resting[order.id] = order
                events.append({"type": "rested", "id": order.id,
                               "price": order.price, "qty": order.remaining})
            else:
                reason = "stp" if stp_stopped else order.tif.value if order.kind is Kind.LIMIT else "market"
                events.append({"type": "canceled", "id": order.id,
                               "qty": order.remaining, "reason": reason})
                order.remaining = 0
        return events

    def _cancel(self, order_id: int) -> list[dict]:
        order = self.resting.pop(order_id, None)
        if order is None:
            return [{"type": "rejected", "id": order_id, "reason": "unknown_order"}]
        (self.bids if order.side is Side.BUY else self.asks).remove(order)
        qty, order.remaining = order.remaining, 0
        return [{"type": "canceled", "id": order_id, "qty": qty, "reason": "user"}]

    # ---- matching ---------------------------------------------------
    @staticmethod
    def _price_ok(taker: Order, maker_price: int) -> bool:
        if taker.kind is Kind.MARKET:
            return True
        if taker.side is Side.BUY:
            return maker_price <= taker.price
        return maker_price >= taker.price

    def _would_take(self, taker: Order, book: BookSide) -> bool:
        best = book.best()
        return best is not None and self._price_ok(taker, best[0])

    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

    def _expire(self, maker: Order, book: BookSide, events: list[dict]) -> None:
        book.remove(maker)
        del self.resting[maker.id]
        events.append({"type": "canceled", "id": maker.id, "qty": maker.remaining,
                       "reason": "stp"})
        maker.remaining = 0

    def _fillable(self, taker: Order, book: BookSide) -> int:
        """Dry run of _match for FOK: how much would fill, applying the same STP rules."""
        total = 0
        for price, level in book.levels.items():
            if not self._price_ok(taker, price):
                break
            for maker in level.orders.values():
                if maker.owner == taker.owner and taker.stp is not STP.NONE:
                    if taker.stp in (STP.EXPIRE_TAKER, STP.EXPIRE_BOTH):
                        return total
                    continue  # EXPIRE_MAKER: skipped, matching goes on
                total += maker.remaining
                if total >= taker.qty:
                    return total
        return total


def replay(journal: list[dict]) -> tuple[MatchingEngine, list[dict]]:
    """Rebuild an engine from its input journal."""
    eng, events = MatchingEngine(), []
    for cmd in journal:
        events.extend(eng.process(cmd))
    return eng, events

A walkthrough that touches every path:

"""Walkthrough: FIFO, partial fill, FOK, post-only, IOC, STP, market, cancel."""
from engine import MatchingEngine

eng = MatchingEngine()


def send(label, **cmd):
    cmd.setdefault("op", "new")
    print(f"> {label}")
    for e in eng.process(cmd):
        print("   ", e)


send("alice sells 5 @ 101", owner="alice", side="sell", price=101, qty=5)
send("bob sells 3 @ 101", owner="bob", side="sell", price=101, qty=3)
send("carol sells 4 @ 102", owner="carol", side="sell", price=102, qty=4)
send("dave buys 7 @ 101", owner="dave", side="buy", price=101, qty=7)
send("erin FOK buys 10 @ 102", owner="erin", side="buy", price=102, qty=10, tif="fok")
send("frank post-only buys 2 @ 102", owner="frank", side="buy", price=102, qty=2, post_only=True)
send("erin IOC buys 10 @ 102", owner="erin", side="buy", price=102, qty=10, tif="ioc")
send("frank bids 2 @ 99", owner="frank", side="buy", price=99, qty=2)
send("gina bids 3 @ 98", owner="gina", side="buy", price=98, qty=3)
send("frank market sells 6, stp=expire_maker", owner="frank", side="sell",
     kind="market", tif="ioc", qty=6, stp="expire_maker")
send("henry bids 1 @ 97", owner="henry", side="buy", price=97, qty=1)
send("cancel #11", op="cancel", id=11)
send("cancel #11 again", op="cancel", id=11)
print("book:", eng.snapshot())

> alice sells 5 @ 101
    {'type': 'accepted', 'id': 1}
    {'type': 'rested', 'id': 1, 'price': 101, 'qty': 5}
> bob sells 3 @ 101
    {'type': 'accepted', 'id': 2}
    {'type': 'rested', 'id': 2, 'price': 101, 'qty': 3}
> carol sells 4 @ 102
    {'type': 'accepted', 'id': 3}
    {'type': 'rested', 'id': 3, 'price': 102, 'qty': 4}
> dave buys 7 @ 101
    {'type': 'accepted', 'id': 4}
    {'type': 'trade', 'price': 101, 'qty': 5, 'maker': 1, 'taker': 4, 'taker_side': 'buy'}
    {'type': 'trade', 'price': 101, 'qty': 2, 'maker': 2, 'taker': 4, 'taker_side': 'buy'}
> erin FOK buys 10 @ 102
    {'type': 'accepted', 'id': 5}
    {'type': 'canceled', 'id': 5, 'qty': 10, 'reason': 'fok_not_fillable'}
> frank post-only buys 2 @ 102
    {'type': 'accepted', 'id': 6}
    {'type': 'canceled', 'id': 6, 'qty': 2, 'reason': 'post_only_would_take'}
> erin IOC buys 10 @ 102
    {'type': 'accepted', 'id': 7}
    {'type': 'trade', 'price': 101, 'qty': 1, 'maker': 2, 'taker': 7, 'taker_side': 'buy'}
    {'type': 'trade', 'price': 102, 'qty': 4, 'maker': 3, 'taker': 7, 'taker_side': 'buy'}
    {'type': 'canceled', 'id': 7, 'qty': 5, 'reason': 'ioc'}
> frank bids 2 @ 99
    {'type': 'accepted', 'id': 8}
    {'type': 'rested', 'id': 8, 'price': 99, 'qty': 2}
> gina bids 3 @ 98
    {'type': 'accepted', 'id': 9}
    {'type': 'rested', 'id': 9, 'price': 98, 'qty': 3}
> frank market sells 6, stp=expire_maker
    {'type': 'accepted', 'id': 10}
    {'type': 'canceled', 'id': 8, 'qty': 2, 'reason': 'stp'}
    {'type': 'trade', 'price': 98, 'qty': 3, 'maker': 9, 'taker': 10, 'taker_side': 'sell'}
    {'type': 'canceled', 'id': 10, 'qty': 3, 'reason': 'market'}
> henry bids 1 @ 97
    {'type': 'accepted', 'id': 11}
    {'type': 'rested', 'id': 11, 'price': 97, 'qty': 1}
> cancel #11
    {'type': 'canceled', 'id': 11, 'qty': 1, 'reason': 'user'}
> cancel #11 again
    {'type': 'rejected', 'id': 11, 'reason': 'unknown_order'}
book: {'bids': [], 'asks': [], 'next_id': 12}

Follow order 4: dave’s buy for 7 hits alice’s 5 first (she arrived first at 101), then 2 of bob’s 3. Bob’s leftover 1 stays at the front of the 101 queue, and erin’s IOC takes it before moving up to 102. Erin’s FOK for 10 is killed without touching the book because only 5 are available within her limit.

Step 4. Self-trade prevention

A self-trade is when an incoming order would match a resting order from the same account. Exchanges block these: a trade with yourself prints volume while nothing changes hands. Binance’s STP FAQ defines modes in terms of who gets expired: EXPIRE_TAKER expires the incoming order’s remaining quantity, EXPIRE_MAKER expires the resting order, EXPIRE_BOTH does both, and there’s also a DECREMENT mode. Coinbase uses different names (decrement and cancel, cancel oldest, cancel newest, cancel both) and states that the STP instruction on the taker order takes precedence. This engine follows the same rule: the taker’s mode decides, and it defaults to expire_taker.

In the demo, frank’s market sell with expire_maker first expires his own resting bid at 99 (canceled ... reason: stp), then trades 3 with gina at 98, then cancels the rest because a market order never rests.

STP gets tricky when combined with FOK. The FOK pre-check must apply the same STP rules as the real matching loop, otherwise the pre-check counts liquidity the loop will never be allowed to take:

def _fillable(self, taker: Order, book: BookSide) -> int:
    """Dry run of _match for FOK: how much would fill, applying the same STP rules."""
    total = 0
    for price, level in book.levels.items():
        if not self._price_ok(taker, price):
            break
        for maker in level.orders.values():
            if maker.owner == taker.owner and taker.stp is not STP.NONE:
                if taker.stp in (STP.EXPIRE_TAKER, STP.EXPIRE_BOTH):
                    return total
                continue  # EXPIRE_MAKER: skipped, matching goes on
            total += maker.remaining
            if total >= taker.qty:
                return total
    return total

Step 6 shows what happens when it doesn’t.

Step 5. A deterministic journal and replay

Martin Fowler’s write-up of the LMAX architecture describes an engine whose state “is entirely derivable by processing the input events,” with a durable journal of inputs and replay to rebuild state after a restart. It works only if the engine is deterministic, and LMAX’s point was that the business logic is deterministic and fast enough that storing outputs gains nothing.

Determinism here comes from four rules: journal inputs, not outputs (process() appends the command before applying it); no clocks or randomness inside the engine (ids come from a counter, timestamps are stamped by the gateway and journaled with the command); one thread applying commands in journal order; and containers whose iteration order is defined by price and arrival only.

replay() builds a fresh engine and feeds it the journal; state_hash() hashes a canonical JSON snapshot of the book. A unit test writes the journal as JSON lines, reads it back, replays it and compares hashes; the Hypothesis machine below does the same at the end of every generated scenario, and also compares the full event streams.

Step 6. Property-based tests with Hypothesis

Example tests check the cases you thought of; matching bugs live in sequences you didn’t (a cancel after a partial fill, an STP expiry inside a FOK). Hypothesis’s stateful testing generates those sequences. You describe the possible actions as @rules and the properties as @invariants, which, per the docs, run “after every step.” When something fails, Hypothesis shrinks the sequence and prints a short program that reproduces it.

The machine keeps a ledger of every order from the events alone, then checks the invariants against the engine’s actual book:

from hypothesis import settings, strategies as st
from hypothesis.stateful import RuleBasedStateMachine, invariant, precondition, rule

from engine import MatchingEngine, replay

OWNERS = st.sampled_from(["a", "b", "c"])
PRICES = st.integers(min_value=95, max_value=105)  # integer ticks
QTYS = st.integers(min_value=1, max_value=10)
STPS = st.sampled_from(["none", "expire_taker", "expire_maker", "expire_both"])


@st.composite
def new_orders(draw):
    kind = draw(st.sampled_from(["limit", "limit", "limit", "market"]))
    cmd = {"op": "new", "owner": draw(OWNERS), "side": draw(st.sampled_from(["buy", "sell"])),
           "kind": kind, "qty": draw(QTYS), "stp": draw(STPS)}
    if kind == "limit":
        cmd["price"] = draw(PRICES)
        cmd["tif"] = draw(st.sampled_from(["gtc", "gtc", "ioc", "fok"]))
        cmd["post_only"] = cmd["tif"] == "gtc" and draw(st.booleans())
    else:
        cmd["tif"] = draw(st.sampled_from(["ioc", "fok"]))
    return cmd


class EngineMachine(RuleBasedStateMachine):
    def __init__(self):
        super().__init__()
        self.eng = MatchingEngine()
        self.ledger = {}   # id -> {"qty", "filled", "canceled"}
        self.cmds = {}     # id -> original command
        self.events = []

    def _apply(self, cmd):
        evs = self.eng.process(cmd)
        self.events.extend(evs)
        taker_trades = []
        for e in evs:
            if e["type"] == "accepted":
                self.ledger[e["id"]] = {"qty": cmd["qty"], "filled": 0, "canceled": 0}
                self.cmds[e["id"]] = cmd
            elif e["type"] == "trade":
                self.ledger[e["maker"]]["filled"] += e["qty"]
                self.ledger[e["taker"]]["filled"] += e["qty"]
                taker_trades.append(e)
            elif e["type"] == "canceled":
                self.ledger[e["id"]]["canceled"] += e["qty"]
        self._check_trades(taker_trades)
        if cmd.get("tif") == "fok":
            rec = self.ledger[evs[0]["id"]]
            assert rec["filled"] in (0, rec["qty"]), f"FOK partially filled: {rec}"

    def _check_trades(self, trades):
        prev = None
        for t in trades:
            taker, maker = self.cmds[t["taker"]], self.cmds[t["maker"]]
            assert not taker.get("post_only"), "post-only order took liquidity"
            assert maker["side"] != taker["side"]
            assert t["price"] == maker["price"], "trade must print at the maker's price"
            if taker["kind"] == "limit":
                ok = t["price"] <= taker["price"] if taker["side"] == "buy" else t["price"] >= taker["price"]
                assert ok, "trade through the taker's limit"
            if taker["owner"] == maker["owner"]:
                assert taker["stp"] == "none", "self-trade despite STP"
            # price priority, then time priority, as the taker walks the book
            key = (t["price"] if taker["side"] == "buy" else -t["price"], t["maker"])
            assert prev is None or key > prev, f"priority violated: {prev} -> {key}"
            prev = key
        # FIFO: nothing older than a filled maker may still rest at that price
        for t in trades:
            side = self.eng.asks if t["taker_side"] == "buy" else self.eng.bids
            level = side.levels.get(t["price"])
            if level:
                assert min(level.orders) >= t["maker"], "older order skipped at same price"

    @rule(cmd=new_orders())
    def new(self, cmd):
        self._apply(cmd)

    @precondition(lambda self: self.ledger)
    @rule(data=st.data())
    def cancel(self, data):
        oid = data.draw(st.sampled_from(sorted(self.ledger) + [10**9]))
        self._apply({"op": "cancel", "id": oid})

    @invariant()
    def book_is_never_crossed(self):
        bid, ask = self.eng.best_bid(), self.eng.best_ask()
        assert bid is None or ask is None or bid < ask, f"crossed book {bid} >= {ask}"

    @invariant()
    def quantity_is_conserved(self):
        for oid, rec in self.ledger.items():
            resting = self.eng.resting[oid].remaining if oid in self.eng.resting else 0
            assert rec["filled"] + rec["canceled"] + resting == rec["qty"], (oid, rec, resting)

    @invariant()
    def levels_are_consistent_and_fifo(self):
        seen = set()
        for side in (self.eng.bids, self.eng.asks):
            for price, level in side.levels.items():
                ids = list(level.orders)
                assert ids == sorted(ids), "FIFO order broken inside a level"
                assert level.orders, "empty level left behind"
                assert level.volume == sum(o.remaining for o in level.orders.values())
                assert all(o.remaining > 0 and o.price == price for o in level.orders.values())
                seen.update(ids)
        assert seen == set(self.eng.resting)

    def teardown(self):
        twin, twin_events = replay(self.eng.journal)
        assert twin_events == self.events, "replay produced different events"
        assert twin.state_hash() == self.eng.state_hash(), "replay produced a different book"


EngineMachine.TestCase.settings = settings(max_examples=300, stateful_step_count=60, deadline=None)
TestEngine = EngineMachine.TestCase

The invariants:

• Never crossed: after every step, best bid < best ask.
• Quantity is conserved: for every order, filled + canceled + still resting = original quantity.
• FIFO: order ids inside each level are ascending, and after a taker fills a maker at a price, no older order is left resting at that price.
• Priority while walking: a taker’s trades are in strictly improving (price, maker id) order, and never through its limit.
• Order-type rules: post-only never takes, FOK fills all or nothing, no self-trade unless STP is none.
• Replay: replaying the journal gives identical events and an identical book hash.

10 passed in 20.78s

The first run failed, and the bug was in my test, not the engine. The FIFO check originally said min(level.orders) > maker, and Hypothesis immediately produced a partial fill where the maker stays at the front of its queue with a smaller quantity. The correct condition is >=. Weak invariants are a real risk with property tests, so the next step was to check that these invariants catch real bugs.

Planting bugs to test the tests

conftest.py can swap in a mutant via an environment variable. Two plausible bugs:

def _fillable(self, taker, book):
    # Looks reasonable: sum liquidity at acceptable prices. Ignores STP.
    total = 0
    for price, level in book.levels.items():
        if not self._price_ok(taker, price):
            break
        total += level.volume
    return total

and a < instead of <= in the price check. Results from this machine:

$ MUTANT=strict_price_check pytest -x tests/test_properties.py   # found in ~8 s
AssertionError: crossed book 95 >= 95
  new  a buy   1 @95  limit  gtc stp=none
  new  a sell  1 @95  limit  gtc stp=none

$ MUTANT=fok_ignores_stp pytest -x --hypothesis-seed=1 tests/test_properties.py   # found in ~74 s
AssertionError: FOK partially filled: {'qty': 2, 'filled': 1, 'canceled': 1}
  new  a buy   1 @95  limit  gtc stp=none
  new  a buy   1 @95  limit  ioc stp=none
  new  a buy   1 @95  limit  gtc stp=none
  new  b buy   1 @95  limit  gtc stp=none
  new  a buy   1 @95  limit  gtc stp=none
  new  a sell  2   mkt market fok stp=expire_maker

(The output is condensed to one line per step by condense.py in the repo; the raw pytest output is in out/.)

The off-by-one shrinks to two orders at the same price that don’t trade, leaving bid = ask. The FOK bug is rarer: it needs a FOK order, the same owner resting on the other side, and an STP mode other than none. The naive pre-check sees 4 lots at 95; the real loop expires the seller’s own three bids, fills 1 lot with b, and the “fill-or-kill” ends up half filled. It took 74 to 84 seconds to find in my runs, and one seeded run hit my 100-second timeout without finding it, so a quick CI run can miss bugs like this; run a longer profile nightly. Once found, I minimized it by hand and pinned it as an example test:

def test_fok_respects_stp_expire_maker():
    # Hand-minimized from a Hypothesis counterexample (see MUTANT=fok_ignores_stp).
    eng = MatchingEngine()
    eng.process(new(owner="a", side="buy", price=95, qty=1))
    eng.process(new(owner="b", side="buy", price=95, qty=1))
    evs = eng.process(new(owner="a", side="sell", kind="market", tif="fok",
                          qty=2, stp="expire_maker"))
    assert evs[-1]["reason"] == "fok_not_fillable"
    assert not [e for e in evs if e["type"] == "trade"]

A third check runs in the benchmark: the naive list engine and the real one process the same 25,000 orders and must produce the same trades (same trades: True). That’s differential testing, and it’s how this Python engine pays off later: replay one journal through it and through a Go or Rust engine, then diff the outputs.

Step 7. Benchmark: orders per second

The workload is deterministic (seed 42): about 60% passive limit orders up to 200 ticks from a drifting mid price, 15% aggressive orders that cross the spread, 25% cancels of random live orders. The book grows as the run goes on, which is what hurts the naive version.

def workload(n, seed=42):
    """Deterministic mix: ~60% passive limits, ~15% aggressive limits, ~25% cancels."""
    rng = random.Random(seed)
    cmds, live, mid, next_id = [], [], 10_000, 1
    for _ in range(n):
        r = rng.random()
        if r < 0.25 and live:
            cmds.append({"op": "cancel", "id": live.pop(rng.randrange(len(live)))})
            continue
        side = rng.choice(("buy", "sell"))
        if r < 0.85:   # passive: rests away from the mid
            off = rng.randint(1, 200)
        else:          # aggressive: crosses the spread
            off = -rng.randint(0, 5)
        price = mid - off if side == "buy" else mid + off
        cmds.append({"op": "new", "owner": f"u{rng.randrange(1000)}", "side": side,
                     "price": price, "qty": rng.randint(1, 20), "stp": "none"})
        live.append(next_id)  # ids are assigned in order by both engines
        next_id += 1
        mid += rng.choice((-1, 0, 1))
    return cmds

Python 3.13.18 on x86_64, x86_64
n= 10,000  resting at end= 3,395  trades= 2,170  levels:   221,201 orders/s  naive list:   12,657 orders/s  same trades: True
n= 25,000  resting at end= 9,012  trades= 5,034  levels:   186,398 orders/s  naive list:    2,894 orders/s  same trades: True
n=100,000  resting at end=30,060  trades=25,973  levels:   151,476 orders/s
n=200,000  resting at end=51,659  trades=63,612  levels:   143,198 orders/s
per-order latency (200k, levels): p50=5.1us p99=37.2us p99.9=4123.7us

How to read these numbers:

• The data structure matters more than anything else here. At 25,000 orders (about 9,000 resting), the sorted-levels engine was 64 to 91 times faster than the re-sorted list across my runs, and the gap grows with depth because the list costs O(book size) per order.
• Absolute numbers are noisy. This ran on a shared 2-vCPU VM next to other jobs. I measured CPU time (process_time) rather than wall time; across two runs the sorted engine did 125,000 to 221,000 orders/s. Earlier wall-clock runs ranged from about 60,000 to 218,000 orders/s depending on load. Treat it as “on the order of 100k orders/s in pure Python.”
• The tail is not the engine’s. Median latency per order was 4 to 6 µs and p99 under 40 µs, but p99.9 reached milliseconds. Turning the garbage collector off (tail_check.py) didn’t remove it, so on this VM it’s mostly scheduling noise, though one GC-on run showed a 193 ms worst-case stall.

Where does the time go? The profile says it isn’t the book:

         1373468 function calls in 2.201 seconds

   Ordered by: internal time
   List reduced from 42 to 8 due to restriction <8>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    37472    0.567    0.000    1.925    0.000 engine/engine.py:51(_new)
    37472    0.188    0.000    0.513    0.000 engine/engine.py:125(_match)
   149888    0.183    0.000    0.304    0.000 enum.py:696(__call__)
    31914    0.157    0.000    0.232    0.000 engine/book.py:29(add)
   219274    0.150    0.000    0.150    0.000 {method 'get' of 'dict' objects}
    50000    0.148    0.000    2.201    0.000 engine/engine.py:24(process)
    74944    0.126    0.000    0.173    0.000 engine/engine.py:59(<lambda>)
   149888    0.122    0.000    0.122    0.000 enum.py:1158(__new__)

Most of the time is in _new: validation, building an Order, and parsing enum strings (150,000 Enum() calls for 37,000 new orders). SortedDict work barely shows up. In Python, interpreter overhead per command dominates long before data-structure costs do.

For scale, Fowler’s 2011 LMAX article describes a single Java thread processing 6 million orders per second on commodity hardware. Different language, workload and machine, so not a like-for-like comparison, but it shows why exchanges write the hot path in compiled languages. The GIL isn’t the real limit: matching one instrument is sequential by design. You parallelize across instruments (one engine per market) and around the engine (gateways, risk checks, market data).

Gotchas I hit or nearly hit

• Float prices sneak in through JSON. Parse prices as strings into Decimal, convert to ticks at the gateway, reject non-multiples instead of rounding.
• Malformed input must be rejected, not raised. My first version called Side(cmd["side"]) directly, so a typo raised ValueError after the command was already journaled. Now every field is validated before any state changes, and a test covers it.
• Two code paths that “do the same thing” drift. The FOK dry run must mirror the matching loop, including STP.
• Partial fills keep queue position. Don’t remove and re-add a partially filled maker.
• Tests can be wrong too. Plant bugs to prove the properties have teeth.

From a reference engine to a production crypto exchange matching engine

What this example deliberately leaves out, and what a production exchange matching engine adds:

• [ ] Balance and margin checks before an order reaches the book (the engine assumes a risk gate in front of it).
• [ ] Price protection for market orders (a maximum deviation from the last trade or best price), and price bands.
• [ ] Durable journal writes with fsync/replication before acknowledging, plus periodic snapshots so replay doesn’t start from day one.
• [ ] Order amendments, plus stop and trailing orders, which usually live outside the core book.
• [ ] The same journal replayed through the reference and production engines in CI, with outputs diffed.

Wrapping up

A matching engine is a few hundred lines, but the rules are dense. Writing it in Python first gives you a readable spec and an oracle; Hypothesis explores sequences you’d never write by hand; planted bugs tell you whether your invariants are worth anything.

The code is in code.zip: run pytest -q for the tests, python bench.py for the numbers, and MUTANT=fok_ignores_stp pytest -x tests/test_properties.py to watch a bug get caught.

Which invariant would you add? I’m curious whether anyone tests market-data consistency (depth snapshots versus the trade stream) as a property.