[High-Performance C++ Engine #2] Zero-Mutex Market Data Engine — Symbol Hash Sharding & Lock-Free RCU/CoW

Symbol Hash Sharding (FNV-1a) and Lock-Free RCU Copy-on-Write Architecture

▲ [Figure 2] Per-domain symbol-hash sharding (FNV-1a) for serialized writes combined with Lock-Free RCU + Copy-on-Write wait-free reads

Recap & Goals of Part 2

In [Part 1], we dissected why legacy Win32/MFC trading clients freeze during the 09:00 AM market open burst. Pushing every incoming packet onto the UI thread via PostMessage—and having each open window redundantly perform byte-swapping, string formatting, and synchronous GDI repaints—saturated the main message loop.

To break this bottleneck, we introduced MarketDataEngine, a centralized high-performance in-memory market data cache sitting between the network layer and the UI layer. However, there is a classic trap when building a central cache: wrapping the entire symbol map in a single std::mutex or SRWLOCK.

What happens if background worker threads acquire a lock tens of thousands of times per second to write market ticks while the main UI thread attempts to acquire that same lock to paint the screen? You end up with a paradox where the UI thread stalls on lock contention against background workers.

In [Part 2], we dive deep into how we eliminated write-write contention via Domain Separation + Symbol Hash Sharding and eliminated read-write contention via a Lock-Free RCU (Read-Copy-Update) + Copy-on-Write snapshot architecture.

1. Isolating Write Bottlenecks: Domain Separation + Symbol Hash Sharding

Real-time market data feeds comprise multiple distinct domains with vastly different payload sizes and arrival rates:

Trades & Expected Execution (Auction): Extremely high frequency; updates last price, net change, and cumulative volume.
OrderBook Depth (10-Level Quotes): Large payloads (~1KB containing 10 levels of bid/ask prices, sizes, and LP quantities) with heavier parsing cost.
Auxiliary Feeds (Program Trading, Investor Breakdown, Volatility Interruption [VI], Alerts): Lower frequency but diverse parsing rules.

If a single worker thread processed all packets sequentially, parsing 100 1KB depth packets would delay hundreds of lightweight trade packets queued behind them (Head-of-Line Blocking). Conversely, if an unpartitioned thread pool pulled packets indiscriminately, two consecutive trade packets for the same symbol could be processed simultaneously on different CPU cores and commit out of order (Race Condition).

To solve both problems simultaneously, we designed a Domain-Separated Shard Group + Symbol Hash (FNV-1a) Routing architecture:

flowchart TD
    A["Real-Time Packet Ingress"] --> B["Issue Monotonic Ingress Sequence (atomic fetch_add)"]
    B --> C{"Classify Feed Domain"}
    C -->|"Trade / Expected"| D["Trade Shard Group (N Workers)"]
    C -->|"10-Level Depth"| E["Depth Shard Group (M Workers)"]
    C -->|"Aux Feeds / Initial RQ"| F["Aux Shard Group"]
    D -->|"Hash(SymbolCode) % N"| G["Same-symbol trades always execute serially on the same worker"]
    E -->|"Hash(SymbolCode) % M"| H["Same-symbol depth updates always execute serially on the same worker"]

Key Design Highlights

Immediate Ingress Sequence Stamping: The moment a packet enters the engine, it is stamped with a globally monotonic sequence number via m_ingressOrder.fetch_add(1, std::memory_order_relaxed).
Per-Symbol Serial Execution Within Each Domain: Within any domain group, the same symbol code (e.g., 005930) always routes to the exact same worker queue via Hash(code) % shardCount. Consequently, per-symbol packet ordering within a domain is 100% guaranteed without locks.
CPU Core Affinity Partitioning: Worker threads avoid Core 0 (where the main Win32 UI thread primarily runs) and bind across the remaining physical/logical cores, minimizing L1/L2 cache pollution and context switching on the UI thread.

2. Eliminating Read Bottlenecks: Lock-Free RCU (`RcuSnapshotSlots`) & Copy-on-Write

Now consider what happens when different domain workers (e.g., a Trade worker and a Depth worker) update the snapshot (SymbolSnapshot) for the same symbol concurrently, or when the UI thread reads that snapshot at the exact same instant.

In C++11/17, while the control block reference count of std::shared_ptr<const SymbolSnapshot> is atomic, concurrently calling store on one thread and load on another against the same shared_ptr instance is a data race (Undefined Behavior). (C++20 introduced std::atomic<std::shared_ptr<T>>, but many commercial standard library implementations still rely on internal spinlocks.)

To achieve true lock-free reads and writes across per-symbol exchange slots (Primary, Alternative, Consolidated), we implemented an Exponential-Backoff CAS-based RCU (Read-Copy-Update) + Copy-on-Write pattern.

sequenceDiagram
    participant W as "Background Shard Worker (Writer)"
    participant S as "SymbolContext (Atomic RCU Slot)"
    participant UI as "Main UI Thread / ScreenWorker (Reader)"

    Note over S: Currently published snapshot: Snapshot v1 (Immutable, const)
    UI->>S: Call GetSnapshot() (Acquires v1 pointer immediately without locks!)
    W->>S: Load current pointer (v1)
    W->>W: Acquire new buffer (v2) from Object Pool & copy v1 (Copy-on-Write)
    W->>W: Apply byte-swapped trade/depth mutation onto v2
    W->>S: Atomic CAS(expected=v1, desired=v2) pointer swap!
    Note over UI: UI safely finishes reading v1 and releases reference automatically
    UI->>S: Next frame GetSnapshot() call -> Immediately acquires v2!

Anatomy of the Copy-on-Write (CoW) Update Loop

// How a background worker updates a symbol's snapshot via Lock-Free CAS
template <typename MutateFunc>
std::shared_ptr<const SymbolSnapshot> UpdateSymbolRcu(
    SymbolSlot& slot,
    ObjectPool<SymbolSnapshot>& pool,
    MutateFunc&& mutate)
{
    uint32_t spinCount = 0;
    while (true) {
        // 1. Atomically load the currently published immutable snapshot (oldSnap)
        std::shared_ptr<const SymbolSnapshot> oldSnap = slot.LoadAcquire();

        // 2. Acquire a fresh buffer from the Object Pool and copy current state (CoW)
        std::shared_ptr<SymbolSnapshot> newSnap = pool.Acquire();
        if (oldSnap) {
            *newSnap = *oldSnap; // Fast POD-level memory copy
        } else {
            newSnap->InitializeDefaults();
        }

        // 3. Apply only this packet's domain delta onto the copy (Mutate).
        //    Even if CAS collides with another domain worker and retries,
        //    re-applying mutate() onto the newer oldSnap guarantees zero data loss!
        if (!mutate(*newSnap)) {
            return oldSnap; // Abort immediately if packet is stale/duplicate or no-op
        }
        newSnap->revision = oldSnap ? (oldSnap->revision + 1) : 1;

        // 4. Atomically swap the published pointer via Compare-And-Swap (CAS)
        if (slot.CompareExchangeRelease(oldSnap, std::const_pointer_cast<const SymbolSnapshot>(newSnap))) {
            return newSnap; // Successfully published!
        }

        // 5. On contention, perform exponential backoff (CPU PAUSE -> SwitchToThread) and retry
        CasBackoff::Pause(spinCount);
    }
}

Why This Architecture Is So Effective

Zero Read Latency on the UI Thread (Wait-Free Reads):
The UI thread simply calls slot.LoadAcquire() to obtain a std::shared_ptr<const SymbolSnapshot>. Because published snapshots are strictly immutable, 100 new trades can arrive in the background while the UI is mid-render without ever causing torn reads or lock waits.
100% Delta Preservation Across Cross-Domain CAS Collisions:
If a Trade Worker and a Depth Worker concurrently update the same symbol and the Depth Worker loses the first CAS race, the next loop iteration reloads the freshly published oldSnap (containing the new trade) and re-applies the Depth mutation on top of it—ensuring neither update is ever lost or overwritten.
Zero OS Heap Contention via Lock-Free Object Pool (DataPool):
Calling new SymbolSnapshot on every tick would shift contention to the OS heap allocator (malloc / HeapAlloc). Instead, a free-list object pool (DataPool) paired with a custom shared_ptr deleter recycles snapshot buffers immediately once the last reader releases its reference.

3. Fine-Grained Domain Dirty Bitmask

A SymbolSnapshot contains hundreds of fields. When a trade packet arrives, the 10-level orderbook hasn't changed; when a depth packet arrives, program trading metrics haven't changed.

So that each UI screen can determine in $O(1)$ time "which domains changed since the revision I last rendered?", the snapshot tracks monotonic per-domain sequences alongside bitmask flags:

enum DomainDirtyFlags : uint32_t {
    DOM_NONE     = 0,
    DOM_MASTER   = 1 << 0, // Last price, net change, change rate, volume, O/H/L
    DOM_QUOTE    = 1 << 1, // 10-level bid/ask prices, sizes, and LP quantities
    DOM_EXPECTED = 1 << 2, // Auction expected execution price & volume
    DOM_PROGRAM  = 1 << 3, // Program trading flow
    DOM_INVESTOR = 1 << 4, // Investor breakdown metrics
    DOM_VI       = 1 << 5, // Static/Dynamic Volatility Interruption status & base price
};

Each screen maintains a lightweight per-domain cursor (SnapshotCursor) and compares it against the latest snapshot to update only the exact UI cells whose domain bits actually changed.

Coming Up Next

We now have the core engine capable of ingesting high-velocity packets in the background and publishing immutable snapshots without locks. Yet real-world financial markets present even tougher domain challenges:

"How do we synthesize separate 10-level orderbooks from the Primary Exchange and Alternative Exchange (ATS) into a unified real-time 10-level orderbook?"
"When real-time trades arrive while an initial Request/Reply (RQ) snapshot query is still in flight, how do we prevent the late RQ response from overwriting newer real-time ticks?"

In [Part 3], we explore Multi-Exchange Real-Time OrderBook Synthesis and Deterministic State Projection for Out-of-Order Streams.