Trash talk: the Orinoco garbage collector(한글)

이 글은 아래 원문을 번역한 글로 의역이 있을 수 있습니다. 정확한 의미를 파악하고 싶으신 분은 원문을 참고해주시기 바랍니다.

 

원문: https://v8.dev/blog/trash-talk

저작권 정보: https://v8.dev/terms#site-policies

---

휴지통 이야기: 오리노코 가비지 컬렉터

V8 가비지 컬렉터(GC)는 지난 몇 년 동안 많은 변화가 있었습니다. 오리노코 프로젝트는 가비지 컬렉터를 순차적인 STW(stop-the-world) 방식에서 병렬적인 concurrent(동시에 공존하는) 방식으로 바꿨습니다.

참고) STW/Concurrent garbage collector

 

모든 가비지 컬렉터에는 주기적으로 수행해야 하는 필수 작업이 몇 가지 있습니다.

 

1. 활성(live)/비활성(dead) 객체 확인

2. 비활성 객체가 사용하는 메모리 재활용/재사용

3. 메모리 압축/조각 모음 (옵션)

주 가비지 컬렉터(Major GC)(Full Mark-Compact, 전체 표시-압축)

주 가비지 컬렉터는 힙 전체에서 가비지 컬렉팅을 수행합니다.

주 가비지 컬렉터는 표시, 스위핑, 압축 세 단계로 이루어집니다.

표시 단계(Marking)

가비지 컬렉터에서 필수적인 기능은 어떤 객체를 수집할 수 있는지 파악하는 것입니다. 가비지 컬렉터는 'liveness'의 대용으로 도달 가능성을 사용하여 이 작업을 수행합니다. 즉, 런타임 내에 현재 도달할 수 있는 객체는 모두 유지될 것이고, 도달할 수 없는 객체는 모두 수집될 것입니다.

 

표시 단계는 도달할 수 있는 객체를 찾는 과정입니다. 가비지 컬렉터는 root set이라 불리는 알려진 객체 포인터 집합에서 시작합니다. 여기에는 실행 스택(execution stack)과 전역 객체가 포함됩니다. 가비지 컬렉터는 root set의 각 포인터를 따라 자바스크립트 객체로 이동하여 도달 가능한 객체로 표시합니다. 그런 다음 그 객체 안의 모든 포인터를 따라가면서, 런타임에 도달할 수 있는 객체를 모두 찾아 표시할 때까지 이 과정을 재귀적으로 계속합니다.

스위핑 단계(Sweeping)

스위핑 단계는 비활성 객체에 의해 남겨진 메모리의 틈(gaps)을 free-list에 추가하는 과정입니다. 표시 단계가 완료되면, 가비지 컬렉터는 도달할 수 없는 객체에 의해 남겨진 인접한 틈들을 찾아 적절한 free-list에 추가합니다. Free-list는 검색을 빠르게 하기 위해 메모리 청크의 크기로 구분됩니다. 나중에 우리가 메모리를 할당하고 싶을 때, 우리는 그냥 free-list를 보고 적절한 크기의 메모리 청크를 찾으면 됩니다.

압축 단계(Compaction)

주 가비지 컬렉터는 단편화 휴리스틱에 기초하여 일부 페이지를 제거/압축합니다. 오래된 PC의 하드디스크 조각 모음과 비슷하게 생각하면 됩니다. 가비지 컬렉터는 활성 객체를 현재 압축되어 있지 않은 다른 페이지로 복사합니다(해당 페이지의 free-list를 사용합니다). 그러면 우리는 비활성 객체가 남긴 메모리의 작고 흩어진 틈들을 사용할 수 있습니다. 활성 객체를 복사하는 방법의 약점은, 만약 오래 사는 객체를 많이 할당하면 이런 객체들을 복사하는데 많은 비용이 든다는 것입니다. 그렇기 때문에 우리는 고도로 단편화된 일부 페이지만 압축하고 나머지 페이지는 스윕 단계만 수행합니다. 스윕 단계에서는 살아남은 객체를 복사하지 않습니다.

세대 레이아웃(Generational Layout)

