Building a Low-Latency
Order Book from Scratch

A book is two sorted collections of resting intentions. Buy orders (bids) sorted high-to-low, sell orders (asks, or offers) sorted low-to-high. The best bid and best ask together are the touch; the gap between them is the spread; the total live quantity resting at one price is the depth at that level. That is the entire data model.

An order is a standing offer: “I will buy up to 500 at 100 or better.” It sits in the book until someone takes it, or the owner cancels it, or it expires. Nothing happens on a timer — a book is entirely event-driven, and every state change is caused by an incoming message.

Why the book can never cross

If the best bid were 101 and the best ask 100, someone would be willing to buy at 101 while someone else is willing to sell at 100 — so a trade must happen. The engine's job is to make that trade immediately, which means a resting book is always in a state where best_bid < best_ask. That is your first and most important invariant, and asserting it after every operation will find more bugs than any test you write deliberately.

Price–time priority, and why it forces a queue

When two orders compete, the rule is: better price wins; at equal price, earlier arrival wins. Price first, time as the tie-break. This is what makes an exchange defensibly fair — you cannot jump a queue by being bigger or better connected, only by offering a better price.

The consequence is structural, and it dictates your design: because ties are broken by arrival time, the orders at a single price level must be a FIFO queue, not a set or a bag. Every FIFO-related bug you hit later comes from this rule, not from your choice of container. And it is why cancellation is awkward: removing an order from the middle of a queue while preserving the order of everything behind it is the central mechanical problem of rungs 1 and 2.

The three operations — and the one surprising rule

Everything an exchange does decomposes into three operations:

• Add — a new order arrives. If it crosses the opposite touch, match it; otherwise rest it at the back of its price level's queue.
• Cancel — remove a resting order by its id. Must be O(1), because cancels vastly outnumber trades in real flow.
• Execute — a trade happens: reduce the front resting order's quantity, and remove it if it reaches zero.

The rule that home-made engines get wrong: a trade executes at the resting order's price, never the incoming order's. Bid 101 into an ask resting at 100 and you pay 100, not 101. The resting order is entitled to that better price because it was there first — the same time-priority rule again, viewed from the other side. The difference is called price improvement, and getting it right is a five-second signal to an interviewer that you understand the domain rather than the data structure.

The two sides also have names worth using: the incoming order is the aggressor or taker; the order it consumes is the maker. Exchanges usually charge takers and rebate makers, because makers supply the liquidity that makes the book worth trading against at all.

Money is decimal and double is binary, and that mismatch will corrupt your book in a way no test catches unless you go looking. This chapter is short because the fix is short — but the reasoning matters, because “use integers” without the why is a rule you will break under pressure.

Why doubles lie

A double stores a number as a binary fraction: sums of 1/2, 1/4, 1/8 and so on. Some decimals land exactly on such a sum — 0.5, 0.25, 0.75. Most do not. 0.1 in binary is 0.0001100110011... repeating forever, exactly the way 1/3 repeats in decimal. Stored in 53 bits of mantissa, it is truncated, so what you actually hold is approximately 0.1.

Try it and watch: 0.1 + 0.2 == 0.3 is false. The left side is 0.30000000000000004. That single fact is enough to break an order book, and here is the precise mechanism — this is the part worth internalising:

Your book finds a price level by comparing prices. If one order's price arrived as a literal 100.10 and another's was computed as 100.00 + 0.10, those two doubles differ in the last bit. They are not equal. So two orders that a human would say are at the same price land at two different levels in your book. Depth is wrong, the touch is wrong, and matching silently skips liquidity that is sitting right there. Nothing crashes. The book is just quietly incorrect, and it will stay incorrect until someone reconciles against an exchange and cannot work out why.

Accumulated error compounds the problem: add a hundred fills together and the drift becomes visible in the cents column, which in a real system means money that does not add up.

The fix: count ticks, not currency

An exchange never allows arbitrary prices. It defines a minimum increment — the tick — and every valid price is an integer multiple of it. A tick might be one cent, or a hundredth of a cent for a liquid instrument. So stop storing currency and store how many ticks, as a signed 64-bit integer:

using Price = std::int64_t;   // ticks, not dollars

// with a tick of 1/10000 of a unit:
constexpr std::int64_t TICKS_PER_UNIT = 10'000;

Price from_decimal_string(std::string_view s);  // parse at the edge
std::string to_decimal_string(Price p);         // format at the edge

Now every price comparison is exact integer comparison. Two orders at the same price are at the same level, always, with no tolerance and no epsilon. Addition and subtraction are exact. Equality means equality.

Does int64 have the range? Worth checking rather than assuming, since this is the one question an interviewer will ask. A signed 64-bit integer holds up to about 9.2 × 10¹⁸. At 10,000 ticks per unit that is prices up to roughly 9.2 × 10¹⁴ currency units — nine hundred trillion. There is no instrument on earth that needs more, so the range question is settled and you can say why.

Where conversion is allowed: at the edges only — parsing an inbound message, and formatting for display or logging. Between those two points, no floating point touches a price. Write a test that greps your own price path for double and float and fails if it finds any; that test will save you a week at some point.

Why not a decimal float type? Because you do not need one. Decimal floating point solves representation, but you would still be paying for a general-purpose numeric type when the real insight is that prices are not continuous quantities at all — they are a lattice. Ticks are the natural unit, and integers are the natural representation of a lattice. This is the same reason you count pixels rather than storing inches.

Big-O tells you how an operation scales. It does not tell you what it costs, and for a book-sized container those two answers can point in opposite directions. This chapter is about what the standard containers actually do to memory, because that — not the complexity class — is what decides your design at rung 1.

The distinction that matters: node-based versus contiguous

Every standard container is one of two shapes. Contiguous ones (vector, and deque in chunks) store elements next to each other in memory. Node-based ones (map, set, list, and the buckets of unordered_map) allocate a separate node per element and link them with pointers.

