GC — Stop-the-World, Card Table, 그리고 알고리즘의 진화

지난 글에서는 JVM의 어떤 객체가 GC 대상이 되는지(3가지 가설, GC Root)를 다뤘다. 이번 글에서는 그 GC가 실제로 어떤 과정으로 동작하는지, 속도가 느려지는 원인인 STW는 무엇인지, 그리고 GC가 어떻게 발전해왔는지를 다룬다. 핵심 질문은 하나다.

GC의 역사는 곧 Stop-the-World를 줄여온 역사다. 어떻게 줄여왔는가?

1 Stop-the-World — GC 속도 저하의 원인

GC가 살아있는 객체를 판별하려면 GC Root에서 참조 그래프를 탐색(Mark)해야 한다. 문제는 탐색하는 동안 애플리케이션 스레드가 참조를 바꿔버리면 판정이 틀어진다는 것이다.

// GC가 A를 Mark하는 중에...
A.ref = B;      // 애플리케이션 스레드가 참조를 추가하면
C.ref = null;   // Mark 결과와 실제 그래프가 어긋난다

가장 확실한 해결책은 GC가 도는 동안 애플리케이션 스레드를 전부 멈추는 것이다. 이것이 Stop-the-World(STW)다. STW 동안 애플리케이션은 아무 요청도 처리하지 못하고, 힙이 클수록 탐색할 그래프가 커져 STW도 길어진다.

Safepoint

스레드는 아무 지점에서나 마음대로 멈추지 못한다. 객체 참조가 일관된 상태임이 보장되는 지점, 즉 Safepoint에서만 멈춘다. JVM은 다음 위치에 Safepoint를 심어둔다.

메서드 호출 직후
루프의 백엣지(back-edge, 루프 마지막에서 처음으로 돌아가는 지점)
예외 처리 지점
일부 반환 지점

while (true) {
    i++;
    // ← 매 반복마다 Safepoint 폴링 (GC가 요청했는지 검사)
}

만약 루프에 Safepoint가 없다면 이 스레드는 영원히 GC에 협조하지 않는다. GC가 필요하면 모든 스레드가 Safepoint에 도달할 때까지 기다린 뒤에야 STW가 시작된다.

counted loop와 TTSP 문제

counted loop란 다음처럼 반복 횟수가 명확하고, int 인덱스 기반이며, 종료가 보장되는 루프다.

for (int i = 0; i < 1_000_000; i++) {
    // ...
}

JIT 입장에서는 "어차피 유한 루프인데 매 반복마다 Safepoint를 검사하면 느리다"고 판단해, 최적화 과정에서 루프 내부의 Safepoint 폴링을 제거할 수 있다. 문제는 이 루프가 거대할 때다. 이 루프를 도는 스레드 하나가 Safepoint에 도달하지 못하면, 이미 멈춘 나머지 모든 스레드가 그 스레드 하나를 기다린다. 이를 Time-To-Safepoint(TTSP) 문제라 부른다.

JVM도 나중에 문제를 인식했다.

예전 HotSpot은 counted loop에서 polling 제거를 적극적으로 했다.

하지만 TTSP 이슈가 많이 발생해서:

-XX:+UseCountedLoopSafepoints

옵션이 추가되었다.

다만 요즘 JVM은 예전보다 똑똑하다.

최신 HotSpot(C2)은 무조건 제거하지는 않는다.

루프 크기, 최적화 상태 등에 따라 다르게 처리한다.

그래도 아주 긴 계산 루프에서는 여전히 TTSP 문제가 발생할 가능성이 있다.

2 Mark-Sweep-Compact와 세대별 GC

모든 GC 알고리즘의 뼈대는 3단계다.

단계동작부작용

Mark	GC Root에서 참조 그래프 탐색, 살아있는 객체 표시	그래프 크기에 비례한 시간
Sweep	표시되지 않은 객체 수거	단편화(Fragmentation) 발생
Compact	살아남은 객체를 한쪽으로 밀어 단편화 제거	객체 이동 → 참조 주소 갱신 필요 → 비용 큼

Sweep만 하면 힙에 구멍이 숭숭 뚫린다. 총 여유 공간은 충분한데 연속된 공간이 없어 큰 객체를 할당하지 못하는 상황이 온다. 그래서 Compact가 필요하지만, 객체를 옮기면 그 객체를 가리키던 모든 참조를 갱신해야 해서 비싸다. 이 트레이드오프가 이후 모든 알고리즘 설계를 관통한다.

Copying Collector — 약한 세대 가설의 구현

Mark-Sweep과 전혀 다른 접근이 하나 더 있다. Copying Collector는 공간을 둘로 나눠두고, GC 때 살아있는 객체만 반대편 공간으로 복사한 뒤, 원본 공간을 통째로 리셋하는 방식이다.

