The Single Lock Problem

A coarse-grained lock protecting an entire data structure creates a bottleneck under concurrent load. Whether it’s a hash table, a cache, or an in-memory index, a single mutex serializes all access—even when threads are working on logically independent data. One thread holds the lock while others queue, wasting CPU cycles and degrading throughput as concurrency increases.

The problem isn’t the lock itself but the granularity. A lock guarding a million-entry hash table treats a write to bucket 0 and a write to bucket 999,999 as conflicting operations, even though they’re completely independent. The lock is doing more work than necessary.

Partitioning Synchronization

Lock striping splits a single lock into an array of locks, each protecting a partition of the data structure. Instead of one mutex guarding the entire hash table, you use 16 or 32 or 64 locks, each responsible for a range of buckets. A thread acquires only the lock corresponding to the bucket it needs to access.

The hash function that maps keys to buckets now also determines which lock to acquire. If a hash table has 1024 buckets and 16 locks, each lock protects 64 consecutive buckets. Thread A accessing bucket 5 and thread B accessing bucket 800 acquire different locks and proceed in parallel.

This doesn’t eliminate contention—it partitions it. Threads accessing the same partition still serialize, but threads working on different partitions can proceed concurrently. The effectiveness depends on how uniformly the workload distributes across partitions.

Choosing the Stripe Count

More locks mean less contention but higher memory overhead and increased complexity. The optimal stripe count depends on expected concurrency and access patterns.

A good starting point is the number of CPU cores or a small multiple of it. Beyond a certain point, adding more locks yields diminishing returns—if you have 8 concurrent threads, 64 locks won’t perform significantly better than 32. The marginal benefit decreases as stripe count increases because the probability of contention on any single lock drops exponentially.

The stripe count is usually a power of two, allowing fast modulo operations via bitwise AND. Instead of hash % stripe_count, you compute hash & (stripe_count - 1), which is faster and produces the same result when stripe count is a power of two.

Implementation Tradeoffs

Lock striping introduces complexity that fine-grained locking avoids. With a lock per bucket, each operation touches exactly one lock. With striping, you lock a partition containing multiple buckets, so operations on different buckets within the same partition still contend.

Resizing becomes harder. Growing a hash table typically requires rehashing all entries, which means acquiring all stripe locks simultaneously—a potential deadlock risk if lock acquisition order isn’t carefully managed. Some implementations freeze writes during resize, others use a temporary coarse lock, and some avoid resizing entirely by preallocating capacity.

Read-heavy workloads benefit less from striping than write-heavy ones. If most operations are reads, a read-write lock may be a better fit, allowing concurrent reads with a single lock. Striping shines when writes dominate or when write volume is high enough that even read-write locks bottleneck.

Striping in Production Systems

Java’s ConcurrentHashMap uses lock striping internally, partitioning the table into segments, each with its own lock. This allows concurrent writes to different segments without coordination. The segment count defaults to 16 but can be tuned based on expected concurrency.

Database buffer pools often use striped latches to protect page access. A buffer pool holding thousands of pages uses dozens of latches, each protecting a subset of pages. This reduces contention when multiple queries access different pages simultaneously.

Memcached uses slab-level locks rather than a single global lock, effectively striping synchronization across memory classes. Different threads allocating from different slabs don’t contend, improving throughput under heavy allocation workloads.

When Not to Stripe

Lock striping makes sense when contention is high, access distributes uniformly, and the data structure is large enough that partitioning is meaningful. For small structures or low-contention scenarios, a single lock is simpler and performs just as well.

If access patterns are skewed—most threads hitting a few hot keys—striping won’t help much. The hot partition becomes a bottleneck while other partitions sit idle. In these cases, application-level caching, sharding, or redesigning the data layout may be more effective.

Striping also doesn’t help when operations span multiple partitions. If you need to lock two or more stripes simultaneously, you reintroduce coordination overhead and potential deadlock risk. Lock-free data structures or redesigning the operation to avoid cross-partition access may be better alternatives.