V8의 힙은 generation라고 하는 다른 영역으로 나누어져 있습니다. young generation(다시 'nursery'와 'intermediate'로 나뉩니다)과 old generation입니다. 객체는 처음에 nursery에 할당됩니다. 만약 다음 가비지 컬렉팅 때 살아남으면, 그 객체는 young generation의 intermediate로 옮겨집니다. 그리고 그다음 가비지 컬렉팅에서도 살아남으면, 그 객체는 old generation으로 옮겨집니다.

V8의 힙은 generation으로 분리됩니다. 객체들은 가비지 컬렉팅에서 살아남을 때 generation에서 generation으로 옮겨집니다.

가비지 컬렉션에는 "The Generational Hypothesis"라는 격언이 있습니다. 이는 기본적으로 모든 객체는 젊을 때 죽는다는 것을 말합니다. 다시 말해, 가비지 컬렉터의 관점에서 대부분의 객체는 할당되고 거의 바로 도달할 수 없게 됩니다. 이것은 V8이나 JavaScript 뿐만 아니라 대부분의 동적 언어에 적용되는 이야기입니다.

 

V8의 generational 힙 레이아웃은 이런 객체 수명에 대한 사실을 활용하도록 설계되었습니다. 가비지 컬렉터는 압축/이동 가비지 컬렉터로 가비지 컬렉팅에서 살아남은 객체를 옮깁니다. 객체를 복사하는 것은 많은 비용이 들기 때문에 이는 직관적으로 와닿지 않습니다. 그러나 "The Generational Hypothesis"에 따르면 가비지 컬렉팅에서 실제로 살아남는 객체는 극소수라는 것을 알 수 있습니다. 살아남은 객체만 옮김으로써 다른 모든 할당된 메모리는 '암묵적'으로 쓰레기가 됩니다. 즉, 우리는 살아남은 객체의 수만큼의 비용(복사 비용)만 지불하고, 할당한 모든 객체만큼의 비용은 지불하지 않습니다.

부 가비지 컬렉터(Minor GC)(Scavenger)

V8에는 가비지 컬렉터가 2개 있습니다. 주 가비지 컬렉터(Major GC, Mark-Compact)는 전체 힙에서 가비지 컬렉팅을 수행합니다. 부 가비지 컬렉터(Minor GC, Scavenger)는 young generation 내에서 가비지 컬렉팅을 수행합니다. 주 가비지 컬렉터는 전체 힙에서 가비지 컬렉팅을 하는데 효과적이지만, "The Generational Hypothesis"에 따르면 새로 할당된 객체가 가비지 컬렉팅이 될 가능성이 높다는 것을 알 수 있습니다.

 

young generation에서만 가비지 컬렉팅을 하는 Scavenger는 활성 객체를 새로운 페이지로 이동(evacuation)시킵니다. V8은 young generation에 'semi-space' 디자인을 사용합니다. 이는 이동 과정을 하기 위해 전체 공간의 반은 항상 비워두는 것을 의미합니다. 부 가비지 컬렝팅이 실행될 때, 초기에 비어있는 공간을 'To-Space'라고 부르고, 복사해온 공간을 'From-Space'라고 부릅니다. 최악의 경우에 모든 객체가 살아남으면 모든 객체를 복사해야 합니다.

 

Scavenger를 위해 old-to-new 참조를 표시하는 추가적인 root set을 갖습니다. old-space에 있는 포인터들은 young generation에 있는 객체를 가리킵니다. Scavenger에서는 전체 힙을 추적하는 대신, write barriers를 이용하여 old-to-new 참조를 유지합니다. 스택과 글로벌을 결합할 때, 우리는 old generation 전체를 추적하지 않아도 young generation에 대한 참조를 모두 알 수 있습니다.

 

이동(evacuation) 단계는 모든 활성 객체들을 (페이지 내에 있는) 연속적인 메모리 chunk로 옮깁니다. 이렇게 하면 단편화(비활성 객체들이 남긴 틈)를 제거할 수 있습니다. 그런 다음 우리는 두 공간을 바꿉니다(switch). 즉, 'To-Space'는 'From-Space'가 되고, 'From-Space'는 'To-Space'가 됩니다. 가비지 컬렉팅이 완료되면, 새로운 할당은 'From-Space'의 free address에 수행됩니다.

