Search code examples
javamultithreadingconcurrenthashmap

Java 8+ ConcurrentHashMap lock striping

I have been reading through Concurency in Practice by Brian Goetz.

In the chapter about Lock Striping it is written that ConcurrentHashMap uses 16 buckets to improve multithreaded access by many threads :

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 have read those questions :

ConcurrentHashMap locking

Need simple explanation how “lock striping” works with ConcurrentHashMap

However those answers are valid for Java version <= 7.

For Java 8+ the behaviour seems to be changed significantly. For Java 8+ it seems that that the lock is acquired not for a Segment but for particular Node in table (transient volatile ConcurrentHashMap.Node<K, V>[] table;). For example for the putVal operation :

ConcurrentHashMap.Node var7;

.... ///retrive node for var7

synchronized(var7) {
....
}

And also from Java8 + field like DEFAULT_CONCURRENCY_LEVEL and class Segment seems to be unused in the implementation (it is only used in private method writeObject::ObjectOutputStream and this method is not invoked anywhere in ConcurrentHashMap implementation).

  1. What is the cause of such significant change in ConcurrentHashMap implementation?

  2. If class Segment is unused and also field like DEFAULT_CONCURRENCY_LEVEL is also unused - why not get rid of it from implementation - is it for some historical reasons?

  3. If we are not locking on segments, like it used to be for Java version < 7, is locking only on specific node sufficient? If yes - why? Does that mean that we do not need lock striping here?

Solution

  • What is the cause of such significant change in ConcurrentHashMap implementation?

    ConcurrentHashMap.java#l272:

    * The primary design goal of this hash table is to maintain
* concurrent readability (typically method get(), but also
* iterators and related methods) while minimizing update
* contention.

    Segment class remains unused because of compatibility reasons, ConcurrentHashMap.java#l481:

    * Maintaining API and serialization compatibility with previous
* versions of this class introduces several oddities. Mainly:
* [...]
* We also declare an unused "Segment" class that is
* instantiated in minimal form only when serializing.

    ... is locking only on specific node sufficient? If yes - why?

    ConcurrentHashMap.java#l320:

    * Using the first node of a list as a lock does not by itself
* suffice though: When a node is locked, any update must first
* validate that it is still the first node after locking it,
* and retry if not.