Какие знаешь алгоритмы поиска мусора?

Алгоритмы Garbage Collection в Java

Garbage Collection — один из самых важных механизмов JVM. За 10+ лет разработки я работал с разными GC алгоритмами в production систем разной масштабируемости. Разберу основные подходы.

1. Mark-Sweep (Пометить и Удалить)

Самый базовый алгоритм:

public class MarkSweepExample {
    /**
     * Алгоритм Mark-Sweep работает в 2 фазы:
     * 
     * 1. Mark (Пометить)
     *    - Начиная с root references (стек, статические переменные)
     *    - Рекурсивно ходим по всем объектам
     *    - Помечаем как "live" (живые)
     * 
     * 2. Sweep (Подмести)
     *    - Проходим по памяти
     *    - Удаляем все непомеченные объекты
     *    - Освобождаем их память
     */
    
    // Проблема: Memory Fragmentation
    // После нескольких циклов память становится разреженной
    // Нельзя выделить большой объект хотя памяти достаточно
}

Характеристики:

• Простой в реализации
• Останавливает приложение (STW — Stop The World)
• Приводит к фрагментации памяти
• Время работы зависит от размера heap'а

2. Mark-Sweep-Compact (Пометить, Удалить, Уплотнить)

public class MarkSweepCompactExample {
    /**
     * Улучшение Mark-Sweep:
     * 
     * 1. Mark — помечаем живые объекты (как выше)
     * 2. Sweep — удаляем мусор (как выше)
     * 3. Compact — уплотняем живые объекты
     *    - Все живые объекты сдвигаются к началу памяти
     *    - Образуется блок свободной памяти в конце
     *    - Проблемы с фрагментацией решены
     * 
     * Но: Compact очень дорогой процесс (STW время растёт)
     */
}

Характеристики:

• Решает проблему фрагментации
• Очень долгие STW паузы
• Используется в Minor GC (молодое поколение)
• Дорого для больших heap'ов

3. Generational Garbage Collection

Основано на гипотезе "weak generational hypothesis":

public class GenerationalGCExample {
    /**
     * Наблюдение: большинство объектов умирают молодыми
     * Решение: разделить heap на поколения
     */
    
    // Young Generation (Молодое поколение)
    // - Новые объекты создаются здесь
    // - Частые GC сборки (быстрые)
    // - Маленькая область памяти
    public void createNewObjects() {
        Object obj1 = new Object(); // -> Young Gen
        Object obj2 = new Object();
        Object obj3 = new Object();
        // GC Young происходит часто, быстро
    }
    
    // Old Generation (Старое поколение)
    // - Объекты, пережившие несколько Young GC
    // - Редкие GC сборки (долгие)
    // - Большая область памяти
    List<String> longLivedList = new ArrayList<>();
    // Будет перемещён в Old Gen после нескольких GC
    
    // Пример:
    // Young Gen: 32MB, GC каждые 100ms (быстро)
    // Old Gen: 512MB, GC каждые 10 секунд (медленно)
}

Процесс:

• Новые объекты → Young Generation
• Minor GC (маленькие сборки) → очень частые, быстрые
• Пережившие объекты → Old Generation
• Major GC (большие сборки) → редкие, но долгие

4. Copy (Копирование)

public class CopyGCExample {
    /**
     * Используется в Young Generation
     * 
     * Heap делится на 2 области: From и To (50/50)
     * 
     * Процесс:
     * 1. Все живые объекты скопировать из From в To
     * 2. Удалить всё From
     * 3. Поменять From и To местами
     * 
     * Преимущества:
     * - Нет фрагментации (объекты идут подряд)
     * - Можно сбросить мусор одной операцией
     * 
     * Недостаток:
     * - Требует 2x памяти
     * - Дорого копировать долгоживущие объекты
     */
}

Используется в:

• Serial GC (Young Gen)
• Parallel GC (Young Gen)
• G1GC (молодые регионы)

5. Incremental GC (Инкрементальная сборка)

public class IncrementalGCExample {
    /**
     * Вместо одной длинной STW паузы
     * Делаем несколько коротких пауз
     * 
     * Преимущество: более предсказуемые паузы
     * Недостаток: общее время работы дольше
     * 
     * Используется в:
     * - CMS (Concurrent Mark Sweep)
     * - G1GC
     */
}

6. Serial GC (Однопоточная сборка)

public class SerialGCExample {
    /**
     * Самый простой GC алгоритм
     * 
     * Young Gen: Copy алгоритм
     * Old Gen: Mark-Sweep-Compact
     * 
     * Запуск: java -XX:+UseSerialGC MyApp
     * 
     * Где использовать:
     * - Single-threaded приложения
     * - Системы с маленькой памятью
     * - Batch-processing где пауза не критична
     * 
     * Где избегать:
     * - Low-latency системы (финтех, игры)
     * - Multi-core машины
     */
}

7. Parallel GC (Параллельная сборка)

public class ParallelGCExample {
    /**
     * Использует несколько потоков для GC
     * Стремится максимизировать throughput (пропускная способность)
     * 
     * Young Gen: параллельное копирование (несколько потоков)
     * Old Gen: параллельное Mark-Sweep-Compact
     * 
     * Запуск: java -XX:+UseParallelGC MyApp
     * 
     * Параметры:
     * -XX:ParallelGCThreads=8 (количество потоков GC)
     * -XX:GCTimeRatio=99 (99% времени на приложение, 1% на GC)
     * -XX:MaxGCPauseMillis=200 (макс пауза 200ms)
     * 
     * Где использовать:
     * - Batch processing
     * - Системы где пауза GC менее критична
     * - High-throughput приложения
     */
}

8. CMS GC (Concurrent Mark Sweep)

public class CMSGCExample {
    /**
     * Минимизирует STW паузы благодаря concurrent marking
     * 
     * Процесс:
     * 1. Initial Mark (STW) — помечаем root references
     * 2. Concurrent Mark — ходим по объектам одновременно с приложением
     * 3. Remark (STW) — помечаем изменения во время concurrent mark
     * 4. Concurrent Sweep — удаляем мусор одновременно с приложением
     * 
     * Запуск: java -XX:+UseConcMarkSweepGC MyApp
     * 
     * Преимущества:
     * - Короткие STW паузы
     * - Хорошо для low-latency систем
     * 
     * Недостатки:
     * - Более высокое CPU использование
     * - Фрагментация памяти
     * - Deprecated в Java 9+, удалён в Java 14
     */
}

9. G1GC (Garbage First)

public class G1GCExample {
    /**
     * Современный GC алгоритм, по умолчанию с Java 9+
     * Предназначен для больших heap'ов с предсказуемыми паузами
     * 
     * Концепция: Heap делится на регионы (regions)
     * - Каждый регион либо Young, либо Old
     * - Динамическое переопределение поколений
     * 
     * Процесс:
     * 1. Young GC (STW) — копирует объекты из Young регионов
     * 2. Concurrent Mark — помечает живые объекты в Old регионах
     * 3. Remark (STW) — финальная пометка
     * 4. Cleanup (STW) — удаляет пустые регионы
     * 5. Mixed GC — комбинирует Young и Old регионы
     * 
     * Запуск: java -XX:+UseG1GC MyApp
     * 
     * Параметры:
     * -XX:MaxGCPauseMillis=200 (целевая пауза 200ms)
     * -XX:G1ReservePercent=10 (10% памяти зарезервировано)
     * -XX:G1HeapRegionSize=16 (размер региона)
     * 
     * Преимущества:
     * - Предсказуемые паузы (целевой MaxGCPauseMillis)
     * - Хорошо для больших heap'ов (4GB+)
     * - Параллельный и concurrent marking
     * 
     * Где использовать:
     * - Production системы
     * - Big data processing
     * - Долгоживущие приложения
     */
}

10. ZGC и Shenandoah (Низколатентные GC)

public class LowLatencyGCExample {
    /**
     * ZGC (Z Garbage Collector) — Java 11+
     * 
     * Характеристики:
     * - STW паузы < 10ms независимо от heap размера
     * - Работает с heap'ом до 16TB
     * - Оптимизирован для NUMA и multi-core
     * 
     * Запуск: java -XX:+UseZGC MyApp
     * 
     * Shenandoah GC — Java 12+ (OpenJDK)
     * 
     * Характеристики:
     * - STW паузы < 10ms
     * - Более ранний выпуск ZGC-подобной функциональности
     * 
     * Запуск: java -XX:+UseShenandoahGC MyApp
     * 
     * Где использовать:
     * - Финтех, высокочастотный трейдинг
     * - Real-time системы
     * - Trading platforms
     */
}

Выбор GC алгоритма

public class GCSelection {
    /**
     * Вопросы для выбора:
     * 
     * 1. Размер heap'а?
     *    < 1GB → Serial GC
     *    1-4GB → Parallel GC или G1GC
     *    > 4GB → G1GC, ZGC, Shenandoah
     * 
     * 2. Критична ли пауза GC?
     *    Нет → Parallel GC (максимум throughput)
     *    Да → G1GC, ZGC, Shenandoah
     * 
     * 3. Количество CPU ядер?
     *    1 → Serial GC
     *    2-8 → Parallel GC
     *    > 8 → G1GC или современные GC
     * 
     * 4. Тип приложения?
     *    Batch → Parallel GC
     *    Web API → G1GC
     *    Real-time → ZGC/Shenandoah
     */
}

Мониторинг GC

public class GCMonitoring {
    // Базовые флаги логирования
    // java -XX:+PrintGCDetails -XX:+PrintGCDateStamps app.jar
    
    // Современный способ (Java 9+)
    // java -Xlog:gc*:file=gc.log app.jar
    
    // Анализ GC логов через:
    // - GCeasy.io
    // - JVM Analytics
    // - Сам через ручной анализ
    
    // Metrics for monitoring:
    // - GC pause time (пауза)
    // - GC frequency (частота)
    // - Heap utilization (использование памяти)
    // - Full GC frequency (сколько Major GC)
}

Практические советы

1. Не оптимизируйте GC без измерений — используйте профайлеры
2. G1GC — хороший выбор по умолчанию для большинства приложений
3. Установите MaxGCPauseMillis — чётко определите requirements
4. Мониторьте heap — Watch для memory leaks
5. Избегайте explicit GC — System.gc() часто вредит
6. Профилируйте памяти — используйте JProfiler, YourKit
7. Помните про объекты — лучше создавать меньше объектов, чем оптимизировать GC