Market Microstructure 101: How a Limit Order Book Actually Works

Price-time priority, in one sentence

At a given price level, the order that arrived first fills first — full stop. That single rule is what makes a limit order book fair and deterministic, and it's why the data structure underneath it is a sorted collection of price levels, each holding a FIFO queue of resting orders:

Bids (highest first)         Asks (lowest first)
100.25 -> [order A, order C]  100.30 -> [order B]
100.20 -> [order D]           100.35 -> [order E, order F]

A marketable order walks the opposite side's queue from the best price outward, consuming resting orders in arrival order until it's filled or the book runs out of liquidity at an acceptable price. Everything else in a matching engine — cancellation, self-trade prevention, even how fast the thing runs — is in service of keeping that one rule true under concurrent, high-frequency load. The Limit Order Book Simulator is a from-scratch C++20 implementation of exactly this, compiled to WebAssembly for the live demo embedded further down.

The data structure

Price levels live in

using Bids = std::map<Price, PriceLevel, std::greater<Price>>;
using Asks = std::map<Price, PriceLevel, std::less<Price>>;

— bids ordered descending, asks ascending, specifically so that map::begin() is always the best price on either side, with no separate "find the max" step. std::map also buys something less obvious than ordered iteration: iterator and pointer stability across inserts and erases of other keys. That matters here because a cancel handle stored for one price level has to stay valid even while unrelated price levels are being added and removed elsewhere in the book — a hash-based ordered structure wouldn't give you that guarantee for free.

Each PriceLevel wraps a std::list<Order>, not a std::deque, and that choice is deliberate rather than a default reached for out of habit: cancellation needs O(1) erase from an arbitrary interior iterator without invalidating the iterators of neighboring elements, and std::deque only guarantees O(1) erase at the front or back — an interior erase on a deque can invalidate other iterators and is generally linear. std::list guarantees both.

That still leaves the question of how you find the right iterator to erase in the first place, given only an order ID. The answer is a handle table:

std::unordered_map<OrderId, OrderHandle> handles_;
// OrderHandle = { Side, Price, PriceLevel::Handle }
// PriceLevel::Handle = std::list<Order>::iterator

Cancelling an order is a hash lookup to find its side, price, and list iterator, then an O(1) erase from that specific list — no scanning the book, no walking price levels. One sharp edge in that code worth calling out: the handle's iterator has to be copied out of handles_ before erasing the entry from handles_ itself, because erasing from the map can invalidate the reference you're still holding into it. It's a small thing, but it's exactly the kind of bug a differential fuzzer (more on that below) is built to catch if you get it wrong.

One more detail that looks minor and isn't: prices are stored as int64_t ticks, never as floating point. Floats as std::map keys are a well-known footgun — two prices that should compare equal can silently fail to, which would corrupt price-level grouping — and it also matters for testing: the differential fuzzer's exact-equality assertions between the production book and a reference implementation only mean something if price comparisons are exact, not "close enough."

Matching mechanics

A limit order's price acts as a gate on the matching loop — it walks the opposite side's price levels from the best price outward, but stops the moment the best remaining level would cross past the order's limit price. A market order has no such gate: it sweeps until either it's fully filled or the book runs dry, and — this is a specific design choice, not the only valid one — any unfilled remainder is dropped rather than rested as a resting limit order at the last traded price. That's IOC (immediate-or-cancel) behavior: a market order that can't fully fill doesn't linger in the book waiting for more liquidity to show up.

Self-trade prevention follows a "cancel-newest" policy, and where it's checked in the loop matters. The check happens before any partial fill is considered on that resting order: if the resting order's client ID matches the incoming order's client ID, the incoming order's entire remaining quantity is zeroed out and rejected — not skipped over in favor of the next resting order at that level. Skipping ahead would be the more liquidity-friendly choice, but it would also break time priority for every other order resting at that price level, which is the one invariant the whole system exists to protect. A stricter, less permissive rule here is the price of keeping that guarantee intact.

Proving it's actually correct

