Predictable Limit Order Book + ITCH Replay

A C++20 price-time-priority matching engine built around predictable tail latency, explicit capacity, reproducible A/B benchmarks, and real NASDAQ ITCH 5.0 replay. The production book uses direct tick indexing plus a hierarchical occupancy bitmap; wide ITCH ranges automatically fall back to a sparse map representation instead of attempting an unbounded flat allocation.

Architecture

Concern	Implementation	Tradeoff
Price	Signed 64-bit integer	ITCH price4 values, including the full uint32_t range, are lossless; no floating point
Flat book	Two Levels per tick plus hierarchical 64-way occupancy bitmap	Fast direct indexing; memory proportional to configured range
Sparse book	std::map<Price, Level> baseline/fallback	Memory follows active levels; more pointer chasing and cache misses
Time priority	Intrusive doubly linked FIFO per side/price	Constant-work append and arbitrary unlink; two pointers per order
Cancel lookup	Fixed-capacity open-addressed ID index with backward-shift deletion	O(1) expected, no resize/tombstone buildup; capacity chosen up front
Order memory	Preallocated free-list pool	No allocation on the engine hot path; explicit exhaustion status
Best recovery	Multi-layer bitmap with countl_zero/countr_zero	O(log_64(range)), replacing the old data-dependent tick scan
Feed reconstruction	Explicit non-matching AddResting action	Reuses pool/index/levels/bitmap without confusing outbound ITCH with order entry

Matching contract

• New orders match best price first, then FIFO at that price, and trade at the resting price.
• Residual quantity rests at the tail. A fully consumed aggressor returns Filled.
• Cancel locates order_id -> node* and unlinks without walking the level.
• Same-price quantity reduction retains priority. An increase or price change cancels and reinserts, losing priority.
• A repriced modify may trade: full execution returns Filled; partial execution plus a resting residual returns Modified and emits trades through the callback.
• AddResting is reserved for trusted replay/recovery state and never matches.
• Invalid/off-tick prices, zero quantities, duplicates, unknown IDs, and exhausted capacity return explicit statuses.

Command and OrderNode include a 64-bit owner_id. Engines can select:

• Allow (default)
• CancelAggressor
• CancelResting
• DecrementBoth

Owner zero means unspecified and does not trigger STP. Tests cover every policy, including the absence of emitted trades for prevented quantity.

Every prevention also emits a SelfTradePrevention callback containing the action, resting/aggressor IDs, owner, price, and affected quantity. This makes CancelResting liquidity removal observable and lets callers distinguish an Accepted residual after DecrementBoth from an ordinary add.

Build and verification

Requirements: CMake 3.24+, Ninja, and a C++20 compiler. Dependencies are pinned with FetchContent.

cmake --preset debug
cmake --build --preset debug
ctest --preset debug

cmake --preset release
cmake --build --preset release
ctest --test-dir build/release --output-on-failure

• debug: ASan + UBSan, frame pointers.
• release: -O3 -march=native.
• profile: -O3 -g -fno-omit-frame-pointer for perf record/flamegraphs.
• tsan: ThreadSanitizer configuration for the SPSC queue tests.

The suite currently contains 45 tests covering matching, modify semantics, STP and prevention observability, invalid configuration rejection, 100K ID churn, wide bitmap ground-truth checks, binary ITCH offsets/framing, high price4, MoldUDP64 sequencing/retransmission, CRC32C journals, flat and sparse replay, exact anomaly counters, real-fixture reconciliation, snapshot+WAL resume, multi-instrument sharding, sequence gaps, and cross-thread SPSC publication. Debug and Release pass locally; concurrency tests also run under TSan.

Parser fuzzing

The libFuzzer target attacks both raw message bodies and length-framed streams:

cmake -S . -B build/fuzz -G Ninja \
  -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ \
  -DLOB_BUILD_TESTS=OFF -DLOB_BUILD_BENCHMARKS=OFF \
  -DLOB_BUILD_HARNESS=OFF -DLOB_BUILD_FUZZERS=ON
cmake --build build/fuzz --target itch50_fuzz
./build/fuzz/itch50_fuzz -runs=100000

Ubuntu Clang CI builds and smoke-runs 20K cases. The local Apple Command Line Tools installation compiles the target sources but lacks libclang_rt.fuzzer_osx.a, so a local macOS fuzzer pass is not claimed.

NASDAQ ITCH 5.0

The fixed-buffer streaming parser supports the book-mutating messages A/F/E/C/X/D/U, System Events (S), explicit big-endian decoding, six-byte timestamps, strict recognized-message lengths, clean early stopping at a record boundary, and safe counting/skipping of unsupported types.

