Low-level designDeep dive7 min

Concurrent collections

A thread-safe collection makes each single call safe, not a sequence of calls. Read-then-write still races unless the collection offers the whole update as one atomic operation, such as a map's merge or compute.

Watch it evolve1 / 7

The problem

Four feeds, one map of counts

Every get and put on TagCounts holds a lock. Feeds add one to a tag by reading its count and writing it back.

Start

Stage 1

Final

1 · The situation

Counting hashtags from four feeds

A trend tracker reads posts from four feeds at once, one thread per feed, and counts how often each hashtag appears in a shared TagCounts map. The map is a thread-safe one: every get() and every put() holds a lock, as Java's Collections.synchronizedMap() does. Adding one to a tag reads its count and writes it back plus one.

As on the other concurrency pages, the first program replays one order of steps that real threads can run in, so its output is the same every run.

Safe calls, unsafe sequenceJava

class TagCounts {
    private final Map<String, Integer> counts = Collections.synchronizedMap(new HashMap<>());

    TagCounts() {
        counts.put("#launch", 3);
    }

    int get(String tag) {
        return counts.getOrDefault(tag, 0);
    }

    void put(String tag, int count) {
        counts.put(tag, count);
    }
}

class Feed {
    private final String name;
    private final TagCounts counts;
    private int seen;

    Feed(String name, TagCounts counts) {
        this.name = name;
        this.counts = counts;
    }

    void readStep(String tag) {
        seen = counts.get(tag);
        System.out.println(name + " reads " + tag + " = " + seen);
    }

    void writeStep(String tag) {
        counts.put(tag, seen + 1);
        System.out.println(name + " writes " + tag + " = " + (seen + 1));
    }
}

2 · The race

A safe map, and a lost count

Feed A reads #launch = 3
Feed B reads #launch = 3
Feed A writes #launch = 4
Feed B writes #launch = 4
#launch: 4, expected 5

Two posts tagged #launch, one count added.

Every call was locked, and the count is still wrong. The lock protected the map during get() and again during put(), but not in between, and between is where Feed B read the same 3 that Feed A was about to replace. A thread-safe collection guarantees that each operation is safe on its own; it says nothing about a sequence of them.

Feed A

TagCounts

Feed B

