⚡ Limit Order Book

A from-scratch C++20 matching engine implementing price-time priority (FIFO) matching — the same core mechanism behind every stock exchange, crypto exchange, and HFT system.

~180–300 ns/order · ~3.3–5.4M orders/sec · O(1) cancellation (measured, not marketing — see Benchmarks)

---

Table of Contents

• The Problem
• Why This Project
• How It Works
• Architecture
• Features
• Quick Start
• Example Output
• Measured Performance
• Design Decisions
• Limitations
• Roadmap
• Project Structure
• License

---

🧩 The Problem

Every exchange — NASDAQ, NSE, Binance — runs on the same basic idea: people submit buy and sell orders at specific prices, and the exchange must match them fairly and instantly.

• Fair → if two people bid the same price, whoever arrived first fills first. This is called FIFO / time priority.
• Instant → this has to happen in microseconds, because thousands of orders can arrive every second.

That's simple to say, but hard to build efficiently:

• Finding the best price instantly — without scanning every order
• Cancelling any order instantly by ID — without scanning the book
• Enforcing strict arrival-order fairness at every price level
• Doing all of this with minimal memory allocation and cache misses

This project builds that engine from scratch, and benchmarks it honestly on real hardware.

---

🎯 Why This Project

Audience	What this gives you
Quant / trading-systems interview prep	"Build a limit order book" is one of the most common systems-design questions at prop trading firms. This is a working reference you can read, run, and explain line-by-line.
Low-latency C++ learners	Shows why std::map + std::list + std::unordered_map beats a naive array-based book — and where the real bottlenecks still are.
Anyone curious how exchanges work	The demo walks through real scenarios — partial fills, FIFO priority, cancellation — with plain-English output, no finance background needed.

---

🔄 How It Works

Order matching:

flowchart TD
    A[New order arrives] --> B{Crosses the book?}
    B -->|Yes| C[Match against opposite side]
    C --> D[Fill oldest resting order first]
    D --> E{Fully filled?}
    E -->|No, quantity remains| C
    E -->|Yes| F[Trade recorded]
    B -->|No| G[Rest order in book, end of queue]
    G --> F

Loading

Cancellation:

flowchart LR
    A[Cancel order by ID] --> B[Hash map lookup, constant time]
    B --> C[Jump to exact list position]
    C --> D[Remove from linked list]
    D --> E{Price level now empty?}
    E -->|Yes| F[Remove price level]
    E -->|No| G[Done]

Loading

---

🏗️ Architecture

                BIDS (Buy Side)                      ASKS (Sell Side)
             sorted: HIGH → LOW                   sorted: LOW → HIGH
        ┌───────────────────────┐            ┌───────────────────────┐
        │  100.75 → Order A     │            │  100.80 → Order D     │
        │  100.50 → Order B, C  │ ← spread → │  101.00 → Order E     │
        │  100.25 → Order F     │            │  101.25 → Order G     │
        └───────────────────────┘            └───────────────────────┘

Each price level (e.g. 100.50 → Order B, C) is a std::list<Order> in strict arrival order — new orders are pushed to the back, fills are taken from the front. That's what enforces FIFO / time priority.

Sitting alongside the book, a std::unordered_map<OrderId, Location> maps every live order directly to its side, price, and exact position in that list — so cancelOrder(id) never has to search through a single price level or the map itself.

Structure	Why it's used	What it gives you
std::map<Price, list>	Keeps price levels sorted automatically	O(log P) insert; begin() is always the best price
std::list<Order> per level	Preserves arrival order	O(1) push to back, O(1) pop from front — this is FIFO
std::unordered_map<OrderId, ...>	Direct order lookup	O(1) cancel-by-id instead of scanning the book

---

✨ Features

• Full price-time priority matching (FIFO at every level)
• Partial fills across multiple resting orders
• O(1) order cancellation by ID
• Best bid / best ask lookup in O(1)
• Order book depth printer for visual inspection
• A benchmark harness measuring real throughput/latency

---

🚀 Quick Start

git clone https://github.com/<your-username>/limit-order-book-cpp.git
cd limit-order-book-cpp
make            # builds ./demo and ./benchmark
./demo          # walks through matching, FIFO, partial fills, cancellation
./benchmark     # measures real throughput/latency on YOUR machine

Requires a C++20 compiler — tested with g++ 13 (Linux) and Apple clang 17 (macOS).

---

📖 Example Output

=== Incoming sell crosses the book, fills FIFO ===
  TRADE: resting #1 x aggressor #6 | price=10050 qty=100
  TRADE: resting #5 x aggressor #6 | price=10050 qty=20
Remaining volume at 100.50: 30 (expected 30, from #5)

Order #1 arrived before order #5 at the same price, so it fills first — the book enforces arrival order automatically, without the incoming order needing to know or care.

---

📊 Measured Performance

Real numbers from ./benchmark, 1,000,000 randomly generated orders, -O2:

Machine	Avg latency/order	Throughput	Avg latency/cancel
Apple M-series (clang 17)	~183 ns	~5.45M orders/sec	~192 ns
x86_64 container (g++ 13)	~275–300 ns	~3.3–3.6M orders/sec	~350–370 ns

Run it yourself — results depend on CPU, compiler, and allocator. Quote your own numbers if you cite this project anywhere.

---

🔍 Design Decisions

• Integer price ticks, not floats — avoids rounding/comparison bugs at price boundaries.
• Templated matching function — bids and asks are different C++ types (different std::map comparators), so the shared matching logic is a template instead of duplicated code.
• std::list over a vector — O(1) removal from the middle via a stored iterator. The tradeoff is a heap allocation per order node (see Limitations).

⚠️ Limitations

• Single-threaded — no lock contention modeling
• std::list allocates per order node; production engines typically use intrusive lists or pool allocators to avoid this
• No market orders, stop orders, or cancel-replace — vanilla limit orders only
• No persistence, networking, or exchange protocol (FIX/ITCH) — this is the matching core, not a full exchange

🗺️ Roadmap

• Cancel-replace (modify quantity/price)
• Market orders
• Intrusive linked list to remove per-order heap allocation
• Multi-threaded ingestion with a lock-free queue

---

📂 Project Structure

include/Order.hpp        Order struct + core type aliases
include/OrderBook.hpp    OrderBook class + templated matching engine
src/OrderBook.cpp        addOrder / cancelOrder / bestBid / bestAsk / printBook
src/main.cpp             Demo walking through matching scenarios
src/benchmark.cpp        Throughput/latency benchmark
Makefile                 make -> builds ./demo and ./benchmark

📄 License

MIT — use it, learn from it, extend it.