[JAVA] Concurrent Collections - ConcurrentHashMap()

 

 

ConcurrentHashMap을 알기전에 Thred Safty 알아보기!

 

 

Thread safty 하다?

Thread safty (스레드 안전) 은 멀테 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없음을 뜻한다. 보다 엄밀하게는 하나의 함수가 한 스레드로부터 호출되어 실행 중일때, 다른 스레드가 그 함수를 호출하여 동시에 함께 실행되더라도 각 스레드에서 함수의 수행결과가 올바르게 나오는 것으로 정의한다. 

 

thread safty 하게  스레드를 구현하는 방법은 아래와 같다. 

 

1. Re-entrancy : 어떤 함수가 한 스레드에 의해 호출되어 실행 중일때, 다른 스레드가 그 함수를 호출하더라도 그 결과가 각각에게 올바르 주어져야 한다. 

ex) 각 스레드의 독립적 수행

 

2. Mutual exclusion : 공유 자원을 꼭 사용해야 할 경우 해당 자원의 접근을 세마포어 등의 락으로 통제한다

ex) Python의 threading.lock, Java의 synchronized 

 

3. Thread-local storage : 공유 자원이 사용을 최대한 줄여 각각의 스레드에서만 접근 가능한 저장소들을 사용함으로써 동시 접근을 막는다.

ex) 동시 접근, 전역 변수 자제

 

4. Atomic operations : 공유 자원에 접근할 때 원자 연산을 이용하거나 '원자적'으로 정의된 접근 방법을 사용함으로써 상호 배제를 구현할 수 있다. 

ex) '원자적' 접근, a += b의 경우, 먼저 +연산을 한 뒤에 =연산을 하므로, 원자적이라고 보기 어렵다.

 

 

 

  이런 동시성 제어를 위해 존재 하는 패키지가 Concurrent 인데  ConcurrentHashMap 을 포함하고 있다. 

 

concurrent?

- java.util.concurrent 패키지

- Java 1.5 API Docs

java.util.concurrent (Java 2 Platform SE 5.0)

 

 

 

그렇다면,

HashMap 과 비슷한 다른 Map과의 차이점은 무엇일까? thread safty 관점에서 확인해 보자.

 

 

HashMap vs SynchronizedMap vc ConcurrentHashMap

 

 

 

1) Thread safty 하지 않다. 

- HashMap : 여러 스레드의 접근이 가능하며 하나의 null key, 여러 null values 를 가질 수 있다 

 

2) Thread safty 하지만 성능이 좋지 않다.

- HashTable (Legacy Class in Java) : 동기화된 구조, 즉 잠금을 제공한다. 스레드 1이 접근하고 실행이 종료되면 스레드 2가 값을 가져와 실행될 수 있다. 스레드가 안전하지만 대기 현상으로 느린 성능을 가질 수 있다. 

- SynchronizedMap : 동기화된 구조, null key, null values 가 제공되며 전체 객체 수준에서 스레드가 동작한다.

 여러 쓰레드의 대기현상으로 성능 저하가 발생한다.  

 

3) Thread safty 하고 성능이 좋다.

- CocurrentHashMap : JDK 1.5 이후 동시성 성능을 높이기 위해 나온 클래스,

  읽기 작업에는 여러 쓰레드가 동시에 읽을 수 있지만 쓰기 작업에는 특정 세그먼트 or 버킷에 대한 Lock 을 사용한다.  

 

 

 

 

 

 SynchronizedMap과 ConcurrntHashMap의 성능 테스트

 

@Benchmark
public void randomReadAndWriteSynchronizedMap() {
    Map<String, Integer> map = Collections.synchronizedMap(new HashMap<String, Integer>());
    performReadAndWriteTest(map);
}

@Benchmark
public void randomReadAndWriteConcurrentHashMap() {
    Map<String, Integer> map = new ConcurrentHashMap<>();
    performReadAndWriteTest(map);
}

private void performReadAndWriteTest(final Map<String, Integer> map) {
    for (int i = 0; i < TEST_NO_ITEMS; i++) {
        Integer randNumber = (int) Math.ceil(Math.random() * TEST_NO_ITEMS);
        map.get(String.valueOf(randNumber));
        map.put(String.valueOf(randNumber), randNumber);
    }
}

