TRIDENT

A from-scratch exchange core: match, persist, query — one binary, zero third-party dependencies.

NASDAQ ITCH 5.0 in → sub-microsecond order-book updates → a durable, crash-safe audit trail → SIMD- and JIT-accelerated regex analytics over billions of events. Three elite systems on one lock-free spine, written in C++20 (libc + compiler intrinsics only — no Boost, no abseil, no external anything).

Portfolio project. Every number below was measured on the machine named under Methodology; every correctness claim is backed by a test in tests/ or tools/. Read Methodology before quoting any figure — the honest scope of each metric is stated there.

---

The three engines

1. Match — a lock-free limit order book & matching engine. Zero-copy ITCH 5.0 replay, an O(1) bitmap price ladder (best bid/ask = three tzcnts, no tree walk), intrusive FIFO queues for price-time priority, a flat SIMD-free Swiss-style order map, and a slab allocator so the steady state never calls malloc.
2. Persist — an embedded LSM-tree audit store. A write-ahead log with group commit, immutable SSTables (fixed-width records → the file is a binary-searchable array, no index block), blocked bloom filters, and loser-tree K-way compaction. Crash recovery is a pure function of disk.
3. Query — a JIT-compiled regex analytics engine. A regex becomes a Thompson NFA → byte-class DFA → x86-64 machine code emitted at runtime into W^X memory, with an AVX2/AVX-512 prefilter, scanning the SSTables in one fused pass.

---

