Project: Matching Engine

A matching engine is the part of an exchange that receives orders, pairs buyers with sellers, and reports trades. This project builds one in four stages on top of the order book from Project: Limit Order Book. Each stage is a complete program. The order types and time-in-force values come from Market Data, Orders, and FIX, and stage 3 reuses the sequence and ring buffer design from The LMAX Disruptor Pattern.

Stage	Adds	Shows
1	Price-time priority, partial fills, trade events	Matching rules on a scripted stream
2	Market orders, IOC, FOK, cancel, rejects	Event model with sealed records
3	Gateway thread, input ring buffer, single engine thread	Same events as a direct call
4	Write-ahead command journal and replay	Recovery after a crash gives identical events

The book uses the TreeMap layout of the order book's stage 1, because it keeps the matching code short. The array book and order pool of stages 2 and 3 of that project plug in behind the same methods.

Problem statement

Build the engine for one instrument. It accepts new orders (limit or market, with DAY, IOC, or FOK) and cancels, matches them by price-time priority, and emits events: trades, rested orders, cancels, and rejects. Given the same input sequence, it must produce the same events every time, so that the engine can be recovered or audited by replaying its input.

Requirements

Price-time priority: an incoming order trades first with the best opposite price, and inside a price level with the order that arrived first.
The trade price is the resting order's price. A buy limit at 10030 that meets an ask at 10027 trades at 10027; the taker (incoming order) gets the better price.
An order trades against as many resting orders as it needs (partial fills on both sides); the remainder of a DAY limit order rests.
Market orders never rest; their unfilled remainder is cancelled. IOC remainders are cancelled. FOK orders either fill completely at once or are cancelled with no trades.
Duplicate ids, non-positive quantities, and cancels of unknown ids are rejected with an event, not an exception.
One thread owns the book. Other threads hand it commands through a ring buffer.
Every command is journaled before it is processed, and replaying the journal reproduces the event stream exactly.

Stage 1: price-time matching with partial fills

The engine looks at the best opposite level while the incoming order still has quantity and the level's price is acceptable (ask <= limit for a buy, bid >= limit for a sell). Inside the level it fills the oldest order first. A resting order that reaches zero leaves the queue; an empty level leaves the map.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;

record Trade(long taker, long maker, long price, long qty) {}

final class Order {
    final long id;
    final boolean buy;
    final long price;
    long qty;
    Order(long id, boolean buy, long price, long qty) { this.id = id; this.buy = buy; this.price = price; this.qty = qty; }
}

final class Engine {
    private final TreeMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, ArrayDeque<Order>> asks = new TreeMap<>();
    final List<Trade> trades = new ArrayList<>();

    /** Matches a DAY limit order and rests the remainder. Returns the quantity that rested. */
    long limit(long id, boolean buy, long price, long qty) {
        TreeMap<Long, ArrayDeque<Order>> opposite = buy ? asks : bids;
        while (qty > 0 && !opposite.isEmpty()) {
            long px = opposite.firstKey();
            if (buy ? px > price : px < price) break;          // best opposite price not acceptable
            ArrayDeque<Order> level = opposite.firstEntry().getValue();
            while (qty > 0 && !level.isEmpty()) {
                Order maker = level.peekFirst();
                long q = Math.min(qty, maker.qty);
                trades.add(new Trade(id, maker.id, px, q));
                maker.qty -= q;
                qty -= q;
                if (maker.qty == 0) level.pollFirst();
            }
            if (level.isEmpty()) opposite.remove(px);
        }
        if (qty > 0) (buy ? bids : asks).computeIfAbsent(price, p -> new ArrayDeque<>()).addLast(new Order(id, buy, price, qty));
        return qty;
    }

    String book() {
        return "bids " + levels(bids) + " asks " + levels(asks);
    }

    private static List<String> levels(TreeMap<Long, ArrayDeque<Order>> side) {
        List<String> out = new ArrayList<>();
        side.forEach((px, q) -> {
            StringBuilder s = new StringBuilder(px + "x" + q.stream().mapToLong(o -> o.qty).sum() + "(");
            q.forEach(o -> s.append(s.charAt(s.length() - 1) == '(' ? "" : ",").append(o.id));
            out.add(s.append(')').toString());
        });
        return out;
    }
}

public class Main {
    static void send(Engine e, long id, boolean buy, long price, long qty) {
        int before = e.trades.size();
        long rested = e.limit(id, buy, price, qty);
        System.out.println((buy ? "BUY  " : "SELL ") + id + " " + qty + "@" + price + " -> rested " + rested);
        e.trades.subList(before, e.trades.size()).forEach(t -> System.out.println("     " + t));
    }

    public static void main(String[] args) {
        Engine e = new Engine();
        send(e, 1, false, 10_027, 100);
        send(e, 2, false, 10_027, 200);
        send(e, 3, false, 10_028, 300);
        send(e, 4, true, 10_025, 100);
        System.out.println(e.book());
        send(e, 5, true, 10_028, 350);
        System.out.println(e.book());
        send(e, 6, false, 10_024, 150);
        System.out.println(e.book());
    }
}

