가비지 컬렉션 알고리즘 완전 정복 — Mark-Sweep부터 ZGC 1ms까지, 세대별 GC와 현대 저지연 컬렉터의 모든 것 (2025)

0. GC 는 왜 여전히 어려운가

2000년대에 "Java GC 는 나쁘다, C++ 를 써라" 가 유행했다. 2020년대에는 Java 의 ZGC 가 수 TB 힙에서도 1ms 이하 일시정지. Go 는 10ms 이하로 수렴. 근데 왜 여전히 프로덕션에서 GC 튜닝으로 밤을 새우는가?

간단한 이유: GC 는 시간/공간/정확성의 3차원 트레이드오프. "하나를 잘하면 다른 게 망가진다." 지난 65년간 이 세 축 사이에서 균형점을 찾는 알고리즘이 계속 발명됐고, 언어마다 다른 타협 을 선택했다.

이 글은 GC 알고리즘이 어떻게 진화해왔는지, 왜 각 언어가 다른 GC 를 쓰는지, 그리고 현대 저지연 GC 들이 어떻게 "불가능해 보이던 1ms 일시정지" 를 달성했는지 파헤친다.

1. GC 가 해결하는 문제

1.1 수동 메모리 관리의 악몽

C 에서의 네 가지 영원한 버그:

• 메모리 누수: free 호출 안함.
• Double free: 이미 해제된 메모리를 다시 해제.
• Use-after-free: 해제된 메모리에 접근.
• Dangling pointer: 해제된 객체를 여전히 가리키는 포인터.

Chrome 의 2019년 보안 버그의 70% 가 메모리 안전성 문제 (Microsoft 도 비슷한 통계). 이게 Rust 의 ownership 이나 GC 언어의 존재 이유.

1.2 GC 의 약속

"도달 불가능한 (unreachable) 객체는 자동으로 회수." 여기서 "도달 불가능" = "프로그램의 root 에서 시작해 포인터 추적으로 도달할 수 없는 객체".

Roots:

• 스택 변수.
• 전역 변수.
• CPU 레지스터.
• JNI handles (Java).

이 root 집합에서 그래프 탐색 → 도달 못하는 객체는 죽음.

1.3 GC 가 안 해주는 것

• 순환 참조 해제: 참조 카운팅 GC (Python 이 일부 사용) 는 순환 탐지 보조 필요.
• 리소스 해제: 파일 핸들, 소켓. Finalizer 의존은 위험 → try-with-resources, defer, RAII.
• 실시간 보장: 일반 GC 는 최악 시간이 예측 불가.

2. 고전 알고리즘들

2.1 Mark-and-Sweep (1960, McCarthy, Lisp)

John McCarthy 의 Lisp 인터프리터에 최초 GC. 두 단계:

Mark: Root 에서 DFS/BFS → 도달 가능한 모든 객체에 "살아있음" 표시. Sweep: 힙 전체를 스캔 → 표시 없는 객체를 free list 에 추가.

Before:
[A(m)] [B] [C(m)] [D(m)] [E] [F(m)] [G] [H(m)]

After Sweep:
[A] [FREE] [C] [D] [FREE] [F] [FREE] [H]
       ↓    ↓           ↓
    free list 연결

문제:

• 단편화: 빈 공간이 작은 조각으로 흩어짐.
• 일시정지: 전체 힙 스캔 시 프로그램 중단.
• 큰 힙 = 긴 GC 시간.

2.2 Copying GC (1970, Cheney)

힙을 반으로 나눔. 한 쪽 (from-space) 만 사용. GC 시:

1. Root 에서 시작해 살아있는 객체를 to-space 로 복사.
2. 복사 시 from-space 의 원본에 "forwarding pointer" 남김.
3. 복사 중 다른 참조가 원본을 찾으면 forwarding 따라감.
4. 복사 완료 후 from-space 전체를 한 번에 비움.

장점:

• 할당이 극도로 빠름: ptr++ 로 끝. 자유 공간 탐색 없음.
• 단편화 없음: 복사 시 밀착.
• 시간이 살아있는 객체 수에 비례 (죽은 객체 스캔 안 함).

