Part II — Inside the Order Matching Engine

In the previous article we covered, at a high-level the architecture of this prototype betting exchange, its design decisions and trade-offs. In this article we will cover arguably the most interesting part of the system: the order matching engine (OME), which is part of the Order Matching System (OMS).

An OME is, in essence, an electronic system that matches buy and sell orders in a market. The market could be:

• equities
• commodities
• cryptocurrencies
• futures (derivatives)
• betting

Each market will have its own unique set of participants, tradeable instruments, and rules, and as such when building an OME and the supporting OMS around it, domain-specific knowledge and assumptions are required.

Central to any OME is the matching policy, which governs how orders are meant to be matched.

Matching Policy

#

This policy, just like the wider OME is driven by the specific domain. However, due to the similarity of incentives across market participants, a small number of matching algorithms have emerged as dominant, with the most common being: price-time priority, which is a combination of the following rules:

1. the best price wins
2. if price is equal, the earliest order wins

This prototype only implements the second rule. Orders are matched at exact odds levels, and FIFO ordering is preserved within each level.

For example:

BID/BACK     ASK/LAY
10.5 @ 100   10.5 @ 100

will match, but:

BID/BACK     ASK/LAY
             10.6 @ 100
10.5 @ 100   
             10.4 @ 100

will not. In a real-world implementation, with best-price the bid would be matched with the 10.4 ask because it is economically beneficial for both traders. To generalise, a trade happens when:

Betting exchange focus

#

Earlier I mentioned that domain-specific knowledge is required to build an OME that is suitable for the target markets. In this series I’ll focus on betting exchanges as an alternative to traditional financial markets. As such, the code incorporates betting terminology, so you’ll see BACK instead of BID and LAY in place of ASK. They are similar but not the same.

In a betting exchange, unlike a traditional market, you’re not trading on an outcome that involves the exchange of a physical commodity like oil futures with delivery, or the exchange of an instrument like a company stock, etc. but on a single event with multiple outcomes. For example three people can bet on the outcome of a football match, one person believes team A will win, another thinks team A will lose, and another thinks it’ll be a draw.

That is the crucial distinction between trading an asset and betting on an outcome.

To draw an analogy from public equities, consider a company’s upcoming earnings call. Rather than trading the stock itself, participants could speculate on one of several outcomes:

Company X earning call (due a week from now)

Outcomes of X's earnings:

- exceeds analyst's expectations (equivalent to win in the football match)
- just about meets the expectations (draw)
- fails to meet expectations (lose)

Participants express views on any of these three outcomes. The likelihood of any outcome will be reflected in the odds. This pattern is consistent across all prediction markets. With likelier outcomes having lower odds and lower payouts, and less likely outcomes having higher odds and payouts.

With the above context we can now dive into the engine’s architecture.

Engine Architecture

#

Scope

#

This engine is responsible for maintaining an in-memory order book and matching incoming orders using deterministic rules.

It is deliberately scoped to a single market. Each market owns its own order book and matching engine instance. This avoids cross-market coordination inside the matching path and keeps the implementation straightforward.

So:

1 market -> 1 order book -> 1 matching engine

rather than:

many markets -> shared matching engine

System Diagram

#

flowchart TD

A[Incoming Order] --> B[Validate Order]

B --> C[Select Opposite Side of Order Book]

C --> D{Find Matching Price Level}

D -->|No Match| E[Insert Into Order Book
Price Level Queue]

D -->|Match Found| F[Select FIFO Order
at Exact Price Level]

F --> G[Compute Trade]

G --> H[Update Remaining Quantities]

H --> I{Order Fully Filled?}

I -->|Yes| J[Emit Trade Event]

I -->|No| F

J --> BCT[Background Consumer Thread: Receive Trade Event]

BCT --> EP[Event Publisher: Publish event to Redis Stream]

Engine Dynamics

#

Consider the following order book:

BACKs            
10.5 -> [100, 80, 40, 200]      
10.4 -> [90]        

LAYs            
10.5 -> [50]         
10.7 -> [30]  

The lay order at 10.5 will match against the oldest back order at the same level. The remaining unmatched back orders at that level will sit in the order book until a compatible lay is received.

No Match

#

We’re in the “No Match” branch in the diagram:

1. incoming order;
2. no opposite order found at the same price level after looking up in the order book;
3. add order to its appropriate side in the order book at:
   • if incoming order is a BACK then add to queue of BACK orders
   • if incoming order is a LAY then add to queue of LAY orders

Match Found

#

We’re in the “Match Found” branch in the diagram:

1. incoming order;
2. a lookup in the order book is performed to find an exact price level from the opposite side;
3. from within a given price level, iterate through the FIFO queue
4. perform partial/full fills by subtracting \( min(incoming \ order.value, opposite \ order.value) \) from both the incoming order and the opposite one
5. trigger a trade event based on this match, using the \( min(incoming, opposite) \) as trade size
6. emit trade event to the event channel
7. check if opposite order has been filled in full, and if so remove from book
8. check if incoming order has been filled in full, if so break iteration
9. final pass to clean up order book from levels with no queued orders

Engine Design Decisions

#

Separations of concerns

#

The engine produces (trade) events. It doesn’t handle analytics, persistence, or external communication. It stays hot and fast.

Deterministic execution model

#

The engine is designed to behave as a deterministic state machine over incoming orders. That is:

• given the same orders (inputs), the same events (outputs) will be produced
• the matching logic has no hidden side effects
• state mutation is easily observable and incremental

Partial fills

#

• an order may not be fully matched
• matching can occur in increments

Matching loop semantics

#

Matching continues until an order is fully filled or there’s no liquidity.

Ordering guarantee

#

• ordering is preserved within a price level
• fairness is guaranteed for equal-price orders

