Concurrent Data Structures

1.1What hits++ really does

Let's slow the increment down. A processor does arithmetic on numbers it holds itself, so to add one to a number that lives in memory it has to do three things in order: read the current count from memory, add one, and write the new count back. Suppose the count for /home is 41, and two requests for /home arrive at the same moment, one on thread A and one on thread B.

Both threads did their three steps correctly. B's write replaced A's with a number computed from the same stale 41. We call this a lost update, and it happens whenever the result depends on exactly how two threads' steps interleave, a situation known as a race condition. It's a nasty bug because it's silent and rare. Most of the time the two threads don't overlap and the count comes out right, so the program passes every test and then loses visits under real load.

1.2Taking turns with a lock

What we want is for the three steps to run without anyone else's steps in the middle. A mutex, short for "mutual exclusion" and also called a lock, gives us that. It's a value that only one thread can hold at a time. A thread calls lock() before it touches the shared data, and if another thread already holds the mutex, lock() makes it wait. When the holder is done it calls unlock(), and one of the waiting threads gets in. The code between lock() and unlock() is called a critical section.

Run the two visits again with a mutex around the increment. If B asks for the mutex while A is inside the critical section, B waits until A has written 42. Then B gets the mutex, reads 42, and writes 43.

The word for what the lock gave us is atomic: an operation is atomic when no other thread can see it half done. A critical section is atomic as long as every thread that touches the data goes through the same mutex, because any thread that isn't inside it is waiting outside.

1.3Watching it happen

Let's make the lost update happen on purpose. Eight threads each add 1 to one shared counter two million times, so the right answer is 16,000,000.

The first version leaves the increment unprotected, with one small detail. A plain long written by two threads at once is what C++ calls undefined behaviour, which allows the compiler to do anything at all with the program, so the result would tell us nothing. Instead the counter is a std::atomic<long>, a long that the hardware always reads and writes in one piece, and the increment is written as two separate calls: racy.load() reads the count and racy.store(...) writes the new one. Each call is safe by itself, so the only thing left unprotected is the gap between the read and the write, which is exactly the gap from the Scene above. The second version runs a plain increment inside a critical section. std::lock_guard takes the mutex when it's created and gives it back at the closing brace, so everything between the braces is the critical section.

#include <atomic>
#include <cstdio>
#include <mutex>
#include <thread>
#include <vector>
 
int main() {
    const int T = 8; const long N = 2000000;
 
    std::atomic<long> racy{0};          // each load and each store is atomic; the pair is not
    { std::vector<std::thread> ts;
      for (int i = 0; i < T; i++) ts.emplace_back([&] {
          for (long k = 0; k < N; k++) racy.store(racy.load() + 1); });
      for (auto& th : ts) th.join(); }
 
    long locked = 0; std::mutex m;      // the same increment, inside a critical section
    { std::vector<std::thread> ts;
      for (int i = 0; i < T; i++) ts.emplace_back([&] {
          for (long k = 0; k < N; k++) { std::lock_guard<std::mutex> g(m); locked++; } });
      for (auto& th : ts) th.join(); }
 
    std::printf("8 threads x %ld increments, so the answer should be %ld\n", N, T * N);
    std::printf("no lock : %ld\n", racy.load());
    std::printf("mutex   : %ld\n", locked);
}

8 threads x 2000000 increments, so the answer should be 16000000
no lock : 2584883
mutex   : 16000000

The unlocked version ended near 2.6 million, so about five out of every six increments were lost. The exact number changes on every run (other runs land anywhere from about 2 million to a little over 3 million), but it stays far below 16 million, because with eight threads hammering one number the read-then-write pairs overlap almost constantly. The locked version gets 16,000,000 every time.

Look again at the shape of the unlocked loop, racy.store(racy.load() + 1). Every call in it is atomic, and the pair isn't. That shape comes back in the next section, and it's the reason "thread-safe" promises less than most people assume.

A counter is one number, while the hit table is a whole map with an entry for every page. The map has internal structure of its own, so we have to decide what to lock there and what exactly the lock promises.

