ConcurrentHashMap 깊숙히 파보기

ksngh·2024년 11월 29일
동시성자료구조자바
4

자료구조

목록 보기
1/1
post-thumbnail

Why, How ConcurrentHashMap?

백엔드 개발자라면 동시성 문제를 마주하게 되는 순간이 찾아옵니다. 이러한 문제를 해결하다 보면 자연스럽게 ConcurrentHashMap을 접하게 됩니다. 사용한 적이 없다해도, 들어본적은 있는 ConcurrentHashMap!! 단순히 이 자료구조를 사용하는 데 그치지 않고, 어떻게 동작하는지, 왜 효율적인지를 깊이 이해한 후 활용하고 싶었습니다.

목차는 다음과 같습니다!

  • HashMap은 무엇인가??
    ConcurrentHashMap을 알기 전에, HashMap은 그럼 어떻게 작용하는가를 알고 가야합니다.
  • 그래서 ConcurrentHashMap은 뭐가 다른가?
    먼저 알아본 HashMap에서, ConcurrentHashMap은 뭐가 달라졌는지를 비교해보고 확인하는 순서입니다.

1. HashMap은 어떻게 작용하는가?

1.1 HashMap의 기본 구조

HashMap은 배열 + 연결 리스트 + 트리 구조로 이루어져 있습니다.

  • 배열: 데이터를 저장할 버킷(bucket)을 관리.
    각 버킷은 특정 해시 값을 가진 데이터를 저장.
    배열의 크기(tableSize)는 해시 함수에 의해 데이터가 분산되도록 함.

  • 연결 리스트: 동일한 해시 값을 가진 데이터를 관리.
    충돌(collision)이 발생하면 연결 리스트에 데이터 추가.

  • 트리 구조:
    연결 리스트에 저장된 데이터가 많아지면 Red-Black Tree로 변환.
    탐색 성능이 O(log n)으로 향상.

1.2 트리 구조

  • 트리 구조는 부모-자식 관계로 이루어진 계층적 데이터 구조입니다.

  • HashMap과 ConcurrentHashMap에서는 Red-Black Tree를 사용:
    항상 균형을 유지하여 최악의 경우에도 O(log n)의 삽입, 삭제, 검색 성능을 보장. 노드 삽입/삭제 시 자동으로 균형을 맞춤.
    Java 8 이상에서는 버킷의 데이터 개수가 8개 이상일 때 Red-Black Tree로 전환.

1.3 버킷(Bucket)

  • 버킷은 동일한 해시 값을 가진 데이터가 저장되는 공간입니다.

  • 초기에는 비어 있다가 데이터가 추가되면 연결 리스트로 관리.

  • 해시 충돌이 많아져 데이터 개수가 8개 이상이 되면 트리 구조로 변환.

1.4 HashMap의 작동 방식

  • 해시 값 생성:
    키의 hashCode()를 호출해 32비트 정수 해시 값을 생성.

  • 버킷 인덱스 계산:
    (hashCode % tableSize)로 버킷 위치를 결정.
    실제로는 비스마스킹이나 등등을 이용해 더 많은 버킷 위치를 결정한다.

  • 버킷에 데이터 저장:
    충돌 발생 시 연결 리스트로 관리.
    데이터 개수가 많으면 Red-Black Tree로 전환.

  • 데이터 검색:
    버킷을 통해 데이터 접근.
    연결 리스트 순회 또는 트리 탐색을 통해 데이터 검색.

1.5 코드로 알아보기

아까 알아보았듯, 해시 맵은 배열구조 로 관리하고,
배열 안에는 노드 객체 또는 트리 노드 객체로 존재하는 것입니다.
다음은 코드로 확인해 보겠습니다.

  • 노드 객체
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;       // 키의 해시 값
    final K key;          // 키
    V value;              // 값
    Node<K, V> next;      // 다음 노드 (연결 리스트 형태로 연결)

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final String toString() {
        return key + "=" + value;
    }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
  • 트리 노드 객체
    TreeNode는 연결 리스트가 많아지면 Red-Black Tree로 변환되어 데이터를 관리합니다.
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
    TreeNode<K, V> parent;  // 부모 노드
    TreeNode<K, V> left;    // 왼쪽 자식
    TreeNode<K, V> right;   // 오른쪽 자식
    TreeNode<K, V> prev;    // 연결 리스트의 이전 노드
    boolean red;            // 노드 색상 (Red-Black Tree에서 사용)

    TreeNode(int hash, K key, V value, Node<K, V> next) {
        super(hash, key, value, next);
    }

    // 트리 변환 및 탐색 관련 메서드 포함
}
  • HashMap 내부 변수
transient Node<K, V>[] table; // 데이터를 저장하는 배열
transient int size;          // 현재 저장된 데이터의 개수
final float loadFactor;      // 로드 팩터 (배열 크기 확장 기준)
int threshold;               // 배열 크기 확장 임계치

로드 팩터(loadFactor): 배열이 얼마나 차면 크기를 확장할지를 결정하는 값으로, 기본값은 0.75입니다.
임계치(threshold): 배열 확장의 기준이 되는 데이터 개수로, capacity * loadFactor로 계산됩니다.

