Building an Ultra-Low Latency Order Book — Low-Level Design for High-Frequency Trading

Table of contents

Why HFT?

High-frequency trading (HFT) firms make billions by being milliseconds faster than everyone else. Citadel Securities, Jump Trading, Tower Research — they all compete on latency. A strategy that makes money at 10 microseconds of latency might lose money at 100 microseconds.

This isn’t just about speed — it’s about understanding every layer of the system and optimizing each one. Let’s build one.

Market Microstructure 101

Before we write code, we need to understand how markets actually work.

What Is an Order Book?

An order book is a list of all buy and sell orders for a stock, organized by price level. Think of it like a marketplace:

Price    │ Size  │ Side
─────────┼───────┼─────
105.50   │ 200   │ Sell (Ask)
105.40   │ 150   │ Sell (Ask)
105.30   │ 300   │ Sell (Ask)
─────────┼───────┼─────  ← Spread (30 cents)
105.00   │ 180   │ Buy (Bid)
104.90   │ 250   │ Buy (Bid)
104.80   │ 400   │ Buy (Bid)

• Bid: The highest price someone is willing to pay
• Ask: The lowest price someone is willing to sell
• Spread: The gap between best bid and best ask
• Mid-price: The average of best bid and best ask

Order Types

Market Order:  "Buy/Sell immediately at best available price"
Limit Order:   "Buy at $X or less / Sell at $X or more"
Stop Order:    "Trigger a market order when price reaches $X"
Iceberg Order: "Show only 100 shares publicly, hide the rest"

Market Data Feed

Exchanges send real-time market data via feeds:

NASDAQ ITCH Feed (binary, ~500MB/s):
  - Order Added:      Stock=AAPL, Price=105.30, Size=500, Side=Buy
  - Order Executed:   Stock=AAPL, Price=105.30, Size=100
  - Order Cancelled:  Stock=AAPL, OrderID=12345
  - Price Level Update: Stock=AAPL, Price=105.30, Size=400 (was 500)

The Order Book Data Structure

Naive Approach: Sorted Lists

The simplest approach — two sorted lists (bids and asks):

struct Order {
    uint64_t id;
    double price;
    int size;
    Side side;
    uint64_t timestamp;
};

class OrderBook {
    std::vector<Order> bids;  // Sorted descending by price
    std::vector<Order> asks;  // Sorted ascending by price
};

Problem: Inserting an order is O(n) because you need to find the right position. With millions of orders, this is too slow.

Better Approach: Skip Lists

Skip lists give O(log n) insert, delete, and lookup:

template<typename T>
class SkipList {
    struct Node {
        T data;
        std::vector<Node*> next;
        int level;
    };

    Node* head;
    int maxLevel;
    std::mt19937 rng;

    int randomLevel() {
        int level = 1;
        while (rng() % 2 == 0 && level < maxLevel)
            level++;
        return level;
    }

public:
    void insert(const T& data) {
        std::vector<Node*> update(maxLevel, head);
        Node* current = head;

        for (int i = maxLevel - 1; i >= 0; i--) {
            while (current->next[i] && current->next[i]->data < data) {
                current = current->next[i];
            }
            update[i] = current;
        }

        int newLevel = randomLevel();
        Node* newNode = new Node{data, std::vector<Node*>(newLevel), newLevel};

        for (int i = 0; i < newLevel; i++) {
            newNode->next[i] = update[i]->next[i];
            update[i]->next[i] = newNode;
        }
    }
};

Why skip lists over red-black trees?

1. Simpler to implement and debug
2. Better cache locality for sequential access
3. Easier to make lock-free (we’ll get to that)
4. Financial industry standard (used by many exchange implementations)

Best Approach: Price-Level Map + Order Map

The real structure uses two maps:

class OrderBook {
    // price -> queue of orders at that price
    std::map<double, std::deque<Order>, std::greater<double>> bids;
    std::map<double, std::deque<Order>, std::less<double>> asks;

    // order_id -> order (for O(1) lookup/cancel)
    std::unordered_map<uint64_t, Order> orderMap;

    double bestBid() const { return bids.begin()->first; }
    double bestAsk() const { return asks.begin()->first; }
    double spread() const { return bestAsk() - bestBid(); }
    double midPrice() const { return (bestBid() + bestAsk()) / 2.0; }

    void addOrder(const Order& order) {
        auto& levels = order.side == Side::Buy ? bids : asks;
        levels[order.price].push_back(order);
        orderMap[order.id] = order;
    }

