How does ConcurrentHashMap work when read and write request come for the same segment?

user_12705919 0
Viewed 119

I am trying to understand how locks work in ConcurrentHashMap. My understanding is that in ConcurrentHashMap there are segments and a write requests acquires a lock on a particular segment while there can be simultaneous reads on other segments. But say,

  1. A read request comes in for segment 10, and a write request comes in for the same segment 10. While a request is reading, a write request tries to modify it. How does the write request know it has to wait until a read is finished? Are there two separate locks one for read and one write lock in ConcurrentHashMap or just one lock? Does write have to acquire a read lock too for writing and that's the reason why write waits? If there is only one lock how does simultaneous read work?

  2. Two requests 1 and 2 come in for the same segment 2. Request 1 acquires the lock on segment 1, does the request have to wait until 2 has finished reading?

concurrenthashmap java
1 Answers

The best way to understand ConcurrentHashMap, is by understanding synchronization in java in reviewing the source code. From the Source code http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/concurrent/ConcurrentHashMap.java

Insertion (via +[]=+ or its variants) of the first node in an empty bin is performed by just CASing it to the bin. This is by far the most common case for put operations under most key/hash distributions. Other update operations (insert, delete, and replace) require locks. We do not want to waste the space required to associate a distinct lock object with each bin, so instead use the first node of a bin list itself as a lock. Blocking support for these locks relies +Util::CheapLockable. However, we also need a try_lock construction, so we overlay these by using bits of the Node hash field for lock control (see above), and so normally use builtin monitors only for blocking and signalling using cheap_wait/cheap_broadcast constructions. See +Node#try_await_lock+. Locking support for these locks relies on builtin "synchronized" monitors. which mean

Which basically means every Insert/Update/Delete operation on ConcurrentHashMap will blocked until the operation is finished

for read value there is no blocking

public V get(Object key) {

        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;

        int h = spread(key.hashCode());

        if ((tab = table) != null && (n = tab.length) > 0 &&

            (e = tabAt(tab, (n - 1) & h)) != null) {

            if ((eh = e.hash) == h) {

                if ((ek = e.key) == key || (ek != null && key.equals(ek)))

                    return e.val;

            }

            else if (eh < 0)

                return (p = e.find(h, key)) != null ? p.val : null;

            while ((e = e.next) != null) {

                if (e.hash == h &&

                    ((ek = e.key) == key || (ek != null && key.equals(ek))))

                    return e.val;

            }

        }

        return null;
    }
user_36424100
Related