// Design & architecture

Anvil

A single-threaded, deterministic C++20 price-time-priority matching engine — the data model, the matching semantics, the correctness evidence, and the live-demo layer that wraps it unmodified — with the reasoning behind each decision and the road to production mapped.

What Anvil is

Anvil reads a stream of New / Cancel / Amend messages, matches them under strict price-then-time (FIFO) priority, holds the resting order book in memory, and emits deterministic, replayable output — trades and rejections in processing order, then a dump of the resting book. Input is a fixed six-field CSV line (ticker,type,id,side,qty,price); a venue matching a single instrument, distilled to its core.

Two things share one repository, and the framing is deliberate. The engine core (in src/) is the matching engine, built properly within its scope. The demo layer wraps that engine unmodified in a Crow C++ server that streams the live book to a browser trading terminal. This is the matching core done well — not a production venue; the venue-scale gaps are a designed-for boundary, named at the close, not an oversight.

The engine — data model

Correctness and speed both fall out of the data model. The guiding rule throughout: indices, not pointers; integers, not strings; values, not exceptions.

The core types the rest of this section builds on, in one place. The one worth pausing on is Level: it is only a FIFO queue at a single price — head/tail indices into the order pool, and nothing else — with no aggregate quantity by design.

Pools and indices, everywhere

Orders and price levels live in two std::vector object pools. Every cross-reference — FIFO links, an order's owning level, the id index, the price→level maps — is a 32-bit index, never a pointer. Three concrete reasons:

• ▹Pools reallocate as they grow. A vector that resizes invalidates every pointer into it; 32-bit indices survive the move untouched.
• ▹Half the linkage size. prev / next / level as uint32_t are half the size of 64-bit pointers — denser cache lines on the hot path.
• ▹The whole engine is relocatable. No interior pointers means the entire engine could be serialized, snapshotted, or moved as plain bytes.

Both pools carry an intrusive free list threaded through the dead objects themselves — a freed order's next link doubles as the free-list link — so there is no side allocator bookkeeping. The two pools are separate structs (OrderPool and LevelPool), and OrderIdx / LevelIdx are both uint32_t aliases — keeping each index paired with its own pool is a discipline the code holds, not one the compiler enforces. NIL = 0xFFFFFFFF is the null index.

The book — flat_map + level indirection

Each side of a book is a sorted map from price to level: bids use std::greater<> so begin() is the best (highest) bid; asks use std::less<> so begin() is the best (lowest) ask. With Boost this is a flat_map — a sorted contiguous vector of (price, levelIdx) pairs: cache-friendly, branch-predictable scans, no per-node allocation.

The map stores only the pair, never the level. That indirection is the whole trick: inserting or erasing a price level memmoves the flat_map's backing storage, so any iterator into it is instantly stale — but the Level objects sit in their own pool and never move. So an order's level index stays valid for its whole life (an O(1) hop from any order to its level, used by cancel and amend), while the matching loop never caches a flat_map iterator across an insert or erase — it copies the price/level into locals and drops the iterator before any structural change.

ID packing — no strings

Order ids are ≤ 10 chars from a 63-symbol alphabet ([A-Za-z0-9-]). Each char encodes to 1..63 in 6 bits; 10 × 6 = 60 bits fit a uint64_t. The packed key is the hash-map key and the print source. Charset and length validation fall straight out of the encoder — any unencodable char or over-length id makes the pack fail, so there is no separate id validator, no string hashing, no allocation, no comparison on the path.

Fixed-point prices — doubles never touch the data

Prices are int32_t ticks (price × 10⁴, 4 dp). The input path parses a price directly to ticks — integer part × 10⁴ plus the right-padded fraction — using only the integer overloads of std::from_chars. No double, no rounding error, exact equality comparisons, so map keys never drift. The 100,000.0000 ceiling is 10⁹ ticks, comfortably inside int32_t.

Parsing and the output seam

The whole file is slurped into one buffer and parsed in place with string_view slices — zero per-line allocations; std::from_chars is the only numeric conversion (non-allocating, locale-independent, and it reports trailing garbage, which is exactly the validation wanted). The matching core then emits semantic events — a fill happened, an order is resting, a message was rejected — not formatted text. A single Sink turns those events into output bytes; match and dump_book stay free of any string formatting. That one seam is what the demo later re-points without touching the engine.

