ConcurrentHashMap은 어떤식으로 되어있기에 동시성을 보장하면서 적당히 성능도 최적화 되어있는거야?

[ljh468]

Q1. ConcurrentHashMap은 어떤식으로 되어있기에 동시성을 보장하면서 적당히 성능도 최적화 되어있는거야?

1. 버킷(Bucket) 단위의 세밀한 잠금 (Fine-grained Locking)

HashMap은 내부적으로 배열(버킷)을 사용함. ConcurrentHashMap은 데이터를 조작할 때 맵 전체를 잠그는 대신, 해당 데이터가 들어있는 **버킷의 첫 번째 노드(Node)**만을 잠그는 방식임

• 동시성 확보: 서로 다른 버킷에 접근하는 스레드들은 잠금 경쟁 없이 동시에 작업을 수행할 수 있음
• 성능 최적화: 특정 데이터가 속한 줄(Linked List 또는 Tree)에만 락을 걸기 때문에 병렬성이 좋음

---

2. CAS(Compare-And-Swap) 알고리즘 활용

모든 작업에 synchronized 키워드를 사용하지 않음. 새로운 노드를 삽입할 때, 해당 버킷이 비어 있다면 Lock 없이 CAS 알고리즘을 사용하여 안전하게 노드를 추가함

• 작동 방식: "현재 메모리의 값이 내가 예상한 값과 같다면 새로운 값으로 교체하라"는 하드웨어 수준의 명령을 사용함
  • compareAndSet(expectedValue, newValue);
  • 락을 거는 오버헤드가 전혀 없으므로 빈 버킷에 데이터를 넣는 속도가 매우 빠름

---

3. 읽기 작업에서의 Non-blocking (Lock-free)

get() 메서드와 같은 읽기 작업은 락을 전혀 사용하지 않음.

• Volatile 키워드: 내부 노드의 가치(val)와 다음 노드 포인터(next)에 volatile 키워드를 사용하여, 한 스레드가 변경한 내용이 즉시 다른 스레드에게 보이도록(Visibility) 보장함
• 읽기 작업이 많은 대부분의 애플리케이션 환경에서 유의미한 성능 향상을 가져올 수 있음

---

4. 데이터 구조의 진화 (Bin/Bucket 구조)

Java 8부터는 성능을 더 높이기 위해 데이터 양에 따라 버킷 내부 구조를 유연하게 바꿨다고 함=

1. Linked List: 데이터가 적을 때는 일반적인 연결 리스트를 사용
2. Red-Black Tree: 하나의 버킷에 데이터가 일정 개수(8개) 이상 쌓이면 리스트를 균형 이진 탐색 트리로 변환함

• 이를 통해 최악의 경우에도 탐색 시간 복잡도를 $O(n)$에서 $O(\log n)$을 유지함

---

정리: 왜 빠른가?

특징	설명
잠금 범위	맵 전체가 아닌 노드(버킷) 단위로 최소화
락 기법	무거운 synchronized 대신 가벼운 CAS 우선 사용
읽기 성능	volatile을 이용해 락 없이(Lock-free) 데이터 읽기
구조 최적화	데이터가 많아지면 Tree 구조로 전환하여 탐색 가속

ConcurrentHashMap은 "안전하게 공유하면서도 최대한 서로 방해하지 않게" 설계된 아주 복잡한 구조라고 이해하면 됨 -> 우리는 구현된 것을 필요에 맞게 잘 사용하기만 하면 됨

---

핵심 알고리즘 코드 참고

빈 버킷인 경우: CAS 활용 (Lock-free)

final V putVal(K key, V value, boolean onlyIfAbsent) {
    int hash = spread(key.hashCode());
    // ... 생략 ...
    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) {
            // [핵심] 버킷이 비어있으면 CAS로 삽입 시도 (Lock 없음)
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break; 
        }
        // ...
    }
}

충돌이 발생한 경우: 세밀한 잠금 (Synchronized)

else {
            V oldVal = null;
            // [핵심] 해당 버킷의 첫 번째 노드(f)에만 락을 건다.
            synchronized (f) {
                if (tabAt(tab, i) == f) { // 락 획득 후 상태 재확인
                    if (fh >= 0) { // 연결 리스트인 경우
                        // 리스트를 순회하며 노드 추가/수정
                    }
                    else if (f instanceof TreeBin) { // 트리인 경우
                        // 트리 노드 추가/수정
                    }
                }
            }
            // ... 데이터 개수에 따라 Tree로 변환하는 로직 포함
        }

데이터 일관성: volatile

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;                      // volatile: 쓰기 즉시 다른 스레드에 가시성 보장
    volatile Node<K,V> next;   // volatile: 다음 노드 추가 시 즉시 가시성 보장
    // ...
}