How do you decide how coarse or fine-grained your locking should be, what is lock striping, and what is the convoy effect that can appear under a hot lock?

## The granularity spectrum **Coarse-grained**: one lock guards a whole subsystem or data structure. Easy to reason about — one invariant, one lock, no ordering problems — but every operation is serialized against every other, including ones that touch disjoint data. **Fine-grained**: many locks guard disjoint parts (per bucket, per node, per shard, per account). Disjoint operations run in parallel, but you inherit multi-lock problems: lock-ordering deadlocks, operations that must atomically span parts, harder invariants, and more acquisitions per operation. The governing model is **Amdahl's law**: if fraction *s* of the work is serialized, maximum speedup is 1/(s + (1−s)/p) for *p* processors, so with s = 0.05 you cannot exceed 20× however many cores you buy. A global lock makes *s* the fraction of time spent inside it. Fine-graining is precisely the act of shrinking *s*. It is also why the first lever is usually not more locks but a *shorter critical section* — move computation, formatting, allocation and I/O outside the lock. ## Lock striping Striping (sharding) applies when the protected data is keyed and operations are usually key-local: ``` locks[N] lockFor(key) = locks[hash(key) mod N] put(k, v): L = lockFor(k); L.acquire(); ... ; L.release() ``` Design points: - **Choosing N.** Too small and you keep contention; too large and you burn memory, hurt cache locality, and make global operations expensive. A few times the core count is a common starting point, tuned by measurement. - **Cross-stripe operations.** Anything atomic across two keys must take both locks **in a fixed global order** (by stripe index) or use try-and-backoff, otherwise you have reintroduced deadlock. - **Global operations.** Exact size, iteration, or resize needs every stripe. Options: accept an approximate answer from per-stripe counters, acquire all locks in index order for the rare global case, or maintain a separate summary. - **False sharing.** If the N lock words share cache lines, threads on different stripes still ping-pong the same lines and you get contention with none of the logical conflict. Pad locks to cache-line boundaries when it matters. An alternative to striping worth naming: partition by *thread* rather than by key — each thread mutates only its own state, and a reader aggregates. That removes the lock entirely for the write path, at the cost of approximate or snapshot-style reads. ## The convoy effect A convoy is not simple contention. It starts when the lock **holder stops running** while holding — because its timeslice expires, it takes a page fault, it allocates and triggers a collection, or it performs I/O. Every other thread that wants the lock now blocks and queues, and the queue keeps growing for the whole time the holder is off-CPU. When the holder finally releases, the effects persist: - Every queued thread must be woken individually, so each grant costs a context switch instead of a fast uncontended acquire. - The group is now **synchronised**: they were all released at nearly the same moment, so they arrive at the *next* lock together and requeue, reproducing the convoy for as long as the workload lasts. - Because each thread runs only a short critical section before releasing, the system spends most of its cycles on scheduling rather than work; measured throughput can fall below what a single thread alone would achieve. Remedies, in order of impact: 1. **Never block while holding a lock** — no I/O, no network calls, no unbounded allocation, no waiting on another thread's result, no alien code. 2. **Shorten hold time** so the odds of being preempted while holding drop. 3. **Allow barging** — an unfair lock lets a running thread proceed instead of forcing a lockstep handoff, which breaks the synchronisation that sustains the convoy. 4. **Reduce contention** via striping or partitioning so fewer threads are ever queued behind one holder. 5. Where supported, adaptive spinning: brief spin before parking, so short holds never reach the scheduler at all. ## How to actually decide Instrument first: hold time, wait time distribution, acquisitions per second, and queue length per lock. Then follow the order: shrink the critical section, remove blocking calls from it, stripe or partition, and only then consider exotic policies. Every added lock is permanent complexity — a new ordering rule that every future change must respect — so it should be bought with a measurement, not an intuition.