    void cancelOrder(uint64_t orderId) {
        auto it = orderMap.find(orderId);
        if (it == orderMap.end()) return;

        auto& levels = it->second.side == Side::Buy ? bids : asks;
        auto& queue = levels[it->second.price];

        queue.erase(
            std::remove_if(queue.begin(), queue.end(),
                [orderId](const Order& o) { return o.id == orderId; }),
            queue.end()
        );

        if (queue.empty()) levels.erase(it->second.price);
        orderMap.erase(it);
    }
};

Why this structure?

• Price levels are sorted (map)
• Orders at same price are FIFO (deque) — time priority
• O(log n) for price level operations
• O(1) for order lookup by ID
• O(1) amortized for matching

Matching Engine: Where Trades Happen

The matching engine is the heart of the system. It takes incoming orders and matches them against existing orders:

class MatchingEngine {
    OrderBook& book;
    std::vector<Trade> trades;

public:
    std::vector<Trade> processOrder(const Order& incoming) {
        std::vector<Trade> result;

        if (incoming.side == Side::Buy) {
            result = matchBuy(incoming);
        } else {
            result = matchSell(incoming);
        }

        // If order not fully filled, add to book
        if (remainingSize(incoming) > 0) {
            book.addOrder(incoming);
        }

        return result;
    }

private:
    std::vector<Trade> matchBuy(const Order& buy) {
        std::vector<Trade> result;
        int remaining = buy.size;

        // Match against asks (lowest first)
        while (remaining > 0 && !book.asks.empty()) {
            auto& [price, orders] = *book.asks.begin();

            if (buy.price < price) break;  // Limit order can't match

            while (remaining > 0 && !orders.empty()) {
                auto& sell = orders.front();
                int fillSize = std::min(remaining, sell.size);

                result.push_back({
                    .price = price,
                    .size = fillSize,
                    .buyOrderId = buy.id,
                    .sellOrderId = sell.id,
                    .timestamp = now()
                });

                remaining -= fillSize;
                sell.size -= fillSize;

                if (sell.size == 0) {
                    orders.pop_front();
                    book.orderMap.erase(sell.id);
                }
            }

            if (orders.empty()) {
                book.asks.erase(book.asks.begin());
            }
        }

        return result;
    }
};

Price-Time Priority

Orders are matched in two steps:

1. Price priority: Best price first (highest bid, lowest ask)
2. Time priority: Earlier orders at same price first (FIFO)

Example:
Ask queue at $105.30:
  [Order A (10:00:01), Order B (10:00:02), Order C (10:00:03)]

Incoming buy order for 500 shares at $105.30:
  - Fill 200 from Order A (oldest first)
  - Fill 200 from Order B
  - Fill 100 from Order C
  - Order C still has 200 remaining

Lock-Free Data Structures

In HFT, you can’t afford locks. A mutex lock can take 10-100 nanoseconds — that’s an eternity when your target is microsecond-level latency.

Compare-and-Swap (CAS)

CAS is the building block of lock-free programming:

template<typename T>
class LockFreeQueue {
    struct Node {
        T data;
        std::atomic<Node*> next;
        Node(const T& d) : data(d), next(nullptr) {}
    };

    std::atomic<Node*> head;
    std::atomic<Node*> tail;

public:
    void push(const T& data) {
        Node* newNode = new Node(data);
        Node* currentTail = tail.load(std::memory_order_relaxed);
        Node* next = nullptr;

        while (true) {
            if (currentTail->next.compare_exchange_weak(
                    next, newNode,
                    std::memory_order_release,
                    std::memory_order_relaxed)) {
                // Successfully linked the new node
                tail.compare_exchange_strong(
                    currentTail, newNode,
                    std::memory_order_release,
                    std::memory_order_relaxed);
                return;
            }
        }
    }

    bool pop(T& data) {
        Node* currentHead = head.load(std::memory_order_relaxed);
        Node* currentTail = tail.load(std::memory_order_relaxed);
        Node* next = currentHead->next.load(std::memory_order_relaxed);

        if (currentHead == currentTail) {
            if (next == nullptr) return false;  // Empty
            // Tail is lagging, advance it
            tail.compare_exchange_strong(
                currentTail, next,
                std::memory_order_release,
                std::memory_order_relaxed);
        } else {
            data = next->data;
            head.compare_exchange_strong(
                currentHead, next,
                std::memory_order_release,
                std::memory_order_relaxed);
            delete currentHead;
            return true;
        }
        return false;
    }
};

Memory Ordering

std::memory_order controls how operations on different threads are synchronized:

// Relaxed: No ordering guarantees (just atomicity)
std::memory_order_relaxed

// Acquire: Prevents reads/writes after this from being reordered before
std::memory_order_acquire

// Release: Prevents reads/writes before this from being reordered after
std::memory_order_release

// Acquire-Release: Full synchronization
std::memory_order_acq_rel

// Sequential Consistency: Strongest ordering (slowest)
std::memory_order_seq_cst

