모범답안 — 가비지 컬렉션 알고리즘 비교: 레퍼런스 카운팅 vs Mark-Sweep vs 세대별 GC

난이도: 중

핵심 답변

레퍼런스 카운팅: 각 객체가 "나를 가리키는 참조 수"를 갖고, 참조가 생기면 +1, 없어지면 -1 하다가 0이 되는 즉시 해제한다. 회수 시점이 결정적(deterministic)이라 정지(stop-the-world)가 없지만, 순환 참조(A→B, B→A)는 서로가 서로를 가리켜 카운트가 절대 0이 안 되므로 영원히 해제되지 않는다(메모리 누수).
Mark-Sweep: 참조 카운트를 관리하지 않는 대신, GC가 실행될 때 루트 집합(스택의 지역변수, 전역변수, 레지스터 등)에서 출발해 도달 가능(reachable) 한 객체를 전부 마킹(mark)하고, 마킹되지 않은 객체를 쓸어(sweep) 회수한다. 순환 참조라도 루트에서 도달할 수 없으면 자동으로 회수되므로 순환 참조 문제가 원천적으로 없다. 다만 회수 여부를 그때그때가 아니라 GC 사이클이 돌 때 일괄 판단하므로, 그 사이 죽은 객체는 잠시 살아있는 것처럼 남아있다가(stop-the-world 필요) 회수된다.
세대별 GC: Mark-Sweep(-Compact)을 개선해, "대부분의 객체는 금방 죽는다"(weak generational hypothesis)는 경험칙에 따라 힙을 나이별로 나눈다. 갓 태어난 객체(Gen 0)만 자주·싸게 훑고, 살아남은 것만 상위 세대(Gen 1/2)로 승격시켜 점점 덜 자주 훑는다. 매번 전체 힙을 스캔하지 않아도 되므로 평균 GC 비용이 크게 줄어든다.

깊이 있는 설명 (메커니즘, 왜)

레퍼런스 카운팅의 메커니즘과 한계

참조가 대입될 때마다 카운트를 증감시키는 부기(bookkeeping) 비용이 모든 대입 연산에 분산된다(정지 없음, 그러나 상시 오버헤드). 카운트가 0이 되면 즉시 소멸자가 실행되므로 자원 해제 시점이 예측 가능하다는 장점이 크다(C++ shared_ptr, Python 객체 등). 하지만 순환 구조 A↔B는 외부에서 아무도 참조하지 않아도 서로의 카운트를 1 이상으로 유지시켜 도달 불가능한데도 카운트는 0이 아닌 상태가 영구화된다. 이것이 순수 레퍼런스 카운팅의 근본적 결함이다. (CPython은 이를 보완하기 위해 별도의 순환 탐지기(cyclic GC)를 병행 실행한다.)

Mark-Sweep이 순환 참조를 해결하는 원리

Mark-Sweep은 "참조 수"가 아니라 "루트에서 도달 가능한가"만 따진다. A와 B가 서로를 가리켜도, 루트 집합 어디에서도 A나 B로 가는 경로가 없다면 마킹 단계에서 둘 다 마킹되지 않고, 스윕 단계에서 함께 회수된다. 즉 국소적인 참조 수 대신 전역적 도달 가능성을 기준으로 삼기 때문에 순환은 애초에 문제가 되지 않는다. 대가는 "언제 죽었는지"를 그 즉시 알 수 없고, GC 사이클이 돌아야만 죽은 객체가 확정적으로 회수된다는 점 — 그래서 전통적 Mark-Sweep은 GC 실행 중 애플리케이션을 멈추는 stop-the-world가 필요하다(마킹 도중 참조 그래프가 바뀌면 안 되므로).

세대별 GC가 Mark-Sweep을 개선하는 방식

순수 Mark-Sweep은 객체 수가 늘수록 매 GC마다 힙 전체를 훑어야 해서 비용이 선형으로 증가한다. 세대별 GC는 "신생 객체 대부분은 금방 죽는다"는 통계적 관찰에 근거해 힙을 세대로 쪼갠다:

Gen 0(신생): 갓 할당된 객체. 자주, 짧게 수집. 대부분 여기서 죽는다.
Gen 1: Gen 0에서 살아남은 객체의 완충 지대.
Gen 2(장수): 오래 산 객체. 드물게 수집하지만 전체를 훑어야 해서 가장 비싸다(=풀 GC).

이렇게 하면 대부분의 GC 사이클이 작은 Gen 0만 훑고 끝나므로 평균 정지 시간이 크게 줄어든다. 다만 Gen 2 수집(풀 GC)이 걸리면 그 순간은 여전히 전체(또는 그에 준하는) 스캔이 필요해 정지 시간이 길어질 수 있다 — "세대별이니 항상 빠르다"는 절반만 맞는 말이다.

응용/실무 연결 (게임서버 관점: 세 팀 사례)

A팀 — 순환 참조로 인한 누수

"아이템 → 소유 캐릭터", "캐릭터 → 장착 아이템"이 서로를 강한 참조로 붙잡고 있으면, 캐릭터가 로그아웃해 외부에서 아무도 그 캐릭터를 참조하지 않아도 아이템↔캐릭터 사이의 상호 카운트는 0이 되지 않는다. 해결책:

소유 관계 중 한쪽(보통 "역참조", 예: 아이템→캐릭터)을 **약한 참조(weak reference)**로 바꿔 카운트에 기여하지 않게 한다. 그러면 캐릭터가 다른 곳에서 안 잡히면 정상적으로 카운트가 0이 되어 해제되고, 그 시점에 아이템도 함께 정리된다.
또는 순수 레퍼런스 카운팅 대신 순환 탐지를 병행하는 GC(CPython의 gc 모듈처럼)를 도입해 주기적으로 도달 불가능한 순환 구조를 별도로 찾아 회수한다.
설계 차원에서는 소유권 방향을 명확히 단방향으로 만들고(캐릭터가 아이템을 소유, 아이템은 캐릭터를 ID로만 참조), 양방향 탐색이 필요하면 참조가 아닌 조회(예: 캐릭터 ID로 룩업)로 대체하는 것도 근본적 예방책이다.

B팀 — 세대별 GC의 풀 GC 정지

"인벤토리가 매우 커지는 순간" 정지가 발생한다는 것은, 대규모 길드 창고 데이터처럼 크고 오래 사는 객체가 여러 사이클을 넘겨 생존하며 Gen 2로 승격되었고, 그 시점에 Gen 2(풀) GC가 트리거되어 전체 힙(혹은 대형 객체 힙 포함)을 훑었을 가능성이 높다. 완화책:

Background GC: Gen 2 마킹의 상당 부분을 애플리케이션과 동시에(백그라운드 스레드로) 수행해 정지 시간을 줄인다.
할당률 감소: 매 틱 임시 객체를 덜 만들면 Gen 0가 덜 자주 차서 승격 압력 자체가 줄어든다.
객체 풀링: 길드 창고처럼 반복적으로 크게 할당/해제되는 구조를 재사용 가능한 풀로 바꿔,애초에 GC가 추적할 "새로 생겼다 죽는" 객체 수를 줄인다.
서버 GC 모드: 코어별 힙/스레드를 두어 처리량과 정지 분산을 개선.

C팀 — "세대별이니 항상 빠르다"의 함정

세대별 GC의 이득은 신생 객체가 실제로 금방 죽을 때만 성립한다. 길드 창고 데이터처럼 오래 살아남는 대량의 객체는 Gen 0→1→2로 **승격(promotion)**되고, 일단 Gen 2에 자리 잡으면:

Gen 2 수집은 드물지만 전체를 훑어야 해서 가장 비싸다.
세대 간 참조(예: Gen 2 객체가 Gen 0 객체를 가리키는 경우)를 추적하기 위한 카드 테이블(card table) 기록 비용이 쓰기마다 붙는다(쓰기 배리어).
튜닝 없이 "세대별이라 안전하다"고 방치하면, 실제로는 대량의 장수 객체가 쌓여 풀 GC 빈도와 비용이 늘어나는 것을 놓치기 쉽다.