Complexity

L is the number of distinct price levels on one side of one ticker — in practice tens, occasionally low hundreds. At that scale the asymptotics are not the story: constant factors and access patterns dominate. A contiguous flat_map of tens of entries fits in a couple of cache lines and beats a pointer-chasing node tree, even though both are “O(log L)” — flat, cache-resident, and branch-friendly wins in this size regime.

Matching semantics & rationale

The trading semantics are deliberate, each chosen with its alternative consciously rejected. These are the decisions that make Anvil a matching engine and not just a sorted container.

• ▹Trade price is the resting order’s price, not the aggressor’s. The passive side set the price, so a sweep through several levels prints at successively worse resting prices rather than one blended fill — the standard continuous-auction convention. The aggressor may receive price improvement.
• ▹Amend quantity is the new total (remaining = new_total − filled), matching cancel/replace on real venues. Price unchanged and smaller → reduce in place with time priority preserved; price changed or quantity increased → unlink and re-enter as new (loses priority, may trade immediately); new_total ≤ filled → auto-cancel (a venue convention, not an error, because the only correct resting quantity is then zero).
• ▹Cancel is by id alone, unconditional. The echoed side / price / quantity on a cancel are non-authoritative and ignored. Rationale: a cancel rejected on a stale echo would leave live risk resting on a book the client believes is dead — real venues cancel by id.
• ▹Global id uniqueness. Ids are unique across all tickers, so one global id index locates any order. A freed id (filled, cancelled, auto-cancelled) leaves the index and may be reused — consistent with the input-uniqueness assumption.
• ▹Errors are reported by value, not exceptions. Rejection is routine, high-frequency control flow here, so the parser returns a result and the engine funnels failures through the sink — never a throw. A rejected line stays about as cheap as an accepted one, the hot path stays allocation-free, and a thrown exception (heap-allocated, unwind tables, RTTI) would cost ~100× the engine's tens-of-ns budget. Genuinely exceptional faults like allocation failure are still left to propagate.

The amend decision flow

Every amend traces this exact dispatch — the tests follow it step for step. Side is validated only here (cancel ignores it, new establishes it), and an at-or-below-filled amend auto-cancels rather than erroring.

Correctness — evidenced five ways

Correctness is evidenced in five complementary layers — example-based, exhaustive, structural, differential, and adversarial — so a bug has to survive all five to ship. The honest limit is named too: differential testing verifies the implementation against a second one, not the interpretation — but the verifier and the reference together make “the engine does what was specified” very well evidenced.

Two libFuzzer harnesses round it out: one asserts the parser never crashes on any byte string; the other drives the whole engine and runs the invariant verifier after every message — fuzzing memory safety and structural invariants together. Any reproducer is minimised and pinned as a regression line.

Performance

Benchmark mode runs the full pipeline — slurp, parse, validate, match, format trades and errors — and times only the processing loop (output is formatted into the buffer exactly as in normal mode, then discarded; only the write to stdout is skipped). Numbers are the median of ≥ 5 reps after a warm-up. On a 1,000,000-message mixed workload (16 tickers, ~875k trades, ~70k rejections):

That is ≈ 0.38–0.49 µs per message end-to-end including parse and trade formatting; the core book operation itself is tens of nanoseconds. The Boost-vs-std gap is the flat-vs-node-map effect, but its size and even its sign move with the standard library and the hardware — Boost leads ~1.3× on Windows MinGW, the two are level on Ubuntu GCC, and std edges ahead on the Ubuntu uniform shape — which is why no fixed multiplier is quoted. The adversarial sweep also confirms the footprint claim with data: because a cancel-storm caps the live population, the engine's own memory plateaus as message count grows — memory tracks live order count, not total messages, because the pools recycle freed slots.

The live demo — architecture

The demo wraps the engine without changing it. One anvil_server (Crow) owns the matching engine on a dedicated thread and serves the REST API, the WebSocket stream, and an on-demand dummy-order feeder from one origin. The point is watching the book move, so the streaming path is the heart of it; REST is the control surface.