Rule of thumb: Use relaxed for counters, acquire/release for producer-consumer patterns, seq_cst when you’re unsure.

Kernel Bypass Networking

Traditional networking goes through the kernel, which adds latency:

Traditional:
App → Kernel (syscalls, copies) → NIC Driver → NIC → Network
     ↑ ~1-5 microseconds overhead ↑

Kernel Bypass (DPDK):
App → NIC directly (no kernel involvement)
     ↑ ~100 nanoseconds ↑

DPDK (Data Plane Development Kit)

DPDK gives you direct access to NIC memory:

// Initialize DPDK
rte_eal_init(argc, argv);
rte_eth_dev_configure(port, 1, 1, &port_conf);
rte_eth_rx_queue_setup(port, 0, 128, socket_id, &rx_conf, mbuf_pool);
rte_eth_tx_queue_setup(port, 0, 128, socket_id, &tx_conf);
rte_eth_dev_start(port);

// Receive packets (no kernel involved)
struct rte_mbuf *pkts[BURST_SIZE];
uint16_t nb_rx = rte_eth_rx_burst(port, 0, pkts, BURST_SIZE);

// Process and send
for (int i = 0; i < nb_rx; i++) {
    process_packet(pkts[i]);
    rte_eth_tx_burst(port, 0, &pkts[i], 1);
}

Real-world impact: DPDK can reduce latency from ~5 microseconds to ~500 nanoseconds. That’s a 10x improvement just from removing kernel overhead.

XDP (eXpress Data Path)

XDP is a lighter-weight alternative to DPDK — it runs inside the kernel but at the earliest possible point:

SEC("xdp")
int xdp_prog(struct xdp_md *ctx) {
    void *data = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;

    struct ethhdr *eth = data;
    if (eth + 1 > data_end) return XDP_PASS;

    // Custom packet processing at line rate
    if (eth->h_proto == htons(ETH_P_IP)) {
        return process_ip_packet(data, data_end);
    }

    return XDP_PASS;
}

XDP is faster than DPDK for simple packet processing but less flexible.

FPGA for Trading

FPGAs (Field-Programmable Gate Arrays) are hardware chips that can be reconfigured for specific tasks. HFT firms use them to implement trading logic in hardware:

Network → FPGA (matches orders in hardware) → Network
         ↑ ~50 nanoseconds total latency ↑

Why FPGA?

• Deterministic latency: No OS jitter, no garbage collection pauses
• Parallel processing: Process multiple data streams simultaneously
• Custom protocols: Implement proprietary protocols directly in hardware

FPGA Order Matching Example (Verilog)

module order_matcher (
    input wire clk,
    input wire rst,
    input wire [31:0] order_price,
    input wire [31:0] order_size,
    input wire order_side,  // 0=buy, 1=sell
    input wire order_valid,
    output wire matched,
    output wire [31:0] match_price,
    output wire [31:0] match_size
);

    // Price levels stored in BRAM (Block RAM)
    reg [31:0] bid_prices [0:255];
    reg [31:0] bid_sizes [0:255];
    reg [7:0] bid_count;

    always @(posedge clk) begin
        if (rst) begin
            bid_count <= 0;
        end else if (order_valid && !order_side) begin
            // Try to match against asks
            // If no match, add to bid book
            // All in one clock cycle!
        end
    end
endmodule

Real-world latency comparison:

Backtesting Engine

A backtesting engine simulates your strategy against historical data. It’s how you prove your strategy works before risking real money.

Architecture

┌─────────────────────────────────────────────────┐
│                Backtesting Engine                │
├─────────────────────────────────────────────────┤
│                                                 │
│  ┌──────────────┐  ┌──────────────┐            │
│  │  Historical  │  │   Strategy   │            │
│  │    Data      │→│    Engine    │            │
│  │   (tick)     │  │              │            │
│  └──────────────┘  └──────┬───────┘            │
│                           │                     │
│                    ┌──────▼───────┐            │
│                    │    Order     │            │
│                    │    Book      │            │
│                    │  (simulated) │            │
│                    └──────┬───────┘            │
│                           │                     │
│                    ┌──────▼───────┐            │
│                    │  P&L Report  │            │
│                    │  (metrics)   │            │
│                    └──────────────┘            │
└─────────────────────────────────────────────────┘

Event-Driven Architecture

