Привет! Меня зовут Дмитрий Королёв, я бэкенд-разработчик в Авито. Я хочу рассказать, как устроен сборщик мусора в Golang и как он работает, чтобы вы могли писать более производительные приложения и лучше понимать внутреннее устройство языка.  

За последние 10 лет сборщик мусора в golang ускорился более чем в 400 раз. И это не предел. Расскажу, как разработчики этого добились, — от базовой имплементации до нетривиальных оптимизаций.

Mark and Sweep Garbage Collector — кто такой?

Mark and Sweep — популярный алгоритм для сборщиков мусора. Он или его модификации много лет работают сейчас или работали ранее в Java, Python, Lua и других языках. Его работа состоит из 2 фаз:

• Mark: находим и отмечаем все достижимые объекты из набора (например, в куче).

• Sweep: проходим по всем объектам в куче, затираем недостижимые и возвращаем их в пул свободной памяти.

Если вы не знакомы с тем, как выделяется память в Golang, то рекомендую эту статью.

Набор объектов в наборе можно представить в виде графа, а работа алгоритма похожа на обход в ширину. Рассмотрим на примере:

До начала разметки есть граф неразмеченных объектов произвольного размера:

Разметка — шаг 1. Покрасили объект 1. Пул объектов, которые связаны с объектом 1 — 3 и 4:

Разметка — шаг 2. Покрасили объекты 3 и 4. Пул объектов, связанных с окрашенной частью графа — 6:

Разметка — шаг 3. Покрасили объект 6. Объектов, связанных с окрашенной частью графа, не осталось. Пришло время чистить мусор:

Объекты 2 и 7 недостижимы, их можно переработать:

Память недостижимых объектов отмечается доступной для перезаписи или сразу возвращается системе. 

В Golang память отмечается доступной для перезаписи, запускается горутина, которая постепенно возвращает её системе. За этот процесс отвечает Scavenger. Все достижимые объекты продолжают жить нетронутыми:

Чтобы операция прошла корректно, программа должна быть приостановлена во время стадии разметки (Mark). Такая пауза в выполнении называется Stop The World (STW). 

STW — очевидное зло с точки зрения перфоманса приложений. Любой язык с механизмом сборки мусора стремится сократить его влияние до минимума.

Алгоритмы для уменьшения STW в Golang

Популярное решение для уменьшения STW — имплементация алгоритма трёхцветной маркировки (Three-color Marker Algorithm). Этот подход работает и в Golang: все объекты в стадии разметки красятся в чёрный, серый или белый цвет:

• белый — потенциальный мусор, ещё не затронутые алгоритмом объекты;

• серый — объекты «на рассмотрении»;

• чёрный — активные объекты.

Изначально все объекты в куче и на стеке окрашены в белый.

В целом, алгоритм можно представить циклом из нескольких шагов:

1. Покрасить все корневые объекты (стек и глобальные переменные) в серый.

2. Выбрать серый объект из набора серых объектов и пометить его как чёрный.

3. Все объекты, на которые указывает чёрный объект, пометить серым. Это гарантирует, что сам объект и объекты, на которые он ссылается, не будут выброшены в мусор.

4. Если в графе остались серые объекты, вернуться к шагу 2.

Рассмотрим пример

Шаг 1:

Шаг 2:

Шаг 3:

Шаг 4:

Шаг 5 (уже повторяем с шага 2):

Шаг 6:

Серые объекты кончились, но белые остались. Вот мы и нашли мусор! Теперь эти участки при необходимости могут быть перезаписаны.

Но есть проблема. Чтобы сборщик мусора работал, мы обязаны делать STW и за один заход проходиться сразу по всем объектам в памяти программы. А вот что будет, если попробовать красить итерационно.

Сейчас граф объектов окрашен таким образом:

Представим, что в процессе окраски мы создали связь между белым объектом и уже окрашенным в чёрный. При этом у белого объекта больше нет связей. Тогда алгоритм покраски его не затронет и в итоге он будет отмечен как мусор. Это фатальная ошибка для любого приложения.