Output

SELL 1 100@10027 -> rested 100
SELL 2 200@10027 -> rested 200
SELL 3 300@10028 -> rested 300
BUY  4 100@10025 -> rested 100
bids [10025x100(4)] asks [10027x300(1,2), 10028x300(3)]
BUY  5 350@10028 -> rested 0
     Trade[taker=5, maker=1, price=10027, qty=100]
     Trade[taker=5, maker=2, price=10027, qty=200]
     Trade[taker=5, maker=3, price=10028, qty=50]
bids [10025x100(4)] asks [10028x250(3)]
SELL 6 150@10024 -> rested 50
     Trade[taker=6, maker=4, price=10025, qty=100]
bids [] asks [10024x50(6), 10028x250(3)]

Order 5 walks the book: it takes all of order 1 and then order 2 at 10027 in arrival order, then 50 of order 3 at 10028, so order 3 is partially filled and keeps its place. Order 6 is a sell limit at 10024; the best bid is 10025, which is better for the seller, so it trades at 10025 (the resting price) and the remaining 50 rest at 10024. Every trade names the taker and the maker; exchanges charge or rebate fees by that role.

Stage 2: market, IOC, and FOK orders, cancels, and rejects

Stage 2 turns the outputs into a sealed event hierarchy (from Records and Sealed Types) so every outcome of a command is a record in one list. Three rules extend the matching loop:

A market order uses Long.MAX_VALUE (buy) or Long.MIN_VALUE (sell) as its limit, so every price is acceptable, and it never rests.
IOC matches like a limit order and cancels the remainder instead of resting it.
FOK first sums the quantity available at acceptable prices. If the sum is short, the order is cancelled before any trade, because a FOK that traded partly could not be undone.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

enum OrdType { LIMIT, MARKET }
enum Tif { DAY, IOC, FOK }

sealed interface Event permits Trade, Rested, Cancelled, Rejected {}
record Trade(long taker, long maker, long price, long qty) implements Event {}
record Rested(long id, boolean buy, long price, long qty) implements Event {}
record Cancelled(long id, long qty, String reason) implements Event {}
record Rejected(long id, String reason) implements Event {}

final class Order {
    final long id;
    final boolean buy;
    final long price;
    long qty;
    Order(long id, boolean buy, long price, long qty) { this.id = id; this.buy = buy; this.price = price; this.qty = qty; }
}

final class Engine {
    private final TreeMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, ArrayDeque<Order>> asks = new TreeMap<>();
    private final Map<Long, Order> live = new HashMap<>();
    private final Set<Long> seen = new HashSet<>();
    final List<Event> events = new ArrayList<>();

    void submit(long id, boolean buy, OrdType type, long price, long qty, Tif tif) {
        if (!seen.add(id)) { events.add(new Rejected(id, "duplicate id")); return; }
        if (qty <= 0) { events.add(new Rejected(id, "bad qty")); return; }
        long limit = type == OrdType.MARKET ? (buy ? Long.MAX_VALUE : Long.MIN_VALUE) : price;
        if (tif == Tif.FOK && available(buy, limit, qty) < qty) {
            events.add(new Cancelled(id, qty, "FOK not fillable"));
            return;
        }
        long remaining = match(id, buy, limit, qty);
        if (remaining == 0) return;
        if (type == OrdType.MARKET) {
            events.add(new Cancelled(id, remaining, "no liquidity"));
        } else if (tif == Tif.IOC) {
            events.add(new Cancelled(id, remaining, "IOC remainder"));
        } else {
            Order o = new Order(id, buy, price, remaining);
            (buy ? bids : asks).computeIfAbsent(price, p -> new ArrayDeque<>()).addLast(o);
            live.put(id, o);
            events.add(new Rested(id, buy, price, remaining));
        }
    }

    void cancel(long id) {
        Order o = live.remove(id);
        if (o == null) { events.add(new Rejected(id, "unknown id")); return; }
        TreeMap<Long, ArrayDeque<Order>> side = o.buy ? bids : asks;
        ArrayDeque<Order> level = side.get(o.price);
        level.remove(o);
        if (level.isEmpty()) side.remove(o.price);
        events.add(new Cancelled(id, o.qty, "user"));
    }

    private static boolean crosses(boolean buy, long levelPx, long limit) {
        return buy ? levelPx <= limit : levelPx >= limit;
    }

    private long available(boolean buy, long limit, long wanted) {
        long sum = 0;
        for (var e : (buy ? asks : bids).entrySet()) {
            if (!crosses(buy, e.getKey(), limit)) break;
            for (Order o : e.getValue()) {
                sum += o.qty;
                if (sum >= wanted) return sum;
            }
        }
        return sum;
    }

