목적
GC의 목적 자체는 단순하다. 사용되지 않는 메모리를 찾아 재사용할 수 있는 메모리로 전환하는 것이다.
GC는 Heap 메모리를 대상으로 한다.
Root Object
- V8 엔진에서 직접 참조되는 객체
- 전역 객체, Browser에서는 DOM 등
살아 있다? - Live 객체
- Pointer의 체이닝을 탐색해 접근 가능하다
Stack: 함수 단위로 이루어지며, 지역 변수, 실행 Parameter, 반환값, 반환 주소, 객체의 포인터 주소가 저장됨
Heap: 객체를 대상으로 함
Heap의 구조
를 그림으로 살펴 보자
Pointer 탐색
Remember Set
먼저, 힙 영역에서 Pointer와 Data를 구분해야 한다.
GC Root로부터 포인터를 탐색하여 Live 객체를 찾는다.
Java와 같은 정적 타입 언어일 경우, 컴파일 단계에서 각 Class 내의 메모리 Offset을 미리 알 수 있어, 어떤 객체에 대해 미리 파악한 Offset을 통해 모든 포인터를 찾아낼 수 있다.
JS는 동적 타입 언어이기 때문에 프로그램을 실행하며 실제로 코드가 컴파일 될 때 해당 객체들의 Offset을 매번 Update하여 이를 기록해 둔다.
GC 과정에서 객체가 Heap에서 이동할 때, 해당 메모리의 Pointer들을 갱신해 주어야 한다. 이 작업을 위해 이전 위치에 대한 Pointer들을 찾아야 하는데, V8 엔진에서는 이를 위해 Remember Set이라는 자료구조를 사용하여 이 포인터들을 기록해 추적한다.
Garbage Collection
일반적으로 대부분의 Application에서, 객체들은 수명이 짧은 경우가 많다.
이런 특성을 캐치해서 Heap을 New Space / Old Space의 2개의 영역으로 나눈다.
New Space
New Space는 1~8MB(작은 크기)로 설정이 가능하며, 이 이상의 크기를 가지는 객체는 Large Object Space에 저장된다.
이 공간은 From / To Space로 2개의 영역(역할)으로 나눠지며, 객체들은 항상 To Space에 할당되는데, 객체에 대한 메모리를 할당할 때마다 증가하는 할당 포인터가 존재하고 이 값이 해당 Space의 끝에 도달하게 되면 Minor GC(Scavenge)가 발생하게 된다.
Minor GC
To-Space에 남은 메모리보다 큰, 새로운 객체를 메모리에 할당하는 상황이라고 가정하자.
먼저, From Space와 To Space의 역할이 바뀐다. 이 때 살아남은 객체들은 To Space로 이동하게 되며, 연속된 메모리로 구성하여 메모리 단편화를 해결해 메모리를 추가적으로 확보한다. 메모리가 확보되었다면 이 때 새로운 객체를 To-Space에 할당한다.
시간이 흘러, To Space에 객체가 많이 생겨 또 메모리가 부족하게 되었고, 새로운 객체를 할당하려고 하는 상황이라 가정한다.
마찬가지로 To / From Space의 역할을 바꾸고, From Space에서 살아남은 객체들을 To-Space로 옮기며 연속된 메모리로 할당하여 메모리 단편화를 해결하여 추가적인 메모리를 확보한다. 이 때, GC에서 2번 이상 살아남게 된 객체들은 Old Space로 이동한다.
Old Space에 저장될 때, 다른 객체를 참조하는 포인터를 가진 객체는 Pointer Space에, Raw Data만을 가진 객체들은 Data Space에 위치시킨다.
이후, From-Space에 남은 객체들을 Garbage로 간주하여 삭제하고 To-Space에 새로운 객체를 할당한다.
이 과정을 V8의 Minor GC라 하며, 사용된 알고리즘을 Scavenge라 한다.
Scavenge 알고리즘은 빠른 성능을 보이지만, To/From Space에 대해 물리적인 메모리 백업이 필요하므로 메모리 공간에 대한 오버헤드가 존재한다. 그래서 Old Space같이 큰 메모리 영역에 대해서는 Mark-Sweep-Compact 알고리즘을 이용한 방식인 Major GC를 진행해야 한다.
V8의 Minor GC 처리: Parallel Scavenging
STW를 발생시키며 다른 Worker 스레드들과 함께 위의 알고리즘을 처리한다.
다른 스레드가 동일한 객체에 대해 작업을 수행하지 않도록 동기화 작업을 수행하는 오버헤드가 있다.
이 때 살아남은 객체들이 To-Space로 이동하게 되며, 모든 스레드들은 이동된 객체에 대한 포인터들을 갱신하는데, 이 때 다른 스레드들이 이 객체에 접근했을 경우 잘못된 메모리를 가리키는 포인터로 파악할 수 있다. 이를 알 수 있도록 하기 위해 해당 메모리에 Fowarding pointer(해당 객체에 대한 새로운 메모리 주소를 가리키는 포인터)를 남긴다.
Major GC
- Old Space가 꽉 차게 될 때 발생
Marking
다음의 3가지 상태로 표현된다.
- White: 아직 GC가 탐색하지 못한 상태
- Gray: GC가 탐색했으나, 해당 객체가 참조하는 객체들에 대해서는 탐색하지 못한 상태
- Black: GC가 탐색했으며, 해당 객체가 참조하는 객체들에 대해서도 탐색이 완료된 상태
이는 기본적으로 DFS로 수행되며, Deque를 이용하고 탐색에서는 Stack 형태로 사용한다.
처음에 모든 객체는 흰색으로 마킹되어 있다.
먼저, Root 객체를 회색으로 마킹한 후 Marking Deque에 Push하는 것으로 시작한다.
이후, 다음 과정을 반복한다.
1. Marking Deque에서 Pop_front()를 하여 객체를 꺼낸다.
2. 꺼낸 객체를 검은색으로 마킹한다.
3. 인접 객체를 회색으로 마킹한 후, Marking Deque에 Push_front()를 한다.
* 여러 곳에서 참조하는 객체가 존재한다면 이미 회색이거나 검은색인 객체가 있을 수 있다. 이 객체들에 대해서는 처리하지 않는다. 즉, 흰색 객체가 회색 객체로 바뀐 경우에만 Push를 한다.
DFS 알고리즘이므로 이 Deque가 비어 있게 되면 종료되며, 살아 있는 모든 객체들은 검은색으로 마킹된 상태가 되고 죽어 있는 객체들은 흰색으로 마킹된 상태가 된다.
Queue에 오버플로우가 발생한 경우, 회색 객체들이 남지만 Deque가 빈 상태가 되어 문제가 발생한다. 이 때에는 Heap을 탐색하여 회색 마킹된 오브젝트들을 찾아 Deque에 다시 넣어주고 탐색 알고리즘을 다시 수행한다.
Marking이 완료되면 Sweep 알고리즘이 동작한다.
만약 검은색 마킹이 없다면 어떨까?
Pop된 객체는 회색이며, 이 때 별다른 처리가 없다고 가정해도 로직을 끝낼 수 있지만, 특정 객체에 대한 탐색이 완전히 끝났다는 정보를 어딘가에 기록해야 한다. 이를 위한 것이 검은색으로 마킹하는 것이다.
Sweep
Page들은 Free List와 Marking Bitmap을 가지고 있는데,
이 프로세스는 Page 단위로 수행되며, Marking Bitmap을 탐색해 흰색 객체(죽어 있는 객체)를 찾아 탐색하여 Free Space로 전환시키고 Free List에 해당 메모리를 추가한다.
Compact
메모리 단편화가 심한 Page의 객체들을 공간이 여유로운 Page 혹은 새로운 Page에 이동시키면서 재배치를 하여 추가적인 메모리를 확보한다.
V8은 Page를 비우는 과정에서 옮겨진 객체들에 대한 포인터들을 기록해두며, Page가 비워지게 되면 이들을 옮긴 객체들을 가리키도록 업데이트한다.
다음 그림은 전체적인 과정을 간략하게 보여준다.
Write Barrier
만약, Old Space의 객체가 New Space의 객체를 참조하고 있는 상황이라 가정해 보자.
Minor GC가 발생하여 New Space의 객체가 삭제되게 되면, 해당 객체를 참조하고 있는 Old GC의 객체는 삭제된 메모리의 객체를 참조하는 문제가 발생하게 된다.
그렇다고 이를 위해 Heap 전체에 대한 탐색을 진행한다면 이에 대한 오버헤드가 커지게 된다.
그렇기 때문에 어플리케이션에서 참조를 대입하거나 수정할 때, 해당 객체에 대해 '어떤 영역의 객체가 어떤 영역의 객체를 참조한다'는 정보를 기록해 두는 방법을 사용하게 되었고, 이를 Write Barrier라고 한다.
Mark-Sweep-Compaction을 어떻게 처리해야 효율적일까?
GC는 위에서 설명한 원리를 바탕으로 동작하지만, 모든 Minor/Major GC는 Stop the world(GC를 제외한 모든 어플리케이션의 스레드가 멈추는 현상)가 발생하며, 이를 어떻게 처리하는지에 따라 그 시간을 줄일 수 있다.
이에 대해 V8에서 어떻게 처리하고 있는지에 대해 알아본다. Minor GC는 수행시간이 빨라 Major GC에 대해서만 다룬다.
V8에서는 Parrallel Marking과 Concurrent Marking 기법을 합쳐서 이용한다.
직접 이를 구현한다고 가정해 보자.
먼저, 하나의 메인 스레드에서 이를 구현한다면 다음과 같은 형태가 될 것이다.
Single Thread(on Main Thread) GC
STW 시간이 엄청나게 길어지게 된다. 이는 어플리케이션이 정상적으로 동작하지 않는 형태가 된다.
"GC작업을 잘개 쪼개서 수행하면 어떨까?" 하는 생각으로 만들게 된 것이 Incremental GC이다.
Incremental GC
간단하다고 생각할 수 있지만, 이는 Heap 객체 그래프가 GC가 완료되기 전에 수정될 수 있다는 문제가 존재한다.
이를 막기 위해서는 검은색 마킹된 객체가 흰색 마킹된 객체를 참조하게 되지 않아야 한다는 것이다.
GC가 잘 동작하려면 검은색 마킹된 객체의 인접 객체들은 흰색이 아니어야 하기 때문이다.
그래서 이 때, Write Barrier를 이용한 처리를 진행한다.
객체가 어떤 객체를 참조할 때, Write Barrier를 통해 Old -> New 포인터로의 정보를 기록하는 것 뿐만 아니라 검은색 객체가 흰색 객체를 참조하는 것도 기록한다.
Marking을 부분적으로 진행하면서 검은색 -> 흰색 참조를 하는 객체를 발견하면, 처리하지 않고 회색으로 변경하여 다시 Marking Worklist에 추가한다.
이제 잘 동작하는 것을 보게 되면 자연스레 멀티스레드를 이용한 방식을 떠올리게 된다.
Parrallel Marking
Marking 단계부터 간단하게 생각해 보면 어떻게든 멀티스레딩을 이용하여 수행하면 성능이 좋아질 것 같다는 생각이 든다.
Stop the world 없이 멀티스레드로 마킹을 진행한다면 어떨까? 하지만 문제점이 떠오를 것이다.
"Marking을 하는 도중에 Heap 그래프가 바뀐다면, Marking했던 정보들이 쓸모가 없어지는데.."
그렇다면 STW를 그대로 둔다고 가정한다면 위와 같은 문제를 고려하지 않아도 된다. 결과적으로 GC 속도를 빠르게 하는 것이 목표라면?
이에 대한 GC 자료구조를 Thread-Safe하게 만들면 된다.
즉, 스레드 간의 마킹 결과를 효율적으로 공유할 방법을 생각해 봐야 한다. 다음처럼 구조를 만들면 어떨까?
Marking Worklist : 위에서 설명한 Major GC의 Marking Queue
Worker 스레드들은 Heap 객체 그래프를 Read하기만 하며, Marking Worklist와 Page의 Marking bitmap에 대해서만 Read/Write가 가능하도록 구성하는 것이다.
전역 Marking Worklist에 대해서는 Read/Write 락을 통해 동기화하며, 이를 Worker 스레드들이 부분적으로 가져가 각자 가지고 있는 Marking worklist에 넣고 처리한다.
Marking bitmap은 atomic 계산으로만 수정되므로 이에 대한 lock은 필요하지 않으며, 이 값을 통해 각 스레드에서 객체의 색을 구분해 처리한다.
만약 어떤 Worker Thread의 Marking Worklist에 객체가 너무 많다면 이를 전역 Marking Worklist에 보내 다른 스레드들이 처리하게 한다.
여기까지가 실제로 Parallel Marking의 과정이다.
Concurrent Marking
여기까지 구현한다면, 더 좋은 방법에 대해 생각해보게 된다.
"혹시 어플리케이션 스레드를 동작시키면서 worker 스레드에서만 GC를 처리하는 방법은 없을까?"
이 질문을 해결하는 것이 Concurrent Marking이다. 자세한 구현 내용은 매우 어렵지만, Worker 스레드들이 Heap의 객체 그래프를 방문하는 동안 JS가 메인 스레드에서 실행될 수 있도록 해 주는 방법이다.
Background Marking 중에 발생하는 문제가 있다.
- Heap 그래프가 수정되는 문제
- Main 스레드와 Worker 스레드가 동시에 동일한 객체를 읽거나 수정함에 따라 Read/Write 레이스가 발생하는 문제
이를 위한 객체 동기화 작업이 추가되어 오버헤드가 존재하게 된다.
V8의 Major GC의 Marking: Incremental + Concurrent + Parallel Marking을 종합
1. Old Space가 가득 차게 되면 Concurrent Marking을 진행하며, 그동안 JS가 실행된다. 이 때 발생하는 Heap 객체 그래프의 변경에 대해, 각 객체 간의 참조 및 색 정보를 Write Barrier로 기록하여, 추후 검은색 -> 흰색 객체일 경우에 대한 처리를 할 수 있도록 한다. Concurrent Marking이 완료되면 STW를 발생시키며, Main Thread는 다시 한 번 Heap 객체 그래프를 순회하여 모든 객체가 검은색인지 확인한다.
2. 1번 작업이 끝나면 동시에 Sweep(Page에서 흰색 객체를 삭제해 Free-List에 등록)과 Compaction(메모리 단편화가 심한 Page를 골라 여유로운/새로운 페이지에 정리) 과정을 별개로 진행하며, 그렇기 때문에 모든 Old Space에 대해 Compaction이 일어나는 것은 아니게 된다. 하지만 이는 GC 시간을 줄이기 위함이며, 그렇기 때문에 다음 Major GC에서의 Compaction 과정에서 처리된다.
마치며
Concurrent Marking에 대한 세부적인 정보가 많지 않아 어느 정도 두루뭉술하게 작성된 부분이 있습니다.
JVM의 GC와 동작이 비슷하다는 얘기를 많이 들었고, 마침 JVM GC에 대한 문서가 많아 이를 참고하면 될 것이라 생각했지만, 실제로는 다른 부분이 너무나도 많았네요.
틀린 부분이 있다면 댓글을 남겨주시면 감사하겠습니다.
출처