단점:

• 메모리 절반만 사용 가능.
• 큰 객체 복사 비용.

2.3 Mark-Compact

Mark + Compact (살아있는 객체를 앞으로 밀착 복사).

Mark-Sweep 의 단편화 문제 해결. 하지만 일시정지 길어짐.

2.4 Reference Counting

각 객체에 카운터. 참조 추가 시 +1, 제거 시 -1. 0 이 되면 즉시 해제.

장점:

• 일시정지 없음 (부분적).
• 결정론적 (언제 해제될지 예측 가능).

단점:

• 순환 참조 처리 못함: A → B → A 면 둘 다 카운트 1, 영원히 살아남음.
• 카운터 업데이트 비용 (멀티스레드에서 특히 원자적 연산).
• 캐시 효율 나쁨 (참조 업데이트마다 객체 메타데이터 수정).

Python (CPython), Objective-C, Rust (Rc/Arc) 가 채택.

3. Generational GC — 1984년의 돌파구

3.1 Generational Hypothesis

David Ungar (1984) 의 관찰:

"대부분의 객체는 아주 짧게 살다가 죽는다. 살아남은 객체는 대체로 오래 산다."

• HTTP 요청 처리 중 만든 임시 객체: 요청 끝나면 죽음.
• 설정 객체, 연결 풀: 프로그램 내내 삶.

3.2 Young / Old Generation 분리

Young Generation (Eden + Survivor 0 + Survivor 1)
                ↓ 여러 번 살아남은 객체 promotion
Old Generation (Tenured)

• Young 은 자주 GC (Copying GC, 빠름).
• Old 은 드물게 GC (Mark-Sweep-Compact).

3.3 일반적 숫자

JVM 기본:

• Young GC: 수 ms ~ 수십 ms, 자주 (수 초마다).
• Old GC: 수백 ms ~ 수 초, 드물게 (분~시간).
• Young 객체의 95%+ 가 첫 GC 에서 사라짐.

3.4 Cross-Generation Reference 문제

Old → Young 참조 있으면 Young GC 시 Old 도 봐야 함? Old 전체 스캔이면 "빠른 Young GC" 의미 없음.

해결: Card Table / Remembered Set.

• Old 영역을 작은 카드로 분할 (512 바이트 단위).
• Old → Young 참조가 생기면 해당 카드를 "dirty" 로 표시.
• Young GC 시 dirty card 만 스캔.

쓰기 시마다 체크 (write barrier): if (new_ref is young) mark_dirty(card). 할당 약간 느려지지만 Young GC 가 엄청 빨라짐.

3.5 Generational 의 비용

• 각 객체 약간 추가 헤더 (age 필드).
• Write barrier 오버헤드 (할당/참조 설정 시).
• Young 이 너무 작으면 promotion 폭주 → Old 빨리 참.
• Young 이 너무 크면 Young GC 가 느려짐.

이 튜닝이 Java 에서 -Xmn, -XX:NewRatio 같은 옵션의 근원.

4. JVM GC 의 진화 — Serial 에서 ZGC 까지

4.1 Serial GC (1998)

단일 스레드 Mark-Sweep-Compact. 작은 힙 (수백 MB) 에 적합. 지금도 -client 모드 기본.

4.2 Parallel GC (2002)

여러 스레드가 동시에 GC. Young/Old 모두. 처리량 (throughput) 우선.

• 일시정지: 수백 ms ~ 수 초.
• 처리량: 최고.
• 배치 처리에 좋음.

4.3 CMS (Concurrent Mark Sweep, 2004-2020)

Old GC 의 대부분을 애플리케이션 실행 중 수행. Young GC 는 여전히 STW.

• 일시정지: 수십 ms.
• 비용: CPU 소비 증가, 단편화.

Java 14 에서 제거.

4.4 G1 GC (Garbage First, 2012 정식)

Java 9 부터 기본:

핵심 혁신:

• 힙을 region (1-32MB) 으로 분할.
• 각 region 이 Young 또는 Old 역할.
• Mark 는 concurrent, 수거는 STW 지만 선택적 region 만.