    private long match(long takerId, boolean buy, long limit, long qty) {
        TreeMap<Long, ArrayDeque<Order>> opposite = buy ? asks : bids;
        while (qty > 0 && !opposite.isEmpty()) {
            long px = opposite.firstKey();
            if (!crosses(buy, px, limit)) break;
            ArrayDeque<Order> level = opposite.firstEntry().getValue();
            while (qty > 0 && !level.isEmpty()) {
                Order maker = level.peekFirst();
                long q = Math.min(qty, maker.qty);
                events.add(new Trade(takerId, maker.id, px, q));    // trade at the resting order's price
                maker.qty -= q;
                qty -= q;
                if (maker.qty == 0) { level.pollFirst(); live.remove(maker.id); }
            }
            if (level.isEmpty()) opposite.remove(px);
        }
        return qty;
    }

    String book() {
        return "bids " + levels(bids) + " asks " + levels(asks);
    }

    private static List<String> levels(TreeMap<Long, ArrayDeque<Order>> side) {
        List<String> out = new ArrayList<>();
        side.forEach((px, q) -> out.add(px + "x" + q.stream().mapToLong(o -> o.qty).sum()));
        return out;
    }
}

public class Main {
    static void show(Engine e, String what, Runnable command) {
        int before = e.events.size();
        command.run();
        System.out.println(what);
        e.events.subList(before, e.events.size()).forEach(ev -> System.out.println("    " + ev));
    }

    public static void main(String[] args) {
        Engine e = new Engine();
        e.submit(1, false, OrdType.LIMIT, 10_027, 100, Tif.DAY);
        e.submit(2, false, OrdType.LIMIT, 10_028, 300, Tif.DAY);
        e.submit(3, true, OrdType.LIMIT, 10_025, 200, Tif.DAY);
        e.submit(4, true, OrdType.LIMIT, 10_024, 100, Tif.DAY);
        System.out.println(e.book());

        show(e, "IOC buy 5 150@10027", () -> e.submit(5, true, OrdType.LIMIT, 10_027, 150, Tif.IOC));
        show(e, "FOK buy 6 400@10028", () -> e.submit(6, true, OrdType.LIMIT, 10_028, 400, Tif.FOK));
        show(e, "FOK buy 7 250@10028", () -> e.submit(7, true, OrdType.LIMIT, 10_028, 250, Tif.FOK));
        show(e, "MARKET sell 8 250", () -> e.submit(8, false, OrdType.MARKET, 0, 250, Tif.DAY));
        show(e, "MARKET buy 9 80", () -> e.submit(9, true, OrdType.MARKET, 0, 80, Tif.DAY));
        show(e, "cancel 4, cancel 4", () -> { e.cancel(4); e.cancel(4); });
        show(e, "buy 1 again, buy 10 qty 0", () -> {
            e.submit(1, true, OrdType.LIMIT, 10_020, 5, Tif.DAY);
            e.submit(10, true, OrdType.LIMIT, 10_020, 0, Tif.DAY);
        });
        System.out.println(e.book());
    }
}

Output

bids [10025x200, 10024x100] asks [10027x100, 10028x300]
IOC buy 5 150@10027
    Trade[taker=5, maker=1, price=10027, qty=100]
    Cancelled[id=5, qty=50, reason=IOC remainder]
FOK buy 6 400@10028
    Cancelled[id=6, qty=400, reason=FOK not fillable]
FOK buy 7 250@10028
    Trade[taker=7, maker=2, price=10028, qty=250]
MARKET sell 8 250
    Trade[taker=8, maker=3, price=10025, qty=200]
    Trade[taker=8, maker=4, price=10024, qty=50]
MARKET buy 9 80
    Trade[taker=9, maker=2, price=10028, qty=50]
    Cancelled[id=9, qty=30, reason=no liquidity]
cancel 4, cancel 4
    Cancelled[id=4, qty=50, reason=user]
    Rejected[id=4, reason=unknown id]
buy 1 again, buy 10 qty 0
    Rejected[id=1, reason=duplicate id]
    Rejected[id=10, reason=bad qty]
bids [] asks []

Walking through the results:

IOC 5 fills 100 against order 1 at 10027 and cancels 50; it does not rest, so the book has no bid at 10027 afterwards.
FOK 6 wants 400 but only 300 is offered at or below 10028, so it is cancelled with no trade. FOK 7 wants 250 and gets all of it from order 2.
The market sell takes 200 from order 3 at 10025 and 50 from order 4 at 10024, two prices in one order. That walk through levels is called slippage; venues limit it with price bands or by converting market orders to limits at a collar price.
The market buy finds only 50 left on the ask side and cancels the other 30.
The second cancel of order 4 is rejected, because order 4 was cancelled first (its remaining 50 were the leaves). Id 1 is rejected as a duplicate even though order 1 is gone: ids are unique for the session, so a late cancel cannot hit a new order with a reused id.

The seen set grows for the whole session. A production engine bounds it with session-scoped id ranges or a per-session sequence check.

Stage 3: a single engine thread fed by a ring buffer

The book is not thread-safe, and it does not need to be: one thread owns it. Gateways (the threads that decode client messages) pass commands to that thread through a single-producer ring buffer of pre-allocated Command slots, the design from The LMAX Disruptor Pattern:

The producer claims a sequence, writes the slot's fields, and publishes with a release write to the cursor.
The engine reads the cursor with an acquire read, processes every slot up to it (a batch), and then publishes its own sequence once. That sequence gates the producer so it never overwrites an unread slot.
The engine copies what it needs out of a slot before it publishes its sequence. Keeping a reference to the slot would read a later command after the producer reuses it.

Ordering is decided once, by the sequence number of each slot. The engine's output then depends only on that order, not on thread timing, so the program compares the threaded run with a direct single-threaded run of the same script.

Java

import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

enum OrdType { LIMIT, MARKET }
enum Tif { DAY, IOC, FOK }

sealed interface Event permits Trade, Rested, Cancelled, Rejected {}
record Trade(long taker, long maker, long price, long qty) implements Event {}
record Rested(long id, boolean buy, long price, long qty) implements Event {}
record Cancelled(long id, long qty, String reason) implements Event {}
record Rejected(long id, String reason) implements Event {}

final class Order {
    final long id;
    final boolean buy;
    final long price;
    long qty;
    Order(long id, boolean buy, long price, long qty) { this.id = id; this.buy = buy; this.price = price; this.qty = qty; }
}

final class Engine {
    private final TreeMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, ArrayDeque<Order>> asks = new TreeMap<>();
    private final Map<Long, Order> live = new HashMap<>();
    private final Set<Long> seen = new HashSet<>();
    final List<Event> events = new ArrayList<>();

    void submit(long id, boolean buy, OrdType type, long price, long qty, Tif tif) {
        if (!seen.add(id)) { events.add(new Rejected(id, "duplicate id")); return; }
        if (qty <= 0) { events.add(new Rejected(id, "bad qty")); return; }
        long limit = type == OrdType.MARKET ? (buy ? Long.MAX_VALUE : Long.MIN_VALUE) : price;
        if (tif == Tif.FOK && available(buy, limit, qty) < qty) {
            events.add(new Cancelled(id, qty, "FOK not fillable"));
            return;
        }
        long remaining = match(id, buy, limit, qty);
        if (remaining == 0) return;
        if (type == OrdType.MARKET) {
            events.add(new Cancelled(id, remaining, "no liquidity"));
        } else if (tif == Tif.IOC) {
            events.add(new Cancelled(id, remaining, "IOC remainder"));
        } else {
            Order o = new Order(id, buy, price, remaining);
            (buy ? bids : asks).computeIfAbsent(price, p -> new ArrayDeque<>()).addLast(o);
            live.put(id, o);
            events.add(new Rested(id, buy, price, remaining));
        }
    }

    void cancel(long id) {
        Order o = live.remove(id);
        if (o == null) { events.add(new Rejected(id, "unknown id")); return; }
        TreeMap<Long, ArrayDeque<Order>> side = o.buy ? bids : asks;
        ArrayDeque<Order> level = side.get(o.price);
        level.remove(o);
        if (level.isEmpty()) side.remove(o.price);
        events.add(new Cancelled(id, o.qty, "user"));
    }

    private static boolean crosses(boolean buy, long levelPx, long limit) {
        return buy ? levelPx <= limit : levelPx >= limit;
    }

    private long available(boolean buy, long limit, long wanted) {
        long sum = 0;
        for (var e : (buy ? asks : bids).entrySet()) {
            if (!crosses(buy, e.getKey(), limit)) break;
            for (Order o : e.getValue()) {
                sum += o.qty;
                if (sum >= wanted) return sum;
            }
        }
        return sum;
    }

    private long match(long takerId, boolean buy, long limit, long qty) {
        TreeMap<Long, ArrayDeque<Order>> opposite = buy ? asks : bids;
        while (qty > 0 && !opposite.isEmpty()) {
            long px = opposite.firstKey();
            if (!crosses(buy, px, limit)) break;
            ArrayDeque<Order> level = opposite.firstEntry().getValue();
            while (qty > 0 && !level.isEmpty()) {
                Order maker = level.peekFirst();
                long q = Math.min(qty, maker.qty);
                events.add(new Trade(takerId, maker.id, px, q));    // trade at the resting order's price
                maker.qty -= q;
                qty -= q;
                if (maker.qty == 0) { level.pollFirst(); live.remove(maker.id); }
            }
            if (level.isEmpty()) opposite.remove(px);
        }
        return qty;
    }

    String book() {
        return "bids " + levels(bids) + " asks " + levels(asks);
    }

    private static List<String> levels(TreeMap<Long, ArrayDeque<Order>> side) {
        List<String> out = new ArrayList<>();
        side.forEach((px, q) -> out.add(px + "x" + q.stream().mapToLong(o -> o.qty).sum()));
        return out;
    }
}

final class Command {
    static final int NEW = 1, CANCEL = 2, STOP = 3;
    int kind;
    long id;
    boolean buy;
    OrdType type;
    long price;
    long qty;
    Tif tif;

