[Java] ConcurrentHashMap

ConcurrentHashMap의 내부구조

 

 

ConcurrentHashMap이란?

ConcurrentHashMap은 Java 1.5 버전에서 HashTable의 대안으로 소개 되었다. Java 1.5 버전 이전에는 concurrent하고 multi-threaded 를 고려한 map을 구현하려면 HashTable 또는 synchronized map을 사용해야 했다. 왜냐하면 HashMap은 thread-safe 하지 않았기 때문이다.

 

ConcurrentHashMap은 concurrent multi-threaded 환경에서 안정적으로 동작하고 HashTable과 synchronized map 보다 더 나은 성능을 가지고 있다. 그 이유는, ConcurrentHashMap은 map의 일부에만 lock을 거는데 반해, 앞의 두 가지는 map 전체에 lock을 걸기 때문이다. map 전체에 lock을 거는 것은 성능 오버헤드를 발생시킨다. 하나의 쓰레드가 락을 유지하는 동안, 다른 모든 쓰레드는 컬렉션을 사용할 수 없다.

 

oracle docs에 따르면,

검색의 전체 동시성과 업데이트에 대한 높은 기대 동시성을 지원하는 해시 테이블입니다. 이 클래스는 Hashtable과 동일한 기능 사양을 준수하며, 각 Hashtable 방법에 해당하는 메소드 버전을 포함한다. 그러나 모든 작업이 스레드 안전함에도 불구하고 검색 작업은 잠금을 수반하지 않으며 모든 액세스를 방지하는 방식으로 전체 테이블을 잠글 수 있는 어떠한 지원도 없습니다. 이 클래스는 동기화 세부 정보가 아닌 스레드 안전성에 의존하는 프로그램에서 해시 테이블과 완전히 상호 운용 가능합니다.

 

ConcurrentHashMap putVall 메소드를 보면

public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh; K fk; V fv;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else if (onlyIfAbsent // check first node without acquiring lock
                     && fh == hash
                     && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                     && (fv = f.val) != null)
                return fv;
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key, value);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

ConcurrentHashMap은 Hashtable과는 다르게 put() 메서드에  synchronized 키워드가 붙어있지 않다. 위의 코드에서 중간쯤을 보면 동일 Entry(아래 코드에서는 Node)에 추가 될 경우 해당 Entry에 대해서 synchronized를 적용한 것을 확인할 수 있다. 즉, Entry 배열 아이템 별로 동기화 처리를 하고 있는 것이다. 이런 방식은 MultiThread 환경에서 성능을 크게 향상시킨다. 

 

ConcurrentHashMap concurrencyLevel, loadFactor

 

 

기본값으로는 Capacity 는 16, MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8, loadFactor는 0.75, concurrencyLevel은 16으로 정해져 있다. 또 ConcurrentHashMap은 키 값에 null을 허용하지 않는다.

 

여기서 concurrencyLevel = 16을 주의깊게 보자.

ConcurrentHashMap은 기본적으로 16개의 세그먼트로 나뉘어져 있고, 각 세그먼트별로 다른 lock으로 동기화 되도록 만들었다. 세밀한 locking 방법을 적용시켜 오버헤드를 줄였다

 

ConcurrentHashMap의 내부구조를 깠을때, 4번째 생성자는 아래와 같다. concurrencyLevel을 이용하여 세그먼트 갯수를 정할 수 있다. 여기서 세그먼트 갯수는 분리된 세그먼트당 락을 갖도록 하기 때문데 멀티 쓰레드에서 전체적링 락킹 방법보다 훨씬 효율적이고 뛰어난 성능을 보여준다.

 

 

 

loadFactor

HashMap 에서는 loadFactor따라서 table 이 resize 되는 시점이 결정되지만, ConcurrentHashMap 에서는 이 인자 값과 상관 없이 0.75f로 동작한다. 예를 들어, 초기 테이블 크기가 16 이면 entry 수가 12개가 될 때 해시테이블 사이즈를 16에서 32로 증가시킨다.

 

ConcurrentHashMap의 리사이징

 

 

HashMap 에서의 리사이징은 단순히 resize() 함수를 통해 새로운 배열(newTab)을 만들어 copy 하는 방식이였지만,
ConcurrentHashMap 에서는 기존 배열(table)에 새로운 배열(nextTable) 로 버킷을 하나씩 전송(transfer) 한다. 이 과정에서 다른 스레드가 버킷 전송에 참여할 수도 있다. 전송이 모두 끝나면 크기가 2배인 nextTable 이 새로운 배열이 된다.
변수 sizeCtl 과 resizeStamp 메서드를 통해 resizing 과정이 중복으로 일어나지 않도록 방지한다.

 

 

정리 

MultiThread 환경에서 동기화 처리가 필요하다면 ConcurrentHashMap을 사용하는 것이 안정적이다. 동기화가 필요하지 않은 경우라면 그냥 HashMap을 사용하자. Hashtable은 Thread-Safe 하긴 하나 느리다는 단점이 있다.