여기서 중요한 것은 죽은 객체를 '치우는' 동작 자체가 없다는 점이다.

방식죽은 객체 처리비용이 비례하는 대상

Sweep	하나하나 방문해서 해제	전체 객체 수
Copying	아예 건드리지 않음 (영역 포인터만 리셋)	생존자 수

지난 글의 약한 세대 가설을 떠올려보자. 대부분의 객체는 금방 죽는다. 즉 Young 영역의 생존자는 극소수다. 비용이 생존자 수에만 비례하는 Copying은 Young 영역에 압도적으로 유리하고, 복사 과정에서 객체가 한쪽에 몰리므로 단편화도 원천 차단된다. Young 영역의 GC가 Copying 방식인 이유다.

Heap 구조와 Minor GC

힙은 Young 영역과 Old 영역으로 나뉘고, Young은 다시 Eden과 2개의 Survivor(S0, S1) 로 나뉜다. Copying을 위해 Survivor 한쪽은 반드시 비워둔다.

[Eden            ][S0 (From)][S1 (To, 비움)]     [Old              ]

새 객체는 Eden에 할당된다
Eden이 가득 차면 Minor GC가 시작된다

Minor GC 동작 과정

Eden + 현재 사용 중인 Survivor(From)에서 살아있는 객체를 식별한다
생존자를 비어있는 Survivor(To)로 복사하고, age 카운터를 +1 한다 (몇 번의 GC를 살아남았는지 기록)
이때 age가 임계값(-XX:MaxTenuringThreshold, 기본 15) 이상인 객체는 To가 아닌 Old 영역으로 복사된다 — 승격(Promotion)은 별도 단계가 아니라 복사하는 순간의 목적지 판정이다
Eden과 옛 Survivor(From)는 죽은 객체를 개별 정리하지 않고 통째로 비운다
Survivor의 역할을 swap 한다 (From ↔ To)

객체가 Old 영역으로 가는 3가지 경로

경로조건성격

age 승격	age ≥ 임계값	정상 승격
조기 승격	Survivor(To)가 가득 차 복사 공간 부족	비정상 승격 (Survivor 크기 튜닝 신호)
직행 할당	처음부터 크기가 매우 큰 객체	승격이 아니라 Eden을 거치지 않는 직접 할당 (G1에서는 Humongous Region으로)

여기까지가 지난 글 가설들의 구현이다. 강한 세대 가설(오래 산 객체는 더 오래 산다)이 바로 age 기반 승격과 Old 분리의 근거다 — 여기까지 살아남은 객체는 앞으로도 오래 살 가능성이 높으므로, Old로 보내 Minor GC 대상에서 제외한다.

GC 범위에 따른 용어 정리 (Major/Full GC는 공식 스펙 용어가 아니라 관례적 용어라 문서마다 정의가 조금씩 다르다)

용어대상트리거

Minor GC	Young 영역	Eden이 가득 참
Major GC	Old 영역	Old가 가득 참
Full GC	Heap 전체 (+ Metaspace)	Old 부족, 승격 실패 등

3 Card Table과 Write Barrier — 세 번째 가설의 구현

가설 3개 중 2개의 구현을 봤다. 이제 마지막이다.

가설구현

약한 세대 가설	Young 분리 + Copying Collector + Minor GC
강한 세대 가설	age 기반 승격 + Old 분리
세대간 참조 희소성	Card Table + Write Barrier (이번 장)

Minor GC의 GC Root는 지난 글에서 본 static 변수, 스택, 스레드만이 아니다. Old 영역에서 Young 영역을 가리키는 참조도 (Minor GC 관점에서는) Root로 취급해야 한다. Old 객체가 살아있고 그 객체가 Young 객체를 참조한다면, 그 Young 객체도 살아있기 때문이다.

그럼 Minor GC 때마다 Old 영역 전체를 스캔해야 하나? 그러면 Young/Old를 나눈 의미가 없다. 여기서 세대간 참조 희소성 가설이 등장한다. Old → Young 참조는 드물다. 드물다면, 그 드문 것만 기록해두면 된다.

Card Table

Old 영역을 512바이트 단위의 카드(Card) 로 쪼개고, 각 카드의 상태를 바이트 배열로 관리한다.

Old 영역:   [card 0][card 1][card 2][card 3] ...
Card Table: [clean ][dirty ][clean ][dirty ] ...
                       │                │
                       └─ 이 카드 안에 Young을 가리키는 참조가 있을 "수" 있음

Old 객체의 필드에 Young 객체 참조가 쓰이면, 해당 카드를 dirty로 표시한다. Minor GC는 Old 전체가 아니라 dirty 카드만 스캔하면 된다.

Write Barrier

그럼 dirty 표시는 누가 하는가? JVM이 참조 대입 코드마다 자동으로 끼워 넣는 짧은 코드, Write Barrier다.