./build/release/lob_itch_replay <decompressed-itch-file> AAPL

Useful options:

--representation auto|flat|sparse
--max-flat-levels N       # auto-mode threshold; default 2,000,000
--capacity N              # otherwise discovered peak live orders + 1024
--snapshot FILE           # persist the final deterministic book state
--strict                  # nonzero exit if replay anomalies were counted

Replay makes two streaming passes. Discovery identifies the selected stock locate, exact raw-price range, and peak live-order count. Auto mode chooses the bitmap only when the range fits the configured threshold; otherwise it instantiates BasicMatchingEngine<MapBook>. Thus high absolute prices and wide names do not imply multi-gigabyte tick arrays. Partial executions/cancels reduce in place and preserve FIFO; replaces use the new reference and lose priority.

Default replay treats counted anomalies as statistics and returns success when parsing is structurally sound. --strict converts any rejected update into exit code 3. Applied and attempted counters are separate, so a failed reduction is never reported as an execution/cancel success.

An equal opposing price is deliberately classified with a crossed update (>= for bids, <= for asks): NASDAQ's own displayed book should have executed rather than retain a locked same-venue quote. These updates are rejected before mutation and counted as locked_or_crossed.

Retained real-data evidence

The repository includes samples/01302019.AAPL.ITCH50.subset, extracted without re-encoding from NASDAQ's official 2019 ITCH file.

Provenance/result	Value
Trading date / stock / locate	2019-01-30 / AAPL / 14
Fixture SHA-256	d51d2166a08b2fe6019f2d2654c9a0d339dee4801cce33dc1af7f3d300e0bd73
Messages / malformed / rejected	303 / 0 / 0
Adds / executions / cancels / deletes	178 / 57 / 1 / 60
Unsupported/ignored / final resting	7 / 101
Executed shares	8,419
Local replay throughput	~2.87M feed messages/sec

This is a small genuine parser/replay fixture, not a full-day throughput claim. Exact derivation is documented in samples/README.md. scripts/replay_sample.sh prints SHA-256, system, compiler, and replay output for any retained sample.

Snapshots, recovery, and gaps

snapshot.hpp implements a versioned, endian-defined snapshot format containing configuration, STP policy, and FIFO-ordered records (id, owner, side, price, quantity). FIFO order within each (side, price) level is an explicit format contract; global price-level traversal order may differ by representation. Restore rejects bad magic/version, configuration mismatch, invalid/crossed records, duplicates, insufficient capacity, and nonempty targets. On failure the caller discards the partially constructed target.

The retained AAPL fixture is also a reconciliation property test: two full replays must produce byte-identical snapshots and identical applied-execution streams; midpoint replay → snapshot → restore → remaining replay must equal straight-through replay; and bitmap and sparse books must finish with identical per-level FIFO state, best prices, statistics, and execution stream.

./build/release/lob_itch_replay samples/01302019.AAPL.ITCH50.subset AAPL \
  --snapshot aapl.snapshot
./build/release/lob_snapshot_restore aapl.snapshot

Restore automatically chooses flat or sparse representation from snapshot range. The same API is tested with high-price sparse books and preserves FIFO, owners, quantities, and best prices.

SequenceTracker is intentionally transport-facing: it detects missing, duplicate, and old MoldUDP64/Soup envelope sequences and requires explicit resynchronization. The two-byte ITCH tracking field is not incorrectly treated as a transport sequence. A decompressed historical file contains no original UDP envelope, so live retransmission coordination remains an integration concern.

Live transport and durable recovery

lob_mold_capture is a POSIX live MoldUDP64 receiver. It joins a multicast group, validates complete datagrams before delivery, suppresses duplicates, handles overlapping retransmissions exactly once, detects gaps, optionally emits UDP retransmission requests, and appends each sequenced ITCH body to a CRC32C write-ahead journal before parsing and dispatching it to four bounded, single-owner book shards.

./build/release/lob_mold_capture \
  <multicast-group> <port> live.wal <interface-ip> 0 \
  <retransmission-host> <retransmission-port> 1

The fsync interval defaults to 1 for durability, while a larger value is an explicit throughput/durability tradeoff. Optional trailing arguments set per-instrument order capacity (default 65,536) and socket receive-buffer bytes (default 16 MiB). SIGINT/SIGTERM drains the shards, durably flushes the journal, and prints transport, parser, backpressure, worker, and per-book summaries. Heartbeats, malformed datagrams, gaps, duplicates, ITCH parse failures, journal failures, and retransmission requests are counted separately.

The journal format is versioned by magic, network-endian, strictly monotonic by sequence, length-bounded, and CRC32C-protected. lob_journal_replay replays it through four single-owner shards and can write one sequence-bearing snapshot per instrument:

./build/release/lob_journal_replay live.wal 0 snapshots/
./build/release/lob_snapshot_restore snapshots/14-AAPL.snapshot

Snapshot version 2 stores the last durable transport sequence. Recovery can load that snapshot and replay only journal records after the recorded sequence. The real-fixture test proves full replay equals journal → midpoint snapshot → restore → remaining journal.

Latency measurement

The standalone harness preallocates all measurement/live-ID storage, times only the engine operation, and records official HdrHistogram p50/p99/p99.9/max buckets. Successful and intentionally rejected cancels use separate histograms. On x86 it uses fenced rdtscp; other platforms report steady-clock ticks.

Latest 1M-message Apple Silicon sanity run (non-isolated macOS; clock ticks are nanoseconds here):

Operation	p50	p99	p99.9
Add	84 ns	250 ns	416 ns
Successful cancel	84 ns	292 ns	458 ns
Rejected cancel	83 ns	208 ns	375 ns
Match	84 ns	250 ns	375 ns

Throughput was 7.10M messages/sec. These figures are laptop sanity checks, not pinned Linux claims.

Representation A/B

The pathological benchmark removes a best bid separated from the next bid by an empty gap:

Gap	Linear p50	Linear p99.9	Bitmap p50	Bitmap p99.9
1,000	375 ns	875 ns	below clock quantum	83 ns
10,000	5,043 ns	31,887 ns	below clock quantum	42 ns
100,000	48,351 ns	142,591 ns	below clock quantum	42 ns
199,999	131,839 ns	542,207 ns	below clock quantum	42 ns

The same-run common case removes adjacent best prices: bitmap 22.0 ns CPU versus linear 16.2 ns, exposing the real maintenance tax. Match-at-top measured bitmap 22.0 ns versus map 45.3 ns. Keep both sides of that story: predictable worst-case recovery costs a few nanoseconds on level transitions.

For defensible Linux evidence, build Release on the target and run scripts/linux_benchmark.sh. It records UTC time, kernel, CPU, compiler, governor, selected core, five pinned trials, and the A/B benchmark. The manual operational-evidence workflow runs the same harness on Ubuntu and uploads its complete log. No pinned Linux result is claimed from this macOS environment.

Memory and scaling

On the current 64-bit ABI, a 200K-tick flat book uses roughly 9.6 MB for bid/ask level metadata. Adding owner_id makes each pooled order approximately 48 bytes, so a one-million-order pool is about 48 MB. A 1M-capacity ID index rounds to 2,097,152 slots and is about 50 MB at 24 bytes/slot. A generously configured flat instrument is therefore around 108 MB plus bitmap/container overhead.

ITCH replay does not blindly clone that layout. Auto representation uses the flat bitmap only up to two million levels (about 96 MB of level metadata), then selects the sparse map. Production multi-instrument deployment should additionally use per-symbol capacities/bands or segmented/radix structures. One-owner-per-shard solves synchronization ownership, not memory per instrument.

SPSC sharding primitive

SpscQueue<T, Capacity> is a bounded power-of-two queue with cache-line-separated cursors. The producer publishes a fully written slot with a release store; the consumer observes it with an acquire load. Consumer head publication uses the symmetric release/acquire pair before producer reuse. No claim that it is universally faster is made; TSan covers a 500K-item ordered cross-thread transfer.

ShardedMarket<N> now supplies that dispatcher: stock-locate hashes to one owner thread, every shard has bounded SPSC ingress, sparse per-instrument books avoid cloning huge flat ranges, and enqueue rejection exposes backpressure. Worker exceptions are contained and counted instead of terminating the process. Tests replay the retained AAPL fixture through four shards and verify the same 101-order final state; the complete Mold gap → retransmit → journal → parse → shard pipeline is also tested for exactly-once application.

Deployment evidence still environment-bound

The code paths and repeatable automation are complete, but results that require external infrastructure cannot honestly be manufactured in this workspace:

1. Execute scripts/full_day_replay.sh (or dispatch operational-evidence with full-day enabled) on a machine with enough bandwidth/storage and retain its checksum, resource usage, replay, restore, and snapshot reports.
2. Run the provenance harness on the actual pinned, isolated production-class Linux core and publish all trials; a shared GitHub runner is useful evidence but is not an isolated-host latency claim.
3. Add venue-specific owner/MPID entitlement data before enabling STP for ITCH-derived flows.
4. Integrate the capture process with the venue-provided retransmission endpoint, credentials, network interface, and operational alerting in its deployment environment.
5. Load-test shard count, per-symbol capacity, fsync interval, and backpressure policy with the actual production symbol universe.