    void applyTo(Engine e) {
        if (kind == NEW) e.submit(id, buy, type, price, qty, tif);
        else if (kind == CANCEL) e.cancel(id);
    }
}

/** Deterministic order stream: about 80% new orders, 20% cancels of earlier ids. */
final class Script {
    private long seed = 7;
    private long nextId = 1;

    private long rnd() { seed = seed * 6364136223846793005L + 1442695040888963407L; return seed >>> 33; }

    void next(Command c) {
        long r = rnd();
        if (r % 5 == 0 && nextId > 1) {
            c.kind = Command.CANCEL;
            c.id = 1 + (r >> 3) % (nextId - 1);
            return;
        }
        c.kind = Command.NEW;
        c.id = nextId++;
        c.buy = (r & 8) != 0;
        int t = (int) ((r >> 4) % 10);
        c.type = t == 9 ? OrdType.MARKET : OrdType.LIMIT;
        c.tif = t == 7 ? Tif.IOC : t == 8 ? Tif.FOK : Tif.DAY;
        c.price = c.buy ? 9_995 + (r >> 8) % 10 : 10_000 + (r >> 8) % 10 - 4;
        c.qty = 1 + (r >> 16) % 100;
    }
}

class LhsPadding { protected long p1, p2, p3, p4, p5, p6, p7; }
class Value extends LhsPadding { protected volatile long value; }
class RhsPadding extends Value { protected long p9, p10, p11, p12, p13, p14, p15; }

final class Sequence extends RhsPadding {
    private static final VarHandle VALUE;
    static {
        try {
            VALUE = MethodHandles.lookup().findVarHandle(Value.class, "value", long.class);
        } catch (ReflectiveOperationException e) {
            throw new ExceptionInInitializerError(e);
        }
    }
    Sequence(long initial) { VALUE.setRelease(this, initial); }
    long get() { return (long) VALUE.getAcquire(this); }
    void set(long v) { VALUE.setRelease(this, v); }
}

/** Single producer, single consumer ring of pre-allocated commands. */
final class CommandRing {
    private final Command[] slots;
    private final int mask;
    final Sequence cursor = new Sequence(-1);     // last published by the producer
    final Sequence consumed = new Sequence(-1);   // last processed by the engine
    private long claimed = -1;                    // producer-only

    CommandRing(int size) {
        if (Integer.bitCount(size) != 1) throw new IllegalArgumentException("size must be a power of two");
        slots = new Command[size];
        for (int i = 0; i < size; i++) slots[i] = new Command();
        mask = size - 1;
    }

    long next() {
        long seq = ++claimed;
        while (seq - slots.length > consumed.get()) Thread.onSpinWait();   // ring full: wait for the engine
        return seq;
    }

    Command get(long seq) { return slots[(int) (seq & mask)]; }
    void publish(long seq) { cursor.set(seq); }
}

public class Main {
    static final int COMMANDS = 50_000;

    public static void main(String[] args) throws InterruptedException {
        CommandRing ring = new CommandRing(1_024);
        Engine engine = new Engine();

        Thread engineThread = new Thread(() -> {
            long next = 0;
            boolean running = true;
            while (running) {
                long available = ring.cursor.get();
                if (available < next) { Thread.onSpinWait(); continue; }
                while (next <= available) {
                    Command c = ring.get(next++);
                    if (c.kind == Command.STOP) { running = false; break; }
                    c.applyTo(engine);
                }
                ring.consumed.set(next - 1);
            }
        }, "engine");

        Thread gateway = new Thread(() -> {
            Script script = new Script();
            for (int i = 0; i < COMMANDS; i++) {
                long seq = ring.next();
                script.next(ring.get(seq));
                ring.publish(seq);
            }
            long seq = ring.next();
            ring.get(seq).kind = Command.STOP;
            ring.publish(seq);
        }, "gateway");

        engineThread.start();
        gateway.start();
        gateway.join();
        engineThread.join();

        Engine direct = new Engine();
        Script script = new Script();
        Command c = new Command();
        for (int i = 0; i < COMMANDS; i++) { script.next(c); c.applyTo(direct); }

        long trades = engine.events.stream().filter(ev -> ev instanceof Trade).count();
        long volume = engine.events.stream().mapToLong(ev -> ev instanceof Trade t ? t.qty() : 0).sum();
        System.out.println("commands: " + COMMANDS + ", events: " + engine.events.size());
        System.out.println("trades: " + trades + ", volume: " + volume);
        System.out.println("rejects: " + engine.events.stream().filter(ev -> ev instanceof Rejected).count()
                + ", cancels: " + engine.events.stream().filter(ev -> ev instanceof Cancelled).count());
        System.out.println("same events as direct run: " + engine.events.equals(direct.events));
        System.out.println("same book as direct run: " + engine.book().equals(direct.book()));
    }
}

Output

commands: 50000, events: 65625
trades: 30065, volume: 765926
rejects: 9108, cancels: 6636
same events as direct run: true
same book as direct run: true

