[Go] GC의 구조

Go는 바이너리를 내뱉는 네이티브 언어임에도 GC가 달린 꽤 특이한 입지의 언어다.

근데 아직 Java 같은 고참들에 비하면 GC 자체의 성숙도가 낮은 상태이긴 하다.
애초에 메모리 사용량이 극단적으로 높은 메인프레임에 쓰이기보단 자잘한 보조도구에 더 많이 쓰이는게 현실이다보니, 문제가 덜 튀기도 하는 것 같다.

그래도 가볍게 쓰는 수준에서는 큰 문제가 없고, 계속해서 발전하고는 있다.

전반적인 Go GC의 구조는 1.5 버전부터 어느 정도 완성되었고, 그 이후로는 일반적인 개선만 이루어지고 있다.

Go가 어떤 매커니즘으로 GC를 처리하고, 어떤 장점과 한계가 있는지 정리해보겠다.

이쪽 업계 선배인 Java와도 비교해보면 좋을 것이다.
https://m.blog.naver.com/sssang97/223575258532
본 포스트에서도 Java의 GC와 비교하면서 Go만이 갖고 있는 특징과 장단점을 정리해본다.

Basic: Mark and Sweep 알고리즘

현대 GC의 근간이 된 기법 중 하나다.
1960년에 리습의 창시자 매카시가 만들었다.

https://m.blog.naver.com/sssang97/221567636644

Java에서도 몇몇 GC 기법은 마크앤 스윕 기반으로 만들어졌으나 퇴출된 모양새고, Go는 지금도 이걸 쓴다.

루트객체들부터 한바퀴 뺑 돌면서 참조되고 있는지를 체크하고, 참조되지 않은걸 싹 지워버린다는 간단한 방법이다.

구현하기에는 편리하지만 단점이 많아서 자바는 이 구조를 거의 버렸다.

매 GC 타임마다 모든 객체를 풀스캔하면서 찍고, 또 풀스캔하면서 지워야 하기 때문에 메모리가 커지면 감당이 잘 안된다는게 단점이다.

게다가 메모리 파편화도 심하다. 그냥 일단 지우고 보는게 최종 목적이기 때문에 파편화를 해결하려면 조각모음을 또 추가로 수행해야 한다.

메모리 파편화가 누적될수록 연속된 큰 공간이 없어져서 빈 공간을 찾기도 힘들고, 추가적인 정리작업이 필요해질 수도 있기 때문이다.

Now: Concurrent Mark and Sweep

Go는 Mark and Sweep의 변형인 Concurrent Mark and Sweep(CMS)을 기본 GC 알고리즘으로 사용한다.

이건 사실 자바가 진작에 폐기한 CMS와 접근법이 비스무리하다. 세부 구현에서 차이가 있기는 하지만 말이다.

GC를 수행하는 스레드와 애플리케이션의 유저스레드가 거의 동시적으로 처리된다고 해서 Concurrent라고 하는 것이다.

Now: tri-color Mark and Sweep

Go는 마크앤스윕을 증분적으로(incremental) 처리한다. 그런 목적으로 위해 응용되는 원리가 3색 마크앤스윕이다.

만물상 다익스트라가 1978년에 고안했고 Go 1.5부터 도입됐다.

일반적인 마크앤스윕은 mark 과정과 sweep 과정을 처리할때 Stop The World를 때려야 한다.

하지만 Go CMS에서는 정지시간을 최소화한 채로 GC와 유저스레드가 동시에 실행된다.

근데 이러면 GC가 실행되는 도중에도 새로운 메모리가 할당될 수 있다는 문제점이 생긴다. 도중에 끼어든 메모리는 당연히 GC 대상으로 잡히지 않을 것이고, 누수가 될 수 있다.

이걸 완화하기 위한 방법론이 3색(tri-color) 마크앤스윕이다.

단순한 마크앤스윕은 "marked=false"와 "marked=true" 2개의 색상만 존재하지만, GoGC는 한가지의 색상을 더 추가한다.

흰색(제거대상), 검은색(생존), 회색(?)이다.
회색은 "스캔되지는 않았지만 삭제할 수도 없음"을 뜻한다.

