Concurrent Hash Map

ConcurrentHashMap은 여러 스레드가 동시에 안전하게 접근할 수 있도록 설계된 HashMap의 동시성 버전이다.
이 자료구조는 멀티스레드 환경에서 높은 성능과 확장성을 제공하면서도 스레드 안전성을 보장한다.

Java의 동시성 컬렉션 중 하나로, 멀티스레드 환경에서 안전하게 사용할 수 있도록 설계된 Map 구현체이다.

Java를 제외한 프로그래밍 언어와 라이브러리에서도 동시성을 지원하기 위해 구현되어 있는 자료 구조이다.

특징

  1. Thread-safe: 내부적으로 동기화 처리가 되어 있어 멀티스레드 환경에서 안전하다.
  2. 높은 동시성: 여러 스레드가 동시에 맵을 수정할 수 있으며, 읽기 작업은 락 없이 수행된다.
  3. 원자적 연산 지원: putIfAbsent(), replace(), remove() 등의 원자적 연산을 제공한다.
  4. 일관성 있는 반복자: 반복자가 생성된 시점의 맵 상태를 반영하며, ConcurrentModificationException을 발생시키지 않는다.
  5. 락 스트라이핑(Lock Striping): 맵을 여러 부분으로 나누어 각각 독립적으로 잠금을 걸어 동시성을 향상시킨다.
  6. Null 불허: 키와 값에 null을 허용하지 않는다. 이는 동시성 환경에서 null의 의미가 모호해질 수 있기 때문이다.
  7. 약한 일관성: 순간적으로 맵의 상태가 일관되지 않을 수 있지만, 최종적으로는 일관된 상태로 수렴한다.

구현 방식

ConcurrentHashMap은 다음과 같은 기술을 사용하여 구현된다:

  1. 분할 잠금(Segmented Locking): 맵을 여러 세그먼트로 나누어 각 세그먼트마다 독립적인 락을 사용한다.
  2. CAS(Compare-And-Swap) 연산: 락 없이 원자적 업데이트를 수행한다.
  3. volatile 키워드: 변수의 가시성을 보장한다.

구현 방식:
Java 8 이후의 ConcurrentHashMap은 내부적으로 다음과 같은 구조를 가집니다:

  1. Node 배열: 해시 버킷을 저장하는 기본 데이터 구조
  2. TreeBin: 해시 충돌이 많이 발생할 경우 연결 리스트를 Red-Black 트리로 변환
  3. ReservationNode: 병렬 업데이트를 위한 임시 노드

장점

  1. 높은 성능: 세밀한 락 사용으로 동시성을 극대화한다.
  2. 확장성: 동시에 접근하는 스레드 수가 증가해도 성능 저하가 적다.
  3. 안전성: 멀티스레드 환경에서 데이터 무결성을 보장한다.
  4. 메모리 효율성: 동기화를 위한 추가 객체 생성 최소화
  5. 안정성: 데드락과 같은 동시성 문제 예방

응용

ConcurrentHashMap은 다음과 같은 상황에서 주로 사용된다:

  1. 캐시 시스템: 높은 동시성이 필요한 캐싱 솔루션
  2. 세션 관리: 웹 애플리케이션에서의 사용자 세션 저장
  3. 실시간 데이터 처리: 동시에 여러 데이터 스트림 처리
  4. 메시지 큐잉 시스템: 메시지 라우팅 테이블 관리
  5. 멀티스레드 애플리케이션의 공유 데이터 저장
  6. 동시성이 높은 웹 서버나 데이터베이스 시스템

동작 원리

  1. 버킷 단위 락: 전체 맵이 아닌 개별 버킷에 대해 락을 사용한다.
  2. 읽기 작업 최적화: 읽기 작업은 락 없이 수행되어 성능을 향상시킨다.
  3. 동적 확장: 맵의 크기가 임계값을 초과하면 자동으로 확장된다.

구성 요소

  1. Node: 키-값 쌍을 저장하는 기본 노드
  2. TreeNode: 트리 구조에서 사용되는 노드
  3. ForwardingNode: 리사이징 시 사용되는 특수 노드
  4. ReservationNode: 동시 삽입 작업을 위한 임시 노드
  5. Segment: Java 7까지 사용된 잠금 단위(Java 8에서는 제거됨)
  6. Table: Node의 배열

예시 코드

Java에서의 ConcurrentHashMap 사용 예:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        
        // 데이터 추가
        map.put("A", 1);
        map.put("B", 2);
        
        // 데이터 조회
        System.out.println(map.get("A")); // 출력: 1
        
        // 조건부 갱신
        map.computeIfPresent("B", (k, v) -> v + 1);
        System.out.println(map.get("B")); // 출력: 3
        
        // 동시 처리
        map.forEach((k, v) -> System.out.println(k + ": " + v));
    }
}

Python에서의 유사한 구현 (threading 모듈 사용):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from threading import Lock

class ConcurrentDict:
    def __init__(self):
        self._dict = {}
        self._lock = Lock()
    
    def put(self, key, value):
        with self._lock:
            self._dict[key] = value
    
    def get(self, key):
        with self._lock:
            return self._dict.get(key)

# 사용 예
concurrent_dict = ConcurrentDict()
concurrent_dict.put("A", 1)
print(concurrent_dict.get("A"))  # 출력: 1

참고 및 출처