Design an Order Matching Engine (Stock Brokerage System)

Problem Statement

Design an in-memory Order Matching Engine for a stock brokerage system (similar to Zerodha or Groww). The matching engine must support submitting buy and sell orders for different stock symbols, manage stock-specific order books using price-time priority, execute matches when buy prices meet or exceed sell prices, and output trades containing execution prices and quantities.

Asked In Companies

Goldman Sachs Morgan Stanley Groww AngelOne

---

Functional Requirements

• Support BUY and SELL orders.
• Provide an OrderBook per stock symbol that tracks orders using price-time priority.
• Sort BUY orders in descending order (highest bidding price first).
• Sort SELL orders in ascending order (lowest asking price first).
• Execute trades immediately if an incoming order matches existing opposite orders.
• Support partial order fills (e.g., if a buy order asks for 10 shares and a sell order offers 4, fill 4 and leave 6 in the queue).
• Ensure thread safety during simultaneous order placements.

---

Objects Required

• OrderType (Enum mapping BUY and SELL)
• Order (Data class encapsulating order info)
• Trade (Value object tracking matching deals)
• OrderBook (Core queue collector processing stock bids)
• MatchingEngine (Orchestrator routing requests to correct books)

---

OrderType Enum

We define the direction of the trade using a basic enum. This separates buy logic from sell logic cleanly.

public enum OrderType {
    BUY,
    SELL
}

This simple enum prevents string matching bugs and guides the order sorting logic inside the priority queues.

---

Order Class

The Order class represents a client's request. It contains values representing target quantity, execution constraints, and creation timelines.

public class Order {
    private final String id;
    private final String symbol;
    private final OrderType type;
    private final double price;
    private int quantity;
    private final long timestamp;

    public Order(String id, String symbol, OrderType type, double price, int quantity) {
        this.id = id;
        this.symbol = symbol;
        this.type = type;
        this.price = price;
        this.quantity = quantity;
        this.timestamp = System.nanoTime(); // Use nanoseconds for ultra-precise sorting
    }

    public String getId() { return id; }
    public String getSymbol() { return symbol; }
    public OrderType getType() { return type; }
    public double getPrice() { return price; }
    public int getQuantity() { return quantity; }
    public void setQuantity(int quantity) { this.quantity = quantity; }
    public long getTimestamp() { return timestamp; }
}

The constructor captures parameters and assigns a nanosecond-precision timestamp. setQuantity() allows the matching process to mutate quantity directly during partial fills.

---

Trade Class

A Trade object is generated whenever a buy order and a sell order intersect. It serves as an immutable transaction record.

public class Trade {
    private final String buyOrderId;
    private final String sellOrderId;
    private final double price;
    private final int quantity;

    public Trade(String buyOrderId, String sellOrderId, double price, int quantity) {
        this.buyOrderId = buyOrderId;
        this.sellOrderId = sellOrderId;
        this.price = price;
        this.quantity = quantity;
    }

    @Override
    public String toString() {
        return String.format("Executed Trade: [BuyID: %s, SellID: %s] | Price: %.2f | Qty: %d",
                buyOrderId, sellOrderId, price, quantity);
    }
}

The constructor freezes transaction details. The overridden toString() helps output logs to console when displaying execution paths.

---

OrderBook Class