2.1One mutex around the whole map

The map has more to protect than its counts. A hash map keeps its entries in many short lists called buckets. The first visit to a new page inserts a new entry, which links a node into one of those lists or, when the table is getting full, rebuilds the whole table at a larger size. Two threads doing that at once can corrupt the map's own memory, which is worse than a lost count, because the program may crash somewhere far from the cause.

So the simplest safe design puts one mutex around the entire map and makes every method take it first:

class SafeMap {
    std::mutex m;
    std::unordered_map<std::string, long> map;
public:
    bool contains(const std::string& k)       { std::lock_guard<std::mutex> g(m); return map.count(k) > 0; }
    void insert(const std::string& k, long v) { std::lock_guard<std::mutex> g(m); map[k] = v; }
};

Every method is a critical section on the same mutex, so only one thread is ever inside the map at a time. The map's buckets can't be corrupted, and each method call is atomic in the sense of section 1.2: no other thread can see it half done.

2.2What thread-safe promises

A class built this way is called thread-safe. That sounds like a blanket guarantee, and in fact it's a narrow one. The precise version is linearizability: every call appears to take effect at a single instant somewhere between the moment it was called and the moment it returned, and all threads agree on the order in which those instants happened. With our mutex it's easy to see why this holds: each call takes effect while it holds the lock.

Notice what that promise is about: each call on its own. It says nothing about two calls that one thread makes one after the other, and another thread is free to slip in between them.

2.3Check, then act

Now use the safe map the way a hit counter would. The first visit to a new page, say /pricing, has to create its entry, and the natural way to write that is to check and then insert:

// Each call is atomic. The pair is not.
if (!map.contains(url))      // thread B can run its own check and insert right here
    map.insert(url, 1);      // and this overwrites B's entry

We've seen this shape before: it's the load-then-store of section 1. Two requests for /pricing arrive on two threads, and we step through what the map sees:

?So what's the fix, if every call is already atomic?

Make the pair one call. That's why every concurrent map API grows a combined method: Java's computeIfAbsent, Go's LoadOrStore, Rust's entry(). They exist to make check-then-act a single atomic operation. For our server the combined method is "add n to this page's count, creating the entry first if it's missing":

void add(const std::string& k, long n) { std::lock_guard<std::mutex> g(m); map[k] += n; }

add holds the mutex for the lookup, the creation and the increment together, so no other thread can get in between them.

2.4Why start here

This design is where almost every program should start. It's correct, it fits on one screen, and it's easy to debug, because only one thread is ever inside the map. Taking a lock nobody else wants is cheap too: chapter 13 measured about four nanoseconds for an uncontended lock() and unlock(). Replacing the design later is a change inside one class, so starting here costs little. A profiler, a tool that measures where a running program spends its time, can tell you when to move.

What a profiler will eventually show, once many threads want the lock at the same moment, is threads waiting on it. The next question is how much that waiting costs.

3.1Eight threads, one lock

When many threads want the same lock at once, we say there's contention on it. To measure what contention costs, we'll use the simplest shared thing there is: one counter for the total number of hits across all pages. Eight threads each add 1 to it two million times. In the first version they share one counter behind one mutex. In the second, every thread has its own counter, and the program adds the eight at the end.

Two details in the code need explaining. Each private counter is wrapped in a struct marked alignas(128), which makes it start on its own cache line. A chip's cores, its independent processors, pass memory to each other in fixed chunks of 64 bytes, or 128 on Apple Silicon, and each chunk is a cache line. Two counters in one chunk would make the cores fight over it. Section 4.2 explains that fight. The line with __asm__ volatile is empty assembly that stops the compiler from replacing the whole loop with a single addition.

#include <chrono>
#include <cstdio>
#include <mutex>
#include <thread>
#include <vector>
 
struct alignas(128) Padded { long v = 0; };        // each counter gets its own cache line (128 B on Apple Silicon)
 
static double ms_since(std::chrono::steady_clock::time_point t) {
    return std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t).count();
}
 