https://blog.stackademic.com/basics-of-golang-gc-explained-tri-color-mark-and-sweep-and-stop-the-world-cc832f99164c

3색 CMS에서는 다음과 같은 스텝으로 GC를 처리한다.

1. 루트 객체를 모두 회색으로 칠한다.
2. 회색을 검은색으로 칠하고, 흰색을 가리키고 있는게 있는지 확인한다.
3. 가리키고 있는 대상중 흰색이 발견되면 회색으로 칠한다.
4. 회색이 전부 사라질때까지 2-3을 반복
5. 흰색을 전부 삭제한다.

GC를 실행하는 도중에 끼어든 객체들도 일단 회색 객체로 할당하고, 회색이 있으면 다시 GC 싸이클을 도는 것이다.

도중에 회색 객체가 생기면 생기는대로 뺑뺑이 돌려서 처리하니, 각각의 Stop the World 시간은 짧지만 GC의 사이클 자체는 더 길어지는 문제가 있다. 그래서 메모리 해제가 좀 지연될 수도 있다.

footprint를 희생하는 대신 평균적인 정지시간(latency)을 최소화하는 구조다.

GC로 인한 지연시간이 최대 10ms라고 자랑하는 것도, GC가 짧아서가 아니라 찔끔찔끔 끊어서 처리해서 가능한 것이다. GC 완료에 소요되는 시간 자체는 길다.

Diff: 세대별 GC 없음

여타 GC 시스템들은 세대 이론에 입각해서 "확률적으로 금방 삭제될 객체들이 모여있는" 신세대 영역과 "오래 생존할 객체들이 모여있는" 구세대 영역으로 메모리를 분리해서 관리한다.
그리고 실제로도 다년간 증명된 방법이다.

이를 통해서 메모리 파편화 문제와 GC 성능을 효과적으로 최적화할 수 있었다.

하지만 Go는 세대별 이론을 도입하지 않고 자신만의 길을 걷고 있다.
향후에는 어떨지 모르지만, 지금은 없다.
Go 개발진들도 넣지 않을거라는 단언을 하지는 않고 "실험이 필요한" 부분이라고 유예하고 있다.

아마 일단은 GC 구조를 간단하고 가볍게 유지하려는 목적이 큰거같다.

Go는 대신 세대별 이론에서 나오는 "수명이 짧은 객체"를 힙 대신 스택에 할당하는 꼼수로 잦은 할당&해제로 인한 부하를 감소시킨다. 이걸 escape analysis라고 부른다.
그래서 Go에서는 동적할당을 하더라도 스택에 할당될 가능성이 있다.

근데 이게 모든걸 커버하는건 아니라서 Java보다 뒤떨어지는건 맞다. 할당 관련해서는 그냥 효율적인 형태로 짜라고 권유하면서 사용자 책임으로 떠넘기는 경향이 있다.

Basic: Escape Analysis

동적 객체 할당은 스택 기반의 지역변수보다 생존주기가 자유롭다는 점에서 수집 시점을 잡아내기가 까다롭다.

하지만 동적할당도 코드 패턴에 따라서는 해제 시점이 명확하게 드러날 때가 있다.
그런 경우를 정적분석으로 최적화하는걸 Escape 분석이라고 말한다.

예를 들어 다음 코드는 동적 할당이 포함되지만

void Function() {
** var obj = new Something();**
** **** // ...******
** return**
}

obj가 사실상 저 함수 종료 시점에 날라간다는게 명확하다. 따라서 Escape 대상에 들어가고, 동적할당이 아닌 스택 할당으로 최적화된다.

반면 다음과 같은 코드는

Something Function() {
** var obj = new Something();**
** **** // ...******
** return obj**
}

객체가 함수 흐름 밖으로 전이되기에 객체의 생존주기를 예측할 수 없다. 이건 최적화할 수 없다.
그냥 힙에 들어간다.

참고로 이건 Go에만 사용되는건 아니고, Java 같은 다른 언어들도 공통적으로 쓰는 최적화 기법이다.

Diff: 메모리 컴팩션 없음

GC를 통해 쓰레기 객체를 잘 정리하더라도, 공간이 듬성듬성 떠서 누더기가 되는 것을 메모리 파편화라고 한다.