That difference decides three things at once: how many separate allocations you perform, whether walking the container is a sequential memory read or a scatter of random ones, and which operations invalidate what.

std::map — the elegant trap

std::map<Price, Level> looks like the obvious answer for price levels. It is sorted, so begin() is your touch; lookup is O(log n); insertion keeps everything ordered. The interface is exactly the shape of the problem.

What it hides: it is a balanced binary tree with one heap allocation per level, and those nodes are scattered wherever the allocator put them. So an O(log n) lookup over 1,000 levels is about ten steps, and each step is a pointer dereference to an unpredictable address — which means each step is a potential cache miss costing on the order of a hundred times an L1 hit. Ten misses to answer one lookup. Meanwhile a binary search over a sorted vector of the same 1,000 levels does the same ten comparisons but touches only two or three cache lines, because the elements it probes are near each other.

Same complexity class. Very different cost. That is the whole reason Ch 9 exists, and it is the mechanism behind the phrase contiguity beats asymptotics at small n.

Invalidation — the rules that actually bite

Your order index has to map an order_id to a resting order in O(1). The obvious implementation stores a pointer or an iterator. Whether that is safe depends entirely on rules you must look up rather than recall, because they are not intuitive:

The practical conclusion: if you choose a contiguous level container, your order index cannot store a pointer or an iterator. It must store a stable handle — a price plus a slot number, say — that you resolve on each use. If you skip this, you get the classic rung 1 symptom: the book works perfectly until an insert happens to trigger reallocation, and then you are reading freed memory and the crash lands somewhere unrelated.

One container to distrust for a reason unrelated to speed

unordered_map's iteration order is unspecified by the standard. It depends on bucket count, hash function and insertion history, and it is not something you may rely on. In practice a given build often reproduces the same order for the same insertion sequence — which is worse than if it never did, because it means the bug hides. If you ever iterate an unordered_map to compute a hash of your engine's state, rung 4's deterministic replay will fail intermittently and you will spend an evening blaming your matching logic. Iterate something ordered, or sort before hashing.

There are exactly two places your program puts data, they behave completely differently, and the difference is the entire reason Ch 6 exists. This is short, and it is load-bearing.

The stack: a pointer that moves

Local variables live on the stack. Allocating one costs a single register adjustment — the stack pointer moves down by the size you need. Freeing costs the same in reverse, and it happens automatically when the variable goes out of scope. There is no bookkeeping, no search, no failure mode short of running out of stack entirely.

It is also the fastest memory you will ever touch, for a reason that has nothing to do with the allocation: the top of the stack was used moments ago, so it is almost certainly already in L1 cache. Stack data is cache-hot by construction.

The constraints are that the size must be known at compile time, and the lifetime ends with the scope. Everything that outlives its scope or is sized at runtime has to go elsewhere.

The heap: a data structure you don't see

new looks like one operation. It is a call into a general-purpose allocator that is maintaining its own data structures on your behalf, and here is roughly what happens inside:

• It searches free lists or size-class bins for a block big enough. Not free — it is walking a structure whose shape depends on everything your program has allocated and freed so far.
• It may split a larger block, and write bookkeeping headers next to your memory so delete knows the size later.
• If nothing suitable exists, it asks the operating system for more — an mmap or sbrk syscall, which is a different order of cost entirely, and the fresh pages it returns will each take a page fault the first time you touch them.
• In a multithreaded program it must be thread-safe, so it takes a lock or consults a per-thread cache. Under contention that is a stall.

Why this rules out new on the hot path. The average cost is not the problem — a well-warmed allocator serves most requests in tens of nanoseconds. The problem is the distribution. Most calls are fast; occasionally one splits a block, or trips a syscall, or faults a page, or waits on a lock, and that call costs microseconds. On a path budgeted in tens of nanoseconds, a microsecond is a hundred times your budget.

That is a tail-latency argument, and it is the shape of nearly every performance argument in this book: you are not trying to make the average faster, you are trying to remove the rare disaster. An allocator you cannot predict is a rare disaster generator, and a p99.9 measurement is where it shows up. A mean will hide it completely.

Which sets up the fix: if you cannot afford unpredictable allocation, take the allocation out of the hot path entirely. Grab all the memory once, at startup, and hand out fixed-size pieces yourself in constant time. That is a pool, and it is the next chapter.

A general-purpose allocator is slow because it is general: it must serve any size, in any order, forever, from a structure that reflects everything your program has ever allocated. Drop the generality and almost all the cost disappears. Every object in the hot path here is an Order, and they are all identical in size — so you never need a search at all.

The free list, and why it costs nothing to store

Allocate one contiguous slab of N × sizeof(Order) at startup. Now you need to track which slots are free, and the trick is that you store that information inside the free slots themselves. A slot is either holding a live order, or it is free — and if it is free, its bytes are yours to use. So put the index of the next free slot in the first few bytes of each free slot, and keep one head index pointing at the first.

The result is a linked list threaded through unused memory, costing zero extra bytes. And both operations become three or four instructions with no branching on data:

// allocate: pop the head
std::uint32_t slot = free_head_;
free_head_ = next_of(slot);          // read the index stored in the slot
return &slab_[slot];

// free: push onto the head
next_of(slot) = free_head_;
free_head_ = slot;

No search. No splitting. No syscall. No lock. No bookkeeping header written beside your object. That is the whole difference between 0.96 ns and 209 ns — the 217× in this chapter is not a clever optimisation, it is the removal of work that was never necessary for this case.

Why it is also cache-friendly, which matters more than the 217×

The slab is contiguous, so orders allocated near each other in time sit near each other in memory — and per Ch 8, that means walking them pays one cache miss per line rather than one per object. A general allocator gives you no such guarantee; consecutive new calls can land anywhere. So the pool improves the average by 217× and improves the tail by removing the syscall and lock paths entirely, which is the improvement you actually care about.

Pre-faulting: paying the page cost before the market opens

