When Locks Win — Contention, Fairness & Hybrid Designs
A short mutex often beats a CAS storm on one cache line. Locks cover multi-field invariants, fairness, and review. This page is when to keep them, when to shard, and when a hybrid is honest.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
When is a mutex the default?
Answer
The invariant spans fields, the thread may sleep, or contention is low enough that the fast path is already cheap.
L2
Why can removing a lock make p99 worse?
Answer
Contended CAS on one cache line spins and bounces. A parking mutex takes waiters off the CPU. The spin can burn more time than the critical section.
L3
What is lock striping?
Answer
Many locks, each covering a slice such as a hash bucket, so unrelated keys do not share one line. It is not a lock-free map.
L4
What does a hybrid path promise?
Answer
A few CAS or try-lock attempts, then a mutex for the full invariant. Progress on the slow path is blocking. Do not claim lock-free.
L5
Throughput versus fairness?
Answer
A barging mutex or a CAS loop can have great throughput and a terrible tail. A ticket or MCS lock queues the waiters and spends more to bound that tail.
L6
How do you know the lock is the problem?
Answer
A profile: on-CPU spin, off-CPU wait, and lock-contention stats. If threads wait and the section is tiny, consider an atomic or a shard. If the section is fat, shrink it first.
L7
What is a seqlock good for?
Answer
Rare writes and many readers. The writer bumps a sequence. Readers retry if the sequence changed. It still needs a real memory order and a section that readers can repeat.
Failure modes
CAS storm after the lock was removed
The critical section was short and contended. CPU goes to the ceiling. The mutex was the throttle.
Hybrid advertised as lock-free
The slow path takes a mutex. A holder can block everyone who falls back. The progress class changed.
Stripe that is still one line
Adjacent locks share a cache line through false sharing. The stripe count is on paper only.
Fairness ignored until the tail SLO burns
Barging looks fast in a throughput chart and one thread's p99 is the incident.
Misconceptions
Locks do not scale, so production code should be lock-free.
Uncontended locks scale. Contended single-line CAS does not. Sharding and shorter sections scale more often than a new algorithm.
A try-lock loop is lock-free.
If you eventually block on the mutex, you are blocking. The tries are an optimization.
This page is about Redis or ZooKeeper locks.
Those are distributed leases and fencing. Process-local contention is the subject here.
Interviewer traps
Re-teaching deadlock ordering or condition-variable loops.
Say the mutex stays, then point at the mutex cluster. Stay on contention and the hybrid.
Treating a distributed lease as the answer to a hot counter.
A hot counter is a fetch-add or a shard in one process. A lease is a different failure domain.
Design scenario
Same prompt for every reader.
Requirements
Session updates must stay multi-field consistent. The counter must not share the map's lock. The queue should not be rewritten as MPMC unless a profile says the mutex is hot and a library is chosen.
Traffic / scale
The counter is the hottest word. Session updates collide on a few keys. The queue is moderate.
Latency
Session p99 must not track a CAS spin. The counter must stay off the session lock.
Consistency
A session's fields change together. A reader never sees a new id and an old expiry.
Availability
A thread stuck in a session update may delay that shard. It must not stop counter increments.
Failure assumptions
- The CAS rewrite was justified by a slogan, not a profile.
- A few session keys are hot.
- Someone will share one cache line between stripes.
Constraints
- Do not hold the session lock across I/O.
- Do not describe the fallback mutex as lock-free.
Prompt
A process has a metrics counter, a hash map of sessions updated on several fields, and a small task queue. A prototype replaced the map's mutex with a single CAS loop and CPU saturated. The counter was never the problem.
API
Which structure is fetch-add, which is a striped mutex, and which stays a single mutex?
Data
How many stripes, and how do you keep them on separate cache lines?
Architecture
What profile number would justify replacing the queue with a library?
What to do with a hot update
Prefer
Shrink, shard, or park
Make the critical section smaller, give hot keys different lines, or let a mutex park waiters. Keep fetch-add for the true single-word counter.
- A profile names the line before anyone deletes a lock.
- Stripes are still locks, with less collision.
- The slow path of a hybrid is allowed to block.
Alternative
Replace every mutex with CAS
One word, every core, no backoff. CPU saturates and the tail belongs to whoever wins the line.
- The uncontended benchmark that justified the change is gone.
- Multi-field session updates tear.
- The team cannot debug a failure that does not deadlock.
A contention decision that survives review
Measure, then shard, then ask whether anyone still has to wait.
- 1
Profile the wait and the spin
On-CPU time in a CAS loop and off-CPU time on a mutex are different problems. A slogan is not a profile. - 2
Shrink the critical section first
Move I/O and allocation out. A fat section is slow under any primitive. - 3
Shard what is actually hot
Per-core counters, or a stripe per bucket, padded so neighbors do not share a line. - 4
Fall back to a lock when the CAS fails
A few attempts, then the mutex that can express the whole invariant. Say blocking out loud.
Overview
Lock-free is not a purity test. Under contention, a short critical section behind a mutex often beats every core spinning on one word. Locks also cover multi-field invariants, can be made fair, and show up in deadlock reports a human can read. This page is the decision. It does not re-teach lock ordering or condition variables. Those stay on mutexes. It is also not about leases. Distributed locks fail differently, across processes, with fencing tokens.
Where the mutex is the right tool
- The invariant spans fields. Two account balances, a set of graph edges, a session id and its expiry. One CAS does not cover them.
- The section is long or unpredictable. I/O, allocation, or a validation loop. A CAS around that work is a spinlock with extra steps.
- Contention is low or moderate. An uncontended mutex fast path is a CAS already. Clarity wins until a profile says otherwise.
- You care about the tail. A CAS loop barges. A ticket or MCS lock queues waiters.
- The team has to operate it. Lock-order tooling and a stack trace beat a rare ABA that only fails on Tuesdays.
- A library already exists.
ConcurrentHashMap,sync.Map, or a mutex around a map beats a weekend lock-free map.
Where the atomic stays
- A single-word counter, sequence number, or a tiny state machine.
- An SPSC ring whose proof you already have from lock-free structures.
- Read-mostly data with a seqlock or an epoch, if you can say the order.
- Runtime internals owned by people who review reclamation for a living.
Contention is a cache line
Every core that CASes the same word invalidates every other core's copy. The line spends its life in transit. A mutex that parks waiters takes those cores off the line so the holder can finish. Removing the lock can raise CPU and p99 together. That is the usual surprise in the prototype that "got rid of the lock."
Decisions
- 1
Hot shared word
- nextCAS failures high?
- ?
CAS failures high?
- NoKeep the atomic
- YesAsk if you can shard
- 3
Keep the atomic
- 4
Ask if you can shard
Lesson map
When Locks Win — Contention, Fairness & Hybrid Designs
A short mutex often beats a CAS storm on one cache line. Locks cover multi-field invariants, fairness, and review. This page is when to keep them, when to shard, and when a hybrid is honest.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["Hot shared word"] b["CAS failures high?"] c["Keep the atomic"] d["Ask if you can shard"] a -->|Hot shared word to CAS failures high?| b b -->|No| c b -->|Yes| d
If you cannot shard, the next cut is the length of the update:
Decisions
- 1
Cannot shard the word
- nextSection still short?
- ?
Section still short?
- YesMutex or try-CAS then lock
- NoMove work off the line
- 3
Mutex or try-CAS then lock
- 4
Move work off the line
Hybrids
Optimistic path, then a lock:
for attempt in 0..K:
if cas_path_succeeds():
return
backoff(attempt)
acquire mutex
slow_path_with_full_invariant()
release mutexYou see this in allocators and in maps that stripe locks. The first attempts are the fast path. The mutex is the algorithm for the hard case. Once that fallback exists, a thread can block, so the progress class is blocking. Document it that way.
A seqlock is the read-mostly cousin. The writer takes a lock or bumps an odd sequence, writes, then publishes an even sequence with a release. Readers load the sequence, copy the data, and retry if the sequence changed or was odd. Readers must tolerate a torn copy and must not have side effects in the retry. The order rules are the memory ordering page. Seqlocks are a poor fit for a write-heavy map.
Lock striping is many mutexes. A hash map locks the bucket, not the world. Unrelated keys proceed together. Pad each stripe to its own cache line or false sharing puts you back on one line. Striping is not lock-free. It is a smaller lock.
Fairness
| Primitive | Fairness | Note |
|---|---|---|
| Raw CAS loop | Unfair | Barging, and it thrashes the line |
| Spinlock | Unfair | Do not hold it long |
| OS mutex | Often barging | Throughput is the usual goal |
| Ticket or MCS lock | FIFO-shaped | Better tails, more machinery |
| Channel | The scheduler | Backpressure is not lock fairness |
Throughput is not fairness. A latency SLO can force a fairer lock or a shard even when the average looks fine. Say which one the product asked for.
How you know
Look at a profile before you rewrite the synchronization. If threads are off-CPU inside the lock and the section is tiny, an atomic or a shard is plausible. If they are on-CPU inside a CAS loop, the lock you removed was doing useful parking. If the section is large, shrink it before you change the primitive. "Locks do not scale" is not a flame graph.
Sandbox
The hybrid counter takes the fast path when the flag is free and counts a fallback when it is not. The sharded counter keeps each id on its own slot so the sum does not need one line.
ExpectedAn idle counter uses the fast path. A held flag uses the fallback and still adds.
Press Run. Snippets must be self-contained — no network, files, or native modules.
ExpectedTwo writers on different slots sum to 2, and the same slot sums to 2 as well.
Press Run. Snippets must be self-contained — no network, files, or native modules.
In native code, pad each shard to a cache line. Adjacent Int32 slots still bounce if two cores write neighbors. The sketch above only shows the index split.
A decision table
| You need | Prefer |
|---|---|
| Several fields updated together | A mutex, or a real transactional API |
| The highest uncontended increment rate | Relaxed fetch-add, sharded if it gets hot |
| A one-producer one-consumer stage | The SPSC ring |
| A tail latency SLO | A fair lock, a shard, or both |
| Something you can hand to a new teammate | The mutex, until a profile disagrees |
| A queue at the edge of the latency budget | A reviewed lock-free library, not a new one |
Killing a process mid-update is a durability question, not a reason to CAS a linked list. Journaling and lock-free structures solve different failures.
Interview Q&A
The interviewer says locks do not scale and lock-free is mandatory. What do you say?
Answer
Uncontended locks scale. A contended CAS on one line also fails to scale, and it fails by spinning. Ask what is contended, how long the section is, and whether the tail has to be fair. Then shard or shorten the section. Lock-free is for a progress or latency case you can name, usually inside a library someone owns.
How do you know the lock is the problem?
Answer
Profile it. CPU in the spin, off-CPU wait on the futex, and a contention statistic if the runtime has one. Tiny section plus waiting threads: consider an atomic or a shard. Fat section: shrink it before you touch the primitive.
What is lock striping?
Answer
Several locks, each guarding a slice of the data, so two updates on different slices do not exclude each other. Hash-map bucket locks are the usual picture. It reduces collisions. It is still locks, and adjacent stripes that share a cache line will still bounce.
Can a hybrid priority-invert?
Answer
Yes, if a low-priority thread holds the fallback mutex and high-priority threads finish their CAS attempts and then block behind it. Know the scheduler. Priority inheritance is a real-time concern, not the default server case, and it is still a reason to be honest that the fallback blocks.
Why not hold the lock across a write to the network?
Answer
The holder stalls every waiter for a round trip, and a CAS replacement of that section would spin for the same round trip. Do the I/O outside. The lock should cover the invariant, not the RPC.
Is a seqlock a replacement for a mutex map?
Answer
No. It fits a small, read-mostly record that readers can copy twice and compare. A map with frequent writes wants stripes or a single mutex. Readers must also use the acquire and release the sequence requires.
What should you say about distributed locks in this interview?
Answer
That they are not this problem. A Redis or ZooKeeper lease can expire while the holder still runs. Fencing is how the resource rejects the stale holder. None of that fixes a hot counter inside one process. Offer the pointer and come back to the cache line.
What do you ship for the session map in the design prompt?
Answer
A striped mutex, padded, with I/O outside the stripe. The counter is a separate fetch-add. The queue stays a mutex or a library until a profile says the lock is hot. The CAS-only rewrite is how the CPU graph caught fire.
Pitfalls
- Deleting a lock because lock-free sounds faster, with no contention number.
- Calling the mutex fallback lock-free in the API docs.
- Striping into one cache line.
- Using a distributed lease for a process-local map.
- Re-deriving condition-variable waiting while answering a contention question.
Take "we should remove the lock." Replace it with the structure, the contention evidence, and the progress class after the change. If you do not have the evidence, the answer is to keep the mutex and shrink the section.
Go Deeper
- Ulrich Drepper, Futexes Are Tricky, and the futex man page for what a parking mutex actually waits on.
- Paul McKenney, Is Parallel Programming Hard, for RCU and for why spinning is not free.
- ConcurrentHashMap and Go's sync package for designs that already made this tradeoff.
- The hub's link list is where profiling, Raft, and channels stay. This page does not absorb them.
Back to the hub.