How many commands the engine takes per batch changes from run to run, and so does how often the gateway waits on a full ring. None of that is printed, because none of it changes the events: the comparison with the direct run is true on every run. Many cancels are rejects, because the script picks ids at random and many of those orders have already traded or been cancelled.

Design points of this stage:

Choice	Reason
One thread owns the book	No locks in matching, and a total order of events
Pre-allocated `Command` slots	The gateway copies fields in; no object per command
Batching	The engine writes `consumed` once per batch, so the gateway reads a shared cache line less often
`STOP` as a command	Shutdown is ordered with the other commands, so nothing is lost
Busy spin with `Thread.onSpinWait`	Lowest wake-up latency; costs a full core per spinning thread

Stage 4: command journal and deterministic replay

The engine is a deterministic state machine: its state and its events depend only on the sequence of commands it applies. That property gives recovery for free. A sequencer writes each command to a journal before the engine applies it (write-ahead), and after a crash a new engine replays the journal and reaches the same state. The same journal lets an auditor or a test reproduce any past session exactly.

Determinism requires that the engine reads nothing outside the command: no clock, no random numbers, no iteration over a hash-ordered collection that affects output. Where an engine needs a timestamp, the sequencer stamps it into the command before journaling.

The journal below stores fixed-size 28-byte records in a ByteBuffer, the layout style from Binary Protocols. Production journals write the same records to a memory-mapped file or replicate them to a standby before the engine applies them.

Java

import java.nio.ByteBuffer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

enum OrdType { LIMIT, MARKET }
enum Tif { DAY, IOC, FOK }

sealed interface Event permits Trade, Rested, Cancelled, Rejected {}
record Trade(long taker, long maker, long price, long qty) implements Event {}
record Rested(long id, boolean buy, long price, long qty) implements Event {}
record Cancelled(long id, long qty, String reason) implements Event {}
record Rejected(long id, String reason) implements Event {}

final class Order {
    final long id;
    final boolean buy;
    final long price;
    long qty;
    Order(long id, boolean buy, long price, long qty) { this.id = id; this.buy = buy; this.price = price; this.qty = qty; }
}

final class Engine {
    private final TreeMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, ArrayDeque<Order>> asks = new TreeMap<>();
    private final Map<Long, Order> live = new HashMap<>();
    private final Set<Long> seen = new HashSet<>();
    final List<Event> events = new ArrayList<>();

    void submit(long id, boolean buy, OrdType type, long price, long qty, Tif tif) {
        if (!seen.add(id)) { events.add(new Rejected(id, "duplicate id")); return; }
        if (qty <= 0) { events.add(new Rejected(id, "bad qty")); return; }
        long limit = type == OrdType.MARKET ? (buy ? Long.MAX_VALUE : Long.MIN_VALUE) : price;
        if (tif == Tif.FOK && available(buy, limit, qty) < qty) {
            events.add(new Cancelled(id, qty, "FOK not fillable"));
            return;
        }
        long remaining = match(id, buy, limit, qty);
        if (remaining == 0) return;
        if (type == OrdType.MARKET) {
            events.add(new Cancelled(id, remaining, "no liquidity"));
        } else if (tif == Tif.IOC) {
            events.add(new Cancelled(id, remaining, "IOC remainder"));
        } else {
            Order o = new Order(id, buy, price, remaining);
            (buy ? bids : asks).computeIfAbsent(price, p -> new ArrayDeque<>()).addLast(o);
            live.put(id, o);
            events.add(new Rested(id, buy, price, remaining));
        }
    }

    void cancel(long id) {
        Order o = live.remove(id);
        if (o == null) { events.add(new Rejected(id, "unknown id")); return; }
        TreeMap<Long, ArrayDeque<Order>> side = o.buy ? bids : asks;
        ArrayDeque<Order> level = side.get(o.price);
        level.remove(o);
        if (level.isEmpty()) side.remove(o.price);
        events.add(new Cancelled(id, o.qty, "user"));
    }

    private static boolean crosses(boolean buy, long levelPx, long limit) {
        return buy ? levelPx <= limit : levelPx >= limit;
    }

    private long available(boolean buy, long limit, long wanted) {
        long sum = 0;
        for (var e : (buy ? asks : bids).entrySet()) {
            if (!crosses(buy, e.getKey(), limit)) break;
            for (Order o : e.getValue()) {
                sum += o.qty;
                if (sum >= wanted) return sum;
            }
        }
        return sum;
    }

    private long match(long takerId, boolean buy, long limit, long qty) {
        TreeMap<Long, ArrayDeque<Order>> opposite = buy ? asks : bids;
        while (qty > 0 && !opposite.isEmpty()) {
            long px = opposite.firstKey();
            if (!crosses(buy, px, limit)) break;
            ArrayDeque<Order> level = opposite.firstEntry().getValue();
            while (qty > 0 && !level.isEmpty()) {
                Order maker = level.peekFirst();
                long q = Math.min(qty, maker.qty);
                events.add(new Trade(takerId, maker.id, px, q));    // trade at the resting order's price
                maker.qty -= q;
                qty -= q;
                if (maker.qty == 0) { level.pollFirst(); live.remove(maker.id); }
            }
            if (level.isEmpty()) opposite.remove(px);
        }
        return qty;
    }

