Thursday, 22 March 2018

Lock Striping in Java Concurrency

If 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 thread contention won't happen 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.

Lock Striping in Java

If you have to look for an example of lock striping in Java then it has to be a ConcurrentHashMap.

By default ConcurrentHashMap in Java 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 Java ConcurrentHashMap
Lock Striping in ConcurrentHashMap

Drawback of lock striping

One of the downside of lock striping 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. Difference between HashMap and ConcurrentHashMap in Java
  2. CopyOnWriteArrayList in Java
  3. CountDownLatch in Java concurrency
  4. Synchronization in Java multithreading
  5. ReentrantReadWriteLock in Java

You may also like -

5 comments:

  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?

    ReplyDelete
  2. Because the reading thread gets the latest copy/snapshot of underlying collection. They never get the direct access to the items in collection. This is similar to copyonwritearraylist

    ReplyDelete
    Replies
    1. Yes what you wrote is true for CopyOnWriteArrayList but lock striping is more about having separate thread for separate buckets to improve concurrency and ConcurrentHashMap is a better example of lock striping.

      Delete
  3. Why os it difficult and costly? "...of the downside of lock striping 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

    ReplyDelete
    Replies
    1. It will be more difficult right? If you want to lock the collection, where lock striping is used, for exclusive access then you will have to ensure that you get hold of all the locks. For example ConcurrentHashMap where you have 16 locks by default and each lock is used to lock portion of the bucket. Now if you want to lock the ConcurrentHashMap exclusively that means you will have to get hold of all the 16 locks at the same time which is difficult and time consuming process.

      Delete