[java] ConcurrentHashMap 동기화 방식

« 2024/04 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

java8 (jdk 1.8.0_162) 기준으로 작성하였다.
기본적인 동작은 HashMap 과 동일하거나 비슷한 부분이 많아, HashMap 의 동작 원리 를 먼저 알아야 이해하기가 수월하다.

HashMap 은 멀티스레드 환경에서 동시에 수정을 시도하는 경우 예상치 못한 결과가 발생할 수 있다. 멀티스레드 환경에서 안전하게 HashMap 을 조작할 수 있도록 java 에서 제공하는 concurrent 패키지의 자료 구조인 ConcurrentHashMap 을 사용하면서 동작 원리가 궁금해 찾아 보다가, 블로그 글마다 설명하는 내용이 다르기도 하고(java8 부터 동기화 부분 로직이 바뀌었다), 대략적인 설명만 읽어서는 잘 이해가 안되기도 했다.

그래서 직접 들어가 보기로 했다. 코드도 복잡하고, 변수 네이밍도 아주 심플해서 예상보다 더 읽기가 어려웠다.
codeglance 로 바라본 put 함수의 indent 는 아래 보는 것과 같이 아름답다.🤣

HashMap, Hashtable, ConcurrentHashMap

Map interface 를 구현한 3가지 구현체들의 차이는 자료가 워낙 많고, 구글에 검색 해보면 쉽게 찾아볼 수 있으니 넘어 가자.
동시성에 관련해서 간단하게만 살펴 보면 아래와 같다.

HashMap : Thread 에 안전하지 않다.
Hashtable : Thread safe. 데이터 관련 함수에 synchronized 키워드가 선언 되어 있다.
ConcurrentHashMap : 역시 thread-safe 이 보장된다. 차이점은 지금부터 알아보자!

동기화 처리 방식

Hashtable 과는 다르게, 주요 method 에 synchronized 키워드가 선언되어 있진 않다. 먼저 ConcurrentHashMap 에서 새로운 entry 를 put 할 때의 코드를 따라가 보았다. put 함수는 크게 2가지 경우로 나눌 수 있는데(분기는 총 4 부분으로 나뉨), 새로운 노드가 들어갈 배열의 인덱스가 비어있는 경우(아래 1번)와 이미 기존 노드가 있는 경우(아래 2번)이다.

빈 해시 버킷에 노드를 삽입하는 경우, lock 을 사용하지 않고 Compare and Swap 을 이용하여 새로운 노드를 해시 버킷에 삽입한다.(원자성 보장)

(1) 무한 루프. table 은 내부적으로 관리하는 가변 배열이다.
(2) 새로운 노드를 삽입하기 위해, 해당 버킷 값을 가져와(tabAt 함수) 비어 있는지 확인한다.(== null)
(3) 다시 Node 를 담고 있는 volatile 변수에 접근하여 Node 와 기대값(null) 을 비교하여(casTabAt 함수) 같으면 새로운 Node 를 생성해 넣고, 아니면 (1)번으로 돌아간다(재시도).

volatile 변수에 2번 접근하는 동안 원자성(atomic)을 보장하기 위해 기대되는 값과 비교(Compare)하여 맞는 경우에 새로운 노드를 넣는다(Swap).
CAS 구현은 java.util.concurrent.atomic 패키지의 Atomic* 클래스들과 동일하게 내부적으로 sun.misc.Unsafe을 사용하고있다. (Unsafe 는 jdk11 부터 없어 졌다고 한다.)
아, 참고로 volatile[ˈvälətl]은 [발-러들] 이라 읽는다.
이미 노드가 존재 하는 경우는 synchronized (노드가 존재하는 해시 버킷 객체) 를 이용해 하나의 스레드만 접근할 수 있도록 제어한다.
서로 다른 스레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 된다. (이 부분이 내가 가장 알고 싶었던 곳이다‼️)

synchronized 안의 로직은 HashMap 과 비슷한 로직이다. 동일한 Key 이면 Node 를 새로운 노드로 바꾸고, 해시 충돌(hash collision) 인 경우에는 Separate Chaining 에 추가 하거나 TreeNode 에 추가한다. TREEIFY_THRESHOLD 값에 따라 체이닝을 트리로 바꾼다.

생성자