int main() {
    const int T = 8; const long N = 2000000;
    long shared = 0; std::mutex m;
    auto t = std::chrono::steady_clock::now();
    { std::vector<std::thread> ts;
      for (int i = 0; i < T; i++) ts.emplace_back([&] {
          for (long k = 0; k < N; k++) { std::lock_guard<std::mutex> g(m); shared++; } });
      for (auto& th : ts) th.join(); }
    double one_lock = ms_since(t);
 
    std::vector<Padded> mine(T);
    t = std::chrono::steady_clock::now();
    { std::vector<std::thread> ts;
      for (int i = 0; i < T; i++) ts.emplace_back([&, i] {
          { long local = 0;
            for (long k = 0; k < N; k++) { local++; __asm__ volatile("" : "+r"(local)); }   // stop loop folding
            mine[i].v = local; } });
      for (auto& th : ts) th.join(); }
    double no_share = ms_since(t);
    long total = 0; for (auto& p : mine) total += p.v;
 
    std::printf("8 threads x %ld increments\n", N);
    std::printf("one shared counter, one mutex : %8.1f ms  (total %ld)\n", one_lock, shared);
    std::printf("one counter per thread        : %8.1f ms  (total %ld)\n", no_share, total);
}

8 threads x 2000000 increments
one shared counter, one mutex :    308.4 ms  (total 16000000)
one counter per thread        :      0.7 ms  (total 16000000)

Both versions counted exactly 16,000,000. The shared counter took about 300 to 350 ms across repeated runs, and the per-thread counters took under a millisecond or so, which makes them several hundred times faster.

Turn the first number into a cost per increment. Only one thread can be inside the critical section at a time, so the 16 million increments happen one after another, and about 320 ms spread over 16 million is about 20 ns each. That's five times the four nanoseconds of an uncontended lock. Put another way, one thread doing all 16 million increments alone, at about 4 ns each, would have finished in about 64 ms, so adding seven more threads made the job slower and bought no parallelism at all. The extra time goes to handing the lock from thread to thread, which means moving it from one core to another, while the other seven threads wait their turn.

3.2The lock turns the map into a queue

Eight threads fighting over one lock spend their time waiting for each other, and nothing they do in parallel helps. It's a supermarket where every shopper must queue at one till, however many have full baskets. The private counters never touch each other's memory, so nothing waits. They leave one job over, adding the eight totals at the end. That's the price of not sharing. For a counter it's tiny, and we come back to it in section 6, because most structures are harder to split than a counter.

The same thing happens to the map. With one lock around it, only one thread is ever inside, so eight threads can't complete more map operations per second than one thread could. Waiting also grows much faster than the load. Chapter 16's queueing arithmetic shows that as a shared resource gets busier, the line in front of it grows far faster than the traffic does, and in practice a lock becomes the bottleneck once about two threads are competing for it.

?Why do threads wait, if they're touching different keys?

Look at what the threads are doing. Thread A is adding a visit to /cart, and thread B is reading the count for /login. They touch different entries and could never interfere with each other. They wait anyway, because the lock belongs to the whole map and knows nothing about keys. The lock is wider than the thing it has to protect, so the next step is to make it narrower.

4.1An array of locks, picked by hash

We want threads on different pages to use different locks, and threads on the same page to share one. A hash function turns a key like /home into a large number, always the same number for the same key. Take that number modulo 16, meaning the remainder after dividing by 16, and every key gets a fixed number from 0 to 15.

That gives us a design. Keep sixteen small maps, each with its own mutex, and let a key's hash pick which one holds it:

struct Stripe {
    std::mutex m;
    std::unordered_map<std::string, long> map;
};
std::vector<Stripe> stripes(16);
 
Stripe& pick(const std::string& key) {
    return stripes[std::hash<std::string>{}(key) % stripes.size()];
}

Each piece is called a stripe, and the idea is lock striping. It's how Rust's dashmap and Java's older ConcurrentHashMap work. Here is a handful of requests going through a map with three stripes (three keeps the picture small; a real map would use more):