Garbage First 의 의미: "쓰레기가 가장 많이 찬 region 부터 수거" → 동일 시간 내 최대 메모리 회수.

장점:

• 큰 힙 (수십 GB) 에서도 일시정지 제한 가능 (-XX:MaxGCPauseMillis=200).
• Young/Old 경계 유연.
• 단편화 적음.

단점:

• Write barrier 오버헤드가 G1 에서 더 높음.
• 복잡한 튜닝.

4.5 ZGC (Z Garbage Collector, 2019 정식)

Oracle 이 Azul C4 에서 영감. TB 단위 힙에서 1ms 이하 일시정지 목표.

4.5.1 Colored Pointers

64비트 주소의 상위 비트를 색깔 로 사용 :

[reserved | finalizable | remapped | marked1 | marked0 | actual address]
     3         4            5          6         7       8-42

각 색깔이 GC 상태 표현. 한 포인터에 여러 정보.

4.5.2 Load Barrier

포인터 읽기 마다 체크:

ref = object.field     // load barrier 삽입됨
if (!is_good_color(ref))
    ref = fix(ref);    // GC 상태에 맞게 수정
use(ref);

• 쓰기 barrier 대신 읽기 barrier.
• 앱이 GC 와 "협력" 해서 객체 이동 처리.

4.5.3 거의 모든 단계 Concurrent

• Mark: concurrent.
• Relocate (이동): concurrent.
• STW 는 시작/종료 ~1ms.

4.5.4 비용

• 메모리 오버헤드: load barrier 로 CPU 약간 느려짐.
• 추가 메모리 (forwarding table).
• 하지만 지연 민감 서비스에서 결정적.

4.6 Shenandoah (Red Hat, 2014-)

ZGC 와 비슷한 목표, 다른 접근:

Brooks Pointer: 각 객체 앞에 "실제 위치" 포인터 헤더. 객체 이동 시 이 포인터만 갱신.

• STW 1-10ms 로 유지.
• ZGC 와 다른 점: 32비트도 지원, 읽기 barrier 가 약간 다름.
• Red Hat OpenJDK 에 기본, Oracle 은 별도 모듈.

4.7 비교 요약

5. Go GC — 저지연 우선의 단일 철학

5.1 초기 (Go 1.0)

Mark-Sweep, STW. 일시정지 수백 ms. "Go 는 GC 때문에 못 쓴다" 평.

5.2 Go 1.5 (2015) 의 대수술

Concurrent Tri-color Mark-Sweep:

• Mark 단계 동안 앱 계속 실행.
• STW 는 시작/종료 짧은 순간.
• 목표: 일시정지 10ms 이하.

결과: Go 사용층 급속 확대.

5.3 Go 1.8+ 의 개선

• STW 1ms 목표, 실제 대부분 달성.
• Hybrid write barrier: Dijkstra + Yuasa 조합.
• Background sweep: 마킹 끝나면 앱과 동시에 스윕.

5.4 Generational 없음

Go 는 지금까지 세대별 GC 를 채택하지 않음. 이유:

• 컴파일러 escape analysis 가 스택 할당을 강하게 활용.
• 단순한 런타임 철학.
• 세대별 도입의 복잡성이 이득보다 크다고 판단.

하지만 2023년부터 "green tea" 프로젝트로 generational GC 실험 중.

5.5 GC Tuning

Go 는 튜닝 노브가 매우 적음:

• GOGC: 힙 증가율 %. 기본 100 (힙 2배 되면 GC). 낮추면 GC 자주, 높이면 메모리 사용 증가.
• GOMEMLIMIT: 소프트 메모리 상한 (1.19+).

Java 의 수십 개 옵션 대비 단순.

6. V8 GC (Chrome, Node.js)

6.1 Orinoco — 병렬 + 동시 + 증분 GC

V8 의 현대 GC 이름. 여러 기법 조합:

• Young Generation (Scavenger): Parallel Copying.
• Old Generation: Incremental Mark-Compact + Concurrent Marking.
• Major GC: 수백 ms → 수 ms 로 감소.

6.2 Concurrent Marking (2018)