Reserving address space is not the same as having memory. The first write to each fresh page takes a page fault — a trap into the kernel to map a physical page — and that is microseconds. Ten thousand orders means potentially hundreds of faults scattered through your first minute of trading.

So touch every page at construction: write one byte per page across the whole slab, once, before anything is timed. The cost is identical; you have simply moved it off the latency-critical path. This is the same reasoning as Ch 18's warm-up, and it is worth stating as a general principle: a cost you cannot remove, you relocate.

What the pool costs you, honestly

Three things, and an interviewer will ask for at least one:

• Fixed size. One pool serves one type. Fine here, useless as a general allocator.
• Fixed capacity, which forces a real decision: what happens when it is full? Reject the order is the honest answer — a real exchange has a finite book and says so. Grow the slab quietly reintroduces exactly the unpredictable allocation you built the pool to remove, so if you grow, do it at a quiet moment and never on the hot path.
• You own lifetime. The pool hands out raw storage; nothing calls constructors or destructors for you unless you do it explicitly.

The invariant that catches the bugs: a slot is either in the free list, or owned by exactly one live order — never both, never neither. Assert it in debug builds by walking the free list and checking it does not contain any slot the book believes is live. That single check catches double-free and use-after-free, which are otherwise the hardest class of bug in this whole project.

Cancellation is the most frequent operation in real order flow — cancels vastly outnumber trades — so an O(K) scan to find the order inside its price level is not a small inefficiency, it is the wrong data structure. This chapter is how you get to O(1), and the idea generalises far beyond order books.

Non-intrusive: the container owns a box around your data

std::list<Order> does not store your Order. It allocates a node containing a prev pointer, a next pointer, and your Order copied inside it. Two consequences follow, and both hurt:

• An allocation per insert, and a deallocation per erase — the exact cost Ch 6 just removed.
• An extra indirection: you hold an Order*, but the links live in a node you cannot see, so you cannot get from your order to its neighbours. To erase, the container must find the node — and finding means scanning.

Intrusive: the links live inside the object

Put the pointers in Order itself:

struct Order {
    std::int64_t price;
    std::int64_t id;
    std::uint32_t qty;
    Order* prev;      // the list lives here
    Order* next;
};

Now the object is its own node, and three things change at once. There is no allocation at all to link or unlink — the pointers already exist inside memory the pool already gave you. The order and its links share a cache line, so reaching a neighbour is one hop instead of two. And most importantly: an Order* is a complete position. Given the pointer, you know where the order sits in the queue, because the queue's structure is stored in the order.

That is what unlocks O(1) cancel. Your order_id → Order* hash map hands you the pointer directly, and from the pointer you can unlink without ever touching the level, the head, or any other order except the two neighbours.

The cancel operation: three pointer rewires

if (o->prev) o->prev->next = o->next; else level.head = o->next;
if (o->next) o->next->prev = o->prev; else level.tail = o->prev;
level.total_qty -= o->qty;

That is the entire operation: two conditional stores, plus a depth update. No search, no comparison, no allocation, no iteration. Roughly four memory writes to two cache lines. The conditionals exist only to handle the ends — if the order was the head, the level's head pointer must move instead of a predecessor's next; likewise for the tail. Forgetting either end case is the single most common bug here, and it produces a level that looks correct until you cancel the first or last order in it.

What intrusive lists cost you

• One list per link-field pair. An object with one prev/next can be in exactly one intrusive list. Two lists means two pairs of pointers, declared deliberately.
• You own lifetime. The list does not allocate, so it also does not free. Unlinking an order and forgetting to return its slot to the pool is a leak the container will not catch for you.
• Corruption hits your object. A bad rewire in a std::list corrupts the container's private nodes. Here it corrupts your Order, which is also holding a price and a quantity — so the symptom can appear as a wrong number rather than a crash.

The invariant that finds those bugs immediately: for every node in every level, x->next->prev == x and x->prev->next == x, with the head's prev and the tail's next both null. Walk each level in a debug build after every operation and assert it. This converts “the book went wrong somewhere” into “the links broke at operation 12,443,” which is a completely different problem.

Your CPU does not read individual bytes from memory. It reads fixed-size blocks called cache lines, and once you know that, several design rules that look arbitrary become obvious.

The memory hierarchy, in the only units that matter

Approximate costs, in CPU cycles, to fetch data that is already in each level:

The number to carry in your head: a miss all the way to DRAM costs on the order of a hundred times an L1 hit. This is why performance work on data structures is mostly about memory access patterns rather than instruction counts. You are not trying to do less arithmetic; you are trying to touch fewer, closer lines.

Cache lines, and the free lunch they offer

A cache line is 64 bytes on x86-64. Note carefully: Apple Silicon uses 128-byte cache lines, so a hardcoded 64 in your padding is wrong on the machine you are actually building on. Use std::hardware_destructive_interference_size rather than a literal, and verify it prints what you expect on your Mac before you rely on it.

When you touch one byte, the whole line comes into cache. So if the next thing you need is next to the thing you just read, it arrived free. If it is somewhere else, you pay again. That single asymmetry is the reason a contiguous array beats a linked structure of the same complexity class: walking an array pays one miss per line and gets several elements from it; chasing pointers pays one miss per element.

Struct layout: padding you did not ask for

The compiler inserts invisible padding so each field sits at an address that is a multiple of its own size. Field order therefore changes the size of your type:

struct Bad {           struct Good {
    std::uint8_t  side;        std::int64_t  price;    // 8
    std::int64_t  price;       std::int64_t  id;       // 8
    std::uint8_t  flags;       std::uint32_t qty;      // 4
    std::int64_t  id;          std::uint8_t  side;     // 1
    std::uint32_t qty;         std::uint8_t  flags;    // 1
};  // 40 bytes            };  // 24 bytes

Same five fields, same information, 40 bytes versus 24 — because Bad pays seven bytes of padding after each uint8_t to realign the following int64_t. Order fields largest first and the padding mostly disappears.

Why you should care about sixteen bytes: at 24 bytes you fit two orders per 64-byte line and five per 128-byte line; at 40 you fit one, and three. That is a two-to-three times difference in how many orders arrive per cache miss when you walk a price level — which is the single most frequent memory access pattern in the whole engine.

Do not estimate this — print it. Run clang -Xclang -fdump-record-layouts -c order.cpp and the compiler tells you every field's offset and exactly where the padding sits. Run it on your Order the moment you define it, reorder the fields, and run it again. The difference in total size is your first optimisation, it took four minutes, and you can explain the mechanism.

A preview you will need at rung 7

The flip side of “neighbours come along for free” is that neighbours also share a line's ownership. If two threads write to two different variables that happen to live in the same cache line, each write invalidates the other core's copy of the line, and throughput collapses even though the code is entirely correct. That is false sharing, and the fix is to pad the two variables apart so they land on separate lines. Remember that it exists; Ch 15 is where it bites.

You need to get from a price to its level on every single operation. This is the most frequently executed lookup in the engine, and the choice you make here is the one design decision that most affects your rung 6 numbers. There are three real options.

Option 1 — a tree: std::map<Price, Level>

Sorted by construction, so begin() is the touch and iteration walks levels in price order. Lookup, insert and erase are all O(log n), and it handles any price range without you thinking about it. As Ch 4 covered, the cost is one heap-allocated node per level, scattered in memory, so each of the ~10 steps of a lookup over 1,000 levels is a potential cache miss. Choose it when the price range is unbounded or unknown, or when you want obviously-correct code and are not yet optimising — which is exactly what rung 1's escape hatch says.

Option 2 — a flat array indexed by tick

Allocate one slot per possible price and index directly: levels[price - min_price]. Lookup is O(1) with a single memory access, and there is no search, no comparison, no pointer chasing. It is as fast as this problem gets.

The cost is memory, and it is worth actually computing rather than hand-waving. If a level is 64 bytes and your instrument trades between 90.0000 and 110.0000 at a tick of 1/10000, that is 200,000 ticks × 64 bytes = 12.8 MB — larger than L2, so a scan would miss constantly, but perfectly fine as a directly-indexed table where you only ever touch the few levels near the touch. Widen the range to 0–10,000 and it becomes 6.4 GB and the idea collapses.

Choose it when the price range is bounded and known in advance, which for a single instrument it usually is. This is what real matching engines do.

Option 3 — a sorted vector with binary search

Keep only the levels that exist, in a contiguous array, sorted by price. Lookup is O(log n) — the same complexity as the map — but the elements a binary search probes are close together, so it touches two or three cache lines instead of ten scattered nodes. The cost moves to insertion: adding a level in the middle means shifting everything above it, which is a memmove.

The reason that memmove is usually acceptable is a property of the domain rather than of the data structure: real order flow clusters near the touch. New levels almost always appear just inside or just outside the current best price, so the shift is short. If flow were uniformly distributed across the whole book, this option would be the worst of the three.

The decision, and the honest way to make it

Notice that every one of these is a bet about your data, not a fact about computer science. The flat array bets the range is narrow. The sorted vector bets flow clusters. The map bets you would rather not think about it yet. So write your bet down in docs/decisions/ as a claim about the data — “ticks are dense and the live range is narrow, therefore…” — and rung 6 will tell you whether the bet paid. An interviewer who knows this material is not checking whether you picked the fashionable answer; they are checking whether you know it was a bet at all.

Three structures, one job each, and the reason every operation in the summary table below is O(1) with zero allocations is that each structure removed exactly one source of work. Nothing here is clever in isolation; the composition is the design.

The three structures, and what each one buys

• Price → level. A flat array indexed by tick (or a sorted vector), from Ch 9. Removes the tree walk and its scattered cache misses. Answers “where is price P?” in one memory access.
• Level → ordered orders. An intrusive FIFO queue inside each level, from Ch 7. Enforces the time half of price–time priority, and makes unlink O(1).
• Order id → order. A hash map to Order*. Removes the search from cancel — and note it is the only structure in the engine that costs a cache miss on a typical operation, which is why the summary table says ~1 miss rather than zero.

Plus the cached BBO: the best bid and best ask kept as two plain values, updated whenever an operation could change them. That is why Get BBO costs 1.5 ns and zero misses — it does not look anything up at all. It is the single cheapest and most-called query in the system, so it is worth caching even though the flat array could answer it directly.

Walking the three operations through all three structures

Add. Take a slot from the pool (Ch 6, no allocation). If the incoming order crosses the opposite touch, match against the front of that level's FIFO until it stops crossing. Whatever remains: index the price array to get the level, link the order at the tail of its queue — tail, always, because arrival order is priority — insert into the id map, add to the level's depth, and refresh the cached BBO if this order created a new best or filled the old one.

Cancel. One hash lookup to get the Order*. Three pointer rewires to unlink it (Ch 7). Subtract its quantity from the level's depth. Return the slot to the pool. Then — and this is the step people forget — if the level is now empty and it was the touch, the cached BBO is stale and must be recomputed by scanning outward for the next non-empty level.

Execute. Reduce the front resting order's quantity. If it reaches zero, unlink it and return its slot, exactly as cancel does. Update the level's depth and, again, the BBO if the level emptied. Emit the fill at the resting order's price, per Ch 2.

The traps this composition creates

Every one of the following is a bug you will actually write, because they are all consequences of having three structures that must agree with each other:

• Stale BBO. The touch is cached, so any operation that can empty a level or create a better one must refresh it. Miss one path — usually cancel — and the book reports a touch that no longer has liquidity behind it, which makes matching loop or skip.
• Depth that drifts. A level's total_qty is a cached sum. Update it on add, cancel and partial fill, or it slowly diverges from the orders actually linked there. Prefer deriving it in debug builds and asserting the cached value matches.
• Three-way disagreement. An order can be in the id map but unlinked, or linked but returned to the pool. Each is a separate leak or a use-after-free.

Which is precisely why rung 5 exists. These are not bugs a hand-written test finds, because they need a specific interleaving of adds, cancels and fills to surface. A reference model that keeps one obvious structure instead of three cannot have them — so it disagrees with your fast engine the moment one appears, and hands you the sequence that caused it. Build the composition here; prove it there.

The results in this chapter — 1.5 ns for a BBO query, ~10 ns to add, ~12 ns to cancel, 8.9 M operations a second — are only worth anything if the measurement was honest. Microbenchmarking is unusually easy to get wrong, and every one of the traps below produces a number that looks plausible and means nothing.

Trap 1: the compiler deletes your benchmark

If nothing consumes the result of the work, the optimiser is entitled to remove the work. You measure an empty loop and report 0.3 ns per operation, and it is correct — you did nothing very quickly. The fix is to make the result observable: accumulate into a volatile sink, or use your benchmark library's do-not-optimise barrier. The sanity check is cheap and you should run it every time: double the work and confirm the time roughly doubles. If it doesn't, you are not measuring what you think.

Trap 2: measuring the clock instead of the code

This one specifically threatens the numbers above. Reading a high-resolution clock costs something — typically on the order of 20 ns, sometimes more. If a single add takes 10 ns, then timing each call individually means the timer is two-thirds of your measurement and your result is mostly noise about the clock.

The fix is to time a batch: start the clock, do a million operations, stop, divide. The per-call cost then carries the timer's cost divided by a million, which is nothing. The consequence is that you get a reliable average but lose per-operation percentiles — so if you want p99.9, you need a different technique (a cycle counter, or sampling), and you should say which you used.

Trap 3: cold start

The first few thousand iterations measure page faults, an empty cache and an untrained branch predictor — the very costs Ch 6's pre-faulting and Ch 18's warm-up exist to move. Run a warm-up pass and discard it. Report what steady state looks like, and say separately what the first message costs, because in a real system that first message is a real event.

Trap 4: the machine is not holding still

CPU frequency scaling, thermal throttling and other processes all move your numbers. Two runs of the same code can differ by tens of percent. Run long, run with the machine otherwise idle and on mains power, and repeat the whole benchmark rather than trusting one execution. On Apple Silicon also be aware that the scheduler can place you on an efficiency core, which will quietly halve your results.

Trap 5: reporting a mean

An average hides exactly the events that matter. One operation in a thousand at ten microseconds barely moves a mean and completely defines what a user experiences. Report p50, p99 and p99.9. A mean is the number you quote when you have not looked at the distribution, and an interviewer will read it that way.

The question those two numbers invite — be ready for it

Add costs ~10 ns, and throughput is 8.9 M ops/sec. Those are not the same claim: 10 ns per operation would imply 100 M/sec if the operation were all there was. Be able to explain the gap. The microbenchmark times one call into the book; the throughput figure measures the whole path — parsing, dispatch, the ring handoff, the loop itself. Both are true and they measure different things. An interviewer who spots the discrepancy is testing whether you know what your own harness measured, and “the 10 ns is the matching call, the 8.9 M is end-to-end” is a complete answer. Not knowing is the failure, not the discrepancy.

Which is why the mindset in this chapter is the whole chapter: measure, understand, fix, measure again — with understand carrying the weight. A before/after pair you cannot explain mechanically is a coincidence you are taking credit for.

The instinct from web development is to make each component a service and put a network between them. That instinct is right for web systems and catastrophic here, and it is worth being able to say why in numbers rather than as a preference.

What an HTTP request actually costs

Count the work in one request, none of which is your logic:

• Connection setup — a TCP three-way handshake, and a TLS handshake on top if secured. Amortised by keep-alive, but not free.
• Text parsing. HTTP headers are text with case-insensitive keys and variable whitespace. Then the body is usually JSON, which means parsing numbers out of decimal strings and allocating for every field.
• Serialisation on both sides. Your struct becomes text, and text becomes their struct.
• Syscalls and copies. Each send and recv is a trap into the kernel, and the data is copied between your buffer and kernel buffers.
• Scheduling. The receiving process has to be woken, which means a context switch, which means its caches are cold when it starts.

Put an order of magnitude on it: an HTTP round trip on the same machine is typically tens to hundreds of microseconds. A direct function call is a few nanoseconds. That is a factor of roughly 10³ to 10⁵. Against a book that adds an order in ~10 ns, a single localhost HTTP hop costs more than ten thousand operations.

The conclusion is not “HTTP is bad.” It is arithmetic: you cannot put a network between two components that must be fast, because the network costs more than the components do.

The pipeline model

So the architecture inverts. Instead of services connected by networks, you have one process containing stages connected by function calls, shared memory and lock-free queues. The network exists at exactly two places — data arriving from the exchange, and orders going out — and those are unavoidable because the exchange is genuinely somewhere else.

Everything in between is in-process by construction. A stage hands work to the next by writing to a ring buffer in shared memory; no serialisation, because both sides are the same program and agree on the layout; no syscall, because nothing crosses into the kernel; no copy beyond the one write.

The trade you are making, stated honestly

This is where the answer becomes senior rather than dogmatic, because a monolithic pipeline gives up real things:

• Independent deployment. One process means one release. You cannot restart the parser without restarting the matcher.
• Language independence. Shared memory needs an agreed memory layout, which in practice means one language.
• Independent scaling. You cannot run twelve parsers and one matcher; you scale the whole process or nothing.
• Fault isolation. A segfault in the decoder takes the matching engine with it. Services would have contained it.

Web systems accept microseconds of overhead to buy every one of those properties, and they are right to — their latency budget is tens of milliseconds, so a 200 µs hop is a rounding error. Here the budget is tens of nanoseconds and the same hop is the entire system. Same reasoning, opposite conclusion, because the budget differs by six orders of magnitude. Being able to say that is the difference between having read about HFT architecture and understanding why it looks the way it does.

Everything below the fold in this chapter is stated correctly and compressed hard. Here is the same content derived rather than asserted, because “understand every word” is only possible if each word was explained once.

Free-running counters — and why they are never reset

head and tail only ever increase. Not once, ever, are they wrapped or zeroed by your code. The producer writes a slot then increments tail; the consumer reads a slot then increments head. Wrapping happens only when you index, never when you store.

That sounds wasteful and is the source of all three of the design's nice properties, so it is worth the paragraph. With 64-bit counters at 100 million operations per second, you would need something like five thousand years to overflow, so overflow is not a practical concern. And even if it were, unsigned arithmetic wraps modulo 2⁶⁴, so tail - head stays correct across the wrap as long as the real difference is smaller than 2⁶⁴ — which it is, because it can never exceed the capacity.

The mask: one identity, not a topic

counter & (Capacity - 1) is the whole trick, and it is a single fact about binary numbers. Take a capacity of 1024. Then Capacity - 1 is 1023, which in binary is 0b1111111111 — ten ones. ANDing with it keeps the low ten bits and discards every bit above them. Discarding the high bits is exactly what dividing by 1024 and taking the remainder does. So:

counter & (Capacity - 1)   ==   counter % Capacity     // powers of two ONLY

It is used because an AND is a single cycle and an integer division is tens of them. And the “powers of two only” caveat is the reason capacity is not a free choice: with capacity 1000, 999 is 0b1111100111 and the identity collapses. Assert it in the constructor: static_assert((Capacity & (Capacity - 1)) == 0).

Size = tail − head, and the property it buys you

Because both counters only ever increase, their difference is the number of items in flight. There is no separate count to keep in sync, which deletes a whole family of bug. Empty is tail == head; full is tail - head == Capacity.

This is the real payoff, and it is easy to miss: full and empty are distinguishable. If you had instead stored wrapped indices — incrementing modulo capacity, as the naive design does — then a full buffer and an empty buffer would both show head == tail and be indistinguishable. The usual workarounds are to waste a slot, or to keep a separate size counter that both threads must update, which reintroduces shared mutable state into a design whose whole point is not having any. Free-running counters make the problem disappear instead of solving it.

Memory ordering: what “reordering” actually is

Two separate things reorder your memory operations, and it helps to keep them apart. The compiler reorders at compile time, because as far as it can tell nothing observes the difference. The CPU reorders at run time — it executes out of order, and stores drain from a buffer in an order that is not necessarily program order. Both are invisible in single-threaded code, and both are catastrophic across two threads.

The concrete failure: the producer writes the message into the slot, then publishes the new tail. If those two become visible to the other core in the opposite order, the consumer sees a tail saying “there is a message” and then reads a slot that is still half-written. Nothing crashes. You process a message that never existed.

A happens-before edge is the guarantee that forbids exactly this, and here is what it means operationally rather than formally: if the producer's release-store is what the consumer's acquire-load read, then everything the producer wrote before that store is visible to the consumer after that load. That is the entire contract, and it is why the pairing matters — a release with no matching acquire guarantees nothing.

So the code, with every ordering justified:

bool try_push(const T& v) {
    const auto t = tail_.load(std::memory_order_relaxed);  // I am the only writer of tail
    const auto h = head_.load(std::memory_order_acquire);  // published by the consumer
    if (t - h == Capacity) return false;                   // full

    slot_[t & MASK] = v;                                   // 1. write the payload
    tail_.store(t + 1, std::memory_order_release);         // 2. publish it -- AFTER (1)
    return true;
}

bool try_pop(T& out) {
    const auto h = head_.load(std::memory_order_relaxed);  // I am the only writer of head
    const auto t = tail_.load(std::memory_order_acquire);  // published by the producer
    if (t == h) return false;                              // empty

    out = slot_[h & MASK];                                 // 3. read the payload
    head_.store(h + 1, std::memory_order_release);         // 4. free the slot -- AFTER (3)
    return true;
}

Why relaxed on your own counter is safe: you are its only writer, so no other thread can surprise you with a value, and you need no ordering guarantee against yourself. This is the single-writer property doing the work — and it is why SPSC is the easy case.

Why the release on head_ in try_pop is not optional: it stops the producer overwriting a slot the consumer is still reading. Step 3 must be visible before step 4 advertises the slot as reusable. Both directions need the pairing, not just the publish direction — which is the detail people drop.

Why not just use seq_cst everywhere?

Because on your machine it costs real instructions. On x86-64 the hardware is already strongly ordered, so acquire loads and release stores compile to plain loads and stores — acquire/release is free and only sequential consistency needs a fence. ARM64 is weakly ordered: acquire becomes ldar, release becomes stlr, and sequential consistency adds dmb barriers on top. So on Apple Silicon, reaching for seq_cst out of caution is a measurable cost for a guarantee this design does not need. Put both versions into Compiler Explorer with an ARM64 target and read the difference — it is a five-minute experiment and it makes the whole topic concrete.

ABA, so the phrase is not a mystery

The chapter says multi-producer needs CAS and has an ABA problem. Briefly: with compare-and-swap you read a value, compute a new one, then swap only if the old value is unchanged. Thread A reads head pointing at node X and stalls. Other threads pop X, push several things, and eventually push X back. A wakes, compares, sees X, and succeeds — even though the structure changed completely underneath it. The value went A, then B, then A again, so the comparison cannot tell. Fixes involve version tags or hazard pointers, and they are genuinely harder.

With SPSC, each counter has exactly one writer, so there is no compare-and-swap at all, and therefore no ABA. Knowing why SPSC avoids the problem, rather than knowing that it does, is the answer that lands.

One correction for your machine, in the false-sharing code

The alignas(64) below is right on x86-64. Apple Silicon uses 128-byte cache lines, so 64 bytes of alignment may leave head_ and tail_ on the same line and you will still get the ping-pong you were trying to avoid. Prefer std::hardware_destructive_interference_size, and then verify: print it on your Mac, and if your standard library reports 64, pad to 128 explicitly. Do not trust the constant without printing it — and either way, prove the padding worked with a before/after throughput number rather than by inspection.

The thread topology, and why it is exactly two

The receive thread does one thing: pull datagrams off the socket, decode them in place, and push them into the ring. The matching thread does one thing: drain the ring and apply each message to the book. Nothing else runs on either.

Two, not more, for a reason worth stating: the book has exactly one writer. That is what removes every lock and every atomic from the matching path, and it is also what makes rung 4's deterministic replay achievable — two threads mutating one book would interleave differently on every run and destroy reproducibility. So parallelism goes across instruments (a book each, a thread each) and never inside one book. Adding threads to a single book is the one optimisation that cannot work.

The matching thread's rule follows from the same logic and is absolute: it must never do anything that can block. No allocation (Ch 6), no logging (Ch 18), no syscall, no lock. Its single-threadedness is fast because nothing can stop it, not merely because nothing contends with it.

Sizing the socket, and the platform detail that will bite you

The kernel holds arriving datagrams in a receive buffer. When a burst arrives faster than you drain, that buffer fills and the kernel discards datagrams silently — there is no error returned to you, because UDP promises nothing. So enlarge it deliberately with SO_RCVBUF, and know that the OS may cap what it grants you: set it, then read it back with getsockopt and log the value you actually received rather than the one you asked for.

On the batching side, Linux offers recvmmsg to collect many datagrams in one syscall. macOS does not have it — you have recvmsg and a loop. Build on the Mac, so plan for the loop and do not copy a Linux feed handler's structure expecting it to compile.

Gap detection: the counter that makes loss honest

Because loss is permitted, the application must detect it. Every real feed numbers its messages, so you keep the last sequence you saw and check:

if (seq != last_seq_ + 1) {
    gaps_ += (seq - last_seq_ - 1);   // how many vanished
    gap_events_++;                    // how many times it happened
}
last_seq_ = seq;

Two counters, not one, and the distinction matters: how many messages were lost tells you about volume, how many separate gap events tells you whether you are seeing steady low-level loss or occasional catastrophic bursts. Those have different causes and different fixes. Exposing both, and printing them, is the honest instrument — and it is exactly why exchanges run a separate gap-recovery channel: detection is your job, and recovery needs a second path because the first one already failed.

Pinning, and why you should care less about it on this machine

On Linux you would pin each thread to a dedicated core so the scheduler cannot migrate it and throw away its warm caches. macOS gives you no equivalent hard affinity API — you can express quality-of-service hints, and the scheduler decides. In practice that means keep the machine idle, stay on mains power, run at a normal QoS so you are not placed on an efficiency core, and accept that your tail numbers will be noisier than a tuned Linux box's. Say so in the README rather than pretending otherwise; a stated limitation reads as competence, and an unexplained noisy p99.9 reads as carelessness.

Read the tool table below with one correction in mind: perf and cachegrind are Linux tools, and you are building on a Mac. The method in this chapter is exactly right; the instruments are not the ones you have. Here is the same workflow in tools that actually run on Apple Silicon, plus what the numbers mean.

The macOS equivalents

One trap worth naming: running Linux perf inside Docker on your Mac will not save you. Docker Desktop runs a Linux VM, and hardware performance counters are generally not exposed to a guest, so perf stat there reports software events at best and nothing useful at worst.

Memory-bound or compute-bound? The two numbers that tell you

This is the chapter's “first look” question, and it has a concrete answer. Get instructions and cycles from CPU Counters and divide:

• IPC below ~1 — the core is retiring less than one instruction per cycle, so it is stalled most of the time. You are memory-bound. Look at layout, locality and allocation.
• IPC above ~2 — the core is busy doing actual work. You are compute-bound. Look at algorithm and instruction count.

Then confirm with the cache-miss counters: a high last-level-cache miss rate per instruction corroborates memory-bound. For this project the answer will almost always be memory-bound, which is why Ch 6, 7, 8 and 9 are all about layout rather than cleverness — but measure it rather than assuming it, because assuming is how you spend a weekend optimising the wrong half.

How to actually read a profile

Three rules that stop the common misreadings:

• Width is time; depth is not cost. A deep stack is not expensive because it is deep. Look for wide frames — a wide plateau is where the samples landed.
• The horizontal axis is not time order. Frames are merged and sorted for legibility, so you cannot read a timeline off a flame graph. If you need ordering, you need a trace, not a profile.
• Use the inverted view to find leaves. The top-down tree tells you who called what; the inverted tree aggregates by leaf function and tells you where the cycles actually went. The second is usually the one that answers your question.

The A/B substitute, for when you have no cachegrind

You cannot simulate cache behaviour per line, so falsify the hypothesis by changing exactly one thing and measuring:

1. Write the hypothesis down, with a predicted direction and rough size. “Reordering Order's fields drops it from 40 to 24 bytes, so a level walk should touch about half the lines and p99 should improve by 20–40%.”
2. Confirm the mechanism independently — here, clang -Xclang -fdump-record-layouts proves the size actually changed.
3. Change only that. Measure. Compare percentiles, not means.
4. Record the result even when you were wrong, which is rung 6's gate and better interview material than a success.

This is weaker than a cache simulator and it is strictly honest, which counts for more. And it forces the prediction step, which is where the understanding lives.

The jitter lesson, sharpened for your situation

The callout below is the most valuable paragraph in this chapter and it was learned the hard way: the multi-millisecond maximum was the hypervisor, not page faults. Take the general form seriously — the median and p99 are yours to optimise; the far tail belongs to the machine.

On macOS you have none of the mitigations it lists. No isolcpus, no taskset, no tickless kernel, no IRQ affinity, and the scheduler may place you on an efficiency core whenever it likes. The practical consequences, which belong in your README rather than being discovered by a reader:

• Report p50, p99 and p99.9. Do not report a maximum, and do not chase one — on this machine the max is a measurement of macOS, not of your engine.
• State the environment next to the numbers: the machine, that it was idle, on mains power, at default QoS. A stated limitation reads as competence; an unexplained noisy tail reads as carelessness.
• Keep the runs long and repeat them. One execution on a laptop is an anecdote.

And the thing to say if an interviewer pushes on it: “I optimised what the machine let me control, measured percentiles rather than a max, and documented why the far tail is environmental — on a tuned Linux box with core isolation I'd expect the p99.9 to tighten considerably.” That answer is stronger than a suspiciously clean number, because anyone who has done this work knows laptops do not produce clean tails.

Backpressure: what to do when the ring is full

The chapter above stops at the interesting question, so here it is. A bounded queue will fill, and you must choose in advance what happens then. There are exactly three policies, and the right one depends on what the data is:

• Drop the oldest. Correct for market data, because the value is perishable — a price from 40 microseconds ago is worse than useless, it is misleading. Overwrite it and increment a counter.
• Reject the newest, with an error to the sender. Correct for order entry, because an order is not perishable and must never be silently discarded. The client is told “not accepted” and can decide.
• Block until space appears. Almost never correct here, and it is the tempting default. It converts a capacity problem into a latency problem and propagates the stall backwards into the receive thread, which then drops datagrams in the kernel where you cannot see it. You have not solved anything; you have moved the failure somewhere unobservable.

The general principle, and it is the useful part: a full queue is a decision, not an error. Systems that treat it as an error end up blocking, and systems that block turn a bounded problem into an unbounded one.

Observability that costs nothing

You cannot log on the hot path, but you must know what happened. The resolution is that counters are not logs. A plain integer incremented in the processing loop — orders accepted, orders rejected, gaps detected, ring-full events, pool exhaustions — costs one increment to memory. No formatting, no allocation, no lock, no I/O.

A second, low-priority thread reads and reports them. It needs no synchronisation beyond relaxed atomics, because a counter read a few nanoseconds late is still true — you are looking at a rate over seconds, so tearing on an individual read simply does not matter. This is the rare place where the weakest possible ordering is not merely adequate but correct.

The same structure handles the events you genuinely need detail for: the hot path writes a small fixed-size record into a ring, and the drain thread formats it. The trading thread touches no I/O, ever.

Startup and shutdown, as states rather than moments

Both are the parts that separate a benchmark from a system, and both are ordered sequences you should be able to recite:

Startup: allocate the pool and pre-fault every page; size and verify SO_RCVBUF; join the multicast group; run a warm-up pass through the matching path with synthetic messages and discard the results; only then begin accepting real traffic. Every one of those exists to move a first-message cost off the live path.

Shutdown: the producer sets a done flag with release ordering and stops writing. The consumer, seeing the flag with acquire ordering, drains the remaining ring entries and only then exits. That order is the entire point: draining is a state you pass through, not a signal you handle. A shutdown that exits on the flag loses every message still in flight — which, for order entry, means losing orders you already told the client you had accepted.

What “hardened” actually means

Not “faster” and not “has more features”. It means the system behaves predictably at its edges: the first message, the last message, the overload, the missing packet, the exhausted pool. A benchmark only ever exercises the middle. Everything in this chapter is about the fact that production is mostly edges, and that each edge should have a named policy and a counter rather than an accident.

You have a single-instrument matching engine that is correct, measured and fast. Here is what a production exchange has that this does not — stated precisely, because naming your gaps exactly is a senior signal, and a README that implies completeness is a red flag. An interviewer will trust the numbers more if the limitations are specific.

Cheap to add — more of the same shape

• Multiple instruments. A book per symbol, a thread per book, a hash from symbol to book. Genuinely easy, because the single-writer rule already holds per book — which is the design paying off rather than being worked around.
• Order modify (cancel-replace). One real decision inside it: does reducing quantity keep time priority, or lose it? Real exchanges keep priority on a reduction and lose it on a price change or a size increase. Implementing that rule is small; knowing it exists is the point.
• Self-trade prevention. Refuse to match two orders from the same participant. A check in the matching loop, and a policy question about which side gets cancelled.
• Pre-trade risk checks. Position limits, maximum order size, price collars — a fixed set of comparisons before the order reaches the book. Cheap, and the reason exchanges are not obligated to accept anything sent to them.

Architecturally significant — these change the design

• Persistence and recovery. Rung 4's event log is most of the answer already, which is the best argument for having built it: recovery is replaying the log. What it does not give you is bounded recovery time, so real systems add periodic snapshots and replay only the tail.
• The opening auction. Orders accumulate without matching, then one uncross computes the single price maximising executed volume and fills everything crossing it. This is a genuinely different algorithm from continuous matching, not a variation on it — and it is a favourite interview question precisely because it tests whether you understand matching as a rule rather than as a loop.
• Market data publication. Publishing every book change to thousands of subscribers is a fan-out problem, and it introduces conflation: a slow subscriber should receive the current state, not a backlog of stale states. That is the drop-oldest policy from Ch 18, applied per subscriber.
• Multi-process and sharding. Once one machine is not enough, sequencing across shards becomes the hard problem — and it is exactly the ordering question Ch 15 asks, at a different scale.
• The audit trail. Regulators require a reconstructable record of every message and decision, with timestamps of specified accuracy. It constrains logging, clocks and retention, and it is the reason real engines are event-sourced whether they wanted to be or not.

What to write in the README instead of “done”

List the four or five limitations you most consciously chose — single instrument, no auction, no risk checks, fixed pool capacity that rejects rather than grows, replay without snapshots — and for each one, a clause saying why it was the right call for this scope. That paragraph does more for you than another optimisation would. It demonstrates that you know where the edges of your own system are, which is the actual thing being assessed when someone asks about a project you built.