GC Algorithm and Garbage Collectors (Java Performance Fundamental)

Garbage Collection Algorithm의 구성

Reference Counting Algorithm

• 초기의 대표적인 GC 전략
• 각 Object의 reference count를 관리
• 특정 Object가 GC대상이 되면, 해당 Object에 의해 참조되는 Object의 count를 연쇄적으로 감소시킴

  장점 & 단점

• (+) Garbage object 판단이 쉬움
• (+) GC 대상인지 판단을 위한 STW가 발생하지 않음
• (+) GC 구동 시점에 제약이 없어 실시간성 가능
• (-) reference count 관리 비용 발생
• (-) Circular Linked List와 같은 경우는 영원히 GC 대상이 되지 못함

Mark and Sweep Algorithm

• Root set에서 시작해 deep dive하며 reference 관계를 추적함
• Tracing algorithm이라고도 불림
• Mark 단계에서는 Live object를 찾아 Mark 함. 이 때 Object 내 flag 또는 bitmap table을 이용함.
• Sweep 단계에서는 Mark되지 않은 객체들을 제거함

  장점 & 단점

• (+) Reference 관계를 정확히 파악할
• (+) Reference 관계를 맺을 때 부가적인 Overhead가 없음
• (-) STW 현상이 발생함
• (-) Compaction의 부재로 Fragmentation이 발생함

Mark and Compaction Algorithm

• Fragmentation 문제점과 이로인한 Memory 효율화를 개선하기 위한 알고리즘
• Mark 단계에서는 Live object를 Mark
• Compaction 단계에서는 Live object를 연속된 memory 공간에 차례로 쌓아둠
  • Compaction 단계에서 적재되는 Object들의 순서에 따라 Arbitrary(순서 보장x), Linear(인접한 Pointer 순), Sliding(Allocation 순) 방식이 있다.
• 위 두 단계에서 Handle을 사용하는데, Handle은 Live/Dead를 구분하는 Flag와 Object가 저장되어있는 위치공간 주소로 구성된다. Mark 단계에서는 각 Obejct에 해당하는 Handle에 Object가 저장된 위치 공간을 기록하고, Compaction 단계에서는 Object 이동 후 Handle을 업데이트 시킨다.

  장점 & 단점

• (+) Fragmentation을 방지 및 이로인한 Memory 효율성
• (-) Reference 업데이트 시 Object를 접근하는데 따른 Overhead 존재
• (-) STW 발생

Copying Algorithm

• Stop the Copy algorithm이라고도 불린다.
• Heap을 Active, Inactive영역으로 나누어 사용한다.
• Active영역에만 Object가 생성되고, Active영역이 가득차면 Live Object만 Inactive영역으로 이동한다.

  장점 & 단점

• (+) Framgentation을 방지 (Inactive영역으로 이동 시 차례로 적재)
• (-) STW 발생
• (-) Copy에 따른 Overhead 발생
• (-) 공간활용(50% Active / Inactive 50%) 측면에서 비효율적이다.

Generational Algorithm

• Copying Algorithm에서 Copy에 따른 Overhead 발생한다는 점, 대다수의 Object는 매우 수명이 짧다는 점, 소수의 수명이 긴 Object가 존재하고 이 Long Lived Obejct는 계속해서 복사된다는 점을 개선한 알고리즘
• Heap 영역을 몇 개의 Sub Heap(Young Generation, Old Generation)으로 나누어 구성
• Young Generation에서 자주 GC가 발생되고, 여기서 오래 살아남은 객체는 Old Generation으로 이동

  장점 & 단점

• (+) 각 Sub Heap에 Mark and Sweep, Copying 등의 Algorithm을 가미할 수 있다.

Train Algorithm

• TBD

  장점 & 단점

• (+) TBD
• (-) TBD

Hotspot JVM과 관련된 눈여겨 볼 점

Weak Generational Hypothesis

• 대부분의 Obejct는 매우 수명이 짧다.
• Old Object에서 Young Object로의 참조는 매우 적게 일어난다.

