Design a Stock Exchange: The Order Matching Engine That Won't Lose Money

// io.thecodeforge — System Design tutorial

import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.locks.ReentrantLock;

public class OrderBook {
    // Price -> Queue of orders. ConcurrentSkipListMap for sorted iteration.
    private final ConcurrentSkipListMap<Long, Deque<Order>> bids = new ConcurrentSkipListMap<>(Collections.reverseOrder());
    private final ConcurrentSkipListMap<Long, Deque<Order>> asks = new ConcurrentSkipListMap<>();
    private final ReentrantLock lock = new ReentrantLock(); // coarse lock, will improve later

    public void addOrder(Order order) {
        lock.lock();
        try {
            var side = order.side == Side.BUY ? bids : asks;
            side.computeIfAbsent(order.price, k -> new ArrayDeque<>()).addLast(order);
        } finally {
            lock.unlock();
        }
    }

    public Order getBestBid() {
        lock.lock();
        try {
            var entry = bids.firstEntry();
            return entry != null ? entry.getValue().peekFirst() : null;
        } finally {
            lock.unlock();
        }
    }

    // ... matching logic
}

enum Side { BUY, SELL }

class Order {
    long id;
    Side side;
    long price; // in cents to avoid floating point
    long quantity;
    long timestamp;
    volatile Status status = Status.ACTIVE;
}

enum Status { ACTIVE, CANCELLED, MATCHED }

// io.thecodeforge — System Design tutorial

public class MatchingEngine {
    private final OrderBook book = new OrderBook();

    public List<Trade> matchOrder(Order incoming) {
        List<Trade> trades = new ArrayList<>();
        book.lock.lock();
        try {
            var oppositeSide = incoming.side == Side.BUY ? book.asks : book.bids;
            var bestPrice = oppositeSide.firstEntry();
            while (bestPrice != null && canTrade(incoming, bestPrice.getKey())) {
                var queue = bestPrice.getValue();
                var resting = queue.peekFirst();
                while (resting != null && incoming.quantity > 0) {
                    long tradeQty = Math.min(incoming.quantity, resting.quantity);
                    long tradePrice = resting.price; // always at resting price
                    trades.add(new Trade(incoming.id, resting.id, tradePrice, tradeQty));
                    incoming.quantity -= tradeQty;
                    resting.quantity -= tradeQty;
                    if (resting.quantity == 0) {
                        queue.pollFirst();
                        resting = queue.peekFirst();
                    }
                }
                if (queue.isEmpty()) {
                    oppositeSide.pollFirstEntry();
                }
                bestPrice = oppositeSide.firstEntry();
            }
            if (incoming.quantity > 0) {
                book.addOrder(incoming);
            }
        } finally {
            book.lock.unlock();
        }
        return trades;
    }

    private boolean canTrade(Order incoming, long oppositePrice) {
        return incoming.side == Side.BUY ? incoming.price >= oppositePrice : incoming.price <= oppositePrice;
    }
}

class Trade {
    long buyOrderId, sellOrderId, price, quantity;
    Trade(long buy, long sell, long price, long qty) { this.buyOrderId = buy; this.sellOrderId = sell; this.price = price; this.quantity = qty; }
}

// io.thecodeforge — System Design tutorial

import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.atomic.AtomicReference;

public class LockFreeOrderBook {
    private final ConcurrentSkipListMap<Long, ConcurrentLinkedDeque<Order>> bids = new ConcurrentSkipListMap<>(java.util.Collections.reverseOrder());
    private final ConcurrentSkipListMap<Long, ConcurrentLinkedDeque<Order>> asks = new ConcurrentSkipListMap<>();

    public void addOrder(Order order) {
        var side = order.side == Side.BUY ? bids : asks;
        var queue = side.computeIfAbsent(order.price, k -> new ConcurrentLinkedDeque<>());
        queue.addLast(order);
    }

    public Order getBestBid() {
        var entry = bids.firstEntry();
        if (entry == null) return null;
        return entry.getValue().peekFirst();
    }

