Part III — Inside the Order Book

In the previous article we covered the order matching engine, its structure, purpose, behaviour, and how it uses the order book to manage and match orders. In this article we will examine the internals of the order book and how its design enables deterministic behaviour in the order matching engine (OME).

An order book, in the context of a betting exchange, is a collection of unmatched orders representing participants’ interest in a given market. For example:

Market:  Team A vs Team B
Outcome: Team A wins

Order Book (Back vs Lay):

------------------------------------------------------------
BACK SIDE                       | LAY SIDE
------------------------------------------------------------
Odds     | Liquidity            | Odds     | Liquidity
------------------------------------------------------------
2.06     | £300                 | 2.10     | £400
2.10     | £500                 | 2.14     | £600
2.08     | £200                 | 2.16     | £250
------------------------------------------------------------

In the previous article we covered how matching works, so we know that, with the current implementation, the BACK at 2.10 will be matched with the LAY at 2.10. The question now becomes: how does the order book organise orders so that the matching engine can find the correct counterpart quickly while preserving First In, First Out (FIFO) ordering?

Anatomy of the Order Book

#

Before looking at the implementation details, it’s worth considering what the order book needs to achieve.

At a minimum, it must:

• group orders by odds level;
• preserve FIFO ordering within each level;
• support efficient insertion of new orders;
• support efficient lookup of existing levels;
• support removal of fully matched orders.

These requirements heavily influence the choice of data structures. Rather than maintaining a single collection of orders and searching through it on every match attempt, the order book organises orders into price-level buckets.

OrderBook
├── BACKS
│   ├── 2.06 -> [order, order, order]
│   ├── 2.08 -> [order]
│   └── 2.10 -> [order, order]
│
└── LAYS
    ├── 2.10 -> [order]
    ├── 2.14 -> [order, order]
    └── 2.16 -> [order]

Each side of the book is organised independently. Orders are first grouped by odds level and then queued according to arrival time.

This structure allows the matching engine to locate a specific odds level directly and process orders in FIFO order without scanning the entire book.

Implementation Details

#

In code, the structure is represented as two maps: one for BACK orders and another for LAY orders. Each map stores a queue of orders for a given odds level.

In pseudo-code:

OrderBook
├── BACKS: map<odds, queue<order>>
└── LAYS:  map<odds, queue<order>>

The next step is representing this structure in memory.

Enter the \( BTreeMap\)

#

Rust offers several map implementations, with HashMap and BTreeMap being the most commonly used. At first glance, HashMap may seem like the obvious choice because it provides average-case \( O(1) \) lookups. However, lookup speed is not the only consideration when designing an order book.

So why the BTreeMap? It offers:

Ordered price levels

#

A BTreeMap maintains keys in sorted order. This means price levels are always stored from lowest to highest odds without requiring additional sorting. This becomes particularly useful in a production-style matching engine where finding the best available price is a common operation.

The natural ordering of keys is a property of the underlying \( B-tree \) data structure, which stores keys in sorted order while maintaining logarithmic lookup performance.

Deterministic iteration

#

Unlike HashMap, iteration order in a BTreeMap is deterministic. This aligns well with the broader design goal of keeping the matching engine deterministic and predictable in all environments: development, testing, and production.

Future-proofing

#

Although this prototype currently matches only exact odds levels, future versions may implement full price-time priority. In that model, locating the best available price becomes a first-class operation.

A sorted structure naturally supports that evolution.

Limitations and trade-offs

#

The trade-off is lookup complexity. Hashmap provides average-case \( O(1) \) access, while a BTreeMap does it in \( O(log \ n) \). For this prototype, the benefits of ordered price levels and deterministic iteration outweighed the additional lookup cost.

With the design motivations established, we can now examine the implementation.

Code

#

use std::collections::{BTreeMap, VecDeque};

pub struct OrderBook {
    pub market: Market,
    pub backs: BTreeMap<Odds, VecDeque<Order>>,
    pub lays: BTreeMap<Odds, VecDeque<Order>>
}

The BTreeMap groups orders by Odds levels, while the VecDeque preserves FIFO ordering within each level. Combined, they organise orders along two dimensions: price and time.

For the sake of completion here’s the code for Odds and Order:

pub struct Odds {
    pub ticks: u64,
}

pub struct Order {
    pub order_id: Uuid,
    pub market_id: Uuid,
    pub side: OrderSide,
    kind: OrderKind,
    pub odds: Odds,
    stake: Stake,
    pub remaining_stake: Stake,
    status: OrderStatus,
    timestamp: DateTime<Utc>,
}

So far we have examined the order book as the structure that organises orders for deterministic matching. In the next article we will look at how trade events produced by the matching engine are streamed out of the system.