Scavenger는 활성 객체를 새로운 페이지로 이동시킵니다.

우리는 이 전략 하나로 young generation 영역을 빠르게 정리합니다. 두 번의 가비지 컬렉팅에서 살아남은 객체들은 'To-Space' 대신 old generation으로 이동됩니다.

 

Scavenging의 마지막의 단계는 이동된 객체의 참조 포인터를 업데이트하는 것입니다. 복사된 모든 객체는 포인터가 가리킬 새 위치의 주소를 남깁니다.

Scavenger는 'intermediate'에 있는 객체를 old generation으로, 'nursery'에 있는 객체를 새로운 페이지로 이동시킵니다.

Scavenger는 표시(marking), 이동(evacuating), 그리고 포인터 업데이트(pointer-updating) 세 단계를 수행합니다 - 각 단계는 별개의 단계라기보다는 차례로 수행되는 단계입니다(interleaved).

오리노코(Orinoco)

이런 알고리즘과 최적화 기법의 대부분은 가비지 컬렉터 문서에서 흔히 볼 수 있고, 가비지 컬렉팅을 하는 많은 언어들에서 찾아볼 수 있습니다. 그러나 최신 가비지 컬렉터은 많은 발전을 이뤘습니다. 가비지 컬렉팅에 소요되는 시간을 측정하는 중요한 지표 중에 하나는 가비지 컬렉팅이 수행되는 동안 메인 스레드가 중단되어있는 시간입니다. 기존의 'stop-the-world' 가비지 컬렉터에서는 이 시간이 실제로 늘어날 수 있고, 가비지 컬렉팅이 수행되는 동안 페이지가 버벅거리거나 렌더링이 지연되어 사용자 경험이 직접적으로 저해됩니다.

V8 가비지 컬렉터, Orinoco의 로고

오리노코(Orinoco)는 가비지 컬렉터 프로젝트의 코드명으로, 메인 스레드를 자유롭게 만들기 위해 가비지 컬렉팅에 최신 parellel(병렬), incremental(점증), concurrent(동시에 공존하는) 기술을 사용합니다. 가비지 컬렉터 맥락에서 특별한 의미를 갖는 용어들의 정의를 자세히 살펴보겠습니다.

Parellel

병렬(Parellel)은 메인 스레드와 헬퍼 스레드가 동시에 거의 동일한 양의 일을 하는 것입니다. 이것은 여전히 'stop-the-world' 방식이지만, 총 중단 시간이 참여하는 스레드(동기화를 위한 일부 오버헤드 포함)의 숫자만큼 나눠집니다. 세 가지 기술 중 가장 쉬운 기술입니다. 실행 중인 자바스크립트가 없으므로 자바스크립트 힙은 일시 중단되고, 각 헬퍼 스레드는 다른 헬퍼 스레드가 접근하길 원할 수도 있는 객체에 대한 접근을 동기화하기만 하면 됩니다.

메인 스레드와 헬퍼 스레드는 동시에 같은 작업을 수행합니다.

Incremental

증분(Incremental)은 메인 스레드가 적은 양의 작업을 간헐적으로 실행하여 가비지 컬렉팅 작업을 점진적으로 완료해나가는 것입니다. 메인 스레드를 일시 정지하고 가비지 컬렉팅 전 과정을 진행하는 것이 아니라 전체 작업 중 일부만 진행합니다. 각각의 점진적인 작업 사이에 자바스크립트가 실행될 수 있기 때문에, 즉 힙의 상태가 변경될 수 있어 이전에 해놓은 작업이 무효화될 수 있기 때문에 좀 더 어려운 기술입니다. 그림에서 볼 수 있듯이, 이렇게 하면 메인 스레드에서 소요되는 시간이 줄어들지 않고(보통 약간 증가함) 시간이 지나면서 분산됩니다. 이는 기존에 문제였던 메인 스레드의 지연 시간을 해결할 수 있는 좋은 기술입니다. 가비지 컬렉팅을 지속하면서 또한 자바스크립트의 간헐적인 실행을 허용함으로써, 애플리케이션은 계속 사용자 입력에 응답하고 애니메이션을 만들 수 있습니다.

