스레드 32개를 붙여도 LongAdder 셀이 8개뿐인 이유 — Striped64의 base 우선과 NCPU 상한

1. 도입 — "스레드마다 카운터 하나"라는 설명의 빈틈

8코어 머신에서 LongAdder 하나에 스레드 32개가 100만 번씩 increment()를 하게 한 뒤 내부 cells 배열 길이를 찍어 봤다. 결과는 32가 아니라 8이었다. 단일 스레드로 100만 번 더했을 때는 아예 null이었다.

LongAdder는 흔히 "스레드별 카운터를 두고 나중에 합친다"로 설명된다. 이 설명으로는 위 두 숫자를 설명할 수 없다. 셀은 스레드에 붙은 게 아니라 CAS 실패를 신호로 자라는 해시 테이블이고, 그 크기는 스레드 수가 아니라 CPU 수에서 멈춘다. OpenJDK의 Striped64.java(LongAdder의 부모 클래스)를 따라가며 이 흐름을 정리했다.

2. 핵심 개념 — 경합이 생겨야 쪼갠다

LongAdder는 경합이 없으면 base 하나에만 CAS하고, CAS가 실패했을 때만 Cell[]을 크기 2로 만든다. 같은 슬롯에서 충돌이 거듭되면 2배씩 키우되 NCPU 이상으로는 키우지 않고, 그다음엔 스레드의 해시를 바꿔 빈 슬롯을 찾는다.

상태는 필드 세 개가 전부다.

Striped64
 ├─ volatile long   base       // 무경합 경로
 ├─ volatile Cell[] cells      // null 또는 길이 2^k
 └─ volatile int    cellsBusy  // 0→1 CAS 스핀락 (생성·확장 전용)

@Contended static final class Cell { volatile long value; }

처음부터 쪼개지 않는 이유는 Cell에 붙은 @Contended 때문이다. 배열에 담긴 객체는 메모리상 인접해 같은 캐시 라인을 공유하기 쉽고, 그러면 셀을 쪼개도 false sharing으로 효과가 사라진다. 그래서 셀마다 패딩을 두는데, 그만큼 크다. 소스 주석도 "셀이 크기 때문에 필요할 때까지 만들지 않는다"고 설명한다. (false sharing과 @Contended 자체는 이전 글에서 다뤘다.)

3. 내부 동작 — 테이블이 자라는 조건

add(x)의 fast path는 이렇다.

if ((cs = cells) != null || !casBase(b = base, b + x)) {
    int index = getProbe();               // 스레드의 해시값
    boolean uncontended = true;
    if (cs == null || (m = cs.length - 1) < 0 ||
        (c = cs[index & m]) == null ||
        !(uncontended = c.cas(v = c.value, v + x)))
        longAccumulate(x, null, uncontended, index);  // slow path
}

cells가 null이고 base CAS가 성공하면 그걸로 끝이다. 이 경로는 AtomicLong과 사실상 같다. 테이블이 한 번 생기면 이후 add는 base를 건너뛰고 곧바로 cs[probe & (n-1)] 슬롯에 CAS한다.

slow path인 longAccumulate에서 헷갈렸던 지점은 두 가지다.

확장은 충돌 한 번으로 일어나지 않는다. 첫 실패에서는 collide=true만 세우고 probe를 바꿔 다른 슬롯을 시도한다. 재해싱한 뒤에도 또 실패해야 cells = Arrays.copyOf(cs, n << 1)이 실행된다. 우연히 한 번 겹친 것으로 메모리를 두 배로 쓰지 않으려는 히스테리시스다.

상한은 NCPU다. n >= NCPU이면 확장 분기에 들어가지 않는다. 크기가 2부터 2배씩 크므로 실제 최대 크기는 "NCPU 이상인 가장 작은 2의 거듭제곱"이다. NCPU=6이면 2→4→8에서 멈춘다. 이유도 주석에 있다. 동시에 실행되는 스레드는 CPU 수를 넘지 못하므로, 원리적으로는 충돌 없는 매핑이 존재한다. 그다음 할 일은 테이블을 키우는 게 아니라 충돌난 스레드의 해시를 무작위로 바꿔 그 매핑을 찾는 것이다.

