가비지 컬렉션(Garbage Collection, GC)의 이해 - "자동화된 메모리 관리"

 

대부분의 현대적인 프로그래밍 언어는 가비지 컬렉션(Garbage Collection, 쓰레기 수집)을 사용한다. 가비지 컬렉션 알고리즘의 개념을 살펴보고 자바, 파이썬을 포함한 주요 프로그래밍 언어에서 가비지 컬렉션이 구현되는 방법을 알아보자.
일단 가비지 컬렉션 자체의 장단점부터 살펴보자. 가비지 컬렉션이 메모리 할당 오류에 대한 보편적인 해결책인 이유가 무엇일까? C, C++ 등 가비지 컬렉션이 없는 언어에서 메모리 관리가 왜 위험한지부터 시작하자.

C/C++ 메모리 관리의 위험성

메모리 할당 문제는 잠재적인 버그와 취약점을 유발하는, C/C++에서 흔히 발생하는 문제의 일부지만, 그 일부의 비중이 크고 추적해서 수정하기도 까다롭다. 메모리 할당 버그에는 다음과 같은 시나리오가 포함된다.

• 할당했던 메모리를 해제하지 않음. 최종적으로 시스템의 모든 RAM을 사용하고 프로그램뿐만 아니라 컴퓨터 전체가 멈출 수 있다.
• 메모리가 해제된 후 포인터를 통해 버퍼를 읽거나 쓰려고 시도할 때 무작위의 결과가 발생할 수 있다. 이를 댕글링 포인터(dangling pointer)라고도 한다.
• 메모리 블록을 이중으로 해제. 이에 따라 메모리 관리자, 최종적으로는 프로그램 또는 전체 시스템이 멈출 수 있다.

그 외에 일반적인 C/C++ 취약점에는 데이터로 코드를 덮어쓸 수 있는 버퍼 오버런과 문자열 조작이 포함된다. 흥미로운 부분은 공격자가 악성 실행 가능 코드가 되도록 데이터를 만든 후 이 코드를 실행하는 경우다.

즉, 보호된 모드 시스템의 개별적인 코드 및 데이터 세그먼트로 인해 버퍼 오버런과 문자열 조작이 발생하지 않아야 하는데, 일부 상황에서는 여전히 발생 가능하며 실제로 발생한다. 예를 들어 문자열로 SQL 문을 구성한 다음 실행을 위해 데이터베이스로 보내면서 많은 경우 SQL 주입 취약점을 일으키는 프로그램이 있다. 물론 SQL 주입 취약점을 피하기 위한 모범 사례가 있지만 데이터베이스 클라이언트에서 이 같은 범주의 새로운 버그가 계속 발생하는 것을 보면 확실히 모든 프로그래머가 이 모범 사례를 따르는 것은 아니다.

가비지 컬렉션, 결함이 있는 해결책

이때 가비지 컬렉션을 사용하면 주요 메모리 할당 및 할당 해제 문제를 완전히 제거할 수 있다. 하지만 여기에는 대가도 있다. 가장 큰 문제는 가비지 컬렉터의 오버헤드, 가비지 컬렉터가 실행될 때의 예측할 수 없는 멈춤, 서버 프로세스가 멈출 때의 지연 증가 등이다. 특히 마지막 문제는 자바 기반 서버 프로그램에서 자주 발생한다.

가비지 컬렉션의 오버헤드는 상당히 클 수 있으며 메모리와 성능 간의 타협이 필요하다. 매튜 허츠와 에머리 D. 버거의 2005년 논문에는 다음과 같은 내용이 있다.
 