GC의 작업의 작은 덩어리(chunks)들이 메인 스레드 실행 사이 사이에 교차로 배치됩니다.

Concurrent

동시 실행(Concurrent)은 메인 스레드가 자바스크립트를 실행할 때, 헬퍼 스레드가 백그라운드에서 가비지 컬렉팅을 수행하는 것입니다. 자바스크립트 힙의 모든 것이 언제든 변경될 수 있고, 이전에 수행한 작업이 유효하지 않을 수 있기 때문에 세 가지 기술 중 가장 어려운 기술입니다. 무엇보다 헬퍼 스레드들과 메인 스레드가 동시에 동일한 객체를 읽거나 수정하는 경우에 대한 읽기/쓰기 레이스(race)가 존재합니다. 여기서 장점은 (헬퍼 스레드와의 동기화를 위한 약간의 오버헤드가 있긴 하지만) 메인 스레드가 자바스크립트를 완전히 자유롭게 실행할 수 있다는 것입니다.

GC 작업은 완전히 백그라운드에서 수행됩니다. 메인 스레드는 자바스크립트를 실행 할 수 있습니다.

V8의 가비지 컬렉터 상태

Scavenging

오늘날, V8은 young generation의 가비지 컬렉팅을 수행하는 동안 헬퍼 스레드들에 작업을 분산하기 위해 병렬 scavenging을 사용합니다. 각 스레드는 To-Space에서 옮겨지길 간절히 바라는 활성 객체(live object)를 가리키는 여러 개의 포인터를 받습니다. scavenging 작업은 객체를 제거할 때 atomic 읽기/쓰기/비교 및 교체 연산을 통해 동기화해야만 합니다. 다른 scavenging 작업이 다른 경로로 같은 객체를 찾아서 옮기려고 시도했을 수도 있기 때문입니다. 도우미가 객체를 성공적으로 옮기면 돌아가서 포인터를 업데이트합니다. 그리고 객체에 도달하는 다른 작업이 포인터를 찾았을 때 다른 포인터들을 업데이트할 수 있도록 이전 포인터를 남깁니다. scavenging 작업은, 동기화 없이 빠르게 활성 객체를 할당하기 위해, 스레드 로컬 할당 버퍼(TLAB, thread-local allocation buffers)를 사용합니다. 

참고) Introduction to Thread Local Allocation Buffers(TLAB)

병렬 가비지 컬렉팅(Parallel scavenging)은 가비지 컬렉팅 작업을 메일 스레드와 헬퍼 스레드에 분산합니다.

Major GC

V8의 주 가비지 컬렉터는 표시(Mark) 단계를 동시에 실행하며 시작합니다. 힙이 동적으로 계산된 한도에 가까워지면, 동시 표시 작업이 시작됩니다. 헬퍼 스레드들은 여러 개의 포인터를 받고, 그들은 참조를 따라가며 발견한 객체들에 표시합니다. 동시 표시 작업은 자바스크립트가 메인 스레드에서 실행되는 동안 완전히 백그라운드에서 실행됩니다. 쓰기 장벽(Write barriers)은 헬퍼 스레드가 동시 표시 작업을 하는 중에 자바스크립트가 생성한 객체 간의 새로운 참조를 추적하는 데 사용됩니다.

참고) Write barriers

주 가비지 컬렉터는 표시(marking), 스위핑(sweeping), 병렬 압축(parallel compaction) 및 포인터 업데이트를 동시에 진행합니다.

동시 표시 작업이 완료되거나 동적 할당의 한계에 도달하면 메인 스레드가 표시 단계의 마무리를 빠르게 수행합니다. 그동안 메인 스레드가 일시 중지됩니다. 이 중단 시간이 주 가비지 컬렉션의 총 중단 시간의 대부분입니다. 메인 스레드는 루트를 다시 한번 살펴보고, 모든 활성 객체가 표시되었는지 확인한 다음, 여러 헬퍼 스레드와 함께 병렬로 압축 및 포인터 업데이트를 시작합니다. old-space에 있는 모든 페이지를 압축할 수 있는 것은 아닙니다 - 압축되지 않은 페이지들은 위에서 언급한 free-lists를 사용하여 삭제될 것입니다. 일시 중지한 동안 메인 스레드는 동시 스위핑 작업을 시작합니다. 병렬 압축 작업과 함께 메인 스레드에서 동시에 실행됩니다 - 심지어 자바스크립트가 메인 스레드에서 실행 중일 때에도 실행될 수 있습니다.

