Rebuilding Open Exchange's order book: array-backed, 281,000 orders/sec, and the memory bug we hit on the way

Note (July 2026): this post documents the alpha array-backed rebuild. The current baseline is higher and was re-measured for v0.3.0-beta; see the beta release.

How we replaced the matching engine's order book, what the load tests actually showed, and the out-of-memory bug we found while pushing for its limits.

All numbers and failures below come from a dev/local cluster on a single developer machine. No production system or customer traffic was involved; the point was to break things somewhere safe.

Summary

We replaced the order book at the core of Open Exchange's matching engine, moving from a preallocated, geometry-bound structure to an array-backed one. On a single desktop (Intel 13700K) running a 3-node Raft cluster:

• Matching latency stayed sub-microsecond (p50 around 0.3 µs) at every load we tried.
• The cluster sustained 281,000 orders/sec at 100% success, and was still accepting more when our load generator ran out of cores.
• Order-book memory dropped about 3x, and now scales with resting orders instead of the configured price range.
• Under overload it sheds load and recovers without losing data, though we had to fix a memory bug to get there.

The most useful result wasn't the throughput figure. It was the reminder that the matching engine is the cheap part, and the hard problems live in the pipeline around it.

The order book we replaced

The old book mapped a price straight to an array slot:

slot = (price − basePrice) / tickSize

O(1) lookups, no pointer-chasing, cache-friendly. The cost was that it baked the market's geometry into memory:

• Fixed price range and tick. You set basePrice, maxPrice and tickSize up front, and the book preallocated a slot for every price level in range. BTC-USD with a $1 tick over a $100k range is about 100,000 levels × 64 orders × 4 longs, roughly 200 MB per side, most of it empty.
• A hard cap of 64 orders per level. The 65th order at a price was rejected.
• Memory proportional to the price range, not the order count.
• No way to change the range at runtime without reallocating the whole book.

We wanted to keep the zero-allocation hot path and lose the geometry.

Why zero-allocation still mattered shaped the rest of the design. The nodes run generational ZGC on Azul Zulu Community 21, the free OpenJDK build, so there's no pauseless C4 collector. ZGC removes stop-the-world pauses but is not allocation-free: it puts a load barrier on every reference read. For a sub-microsecond engine, a structure full of object references pays that barrier on every access. A flat long[] book pays nothing, because it's primitive index math with no references. So the target was clear: dynamic, geometry-free price levels with no GC references on the hot path.

The array-backed design

ArrayOrderBook is two pooled structures, both living in flat primitive arrays.

Price levels are an AA tree stored in parallel arrays. We took the balancing operations (skew, split, insert, delete) from an object-based AA tree and rewrote them in index form. A node is an int index into nPrice[], nLeft[], nRight[], nAA[], with per-level nHead[], nTail[], nCount[] and nTotalQty[]. Node ids come from a free-list. Best price is the leftmost node on the ask side or the rightmost on the bid side; the taker sweep is an in-order walk.

Orders are a shared slot pool, a doubly-linked FIFO per level: sOrderId[], sUserId[], sQty[], sNext[], sPrev[]. Depth is bounded only by the pool size, which is tunable rather than fixed at 64. Memory scales with resting orders, and there are no allocations or GC references on the hot path.

One design choice is worth calling out, because it's the kind of thing that's easy to get wrong. Orders key on their price, not on a node id. AA deletion rebalances by copying a successor's payload into the deleted node's slot, so node identity is not stable across deletes. If an order held a node id, a rebalance could move it out from under that reference. Keying orders on the immutable price, resolved to the current owning node with an O(log n) lookup, keeps cancels and fills correct no matter how the tree reshuffles its slots. During matching, reduceHead returns a levelEmptied flag so the sweep stops touching a node whose level was just deleted, and continues by price value with nextLevel(price), which still works when the node it consumed is gone.

Two other things changed once the geometry was gone:

Validation moved out of the book. The off-tick and out-of-range checks used to rely on the storage geometry. They now sit in a per-market PriceRules layer. Tick is still a hard rule, but the price range is a soft bound that can be adjusted at runtime.

Top-of-book needed a seqlock. Market data is published every 50 ms from a separate thread. The old book was safe to read concurrently because price-to-slot mapping is positionally stable, so a reader can never follow a dangling pointer. A tree mutates structurally, with rotations relinking nodes and ids being recycled, so a concurrent reader could see inconsistent state. The writer now publishes a top-N snapshot under a seqlock, and the market-data thread reads that snapshot instead of walking the live tree.

Checking it was correct

Replacing the core of a matching engine needs a guardrail. Ours was a determinism corpus: 15 scenarios replayed through the engine and compared byte-for-byte at the Engine.acceptOrder to MatchEventSink boundary.

We put both engines behind a MatchingEngine interface and a flag, then ran the whole corpus through both and asserted identical output, with one exception: the scenario where they should differ, because the old 64-cap rejects a 65th order and the new book rests it. That was the only difference. We added cross-implementation snapshot round-trips, so a node can recover an old snapshot into the new book and the reverse, plus a model-based test that runs 40,000 random operations against a reference TreeMap. That was enough to treat the new engine as a drop-in replacement.