// 개발자가 쓴 코드
oldObject.field = youngObject;

// JVM이 실제로 실행하는 코드 (개념적으로)
oldObject.field = youngObject;
cardTable[addressOf(oldObject) >> 9] = DIRTY;  // 512B = 2^9

모든 참조 대입에 비용이 추가되지만(보통 수 ns), Minor GC 때 Old 전체 스캔을 피하는 이득이 훨씬 크다. 평상시에 조금씩 비용을 내고, GC 때 크게 아끼는 전형적인 트레이드오프다.

4 GC 알고리즘의 진화

이제 도구가 갖춰졌다. 각 알고리즘이 STW를 어떻게 줄여왔는지 순서대로 본다.

Serial GC — 출발점

GC 스레드 1개로 Mark-Sweep-Compact 수행
전 과정이 STW
힙이 작은 단일 코어 환경, 컨테이너 리소스가 극도로 제한된 환경 정도에서만 의미가 있다
-XX:+UseSerialGC

Parallel GC — 처리량의 시대 (Java 8 기본)

GC 작업 자체를 여러 스레드로 병렬화. STW는 여전히 발생하지만 길이가 짧아진다
목표가 처리량(Throughput) 최대화: 전체 실행 시간 중 GC가 차지하는 비율을 최소화해 단위 시간당 처리량을 높인다
배치 처리처럼 "잠깐 멈춰도 총 작업이 빨리 끝나면 되는" 워크로드에 여전히 유효하다
-XX:+UseParallelGC

CMS — Concurrent의 시초 (Java 14에서 제거)

Mark 단계 대부분을 애플리케이션 스레드와 동시에(Concurrent) 수행해 STW를 크게 줄인 첫 시도
그러나 치명적 약점이 있었다
- Compact를 하지 않아 단편화 누적 → 결국 Full GC(전체 STW Compact)로 폭발
- 동시 수행을 위한 CPU 경합, 복잡한 튜닝
실패로 끝났지만, CMS가 개척한 Concurrent Marking은 이후 모든 GC의 토대가 됐다

G1 GC — 예측 가능한 멈춤 (Java 9+ 기본)

G1은 힙 구조 자체를 바꿨다. Young/Old를 물리적으로 연속된 큰 덩어리로 두지 않고, 힙을 동일 크기의 Region(기본 1~32MB) 수백~수천 개로 쪼갠다. 각 Region이 그때그때 Eden, Survivor, Old 역할을 맡는다.

[E][O][O][E][S][O][H][H][E][O][ ][O] ...
 └ Region 단위로 역할이 동적으로 배정된다

Garbage-First: 쓰레기 비율이 가장 높은 Region부터 골라서 수거한다. 적은 비용으로 많은 공간을 회수
Pause 목표 기반 동작: -XX:MaxGCPauseMillis=200(기본 200ms)을 주면, G1이 목표 안에 끝낼 수 있는 만큼의 Region만 골라 수거한다. "얼마나 오래 멈출지"를 개발자가 협상할 수 있게 됐다
수거 = 생존자를 다른 Region으로 복사 → Region 단위 Compact가 자연스럽게 일어나 CMS의 단편화 문제를 해결
Humongous 객체: Region 크기의 50%를 넘는 객체는 전용 Region(H)에 연속 할당된다. 앞서 본 "Old 직행 할당"이 G1에서 구현되는 방식이다. 거대 배열을 자주 만들면 Humongous 할당이 잦아져 GC 압박이 커진다 — 실무에서 대용량 byte[] 캐시가 문제 되는 지점이다

ZGC — 힙 크기와 무관한 정지 시간 (Java 15 정식, 21에서 세대 지원)

G1도 생존자 복사(Evacuation)는 STW로 한다. ZGC는 이 마지막 벽을 넘었다. 객체 이동조차 애플리케이션과 동시에 수행해, 힙이 수 TB여도 STW를 1ms 미만으로 유지한다.

핵심 기술은 두 가지다.

Colored Pointer — 64비트 포인터의 남는 상위 비트에 객체의 GC 상태(Marked, Remapped 등)를 심는다. 객체가 아니라 포인터 자체에 메타데이터를 넣는 발상이다.

Load Barrier — Write Barrier가 "쓸 때" 끼어들었다면, ZGC는 참조를 읽을 때 끼어든다.

// 개발자가 쓴 코드
Object o = container.field;

// ZGC가 실제로 실행하는 것 (개념적으로)
Object o = container.field;
if (포인터 색상이 현재 GC 단계와 안 맞으면) {
    o = 객체의 새 주소로 교정하고 포인터를 갱신;  // self-healing
}

