Project 1: Limit Order Book Engine
Build the fundamental data structure of every exchange and trading system - a fully functional limit order book that maintains bid/ask levels, handles order matching, and reports trades with nanosecond-level performance.
1. Quick Reference
| Attribute | Value |
|---|---|
| Difficulty | Intermediate |
| Time Estimate | 1-2 weeks |
| Languages | C++ or Rust |
| Prerequisites | Basic C++/Rust, understanding of maps/queues/linked lists |
| Key Topics | Cache optimization, data structures, memory layout, order matching, custom allocators |
| Coolness Level | Level 4: Hardcore Tech Flex |
| Portfolio Value | Resume Gold - Every HFT firm asks about this |
2. Learning Objectives
By completing this project, you will be able to:
- Understand limit order book mechanics: Explain how bids, asks, price levels, and order queues work in real exchanges
- Master cache-friendly data structure design: Implement data layouts that minimize cache misses and maximize throughput
- Learn price-time priority matching: Build a matching algorithm that correctly executes orders following exchange rules
- Gain experience with memory pooling: Eliminate malloc/new from your hot path using custom allocation strategies
- Benchmark and optimize for nanosecond latency: Use profiling tools to identify bottlenecks and measure improvements
- Compare data structure tradeoffs: Analyze red-black trees vs hash maps vs arrays for price level organization
- Build the foundation for HFT systems: This project is the core component that all subsequent projects build upon
3. Theoretical Foundation
3.1 Core Concepts
What is a Limit Order Book?
A limit order book (LOB) is the central data structure used by all electronic exchanges to match buyers with sellers. Every stock exchange (NYSE, NASDAQ), cryptocurrency exchange (Coinbase, Binance), and futures exchange (CME) maintains an order book for each tradable instrument.
LIMIT ORDER BOOK: AAPL
+-----------------------------------------------------+
| ASKS (SELLS) |
| |
| Price | Quantity | Orders |
| ---------+----------+----------------------- |
| $150.30 | 2,500 | [O5:500, O6:2000] <-- Best Ask
| $150.29 | 1,200 | [O4:1200] |
| $150.28 | 3,800 | [O3:800, O7:3000] |
| ---------+----------+----------------------- |
| |
| === SPREAD: $0.02 === |
| |
| ---------+----------+----------------------- |
| $150.26 | 4,100 | [O1:1000, O2:100, ...] <-- Best Bid
| $150.25 | 2,300 | [O8:2300] |
| $150.24 | 5,600 | [O9:1000, O10:4600] |
| |
| BIDS (BUYS) |
+-----------------------------------------------------+
Key Terminology:
| Term | Definition |
|---|---|
| Bid | An offer to buy at a specific price |
| Ask (Offer) | An offer to sell at a specific price |
| Best Bid | Highest price any buyer is willing to pay |
| Best Ask | Lowest price any seller is willing to accept |
| Spread | Difference between best ask and best bid |
| Price Level | All orders at the same price |
| Depth | Total quantity available at each price level |
| Liquidity | How easily you can trade without moving the price |
Price-Time Priority (FIFO)
When multiple orders exist at the same price level, they are executed in the order they arrived. This is called price-time priority or FIFO (First In, First Out).
Price Level $150.26:
[Order A: 9:00:00.001] -> [Order B: 9:00:00.003] -> [Order C: 9:00:00.007]
^ ^
Arrived first Arrived second
(Matched first) (Matched second)
Why This Matters: Speed is everything in HFT. If you can submit your order 1 microsecond faster than a competitor, you get priority at that price level. This is why HFT firms spend billions on infrastructure.
Order Types and Lifecycle
Order Types You Must Support:
- Limit Order: Buy/sell at a specific price or better
BUY 100 @ $150.25- Will only execute at $150.25 or lowerSELL 100 @ $150.30- Will only execute at $150.30 or higher
- Cancel Order: Remove a previously submitted order
- Must be O(1) or O(log n) to avoid exploitation
- Market Order (optional for this project): Buy/sell immediately at best available price
Order Lifecycle State Machine:
Order Lifecycle
+-------+ +----------+ +-------------+
| NEW |---->| PENDING |---->| FILLED |
+-------+ +----------+ +-------------+
| | ^
| | |
| v |
| +----------+ |
| | PARTIAL |------------+
| +----------+
| |
| v
v +----------+
+--------+ | CANCELED |
|REJECTED| +----------+
+--------+
NEW: Order received but not yet processed
PENDING: Order resting in book, waiting for match
PARTIAL: Some quantity filled, remainder still in book
FILLED: All quantity matched, order complete
CANCELED: Order removed before full execution
REJECTED: Order failed validation (invalid price, etc.)
The Matching Algorithm
When a new order arrives, the matching engine attempts to match it against existing orders on the opposite side:
MATCHING ALGORITHM: New Buy Order @ $150.28 for 1,500 shares
Step 1: Check if order crosses the spread
Best Ask: $150.26 (1,000 shares)
New Buy: $150.28 (1,500 shares)
$150.28 >= $150.26? YES (Order crosses!)
Step 2: Match against best ask
Match: 1,000 shares @ $150.26
Trade generated: BUY 1,000 @ $150.26
Remaining: 500 shares to fill
Step 3: Move to next price level
Next Ask: $150.27 (800 shares)
Match: 500 shares @ $150.27
Trade generated: BUY 500 @ $150.27
Order fully filled!
Step 4: Update order book
- Remove filled orders from ask side
- Update price level quantities
- Broadcast market data update
Pseudocode:
function match_order(incoming_order):
while incoming_order.remaining_qty > 0:
# Get best opposite price level
opposite_level = get_best_level(opposite_side(incoming_order.side))
if opposite_level is None:
break # No more liquidity
if not prices_cross(incoming_order.price, opposite_level.price, incoming_order.side):
break # Order doesn't cross spread
# Match against orders at this level (FIFO order)
for resting_order in opposite_level.orders:
match_qty = min(incoming_order.remaining_qty, resting_order.remaining_qty)
generate_trade(incoming_order, resting_order, match_qty, opposite_level.price)
incoming_order.remaining_qty -= match_qty
resting_order.remaining_qty -= match_qty
if resting_order.remaining_qty == 0:
remove_order(resting_order)
if incoming_order.remaining_qty == 0:
break
# If level is empty, remove it
if opposite_level.total_qty == 0:
remove_level(opposite_level)
# If order has remaining quantity, add to book
if incoming_order.remaining_qty > 0:
add_to_book(incoming_order)
3.2 Why This Matters
The order book is the most performance-critical data structure in a trading system:
| Operation | Frequency | Latency Requirement | Why It Matters |
|---|---|---|---|
| Add Order | 10,000-100,000/sec | < 1 microsecond | Every strategy starts with placing orders |
| Cancel Order | 50,000-500,000/sec | < 500 nanoseconds | Rapid requoting requires instant cancellation |
| Match/Execute | Variable | < 1 microsecond | Slow matching = missed opportunities |
| Best Bid/Ask | 100,000+/sec | < 100 nanoseconds | Price check happens before every decision |
Industry Performance Standards:
- NASDAQ: Processes 1+ million messages per second per symbol
- CME: Sub-microsecond matching latency
- NYSE: Order book updates every 64 microseconds (consolidated feed)
- HFT Firms: Internal matching in 10-100 nanoseconds
Real Financial Impact:
Scenario: You're quoting both sides of AAPL
Your Quote: BID $150.00 x 1000 | ASK $150.02 x 1000
The market moves against you (AAPL drops)
You need to cancel your $150.00 bid BEFORE someone sells to you
If your cancel takes 10 microseconds and a competitor's takes 1 microsecond:
- They cancel first, you get filled on stale quote
- Loss: potentially $0.10/share x 1000 shares = $100 per incident
- This happens thousands of times per day
3.3 Historical Context
Evolution of Electronic Trading:
Timeline of Electronic Trading
1960s-1970s: Physical trading floors, open outcry
Order books maintained on paper by specialists
1971: NASDAQ launched - first electronic exchange
Order books stored in centralized computers
1980s-1990s: Electronic Communication Networks (ECNs)
Competition drives innovation
1998: SEC Regulation ATS enables more ECNs
Market fragmentation begins
2000s: Decimalization ($0.01 increments)
Algorithmic trading emerges
Latency becomes competitive advantage
2005: Reg NMS - National Best Bid Offer requirement
Order routing becomes complex
2010s: Microsecond wars
Co-location, FPGA-based trading
Flash crashes reveal fragility
2020s: Nanosecond precision
AI-driven market making
Rust gaining adoption for safety
3.4 Common Misconceptions
Misconception 1: “std::map or a red-black tree is good enough for production”
Reality: std::map operations involve pointer chasing and cache misses. Production order books use flat arrays with intrusive lists, achieving 10-50x better performance. A tree traversal that looks O(log n) can take microseconds due to cache misses.
Misconception 2: “The matching algorithm is the hard part”
Reality: The matching algorithm is straightforward (just FIFO). The hard part is the data structure organization that makes matching fast. Algorithm complexity is O(m) where m is matched orders; the challenge is constant factors.
Misconception 3: “Memory allocation is fine if it’s fast”
Reality: Even “fast” allocators like jemalloc add 50-200ns variance. Production HFT systems use pre-allocated pools with O(1) allocation. Any syscall or heap operation in the hot path is unacceptable.
Misconception 4: “Optimizations don’t matter until you have a working version”
Reality: Partially true for correctness, but architecture decisions made early (data layout, allocation strategy) are very hard to change later. Design for performance from the start.
Misconception 5: “Exchanges use complex AI for matching”
Reality: Matching is deliberately simple and deterministic. Price-time priority is a well-defined, auditable algorithm. Complexity lives in the data structure, not the algorithm.
4. Project Specification
4.1 What You Will Build
A limit order book engine that:
- Maintains sorted price levels for both bids (descending) and asks (ascending)
- Supports core order operations: Add, Cancel, Modify
- Implements price-time priority matching correctly
- Generates trade events when orders cross
- Reports market data: Best Bid/Offer, depth at each level
- Achieves sub-microsecond operation times (target: < 500ns for common operations)
4.2 Functional Requirements
| ID | Requirement | Priority |
|---|---|---|
| FR1 | Accept limit orders with: symbol, side (buy/sell), price, quantity, order_id | Must Have |
| FR2 | Match incoming orders against existing book using price-time priority | Must Have |
| FR3 | Cancel orders by order_id in O(1) or O(log n) time | Must Have |
| FR4 | Report best bid and best ask prices and quantities | Must Have |
| FR5 | Generate trade events with: buyer_id, seller_id, price, quantity, timestamp | Must Have |
| FR6 | Support multiple price levels (at least 1000 levels per side) | Must Have |
| FR7 | Maintain FIFO order within each price level | Must Have |
| FR8 | Handle partial fills correctly, updating remaining quantity | Must Have |
| FR9 | Provide order acknowledgments (accepted, rejected, filled, canceled) | Must Have |
| FR10 | Support order modification (price change = cancel + new, quantity change) | Should Have |
| FR11 | Support multiple symbols (order book per symbol) | Should Have |
| FR12 | Provide depth snapshot (top N levels with quantities and order counts) | Should Have |
| FR13 | Track and report statistics (orders processed, trades executed, latency) | Should Have |
| FR14 | Support IOC (Immediate-Or-Cancel) order type | Nice to Have |
| FR15 | Support FOK (Fill-Or-Kill) order type | Nice to Have |
| FR16 | Implement market orders (execute at best available price) | Nice to Have |
4.3 Non-Functional Requirements
| Requirement | Target | Measurement Method |
|---|---|---|
| Add Order Latency | < 500ns (p50), < 2us (p99) | Measure with rdtsc or std::chrono::high_resolution_clock |
| Cancel Order Latency | < 200ns (p50), < 1us (p99) | Same measurement approach |
| Best Bid/Ask Query | < 50ns | Direct struct access, no computation |
| Memory Usage | < 100 bytes per order | Count struct sizes, verify with sizeof |
| Throughput | > 1 million orders/second | Benchmark with sustained load |
| Determinism | No dynamic allocation in hot path | Profile heap usage during operation |
| Correctness | Price-time priority always maintained | Property-based testing |
| Memory Efficiency | < 500MB for 1M orders | Monitor RSS during stress tests |
4.4 Example Usage / Output
$ ./orderbook
=== LIMIT ORDER BOOK ENGINE ===
> ADD BUY 100 50.25 order_001
ACK order_001 ADDED @ 50.25 x 100
BOOK: BID 50.25 x 100 | ASK -- x --
> ADD BUY 200 50.24 order_002
ACK order_002 ADDED @ 50.24 x 200
BOOK: BID 50.25 x 100 | ASK -- x --
> ADD SELL 150 50.30 order_003
ACK order_003 ADDED @ 50.30 x 150
BOOK: BID 50.25 x 100 | ASK 50.30 x 150
> ADD SELL 50 50.25 order_004
ACK order_004 ADDED @ 50.25 x 50
TRADE order_001 order_004 50@50.25
ACK order_004 FILLED
BOOK: BID 50.25 x 50 | ASK 50.30 x 150
> CANCEL order_001
ACK order_001 CANCELED (remaining 50)
BOOK: BID 50.24 x 200 | ASK 50.30 x 150
> ADD SELL 300 50.20 order_005
ACK order_005 ADDED @ 50.20 x 300
TRADE order_002 order_005 200@50.24
PARTIAL order_005 200 filled, 100 remaining @ 50.20
BOOK: BID -- x -- | ASK 50.20 x 100
> DEPTH
=== ORDER BOOK DEPTH ===
ASKS
----
50.30 | 150 (1 orders)
50.20 | 100 (1 orders)
----
SPREAD: $50.20 (no bids)
----
BIDS
----
(empty)
> STATS
Operations: 5 adds, 1 cancel
Trades: 2 (250 shares total)
Avg add latency: 342ns (p50), 891ns (p99)
Avg cancel latency: 156ns (p50), 412ns (p99)
Memory: 5 orders x 64 bytes = 320 bytes
4.5 Real World Outcome
When complete, you will have:
-
A functional matching engine that can process orders, generate trades, and maintain consistent book state
- Benchmark results demonstrating performance progression:
=== BENCHMARK RESULTS === Phase 1 (std::map baseline): Add Order: 2,340ns (p50), 5,120ns (p99) Cancel Order: 1,890ns (p50), 4,230ns (p99) Throughput: 180K orders/second Phase 2 (Custom allocators): Add Order: 456ns (p50), 1,230ns (p99) Cancel Order: 234ns (p50), 678ns (p99) Throughput: 850K orders/second Phase 3 (Cache-optimized): Add Order: 312ns (p50), 891ns (p99) Cancel Order: 89ns (p50), 234ns (p99) Best Bid/Ask: 12ns (p50), 31ns (p99) Throughput: 2.4M orders/second -
Understanding of why your design choices affect performance
- Foundation for Project 3 (Matching Engine) which adds networking
5. Solution Architecture
5.1 High-Level Design
ORDER BOOK ENGINE ARCHITECTURE
+------------------------------------------------------------------------+
| ORDER BOOK ENGINE |
+------------------------------------------------------------------------+
| |
| +------------------------------------------------------------------+ |
| | ORDER INPUT | |
| | | |
| | +-----------+ +-----------+ +-----------+ | |
| | | Add Order | |Cancel Ord | |Modify Ord | | |
| | +-----+-----+ +-----+-----+ +-----+-----+ | |
| | | | | | |
| +---------+----------------+----------------+-----------------------+ |
| | | | |
| v v v |
| +------------------------------------------------------------------+ |
| | ORDER VALIDATOR | |
| | - Price > 0, Quantity > 0 | |
| | - Order ID unique (for adds), exists (for cancels) | |
| | - Side valid (BUY/SELL) | |
| +------------------------------------------------------------------+ |
| | |
| v |
| +------------------------------------------------------------------+ |
| | MATCHING ENGINE | |
| | | |
| | +----------------------------------------------------------+ | |
| | | ORDER BOOK (per symbol) | | |
| | | | | |
| | | +------------------+ +------------------+ | | |
| | | | BIDS (Buy) | | ASKS (Sell) | | | |
| | | | (desc by price) | | (asc by price) | | | |
| | | | | | | | | |
| | | | PriceLevel 50.26 | | PriceLevel 50.28 | | | |
| | | | +- Order Queue | | +- Order Queue | | | |
| | | | PriceLevel 50.25 | | PriceLevel 50.29 | | | |
| | | | +- Order Queue | | +- Order Queue | | | |
| | | | ... | | ... | | | |
| | | +------------------+ +------------------+ | | |
| | | | | |
| | | +--------------------------------------------------+ | | |
| | | | ORDER ID -> ORDER* MAP | | | |
| | | | (for O(1) cancel/modify by order_id) | | | |
| | | +--------------------------------------------------+ | | |
| | | | | |
| | +----------------------------------------------------------+ | |
| | | |
| +------------------------------------------------------------------+ |
| | |
| v |
| +------------------------------------------------------------------+ |
| | EVENT OUTPUT | |
| | | |
| | +----------+ +----------+ +----------+ +----------+ | |
| | |Order ACK | | Trade | | Cancel | | Market | | |
| | | | | Event | | ACK | | Data | | |
| | +----------+ +----------+ +----------+ +----------+ | |
| | | |
| +------------------------------------------------------------------+ |
| |
| +------------------------------------------------------------------+ |
| | MEMORY POOL | |
| | Pre-allocated Order objects for zero-allocation hot path | |
| +------------------------------------------------------------------+ |
| |
+------------------------------------------------------------------------+
5.2 Key Components
| Component | Responsibility | Performance Requirement |
|---|---|---|
| Order Validator | Validate order parameters before processing | O(1), < 50ns |
| Order Book | Maintain sorted price levels and order queues | O(log n) add, O(1) best price |
| Price Level | FIFO queue of orders at same price | O(1) add/remove from ends |
| Order Map | OrderID -> Order* for fast lookup | O(1) lookup and delete |
| Matching Logic | Execute crossing orders, generate trades | O(m) where m = matched orders |
| Memory Pool | Pre-allocated order storage | O(1) allocate/deallocate |
| Event Publisher | Output trades, acks, market data | Non-blocking, append-only |
5.3 Data Structures
Price Level Organization Options:
| Data Structure | Add Level | Remove Level | Find Best | Memory Overhead | Cache Behavior |
|---|---|---|---|---|---|
std::map<Price, Level> |
O(log n) | O(log n) | O(1) amortized | High (nodes) | Poor (pointer chase) |
| Sorted vector | O(n) | O(n) | O(1) | Low | Excellent |
| Skip list | O(log n) | O(log n) | O(1) | Medium | Medium |
| Array + hash map | O(1) | O(1) | O(1) | Medium | Excellent |
Recommended: Price Level Array
Price Level Array Design
Price Range: $100.00 - $200.00 at $0.01 increments = 10,000 possible levels
Array Size: 10,000 x sizeof(PriceLevel*) = 80KB (fits in L2 cache!)
Price Index = (price - base_price) / tick_size
+----------------------------------------------------------------+
| Index: 0 1 2 3 ... 9999 |
| Price: 100.00 100.01 100.02 100.03 ... 199.99 |
| | | | | ... | |
| v v v v v |
| NULL Level* NULL Level* ... NULL |
| | | |
| v v |
| +-----+ +-----+ |
| |Queue| |Queue| |
| |O1->O2 |O7->O8 |
| +-----+ +-----+ |
+----------------------------------------------------------------+
Best bid/ask tracking:
- best_bid_idx: index of highest non-empty bid level
- best_ask_idx: index of lowest non-empty ask level
After removing best level, scan for next non-empty level
(Typically 1-3 indices away, so O(1) in practice)
Order Queue: Intrusive Doubly-Linked List
Intrusive Linked List Design
Instead of:
std::list<Order*> // Allocates ListNode objects separately
Use intrusive:
struct Order {
Order* prev; // Part of Order struct itself
Order* next; // No separate allocation!
uint64_t id;
uint32_t qty;
// ...
};
Price Level Queue:
+-------------------------------------------------------------+
| head --> Order_A <--> Order_B <--> Order_C <-- tail |
| | | |
| +------------- FIFO queue ------------+ |
+-------------------------------------------------------------+
Operations:
Add to back: O(1) - tail->next = new; new->prev = tail; tail = new;
Remove any: O(1) - prev->next = next; next->prev = prev;
Get front: O(1) - return head;
Order Struct Memory Layout:
// BAD: Wasted space due to alignment padding (56 bytes with 11 wasted)
struct OrderBad {
char side; // 1 byte + 7 padding
double price; // 8 bytes
uint32_t quantity; // 4 bytes + 4 padding
uint64_t order_id; // 8 bytes
Order* next; // 8 bytes
Order* prev; // 8 bytes
uint64_t timestamp; // 8 bytes
};
// GOOD: Ordered by size to minimize padding (48 bytes, no waste)
struct OrderGood {
uint64_t order_id; // 8 bytes
uint64_t timestamp; // 8 bytes
double price; // 8 bytes
Order* next; // 8 bytes
Order* prev; // 8 bytes
uint32_t quantity; // 4 bytes
char side; // 1 byte
char padding[3]; // explicit padding
};
// BEST: Fixed-point price, minimal size (40 bytes)
struct OrderBest {
Order* next; // 8 bytes - hot path access first
Order* prev; // 8 bytes
uint64_t order_id; // 8 bytes
int64_t price_ticks; // 8 bytes (price in tick units, not float)
uint32_t quantity; // 4 bytes
uint16_t symbol_id; // 2 bytes
uint8_t side; // 1 byte
uint8_t flags; // 1 byte (canceled, partial, etc.)
};
5.4 Algorithm Overview
Add Order Algorithm:
function add_order(order):
// Step 1: Validate
if not valid(order):
return REJECTED
// Step 2: Check for match
if order.side == BUY:
while order.remaining_qty > 0 AND best_ask exists AND order.price >= best_ask.price:
match_at_level(order, best_ask_level)
else: // SELL
while order.remaining_qty > 0 AND best_bid exists AND order.price <= best_bid.price:
match_at_level(order, best_bid_level)
// Step 3: If remaining quantity, add to book
if order.remaining_qty > 0:
level = get_or_create_level(order.side, order.price)
level.add_order(order)
order_map[order.id] = order
update_best_price(order.side)
return order.status
function match_at_level(incoming, level):
for resting_order in level.orders: // FIFO order
match_qty = min(incoming.remaining_qty, resting_order.remaining_qty)
emit_trade(incoming, resting_order, match_qty, level.price)
incoming.remaining_qty -= match_qty
resting_order.remaining_qty -= match_qty
if resting_order.remaining_qty == 0:
level.remove_order(resting_order)
order_map.remove(resting_order.id)
order_pool.deallocate(resting_order)
if incoming.remaining_qty == 0:
break
if level.is_empty():
remove_level(level)
update_best_price(level.side)
Cancel Order Algorithm:
function cancel_order(order_id):
order = order_map.get(order_id)
if order is None:
return NOT_FOUND
level = get_level(order.side, order.price)
level.remove_order(order) // O(1) with doubly-linked list
if level.is_empty():
remove_level(level)
update_best_price(order.side)
order_map.remove(order_id)
order_pool.deallocate(order)
return CANCELED
6. Implementation Guide
6.1 Development Environment Setup
C++ Setup:
# Ubuntu/Debian
sudo apt-get update
sudo apt-get install g++ cmake gdb valgrind linux-tools-generic
# Verify compiler supports C++17/20
g++ --version # Need 7+ for C++17, 10+ for C++20
# Install perf for profiling (Linux)
sudo apt-get install linux-tools-common linux-tools-$(uname -r)
# macOS
xcode-select --install
brew install cmake
# Create project
mkdir -p orderbook/{src,include,tests,benchmarks}
cd orderbook
Rust Setup:
# Install Rust
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
source $HOME/.cargo/env
# Create project
cargo new orderbook
cd orderbook
# Add dependencies to Cargo.toml
cat >> Cargo.toml << 'EOF'
[dev-dependencies]
criterion = "0.5"
[[bench]]
name = "orderbook_bench"
harness = false
EOF
6.2 Project Structure
C++ Structure:
orderbook/
+-- CMakeLists.txt
+-- src/
| +-- main.cpp # CLI entry point
| +-- orderbook.cpp # Order book implementation
| +-- matching_engine.cpp # Matching logic
| +-- memory_pool.cpp # Custom allocator (Phase 2)
+-- include/
| +-- order.hpp # Order struct
| +-- orderbook.hpp # OrderBook class
| +-- price_level.hpp # PriceLevel with order queue
| +-- matching_engine.hpp # Matching interface
| +-- memory_pool.hpp # Pool allocator
+-- tests/
| +-- test_orderbook.cpp
| +-- test_matching.cpp
+-- benchmarks/
| +-- bench_orderbook.cpp
+-- README.md
Rust Structure:
orderbook/
+-- Cargo.toml
+-- src/
| +-- main.rs # CLI entry point
| +-- lib.rs # Library root
| +-- order.rs # Order struct
| +-- orderbook.rs # OrderBook implementation
| +-- price_level.rs # PriceLevel
| +-- matching.rs # Matching logic
+-- tests/
| +-- integration_tests.rs
+-- benches/
| +-- orderbook_bench.rs
+-- README.md
6.3 The Core Question You’re Answering
“How do you organize price levels and orders such that the most common operations (add order, match, cancel) are O(1) or O(log n) while maintaining cache efficiency?”
This question forces you to confront the reality that big-O notation alone is insufficient for HFT. An O(log n) tree operation with poor cache behavior can be slower than an O(n) scan of a cache-resident array.
The answer involves:
- Choosing data structures that keep hot data together in memory
- Minimizing pointer indirection (each pointer chase is a potential cache miss)
- Pre-allocating memory to avoid allocation in the hot path
- Using integer arithmetic (fixed-point prices) instead of floating-point
6.4 Concepts You Must Understand First
Before starting implementation, verify your understanding with these self-assessment questions:
| Concept | Self-Assessment Question | Where to Learn |
|---|---|---|
| Hash maps | What is the expected time complexity of insert/lookup? What happens during a resize? | CS:APP Ch. 6, Language docs |
| Linked lists | How do you remove a node from a doubly-linked list in O(1) when you have a pointer to that node? | Any data structures textbook |
| CPU cache hierarchy | What is a cache line (typically 64 bytes)? Why does data locality matter? | CS:APP Ch. 6 |
| Struct alignment | Why does the order of struct members affect sizeof? What is padding? | CS:APP Ch. 3.9 |
| Memory allocation | Why is malloc potentially slow? What is a memory pool? | CS:APP Ch. 9 |
| Fixed-point arithmetic | How do you represent $150.25 as an integer (15025 ticks)? Why prefer this over float? | Any numerics reference |
6.5 Questions to Guide Your Design
Data Structure Questions:
- How will you represent prices internally? (float, double, int64 ticks?)
- What data structure will hold all price levels? (map, vector, array?)
- How will you maintain FIFO order within a price level?
- How will you enable O(1) cancel-by-order-id?
- How will you track the best bid and best ask efficiently?
- What happens when a price level becomes empty?
Memory Questions:
- Will you allocate Order objects on demand or pre-allocate a pool?
- How much memory will your order book use with 100,000 orders?
- What is the size of your Order struct after considering alignment?
- Will your hot data structures fit in L1/L2/L3 cache?
Algorithm Questions:
- When a new buy order matches multiple sell orders, in what order are they filled?
- After filling the best ask level completely, how do you find the new best ask?
- What happens if a cancel arrives for an order that’s currently being matched?
- How do you handle partial fills (order partially matched, rest rests in book)?
Performance Questions:
- What operations happen most frequently? (Hint: typically cancel > add > match)
- Where will cache misses likely occur in your design?
- How will you benchmark your implementation?
- What is your target latency for each operation type?
6.6 Thinking Exercise
Before writing any code, work through this scenario by hand on paper:
Scenario:
Start with an empty order book. Process these orders in sequence:
1. ADD BUY 100 @ 50.25 order_A
2. ADD BUY 200 @ 50.24 order_B
3. ADD BUY 150 @ 50.25 order_C
4. ADD SELL 50 @ 50.30 order_D
5. ADD SELL 300 @ 50.25 order_E
6. CANCEL order_B
7. ADD SELL 100 @ 50.20 order_F
Questions to answer on paper:
-
After step 3, draw the bid side of the book. Which orders are at price 50.25, and in what FIFO order?
-
After step 4, what does the book look like? What trades (if any) were generated?
-
After step 5, what trades were generated? List each trade with: price, quantity, buyer order, seller order.
-
After step 5, what is the state of order_A? Order_C? Order_E?
-
After step 6, draw the full book (both bids and asks).
-
After step 7, what trades were generated? What is the final book state?
Verification:
- Total shares bought should equal total shares sold across all trades
- Every trade should have happened at the price of the resting (older) order
- FIFO should have been maintained within each price level
6.7 Hints in Layers
If you’re stuck, reveal hints one at a time: