V8 Engine garbage collector 이야기

이 글은 Trash talk를 참고 및 번역 하였습니다.

 

과거 몇년간 V8의 garbage collector (GC)는 많은 변화가 있었습니다. Orinoco 프로젝트는 sequential, stop-the-world garbage collector를 취하여 parallel, concurrent collector로 점차적으로 변경하였습니다.

 

모든 GC는 아래의 주요 몇가지 작업을 주기적으로 진행하여야 합니다.

 1. live/dead 객체 식별

 2. dead 객체에 점유된 메모리를 재활용/재사용

 3. 메모리 압축/조각모음 (선택)

 

 이 작업들은 순차적으로 진행하거나, 병렬적으로 수행 될 수 있습니다. 직접적인 방법으로는 JS의 실행을 멈추고 이 작업들을 순차적으로 메인 스레드에서 실행하는 것입니다. 그러나 이 방법은 jank (화면이 멈추거나 버벅이는 것)나 latency (반응 시간)의 이슈가 메인 스레드에서 발생 할 수 있으며 이에 관한 내용은 Jank 에서 더 자세히 보실 수 있습니다.

 

Major GC (Full Mark-Compact)

이 major GC는 전체 heap에서 garbage collect를 진행 합니다.

Major GC는 marking, sweeping, compacting 단계로 일어 납니다. (출처 : https://v8.dev/blog/trash-talk)

 Marking

  어느 객체가 수집될지 확인하는 작업은 GC의 주요한 부분인데, 이 작업을 GC는 'liveness' proxy로 접근 할 수 있는지로 확인합니다. 이것은 어느 객체라도 현재 런타임에서 접근이 가능하다면 보존되며, 접근할 수 없는 객체는 collect 된다는 의미입니다.

 

 Sweeping

  Sweeping은 dead 객체에의해 남겨진 메모리 갭을 free-list라고 불리는 데이터 구조에 추가하는 프로세스 입니다.

 한번 marking이 완료되면, GC는 접근 할 수 없는 객체가 남긴 연속적은 갭을 찾아 free-list에 추가합니다.

 free-list는 빠른 검색을 위해 메모리 chunk 크기로 분리되고, 앞으로 메모리를 할 당 할때 이 free-list를 보고 적절한 크기의 메모리를 찾습니다.

 

 Compaction

  또 Major GC는 fragmentation heuristic에 기반하여 evacuate/compact할 page를 선택합니다. 이 것은 오래된 PC의 하드 디스크 조각모음이라고 볼 수도 있습니다. 우리는 살아남은 객체를 압축되지 않은 다른 페이지로 복사합니다 (free-list를 사용하여).

  이런 방법으로 dead 객체들이 남긴 작은 갭들을 사용 할 수 있습니다. 하지만 살아있는 객체가 많다면 이 작업은 많은 비용을 요구하기 때문에 fragmented page가 적다면 수행하지 않는것이 좋을 수 있습니다.

 

Generational layout

 V8에서 heap은 generations 라고 불리는 영역으로 나눠집니다. 이 영역은 Young generation ( 더 세분화 하면 nursery와 intermediate라는 sub-generation)과 Old generation으로 구분 되는데, 객체는 처음 nursery 영역에 할당 됩니다.

 만약 그 객체들이 다음 GC에서 살아남게 되면 intermediate로 옮겨지게 되고, GC 과정을 거치면서 계속 살아남은 객체들은 Old Generation으로 이동 됩니다.

 

V8의 heap에서 GC를 거치며 살아남은 객체가 이동하는 모습 (출처 : https://v8.dev/blog/trash-talk)

    V8의 generation layout은 객체의 수명에 대해 gerneration 가설 (객체는 young 영역에서 대부분 죽는다)를 이용하도록 설계가 되어있습니다.

  GC는 압축/이동 GC이며 GC에서 살아남은 객체를 복사한다는 것입니다. 객체를 복사하는데에는 많은 비용이 발생하지만 위 가설에 의해 매우 적은 비율의 살아남은 객체에만 해당할 것입니다.

Minor GC (Scavenger)

 V8에는 두가지 GC가 있는데, 하나는 Major GC (Mark-Compact)이며 전체 heap 영역을 대상으로 garbage collect를 진행하며, 또 다른 하나는 Minor GC (Scavenger)이며 garbage collect를 young generation에 진행합니다.

 

 young 영역에서만 GC를 진행하는 Scavenger는 살아남은 객체를 항상 새로운 page로 이동시킵니다. V8은 young generation을 위해 설계된 semi-space를 사용하는데, 이것은 전체 공간의 절반이 항상 비어있음을 의미합니다.

 Scavenge 동안 초기에 비어있는 영역을 To-space라고 부르며, 복사할 영역을 From-space라고 합니다.

 최악의 경우엔 모든 객체가 살아남아 모든 객체를 복사해야할 수도 있습니다.

 

 Scavengeing 에서 추가적으로 old-to-new 레퍼런스 셋이 있는데, 이 포인터들은 old-space에서 young generation에 있는 객체들을 가르킵니다. 모든 scavenge에서 전체 heap 그래프를 추적하기보다 write barriers를 사용하여 old-to-new 레퍼런스를 유지합니다.

 스택과 전역 변수를 함께 사용 할 때 old generation 전체를 추적할 필요 없이 young generation의 레퍼런스를 알 수 있습니다.

 

 evacuation 단계에서 모든 살아남은 객체들을 연속된 메모리 chunk (page 내에 있는)로 이동합니다. 이 것은 죽은 객체들이 남긴 fragmentation gap들을 제거 할 수 있는 이점이 있습니다. 그리고 나서 두 개의 영역을 교체 합니다. (To-space -> From-space).

 한번 GC가 완료되면 새로운 free address가 from space에 할당 됩니다. 

 

Scavenger에서 살아 남은 객체를 fresh page로 이동하는 모습. (출처 : https://v8.dev/blog/trash-talk)

  이 방법 하나 만으론 young generation을 빠르게 소모하기에, 두 번째 GC에서 살아남은 객체들을 To-space로 이동하기 보다 old generation으로 이동합니다.

  Scavenging의 마지막 단계는 이동된 원본 객체의 레퍼런스들을 업데이트 하는것 입니다. 객체를 복사할 때마다 원본 포인터가 새로운 위치를 가르키도록 하기위해 forwarding-address를 남깁니다.

 

Scavenger는 'intermediate' 객체를 old gerneration으로, 'nursery' 객체를 fresh page로 이동합니다. (출처 : https://v8.dev/blog/trash-talk) 

  Scavengin에서 이 세가지 단계 (marking, evacuating, pointer-updating)를 수행하며 모두 구별된 phase가 아닌 병렬 처리를 합니다.

Orinoco

  이 알고리즘들과 최적화 방법들은 대부분 GC에서 일반적입니다만, 아직 최첨단 GC는 갈길이 멉니다. GC에서 소요된 시간을 측정하는 주요한 기준 중 하나는 메인 스레드가 GC 동안 멈춰있는 시간입니다. 전통적인 'stop-the-world' GC는 사용자의 경험에 직접적인 영향을 주며 렌더링과 응답성을 악화시킵니다.

 

  Orinoco는 프로젝트의 코드 명으로 가장 최신의 parallel, incremental, concurrent기술을 사용하여 메인 스레드를 해제 합니다. 여기에 사용된 용어를 아래에서 설명 하도록 하겠습니다.

Parallel

  Parallel은 메인 스레드와 헬퍼 스레드가 같은 시간에 같은 양의 일을 처리하는 것입니다. 이것은 여전히 'stop-the-world' 방식이지만 총 pause 시간이 참여하는 스레드 수만큼 감소합니다 (약간의 동기화 오버헤드 존재). 이것이 세가지 기술중 가장 쉬운 부분입니다. 

  Javascript heap에 실행되는 Javascript가 없을때 멈추게 되므로, 각 헬퍼 스레드는 다른 헬퍼가 접근하려는 어느 객체에든 접근을 동기화 해야 합니다.

메인 스레드와 헬퍼 스레드가 같은 시간에 같은 일을 처리하는 모습 (출처 : https://v8.dev/blog/trash-talk)

Incremental

 Incremental은 메인스레드가 간헐적으로 적은 양의 작업을 수행하는 것입니다. GC에 필요한 총 작업량의 일부만 점진적으로 일시 중지하여 전체 GC를 수행하지는 않습니다.

 Javascript가 각 작업 세그먼트 사이에서 실행 되므로 heap 상태가 변경되어 이전 작업이 무효화 될 수 있기 때문에 더 어려운 작업입니다.

 다이어 그램에서 볼 수 있듯이 메인 스레드에서 소비되는 시간이 줄지는 않습니다(사실 약간 증가). 하지만 이를 통해서 원래 우리가 가지고 있던 문제인 메인 스레드의 정지 시간 문제를 해결 할 수 있습니다.

메인 스레드에서 작은 chunk 작업이 수행되는 모습 (출처 : https://v8.dev/blog/trash-talk)

Concurrent

 Concurrent는 메인스레드가 지속적으로 Javascript 수행을 하고 헬퍼 스레드가 백그라운드에서 GC 작업을 완전히 수행하는 경우 입니다. 이 기술은 세가지 기술중 가장 어렵습니다. Javascript heap의 내용이 언제든 변경될 수 있기에 이전 작업들이 무효화 될 수 있으며, 메인 스레드와 헬퍼 스레드가 같은 객체에 대해 read/write race가 일어나는 부분이 우려되는 부분입니다. 하지만 여기선 헬퍼 스레드와 메인 스레드 와의 사소한 동기화 오버헤드가 있지만 메인 스레드가 Javascript를 완전히 자유롭게 실행 할 수 있다는 장점이 있습니다.

GC 작업이 완전히 백그라운드에서 일어나며, 메인 스레드는 자유롭게 JS 실행을 할 수 있습니다 (출처 : https://v8.dev/blog/trash-talk) 

State of GC in V8

Scavenging

 

 오늘날 V8은 parallel scavenging을 사용하며, 헬퍼 스레드를 통해 작업을 분산 합니다. 각 스레드는 여러 포인터를 받는데, 이로 살아남은 객체들을 To-space로 이동합니다. Scavenging은 작업을 수행 할 때 atomic하게 read / write / compare-and-swap 작업을 동기화 해야합니다(다른 스레드가 동일한 객체에 대해 작업을 수행하지 않도록 하기 위해).

 어느 스레드던 객체를 이동후엔 포인터를 업데이트 하는데, 다른 스레드에서 작업을 수행할 때 객체를 찾을 수 있도록 forward pointer를 남깁니다. 살아남은 객체를 동기화가 필요없는 할당(빠른 속도를 위해)을 위해 로컬 할당 버퍼를 사용합니다. 

 

메인 스레드와 헬퍼 스레드들에 scavengin 작업을 할당하여 수행하는 모습 (출처 : https://v8.dev/blog/trash-talk) 

Major GC

 V8의 Major GC는 concurrent marking으로 시작합니다. heap이 동적으로 계산된 한계에 도달하면 concurrent marking 작업이 수행됩니다. 헬퍼는 각각 따를 포인터를 가지고 있으며, 발견된 객체의 모든 참조를 따라 각 객체를 mark 합니다. 

 Concurrent marking은 메인 스레드에서 JS가 수행될때 백그라운드에서 전체적으로 발생 합니다.  Write barriers은 헬퍼가 marking을 수행하는 동안 JS에서 생성한 객체 간의 새로운 참조를 추적하는데 사용됩니다.

 

메인 스레드가 concurrent marking, sweeping 및 parallel compaction, pointer updating을 수행 (출처 : https://v8.dev/blog/trash-talk) 

 Concurrent marking이 완료되거나, 동적 할당 제한에 도달하면 메인 스레드는 quick marking을 완료단계로 수행합니다.

 메인 스레드는 이 시간에 멈추게 되며, 이것은 GC의 전체 중지 시간을 나타냅니다. 메인 스레드는 root를 다시 한번 스캔하여 모든 객체가 mark 된 것을 확인 하고, 여러 헬퍼 스레드와 함께 parallel compaction과 pointer updating을 수행합니다.

 모든 old-space가 compaction 대상이 되는 것은 아니며, 이전에 언급한 free-list를 사용하여 압축되지 않은 page를 압축합니다.

 이 작업은 메인스레드에서 JS가 수행되는 동안에도 진행 할 수 있습니다.

Idle-time GC

 JS 사용자가 GC에 직접 접근 할 수는 없습니다, 그러나 V8은 JS 프로그램 자체가 할 수 없더라도 embedder가 GC를 시작하는 메터니즘을 제공합니다. GC는 궁극적으로 시작될 선택적 작업인 'Idle Tasks'를 게시 할 수 있습니다.

 Chrome과 같은 Embedder는 'idle time'이라는 개념이 있을 수 있습니다. 예를 들어 Chrome에서 초당 60 프레임의 브라우저는 애니메이션의 각 프레임을 렌더링 하는데 약 16.6ms를 사용합니다. 애니메이션 작업이 일찍 완료되면 Chrome은 GC가 다음 프레임 이전의 여유 시간에 일부를 실행 할 수 있도록 선택 할 수 있습니다.

 

Idle GC가 메인 스레드에서 Idle time을 이용하여 GC 작업을 수행하는 모습 (출처 : https://v8.dev/blog/trash-talk)

더 자세한 내용은 our in-depth publication on idle-time GC에서 확인 할 수 있습니다.