Какой алгоритм работы Garbage Collector в Go?

Алгоритм работы Garbage Collector в Go

Сборщик мусора (Garbage Collector, GC) в Go — это неблокирующий, конкурентный, триколорный (tricolor) mark-and-sweep сборщик. Он предназначен для минимизации пауз (stop-the-world) и обеспечения предсказуемой производительности в высоконагруженных приложениях. Алгоритм эволюционировал, и с версии Go 1.5 используется конкурентная маркировка и очистка.

Основные фазы работы GC

Алгоритм работает в три основные фазы:

1. Фаза маркировки (Mark Phase)

Цель — обнаружить все достижимые (live) объекты в куче (heap). Используется алгоритм триколорной маркировки:

• Белые объекты — потенциальный мусор (ещё не обработаны).
• Серые объекты — достижимые, но их поля не проверены.
• Чёрные объекты — достижимые и полностью обработанные.

Процесс маркировки:

• Начало: Корневые объекты (глобальные переменные, локальные переменные в стеке goroutine, регистры) помечаются как серые.
• Обработка: Пока есть серые объекты, GC рекурсивно проходит по их полям, помечая белые объекты как серые, а исходные серые — как чёрные.
• Завершение: Когда серых объектов не остаётся, все достижимые объекты становятся чёрными, а белые — мусором.

Пример упрощённой логики:

// Псевдокод триколорного алгоритма
var whiteSet, graySet, blackSet Set

for _, root := range roots {
    graySet.add(root)
}

for !graySet.isEmpty() {
    obj := graySet.pop()
    for _, ref := range obj.references() {
        if whiteSet.contains(ref) {
            whiteSet.remove(ref)
            graySet.add(ref)
        }
    }
    blackSet.add(obj)
}
// Все оставшиеся в whiteSet — мусор

2. Фаза очистки (Sweep Phase)

После маркировки GC проходит по всей куче и освобождает память, занятую белыми (недостижимыми) объектами. Очистка выполняется конкурентно с работой приложения, но требует кратких пауз для подготовки.

3. Фаза очистки памяти (Memory Reclamation)

Освобождённая память возвращается в кучу для повторного использования. В Go управление памятью построено на сегментах (spans) и кешах размеров (size classes) для эффективного аллокатора.

Ключевые особенности GC в Go

• Конкурентность: Основные фазы выполняются параллельно с программой. С версии Go 1.8 маркировка и очистка почти полностью конкурентны.
• Инкрементальность: GC разбивает работу на небольшие части, чтобы минимизировать задержки.
• Write Barrier: Для корректности при конкурентной маркировке используется барьер записи (write barrier). При изменении указателей во время маркировки барьер помечает затронутые объекты.

// Write barrier при изменении указателя *p = obj
func writeBarrier(p *interface{}, obj interface{}) {
    shade(obj) // Пометить obj как серый при необходимости
    *p = obj
}

• Pacer (Регулятор): GC использует пакер для прогнозирования, когда запускать следующую сборку. Он основывается на целевом соотношении GOGC (по умолчанию 100%), которое определяет, сколько новой памяти можно выделить до следующего GC относительно живой памяти.
• Короткие Stop-the-World паузы: Паузы возникают только в начале маркировки (корневая сканирование стека, запуск барьера записи) и в конце (завершение маркировки).

Параметры и настройка GC

• GOGC: Переменная окружения, задающая процент роста кучи перед запуском GC. Например, GOGC=100 означает, что GC запустится, когда размер кучи увеличится вдвое относительно живой памяти после предыдущей сборки.
• Отладка: Можно использовать пакет runtime/debug для получения статистики:

import "runtime/debug"

debug.SetGCPercent(200) // Изменить целевой процент
var stats debug.GCStats
debug.ReadGCStats(&stats) // Прочитать статистику

Эволюция и производительность

С версии Go 1.5 GC стал конкурентным, что сократило паузы с сотен миллисекунд до единиц. В версиях 1.8–1.12 улучшена предиктивность пауз (обычно менее 1 мс). Submillisecond паузы стали возможны благодаря оптимизациям: гибридный барьер записи, раздельная сканирование стеков, улучшенный pacer.

Пример влияния на приложение

package main

import (
    "fmt"
    "runtime"
    "time"
)

func main() {
    // Запускаем GC вручную для демонстрации
    var data [][]byte
    for i := 0; i < 100; i++ {
        data = append(data, make([]byte, 1024*1024)) // 1 MB
        if i % 10 == 0 {
            runtime.GC() // Принудительный вызов GC
            time.Sleep(500 * time.Millisecond)
        }
    }
    fmt.Println("Выделено 100 MB с периодическим GC")
}

Вывод

Алгоритм GC в Go сочетает триколорную маркировку, конкурентную очистку и умный pacer для баланса между использованием памяти и производительностью. Его ключевые преимущества — низкие задержки и масштабируемость в многопоточных средах, что делает Go пригодным для latency-sensitive приложений, таких как веб-серверы и распределённые системы. Понимание работы GC помогает оптимизировать приложения, например, уменьшая количество указателей или контролируя время жизни объектов.