The granularity question
Every lock has a scope: the set of data it protects. Coarse-grained locking uses one lock, or very few, to guard an entire data structure or subsystem; fine-grained locking splits that same structure into many independently-locked pieces so unrelated operations can proceed in parallel. Neither is universally "better" — this is a genuine engineering trade-off, and one of the areas where a senior-level answer is "it depends, and here's how I'd measure it" rather than a single rule.
| Coarse-grained (one big lock) | Fine-grained (many small locks) |
|---|
| Correctness | Easy to reason about — one lock, one invariant | Harder — every invariant that spans two pieces must still hold when they're locked separately |
| Concurrency | Poor under contention — every operation serializes behind the single lock, even ones touching unrelated data | Good — operations on different shards/pieces run fully in parallel |
| Overhead | One acquire/release per operation | More lock objects to allocate, acquire, and release — a real, if usually small, per-operation cost |
| Deadlock risk | Essentially none — only one lock exists | Real — any operation that must hold two or more of the fine-grained locks simultaneously can deadlock if different threads acquire them in different orders |
| When it's the right call | Low contention, short critical sections, or correctness/simplicity outweighs throughput | High contention, hot path, profiling has proven the single lock is the bottleneck |
The standard advice, echoed by OSTEP's chapter on lock-based data structures, is to start coarse-grained. A single lock around an entire structure is trivially correct, and for most workloads it's also fast enough, because lock acquisition itself is cheap — the expensive part is waiting for it, which only matters under real contention. Splitting locks earlier than the data justifies is a classic premature optimization: it adds real complexity and deadlock surface area in exchange for parallelism nobody is currently using.
Lock striping: the standard fine-grained pattern
When contention is real and measured, the most common fine-grained technique is lock striping (also called sharding): instead of one lock for the whole structure, allocate a fixed array of N locks, and deterministically map every element to exactly one of them — classically hash(key) % N. Two threads touching different shards never contend at all; only threads that happen to hash to the same shard serialize with each other. This is precisely how early versions of Java's ConcurrentHashMap scaled far past a single synchronized HashMap: 16 segment locks meant up to 16 threads could write concurrently as long as their keys landed in different segments. Later JDK versions went even finer, locking individual hash buckets instead of fixed segments, but the underlying idea — shrink the lock's scope to shrink what serializes — is identical.
locks = [new_lock() for _ in range(N)]
put(key, value):
i = hash(key) % N
locks[i].acquire()
... mutate only the bucket(s) that hash to i ...
locks[i].release()
Striping isn't free: any operation that needs a global view — "how many total entries?" — now has to either accept an approximate or stale answer, or acquire every stripe lock, which reintroduces full serialization for that one operation and, if done carelessly, a deadlock risk.
The deadlock risk fine-grained locking introduces
The moment any single operation needs to hold more than one of your fine-grained locks at once — moving an element from bucket A to bucket B, for example — you've created the classic precondition for deadlock: if thread 1 locks A then B while thread 2 locks B then A, they can each hold one lock while waiting on the other, forever. The standard, deceptively simple fix is a global lock ordering: define one consistent order across all locks — by memory address, by shard index — and require every code path to acquire multiple locks in that order, never the reverse. This is worth previewing here because Deadlock, Livelock & Starvation, later in this roadmap, covers it in full depth as one of the four necessary conditions for deadlock.
False sharing: correct, but silently slow
Even when your locking is airtight, fine-grained data layout can betray you at the hardware level through false sharing. CPU caches move data in fixed-size cache lines, typically 64 bytes, and cache-coherency protocols invalidate an entire line whenever any core writes to any part of it. If two threads have their own logically independent counters — say, adjacent elements of an array, one per thread, specifically to avoid needing a shared lock — but those counters happen to sit on the same cache line, every write from thread A invalidates thread B's cached copy of the line and vice versa, even though the two counters are unrelated and there is no data race at all. The result looks exactly like lock contention — throughput collapses as you add threads — with none of the causes a profiler's lock-wait metrics would show, which makes it a notoriously sneaky class of bug to diagnose. The fix is padding: space each hot, independently-written variable out to its own cache line, or restructure so each thread accumulates in fully separate memory and merges only occasionally, trading memory for eliminating the invalidation traffic.
Pitfalls and interview gotchas
- Splitting locks before measuring. Fine-grained locking is a response to proven contention, not a default — reach for it after profiling shows the coarse lock is actually the bottleneck, not preemptively.
- A multi-lock operation without a fixed acquisition order. The single most common way fine-grained designs introduce deadlock; always articulate, and ideally enforce in code rather than just in a comment, one global ordering.
- "Global" operations under striping. Size, iteration, or any cross-shard invariant either needs to tolerate staleness and approximation, or must acquire every stripe lock — know which one your design promises, because they have very different consistency guarantees.
- Mistaking false sharing for a correctness bug. It produces a performance symptom — throughput doesn't scale with threads, sometimes gets worse — with no incorrect output. Don't go looking for a race condition that isn't there; look at memory layout and cache-line boundaries instead.
- Padding everything "just in case." Padding trades memory for eliminated coherency traffic; over-applying it to rarely-contended or read-mostly data wastes cache capacity for no benefit — pad only variables that are both hot (frequently written) and genuinely shared across cores.