With sixteen stripes and random keys, two threads land on the same stripe about one time in sixteen, so most of the waiting disappears. The combined method from section 2 carries over unchanged, since the thread takes only its key's stripe and does the lookup and increment inside it:

void add(const std::string& key, long n) {
    Stripe& s = pick(key);
    std::lock_guard<std::mutex> g(s.m);   // locks one stripe, not the whole map
    s.map[key] += n;
}

4.2Giving each stripe its own cache line

The Stripe struct above hides a performance trap, and it's why the version in real code starts with alignas(128). Each core keeps recently used memory in its own small, fast cache, and it moves memory in and out in cache lines, 64 bytes on most processors and 128 on Apple Silicon. Before a core can write to a line, every other core has to drop its copy. A line that several cores keep writing therefore gets passed back and forth between them, and each pass is slow (chapter 02 shows how cores pass lines to each other). Taking a mutex is a write to the mutex's memory, so a lock is exactly this kind of line.

A stripe is small, so neighbouring stripes in the vector often sit in the same line. Thread A locking stripe 3 and thread B locking stripe 4 are using different locks, and yet each lock write drags the shared line away from the other core. This is false sharing: the threads share no data, but they share a cache line. Chapter 13 measured its cost on counters: 14.6 ns per operation with the counters sharing a line, against 0.27 ns once each had its own, about 55 times as much at eight threads.

To fix it, pad each stripe out to a whole line:

// Each stripe starts on its own cache line. Without alignas this brings back
// the false sharing that chapter 13 measured at 55x.
struct alignas(128) Stripe {
    std::mutex m;
    std::unordered_map<std::string, long> map;
};

We pad to 128 bytes because that's the line size on Apple Silicon, and 64 isn't enough there. On processors with 64-byte lines, 128 is still safe. Every shared lock or counter wants its own line, and two places commonly miss it: a size counter stored next to the buckets, and the head and tail positions of a ring buffer (a fixed-size circular queue) kept in one struct. With either mistake the false-sharing penalty lands on an otherwise well-designed structure, and nothing in the code looks wrong.

4.3What striping is worth

With padded stripes we can measure the gain. In this experiment eight threads each run 100,000 critical sections, and the map has one, eight or sixty-four stripes. Thread number t always uses stripe t modulo the stripe count, so with one stripe all eight threads share a single lock, and with eight or more each thread has a lock to itself. Every stripe is padded as above.

The "body" column is how much work happens inside each critical section, counted in rounds of a multiply and an add: with a body of 0 the lock is nearly the whole cost, and with 256 it's a small share. Each figure is the median of three runs, taken as the whole run's time divided by the number of critical sections completed, so a smaller number means the threads got more done in parallel. The one-stripe figure at body 0, 23 ns, is the same kind of number as the 20 ns per increment from section 3.1.

Look at the first and last columns. Going from one lock to a lock per thread is worth roughly 16 to 22 times at eight threads, and the gain holds at every critical-section length. That's more than the eightfold you'd expect from eight threads running side by side. The most likely reason is the one section 3.1 found: a contended mutex costs more per operation than an uncontended one, because its cache line keeps moving between cores, so the one-stripe column starts from something worse than a single thread would manage. Striping removes that traffic as well as the waiting.

4.4Why 64 stripes is no better than 8

?If collisions keep getting rarer, why stop at eight?

Because in this experiment each of the eight threads already has a stripe to itself at eight stripes. Nobody collides, nobody waits, and no lock's cache line moves between cores. There's no cost left for extra stripes to remove, so all they add is memory, spread over more cache lines.

A real server picks stripes by key, and keys land on stripes by chance, so two threads can still collide. A few spare stripes above the thread count keep those collisions rare, which is why sixteen for eight threads is a sensible choice. Going much further buys almost nothing, because the number of threads, not the number of keys, limits how many locks can be in use at once.

4.5A benchmark that gets striping wrong

