[left-right datastructure] The Cost of Concurrency Coordination

I used to use this dual-copy/pointer swap trick for Linkedin's ATS server.

Reference:
The Cost of Concurrency Coordination with Jon Gjengset

In concurrent systems programming, conventional wisdom often reduces synchronization performance to simple rules of thumb:

• "Mutexes are slow because threads get descheduled."
• "If your workload is read-heavy, swap out your Mutex for a Reader-Writer Lock (RwLock)."
• "Lock-free data structures are inherently fast."

Experience engineer should know these statements aren't true.

It really based on the workload patterns. (DoD)

The RwLock Trap

When developers see read contention on a mutex, the standard instinct is reaching for a Reader-Writer Lock (std::sync::RwLock in Rust, std::shared_mutex in C++). In theory, multiple readers are non-exclusive and should execute cleanly in parallel.

In practice, the benchmark reveals something surprising:

The RwLock read throughput starts roughly equal to the Mutex.

As the number of concurrent reader threads grows, RwLock performance degrades faster and ends up significantly worse than the basic Mutex.

The Hardware Reality: Cache Lines and the MESI Protocol

Why RwLock::read() is Actually a Write

Here lies the catch: Taking a read lock is not a read operation.

To track how many active readers hold the lock, an RwLock maintains an internal reader counter. When a reader calls read(), the CPU must execute an atomic increment (fetch_add) on that shared counter.

Core 0 (Reader 1)   --> fetch_add(reader_count) --> Needs Exclusive Ownership (Line in 'M')

Core 1 (Reader 2)   --> fetch_add(reader_count) --> Forces Core 0 invalidation; pulls line to Core 1

Core 0 (Releasing)  --> fetch_sub(reader_count) --> Pulls line back from Core 1

Every single acquire and release triggers cache-line bouncing across the processor interconnect. Each transition costs ~30 ns. Across acquire and release, a thread spends ~60 ns just synchronizing the lock state—over half the latency of a trip out to main RAM.

Why does Mutex hold up better under extreme thread contention than RwLock?

With a Mutex, only the current owner touches the lock line. Other threads block or queue up in sequence.

With an RwLock, dozens of reader threads aggressively hammer the exact same counter simultaneously, creating intense cache-line ping-pong across every core.

The Left-Right Data Structure: Coordination Without Contention

To make readers truly scalable, readers must never write to a shared cache line.

Jon presents Left-Right, a concurrency primitive, designed for workloads with frequent reads and infrequent writes (e.g., in-memory key-value lookups, routing tables, configuration maps).

High-Level Architecture

Instead of locking access to a single instance, Left-Right maintains two identical copies of the underlying data structure (the Left copy and the Right copy), mediated by an atomic pointer.

The Read Path (Wait-Free & Shared-State Free)

Every reader thread is registered with a private, thread-local counter aligned to its own cache line.

When reading:

• The reader announces its entry by updating its own thread-local counter.
• It loads the global atomic pointer to find the current active copy (Left or Right).
• It executes the read directly on that copy without taking any locks.
• It signals completion on its private counter.
• Because each reader modifies only its own cache line, there is zero cross-core invalidation between readers. Their cache lines stay in the Exclusive/Modified state within their local L1/L2 caches.

The Write Path (Two-Phase Reconciliation)

• Step 1: Writer mutates Right Copy (inactive)
• Step 2: Writer swaps Atomic Pointer to Right
• Step 3: Writer waits for readers in Left Copy to exit (epochs/counters)
• Step 4: Writer replays mutations onto Left Copy

Mutate Inactive Copy: The writer applies the update to the copy that readers aren't currently directed to (e.g., the Right copy).

Atomic Pointer Swap: The writer atomically swings the pointer to Right. All new incoming read operations will now read from Right.

Wait for Old Readers: Readers that entered before the pointer swap are still safely executing inside the Left copy. The writer scans the per-thread counters in a loop until it confirms that all readers active during the switch have finished.

Replay & Synchronize: Once the Left copy is completely drained of readers, the writer replays the exact same update from an operational log onto the Left copy. Both copies are now identical again.

The "Four-Core Drop": A Real-World Lesson in False Sharing

While benchmarking Left-Right, Jon observed expected linear scalability up to three cores—then suddenly, at four cores, throughput plummeted by nearly an order of magnitude:

Throughput

    ^

    |         /

    |       /

    |     /   <-- Expected linear scaling

    |   /

    |  *

    |       |     \__ * <-- Plummeted 10x at 4 cores!

    +----------------------------------------> Cores

The bug wasn't an algorithmic flaw or a NUMA boundary traversal. It was False Sharing:

• The internal implementation stored per-thread reader counters together in an array.
• Multiple 64-bit counter values fit inside a single 64-byte cache line (8 bytes × 8 = 64 bytes).
• Even though Core 0 and Core 1 were updating completely independent counter variables, those variables shared the exact same physical cache line. The CPU was forced to ping-pong the line between cores on every single reader check-in.

The Fix

Enforce cache-line alignment on the counter type:

#[repr(align(64))]

struct AlignedReaderCounter {

    counter: AtomicUsize,

}

By ensuring each thread's counter lived on its own dedicated 64-byte boundary, the false sharing vanished, and performance restored to ~3 billion reads/second across 10 cores—scaling linearly.

Engineering Trade-offs: When Should You Use Left-Right?

Left-Right is not a magic drop-in replacement for every concurrency scenario. It trades memory and write performance for extreme read throughput:

Constraint	Left-Right Trade-Off
Memory Footprint	Doubled (2×), because two full copies of the data structure must live in memory.
Write Overhead	High. Writers must apply changes twice (once per copy), keep an operation log, and wait for reader epochs to drain.
Write Concurrency	Single writer only. Multiple concurrent writers require an external lock.
Consistency Model	Eventually consistent / Non-linearizable. Readers might see slightly stale data before a pointer swap, and writers cannot immediately read-your-own-writes from the reader handle.
Determinism	Operations must be completely deterministic so that replaying them on the second copy yields identical internal state.

Summary Takeaways

• "Lock-Free" does not mean "Contention-Free": Eliminating OS-level locks doesn't matter if your threads are repeatedly modifying the same atomic variable on a single shared cache line.
• Short critical sections expose synchronization overhead: If your protected work takes 5 ns (like a hash map lookup) and your lock acquire/release costs 60 ns in cache line bounces, synchronization dominates your runtime.
• Align for the hardware: Always guard against false sharing in concurrent per-thread arrays using 64-byte alignment (alignas(64) in C++, #[repr(align(64))] in Rust).
• Tailor algorithms to your access patterns: When your system is 99% reads and you can afford the memory overhead and deterministic write logs, patterns like Left-Right turn cache lines from a bottleneck into an advantage.