Limitations and Future Work

#

• No price-time priority across levels
• No distributed matching
• Limit orders only
• Externalised durability and recovery

These limitations are deliberate and keep the implementation focused on deterministic matching behaviour rather than exchange infrastructure concerns.

Selected Code Snippets

#

The core system lives in engine.rs:

// engine.rs

use std::collections::VecDeque;
use tokio::sync::mpsc::Sender as TokioSender;
use uuid::Uuid;
use crate::domain::market::MarketStatus;
use crate::domain::order::{Order, OrderSide};
use crate::domain::stake::Stake;
use crate::domain::trade::Trade;
use crate::matching_engine::order_book::OrderBook;

/// A matching engine will contain the order book for one market only.
///
/// This simplifies the design.
pub struct MatchingEngine {
    pub order_book: OrderBook,
    pub event_sender: TokioSender<Trade>
}

impl MatchingEngine {
    pub fn new(order_book: OrderBook, event_sender: TokioSender<Trade>) -> MatchingEngine {
        MatchingEngine {
            order_book,
            event_sender,
        }
    }

    /// Processes a new order.
    ///
    /// When a new order arrives it needs to be validated, and then
    /// if validation passes, only two outcomes can happen:
    ///
    /// 1. no compatible orders exist, and the new order cannot be immediately matched,
    ///    so insert into order book
    /// 2. at least one compatible order exists so match orders and execute the trade
    ///
    /// When 2. happens, after the trade has been executed we need to update quantities
    /// and if the order cannot be filled in full then the remainder needs to be added
    /// to the order book
    pub fn process_order(&mut self, mut order: Order) -> Result<(), String> {
        if self.validate_order(&order) == false {
            return Err(String::from("Invalid order submitted"))
        }

        // attempt to match the incoming order to the opposite side
        match order.side {
            // search LAYs at the current odds, if any
            OrderSide::Back => {
                // there's a match so fulfill order; we want to match the inbound order to
                // as many orders as possible from the opposite side of the order book
                // -- this generates trading activity
                if let Some(_) = self.order_book.lays.get_mut(&order.odds) {
                    self.match_order(order);
                }
                // no match, so add to order book as is
                else {
                    self.insert_order(order);
                }
            },
            // search BACKs at the current odds, if any
            OrderSide::Lay => {
                // there's a match -> trades generated
                if let Some(_) = self.order_book.backs.get_mut(&order.odds) {
                    self.match_order(order);
                }
                // no match
                else {
                    self.insert_order(order);
                }
            }
        }

        Ok(())
    }

    fn validate_order(&self, order: &Order) -> bool {
        if order.remaining_stake.value <= 0 {
            return false
        }
        if order.odds.ticks <= 0 {
            return false
        }
        if order.market_id != self.order_book.market.market_id {
            return false
        }
        if self.order_book.market.status != MarketStatus::Open {
            return false
        }

        true
    }

    fn match_order(&mut self, mut order: Order) {
        let mut empty_lays = Vec::new();
        let mut empty_backs =  Vec::new();

        let orders = match order.side {
            OrderSide::Back => self.order_book.lays.get_mut(&order.odds),
            OrderSide::Lay => self.order_book.backs.get_mut(&order.odds)
        };

        if let Some(orders) = orders {
            while order.remaining_stake.value > 0 && orders.len() > 0 {
                while let Some(opposite_order) = orders.front_mut() {
                    let stake_size = order.remaining_stake.value
                        .min(opposite_order.remaining_stake.value);

                    let (back_order_id, lay_order_id) = match order.side {
                        OrderSide::Back => (order.order_id, opposite_order.order_id),
                        OrderSide::Lay => (opposite_order.order_id, order.order_id)
                    };

                    self.event_sender.try_send(Trade::new(
                        Uuid::new_v4(),
                        order.market_id,
                        order.odds.clone(),
                        Stake::new(stake_size),
                        back_order_id,
                        lay_order_id
                    )).expect("Failed to send trade");

                    order.remaining_stake.value -= stake_size;
                    opposite_order.remaining_stake.value -= stake_size;

                    if opposite_order.remaining_stake.value == 0 {
                        orders.pop_front();
                    }

                    if orders.is_empty() {
                        match order.side {
                            OrderSide::Back => {
                                empty_lays.push(&order.odds)
                            },
                            OrderSide::Lay => {
                                empty_backs.push(&order.odds)
                            },
                        };
                    }

                    if order.remaining_stake.value == 0 {
                        break;
                    }
                };
            }
        }

        for level in empty_backs {
            self.order_book.backs.remove(level);
        }

        for level in empty_lays {
            self.order_book.lays.remove(level);
        }
    }

    fn insert_order(&mut self, order: Order) {
        let odds = order.odds.clone();

        match order.side {
            OrderSide::Back => {
                self.order_book.backs.entry(odds)
                    .or_insert_with(VecDeque::new)
                    .push_back(order);
            },
            OrderSide::Lay => {
                self.order_book.lays.entry(odds)
                    .or_insert_with(VecDeque::new)
                    .push_back(order);
            },
        }
    }
}

The main function process_order accepts an Order and handles it as described above. From within this function, two other important functions are called, match_order and insert_order. Their names are indicative of their functionality and respectively correspond to the “Match Found” and “No Match” branches in the diagram.

When a match is found the engine emits a trade event through an asynchronous Multi Producer Single Consumer (MPSC) channel:

self.event_sender.try_send(Trade::new(...))

Throughout this article we’ve treated the order book as an implementation detail of the matching engine. In reality, the order book is the central data structure that makes deterministic matching possible.

In the next article we’ll examine its internal representation, how orders are organised by odds level, and why the chosen data structures make FIFO matching efficient.