V8의 동시 마킹

이 게시글은 _동시 마킹_이라는 가비지 컬렉션 기술에 대해 설명합니다. 해당 최적화는 자바스크립트 애플리케이션이 실행을 계속하는 동안 가비지 컬렉터가 힙을 스캔하여 살아있는 객체를 찾고 마킹하도록 허용합니다. 우리의 벤치마크는 동시 마킹이 메인 스레드에서 마킹에 소요되는 시간을 60%–70% 감소시킨다는 것을 보여줍니다. 동시 마킹은 Orinoco 프로젝트의 마지막 퍼즐 조각으로, 기존 가비지 컬렉터를 대부분 동시적이고 병렬적인 새로운 가비지 컬렉터로 점진적으로 대체하는 프로젝트입니다. 동시 마킹은 크롬 64 및 Node.js v10에서 기본적으로 활성화되어 있습니다.

배경

마킹은 V8의 Mark-Compact 가비지 컬렉터의 단계 중 하나입니다. 이 단계에서는 컬렉터가 모든 살아있는 객체를 발견하고 마킹합니다. 마킹은 전역 객체와 현재 활성화된 함수와 같은 알려진 살아있는 객체 집합, 일명 루트에서 시작됩니다. 컬렉터는 루트를 살아있는 것으로 마크하고, 그것들 안의 포인터를 따라 추가적인 살아있는 객체들을 발견합니다. 이후 컬렉터는 새로 발견된 객체를 마킹하고 포인터를 따라가며 더 이상 마킹할 객체가 없어질 때까지 이를 반복합니다. 마킹이 끝나면 힙에서 마크되지 않은 모든 객체는 애플리케이션에서 도달할 수 없으며 안전하게 회수될 수 있습니다.

마킹은 그래프 탐색으로 생각할 수 있습니다. 힙의 객체는 그래프의 노드이고, 객체 간의 포인터는 그래프의 간선입니다. 그래프의 주어진 노드에서는 객체의 숨겨진 클래스를 통해 해당 노드의 모든 출발 간선을 찾을 수 있습니다.

V8은 마킹을 각 객체당 두 개의 마크 비트와 마킹 작업 리스트를 사용하여 구현합니다. 두 개의 마크 비트는 세 가지 색상, 즉 흰색(00), 회색(10), 검은색(11)을 인코딩합니다. 초기에는 모든 객체가 흰색으로, 이는 컬렉터가 아직 그들을 발견하지 못했음을 나타냅니다. 흰색 객체는 컬렉터가 그 객체를 발견하고 그것을 마킹 작업 리스트에 추가하면 회색으로 변합니다. 회색 객체는 컬렉터가 마킹 작업 리스트에서 그것을 꺼내고 모든 필드를 방문하면 검은색으로 변합니다. 이 스킴은 3색 마킹이라고 불립니다. 마킹은 더 이상 회색 객체가 없을 때 완료됩니다. 모든 남은 흰색 객체는 도달할 수 없으며 안전하게 회수될 수 있습니다.

위에 설명된 마킹 알고리즘은 애플리케이션이 중단된 동안에만 작동합니다. 만약 마킹이 진행 중일 때 애플리케이션 실행을 허용한다면, 애플리케이션이 그래프를 변경하여 결국 컬렉터를 속이고 살아있는 객체를 제거할 수도 있습니다.

마킹 중단 시간 줄이기

한 번에 모든 마킹 작업을 수행하면 큰 힙에서는 몇백 밀리초가 걸릴 수 있습니다.

이러한 긴 중단은 애플리케이션을 응답하지 않게 만들고 사용자 경험을 저해할 수 있습니다. 2011년 V8은 정지-세계 마킹에서 점진적 마킹으로 전환했습니다. 점진적 마킹 동안 가비지 컬렉터는 마킹 작업을 작은 조각으로 나누고 조각 사이에서 애플리케이션 실행을 허용합니다:

가비지 컬렉터는 각 조각에서 수행할 점진적 마킹 작업의 양을 애플리케이션의 할당 속도와 맞추어 선택합니다. 일반적인 경우 이는 애플리케이션의 응답성을 크게 향상시킵니다. 메모리 압박 하에 있는 큰 힙에서는 컬렉터가 할당을 따라잡으려고 시도하면서 여전히 긴 중단이 있을 수 있습니다.

점진적 마킹은 무료가 아닙니다. 애플리케이션은 객체 그래프를 변경하는 모든 작업에 대해 가비지 컬렉터에 알림을 제공해야 합니다. V8은 알림을 Dijkstra 스타일의 쓰기 바리어를 사용하여 구현합니다. 자바스크립트에서 object.field = value 형태의 각 쓰기 작업 후에 V8은 쓰기 바리어 코드를 삽입합니다:

// `object.field = value` 후 호출됨.
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

쓰기 방벽은 어떤 검은 객체도 흰 객체를 가리키지 않도록 보장하는 불변성을 강제합니다. 이는 강한 삼색 불변성으로도 알려져 있으며, 애플리케이션이 활성 객체를 가비지 컬렉터로부터 숨길 수 없도록 보장합니다. 따라서 마킹 종료 시 모든 흰 객체는 애플리케이션에서 실제로 도달할 수 없으며 안전하게 해제될 수 있습니다.

증분 마킹은 이전 블로그 게시물에 설명된 대로 유휴 시간 가비지 수집 스케줄링과 잘 통합됩니다. Chrome의 Blink 태스크 스케줄러는 유휴 시간 동안 메인 스레드에서 발생하는 작은 증분 마킹 단계를 끊김 없이 스케줄링할 수 있습니다. 이 최적화는 유휴 시간이 사용 가능한 경우에 매우 효과적으로 작동합니다.

쓰기 방벽 비용 때문에, 증분 마킹은 애플리케이션의 처리량을 감소시킬 수 있습니다. 추가 작업자 스레드를 활용하여 처리량과 일시 중지 시간을 모두 개선할 수 있습니다. 작업자 스레드에서 마킹을 수행하는 방법에는 병렬 마킹과 동시 마킹의 두 가지 방법이 있습니다.

병렬 마킹은 메인 스레드와 작업자 스레드에서 이루어집니다. 애플리케이션은 병렬 마킹 단계 내내 일시 중지됩니다. 이는 멀티스레드 버전의 stop-the-world 마킹입니다.

동시 마킹은 대부분 작업자 스레드에서 이루어집니다. 동시 마킹이 진행 중인 동안에도 애플리케이션은 계속 실행될 수 있습니다.

다음 두 섹션에서는 V8에서 병렬 및 동시 마킹을 지원하기 위해 추가한 내용을 설명합니다.

병렬 마킹

병렬 마킹 동안 애플리케이션이 동시에 실행되지 않는다고 가정할 수 있습니다. 이는 구현을 크게 단순화하는데, 이는 객체 그래프가 정적이며 변경되지 않는다고 가정할 수 있기 때문입니다. 객체 그래프를 병렬로 마킹하려면, 가비지 컬렉터 데이터 구조를 스레드 안전하게 만들어야 하며, 스레드 간에 마킹 작업을 효율적으로 공유할 방법을 찾아야 합니다. 아래 다이어그램은 병렬 마킹에 관련된 데이터 구조를 보여줍니다. 화살표는 데이터 흐름의 방향을 나타냅니다. 단순화를 위해 힙 단편화 방지를 위해 필요한 데이터 구조는 다이어그램에서 생략되었습니다.

스레드가 객체 그래프를 읽기만 하고 절대로 변경하지 않는다는 점에 주목하세요. 객체의 마크 비트와 마킹 작업 목록은 읽기 및 쓰기 접근을 지원해야 합니다.

마킹 작업 목록과 작업 훔치기

마킹 작업 목록의 구현은 성능 면에서 매우 중요하며, 스레드 로컬 성능과 작업이 부족할 경우 다른 스레드에 분배될 수 있는 작업 양 간의 균형을 맞춘 것입니다.

이 트레이드오프 공간의 극단적인 예는 (a) 모든 객체를 잠재적으로 공유할 수 있도록 완전히 동시적 데이터 구조를 사용하는 경우와 (b) 어떤 객체도 공유할 수 없는 완전히 스레드 로컬 데이터 구조를 사용하여 스레드 로컬 처리량을 최적화하는 경우입니다. Figure 6은 V8이 세그먼트를 기반으로 한 마킹 작업 목록을 사용하여 이러한 요구를 어떻게 균형 잡는지 보여줍니다. 세그먼트가 가득 차면 공유 글로벌 풀에 공개되어 훔치기가 가능해집니다. 이를 통해 V8은 가능한 한 오랜 기간 동안 동기화 없이 로컬 작업을 수행할 수 있으며, 다른 스레드가 로컬 세그먼트를 완전히 소진하여 굶주린 경우에도 새로운 객체 하위 그래프에 도달하는 단일 스레드의 경우를 처리할 수 있습니다.

동시 마킹

