ConcurrentHashMap은 어떻게 동시성을 보장할까?

들어가기 앞서

프로젝트 진행 중 도서 데이터를 비동기적으로 크롤링하여 HashMap에 저장하는 로직을 구현했습니다. 목표는 100개의 데이터를 수집하는 것이었으나, HashMap을 사용하면서 데이터 개수가 일치하지 않는 문제가 발생했습니다.

문제 원인을 분석한 결과, 비동기 작업에서 발생하는 동시성 문제로 인해 HashMap만으로는 데이터 관리에 어려움이 있다는 점을 알게 되었습니다. 이를 해결하기 위해 HashMap, HashTable, ConcurrentHashMap의 차이점을 살펴보고, 각 자료구조가 어떤 방식으로 동작하는지 비교해보려 합니다.

 

HashMap

• key와 value에 null 허용
• 동기화를 보장하지 않음

HashMap은 스레드 안전(thread-safe)을 보장하지 않기 때문에, 주로 싱글 스레드 환경에서 사용하는 것이 적합합니다. 동기화를 처리하지 않기 때문에 데이터 탐색 속도가 빠르다는 장점이 있지만, 그만큼 신뢰성과 안정성 면에서는 제한이 있습니다. 결과적으로 HashMap은 HashTable이나 ConcurrentHashMap보다 데이터 탐색 속도가 빠르지만, 멀티스레드 환경에서는 주의가 필요한 자료구조입니다.

 

HashTable

• key와 value에 null을 허용하지 않음
• 동기화 보장

HashTable은 스레드 안전(thread-safe)을 보장하므로 멀티스레드 환경에서 사용할 수 있습니다. 이는 데이터 처리 메서드에 synchronized 키워드가 적용되어 있어, 메서드 호출 시 쓰레드 간 동기화 락이 걸리기 때문입니다. 이 동기화 락 덕분에 멀티스레드 환경에서도 데이터의 무결성이 보장됩니다. 그러나, 동기화 락은 속도를 저하시킬 수 있어, 성능 측면에서는 다소 불리한 점이 있습니다.

 

ConcurrentHashMap

• key와 value에 null을 허용하지 않음
• 동기화 보장

ConcurrentHashMap은 스레드 안전(thread-safe)을 보장하여 멀티스레드 환경에서 사용할 수 있는 자료구조입니다. 이 구현체는 HashMap의 동기화 문제를 보완하기 위해 개발되었습니다. ConcurrentHashMap은 동기화 처리 시, 특정 노드(Node)를 조작할 때 해당 노드에만 락을 거는 방식으로 작동합니다. 이를 통해 HashTable보다 데이터를 다루는 속도가 빠르고, 성능이 향상됩니다. 즉, 노드별로 개별 락을 걸어 멀티스레드 환경에서도 높은 효율성을 제공합니다.

그렇다면, ConcurrentHashMap이 어떻게 이러한 성능 최적화를 가능하는지 알아보기 위해 조금 더 자세히 알아보겠습니다. 

ConcurrentHashMap.putVal() 

putVal() 메서드는 해당 자료구조에 데이터를 삽입할 때 실행되는 메서드로 이 메서드는 여러 스레드가 같은 키에 쓰기를 시도할 때 동시성 제어를 통해 안전하게 데이터를 삽입하거나 업데이트할 수 있도록 설계되어 있습니다. 따라서 putVal 메서드를 자세히 살펴보는 것이 중요합니다. 

이 메서드는 Lock, CAS(Compare-And-Swap) 연산, 노드 동기화 등의 기법을 활용하여 멀티스레드 환경에서도 데이터의 일관성과 안전성을 보장합니다. 

 

putVal() 메서드의 호출 

public V put(K key, V value) {
	return putVal(key, value, false);
}

public V putIfAbsent(K key, V value) {
	return putVal(key, value, true);
}

final V putVal(K key, V value, boolean onlyifAbsent) {
	...
}

위 두 메서드는 내부적으로 putVal 메서드를 호출합니다. 

 

메서드가 두 개로 나누어져 있는 이유는 사용 목적이 다르기 때문입니다. put 메서드는 기존의 값을 덮어쓰고 새로운 값으로 업데이트할 때 사용되는 반면, putIfAbsent는 키가 존재하지 않을 때만 값을 삽입하고, 키가 이미 존재하는 경우 기존 값을 그대로 유지하는 로직을 가지고 있습니다. 이러한 목적에 따라 두 메서드가 구분되어 구성되어 있습니다. 

 

CAS (Compare-And-Swap)

ConcurrentHashMap에서 사용하는 CAS 기법은 비동기 동시성 제어 방법 중 하나로, 여러 쓰레드가 동시에 데이터를 수정하려 할 때 데이터의 일관성을 보장합니다. CAS는 하드웨어 수준에서 수행되는 원자적 연산으로, 공유 변수의 현재 값을 기대한 값과 비교하여, 기대한 값이 일치하는 경우에만 새로운 값으로 변경하는 과정을 통해 동시성 문제를 해결합니다. 

 