종합

세 사례 모두 "GC가 언제, 무엇을, 왜 훑는지"를 모르면 틱 레이턴시 스파이크로 직결된다는 공통점이 있다. 레퍼런스 카운팅은 순환 참조로 인한 누수(메모리가 안 줄어듦)를, 추적식/세대별 GC는 대규모 마킹/스윕으로 인한 정지(멈춤)를 각각의 실패 모드로 갖는다. 실시간 게임서버는 두 실패 모드 모두가 곧바로 플레이어 체감 지연으로 이어지므로, 사용 언어의 GC 알고리즘 특성을 이해하고 할당 패턴·참조 구조를 그에 맞게 설계하는 것이 성능 튜닝의 핵심이다.

흔한 오답·함정

"레퍼런스 카운팅은 GC가 아니다" → 레퍼런스 카운팅도 자동 메모리 관리 기법의 하나로 GC의 한 종류다. 다만 정지 없이 즉시(incremental) 회수한다는 점이 추적식과 다르다.
"Mark-Sweep은 순환 참조도 못 잡는다" → 정반대다. Mark-Sweep(추적식 GC)의 핵심 장점이 바로 순환 참조를 자동으로 해결한다는 것이다. 순환 참조에 취약한 쪽은 레퍼런스 카운팅이다.
"세대별 GC는 정지가 아예 없다" → Gen 0/1 수집은 짧지만, Gen 2(풀) GC는 여전히 정지를 유발할 수 있다. "짧고 잦은 정지 위주로 바뀐다"가 정확한 표현이다.
"약한 참조를 쓰면 순환 참조가 저절로 사라진다" → 약한 참조는 카운트에 기여하지 않게 만들 뿐, 설계자가 어느 방향을 약하게 할지 의도적으로 골라야 한다. 무분별하게 쓰면 필요한 객체가 예상보다 일찍 해제될 위험도 있다.

꼬리질문 대비

Q: Mark-Sweep과 Mark-Compact의 차이는? A: Mark-Sweep은 죽은 객체 자리를 그대로 비워둬(free list) 단편화가 생길 수 있고, Mark-Compact은 살아있는 객체를 한쪽으로 밀어 압축해 단편화를 없애는 대신 이동 비용(포인터 갱신 포함)이 추가된다. .NET의 Gen 2는 기본적으로 압축을 동반한다.
Q: 카드 테이블(card table)은 왜 필요한가? A: 세대별 GC에서 "젊은 세대만 훑는" 최적화를 하려면, 늙은 세대(Gen 2) 객체가 젊은 세대 객체를 참조하는 경우를 놓치면 안 된다. 매번 늙은 세대 전체를 다시 스캔하는 대신, 쓰기 배리어로 "이 카드(작은 메모리 구간)에 늙은→젊은 참조가 생겼다"를 기록해두고 젊은 세대 GC 때 그 카드들만 추가로 훑는다.
Q: C++에서 순환 참조를 예방하는 관용구는? A: 소유권을 갖는 쪽은 shared_ptr/unique_ptr, 소유하지 않는 역참조 쪽은 weak_ptr을 쓴다. weak_ptr은 카운트에 영향을 주지 않아 순환을 끊는다.
Q: 게임서버에서 GC 정지가 특히 문제인 이유는? A: 실시간 틱 루프는 일정한 프레임 예산(예: 16~50ms) 안에 모든 로직을 끝내야 하는데, 예측 불가능한 시점에 수십 ms의 stop-the-world가 끼어들면 그 틱이 예산을 초과해 입력 반응 지연, 판정 밀림 등 플레이어가 체감하는 끊김으로 직결된다.

14. 가비지 컬렉션 알고리즘 비교: 레퍼런스 카운팅 vs Mark-Sweep vs 세대별 GC