Coarse vs. Fine-grained Locking

In concurrent applications, synchronization is necessary to protect shared mutable data. However, how we apply locks—the granularity of our locking strategy—has a massive impact on performance. Using locks that are too broad causes performance bottlenecks, while locks that are too narrow introduce complexity and risk deadlocks.

1. Learning Objectives

• Differentiate between coarse-grained locking and fine-grained locking.
• Understand the causes and impact of Lock Contention.
• Master Lock Striping techniques to optimize collection throughput.
• Analyze how JDK's ConcurrentHashMap uses segmented locking to reduce contention.
• Evaluate the memory overhead and complexity trade-offs of granular locks.

2. Problem & Naive Solution

Suppose you are building a high-throughput cache for a web server. The cache stores thousands of user sessions in a key-value map. Multiple request threads read and write to this cache concurrently.

The Naive Solution (Coarse-Grained Monolithic Lock)

A developer makes the cache thread-safe by synchronizing all operations on a single global lock monitor:

3. Issues with the Naive Approach

• Severe Lock Contention: Because all operations are synchronized on the same cache instance, only one thread can read or write at any time. If Thread 1 is writing to key UserA, Thread 2 is blocked from reading key UserB, even though they are completely unrelated. Under high traffic, this bottlenecks performance, turning concurrent execution into slow sequential processing.
• Poor Resource Utilization: The CPU cores sit idle waiting to acquire the monolithic lock, failing to leverage multi-core hardware.

4. Lock Striping Comparison

Below is a comparison of coarse-grained locking (locking the entire structure) and fine-grained lock striping (dividing the structure into segments, each protected by its own lock).

5. Theory: Locking Granularity & Lock Striping

Let's explore the concepts behind locking granularity:

A. Coarse-Grained Locking

• Pros: Simple to implement, easy to verify correctness, low risk of deadlocks.
• Cons: High lock contention, poor performance under concurrent write workloads.
• Typical Use Case: System setup, startup initialization, or low-contention environments.

B. Fine-Grained Locking & Lock Striping

Instead of locking the entire collection, Lock Striping uses an array of locks (stripes). Keys are partitioned across these stripes using a hash function:

This allows threads to access different segments of the collection concurrently.

• Pros: High throughput, reduced lock contention, better multi-core scalability.
• Cons: Higher memory overhead (allocating multiple lock objects), complex implementation, and increased risk of deadlocks if a thread needs to acquire multiple locks.

C. ConcurrentHashMap Segmented Locking

In early Java versions, Hashtable used a monolithic lock. ConcurrentHashMap optimized this by using lock striping (dividing the map into 16 segments). In modern Java versions, ConcurrentHashMap uses Compare-And-Swap (CAS) operations for bucket insertion, falling back to synchronizing only the first node of a bucket during hash collisions, providing extremely high concurrency.

6. Syntax Explanation

To implement lock striping, we allocate an array of lock monitors:

• Java: Instantiate an array of Object monitors or ReentrantLock instances.
• Python: Create a list of threading.Lock() instances.
• C++: Allocate a std::vector<std::mutex> to manage segmented locks.

7. Step-by-Step Implementation

1. Define the Lock Array: Determine the number of lock stripes (e.g., 16). Instantiate an array of lock objects.
2. Implement Hash Mapping: Write a helper function that maps key hash codes to lock array indices.
3. Acquire Segment Lock: Inside the put or get methods, calculate the key's lock index and acquire that specific segment lock.
4. Release Segment Lock: Wrap the operation in a try-finally block to guarantee the segment lock is released.

8. Complete Code (Striped Key-Value Cache)

This program implements a concurrent Key-Value cache using lock striping (16 lock segments) to reduce thread contention.

9. Code Walkthrough

• Stripe Mapping: When calling put(key, value), the map computes Math.abs(key.hashCode()) % numStripes to select the segment (stripe) that owns the key. Only the lock associated with that segment is acquired.
• Concurrent Execution: If Thread 1 is writing to UserA (stripe 0) and Thread 2 is writing to UserB (stripe 1), they acquire different locks, allowing them to run concurrently without waiting for one another.

10. Complexity Analysis

• Time Complexity: $O(1)$ to find the bucket index and acquire the lock.
• Space Complexity: $O(S)$ space, where $S$ is the number of lock stripes allocated.

11. Best Practices

• Measure Performance Before Implementing Striping: Do not use lock striping prematurely. It adds design complexity. Only implement it if benchmarks show that global locks are causing performance bottlenecks.
• Avoid Acquiring Multiple Striped Locks: If a thread attempts to acquire multiple segment locks (e.g., to clear the map), it must acquire them in a strict, consistent order (e.g., locking from index 0 to $N-1$) to prevent deadlocks.

12. Common Mistakes

• Over-Allocating Lock Stripes: Spawning thousands of lock objects. This wastes heap memory and introduces resource management overhead. Stick to default capacities (e.g., 16 or 32 stripes).
• Dynamic Re-Hashing Without Locking All Stripes: Attempting to resize a striped collection without acquiring all segment locks. This allows other threads to modify data during the resize, corrupting the collection state.

13. Interview Discussion

14. Practice Exercises

• Easy: Write a program that measures the throughput of a synchronized map versus a striped map under concurrent write workloads.
• Medium: Implement a striped counter class that has an array of 8 counters. Threads update random indices, and a read method sums them up.
• Hard: Build a thread-safe HashTable implementation that supports dynamic resizing. Acquire all segment locks in a consistent order during resizing to prevent deadlocks.

15. Challenge Problem

Design an Enterprise User Management Registry. The registry stores millions of users, keyed by a UUID string. It supports high-frequency operations:

• registerUser(String uuid, UserDetails details)
• updateUserStatus(String uuid, Status status)
• countActiveUsers(): Aggregates active status counters across all segments.

Implement this registry using lock striping (16 stripes). Ensure that countActiveUsers() acquires locks in a consistent order to prevent deadlocks when executing concurrently with registration requests.

16. Summary & Cheat Sheet

• Coarse-Grained Locking locks the entire collection, which is simple but can cause high lock contention.
• Fine-Grained Locking / Lock Striping divides a collection into segments, each protected by its own lock, reducing contention and improving throughput.
• Always acquire multiple locks in a consistent order to prevent deadlocks.

17. Quiz

18. Next Lesson Preview

In the next lesson, we will cover Reentrant Locks & CAS. We will study lock-free algorithms, hardware-level Compare-And-Swap (CAS) instructions, and compare optimistic locking with reentrant locks!