동시 마킹을 통해 JavaScript는 메인 스레드에서 실행되는 한편 작업자 스레드는 힙의 객체를 방문할 수 있습니다. 이는 많은 잠재적 데이터 경쟁을 야기할 수 있습니다. 예를 들어, JavaScript는 작업자 스레드가 필드를 읽고 있는 동시에 객체 필드에 쓰기를 수행할 수 있습니다. 이러한 데이터 경쟁은 가비지 컬렉터가 활성 객체를 해제하거나 원시 값을 포인터와 혼동하도록 만들 수 있습니다.

객체 그래프를 변경하는 메인 스레드의 각 작업은 잠재적인 데이터 경쟁의 원인이 될 수 있습니다. V8은 많은 객체 레이아웃 최적화를 제공하는 고성능 엔진이기 때문에 가능한 데이터 경쟁 원인의 목록이 상당히 깁니다. 여기에는 주요한 분류가 있습니다:

• 객체 할당.
• 객체 필드 쓰기.
• 객체 레이아웃 변경.
• 스냅샷에서의 역직렬화.
• 함수 디옵티마이제이션 중 물질화.
• 젊은 세대 가비지 수집 중 대피.
• 코드 패치.

메인 스레드는 이러한 작업에서 작업자 스레드와 동기화해야 합니다. 동기화의 비용과 복잡성은 작업에 따라 다릅니다. 대부분의 작업은 원자 메모리 접근을 통한 가벼운 동기화를 허용하지만, 일부 작업은 객체에 대한 독점 접근을 필요로 합니다. 다음 하위 섹션에서는 흥미로운 몇 가지 경우를 강조합니다.

쓰기 방벽

객체 필드 쓰기에 의해 발생하는 데이터 경쟁은 쓰기 작업을 완화된 원자적 쓰기로 전환하고 쓰기 방벽을 조정하여 해결됩니다:

// atomic_relaxed_write(&object.field, value); 호출 후
write_barrier(object, field_offset, value) {
  if (color(value) == white && atomic_color_transition(value, white, grey)) {
    marking_worklist.push(value);
  }
}

다음은 이전에 사용한 write barrier과 비교한 것입니다:

// `object.field = value` 후에 호출됩니다.
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

두 가지 변경 사항이 있습니다:

1. 소스 객체의 색상 체크(color(object) == black)가 제거되었습니다.
2. value의 색상 변화가 white에서 grey로 원자적으로 발생합니다.

소스 객체 색상 체크 없이 write barrier는 더 보수적으로 변합니다. 즉, 실제로 도달하지 않는 객체를 활성화된 객체로 표시할 수 있습니다. 우리는 write 작업과 write barrier 사이에 필요한 비용이 많이 드는 메모리 장벽을 피하기 위해 체크를 제거했습니다:

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

메모리 장벽 없이 객체 색상을 읽는 작업이 쓰기 작업보다 먼저 재정렬될 수 있습니다. 재정렬을 방지하지 않으면 write barrier가 객체 색상을 grey로 확인하고 중단할 수 있지만, 작업자 스레드는 새로운 값을 보지 못한 채 객체를 표시할 수 있습니다. Dijkstra 등에서 제안한 원래 write barrier도 객체 색상을 확인하지 않았습니다. 그들은 단순함을 위해 그렇게 했지만, 우리는 정확성을 위해 필요합니다.

Bailout 작업 목록

예를 들어 코드 패치와 같은 일부 작업은 객체에 대한 독점적인 접근을 필요로 합니다. 초기에는 객체별 잠금을 피하기로 결정했는데, 이는 우선 순위 반전 문제를 초래할 수 있기 때문입니다. 이 문제에서는 주 스레드가 작업자 스레드가 객체 잠금을 유지하면서 비활성화된 상태로 대기해야 합니다. 객체를 잠그는 대신 작업자 스레드가 객체 방문을 포기하도록 허용합니다. 작업자 스레드는 bailout 작업 목록에 객체를 추가하여 이 작업을 수행하며, 이 목록은 주 스레드만 처리합니다:

작업자 스레드는 최적화된 코드 객체, 숨겨진 클래스 및 약한 컬렉션에 대해 중단합니다. 이들을 방문하려면 잠금이나 비용이 많이 드는 동기화 프로토콜이 필요하기 때문입니다.

회고적으로 볼 때, bailout 작업 목록은 점진적 개발에 매우 유용했습니다. 우리는 모든 객체 유형에 대해 bailout을 수행하는 작업자 스레드로 구현을 시작하고 하나씩 동시성 처리를 추가했습니다.

객체 레이아웃 변경