예: 초기 배열 크기 16, 로드 팩터 0.75라면 임계치는 16 * 0.75 = 12가 됩니다.

2. 그럼 ConcurrentHashMap은 뭐가 다를까??

2.1 HashMap과 ConcurrentHashMap의 차이


HashMap은 단일 스레드 환경에서 효율적으로 동작하지만, 멀티스레드 환경에서는 동시성 문제가 발생합니다. 반면, ConcurrentHashMap은 멀티스레드 환경에서도 안전하게 동작하도록 설계된 Map 자료구조입니다. 두 자료구조의 차이점을 비교해 보겠습니다.

특징HashMapConcurrentHashMap
스레드 안전성제공하지 않음제공 (락 분할과 CAS 사용)
락 사용 여부없음버킷 단위 락, CAS 활용
Null 허용 여부Null 키와 값 허용Null 키와 값 허용하지 않음
구조배열 + 연결 리스트 + 트리 구조배열 + 연결 리스트 + 트리 구조
성능단일 스레드 환경에서 빠름멀티스레드 환경에서 효율적

2.2 동시성을 보장할 수 있는 이유

ConcurrentHashMap은 volatile, CAS(Compare-And-Swap), 그리고 버킷 단위 락을 활용하여 동시성을 보장합니다. 각 기술의 동작 원리를 살펴보겠습니다.

2.2.1 volatile

volatile은 Java 메모리 모델에서 변수의 최신 값을 모든 스레드가 즉시 확인할 수 있도록 보장하는 키워드입니다.

  • 동작 원리:
    1. 한 스레드에서 volatile 변수의 값을 변경하면, 변경된 값이 CPU 캐시가 아닌 메인 메모리에 기록됩니다.
    2. 다른 스레드는 메모리 장벽(memory barrier) 덕분에 메인 메모리에서 값을 읽어오기 때문에, 변경 사항을 즉시 확인할 수 있습니다.
  • HashMap과의 차이:
    • HashMap은 멀티스레드 환경에서 데이터의 최신 상태를 보장하지 않아 동시성 문제가 발생합니다.
    • ConcurrentHashMap에서는 volatile로 선언된 변수(value, next) 덕분에 가시성을 보장하며, 읽기 작업에서 락 없이 최신 데이터를 확인할 수 있습니다.

예를 들어, Node 클래스의 주요 필드인 value와 next는 다음과 같이 volatile로 선언되어 있습니다:

static class Node<K, V> {
    final int hash;
    final K key;
    volatile V value; // 최신 값을 읽기 위해 volatile 선언
    volatile Node<K, V> next; // 연결된 다음 노드
}

2.3 CAS (Compare-And-Swap)

  • CAS는 락 없이 데이터를 원자적으로 변경하는 비차단 동시성 제어 기법입니다.

  • CAS 동작 원리:

    1. 현재 메모리의 값을 읽어옵니다.
    2. 기대한 값과 실제 값이 같다면, 새로운 값으로 교체합니다.
    3. 다른 스레드가 값을 변경해 기대한 값과 다르면, 작업을 재시도합니다.

  • ConcurrentHashMap에서 CAS 사용:

    • 데이터를 삽입하거나 변경할 때 CAS를 사용해 락 없이 안전하게 작업을 수행합니다.
    • 예를 들어, 빈 버킷에 새 데이터를 삽입할 때 CAS를 사용합니다.
static final boolean casTabAt(Node<K, V>[] tab, int i, Node<K, V> c, Node<K, V> v) {
    return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v);
}

2.4 버킷 단위 락

ConcurrentHashMap은 락을 전체 맵이 아닌 버킷(bucket) 단위로 적용합니다. 이를 통해 동시 접근 시에도 성능을 유지합니다.

  • 동작 원리:

    • 특정 버킷(혹은 노드)에 대해서만 락을 걸어 데이터 변경 작업을 수행합니다.
    • 나머지 버킷은 락이 걸리지 않아 다른 스레드가 자유롭게 접근할 수 있습니다.

  • 읽기 작업에 영향을 주지 않는 이유:

    • 읽기 작업은 락 없이 수행되며, 쓰기 작업 중에도 volatile로 선언된 최신 값을 읽을 수 있습니다.
    • 락은 쓰기 작업을 위해 해당 버킷에만 걸리므로, 다른 버킷의 데이터 읽기 작업은 계속해서 수행 가능합니다.

2.4.1 락 구현: synchronized와 ReentrantLock

  1. synchronized 블록:
    • 특정 버킷에 대한 락을 간단하게 구현.
    • 아래 예제는 특정 버킷(bin)에만 락을 걸어 데이터를 변경하는 방식입니다.
synchronized (bin) { 
    Node<K, V> p = table[index];
    // 데이터 추가 또는 수정 작업
}
  1. ReentrantLock:
    • ReentrantLock은 Lock 인터페이스의 구현체로, 더 세부적인 락 제어를 가능하게 합니다.
    • 락 해제, 대기 시간 설정 등 세밀한 동작이 가능합니다.
ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
    // 락이 걸린 상태에서 작업 수행
} finally {
    lock.unlock(); // 락 해제
}

