orderbook-rs

OrderBook-rs is a high-performance, thread-safe limit order book engine implemented in Rust. It is designed for low-latency trading systems, focusing on concurrent access patterns and lock-free data structures to maximize throughput in high-frequency trading (HFT) scenarios.

Key Capabilities

• Lock-Free Architecture: Uses atomics and lock-free structures to minimize thread contention.
• Diverse Order Types: Supports limit, iceberg, post-only, fill-or-kill (FOK), immediate-or-cancel (IOC), good-till-date, trailing stop, pegged, market-to-limit, and reserve orders.
• Concurrent Price Levels: Each price level can be modified independently by multiple threads without blocking.
• Scalability: Designed to handle millions of orders and thousands of price levels with minimal memory overhead.
• Performance Monitoring: Includes built-in statistics tracking for benchmarking.

OrderBook-rs provides zero-allocation, lazy iterators for efficient depth analysis. These allow you to traverse the book without allocating large vectors.

• levels_until_depth(side, depth): Iterate through levels until a cumulative depth is reached.
• levels_with_cumulative_depth(side, levels): Iterate through a fixed number of levels, providing cumulative size at each step.
• levels_in_range(side, min_price, max_price): Iterate through levels within a specific price range.

// Iterate with cumulative depth tracking
for level in book.levels_with_cumulative_depth(Side::Sell, 10) {
    println!("Price: {}, Size: {}, Cumulative: {}", 
             level.price, level.size, level.cumulative);
}

// Iterate until cumulative depth reached
let levels: Vec<_> = book
    .levels_until_depth(Side::Buy, 1000)
    .collect();

// Combine with functional operations
let total_volume: u64 = book
    .levels_until_depth(Side::Buy, 5000)
    .map(|level| level.size)
    .sum();

The HDR (High Dynamic Range) benchmarks in orderbook-rs follow these principles:

• Histogram Resolution: Uses Histogram::<u64> sized for 1 ns to 1 s with three significant figures.
• Sample Collection: Uses std::time::Instant::now() around a closure, with std::hint::black_box to prevent compiler optimizations from removing measured code.
• Warmup: Long-running scenarios (like add_only or mixed_70_20_10) discard the first 200,000 operations before measurement. Pre-loading scenarios seed the book in a non-measured loop.
• Workload Determinism: Uses a self-contained xorshift PRNG seeded with 0xA5A5_A5A5_A5A5_A5A5_A5A5 to ensure reproducible operation streams.
• Closed-loop (Coordinated Omission): The driver waits for each engine call to return before issuing the next. This measures pure service time. It systematically under-reports tail latencies compared to a real-world load generator because it does not account for queueing delays that occur under saturation.
• CPU Pinning: On Linux, you can reduce variance by pinning to a specific core using taskset -c <core>.

The OrderQueue within a PriceLevel uses a hybrid lock-free architecture to prevent deadlocks and maximize throughput under high contention.

Architecture

Instead of a single queue that requires draining to find or remove specific orders, the system uses:

1. dashmap::DashMap: Stores orders to allow $O(1)$ average-case time complexity for insertions, lookups, and removals by Id.
2. crossbeam_skiplist::SkipMap<sequence, Id>: A sequence-keyed index that maintains FIFO (First-In-First-Out) order for matching, while allowing $O(\log n)$ ordered iteration and deterministic snapshots.

Performance Characteristics

• High Contention (Hot Spots): The architecture is highly efficient when operations are concentrated on a single price level, capable of reaching tens of millions of operations per second.
• Price Level Distribution: Optimal performance is typically observed with 50-100 price levels. Performance may degrade if the number of price levels is very low (1-10), as per-level contention increases.

The binary wire protocol uses a fixed-layout, little-endian framing. Every frame consists of a length prefix, a message kind, and a payload. Frames are contiguous; there are no separators or trailers. Decoders should advance their read cursor by the bytes_consumed value returned from decode_frame.

Frame Layout:

Note: The minimum legal len is 1 (kind byte present, zero-byte payload).

+-------------------+--------+--------------------------+
| len (u32 LE)      | kind   | payload                  |
| 4 B               | 1 B    | len - 1 B                |
+-------------------+--------+--------------------------+