CAS는 또한 락을 사용하지 않으므로 데드락과 같은 문제를 방지하면서도 높은 성능을 유지할 수 있으며, 이러한 특성 덕분에 멀티 쓰레드 환경에서도 성능 저하 없이 데이터의 일관성을 유지하는데 효과적입니다. 

 

CAS의 동작 방식

1. 쓰레드가 특정 메모리 위치의 값을 읽고, 이를 기대 값으로 저장합니다. 
2. 쓰레드는 CAS 연산을 호출하면서 기대 값과 새로 설정하려는 값을 함께 전달합니다.
3. CAS 연산이 호출되면, 메모리의 현재 값과 기대 값을 비교합니다. 
   • 만약 현재 값이 기대 값과 일치한다면, 이는 해당 메모리 위치의 값이 다른 쓰레드에 의해 변경되지 않았다는 뜻이므로, 원자적으로 새로운 값으로 교체합니다.
   • 만약 현재 값이 기대 값과 다르다면, 쓰레드가 값을 변경한 것이므로, 교체는 실패하고 쓰레드는 필요한 재시도를 수행하거나 다른 방식으로 처리를 진행합니다. 

이 과정을 통해 CAS를 통해 데이터를 변경하면 어떤 쓰레드나 프로세스도 개입할 수 없게 보호되므로, CAS 연산은 항상 완전하게 수행되거나 전혀 수행되지 않는 두 가지 상태 중 하나만 가질 수 있습니다. 이를 통해 데이터의 일관성을 유지할 수 있습니다. 

❓CAS의 한계점
CAS는 메모리 값이 변경되었는지 확인하지만, 그 값이 중간에 변경되었다가 다시 원래 값으로 돌아오는 상황을 처리하지 못합니다. 이를 ABA 문제라고 합니다.

 

putVal() 메서드 분석

1. 입력 값 검증 및 해시 계산

if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;

• 입력 값 검증: ConcurrentHashMap은 키와 값에 null을 허용하지 않기 때문에 NullPointerException을 리턴하도록 설계되어 있습니다. 
• 해시 계산: key.hashCode()를 호출하여 해시 코드를 가져오고, spread() 메서드를 통해 해시를 더 균등하게 분산시킵니다. 이 과정은 해시 충돌을 줄여 해시 테이블의 성능을 최적화하기 위함입니다. 

2. 무한 루프와 테이블 초기화

if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = =0;

for (Node<K,V>[] tab = table; ; ) {
	if (tab == null || (n = tab.length) == 0) 
		tab = initTable();
	...
}

• 무한 루프 설정: 이 반복문에서는 for문의 조건을 생략하여 무한 루프를 생성합니다. 이는 특정 조건이 충족될 때까지 반복하기 위한 것으로, 반복 종료는 루프 내에서 명시적으로 break가 호출될 때만 이루어집니다.
• 테이블 초기화 확인: 해시 테이블 tab이 초기화되지 않았거나 길이가 0인 경우, initTable() 메서드를 호출하여 초기화합니다.

3. 비어있는 버킷에 노드 추가 (CAS 연산)

for (Node<K,V>[] tab = table; ; ) {
	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;
	}
}

• 버킷 검사: 계산된 인덱스 i에 있는 버킷이 비어있는지 확인합니다. 비어있다면 tabAt() 메서드를 통해 해당 위치의 값을 가져옵니다.
• CAS 연산을 통한 노드 추가: 버킷이 비어있을 경우 casTabAt() 메서드를 사용해 원자적으로 새로운 노드를 추가합니다. CAS가 성공하면 노드가 추가된 것이므로, break로 반복문을 종료합니다. 

4. 리사이징 상태 확인 및 지원

for (Mode<K,V>[] tab = table; ; ) {
	... 
	
	else if ((fh = f.hash) == MOVED) {
		tab = helpTransfer(tab, f);
	}
}

• 리사이징 상태 확인: f.hash값이 MOVED라면, 테이블이 현재 리사이징 중임을 나타냅니다. 리사이징은 해시 테이블이 특정 임계치에 도달하여 크기를 확장해야 할 때 발생합니다.
• 리사이징 지원: helpTransfer() 메서드를 호출하여 현재 쓰레드가 리사이징 작업을 지원하도록 합니다. 이를 통해 여러 쓰레드가 병렬로 리사이징을 수행하여 테이블 크기를 효율적으로 조정할 수 있습니다. 

5. 조건부로 기존 노드 확인 및 반환

for (Mode<K,V>[] tab = table; ; ) {
	... 
	
	else if ((fh = f.hash) == MOVED) {
		tab = helpTransfer(tab, f);
	}
	
	else if (onlyIfAbsnet
				&& fh == hash
				&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
				&& (fv = f.val) != null) {
		return fv;
	}
}

• 조건부 확인: onlyIfAbsent가 true인 경우, 키가 이미 존재하면 값을 변경하지 않으므로 첫 번째 노드를 락 없이 확인합니다.
• 기존 값 반환: 키가 이미 존재하고 값이 null이 아닌 경우, 기존 값을 반환하며 메서드를 종료합니다.