2.5 ConcurrentHashMap의 상속 구조

3. 정리

3.1 HashMap과 ConcurrentHashMap의 차이점

특징HashMapConcurrentHashMap
스레드 안전성스레드 안전하지 않음스레드 안전 (멀티스레드 환경에서 사용 가능)
락 사용 여부락을 사용하지 않음버킷 단위로 락을 사용 (락 분할 + CAS)
Null 허용 여부Null 키와 Null 값 허용Null 키와 Null 값 허용하지 않음
구조배열 + 연결 리스트 + 트리 구조배열 + 연결 리스트 + 트리 구조
락의 범위락 없음버킷 단위 락으로 특정 버킷만 잠금
읽기 작업단일 스레드 환경에서 빠름락 없이 수행 (volatile로 가시성 보장)
쓰기 작업멀티스레드 환경에서 충돌 발생 가능CAS와 락 분할을 사용해 쓰기 작업을 안전하게 수행
성능단일 스레드 환경에서 빠름멀티스레드 환경에서 성능 최적화
해시 충돌 처리 방식연결 리스트 및 Red-Black Tree로 관리연결 리스트 및 Red-Black Tree로 관리
멀티스레드 환경멀티스레드 환경에서 동작 불안정멀티스레드 환경에서 안정적으로 동작

3.2 주요 차이점 설명

3.2.1 스레드 안전성

  • HashMap: 스레드 안전성을 제공하지 않으므로, 멀티스레드 환경에서 데이터 손상 및 충돌 가능성이 있음.
  • ConcurrentHashMap: 락 분할(Lock Striping)과 CAS를 사용해 스레드 안전성을 제공하며, 멀티스레드 환경에서도 안전하게 동작.

3.2.2 Null 허용 여부

  • HashMap: null 키와 값을 허용.
  • ConcurrentHashMap: null 키와 값을 허용하지 않음. (왜냐하면 null 값은 동시성에서 키가 존재하지 않는 것과 혼동될 가능성이 있기 때문.)

3.2.3 락의 범위

  • HashMap: 락이 없기 때문에 멀티스레드 환경에서 동기화를 추가해야 함.
  • ConcurrentHashMap: 특정 버킷에만 락을 걸어 다른 버킷은 동시에 접근 가능하도록 락 분할을 사용.

3.2.4 읽기 작업

  • HashMap: 읽기 작업은 단일 스레드 환경에서 빠르게 수행.
  • ConcurrentHashMap: 락 없이 volatile을 사용해 최신 값을 읽어옴. 따라서 읽기 작업은 멀티스레드 환경에서도 안전하고 빠르게 동작.

3.2.5 쓰기 작업

  • HashMap: 동시 쓰기 작업 시 데이터 손상 가능.
  • ConcurrentHashMap: CAS(Compare-And-Swap)를 사용해 락 없이 데이터를 변경하거나, 특정 버킷에만 락을 걸어 데이터를 수정.

3.2.6 성능

  • HashMap: 단일 스레드 환경에서 가장 빠름.
  • ConcurrentHashMap: 멀티스레드 환경에서도 높은 성능을 유지하며 동기화된 Map보다 빠르게 동작.

이렇게 ConcurrentHashMap을 HashMap과 비교해보며 동작 원리를 파악해 볼 수 있었습니다. 여러분들의 동시성 문제를 해결할 수 있기를 바라면서, 글을 마치겠습니다!!

레퍼런스

HashMap:

해시맵 구조
https://www.geeksforgeeks.org/load-factor-in-hashmap-in-java-with-examples/

트리 구조
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0#:~:text=%ED%8A%B8%EB%A6%AC%20%EA%B5%AC%EC%A1%B0(tree%20%E6%A7%8B%E9%80%A0%2C%20%EB%AC%B8%ED%99%94%EC%96%B4,%EC%9D%B4%20%EC%97%86%EB%8A%94%20%EC%97%B0%EA%B2%B0%20%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%8B%A4.&text=%ED%8A%B8%EB%A6%AC%EC%97%90%EC%84%9C%20%EC%B5%9C%EC%83%81%EC%9C%84%20%EB%85%B8%EB%93%9C%EB%A5%BC,node%20%EB%BF%8C%EB%A6%AC%20%EB%85%B8%EB%93%9C)%EB%9D%BC%EA%B3%A0%20%ED%95%9C%EB%8B%A4.

ConcurrentHashMap :

구조 (이게 도움이 많이 되었습니다.):
https://www.scaler.com/topics/hashmap-vs-concurrenthashmap/

설명 :
https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html

profile
ksngh
백엔드 개발자입니다.

2개의 댓글

comment-user-thumbnail
Banchic
2024년 12월 9일

모던 자바 인 액션에서 오늘 ConcurrentHashMap을 봤는데 이런 우연이... 내부 구조는 매우 어렵군요.. 좋은 글 감사합니다

1개의 답글