JavaScript 실행 스레드와 별도의 마킹 스레드. Chrome 에서 GC 로 인한 프레임 드롭 제거.

6.3 Sweeping Optimization

Minor GC (Young) 이후 오래된 객체의 Compact 는 백그라운드에서 천천히. Idle time 에 실행.

6.4 Node.js 특화

• 긴 GC 일시정지 감지 시 event loop 지연.
• --max-old-space-size 로 힙 크기 제한.
• perf_hooks 의 PerformanceObserver 로 GC 이벤트 관찰.

7. Python — 참조 카운팅 + 사이클 GC

7.1 기본: 참조 카운팅

CPython 의 모든 객체는 ob_refcnt 필드. 참조 생성/소멸마다 갱신.

• 장점: 즉시 해제, GC 일시정지 없음 (대체로).
• 단점: 멀티스레드에서 GIL 이 필요한 주된 이유 (원자 카운터 비용 회피).

7.2 사이클 수집기

참조 카운팅이 못 잡는 순환 참조 해결:

• 세대별 (0, 1, 2).
• 주기적 실행.
• gc.disable() 가능.

7.3 PyPy — 세대별 Mark-Sweep

PyPy 의 MiniMark GC 는 CPython 보다 훨씬 빠름. 세대별, 병렬, 할당 최적화. 수치 연산에서 CPython 대비 10배+.

7.4 Python 3.12 의 실험

"No GIL" Python 제안과 함께 참조 카운팅을 biased 방식으로 (스레드 로컬로) 변경 실험. 장기적으로 Python GC 도 재설계 가능성.

8. Azul C4 — 상업적 극단

8.1 Continuously Concurrent Compacting Collector

Azul Systems 가 개발한 JVM GC. ZGC 의 원형:

• TB 단위 힙에서 1ms 일시정지 보장.
• 모든 단계 concurrent.
• Read barrier + forwarding.

8.2 용도

• 금융 거래 시스템 (마이크로초 단위 지연 중요).
• 대규모 캐시 서버.
• 실시간 분석 엔진.

상업 제품 (Azul Platform Prime). ZGC, Shenandoah 가 오픈 소스 대안.

9. 튜닝 실전 — JVM 예시

9.1 먼저 측정

-Xlog:gc*:file=gc.log:time,uptime,level,tags

도구:

• GCViewer: 로그 시각화.
• GCEasy: 온라인 분석.
• JFR (Java Flight Recorder): 종합 프로파일.

9.2 메트릭

• Throughput: 앱 실행 시간 / 전체 시간. 95%+ 권장.
• Pause time: 최대/평균/P99 일시정지.
• Allocation rate: 초당 할당 바이트. 너무 높으면 앱 재설계.
• Promotion rate: Old 로 승격 속도.

9.3 일반 원칙

• 힙 크기 설정: -Xms = -Xmx (동일). OS 메모리 할당 안정화.
• GC 선택: 지연 민감 → G1 또는 ZGC. 처리량 → Parallel.
• STW 목표 설정: -XX:MaxGCPauseMillis=200. 너무 작으면 오히려 잦은 GC.
• Young 크기: 할당률의 3-5배.

9.4 자주 보는 증상

• "Allocation failure" 로그 범람: Young 이 너무 작음.
• Full GC 빈발: Old 가 꽉 참. 메모리 누수 의심.
• Promotion failure: Old 여유 부족 + 승격 실패 → concurrent mode failure.

10. GC 가 없는 선택 — Rust, Zig

10.1 Rust 의 Ownership

컴파일 타임에 소유권 추적:

let s = String::from("hello");  // s 가 메모리 소유
let t = s;                       // 소유권 이전. s 는 이제 못 씀.
// s 범위 벗어나면 메모리 해제.

• Runtime GC 없음 → 일시정지 없음.
• 메모리 안전 보장 (Rust 의 borrow checker).
• 러닝 커브 가파름.

참조 카운팅이 필요하면 Rc<T>, 멀티스레드면 Arc<T>. 순환 참조는 Weak<T> 로 끊음.

10.2 Zig 의 명시적 Allocator

