A running record of every architectural and technical decision made for this project, with reasoning. Useful for future-me, anyone reviewing the project, and reinforcing my own understanding.
A from-scratch limit order book / matching engine in C++ — the core machinery of a stock exchange (NASDAQ, NYSE), rebuilt small and honest. Orders in, matching by real exchange rules (price-time priority), fills out. Not connected to real markets; the point is the engineering:
- Cache-conscious data structures measured in nanoseconds
- A binary wire protocol + POSIX TCP server (how real venues take orders)
- Honest latency benchmarking (cycle counters, percentiles, realistic workloads)
Dual purpose:
- Interview artifact — quant/trading firms ask exactly these design questions ("array vs tree for a book?", "how is cancel O(1)?"). Having built one turns quizzes into home turf.
- QuantOS foundation — this book/matcher core later gets adapted into QuantOS's Execution Simulator (the thing that makes backtests use real fill mechanics instead of "assume filled at close"). LiquidBook completes first as its own project.
Original planning bullets (had [X]/[Y] metric placeholders):
- Architected a price-time priority limit order book in C++ with flat-array price levels chosen over pointer-based trees, keeping the hot matching path cache-resident and minimizing cache misses during high-frequency order matching and cancellation. → M1
- Implemented a binary order protocol for low-overhead, allocation-free message parsing and a POSIX TCP server routing order flow across concurrent sessions, handling connection lifecycle and partial reads without blocking the matching thread. → M2 + M3
- Instrumented end-to-end and per-operation latency profiling via rdtsc CPU cycle counters across the matching hot path, using an order-flow benchmark stressing insertions, cancellations, and crossing fills to isolate throughput bottlenecks and tail latency. → M4
- Architected a price-time priority limit order book in C++ with flat-array price levels over pointer-based trees, keeping the hot matching path cache-resident and sustaining 60M+ matching operations/sec across high-frequency insertion and cancellation.
- Implemented an allocation-free binary protocol and POSIX TCP server routing orders across concurrent sessions, sustaining 1.5M+ orders/sec over TCP while handling connection lifecycle and partial reads without blocking the matching thread.
- Instrumented end-to-end and per-operation latency profiling via CPU cycle counters across matching hot path, measuring ~16 ns per op in-process and ~30 µs p50 round-trip under order-flow benchmark stressing insertions, cancellations, and crossing fills.
Metric-placement logic: engine throughput (60M/s) in bullet 1, TCP throughput (1.5M/s) in bullet 2, latency (16ns in-proc + 30µs e2e p50) in bullet 3 — each number in its right bullet, no repeats.
Two honesty edits vs the original: (a) rdtsc → "CPU cycle counters" because this Mac is ARM (uses cntvct_el0); rdtsc is x86-only, so writing it while running on ARM is false. (b) Dropped a standalone in-process "p50 in ns" — Apple's counter granularity (~42ns steps) makes engine p50 read 0, so it's not honestly citable; the real p50 cited (~30µs) is the end-to-end path. To legitimately use "rdtsc" + a true in-process p50/p99 in ns, run benchmark_engine.cpp on an x86 Linux box.
Every phrase in these bullets is decoded in the Jargon Glossary at the bottom of this file.
Why: the domain language. Low-latency trading systems are C++; the firms this project targets interview in it. C++20 specifically for <bit> (std::countr_zero / std::countl_zero — hardware bit-scan instructions behind portable functions, used for best-price lookup).
The book is templates-and-inline-friendly and small. No .cpp compile units for the library itself means the simplest possible build. Split into compiled units later only if compile times hurt.
Tests are plain assert-style checks with a tiny CHECK macro — no GTest/Catch2. Why: nothing to install, nothing to fetch, the whole project builds with a compiler alone. Dependencies get added when they clearly earn it (same discipline as the bazaar tracker's "defer dependencies" pattern). Google Benchmark is the one planned exception (M4) — statistical benchmarking rigor is genuinely hard to hand-roll.
What it is: a recipe file for building. The compiler (clang++) is the oven; CMake is the written recipe. cmake -S . -B build reads the recipe and generates a build plan; cmake --build build compiles everything in it.
What it buys:
- One place for flags (C++ version, warnings) instead of retyping per command
- Multiple targets later (M3+:
lb_tests,lb_server,lb_bench) built by one command - Only rebuilds what changed
- Industry standard — IDEs read it natively, interviewers assume fluency
Honest note: overkill for one test binary today. Kept because M3/M4 need it and it costs ~20 lines now. Raw equivalent, works fine meanwhile:
clang++ -std=c++20 -O2 -Wall -Wextra -Iinclude tests/test_book.cpp -o lb_testsliquidbook/
├── CMakeLists.txt # build recipe
├── notes.md # this file
├── include/liquidbook/ # THE LIBRARY — public headers
│ ├── types.hpp # vocabulary: Price, Qty, OrderId, Side, Event
│ ├── pool.hpp # order memory: preallocated slots, free list, generations
│ └── book.hpp # price ladder + levels + matcher (the core)
├── tests/
│ └── test_book.cpp # assert tests, zero dependencies
├── src/ # M2 protocol, M3 server land here — empty now
├── benchmarks/ # M4 harness — empty now
└── docs/ # design notes if needed later
Why include/liquidbook/ double-nesting: consumers write #include "liquidbook/book.hpp" — namespaced include paths, standard C++ library layout. CMake's target_include_directories(... include) makes the path resolve.
Growth rule: structure grows when files demand it, not before. This layout carries through M4 without moving anything.
A single reference for the whole codebase: what each file is, its key pieces, and how control flows through them. Read top-to-bottom = the same order data actually moves.
Just shared type names + enums, no behavior. Everything else builds on these.
| Name | Is | Notes |
|---|---|---|
Price = int64_t |
a tick | signed (allows negative/relative prices) |
Qty = uint64_t |
a lot count | unsigned |
OrderId = uint64_t |
a handle | generation << 32 | pool slot index; 0 = invalid |
NIL = UINT32_MAX |
"no index" | list terminator + "empty" marker |
Side |
Buy / Sell | |
OrdType |
Limit / Market / IOC | |
RejectReason |
None/BadQty/BadPrice/PoolFull | why a submit bounced |
EventType |
Ack/Reject/Fill/Canceled/CancelOk/TooLate | the facts the book emits |
Event |
one fact | fields mean different things per type (see the USAGE block in the file) |
BookConfig |
book settings | price band + pool size |
Order struct + OrderPool class. Pre-allocated slots handed out and reclaimed; zero runtime allocation.
Mental model: a stack of pre-made slots. acquire() pops the top free slot; release() pushes it back. next field does double duty — links orders inside a price level when in use, links the free chain when free.
| Function | Does | Cost |
|---|---|---|
acquire() |
pop a free slot, wipe it, return its index | O(1) |
release(idx) |
bump generation (kills stale ids), push slot back on free list | O(1) |
id_of(idx) |
build the public OrderId = gen<<32 | idx |
O(1) |
resolve(id) |
id → slot index, or NIL if generation mismatches (stale/reused) |
O(1) |
full() / used() |
free list empty? / live-order count | O(1) |
The generation counter is the whole safety story: a late cancel for a slot that's been recycled fails resolve (gen won't match) → harmless, instead of clobbering a stranger's order.
Level struct + OrderBook class. This is the heart.
Data layout:
bids_/asks_— flat arrays, oneLevelper price tick, indexed byprice - min_price. One subtraction + one read to reach any level (no tree, no pointer-chasing).bid_bits_/ask_bits_— occupancy bitmaps, 1 bit per level (set = non-empty). Finding the next best price =countr_zero/countl_zero= one CPU instruction over 64 levels at a time (~64× faster than scanning).best_bid_/best_ask_— cached ladder index of the best price (-1= side empty).- each
Level= FIFO queue (head=oldest fills first = time priority,tail,count,total).
Public API — the flow of submit() (the main path):
submit(side, type, price, qty, out):
1. validate -> qty==0? BadQty | out-of-band price? BadPrice | pool full? PoolFull (push Reject, return 0)
2. acquire -> grab a pool slot, fill in the order fields
3. Ack -> push Ack event with the new OrderId
4. match() -> cross against the opposite side (fills pushed)
5. resolve remainder:
open == 0 -> release slot (fully filled, never rested)
Limit + leftover -> rest() (join the book)
Market/IOC left -> push Canceled, release (these never rest)
6. return OrderId
Order matters: Ack before match before rest — this preserves time priority (the order is acknowledged, tries to trade, only then rests behind whatever was already there).
cancel(id, out) flow:
resolve(id) -> NIL or not resting? push TooLate, done (stale/filled/foreign)
else: subtract from level.total, unlink() from the FIFO,
on_level_empty() if it emptied, push CancelOk, release()
resolve is the guard: a filled order's slot was already released + generation-bumped, so its old id resolves to NIL → TooLate.
Private helpers (the machinery the two public calls lean on):
| Helper | Job |
|---|---|
idx_of(price) / price_of(i) |
price ↔ ladder index |
set_bit / clear_bit |
flip a level's occupancy bit |
find_next / find_prev |
scan bitmap for next non-empty level via countr_zero/countl_zero |
on_level_empty |
clear the bit + recompute cached best bid/ask when a level hits 0 |
unlink |
splice one order out of its level's doubly-linked FIFO — O(1), no search |
rest |
append a leftover limit order to its level's tail, set bit, push best outward |
match |
the matching walk (below) |
check_invariants |
test-only full-book consistency scan (O(everything), never on hot path) |
match() — the matching walk (the core loop):
while taker still has open qty:
best = best opposite level; if none -> stop
crossable? (market, or price good enough) if NOT -> stop <-- the inverted-bug line, see fix above
walk that level head-first (time priority):
fill = min(taker.open, maker.open) at the MAKER's price
push Fill event
maker fully eaten -> unlink + release, advance to next maker
level emptied -> on_level_empty()
Outer loop = price levels, best first (price priority). Inner loop = orders within a level, oldest first (time priority). Fills always execute at the resting maker's price (price improvement goes to the aggressor).
Turns messages into fixed byte layouts and back. All little-endian, zero allocation. (See the M2 section above for the full byte math.) Direction split:
- inbound (client→server, commands):
WireNew,WireCancel—encode_*on client,decode_*on server. - outbound (server→client, events): the
Event—encode_eventon server,decode_eventon client. inbound_msg_size(type)— framing key: type byte → total length (New=19, Cancel=9). Outbound is one fixed size (kEventSize=42), so no table needed.
Two threads (see "How the M3 Server Works" section for the deep version):
- network thread (main):
poll()event loop, owns all sockets, does reads/writes, frames inbound bytes, flushes outbound. - matching thread: owns the single
OrderBook, pops commands, runs them, encodes events, pokes the network thread via the self-pipe. - Handoff = two mutex-guarded queues (
g_in_q,g_out_q) + a condition variable + the self-pipe. Book itself is lock-free (one owner thread).
Dumb prover: dials the server, sends a couple orders (encode_new), reads events back (decode_event, fixed 42-byte strides), prints them. Stands in for real trader software.
CLIENT SERVER (net thread) SERVER (match thread)
WireNew ──encode_new──► bytes
bytes ──TCP write───────────► read() into inbuf
frame via inbound_msg_size
decode_new ──► g_in_q ──────► pop, book.submit()
events -> encode_event -> g_out_q
poke self-pipe
poll wakes, move bytes ◄──────┘
read() ◄──TCP──── write() ◄── to session outbuf
decode_event ──► print
Same submit() runs whether driven by a test (M1) or the network (M3) — the book never knows the difference. That's the payoff of keeping the core free of I/O.
Price = int64_t (ticks), Qty = uint64_t (lots). Why: floats lose precision in surprising ways (0.1 + 0.2 != 0.3); for money that's not a quirk, it's corruption. Real exchanges work in integer ticks too. Any float↔tick conversion happens outside the book, once, at the edges.
Levels live in a plain contiguous array indexed by price - min_price. Price 105 → slot 104 (with min 1). Finding a level = one subtraction + one memory read.
The rejected alternative: std::map<Price, Level> (red-black tree). Textbook, unbounded price range — and slow: every lookup walks tree nodes, each node a separately-allocated chunk somewhere in RAM, ~one cache miss per hop.
Why cache is the whole argument: CPU keeps recently-used memory in tiny fast cache (L1 ≈ 1ns/read) vs main RAM (≈ 100ns — 100x slower). A cache miss = CPU stalls waiting on RAM. At a ~1µs total operation budget, each miss burns ~10% of the budget. Contiguous arrays that get touched repeatedly stay cache-resident; pointer-chasing trees don't. This is the entire "flat-array over pointer-based trees" resume claim.
Cost accepted: fixed price band (config min_price..max_price); orders outside it are rejected. Fine for a simulator; the QuantOS adaptation adds an overflow map + band re-anchoring for correctness at any price (deferred — see Open Decisions).
All order memory allocated once at startup (pool_capacity slots). Adding an order = pop a free slot off a free list. Removing = push it back. Why: heap allocation (new/malloc) is slow and unpredictable — occasional huge pauses that destroy tail latency. Banning it from per-order work keeps latency flat. The free list is LIFO deliberately: a just-freed slot is still cache-warm for the next add.
OrderId = generation << 32 | slot_index. Each slot carries a generation counter, bumped every time the slot is recycled.
The bug this kills: order A dies, its slot gets reused by order B, then a late cancel for A arrives. Without generations, that cancel would delete B — a stranger's order. With them, A's stale id fails the generation check and resolves to "TooLate" harmlessly. This is the use-after-free bug class, killed structurally. Test test_stale_handle_generation proves it.
Each price level = doubly-linked queue of orders, links (prev/next as pool indices, not pointers) stored inside the Order struct itself. Why FIFO: first-in-first-out = time priority by construction — the oldest order at a price fills first because it's at the head. Why intrusive: zero extra allocation, order and its links share a cache line. Why doubly-linked: cancel = unlink in O(1) — no searching. Real order flow is dominated by cancels (market makers constantly re-quoting), so cancel speed matters as much as add speed.
One bit per price level, set = level non-empty. Best bid/ask are cached; when a level empties, finding the next best price = scan the bitmap with std::countr_zero/countl_zero — a single hardware instruction finds the next set bit in a 64-bit word. Alternative (walk the array slot by slot) is fine on average, terrible when the book is sparse.
Every operation emits events in fixed order: Ack (or Reject) exactly once, first → zero or more Fills in match order → terminal Canceled if a Market/IOC remainder dies. Cancels answer CancelOk or TooLate. Why fixed order matters: consumers (tests now, network clients in M3, QuantOS later) rely on it; ambiguity in event ordering is where downstream state machines rot.
- Price priority: aggressor always matches the best-priced opposite level first.
- Time priority: within a level, FIFO.
- Fills execute at the resting order's price (price improvement goes to the aggressor). This is how real continuous markets clear; anything else fabricates fake price-improvement stats.
- Market/IOC remainders never rest — canceled with a terminal event.
- Cancel-vs-fill races: fills win. A fill that already happened is a fact; cancel gets the remainder or
TooLate, never an un-fill. - No modify/replace — cancel + new order (new order = new time priority). Priority-retaining modify is venue-specific rule soup; deliberately out of scope.
- Level
total= sum of open qty of its linked orders;countmatches chain length. - FIFO order within a level = insertion order.
- Bitmap bit set ⟺ level non-empty, exactly.
- Cached best bid/ask always point at true best non-empty levels.
- No stale handle ever succeeds; no slot double-free.
- Conservation: every lot submitted = filled + resting + canceled.
check_invariants() walks the whole book and verifies 1–4; tests call it after every scenario. It's O(everything) and never runs on the hot path — it's a correctness oracle, not production code.
Why: three reasons, all about the hot path and flexibility.
- Caller reuses one buffer → no per-call allocation. Returning
std::vector<Event>would allocate a fresh vector every operation. Millions of ops = millions of allocations = the exact tail-latency spikes we ban. With an out-param, the caller keeps one vector and.clear()s it (clear keeps capacity — no realloc after warmup). Allocation-free hot path, same discipline as the order pool. - One operation naturally emits many events. A single aggressive order can produce Ack + N Fills + Canceled. An output vector expresses "append however many happened" cleanly; a single return value can't.
- Batching-friendly. Caller can pass the same vector across several
submitcalls, accumulate all events, then flush once (M3's matching thread does exactly this — collect, encode, send). No forced flush per op.
Return value is just the OrderId (a scalar — free to return), or 0 on reject.
The book could have taken a callback (on_fill(...)). It doesn't — it fills a data vector. Why:
- Testable: tests inspect the returned events as a list. No callback plumbing.
- Decoupled: the book knows nothing about who consumes events — tests, a TCP socket, or (later) QuantOS's Python layer. Same core, any consumer.
- No reentrancy hazards: a callback could call back into the book mid-operation. Data-out can't.
- Matches the future QuantOS pull model (
step()returns a batch of events, e4 spec). Building it this way now means zero rework later.
book.hpp includes only pool.hpp. No sockets, no files, no threads. Why: the book is a pure function of (current state, operation) → (new state, events). Purity buys determinism (same ops → same result, critical for the QuantOS adaptation), trivial testing, and free reuse behind any shell (TCP now, pybind11 later). All the messy IO lives in the M3 server layer, bolted on the outside. This is the hexagonal-boundary idea in miniature: core stays clean, adapters wrap it.
The book has no locks. Thread-safety comes from ownership, not mutexes: exactly one thread (the matching thread) ever touches the book. Network threads hand it work through a queue and read results from another queue. Why: a lock around the book would put mutex contention on the hottest code in the system, and real matching engines are single-threaded on the match path for exactly this reason (also gives determinism). Locks live only on the small queues between threads, never on the book itself.
M3 tags each client with a uint64_t sid from an ever-increasing counter, not its socket fd. Why: file descriptors get reused — client A on fd 7 disconnects, client B connects and the OS hands out fd 7 again. If the matching thread had queued output tagged "fd 7" for A, it would wrongly land on B. A monotonic sid is never reused, so stale output for a dead session simply finds no matching sid and gets dropped. (Same spirit as the pool's generation counters — monotonic tags defeat reuse hazards.)
Every inbound message starts with a type byte; inbound_msg_size(type) maps it to that message's total length. Why: TCP is a boundary-less byte stream — the server must know where one message ends and the next begins. Type-then-fixed-size means: read 1 byte, look up the length, wait until that many bytes have arrived, slice one message off, repeat. Unknown type → size 0 → drop the connection (garbage or malicious client). Simpler than length-prefixing and sufficient because every message type here has a fixed size.
Sockets are set non-blocking; the network thread waits in poll(). Why non-blocking: a blocking read/write on a slow client would freeze the network thread (and everyone else on it). Non-blocking calls return immediately with EAGAIN instead of sleeping. Why the self-pipe: the matching thread produces output on its own schedule; it writes one byte to a pipe the network thread is polling, waking poll() instantly so results flush without a latency-adding timeout. Classic POSIX pattern for "wake a poll loop from another thread" (macOS has no eventfd).
commands (InMsg)
network ───────────────► matching
thread ◄─────────────── thread
events (OutMsg)
- network thread (main): owns the listen socket + every client socket, runs the
poll()loop, does all reads/writes. - matching thread: owns the single
OrderBook, runs one op at a time.
Why split: if one thread did both, a slow client's socket read would stall matching for everyone. Separated → matching never waits on network, network never waits on matching. Each runs at its own pace.
Lives in a poll() loop (poll = "sleep until any of these sockets has activity"). Watches the listen socket, the wake-pipe, and every client socket. Each wake it does 4 things:
- Accept new clients on the listen socket → make a
Session, assign asid. - Drain the wake-pipe (bytes are meaningless — it exists only to break
poll()). - Per client: read available bytes → frame into whole messages → push to inbound queue; and write any pending output bytes when the socket is writable.
- Reap sessions that disconnected or errored.
All sockets are non-blocking — read/write return immediately with EAGAIN instead of sleeping. One thread juggles many clients without ever getting stuck on a slow one.
sleep until inbound queue has work
pop one command → run on book (submit/cancel) → encode events to bytes
push bytes to outbound queue → poke network thread → repeat
Only this thread ever touches the book, so the book has no locks — it can't race with itself. Thread-safety by ownership, not mutexes. This matters because a lock around the book would put contention on the hottest code in the system; real matching engines are single-threaded on the match path for exactly this reason (also buys determinism, which the QuantOS adaptation needs).
- inbound queue: network pushes commands, matching pops.
- outbound queue: matching pushes event-bytes, network pops.
Both mutex-guarded (two threads touch them). Everything else lives inside a single thread → no locks. The mutex is only on the small handoff, never on the book.
Inbound uses a condition variable — the matching thread sleeps until work arrives instead of busy-spinning (which would peg a CPU core doing nothing). Network thread signals it after every push.
Problem: the network thread is asleep in poll(); the matching thread just produced output — how to wake the sleeper? Answer: a pipe. Matching writes 1 byte → the network thread's poll() sees the pipe readable → wakes → flushes output immediately. No timeout, no added latency. (macOS has no eventfd, so a plain pipe is the wakeup channel.)
TCP is a boundary-less byte stream. Each session keeps an inbuf; on read, append bytes then slice:
peek type byte → inbound_msg_size() → total length
have that many bytes? → decode one message, step forward, repeat
NOT enough bytes? → partial: leave it, wait for the next read
unknown type byte (0)? → junk client, drop the connection
Leftover partial bytes stay in inbuf until the rest arrives. That's what "handling partial reads without blocking the matching thread" means in the resume bullet.
Clients are tracked by a monotonic sid (1, 2, 3…), not the socket fd. File descriptors get reused — a dead client's fd 7 gets handed to the next connection. Output the matching thread tagged "fd 7" for the dead client would land on the new one. A monotonic sid never repeats, so stale output finds no session and is safely dropped. (Same idea as the pool's generation counters — monotonic tags defeat reuse hazards.)
client writes New bytes
→ network reads, frames, pushes InMsg, notifies condvar
→ matching pops, book.submit(), gets Ack+Fill, encodes, pushes OutMsg, pokes pipe
→ network wakes, moves bytes into the session's outbuf, poll() says writable, writes to socket
→ client reads, decodes, prints
- Submitter-only event routing: events go back only to the session that sent the command. A resting order's owner isn't notified when someone else's order fills it (no
order_id → sessionownership map yet). Real exchanges notify both sides; deferred — noted in Open Decisions. - pollfd list rebuilt every loop iteration: fine at small connection counts; a persistent fd set (or
kqueue/epoll) is the scale-up path, not needed here. poll()overkqueue/epoll:pollis POSIX-portable (works mac + linux) and simple; the OS-specific readiness APIs are faster at thousands of connections but overkill for this project.
Everything needed to understand server.cpp/client.cpp — the C++ threading primitives, the POSIX syscalls, and TCP itself.
::pipe, ::read, ::close — the leading :: means "global namespace." It forces the plain C operating-system function, not some same-named thing in the current namespace/class. ::read(fd,...) = unambiguously "the OS's read."
Some functions are system calls — they ask the OS kernel to do something only it can (sockets, files, processes, hardware): socket, bind, read, write, poll, pipe, close. They cross from your program into the kernel. Regular library calls (std::vector::push_back) run entirely in your program. Syscalls are the ones that touch the outside world.
MUTual EXclusion — a lock. Only one thread holds it at a time. Solves the data race: two threads touching the same data simultaneously (e.g. both pushing to one queue) scramble its internals → corruption/crash.
m.lock(); // if another thread holds it, WAIT until free
// ... touch shared data safely ...
m.unlock(); // releaseIn the code you don't see raw lock/unlock — you see std::lock_guard<std::mutex> lk(mtx); which auto-locks on creation and auto-unlocks at end of {} scope (can't forget to unlock). std::unique_lock is the same but can unlock early and works with condition variables.
Lets a thread sleep until something becomes true, without busy-waiting.
while (queue.empty()) { } // BAD: spins, pegs a CPU core
cv.wait(lk, []{ return !queue.empty() || stop; }); // GOOD: sleeps, 0 CPUThe thread sleeps (releasing the lock while asleep); another thread's cv.notify_one() wakes it to re-check. The []{ return ... } is a lambda (inline anonymous function) — here the condition to test. Matching thread waits on g_in_cv until inbound has work; network thread notifies after pushing.
A variable safe to read/write across threads without a mutex, for simple types. g_stop — network thread .store(true), matching thread .load(). Atomic ops are indivisible (never caught half-done), so no lock needed.
::pipe(fds) — a syscall making a one-way in-memory tube with two fds: fds[0] = read end, fds[1] = write end. Bytes written to fds[1] come out fds[0].
Used here to wake a sleeping thread. The network thread sleeps in poll(); the matching thread needs to wake it. So poll() also watches the pipe's read end. Matching thread writes 1 byte → read end becomes readable → poll() wakes → network thread flushes output. The byte's value is meaningless; its arrival is the signal. (macOS has no eventfd, so a plain pipe is the wakeup channel.)
The setup (in main):
int wake[2]; // will hold 2 fds
if (::pipe(wake) < 0) { ... } // OS fills them: wake[0]=read, wake[1]=write
set_nonblocking(wake[0]); // draining read never blocks
set_nonblocking(wake[1]); // poke write never blocks (full pipe → EAGAIN, fine)
g_wake_w = wake[1]; // stash WRITE end in a global so the matching
// thread (separate function) can reach itOnly the write end goes global (matching thread only writes); the read end stays local to main (only the network thread reads). The poke: ::write(g_wake_w, &one, 1). Multiple pokes before one wake is fine — the network thread drains the read end in a loop, so N doorbell-presses collapse into one trip to the door.
The server-socket lifecycle, in order:
| Call | What it does |
|---|---|
::socket(AF_INET, SOCK_STREAM, 0) |
Make a socket, return an fd. AF_INET=IPv4, SOCK_STREAM=TCP (vs SOCK_DGRAM=UDP), 0=default proto. |
::setsockopt(lfd, SOL_SOCKET, SO_REUSEADDR, ...) |
SO_REUSEADDR = rebind the port immediately after restart instead of waiting out the OS cooldown. |
::bind(lfd, &addr, sizeof) |
Claim an address (IP+port) for the socket. |
::listen(lfd, 64) |
Mark it passive (accepting connections); 64 = backlog = max pending connections queued before refusing. |
::accept(lfd, ...) |
Pull one waiting connection off the queue → a new fd for that one client. Listen socket keeps listening. |
| `::fcntl(fd, F_SETFL, flags | O_NONBLOCK)` |
::poll(pfds, n, -1) |
Sleep until any watched fd is ready (POLLIN=readable, POLLOUT=writable), mark which in .revents. -1=wait forever. One thread watches many sockets. |
::read(fd,buf,len) / ::write(fd,buf,len) |
Move bytes. Return count moved, 0=peer closed (read), -1=error (errno; EAGAIN=nothing now, not a real error). |
::close(fd) |
Release the fd, close the connection. |
::inet_pton(AF_INET,"127.0.0.1",&a) (client) |
Text IP → binary form. |
::connect(fd,&addr,...) (client) |
Dial a server address. |
htons(port) = host-to-network-short: networks use big-endian; convert the 16-bit port from host order to network order (same endianness idea as the wire protocol, but for the OS's address structs). INADDR_ANY (0.0.0.0) = bind to all interfaces (localhost + LAN), not one IP.
sockaddr_in addr{}; // OS struct for an IPv4 address; {} zeroes it
addr.sin_family = AF_INET; // IPv4 (must match socket())
addr.sin_addr.s_addr = INADDR_ANY; // all interfaces (0.0.0.0)
addr.sin_port = htons(static_cast<uint16_t>(port)); // cast int→16-bit, then host→network order
if (::bind(lfd, reinterpret_cast<sockaddr*>(&addr), sizeof(addr)) < 0) { ... }
if (::listen(lfd, 64) < 0) { ... } // passive mode, backlog 64
set_nonblocking(lfd); // accept() must never blockreinterpret_cast<sockaddr*>(&addr)—bindwants a genericsockaddr*; you have asockaddr_in*(the IPv4 flavor). The cast reinterprets the pointer — a historical C-API wart; the two structs are layout-compatible for this.sizeof(addr)tellsbindhow many bytes to read.< 0= failure on both;perrorprints the OS reason ("Address already in use", "Permission denied" for ports <1024, etc.).
TCP (Transmission Control Protocol) is a set of rules two computers follow when exchanging data over a network. Like certified mail for a 100-page document: every page numbered, missing pages re-requested, out-of-order pages reordered, receipt confirmed. TCP does that for bytes.
Send Hello World. TCP may actually send:
Packet 1: Hel
Packet 2: lo␣
Packet 3: World
If Packet 2 is lost, the receiver gets Packets 1 and 3, notices "#2 never arrived," and asks for it again. Your program simply reads Hello World — you never see the missing packet.
IP (the layer under TCP) is unreliable — it only promises "I'll try my best." Packets can disappear, duplicate, arrive late, or arrive out of order. TCP fixes all of that.
write(sock, "ABCDEF", 6); → peer reads "ABCDEF"
Exactly once. In order. Without corruption. That's the entire point.
Like a phone call: Alice ────── Bob, two ends, each an endpoint. Networking is identical: Computer A ────── Computer B, each side owns one endpoint. A TCP endpoint = IP Address + Port Number, e.g. 192.168.1.50:8080. The other side might be 18.205.93.2:443. The connection is those two endpoints, and together they uniquely identify it.
A socket is the kernel object representing one endpoint. int sock = socket(AF_INET, SOCK_STREAM, 0); says "Kernel, create a TCP endpoint for me." Its state evolves:
socket() → State: CLOSED, IP: none, Port: none
bind(...) → IP = 127.0.0.1, Port = 8080
connect(.) → Local 127.0.0.1:50000 ↓ Remote 8.8.8.8:80 (knows both sides)
One computer runs Chrome, Discord, Spotify, VS Code, Steam — all on the network at once. How does the OS know which program gets an incoming packet? Ports. Each program is bound to a port; an incoming packet with Destination Port = 50002 → kernel routes it to whichever program owns 50002.
Server runs on a known endpoint, e.g. 10.0.0.5:8080, and clients connect there. A client (browser) also has an endpoint — the OS auto-picks a temporary source port, e.g. 192.168.1.8:49152. The connection becomes:
192.168.1.8:49152 ↓ 10.0.0.5:8080
The server replies to that exact client endpoint.
A TCP connection is uniquely identified by:
(Local IP, Local Port, Remote IP, Remote Port)
That's why one web server can have thousands of clients on the same port (:443): each client has a different source IP and/or source port, so each connection's 4-tuple is unique.
socket()
│
▼
Kernel Socket Object (State = CLOSED)
│ bind()
▼
Local Endpoint 127.0.0.1:8080
│ listen()
▼
Waiting for Clients
│ accept()
▼
Connected Socket
Local: 127.0.0.1:8080
Remote: 192.168.1.50:52344
│ read()/write()
▼
Reliable TCP Stream
- TCP — the protocol: the rules making communication reliable (ordering, retransmission, checksums, flow/congestion control).
- TCP endpoint — a network address where communication happens: IP + port (e.g.
203.0.113.10:8080). - Socket — the kernel object your program uses to send/receive through an endpoint, handled via the file descriptor from
socket().
So int sock = socket(AF_INET, SOCK_STREAM, 0); doesn't create "the Internet" or even the connection — it asks the kernel for an object that will eventually represent your end of a TCP connection. Once connected, every read()/write() on it goes through TCP, which transparently handles packetization, acknowledgments, retransmission, and in-order delivery.
Does my laptop have infinite IPs and ports? No — and IPs and ports are different things.
IP address = your house address. Your laptop usually has one IP on the local network (e.g. 192.168.1.104); your router has a separate public IP (e.g. 73.14.211.90). The Internet sees the router's public IP, not your laptop's private one (because of NAT). So a laptop typically has: 1 IPv4 address, maybe some IPv6 addresses, and localhost (127.0.0.1) for talking to itself.
Ports = apartments inside the building. If IP 192.168.1.104 is the building, 192.168.1.104:8080 means building 192.168.1.104, apartment 8080. There are 65,536 ports (0–65535), some reserved:
22 SSH 25 SMTP 53 DNS 80 HTTP 443 HTTPS
Most client programs use high-numbered "ephemeral" ports (often ~49152–65535, exact range is OS-dependent).
Can two programs use the same port? Usually no. If Chrome binds port 50001, Spotify can't also bind 50001 (unless special options like SO_REUSEPORT in specific scenarios) — otherwise the kernel wouldn't know which program should receive the data.
Then how can thousands of Chrome tabs exist? Because connections are identified by the full 4-tuple (Local IP, Local Port, Remote IP, Remote Port):
tab 1: 192.168.1.104:50001 → 142.251.35.46:443 (Google)
tab 2: 192.168.1.104:50002 → 104.18.x.x:443 (OpenAI)
Different local ports → no conflict.
Does the server know my IP? Yes — it has to, or it couldn't send the response. Every TCP packet carries source and destination addressing. The server sees your client IP + port (or, behind a home router, your router's public IP and NAT-translated port rather than your private 192.168.x.x).
Can the server connect back to me? Potentially — it knows your IP. But your router/firewall usually blocks unsolicited inbound connections, so it can't just start talking to your laptop unless you've allowed it (port forwarding, etc.).
Can I choose my client port? Yes, but almost nobody does. Normally connect(sock, ...) lets the kernel pick an available ephemeral port (e.g. 53142) — you never notice. You can force one with bind(sock, my_port) before connect, but it's uncommon (the OS is good at picking unused ports; hardcoding risks conflicts).
Can I choose my IP? Usually no — it comes from your Wi-Fi / Ethernet / VPN / cloud / network config; you can't invent one. With multiple interfaces (Wi-Fi + Ethernet + VPN) you can choose which assigned IP/interface to bind to, but it must be one actually assigned to your machine.
What does the server actually store? One socket per client. Connect to Google and it creates a socket Local 142.251.35.46:443 ↔ Remote 73.14.211.90:53142 representing you. Another user gets another socket 142.251.35.46:443 ↔ 98.201.4.55:53822. That's why one listening socket can accept thousands of clients — each accepted connection is its own socket, distinguished by its unique 4-tuple.
Full example (Starbucks Wi-Fi): laptop gets private IP 192.168.0.14, router has public IP 104.28.151.83. Open ChatGPT; kernel picks local port 54218; ChatGPT's server is 104.18.x.x:443. After NAT the connection looks like:
104.28.151.83:54218 → 104.18.x.x:443
ChatGPT replies to that source IP+port; the router's NAT table forwards it back to your laptop's private address.
Key intuition: an IP identifies a machine (really, a network interface); a port identifies a specific endpoint on it; together IP:Port = an endpoint; and a TCP connection is uniquely (Local IP, Local Port, Remote IP, Remote Port). That's why millions of machines connect to the same server on port 443 without collisions — the server distinguishes clients by the whole tuple, not by its own port.
This is where you move from "one connection" thinking to "handle thousands of connections efficiently." Instead of one thread per client, the network thread watches many file descriptors and reacts only when something happens. That's an event loop.
pollfd — a "watch request" struct from the OS:
struct pollfd {
int fd; // file descriptor to watch
short events; // what we care about (POLLIN / POLLOUT)
short revents; // what actually happened (kernel fills this in)
};Think of it as a subscription: "Kernel, watch this fd, tell me when it becomes interesting." pollfd is not a socket — it's a temporary watch request you hand the kernel each loop.
The event flags:
POLLIN= "there is data available to read." On a client socket: the client sent bytes. On the listening socket: a connection is waiting to beaccept()ed.POLLOUT= "the socket's send buffer has room; you can write now." Needed only when a previouswrite()couldn't flush everything (kernel buffer was full) and bytes are parked inoutbufwaiting.
Building the watch list each iteration:
std::vector<pollfd> pfds;
pfds.push_back({lfd, POLLIN, 0}); // [0] listening socket -> "wake me when someone connects"
pfds.push_back({wake[0], POLLIN, 0}); // [1] self-pipe read end -> "wake me when matching has output"
for (auto& [sid, s] : sessions) { // [2..] every connected client
short ev = POLLIN; // always watch reads: clients can always send orders
if (s.out_off < s.outbuf.size()) // only ask about writes if we actually have bytes queued...
ev |= POLLOUT; // ...else the socket is ~always writable and we'd spin awake for nothing
pfds.push_back({s.fd, ev, 0});
}lfd is the listening socket (from socket/bind/listen) — never a client; it only produces new connections. The self-pipe entry is how the matching thread wakes this loop (writes to wake[1] → wake[0] becomes readable). Example resulting list:
index fd events
0 3 POLLIN (listen)
1 4 POLLIN (wake pipe)
2 7 POLLIN (client A)
3 8 POLLIN (client B)
poll() — sleep until something is ready:
int n = poll(pfds.data(), pfds.size(), -1);pfds.data()— pointer to the watch array;pfds.size()— how many;-1— timeout = sleep forever until something happens. No busy looping — the thread sleeps at 0% CPU until the kernel wakes it. When client A sends data, the kernel sets that entry'sreventstoPOLLINand returns.
Reacting to what fired: each entry's revents now says what happened (0 = nothing). The loop checks them:
if (pfds[0].revents & POLLIN) { ... accept() ... } // listen fired -> new connection
if (pfds[1].revents & POLLIN) { ... drain pipe ... } // matching produced output
for (client sockets) {
if (revents & POLLIN) { read -> frame -> queue to matcher }
if (revents & POLLOUT) { write pending outbuf bytes }
}Accepting a client (lfd fired):
int cfd = ::accept(lfd, nullptr, nullptr); // lfd is NOT the client -> it CREATES the client socket (new fd)
set_nonblocking(cfd); // never let a slow client freeze the network thread
uint64_t sid = next_sid++; // internal monotonic identity
sessions[sid] = Session{cfd, sid, {}, {}, 0};
fd_to_sid[cfd] = sid; // reverse lookup: poll() gives us an fd, we need its Sessionaccept doesn't return the client's data — it spawns a new socket fd dedicated to that one client. The listening socket keeps listening. set_nonblocking is critical: a blocking read on a stalled client would freeze the whole thread (and every other client on it).
Why rebuild the pollfd vector every loop: the set of connections changes constantly — clients connect and disconnect between iterations. The watch list must reflect current sessions, so it's rebuilt fresh each pass. (At thousands of connections you'd switch to a persistent epoll/kqueue set instead of rebuilding — the scale-up path, unneeded here.)
The whole network thread, in one picture:
while (true):
build list of fds to watch (listen + pipe + all clients)
poll() # sleep until something is ready
dispatch on what fired:
new client? -> accept()
matching finished? -> drain pipe, flush output
client sent order? -> read() -> decode() -> queue to matcher
client writable? -> write() pending bytes
This is the same architecture behind high-performance web servers, exchanges, proxies, and databases. Key idea: pollfd isn't a socket — it's a temporary "watch request" handed to the kernel: "tell me when this fd needs attention."
- 13 scenario tests, each mapping to one behavior: rest/BBO, full cross, price priority, time priority, partial fills, IOC remainder, market-into-empty-book, cancel ok, cancel-too-late, cross-then-rest, multi-level sweep, rejects, stale-handle/generation safety.
- Invariant checker after every test — catches corruption the scenario's asserts didn't think to look for.
- Plain asserts, no framework (see Stack Decisions).
- Later (QuantOS engine phase): differential oracle — a deliberately naive, obviously-correct second implementation; fuzz random op sequences through both, demand identical outputs. The gold standard for "how do you know the fast one is right?" Overkill for LiquidBook M1, noted so future-me knows where it goes.
-
types.hpp— vocabulary -
pool.hpp— order pool, free list, generations -
book.hpp— ladder, levels, matcher, cancel, BBO, invariant checker -
tests/test_book.cpp— 13 tests -
CMakeLists.txt— deferred to M3 (one test file didn't justify it; cmake not installed anyway) - Build green via direct compile:
g++ -std=c++20 -O2 -Wall -Wextra -Iinclude tests/test_book.cpp -o lb_tests && ./lb_tests→all tests passed - Full M1 code review — walked pool.hpp + book.hpp function by function, understood ladder/pool/matcher/generation-handle mechanics
- Note:
cmakenot installed on machine; using directg++/clang++compile until M3 needs multi-target builds.
- Fixed-layout message structs:
WireNew,WireCancel→ inbound; one fixedEventlayout → outbound - Encode/decode against raw byte buffers — zero allocation, fixed offsets, explicit little-endian (no JSON, no strings, no memcpy-a-struct)
- Framing: type byte first +
inbound_msg_size(type)lookup (New=19, Cancel=9). Outbound all one fixed size (kEventSize=42) → no size table needed, client reads fixed 42-byte strides - Round-trip tests (
tests/test_protocol.cpp): 5 tests — new/cancel/event roundtrip (signed price survives), unknown-type→0, byte-helper endian →all protocol tests passed - Wire message directions: inbound = commands (
New/Cancel), outbound = events. Never inbound event, never outbound command (client has no book, can't produce facts).
-
socket/bind/listen/acceptloop; multiple concurrent client sessions (src/server.cpp) - Partial-read handling: per-session
inbufaccumulates fragments until a full message frames (type byte +inbound_msg_size) - Connection lifecycle: clean disconnect, mid-message death, unknown-type drop, no leaks
- Threading: network thread owns sockets +
poll()loop; matching thread owns the (lock-free) book; two mutex-guarded queues + condvar + self-pipe wakeup between them -
src/client.cpptest driver — dials, sends 2 orders, prints Ack/Ack/Fill - Verified end-to-end: server accepts, matches, returns events; survives repeated connects; clean Ctrl-C
- Known simplification: submitter-only event routing (makers not notified when someone else fills them) — documented, deferred.
- CMake still deferred; building with direct
g++ ... -pthread.
- Cycle-counter timer:
cntvct_el0on ARM (this Mac),rdtscon x86 (benchmarks/benchmark_engine.cpp). NOTE: this Mac'scntfrq_el0= 1 GHz sons/cycle=1.0is CORRECT (1 tick = 1ns), but the counter physically updates in ~42ns steps → sub-42ns ops read p50=0. The counter IS engaged (claim is true); it's just coarse. - Engine bench: phased add / cancel / match on fresh books (clean attribution), xorshift workload, reused event buffer (no alloc in timed loop)
- Net bench (
benchmarks/benchmark_net_to_net.cpp): ping-pong round-trip latency + pipelined throughput (reader thread drains responses → no deadlock) - Reports p50/p99/max + throughput
Measured results (this Mac, Apple Silicon arm64):
| bench | metric | value |
|---|---|---|
| engine add | throughput | ~77 M ops/s (~13 ns/op avg) |
| engine cancel | throughput | ~134 M ops/s (~7 ns/op avg) |
| engine match | throughput | ~60 M ops/s (~16 ns/op avg) |
| net latency | p50 / p99 | ~26–41 µs / ~63–102 µs round-trip |
| net throughput | orders/sec | ~1.5–1.8 M/s over TCP (~0.6 µs/order) |
Reliable numbers = throughput (immune to timer granularity) and the net p50 (µs-scale, well above the 42ns floor). In-process per-op p50 reads 0 on this Mac (granularity); its real value comes from throughput (~16ns match). For true in-process p50/p99 in ns, run the engine bench on x86 Linux (rdtsc, ~0.3ns).
How to run:
# engine (no server needed)
g++ -std=c++20 -O2 -Wall -Wextra -Iinclude benchmarks/benchmark_engine.cpp -o build/lb_bench && ./build/lb_bench 200000
# net (needs a FRESH server — book persists across connections)
g++ -std=c++20 -O2 -Wall -Wextra -Iinclude src/server.cpp -o build/lb_server -pthread
g++ -std=c++20 -O2 -Wall -Wextra -Iinclude benchmarks/benchmark_net_to_net.cpp -o build/lb_bench_net -pthread
./build/lb_server 9001 # terminal A (restart before each run)
./build/lb_bench_net 9001 # terminal Bmatch() break condition was inverted (if (crossable) break; instead of if (!crossable) break;) — introduced while re-commenting book.hpp, would have made nothing ever match. Fixed to break only when the taker canNOT cross. Re-ran tests → green. Lesson: re-run the test suite after any edit to the hot loop, even a "comment-only" pass.
Core carries over; adaptation adds: determinism discipline (seeded RNG, no clock reads), synthetic-market simulation layer, queue-position accounting, pybind11 Python bindings, oracle/fuzz test regime. TCP shell stays here as LiquidBook's standalone identity. Specs already written: quant-os/docs/engine/e0–e6.
- Floats never touch money. Integer ticks/lots inside; convert at the edges, once.
- No allocation on the hot path. Preallocate, pool, reuse. Allocation = tail-latency spikes.
- Cancels dominate real order flow. Cancel must be O(1), and benchmarks must stress it.
- Fills are facts. Races resolve in favor of what already executed; nothing un-fills.
- Percentiles, not averages. p99 (worst 1%) is where systems die; one 100µs spike vanishes in a mean.
- Handles over pointers. Index + generation survives slot reuse safely; raw pointers don't.
- Invariant checkers over example-only tests. Scenarios prove behaviors; the invariant walk catches everything the scenario forgot to assert.
- Hot path / cold path split. Per-order code counts nanoseconds; setup code counts readability. Never confuse the budgets.
| Phrase | Meaning |
|---|---|
| Limit order book | The sorted waiting list of unfilled orders. Bids (buyers) one side, asks (sellers) other. "Limit" = order with a price boundary. |
| Price-time priority | Who trades first: best price wins; ties broken by arrival time (FIFO within a level). |
| Flat-array price levels | Levels in a contiguous array indexed by price - min_price. One arithmetic op + one read to find any level. |
| Pointer-based trees | The alternative (std::map/red-black tree): each price lookup walks nodes scattered across RAM — a cache miss per hop. |
| Hot matching path | The code that runs per order, millions of times. The only place nanoseconds matter. |
| Cache-resident | Working data small and contiguous enough to stay in the CPU's L1/L2 cache (~1ns reads) instead of RAM (~100ns). |
| Cache miss | CPU needs data not in cache → stalls ~100ns for RAM. At a 1µs budget, each miss = 10% gone. |
| High-frequency matching and cancellation | Real flow is mostly cancels (market makers re-quoting constantly) — so cancel is engineered as hard as add: O(1) via handle → slot → unlink. |
| Phrase | Meaning |
|---|---|
| Binary order protocol | Messages as raw fixed-layout bytes (byte 0 = type, next 8 = price...). Not JSON/text. Real venues (NASDAQ OUCH) do this. |
| Low-overhead parsing | Reading fixed offsets from a buffer — no string splitting, no parser library. |
| Allocation-free | Zero malloc/new per message; one reused buffer. Keeps latency flat. |
| POSIX TCP server | A program accepting network connections via the OS's raw C socket API (socket/bind/listen/accept/read/write) — no framework. POSIX = the Unix standard. |
| Routing order flow | Bytes from client → parsed order → book → resulting events → back to the right client. |
| Concurrent sessions | Multiple clients connected at once, each an independent connection, all feeding one book. |
| Connection lifecycle | Connect, disconnect, die mid-message, reconnect — handled cleanly every time (close sockets, free session state, no leaks). |
| Partial reads | TCP delivers a byte stream with no message boundaries — one read() may return half a message or 2.5. Server buffers fragments and reassembles. THE classic networking bug. |
| Without blocking the matching thread | Blocking = thread sleeps waiting on network. If the matching thread ever waits on a slow client, the whole book freezes. So: network threads own sockets, matching thread owns the book, queue between. |
| Phrase | Meaning |
|---|---|
| Instrumented | Measurement hooks built into the code itself. |
| Per-operation latency | Time for one add / cancel / match, isolated — tells you where time goes. |
| End-to-end latency | Full trip: bytes at socket → parse → match → response sent — what a user experiences. |
| rdtsc CPU cycle counters | x86 instruction reading the CPU's cycle counter (~0.3ns resolution, nearly free to read). Normal clocks cost more to read than the thing being measured. ARM (this Mac) equivalent: cntvct_el0. |
| Order-flow benchmark | A generated stream of realistic mixed operations replayed at max speed — not one op in a loop. |
| Insertions / cancellations / crossing fills | The three op types stressing different code paths: resting adds (build depth), cancels (dominant in real flow), immediate matches (exercise the fill walk). |
| Throughput bottleneck | The one slowest component capping total ops/sec — found by profiling, fixed first. |
| Tail latency | The worst cases: p99 = slowest 1%. Averages lie; tails expose allocation, cache eviction, rare-path bugs — and kill trading systems. |
- Band re-anchoring + overflow map: current design rejects out-of-band prices. Fine for M1–M4; the QuantOS adaptation needs the dense-band + overflow hybrid (spec'd in quant-os e1 §3.1). Deferred.
- Self-match policy: currently orders can match against the submitter's own resting orders (there's no ownership concept yet). Becomes a real question when QuantOS strategies share a book. Deferred.
- Framing choice for M2: fixed-size messages (simplest, slightly wasteful) vs length-prefixed (flexible). Decide at M2 start.
- Threading model detail for M3: one network thread + one matching thread + SPSC queue is the lean default; measure before anything fancier.
- GTest/Catch2: revisit if plain asserts start hurting (test fixtures, parametrized tests). Not yet.
- Git init: not initialized yet — decide when.
- Apple Silicon benchmark caveat: cycle-counter numbers on ARM Mac aren't directly comparable to x86 server numbers; report hardware alongside every number (honesty rule from QuantOS NG-2 applies here too).