Decoupled Vector-Map Data Layout for Allocation-Free Limit Order Book
How I Learned to Understand How an Order Book Stores Data
A complete guide to how a Limit Order Book organizes orders in memory, written from the perspective of someone who was confused, asked a lot of questions, and slowly figured it out.
A Limit Order Book is the core of every stock exchange. It holds all the buy and sell orders waiting to be matched. The challenge is not the matching logic itself. The real challenge is storing and retrieving hundreds of thousands of live orders fast enough to handle millions of events per second.
A plain list fails because finding the best price requires scanning every order, and deleting an order from the middle forces everything else to shift. Both operations are too slow for a real exchange.
One approach which I explored in this article is a three-layer architecture. A Memory Pool is a pre-allocated flat array of order slots that eliminates all operating system memory calls during trading. A Price Map is a sorted binary tree that indexes only the distinct price levels, giving instant access to the best bid and ask. An Order Directory is a flat lookup table that maps any OrderID to its exact pool slot in one step, enabling instant cancellations.
Inside the Memory Pool, orders at the same price are connected by a doubly linked list built from next_idx and prev_idx fields stored as uint32_t indices rather than raw 64-bit pointers, cutting link memory cost in half and fitting more orders into CPU cache per cache line.
When an order is cancelled, the system never shifts any data. It heals the chain by relinking neighbours, returns the freed slot to a Free List for immediate reuse, and updates the Price Map boundaries if the head or tail changed. The entire operation touches only a handful of integers and completes in O(1) time.
It is worth noting that this design makes deliberate trade-offs. The fixed pool size means memory is reserved even when most slots are idle. The std::map for price levels still performs tree allocations on the heap. Other systems solve the same problem differently — some use lock-free ring buffers, some use hash maps for price lookup, and some use entirely custom allocators. This architecture is a solid and well-understood starting point, but memory management in high-frequency trading is an active area with many valid approaches, and what works best depends heavily on the hardware, the market, and the load profile.
This article walks through every concept, every operation, and every failure case with full three-layer memory snapshots after each step.
Table of Contents
1. Introduction
When I first started learning about how a stock exchange works, I thought the storage part would be easy. "Just keep a list of buy orders and a list of sell orders. When prices match, execute the trade." That sounded simple.
Then I started asking the deeper questions. How does the exchange find the best price when there are 500,000 live orders? If I cancel an order in the middle of the book, how does the system find it instantly without scanning everything? If I delete an order from a list and the list must stay compact, doesn't everything shift? How can this possibly run millions of times per second?
Every answer led to a new question, and the deeper I went, the more I realised the real challenge is not the trading logic. The real challenge is how the order book stores and retrieves data inside the computer's memory. Everything else follows from getting that right.
This article is the explanation I wish I had at the start. It covers only the order book and specifically how order book data is stored, accessed, and managed inside memory. No other topics are mixed in.
No prior experience is required beyond knowing what an array is.
2. The Problem: Why Naive Storage Fails in an Order Book
The Order Book's Job
An order book holds two sides. The buy side holds all orders from traders who want to buy a stock. The sell side holds all orders from traders who want to sell the same stock. Every order has a price and a quantity.
When a new order arrives, the exchange checks if any existing order on the opposite side matches. If a buyer offers $100 and a seller asks $100, they match and a trade executes. If no match exists, the new order is stored in the book and waits.
At any given moment a real order book for a single stock might hold tens of thousands of live orders, and thousands more arrive and cancel every second.
What Breaks in a Simple List
The most natural thing to try is a plain list:
Plain list of all orders:
Position 0: Order 501, Buy, 10 shares at $100.00
Position 1: Order 502, Sell, 20 shares at $101.00
Position 2: Order 503, Buy, 5 shares at $100.00
Position 3: Order 504, Sell, 15 shares at $99.50
Position 4: Order 505, Buy, 30 shares at $100.00
...
Problem 1: Finding the best price requires scanning the entire list. If there are 50,000 orders, you must check all 50,000 to find the cheapest seller or the highest buyer. Computer scientists call this O(N) — the time taken grows with the number of orders. At high volumes, this makes the engine completely unusable.
Problem 2: When a trader cancels an order at position 2, a standard list must physically slide positions 3, 4, 5 and every order after it one slot to the left to close the gap. If there are 50,000 orders and the cancellation is near the front, you move almost 50,000 items. This is called an O(N) deletion. During busy market hours, when thousands of cancellations arrive every second, this destroys performance.
Problem 3: When the list fills up completely, a standard dynamic list asks the operating system for a larger block of memory, copies every single order into that new block, and frees the old block. This "stop the world" moment can freeze the matching engine for milliseconds at the worst possible time.
These three problems together make naive storage completely unworkable for a serious order book. The solution is a combination of a memory pool, an index based linking system, and a sorted price map working as three layers.
3. Core Concepts
3.1 What is a Vector?
Simple definition: A vector is a list that stores all its items in one continuous block of memory. Every item sits immediately next to the previous one. There are no gaps, no scattered addresses.
Why it matters for the order book: The CPU does not read one byte at a time. It reads memory in chunks called cache lines, typically 64 bytes at once. When you access one slot in a vector, the CPU automatically loads the next several slots into its fast scratchpad (the cache) for free. This is called spatial locality, and it makes sequential access through a vector extremely fast.
Real life analogy: A row of school lockers numbered 0 through 999. Every locker is bolted right next to the previous one. If you want locker 7, you walk directly to position 7. You do not check lockers 0 through 6 first. And because the lockers are side by side, if you open locker 7 and then need locker 8, locker 8 is already right there.
What the data looks like in memory:
Memory address (bytes): 100 104 108 112 116
Value stored: 10 20 30 40 50
When CPU reads address 100, it also pre-loads 104, 108, 112, 116 automatically.
Reading 20 (address 104) afterward costs almost nothing because it is already in cache.
The strength of a vector: accessing any slot by its number is instant. The CPU calculates the address as:
Address of slot N = Base address + (N * size of one slot)
Example: If base is 100 and each slot is 4 bytes:
Slot 0 = 100 + (0 * 4) = address 100
Slot 7 = 100 + (7 * 4) = address 128 (found instantly, no searching)
The weakness of a vector in standard use: if you delete an item from the middle and want no gaps, every item after it must shift. We will solve this problem completely in the order book design.
Learn more: https://en.wikipedia.org/wiki/Array_data_structure
3.2 Array Index Mapping
Simple definition: Instead of storing full memory addresses (like the number 0x7fff5fbff61a) to link one order to another, we store simple slot numbers (like 0, 1, 2, 3). We call these slot numbers "indices." We use an index to point from one order to the next.
Why it matters: In a 64-bit computer, a raw memory pointer takes 8 bytes of storage. A slot index stored as a uint32 takes only 4 bytes. That is half the size.
This matters enormously in an order book. If you have one million active orders and each order stores two links (a "next" link and a "previous" link), the difference is:
Using raw pointers (8 bytes each):
2 links * 8 bytes * 1,000,000 orders = 16,000,000 bytes = 16 MB
Using uint32 indices (4 bytes each):
2 links * 4 bytes * 1,000,000 orders = 8,000,000 bytes = 8 MB
Savings: 8 MB per million orders.
The CPU cache is typically 4 to 8 MB. Saving 8 MB means significantly more order data fits in cache at once, which directly reduces cache misses and speeds up the engine.
Real life analogy: When you write a note to a friend in the same building, you do not write their full street address. You just write their room number. "Room 42" is shorter than "42nd floor, East Tower, 123 Main Street, New York, NY 10001." Both get the message delivered. The room number is more efficient.
What this looks like in code:
struct OrderNode {
uint32_t order_id; // The unique ID assigned to this order
uint32_t qty; // How many shares this order is for
uint32_t price; // The price this order is at
uint32_t next_idx; // Slot number of the NEXT order at this price
uint32_t prev_idx; // Slot number of the PREVIOUS order at this price
};
When next_idx holds the value 9, it means "the next order in this price queue is sitting at slot 9 of the memory pool." The CPU finds it with one math operation: base address plus 9 times the size of one OrderNode. No searching required.
Learn more: https://en.wikipedia.org/wiki/Pointer_(computer_programming)
3.3 Why uint32 Is Enough and Why It Matters
This is the question I had when I first saw uint32 used for indices. Is 32 bits really enough? Could we run out of slot numbers?
A uint32 can hold any value from 0 to 4,294,967,295. That is over 4.2 billion distinct slot numbers.
In a typical high frequency trading order book, you might pre-allocate space for 1 to 10 million simultaneously active orders. That is far below the 4.2 billion limit of uint32. A slot index will never reach a value that uint32 cannot hold.
Let us look at the actual numbers in detail:
uint8 (1 byte): holds values 0 to 255
Maximum pool size: 256 orders.
This is NOT enough. Even a small exchange has more than 256 live orders.
uint16 (2 bytes): holds values 0 to 65,535
Maximum pool size: 65,536 orders.
This is borderline. Some small systems might fit, but busy exchanges would overflow.
uint32 (4 bytes): holds values 0 to 4,294,967,295
Maximum pool size: over 4 billion orders.
This is more than enough. Real order books use 1 to 10 million slots, well within range.
uint64 (8 bytes): holds values 0 to 18,446,744,073,709,551,615
Maximum pool size: over 18 quintillion orders.
This is excessive. Using this doubles the memory cost of every index link compared to uint32.
The reason uint8 is not sufficient is clear from this table. Even 65,535 (the uint16 limit) would be too small for a real exchange. uint32 at 4 billion gives massive headroom. uint64 is wasteful for this purpose.
Why does choosing the right size matter?
Memory cost of next_idx and prev_idx across 1 million order slots:
Using uint8 (1 byte each): 2 * 1 byte * 1,000,000 = 2,000,000 bytes = 2 MB
BUT: can only address 256 slots. Useless.
Using uint16 (2 bytes each): 2 * 2 bytes * 1,000,000 = 4,000,000 bytes = 4 MB
But: limited to 65,536 slots. Not enough.
Using uint32 (4 bytes each): 2 * 4 bytes * 1,000,000 = 8,000,000 bytes = 8 MB
Addresses 4 billion slots. Perfect for order books.
Using uint64 (8 bytes each): 2 * 8 bytes * 1,000,000 = 16,000,000 bytes = 16 MB
Addresses 18 quintillion slots. Wastes 8 MB compared to uint32 for no benefit.
A CPU cache line holds 64 bytes. One OrderNode using uint32 for all fields:
OrderNode with uint32 fields:
order_id: 4 bytes
qty: 4 bytes
price: 4 bytes
next_idx: 4 bytes
prev_idx: 4 bytes
Total: 20 bytes per order
Orders per cache line: 64 / 20 = 3.2, so about 3 orders per cache line.
If we used uint64 for next_idx and prev_idx instead:
OrderNode with uint64 links:
order_id: 4 bytes
qty: 4 bytes
price: 4 bytes
next_idx: 8 bytes
prev_idx: 8 bytes
Total: 28 bytes per order
Orders per cache line: 64 / 28 = 2.2, so about 2 orders per cache line.
By using uint32 instead of uint64 for our indices, we fit 3 orders per cache line instead of 2. When the CPU traverses the order queue, it loads 3 orders at once instead of 2. Over millions of operations per second, this difference is measurable in nanoseconds per trade.
The conclusion: uint32 is sufficient because 4 billion is far more slot numbers than any real order book will ever need. It is efficient because it cuts the memory cost of every index link in half compared to uint64, allowing more orders to fit in CPU cache simultaneously.
Learn more: https://en.wikipedia.org/wiki/Integer_(computer_science)
3.4 Memory Pool
Simple definition: A memory pool is a large block of memory that your program asks the operating system for exactly once, at startup. You divide this block into fixed size slots. Your program manages slot assignments itself, instead of asking the operating system every time a new order arrives.
Why it matters for the order book: In a normal program, when you want to store a new object, you call a function like new or malloc. This asks the operating system to find you a free block of memory. The OS must search its own internal tables, which takes unpredictable time, often hundreds to thousands of nanoseconds. If a matching engine does this for every incoming order, latency spikes appear at random moments during the trading day. These spikes cause the engine to miss price moves.
A memory pool eliminates all of this. At 8 AM before the market opens, the engine asks the OS for a single large block, big enough to hold one million order slots. The OS gives it. For the rest of the day, the engine never asks the OS for memory again. It just assigns and recycles slots within this pre-owned block.
Real life analogy: A hotel builds 1,000 rooms before the doors open. When guests arrive, the receptionist assigns them existing rooms instantly. If the hotel had to construct a new room every time a guest arrived, the first guest would wait hours. The rooms are pre-built. The memory pool is pre-built.
What this looks like in code:
// At startup, reserve space for 1 million order nodes all at once
std::vector<OrderNode> node_pool(1000000);
// This one line asks the OS for memory ONCE.
// During trading, no OS call is ever made again for order storage.
The pool has a fixed size. It never grows. It never shrinks. Slots are assigned to new orders and returned when orders are cancelled or executed. The total number of simultaneously active orders must stay below the pool size, but because orders are constantly being matched and cancelled, the same million slots can handle billions of orders over the course of a trading day.
Learn more: https://en.wikipedia.org/wiki/Memory_pool
3.5 Free Index List
Simple definition: The Free Index List (also called the Free List) is an internal chain that tracks which slots in the memory pool are currently empty and available for new orders. It is the mechanism that lets the engine find an empty slot in O(1) time without scanning the pool.
Why it matters: After thousands of orders have been placed and cancelled, the pool will have empty slots scattered at various positions. Without the Free List, finding an empty slot would require scanning the entire pool until a gap is found, which is O(N). The Free List makes this O(1) by maintaining a ready chain of available slot numbers.
How it works: The Free List reuses the next_idx field inside each empty slot. Since an empty slot has no active order, its next_idx is repurposed to point to the next empty slot in the chain. A single integer called next_free_idx points to the first slot in this chain.
Real life analogy: The hotel receptionist has a notepad on the desk. The notepad lists available rooms in order: "Room 3, then Room 7, then Room 12." When a guest arrives, the receptionist gives them Room 3 and updates the notepad to start from Room 7 next. When a guest checks out of Room 5, the receptionist adds Room 5 to the top of the notepad. No one walks through the hallways checking door handles.
What this looks like at startup:
All slots are empty. They form one long chain through next_idx:
next_free_idx = 0
pool[0].next_idx = 1
pool[1].next_idx = 2
pool[2].next_idx = 3
pool[3].next_idx = 4
pool[4].next_idx = INVALID (end of the free chain)
Reading this aloud: "The first free slot is 0.
After 0 is used, the next free is 1.
After 1 is used, the next free is 2.
After 2 is used, the next free is 3.
After 3 is used, the next free is 4.
After 4 is used, there are no more free slots (INVALID)."
Allocating a slot for a new order:
Step 1: Read next_free_idx. It says 0.
Step 2: Save that value: new_slot = 0
Step 3: Read pool[0].next_idx. It says 1.
Step 4: Set next_free_idx = 1 (advance the free chain head)
Step 5: Write the new order data into pool[0]
Result: next_free_idx is now 1. pool[0] holds the new order.
Time taken: O(1). No scanning. No searching.
Returning a cancelled slot to the Free List:
Order in Slot 1 is cancelled. We want to make Slot 1 available again.
Current state: next_free_idx = 3 (meaning Slot 3 is the current first free slot)
Step 1: pool[1].next_idx = next_free_idx (Slot 1 now points to Slot 3)
This is critical. We link Slot 1 into the chain BEFORE moving the head.
If we moved the head first, we would lose Slot 3 from the chain forever.
Step 2: next_free_idx = 1 (Slot 1 is now the first available slot)
Result: Free chain is now 1 -> 3 -> (whatever was after 3)
Time taken: O(1). Two integer assignments.
The order of these two steps matters. Always link the slot into the chain first, then update the head pointer. Doing it in reverse order causes the Free List to lose all slots that were previously in the chain.
Learn more: https://en.wikipedia.org/wiki/Free_list
3.6 Memory Fragmentation
Simple definition: Fragmentation is the condition where the memory pool has many empty slots, but those empty slots are scattered in between active order slots. The pool has enough space for new orders, but the space is broken into individual pieces across the pool.
Why it matters in traditional systems: Programs that ask the OS for memory every time they need storage can end up with hundreds of small scattered allocations. Over hours, the OS's own memory map becomes fragmented. Even if there are 500 MB of total free memory, the OS might not be able to find one contiguous 100 MB block. The program then fails to allocate even though there is technically "enough" memory.
Why fragmentation is mostly harmless in our order book design: Our pool is pre-allocated as one large contiguous block and never grows or shrinks. Individual orders each need exactly one slot. A slot does not need to be adjacent to other slots of the same price level, because the doubly linked list (through next_idx and prev_idx) connects them logically regardless of physical position. The Free List finds available slots instantly regardless of where they are in the pool.
What fragmentation looks like in our pool:
After many orders placed and cancelled, the pool looks like this:
Slot 0: EMPTY (in Free List)
Slot 1: Order 502, Buy at $100.00
Slot 2: EMPTY (in Free List)
Slot 3: Order 705, Sell at $101.00
Slot 4: EMPTY (in Free List)
Slot 5: Order 601, Buy at $100.00
Free List chain: 0 -> 2 -> 4 -> INVALID
The slots with orders are at positions 1, 3, 5.
The free slots are at 0, 2, 4.
They are interleaved (fragmented).
Does this cause a problem?
Finding the next free slot: next_free_idx = 0. Done in O(1). No problem.
Traversing the $100.00 buy queue: Slot 1 and Slot 5 are linked by next_idx and prev_idx.
The engine follows the chain, not the physical order in the array. No problem.
The only case where fragmentation could become a problem is if the pool fills completely (all slots are active and the Free List is empty). At that point no new orders can be accepted until existing ones are cancelled or executed. This is handled by checking the Free List before accepting a new order.
Learn more: https://en.wikipedia.org/wiki/Fragmentation_(computing)
3.7 Memory Corruption
Simple definition: Memory corruption happens when the program reads or writes to a slot that contains data belonging to a different context, or reads stale data from a slot that has already been recycled. The program does not crash immediately. It silently uses wrong data and makes wrong decisions.
Why it matters in an order book: A corrupted order book might execute a trade at the wrong price, match a buyer with the wrong seller, process a cancellation for an order that does not belong to the price being queried, or leave dangling links that create infinite loops when traversing a price queue. All of these cause incorrect trades and potential financial loss.
The most dangerous form: the dangling link. This happens when a slot is recycled into the Free List before the neighbouring slots in the same price queue have updated their links to bypass it.
Example of the wrong sequence that causes corruption:
Setup: Three orders are at price $100.00.
Slot 1 (Order 502) <-> Slot 2 (Order 503) <-> Slot 3 (Order 504)
Map: head_idx = 1, tail_idx = 3
Slot 2 (Order 503) is cancelled.
WRONG sequence (dangerous):
Step A: Add Slot 2 to Free List immediately.
next_free_idx = 2
pool[2].next_idx = (whatever was previously free)
Step B: A new order arrives at $99.00 and claims Slot 2.
pool[2] is overwritten with the new $99.00 order.
Step C: (We forgot to update Slot 1 and Slot 3)
pool[1].next_idx still = 2 (points to the $99.00 order by mistake)
pool[3].prev_idx still = 2 (points to the $99.00 order by mistake)
Result: The $100.00 price queue now includes a $99.00 order in the middle.
When the engine traverses $100.00 orders, it will process a $99.00 order.
This is a trade at the wrong price. Corruption has occurred.
The correct sequence that prevents corruption:
Slot 2 (Order 503) is cancelled.
CORRECT sequence (safe):
Step A: Heal the chain first.
pool[1].next_idx = 3 (Slot 1 now skips over Slot 2 to Slot 3)
pool[3].prev_idx = 1 (Slot 3 now points back to Slot 1)
Step B: Only NOW add Slot 2 to Free List.
pool[2].next_idx = next_free_idx
next_free_idx = 2
Result: No active order in the $100.00 queue points to Slot 2 anymore.
Even when a new $99.00 order claims Slot 2, the $100.00 queue is unaffected.
The two price levels remain completely separated.
The golden rule: always unhook a slot from its neighbours before releasing it to the Free List. Chain healing comes first. Recycling comes second.
Learn more: https://en.wikipedia.org/wiki/Memory_corruption
3.8 Price Levels in an Order Book
Simple definition: A price level is a specific dollar amount at which one or more orders are resting. "$100.00" is one price level. "$100.01" is a different price level. All orders at the same price belong to the same price level and are stored in a queue together.
Why it matters: The fundamental rule of an exchange is that trades execute at the best available price. For a buy order matching against sellers, the best price is the lowest available ask. For a sell order matching against buyers, the best price is the highest available bid. To find the best price instantly, price levels must be kept sorted.
The order book at any real moment:
Sell side (sorted lowest to highest):
$101.50: Order 904 (qty 50)
$101.00: Order 905 (qty 100), Order 906 (qty 20)
$100.50: Order 907 (qty 30)
<-- bid/ask spread: the gap between best ask and best bid -->
Buy side (sorted highest to lowest):
$100.00: Order 501 (qty 10), Order 502 (qty 5)
$99.50: Order 503 (qty 30)
$99.00: Order 504 (qty 15)
The gap between the lowest ask ($100.50) and the highest bid ($100.00) is $0.50. This is called the spread. No trade executes yet because no buyer is willing to pay as much as any seller is asking.
How price levels are stored in code:
struct PriceLevel {
uint32_t head_idx; // Pool slot of the OLDEST order at this price
uint32_t tail_idx; // Pool slot of the NEWEST order at this price
uint64_t total_volume; // Sum of all quantities at this price
};
// A sorted map: price value (key) --> PriceLevel struct (value)
std::map<uint32_t, PriceLevel> buy_side_map;
std::map<uint32_t, PriceLevel> sell_side_map;
The std::map is a self-balancing binary tree. It keeps all price levels sorted automatically. The lowest ask is always at buy_side_map.begin(). The highest bid is always at buy_side_map.rbegin(). Finding the best price is O(1) once the tree is built. Adding or removing a price level costs O(log P) where P is the number of distinct price levels currently active, which is typically a small number (tens to hundreds, not millions).
Learn more: https://en.wikipedia.org/wiki/Order_book
3.9 Multiple Orders at the Same Price
Simple definition: Multiple traders can submit orders at the exact same price. These orders queue up at that price level. The rule is FIFO: First In, First Out. The order that arrived earliest gets matched first.
Why it matters: Two traders both want to buy at $100.00. The exchange must decide who gets filled when a seller arrives at $100.00. The rule is: whoever submitted their order first wins. This is called time priority.
How time priority is stored without timestamps: You might expect each order to store a timestamp so the engine can compare arrival times. But timestamps are not needed. The physical position in the doubly linked chain at a price level encodes time priority naturally.
When a new order arrives at a price, it is always appended to the tail of the chain. The oldest order is always at the head. When a trade executes, it pulls from the head. The chain position IS the timestamp.
This saves 8 bytes per order (the size of a uint64 timestamp). With one million orders, that is 8 MB of memory saved, which directly increases the amount of the order book that fits in CPU cache.
What a queue of five orders at the same price looks like:
Five orders arrived at $100.00 in sequence:
Order 501 (qty 10) arrived first
Order 502 (qty 5) arrived second
Order 503 (qty 20) arrived third
Order 504 (qty 8) arrived fourth
Order 505 (qty 15) arrived fifth (most recent)
They are stored in pool slots 0, 1, 2, 3, 4 (the order they arrived claims successive free slots).
Price Map entry for $100.00:
head_idx = 0 (points to the oldest order)
tail_idx = 4 (points to the newest order)
Pool slots for $100.00 queue:
Slot 0 (Order 501, qty 10): prev_idx = INVALID, next_idx = 1
Slot 1 (Order 502, qty 5): prev_idx = 0, next_idx = 2
Slot 2 (Order 503, qty 20): prev_idx = 1, next_idx = 3
Slot 3 (Order 504, qty 8): prev_idx = 2, next_idx = 4
Slot 4 (Order 505, qty 15): prev_idx = 3, next_idx = INVALID
When a sell order arrives and wants to match at $100.00:
Engine reads head_idx = 0. Goes to Slot 0. Processes Order 501 first.
If Order 501 fills completely, engine reads pool[0].next_idx = 1. Goes to Slot 1. Processes Order 502.
Continues in order: 0, 1, 2, 3, 4.
FIFO is automatically maintained by following the chain from head to tail.
3.10 Hole Reuse Strategy
Simple definition: When an order is cancelled and its pool slot becomes empty, the system does not erase the slot, does not compress the array, and does not move any other data. It simply marks the slot as available by adding its index to the Free List. The next new order claims that slot and overwrites the old data.
Why it matters: In a standard dynamic array, deleting an element from the middle forces everything after it to shift left to fill the gap. This is O(N). The hole reuse strategy completely eliminates this cost by leaving the "hole" exactly where it is, tracking it in the Free List, and filling it with new data only when a new order needs a slot.
What this looks like concretely with an order book example:
Starting state: Three orders at $100.00 are in slots 0, 1, 2.
Pool:
Slot 0 (Order 501, Buy $100.00): prev_idx = INVALID, next_idx = 1
Slot 1 (Order 502, Buy $100.00): prev_idx = 0, next_idx = 2
Slot 2 (Order 503, Buy $100.00): prev_idx = 1, next_idx = INVALID
Price Map: $100.00 head_idx = 0, tail_idx = 2
Free List: next_free_idx = 3 (slots 0, 1, 2 are all in use)
Order 502 (in Slot 1) is cancelled.
What does NOT happen:
Slot 2 does NOT move to Slot 1.
No data is copied.
No elements are shifted.
What DOES happen:
Step 1: Heal the chain. Slot 0 points directly to Slot 2.
pool[0].next_idx = 2
pool[2].prev_idx = 0
Step 2: The Price Map is unchanged. head is still 0, tail is still 2. Correct.
Step 3: Add Slot 1 to the Free List.
pool[1].next_idx = next_free_idx = 3
next_free_idx = 1
Pool after cancellation:
Slot 0 (Order 501, still active): prev_idx = INVALID, next_idx = 2
Slot 1 (HOLE - recycled): next_idx = 3 (this field is now part of Free List)
Slot 2 (Order 503, still active): prev_idx = 0, next_idx = INVALID
Price Map: $100.00 head_idx = 0, tail_idx = 2 (unchanged, still correct)
Free List: next_free_idx = 1 (Slot 1 available, then Slot 3 after it)
Now a new order at $99.00 arrives.
Engine reads next_free_idx = 1.
Engine claims Slot 1.
Engine advances Free List: reads pool[1].next_idx = 3, sets next_free_idx = 3.
Engine writes the new $99.00 order into Slot 1.
Slot 1 now holds a $99.00 order.
The $100.00 queue (Slot 0 to Slot 2) is completely unaware of Slot 1.
Slot 0's next_idx = 2 (jumps over Slot 1 entirely).
Slot 2's prev_idx = 0 (points back to Slot 0 entirely).
Two price levels, two separate logical chains, all in the same physical array, zero interference.
3.11 Allocation Strategy
Simple definition: The allocation strategy is the complete set of rules the engine follows to assign pool slots to new orders and to return freed slots back to the Free List.
The five rules of this strategy:
Rule 1: Pre-allocate everything at startup. The OS is asked for memory exactly once. Never during trading.
Rule 2: Use the Free List for O(1) allocation. next_free_idx always points directly to the next available slot.
Rule 3: Return freed slots to the front of the Free List (stack behaviour). The most recently freed slot becomes the next slot to be reused. This is beneficial because that slot was recently accessed and is likely still in the CPU cache.
Rule 4: Never shift data. When removing an order, only update a few integer values (next_idx and prev_idx of neighbours, and Free List head). No copying of order data happens.
Rule 5: Keep physical storage separate from logical ordering. The vector index tells you where the order lives. The next_idx and prev_idx fields tell you what order the orders are processed in. These two concepts are independent.
Why separating physical and logical order is the key insight:
Standard vector (physical order = logical order):
Position: [0] [1] [2] [3]
Content: Order 501 Order 502 Order 503 Order 504
^-- deleted --^
To delete Slot 1: must slide Order 503 and Order 504 left by one.
Cost: O(N)
Memory pool vector (physical order is irrelevant):
Position: [0] [1] [2] [3]
Content: Order 501 (HOLE) Order 503 Order 504
Logical order is maintained by links inside the structs:
Order 501: next_idx = 2 (points directly to Order 503, skips the hole)
Order 503: prev_idx = 0 (points directly back to Order 501)
Cost of deletion: update 2 integers. O(1).
Learn more: https://en.wikipedia.org/wiki/Dynamic_memory_allocation
4. System Design: How the Three Layers Work Together
The order book engine uses three data structures simultaneously. Each one has exactly one job. None of them can do the other's job.
Incoming message from trader
(order or cancellation)
|
_______________+_______________
| |
PRICE SEARCH CANCELLATION LOOKUP
[Price Map: std::map] [Order Directory: std::vector]
Keeps all price levels Maps OrderID to pool slot.
sorted. Finds best price Finds any order in O(1)
in O(log P) tree hops. without scanning.
| |
|_____________+_________________|
|
[Memory Pool: std::vector<OrderNode>]
Physical warehouse of all order data.
O(1) slot access via index math.
No OS allocations during trading.
No data shifting on deletion.
Component 1: The Memory Pool (std::vector of OrderNode)
This is the physical storage. Every active order in the book lives in exactly one slot of this vector. The vector is pre-allocated at startup and never resized. The Free List manages which slots are available.
struct OrderNode {
uint32_t order_id;
uint32_t qty;
uint32_t price;
uint32_t next_idx; // Next order in same price queue (INVALID if tail)
uint32_t prev_idx; // Previous order in same price queue (INVALID if head)
};
std::vector<OrderNode> node_pool(1000000); // 1 million slots reserved at startup
Component 2: The Price Map (std::map)
This is the sorted index. It stores one entry per active price level. That entry holds head_idx and tail_idx pointing into the Memory Pool. The map keeps all prices sorted automatically via a balanced binary tree internally.
struct PriceLevel {
uint32_t head_idx; // Oldest order at this price
uint32_t tail_idx; // Newest order at this price
uint64_t total_volume; // Sum of quantities at this price
};
std::map<uint32_t, PriceLevel> buy_side_map;
std::map<uint32_t, PriceLevel> sell_side_map;
Component 3: The Order Directory (flat std::vector)
This is the instant lookup table for cancellations. The index of this vector is the OrderID. The value stored is the pool slot where that order lives. A trader sends "cancel order 9942." The engine reads directory[9942] and instantly knows which pool slot to go to.
std::vector<uint32_t> order_directory(MAX_ORDER_ID, INVALID);
// order_directory[9942] = 7 means "Order 9942 is in pool slot 7"
Why the directory must be a flat vector and not a map:
If the directory were a std::map, looking up an OrderID would require traversing the binary tree. That costs O(log N) time. Using a flat vector, looking up an OrderID by index is O(1). For a cancellation, this is the difference between 50 nanoseconds (tree traversal) and 1 nanosecond (direct array access).
Why each component is irreplaceable:
Remove the Memory Pool:
Every order allocation calls the OS. Latency becomes unpredictable.
Cache locality is destroyed because nodes scatter across the heap.
Remove the Price Map:
Finding the best price requires scanning all pool slots. O(N) per trade.
With 100,000 active orders, every incoming market order triggers 100,000 comparisons.
Remove the Order Directory:
Finding which pool slot holds a specific OrderID requires scanning the entire pool.
O(N) per cancellation. Same disaster.
5. Deep Dive Scenarios: Every Case With Full Memory Snapshots
For all scenarios below, we start with a pool of 6 slots (numbered 0 through 5) to keep the examples readable. All three layers are shown after every operation.
Starting State (Engine Just Booted)
LAYER 1: PRICE MAP
buy_side_map: (empty)
sell_side_map: (empty)
LAYER 2: MEMORY POOL
Slot 0: order_id=0, qty=0, next_idx=1, prev_idx=INVALID (free, part of chain)
Slot 1: order_id=0, qty=0, next_idx=2, prev_idx=INVALID (free)
Slot 2: order_id=0, qty=0, next_idx=3, prev_idx=INVALID (free)
Slot 3: order_id=0, qty=0, next_idx=4, prev_idx=INVALID (free)
Slot 4: order_id=0, qty=0, next_idx=5, prev_idx=INVALID (free)
Slot 5: order_id=0, qty=0, next_idx=INVALID, prev_idx=INVALID (free, end of chain)
LAYER 3: ORDER DIRECTORY
All entries: INVALID
FREE LIST: next_free_idx = 0
5.1 Adding a New Order at a New Price
Event: Trader A submits "Buy 10 shares at $100.00" (assigned OrderID 501).
This is the best case. The price $100.00 does not exist yet, so no chain linking is needed. The order becomes both head and tail of a new single-order queue.
Step 1: Check Free List. next_free_idx = 0. Claim Slot 0. Read pool[0].next_idx = 1. Update next_free_idx = 1.
Step 2: Write order data into Slot 0.
Step 3: Check buy_side_map for $100.00. Not found. Create new price level entry with head_idx = 0 and tail_idx = 0. (This is the first and only order at this price, so it is simultaneously the head and the tail.)
Step 4: Record in directory: order_directory[501] = 0.
LAYER 1: PRICE MAP
buy_side_map:
$100.00 --> head_idx = 0, tail_idx = 0, total_volume = 10
sell_side_map: (empty)
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, price=100, next_idx=INVALID, prev_idx=INVALID [ACTIVE: Buy $100.00]
Slot 1: order_id=0, qty=0, next_idx=2, prev_idx=INVALID [FREE]
Slot 2: order_id=0, qty=0, next_idx=3, prev_idx=INVALID [FREE]
Slot 3: order_id=0, qty=0, next_idx=4, prev_idx=INVALID [FREE]
Slot 4: order_id=0, qty=0, next_idx=5, prev_idx=INVALID [FREE]
Slot 5: order_id=0, qty=0, next_idx=INVALID, prev_idx=INVALID [FREE]
LAYER 3: ORDER DIRECTORY
directory[501] = 0
All others: INVALID
FREE LIST: next_free_idx = 1
Time: O(log P) for the map insert (P=1, so log(1)=0 hops). All other steps O(1).
5.2 Adding a Second Order at the Same Price
Event: Trader B submits "Buy 5 shares at $100.00" (assigned OrderID 502).
This is the normal case. The price $100.00 already exists. The new order joins the tail of the existing queue.
Step 1: Check Free List. next_free_idx = 1. Claim Slot 1. Advance: next_free_idx = 2.
Step 2: Write order data into Slot 1.
Step 3: buy_side_map already has $100.00. Its current tail_idx = 0 (pointing to Slot 0, Order 501). Link the new order behind the current tail:
pool[0].next_idx = 1 (old tail now points forward to new order)
pool[1].prev_idx = 0 (new order points backward to old tail)
Update map: tail_idx = 1 (new order is now the tail)
Step 4: order_directory[502] = 1.
LAYER 1: PRICE MAP
buy_side_map:
$100.00 --> head_idx = 0, tail_idx = 1, total_volume = 15
sell_side_map: (empty)
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, price=100, next_idx=1, prev_idx=INVALID [ACTIVE: Buy $100.00 HEAD]
Slot 1: order_id=502, qty= 5, price=100, next_idx=INVALID, prev_idx=0 [ACTIVE: Buy $100.00 TAIL]
Slot 2: order_id=0, qty=0, next_idx=3, prev_idx=INVALID [FREE]
Slot 3: order_id=0, qty=0, next_idx=4, prev_idx=INVALID [FREE]
Slot 4: order_id=0, qty=0, next_idx=5, prev_idx=INVALID [FREE]
Slot 5: order_id=0, qty=0, next_idx=INVALID, prev_idx=INVALID [FREE]
LAYER 3: ORDER DIRECTORY
directory[501] = 0
directory[502] = 1
All others: INVALID
FREE LIST: next_free_idx = 2
Note: The chain at $100.00 is: Slot 0 <--> Slot 1
Map knows it starts at Slot 0 (head) and ends at Slot 1 (tail).
To add another order: claim Slot 2, link pool[1].next_idx = 2, set tail_idx = 2.
The pattern repeats for every subsequent order at this price.
5.3 Cancelling the Head Order
Event: Trader A cancels Order 501 (which sits at Slot 0, the head of the $100.00 queue).
This is the case where the map's head_idx must advance. The second order in line becomes the new head.
Step 1: order_directory[501] = 0. Engine goes to Slot 0.
Step 2: Read Slot 0's neighbours. prev_idx = INVALID (confirms Slot 0 is the head). next_idx = 1 (Slot 1 is the next order).
Step 3: Heal the chain. Slot 1 is becoming the new head. It should have nothing before it:
pool[1].prev_idx = INVALID
Step 4: Update the Price Map. The head of $100.00 moves from 0 to 1:
buy_side_map[$100.00].head_idx = 1
Step 5: Clear directory. order_directory[501] = INVALID.
Step 6: Recycle Slot 0 into Free List:
pool[0].next_idx = next_free_idx (= 2)
next_free_idx = 0
LAYER 1: PRICE MAP
buy_side_map:
$100.00 --> head_idx = 1, tail_idx = 1, total_volume = 5
sell_side_map: (empty)
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, next_idx=2, prev_idx=INVALID [RECYCLED: Free List head]
(data still physically here but logically dead; will be overwritten by next new order)
Slot 1: order_id=502, qty= 5, price=100, next_idx=INVALID, prev_idx=INVALID [ACTIVE: Buy $100.00 HEAD+TAIL]
Slot 2: order_id=0, qty=0, next_idx=3, prev_idx=INVALID [FREE]
Slot 3: order_id=0, qty=0, next_idx=4, prev_idx=INVALID [FREE]
Slot 4: order_id=0, qty=0, next_idx=5, prev_idx=INVALID [FREE]
Slot 5: order_id=0, qty=0, next_idx=INVALID, prev_idx=INVALID [FREE]
LAYER 3: ORDER DIRECTORY
directory[501] = INVALID (cleared)
directory[502] = 1
All others: INVALID
FREE LIST: next_free_idx = 0 (Slot 0 available first, then Slot 2, 3, 4, 5)
chain: 0 -> 2 -> 3 -> 4 -> 5 -> INVALID
The $100.00 queue now has only one order: Order 502 in Slot 1.
Slot 1's prev_idx and next_idx are both INVALID, confirming it is alone.
5.4 Cancelling a Middle Order
Let us first add a third order so there is a meaningful middle to cancel.
Setup (after adding Order 503, "Buy 20 shares at $100.00", OrderID 503, into Slot 2):
LAYER 1: PRICE MAP
$100.00 --> head_idx = 1, tail_idx = 2, total_volume = 25
LAYER 2: MEMORY POOL
Slot 0: [RECYCLED]
Slot 1: order_id=502, qty= 5, price=100, next_idx=2, prev_idx=INVALID [HEAD]
Slot 2: order_id=503, qty=20, price=100, next_idx=INVALID, prev_idx=1 [TAIL]
Slot 3, 4, 5: [FREE]
FREE LIST: next_free_idx = 3
Now add Order 504 ("Buy 8 shares at $100.00") to give us a true middle:
LAYER 1: PRICE MAP
$100.00 --> head_idx = 1, tail_idx = 3, total_volume = 33
LAYER 2: MEMORY POOL
Slot 0: [RECYCLED]
Slot 1: order_id=502, qty= 5, price=100, next_idx=2, prev_idx=INVALID [HEAD]
Slot 2: order_id=503, qty=20, price=100, next_idx=3, prev_idx=1 [MIDDLE]
Slot 3: order_id=504, qty= 8, price=100, next_idx=INVALID, prev_idx=2 [TAIL]
Slot 4, 5: [FREE]
FREE LIST: next_free_idx = 4
Event: Trader cancels Order 503 (Slot 2, the middle order).
Step 1: order_directory[503] = 2. Engine goes to Slot 2.
Step 2: Read neighbours. prev_idx = 1 (Slot 1 is before). next_idx = 3 (Slot 3 is after).
Step 3: Heal the chain. Slot 1 must jump directly to Slot 3, and Slot 3 must point back to Slot 1:
pool[1].next_idx = 3
pool[3].prev_idx = 1
Step 4: Map does NOT need to change. head is still Slot 1. tail is still Slot 3. Both are correct. The map only tracks the outer boundaries. The internal link was handled entirely within the pool.
Step 5: Clear directory. order_directory[503] = INVALID.
Step 6: Recycle Slot 2:
pool[2].next_idx = next_free_idx (= 4)
next_free_idx = 2
LAYER 1: PRICE MAP
$100.00 --> head_idx = 1, tail_idx = 3, total_volume = 13
(total_volume updated: 5 + 8 = 13)
(Map did not need structural change, only volume update)
LAYER 2: MEMORY POOL
Slot 0: [RECYCLED from earlier]
Slot 1: order_id=502, qty= 5, price=100, next_idx=3, prev_idx=INVALID [HEAD - next_idx updated from 2 to 3]
Slot 2: order_id=503, qty=20, next_idx=4, prev_idx=INVALID [RECYCLED: was middle order]
(data still here physically but logically dead, Slot 2 is now in Free List)
Slot 3: order_id=504, qty= 8, price=100, next_idx=INVALID, prev_idx=1 [TAIL - prev_idx updated from 2 to 1]
Slot 4, 5: [FREE]
LAYER 3: ORDER DIRECTORY
directory[502] = 1
directory[503] = INVALID (cleared)
directory[504] = 3
All others: INVALID
FREE LIST: next_free_idx = 2 chain: 2 -> 4 -> 5 -> INVALID
Traversing $100.00 queue now:
Engine reads head_idx = 1. Goes to Slot 1 (Order 502, qty 5).
Reads pool[1].next_idx = 3. Goes to Slot 3 (Order 504, qty 8).
Reads pool[3].next_idx = INVALID. Stops.
Slot 2 is completely skipped. It does not interfere.
5.5 Cancelling the Tail Order
Event: Trader cancels Order 504 (Slot 3, the tail of the $100.00 queue).
Step 1: order_directory[504] = 3. Engine goes to Slot 3.
Step 2: Read neighbours. prev_idx = 1 (Slot 1 is before). next_idx = INVALID (confirms this is the tail).
Step 3: Heal the chain. Slot 1 is now the new tail. It should point forward to nothing:
pool[1].next_idx = INVALID
Step 4: Update map. tail must move from 3 to 1:
buy_side_map[$100.00].tail_idx = 1
Step 5: Clear directory. order_directory[504] = INVALID.
Step 6: Recycle Slot 3:
pool[3].next_idx = next_free_idx (= 2)
next_free_idx = 3
LAYER 1: PRICE MAP
$100.00 --> head_idx = 1, tail_idx = 1, total_volume = 5
(tail moved from 3 to 1; only one order remains)
LAYER 2: MEMORY POOL
Slot 0: [RECYCLED]
Slot 1: order_id=502, qty= 5, price=100, next_idx=INVALID, prev_idx=INVALID [ACTIVE: head and tail]
Slot 2: [RECYCLED]
Slot 3: order_id=504, qty=8, next_idx=2, prev_idx=INVALID [RECYCLED: was tail]
Slot 4, 5: [FREE]
LAYER 3: ORDER DIRECTORY
directory[502] = 1
directory[504] = INVALID
All others: INVALID
FREE LIST: next_free_idx = 3 chain: 3 -> 2 -> 4 -> 5 -> INVALID
Only Order 502 remains at $100.00, in Slot 1.
Both prev_idx and next_idx of Slot 1 are INVALID, confirming it is alone at this price.
5.6 Cancelling the Only Order at a Price
Event: Trader cancels Order 502 (Slot 1), which is now the only order at $100.00.
Step 1: order_directory[502] = 1. Engine goes to Slot 1.
Step 2: Read neighbours. prev_idx = INVALID and next_idx = INVALID. This order is alone.
Step 3: No chain healing needed. There are no neighbours to update.
Step 4: Remove the price level entirely from the Price Map:
buy_side_map.erase($100.00)
The map tree node for $100.00 is deleted. The tree self-balances.
Step 5: Clear directory. order_directory[502] = INVALID.
Step 6: Recycle Slot 1:
pool[1].next_idx = next_free_idx (= 3)
next_free_idx = 1
LAYER 1: PRICE MAP
buy_side_map: (empty again)
sell_side_map: (empty)
LAYER 2: MEMORY POOL
Slot 0: [RECYCLED]
Slot 1: order_id=502, qty=5, next_idx=3, prev_idx=INVALID [RECYCLED: was only order at $100]
Slot 2: [RECYCLED]
Slot 3: [RECYCLED]
Slot 4: [FREE]
Slot 5: [FREE]
LAYER 3: ORDER DIRECTORY
All entries: INVALID
FREE LIST: next_free_idx = 1 chain: 1 -> 3 -> 2 -> 4 -> 5 -> INVALID
The order book is back to an empty state with all slots available.
The free chain order is 1, 3, 2, 4, 5 (not 0, 1, 2, 3, 4, 5 as at startup).
This is normal. The free chain does not need to be in order. Any slot is equally valid.
5.7 Matching and Executing an Order
Let us rebuild the book with a buy order and a sell order that will match.
Setup: Add Order 601 "Buy 10 shares at $100.00" (Slot 0) and Order 701 "Sell 10 shares at $100.00" (Slot 1).
LAYER 1: PRICE MAP
buy_side_map:
$100.00 --> head_idx = 0, tail_idx = 0, total_volume = 10
sell_side_map:
$100.00 --> head_idx = 1, tail_idx = 1, total_volume = 10
LAYER 2: MEMORY POOL
Slot 0: order_id=601, qty=10, price=100, next_idx=INVALID, prev_idx=INVALID [ACTIVE: Buy $100]
Slot 1: order_id=701, qty=10, price=100, next_idx=INVALID, prev_idx=INVALID [ACTIVE: Sell $100]
Slots 2-5: [FREE]
LAYER 3: ORDER DIRECTORY
directory[601] = 0
directory[701] = 1
FREE LIST: next_free_idx = 2
Event: A matching event is triggered. Best buy = $100.00. Best sell = $100.00. They match.
Step 1: Engine reads buy_side_map.rbegin() to get the best (highest) bid. Gets $100.00. Step 2: Engine reads sell_side_map.begin() to get the best (lowest) ask. Gets $100.00. Step 3: Prices match. Proceed with execution.
Buy side: head_idx = 0. Engine reads Slot 0 (Order 601, qty 10). Sell side: head_idx = 1. Engine reads Slot 1 (Order 701, qty 10).
Both want to trade 10 shares. Perfect fill. Both are fully consumed.
Execute and clean up Order 601 (Buy):
pool[0].next_idx = INVALID, so no next order at this buy price.
Remove $100.00 from buy_side_map entirely (no orders remain there).
order_directory[601] = INVALID.
Recycle Slot 0: pool[0].next_idx = 2, next_free_idx = 0.
Execute and clean up Order 701 (Sell):
pool[1].next_idx = INVALID, so no next order at this sell price.
Remove $100.00 from sell_side_map entirely.
order_directory[701] = INVALID.
Recycle Slot 1: pool[1].next_idx = next_free_idx (= 0), next_free_idx = 1.
LAYER 1: PRICE MAP
buy_side_map: (empty)
sell_side_map: (empty)
LAYER 2: MEMORY POOL
Slot 0: order_id=601, qty=10, next_idx=2, prev_idx=INVALID [RECYCLED: was buy order]
Slot 1: order_id=701, qty=10, next_idx=0, prev_idx=INVALID [RECYCLED: was sell order]
Slots 2-5: [FREE as before]
LAYER 3: ORDER DIRECTORY
All entries: INVALID
FREE LIST: next_free_idx = 1 chain: 1 -> 0 -> 2 -> 3 -> 4 -> 5 -> INVALID
Trade executed: 10 shares at $100.00. Both orders removed. Engine ready for next event.
What happens when it is a partial fill:
Say Order 601 wants to buy 15 shares, and Order 701 only sells 10. Prices match.
Execute 10 shares (the maximum both agree on).
Order 701 is fully filled. Remove it from the sell side (same cleanup as above).
Order 601 is partially filled. Reduce its quantity: pool[0].qty = 15 - 10 = 5. It stays in the pool, stays in the buy side map. head_idx still = 0.
The next incoming sell order at $100.00 will match against the remaining 5 shares.
5.8 Reusing Freed Memory Holes
This scenario proves that freed slots are perfectly reused and that different price levels can share the same physical pool without interference.
Setup: Fill slots 0, 1, 2 with orders at $100.00. Then cancel the middle order (Slot 1). Then place a new order at a completely different price $99.00, which will claim Slot 1.
After placing three $100.00 orders in slots 0, 1, 2:
LAYER 1: PRICE MAP
$100.00 --> head_idx=0, tail_idx=2
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, price=100, next_idx=1, prev_idx=INVALID [HEAD $100]
Slot 1: order_id=502, qty= 5, price=100, next_idx=2, prev_idx=0 [MIDDLE $100]
Slot 2: order_id=503, qty=20, price=100, next_idx=INVALID, prev_idx=1 [TAIL $100]
Slots 3-5: [FREE]
FREE LIST: next_free_idx = 3
Cancel Order 502 (Slot 1, middle):
LAYER 1: PRICE MAP
$100.00 --> head_idx=0, tail_idx=2 (unchanged)
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, price=100, next_idx=2, prev_idx=INVALID [HEAD $100, next_idx healed: was 1, now 2]
Slot 1: order_id=502, qty= 5, next_idx=3, prev_idx=INVALID [RECYCLED: free, points to Slot 3]
Slot 2: order_id=503, qty=20, price=100, next_idx=INVALID, prev_idx=0 [TAIL $100, prev_idx healed: was 1, now 0]
Slots 3-5: [FREE]
FREE LIST: next_free_idx = 1 chain: 1 -> 3 -> 4 -> 5 -> INVALID
Now a new order arrives: "Buy 30 shares at $99.00" (OrderID 604).
Engine reads next_free_idx = 1. Claims Slot 1. Advances free list: reads pool[1].next_idx = 3, sets next_free_idx = 3.
Writes new order into Slot 1.
$99.00 does not exist in the map. Creates new entry: head_idx = 1, tail_idx = 1.
order_directory[604] = 1.
LAYER 1: PRICE MAP
$100.00 --> head_idx=0, tail_idx=2
$99.00 --> head_idx=1, tail_idx=1
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, price=100, next_idx=2, prev_idx=INVALID [HEAD of $100.00]
Slot 1: order_id=604, qty=30, price= 99, next_idx=INVALID, prev_idx=INVALID [ONLY order at $99.00]
Slot 2: order_id=503, qty=20, price=100, next_idx=INVALID, prev_idx=0 [TAIL of $100.00]
Slots 3-5: [FREE]
LAYER 3: ORDER DIRECTORY
directory[501] = 0
directory[503] = 2
directory[604] = 1
directory[502] = INVALID (cleared when cancelled)
FREE LIST: next_free_idx = 3 chain: 3 -> 4 -> 5 -> INVALID
Critical observation:
Slot 0 (Order 501) has next_idx = 2. It jumps completely over Slot 1.
Slot 2 (Order 503) has prev_idx = 0. It points back to Slot 0, not Slot 1.
The $100.00 queue is: Slot 0 <--> Slot 2. Slot 1 is invisible to it.
The $99.00 queue is: Slot 1 alone. It has no connection to Slot 0 or Slot 2.
Two price levels, two independent logical chains, all in the same physical array.
5.9 Five Orders at the Same Price: Full Sequence
Event: Five orders arrive at $100.00 one after another. Order 501: Buy 10 shares at $100.00 Order 502: Buy 5 shares at $100.00 Order 503: Buy 20 shares at $100.00 Order 504: Buy 8 shares at $100.00 Order 505: Buy 15 shares at $100.00
After all five are placed (they claim slots 0 through 4 in order):
LAYER 1: PRICE MAP
$100.00 --> head_idx=0, tail_idx=4, total_volume=58
LAYER 2: MEMORY POOL
Slot 0: order_id=501, qty=10, price=100, next_idx=1, prev_idx=INVALID [HEAD - arrived first]
Slot 1: order_id=502, qty= 5, price=100, next_idx=2, prev_idx=0
Slot 2: order_id=503, qty=20, price=100, next_idx=3, prev_idx=1
Slot 3: order_id=504, qty= 8, price=100, next_idx=4, prev_idx=2
Slot 4: order_id=505, qty=15, price=100, next_idx=INVALID, prev_idx=3 [TAIL - arrived last]
Slot 5: [FREE]
LAYER 3: ORDER DIRECTORY
directory[501]=0, directory[502]=1, directory[503]=2, directory[504]=3, directory[505]=4
FREE LIST: next_free_idx = 5 (only Slot 5 remains free)
Now a large sell order arrives and wants to buy 38 shares worth of sell orders at $100.00.
The engine consumes from the head:
Execute Order 501 (10 shares). 10 of 38 filled. Remove Slot 0. head_idx advances to 1. Execute Order 502 ( 5 shares). 15 of 38 filled. Remove Slot 1. head_idx advances to 2. Execute Order 503 (20 shares). 35 of 38 filled. Remove Slot 2. head_idx advances to 3. Order 504 has 8 shares. We only need 3 more. Partially fill Order 504. Reduce qty from 8 to 5. Order 504 stays in the book.
LAYER 1: PRICE MAP
$100.00 --> head_idx=3, tail_idx=4, total_volume=20
(total_volume: 5 remaining in Order 504 + 15 in Order 505 = 20)
LAYER 2: MEMORY POOL
Slot 0: [RECYCLED: Order 501 was fully executed]
Slot 1: [RECYCLED: Order 502 was fully executed]
Slot 2: [RECYCLED: Order 503 was fully executed]
Slot 3: order_id=504, qty=5, price=100, next_idx=4, prev_idx=INVALID [HEAD - partially filled, qty reduced]
Slot 4: order_id=505, qty=15, price=100, next_idx=INVALID, prev_idx=3 [TAIL - untouched]
Slot 5: [FREE]
LAYER 3: ORDER DIRECTORY
directory[501]=INVALID, directory[502]=INVALID, directory[503]=INVALID
directory[504]=3 (still active with 5 remaining shares)
directory[505]=4
FREE LIST: next_free_idx = 2 (Slot 2 was last recycled, then 1, then 0)
chain: 2 -> 1 -> 0 -> 5 -> INVALID
This example shows all three cases together: best case (new order appended to tail), normal case (middle consumed during matching), and partial fill where the head order survives with reduced quantity.
6. Memory Architecture: The 3 Layer Model
When the order book engine runs, data does not sit in one place. It moves between three tiers of memory, each with dramatically different speed.
TIER 1: CPU Cache (L1, L2, L3)
Speed: ~1 to 10 nanoseconds
Size: 256 KB (L1) to 8 MB (L3)
Contents: A small hot slice of the pool that was recently accessed
TIER 2: RAM (Main Memory)
Speed: ~50 to 100 nanoseconds
Size: 8 GB to 256 GB on a modern server
Contents: The entire pre-allocated node_pool, the map, the directory
TIER 3: SSD or Disk Storage
Speed: ~50,000 to 1,000,000 nanoseconds (microseconds to milliseconds)
Size: Terabytes
Contents: Trade logs, audit trails, end-of-day records. NOT in the critical path.
The order book's critical matching path never touches disk. Everything the matching engine needs during a trade lives in RAM, and the most recently accessed portions of RAM live in cache.
What happens during a new order insertion
T = 0ns: Trader's message arrives at the engine.
T = 1ns: Engine reads next_free_idx from RAM.
If this was accessed recently: already in L1 cache. Cost: 1ns.
If cold: CPU fetches from RAM. Cost: 50-100ns.
T = 2ns: Engine writes new order data into pool[slot].
The write goes to L1 cache first (write-back policy).
RAM is updated later asynchronously.
T = 3ns: Engine reads buy_side_map for the price.
If this price was recently accessed (active price): in cache. Cost: 1-4ns.
If this is a new price not recently seen: cache miss. Cost: 50-100ns.
T = 4ns: Engine writes order_directory[order_id].
Goes to L1 cache. Fast.
Total time (all data hot in cache): 4 to 10 nanoseconds
Total time (cold cache, all from RAM): 200 to 400 nanoseconds
What happens during a cancellation
T = 0ns: Cancel message arrives.
T = 1ns: Read order_directory[order_id].
Flat vector access. If directory is in cache: 1ns. If cold: 50-100ns.
T = 2ns: Read pool[target_slot] to get prev_idx and next_idx.
If this slot was recently active: likely in cache. Fast.
If this order was placed hours ago and not touched since: cold. Slower.
T = 3ns: Read pool[prev_slot] and pool[next_slot] to heal the chain.
Each read: 1ns if in cache, 50-100ns if cold (two separate cache lines).
T = 4ns: Update buy_side_map entry (if this was the head or tail).
Map nodes scatter in RAM, so map access is often a cache miss.
T = 5ns: Recycle the freed slot (update free list).
Fast. next_free_idx is a single integer, likely in cache.
Best case (all data in L1/L2 cache): 5 to 15 nanoseconds
Normal case (mix of cache hits and misses): 50 to 200 nanoseconds
Worst case (all data cold, all from RAM): 300 to 600 nanoseconds
Why the vector pool helps the cache dramatically
Standard heap allocations (calling new for every order) place each order node at a random location in RAM decided by the OS allocator. When the engine traverses a price queue, it follows next_idx pointers from one scattered address to another. Each hop is a new RAM read. Result: every step of traversal is a cache miss.
Our pre-allocated vector pool places all order nodes in one continuous block. Even if the logical chain jumps from Slot 0 to Slot 9 to Slot 3, all three slots are within the same memory region. The CPU pre-fetches neighbouring slots when any one slot is read. Slots 0 through 8 may already be in L2 cache by the time Slot 9 is needed.
Standard heap (orders scattered):
Order at address 0x7f1a3c00 -> Order at address 0x4b2d0e80 -> Order at address 0x2c8f1100
Each arrow: a random jump anywhere in RAM. Likely cache miss every time.
Memory pool (orders in one block):
pool[0] at base+0 -> pool[9] at base+180 -> pool[3] at base+60
All three are within the same block. base+0 to base+220.
When base+0 is loaded, the CPU pre-fetches base+64 and base+128.
pool[3] (at base+60) is already in cache before it is even requested.
How the map interacts with the cache
The std::map is a binary tree where each node is a separate heap allocation. These nodes are scattered in RAM. Traversing the tree for a price lookup almost always causes cache misses.
This is why our architecture limits the map to price levels only (a small number P) and not individual orders (a large number N). If we stored every order in a map, N would be millions, and every access would be a cache miss. By using the map only for price levels (typically 10 to 200 active prices at any moment), the entire map often fits in L2 or L3 cache.
Orders in std::map (bad):
N = 100,000 orders in the map.
Map nodes scattered across RAM. Every lookup: cache miss.
Price levels in std::map (good):
P = 50 active price levels.
50 tree nodes. Likely fits in L2 cache (8 MB) entirely.
Lookups mostly served from cache.
7. Failure Cases: Best, Worst, and Normal
7.1 Free List Corruption (Lost Slots)
What it is: During the recycling of a freed slot, if the head pointer is updated before the slot is linked into the chain, all previously available slots become unreachable.
Best case: Bug is caught immediately because next_free_idx points to INVALID faster than expected. The pool appears full when it is not.
Normal case: The lost slots are discovered during a daily diagnostic scan that compares the count of active orders plus the length of the free chain against the total pool size. The mismatch reveals the lost slots.
Worst case: The bug is not detected. The lost slots are never reused. Over a trading day with millions of cancellations, the pool fills with recycled-but-unreachable slots. Eventually new orders cannot be accepted even though most of the pool is technically empty.
WRONG recycling (loses slots):
Current state: next_free_idx = 5 (Slot 5 is the current free head)
We want to recycle Slot 2.
Step 1 (WRONG): next_free_idx = 2 (head updated before linking)
Step 2: pool[2].next_idx = ??? (we forgot to link Slot 2 to Slot 5)
Free chain now: 2 -> (garbage or INVALID)
Slot 5 and everything after it is permanently lost.
CORRECT recycling (preserves all slots):
Step 1: pool[2].next_idx = 5 (Slot 2 links to old head first)
Step 2: next_free_idx = 2 (now we move the head)
Free chain now: 2 -> 5 -> (rest of chain intact)
7.2 Dangling Link Corruption
What it is: A slot is recycled while another slot's next_idx or prev_idx still points to it. When the recycled slot is claimed by a new order from a different price level, the old pointer now leads into the wrong price's data.
Best case: The dangling slot is claimed by a new order at the same price level. The data is overwritten but the link still exists, causing duplicate order processing for the new order.
Normal case: The dangling slot is claimed by a new order at a different price level. The engine follows the old link during a traversal and processes one order from the wrong price. This results in an incorrect trade execution.
Worst case: The dangling slot is at a position that gets visited on every single traversal of the affected price level. Every match event processes the wrong order. This corrupts trade records continuously until the engine is restarted.
Detection: A consistency check that traverses every active price queue from head to tail and verifies that each slot's order_id matches what the directory says about that slot.
Prevention: Chain healing always runs completely before the slot is added to the Free List. Never partially heal.
7.3 Index Mismatch in the Order Directory
What it is: The order directory says Order 502 is in Slot 7, but Slot 7 now holds a completely different order because Order 502 was cancelled and the directory was not cleared.
Best case: The second order claiming Slot 7 has an order_id stored in Slot 7 itself. When a cancellation for Order 502 arrives and the engine goes to Slot 7, it reads the order_id from the slot and discovers the mismatch. It rejects the cancellation with an error.
Normal case: The engine proceeds with the cancellation without checking order_id. It unhooks Slot 7's current occupant (a valid live order) from its price queue by mistake. A valid order disappears from the book silently.
Worst case: The mistakenly cancelled order was the head of an important price level. That price level's head_idx now points to a recycled slot. The next trade execution reads garbage data and executes a trade with invalid parameters.
Prevention: Always set order_directory[order_id] = INVALID when an order is cancelled or executed. When claiming a new slot for a new order, set order_directory[new_order_id] = new_slot only after verifying the directory entry is INVALID (confirming no existing mapping was in place for that OrderID).
7.4 Pool Exhaustion
What it is: All pool slots are currently holding active orders. next_free_idx = INVALID. A new order arrives but there is no slot to put it in.
Best case: The engine has a check at the start of every order insertion:
if (next_free_idx == INVALID) {
reject_order(new_order_id, REASON_POOL_FULL);
return;
}
The order is rejected cleanly. The trader receives a rejection message. No corruption occurs.
Normal case: The pool was sized too small for peak load. Rejection happens during a busy period, causing the exchange to reject legitimate orders. Traders are frustrated. The pool needs to be resized.
Worst case: There is no check. The engine tries to write to "slot INVALID." On most systems, this writes to a completely wrong memory address, overwriting some other data structure (possibly the map or the directory). Corruption occurs across the entire engine.
Prevention: Always check next_free_idx against INVALID before claiming a slot. Size the pool generously. Monitor the ratio of active orders to pool capacity in real time and alert when it exceeds 80%.
7.5 Partial Execution State Corruption
What it is: A partially filled order has its quantity reduced but is not fully removed. If the quantity update is not atomic and another thread reads the order at the same time, the other thread may see a partially updated state.
Best case: The engine runs on a single thread for its critical matching path (which is the standard design for HFT engines). No concurrent reads of the same order occur during an update. The partial fill is applied cleanly.
Normal case: The engine has a read side that publishes order book snapshots to a market data feed. If the read side reads Slot 3's quantity at the same moment the matching engine is writing a new quantity to Slot 3, the read side may publish an incorrect quantity to external participants.
Worst case: Two matching threads share the same pool without synchronisation. Both read the same head order at the same time. Both reduce it against two incoming orders simultaneously. The final quantity becomes negative or wraps around uint32 to a huge number.
Prevention: Keep the critical matching path on a single thread. Use a separate lock-free mechanism for publishing read-only snapshots. If multiple matching threads are required, partition the order book so each thread owns its own non-overlapping set of price levels and pool slots.
8. Final Mental Model
After working through all of this, the clearest mental picture I have of the whole system is this.
The order book is like a massive automated warehouse with three management systems that work together.
The warehouse floor is the Memory Pool. It has exactly one million numbered storage bays. Every bay is the same size. When an order arrives, it goes into an empty bay. When it is cancelled or executed, the bay is emptied and added to the availability list. The bays never move. The warehouse never expands or shrinks during the trading day. Nothing inside the warehouse is rearranged just because one bay empties out.
The availability list is the Free List. The warehouse manager has a notepad that always shows which bay to use next. When a bay is emptied, its number goes to the top of the notepad. When a new order arrives, the manager reads the top of the notepad, puts the order there, and crosses off that bay number. No one walks through the warehouse looking for empty bays.
The sorting catalog at the entrance is the Price Map. The catalog is a sorted directory that lists every active price level. For each price, it records which bay holds the oldest order waiting at that price (head) and which bay holds the newest order (tail). Orders inside the warehouse at the same price are linked to each other by a chain that goes through the bays in arrival order. When the engine needs to fill orders at $100.00, it reads the catalog, finds the first bay in the chain, fills it, and then follows the chain to the next bay.
The claim ticket counter is the Order Directory. When a trader submits an order, they get a ticket with a unique OrderID. The counter writes down which warehouse bay holds their order. When they cancel, they hand in the ticket. The counter reads the bay number directly. The manager goes straight to that bay. No searching.
This is the system in one formula:
Price Map (std::map) finds the best price in the order book in O(log P)
Memory Pool (std::vector) stores every live order with O(1) access per slot
Order Directory (std::vector) locates any specific order for cancellation in O(1)
Together: sort in O(log P), store in O(1), cancel in O(1), no OS calls, no data shifts.
9. References
Data Structures used in this article:
Array data structure: https://en.wikipedia.org/wiki/Array_data_structure
Linked list: https://en.wikipedia.org/wiki/Linked_list
Doubly linked list: https://en.wikipedia.org/wiki/Doubly_linked_list
Binary search tree: https://en.wikipedia.org/wiki/Binary_search_tree
Red-black tree (internal implementation of std::map): https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Hash table: https://en.wikipedia.org/wiki/Hash_table
Memory Management:
Memory management overview: https://en.wikipedia.org/wiki/Memory_management
Memory pool: https://en.wikipedia.org/wiki/Memory_pool
Free list: https://en.wikipedia.org/wiki/Free_list
Dynamic memory allocation: https://en.wikipedia.org/wiki/Dynamic_memory_allocation
Memory fragmentation: https://en.wikipedia.org/wiki/Fragmentation_(computing)
Memory corruption: https://en.wikipedia.org/wiki/Memory_corruption
Dangling pointer: https://en.wikipedia.org/wiki/Dangling_pointer
CPU and Hardware:
CPU cache: https://en.wikipedia.org/wiki/CPU_cache
Cache miss: https://en.wikipedia.org/wiki/Cache_miss
Locality of reference: https://en.wikipedia.org/wiki/Locality_of_reference
Integer types: https://en.wikipedia.org/wiki/Integer_(computer_science)
Trading Systems:
Order book: https://en.wikipedia.org/wiki/Order_book
Limit order: https://en.wikipedia.org/wiki/Order_(exchange)#Limit_order
High-frequency trading: https://en.wikipedia.org/wiki/High-frequency_trading
Bid-ask spread: https://en.wikipedia.org/wiki/Bid%E2%80%93ask_spread
FIFO execution: https://en.wikipedia.org/wiki/FIFO_and_LIFO_accounting
C++ Standard Library References:
std::vector reference: https://en.cppreference.com/w/cpp/container/vector
std::map reference: https://en.cppreference.com/w/cpp/container/map
uint32_t reference: https://en.cppreference.com/w/cpp/types/integer
Engineering resources:
Cache-friendly data structures (CppCon): https://www.youtube.com/watch?v=WDIkqP4JbkE
This article was written by a learner, for learners. Every concept here came from asking "but why?" and "but how?" repeatedly until the system made sense from the ground up. If something is still unclear, the best next step is to write the code yourself. Build a tiny version with 6 slots, trace through insertions and cancellations by hand, and the mental model will snap into place.