빈 시간에 작업하는 GC(유휴 시간 GC, Idle-time GC)

자바스크립트 사용자는 가비지 컬렉터에 직접 접근할 수 없습니다; 이는 완전히 구현 방법에 따라 정의된 것입니다(implementation-defined). 심지어 자바스크립트 프로그램도 스스로는 못하지만, V8은 embedder에게 가비지 컬렉션을 유발할 수 있는 기능을 제공합니다. 가비지 컬렉터는 어쨌든 결국 유발되는 선택적 작업인 '유휴 작업'을 전송(post)할 수 있습니다. 크롬과 같은 Embedders들은 여유 혹은 유휴 시간에 대한 개념을 알고 있을 수 있습니다. 크롬의 예를 들면, 초당 60 프레임으로, 애니메이션의 각 프레임을 렌더링 하는 데 약 16.6ms가 소요됩니다. 애니메이션 작업이 빨리 끝나면, 크롬은 다음 프레임 전까지 남는 시간에 가비지 컬렉터가 생성한 이런 유휴 작업 중 일부를 실행하도록 선택할 수 있습니다.

참고) implementation-defined

Idle GC는 메인 스레드의 빈 시간을 활용하여 GC 작업을 수행합니다.

자세한 내용은 유휴시간 GC에 대한 깊이 있는 설명을 참고하세요.

요점

V8의 가비지 컬렉터는 시작 이후 많은 발전을 이뤄왔습니다. 이미 존재하는 가비지 컬렉터에 parallel, incremental, concurrent 기술을 추가하는 데에 다 년 간의 노력이 들었으나 성과를 거두어 많은 작업이 백그라운드에서 실행되게 바뀌었습니다. 일시 중시 시간, 지연 시간, 페이지 로드, 애니메이션, 스크롤링, 사용자 상호 작용(user interaction)이 대폭 개선되어 훨씬 부드러워졌습니다. Parellel Scavenger는 표준 작업량 기준, 메인 스레드가 young generation 가비지 컬렉팅을 수행하는 총시간을 약 20~50% 단축했습니다. 유휴 시간 GC(Idle-time GC)는 Gmail이 유휴 상태일 때 자바스크립트 힙 메모리를 45% 줄일 수 있습니다. 동시에 표시 단계와 스위핑 단계를 진행하는 것은 무거운 WebGL 게임에서의 (메인 스레드) 중단 시간을 50%까지 줄였습니다.

 

하지만 여기서 끝이 아닙니다. 가비지 컬렉팅으로 중단되는 시간을 줄이는 것은 여전히 웹상에서 사용자들에게 최고의 경험을 제공하는데 중요하며, 우리는 더 진보된 기술을 찾고 있습니다. 추가로 Blink(크롬의 렌더러)에도 가비지 컬렉터(Oilpan)가 있는데, 두 가비지 컬렉터의 협력을 개선하고 Orinoco에서 Oilpan으로 신기술을 이식(port)하는 작업을 하고 있습니다.

 

대부분의 개발자들은 자바스크립트 프로그램을 개발할 때 GC에 대해서 생각할 필요가 없지만, 내부 동작을 이해하는 것은 메모리 사용과 좋은 프로그래밍 패턴을 생각하는데 도움을 줄 것입니다. 예를 들어, V8 힙 메모리의 세대 구조(generational structure)를 고려하면, 우리는 살아남은 객체에 대해서만 비용을 지불하기 때문에 단명하는 객체는 가비지 컬렉터 관점에서 비용이 매우 적게 듭니다. 이런 종류의 패턴은 자바스크립트뿐만 아니라 가비지 컬렉팅을 하는 많은 언어들에서 잘 동작합니다.