객체의 필드는 태그된 포인터, 태그된 작은 정수(복수로 Smi라고도 함), 또는 언태그된 부동 소수점 숫자와 같은 언태그된 값을 저장할 수 있습니다. Pointer tagging은 언태그된 정수를 효율적으로 나타낼 수 있는 잘 알려진 기술입니다. V8에서는 태그된 값의 가장 적은 유의 비트가 포인터인지 정수인지를 나타냅니다. 이는 포인터가 워드 정렬된다는 사실을 기반으로 합니다. 필드가 태그인지 언태그인지에 관한 정보는 객체의 숨겨진 클래스에 저장됩니다.

V8의 일부 작업은 객체의 숨겨진 클래스를 다른 클래스로 전환함으로써 객체 필드를 태그에서 언태그로(혹은 그 반대로) 변경합니다. 그러한 객체 레이아웃 변경은 동시 표시 작업에 대해 안전하지 않습니다. 작업자 스레드가 객체를 동시적으로 방문하면서 이전 숨겨진 클래스를 사용하는 동안 이 변경이 발생하면 두 가지 유형의 버그가 발생할 수 있습니다. 첫째로, 작업자가 언태그된 값이라고 생각하여 포인터를 놓칠 수 있습니다. 이 유형의 버그는 write barrier가 보호합니다. 둘째로, 작업자가 언태그된 값을 포인터로 처리하고 이를 참조하려고 하면 일반적으로 프로그램 충돌 후 잘못된 메모리 접근이 발생합니다. 이를 처리하기 위해 우리는 객체의 마크 비트를 동기화하는 스냅샷 프로토콜을 사용합니다. 이 프로토콜에는 두 개의 당사자가 참여합니다: 필드 변경을 수행하는 주 스레드와 객체를 방문하는 작업자 스레드입니다. 필드를 변경하기 전에 주 스레드는 객체를 검정색(black)으로 표시하고 나중에 방문하도록 bailout 작업 목록에 추가합니다:

atomic_color_transition(object, white, grey);
if (atomic_color_transition(object, grey, black)) {
  // 객체는 bailout 작업 목록 처리 동안 주 스레드에서 다시 방문됩니다.
  bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

다음 코드 스니펫에 표시된 대로 작업자 스레드는 먼저 객체의 숨겨진 클래스를 로드하고 숨겨진 클래스가 지정한 객체의 모든 포인터 필드를 스냅샷화합니다. 그런 다음 원자적 Compare-and-Swap 작업을 사용하여 객체를 검정색(black)으로 표시하려고 시도합니다. 표시가 성공하면 이는 스냅샷이 숨겨진 클래스와 일치해야 함을 의미합니다. 주 스레드가 객체의 레이아웃을 변경하기 전에 객체를 검정색으로 표시하기 때문입니다.

snapshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
  pointer = atomic_relaxed_load(object + field_offset);
  snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
  visit_pointers(snapshot);
}

안전하지 않은 레이아웃 변경이 발생한 흰색 객체는 메인 스레드에서 표시해야 합니다. 안전하지 않은 레이아웃 변경은 상대적으로 드물기 때문에 실제 애플리케이션의 성능에 큰 영향을 미치지 않습니다.

모든 것 통합하기

우리는 기존의 점진적 마킹 인프라스트럭처에 동시 마킹을 통합했습니다. 메인 스레드는 루트를 스캔하고 마킹 작업 목록을 채우면서 마킹을 시작합니다. 그 후, 워커 스레드에 동시 마킹 작업을 게시합니다. 워커 스레드는 마킹 작업 목록을 공동으로 비우며 메인 스레드가 마킹을 더 빠르게 진행할 수 있도록 돕습니다. 가끔 메인 스레드는 구조 실패 작업 목록과 마킹 작업 목록을 처리하며 마킹에 참여합니다. 마킹 작업 목록이 모두 비워지면 메인 스레드는 가비지 컬렉션을 최종화합니다. 최종화 과정에서 메인 스레드는 루트를 다시 스캔하며 흰색 객체를 더 발견할 수 있습니다. 이러한 객체들은 워커 스레드의 도움으로 병렬로 마킹됩니다.

결과

우리의 실제 성능 벤치마크 프레임워크에 따르면 모바일과 데스크톱에서 각각 약 65%와 70%의 메인 스레드 마킹 시간이 가비지 컬렉션 사이클당 감소했습니다.

동시 마킹은 Node.js에서도 가비지 컬렉션 지연을 줄입니다. 이는 Node.js가 한 번도 유휴 시간 가비지 컬렉션 스케줄링을 구현하지 않았기 때문에 마킹 시간을 비지연 크리티컬 단계에서 숨길 수 없었던 만큼 특히 중요합니다. 동시 마킹은 Node.js v10에서 도입되었습니다.