"메모리가 5배 더 많다면 성숙한 비복사 공간이 있는 아펠(Appel)식 세대별 컬렉터의 성능은 도달 가능성 기반의 명시적 메모리 관리의 성능과 대등하다. 메모리가 3배 더 많다면 컬렉터의 실행 성능은 명시적 메모리 관리에 비해 평균 17% 느리다. 메모리가 2배인 경우 가비지 컬렉션의 성능은 70% 가까이 하락한다. 물리적 메모리가 부족하면 페이징으로 인해 가비지 컬렉션의 속도는 명시적 메모리 관리에 비해 훨씬 더 느리게 된다.

아펠식 세대별 수집기는 '보수적인' 가비지 컬렉터다. 더 공격적인 가비지 컬렉터는 적은 메모리에서도 높은 성능을 보인다. 이런 특성은 지연을 최소화해야 하는 실시간 프로그램 및 고처리량 서버에서는 가비지 컬렉터를 지원하는 언어가 적합하지 않을 수 있음을 의미한다. 실제로 그동안 실시간 리스프(Lisp)와 실시간 자바를 구현하려는 노력이 여러 번 있었지만, 모두 가비지 컬렉터를 수정하거나 없앴다.

최근 여러 자바 및 스칼라 서버도 가비지 컬렉터 없는 언어로 다시 작성됐다. C++로 카산드라를 다시 쓴 스킬라(Scylla), 주로 C++로 작성된 카프카 플러그인 대체제인 레드판다(Redpanda)가 대표적이다. 스킬라와 레드판다 모두 원래의 서버에 비해 지연이 비약적으로 줄어들었다. 또한 둘 다 같은 부하에 대해 필요한 클러스터가 훨씬 더 작다.

주요 가비지 컬렉션 알고리즘

가비지 컬렉션 알고리즘은 수십 가지가 있다. 가장 중요한 몇몇 알고리즘과 각각의 주요 특징을 살펴보자.

추적 가비지 컬렉션
추적 가비지 컬렉터(Tracing garbage collector)는 참조 횟수 계산의 단점을 개선한 것으로 다음에 살펴볼 모든 알고리즘과 그 외에도 상당히 많은 알고리즘을 포함한다. 추적 가비지 컬렉션의 핵심 개념은 추적 프로세스가 루트 개체부터 시작하고(예를 들어 현재 지역 변수, 전역 변수 및 현재 함수 매개변수) 참조를 따라가서 어느 개체에 도달할 수 있는지를 확인하는 것이다. 도달할 수 없는 모든 개체는 가비지 컬렉션된다. 추적 가비지 컬렉션은 워낙 보편적이어서 그냥 가비지 컬렉션이라고도 한다.

표시 및 청소
표시 및 청소(Mark and sweep) 알고리즘의 역사를 보면 1960년대 존 매카시와 리스프까지 거슬러 올라간다. 주요 개념은, 먼저 시스템을 동결하고 그다음 루트 집합에서 도달할 수 있는 모든 개체를 “사용 중”으로 표시한다. 세 번째 단계에서는 모든 메모리를 청소하면서 “사용 중”이라고 표시되지 않은 모든 블록을 해제한다. 마지막으로, 다음 수집을 준비하기 위해 나머지 모든 메모리 블록에서 “사용 중”인 비트가 지워지고 시스템이 동작을 재개한다. 당연히 실시간 시스템에는 적합하지 않은 알고리즘이다.

표시 및 청소의 한 변형은 메모리의 3가지 “색”을 사용한다. 흰색 블록은 도달할 수 없는 블록이며 알고리즘이 종료되는 시점에 여전히 흰색 집합에 있다면 해제된다. 검은색 블록은 루트에서 도달 가능하며 흰색 집합의 개체에 대한 나가는 참조가 없다. 회색 블록은 루트에서 도달할 수 있지만 아직 “흰색” 개체에 대한 참조 여부는 확인되지 않았음을 의미한다. 알고리즘이 완료된 후 회색 블록은 모두 검은색 집합에 들어간다. 일반적으로 첫 표시에서는 루트에 의해 참조되는 모든 블록을 회색 집합에, 다른 모든 블록을 흰색 집합에 집어넣는다.

