쓰레기 토크: 오리노코 가비지 컬렉터

지난 몇 년 동안 V8 가비지 컬렉터(GC)는 많은 변화를 겪었습니다. 오리노코 프로젝트는 순차적으로 중단되는 가비지 컬렉터를 대부분 병렬적이고 동시적으로 실행 가능한 컬렉터로 변환시켰으며, 점진적 대체 방식도 포함했습니다.

노트

참고: 기사를 읽는 것보다 발표 영상을 선호하신다면 아래 비디오를 즐겨보세요! 아니라면 비디오를 건너뛰고 계속 읽어주세요.

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

1. 살아있는/죽은 객체 식별
2. 죽은 객체가 점유한 메모리 재활용/재사용
3. 메모리 정리/조각화 해제 (선택 사항)

이 작업들은 순차적으로 수행되거나 임의적으로 교차 수행될 수 있습니다. 직관적인 방법은 JavaScript 실행을 멈추고 메인 스레드에서 각 작업을 순차적으로 수행하는 것입니다. 하지만 이는 메인 스레드에서 끊김(jank)과 지연(latency)을 초래할 수 있으며, 이전 블로그 게시물에서 언급했듯이 프로그램 처리량을 감소시킬 수 있습니다.

주요 GC (전체 마크-컴팩트)

주요 GC는 힙 전체에서 쓰레기를 수집합니다.

마킹

어느 객체를 수집할 수 있는지 파악하는 것은 가비지 컬렉션의 핵심 요소입니다. 가비지 컬렉터는 '활성'의 대체 개념으로 접근성을 사용하여 이를 수행합니다. 이는 현재 런타임에서 접근 가능한 모든 객체는 유지되어야 하며, 접근 불가능한 객체는 수집될 수 있다는 것을 의미합니다.

마킹은 접근 가능한 객체를 찾는 과정입니다. GC는 루트 집합이라고 하는 알려진 객체 포인터의 집합에서 시작합니다. 여기에는 실행 스택과 전역 객체가 포함됩니다. 그런 다음 JavaScript 객체로 이어지는 각 포인터를 따라가며 해당 객체를 접근 가능한 것으로 표시합니다. GC는 해당 객체의 모든 포인터를 따라가며 이 과정을 재귀적으로 반복하여 런타임에서 접근 가능한 모든 객체가 발견되고 마킹될 때까지 계속합니다.

스위핑

스위핑은 죽은 객체가 남긴 메모리 공간을 '자유 목록'이라는 데이터 구조에 추가하는 과정입니다. 마킹이 완료되면 GC는 접근 불가능한 객체가 남긴 연속적인 공백을 찾아 이를 적절한 자유 목록에 추가합니다. 자유 목록은 빠른 조회를 위해 메모리 청크의 크기별로 구분됩니다. 미래에 메모리를 할당하고 싶을 때, 자유 목록을 조회하여 적절한 크기의 메모리 청크를 찾기만 하면 됩니다.

컴팩션

주요 GC는 또한 조각화 휴리스틱에 따라 일부 페이지를 정리/컴팩트합니다. 이는 오래된 PC의 하드 디스크 디프래그와 약간 비슷하다고 볼 수 있습니다. 우리는 현재 컴팩트 중이 아닌 다른 페이지로 살아남은 객체를 복사합니다(해당 페이지의 자유 목록을 사용). 이렇게 하면 죽은 객체가 남긴 메모리의 작고 흩어진 공백을 효과적으로 사용할 수 있습니다.

살아남은 객체를 복사하는 가비지 컬렉터의 잠재적 단점은 많은 오래 사는 객체를 할당할 경우 이 객체들을 복사하는 데 높은 비용을 지불해야 한다는 점입니다. 그래서 우리는 일부 고도로 조각화된 페이지만 컴팩트하고, 살아남은 객체를 복사하지 않는 스위핑만 수행합니다.

세대별 레이아웃

V8의 힙은 세대라고 불리는 다양한 영역으로 나뉩니다. 영 세대(‘보육’과 ‘중간’의 하위 세대로 더 나뉨)와 올드 세대가 있습니다. 객체는 먼저 보육 영역에 할당됩니다. 다음 GC를 통과하면 여전히 영 세대에 남아 있지만 '중간' 객체로 간주됩니다. 또 다른 GC를 통과하면 올드 세대로 이동합니다.

가비지 컬렉션에는 중요한 개념이 하나 있습니다: “세대 가설(Generational Hypothesis)”. 이는 기본적으로 대부분의 객체가 수명이 짧다는 것을 말합니다. 즉, 대부분의 객체가 할당된 후, GC 관점에서 거의 즉시 접근 불가능해진다는 것을 의미합니다. 이는 V8이나 JavaScript뿐만 아니라 대부분의 동적 언어에서도 마찬가지입니다.