The OrderBook holds stock order priority queues. It enforces order sorting priorities and contains the primary logic for identifying match candidates.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class OrderBook {
    private final String symbol;
    private final PriorityQueue<Order> buyOrders;
    private final PriorityQueue<Order> sellOrders;

    public OrderBook(String symbol) {
        this.symbol = symbol;
        
        // Buy: Descending by Price, then Ascending by Time (nanoseconds)
        this.buyOrders = new PriorityQueue<>(
            Comparator.comparingDouble(Order::getPrice).reversed()
                      .thenComparingLong(Order::getTimestamp)
        );

        // Sell: Ascending by Price, then Ascending by Time (nanoseconds)
        this.sellOrders = new PriorityQueue<>(
            Comparator.comparingDouble(Order::getPrice)
                      .thenComparingLong(Order::getTimestamp)
        );
    }

    public synchronized List<Trade> addOrder(Order order) {
        if (order.getType() == OrderType.BUY) {
            buyOrders.add(order);
        } else {
            sellOrders.add(order);
        }
        return match();
    }

    private List<Trade> match() {
        List<Trade> executedTrades = new ArrayList<>();

        while (!buyOrders.isEmpty() && !sellOrders.isEmpty()) {
            Order bestBuy = buyOrders.peek();
            Order bestSell = sellOrders.peek();

            // Check if buy price meets or exceeds sell price
            if (bestBuy.getPrice() >= bestSell.getPrice()) {
                double matchPrice = bestSell.getPrice(); // standard rule: match at maker's price
                int matchQuantity = Math.min(bestBuy.getQuantity(), bestSell.getQuantity());

                executedTrades.add(new Trade(bestBuy.getId(), bestSell.getId(), matchPrice, matchQuantity));

                bestBuy.setQuantity(bestBuy.getQuantity() - matchQuantity);
                bestSell.setQuantity(bestSell.getQuantity() - matchQuantity);

                // Evict completely filled orders
                if (bestBuy.getQuantity() == 0) {
                    buyOrders.poll();
                }
                if (bestSell.getQuantity() == 0) {
                    sellOrders.poll();
                }
            } else {
                break; // No matching candidates available
            }
        }
        return executedTrades;
    }
}

Here is an explanation of the core operations in the OrderBook class:

• The constructor initializes custom comparators for buy/sell priority queues to maintain price-time priority.
• addOrder() registers an incoming order in the appropriate queue and calls the internal match() method. This is synchronized to prevent race conditions during updates.
• match() evaluates the top of both queues. If prices overlap, it resolves trade quantities, updates order states (deducting filled amounts), registers a Trade object, and pops fully resolved orders.

---

MatchingEngine Class

The MatchingEngine acts as the routing orchestrator, mapping stock symbols to their respective OrderBook instances.

import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class MatchingEngine {
    private final Map<String, OrderBook> books;

    public MatchingEngine() {
        this.books = new ConcurrentHashMap<>();
    }

    public List<Trade> processOrder(Order order) {
        OrderBook book = books.computeIfAbsent(order.getSymbol(), OrderBook::new);
        return book.addOrder(order);
    }
}

The processOrder() method fetches the target book using a thread-safe ConcurrentHashMap and calls addOrder().

---

Main Driver Class

This class tests our LLD matching engine by simulating concurrent order placements and displaying the matching transactions.

import java.util.List;

public class Main {
    public static void main(String[] args) {
        MatchingEngine engine = new MatchingEngine();

        System.out.println("--- Submitting Initial Orders ---");

        // Submit Sell orders for Apple (AAPL)
        Order sell1 = new Order("S1", "AAPL", OrderType.SELL, 150.00, 10);
        Order sell2 = new Order("S2", "AAPL", OrderType.SELL, 149.50, 5);
        
        engine.processOrder(sell1);
        engine.processOrder(sell2);

        System.out.println("Sell orders placed: S1 (10 shares @ 150.0), S2 (5 shares @ 149.5)");

        // Submit Buy order that matches S2 completely, and S1 partially
        Order buy1 = new Order("B1", "AAPL", OrderType.BUY, 151.00, 12);
        System.out.println("\nPlacing Buy order B1 (12 shares @ 151.0):");
        
        List<Trade> trades1 = engine.processOrder(buy1);
        for (Trade t : trades1) {
            System.out.println(t);
        }

        // B1 requested 12 shares.
        // It matches S2 (5 shares @ 149.5) -> leaves 7 requested.
        // It matches S1 (7 shares @ 150.0) -> S1 left with 3 shares.

        // Place another Buy order below remaining sell price to test no-match scenario
        Order buy2 = new Order("B2", "AAPL", OrderType.BUY, 148.00, 5);
        System.out.println("\nPlacing Buy order B2 (5 shares @ 148.0):");
        List<Trade> trades2 = engine.processOrder(buy2);
        if (trades2.isEmpty()) {
            System.out.println("No immediate trade executed. B2 added to book.");
        }
    }
}

The main() driver initializes the system, registers sell requests, submits an overlapping buy request, and demonstrates partial fills and queue retention rules.

---

Class Diagram

---

Also See

• Most Commonly Asked Low Level Design Interview Questions
• Top 10 Low Level Design Interview Questions