6. 락을 사용한 노드 삽입 및 업데이트

for (Mode<K,V>[] tab = table; ; ) {
	... 
	
	else if (onlyIfAbsnet
				&& fh == hash
				&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
				&& (fv = f.val) != null) {
		return fv;
	}
	
	else {
		V oldVal = null;
        synchronized (f) {
            if (tabAt(tab, i) == f) {
                if (fh >= 0) {
                    binCount = 1;
                    for (Node<K,V> e = f; ; ++binCount) {
                        K ek;
                        if (e.hash == hash &&
                            ((ek = e.key) == key ||
                             (ek != null && key.equals(ek)))) {
                            oldVal = e.val;
                            if (!onlyIfAbsent)
                                e.val = value;
                            break;
                        }

                        Node<K,V> pred = e;
                        if ((e = e.next) == null) {
                            pred.next = new Node<K,V>(hash, key, value);
                            break;
                        }
                    }
                }
                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");
            }
        }
        ...
}

• 락을 사용한 동기화: 버킷에 첫 번째 노드가 존재하면 해당 노드를 synchronized 블록으로 감싸 동기화합니다. 이는 여러 쓰레드가 동시에 같은 버킷에 접근할 때 발생할 수 있는 충돌과 데이터 손상을 방지하기 위함입니다.
• 연결 리스트 처리: 버킷이 연결 리스트 구조로 되어 있는 경우, 리스트의 각 노드를 순회하며 동일한 키를 찾습니다. 키를 발견하면 값을 갱신하고, 존재하지 않으면 리스트 끝에 새로운 노드를 추가합니다.
• 트리 구조 처리: 버킷이 트리 구조인 경우, 트리 노트를 탐색하여 동일한 키를 찾아 값을 업데이트하거나, 키가 없으면 새로운 노드를 추가합니다.

7. 트리화 검사

for (Node<K,V>[] tab = table;;) {

    // ...

    // 이전 설명 코드 (길어서 생략)

    else {
        V oldVal = null;
        synchronized (f) {
            if (tabAt(tab, i) == f) {
                if (fh >= 0) {
                    binCount = 1;
                    for (Node<K,V> e = f;; ++binCount) {
                        ...
                    }
                }
            else if (f instanceof TreeBin) {
                ...
            }
        }

        if (binCount != 0) {
            if (binCount >= TREEIFY_THRESHOLD)
                treeifyBin(tab, i);
            if (oldVal != null)
                return oldVal;
            break;
        }
    }
}

• 트리화 검사: 버킷에 있는 노드의 수(binCount)가 TREEIFY_THRESHOLD(기본 값 8)를 초과할 경우, 연결 리스트를 트리 구조로 변환합니다. 이는 해시 충돌이 많은 상황에서 검색 성능을 최적화하기 위함입니다.

8. 노드 수 증가 및 종료 처리

for (Node<K,V>[] tab = table;;) {
	...

           if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }   
}

addCount(1L, binCount);
return null;

• 노드 수 증가: 새로운 노드가 추가될 때마다 해시맵의 전체 노드 수를 증가시키며, 필요 시 테이블 크기를 조정하여 해시 충돌을 줄이고 성능을 최적화합니다. 
• 결과 반환: 새로운 키-값 쌍이 성공적으로 추가되었음을 나타내기 위해 null을 반환합니다.

동작 과정 총 정리

아래는 put() 메서드 호출 시의 전체 동작 과정입니다. 

동일한 키가 이미 존재하는 경우

1. 입력받은 키와 값이 null인지 확인하고 null일 경우 NullPointerException을 반환합니다.
2. 입력받은 키의 해시코드를 계산하고, 이를 spread() 메서드로 분산시켜 해시 테이블의 인덱스를 찾습니다. 
3. 테이블이 초기화되지 않았거나 길이가 0이면 initTable() 메서드를 호출하여 초기화합니다.
4. 계산된 인덱스 위치에 있는 버킷이 비어있는지 확인합니다.
5. 버킷에 동일한 키로 저장된 노드가 있다면, 기존 값을 새로운 값으로 덮어쓰고 기존 값을 반환합니다. 

동일한 키가 존재하지 않는 경우

1. 입력받은 키와 값이 null인지 확인하고 null일 경우 NullPointerException을 반환합니다.
2. 입력받은 키의 해시코드를 계산하고, 이를 spread() 메서드로 분산시켜 해시 테이블의 인덱스를 찾습니다. 
3. 테이블이 초기화되지 않았거나 길이가 0이면 initTable() 메서드를 호출하여 초기화합니다.
4. 계산된 인덱스 위치에 있는 버킷이 비어있는지 확인합니다.
5. 버킷이 비어있을 경우, CAS 연산을 사용해 원자적으로 새로운 노드를 추가합니다. 
6. 노드가 추가되면 반복문을 종료합니다.