Building a Prediction Market From Scratch — Performance: From 50K to a Million Orders a Second

“How many orders a second can it do?” is the question everyone asks about a matching engine. It’s the wrong first question. The right one is: where does the time actually go? Because almost everyone guesses wrong — they go optimize the matching algorithm, when the real cost is sitting somewhere much less glamorous.

This post is the performance roadmap for Zhulong, our prediction-market engine. I’ll show you where the time goes, why the engine needs a write-ahead log, a handful of latency numbers worth memorizing, and a ladder that climbs from tens of thousands of orders per second to a million. Every number you’ll see I measured on one machine (an Apple M4 Pro) — they’re here for the ratios, not the absolute values, and the benchmark that produced them is at the end so you can run it yourself.

Where the time actually goes

Rank the costs in a naive matching engine from biggest to smallest, and the order surprises people:

1. The fsync that makes orders durable. fsync is the call that forces your data to physically land on the disk and waits for the disk to confirm. If you naively do one after every order, it dwarfs everything else — by a factor of thousands.
2. Memory allocation. Whenever a program needs to store something whose size isn’t known ahead of time, it asks the system for a chunk of memory and hands it back when done. One request is cheap — but a matching engine does this hundreds of thousands of times a second, once for every order and every trade, and then the borrowing-and-returning of memory itself becomes the hot spot, not the matching.
3. The match itself — book lookups, walking price levels, the FIFO queues.
4. Post-trade bookkeeping, event serialization, the network.

Notice the algorithm everyone wants to tune is third. The first two are plumbing. So before any of this makes sense, we have to talk about that fsync — and why it’s there at all.

Why a write-ahead log

The engine keeps everything in memory — order books, balances, positions. Memory is fast, but it has one fatal flaw: pull the plug and it’s gone. A crash, a kill, a power blip, and every order someone just placed vanishes. For anything touching money, that’s not acceptable.

So before applying a command, the engine appends it — the command, the input, not the resulting state — to a local file and fsyncs it to disk. Only after that does it touch memory, and only then does the user hear “accepted.” So “your order went through” means “your order is already on disk.” If the process dies a microsecond later, the order survives. On restart, replay the log from the top and the in-memory state rebuilds itself, bit for bit — because the engine is deterministic: same inputs, same state.

This is why the database gets demoted to an async mirror, and why the write-ahead log, not the database, is the source of truth. (I went deep on this in the architecture chapter.) The point for this post is simpler: durability has a price, and the price is fsync. Which brings us to the one idea about latency that reorganizes how you think about all of it.

The latency numbers worth memorizing

The single most useful thing a systems programmer can carry around is a gut feel for how much slower one thing is than another. They aren’t a little different. They’re different by orders of magnitude. Here’s the ladder, with a trick: blow up 1 ns to 1 second, and see how human those gaps become.

Just read the last few rows. An fsync (milliseconds) is about a million times slower than a memory operation (nanoseconds). So “fsync after every order” turns an engine that could do hundreds of thousands a second into one that does a few hundred. That’s not a tuning problem. That’s a difference in kind — and it’s the first rung on the ladder.

The ladder, one rung at a time

Each rung removes one bottleneck. The numbers in bold are measured speedups from the benchmark at the end.

S0 — Correct and naive. BTreeMap for price levels, HashMap for orders, VecDeque for the FIFO queues, and an fsync after every command. It runs, it’s easy to read, it’s slow. Always start here: correctness first. A fast engine that settles trades wrong is worthless.

S1 — Batch the fsync (group commit). Don’t flush after every order. Write a batch of commands, then fsync once. The cost of an fsync is roughly fixed regardless of how much you’re flushing, so one flush amortized over a thousand commands nearly disappears. Measured: fsync-ing after every order manages a mere 261 orders/sec; batching lifts it to 145,000 orders/sec — a 558× jump. In production you don’t wait for a full batch (that would starve latency) — you flush every ~1 ms or every K commands, whichever comes first. You trade at most a millisecond of latency for hundreds of times the throughput, and you still never lose an order. Best deal in the building.