생성자에서는 초기 해시테이블(associate array) 사이즈를 결정한다. DEFAULT_CAPACITY는 16이다. 생성자에서 직접 해시테이블을 생성하지는 않는다. 해시 테이블 생성은 첫 노드가 삽입될 때 생성된다.(lazily initialized)
생성자의 주요 파라미터는 3가지가 있다. java8 에서는 initialCapacity 외의 다른 파라미터는 전 버전과의 호환성을 위해 존재한다.

int initialCapacity
초기 용량을 결정한다. 구현은 지정된 부하 계수가 주어지면 이 많은 요소를 수용하기 위해 내부 크기 조정을 수행한다.
loadFactor
HashMap 에서 사용되는 부하 계수(테이블 밀도)와 동일하다. 하지만 ConcurrentHashMap 에서는 초기 테이블의 크기를 설정하기 위한 용도로만 쓰인다.
HashMap 에서는 이 값에 따라서 table 이 resize 되는 시점이 결정되지만, ConcurrentHashMap 에서는 이 인자 값과 상관 없이 0.75f로 동작한다(테스트 해보니 0.5로 세팅해도 0.75로 동작한다). 예를 들어, 초기 테이블 크기가 16 이면 entry 수가 12개가 될 때 해시테이블 사이즈를 16에서 32로 증가시킨다.
concurrencyLevel
"동시에 업데이트를 수행하는 예상 스레드 수" 라고 주석에 적혀 있지만, 구현시 이 값은 단순히 초기 테이블 크기를 정하는데 힌트로만 사용된다.

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {

    // concurrencyLevel 이 초기 capacity 값 보다 큰 경우, concurrencyLevel 을 initialCapacity 로 사용한다.
    if (initialCapacity < concurrencyLevel) {
        initialCapacity = concurrencyLevel;
    } 

    // capacity 와 테이블 밀도로 size 를 구한 후, table 의 크기를 결정(2의 n제곱) 한다.
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);

    // 테이블 초기화와 테이블의 리사이징을 제어하는 변수(내부 해시테이블은 가변 배열)
    this.sizeCtl = cap; 
}

table 배열의 크기를 계산 하는 tableSizeFor 메서드는 2의 거듭 제곱 만을 반환한다.
tableSize method

가변 배열 리사이징

HashMap 에서의 리사이징은 단순히 resize() 함수를 통해 새로운 배열(newTab)을 만들어 copy 하는 방식이다.
ConcurrentHashMap 에서는 기존 배열(table) 새로운 배열(nextTable) 로 버킷을 하나씩 전송(transfer) 하는 방식이다. 이 과정에서 다른 스레드가 버킷 전송에 참여할 수도 있다. 전송이 모두 끝나면 크기가 2배인 nextTable 이 새로운 배열이 된다.
변수 sizeCtl 과 resizeStamp 메서드를 통해 resizing 과정이 중복으로 일어나지 않도록 방지한다.
transfer

트리 노드의 순서 결정 (tieBreakOrder)

이 부분은 HashMap 과 구현이 동일하다. 트리 구성시, hashcode 의 값이 같으면서 오브젝트가 동일하지 않은 경우 트리의 ordering 을 위해 System.identityHashCode 을 이용하여 해결한다.
tieBreakOrder

간단한 테스트 코드를 통해 시스템 해시코드와 해시코드가 값이 다르다는 것을 확인할 수 있다.
System.identityHashCode

정리

java 8 이전의 ConcurrentHashMap 은 ReentrantLock 을 상속 받는 Segment 를 이용하여 동기화를 구현하였었다. 이 때는 영역을 구분하여(기본 16개) 영역 별로 잠금을 하는 방식이었다. 각 영역에서는 리사이징 되는 해시테이블을 갖는다.
하지만 java8 에서는 각 테이블 버킷을 독립적으로 잠그는 방식이다. 빈 버킷으로의 노드 삽입은 lock 을 사용하지 않고 단순히 CAS 만을 이용해 삽입한다. 그 외의 업데이트(삽입, 삭제 및 교체)는 lock(synchronized) 을 이용하지만 각 버킷의 첫 번째 노드를 기준으로 부분적인 잠금을 획득하여 스레드 경합을 최소화 하고 안전한 업데이트를 한다.

References

Compare and Swap
Java HashMap은 어떻게 동작하는가?
Java Language - sun.misc.Unsafe
Java volatile이란?

나만보는페이지

나만보는페이지