systems project // C++20
Order Book
One matching engine was the beginning. Now it runs many markets on independent matching threads, takes orders over TCP, writes every command down before it answers, and rebuilds its books from that log after a crash.
v2.0.0 built a matching engine. v2.1.0 built the system around it. v2.2.0 runs it in your browser.
COMPLETE // v2.2.0 // CI GREEN
- SHARDED
- markets spread over matching threads that share nothing
- LOGGED
- every command before its answer; every book rebuilt on restart
- 243
- tests on 16 CI jobs, ThreadSanitizer included
Diagrams here are models. Every number comes from one recorded session, with its conditions beside it.
Watch a buy order sweep the book
A buy order for 200 shares sweeps three resting sell orders across two price levels. Step through each execution.
- 1Best price first
- 2Then first in line
- 3At the resting order's price
- 4Leftover rests at its limit
- STOP Dee $101.28200
- #3 Cam $101.26100
- #2 Ben $101.2530
- #1 Ana $101.2550
- Eli $101.20100
BUY 200 // LIMIT $101.27
FILLED 0 / 200
- #1BUY 50 @ $101.25 from Ana
- #2BUY 30 @ $101.25 from Ben
- #3BUY 100 @ $101.26 from Cam
- STOPDee wants $101.28
- RESTBID 20 @ $101.27 joins the book
Sellers wait above the spread, buyers below. The buy takes the cheapest seller first.
RESULT // locked until the last step
[ SHOW THE CSV AND THE CLI'S OUTPUT ]
order_book_cli replay tests/replay/valid/sweep_and_rest.csv --events --book
sequence,command,order_id,side,price,quantity1,ADD,8001,SELL,10125,50Ana2,ADD,8002,SELL,10125,30Ben3,ADD,8003,SELL,10126,100Cam4,ADD,8004,SELL,10128,200Dee5,ADD,8005,BUY,10120,100Eli6,ADD,8006,BUY,10127,200You
line 2: OrderAccepted id=8001 side=SELL price=10125 qty=50
line 3: OrderAccepted id=8002 side=SELL price=10125 qty=30
line 4: OrderAccepted id=8003 side=SELL price=10126 qty=100
line 5: OrderAccepted id=8004 side=SELL price=10128 qty=200
line 6: OrderAccepted id=8005 side=BUY price=10120 qty=100
line 7: OrderAccepted id=8006 side=BUY price=10127 qty=200
line 7: TradeExecuted incoming=8006 resting=8001 price=10125 qty=50
line 7: TradeExecuted incoming=8006 resting=8002 price=10125 qty=30
line 7: TradeExecuted incoming=8006 resting=8003 price=10126 qty=100
commands processed: 6
add commands: 6
adds accepted: 6
adds rejected: 0
cancel commands: 0
cancels accepted: 0
cancels rejected: 0
replace commands: 0
replaces accepted: 0
replaces rejected: 0
trades executed: 3
volume traded: 180
self-trades prevented: 0
orders expired: 0
stops triggered: 0
resting orders: 3
pending stops: 0
bids:
price=10127 qty=20 orders=1
price=10120 qty=100 orders=1
asks:
price=10128 qty=200 orders=1
last trade price: 10126
Prices are ticks of $0.01. This is the original six-column layout, which v2.2.0 still replays exactly; format v3 adds a symbol column, one file for many markets. CI checks this output byte for byte on every push: input file, replay format.
Your turn: the real engine
The walkthrough above is a recording. This book is the engine itself, compiled to WebAssembly and running in this tab: two shards on their own threads, every order logged before it is answered. Click left of a price to buy there, right to sell there. A reload loses every book.
engine not started
One command's trip through the engine
IN SHORT // Markets are spread over matching threads that share nothing. An order matches as soon as its thread takes it, but its sender hears back only once it is logged.
Pick a market and send an order, or let it play, and watch where it goes.
- SHARD 0
- BRK.B
- NVDA
- SHARD 1
- AAPL
- MSFT
- GOOG
- AMZN
- IBM
- X
Lopsided? The hash places each symbol on its own, so a few can bunch up. It promises no balance; an instrument list can pin any symbol to a shard.
- SEND
- ENTRY CHECK
- HAND-OFF
- MATCH
- LOG
- DURABLE
- ANSWER
- CHECKPOINT
MSFT is placed on shard 1 of 2 by the engine's own hash. Send an order and follow it.
An illustration of the design, not the engine running: placement uses the engine's own hash, FNV-1a over the 8-byte symbol, so these are the shards it would pick. Sources: shards, rings, the log and the hold, checkpoints, wire protocol.
Crash it. It comes back.
IN SHORT // Kill the engine at any moment: it rebuilds its books from the log, and the only commands it can lose are ones it never confirmed. A machine crash needs durability machine for that.
The book from 01, on one shard. Send its orders, then crash it: the model kills the engine's process, not the machine's power.
- ORDERS HIT THE BOOK
- ONE MATCHED, NOT LOGGED
- SOME ARE LOGGED
- CRASH
- RECOVER
Send an order to put it on the book.
RUNNING // nothing sent yet
DEMO // BOOK IN MEMORY
- empty book
COMMAND LOG // 3 RECORDS A FILE
- 1#8001 ADD SELL 50 @ 10125
- 2#8002 ADD SELL 30 @ 10125
- 3#8003 ADD SELL 100 @ 10126
- 4#8004 ADD SELL 200 @ 10128
- 5#8005 ADD BUY 100 @ 10120
- 6#8006 ADD BUY 200 @ 10127
◆ checkpoint 0: the empty book, written at first start
- checkpoint ckpt-DEMO-00000000000000000000.obckpt: the empty book, from the first start
- listening 127.0.0.1:9000
listening 127.0.0.1:9000
- Answered means logged. Matching never waits for the disk, but an answer does, so an engine crash can only lose commands nobody heard back about. So can a machine crash at durability machine, as far as the drive honours its flushes. At durability process, a machine crash can lose answered ones too.
- Checkpoints come from the log. When a log file closes, a worker rolls each book forward from its last checkpoint and proves the result restores. Matching never pauses for one.
- A clean stop proves it. The log is rolled to its end and compared with the live book byte for byte before the last checkpoint is published.
[ SHOW A REAL CRASH AND RESTART ]
The engine is killed mid-run. verify reads what it left, and the next start replays the log: replayed=4 on shard 1 is MSFT and AAPL's four commands. Captured from a Release build of v2.1.0 on Windows 11; the engine's CRLF shown as LF.
engine-demo$ order_book_engine --instruments list.csv --shards 2 --listen 127.0.0.1:9000 --log-dir logs --stop-on-stdin-close
order_book_engine: --instruments list.csv --shards 2 --listen 127.0.0.1:9000 --command-ring 4096 --response-ring 16384 --spin-window 100us --capacity-orders 4096 --capacity-stops 1024 --capacity-levels 256 --max-connections 64 --gateway-threads 1 --high-water-mark 1M --hard-limit 16M --stop-grace 5s --log-dir logs --durability machine --log-file-size 256M --log-ring 65536 --roll-workers 1 --thread-priority normal --stop-on-stdin-close
order_book_engine: shard 0: recovered books=1 replayed=0 tail-cut-bytes=0 from=0 fell-back=0
order_book_engine: shard 1: recovered books=2 replayed=0 tail-cut-bytes=0 from=0 fell-back=0
listening 127.0.0.1:9000
engine-demo$ order_book_cli send v3_two_instruments.csv --connect 127.0.0.1:9000
symbol AAPL
line 3: OrderAccepted id=1 side=BUY price=99 qty=4
line 5: OrderCancelled id=1 qty=4
symbol BRK.B
line 6: OrderAccepted id=3 side=BUY price=98 qty=1
symbol MSFT
line 2: OrderAccepted id=1 side=SELL price=101 qty=5
line 4: OrderAccepted id=2 side=BUY price=101 qty=2
line 4: TradeExecuted incoming=2 resting=1 price=101 qty=2
symbol ZZZ
line 7: Refused symbol=ZZZ id=9 code=UNKNOWN_INSTRUMENT
exit 4
[ the engine's process is terminated: no clean stop, no stop report ]
engine-demo$ order_book_cli verify --log-dir logs
shard 0: start=0 end=1 files=2 tail-cut-bytes=0 files-dropped=1
book BRK.B shard=0 checkpoint=0
shard 1: start=0 end=4 files=2 tail-cut-bytes=0 files-dropped=1
book AAPL shard=1 checkpoint=0
book MSFT shard=1 checkpoint=0
ok
exit 0
engine-demo$ order_book_engine --instruments list.csv --shards 2 --listen 127.0.0.1:9000 --log-dir logs --stop-on-stdin-close
order_book_engine: --instruments list.csv --shards 2 --listen 127.0.0.1:9000 --command-ring 4096 --response-ring 16384 --spin-window 100us --capacity-orders 4096 --capacity-stops 1024 --capacity-levels 256 --max-connections 64 --gateway-threads 1 --high-water-mark 1M --hard-limit 16M --stop-grace 5s --log-dir logs --durability machine --log-file-size 256M --log-ring 65536 --roll-workers 1 --thread-priority normal --stop-on-stdin-close
order_book_engine: shard 0: recovered books=1 replayed=1 tail-cut-bytes=0 from=0 fell-back=0
order_book_engine: shard 1: recovered books=2 replayed=4 tail-cut-bytes=0 from=0 fell-back=0
listening 127.0.0.1:9000
Limits: durability machine is only as good as the drive's flush. Recovery is tested against a model of a drive, and by killing real engines, but nobody has pulled the plug on a real machine.
Simplified: one record reaches the log at a time, and a log file holds three (the default is 256 MiB). Running it for real, and what to do when a start refuses: operator guide, verify and cut-log, log format, checkpoint format.
Sorted arrays, FIFO queues, and an index straight into them
IN SHORT // Each book is laid out so a cancel jumps straight to its order, and a book reserved up front matches without touching the heap.
- O(1) cancel
An index entry points at the order's queue node and its level, so a cancel never searches the book, and never allocates.
- No heap on the matching path
A node pool, an open-addressed index, reused results, and books reserved up front: a test checks the matching path makes no heap call.
- The array's catch, written down
A price near the best is found by galloping from the end, where it stays in the last cache line. A new level far behind every other shifts the whole array.
Checked by machines, not by eye
IN SHORT // Every push runs CI on 16 jobs: 243 tests check it against a second model, crash its log at every step on a modelled drive, and run its threads under ThreadSanitizer.
Matching bugs rarely crash; they surface later as a wrong trade. Recovery bugs wait for the crash.
- Whole-book invariants
After every command, Debug builds check each level, order, cached total, and index entry, and abort on the first violation.
- Independent reference model
Seeded random submissions, cancels, and replaces of every order type run through the engine and a separate model, compared after every command.
- Injected allocation failures
Each allocation is made to fail in turn, and the book must stay consistent.
- Crashes at every step
Logging, file rotation, and start-up are crashed at every step on a modelled drive that tears writes, then recovered and held to an uninterrupted run. Real engines get killed too.
- Byte-exact output
The CLI must match its expected files byte for byte, and a file sent to a live engine must print exactly what replaying it in process prints.
- Threads under a microscope
Every test that runs real threads also runs under ThreadSanitizer and on an Arm runner.
| Debug | Release | Sanitized Debug | Sanitized optimized | ThreadSanitizer | |
|---|---|---|---|---|---|
| GCC | PASS | PASS | PASS | — | THREADED |
| Clang | PASS | PASS | PASS | PASS | THREADED |
| MSVC | PASS | PASS | PASS | PASS | — |
| Clang Arm64 | — | THREADED | — | — | — |
| Emscripten | — | PASS | PASS | — | — |
What the system around the book costs
IN SHORT // Up to the six cores measured, more shards gave more throughput; logging every command at durability process kept about three-quarters of it. Pick a figure to open its chart.
AMD Ryzen 5 5600G, 6 cores with SMT, one NVMe drive, Windows 11 Pro, High performance plan; one recorded session. Each chart has its intervals and conditions.
SCALING // THROUGHPUT AT N SHARDS ÷ 1 SHARD
- measured
- perfect N×
Each shard is its own matching thread with 8 instruments, no log, 1M commands; threads pinned one per physical core, so nothing here says what a seventh core would do. Shards share nothing but the machine: cache, memory, heat.
LAYER BY LAYER // EACH ONE AGAINST THE ONE INSIDE IT
One shard. The centre line is 1.0, the same throughput as the layer inside; left costs, right gains. Every step is its own paired run, so they are never multiplied into a total.
THE PRICE OF REMEMBERING
- 0.764×
- throughput with the command log on, at durability process, against no log (95% CI 0.742–0.772)
- 1.060×
- durability machine, written through to the drive, against process (95% CI 0.953–1.086)
The queue kind, one shard, one producer. Write-through barely moves throughput because matching never waits for the disk: the drive slows the log writer, and answers. One cell shows the drive in charge: quote-refresh at machine, on log files extended as the engine makes them, read 1.25M, 0.63M, and 4.58M commands/s in its three sessions.
FOUR CLOCKS // WHAT EACH NUMBER TIMES
- FROM
- Before one book call
- TO
- After it returns
- CLOSED LOOP
- p50 140 ns · p99 751 ns · p99.9 1.43 µs over 9,000,000 samples
- CONDITIONS
- one book in process, its thread on logical processor 6; 1M commands a run; the book reserved to its peak, so it never grew; matching-heavy-request; 9 runs merged; clock rdtscp;lfence.
One command at a time on one quiet desktop: not a claim about load, other machines, or a network. Loopback is not a network. The intervals nest, but one is never subtracted from another, and throughput's ns per command is not any of them.
[ HOW THIS WAS MEASURED, AND WHAT IT DOESN'T SAY ]
- One unattended session on 2026-11-06: commit 2affa3b, MSVC 19.44 Release, on an AMD Ryzen 5 5600G, 6 cores with SMT, one NVMe drive, Windows 11 Pro, High performance plan.
- Throughput cells are the median of three sessions of 5 runs. Ratios are 16 ABBA pairs with a bootstrap 95% interval; the same binary against itself varies by ±0.4% to ±1.9%, depending on the layer.
- Synthetic, uniform workloads. Gateway and engine clients use loopback on the same machine and take cores the engine could otherwise use.
- No scaling claim past the 6 physical cores, and no Linux numbers: Linux is built and tested in CI only.
- Latency follows the repository's claims rule: each figure with its interval, conditions, and run record, never as a headline, and never compared with any other system.
- The book alone is within 3% of v2.0.0 on ten of eleven workloads. quote-refresh reads 0.963, an accepted and explained exception (#107).
- Still open: the shard layer reads 17–22% below the bare book on its two cheapest workloads (#101), and a roll worker on the matching thread's sibling core nearly halved throughput (#108).
Full write-ups: benchmarks, latency and the claims rule, raw results, worst cases.
[ HISTORY // v1.0.0: THE BOTTLENECK WAS THE HEAP ]
Profiling put 34–47% of v1.0.0's engine time into allocating and freeing memory. Taking allocation off the hot path cut that to 0–5%, and every workload got faster.
NANOSECONDS PER COMMAND // BEFORE → AFTER
- Before
- After
- label = throughput gain
- small-book1.76×
- deep-book1.85×
- matching-heavy1.44×
- cancellation-heavy2.23×
- mostly-resting1.83×
- +13–19% Inline result storage
- +11–29% Per-book node pool
- +5–62% Open-addressed order index
- v1.0.0's code against its own baseline, both builds interleaved in one session: 16 ABBA pairs per workload, median ratio with a bootstrap 95% interval. Only the ratios are claimed.
- One desktop (Ryzen 5 5600G, MSVC Release), five synthetic single-instrument workloads of 100,000 commands; throughput, not latency.
- Part of mostly-resting's gain comes from the harness pre-sizing the index, not from the engine.
Run the CLI, live or recorded
The terminal is the engine itself, running in this tab: type help, send a sample, crash it and start it again. It keeps its log in the tab, so a reload loses every book. Below it, five real runs of the CLI, byte for byte as CI checks them, and one of the engine itself: start, send, stop, verify.
order_book_engine, built for the browser: two shards on Web Workers, a gateway on an in-page connection.
type help, or try: send valid/v3_two_instruments.csv
order-book/tests/replay$ order_book_cli replay valid/price_time_priority.csv --trades --book line 6: TradeExecuted incoming=2005 resting=2001 price=101 qty=10 line 6: TradeExecuted incoming=2005 resting=2002 price=101 qty=15 line 6: TradeExecuted incoming=2005 resting=2003 price=102 qty=20 line 7: TradeExecuted incoming=2006 resting=2005 price=102 qty=5 line 7: TradeExecuted incoming=2006 resting=2004 price=99 qty=3 commands processed: 6 add commands: 6 adds accepted: 6 adds rejected: 0 cancel commands: 0 cancels accepted: 0 cancels rejected: 0 replace commands: 0 replaces accepted: 0 replaces rejected: 0 trades executed: 5 volume traded: 53 self-trades prevented: 0 orders expired: 0 stops triggered: 0 resting orders: 1 pending stops: 0 bids: price=99 qty=2 orders=1 asks: none last trade price: 99 exit 0
PRICE-TIME PRIORITY A buy sweeps two price levels and rests its last 5; a sell then takes them at 102, not at its own 99.
INPUT // valid/price_time_priority.csv
sequence,command,order_id,side,price,quantity
1,ADD,2001,SELL,101,10
2,ADD,2002,SELL,101,15
3,ADD,2003,SELL,102,20
4,ADD,2004,BUY,99,5
5,ADD,2005,BUY,102,50
6,ADD,2006,SELL,99,8
- v2.2.0
- Many instruments on a fixed number of shards, each a matching thread with its own books, log, and checkpoints, behind TCP gateway threads. Limit, market, IOC, FOK, post-only, stop, and stop-limit orders, self-trade prevention, and cancel-replace. All of it also runs in a browser tab, compiled to WebAssembly.
- LIMITS
- One machine and one process, no replication. Placement is fixed at start: moving an instrument takes a clean stop and a restart. A connection is the only identity: no authentication or encryption, no fills reported to the resting side, no cancel on disconnect. No market-data feed. Sockets are poll only, at most 64 connections a gateway thread. In the browser, a reload loses every book.