Need simple explanation how "lock striping" works with ConcurrentHashMap

Question

According to Java Concurrency in Practice, chapter 11.4.3 says:

Lock splitting can sometimes be extended to partition locking on a variablesized set of independent objects, in which case it is called lock striping. For example, the implementation of ConcurrentHashMap uses an array of 16 locks, each of which guards 1/16 of the hash buckets; bucket N is guarded by lock N mod 16.

I still have problems to understand and visualize the lock striping and buckets mechanism. Can someone explain this with good understanding words :)

Thanks in advance.

Solution 1

The hash map is built on an array, where the hash function maps an object to an element in the underlying array. Let's say the underlying array has 1024 elements - ConcurrentHashMap actually turns this into 16 different sub-arrays of 64 elements, e.g. {0, 63}, {64, 127}, etc. Each sub-array has its own lock, so modifying the {0, 63} sub-array doesn't impact the {64, 127} sub-array - one thread can write to the first sub-array while another thread writes to the second sub-array.

Solution 2

The difference between locking in a Collections.synchronizedMap() and a ConcurrentHashMap is as follows:

If multiple threads will access a Collections.synchronizedMap() frequently, there will be a lot of contention since each method is synchronized using a shared lock (i.e. if thread X calls a method on a Collections.synchronizedMap(), all other threads will be blocked from calling any method on a Collections.synchronizedMap() until thread X returns from the method it called).

A ConcurrentHashMap has a variable number of locks (default is 16) that each guard a segment of the keys in the ConcurrentHashMap. So for a ConcurrentHashMap with 160 keys, each lock will guard 10 elements. Therefore, methods operating on a key (get, put, set, etc...) only lock out access to other methods operating on a key where the keys are in the same segment. For example, if thread X calls put(0, someObject), and then thread Y calls put(10, someOtherObject) those calls can execute concurrently, and thread Y does not have to wait for thread X to return from put(0, someObject). An example is provided below.

Additionally, certain methods such as size() and isEmpty() are not guarded at all. While this allows for greater concurrency, it means they are not strongly-consistent (they won't reflect state that is concurrently changing).

public static void main(String[] args) {
  ConcurrentHashMap<Integer, Object> map = new ConcurrentHashMap<>(160);

  new Thread(new Runnable() {
    @Override
    public void run() {
      map.put(0, "guarded by one lock");
    }
  }.start();

  new Thread(new Runnable() {
    @Override
    public void run() {
      map.put(10, "guarded by another lock");
    }
  }.start();

  new Thread(new Runnable() {
    @Override
    public void run() {
      // could print 0, 1, or 2
      System.out.println(map.count());
    }
  }.start();
}

Solution 3

The key concept here is the "bucket" . instead using a global lock for this whole hash Table, it uses one small lock for each bucket. It's also a good analogous to bucket sort which can improve sorting complexity.

Comments

[GedankenNebel]

Okay, I understand. But what about if two or more threads are trying to modify all in sub-array {0,63}?

[Zim-Zam O'Pootertoot]

Then it's first come first served - the first thread to acquire the lock makes its changes, then when it finishes the second thread makes its changes. ConcurrentHashMap has methods like replace to ensure that the second thread doesn't inadvertently overwrite the first thread's changes.

[Marcelo]

I don't think it's actually "first come first served," as I understand (I don't have the exact quote, but I learned it from Java Concurrency in Practice,) fairness is only guaranteed when it's explicit, like in constructors for the different explicit Lock implementations, such as ReentrantLock, or the Queues such as ArrayBlockingQueue. (I know it's an old thread, sorry)

[Big O]

HashMap in java is not thread safe, HashTable is. The first scenario you talk about is for HashTable

[Giri]

Had a very brief look at Java 8 implementation and I don't see any segment level arrays. I know that above answer is written before java 8. But can someone clarify now segments are nothing but individual buckets or row in the table ? Is the word lock striping obsolete since we don't do lock for stripe of rows ?