해시는 Thread의 threadLocalRandomProbe 필드(ThreadLocalRandom과 공유)다. 초기값은 전역 카운터에 0x9e3779b9를 더해 만들고, 재해싱은 Marsaglia xorshift(<<13, >>>17, <<5)로 한다. 마스크가 n-1이라 하위 비트만 쓰이므로, 테이블이 2배가 되면 같은 probe에서 비트 하나가 더 쓰여 스레드들이 자연스럽게 두 그룹으로 갈라진다.

참고로 openjdk/jdk master의 getProbe()는 가상 스레드일 때 캐리어 스레드의 probe를 읽는다(jdk21u는 Thread.currentThread() 기준). 동시에 도는 주체가 캐리어(≈CPU)라는 점에서 NCPU 상한 논리와 들어맞는다. 이 변경이 어느 릴리스에 들어갔는지는 확인하지 못했다.

4. 직접 확인하기, 그리고 흔한 오해

cells가 package-private이라 JShell에서 리플렉션으로 열어 봤다.

// jshell -R--add-opens=java.base/java.util.concurrent.atomic=ALL-UNNAMED
import java.util.concurrent.atomic.*; import java.lang.reflect.*;
Field f = Class.forName("java.util.concurrent.atomic.Striped64").getDeclaredField("cells");
f.setAccessible(true);

LongAdder a = new LongAdder();
for (int i = 0; i < 1_000_000; i++) a.increment();
System.out.println(f.get(a));                 // null: 경합이 없으면 테이블 미생성

var ts = new Thread[32];
for (int t = 0; t < ts.length; t++) {
    ts[t] = new Thread(() -> { for (int i = 0; i < 1_000_000; i++) a.increment(); });
    ts[t].start();
}
for (Thread t : ts) t.join();
Object[] cells = (Object[]) f.get(a);         // Cell은 package-private 타입이라 Object[]로
System.out.println(cells.length + " / NCPU=" + Runtime.getRuntime().availableProcessors());
System.out.println(a.sum());                  // 33000000

OpenJDK 25, 8코어 환경에서 null → 8 / NCPU=8 → 33000000이 나왔다. -R-XX:ActiveProcessorCount=2를 붙이면 테이블이 2를 넘지 않는다. 경합이 약하면 상한보다 작게 머물 수도 있다.

여기서 바로잡아야 할 오해가 두 가지 있었다.

흔한 이해	소스로 본 실제
스레드마다 카운터가 하나씩 있다	셀은 probe 해시로 매핑되는 공유 슬롯이고, 개수 상한은 NCPU다. 셀은 한 번 생기면 회수되지 않는다
LongAdder는 AtomicLong보다 항상 빠르다(또는 무겁다)	무경합이면 base CAS 하나로 같은 경로다. 차이는 경합이 생긴 뒤에만 난다

실패 케이스도 하나 짚어 둔다. sum()은 base와 셀을 락 없이 차례로 더할 뿐이라, Javadoc이 "NOT an atomic snapshot"이라고 명시한다. 이미 읽은 셀에 그 뒤 더해진 값은 빠진다. 그래서 "카운트가 N에 도달하면 한 번만 실행" 같은 판정이나 incrementAndGet() 반환값으로 번호를 매기는 용도에는 LongAdder를 쓸 수 없다. 이런 곳은 AtomicLong의 CAS가 맞다. sumThenReset()도 셀별 getAndSet(0)이라 업데이트가 유실되지는 않지만, 반환값이 리셋 순간의 정확한 합이라는 보장은 없다.

5. 정리

LongAdder는 "CAS가 실패했다"는 신호 하나로 테이블을 만들고, 두 번 연속 충돌해야 키우며, NCPU에서 성장을 멈춘 뒤에는 해시를 바꾸는 쪽으로 전략을 바꾼다. 스레드 32개에 셀 8개는 버그가 아니라 설계 의도다.

다음에는 ConcurrentHashMap의 size()가 쓰는 CounterCell이 Striped64와 무엇이 다른지, LongAccumulator에 결합법칙을 어기는 함수를 넣으면 어떤 결과가 나오는지 따라가 볼 생각이다.

참고 자료

OpenJDK 소스 Striped64.java / LongAdder.java / ThreadLocalRandom.java (openjdk/jdk master, jdk21u) — 특히 Striped64 클래스 주석의 구현 노트
java.util.concurrent.atomic.LongAdder Javadoc — sum()의 비원자성, AtomicLong과의 비교
False Sharing과 @Contended: 캐시 라인 단위 경합과 JVM 패딩

seonwooj0810

이전 포스트