V8의 세대적 힙 배치는 객체 수명에 대한 이러한 사실을 활용하도록 설계되었습니다. GC는 압축/이동 GC로, 가비지 컬렉션에서 살아남은 객체를 복사합니다. 이는 직관적이지 않게 보일 수 있습니다: GC 시점에서 객체를 복사하는 것은 비용이 많이 듭니다. 하지만 세대적 가설에 따르면 실제로 아주 작은 비율의 객체만이 가비지 컬렉션을 생존한다고 알고 있습니다. 살아남은 객체만 이동시킴으로써 다른 모든 할당은 '암묵적' 가비지가 됩니다. 이는 우리가 지불해야 하는 비용(복사 비용)이 할당 수가 아니라 생존 객체의 수와 비례하게 된다는 것을 의미합니다.

소규모 GC (Scavenger)

V8에는 두 개의 가비지 컬렉션이 있습니다. 대규모 GC (Mark-Compact)는 전체 힙에서 가비지를 수집합니다. **소규모 GC (Scavenger)**는 젊은 세대에서 가비지를 수집합니다. 대규모 GC는 전체 힙에서 가비지를 수집하는 데 효과적이지만, 세대적 가설은 새로 할당된 객체가 가비지 컬렉션이 필요할 가능성이 높다는 것을 알려줍니다.

Scavenger는 젊은 세대 내에서만 수집하며, 살아남은 객체는 항상 새로운 페이지로 대피합니다. V8은 젊은 세대에 대해 '세미 스페이스' 디자인을 사용합니다. 이는 대피 단계를 가능하게 하기 위해 전체 공간의 절반이 항상 비어 있다는 것을 의미합니다. 스캐빈지 동안 이 초기 비어 있는 영역은 'To-Space'라고 불리며, 우리가 복사하는 영역은 'From-Space'라고 불립니다. 최악의 경우, 모든 객체가 스캐빈지를 생존할 수 있으며 우리는 모든 객체를 복사해야 할 수도 있습니다.

스캐빈지를 위해 우리는 추가적인 루트 세트를 갖고 있는데, 이는 old-to-new 레퍼런스들입니다. 이는 old-space에서 젊은 세대의 객체를 참조하는 포인터들입니다. 매 스캐빈지 시점마다 전체 힙 그래프를 추적하는 대신, 우리는 쓰기 장벽을 사용하여 old-to-new 레퍼런스 목록을 유지합니다. 스택과 글로벌을 결합하면, 우리는 전체 old generation을 추적할 필요 없이 젊은 세대로의 모든 참조를 알고 있습니다.

대피 단계에서는 모든 생존 객체를 메모리의 연속적인 청크(한 페이지 내)로 이동합니다. 이는 죽은 객체가 남긴 간극을 제거하여 단편화를 완전히 없애는 장점이 있습니다. 그런 다음 두 공간을 전환합니다. 즉, To-Space는 From-Space가 되고 그 반대도 마찬가지입니다. GC 완료 후에는 From-Space에서 다음 사용 가능한 주소에서 새 할당이 발생합니다.

이 전략만으로 우리는 젊은 세대에서 공간을 금세 사용할 수 없게 됩니다. 두 번째 GC를 생존한 객체는 To-Space가 아니라 old generation으로 대피됩니다.

스캐빈지의 마지막 단계는 이동된 원래 객체를 참조하는 포인터를 업데이트하는 것입니다. 복사된 모든 객체는 포워딩 주소를 남기며 이는 원래 포인터를 새로운 위치로 업데이트하는 데 사용됩니다.

스캐빈지에서는 실제로 이 세 단계를 — 마킹, 대피, 포인터 업데이트 — 모두 다른 단계가 아닌 interleaved 방식으로 수행합니다.

Orinoco

이들 알고리즘과 최적화 대부분은 가비지 컬렉션 문헌에서 일반적이며 많은 가비지 컬렉션 언어에서 찾아볼 수 있습니다. 하지만 첨단 가비지 컬렉션은 크게 발전해왔습니다. 가비지 컬렉션에 소요되는 시간을 측정하는 중요한 지표는 GC가 수행되는 동안 메인 스레드가 일시 중지되는 시간입니다. 전통적인 '전 세계 중단' 가비지 컬렉터의 경우, 이 시간이 매우 많아질 수 있으며, GC 수행에 소요된 시간이 사용 경험을 직접적으로 해칠 수 있습니다. 예를 들어 페이지가 끊기고 렌더링 및 대기 시간이 저하됩니다.

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

