Go garbage collection

golang에서 garbage collection이 일어나는 시점과 작동 원리에 대해 알아보고 정리해두고자 한다.

[참고 문서]

https://tip.golang.org/doc/gc-guide

https://changhoi.kim/posts/go/go-gc/

A Guide to the Go Garbage Collector - The Go Programming Language

Garbage Collector

C언어와 C++에서는 메모리를 동적으로 할당해주었으면, 반드시 해제하는 작업이 필요하다. 만약 메모리를 해제하지 않고 프로그램을 종료한다면 메모리 누수가 발생하게 된다.

반면 가비지 컬렉터가 있는 JAVA의 경우 new 로 선언한 변수를 명시적으로 해제하지 않아도 적절한 타이밍에 자동으로 해제된다.

가비지 컬렉터의 핵심은 “Stop the World”이다. Garbage Collecting 시간 동안 GC 쓰레드를 제외한 모든 스레드를 정지시키고, GC는 참조할 수 없는 객체에 대한 메모리를 해제한다. GC가 끝난 후에 일시정지되었던 스레드의 작업들이 재개된다. 이러한 특성 때문에 GC가 편리하기는 하지만 성능을 떨어뜨릴 우려가 있다. 따라서 적절히 튜닝하는 작업이 필요하다.

How does it work?

GC에 대해 더 알아보기 전에, GC에 의해 관리되지 않는 타입의 메모리가 있다.

Non-pointer인 로컬 변수들은 GC에 의해서 관리되지 않는다. 대신, 생성된 lexical scope 내에서 관리한다. GC에 의존해서 관리되는 것보다 호출 stack 에서 관리하는 것이 더 편리하기 때문이다.

Go compiler가 lifetime을 알 수 없는 변수들은 heap에 저장되게 된다. 이들은 동적 메모리 할당이라고 불리는데, 그 이유는 컴파일러와 런타임이 이 메모리가 어떻게 쓰이고 언제 clean up되어야 하는지 거의 모르기 때문이다. 동적 할당된 메모리를 clean up 하기 위해 GC가 필요하다.

Garbage collection은 reference counting과 같이 다양한 방법으로 진행된다. Golang에서는 garbage collection은 tracing 방식으로 동작한다. Object와 Object를 가리키는 Pointer는 object graph를 형성하게 된다. Active한 메모리를 찾기 위해 root에서 시작해서 object graph를 탐색해 가면서 메모리가 살아있는지 찾아낸다. 이때, root가 될 수 있는 대상은 local variable과 global variable이다.

Go에서는 mark-sweep 알고리즘을 사용한다. GC는 object graph를 탐색하면서 살아있는 value를 “mark”하고 tracing이 끝나면 heap에 존재하는 모든 메모리를 다시 순회하면서 마킹되지 않은 메모리를 해제(a.k.a ”sweep”)한다.

Tri-color marking

Go에서는 Tri-color marking를 사용해서 마크 스윕 알고리즘을 동작시킨다. 3개의 set이 생성된다: white, black, grey.

• white set은 recycle될 object의 후보이다.
• black set은 root에서부터 도달할 수 있고,스캔이 완료된 오브젝트이다.
• grey set은 root에서 도달 가능하지만 아직 스캔이 되지 않은 오브젝트이다.

Black set을 empty로, grey set을 root에서 직접 참조 가능한 오브젝트, white set을 그 이외의 모든 오브젝트인 상태로 시작한다. 모든 object는 3개의 set 중에 속해야 한다. 알고리즘은 다음 순서대로 진행된다.

1. Grey set에서 오브젝트를 골라 Black set으로 옮긴다.
2. Grey set으로 referencing하는 white object를 grey set으로 옮긴다.
3. 1, 2번을 grey set이 빌 때까지 반복한다.

최종적으로 grey set이 비면 scan은 끝난다. Black object는 root에서 도달 가능한 오브젝트이고, white는 root에서 도달 불가능하기 때문에 garbage-collect될 대상이다.

More details…

Golang 소스 코드에 있는 mgc.go 파일에 있는 주석을 참고했다. Go는 non-generational, non-compacting한 알고리즘을 사용한다.

1. GC는 sweep termination을 수행한다.
   1. Stop the world. 모든 P를 GC safe-point로 이동시킨다.
2. GC는 mark phase를 수행한다.
   1. write barrier를 enable한다.
   2. Start the world. 새로 할당된 object는 black으로 마킹된다.
   3. root marking 작업을 수행한다. 모든 stack, global 변수, heap pointer 등을 포함한다. Stack scanning은 goroutine을 잠시 중단하고, stack의 포인터들을 찾아낸 후 goroutine을 재개한다.
   4. Grey object를 scan해서 그와 연결된 pointer들을 black으로 마킹한다.
3. GC는 mark termination phase를 수행한다.
   1. Stop the world
   2. 불필요한 메모리를 종료한다.
4. GC는 sweep phase를 수행한다.
   1. write barrier를 disable한다.
   2. Start the world. 여기서부터 새로 할당된 오브젝트는 white이다.
5. 충분한 allocation이 이루어지면 다시 1번부터 수행한다. GC rate과 관련이 있다. 만약 GOGC=100이고 4M를 사용하고 있다면, GC는 8M가 되었을 때 다시 수행한다.