Young Generation - Speed

• Fast Allocation & TLAB(Thread Local Allocation Buffer)
  • TLAB를 통해 Thread마다 할당할 수 있는 범위를 부여
  • Bump the Pointer 테크닉을 활용
  • Memory 할당의 효율성
  • TLAB 내에서는 동기화 이슈가 없음
  • Multi-thread 환경에서는 동기화 이슈가 발생
  • Allocation code 내에 포함되어 있으며 약 10개의 native instruction으로 구성

Old Generation - Efficiency

• Card Table & Write Barrier
  • Old to Young reference를 구별하기 위해 사용
  • 1 Byte Card로 512 Byte의 Old generation 추적 가능
  • Write Barrier는 Bytecode Interpreter내에 포함되어 있으며 2 native instruction으로 구성

Garbage Collector의 종류

Serial Collector

Young Generation Algo'	Old Generation Algo'
Generational Algo'	Mark and Compacting

• Hotspot JVM의 Default GC
• Young 영역을 Eden / Survivor1 / Survivor2로 나누고 Eden 영역이 가득 찰 경우 Live Object만 Survivor1영역으로 보냄. 몇번의 반복 후 Survivor1영역이 가득차면 Live Object만 Survivor2로 보냄. 이후 Tenured 객체는 Old 영역으로 보냄
• 관련 JVM 옵션 (이름만으로 유추 가능하므로 설명은..)
  • -XX:+UseSerialGC
  • -XX:MaxTenuringThreshold=<value>
  • -XX:+PrintTenuringDistribution

Parallel Collector

Young Generation Algo'	Old Generation Algo'
Parallel Copy	Mark and Compacting

• 처리량(Throughput)을 개선하기 위한 GC
• Young Gen'을 병렬처리해 처리량을 늘임. 방식은 Serial Collector의 Young gen과 동일하다.
• 대용량 Memory, Multi core환경에서 처리량을 늘려 전체적인 수행속도 개선을 꾀함
• GC를 Multithread로 수행
• Large Young Generation의 경우 더욱 좋다.
• Promotion Buffer 사용
  • PLAB(Parallel Local Allocation Buffer)라고도 불린다
  • Thread간 동기화 문제 회피 목적
  • Promotion을 위한 Thread별 공간이다
  • 반대급부로 Fragmentation이 발생 가능한데 이는 GC Thread를 감소시키거나 Old Generation Size를 증가시키면 어느정도 상쇄가능하다..
• 관련 JVM 옵션 (이름만으로 유추 가능하므로 설명은..)
  • -XX:+UseParallelGC
  • -XX:ParallelGCThreads=<value_default:# of CPU>

Parallel Compacting Collector

Young Generation Algo'	Old Generation Algo'
Parallel Copy	Parallel Compacting

• 기존 Parallel Collector에서 Old Gen'의 처리량도 늘이자는 목적
• Multi CPU에서 유리하다.
• Old Gen'의 Collection 시간을 줄여준다.
• Old Generation은 다음과 같은 절차로 수행된다.
  • Mark
    • Multi Thread로 동작
    • STW 발생
    • Live Object를 마킹한 뒤, Generation을 몇 개의 Region으로 나누어놓는다.
  • Summary
    • Single Thread로 동작
    • Work Thread와 동시에 작업
    • 나뉘어진 Region 단위로 작업이 이루어진다.
    • 각 Region의 Density를 평가해 Dense Prefix를 설정한다.
    • Dense Prefix의 왼편에 있는 Region은 GC 대상에서 제외시킨다.
  • Compaction
    • Multi thread로 동작
    • STW 발생
    • Thread들이 각각 Region을 Collecting 한다.
    • Region들을 논리적인 Source / Destination으로 구분하여, Source의 Live Object들을 Destination의 빈 공간으로 이동시킨다.
• 관련 JVM 옵션 (이름만으로 유추 가능하므로 설명은..)
  • -XX:+UseParallelOldGC
  • -XX:+UseParallelOldGCCompacting : Default True
  • -XX:+UseParallelDensePrefixUpdate : Default True

