Monday, 30 May 2016

Lock Striping in Java Concurrency

In case you have only one lock for the whole data structure like Array or Map and you are synchronizing it and using it in a multi-threaded environment. Then, effectively any given time only one thread can manipulate the map, as there is only a single lock. All the other threads would be waiting to get the monitor.

If you have to visualize a HashTable or a synchronized HashMap it can be depicted like the following image.

If there are 6 threads only one can get the lock and enter the synchronized collection. Even if the keys these threads want to get (or manipulate the values) are in different buckets as in the image if two threads want to access keys in bucket 0, two threads want to access keys in bucket 1 and two threads want to access keys in bucket n-3, any given time only one thread will get access.

Single lock for whole collection
Single lock for the whole collection

As expected this seriously degrades the performance, now think if there can be separate locks for separate buckets. Then the thread contention won't be at the whole data structure level but at the bucket level. That's the concept of lock striping. Having separate locks for a portion of a data structure where each lock is locking on a variable sized set of independent objects.

That's how ConcurrentHashMap in Java provides synchronization. By default ConcurrentHashMap has 16 buckets and each bucket has its own lock so there are 16 locks too. So the threads which are accessing keys in separate buckets can access them simultaneously.

If you have to visualize it then following image would give you an idea how lock striping for a ConcurrentHashMap will look like.

Here two threads want to access keys in bucket 0 so one of them can enter, again two threads want to access keys in bucket 1 so one of them can enter. Same with bucket n-3. So, with lock striping out of 6 3 threads can work on the data structure.

Lock Striping in ConcurrentHashMap
Lock Striping in ConcurrentHashMap

Drawback of lock striping

One of the downside of lockstriping as mentioned in "Java Concurrency in practice" is that it is more difficult and costly, if you need to lock the collection for exclusive access than with a single lock.

That's all for this topic Lock Striping in Java Concurrency. If you have any doubt or any suggestions to make please drop a comment. Thanks!

Related Topics

  1. ConcurrentHashMap in Java
  2. Difference between HashMap and ConcurrentHashMap in Java
  3. CountDownLatch in Java concurrency
  4. Synchronization in Java multithreading
  5. ReentrantReadWriteLock in Java

You may also like -

1 comment:

  1. The lock striping mechanism allows multiple threads access to the map concurrently. It sound to me that the number of locks determine the number of concurrent threads. Therefore, I not quite understand the statement below (captured from JCIP)

    "Arbitrarily many reading threads can access the map concurrently, ... and a limited number of writers can modify the map concurrently."

    Why there is no limit to the reading threads?