What is an Order Book?
An order book is the core data structure used by exchanges to match buyers and sellers. Think of it as a live ledger showing all the buy orders (bids) on one side and all the sell orders (asks) on the other side, organized by price.
The Two Sides
Bids (Buy Orders): People wanting to buy an asset
- Arranged from highest price to lowest
- Example: Someone willing to pay $10,000 for Bitcoin
Asks (Sell Orders): People wanting to sell an asset
- Arranged from lowest price to highest
- Example: Someone willing to sell Bitcoin for $10,050
Key Concepts
Spread: The gap between the highest bid and lowest ask
- Best Bid: $10,000
- Best Ask: $10,050
- Spread: $50 (the difference)
Mid Price: The average of best bid and best ask
- Formula: (Best Bid + Best Ask) / 2
- Example: ($10,000 + $10,050) / 2 = $10,025
Price Level: A specific price point where one or more orders exist
- At $10,000 there might be 5 different buy orders totaling 10 BTC
The OrderBook-rs Implementation
This Rust library is designed for high-frequency trading (HFT) where microseconds matter. Let’s break down its architecture.
Core Design Philosophy
Lock-Free Architecture: Traditional systems use locks (like a bathroom door sign) where one thread must wait for another. This system uses atomics, think of it like many people editing different parts of a Google Doc simultaneously without blocking each other.
Why This Matters for HFT:
- Processes 200,000+ operations per second
- Multiple traders can place orders simultaneously
- No waiting in line – everyone operates concurrently
Performance Numbers (Real Tests)
HFT Simulation Results (5 seconds):
- 506,105 orders added (101,152/second)
- 314,245 orders matched (62,806/second)
- 204,047 orders cancelled (40,781/second)
- Total: 204,741 operations per second
Hot Spot Performance (when many traders target same price):
- 100% concentration: 19.4 MILLION operations/second
- This shows how well the lock-free design handles contention
Understanding Order Types
Basic Order Types
Limit Order: “I’ll buy at $10,000 or better”
- Sits in the order book until matched or cancelled
- You control the price but not the timing
Market Order: “Buy now at whatever price”
- Executes immediately against best available prices
- You control timing but not the price
Advanced Order Types
Iceberg Order: Shows only part of a large order
- Total: 1000 BTC, Visible: 100 BTC
- Prevents moving the market with one big order
Fill-or-Kill (FOK): Either execute entire order immediately or cancel
- “Buy 100 BTC at $10,000 – all or nothing”
- No partial fills allowed
Immediate-or-Cancel (IOC): Execute what you can right now, cancel the rest
- “Buy up to 100 BTC at $10,000 immediately”
- Accepts partial fills
Post-Only: Only add liquidity, never take it
- Order will be cancelled if it would match immediately
- Used by market makers to avoid fees
Good-Till-Date (GTD): Expires at specific time
- “Keep this order active until Friday 3pm”
How Matching Works
Price-Time Priority
Orders match based on two rules:
- Best price wins: Highest bid matches lowest ask
- First in time wins: If prices are equal, older order gets filled first
Example Matching Flow
Order Book State:
ASKS (Sell Orders)
$10,070 → 50 BTC
$10,050 → 100 BTC
$10,000 → 75 BTC
BIDS (Buy Orders)
$9,900 → 80 BTC
$9,850 → 120 BTC
New Market Buy Order: 150 BTC at market price
Matching Process:
- Takes 75 BTC at $10,000 (clears that level)
- Takes 75 BTC at $10,050 (partial fill of that level)
- Order fully filled, 25 BTC remains at $10,050
Advanced Market Analysis Features
VWAP (Volume-Weighted Average Price)
Shows the “true” average price weighted by volume.
Formula: Sum(Price × Volume) / Total Volume
Example:
- 100 BTC at $10,000 = $1,000,000
- 50 BTC at $10,050 = $502,500
- VWAP = $1,502,500 / 150 BTC = $10,016.67
Why it matters: Better than simple average for understanding actual market price.
Market Impact
Predicts how much your order will move the market.
Scenario: You want to buy 500 BTC
- First 100 BTC at $10,000
- Next 200 BTC at $10,050
- Next 200 BTC at $10,100
- Average execution: $10,066.67
- Slippage: $66.67 per BTC
Order Book Imbalance
Measures buy vs sell pressure.
Formula: (Bid Volume – Ask Volume) / Total Volume
Results:
- +1.0 = All bids (strong buying pressure)
- -1.0 = All asks (strong selling pressure)
- 0.0 = Balanced
Trading Signal: Imbalance can predict short-term price movement.
Data Structures Used
DashMap (Concurrent HashMap)
Stores orders with O(1) lookup time by OrderId.
Why not regular HashMap?
- Regular HashMap needs a lock for every operation
- DashMap allows multiple threads to read/write simultaneously
- Each bucket has its own lock (fine-grained locking)
SegQueue (Lock-Free Queue)
Maintains FIFO order for matching.
How it works:
- Uses atomic compare-and-swap operations
- No traditional locks – uses CPU-level atomics
- Multiple threads can enqueue/dequeue simultaneously
Skip List for Price Levels
Organizes prices for fast lookups.
Structure:
Level 3: $9,800 ---------> $10,000 ---------> $10,200
Level 2: $9,800 -> $9,900 -> $10,000 -> $10,100 -> $10,200
Level 1: $9,800 -> $9,850 -> $9,900 -> $9,950 -> $10,000 -> $10,050 -> $10,100 -> $10,150 -> $10,200
Advantages:
- O(log n) search time instead of O(n)
- Concurrent modifications without locking
- Fast best bid/ask lookups
Memory and Performance Optimization
Price Level Cache
Caches the best bid and best ask to avoid searching.
Before: Search through all price levels After: Direct lookup in cache Speedup: O(log n) → O(1)
Matching Pool
Reuses memory allocations during matching.
Problem: Allocating memory millions of times per second is slow Solution: Pre-allocate a pool and reuse objects Result: Reduced latency and less garbage collection
Practical Trading Applications
Market Making Strategy
Current State:
Best Bid: $10,000
Best Ask: $10,050
Spread: $50
Strategy:
- Place bid at $10,010 (inside spread)
- Place ask at $10,040 (inside spread)
- Profit: $30 per BTC on each round trip
- Risk: Price moves before both sides fill
Queue Position Analysis
Function: queue_ahead_at_price()
Question: If I place a buy order at $10,000, how many orders are ahead of me?
Answer: 150 BTC already waiting at that price
Decision: Either place at $10,001 to jump the queue, or wait in line
Depth-Based Pricing
Function: price_at_depth_adjusted()
Goal: Find price where there’s 1000 BTC of liquidity
Process:
- Sum volumes starting from best bid
- Stop when cumulative reaches 1000 BTC
- Return that price level
Use: Determine realistic execution price for large orders
Thread Safety in Action
Concurrent Operations Example
30 threads running simultaneously:
- 10 threads adding orders
- 10 threads matching/executing orders
- 10 threads cancelling orders
No conflicts because:
- Each price level operates independently
- Lock-free data structures use atomics
- DashMap allows concurrent access to different orders
Why Traditional Locks Fail Here
Problem with locks:
Thread 1: Wants to add order at $10,000
Thread 2: Wants to match order at $10,000
Thread 3: Wants to cancel order at $10,000
Traditional: All three wait in line (slow)
Lock-Free: All three proceed simultaneously
Real-World Performance Characteristics
Price Level Distribution Impact
Optimal: 50-100 price levels → 66,000 ops/sec Too Few: 1-10 levels → 23,000 ops/sec
Too Many: 500+ levels → performance degrades
Why: Sweet spot balances memory locality with search efficiency.
Hot Spot Behavior
Counterintuitive Result: Performance INCREASES with contention
Explanation:
- All data fits in CPU cache
- No cache misses across memory
- Atomic operations are extremely fast when data is hot
Key Takeaways for HFT Development
Correctness First
- Even at 200,000 ops/sec, every trade must be accurate
- Price-time priority must be strictly maintained
- No lost or duplicate orders
Latency Matters
- Microseconds determine profitability in HFT
- Lock-free beats locks by orders of magnitude
- Memory allocation is the enemy – pool and reuse
Scalability
- Design for millions of orders, not thousands
- Concurrent access is the norm, not exception
- Test under realistic multi-threaded load
Monitoring
- Track spread, imbalance, VWAP in real-time
- Detect thin liquidity conditions
- Measure your own market impact
Further Learning
Concepts to Explore
- Order book depth visualization
- Market microstructure theory
- Liquidity provision strategies
- Statistical arbitrage using order flow
Technical Deep Dives
- Compare-and-swap (CAS) operations
- Cache coherency protocols
- False sharing in concurrent systems
- Memory barriers and ordering
Leave a Reply