🧠 Розділ 3 · Питання #12

Які алгоритми GC існують

У віртуальній машині Java необхідно чітко розрізняти теоретичні базові алгоритми очищення пам'яті (фундаментальні підходи) та конкретні реалізації збирачів сміття (Garbage Colle...

🧠 Пам'ять та Garbage Collection 📄 Вихідний Markdown

🟢 Junior Level

У віртуальній машині Java необхідно чітко розрізняти теоретичні базові алгоритми очищення пам’яті (фундаментальні підходи) та конкретні реалізації збирачів сміття (Garbage Collectors) у JVM HotSpot, які комбінують ці алгоритми для різних поколінь купи.

3 базових алгоритми очищення пам’яті

Алгоритм Принцип роботи Плюси Мінуси Де застосовується
Copying (Копіювання) Пам’ять ділиться на дві зони. Живі об’єкти копіюються з активної зони у вільну, а стара зона очищається повністю. Виняткова швидкість, нульова фрагментація Вимагає подвійного запасу пам’яті Young Generation (Eden $\rightarrow$ Survivor)
Mark-Sweep (Розмітка та видалення) 1. Розмітка: обхід графа від GC Roots та маркування живих об’єктів.
2. Очищення: видалення нерозмічених об’єктів.		 Не вимагає переміщення об’єктів, економний за пам’яттю Висока фрагментація: пам’ять покривається ізольованими «дірками» Старі збирачі Old Gen (CMS)
Mark-Compact (Розмітка та ущільнення) 1. Розмітка живих об’єктів.
2. Зсув усіх вижилих об’єктів на початок регіону єдиним щільним монолітом.		 Нульова фрагментація: відновлює швидкий bump-the-pointer Довгі паузи Stop-The-World (багатопрохідний перерахунок посилань) Full GC у G1 та Parallel Old

Побутова аналогія

  • Copying: Переїзд у нову відремонтовану квартиру: ви забираєте із собою лише потрібні речі, а стару квартиру зі сміттям віддаєте під знесення.
  • Mark-Sweep: Пройти кімнатою зі сміттєвим пакетом і викинути обгортки з кутків. Речі залишилися на місцях, але на підлозі утворилися хаотичні порожнечі.
  • Mark-Compact: Викинути обгортки, а всі меблі, що залишилися, щільно зсунути до однієї стіни, звільнивши суцільний вільний простір.

🟡 Middle Level

Палітра збирачів сміття в HotSpot JVM

Віртуальна машина надає набір готових збирачів під різні типи навантажень:

┌────────────────────────────────────────────────────────────────────────┐
│                     ЗБИРАЧІ СМІТТЯ В HOTSPOT                           │
├─────────────────┬──────────────┬──────────────┬────────────────────────┤
│ Збирач сміття   │ Паузи (STW)  │ Throughput   │ Рекомендоване застосування│
├─────────────────┼──────────────┼──────────────┼────────────────────────┤
│ Serial GC       │ 100–500 мс   │ Низький (1 CPU)│ Мікроконтейнери, CLI  │
│ Parallel GC     │ 100–1000 мс  │ Максимум     │ Batch, Big Data, Hadoop│
│ G1 GC (Def)     │ 20–200 мс    │ Високий      │ Web-сервіси, Spring Boot│
│ ZGC             │ < 1 мс       │ Середній (-10%)│ HFT, FinTech, Real-time│
│ Shenandoah      │ < 10 мс      │ Середній (-10%)│ Альтернативний low-lat │
│ Epsilon GC      │ 0 мс (немає) │ Абсолютний   │ Бенчмарки, Lambdas    │
└─────────────────┴──────────────┴──────────────┴────────────────────────┘

Трикутник компромісів GC (Trade-off Triangle)

Неможливо створити збирач сміття, ідеальний за всіма параметрами. Архітектурний вибір завжди диктується компромісом між трьома факторами:

                  Latency (Мінімальні паузи)
                         ▲
                        / \
                       /   \
  Throughput ◄───────┴───────► Footprint
(Пропускна здатність)        (Оверхед по пам'яті/CPU)
  • Parallel GC жертвує Latency (довгі паузи) заради максимального Throughput (усі 100% CPU віддаються розрахунку даних).
  • ZGC жертвує Throughput (витрачає 5–15% CPU на бар’єри читання) заради ультранизького Latency (паузи $< 1$ мс).
  • G1 GC — золота середина: адаптивно балансує паузи та пропускну здатність для більшості enterprise-завдань.

🔴 Senior Level

Триколірна розмітка (Tri-Color Marking)

В основі всіх сучасних паралельних та конкурентних збирачів (G1, ZGC, Shenandoah) лежить абстракція трьох кольорів:

┌────────────────────────────────────────────────────────┐
│ ⚪ БІЛИЙ: Невідвіданий об'єкт. Наприкінці фази розмітки│
│           усі залишкові білі об'єкти — це СМІТТЯ.      │
├────────────────────────────────────────────────────────┤
│ 🔘 СІРИЙ: Об'єкт відвіданий, але його дочірні поля-     │
│           посилання ще не проскановані збирачем.       │
├────────────────────────────────────────────────────────┤
│ ⚫ ЧОРНИЙ: Об'єкт гарантовано живий, і ВСІ його поля    │
│           успішно проскановані.                        │
└────────────────────────────────────────────────────────┘

Проблема конкурентної розмітки (Lost Object Problem):

Під час паралельної роботи застосунку потік виконання (Mutator) може переприв’язати посилання:

  1. Потік забирає посилання на Білий об’єкт $C$ у Сірого об’єкта $B$.
  2. Потік записує посилання на цей Білий об’єкт $C$ у поле Чорного об’єкта $A$.
  3. Оскільки об’єкт $A$ вже чорний, збирач до нього не повернеться. Сірий об’єкт $B$ посилання втратив.
  4. Катастрофа: Живий об’єкт $C$ залишився білим і буде помилково знищений збирачем сміття!

Вирішення проблеми: SATB vs Incremental Update vs Load Barriers

Різні GC розв’язують проблему втрати об’єктів принципово різними механізмами:

1. SATB (Snapshot-At-The-Beginning) — використовується в G1:

  • Застосовує Write Barrier (Бар’єр запису): перед тим як затерти старе посилання в B.field = null, JVM перехоплює старе значення посилання на об’єкт $C$ і примусово поміщає його в локальний буфер розмітки.
  • Об’єкт $C$ позначається сірим і гарантовано виживає.
  • Trade-off: Виникає Floating Garbage (Плаваюче сміття): якщо об’єкт $C$ дійсно більше нікому не потрібен, він все одно переживе поточний цикл збирання.

2. Incremental Update — використовувався в CMS:

  • При додаванні посилання на білий об’єкт у чорний A.field = C, Write Barrier перефарбовує чорний об’єкт $A$ назад у Сірий, змушуючи GC повторно просканувати його поля перед фінішем.

3. Load Barriers (Бар’єри читання) — використовується в ZGC:

  • Перехоплює не запис, а читання посилання Object o = a.field;.
  • Перевіряє метадані кольору покажчика (Colored Pointers). Якщо об’єкт переміщується, Load Barrier на льоту оновлює покажчик прямо в потоці (Self-Healing), роблячи процес евакуації повністю прозорим для застосунку.

Epsilon GC: No-Op збирач сміття

Увімкнений прапорцем -XX:+UseEpsilonGC, цей збирач реалізує лише інтерфейс алокатора пам’яті.

  • Під час виклику new він інкрементує покажчик купи (Bump-the-pointer).
  • Він ніколи не збирає сміття. Коли купа заповнюється, процес негайно падає з java.lang.OutOfMemoryError: Java heap space.
  • Навіщо потрібен у реальному світі:
    1. Ізольовані мікро-бенчмарки (JMH): вимірювання чистої продуктивності коду без завад від фонових потоків GC.
    2. Serverless-функції (AWS Lambda / Knative): мікросервіси із часом життя в кілька секунд, яким гарантовано вистачає 256 МБ купи на час виконання одного запиту.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь (Elevator Pitch)

«Базові алгоритми збирання сміття включають: Copying (швидке копіювання вижилих без фрагментації, застосовується в Young Gen), Mark-Sweep (розмітка та видалення, викликає фрагментацію пам’яті) та Mark-Compact (ущільнення зі зсувом об’єктів, що усуває фрагментацію ціною пауз STW). У HotSpot ці алгоритми об’єднані в готові збирачі: Parallel GC (максимальний throughput для пакетних завдань), G1 GC (збалансований стандарт Java 9+ з регіональною структурою та адаптивними паузами), і надшвидкі ZGC / Shenandoah (паузи $< 1$ мс за рахунок конкурентного ущільнення з бар’єрами читання). Для запобігання втраті живих об’єктів під час конкурентної розмітки G1 використовує алгоритм SATB, а ZGC — Load Barriers».

3–4 каверзних запитання з відповідями

  1. У чому різниця між базовими алгоритмами GC та конкретними збирачами в HotSpot?
    • Відповідь: Базові алгоритми (Copying, Mark-Sweep, Mark-Compact) — це теоретичні методи обходу та очищення пам’яті. Збирачі сміття в HotSpot (Parallel, G1, ZGC) — це складні програмні підсистеми, які комбінують ці алгоритми для різних поколінь пам’яті, керуючи паралелізмом, плануванням потоків, бар’єрами пам’яті та компромісами між пропускною здатністю (Throughput) та паузами (Latency).
  2. Що таке триколірна розмітка (Tri-Color Marking) і як G1 запобігає помилковому видаленню об’єктів?
    • Відповідь: Об’єкти діляться на Білі (невідвідані, кандидати на сміття), Сірі (відвідані, поля не перевірені) та Чорні (живі, всі поля перевірені). Якщо потік застосунку стирає посилання на білий об’єкт у сірого і передає його чорному, збирач може не помітити живий білий об’єкт і видалити його. G1 вирішує цю проблему через алгоритм SATB (Snapshot-At-The-Beginning): бар’єр запису перехоплює факт видалення посилання і примусово позначає старий білий об’єкт як сірий, зберігаючи знімок графа на початок збирання.
  3. Чим принципово відрізняються бар’єри запису (Write Barriers) у G1 від бар’єрів читання (Load Barriers) у ZGC?
    • Відповідь: Write Barrier у G1 спрацьовує під час модифікації посилань в об’єктах (obj.field = newRef), позначаючи брудні сторінки в Card Table або буферизуючи старі посилання для SATB. Load Barrier у ZGC спрацьовує під час розіменування посилання (Ref r = obj.field). Якщо посилання вказує на ще не переміщений об’єкт під час конкурентної евакуації, Load Barrier на льоту оновлює посилання в пам’яті на нову адресу (self-healing), дозволяючи переміщати об’єкти без глобальних пауз Stop-The-World.
  4. У яких сценаріях Parallel GC переважніший за сучасні ZGC чи G1?
    • Відповідь: У сценаріях пакетної обробки даних (Batch Processing, Big Data ETL, наукові обчислення, компіляція), де затримки відповіді (Latency) не мають значення, а критична лише загальна швидкість завершення завдання. Parallel GC не витрачає цикли CPU на фонові бар’єри читання/запису та багатопотокову синхронізацію розмітки, забезпечуючи максимально можливий Throughput на доступних ядрах процесора.

Типові помилки та Red Flags

  • 🚩 Твердження: «ZGC завжди у всіх сценаріях кращий за Parallel GC або G1» (ZGC жертвує 5–15% Throughput і вимагає більше пам’яті на бар’єри; для пакетних завдань Parallel ефективніший).
  • 🚩 Змішування понять базового алгоритму (Mark-Sweep) і готового збирача (G1 GC).
  • 🚩 Омана: «Epsilon GC можна використовувати як звичайний легковажний збирач у проді» (Epsilon узагалі не очищає пам’ять і гарантовано впаде з OOM при заповненні купи).
  • 🚩 Нерозуміння механіки бар’єрів пам’яті (Write Barriers vs Load Barriers).

Пов’язані теми