Design an Order Matching Engine

Looking for the Solution Code?

This page covers the design requirements and high-level approach.

The complete implementation code (Python, Java, C++, etc.), UML Class Diagrams, and detailed step-by-step explanation are available in our Interactive Playground.

Open Playground to View Solution →

What is the Order Matching Engine Problem?

Design an order matching engine for a stock exchange that processes buy and sell orders, maintains an order book, and executes trades based on price-time priority matching. The system should handle order submission, matching algorithms, trade execution, and notify interested parties about trades and order book updates. The design should be thread-safe, performant, and support concurrent order processing.

In this problem, you’ll design a core engine that maintains an “Order Book” and executes trades the moment a price match is found.

Why This Problem?

Order Matching Engine is the ultimate test of:

• Priority Matching - Enforcing Price-Time priority (best price first, then earliest timestamp).
• Partial Fills - Handling trades where quantities don’t match exactly.
• Data Structures - Using Priority Queues or TreeMap for efficient sorted order maintenance.
• Observer Pattern - Real-time broadcasting of trade executions and order book updates.
• Concurrency - Ensuring thread-safe submission and matching in a high-throughput environment.

---

Problem Overview

Design a system that accepts Limit and Market orders, maintains a sorted order book, and matches buyers with sellers efficiently.

Core Requirements

Functional Requirements:

• Order Entry: Accept Buy/Sell orders with ID, timestamp, symbol, price, quantity, and type (Limit/Market).
• Order Book: Maintain separate books for Bids and Asks, sorted by price-time priority.
• Matching Logic: Execute trades when Buy price >= Sell price (at the maker’s price).
• Partial Fills: Handle cases where quantities don’t match exactly, keeping remainders in the book.
• Cancellations: Support cancelling unexecuted orders and removing them from the book.
• Trade Recording: Record executed trade details (Buyer ID, Seller ID, Price, Qty, Timestamp).
• Notifications: Inform interested parties (traders, data feeds) of every match and book update.
• Book Management: Efficiently remove filled orders and adjust partially filled ones.

Non-Functional Requirements:

• Low Latency: Optimized for high-volume, quick matching using efficient data structures.
• Thread Safety: Absolute prevention of race conditions during concurrent order submissions.
• Flexibility: Swappable matching strategies (Strategy Pattern) and order types (Command Pattern).
• Integrity: Ensure the order book remains consistent even under extreme concurrent load.
• Determinism: The same input sequence must strictly result in the same matching outcome.

---

What’s Expected?

1. System Architecture

The engine coordinates between the OrderGateway, the OrderBook, and the TradeDispatcher.

2. Key Classes to Design

classDiagram
    class OrderBook {
        -TreeMap~Price, List~Order~~ bids
        -TreeMap~Price, List~Order~~ asks
        +addOrder(order)
        +match()
    }
    
    class Order {
        -String id
        -Side side (Buy/Sell)
        -double price
        -long quantity
        -long timestamp
    }
    
    class Trade {
        -String buyerOrderId
        -String sellerOrderId
        -double price
        -long quantity
    }

    class MatchingEngine {
        -OrderBook book
        -List~Observer~ observers
        +processOrder(order)
    }

    MatchingEngine --> OrderBook
    OrderBook "1" *-- "many" Order
    MatchingEngine --> Trade

---

System Flow

Matching Logic Flow

---

Key Design Challenges

1. Data Structure for Price-Time Priority

You need to constantly find the maximum bid and the minimum ask.

Solution: Use a Balanced Binary Search Tree (like TreeMap in Java or std::map in C++) where the key is the Price. For each Price, maintain a LinkedList or Queue of Orders to preserve Time priority. This allows $O(\log P)$ insertion and $O(1)$ access to the best price.

2. Handling Partial Fills

A single large Buy order might be matched against 10 small Sell orders.

Solution: Use an Iterative Matching Loop. The engine keeps matching the incoming order against the top of the opposite side of the book until either the incoming order is fully filled or the price no longer matches.

3. Concurrency vs. Fairness

If you use a simple lock on the entire OrderBook, performance will suffer. If you don’t lock, two buyers might match with the same seller.

Solution: Use a Single-Threaded Execution Model for the matching logic itself (similar to LMAX Disruptor or Node.js). Buffer all incoming orders in a high-speed Lock-Free Queue and have one dedicated thread process the matching. This eliminates locking overhead and ensures strict determinism.

---

What You’ll Learn

By solving this problem, you’ll master:

• ✅ Priority-Based Sorting - Managing complex sorting criteria (Price then Time).
• ✅ Trade Execution Logic - Handling partial fills and atomic updates.
• ✅ Performance Optimization - Using trees and queues for low-latency operations.
• ✅ Deterministic Systems - Designing logic that is predictable and fair.

---

View Complete Solution & Practice

Ready to see the full implementation? Open the interactive playground to access:

• 🎯 Step-by-step guidance through the 8-step LLD approach
• 📊 Interactive UML builder to visualize your design
• 💻 Complete Code Solutions in Python, Java, C++, TypeScript, JavaScript, C#
• 🤖 AI-powered review of your design and code

🚀 View Solution in Playground

---

Related Problems

After mastering the Order Matching Engine, try these similar problems:

• Rate Limiter - High-throughput request control.
• Task Scheduler - Priority-based execution and queuing.
• LRU Cache - Fast lookups and eviction logic.