Striping benchmarks are easy to write in a way that hides the benefit, and sometimes shows the opposite. One version of this experiment reported the time per critical section rising from 14.3 ns at one stripe to 25.9 ns at sixteen, as if striping made things slower. That figure came from a flaw in the benchmark, and seeing how the flaw arose explains what striping needs.

Each thread picked its stripe as (thread_id * 7919 + i) % stripes, where i is the loop counter, so it moved to a different stripe on every iteration. Every thread touched every stripe in turn, and each lock's cache line was last written by some other core. Every critical section therefore began with a cache miss, fetching the lock's line from another core, and the benchmark measured those misses spread over many lines instead of anything striping does.

?What was the benchmark missing?

Affinity, which means that a thread keeps using the same stripe, so that stripe's lock stays in that thread's core's cache. Change the benchmark's access to stripes[thread_id % n], as in section 4.3, and the 16× appears. A real server sits somewhere between the two. A given page always hashes to the same stripe, but a thread serves whatever pages arrive, so some of its lock lines will have been touched by other cores since it last used them. The best case in section 4.3 is an upper bound, and the gain you keep grows with how long each critical section runs compared with one cache miss.

Even the correct benchmark spread the work perfectly evenly, one thread per stripe. Real traffic is rarely that polite, and the next section asks what happens when it isn't.

5.1The hot key

A busy site often has one page that takes a large share of the traffic, usually the home page. Say /home receives 40% of all requests. It lives in exactly one stripe, so that stripe's lock is wanted by two out of every five requests, however many stripes there are.

?Why doesn't the aggregate lock profile show it?

Because a total can hide how unevenly it's spread. Add up the wait time over all sixteen stripes and it looks moderate, while one stripe carries nearly all of it and the other fifteen carry almost none. Compare wait time per stripe, never the total. On Linux, the kernel's profiler perf has a perf lock contention mode that shows how long threads waited on each lock. One lock taking nearly all the waiting, while throughput refuses to improve as you add stripes, is the signature of a hot key.

A better structure won't fix it. If the hot entry is a counter, give each thread its own and sum them when someone reads. If it's a cache entry, keep a copy per thread and accept a little staleness. Removing the sharing is the answer, and section 6 shows how.

5.2Treating size() as a fact

Suppose the server also wants to know how many distinct pages it has seen. On a map behind one lock that's a single call. On a striped map, size() has two bad options:

Java's documentation for ConcurrentHashMap warns about exactly this: while other threads are updating the map, size() reflects a passing state that's fine for monitoring or estimation and not for deciding what the program does next, and the newer mappingCount() is documented as an estimate outright. Most people read size() as a fact. Using it for a capacity decision means building on a value that can be wrong in either direction.

5.3Benchmarking with skewed keys

Uniform keys, where every key is equally likely, make every striped structure look excellent, and they hide the one failure mode that will hit you. Test with a skewed distribution instead, such as Zipf, where a few keys take most of the traffic and the rest share a long tail, or with your real key frequencies taken from a log.

A hot key leaves us with a question. If the best fix for a popular counter is to stop sharing it, what does a structure look like when nothing is shared?

6.1A count per thread, merged on read

For something like the /home count, every thread bumping one number is as contended as it gets. So give each thread its own count for /home, and add the counts up only when somebody asks for the total. This is the idea behind the private counters in section 3, which were several hundred times faster than the shared one.

Writes now scale with the number of threads, because no two of them ever touch the same memory. Reads cost one step per thread, so they get slower as threads are added, and they return a slightly stale total. The Linux kernel's per-CPU counters work this way, and so do the per-thread caches in memory allocators such as jemalloc and tcmalloc.

?Why doesn't everything work this way?

Because the cost moves to the reader, and the trick only works for data you can merge: counters, accumulators, statistics, anything where combining the pieces in any order gives the same answer. A table of user sessions, where one thread's write has to be visible to the next thread's read, can't be split into private copies this way. When the trick does apply, it beats every algorithm in this chapter, and it probably applies more often than people check.

6.2When one atomic is enough

