[Java] java.util.concurrent.ConcurrentHashMap

in Study on Java

java.util.concurrent.ConcurrentHashMap 정리

ConcurrentHashMap?

  • 1.5 버전부터 동시성 지원을 위해 도입된 패키지 java.util.concurrent 하위에 존재하는 자료 구조.
  • HashMap 의 경우 Thread-safe 하지 못함. 이러한 단점을 보완한 것이 ConcurrentHashMap.
  • 조회할 때 lock이 수반되지 않음. Thread-safe but, 동기화에 있어서는 safe하지 못함.
  • HashMap과는 다르게 key, value에 null을 허용하지 않음.

HashTable, HashMap, ConcurrentHashMap

  • 10개의 쓰레드가 반복문을 1000번 돌면서 HashTable, HashMap, Sychronized 처리된 HashMap, sychronizedMap, ConcureentHashMap 각각에 Key, Value를 넣었을 때의 결과 테스트 코드
  • 결과
    • HashMap은 동기화 처리가 되지 않을 경우 비정상적으로 작동하는 것을 알 수 있음.
    • synchronized와 같은 동기화 처리를 할 경우 HashMap도 정상 동작하는 것을 알 수 있음. 하지만, 성능상의 문제로 비권장.
@Test
public void put_test() {

    final int MAX_THREADS = 10;

    Hashtable<String, Integer> ht = new Hashtable<>();
    HashMap<String, Integer> hm = new HashMap<>();
    HashMap<String, Integer> hmSyn = new HashMap<>();
    Map<String, Integer> synm = Collections.synchronizedMap(new HashMap<String, Integer>());
    ConcurrentHashMap<String, Integer> chm = new ConcurrentHashMap<>();

    ExecutorService es = Executors.newFixedThreadPool(MAX_THREADS);

    for (int j = 0; j < MAX_THREADS; j++) {
        es.execute(() -> {
                for (int i = 0; i < 1000; i++) {
                    String key = String.valueOf(i);

                    ht.put(key, i);
                    hm.put(key, i);
                    chm.put(key, i);
                    synm.put(key, i);
                    synchronized (hmSyn) {
                        hmSyn.put(key, i);
                    }
                }
            }
        );
    }

    es.shutdown();
    try {
        es.awaitTermination(Long.MAX_VALUE, TimeUnit.SECONDS);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }

    assertThat(ht.size()).isEqualTo(1000);
    assertThat(hm.size()).isGreaterThan(1000);
    assertThat(hmSyn.size()).isEqualTo(1000);
    assertThat(synm.size()).isEqualTo(1000);
    assertThat(chm.size()).isEqualTo(1000);
}

ConcurrentHashMap vs Collections.synchronizedMap()

차이점

Collections.synchronizedMap()

  • Collections 유틸 클래스는 컬렉션들에 대해 다양한 알고리즘을 제공하고 래핑한 컬렉션을 반환한다.
  • synchronizedMap() 메소드는 Thread-safe 기능을 제공한다.
  • 매개변수를 통해 전해 받은 Map에 대해 동기화된 Map을 반환함.
  • thread-safe를 위해 동기화된 Map을 통해 내부의 Map에 대한 접근을 허용한다.

ConcurrentHashMap

  • 변경뿐만 아니라 조회를 위해 동시성을 제공하는 개선된 HashMap.
  • JDK 1.5에 도입
  • thread-safe
  • 읽기 활동은 non-blocking. 반면에 쓰기 활동은 특정 세그먼트 혹은 버킷에 대해 lock을 건다.
  • default 버킷또는 동시성 레벨은 16. 16개의 쓰레드가 세그먼트 또는 버킷을 잠근 후 write를 수행할 수 있음을 의미.

차이점1. ConcurrentModificationException

  • sychronizedMap() : 동시 작업 수행 허용 ❌
  • ConcurrentHashMap : 동시 작업 허용 ⭕️

차이점2. Null 지원

  • sychronizedMap() : null 허용 ⭕️
  • ConcurrentHashMap : key, value에 null 허용 ❌

차이점3. 성능비교

  • 10개 쓰레드, 1000개의 사이즈
@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이 더 우위에 있음. 따라서 Syschronized HashMap < Collections.sychronizedMap < ConcurrentHashMap 순으로 성능이 좋음을 알 수 있다.

결론

데이터 일관성이 중요한 경우 : Collections.synchronizedMap()
읽기 작업보다 쓰기 작업이 훨씬 더 많은, 성능이 중요한 경우 : ConcurrentHashMap

Collections.sychronizedMap() 은 각 쓰레드가 읽기/쓰기 작업 모두에 대해 전체 개체에 대한 잠금을 획득.
ConcurrentHashMap 은 쓰레드가 개별 세그먼트에 대한 잠금을 획득하고, 동시에 수정 가능

ConcurrentHashMap 동기화 처리 방식

  1. 빈 해시 버킷에 노드를 삽입하는 경우 lock 사용 ❌, Compare and Swap을 사용해 새로운 노드를 해시 버킷에 삽입 (원자성 보장)
  2. 이미 노드가 존재하는 경우 synchronized 를 이용해 하나의 스레드만 접근할 수 있도록 제어. 서로 다른 스레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 됨.

빈 버킷으로의 노드 삽입은 lock 을 사용하지 않고 단순히 CAS 만을 이용해 삽입한다. 그 외의 업데이트(삽입, 삭제 및 교체)는 lock(synchronized) 을 이용하지만 각 버킷의 첫 번째 노드를 기준으로 부분적인 잠금을 획득하여 스레드 경합을 최소화 하고 안전한 업데이트를 한다.

Reference