Привет, суслики! Сегодня я хочу рассказать о том, как устроен сборщик мусора в Golang и как он работает, чтобы вы могли писать более производительные приложения и лучше понимать внутреннюю работу языка.
За последние 10 лет сборщик мусора в Голанге ускорился более чем в 400 раз. И это не предел. Расскажу, как разработчики этого добились — от базовой реализации до нетривиальных оптимизаций.
Давайте кодировать!
Марк и подмети Сборщик мусора — кто это?
Mark and Sweep — популярный алгоритм для сборщиков мусора. Он или его модификации уже много лет работают или работали ранее на Java, Python, Lua и других языках. Его работа состоит из 2 этапов:
Отметить: найти и пометить все доступные объекты в наборе (например, в куче).
Развертка: перебирать все объекты в куче, стирать недоступные и возвращать их в пул свободной памяти.
Множество объектов в множестве можно представить в виде графа, а работа алгоритма аналогична обходу по ширине. Давайте рассмотрим пример:
Перед началом разделения имеется граф непомеченных объектов произвольного размера:
Память недоступных объектов помечается доступной для перезаписи или немедленно возвращается в систему.
В Голанге память помечается доступной для перезаписи, запускается горутина, которая постепенно возвращает ее в систему. За этот процесс отвечает Мусорщик. Все доступные объекты продолжают жить нетронутыми:
Чтобы операция прошла правильно, программу необходимо приостановить на этапе маркировки. Эта пауза в исполнении называется «Остановить мир» (STW).
STW — очевидное зло с точки зрения производительности приложений. Любой язык с механизмом сборки мусора стремится минимизировать его влияние.
Алгоритмы уменьшения STW в Golang
Популярным решением для уменьшения STW является реализация алгоритма трехцветного маркера. Этот подход работает и в Golang: все объекты на этапе маркировки окрашиваются в черный, серый или белый цвет:
- белый — потенциальный мусор, объекты, еще не затронутые алгоритмом;
- серый — объекты «на рассмотрении»;
- черный — активные объекты.
Изначально все объекты в куче и стеке окрашены в белый цвет.
В целом алгоритм можно представить циклом из нескольких шагов:
- Закрасьте все корневые объекты (стек и глобальные переменные) серым цветом.
2. Выберите серый объект из набора серых объектов и отметьте его как черный.
3. Отметьте все объекты, на которые указывает черный объект, как серые. Это гарантирует, что сам объект и объекты, на которые он ссылается, не будут выброшены в корзину.
4. Если на графике остались серые объекты, вернитесь к шагу 2.
Давайте посмотрим на пример
Шаг 1:
Шаг 2:
Шаг 3:
Шаг 4:
Шаг 5 (уже повторен, начиная с шага 2):
Шаг 6:
Серые предметы исчезли, а белые остались. Теперь мы нашли мусор! Теперь эти графики при необходимости можно перезаписать.
Но есть проблема. Чтобы сборщик мусора работал, мы должны выполнить STW и пройти по всем объектам в памяти программы за один раз. Но вот что произойдет, если мы попытаемся рисовать итеративно.
Теперь граф объектов раскрашен таким образом:
Представим, что в процессе раскрашивания мы создали связь между белым объектом и объектом, уже окрашенным в черный цвет. При этом у белого объекта больше нет связей. Тогда алгоритм раскраски на него не повлияет и в итоге он будет помечен как мусор. Это фатальная ошибка для любого приложения.
В текущей реализации для этапа покраски требуется STW. Этот период в ранних версиях Go достигал сотен миллисекунд, что является весьма значительным временем. Нам хотелось бы от этого как-то избавиться.
Что такое барьеры записи и зачем они нам нужны
Похоже, надо научиться собирать мусор поэтапно, небольшими кусочками, т. е. амортизировать алгоритм. Тогда вам не придется останавливать выполнение программы на длительный период времени. Сборщик мусора с таким алгоритмом называется инкрементным сборщиком мусора.
Пошаговая сборка мусора требует гарантий того, что если в процессе рисования будут добавлены или удалены связи между объектами, графы останутся правильно раскрашенными.
Барьер записи — это фрагмент кода, который выполняется во время обработки памяти. Оно нам нужно для поддержки инвариантов, гарантирующих правильное пошаговое выполнение алгоритма. Звучит сложно, но на примерах станет понятнее.
Я расскажу вам немного истории Go, чтобы понять, почему он устроен именно так.
До Go 1.8 мы использовали барьер записи вставки Дейкстры. Это работало следующим образом:
func writePointer(slot, ptr):
shade(ptr)
*slot = ptr
- slot — это пункт назначения (например, переменная) в коде Go.
- ptr — это значение, которое помещается в слот кода Go.
- оттенок — превращает белые объекты в серые, серые и черные объекты остаются нетронутыми.
- вставка в названии говорит о том, что триггером его вызова является создание связи между объектами.
Таким образом, если мы напишем x = y, то y после этого всегда будет серым:
Теперь мы стабильно поддерживаем этот инвариант: черные объекты указывают только на серые или другие черные объекты, а белые объекты — нет:
Выглядит просто, работает корректно — что еще нам нужно? Есть подвох. Для объектов в стеке был выбран другой подход вместо включения барьера записи. Они просто были автоматически выделены серым цветом, чтобы не потеряться в производительности приложения. Но без барьера записи нет никакой гарантии, что мы не прикрепим белый объект к черному объекту в стеке.
Чтобы этого избежать, на каждом этапе рисования стек после выполнения программы перекрашивается в серый цвет. Все объекты будут пройдены сборщиком мусора заново. Если будет обнаружено новое соединение с белым объектом, он также будет перекрашен в серый цвет.
Для приложений с большим количеством горутин этот период может доходить до 100 мс. Но такой подход считается более оптимальным, чем использование Write Barrier в стеке.
Начиная с Go 1.8, было изобретено объединение барьера записи вставки Дейкстры и барьера записи удаления Юасы. Удаление в имени означает, что триггером вызова является удаление связи между объектами.
Псевдокод, описывающий, как это работает:
func writePointer(slot, ptr) shade(slot) slot = ptr
Давайте рассмотрим тот же пример, который был приведен до введения барьеров записи:
Создание связи между объектами не активирует барьер записи Yuassa:
С другой стороны, удаление связей запускает:
Таким образом мы не теряем белые предметы. Барьер записи Yuasa дает этот инвариант: любой белый объект, на который указывает черный объект, должен иметь достижимый путь к серому объекту.
Из этих двух барьеров записи мы получаем гибридный барьер записи:
func writePointer(slot, ptr):
shade(*slot)
if current stack is grey:
shade(ptr)
*slot = ptr
Этот барьер записи скрывает объект, на который перезаписывается ссылка. Если стек текущей горутины еще не просканирован, то он также скрывает устанавливаемый объект
При использовании гибридного барьера нет необходимости повторно сканировать стек. После сканирования и затемнения он остается черным.
Этот барьер записи гарантирует выполнение следующих условий:
- черные объекты не указывают на белые объекты, а только на серые или другие черные объекты (барьер записи Дейкстры);
- любой белый объект, на который указывает черный объект, должен иметь достижимый путь к серому объекту (барьер записи юаса)
И эти условия гарантируют корректность пошаговой раскраски графика. Более подробную информацию и подтверждение правильности можно найти здесь. Все новые объекты, созданные в ходе работы алгоритма, сразу помечаются черным, чтобы их наверняка не потерять.
Это может быть проблемой для некоторых приложений. Если вы создадите много недолговечных объектов, то все они обязательно доживут до следующей итерации GC.
Теперь мы знаем, как Golang избавился от длительных пауз в выполнении программы — сборщик мусора стал инкрементальным. Но заметнее стала другая проблема: время работы сборщика мусора стало больше. Вот как выглядит процесс его работы:
Немного о параллельном сборщике мусора
Очевидный вариант оптимизации — использовать все доступные процессоры. Это кратное ускорение времени работы GC:
Есть блок, в котором коллектор работает везде и одновременно. Это не случайно, некоторые его работы требуют STW. Полностью избавиться от него не удастся.
Этапы работы ГК
Текущая стадия работы сборщика мусора хранится в глобальной переменной gcphase.
1. Завершение очистки. Остановка мира 🙂 Необходимо, чтобы все процессоры достигли точки, в которой безопасно запускать GC. После этого все блоки памяти, помеченные как мусор, отправляются «на съедение» Scavenger. Потом он вернет их в ОС. Это позволяет не запрашивать у ОС больше памяти, чем нужно приложению. В обычных условиях к старту GC вся «мусорная» память уже возвращена в систему. Необычным обстоятельством можно считать запуск ГХ вручную.
2. Отметить. Глобальной переменной gcphase присвоено значение _GCmark. Барьер записи включен. Задания с отрисовкой корневых вершин создаются и ставятся в очередь. Корневые вершины — это глобальные переменные и все содержимое стека.
Запускаем мир. Теперь маркировка объектов происходит в специальных воркеров-малярах, запускаемых шадулером. Эти рабочие процессы просматривают все объекты в куче и в стеке. Новые выделенные объекты сразу окрашиваются в черный цвет. Сканировать стек горутины, он останавливается, стек окрашивается и запускается заново.
Так продолжается до тех пор, пока не закончатся серые предметы. На этой фазе GC занимает до 25% ресурсов ЦП, это количество зашито внутри runtime go (см. раздел Latency в Gc Guide).
Отметить завершение. Останавливаем мир, устанавливаем gcphase в _GCmarktermination, отключаем воркеров, рисовавших объекты в памяти. среда выполнения подготавливает будущую работу программы. Например, очищает кэш от M.
Развертка. Мы устанавливаем для gcphase значение _GCoff, барьер записи отключается. Запускаем мир. Теперь вновь выделенные объекты будут окрашены в белый цвет. Выделение может происходить поверх блоков памяти, помеченных как мусор. Кроме того, будет запущена горутина, которая будет постепенно возвращать мусорную память ОС.
Отлично, теперь мы знаем, как работает государственный GC! И когда оно начинается?
Есть 3 причины:
- Превышение динамического лимита пожираемой приложением памяти, заданного с помощью переменной GOGC. Подробно это описано в Руководстве по сборщику мусора Go, поэтому я не буду на этом заострять внимание.
2. Прошло 2 минуты без GC. Да, даже если вы за это время ничего не выделили, GC все равно будет запускаться каждые 2 минуты. За это отвечает Sysmon — специальный поток приложения. Он отвечает за запуск GC по таймеру, вытеснение горутины и другие важные функции. Этот метод можно отключить, установив значение GOGC ‹ 0.
3. Запуск вручную с помощью runtime.GC(). Если вы сделаете этот вызов, когда сборщик мусора уже запущен, то при достижении фазы очистки он запустится снова.
Зачем тебе все это знать
GC в Golang стал неотъемлемой частью языка. Это позволяет разработчикам сосредоточиться на бизнес-логике и функциональности приложения, не беспокоясь о ручном управлении памятью. Если у вас есть базовое представление о том, как работает сборщик мусора в Golang, вы сможете оптимизировать свой код и создавать более эффективные приложения.
Вот и все, ребята! Надеюсь моя статья поможет вам в вашем бизнесе
Спасибо, что прочитали это! Ждем ваших комментариев и предложений 😎✌