Orinoco는 가장 최신의 병렬 처리, 점진적 처리 및 동시 처리 기술을 사용하여 메인 스레드를 해제하는 GC 프로젝트의 코드명입니다. 여기에는 GC 문맥에 특정한 의미가 있는 몇 가지 용어가 있으며, 이를 상세히 정의할 가치가 있습니다.

병렬(Parallel)

병렬 처리란 메인 스레드와 헬퍼 스레드가 대략 동일한 양의 작업을 동시에 수행하는 것을 말합니다. 이것은 여전히 '전 세계 중단' 접근 방식이지만, 총 일시 중지 시간이 참여하는 스레드 수로 나눠집니다(동기화를 위한 약간의 오버헤드 포함). 이는 세 가지 기술 중 가장 쉽습니다. JavaScript 힙이 일시 중지된 상태이므로 JavaScript가 실행되지 않습니다. 따라서 각 헬퍼 스레드는 다른 헬퍼가 접근하려고 할 수 있는 객체에 대한 접근을 동기화하기만 하면 됩니다.

점진적(Incremental)

증분 방식은 Main 스레드가 간헐적으로 소량의 작업을 수행하는 경우입니다. 우리는 증분 일시 중지 시 전체 GC를 수행하는 것이 아니라, GC에 필요한 전체 작업 중 일부 슬라이스만 처리합니다. 이것은 더 어려운 작업입니다. 왜냐하면 각 증분 작업 구간 사이에 JavaScript가 실행되어 힙 상태가 변경되며, 이로 인해 이전에 증분적으로 수행된 작업이 무효화될 수 있기 때문입니다. 다이어그램에서 볼 수 있듯이, 이것은 Main 스레드에서 소비되는 시간을 줄이지 않습니다(사실 약간 증가시키는 경우가 많습니다). 다만, 시간이 지남에 따라 이를 분산시키는 것입니다. 이것은 여전히 우리의 원래 문제 중 하나인 Main 스레드 대기 시간을 해결하기 위한 좋은 기술입니다. JavaScript가 간헐적으로 실행되도록 허용하면서도 가비지 컬렉션 작업을 계속 수행함으로써 애플리케이션이 사용자 입력에 반응하고 애니메이션에서 진행을 지속할 수 있습니다.

동시 실행

동시 실행은 Main 스레드가 JavaScript를 지속적으로 실행하는 동안 도움 스레드가 GC 작업을 전적으로 백그라운드에서 수행하는 경우를 말합니다. 이는 세 가지 기술 중 가장 어려운 기술입니다. JavaScript 힙에서의 어떤 항목이든 언제든지 변경될 수 있기 때문에 이전에 수행한 작업이 무효화될 수 있습니다. 그뿐만 아니라 도움 스레드와 Main 스레드가 동시에 동일한 객체를 읽거나 수정하려고 하면서 발생할 수 있는 읽기/쓰기 경합 문제도 고려해야 합니다. 여기서의 장점은 Main 스레드가 완전히 JavaScript를 실행하는 데 자유롭다는 점입니다 — 다만, 도움 스레드와의 일부 동기화로 인해 약간의 오버헤드가 발생합니다.

V8에서의 GC 상태

수집(Scavenging)

오늘날, V8은 병렬 수집(Parallel Scavenging)을 사용하여 젊은 세대 GC 동안 작업을 도움 스레드에 분산합니다. 각 스레드는 따라가야 할 포인터 몇 개를 할당받아, To-Space로 모든 살아있는 객체를 적극적으로 복구합니다. 수집 작업은 객체를 복구하려 할 때 원자적 읽기/쓰기/비교 및 교환(compare-and-swap) 작업을 통해 동기화해야 합니다. 다른 수집 작업이 다른 경로를 통해 동일한 객체를 발견하여 이동을 시도할 수 있기 때문입니다. 객체 이동에 성공한 도움 스레드는 포인터를 업데이트합니다. 또한 다른 작업자들이 객체를 찾았을 때 포인터를 업데이트할 수 있도록 전달 포인터를 남깁니다. 생존 객체의 동기화 없는 빠른 할당을 위해, 수집 작업은 스레드 로컬 할당 버퍼를 사용합니다.

주요 GC