GC 없음. malloc/free 더 추상화. 모든 함수가 allocator 를 인자로 받음:

const allocator = std.heap.page_allocator;
const list = try std.ArrayList(u32).init(allocator);
defer list.deinit();

defer 로 RAII 유사. 명시적이지만 안전.

10.3 C++ RAII + 스마트 포인터

• std::unique_ptr: 단일 소유.
• std::shared_ptr: 참조 카운팅.
• std::weak_ptr: 순환 끊기.

현대 C++ 는 사실상 GC 없는 자동 메모리 관리. Rust 이전부터 이 방향.

11. 실전 질문들

11.1 "메모리 누수 같은데 GC 가 안 치우네?"

GC 는 도달 가능한 객체를 못 치움. "쓰레기인데 아직 root 에서 참조됨" = 논리적 누수:

• 이벤트 리스너 해제 안 함.
• 캐시가 무한히 커짐.
• ThreadLocal 이 정리 안 됨.
• 싱글톤에 계속 참조 추가.

해결: 메모리 프로파일러로 "가장 많은 인스턴스" 탐색 → 참조 체인 추적.

11.2 "GC 가 너무 자주 돌아"

할당률이 너무 높음:

• 루프 안 오브젝트 생성 지양.
• Primitive 배열 선호.
• Object pool (하지만 복잡성 증가).
• 문자열 concat 을 StringBuilder 로.

11.3 "Full GC 가 길다"

Old 가 너무 크거나 참조 구조가 복잡:

• -Xmx 줄여보기 (반직관적이지만 때로 효과).
• 장수 객체 줄이기.
• 객체 그래프 단순화.

11.4 "GC 튜닝 후 더 느려짐"

가장 흔한 실수. 측정 없이 옵션 추가. 기본값은 수많은 벤치마크로 최적화됨. 근거 있는 변경만:

1. 프로파일.
2. 가설.
3. A/B 비교.
4. 한 번에 하나 변경.

12. 마치며 — 65년의 진화, 계속되는 여정

1959 년 McCarthy 의 Lisp 첫 GC → 1984 년 Generational → 2004 년 CMS → 2012 년 G1 → 2019 년 ZGC.

각 세대는 이전의 한계를 극복했다. 처리량 vs 지연 vs 메모리 의 3차원에서 끊임없이 새 타협점을 찾아왔다. 현재의 frontier:

• 지연: 1ms → 100µs → 하드웨어 지원 없이는 한계.
• 처리량: SIMD, 캐시 최적화.
• 메모리: Colored pointer 의 오버헤드 감소.
• 언어 통합: Escape analysis, region inference (MLKit, Koka).

다음 10년은 아마도:

• 하드웨어 지원 GC (Azul + Intel 의 메모리 태깅).
• 머신러닝 기반 힙 크기 자동 튜닝.
• 영역 타입 시스템 (compile-time memory regions) 의 재평가.

매번 new Object() 할 때 이 65년의 역사가 작동한다. 공짜가 아니지만, 정말 정교한 엔지니어링이다.

다음 글에서는 컨테이너 내부 — Docker 의 마법 뒤에 있는 Linux namespaces, cgroups, overlayfs, 그리고 seccomp/capabilities — 를 파볼 예정이다. docker run 한 줄이 어떻게 격리된 실행 환경을 만드는지.

참고 자료

• Richard Jones, Antony Hosking, Eliot Moss — "The Garbage Collection Handbook" (2nd ed, 2023).
• David Ungar — "Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm" (1984).
• Per-Åke Larson — "Dynamic Hashing" (1988) — Tri-color abstraction 전신.
• G1 설계 논문 — Detlefs et al (ISMM 2004).
• ZGC 설계 문서 — OpenJDK wiki.
• Shenandoah 설계 — Red Hat Developer Blog.
• Go runtime GC blog 시리즈 — Rick Hudson.
• V8 Orinoco 블로그 — v8.dev/blog (orinoco, concurrent-marking 등).
• Azul C4 백서.
• "Crafting Interpreters" — Robert Nystrom (Part III: Bytecode, GC 챕터).