Lock-Free Data Structures for Low-Latency Trading

How we implemented a lock-free orderbook cache using arc_swap and dashmap to minimize latency in our arbitrage detection loop.

The Problem

In a trading system, market data flows continuously from exchange WebSockets while the arbitrage detector reads orderbook state to identify opportunities. The traditional approach uses RwLock:

// Naive approach - contention under load
struct OrderbookStore {
    books: RwLock<HashMap<String, OrderBook>>,
}

This creates contention: readers block when a writer holds the lock, and writers must wait for all readers to release. In a hot loop checking arbitrage conditions, even microseconds of lock contention compounds into missed opportunities.

Decision: Lock-Free Reads

ADR-006 documents our choice: sacrifice memory efficiency for latency consistency.

We use two complementary crates:

Component	Crate	Purpose
Per-market orderbook	arc_swap::ArcSwap	Atomic pointer swap for updates
Market index	dashmap::DashMap	Concurrent hashmap with fine-grained locking

Implementation

The OrderbookCache combines these into a single interface:

use arc_swap::ArcSwap;
use dashmap::DashMap;

pub struct OrderbookCache {
    books: DashMap<String, ArcSwap<OrderBook>>,
}

Reads: Lock-Free

The reader path is a single atomic load:

pub fn get(&self, market_id: &str) -> Option<Arc<OrderBook>> {
    self.books.get(market_id).map(|entry| entry.load_full())
}

load_full() atomically loads the current pointer and increments the reference count. The caller receives an Arc<OrderBook> that remains valid even if the cache is updated afterward.

Writes: Atomic Swap

Updates atomically replace the orderbook without blocking readers:

pub fn update(&self, book: OrderBook) {
    let market_id = book.market_id.clone();

    match self.books.get(&market_id) {
        Some(entry) => {
            // Existing entry: atomic swap
            entry.store(Arc::new(book));
        }
        None => {
            // New entry
            self.books.insert(market_id, ArcSwap::new(Arc::new(book)));
        }
    }
}

The old Arc is dropped when the last reader releases it.

The Consistency Guarantee

This design provides a specific consistency property: readers always see a complete, valid orderbook. They never see a partially updated state (e.g., bids updated but not asks).

However, readers may see stale data if they hold an Arc while updates occur. This is acceptable because our arbitrage detector:

1. Gets orderbooks for both exchanges
2. Calculates opportunity
3. Validates with fresh data before execution

Step 3 catches stale-data false positives.

Verification

The test suite includes a concurrent stress test:

#[test]
fn test_concurrent_read_write_safety() {
    let cache = Arc::new(OrderbookCache::new());

    // 3 writers, 5 readers, concurrent access
    // Verifies no partial writes visible
    // Checks spread relationship maintained
}

Key invariant tested: spread between ask and bid is always consistent, proving no partial updates are visible.

Performance Characteristics

Operation	Complexity	Blocking
Read	O(1)	Never
Write (existing)	O(1)	Never
Write (new market)	O(1) amortized	DashMap shard only

Memory trade-off: each update allocates a new Arc<OrderBook>. Old allocations are freed when the last reader releases. Under high update rates, this creates GC-like pressure, but latency variance remains low.

Lessons Learned

1. Profile first - We initially used RwLock and only changed after observing p99 latency spikes
2. Accept trade-offs - Lock-free isn't free; we trade memory for latency
3. Test concurrency explicitly - The stress test caught a subtle bug in early iteration

The orderbook cache is central to our arbitrage detection. Getting the concurrency model right was worth the implementation effort.