V8에서 주요 GC는 동시 마킹으로 시작됩니다. 힙이 동적으로 계산된 한계에 접근하면, 동시 마킹 작업이 시작됩니다. 각 도움 스레드는 따라가야 하는 포인터 몇 개를 받아, 발견된 객체에서 모든 참조를 따라가며 발견한 객체마다 마킹을 합니다. 동시 마킹은 JavaScript가 Main 스레드에서 실행되는 동안 전적으로 백그라운드에서 수행됩니다. 쓰기 장벽을 사용하여, 도움 스레드가 동시 마킹을 수행하는 동안 JavaScript가 생성한 객체들 간의 새로운 참조를 추적합니다.

동시 마킹이 완료되거나 동적 할당 한계에 도달하면, Main 스레드는 빠른 마킹 완료 단계를 수행합니다. Main 스레드 일시 중지는 이 단계 동안 시작됩니다. 이는 주요 GC의 총 일시 중지 시간을 나타냅니다. Main 스레드는 모든 살아있는 객체가 마킹되었는지 확인하기 위해 다시 한 번 루트를 스캔한 후, 도움 스레드와 함께 병렬 압축 및 포인터 업데이트를 시작합니다. 오래된 공간의 모든 페이지가 압축에 적합한 것은 아닙니다 — 압축되지 않을 페이지는 앞서 언급한 자유 목록(free-lists)을 사용하여 스위핑됩니다. Main 스레드는 일시 중지 동안 동시 스위핑 작업을 시작합니다. 이 작업은 병렬 압축 작업과 Main 스레드 자체에 대해 동시에 실행됩니다 — JavaScript가 Main 스레드에서 실행되는 동안에도 지속될 수 있습니다.

유휴 시간 GC

JavaScript 사용자들은 가비지 컬렉터에 직접 접근할 수 없습니다. 그것은 완전히 구현에 정의됩니다. 그러나 V8은 JavaScript 프로그램 자체가 불가능하더라도, 포함자가 가비지 컬렉션을 트리거할 수 있는 메커니즘을 제공합니다. GC는 ‘유휴 작업’을 게시할 수 있으며, 이는 결국 트리거될 선택적 작업입니다. Chrome과 같은 포함자는 유휴 시간이나 여유 시간의 개념을 가질 수 있습니다. 예를 들어, Chrome에서는 초당 60 프레임에서 애니메이션의 각 프레임을 렌더링하는 데 약 16.6ms가 소요됩니다. 애니메이션 작업이 일찍 완료되면, Chrome은 GC가 생성한 이러한 유휴 작업 중 일부를 다음 프레임 전에 남은 시간 동안 실행하도록 선택할 수 있습니다.

자세한 내용은 우리의 심층적인 유휴 시간 GC 출판물을 참조하세요.

요약

V8의 가비지 컬렉터는 처음 등장 당시부터 크게 발전해 왔습니다. 기존의 GC에 병렬, 점진적, 동시 기법을 추가하는 데는 몇 년의 노력이 필요했지만, 배경 작업으로 많은 작업을 이동시키는 데 성공했습니다. 이를 통해 중지 시간, 지연 시간, 페이지 로드 시간을 크게 개선하여 애니메이션, 스크롤, 사용자 인터랙션이 훨씬 부드러워졌습니다. 병렬 Scavenger는 작업 부하에 따라 주 스레드의 young generation garbage collection 총 시간을 약 20%~50%까지 감소시켰습니다. Idle-time GC는 Gmail의 JavaScript 힙 메모리를 대기 상태에서 45% 감소시킬 수 있습니다. Concurrent marking and sweeping는 무거운 WebGL 게임에서 중지 시간을 최대 50%까지 감소시켰습니다.

하지만 여기서의 작업은 끝나지 않았습니다. 가비지 컬렉션의 중지 시간을 줄이는 것은 웹에서 사용자에게 최고의 경험을 제공하기 위해 여전히 중요하며, 더욱 발전된 기술을 연구하고 있습니다. 그 외에도 Chrome의 렌더러인 Blink 역시 가비지 컬렉터(Oilpan)를 가지고 있으며, 두 컬렉터 간의 협력 개선을 위한 작업과 Orinoco의 일부 새로운 기술을 Oilpan으로 이전하는 작업을 하고 있습니다.

대부분의 개발자는 JavaScript 프로그램을 개발할 때 GC를 신경 쓰지 않아도 되지만, 내부 구조를 일부 이해하면 메모리 사용 및 유용한 프로그래밍 패턴에 대해 생각하는 데 도움이 될 수 있습니다. 예를 들어, V8 힙의 세대 구조에서는 단기 객체가 가비지 컬렉터 관점에서 실제로 매우 저렴합니다. 우리는 수집 단계를 생존하는 객체에 대해서만 비용을 지불하기 때문입니다. 이러한 패턴은 JavaScript뿐만 아니라 많은 가비지 컬렉션 언어에서도 잘 작동합니다.