S2 — Stop borrowing memory on the hot path (the code that runs for every single order). Instead of asking the system for a fresh chunk on every order and trade and handing it back, keep one chunk around and reuse it — empty it and refill it. Think of a worker who runs to the tool room for a screwdriver and returns it after every single screw: the trips cost more than the work. Keep the screwdriver in hand. Measured: borrowing a fresh chunk on every operation costs 13.2 ns; reusing one costs 0.8 ns — 16×. Once you stop asking for memory, you stop paying for it.

S3 — Pick the right data structure (our unfair advantage). A general exchange has a huge price range, so it needs a tree-shaped structure (a BTreeMap — lookups get slower as more price levels pile up, and its scattered memory is unfriendly to the CPU cache). But a prediction market’s prices are just 1 to 99 cents — whole numbers, with a fixed ceiling. So the order book can be a plain fixed array of 99 slots, one queue per slot. Finding a price level is then constant-time (the same speed no matter how many levels there are) and sits in contiguous, cache-friendly memory; finding the best price is a single CPU instruction over a small bitmap — a row of 0/1 bits marking which slots have orders. Measured: the tree is 12.1 ns/op, the array 0.7 ns/op — 17×. The thing other engines sweat over, we get nearly for free, just because our price space is tiny. This is the real reason a prediction market is easier to make fast than a general exchange.

S4 — Squeeze out the system overhead. By now the algorithm isn’t the bottleneck — the operating system’s own overhead is. Pin the matching thread to a single CPU core, so the OS never pauses it to run something else. Replace the lock-based queue with a lock-free one — a fixed ring of slots that the producer and consumer hand off without either ever taking a lock. Move every bit of I/O — disk, network, sending events out — onto other threads, so the matching thread does nothing but match. Process commands in small batches to spread the fixed costs. This bundle of techniques is how LMAX, a London trading venue, famously pushed a single thread past a million operations a second more than a decade ago. It’s the most work, so it comes last — only after the benchmarks prove the earlier rungs landed.

S5 — Shard by market. One core has a ceiling. But different markets’ books are completely independent — market A’s matching has nothing to do with market B’s. So run N matching cores, each the sole writer of its own books. Throughput scales nearly linearly with cores. That’s what “millions per second” means for a venue: ~1M per book, multiplied across shards.

Is a million realistic? Where the pros land

A reality check, because these targets aren’t fantasy. Here’s roughly where established venues sit, using their own publicly reported figures. Read the numbers as orders of magnitude, not a leaderboard — they mix definitions (orders vs. messages vs. trades, one symbol vs. a whole venue, matching-only vs. end-to-end):

Two things stand out. First, our S5 target — around a million orders a second per book, scaled out by sharding — sits in the same range as LMAX’s single thread and the big venues’ order of magnitude. We’re not chasing a number nobody hits. Second, look at Hyperliquid: a fully on-chain order book runs near 200k orders/sec. That’s the bar the on-chain settlement layer (M4) would have to clear, and it’s plainly within reach — reassuring for the day this market goes on-chain.

Publicly reported figures, for orientation only. Sources: the LMAX Disruptor paper, Nasdaq INET, CME Globex, Binance, and the Hyperliquid docs.

The twist: determinism and speed are on the same side

It’s easy to assume safety and speed fight each other. Here they don’t. The choices that make the engine deterministic — a single thread, no locks, commands processed in strict order — are the same choices that make it fast: no lock contention, no cache lines bouncing between cores. And the write-ahead log that guarantees durability is made cheap by the very same group-commit trick from S1.

So the MVP — one process, in memory, with a WAL — isn’t a throwaway you’ll rewrite when you need speed. It’s already the right foundation for a million orders a second. You don’t rebuild to get there; you climb. S1 to S5 are all additive.

See it for yourself

Here’s the self-contained benchmark behind the three measured numbers — no dependencies, just rustc -O perfdemo.rs && ./perfdemo:

use std::collections::BTreeMap;
use std::fs::OpenOptions;
use std::io::Write;
use std::time::Instant;

fn main() { bench_fsync(); bench_pricelevels(); bench_alloc(); }

// (1) Why group commit: fsync per write vs one fsync for the batch
fn bench_fsync() {
    let n = 1000u64;
    let path = std::env::temp_dir().join("perfdemo_wal.bin");
    let payload = [0u8; 64];
    let mut f = OpenOptions::new().create(true).write(true).truncate(true).open(&path).unwrap();
    let t = Instant::now();
    for _ in 0..n { f.write_all(&payload).unwrap(); f.sync_all().unwrap(); }
    let per = t.elapsed();
    let mut f = OpenOptions::new().create(true).write(true).truncate(true).open(&path).unwrap();
    let t = Instant::now();
    for _ in 0..n { f.write_all(&payload).unwrap(); }
    f.sync_all().unwrap();
    let batched = t.elapsed();
    let _ = std::fs::remove_file(&path);
    println!("fsync/write: {:.0} ops/s | batched: {:.0} ops/s | {:.0}x",
        n as f64 / per.as_secs_f64(), n as f64 / batched.as_secs_f64(),
        per.as_secs_f64() / batched.as_secs_f64());
}

// (2) Why a fixed array beats BTreeMap when prices are 1..99
fn bench_pricelevels() {
    let n = 5_000_000u64;
    let mut book: BTreeMap<u64, u64> = BTreeMap::new();
    let mut s = 0u64;
    let t = Instant::now();
    for i in 0..n { let p = 1 + (i % 99); *book.entry(p).or_insert(0) += 1;
        if let Some((&p, _)) = book.iter().next_back() { s ^= p; } }
    let bt = t.elapsed();
    let mut arr = [0u64; 100]; let mut s2 = 0u64;
    let t = Instant::now();
    for i in 0..n { let p = (1 + (i % 99)) as usize; arr[p] += 1;
        let mut best = 0; for q in (1..100).rev() { if arr[q] != 0 { best = q; break; } } s2 ^= best as u64; }
    let ar = t.elapsed();
    println!("BTreeMap: {:.1} ns/op | array: {:.1} ns/op | {:.1}x",
        bt.as_nanos() as f64 / n as f64, ar.as_nanos() as f64 / n as f64,
        bt.as_secs_f64() / ar.as_secs_f64());
    let _ = (s, s2);
}

// (3) Why the hot path must not allocate
fn bench_alloc() {
    let n = 5_000_000u64; let mut s = 0u64;
    let t = Instant::now();
    for i in 0..n { let mut v: Vec<u64> = Vec::new(); v.push(i); v.push(i ^ 7); s ^= v.iter().sum::<u64>(); }
    let a = t.elapsed();
    let mut buf: Vec<u64> = Vec::with_capacity(8);
    let t = Instant::now();
    for i in 0..n { buf.clear(); buf.push(i); buf.push(i ^ 7); s ^= buf.iter().sum::<u64>(); }
    let r = t.elapsed();
    println!("Vec::new: {:.1} ns/op | reused: {:.1} ns/op | {:.1}x",
        a.as_nanos() as f64 / n as f64, r.as_nanos() as f64 / n as f64,
        a.as_secs_f64() / r.as_secs_f64());
    let _ = s;
}

On an Apple M4 Pro: fsync/write 261 ops/s → batched 145,486 ops/s (558x), BTreeMap 12.1 ns → array 0.7 ns (16.9x), Vec::new 13.2 ns → reused 0.8 ns (16.7x).

One rule holds the whole thing together: don’t optimize without a number. Profile first — the bottleneck is almost always the fsync or the allocator, not the algorithm you assumed. We’ll keep a benchmark on every layer as the engine grows, and a throughput guard test that fails the build if a change quietly makes matching slower. And as promised — every line of it open, free, no strings.