Memory

With all five markets constructed and empty, the preallocated engine retains 668 MB; the array-backed one, 222 MB, about 3x less. We confirmed it on the running dev cluster with jmap: the order-book long[] footprint went from 735 MB to 182 MB.

The ratio understates the change. The 668 MB is fixed by the price geometry, the same whether the book holds ten orders or ten million. The 222 MB is the configured pool capacity, tunable per market, and the live set now scales with actual orders.

Latency

This graph changed how we think about the system.

p50 matching latency stays around 0.3 µs across the whole range, from 1,000 to 281,000 orders/sec. The order book is nowhere near saturating.

The p99 tail is the other half. It's about 10 µs at light load and rises to a few milliseconds under heavy load. That tail is not the matching engine. It's the pipeline around it: the 50 ms market-data batching window, the ingest queue, and Raft replication.

Throughput, and a measurement mistake

Our first stress test reported about 9,000 orders/sec. The number was wrong.

The cluster nodes busy-spin on their pinned cores, and our load generator also busy-spins. Co-located on the same 24-thread machine, the generator was competing with the cluster for cores, so 9,000/sec measured CPU contention rather than the engine. Pinned to four spare cores, clear of the cluster, the same test did 281,000 orders/sec, roughly 30x higher. On a single box, a co-located busy-spinning load generator measures the scheduler as much as the system; inject load from a separate machine if you can.

With the generator out of the way, we swept the offered rate up.

Accepted throughput rose linearly to 281,000/sec at 100% success and didn't plateau. The gap to the ideal y = x line is the generator topping out on four cores, not the cluster, which kept accepting everything with only a handful of backpressure events. We didn't find the cluster's ceiling here; we ran out of load-generation capacity first.

The out-of-memory bug

We pushed the dev cluster past its safe operating point and two nodes ran out of heap and crashed. They recovered through Raft, with quorum held and no data lost, but a matching engine running out of memory under load is a bad failure mode, and it was ours to fix. Better to hit it on a test box we could restart at will.

The crash pointed at the egress path, which carries trades and order statuses out to the OMS and the UI gateway. It's a chain of buffers.

The disruptor ring is bounded. The final cluster queues looked bounded. But one link in the middle, the publisher's per-event buffers, was only cleared every 50 ms, and when the flush thread fell behind (CPU starvation, a GC pause, a slow consumer) it grew without limit until the heap was gone.

We bounded it, pushed harder, and it ran out of memory again, because the next link was bounded by the wrong thing. The OMS egress queue was capped at 262,144 entries, but each entry holds a copied batch buffer of up to about 150 KB. A queue bounded by entry count, holding variable-size payloads, can hold tens of gigabytes. It is not bounded by memory at all.

There was also a constraint that ruled out the obvious fix. We couldn't backpressure the matching thread when egress filled up, because that thread is also the one that drains the final egress queue. Blocking it would deadlock the thing meant to relieve the pressure.

So the fix is the same rule at every stage: bound by bytes, and drop with a loud log on overflow instead of growing. Dropped settlement messages are recoverable, since they're derivable from the Raft log and the OMS reconciles against it. The egress is now capped at about 176 MB end to end.

The same 400,000-order/sec overload that had crashed the cluster now runs at 281,000/sec, 100% success, no out-of-memory. Under that pressure it sheds 0.08% of egress, logs it, and reconciles, rather than dying. Throughput went up, because the egress was no longer destabilizing the cluster.

One recovery detail we picked up along the way: a node rejoining as a follower under a stable leader replays its log without emitting egress, and recovers cleanly. A node that becomes leader mid-recovery re-emits the backlog and can run out of memory again. Order of operations during recovery matters.

Results

On a single Intel 13700K, three-node Raft cluster, array-backed engine, egress bounded by bytes:

What we took away

The matching engine is the cheap part. Ours is sub-microsecond and effectively unlimited next to everything around it. The expensive, dangerous problems are in the pipeline: ingest flow control, egress backpressure, replication, recovery.

Bounded has to mean bounded in bytes. A queue capped by entry count, holding variable-size payloads, is unbounded memory. We ran out of heap twice on exactly that.

Backpressure has to be designed. When you can't block the producer, the choices are shed and reconcile, or bound and degrade. Pick deliberately, more so in a system that handles money.

Check the measurement. A 30x error came from where the load generator's threads were scheduled. The first number out of a co-located benchmark is often about the harness.

Push it past the edge in dev. Each out-of-memory taught us something the passing test suite never would have.

The engine is fast, lean, deterministic, and we now understand its limits. That was the alpha baseline; the engine has since reached v0.3.0-beta with a re-measured throughput baseline; see the beta release post.

Open Exchange runs on an Aeron cluster with Raft consensus for continuous operation. We'll keep writing up what we find.