Architecture — four pinned threads, connected only by lock-free rings and immutable files

   data/*.NASDAQ_ITCH50           (mmap'd, zero-copy, big-endian)
            │
            │  2-byte length-framed messages
            ▼
 ┌─────────────────────────┐                        ┌─────────────────────────┐
 │  CORE 4 · MATCH          │   SPSC ring A          │  CORE 6 · WAL / PERSIST  │
 │                          │   64B events,          │                          │
 │  zero-copy ITCH parse    │   128B-padded indices, │  drain ring → group      │
 │  bitmap ladder (tzcnt)   │   release/acquire      │  commit → CRC32C-framed   │
 │  intrusive FIFO, O(1)    │──────────────────────▶ │  WAL segments (fdatasync)│
 │  cancel; slab alloc      │   plain mov on x86,    │  append to memtable      │
 │                          │   no lock/syscall/     │  DEGRADATION LADDER on    │
 │  ingest→book: p50 86 ns  │   malloc               │  ring pressure           │
 └─────────────────────────┘                        └────────────┬─────────────┘
      ▲  the ONLY coupling to storage is ring occupancy;          │ full memtable
      │  a 77 ms fsync stall cost the matcher 628 ns worst-case   │ (SPSC handoff)
      │                                                           ▼
 ┌─────────────────────────┐                        ┌─────────────────────────┐
 │  CORE 5 · QUERY          │   epoch-guarded        │  CORE 2 · FLUSH/COMPACT  │
 │                          │   mmap of immutable    │                          │
 │  regex → NFA → DFA →     │   SSTables             │  sort memtable → SSTable │
 │  x86-64 JIT (W^X)        │◀───────────────────────│  (pair-sort, blocked     │
 │  AVX2/AVX-512 prefilter  │   readers never block  │  bloom); loser-tree      │
 │  57 GB/s in-L1 scan      │   the writer           │  L0→L1 compaction        │
 └─────────────────────────┘                        └─────────────────────────┘

The load-bearing property: the matching thread's entire interaction with storage is one cache-line write + one release store (a plain mov on x86-TSO). Disk latency is physically unreachable from the hot path — proven under a simulated storage stall in M6.

---

Measured results

Single core each, i7-1165G7 (Tiger Lake), Windows 11, MinGW-w64 GCC 16.1, -O3 -march=native. No core isolation (Windows has no isolcpus), so tails carry OS-scheduler noise — medians and p99 are trustworthy, max is polluted.

Latency (nanoseconds) — rdtsc, every sample recorded, log-linear histograms

Path	p50	p90	p99	p99.9
ITCH parse + full field decode	13	16	25	58
Ingest → book update (parse + apply, 100K-order book)	86	156	280	1408
Ingest → book update, real NASDAQ day (8,906 symbols)	304	720	1920	7168
IOC match vs resting book (incl. ~29 ns rdtsc overhead)	72	272	544	1008
Producer latency with storage pipeline attached	164	288	480	1120
Matcher latency under a 77 ms simulated fsync stall	132	208	336	472
Regex JIT match	~10 ns/symbol

Throughput

Metric	Result
ITCH parse (warm)	71 M msg/s (3.7 GB/s)
Order-book replay	9.4 M msg/s
Full durable pipeline (parse→book→ring→WAL)	4.5 M events/s, 0 ring stalls
SIMD byte scan, in-L1 (compute-bound)	scalar 3.7 · AVX2 39.4 · AVX-512 57.7 GB/s (20.6 bytes/cycle)
SIMD byte scan, 256 MB (DRAM-bound)	~13 GB/s — all widths converge at the memory wall

Correctness & crash-recovery invariants

Test	Result
Golden book (golden_m2)	4,999,990 consecutive top-of-book snapshots byte-identical to a naive std::map/std::deque reference
Golden regex (golden_regex)	4 engines (Thompson NFA · DFA · Glushkov bit-parallel · JIT x86-64) agree on curated + exhaustively-fuzzed inputs
I1 prefix property (walcheck)	crash leaves only a torn tail; damage anywhere else = FAIL
I2 sequence continuity	seq strictly 1,2,3,… across every record and segment boundary
I3 recovery equivalence (recover_m4)	book rebuilt from the WAL alone hash-matches the live book (4,999,990 events)
Crash harness (crash_m3.ps1)	10/10 random kill -9 → gap-free prefix; deliberate tail-chop accepted
Record conservation	events in SSTables after compaction == events in WAL, exactly
Query cross-check	every demo query == a brute-force NFA scan of the store
Real-day parse	268,744,780 messages, 0 unknown types, 0 length mismatches, missing-refs = 0

Crisis engineering (M6)

• Write-stall insulation. Injected a 77 ms fsync stall (simulating a compaction storm saturating the NVMe). The degradation ladder climbed all four tiers (Normal 27% → ShedSync 23% → ShedIndex 36% → RawSpill 14% of the run); 0 events dropped, 0 matcher waits, matcher p99.9 = 472 ns. Storage latency and matcher latency differ by ~100,000×.
• Matcher vs query interference. A concurrent analytics scan streaming ~5 GB perturbs matcher p99 by up to +65% (148 → 244 ns) via shared L3/DRAM bandwidth — but on this non-isolated laptop the effect is within run-to-run noise (some runs show none). Cleanly isolating it needs L3 way-partitioning (Intel CAT) or a second NUMA node — a server measurement this hardware can't make honestly.

---

Build & run (Windows, MinGW-w64 GCC ≥ 13)

./build.ps1                              # -O3 -march=native, all targets
./mkitch.exe synth.itch 5000000          # generate book-consistent ITCH data
./run_all.ps1                            # full test + benchmark suite (M0–M6)

Individual milestones:

./bench_m0.exe                           # M0  machine physics probe (cache latencies)
./bench_m1.exe synth.itch                # M1  zero-copy ITCH parser
./golden_m2.exe synth.itch               # M2  book correctness vs reference
./bench_m2.exe synth.itch                # M2  book replay + matching
./bench_m3.exe synth.itch                # M3  two-thread pipeline + WAL
./walcheck.exe wal ; ./tests/crash_m3.ps1  #    recovery invariants + crash harness
./bench_m4.exe synth.itch                # M4  three-thread LSM pipeline
./recover_m4.exe wal lsm                 # M4  I3 recovery + SSTable integrity
./golden_regex.exe                       # M5  4-way regex automata agreement
./bench_m5.exe synth.itch lsm            # M5  SIMD scan + regex JIT + queries
./bench_m6.exe synth.itch lsm 25000      # M6  crisis: write-stall + interference

Portable C++20 core + a thin platform layer (#ifdef _WIN32) for file mapping, thread pinning, fsync, and W^X JIT memory — Linux paths (mmap, mprotect, pthread_setaffinity_np, fdatasync) are present and compile.

---

Repository layout

trident/
├── src/
│   ├── common/   tsc · hist · cpu · endian · mmap · slab · hashmap
│   │             spsc_ring · crc32c · execmem
│   ├── feed/     itch.hpp                     (zero-copy ITCH 5.0 message views)
│   ├── book/     order · ladder · book        (matching engine)
│   ├── store/    event · capture · wal · memtable-in-lsm · sstable · bloom
│   │             loser_tree · manifest · lsm · flow_control
│   └── query/    regex · nfa · glushkov · dfa · jit_x64 · simd_scan · query
├── bench/        bench_m0 … bench_m6           (one per milestone)
├── tests/        golden_m2 · golden_regex · crash_m3.ps1
├── tools/        mkitch · walcheck · recover_m4
├── docs/         milestone & subsystem write-ups
└── build.ps1 · run_all.ps1

---

Methodology

• Timing. lfence; rdtsc … rdtscp; lfence brackets pin the measured window against out-of-order execution. The invariant TSC is calibrated once against steady_clock (src/common/tsc.hpp). Latencies land in a 2 KB log-linear histogram (≤3% bucket error) — every sample recorded, no sampling, no coordinated-omission fudge.
• Scope of the headline. "Sub-200 ns" is ingest → book-update — from "message bytes in memory" to "book mutated + event pushed" — on a warm, pinned core. It is not wire-to-wire tick-to-trade (that needs kernel bypass and is microseconds). The claim is scoped precisely and measured precisely.
• Synthetic vs real. mkitch generates book-consistent, penny-aligned, mean-reverting flow; the engine is also validated against a real NASDAQ day (12302019, 268.7 M messages). The 50 M msg/s crash burst is a synthetic stress spec — real full-feed peaks are single-digit millions/s.
• Machine. i7-1165G7 @ up to 4.7 GHz (TSC 2.803 GHz), 16 GB, consumer NVMe, Windows 11. Numbers are not comparable across machines; thermal throttling on a laptop moves repeat runs by 10–20%.

Non-goals

No network gateway or NIC kernel-bypass; no risk checks, credit limits, or smart order routing; no multi-venue consolidation; single-day symbol space. ITCH replay builds the book from exchange-side events — matching mode (the engine crossing its own synthetic order flow) is a separate, tested path. The scope is deliberately the three engines and the spine that unifies them.