Modeling an Order Book for an Exchange Application

An order book is a fundamental component of an exchange application, responsible for tracking buy and sell orders for trading pairs. Here’s how to efficiently model and implement one.

Understanding the Order Book

An order book maintains two primary lists:

Bids: Buy orders prioritized by highest price first.
Asks: Sell orders prioritized by lowest price first.

Orders are matched based on price and time:

Higher-priced bids and lower-priced asks are matched first.
For orders at the same price, older orders are matched first (FIFO).

Choosing the Right Data Structures

Efficient management of the order book requires appropriate data structures:

Price Levels: Use a balanced binary search tree (e.g., Red-Black Tree or AVL Tree) to store price levels for quick lookups, insertions, and deletions.
Order Queues: Use a FIFO queue at each price level to prioritize older orders.

Suggested Data Structures

Price Level Node

class PriceLevel:
    def __init__(self, price):
        self.price = price
        self.orders = deque()  # FIFO queue of orders

Order

class Order:
    def __init__(self, order_id, trader_id, price, quantity, side):
        self.order_id = order_id  # Unique identifier
        self.trader_id = trader_id  # Who placed the order
        self.price = price
        self.quantity = quantity
        self.side = side  # 'buy' or 'sell'
        self.timestamp = time.time()  # For time-priority

Order Book

class OrderBook:
    def __init__(self):
        self.bids = SortedDict(reverse=True)  # Sorted descending by price
        self.asks = SortedDict()  # Sorted ascending by price

SortedDict: Use a library like sortedcontainers in Python or a tree-based map in other languages to implement the price levels.
deque: Use a double-ended queue for maintaining the FIFO order of orders at each price level.

4. Implement Key Operations

Here are the main operations you need to support:

Add Order

Determine the side (buy or sell).
Check if the price exists in the relevant SortedDict.
Add the order to the corresponding price level (create it if necessary).

Match Order

Match the incoming order against the opposite side of the book.

For buy orders, match with the lowest ask.
For sell orders, match with the highest bid.

Execute trades by reducing the quantities of matching orders.
Remove fully filled orders.

Remove Order

Locate the price level and order in the tree and queue.
Remove the order and clean up the price level if it’s empty.

5. Example Code

Here’s an example implementation for adding and matching orders:

class OrderBook:
    def __init__(self):
        self.bids = SortedDict(reverse=True)  # Higher prices first
        self.asks = SortedDict()  # Lower prices first

    def add_order(self, order):
        book = self.bids if order.side == 'buy' else self.asks

        if order.price not in book:
            book[order.price] = PriceLevel(order.price)

        book[order.price].orders.append(order)

    def match_order(self, order):
        book = self.asks if order.side == 'buy' else self.bids
        matched_orders = []

        while order.quantity > 0 and book:
            best_price = book.peekitem(0)[0]

            if (order.side == 'buy' and order.price < best_price) or \
               (order.side == 'sell' and order.price > best_price):
                break  # No match

            best_level = book[best_price]
            while order.quantity > 0 and best_level.orders:
                match = best_level.orders.popleft()
                trade_qty = min(order.quantity, match.quantity)
                order.quantity -= trade_qty
                match.quantity -= trade_qty
                matched_orders.append((match.order_id, trade_qty))

                if match.quantity == 0:  # Remove fully filled orders
                    continue

            if not best_level.orders:
                del book[best_price]  # Remove empty price levels

        return matched_orders

6. Optimization Tips

Memory Management: Use efficient data structures for queues and trees to reduce overhead.
Concurrency: Use locks or atomic operations to handle simultaneous updates.
Persistence: Store the order book state in a database for recovery.
Testing: Simulate large datasets to verify performance and correctness.

7. Scaling

For high-frequency trading, use in-memory stores like Redis for distributed order books.
Consider sharding based on trading pairs for horizontal scaling.