Sometimes the right structure is no structure. If all you need is one shared number, the processor has instructions that update it in a single indivisible step. In C++ they're called fetch_add and fetch_or. If the counter in section 1.3's experiment had used racy.fetch_add(1) in place of the separate load and store, the read, the add and the write would happen as one step, and the total would come out at exactly 16,000,000 with no mutex at all. A flag that many threads may set wants fetch_or, which sets bits in one step the same way. These are hardware atomics, and checking for one comes before building anything.

They don't make contention disappear, though. All the threads still write to one cache line, and chapter 14 measured fetch_add at about 18 ns per increment against a mutex's 16 ns with eight threads on one counter. Under that much contention it's simpler than a mutex and no faster. For a counter that many threads hammer, per-thread slots still win.

Every design so far either makes threads take turns through a lock or stops them sharing a structure at all. A third family lets threads share a whole structure, such as a queue or a map, without any lock, and the question is when that's worth the trouble.

7.1When blocking is a correctness problem

A lock-free structure is built from atomic instructions such as compare-and-swap (CAS), which changes a value only if it still holds what the caller expected, and it uses no locks. Chapter 14 covers how they work. The short version for this decision is to reach for one when you can't tolerate a thread being paused while it holds something, and not because it sounds faster.

The operating system can pause any thread at any moment to run another one, which is called being descheduled. With a lock, a descheduled holder leaves every waiter stuck, which is usually just slow. In a few places it's a correctness problem. A signal handler is a function the operating system runs on top of whatever a thread was doing: if that thread held the lock the handler wants, the handler waits forever for a thread that can't continue until the handler returns. Interrupt context, kernel code answering a hardware event, isn't allowed to be put to sleep, so it can't wait on an ordinary mutex the way a thread does. And hard real-time systems have deadlines they must meet every single time.

?Aren't lock-free structures faster?

Not under heavy contention. Chapter 14 measured a CAS-based counter at 162 ns per increment against a mutex's 16 ns at eight threads, because threads keep failing and retrying. There's a second cost too: reclamation, knowing when it's safe to free a node that another thread might still be reading, becomes a research problem. If you need a lock-free structure, use an existing implementation.

We now have four designs for the hit table, from one mutex to no sharing at all, and each one fits a different situation. What's left is a way to pick between them.

8.1Five questions

Each design in this chapter answers one of these questions, and the order is the order in which to ask them.

1. Can you avoid sharing entirely? Per-thread state with a periodic merge beats every algorithm in this chapter (section 6). Check this first, every time.
2. Is there a single hardware atomic for it? A counter wants fetch_add, not a structure, and a flag wants fetch_or (section 6.2).
3. Are your keys well distributed? If yes, stripe, with a stripe count close to the thread count (section 4). If a hot key takes a large share, striping buys you nothing and you're back to question 1.
4. Is blocking a correctness problem? A signal handler, an interrupt or a hard deadline means lock-free, and an existing implementation (section 7).
5. Otherwise use one mutex and move on (section 2). It's probably right more often than this chapter's existence suggests.

8.2The four designs side by side

8.3What production code chose

Real systems made the same choices. A few terms in the table: a bin is one bucket of a hash table, and a ring buffer is a fixed-size circular queue whose slots are allocated once and reused.

8.4Finding these problems in a running program

Two tools cover most of what this chapter raised.

# Is one lock taking all the waiting? Compare per lock, never the total (section 5.1). Linux:
perf lock contention
 
# Is there a data race, like the unlocked counter in section 1? Build with ThreadSanitizer and run:
clang++ -std=c++20 -g -fsanitize=thread prog.cpp -o prog && ./prog

ThreadSanitizer reports a data race: two threads touching the same memory at the same time with at least one writing and no synchronization. It would flag a plain unlocked hits++. It stays silent about check-then-act across two safe calls, like section 2.3's contains and insert, because every individual access there is correctly locked. That bug only shows up as wrong counts, so look for it in code review: two calls on one structure with a decision between them.

8.5Symptom, cause, fix