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.