Lock granularity

The problem it solves

You have a map shared by sixteen threads, and one lock around it. Every operation takes that lock, does something short, and releases it. The code is obviously correct.

It is also capped. One thread can be inside the critical section at a time, so the whole system can perform at most one operation per critical section duration — no matter how many threads arrive, no matter how many cores you buy. If the critical section is 100 nanoseconds, the ceiling is ten million operations a second and the seventeenth thread makes no difference to it.

That is the entire content of lock granularity, and it is worth seeing as a curve rather than a slogan, because the shape has two features people consistently miss. The first is that the ceiling exists at all — throughput goes flat, it does not degrade gracefully. The second is that splitting the lock raises the ceiling and it is still a ceiling.

The mechanism

A lock turns its critical section into a serial region, so this is Amdahl’s law with a mutex in place of the sequential fraction. Everything Amdahl says applies unchanged: the ceiling is set by the serial part, adding parallel capacity does not move it, and reducing the serial part is worth more than anything else you can do.

Two levers follow directly.

Split the lock. Instead of one lock for the whole map, keep n locks and route each key to one of them by hash — a striped or sharded lock. Now n critical sections can be in progress simultaneously and the ceiling is n times higher. Java’s ConcurrentHashMap did exactly this for years with a configurable concurrency level; modern versions lock per bin, which is the same idea taken to its limit.

Shorten the critical section. Halve the time the lock is held and the ceiling doubles, for free — no extra memory, no striping to get wrong, no rebalancing. This is almost always the first thing to try and almost always skipped, because splitting the lock feels like the sophisticated answer.

The usual way to shorten it is to move work out: compute the new value before acquiring, do I/O outside, allocate outside, format the log message outside. A critical section should contain the update and nothing that could have been done beforehand.

What the enumeration shows

This is one of the section’s model pages: a curve rather than an interleaving space, because every ordering produces the same throughput and what varies is a parameter.

With one lock and a 100ns critical section, throughput is flat at 10 million operations a second from two threads onwards. Adding threads does nothing at all — the line is horizontal, which is the picture of a ceiling.

Drag the lock count to 8 and the ceiling moves to 80 million. The shape does not change; it is still flat once the threads exceed the locks. That is the point of the second series on the chart, and the reason “we sharded the lock” is a partial answer rather than a solution.

Then drag the critical section from 100ns to 50ns with a single lock, and the ceiling doubles. One dial, no structural change, same benefit as adding a second lock — and none of the complexity.

The numbers worth carrying

• One lock, 100ns critical section: 10M ops/s, forever. The thread count does not appear in that number.
• n locks: ceiling is n × (1 / criticalSection), until the keys collide rather than the locks — which is the birthday problem, and is why more stripes stop helping well before you would guess.
• Halving the critical section doubles the ceiling. This is exact and costs nothing.
• Uncontended lock overhead is 20–50ns, so a critical section of 20ns is mostly lock. Below that, the lock is the work and finer granularity buys nothing.

Where it breaks down

More locks means more memory and more risk. Each stripe is an object, and taking two stripes at once — a putAll, a resize, an operation spanning keys — reintroduces deadlock with a lock ordering that now has n participants. Operations that need a consistent view across stripes need all of them, which is worse than one lock.

Stripes do not help a hot key. All the traffic for one key lands on one stripe. This is the same failure as a hot partition in sharding, and no amount of striping addresses it, because the skew is within a key rather than across them.

The model assumes uniform distribution. Real keys are Zipfian, so the busiest stripe carries far more than its share and the effective ceiling is set by that stripe rather than the average.

Cache effects are not in the model. Sixteen locks in adjacent memory can share cache lines, so threads taking different locks still contend on the hardware — see false sharing. Real striped structures pad their locks apart for exactly this reason, and the model here does not capture the cost of getting that wrong.

What people get wrong

“We added more locks so it scales now.” It scales n times further and is still flat after that. The ceiling moved; the shape did not.

“Fine-grained locking is better.” It is more scalable and more complex and more deadlock-prone. Coarse locking that is never contended is better than fine locking that is.

“Lock-free would fix it.” Lock-free removes blocking, not contention. Sixteen threads compare-and-swapping one location generate more coherence traffic than sixteen threads queueing on a lock — see compare-and-swap.

“The lock is the problem.” The contention is the problem. The same lock in a workload that rarely touches it costs nothing measurable. Profile whether threads are actually waiting before restructuring anything.

In production

The escalation ladder, in the order worth trying:

1. Shorten the critical section. Move computation, allocation and I/O out. Free, and often sufficient.
2. Split by data. One lock per shard, per bin, per account. ConcurrentHashMap, striped counters, per-connection state.
3. Stop sharing. Per-thread accumulators summed on read — LongAdder, per-core statistics — which removes contention rather than dividing it. See work stealing for the same move applied to queues.
4. Change the structure. A reader-writer lock if reads dominate, a copy-on-write collection if writes are rare, immutability if you can afford the allocation.

The measurement that tells you which rung you are on: lock wait time as a fraction of total time, available from jstack sampling, perf lock, Go’s mutex profile, or any decent profiler. If threads are not waiting, none of this matters.

The follow-up questions

“One lock around a shared map, sixteen threads. What is the throughput?” — One critical section at a time. Give the ceiling arithmetic; the thread count is irrelevant.

“How do you make it faster?” — Shorten the critical section first, then split by key. Leading with striping is the answer of someone who has read about it rather than done it.

“You striped it into 16 locks. What did you just introduce?” — Multi-stripe operations and a lock ordering problem, plus false sharing between adjacent locks.

“Your keys are Zipfian. Does striping still work?” — Less well, and for the hot key not at all. The stripe carrying it is the ceiling.