The engine is never modified, only re-pointed

The only engine-side change is what the output sink reference points at. In the CLI it is a CliSink producing byte-identical output to the take-home submission; in the server it is a TeeSink that fans the same events out to several subscribers. Matching, the book, and order semantics are unchanged — and that is proven against the existing functional diff suite, which still passes byte-for-byte. One repo, a logical (not physical) split: engine in src/, server in server/, web client in web/, and the client/server boundary is the versioned PROTOCOL.md contract, not a repo split.

The egress seam is the Composite pattern

This is the load-bearing design idea. EventSink is the component interface; the concrete sinks are leaves; TeeSink both is an EventSink and holds a collection of them, so the engine forwards to one reference and the tee multiplexes — unaware whether it is one sink or many.

Two properties are load-bearing: the engine emits one FillEvent per fill carrying both taker and maker ids (the CLI's two-line text becomes a rendering detail, removing the half-written-trade window); and sink methods are noexcept, achieved by an allocation-free emit path, which is what makes the tee's fan-out atomic — neither one sink nor the loop across sinks can half-apply.

Concurrency — one writer, queues everywhere else

Exactly one thread ever calls into the engine; everything else communicates through queues. This is the one rule that keeps the demo's determinism identical to the take-home's.

• ▹Engine thread owns the engine and its tee. It drains the inbound queue, applies each message serially, emits through the tee, and on a fixed coalesce tick publishes the latest top-N snapshot via an atomic swap.
• ▹Inbound MPSC queue. REST handlers and the feeder are producers. A manual order carries a promise so the handler can return the engine's verdict synchronously; feeder messages carry none.
• ▹Outbound ring + broadcaster. The publish sink does nothing but push a structured event and return; a separate broadcaster thread serialises to JSON and fans out to WebSocket clients. All formatting and socket I/O happen off the matching thread.
• ▹Overflow is each consumer’s problem. The display path is best-effort: on a full ring it drops and flags stale, and the client recovers from the next snapshot. The engine's per-event cost is bounded and independent of any consumer's speed.
• ▹The feeder is on-demand, parked behind a two-gate predicate (a WS client is connected AND the operator toggle is on), so a burstable single instance costs almost nothing at rest.

The wire contract

REST is the control surface; WebSocket is the stream. Order entry reuses the engine’s own format — the POST /api/order body is a raw engine CSV line fed straight into the existing parser, so there is no second validation path. WebSocket frames are JSON, every frame carrying a monotonic seq: a snapshot (full top-N book, on connect and as the coalesced periodic update), and one trade per fill.

• ▹Errors are not on the stream. A rejected order returns HTTP 200 with {accepted: false, reason} — a business outcome in the body, not a transport error. 4xx/5xx are reserved for genuine non-verdicts (queue full, engine timeout, malformed HTTP, blocked origin). This mirrors a real venue: the session accepts the message and the rejection comes back as an execution report.
• ▹Coalescing bounds egress. Book state publishes at a fixed cadence (~10–15 Hz) regardless of match rate; trades stream individually. Egress is bounded independent of the match rate.
• ▹Reconnect is idempotent. A client opens the socket, receives a snapshot, and discards any buffered frame with seq ≤ the snapshot's seq. Ring overflow surfaces as a seq gap, and the client resyncs automatically.
• ▹Decimals on the wire are byte-identical to the CLI, because the JSON is hand-rolled over the engine's same inline price formatter — one source of truth for the wire format.

In production, nginx terminates TLS, serves the static React/TS client, and reverse-proxies REST and the WebSocket upgrade to the local server; systemd supervises it with an env-file. There are no external runtime dependencies. It is deployed on AWS Lightsail behind nginx.

Why these choices

Indices over pointers, as a single discipline. Choosing 32-bit indices for every cross-reference is not a micro-optimisation in isolation — it is one decision that simultaneously survives pool reallocation, halves linkage size for denser cache lines, and makes the whole engine relocatable. One constraint, three payoffs — held as a discipline: OrderIdx and LevelIdx are plain uint32 aliases, not distinct types, so pairing each index with its own pool is a convention the code keeps rather than an invariant the compiler enforces.

Integers and fixed-point, so equality is exact. Packing ids into a uint64 and parsing prices straight to integer ticks removes strings and doubles from the data entirely. The point is not just speed: exact tick equality means map keys never drift, which is what lets the engine be deterministic and replayable in the first place. Correctness and performance come from the same choice.

Single-threaded by design, not by omission. Per-message work is tens of nanoseconds; an SPSC hand-off to a matching thread would cost on the same order as the work itself. Threading a single book would forfeit the determinism a venue requires and buy nothing. The serial core is the deliberate answer, and horizontal sharding — not threads — is named as the scaling axis.

One output seam, so the demo costs the engine nothing. Because the engine always emitted to a single sink reference, wrapping it in a live server was a matter of re-pointing that reference at a tee — not editing the engine. The byte-identical CLI output still passes the original diff suite, so “the demo didn't change the engine” is proven, not asserted. Designing the seam before it was needed is what made the demo cheap.

Errors by value, because rejection is normal here. A poison feed is expected to reject a large fraction of its lines, so rejection is routine control flow, not an exceptional event. Returning a result and routing it through the sink keeps a bad line about as cheap as a good one and the hot-path latency deterministic — whereas a throw would cost ~100× the per-message budget. Exceptions are reserved for the genuinely exceptional, like allocation failure.

The boundary is stated, not blurred. Anvil is explicitly the matching core done well, not a production venue. Durability, HA, real gateways, risk, self-trade prevention, and order-type breadth are absent on purpose, and the write-up says so — placing the seams they would attach at, but not pretending they are built. Naming the boundary is itself part of the engineering judgment on show.

Future areas for development

What separates Anvil from a venue is a whole category of work, and almost none of it is built — by design. The architecture is positioned for most of it at seams that already exist; the gaps that do not attach at a seam are honest engine work, and are named as such. Placing the seams without yet building behind them is the deliberate scope: the matching core, done properly, with the road out mapped.

Scaling out — shard by ticker

Matching is inherently serial per ticker — price-time priority is a total order over arrivals, and deterministic output is a hard venue requirement — so threading a single book buys nothing and forfeits determinism. The scaling axis is therefore horizontal: a thin router fans messages out by ticker to N engine instances, each owning a disjoint ticker set and running exactly this serial loop. Almost every structure is already per-ticker; the one truly global structure is the id index, which a sharded deployment either enforces at the router (it already maps id→shard for cancels/amends) or partitions per shard. Router plus per-shard determinism preserves a globally reconstructable trade sequence.

A windowed dense array for hot instruments

Beyond flat_map, the production path for a liquid instrument is a tick-indexed dense array — a contiguous block of levels addressed by (price − anchor), giving true O(1) best-price and level access with no search and no memmove, re-anchoring (a bounded copy) only when the touch drifts past the window. flat_map is the right default for a sparse arbitrary price range at assessment scale; the dense window is the right answer when the active band is narrow and hot — exactly the shape the trend adversarial workload exercises.

Durability, reliability, and depth — at the seams

• ▹Durability & crash recovery. The single inbound queue is the sequencing point; command journaling there plus deterministic replay is the recovery path. The deterministic serial core is also what makes replication tractable. A JournalSink (durable log, system of record) attaches as another tee child.
• ▹Reliable execution reporting. A VenueSink — sequencing, acks, resend, idempotency — is where accurate per-order fill attribution for the blotter lives, and likewise attaches as a tee child without touching the engine.
• ▹L2 / aggregate depth. Level deliberately stores no aggregate quantity (it is 8 bytes: just head/tail). A depth feed would add one quantity per level, maintained on every fill/insert/unlink — a known, isolated extension point.
• ▹Real order-entry gateways. Production FIX or binary ingress and a sequenced market-data feed attach in front of the inbound queue; the CSV-over-REST contract is the demo's stand-in.

Honest engine work — the matching-semantics gaps

Some gaps do not attach at a seam and are genuine engine work: self-trade prevention (there is no owner field today), broader order types and auctions, and pre-trade risk. And the demo's v1 runs one shared, unauthenticated book by design — a “trading floor” feel — which is the obvious thing to gate first if it is ever exposed more widely. These are named as boundaries, not hidden as omissions.