Concepts / Concurrency in one process / Thread-safe collections and atomics

Thread-safe collections and atomics

Counters and maps many threads can share.

Low-level design conceptConcurrency in one process2 Nov 2026

01The intuition

The problem it solves

A web server counts page views per URL in a dictionary. Every request handler, on its own thread, does the obvious thing.

views: dict[str, int] = {}

def record(url: str) -> None:
    views[url] = views.get(url, 0) + 1      # read, add, write: three steps

Two handlers for the same URL read 41, both write 42, and a view is lost. Lose one in ten thousand and the dashboard is wrong by a few percent and nobody can reproduce it. The dictionary itself does not corrupt in Python, but the read-modify-write around it is not one step, and a counter that is sometimes wrong is worse than one that is slow.

Build it one piece at a time

Step one: wrap the shared dictionary in a class whose every public method holds one lock. Callers can no longer touch the dictionary directly, so the invariant is enforced in one file.

import threading

class ViewCounter:
    def __init__(self) -> None:
        self._views: dict[str, int] = {}
        self._lock = threading.Lock()

    def record(self, url: str) -> None:
        with self._lock:
            self._views[url] = self._views.get(url, 0) + 1

    def get(self, url: str) -> int:
        with self._lock:
            return self._views.get(url, 0)

Step two: the one lock is now the bottleneck for every URL. Stripe the map: hash the key to one of N buckets, each with its own lock and its own dictionary. Two different URLs usually hit different stripes and proceed in parallel; the same URL always hits the same stripe, so its counter stays exact.

class StripedCounter:
    def __init__(self, stripes: int = 16) -> None:
        self._maps: list[dict[str, int]] = [{} for _ in range(stripes)]
        self._locks = [threading.Lock() for _ in range(stripes)]

    def _idx(self, key: str) -> int:
        return hash(key) % len(self._maps)

    def record(self, url: str) -> None:
        i = self._idx(url)
        with self._locks[i]:
            self._maps[i][url] = self._maps[i].get(url, 0) + 1

    def get(self, url: str) -> int:
        i = self._idx(url)
        with self._locks[i]:
            return self._maps[i].get(url, 0)

Step three: operations that span the whole collection, such as "total views" or "top ten", must either take every stripe lock in a fixed order, or accept a slightly stale answer by reading stripe by stripe. Make that choice explicit in the method name.

class StripedCounter(StripedCounter):   # continued
    def total_exact(self) -> int:
        for lk in self._locks:              # fixed order: no deadlock
            lk.acquire()
        try:
            return sum(sum(m.values()) for m in self._maps)
        finally:
            for lk in reversed(self._locks):
                lk.release()

    def total_approx(self) -> int:
        total = 0
        for m, lk in zip(self._maps, self._locks):
            with lk:                        # one stripe at a time
                total += sum(m.values())
        return total

Two threads recording different URLs on a 4-stripe counter:

Threadkeystripewaits for
A/home2nobody
B/about0nobody, runs in parallel
C/home2A to release stripe 2

Why it works

The invariant is per key: the stored count equals the number of completed record calls for that key. Because a key maps to exactly one stripe and every access to that stripe holds its lock, the read-modify-write for one key is atomic. Different keys do not share an invariant, so they do not need to share a lock, which is where the parallelism comes from.

Where it breaks: the moment a method needs two keys at once, such as "move views from old URL to new URL", one stripe lock is not enough, and taking two in arbitrary order can deadlock; take them in index order. The second trap is handing out references: returning the inner dictionary, or iterating it outside the lock, lets a caller read a half-updated structure. Return copies or snapshots.

contention with one lock: every thread waits on every other. With s stripes: a thread waits only on threads using its stripe, roughly 1/s of them

The trade-off you must say out loud

A single lock is correct and simple; stripes add parallelism and make whole-map operations awkward; atomics (a compare-and-swap counter) avoid locks entirely for simple numbers but not for compound updates. For a counter, Python's standard library has no atomic integer, so the striped lock is the honest answer; in Java you would reach for ConcurrentHashMap and LongAdder and say why. The follow-up that usually comes next is "what about a map of maps", where the answer is that nesting thread-safe collections does not make compound operations safe.

Where it shows up in the 100 Google problems

02Used in these problems