    String book() {
        return "bids " + levels(bids) + " asks " + levels(asks);
    }

    private static List<String> levels(TreeMap<Long, ArrayDeque<Order>> side) {
        List<String> out = new ArrayList<>();
        side.forEach((px, q) -> out.add(px + "x" + q.stream().mapToLong(o -> o.qty).sum()));
        return out;
    }
}

final class Command {
    static final int NEW = 1, CANCEL = 2, STOP = 3;
    int kind;
    long id;
    boolean buy;
    OrdType type;
    long price;
    long qty;
    Tif tif;

    void applyTo(Engine e) {
        if (kind == NEW) e.submit(id, buy, type, price, qty, tif);
        else if (kind == CANCEL) e.cancel(id);
    }
}

/** Deterministic order stream: about 80% new orders, 20% cancels of earlier ids. */
final class Script {
    private long seed = 7;
    private long nextId = 1;

    private long rnd() { seed = seed * 6364136223846793005L + 1442695040888963407L; return seed >>> 33; }

    void next(Command c) {
        long r = rnd();
        if (r % 5 == 0 && nextId > 1) {
            c.kind = Command.CANCEL;
            c.id = 1 + (r >> 3) % (nextId - 1);
            return;
        }
        c.kind = Command.NEW;
        c.id = nextId++;
        c.buy = (r & 8) != 0;
        int t = (int) ((r >> 4) % 10);
        c.type = t == 9 ? OrdType.MARKET : OrdType.LIMIT;
        c.tif = t == 7 ? Tif.IOC : t == 8 ? Tif.FOK : Tif.DAY;
        c.price = c.buy ? 9_995 + (r >> 8) % 10 : 10_000 + (r >> 8) % 10 - 4;
        c.qty = 1 + (r >> 16) % 100;
    }
}

final class Journal {
    static final int RECORD = 28;   // kind 1, id 8, buy 1, type 1, tif 1, price 8, qty 8
    private final ByteBuffer buf;

    Journal(int capacity) { buf = ByteBuffer.allocate(capacity * RECORD); }

    void append(Command c) {
        buf.put((byte) c.kind).putLong(c.id);
        if (c.kind == Command.NEW) {
            buf.put((byte) (c.buy ? 1 : 0)).put((byte) c.type.ordinal()).put((byte) c.tif.ordinal())
               .putLong(c.price).putLong(c.qty);
        } else {
            buf.position(buf.position() + 19);    // unused fields stay zero
        }
    }

    int size() { return buf.position() / RECORD; }

    void read(int index, Command c) {
        int at = index * RECORD;
        c.kind = buf.get(at);
        c.id = buf.getLong(at + 1);
        c.buy = buf.get(at + 9) == 1;
        c.type = OrdType.values()[buf.get(at + 10)];
        c.tif = Tif.values()[buf.get(at + 11)];
        c.price = buf.getLong(at + 12);
        c.qty = buf.getLong(at + 20);
    }
}

/** Journals each command, then applies it. */
final class Sequencer {
    final Journal journal;
    final Engine engine;

    Sequencer(Journal journal, Engine engine) { this.journal = journal; this.engine = engine; }

    void process(Command c) {
        journal.append(c);
        c.applyTo(engine);
    }

    static Engine replay(Journal journal, int count) {
        Engine e = new Engine();
        Command c = new Command();
        for (int i = 0; i < count; i++) { journal.read(i, c); c.applyTo(e); }
        return e;
    }
}

public class Main {
    static final int COMMANDS = 20_000, CRASH_AT = 12_000;

    public static void main(String[] args) {
        // 1. Reference run without interruption.
        Sequencer reference = new Sequencer(new Journal(COMMANDS), new Engine());
        Script script = new Script();
        Command c = new Command();
        for (int i = 0; i < COMMANDS; i++) { script.next(c); reference.process(c); }
        System.out.println("journal records: " + reference.journal.size() + " (" + reference.journal.size() * Journal.RECORD + " bytes)");
        System.out.println("events: " + reference.engine.events.size());

        // 2. Full replay gives the same events and book.
        Engine replayed = Sequencer.replay(reference.journal, reference.journal.size());
        System.out.println("full replay identical: " + (replayed.events.equals(reference.engine.events)
                && replayed.book().equals(reference.engine.book())));

        // 3. Crash after CRASH_AT commands: the engine is lost, the journal survives.
        Journal survived = new Journal(COMMANDS);
        Sequencer before = new Sequencer(survived, new Engine());
        Script live = new Script();
        for (int i = 0; i < CRASH_AT; i++) { live.next(c); before.process(c); }
        before = null;   // crash

        // 4. Recover: replay the journal, then continue with the rest of the stream.
        Engine recoveredEngine = Sequencer.replay(survived, survived.size());
        Sequencer recovered = new Sequencer(survived, recoveredEngine);
        for (int i = CRASH_AT; i < COMMANDS; i++) { live.next(c); recovered.process(c); }
        System.out.println("recovered after " + CRASH_AT + " commands, events identical: "
                + recoveredEngine.events.equals(reference.engine.events));

        // 5. Point-in-time replay: the state after the first 8 commands.
        Engine early = Sequencer.replay(reference.journal, 8);
        early.events.forEach(ev -> System.out.println("  " + ev));
        System.out.println("  " + early.book());
    }
}