None of the above is worth much without evidence it's actually implemented right, and "actually right" for a matching engine means something quite specific: given the same sequence of operations, the production book and a naive, obviously-correct-but-slow reference implementation must agree on every observable outcome, every time.

That's what the differential fuzzer does. It drives both lob::OrderBook (the real, std::map/std::list/handle-table implementation above) and a NaiveReferenceBook (a straightforward O(n) linear-scan implementation, easy to convince yourself is correct by inspection) with an identical seeded std::mt19937_64 random sequence — same operation types, same prices, same quantities, same client IDs, applied to both books in lockstep. After every single operation, it asserts exact agreement on:

• the cancel return value and any newly assigned order ID
• the full trade list — id, aggressor, resting order, price, and quantity, not just a trade count
• the best-bid/best-ask invariant and that the book is never left crossed
• a complete resting-order snapshot, sorted by ID, compared field by field

On any mismatch, it prints the seed and iteration index that produced it, so a failure is reproducible on demand rather than a one-off flake. In CI and local development it runs 100,000+ iterations across multiple independent seeds — cheap enough to run constantly, and specific enough that when it fails, you know exactly which operation broke agreement.

Does it actually scale

Correctness without performance data is just a claim, so the project backs it with real Google Benchmark numbers (Apple M4, -O3, Google Benchmark v1.9.1, 7 repetitions per point) rather than asymptotic hand-waving:

Both are flat to within measurement noise across four orders of magnitude of book depth — the handle table's O(1) lookup means cancellation cost genuinely doesn't care how deep the book is. Match cost is a different shape entirely, and correctly so: it scales with the number of price levels crossed by an aggressive order, not with total book depth. Sweeping from 1 to 256 levels costs roughly 414ns to 11.2μs — about 42ns per level — and that number holds steady whether the background book sitting untouched on both sides is empty or 10,000 levels deep, confirming the cost really is "levels touched," not "levels that exist."

The honest part is the number that didn't fit a clean story. A mixed workload (70% new orders, 20% cancels, 10% market orders, driven by a Poisson-arrival order-flow generator) throughputs at 14.4M and 15.0M operations/second at book depths of 10 and 100 — then drops to 8.2M at depth 1,000 and 2.7M at depth 10,000. The project's own BENCHMARKS.md doesn't paper over this: it flags the drop-off as fitting O(log N) poorly (RMS 40%) and attributes it, provisionally, to cache locality on the live working set — the handle table plus scattered list nodes — rather than to any change in algorithmic complexity, and leaves further investigation (perf, cachegrind) as an open item rather than a solved one. A benchmark suite that only reports the numbers that confirm the thesis isn't measuring anything; this one reports the one that complicates it.

From C++ to the browser

The matching engine itself doesn't know anything about JavaScript — it's compiled via Emscripten (emcc -O3 -flto --bind) with a thin embind binding layer (LobEngine) wrapping OrderBook and exposing submitLimitOrder, submitMarketOrder, cancelOrder, and two very differently-shaped ways of getting data back out to the browser.

Book snapshots are pull-based: the frontend polls on a throttle, and each poll writes the current book state into a pre-allocated flat double[64] buffer exposed to JavaScript as a zero-copy typed_memory_view — no per-level JS object allocation, no per-tick push across the JS/WASM boundary for data nobody's watching at 60fps anyway. Trades, by contrast, are push-based: a setOnTrade callback fires once per trade as it happens, because trades are comparatively rare and the trade tape wants each one individually, in order, not batched into the next poll. Same engine, two different marshaling strategies, chosen to match how frequently each kind of data actually needs to move — not applied uniformly out of consistency for its own sake.

Watch it match, live

Submit a limit order inside your own spread and watch it rest at the back of its price level's queue; submit a marketable order and watch it walk the book exactly as described above. The ladder, depth chart, and trade tape are all reading the same snapshot/trade-event pipeline just described.

Source, the differential fuzzer, and the full BENCHMARKS.md are on GitHub.