이 3색 변형 알고리즘은 다음 3단계로 구성된다.

1.  회색 집합에서 개체를 선택해 검은색 집합으로 옮긴다.
2. 참조하는 각 흰색 개체를 회색 집합으로 옮긴다. 이 단계를 통해 이 개체나 이 개체가 참조하는 개체는 가비지 컬렉션이 불가능하게 된다.
3. 회색 집합이 빌 때까지 두 단계를 반복한다.

회색 집합이 비면 모든 흰색 블록을 해제할 수 있다. 3색 알고리즘은 프로그램이 실행되는 동안 백그라운드에서 작동한다. 여전히 오버헤드는 있지만 “매우 심각한” 정도는 아니다.

복사 수집
복사 수집(Copying collection, 세미 스페이스 가비지 컬렉터라고도 함)의 전체적인 개념은 메모리를 “from 공간”과 “to 공간”, 2가지 같은 크기 영역으로 분할하는 것이다. to 공간이 모두 찰 때까지 순차적으로 to 공간에 블록을 할당하다가 다 차면 수집을 수행한다. 이렇게 되면 두 영역의 역할이 바뀌고 from 공간에서 to 공간으로 살아 있는 개체가 복사되고 to 공간의 끝에 여유 공간 블록이 남게 된다(도달할 수 없는 모든 개체에 의해 사용되는 메모리에 해당함).

복사 수집에는 몇 가지 문제가 있다. 가장 큰 문제는 블록을 복사할 때 주소가 바뀐다는 점인데, 해결 방법은 포워딩 주소의 테이블을 유지하는 것이다. 또 다른 큰 문제는 복사 수집은 표시 및 청소에 비해 두 배의 메모리가 필요하다는 것이다. 대부분의 메모리가 가비지인 경우 복사 수집이 표시 및 청소보다 빠르지만, 대부분 메모리가 도달 가능한 경우에는 더 느리다.

세대별 수집
세대별 수집(Generational collection)은 개체의 나이, 즉 세대에 따라 힙을 여러 공간(보통 2~3개)으로 분할하는 것이 특징이다. 일반적으로 최근 개체가 오래된 개체에 비해 가비지일 가능성이 높으므로 비교적 새로운 개체에서 가비지를 스캔하고 오래된 개체는 대부분의 시간 동안 그대로 두는 것이 합리적이다. 일부 세대별 수집기는 세대별로 다른 빈도 및 수집 알고리즘을 사용한다.

 

주요 가비지 컬렉션 알고리즘
가비지 컬렉션 알고리즘은 수십 가지가 있다. 가장 중요한 몇몇 알고리즘과 각각의 주요 특징을 살펴보자.

참조 횟수 계산
참조 횟수 계산(Reference counting)에서 프로그램은 할당된 리소스의 일부 리소스에 대한 참조, 포인터 또는 핸들의 수를 저장하고, 참조가 추가되거나 제거됨에 따라 이 수를 늘리거나 줄인다. 참조 횟수가 0에 도달하면 리소스를 해제할 수 있다. 메모리 가비지 컬렉션은 참조 횟수 계산의 여러 응용 중 하나일 뿐이고 그 외에 시스템 개체, 윈도우 COM 개체, 파일 시스템 블록 또는 파일의 할당 해제를 제어하는 데도 사용된다.

참조 횟수 계산의 두 가지 큰 단점은 과도하게 빈번한 업데이트와 순환 참조다. 업데이트 빈도를 제어하는 한 가지 방법은 컴파일러가 관련된 개체를 일괄 처리하도록 허용하는 것이다. 또한 수가 영원히 0에 도달하지 못하는 순환 참조를 처리하는 해법은 이따금 추적 가비지 컬렉터를 실행해 도달할 수 없는 주기를 제거하는 방법이 있다.

