Concurrent Data Structures

How thread-safe collections avoid one big lock (striped locks, compare-and-swap, copy-on-write, striped counters), with ConcurrentHashMap, CopyOnWriteArrayList and LongAdder explained from their docs.

Overview

A concurrent data structure is a collection that many threads can use at once without the caller adding locks. The simplest way to get one is to put a single lock around every method. That is correct but slow under load, because every thread waits for every other thread, even readers and even threads touching different keys.

The structures in java.util.concurrent and their equivalents elsewhere use a handful of techniques to let threads proceed together. Interviewers ask how they work (usually ConcurrentHashMap), which one fits a workload, and why a thread-safe map still does not make your own code thread-safe.

Thread-safe methods are not thread-safe code

Each call on a concurrent map is atomic, but two calls in a row are not. 'If the key is missing, put it' done as two calls races: both threads see it missing and both put. The same holds for a map wrapped by Collections.synchronizedMap, whose docs also require you to lock the map yourself while iterating it.

1 — reads counts["x"]: 0 — 0
2 — reads counts["x"]: 0 — 0
3 — writes 1 — 1
4 — writes 1 — 1 (one lost)

The fix is to ask the structure for one atomic operation that does the whole thing: merge, compute, computeIfAbsent or putIfAbsent in Java, or a lock held across both steps.

Five techniques

One lock — Every method takes the same lock — Low contention, simple invariants — Every thread waits for every other
Striped (fine-grained) locks — Split the data; each part has its own lock — Maps and sets with many keys — Operations over all parts need all locks
Compare-and-swap (CAS) — Read, compute, and write only if the value has not changed; retry if it has — Single variables, counters, pointers — Retries under heavy contention
Copy-on-write — Writers copy the whole structure and swap it in; readers never lock — Many reads, rare writes (listener lists, config) — Each write copies everything
Striped counters — Many cells, each updated by some threads; the total is summed on read — Hot statistics counters — Reading the sum is slower and not a snapshot

Striped locks

Give the map N locks and pick the lock from the key's hash. Two threads updating different stripes never wait for each other. This is how ConcurrentHashMap worked up to Java 7: the table was partitioned into segments, and the concurrencyLevel argument (default 16) set how many concurrent updaters it aimed to support.

Compare-and-swap

A CAS instruction sets a memory word to a new value only if it still holds the value you read, and tells you whether it did. A lock-free update is a loop: read, compute the new value, CAS; if another thread changed the word in between, the CAS fails and you retry with the fresh value. No thread ever holds a lock, so a thread that stalls cannot block the others. Java exposes this as compareAndSet on the classes in java.util.concurrent.atomic, which its docs describe as a toolkit for lock-free thread-safe programming on single variables.

Python has no user-level CAS, so the simulation below models the hardware instruction with a tiny internal lock and runs the retry loop on top of it; the retries it counts are real conflicts between threads.

Copy-on-write

Readers read the current version without locking; a writer copies it, changes the copy, and publishes the copy with one reference swap. A reader iterating an old version is never disturbed. Java's CopyOnWriteArrayList does this; its docs call it ordinarily too costly but possibly more efficient when traversals vastly outnumber changes, and its iterators work on a snapshot and never throw ConcurrentModificationException.

What you will be able to do

Explain why a sequence of thread-safe calls is not thread-safe, and use the atomic compound operation instead.
Compare one lock, striped locks, CAS, copy-on-write and striped counters, and pick one for a workload.
Describe how ConcurrentHashMap changed from segments (Java 7) to per-bin locking with CAS (Java 8).
Say when LongAdder beats AtomicLong, and when lock-free is not worth it.

Interview questions

How does ConcurrentHashMap perform better than a synchronized HashMap?
What are lock-free data structures, and when should you use them?
When should you use LongAdder instead of AtomicLong?
Which concurrent collection would you pick, and why?