get(#launch): 3

put(#launch, 4)

Each call is locked, and each is correct on its own. The pair isn't.

Sequence	Why it races
get, then put	Another thread can put in between
containsKey, then put	Another thread can add the key in between
size, then decide	The size can change before the decision is acted on
iterate, while others add	A plain synchronized collection must be locked by hand for the whole loop

3 · The fix

One call that does the whole update

The fix is to stop composing the update from separate calls and ask the collection to do all of it atomically. The next program uses real threads: four feeds of 3,000 posts each.

Java's ConcurrentHashMap.merge(tag, 1, Integer::sum) reads, adds and writes as one atomic call. C++ and Python have no concurrent map in their standard libraries, so add() does the read and the write inside one lock. JavaScript workers can't share a Map at all: each worker counts its own, and the main thread adds the results together.

Java

class TagCounts {
    private final ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();

    void add(String tag) {
        counts.merge(tag, 1, Integer::sum);
    }

    List<Map.Entry<String, Integer>> byCount() {
        List<Map.Entry<String, Integer>> entries = new ArrayList<>(counts.entrySet());
        entries.sort((x, y) -> y.getValue() - x.getValue());
        return entries;
    }
}

#launch: 6000
#music: 4000
#food: 2000

12,000 posts, every tag counted, on every run.

Four feed threads share one TagCounts, which offers a single operation: add().

4 · The idea

Concurrent collections and their atomic operations

A synchronized collection wraps an ordinary one in a single lock: every call takes it, so threads take turns on the whole collection. A concurrent collection is built for many threads: Java's ConcurrentHashMap lets reads proceed without blocking and offers compound updates, such as merge() and compute(), that run atomically. Its iterators are weakly consistent: they never throw because of concurrent changes, and they reflect the map at some point at or since the iterator was created, which may or may not include later changes: not a snapshot.

The update	As separate calls	As one atomic call (Java)
Add one to a count	get, then put	`merge(key, 1, Integer::sum)`
Create a value only if absent	containsKey, then put	`putIfAbsent()` or `computeIfAbsent()`
Change a value based on the old one	get, compute, put	`compute()`
Remove only if it still holds a value	get, compare, remove	`remove(key, value)`

The other languages offer fewer of these. C++ has no concurrent containers in its standard library, so the usual design is a class whose methods are the compound operations, each under one lock. Python's FAQ lists D[x] = D[x] + 1 among the operations that are not atomic, so a dict needs a lock around it. JavaScript avoids the question by not sharing collections between workers.

5 · What it costs

What concurrent collections don't promise

Concurrent collections trade some guarantees for speed:

Sizes are estimates. While other threads update the map, size() and isEmpty() describe a moment that may already be gone; fine for monitoring, not for decisions.
Iteration is a moving picture. A weakly consistent iterator may or may not show changes made during the loop.
Atomic only within one call. Two separate atomic calls, such as moving a count from one tag to another, still need a lock around both, or a redesign.
Keep the update functions short. Other updates to the map can wait while merge() or compute() runs, and the function must not update other entries of the same map.

Need	Usually
Many threads updating counts or caches	A concurrent map with atomic compound operations
A consistent picture of several entries at once	A lock around the whole read, or an immutable snapshot
Threads that can work on their own data	Per-thread collections merged at the end, as the JavaScript version does
Very heavily contended counters	Striped counters, such as Java's `LongAdder` as the map's values

6 · Getting it right

Find the compound operations

Look for read-then-write. Every place that reads from a shared collection and then writes based on what it read is a candidate race.
Use the collection's atomic operations instead of composing them; if it has none for your update, wrap the collection in a class whose methods are your updates, each under one lock.
Don't decide from size or containment on a shared collection that others change.
Prefer not sharing. Per-thread counts merged at the end need no locks at all while the threads run.

Language	Thread-safe collections
Java	`ConcurrentHashMap`, `ConcurrentLinkedQueue`, `CopyOnWriteArrayList`, blocking queues; `Collections.synchronizedMap()` for a single-lock wrapper
C++	None in the standard library; a class with a mutex around a container
JavaScript	None needed within one thread; workers share only `SharedArrayBuffer` memory
Python	`queue.Queue` for handing work over; dicts and lists need a lock for compound updates

7 · Look-alikes

Safe, synchronized, concurrent, immutable

Four kinds of collection are often called thread-safe, and they promise different things.

Kind	What it promises
Synchronized wrapper	Each call runs alone under one lock; sequences and iteration need your own locking
Concurrent collection	Many threads at once, atomic compound operations, weakly consistent iteration
Copy-on-write collection	Every write copies the whole collection; readers never wait, and iterate a stable snapshot
Immutable collection	Never changes, so any number of threads read it safely

8 · In practice

Frequency maps in the libraries

Java's ConcurrentHashMap documentation presents exactly this tracker's job, a frequency map, and recommends LongAdder values updated through computeIfAbsent(key, k -> new LongAdder()).increment() for heavily shared counts. It also warns that size(), isEmpty() and containsValue() are only useful when the map isn't being updated.

The same lesson holds for every shared collection in any language: find the compound updates, and make each one a single operation.

Check yourself

4 questions

1. A map is wrapped with Collections.synchronizedMap(). Is if (!map.containsKey(k)) map.put(k, v) safe from two threads?

2. Which call adds one to a tag's count atomically in a ConcurrentHashMap?

3. A thread checks map.size() < 100 on a concurrent map before adding an entry. What's wrong?

4. Why does the JavaScript version give each worker its own Map?

Takeaways

Remember this

A thread-safe collection makes single calls safe, not sequences such as get-then-put or check-then-put.
Use the collection's atomic compound operations, such as merge, compute and putIfAbsent, for read-then-write updates.
Where none exist, wrap the collection in a class whose methods are your updates, each under one lock.
Sizes and iteration on a concurrently updated collection describe moments, not facts to decide on.
Per-thread collections merged at the end avoid sharing altogether.