concurrent data structure

**Concurrent Data Structures** is the **design and implementation of data structures that support simultaneous access by multiple threads without data corruption, using fine-grained locking, lock-free algorithms, or transactional memory to maximize parallelism while maintaining correctness** — the foundation of scalable multi-threaded software. The choice of concurrent data structure — from a simple mutex-protected container to a sophisticated lock-free skip list — determines whether a parallel application scales to 64 cores or serializes at a single bottleneck. **Concurrency Correctness Requirements** - **Safety (linearizability)**: Every operation appears to take effect atomically at some point between its invocation and response — as if executed sequentially. - **Liveness (progress)**: Operations eventually complete, not blocked indefinitely. - **Progress conditions** (strongest to weakest): - **Wait-free**: Every thread completes in a bounded number of steps regardless of others. - **Lock-free**: At least one thread makes progress in a bounded number of steps. - **Obstruction-free**: A thread makes progress if it runs in isolation. - **Blocking**: Other threads can prevent progress (mutex-based). **Concurrent Queue Implementations** **1. Mutex-Protected Queue (Simple)** - Single lock protects entire queue → safe but serializes all enqueue/dequeue. - Throughput: ~1 operation per mutex acquisition → linear throughput regardless of cores. **2. Two-Lock Queue (Michael-Scott)** - Separate locks for head (dequeue) and tail (enqueue). - Producers and consumers operate concurrently as long as queue is non-empty. - 2× throughput improvement when producers and consumers run simultaneously. **3. Lock-Free Queue (Michael-Scott CAS-based)** - Uses Compare-And-Swap (CAS) atomic operation instead of lock. - Enqueue: CAS to swing tail pointer to new node → linearization point. - Dequeue: CAS to swing head pointer → remove node. - Lock-free: Even if one thread stalls, others can complete their operations. - Challenge: ABA problem → need tagged pointers or hazard pointers. **4. Disruptor (Ring Buffer)** - Pre-allocated ring buffer, cache-line-padded sequence numbers. - No allocation per operation → cache-friendly → very high throughput. - Used by: LMAX Exchange (financial trading), logging frameworks. - Throughput: 50+ million operations/second vs. 5 million for ConcurrentLinkedQueue. **Concurrent Hash Map** **Java ConcurrentHashMap (JDK 8+)** - Stripe-level locking: Lock individual linked-list heads (buckets). - Concurrent reads: Fully parallel (volatile reads, no lock for non-structural reads). - Concurrent writes to different buckets: Fully parallel (different locks). - Treeify: Bucket chains longer than 8 → convert to red-black tree → O(log n) per bucket. **Lock-Free Hash Map** - Split-ordered lists (Shalev-Shavit): Lock-free ordered linked list + on-demand bucket allocation. - Each bucket is a sentinel in the ordered list → CAS for insert/delete → fully lock-free. - Hopscotch hashing: Better cache behavior than chaining → faster for dense maps. **Fine-Grained Locking Patterns** **1. Lock Coupling (Hand-over-Hand)** - For linked list traversal: Lock node i → lock node i+1 → release node i → advance. - Allows concurrent operations at different parts of the list. - Used for: Concurrent sorted lists, B-tree traversal. **2. Read-Write Lock** - Multiple concurrent readers allowed; exclusive writer. - `pthread_rwlock_t`, `std::shared_mutex` (C++17). - Read-heavy workloads: Near-linear read scaling; writes serialize. **3. Sequence Lock (seqlock)** - Writer increments sequence number (odd during write, even otherwise). - Reader reads sequence → reads data → reads sequence again → if same and even → data consistent. - Lock-free readers: Readers never block (can retry if writer intervenes). - Used in Linux kernel for jiffies, time-of-day clock. **ABA Problem and Solutions** - CAS sees value A → something changes A→B→A → CAS succeeds incorrectly (value looks unchanged). - Solutions: - **Tagged pointers**: High bits of pointer encode version counter → prevents ABA. - **Hazard pointers**: Thread registers pointer before use → garbage collector cannot free → safe memory reclamation. - **RCU (Read-Copy-Update)**: Readers never blocked → writers create new version → reader sees consistent snapshot. Concurrent data structures are **the engineering foundation that separates programs that scale from programs that serialize** — choosing the right concurrent container for each use case, understanding the tradeoffs between locking and lock-free approaches, and correctly implementing memory reclamation are the skills that determine whether a parallel system delivers 64× speedup on 64 cores or runs no faster than on 2 cores at the bottleneck data structure.