Java ConcurrentHashMap 내부 구조 — Bin, TreeBin, ForwardingNode, 그리고 stride 기반 병렬 resize
이 글은 OpenJDK의
java.util.concurrent.ConcurrentHashMap구현을 코드 수준에서 따라가며 정리한 deep-dive입니다. 락을 어디까지 양보했는지, resize를 어떻게 여러 스레드가 나눠 들고 가는지, 그리고size()가 왜 그렇게 이상하게 생겼는지를 다룹니다. Java 17/21 기준 OpenJDK 메인 라인을 참고했습니다.
ConcurrentHashMap(이하 CHM)은 표면적으로는 그냥 HashMap인데 동시에 써도 안전한 것처럼 보입니다. 하지만 내부는 두 번 크게 갈아엎였습니다. JDK 1.5의 Segment 분할 방식에서 JDK 8의 bin 단위 synchronized + CAS 방식으로 옮겨갔고, 그 뒤로도 Doug Lea의 손에서 꾸준히 다듬어졌습니다.
이 글에서는 현재 코드 베이스가 다음 네 가지 문제를 어떻게 푸는지를 본문 흐름의 축으로 잡습니다.
- 락 단위를 어디까지 줄였는가 (bin 한 칸까지)
- 빈 슬롯과 충돌 슬롯을 어떻게 다르게 다루는가 (CAS vs
synchronized) - resize를 어떻게 한 스레드의 책임에서 끌어내렸는가 (stride +
ForwardingNode) size()의 카운터는 왜 따로 노는가 (CounterCell배열)
0. 잠시 시간을 거슬러 — Segment 분할에서 bin 단위 락으로
이 글의 본론으로 들어가기 전에 한 가지 짚어둘 것이 있습니다. CHM이 처음부터 지금과 같은 구조였던 것은 아닙니다. JDK 1.5에서 등장한 초기 CHM은 내부에 Segment[] 배열을 두고, 각 Segment가 ReentrantLock을 상속한 작은 해시 테이블이었습니다. 기본 동시성 수준 16에 맞춰 16개 세그먼트를 만들고, 키의 해시 상위 비트로 세그먼트를 고른 뒤 그 세그먼트 내부에서 락을 잡는 식이었습니다. 이 방식의 한계는 분명했습니다.
- 동시성 수준이 생성 시점에 고정되어 있어, 코어 64개짜리 머신에 동시성 16짜리 맵을 그대로 가져다 쓰면 락 충돌이 늘어났습니다.
- 세그먼트 자체가 또 하나의 객체였고, 그 안에 별도 테이블·락이 또 있어 메모리 오버헤드가 컸습니다.
- 트리화가 없어, 해시 함수가 빈약한 키 타입이 한 세그먼트에 몰리면 그 세그먼트의 모든 읽기/쓰기가 O(n)이 되었습니다.
JDK 8에서 Doug Lea는 이 구조를 폐기하고 단일 Node[] 테이블 위에 bin 단위 synchronized와 CAS를 얹는 현재 형태로 다시 썼습니다. 이름과 외부 API는 유지됐지만, 내부는 사실상 완전히 다른 자료구조입니다. concurrencyLevel 생성자 인자가 지금도 받기는 하지만 실제로는 무시되는 호환용 파라미터로만 남은 이유가 여기에 있습니다.
1. 전체 구조 — bin 배열 하나, 그리고 sizeCtl
CHM의 본체는 transient volatile Node<K,V>[] table 하나입니다. 길이는 항상 2의 제곱이고, 인덱스는 (n - 1) & hash로 구합니다. 여기까지는 HashMap과 똑같습니다. 다른 점은 다음과 같습니다.
table자체가volatile이며, 각 슬롯 접근은tabAt/casTabAt/setTabAt라는Unsafe기반 메모리 연산을 통해 일어납니다. 즉 슬롯에 대한 읽기는 락 없이 이루어지고, 쓰기는 CAS 또는 슬롯 헤드 노드에 대한synchronized로만 일어납니다.- 다음 세대 테이블
nextTable이 resize 중에만 잠깐 살아 있는 별도 필드로 존재합니다. sizeCtl이라는 하나의int가 다목적 상태 머신 역할을 합니다.
sizeCtl의 의미는 한 줄로 정리하기 어렵지만 OpenJDK 주석을 그대로 옮기면 다음과 같습니다.
When negative, the table is being initialized or resized: -1 for initialization, else -(1 + the number of active resizing threads). Otherwise ... holds the next element count value upon which to resize the table.
즉 sizeCtl은 평상시에는 "다음 임계치"(보통 n * 0.75)이고, 음수가 되는 순간 상태가 바뀝니다. -1이면 다른 스레드가 initTable()을 진행 중이라는 뜻이고, 그 외 음수는 상위 16비트가 resize 세대 스탬프, 하위 16비트가 활성 resize 스레드 수 + 1입니다. 이 한 필드 위에서 초기화, resize 시작, helper 합류, 종료 판정이 전부 이루어집니다.
2. 해시 spread — 음수 해시는 특수 노드 자리
HashMap과 마찬가지로 CHM도 입력 해시의 상위 비트를 하위로 섞어 분포를 펴는 작업을 합니다.
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
HASH_BITS = 0x7fffffff로 부호 비트를 떼어내는 것이 포인트입니다. 일반 키-값 노드의 해시는 항상 0 이상이고, 음수 해시는 특수 노드용으로 예약됩니다.
MOVED = -1 ForwardingNode
TREEBIN = -2 TreeBin (트리 컨테이너)
RESERVED = -3 ReservationNode (computeIfAbsent 임시 점유)
뒤에서 보겠지만 get() 안에서 eh < 0을 보고 분기하는 한 줄이 바로 이 음수 해시 규약 위에서 동작합니다.
3. 노드 계층 — Node, TreeBin, ForwardingNode, ReservationNode
CHM의 bin에는 네 종류의 헤드가 들어갈 수 있습니다.
| 종류 | 해시 | 역할 |
|---|---|---|
Node |
≥ 0 | 일반 키-값. next 링크로 단일 연결 리스트 |
TreeBin |
TREEBIN |
한 bin이 트리화됐을 때 헤드. 내부에 TreeNode 레드-블랙 트리 보유 |
ForwardingNode |
MOVED |
이 bin은 이미 새 테이블로 옮겨졌다는 표지판. nextTable 참조 보유 |
ReservationNode |
RESERVED |
computeIfAbsent 등에서 람다 실행 중 임시로 빈 슬롯을 점유 |
TreeBin은 단순히 트리 루트를 들고 있는 것이 아니라, 트리 회전 중 쓰기 작업과 동시에 읽는 스레드가 충돌하지 않도록 가벼운 reader-writer 동기화를 내장합니다. 트리 쓰기 측은 bin 헤드에 대한 synchronized 락을 이미 들고 있으므로 거기에 얹는 형태입니다. 즉 동시 읽기는 트리에서도 가능하고, 동시 쓰기는 bin 단위로 직렬화됩니다.
TreeBin 내부에는 별도의 lockState라는 정수 필드가 있습니다. 트리 쓰기 스레드가 회전을 시작할 때 이 비트에 "writer 진행 중" 플래그를 세우고, 그동안 들어온 읽기 스레드는 트리 구조를 따라가는 대신 같은 노드들이 단일 연결 리스트 형태로 유지되어 있는 next 링크를 따라갑니다. 트리는 회전 중에도 단일 연결 리스트로서의 일관성은 유지하기 때문에 가능한 트릭입니다. 읽기 측은 약간 느려지는 대신 락을 잡지 않고, 쓰기 측은 회전을 마치고 플래그를 내립니다. 트리화의 비용을 회피하기 위한 한 단계 더 깊은 최적화입니다.
ForwardingNode는 resize 중 가장 중요한 표지입니다. transfer가 한 bin을 모두 새 테이블로 옮긴 직후 그 슬롯에 박혀, 그 뒤로 들어오는 읽기/쓰기는 자동으로 nextTable을 따라가게 됩니다.
flowchart LR
oldTab["old table\nslot i"] -- "before transfer" --> head["Node head\nh, k, v"]
oldTab2["old table\nslot i"] -- "after transfer" --> fwd["ForwardingNode\nhash = MOVED\nnextTable"]
fwd -- "find()" --> newTab["new table\nslot i or i+n"]
4. put — 빈 슬롯엔 CAS, 충돌 슬롯엔 synchronized
put()은 내부적으로 putVal() 한 메서드를 호출합니다. 이 메서드 하나가 CHM의 거의 모든 동시성 정책을 보여주므로 단계별로 따라갑니다.
- 테이블이 비어 있으면
initTable()로 한 번만 초기화. - 해시한 슬롯이 비어 있으면 새 노드를 만들어
casTabAt으로 박는다. 락 없음. - 헤드의 해시가
MOVED라면 resize 중이므로helpTransfer()로 한몫 거든다. - 그 외에는
synchronized (f)안에서 헤드 노드부터 체인을 훑는다. 같은 키가 있으면 값 교체, 없으면 끝에 새 노드 연결. 트리화된 bin이면 트리에 삽입. - 체인 길이가
TREEIFY_THRESHOLD = 8을 넘고 테이블 길이가MIN_TREEIFY_CAPACITY = 64이상이면treeifyBin()을 호출해 단일 연결 리스트를 레드-블랙 트리로 바꾼다. 길이는 8을 넘었는데 테이블이 64 미만이면 트리화 대신tryPresize()로 확장. - 끝나면
addCount()로 원소 수를 1 증가시키고, 임계치를 넘으면 resize 트리거.
핵심은 두 가지입니다. 빈 슬롯에 첫 노드를 박을 때는 락이 일절 없습니다. 그리고 이미 노드가 있는 슬롯이라도 락 범위는 그 bin의 헤드 노드 한 개입니다. 테이블 전체나 세그먼트 단위가 아니라, 길이 N짜리 테이블에는 동시에 N개까지 쓰기 작업이 흘러갈 수 있다는 의미입니다.
flowchart TD
Start([put k, v]) --> Init{table null?}
Init -- yes --> initT[initTable] --> Hash
Init -- no --> Hash[h = spread]
Hash --> Slot{tabAt slot == null?}
Slot -- yes --> CAS{casTabAt OK?}
CAS -- yes --> Count[addCount]
CAS -- no --> Hash
Slot -- no --> Moved{hash == MOVED?}
Moved -- yes --> Help[helpTransfer] --> Hash
Moved -- no --> Lock[synchronized on head]
Lock --> Chain[traverse / insert / replace]
Chain --> Treeify{binCount >= 8?}
Treeify -- yes --> TreeifyBin
Treeify -- no --> Count
TreeifyBin --> Count
Count --> Done([return])
4.1 빈 슬롯 CAS
빈 슬롯에 헤드를 박는 코드는 다음 한 줄입니다.
if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null)))
break;
같은 슬롯을 두 스레드가 동시에 노리면 둘 중 하나만 CAS에 성공합니다. 실패한 쪽은 외부 루프를 다시 돌고, 이번에는 슬롯이 비어 있지 않으니 5단계의 synchronized 경로를 탑니다. CHM이 평균적인 워크로드에서 락을 거의 잡지 않는 이유가 여기에 있습니다. 충돌이 드물면 synchronized 블록 자체에 진입하지 않습니다.
4.2 헤드에 대한 synchronized
CAS가 안 통하는 경우, CHM은 헤드 노드 객체에 대해 synchronized 블록을 잡습니다.
synchronized (f) {
if (tabAt(tab, i) == f) {
// 체인 혹은 트리에서 검색/삽입
}
}
블록 진입 후 tabAt(tab, i) == f 재검증은 필수입니다. 락을 잡는 동안 다른 스레드가 같은 슬롯을 트리화하거나 forwarding으로 교체했을 수 있기 때문입니다. JEP 374에서 biased locking이 기본적으로 비활성화된 이후로도 HotSpot의 lightweight locking이 무경합 synchronized를 잘 처리하므로, 이 패턴의 비용은 평소에는 무시 가능한 수준입니다.
4.3 트리화의 두 가지 의미
TREEIFY_THRESHOLD = 8이라는 숫자는 자주 회자되지만 그 짝인 MIN_TREEIFY_CAPACITY = 64는 덜 알려져 있습니다. 길이 16짜리 테이블에서 한 bin에 8개가 몰렸다고 즉시 트리로 바꾸지는 않습니다. 그건 해시 분포가 나빠서가 아니라 테이블이 너무 작아서일 가능성이 높기 때문이고, CHM은 이런 경우 트리화 대신 tryPresize(n << 1)로 한 번 더 키웁니다. 트리는 어디까지나 "해시 함수가 진짜로 망한 시나리오"에 대한 보험입니다.
반대로 트리 빈에서 노드가 줄어 UNTREEIFY_THRESHOLD = 6 이하가 되면 다시 단일 연결 리스트로 풀어줍니다. 이 6과 8 사이의 갭은 트리화/언트리화가 임계치 근처에서 진동하지 않게 하는 히스테리시스입니다.
5. get — 락 없는 읽기와 음수 해시 분기
읽기 경로는 짧지만 CHM의 설계 의도가 잘 드러납니다.
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
분기 흐름은 세 갈래입니다.
- 헤드의 해시가 찾는 해시와 같으면 즉시 비교 후 반환. 가장 흔한 경로이며 락도, 메서드 호출도 없습니다.
- 헤드 해시가 음수면 특수 노드입니다.
Node.find()는 가상 메서드여서 헤드의 실제 타입(ForwardingNode/TreeBin/ReservationNode)에 따라 다르게 동작합니다.ForwardingNode.find()는nextTable에서 같은 키를 다시 찾습니다. resize 중에도 읽기가 막히지 않는 핵심입니다.TreeBin.find()는 트리에서 키를 찾되, 트리 회전이 진행 중이면 잠시 단일 연결 리스트로 순회해 락 충돌을 회피합니다.ReservationNode.find()는 항상null을 반환합니다.computeIfAbsent람다가 실행 중인 슬롯은 아직 키-값 매핑이 아니기 때문입니다.
- 위 두 경우 모두 아니면
next체인을 따라 보통의 선형 탐색.
tabAt이 volatile 읽기와 동등하므로, 다른 스레드의 setTabAt / casTabAt에 의해 들어간 노드는 happens-before로 안전하게 보입니다. 읽기 측은 락을 일절 잡지 않으면서도 시야가 일관성을 잃지 않습니다.
6. resize — stride, transferIndex, 그리고 협력하는 스레드들
CHM에서 가장 흥미로운 부분은 resize가 한 스레드의 책임이 아니라 여러 스레드가 들어와 같이 나르는 작업이라는 점입니다.
6.1 stride — 작업을 잘게 자른다
transfer()의 가장 첫 단계는 한 번에 옮길 bin 개수, 즉 stride를 정하는 것입니다.
int stride = (NCPU > 1) ? (n >>> 3) / NCPU : n;
if (stride < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
코어가 많을수록 stride는 작아지고, 최소값은 MIN_TRANSFER_STRIDE = 16입니다. 너무 작으면 작업 조율 오버헤드가 커지고, 너무 크면 한 스레드가 한참 동안 자기 stride만 보다 새로 들어온 스레드와 협력하지 못합니다. 16개 bin이라는 하한은 그 균형점입니다.
6.2 transferIndex — 끝에서부터 카운터를 깎는다
전체 테이블의 옮길 범위는 transferIndex라는 카운터 하나로 관리됩니다. resize에 합류하는 스레드는 transferIndex에서 stride만큼 빼고 그 구간을 자기 몫으로 가져갑니다. 인덱스가 0에 도달하면 더 가져갈 일이 없습니다.
if ((nextIndex = transferIndex) <= 0)
// no more work
transferIndex = nextIndex - stride;
이 한 줄짜리 분배 메커니즘 덕분에 N개의 스레드가 별도 조율 없이도 겹치지 않게 일을 나눠 들 수 있습니다.
6.3 ForwardingNode — 다 옮긴 슬롯에 박는 표지판
한 bin의 모든 노드를 새 테이블로 옮긴 직후, transfer 스레드는 다음과 같이 그 슬롯에 ForwardingNode를 박습니다.
setTabAt(tab, i, new ForwardingNode<K,V>(nextTab));
여기서부터 두 가지 일이 동시에 가능해집니다. 우선 이 슬롯에 들어오는 새 put()은 MOVED 해시를 보고 helpTransfer()로 협력에 합류합니다. 동시에 이 슬롯에 들어오는 get()은 ForwardingNode.find()를 통해 nextTable을 따라가 정답을 돌려받습니다. 옛 테이블이 다 비어 transfer가 끝날 때까지 절대로 읽기를 가로막지 않습니다.
flowchart LR
Trigger[addCount over threshold] --> Stamp[resizeStamp n shifted]
Stamp --> InitNew[allocate nextTable size 2n]
InitNew --> Loop[transfer loop]
Loop --> Claim[claim stride via transferIndex]
Claim --> Move[migrate bins to new table]
Move --> Mark[setTabAt old slot = ForwardingNode]
Mark --> More{more bins?}
More -- yes --> Claim
More -- no --> Finish[CAS sizeCtl decrement]
Finish --> Promote{last resizer?}
Promote -- yes --> Swap[table = nextTable; nextTable = null]
Promote -- no --> Exit
6.3.1 resizeStamp의 비트 인코딩
resizeStamp(n)은 어떻게 만들어지는지가 의외로 잘 알려지지 않았습니다. 정의는 다음과 같습니다.
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
numberOfLeadingZeros(n)은 테이블 크기 n에 의해 결정되는 0과 31 사이의 숫자입니다. 거기에 RESIZE_STAMP_BITS = 16의 마지막 비트, 즉 1 << 15를 OR로 켜서 stamp가 항상 16번째 비트를 가지도록 만듭니다. 이렇게 만든 stamp를 16비트 왼쪽으로 시프트해서 sizeCtl의 상위 16비트에 박고, 하위 16비트에는 활성 resizer 카운트 + 1을 넣습니다.
sizeCtl during resize:
| 15..0 stamp (always has top bit set) | 15..0 active resizers + 1 |
↑ shifted into bits 31..16 ↑ bits 15..0
상위 비트에 항상 1이 들어 있다는 사실 덕분에 sizeCtl은 resize 중에는 무조건 음수입니다. 모든 코드가 "음수면 resize 중"이라는 단 한 줄로 상태를 판단할 수 있는 이유가 이 비트 트릭에 있습니다.
6.4 helpTransfer — 들어온 김에 한몫 거든다
put()이 forwarding 슬롯과 마주치면 다음 메서드로 진입합니다.
static final void helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
}
}
resizeStamp(n)은 테이블 크기 n에 대해 16비트 상수를 만들어 냅니다. sizeCtl >>> RESIZE_STAMP_SHIFT가 그 스탬프와 일치하는 동안만 같은 세대의 resize라고 보고, CAS로 활성 resizer 카운트를 +1 한 뒤 transfer()에 들어갑니다. 일을 마치고 빠져나올 때는 다시 CAS로 카운트를 -1 하고, 마지막 한 명이 빠지는 순간 table = nextTab으로 교체합니다. 다음 resize 세대는 새 스탬프를 받으므로 stale helper는 자연스럽게 배제됩니다.
7. addCount와 CounterCell — size()는 왜 따로 노는가
CHM은 매 put()마다 단일 카운터를 증가시키지 않습니다. 그 자리가 곧 contention 핫스팟이기 때문입니다. 대신 addCount()는 두 단계로 동작합니다.
- 일단
baseCount에 CAS로 더해본다. - 실패하거나 이미
counterCells가 존재하면, 스레드별 해시(ThreadLocalRandom.getProbe())로 골라낸CounterCell하나의value에 더한다.
CounterCell은 @Contended로 캐시 라인이 패딩된 long 한 칸짜리 셀이고, LongAdder / Striped64에서 가져온 그대로의 디자인입니다. 여러 스레드가 서로 다른 셀을 두드리므로 캐시 라인 false sharing 없이도 카운팅이 흐릅니다.
대신 진짜 원소 수는 어디에도 한 곳에 모이지 않습니다. size() / mappingCount()는 호출 시점에 baseCount + Σ counterCells[i].value를 합산합니다.
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (CounterCell counterCell : as)
if ((a = counterCell) != null)
sum += a.value;
}
return sum;
}
여기서 중요한 사실 두 가지가 따라 나옵니다. 첫째, size() 결과는 호출 시점의 정확한 스냅샷이 아니며 다른 스레드가 동시에 put / remove를 하고 있으면 값이 살짝 어긋날 수 있습니다. 둘째, 그래서 mappingCount()가 long을 반환합니다. 정수형 한계를 넘는 큰 맵을 다루기 위해서이기도 하지만, "근사적인 추정치"라는 의미를 타입으로 드러내는 의도도 있습니다.
또 한 가지 미묘한 최적화는 resize 트리거 조건에 들어 있습니다. 주석에 따르면 resize 검사는 "두 노드 이상이 있는 bin에 추가될 때만" 시도되어, post-resize 직후에는 평균 1/8 회 put에서만 임계치를 검사합니다. 매 put이 임계치를 보지 않으므로 카운터 검사 자체도 절약됩니다.
7.1 compute, computeIfAbsent, 그리고 ReservationNode
computeIfAbsent처럼 람다를 호출하는 메서드는 한 가지 까다로운 요구를 가집니다. 람다가 새 값을 계산하는 동안 다른 스레드가 같은 키로 또 람다를 호출하면 곤란합니다. 그렇다고 람다를 잡고 있는 동안 헤드 노드에 대한 synchronized 락을 풀면, 다른 쓰기가 그 슬롯을 바꿔 버립니다. CHM은 이 문제를 ReservationNode로 해결합니다.
빈 슬롯에 대해 computeIfAbsent가 호출되면, CHM은 먼저 ReservationNode를 슬롯에 박고 그 노드에 대해 synchronized를 잡은 채 람다를 실행합니다. 람다 결과가 null이면 예약을 풀고 슬롯을 다시 비우며, null이 아니면 결과를 담은 진짜 Node로 교체합니다. 이 사이 들어온 다른 쓰기는 헤드의 RESERVED 해시를 보고 잠시 대기하거나 다른 경로를 탑니다. ReservationNode.find()가 항상 null을 반환하도록 만든 이유는, 람다 계산이 끝나기 전까지 그 슬롯은 "키가 매핑되지 않은 상태"로 보여야 하기 때문입니다.
이 디자인의 부수 효과로 한 가지 미묘한 규약이 생깁니다. computeIfAbsent 람다 안에서 같은 키로 다시 compute*을 호출하면 데드락이 납니다. 자기 자신이 들고 있는 ReservationNode 락을 자기 자신이 다시 잡으려고 하기 때문입니다. Javadoc도 이 점을 명시적으로 경고합니다.
8. 이터레이터의 약한 일관성
keySet() / values() / entrySet()이 반환하는 뷰는 약한 일관성(weakly consistent) 이터레이터를 돌려줍니다. 즉 다음과 같은 성질입니다.
- 이터레이터는 생성 시점 이후에 들어온 변경을 반영할 수도, 안 할 수도 있습니다.
ConcurrentModificationException을 던지지 않습니다.- 절대로 같은 원소를 두 번 반환하지 않으며, null 참조를 따라가지 않습니다.
- resize가 일어나도 이터레이터는 깨지지 않고, 옛 테이블에서 forwarding을 만나면 새 테이블로 따라갑니다.
HashMap의 fail-fast 이터레이터와 정반대 정책입니다. 동시성 컨테이너에서 fail-fast를 강제하려면 매 변경을 모든 이터레이터에 통지해야 하는데, 그 비용은 CHM이 지키려는 무락 읽기 원칙과 정면 충돌합니다.
9. 자주 오해되는 부분 정리
- "CHM은 락이 아예 없다"는 말은 틀립니다. 빈 슬롯과 읽기에는 없지만, 충돌 슬롯에 대한 쓰기는 헤드 노드에 대한
synchronized블록을 잡습니다. 핵심은 락의 범위가 슬롯 한 칸으로 줄어들었다는 점입니다. - "키를 한 번에 하나만 갱신할 수 있다"는 말도 절반만 맞습니다. 같은 슬롯의 동시 쓰기는 직렬화되지만, 다른 슬롯끼리는 완전히 병렬입니다. 길이 1024 테이블이면 사실상 1024-way 잠금에 가깝습니다.
- "
size()는 그냥 멤버 필드 하나일 것이다"라는 직관은 완전히 빗나갑니다.CounterCell배열을 순회 합산해야 합니다. - "resize는 한 스레드가 다 끝낼 때까지 나머지는 막힌다"는 말은 옛
Hashtable이야기입니다. CHM은 들어오는 스레드를 helper로 끌어들이고, 읽기는 forwarding으로 새 테이블에 흘려보냅니다.
10. 정리
ConcurrentHashMap의 설계가 일관되게 추구하는 한 가지는 "락의 범위와 빈도를 최소화한다"는 것입니다. 그 도구상자가 결국 다음 네 가지로 정리됩니다.
- bin 단위로 쪼갠
synchronized잠금 - 빈 슬롯에 대한 CAS 첫 삽입
- stride + transferIndex + ForwardingNode로 분산되는 resize
baseCount+CounterCell배열로 분산되는 원소 카운터
HashMap을 쓰다가 멀티스레드 환경에서 CHM으로 옮길 때, 그 비용 차이를 한 줄로 표현하기는 어렵습니다. 그러나 위 네 가지가 얼마나 정교하게 맞물려 있는지를 보면, "그냥 동기화된 맵"이라는 추상이 사실은 자료구조 수준에서 동시성을 직접 설계한 결과라는 점은 분명합니다.
참고자료
- OpenJDK 소스:
ConcurrentHashMap.java - 공식 Javadoc:
ConcurrentHashMap(Java SE 21) - JEP 374: Deprecate and Disable Biased Locking
Striped64/LongAdder원본:Striped64.java- Doug Lea, JSR 166 mailing list 아카이브: JSR-166 interest site