The currency is coordination

Why can throughput fall as threads are added?

Terms for this article

This article uses a few words from concurrent programming. Short definitions first.

• Thread: one sequence of instructions running on a CPU core. A server runs many threads at once.
• Lock (mutex): a flag that only one thread can hold at a time. Other threads that want it must wait ("block"). Holding a lock lets a thread change shared data safely.
• Atomic operation: an operation the hardware performs as one indivisible step. Other threads see it either not done or fully done, never half done.
• CAS (compare-and-swap): an atomic instruction that says "set this memory word to new only if it still equals old; tell me whether it worked." If two threads try at once, one wins and the other fails and must retry.
• Fetch-and-add (FAA): an atomic instruction that adds a number to a memory word and returns the old value. It never fails: the hardware puts the callers in a line, and each caller gets a different old value.
• Cache coherence: the hardware rule that keeps the copies of one memory location in different cores' caches consistent. The common protocol is called MESI. In plain words: when a core writes to a cache line, every other core's copy of that line is marked invalid. The other cores must fetch the line again (from the writer's cache) before they can use it. Coherence works per cache line (64 bytes), not per byte.
• Memory ordering (release/acquire): modern CPUs may reorder memory operations. A release store says "everything I wrote before this is visible to anyone who sees this store". An acquire load says "after I see this value, I also see everything written before it was stored". Together they let one thread safely hand data to another without a lock.
• Contention: several threads wanting the same resource at the same time.

---

Every cost model in the earlier articles assumed one logical thread of control. How many fetches, how many bytes, how much space: all of these were properties of one actor working alone. This article changes the currency to coordination: the cost of many actors agreeing on who may touch what, and when.

Coordination has a property that none of the earlier currencies had.

Read, write and space costs are monotone: adding memory never made a B-tree slower, and adding disk never made an LSM-tree worse. Coordination cost is superlinear in the number of participants, and it can have negative return. The Universal Scalability Law (USL) describes this. In its common form, the relative throughput with N workers is

Here α is the fraction of work that must run one at a time, and β the cost of workers coordinating pairwise, which grows with N². Because of β, throughput peaks at N* = √((1 − α) / β) and then declines: past that point, adding cores to a contended structure makes it slower. This cannot happen anywhere else here. The derivation and a worked example are on that page; real α and β come from measuring, as in Fit a USL curve to a contended structure.

The contention is physical, and it has an address

The USL's β is not an abstract idea. In a real program it is a specific 64-byte cache line at a specific address.

Not a lock, not a data structure, not a conflict between two operations in the program's logic. A cache line. Because coherence works per 64-byte line, two cores that update two different variables in the same line pass the line back and forth at about 40–100 ns a transfer, against about 1 ns for an uncontended increment. This is false sharing: a 40–100× penalty that is invisible in the source code and is fixed by 64 bytes of padding. It exists because the boundary between "my variable" and "your variable" is not a boundary the hardware recognizes.

The Physical-contention law

The observation is general enough to name. We call it the Physical-contention law:

Three ways not to coordinate

There are exactly three ways to avoid coordination. Every structure in this article is one of them.

1. Do not share. Give each thread its own data. Cost: you must be able to partition the work, and skew (one partition getting more than its share) becomes the hard limit. This is the single-writer principle. It is the only escape that eliminates coordination instead of managing it.
2. Do not mutate. Readers never conflict with other readers. If writers publish new versions instead of changing old ones, readers never conflict with writers either. Cost: extra space, plus a collector to free old versions. This is the Immutability law again: an immutable layout needs an indirection layer and a collector.
3. Gamble and retry. Assume there is no conflict, detect a conflict if one occurs, and retry. Cost: wasted work under contention, at a retry rate that rises like 1/(1 − ρ). This is the Queueing law, which we first met in hash table load factors. It describes optimistic concurrency identically, because both are queueing for a contended slot.

The order of preference follows from this list: partition beats immutability beats optimism beats locking. The first two remove the contention. The last two only price it. This is also, not by chance, the order in which the industry moved over the years.

Coordination is the only cost here that grows superlinearly with the resources you add to fix it. That is why the winning designs remove it instead of optimizing it.