В текущей реализации стадия покраски требует STW. Этот период в ранних версиях Go достигал сотен миллисекунд, а это довольно значительное время. От этого как-то хочется избавиться.

Что такое Write Barrier и зачем они нам

Кажется, что стоит научиться собирать мусор пошагово, по маленьким кусочкам, то есть амортизировать алгоритм. Тогда не придётся не останавливать выполнение программы на длительный период времени. Сборщик мусора с таким алгоритмом называется Incremental Garbage Collector.

Для пошаговой сборки мусора нужны гарантии, что если во время покраски добавить или удалить связи между объектами, графы останутся правильно окрашенными.

Write Barrier — это фрагмент кода, который выполняется при работе с памятью. Нам он нужен для поддержки инвариантов, которые гарантируют правильное пошаговое выполнение алгоритма. Звучит сложно, но на примерах станет понятнее.

Проведу небольшой экскурс в историю Go, чтобы понять, почему он устроен так, как устроен.

До версии Go 1.8 использовали Dijkstra insertion write barrier. Работал он так:

func writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

slot — это место назначения (например, переменная) в коде Go.

ptr — это значение, которое помещается в слот в коде Go.

shade — превращает белые объекты в серые, серые и чёрные оставляет нетронутыми.

insertion в названии говорит о том, что триггером для его вызова служит создание связи между объектами.

Таким образом, если мы пишем x = y, то y всегда после этого будет серым:

Теперь мы стабильно поддерживаем такой инвариант: чёрные объекты указывают только на серые или другие чёрные объекты, а на белые — не указывают:

Это выглядит просто, работает корректно — что ещё нам надо? Есть подвох. Для объектов на стеке вместо включения Write Barrier был выбран другой подход. Их просто автоматом считали серыми, чтобы не нести потери в перформансе приложений. Но без Write Barrier нет гарантии, что мы не прикрепим белый объект к чёрному на стеке. 

Чтобы этого избежать, на каждом шаге покраски стек заново покрасится в серый после выполнения программы. По всем объектам заново пройдётся сборщик мусора. Если обнаружится новая связь с белым объектом, он также будет перекрашен в серый.

Для приложений с большим количеством горутин этот период может достигать до 100 мс. Но считается, что этот подход оптимальнее использования Write Barrier на стеке.

Начиная с Go 1.8 придумали совместить Dijkstra insertion write barrier и Yuasa deletion write barrier. Deletion в названии означает, что триггером для вызова служит удаление связи между объектами.

Псевдокод для описания его работы:

func writePointer(slot, ptr)

   shade(slot)

   slot = ptr

Рассмотрим тот же пример, который приводился перед вводом write barriers:

Создание связи между объектами не триггерит Yuassa write barrier:

А вот удаление связей триггерит:

Таким образом мы не теряем белые объекты. Yuasa write barrier даёт такой инвариант: у любого белого объекта, на который указывает чёрный объект, должен быть достижимый путь до серого объекта.

Из этих двух Write barrier получается Hybrid Write Barrier:

func writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

Этот Write Barrier затеняет объект, на который перезаписывается ссылка. Если стек текущей горутины ещё не просканирован, то он затеняет и устанавливаемый объект

С гибридным барьером не нужно повторное сканирование стека. После того, как он был отсканирован и затемнён, он остаётся чёрным.

Этот Write Barrier гарантирует выполнение условий:

• чёрные объекты не указывают на белые объекты, только на серые или другие черные объекты (dijkstra write barrier);

• любой белый объект, на который указывает черный объект, должен иметь достижимый путь до серого объекта (yuasa write barrier)

А эти условия гарантируют корректность пошаговой покраски графа. Больше информации и доказательство корректности можно найти здесь. Все новые объекты, создаваемые в процессе работы алгоритма сразу помечаются чёрными, чтобы точно их не потерять.

