Limit Order Book

A limit order book is used in stock exchanges to match a buy order with a sell order based on price and time priority

In Stock trading, exchanges like NYSE (New York Stock Exchange) maintains an order book for every security or stock which is traded on their exchange e.g. GOOG, which is a symbol of Google's stock. There are mainly two kinds of orders customers can send, a buy order, and a sell order. When we use Limit Price, which means buy order with a limit price of $50 can be executed if it found a sell order of $50 or an order of lower price says $49, but it can not be executed with a sell order of price $51. Similarly, a sell order can execute for a price, which is either equal to or higher than the limit price. In general, a LIMIT order executes if it found a specified price or better price(lower in the case of a buy, and higher in the case of sell).

Orders are executed on a first come first serve basis, so exchange also maintains a time priority. Now, let's see the flow, an order comes to exchange, exchange looks order book for that symbol, if it found a match it executes order otherwise, it adds that order at the end of a price queue, which represents time priority, head of the queue represents the order with highest time priority i.e. the order which comes before all the order below it.

Now our goal is to perform the above operation as quickly as possible. If you look at it closely, it involves finding the opposite order of matching the price, which is equal to or less/greater than the specified price, removing the order from the order book if it matched or canceled, adding order into the order book at an appropriate place if not matched.

Rough Solution (LLD-Machine Coding)

// Factory Method Pattern for creating orders
interface OrderFactory {
    Order createOrder(boolean isBuy, double price, int quantity);
}

class BuyOrderFactory implements OrderFactory {
    @Override
    public Order createOrder(boolean isBuy, double price, int quantity) {
        return new Order(true, price, quantity);
    }
}

class SellOrderFactory implements OrderFactory {
    @Override
    public Order createOrder(boolean isBuy, double price, int quantity) {
        return new Order(false, price, quantity);
    }
}

// Observer Pattern for notifying clients of price changes
interface Observer {
    void update(double bestBuyPrice, double bestSellPrice);
}

class Client implements Observer {
    private String name;

    public Client(String name) {
        this.name = name;
    }

    @Override
    public void update(double bestBuyPrice, double bestSellPrice) {
        System.out.println("Client " + name + " notified - Best Buy: " + bestBuyPrice + ", Best Sell: " + bestSellPrice);
    }
}

// Command Pattern for order actions
interface Command {
    void execute();
}

class AddBuyOrderCommand implements Command {
    private LimitOrderBook limitOrderBook;
    private Order order;

    public AddBuyOrderCommand(LimitOrderBook limitOrderBook, Order order) {
        this.limitOrderBook = limitOrderBook;
        this.order = order;
    }

    @Override
    public void execute() {
        limitOrderBook.addBuyOrder(order);
    }
}

class AddSellOrderCommand implements Command {
    private LimitOrderBook limitOrderBook;
    private Order order;

    public AddSellOrderCommand(LimitOrderBook limitOrderBook, Order order) {
        this.limitOrderBook = limitOrderBook;
        this.order = order;
    }

    @Override
    public void execute() {
        limitOrderBook.addSellOrder(order);
    }
}

class CancelOrderCommand implements Command {
    private LimitOrderBook limitOrderBook;
    private Order order;

    public CancelOrderCommand(LimitOrderBook limitOrderBook, Order order) {
        this.limitOrderBook = limitOrderBook;
        this.order = order;
    }

    @Override
    public void execute() {
        limitOrderBook.cancelOrder(order);
    }
}

// Strategy Pattern for different matching algorithms
interface MatchingStrategy {
    void matchOrders(Map<Double, List<Order>> buyOrders, Map<Double, List<Order>> sellOrders);
}

class FIFOMatchingStrategy implements MatchingStrategy {
    @Override
    public void matchOrders(Map<Double, List<Order>> buyOrders, Map<Double, List<Order>> sellOrders) {
        // FIFO-based matching logic
        System.out.println("Matching orders using FIFO strategy...");
        // Matching logic goes here
    }
}