GoGC 자체는 메모리 컴팩션을 배제한 채로 구현되어있다.
대신 allocator를 건드리는 것으로 에둘러서 문제를 회피한다.

New: TCMalloc

Go는 TCMalloc이라고 부르는 메모리 Pool 기반 allocator를 통해서 메모리 파편화로 발생하는 문제를 완화한다.
이건 사실 Go 전용 allocator는 아니고, C/C++용으로 만들었던 범용이다.

메모리 파편화 문제가 없다는 주장도 있는데, 그건 과장이고 있기는 있다. 이슈 들어가보면 이런저런 볼멘소리가 많다.

TCMalloc은 내부적으로 꽤 복잡한 레이어를 가진다.

https://google.github.io/tcmalloc/design.html
백엔드, 미들엔드, 프론트엔드다.
백엔드는 OS에서 직접 메모리를 할당해오고, 미들엔드는 할당해온 메모리를 적절히 관리한다.

그리고 프론트엔드는 모아놓은 메모리를 빠르게 프로그램에 나눠준다.
효율적인 메모리 배치를 위해 메모리 크기를 60가지의 클래스로 매우 세분화해서 관리한다. 이것으로 메모리 파편화 문제를 줄인다.

문제

근데 문제는, tcmalloc이 해결한다고 주장하는 장점들은 결국 다 메모리를 희생해서 얻는 거란 것이다.
tcmalloc이 그렇게 엄청나고 완벽하면 다른 언어들도 다 allocator를 tcmalloc으로 썼을 것이다. 다른 언어 개발자들이 바보라서 안썼겠는가?

tcmalloc은 할당 최적화를 위해서 GC 런타임처럼 직접 메모리 풀을 갖고서 동작한다. 그 말인즉, 할당을 해도 바로 OS에 반환되지 않는다는 것이다.

GoGC 자체에서도 메모리풀을 들고서 메모리를 관리하는데, 메모리풀에 메모리를 할당할 때도 tcmalloc 내에서 메모리풀을 또 들고있으니 사실상 Go는 메모리풀이 2단계로 존재하는 셈이다.
내가 알기로 다른 GC 언어들중에 이런건 딱히 없다.

당연히 메모리가 더 게으르게 해제되니 더 줄줄 새고, GoGC에서 아무리 메모리를 반환하더라도 tcmalloc에서 OS에 메모리를 반환하지 않으면 부유물처럼 뜨는 문제가 발생한다.

게다가 통상적으로 tcmalloc은 기본 allocator에 비해 최대 2~3배까지도 메모리를 폭식할 수 있다.

그래서 실제로도 Go로 메모리 할당/해제가 빈번한 프로그램을 돌리면 실제 사용 메모리의 몇배를 넘게도 쓰레기가 남아서 공간을 차지하는 현상이 굉장히 흔하게 발생한다.
low-latency라는 명목 하에 gc 자체를 매우 게으르게 처리하는데, 메모리 관리가 2단계라 할당해제가 더딘거까지 합쳐져서 생기는 불협화음이다.

사실 이건 문제를 해결한다기보단 책임을 회피한 것에 가까워보이는 기술 결정인 것 같다.

그래서 나는 메모리 압력이 심한 사례에서는 아직 Go가 부적절하다고 본다.
CPU 집약적인 경우라면 추천할만하지만, 메모리 집약적인 경우라면 추천하지 않는다.

참조
https://engineering.linecorp.com/ko/blog/go-gc
https://stackoverflow.com/questions/43995901/why-golang-garbage-collector-not-implement-generational-and-compact-gc
https://velog.io/@hyeok3011/Golang-GC
https://go.dev/blog/ismmkeynote
https://google.github.io/tcmalloc/design.html
https://groups.google.com/g/golang-nuts/c/KJiyv2mV2pU
https://blog.stackademic.com/basics-of-golang-gc-explained-tri-color-mark-and-sweep-and-stop-the-world-cc832f99164c
https://www.google.com/search?q=escape+analysis&client=ms-android-samsung-ss&sourceid=chrome-mobile&ie=UTF-8
https://google.github.io/tcmalloc/overview.html
https://github.com/gperftools/gperftools/issues/756