Это может быть проблемой для некоторых приложений. Если создать очень много короткоживущих объектов, то все они точно доживут до следующей итерации GC.

Теперь мы знаем, как Golang избавился от долгих пауз в выполнении программы — Garbage Collector стал Incremental. Но стала ощутимее другая проблема: время работы сборщика мусора стало больше. Вот как выглядит процесс его работы:

Немного о Concurrent garbage collector

Очевидный вариант оптимизации — использовать все имеющиеся процессоры. Это кратно ускорит время работы GC:  

Тут есть блок, в котором сборщик работает везде и одновременно. Это не случайно, некоторая часть его работы требует STW. Полностью от него избавиться не выйдет.

Стадии работы GC

Текущая стадия работы сборщика мусора хранится в глобальной переменной gcphase.

1. Sweep Termination. Останавливаем мир 🙂 Это нужно, чтобы все процессоры дошли до точки, когда можно безопасно запустить GC. После этого все блоки памяти, отмеченные как мусор, отправляются «на съедение» Scavenger. Потом он вернёт их ОС. Это позволяет не запрашивать у ОС больше памяти, чем требуется приложению. В обычных обстоятельствах к началу работы GC вся «мусорная» память уже возвращена системе. Необычным обстоятельством может считаться ручной запуск GC.

2. Mark. Глобальная переменная gcphase выставляется в значение _GCmark. Включается Write Barrier. Создаются и ставятся в очередь джобы с покраской корневых вершин. Корневые вершины — это глобальные переменные и всё содержимое стека.

Запускаем мир. Теперь маркировка объектов происходит в специальных воркерах-малярах, запущенных шедулером. Эти воркеры в проходятся по всем объектам в куче и на стеке. Новые аллоцированные объекты сразу красятся в чёрный. Чтобы просканировать стек горутины, её останавливают, прокрашивают стек и снова запускают.

Так продолжается до тех пор, пока не закончатся серые объекты. В этой фазе GC забирает до 25% от CPU, это число зашито внутри runtime go (см. раздел Latency в Gc Guide).

Mark Termination. Останавливаем мир, выставляем gcphase на _GCmarktermination, выключаем воркеров, которые красили объекты в памяти. runtime готовит будущую работу программы. Например, чистит кеш у M.

Sweep. Выставляем gcphase на _GCoff, выключается Write Barrier. Запускаем мир. Теперь новые аллоцированные объекты будут покрашены в белый. Аллокация может происходить поверх блоков памяти, отмеченных как мусор. Кроме того, будет запущена горутина, которая будет постепенно возвращать мусорную память ОС.

Здорово, теперь мы знаем как работает гошный GC! А когда он запускается?

Есть 3 причины:

1. Превышение динамического лимита «сожранной» приложением памяти, установленного с помощью переменной GOGC. Об этом подробно расписано в Guide to the Go Garbage Collector, поэтому я не буду заострять на этом внимание.

2. Прошло 2 минуты без GC. Да, даже если вы ничего не аллоцировали за это время, GC все равно запустится раз в 2 минуты. За это ответственен Sysmon — особый тред приложения. Он отвечает за запуск GC по таймеру, preemption горутин и другие важные функции. Этот способ можно отключить, выставив значение GOGC < 0. 

3. Ручной запуск с помощью runtime.GC(). Если сделать этот вызов, когда Garbage Collector уже запущен, то по достижении фазы Sweep он запустится заново.

Для чего это всё нужно знать

GC в Golang стал неотъемлемой частью языка. Он позволяет разработчикам сосредоточиться на бизнес-логике и функциональности приложения, не беспокоясь о ручном управлении памятью. Если у вас есть базовое понимание принципов работы сборщика мусора в Golang, то вы сможете оптимизировать ваш код и создавать более эффективные приложения. 

Надеюсь эта статья была вам полезна. Успехов!

Предыдущая статья: «Возьмите инициативу на себя»: готовимся к System Design Interview