GC가 객체를 옮기는 도중에 애플리케이션이 옛 주소를 읽으면, Load Barrier가 그 자리에서 새 주소로 고쳐준다. 그래서 "모든 참조를 한 번에 갱신하기 위한 STW"가 필요 없다. 대가는 모든 참조 읽기에 붙는 미세한 비용과 다소 높은 CPU/메모리 오버헤드다.

Tri-color Marking — Concurrent Mark가 객체를 잃어버리지 않는 이유

CMS 이후의 모든 Concurrent GC는 삼색 마킹으로 동작한다.

색의미

흰색	아직 방문하지 않음 (Mark 종료 시 흰색 = 수거 대상)
회색	방문했지만 자식들은 아직 탐색 전
검은색	자신과 자식 모두 탐색 완료

문제는 Mark 도중 애플리케이션이 이런 짓을 할 때다.

black.ref = white;   // 1. 검은 객체가 흰 객체를 새로 참조
gray.ref = null;     // 2. 회색에서 그 흰 객체로 가는 경로 제거

검은 객체는 "탐색 완료"라 다시 방문하지 않고, 흰 객체로 가는 다른 경로는 끊겼다. 살아있는 객체가 흰색인 채로 Mark가 끝나 수거돼버린다(lost object problem). 이를 막는 것도 Write Barrier다. 위 1번 같은 대입이 일어나면 Barrier가 감지해 해당 객체를 다시 회색으로 되돌리거나(Incremental Update, CMS 방식), 끊기기 직전의 참조를 기록해둔다(SATB, G1 방식).

5 그래서 뭘 써야 하나

워크로드선택이유

배치/오프라인 처리	Parallel GC	멈춤보다 총 처리량이 중요
일반적인 웹 서버 (힙 수 GB)	G1 (기본값)	처리량과 지연의 균형, 튜닝 부담 적음
초저지연 요구 (거래 시스템 등), 초대형 힙	ZGC	STW < 1ms, 힙 크기 무관
극소 리소스 컨테이너	Serial GC	오버헤드 최소

대부분의 경우 정답은 "기본값(G1)을 쓰고, 문제가 측정되면 그때 움직여라"다. GC 로그(-Xlog:gc*) 없이 GC를 튜닝하는 것은 지난 글의 표현을 빌리면, 참조 그래프를 안 보고 메모리 누수를 잡겠다는 것과 같다.

정리

개념핵심

Stop-the-World	Mark 중 그래프 변경을 막기 위한 전체 정지. GC 발전 = STW 축소의 역사
Safepoint	스레드가 안전하게 멈출 수 있는 지점. counted loop의 TTSP 함정 주의
Copying (Young)	약한 세대 가설의 구현. 죽은 객체는 건드리지 않고 생존자만 복사, 비용은 생존자 수에 비례, 단편화 원천 차단
승격 (Promotion)	강한 세대 가설의 구현. age 승격 / 조기 승격 / 직행 할당 3가지 경로로 Old행
Card Table / Write Barrier	세대간 참조 희소성 가설의 구현. dirty 카드만 스캔해 Old 전체 스캔 회피
Serial → Parallel	STW 자체의 병렬화, 처리량 중심
CMS → G1	Concurrent Mark 도입 → Region 구조 + Pause 목표 + 자연스러운 Compact
ZGC	Colored Pointer + Load Barrier로 객체 이동까지 동시 수행, STW < 1ms
Tri-color Marking	Concurrent Mark의 이론적 기반, Write Barrier가 lost object 방지

여기까지 GC 알고리즘의 진화와 STW, Card Table의 동작을 알아봤다. 다음 글에서는 GC 로그를 직접 읽고(-Xlog:gc*), 힙 덤프(jmap, MAT)로 지난 글의 누수 패턴들을 실제로 잡아내는 과정을 다룬다.

GC 동작 방식 및 원리 (2)

GC — Stop-the-World, Card Table, 그리고 알고리즘의 진화

1 Stop-the-World — GC 속도 저하의 원인

Safepoint

counted loop와 TTSP 문제

JVM도 나중에 문제를 인식했다.

다만 요즘 JVM은 예전보다 똑똑하다.

2 Mark-Sweep-Compact와 세대별 GC

Copying Collector — 약한 세대 가설의 구현

Heap 구조와 Minor GC

3 Card Table과 Write Barrier — 세 번째 가설의 구현

Card Table

Write Barrier

4 GC 알고리즘의 진화

Serial GC — 출발점

Parallel GC — 처리량의 시대 (Java 8 기본)

CMS — Concurrent의 시초 (Java 14에서 제거)

G1 GC — 예측 가능한 멈춤 (Java 9+ 기본)

ZGC — 힙 크기와 무관한 정지 시간 (Java 15 정식, 21에서 세대 지원)

Tri-color Marking — Concurrent Mark가 객체를 잃어버리지 않는 이유

5 그래서 뭘 써야 하나

정리

티스토리툴바