Limit order book matching engine
A limit order book matching engine in Java, my first project in the language.
Live demo
The engine, running
The matching logic ported from Java to JavaScript. Submit an order and watch it cross the spread or rest. Select a price to open the queue behind it.
- Resting orders
- 24
- Price levels
- 18
- Trades
- 0
- Dead entries
- 0
Depth
Best prices meet at the spread1 deeper ask level
Spread 10p
1 deeper bid level
Trade tape
Newest first- No trades yet. Submit an order that crosses the spread.
Reading the queue
Each price level is a first-in, first-out queue. Open a level and the highlighted order is the one that arrived first, so it fills next at that price.
Cancel an order in the middle of a queue and it stays there, struck through. Removing it would mean walking the queue, which is O(n). The engine flags it instead and lowers the level's live count, then drops it once it reaches the front. That is why the dead entries count rises when you cancel and falls as the book trades through.
A partially filled order keeps its place at the front. Trades always execute at the resting order's price, not the aggressor's.
Benchmark, JVM build
1M operations, single thread| Metric | Before pooling | After pooling |
|---|---|---|
| Throughput, median of 5 | 9.18M ops/s | 10.18M ops/s |
| Latency p99 | 500–600 ns | 400 ns |
| Latency p99.9 | 1.5–2.7 µs | 1.4–2.0 µs |
| Max GC pause | 12.2 ms | 7.7 ms |
Java Flight Recorder put PriceLevel allocation at 29% of allocated bytes, because levels near the touch empty and refill constantly. Recycling emptied levels moved throughput by about as much as the run-to-run noise, but the tail-latency gain held in every run.
Problem
A matching engine has to decide, for every incoming order, exactly which resting orders it trades with and at what price, and it has to get that right every time. The rule is price-time priority: best price first, and at the same price, whoever arrived first.
Approach
Written in Java, a language I was new to when I started.
The engine takes limit and market orders. A limit order trades against the other side while prices cross, and any remainder rests in the book. A market order takes what it can, and the rest is discarded. Trades always execute at the resting order’s price, and a partially filled order keeps its place in the queue.
Each side of the book is a TreeMap of price levels, with bids in reverse order so firstEntry() is the best price on both sides. Each level is a FIFO queue. Prices are long pence, never double, because binary floating point can’t represent most decimal prices exactly and crossing checks would be unreliable.
Cancelling is O(1) through lazy deletion. Unlinking an order from the middle of an ArrayDeque is O(n), so a cancel flags the order and lowers the level’s live count. Cancelled entries are dropped when they reach the front, so the head of every queue is always a live order.
The engine is single-threaded on purpose. Matching on one book is sequential anyway, and a single writer needs no locks and is fully deterministic: the same input always produces the same trades.
Result
43 tests: 42 unit tests and a differential fuzz test. The fuzz test runs 100,000 random submits and cancels through the engine and through a deliberately naive reference engine. After every operation it checks that the trades and book state match, the book is never crossed, quantity is conserved and FIFO order holds.
To check the fuzz test could catch anything, I planted a bug: a filled order was left in the id index. All 41 unit tests at the time still passed. So did the first version of the fuzz test, because its random cancels almost always hit orders that were long gone. Once I added the case where a cancel arrives just after its order filled, it failed at operation 1,082 with an exact diff. That case is now a regression test. The lesson: fuzzing coverage comes from the input distribution, not the operation count.
Across six benchmark runs on my laptop, throughput was 8.5–10.4M operations per second and p99 latency was 400–800 ns. Java Flight Recorder showed that levels near the touch empty and refill constantly, and allocating a fresh PriceLevel and its queue was about 29% of allocated bytes. Keeping up to 256 emptied levels in a pool and reusing them brought p99 down from 500–600 ns to 400 ns in every run. The throughput gain was about the size of the run-to-run noise.
The next bottleneck is Long boxing, now 56% of allocation. A primitive long-keyed map and a tick-indexed array of price levels are the next steps.