class LIFOMatchingStrategy implements MatchingStrategy {
    @Override
    public void matchOrders(Map<Double, List<Order>> buyOrders, Map<Double, List<Order>> sellOrders) {
        // LIFO-based matching logic
        System.out.println("Matching orders using LIFO strategy...");
        // Matching logic goes here
    }
}

// LimitOrderBook Class implementing Observer Pattern
public class LimitOrderBook {
    private Map<Double, List<Order>> buyOrders;
    private Map<Double, List<Order>> sellOrders;
    private List<Observer> observers;
    private MatchingStrategy matchingStrategy;

    public LimitOrderBook() {
        buyOrders = new TreeMap<>(Collections.reverseOrder());
        sellOrders = new TreeMap<>();
        observers = new ArrayList<>();
    }

    // Observer pattern: Register clients to get notifications
    public void registerObserver(Observer observer) {
        observers.add(observer);
    }

    public void unregisterObserver(Observer observer) {
        observers.remove(observer);
    }

    // Notify all observers of price changes
    private void notifyObservers() {
        double bestBuyPrice = getBestBuyPrice();
        double bestSellPrice = getBestSellPrice();
        for (Observer observer : observers) {
            observer.update(bestBuyPrice, bestSellPrice);
        }
    }

    // Set the matching strategy dynamically
    public void setMatchingStrategy(MatchingStrategy matchingStrategy) {
        this.matchingStrategy = matchingStrategy;
    }

    // Execute order matching based on the selected strategy
    public void matchOrders() {
        if (matchingStrategy != null) {
            matchingStrategy.matchOrders(buyOrders, sellOrders);
            notifyObservers();
        }
    }

    public void addBuyOrder(Order order) {
        double price = order.getPrice();
        buyOrders.computeIfAbsent(price, k -> new ArrayList<>()).add(order);
        notifyObservers();
    }

    public void addSellOrder(Order order) {
        double price = order.getPrice();
        sellOrders.computeIfAbsent(price, k -> new ArrayList<>()).add(order);
        notifyObservers();
    }

    public void cancelOrder(Order order) {
        double price = order.getPrice();
        if (order.isBuy()) {
            buyOrders.getOrDefault(price, new ArrayList<>()).remove(order);
        } else {
            sellOrders.getOrDefault(price, new ArrayList<>()).remove(order);
        }
        notifyObservers();
    }

    public double getBestBuyPrice() {
        return buyOrders.isEmpty() ? Double.MAX_VALUE : buyOrders.keySet().iterator().next();
    }

    public double getBestSellPrice() {
        return sellOrders.isEmpty() ? Double.MIN_VALUE : sellOrders.keySet().iterator().next();
    }
}

// Order class remains the same
public class Order {
    private boolean isBuy;
    private double price;
    private int quantity;

    public Order(boolean isBuy, double price, int quantity) {
        this.isBuy = isBuy;
        this.price = price;
        this.quantity = quantity;
    }

    public boolean isBuy() {
        return isBuy;
    }

    public double getPrice() {
        return price;
    }

    public int getQuantity() {
        return quantity;
    }
}

// Main class for testing
public class Main {
    public static void main(String[] args) {
        LimitOrderBook orderBook = new LimitOrderBook();

        // Create clients (observers)
        Client client1 = new Client("Tekkion");
        Client client2 = new Client("Nupay");

        // Register clients to receive notifications
        orderBook.registerObserver(client1);
        orderBook.registerObserver(client2);

        // Create orders using factory
        OrderFactory buyOrderFactory = new BuyOrderFactory();
        OrderFactory sellOrderFactory = new SellOrderFactory();

        Order buyOrder = buyOrderFactory.createOrder(true, 100.0, 10);
        Order sellOrder = sellOrderFactory.createOrder(false, 101.0, 5);

        // Execute add order commands
        Command addBuyOrderCommand = new AddBuyOrderCommand(orderBook, buyOrder);
        Command addSellOrderCommand = new AddSellOrderCommand(orderBook, sellOrder);

        addBuyOrderCommand.execute();
        addSellOrderCommand.execute();

        // Set matching strategy and match orders
        orderBook.setMatchingStrategy(new FIFOMatchingStrategy());
        orderBook.matchOrders();
    }
}