추적 가비지 컬렉션
추적 가비지 컬렉터(Tracing garbage collector)는 참조 횟수 계산의 단점을 개선한 것으로 다음에 살펴볼 모든 알고리즘과 그 외에도 상당히 많은 알고리즘을 포함한다. 추적 가비지 컬렉션의 핵심 개념은 추적 프로세스가 루트 개체부터 시작하고(예를 들어 현재 지역 변수, 전역 변수 및 현재 함수 매개변수) 참조를 따라가서 어느 개체에 도달할 수 있는지를 확인하는 것이다. 도달할 수 없는 모든 개체는 가비지 컬렉션된다. 추적 가비지 컬렉션은 워낙 보편적이어서 그냥 가비지 컬렉션이라고도 한다.

표시 및 청소의 한 변형은 메모리의 3가지 “색”을 사용한다. 흰색 블록은 도달할 수 없는 블록이며 알고리즘이 종료되는 시점에 여전히 흰색 집합에 있다면 해제된다. 검은색 블록은 루트에서 도달 가능하며 흰색 집합의 개체에 대한 나가는 참조가 없다. 회색 블록은 루트에서 도달할 수 있지만 아직 “흰색” 개체에 대한 참조 여부는 확인되지 않았음을 의미한다. 알고리즘이 완료된 후 회색 블록은 모두 검은색 집합에 들어간다. 일반적으로 첫 표시에서는 루트에 의해 참조되는 모든 블록을 회색 집합에, 다른 모든 블록을 흰색 집합에 집어넣는다.

이 3색 변형 알고리즘은 다음 3단계로 구성된다.
 
회색 집합에서 개체를 선택해 검은색 집합으로 옮긴다.
참조하는 각 흰색 개체를 회색 집합으로 옮긴다. 이 단계를 통해 이 개체나 이 개체가 참조하는 개체는 가비지 컬렉션이 불가능하게 된다.
회색 집합이 빌 때까지 두 단계를 반복한다.

회색 집합이 비면 모든 흰색 블록을 해제할 수 있다. 3색 알고리즘은 프로그램이 실행되는 동안 백그라운드에서 작동한다. 여전히 오버헤드는 있지만 “매우 심각한” 정도는 아니다.

복사 수집
복사 수집(Copying collection, 세미 스페이스 가비지 컬렉터라고도 함)의 전체적인 개념은 메모리를 “from 공간”과 “to 공간”, 2가지 같은 크기 영역으로 분할하는 것이다. to 공간이 모두 찰 때까지 순차적으로 to 공간에 블록을 할당하다가 다 차면 수집을 수행한다. 이렇게 되면 두 영역의 역할이 바뀌고 from 공간에서 to 공간으로 살아 있는 개체가 복사되고 to 공간의 끝에 여유 공간 블록이 남게 된다(도달할 수 없는 모든 개체에 의해 사용되는 메모리에 해당함).

복사 수집에는 몇 가지 문제가 있다. 가장 큰 문제는 블록을 복사할 때 주소가 바뀐다는 점인데, 해결 방법은 포워딩 주소의 테이블을 유지하는 것이다. 또 다른 큰 문제는 복사 수집은 표시 및 청소에 비해 두 배의 메모리가 필요하다는 것이다. 대부분의 메모리가 가비지인 경우 복사 수집이 표시 및 청소보다 빠르지만, 대부분 메모리가 도달 가능한 경우에는 더 느리다.

표시 및 압축
표시 및 압축(Mark and compact) 수집은 단일 메모리 공간 내에서 실행되는 복사 수집이다. 표시 및 압축 수집기는 도달 가능한 모든 개체를 스캔해 힙 아래쪽에 압축하고 그 결과 힙의 상단은 사용이 가능한 상태가 된다. 표시 및 압축 수집의 가장 큰 단점은 소요 시간이다.