Output

journal records: 20000 (560000 bytes)
events: 26181
full replay identical: true
recovered after 12000 commands, events identical: true
  Cancelled[id=1, qty=62, reason=no liquidity]
  Rested[id=2, buy=true, price=9998, qty=16]
  Cancelled[id=3, qty=7, reason=IOC remainder]
  Cancelled[id=4, qty=38, reason=IOC remainder]
  Cancelled[id=2, qty=16, reason=user]
  Rested[id=5, buy=false, price=9997, qty=36]
  Trade[taker=6, maker=5, price=9997, qty=2]
  Rested[id=7, buy=false, price=10000, qty=54]
  bids [] asks [9997x34, 10000x54]

Step 3 throws the engine away after 12,000 commands, which stands for a process crash; only the journal remains. Step 4 rebuilds the engine from those 12,000 records, takes the remaining 8,000 commands from the live stream, and produces the same 20,000-command event list as the uninterrupted run. Step 5 rebuilds the state at any past point, the tool used to investigate a disputed trade.

Replay re-emits events that clients already received before the crash. A recovering engine suppresses output until it passes the last sequence it is known to have published, or downstream consumers drop events with a sequence they have already seen, the idempotency technique from Idempotency and Ledgers. Long journals are shortened with snapshots: the engine periodically serializes its book together with the sequence number it reflects, and recovery loads the newest snapshot and replays only the records after it.

Parts of the project

Part	Stage	Purpose
Matching loop over best opposite level	1 to 4	Price priority across levels, time priority inside a level
Trade at the maker's price	1 to 4	Taker gets any price improvement
`Trade`, `Rested`, `Cancelled`, `Rejected` records	2 to 4	Every outcome is an event in one ordered list
Market limit as `Long.MAX_VALUE` / `Long.MIN_VALUE`	2 to 4	One matching loop for market and limit orders
FOK pre-check with `available`	2 to 4	No partial FOK trades
`seen` id set	2 to 4	Duplicate ids rejected for the session
`Command` slots in `CommandRing` with padded `Sequence`s	3	Lock-free hand-off from gateway to engine
`STOP` command	3	Ordered shutdown
`Journal` of fixed 28-byte records	4	Write-ahead log of inputs
`Sequencer.replay`	4	Recovery, audit, and point-in-time state

Extension tasks

Replace the TreeMap book with the pooled array book from Project: Limit Order Book and make the event list a pre-allocated ring of event slots; verify zero allocation per command with ThreadMXBean.
Add modify (cancel/replace) with the priority rules from the order book project.
Add self-trade prevention: when taker and maker belong to the same account, cancel the resting order instead of trading.
Put the journal writer on its own consumer of the input ring, and gate the engine on the journal's sequence, so journaling and matching run on two threads in a fixed order (the Disruptor's consumer dependency).
Write snapshots every N commands and recover from the latest snapshot plus the journal tail.
Add a price band: reject limit orders more than K ticks from the last trade price, and stop a market order when it would trade outside the band.
Feed the engine from FIX NewOrderSingle and OrderCancelRequest messages and send execution reports with CumQty and LeavesQty.

Interview points

Price-time priority: best price first; at the same price, first in time first.
The trade price is the resting (maker) order's price; the incoming (taker) order gets any improvement.
An order can trade with many resting orders at several price levels; the remainder rests (DAY limit), or is cancelled (IOC, market).
FOK must check available quantity before trading, since trades cannot be undone.
Market orders are implemented as limits at the extreme price that never rest; venues protect them with price bands.
One thread owns the book: no locks, and a total order of events. Other threads hand it commands through a ring buffer of pre-allocated slots.
Do not keep a reference to a ring slot after the consumer sequence passes it; the producer reuses it.
A matching engine is a deterministic state machine. Journaling inputs before applying them gives crash recovery and audit by replay.
Determinism forbids reading clocks, random sources, or hash iteration order inside the engine; the sequencer stamps times into commands.
Replay re-emits events; downstream consumers deduplicate by sequence, and snapshots bound replay time.

Summary

Stage 1 matches DAY limit orders by price-time priority with partial fills and trade events.
Stage 2 adds market, IOC, and FOK orders, cancels, and rejects, with outcomes as sealed records.
Stage 3 runs the engine on one thread, fed by a single-producer ring buffer, and proves the output matches a direct run.
Stage 4 journals each command before applying it and recovers from a crash by replay with identical events.
The same journal gives point-in-time state for investigations.