β

Как стать автором
Погнали в космос?
Да случится мэтч: оцени совместимость с IT в ритейле

Моя лентаВсе потоки

363.6

Рейтинг

AvitoTech
У нас живут ваши объявления

Подписаться

Jimiliani2 15 авг 2023 в 12:30

Go's Garbage Collection: как работает и почему это важно знать

7 мин

52K

Блог компании AvitoTechGo*

Привет! Меня зовут Дмитрий Королёв, я бэкенд-разработчик в Авито. Я хочу рассказать, как устроен сборщик мусора в 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: все объекты в стадии разметки красятся в чёрный, серый или белый цвет:

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

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

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

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

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

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

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

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

Если в графе остались серые объекты, вернуться к шагу 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 причины:

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

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

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

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

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

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

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

Теги:

garbage collector

write barriers

go

Хабы:

Блог компании AvitoTech

Go

+17

219

17
+17

AvitoTech
У нас живут ваши объявления

Подписаться

ВКонтактеGithubTelegram

15

Карма

0

Рейтинг

Дмитрий @Jimiliani2

Go/Python json перекладыватель

Подписаться

Telegram

Комментарии 17
+17

Публикации

Лучшие за суткиПохожие

A_Tsymbalyuk 13 часов назад

Физика ошибок не прощает. Она догонит тебя на крыше и заставит платить (дважды)

Простой

6 мин

8.2K

Кейс

+40

35

25
+25

BabayMazay 12 часов назад

Самодельные французские радиолампы 1920 г. Часть 3. Разрядная трубка, лампа накаливания

Средний

9 мин

1.5K

Ретроспектива

+33

9

11
+11

Bright_Translate 8 часов назад

Как я от нечего делать замедлил Postgres в 42 000 раз

Средний

11 мин

2.7K

Кейс

Перевод

+27

20

2
+2

butivskiydm 11 часов назад

Моё мини-исследование про продолжительность жизни в России

Простой

2 мин

6.4K

Мнение

+22

17

63
+63

lokosst 13 часов назад

Выделенные серверы + Kubernetes: практическое руководство

17 мин

2.4K

Туториал

+21

23

0

JetHabr 11 часов назад

«Плохие парни работают просто»: пентестеры разбирают реальные кейсы

Средний

9 мин

2.1K

Кейс

+17

19

1
+1

k0mar0v 14 часов назад

HTC Desire HD: история, дизайн и возможности легендарного смартфона

6 мин

2.6K

+17

5

5
+5

MaFrance351 13 часов назад

Домофон Лидер-М. Как скрестить трубку с ключом и всем проиграть

Простой

4 мин

2.6K

+16

5

6
+6

psygalaxy 14 часов назад

Как мы ускорили проверку документации с помощью AI-агента: от боли к решению

Средний

25 мин

1.8K

Обзор

+16

30

9
+9

kubelet 16 часов назад

DNS-хаос, зомби-поды и майнеры в кластере: самые невероятные случаи при работе с Kubernetes

Простой

14 мин

1.2K

Кейс

+16

23

1
+1

Показать еще

Информация

Сайт

avito.tech

Дата регистрации

27 мая 2016

Дата основания

2007

Численность

5 001–10 000 человек

Местоположение

Россия

Представитель

vvroschin

ВКонтакте

Виджет

Виджет

Виджет

Блог на Хабре

31 июл в 18:18

Как подготовиться к переходу на роль тимлида и как вернуться, если не вывезли

4.8K

0

28 июл в 16:16

Sigma + Trisigma = 4Sigma или как мы сделали эксперименты еще удобнее

7.1K

1
+1

25 июл в 18:18

Опыт эксплуатации Service Mesh в Авито

3.7K

10
+10

22 июл в 14:14

Сетап А/В-теста, который помог снизить MDE выручки в 2 раза

4.9K

2
+2

17 июл в 18:18

Как стать идеальным менеджером и не выгореть: советы из практики

8.2K

2
+2

Ваш аккаунт

Профиль

Трекер

Диалоги

Настройки

ППА

Разделы

Статьи

Новости

Хабы

Компании

Авторы

Песочница

Информация

Устройство сайта

Для авторов

Для компаний

Документы

Соглашение

Конфиденциальность

Услуги

Корпоративный блог

Медийная реклама

Нативные проекты

Образовательные программы

Стартапам

Настройка языкаТехническая поддержка
© 2006–2025, Habr