Skip to main content
Be Bitwise

Concurrent Data Structures

Advanced Concurrency · VR Foundations track

7 min read

In this module

Scaling Data Structures to Multiple Threads

When a single-threaded hash map or queue becomes a bottleneck in a concurrent system, you have two options: put a lock around it (coarse-grained), or redesign the structure to allow concurrent access (fine-grained or lock-free). Coarse-grained is simple but serialises everything. Fine-grained and lock-free designs are significantly more complex but can yield dramatically higher throughput when contention is real.

Concurrent Hash Maps

The simplest concurrent hash map uses lock striping: instead of one lock for the entire table, you use N locks, each protecting a subset of buckets (typically lock[hash % N]). This allows N threads to operate on different buckets simultaneously. Java's ConcurrentHashMap used this segment-based approach through Java 7. Java 8+ uses a different design based on CAS operations with individual bucket-level synchronisation and tree bins (red-black trees) at high collision counts.

A more advanced design is the lock-free hash map using open addressing with linear probing. Robin Hood hashing adapts well to concurrent settings because it bounds the variance of probe lengths. The key insight is that insert, lookup, and delete can all be expressed as CAS operations on individual array slots.

text
Slot states: EMPTY -> INSERTING -> VISIBLE -> DELETING -> EMPTY

Each slot transitions through states using CAS. An inserting thread marks a slot as INSERTING, writes the key-value pair, then CAS-transitions to VISIBLE. A deleting thread CAS-transitions from VISIBLE to DELETING, then to EMPTY. Readers check that the state is VISIBLE before reading the value.

Resizing a concurrent hash map is the hard part. One approach is to create a new, larger table and migrate entries incrementally. During migration, both tables are active: lookups check the new table first, then the old table. Each operation helps migrate a few entries. Once all entries are migrated, the old table is retired.

Read-Copy-Update (RCU)

Linux uses Read-Copy-Update (RCU) extensively for read-heavy data structures. Readers access data without any synchronisation - no locks, no atomics. Writers create a modified copy, atomically swap the pointer to the new version, and defer freeing the old version until all current readers have finished (a "grace period"). This gives readers zero overhead at the cost of more expensive writes. RCU is ideal when reads vastly outnumber writes.

Concurrent Skip Lists

A skip list is a probabilistic data structure that provides O(log n) search, insert, and delete. It is essentially a hierarchy of sorted linked lists: the bottom level contains all elements, and each higher level contains a random subset.

Skip lists adapt to concurrency more naturally than balanced trees because operations only need to lock or CAS a small number of adjacent nodes, rather than rebalancing an entire subtree. The lock-free skip list (Herlihy et al.) uses CAS operations on the forward pointers at each level. The key challenge is ensuring that a node being deleted is not concurrently traversed by a search. This is handled by marking the forward pointers of a deleted node (using a bit in the pointer) before physically unlinking it.

Java's ConcurrentSkipListMap provides a concurrent sorted map implementation based on this approach. It supports O(log n) operations without global locking, making it suitable for concurrent priority queues and ordered indexes.

Work-Stealing Deques

A work-stealing deque is a double-ended queue optimised for a specific access pattern: one thread (the owner) pushes and pops from the bottom (LIFO order), while other threads (thieves) steal from the top (FIFO order). This asymmetry allows the owner's operations to be extremely fast - typically just a load or store with appropriate fences, no CAS needed in the common case.

The Chase-Lev deque is the standard implementation. It uses a circular array with three fields: top (where thieves steal from), bottom (where the owner pushes/pops), and a pointer to the array. The owner increments bottom to push and decrements to pop. A thief increments top to steal. The only contention occurs when the deque has exactly one element and both the owner and a thief try to take it - this is resolved by a CAS on top.

text
top bottom
| |
v v
[ ][ ][ ][task][task][task][task][ ][ ]
^ ^
| |
thieves steal here owner pushes/pops here
(oldest task) (newest task)

Work-stealing deques are the foundation of parallel task schedulers in languages like Java (ForkJoinPool), Rust (Rayon), and C++ (Intel TBB). When a thread runs out of work, it picks another thread's deque at random and steals one task from the top. (Some schedulers use a steal-half variant, but Chase-Lev takes one per attempt.) This provides excellent load balancing with minimal synchronisation.

The two ends hand out tasks in opposite orders, and that's deliberate. The runner plays both roles in one thread so you can see the order without any races: the owner gets the task it pushed most recently, still warm in its cache, and a thief gets the oldest one, which in a divide-and-conquer job is usually the biggest chunk of remaining work.

Try itPredict the order of the five takes, then rename task 1 to items 0-999 and task 5 to items 0-7 to see why stealing the oldest task grabs the most work.
C (GCC 9.2.0)

The real Chase-Lev deque makes these same moves safe across threads: the owner touches only bottom in the common case, thieves CAS on top, and the only fight is over the last task.

Here's that fight with one task left (top = 0, bottom = 1). The owner reserves the slot by decrementing bottom first, so a thief that reads bottom afterwards sees an empty deque and backs off. A thief that read bottom earlier still thinks there's a task, which is why both sides finish with a CAS on top and exactly one of them can win it.

Epoch-Based Reclamation

A recurring challenge in lock-free data structures is safe memory reclamation: when a node is removed from a data structure, other threads might still hold references to it. Freeing it immediately causes use-after-free bugs.

Epoch-based reclamation maintains a global epoch counter (typically cycling through three values: 0, 1, 2). Each thread has a local epoch. When a thread begins an operation, it loads the global epoch and publishes it as its local epoch. When a thread removes a node, it places the node in a "retire list" tagged with the current global epoch.

The global epoch can advance when all active threads have observed the current epoch. Once the epoch advances twice past a node's retirement epoch, it is safe to free that node - no thread can still hold a reference from before the retirement.

text
Epoch 0: Thread A removes node X, retires it in epoch 0
Epoch 1: All threads have entered epoch 1
Epoch 2: All threads have entered epoch 2
-> Safe to free node X (retired in epoch 0)

This scheme is simple and efficient, but it has a weakness: if any thread stalls (e.g., gets preempted by the OS for a long time), the epoch cannot advance, and no memory can be reclaimed. Hazard pointers do not have this limitation but have higher per-operation overhead.

Choosing the Right Approach

The right concurrent data structure depends on your workload:

  • Read-heavy, rare writes: RCU or read-write locks
  • High-contention queues: lock-free Michael-Scott queue or bounded MPMC queues like Disruptor
  • Parallel task scheduling: work-stealing deques
  • Ordered data: concurrent skip lists
  • General key-value storage: striped concurrent hash maps

Always benchmark with your actual workload. The theoretical advantages of lock-free structures evaporate under low contention, where a simple mutex is just as fast and ten times easier to reason about. Lock-free complexity is only worth paying for when contention is provably high and the performance difference shows up in real measurements.