class BacktestingEngine {
    OrderBook book;
    Strategy& strategy;
    std::vector<Trade> trades;
    double pnl = 0;

public:
    void processEvent(const MarketEvent& event) {
        switch (event.type) {
            case EventType::OrderAdded:
                processOrderAdded(event);
                break;
            case EventType::OrderExecuted:
                processOrderExecuted(event);
                break;
            case EventType::OrderCancelled:
                processOrderCancelled(event);
                break;
        }

        // Let strategy react
        auto signals = strategy.onMarketUpdate(book);
        for (const auto& signal : signals) {
            processSignal(signal);
        }
    }

private:
    void processOrderExecuted(const MarketEvent& event) {
        // Find matching strategy order
        for (auto& trade : trades) {
            if (trade.orderId == event.orderId) {
                double execPrice = event.price;
                double execSize = event.size;

                // Update P&L
                if (trade.side == Side::Buy) {
                    pnl -= execPrice * execSize;
                } else {
                    pnl += execPrice * execSize;
                }

                trade.filledSize += execSize;
                break;
            }
        }
    }
};

Performance Metrics

A good backtesting engine calculates:

struct BacktestResults {
    double totalPnl;
    double sharpeRatio;      // Risk-adjusted return
    double maxDrawdown;      // Worst peak-to-trough
    double winRate;          // % of profitable trades
    double profitFactor;     // Gross profit / Gross loss
    int totalTrades;
    double avgTradePnl;
    double avgHoldingTime;
    double latencyP50;       // 50th percentile latency
    double latencyP99;       // 99th percentile latency
    double latencyP999;      // 99.9th percentile latency
};

Walk-Forward Optimization

Don’t just backtest once. Use walk-forward optimization:

Period 1: Train on Jan-Mar, Test on Apr
Period 2: Train on Feb-Apr, Test on May
Period 3: Train on Mar-May, Test on Jun
...

This prevents overfitting — your strategy works on data it’s never seen, not just on historical data it was optimized for.

Complete System Architecture

Putting it all together:

┌─────────────────────────────────────────────────────────────┐
│                    HFT System Architecture                  │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  ┌──────────┐    ┌──────────┐    ┌──────────┐            │
│  │ Market   │    │ Strategy │    │ Order    │            │
│  │ Data     │───│ Engine   │───│ Router   │            │
│  │ Feed     │    │          │    │          │            │
│  └──────────┘    └──────────┘    └──────────┘            │
│       │               │               │                    │
│       │          ┌────▼────┐          │                    │
│       │          │  Risk   │          │                    │
│       │          │  Engine │          │                    │
│       │          └─────────┘          │                    │
│       │                               │                    │
│  ┌────▼─────────────────────────────▼────┐              │
│  │           Order Book (Lock-Free)       │              │
│  │  ┌─────────┐  ┌─────────┐  ┌───────┐ │              │
│  │  │  Bids   │  │  Asks   │  │Orders │ │              │
│  │  │(Skip    │  │(Skip    │  │(Hash  │ │              │
│  │  │ List)   │  │ List)   │  │ Map)  │ │              │
│  │  └─────────┘  └─────────┘  └───────┘ │              │
│  └─────────────────────────────────────────┘              │
│                        │                                   │
│  ┌─────────────────────▼───────────────────────┐         │
│  │          Network Layer (Kernel Bypass)        │         │
│  │  ┌─────────┐  ┌─────────┐  ┌─────────────┐ │         │
│  │  │  DPDK   │  │   XDP   │  │   FPGA      │ │         │
│  │  └─────────┘  └─────────┘  └─────────────┘ │         │
│  └───────────────────────────────────────────────┘         │
│                        │                                   │
│                  Exchange Network                          │
└─────────────────────────────────────────────────────────────┘

Building Your Own

If you want to build this yourself, start here:

1. Phase 1: Basic order book with matching engine (C++ or Rust)
2. Phase 2: Add market data feed parser (NASDAQ ITCH or similar)
3. Phase 3: Implement a simple strategy (mean reversion, momentum)
4. Phase 4: Build backtesting engine with historical data
5. Phase 5: Optimize with lock-free structures
6. Phase 6: Add kernel bypass networking
7. Phase 7: FPGA implementation (if you’re ambitious)

Resources

• Books: “Trading and Exchanges” by Larry Harris, “Algorithmic Trading” by Ernest Chan
• Papers: “The Microstructure of the ‘Flash Crash’” by Kirilenko et al.
• Exchanges: CME, NASDAQ, and ICE provide historical data for backtesting
• Open Source: QuantLib, R-libtrading, and various GitHub projects

Conclusion

Building an HFT system is one of the most challenging engineering problems. It requires understanding hardware, networking, algorithms, and finance at a deep level.

But even if you never work at a trading firm, the skills you learn — lock-free programming, kernel bypass networking, FPGA development, low-latency system design — are valuable everywhere. These are the skills that separate good engineers from great ones.

The key insight: in HFT, every nanosecond matters. Every layer of abstraction has a cost. The best engineers are the ones who understand exactly where those costs are and can eliminate them.