[Java] ConcurrentHashMap은 왜 빠를까?

들어가며

HashMap 대신 ConcurrentHashMap을 사용해라

Spring 개발을 해왔다면 흔히 듣는 말이다.

왜 이런 말이 나오게 되었는지 ConcurentHashMap의 소스코드를 까(?)보면서 알아보자

HashMap과 Synchronized

HashMap은 싱글 스레드 환경에서 빠르게 동작한다.

HashMap은 기본으로 싱글 스레드 환경에서 사용하기 위해 설계되었다.

동시성을 보장하지 않기 때문에 2개 이상의 스레드가 동시에 실행됐을 때 결과값을 예측할 수 없다.

동시성을 보장하기 위해, HashMap과 Synchronized를 함께 사용할 수 있다.

하지만 락의 범위가 크고, 모든 스레드를 직렬화하기 때문에 성능은 좋지 않다.

예시) 문제가 발생하는 코드

아래 코드를 실행하면 2000을 기대하지만, 실제로는 더 작은 값이 출력된다.

Map<BadKey, Integer> map = new HashMap<>();

Runnable task = () -> {
    for (int i = 0; i < 1_000; i++) {
        map.put(new BadKey(), i);
    }
};

Thread t1 = new Thread(task);
Thread t2 = new Thread(task);

t1.start();
t2.start();

t1.join();
t2.join();

System.out.println(map.size());

ConcurrentHashMap과 CAS

ConcurrentHashMap은 CAS, bin-level lock을 통해 동시성을 보장한다.

ConcurrentHashMap은 멀티 스레드 환경에서 사용하기 위해 설계되었다.

대부분의 멀티 스레드 환경에 적합하며, 동시성을 보장할 수 있다.

어떻게 성능과 동시성을 동시에 챙길 수 있었을까?

그것은 바로, CAS(Compare And Swap)와 bin-level lock 기반 설계 때문이다.

ConcurrentHashMap은 CAS를 짧은 상태 전이에만 사용하고, 구조 변경은 bin-level lock으로 처리해 성능을 올렸다.

이때 bin은 내부 해시 테이블(table)에서 하나의 버킷(bucket)을 의미한다.

(CAS가 무엇인지는 코드를 통해 자세히 살펴보도록 하자)

ConcurrentHashMap의 동작

ConcurrentHashMap의 동작은 조회할 때와 갱신(수정)할 때로 나뉜다.

조회 시
1. 별도의 락을 걸지 않는다.
2. 그 시점에 변경이 완료된 값이라면 변경된 값으로 조회할 수 있다.
3. 가시성 보장: volatile 또는 CAS를 통해 갱신함으로써, 갱신 값이 다른 스레드에도 즉시 가시적으로 보장된다.
갱신(수정) 시
1. CAS: 특정 위치의 값이 내가 예상한 값과 같을 때만 변경한다. (Atomic 하게 동작)
2. Bin-level lock: 전체 연산에 lock을 걸지 않고, 링크 재배열 같은 동시성 문제가 발생할 가능성이 있는 구간에만 synchronized를 통해 lock을 건다.

실제로 putVal (갱신) 코드를 살펴보면,

루프를 돌면서 조건을 확인한다. (guard 역할)

tab 비어있으면 초기화한다.
만약 넣고자 하는 bin이 비어 있으면, CAS를 통해 첫 노드를 삽입하고 break
bin이 리사이징 중(MOVED 상태)이면, 새 테이블로 이동(helpTransfer)
bin의 첫 노드가 동일한 key이고 이미 값이 존재하면 락 없이 기존 값을 바로 반환
아니면 else 문 실행 (리스트 or 트리 재배열)

 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;                   
    }
    else if ((fh = f.hash) == MOVED)
        tab = helpTransfer(tab, f);
    else if (onlyIfAbsent 
             && fh == hash
             && ((fk = f.key) == key || (fk != null && key.equals(fk)))
             && (fv = f.val) != null)
        return fv;
    else { // 아래 코드로 이어집니다. 
    ...
  }

bin-level lock (synchronized)

새로운 값 삽입/수정 등 리스트(트리) 변경이 필요할 때 동작하는 코드다.
bin 첫 노드(Head)를 lock으로 걸고 변경한다.
binCount가 TREEIFY_THRESHOLD 이상이면 TreeBin 전환을 시도한다.
- +) 노드 수가 임계값 이상이면 TreeBin으로 전환을 시도하지만,
  테이블 크기가 크지 않으면 트리화 대신 리사이즈가 우선된다.

synchronized (f) {
    if (tabAt(tab, i) == f) {
        ... 변경 코드들 
        }
        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;
    }
}

CAS의 단점은 없을까?

SPIN 문제: 코드에서 봤듯이, 조건 실패 시 반복문 계속 돌아야 한다.
ABA 문제: 값이 A→B→A로 바뀌면 중간의 바뀐 값은 추적하지 못한다.

ConcurrentHashMap에서도 ABA 문제가 발생할까?

ConcurrentHashMap의 현재 설계에서는 ABA 문제가 의미 있는 버그로 이어지지 않는다

casTabAt(tab, i, null, new Node<K,V>(hash, key, value))

빈 버킷이면 null
누가 먼저 넣었다면 null이 아님 → 실패
중간의 변경 이력은 중요하지 않다.

따라서 A → B → A 여도, 다시 A면 정말로 A인 게 맞다.

마무리

코드를 보기 전에는 CAS 개념이 추상적으로 다가왔지만 코드를 깊게 파보면서 ConcurrentHashMap의 장점을 이해할 수 있었다.

volatile, ReentrantLock, final 클래스 등 더 깊게 파보고 싶은 개념도 알게 되었다.

다음에 이런 주제에 대해서도 블로그 글을 써보려고 한다.

Ref

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html

https://blog.hexabrain.net/403

https://curiousjinan.tistory.com/entry/java-concurrent-hash-map-cas

+ AI 조금

*잘못된 내용은 댓글로 알려주시면 글에 반영하도록 하겠습니다. 감사합니다.

저작자표시 비영리 변경금지 (새창열림)

프로미의 0 to 1

[Java] ConcurrentHashMap은 왜 빠를까? – CAS와 bin-level lock