가비지 컬렉션(Garbage Collection, 이하 GC)이란 힙(heap)에 할당된 객체 중 더 이상 사용되지 않는 객체인 가비지(garbage)를 메모리에서 자동으로 해제해 주는 기능입니다. GC는 작동 방식에 따라 추적(tracing) 기반의 GC와 참조 카운트(reference count) 기반의 GC로 분류됩니다.
추적 기반의 GC는 객체를 접근이 가능한 객체인 reachable 객체와 접근이 불가능한 객체인 unreachable 객체로 분류해 unreachable 객체들을 메모리에서 해제하는 방식으로 동작합니다. 자바는 추적 기반의 GC를 지원하는 대표적인 언어이며, 자바의 GC는 JVM 실행 엔진의 가비지 컬렉터(Garbage Collector)에 의해 주기적으로 실행됩니다.
참조 카운트 기반의 GC는 객체가 참조되고 있는 개수를 세어 해당 객체에 대한 참조가 더 이상 없다면, 즉 참조 카운트가 0이 되면 해당 객체를 메모리에서 해제하는 방식으로 동작합니다. Swift의 ARC는 대표적인 참조 카운트 기반의 GC입니다.
참조 카운트 기반 GC는 객체의 참조 카운트가 0이 되는 순간 객체를 메모리에서 해제하므로 GC 수행 오버헤드가 적습니다. 하지만 객체들끼리 서로를 순환적으로 참조해 메모리에서 해제되지 않는 순환 참조라는 메모리 누수 문제가 발생할 수 있습니다. 또한, 모든 객체는 자신의 참조 카운트를 들고 있어야 하므로 메모리 오버헤드가 존재합니다.
반면에, 추적 기반 GC에서는 순환 참조 문제가 발생하지 않습니다. 대신 추적 기반 GC에는 GC가 수행되는 동안 일시적으로 애플리케이션이 정지하는 현상인 stop-the-world 문제가 있습니다. 하지만 현대의 GC 구현은 이러한 일시 정지 시간을 최소화했습니다. 따라서 많은 프로그래밍 언어는 추적 기반 GC를 사용합니다.
Note
이 글은 추적 기반의 GC를 다룹니다. 참조 카운트 기반 GC의 작동 방식이 궁금하신 분들은 이 글을 참고하세요.
Reachability의 판별
자바는 객체의 접근 가능 여부인 reachability를 판별해 접근이 불가능한 객체인 unreachable 객체들을 메모리에서 해제합니다. 객체의 reachability를 판별하기 위해서는 판별 기준이 되는 시작점이 필요하며, 이를 루트(root)라 합니다. 즉, 루트에서부터 시작해 해당 객체까지 접근이 가능한 객체는 reachable 객체가 되고, 접근이 불가능한 객체는 unreachable 객체가 됩니다.
Reachability 판별의 기준이 되는 루트는 메서드 영역의 static 변수에 의한 참조, JVM 스택(메서드 실행 시 사용하는 파라미터나 지역 변수)에 의한 참조, 네이티브 스택에 의한 참조입니다. 즉, 힙 내부 객체들끼리의 참조를 제외한 모든 참조는 루트가 될 수 있습니다.
주의
우측 하단의 객체는 루트에서부터 접근이 불가하므로, 해당 객체가 reachable 객체를 참조하고 있더라도 unreachable 객체로 판별됩니다.
Stop-the-world
Stop-the-world란 GC를 수행하는 쓰레드를 제외한 모든 쓰레드들이 GC가 완료되기 전까지 작업을 일시적으로 멈추는 현상입니다. 이는 GC가 수행되는 동안 객체 관련 정보가 변경되는 등의 문제가 일어나지 않도록 방지해 애플리케이션의 일관성을 유지하기 위함입니다.
애플리케이션은 GC를 완료한 이후에 중단했던 작업을 다시 시작하므로, stop-the-world는 애플리케이션 성능에 큰 영향을 미칠 수 있습니다. 하지만 어떤 GC 알고리즘을 사용하더라도 이러한 일시 정지는 피할 수 없습니다. 따라서 이 일시 정지 시간을 최소화하기 위한 다양한 GC 알고리즘들이 개발되었습니다.
기본 알고리즘
이번 절에서는 GC를 이해하기 위한 기본적인 알고리즘들을 살펴봅니다.
Naive mark-and-sweep
Naive mark-and-sweep 알고리즘은 두 단계로 실행되며, 각 객체는 reachability 구별을 위한 단일 비트 플래그를 갖고 있습니다.
첫 번째 단계인 mark 단계에서는 루트를 시작으로 전체 객체 트리를 순회하며 루트를 통해 접근할 수 있는 모든 객체를 mark합니다. 즉, mark 단계가 완료되면 애플리케이션에서 사용 중인 reachable 객체들을 식별할 수 있게 됩니다.
두 번째 단계인 sweep 단계에서는 전체 메모리를 스캔하여 mark되지 않은 unreachable 객체들을 메모리에서 해제하고, mark된 reachable 객체들의 플래그를 원래대로 돌려놓습니다.
이 알고리즘의 가장 큰 단점은 일시 정지 시간입니다. 해당 알고리즘은 메모리 전체를 두 번 스캔하는 아주 긴 시간 동안 애플리케이션이 멈추므로 실시간성이 중요한 경우 사용이 어렵습니다. 또한, GC가 수행될수록 메모리 단편화(fragmentation) 문제가 발생하여 메모리 할당이 어려워집니다.
이러한 문제를 개선하기 위해, GC를 나눠서 수행할 수 있는 tri-color marking 알고리즘이나, 메모리 단편화 해결 단계를 추가한 mark-sweep-compact 등의 알고리즘이 개발됐습니다. 비록 이런 알고리즘들의 총 수행 시간은 naive mark-and-sweep 방식보다 오래 걸릴 수 있지만, 일시 정지 시간을 줄이거나 메모리를 효율적으로 사용할 수 있습니다.
Tri-color marking
기존의 mark-and-sweep 알고리즘처럼 객체를 접근 가능과 불가능으로만 나누면 GC를 나눠서 할 수 없습니다. Tri-color marking 알고리즘에서는 객체를 세 가지 색(흰색, 검은색, 회색)으로 마킹해 GC를 나눠서 수행할 수 있도록 합니다.
각 색은 객체에 다음과 같은 의미를 부여하며, 기본적으로 검은색과 회색 객체는 GC의 대상이 아닙니다.
- 흰색: 메모리 수집의 대상이 되는 객체
- 검은색: 흰색 객체를 참조하지 않는 reachable
- 회색: 흰색 객체에 대한 참조 여부가 결정되지 않은 reachable
Tri-color marking 알고리즘은 루트가 직접적으로 참조하는 객체를 회색으로 표시한 상태에서 시작됩니다.
- 회색 객체를 스캔해, 해당 객체가 참조하는 흰색 객체들을 모두 회색으로 바꿉니다.
- 1번에서 선택한 회색 객체를 검은색으로 바꿉니다.
- 스캔할 회색 객체가 더 이상 존재하지 않을 때까지 1, 2번을 반복합니다.
만약 알고리즘이 중간에 중단되었다 하더라도, 다음에 다시 시작할 때 남아있는 회색 객체들만 스캔하면되므로 점진적인 수행이 가능합니다. 따라서 tri-color marking 알고리즘은 점진적으로 실행될 수 있습니다. 또한 tri-color marking 알고리즘을 사용한 GC는 애플리케이션을 중단하지 않고도 수행될 수 있습니다. 이러한 동작은 객체가 할당되는 순간이나 변경되는 순간에 색칠도 같이함으로써 가능합니다.
Java Garbage Collector
이번 절에서는 GC에서 사용되는 기본적인 알고리즘에 대한 이해를 바탕으로 과거의 자바 가비지 컬렉터와 현재의 자바 가비지 컬렉터를 알아봅니다.
Generational Garbage Collector
대부분의 객체는 얼마 못가 unreachable 해지며, 오래된 객체에서 새로운 객체로의 참조는 거의 없다는 가설을 기반으로 Generational Garbage Collector(이하 GGC)가 탄생했습니다. GGC는 GC 과정에서 스캔하는 메모리의 범위를 줄임으로써 일시 정지 시간을 줄이고자 했습니다. 따라서 GGC에서는 힙을 논리적으로 Young 영역과 Old 영역으로 나누어 각 영역별로 GC를 수행합니다. Young 영역에서 수행되는 GC를 Minor GC, Old 영역에서 수행되는 GC를 Major GC 혹은 Full GC라고 부릅니다.
주의
GGC는 고수준의 추상적인 개념이며, 구체적인 가비지 컬렉터가 아닙니다. GGC의 개념을 기반으로 구현된 가비지 컬렉터에는 Serial Garbage Collector, Parallel Garbage Collector 등이 있습니다.Serial Garbage Collector는 단일 스레드에서 모든 GC를 수행하므로, 일시 정지 시간은 길지만 리소스 사용량은 낮습니다. 즉, 단일 프로세서만 있는 시스템이 아니라면 사용할 이유가 없습니다. Parallel Garbage Collector는 Serial Garbage Collector와 비슷하지만, GC를 수행하기 위해 여러 쓰레드를 사용해 일시 정지 시간을 줄인 가비지 컬렉터입니다.
Young 영역
새롭게 생성된 대부분의 객체는 Young 영역에 할당됩니다. 이 중 대부분은 얼마 못가 GC의 대상이 됩니다. 만약 객체가 오래 살아남았다면, 해당 객체는 Old 영역으로 이동됩니다. Young 영역에는 주로 짧은 생명주기를 가진 객체들이 할당되므로, Old 영역보다 적은 메모리 공간만을 필요로합니다.
Young 영역은 더욱 효율적인 메모리 활용을 위해 또다시 Eden과 2개의 Survivor 영역으로 나누어집니다. 새롭게 생성된 대부분의 객체는 Eden 영역에 할당되며, Eden 영역에서 GC가 발생한 후 살아남은 객체는 두 Survivor 영역 중 한 곳으로 이동됩니다. 단, 두 Survivor 영역 중 한 곳은 반드시 비어있어야 합니다.
Young 영역의 크기는 Old 영역에 비해 작으므로 GC를 수행하는데 오래걸리지는 않지만, GC가 빈번하게 발생합니다. 그래도 Minor GC의 일시 정지 시간은 애플리케이션 성능에 큰 영향을 미치지 않습니다.
Minor GC 알고리즘에 대한 설명은 gif로 대체하겠습니다.
보시다시피 GGC에서는 객체들을 복사해 영역 간에 이동시키는 복사이동 기법을 사용합니다. 복사이동 기법은 객체를 모두 새로운 영역으로 복사한 뒤, 기존 객체에 대한 참조를 업데이트하는 방식으로 동작합니다. 이런 과정이 비효율적으로 느껴질 수 있지만, 사실은 그렇지 않습니다. 복사이동 기법을 사용하면, 추가 작업 없이 남은 메모리 공간을 회수할 수 있습니다. 또한, 객체를 새로운 영역에 연속적으로 할당함으로써 메모리 단편화 문제를 쉽게 해결할 수 있습니다.
Old 영역
Old 영역에는 Young 영역에서 오래 살아남은 객체들이 이동됩니다. Young 영역 객체의 age 값이 여러 번의 GC를 거쳐 임계값에 도달하면, 해당 객체는 Old 영역으로 이동됩니다. 이러한 과정이 반복돼 Old 영역의 메모리 공간이 가득차면, Major GC가 수행됩니다.
Major GC는 mark-and-sweep 알고리즘에 compact 단계를 추가해 메모리 단편화 문제를 해결한 mark-sweep-compact 알고리즘을 사용합니다. Compact 단계에서는 reachable 객체들을 한 곳으로 모아 메모리 단편화 문제를 해결합니다. 그러나 객체들을 이동시키기 위한 오버헤드가 발생하며, 이를 최소화하기 위해 여러 쓰레드를 사용해 병렬적으로 GC를 수행합니다.
Old 영역은 일반적으로 Young 영역보다 넓은 메모리 공간을 할당받기 때문에 GC가 상대적으로 드물게 발생하지만, 한 번 GC가 수행되면 오래걸립니다. 따라서 Major GC의 일시 정지 시간은 애플리케이션 성능에 큰 영향을 미칠 수 있습니다.
Garbage First Garbage Collector
Garbage First Garbage Collector(이하 G1)는 현재 자바의 기본 가비지 컬렉터이며 발전하는 컴퓨팅 리소스(큰 메모리, 멀티코어, 하이퍼쓰레딩 등)를 십분 활용하기 위해 탄생했습니다. G1에서는 기존 GGC의 Young/Old 영역 개념을 발전시킨 region이라는 개념을 도입했습니다.
G1은 메모리를 고정 크기의 region들로 관리합니다. Region의 크기는 자동으로 설정되며, 수동으로는 최대 512MB까지 설정할 수 있습니다. 각 region은 GGC와 마찬가지로 Young(Eden, Survivor)과 Old로 구분되며, region 간 복사이동 방식을 사용합니다.
위 그림의 회색 영역은 현재 사용 가능한 메모리를 나타냅니다. G1은 메모리를 효율적으로 관리하기 위해 메모리의 일부(최대 75%)만 사용합니다. 또한 G1은 대부분의 경우 Young region만 스캔합니다. 드물게 스캔하는 Old region에 대해서는 가장 많은 가비지를 가진 곳을 우선적으로 스캔합니다. 이러한 이유로 해당 가비지 컬렉터에는 Garbage First라는 이름이 붙게 되었습니다.
Region의 절반 이상을 차지하는 거대한 객체는 region을 혼자서 점유하며, 이러한 region을 Humongous region이라 합니다. 예를 들어, region의 크기가 16MB고 객체의 크기가 9MB라면 해당 region에는 이 객체 하나만 저장됩니다. 만약 객체의 크기가 17MB라면 해당 객체는 두 개의 연속적인 region에 저장됩니다. Humongous region은 Young region처럼 매번 스캔되지만, Young region은 아닙니다. Humongous 객체는 메모리가 부족해지거나, 더 이상 사용되지 않을 때까지 메모리에서 해제되지 않습니다.
그런데 G1은 어떻게 가장 많은 가비지를 가진 Old region을 파악하고 스캔할 수 있을까요? G1은 remembered set, write barrier 등을 사용해 가장 많은 가비지를 가진 Old region을 찾아낼 수 있습니다.
Write barrier는 JIT 컴파일러나 인터프리터에 의해 참조를 업데이트하는 애플리케이션 코드에 추가되는 코드이며, 이를 통해 G1은 region 간 참조를 파악할 수 있습니다. G1은 write barrier를 사용해 GC 대상이 아닌 참조들(Old -> Old, Old -> Young)을 remembered set이라는 테이블로 관리합니다. 정리하자면, G1은 객체 간의 참조 관계를 저장함으로써 어떤 region이 가장 가비지가 많은지 파악할 수 있습니다.
G1은 parallel, concurrent 하게 동작합니다. Parallel이란 GC를 멀티쓰레드로 수행함을 의미하고, concurrent란 GC 동안 애플리케이션(mutator)이 다른 작업을 수행할 수 있음을 의미합니다. 이로써 G1은 기존의 가비지 컬렉터에 비해 일시 정지 시간이 짧으며, 큰 힙을 효율적으로 관리할 수 있습니다. 하지만 이러한 동작 방식은 애플리케이션이 쓰는 CPU 자원을 지속적으로 점유해 전체적인 throughput을 저하시킬 수 있고, 복잡한 동작을 지원하기 위한 메모리 오버헤드가 발생할 수 있습니다. 따라서, G1은 항상 concurrent하게 동작하지는 않습니다.