세대별 수집
세대별 수집(Generational collection)은 개체의 나이, 즉 세대에 따라 힙을 여러 공간(보통 2~3개)으로 분할하는 것이 특징이다. 일반적으로 최근 개체가 오래된 개체에 비해 가비지일 가능성이 높으므로 비교적 새로운 개체에서 가비지를 스캔하고 오래된 개체는 대부분의 시간 동안 그대로 두는 것이 합리적이다. 일부 세대별 수집기는 세대별로 다른 빈도 및 수집 알고리즘을 사용한다.
 
가비지 컬렉션을 사용하는 언어들
리스프는 존 매카시가 1958년 처음 고안했을 때부터 가비지 컬렉션을 사용했다. 자바, 스칼라, 파이썬, 닷넷/C#은 모두 인기 있는 가비지 컬렉터 언어다. 그 외에 비교적 신생 언어인 고, 루비, D, OCaml, 스위프트, 그리고 오래된 언어인 에펠, 하스켈, ML, 모듈러-3, 펄, 프롤로그, 스킴, 스몰토크 등도 가비지 언어에 포함된다.

자바, 파이썬, 닷넷/C#은 가비지 컬렉션을 구현하는 언어 중에서 가장 인기 있는 프로그래밍 언어다. 자바 가상 머신(JVM)은 실제로 직렬, 병렬, 동시 표시 및 청소, G1GC(가비지 우선 가비지 컬렉터) 등 4가지의 가비지 컬렉터를 제공한다. G1GC는 현재 자바의 기본 가비지 컬렉터로, 소프트한 실시간 목표를 달성하는 지역화된 세대별 병렬 압축 수집기다.

파이썬, 구체적으로 표준 C파이썬 구현은 컨테이너 개체를 청소하는 데만 집중하는 3레벨 세대별 수집과 참조 횟수 계산을 결합해 사용한다. 닷넷 CLR(공통 언어 런타임)은 3레벨 세대별 표시 및 압축 수집 알고리즘을 사용한다. 또한 CLR은 메모리 개체를 큰 개체(85,000바이트 이상)와 작은 개체용, 2개의 힙으로 분리한다. 큰 개체 힙은 일반적으로 압축되지 않고 표시 및 청소만 되지만 필요하다면 압축도 가능하다.

가비지 컬렉션을 사용하는 언어들

리스프는 존 매카시가 1958년 처음 고안했을 때부터 가비지 컬렉션을 사용했다. 자바, 스칼라, 파이썬, 닷넷/C#은 모두 인기 있는 가비지 컬렉터 언어다. 그 외에 비교적 신생 언어인 고, 루비, D, OCaml, 스위프트, 그리고 오래된 언어인 에펠, 하스켈, ML, 모듈러-3, 펄, 프롤로그, 스킴, 스몰토크 등도 가비지 언어에 포함된다.

자바, 파이썬, 닷넷/C#은 가비지 컬렉션을 구현하는 언어 중에서 가장 인기 있는 프로그래밍 언어다. 자바 가상 머신(JVM)은 실제로 직렬, 병렬, 동시 표시 및 청소, G1GC(가비지 우선 가비지 컬렉터) 등 4가지의 가비지 컬렉터를 제공한다. G1GC는 현재 자바의 기본 가비지 컬렉터로, 소프트한 실시간 목표를 달성하는 지역화된 세대별 병렬 압축 수집기다.

파이썬, 구체적으로 표준 C파이썬 구현은 컨테이너 개체를 청소하는 데만 집중하는 3레벨 세대별 수집과 참조 횟수 계산을 결합해 사용한다. 닷넷 CLR(공통 언어 런타임)은 3레벨 세대별 표시 및 압축 수집 알고리즘을 사용한다. 또한 CLR은 메모리 개체를 큰 개체(85,000바이트 이상)와 작은 개체용, 2개의 힙으로 분리한다. 큰 개체 힙은 일반적으로 압축되지 않고 표시 및 청소만 되지만 필요하다면 압축도 가능하다.