    // Matching: atomically dequeue and CAS status
    public boolean tryMatch(Order incoming) {
        var oppositeSide = incoming.side == Side.BUY ? asks : bids;
        var entry = oppositeSide.firstEntry();
        while (entry != null && canTrade(incoming, entry.getKey())) {
            var queue = entry.getValue();
            Order resting = queue.peekFirst();
            while (resting != null) {
                if (resting.status.compareAndSet(Status.ACTIVE, Status.MATCHED)) {
                    // matched
                    long tradeQty = Math.min(incoming.quantity, resting.quantity);
                    incoming.quantity -= tradeQty;
                    resting.quantity -= tradeQty;
                    if (resting.quantity == 0) {
                        queue.pollFirst(); // remove from queue
                    }
                    return true; // simplified: one match per call
                } else {
                    // order was cancelled or already matched, skip
                    queue.pollFirst();
                    resting = queue.peekFirst();
                }
            }
            oppositeSide.pollFirstEntry();
            entry = oppositeSide.firstEntry();
        }
        return false;
    }
}

// Order with AtomicReference for status
class Order {
    long id;
    Side side;
    long price;
    volatile long quantity;
    final AtomicReference<Status> status = new AtomicReference<>(Status.ACTIVE);
    // ...
}

// io.thecodeforge — System Design tutorial

import com.lmax.disruptor.*;
import com.lmax.disruptor.dsl.Disruptor;
import java.util.concurrent.Executors;

public class MarketDataPublisher {
    public static class MarketDataEvent {
        long sequence;
        long price;
        long quantity;
        byte type; // 0=TRADE, 1=ADD, 2=CANCEL
        // ...
    }

    private final Disruptor<MarketDataEvent> disruptor;
    private final RingBuffer<MarketDataEvent> ringBuffer;

    public MarketDataPublisher() {
        disruptor = new Disruptor<>(MarketDataEvent::new, 1024, Executors.defaultThreadFactory());
        disruptor.handleEventsWith((event, sequence, endOfBatch) -> {
            // Send via UDP multicast
            sendUdp(event);
        });
        ringBuffer = disruptor.start();
    }

    public void publishTrade(long price, long quantity) {
        long seq = ringBuffer.next();
        try {
            var event = ringBuffer.get(seq);
            event.type = 0;
            event.price = price;
            event.quantity = quantity;
            event.sequence = seq;
        } finally {
            ringBuffer.publish(seq);
        }
    }

    private void sendUdp(MarketDataEvent event) {
        // serialize and send
    }
}

// io.thecodeforge — System Design tutorial

[Order Submission] -> [Validation Service] -> [Risk Service] -> [Matching Engine] -> [Trade Reporting] -> [Settlement]

Each step communicates via Kafka topics:
- orders.incoming
- orders.validated
- orders.risk_checked
- trades.executed
- trades.reported

// io.thecodeforge — System Design tutorial

import java.util.concurrent.ConcurrentHashMap;

public class RiskService {
    private final ConcurrentHashMap<String, Long> positionLimits = new ConcurrentHashMap<>();
    private final ConcurrentHashMap<String, Long> currentPositions = new ConcurrentHashMap<>();

    public boolean checkOrder(Order order) {
        // Check price collar: no more than 10% away from last trade
        long lastTradePrice = getLastTradePrice(order.symbol);
        if (Math.abs(order.price - lastTradePrice) > lastTradePrice * 0.1) {
            return false; // price too far
        }
        // Check position limit
        String key = order.traderId + ":" + order.symbol;
        long current = currentPositions.getOrDefault(key, 0L);
        long newPosition = order.side == Side.BUY ? current + order.quantity : current - order.quantity;
        long limit = positionLimits.getOrDefault(key, Long.MAX_VALUE);
        if (Math.abs(newPosition) > limit) {
            return false;
        }
        return true;
    }

    private long getLastTradePrice(String symbol) { /* from market data */ return 0; }
}

// io.thecodeforge — System Design tutorial

import java.io.*;
import java.nio.*;
import java.nio.channels.*;

public class WriteAheadLog {
    private final FileChannel channel;
    private final ByteBuffer buffer = ByteBuffer.allocateDirect(8192);

    public WriteAheadLog(String path) throws IOException {
        var file = new RandomAccessFile(path, "rw");
        channel = file.getChannel();
    }

    public void logOrder(Order order) {
        buffer.clear();
        buffer.putLong(order.id);
        buffer.putInt(order.side.ordinal());
        buffer.putLong(order.price);
        buffer.putLong(order.quantity);
        buffer.putLong(System.nanoTime());
        buffer.flip();
        try {
            channel.write(buffer);
        } catch (IOException e) {
            throw new RuntimeException("WAL write failed", e);
        }
    }

    public void flush() {
        try {
            channel.force(true); // sync to disk
        } catch (IOException e) {
            throw new RuntimeException("WAL flush failed", e);
        }
    }
}