Benchmark                                                     Mode  Cnt        Score        Error  Units
MapPerformanceComparison.randomReadAndWriteConcurrentHashMap  avgt  100  3061555.822 ±  84058.268  ns/op
MapPerformanceComparison.randomReadAndWriteSynchronizedMap    avgt  100  3234465.857 ±  60884.889  ns/op
MapPerformanceComparison.randomReadConcurrentHashMap          avgt  100  2728614.243 ± 148477.676  ns/op
MapPerformanceComparison.randomReadSynchronizedMap            avgt  100  3471147.160 ± 174361.431  ns/op
MapPerformanceComparison.randomWriteConcurrentHashMap         avgt  100  3081447.009 ±  69533.465  ns/op
MapPerformanceComparison.randomWriteSynchronizedMap           avgt  100  3385768.422 ± 141412.744  ns/op

 

 

 ConcurrentHashMap이 SynchronizedMap보다도 성능이 좋다는것을 확인 할 수 있다. 

 

 

 

 

ConcurrentHashMap.put()  vs SyncronizedMap.put() 의 동기화 부분을 살펴보자

 

 1.  ConcurrentHashMap.put() 내부의 putVal() 

 

 f 가 비어있지 않은경우, 서로 다른 스레드가 같은 해시 버킷에 접근 할때만 해당 블록이 잠기게 된다. 

 

 

 

 2. ConcurrentHashMap.get()

 

반대로 ConcurrentHashMap.get() 에는 동기화 부분을 확인할 수 없다.  

 

 

 

3. SyncronizedMap.put()

 

 

<정리 >

-  SyncronizedMap 의 경우 put 메서드 자체에 synchronized 키워드가 존재한다.

-  ConcurrentHashMap의 경우 메서드 중간에 synchronized 키워드가 존재하는 것을 확인 할 수  있다.

-  ConcurrentHashMap 의 경우 get() 에서는 synchronized 가 존재 하지 않는다. 

 

 

ConcurrentHashMap .Put() 내부의 CAS(Compare and Swap) 알고리즘이 있다.

* Compare and Swap 은 원자성을 보장하는 동시성 제어 알고리즘이다. 자세한 내용은 이전 게시물 참고 

 

https://truehong.tistory.com/71

[JAVA] AtomicInteger, 쓰레드 동기화(synchronization) , Atomic, CAS 알고리즘 이해하기

 

ConcurrentHashMap.put() 코드를 보자.

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;
            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, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            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, null);
                                    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;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

 

ConcurrentHashMap.put() 코드를 더 자세히 보자.

- Map 에서 데이터(해시값)를 담는 가변 배열 변수 table 을 가져온다.

- 만약 해당 인덱스의 해시 버킷이 null 값이라면 castTabAt()를 통해서 Node를 생성하도록 한다. 

 

- castTabAt() 함수를 살펴보면 return 값에 CAS 함수가 구현되어 원자성(Atomic) 이 보장되고 기대되는 값과 비교     (Compare) 하여 새로운 노드를 넣도록 한다. 

- 이 모습을 보면 해당 버킷의 접근에 대해서 Synchronized 와 CAS가 적용 되어있다고 볼수 있다. 

- 버킷의 수 = 동시 작업 가능한 스레드 수 라고 생각 할 수 있다. 

- 같은 버킷이 아니라면 스레드의 대기가 발생하지 않는다. 

 

 

 

언제 사용 하는지? 

데이터 일관성이 중요한 경우 Collections.synchronizedMap()

읽기 작업보다 쓰기 작업이 훨씬 많으며 성능이 중요한 Application의 경우 ConcurrentHashMap()

 

 

 

 

 

 

 

 

 

참고 : 

https://pplenty.tistory.com/17

https://www.baeldung.com/java-synchronizedmap-vs-concurrenthashmap

https://madplay.github.io/post/java-collection-synchronize

https://www.youtube.com/watch?v=UwurUtvil7w

https://recordsoflife.tistory.com/686?category=875834

https://www.youtube.com/watch?v=2Bvz_jsQPHk 

https://ko.wikipedia.org/wiki/%EC%8A%A4%EB%A0%88%EB%93%9C_%EC%95%88%EC%A0%84

https://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html