CMS Collector

Young Generation Algo'	Old Generation Algo'
Parallel Copy	Concurrent Mark and Sweep

• 응답시간의 개선에 집중한 GC
• Old Gen' 정리 시 최대한 STW 시간을 줄이고자 함(Low Pause GC)
• Fast Elapsed Time에 중점을 둠
• 빈번하지는 않지만 Old GC가 오래 수행되는 것을 개선
• Low Latency Collector라고도 한다.
• 대기시간을 분산해 응답시간을 개선하였다
• 자원의 여유가 있는 상태에서 GC Pause Time을 줄이고자 할 때 적절하다.
• Old Generation은 다음과 같은 절차로 수행된다.
  • Initial Mark
    • Single Thread로 동작한다.
    • STW 발생
    • Direct Referenced Object를 빠르게 식별한다.
  • Concurrent Mark
    • Single Thread로 동작한다.
    • Work Thread와 동시에 작업한다.
    • Direct Referenced Object에서 deep dive하며 참조되는 Object를 식별한다.
  • Remark
    • Multi thread로 동작한다.
    • STW가 발생한다.
    • Mark된 Object들을 재방문하여 Mark작업을 확정한다.
  • Concurrent Sweep
    • Single Thread로 동작한다.
    • Work Thread와 동시에 작업한다.
    • Dead Object Reclaim이 발생한다.
• Compaction이 없어 시간절약할 수 있으나, 연속된 Free Space는 감소한다. 따라서 Allocation 시 FreeList를 탐색해 적절한 크기의 공간을 할당해야 한다. 이는 Fast Allocation의 장점을 없애버리고 Promotion과정에서 Young의 부담이 크다.
• Concurrent Mark 중 새로운 Allocation이 발생가능한데, 이 Live Object가 바로 Garbage로 되어버리면 Floating Garbage가 발생한다. 이는 다음 GC 작업 때 reclaim되고, 이러한 현상이 빈번하면 Memory 요구량이 많아진다.
• GC Scheduling
  • Old Gen이 가득차기 전에 작동한다.
  • Old Gen이 가득차기 까지 남은 예상 시간이 GC 수행에 필요한 시간과 근접해지면 작동한다.
  • Minor GC와 연달아 수행되지 않도록 Remark를 Minor GC 사이에 스케쥴링 한다.
  • 전체 Heap 점유율이 임계값(default:68%) 을 넘기면 작동한다.

Garbage First Collector

• Train Algorithm의 아이디어를 상당부분 차용
• Generation의 물리적인 구분이 사라짐
• Heap을 여러개의 Region으로 나누고, 용도에 따라 Young, Old area로 간주함
• Realtime에 가까운 Low pause 전략
• Concurrent Marker가 각 Region 내 Live data의 양을 계산하여 Garbage가 많은 Region부터 GC를 시작한다.
• G1GC는 다음과 같은 절차로 수행된다.
  • Young GC(Evacuation Pause)
    • Multi Thread로 동작
    • STW 발생
    • Live Object는 Survivor / Old Region으로 이동
  • Concurrent Mark - Marking
    • Single Thread로 동작
    • Work thread와 함께 작업
    • Evacuation Pause 때 넘어온 정보로 Initial Mark 수행
  • Concurrent Mark - Remarking
    • Multi Thread로 동작
    • STW 발생
    • Region당 Live Object를 계산하고 이 때 Empty Region은 즉시 reclaim한다.
  • Old Region Reclaim - Remark
    • Multi thread로 동작
    • Work thread와 함께 작업
    • Live Object가 적은 Region을 골라 몇 개의 Old Region만 collected
• Free List를 사용하지 않고, TLAB를 사용함으로써 Fast Allocation을 지원한다.
• Compaction 시 Linear 방식을 사용한다.
• 관련 JVM 옵션 (이름만으로 유추 가능하므로 설명은..)
  • -XX:+UseG1GC
  • -XX:+UnlockExperimentalVMOptions