[Перевод] GC в Go: приоритет на скорость и простоту

Перевод блог-поста главного автора сборщика мусора в Go, Ричарда Хадсона, изобретателя многих алгоритмов для GC в других языках, одного из ведущих инженеров Intel (сейчас работает в Google).

Go планирует свой сборщик мусора (GC) не только для 2015 года, но и для 2025 и дальше: это должен быть GC, который поддерживает современные принципы разработки программ и хорошо масштабируется вместе с появлением нового софта и железа в следующие десятилетия. В этом будущем нет места для пауз GC с «остановкой мира» (stop-the-world), которые были преградой для более широкого применения таких безопасных и надёжных языков, как Go.

Go 1.5, первый проблеск этого будущего, достиг цели уменьшить верхнюю планку пауз до 10 мс, которую мы поставили перед собой год назад. Некоторые впечатляющие цифры вы можете посмотреть в докладе на GopherСon. Эти улучшения времени отклика привлекли много внимания; блог пост Робина Верлангена «Миллиарды запросов в день встречают Go 1.5» подтверждает наши расчеты реальными результатами. Отдельно нам понравились скриншоты графиков продакнш-сервера от Алана Шреве и его комментарий «Holy 85% reduction!».
Сегодня 16 гигабайт памяти стоят 100$ и все процессоры многоядерны, и поддерживают гипертрединг. Через 10 лет это железо будет выглядеть устаревшим, но программы написанные на Go сегодня должны будут уметь масштабироваться, чтобы работать на растущих ресурсах железа и быть готовыми к «следующему прорыву» (next big thing). Учитывая, что железо дает возможность наращивать пропускную способность, сборщик мусора Go разрабатывается так, чтобы отзывчивость и маленькие паузы были приоритетом, а тюнинг происходил одним ползунком. Go 1.5 это первый большой шаг в этом направлении, и эти первые шаги навсегда повлияют на дальнейшее развитие Go и на программы, написанные на нём. Этот пост даёт обзорную картинку того, что мы сделали в Go 1.5 сборщике.

Детали


Чтобы создать сборщик мусора для следующего десятилетия мы обратились к алгоритму, написанному несколько десятилетий назад. Новый сборщик мусора в Go является конкурентным (concurrent), трехцветным (tri-color), mark-sweep сборщиком, идея которого впервые была предложена Дейкстрой в 1978 году. Этот подход намеренно так сильно несоответствует большинству современных сборщиков мусора «энтерпрайз»-уровня, и мы считаем, что это наилучший подход для современного железа и требований к паузам на новом железе.

В трехцветном сборщике мусора, каждый объект может быть помечен, как белый, серый или чёрный, и мы рассматриваем кучу (heap) как граф связанных объектов. В начале каждого цикла GC все объекты белые. GC проходит всё корневые узлы (roots) графа, которые являются объектами, напрямую доступными программе — это глобальные переменные и переменные в стеке — и помечает их серыми. Затем GC выбирает серый объект, делает его чёрным, а затем сканирует его на наличие указателей и других объектов. Если скан обнаруживает указатель на белый объект, он делает его серым. Этот процесс повторяется, пока не останется серых объектов. В этот момент все белые объекты будут считаться недостижимыми и могут быть переиспользованы.

Это всё происходит параллельно с работой программы, также называемой мутатором (mutator), изменяющей указатели по мере того, как работает сборщик. Из этого следует, что мутатор должен поддерживать инвариант того, что ни один черный объект не указывает на белый, чтобы сборщик мусора не потерял след объекта в той части кучи, которую он уже обошел. Поддержка такого инварианта это задача для «барьеров записи» (write barrier), которая по сути является маленькой функцией, запускающейся каждый раз, когда мутатор меняет указатель в куче. Барьер записи в Go помечает серым объекты, которые были белыми, гарантируя, что сборщик мусора рано или поздно просканирует его.

Определение момента, когда все объекты просканированы — тонкая задача и может быть очень дорогостоящей и сложной, если мы хотим избежать блокировок мутатора. Для простоты Go 1.5 делает максимум возможного в фоне, а потом приостанавливает программу на совсем короткое время, чтобы проверить все потенциально серые объекты. Найти идеальное соотношение для времени необходимого для этой паузы и для всей работы GC является одной из главных задач для Go 1.6.

Конечно же, дьявол кроется в деталях. Когда начинать очередной цикл GC? Какую метрику использовать для принятия этого решения? Как должны взаимодействовать GC и планировщик Go? Как останавливать потоки мутатора так, чтобы хватило времени на сканирование их стеков? Как мы представляем белые, серые и черные объекты, чтобы максимально эффективно искать и сканировать серые объекты? Как мы узнаём, где их корневые узлы? Как мы узнаём, где находятся указатели в объекте? Как мы минимизируем фрагментацию памяти? Как мы решаем вопросы производительности кешей? Насколько большой должна быть куча? И так далее, и тому подобное, кое-что относящееся к аллокациям, кое-что к поиску достижимых объектов, кое-что к планированию, но основные вопросы затрагивают производительность. Дискуссии о более низкоуровневых деталях каждой из этих областей выходят за рамки этого поста.

На более высоком уровне, один из подходов решения этих проблем для GC является добавление в GC ползунков (knobs), по одному на каждую задачу. Разработчик тогда может тюнить GC под себя, настраивая множество параметров. Минус тут в том, что через 10 лет с одним или двумя новыми ползунками каждый год, вы в итоге заканчиваете Трудовым Договором Об Использовании Переключателей GC. Go не пойдёт этим путём. Вместо этого мы даём лишь один ползунок, называемый GOGC. Его значение контролирует общий размер кучи относительно размера достижимых объектов. Дефолтное значение »100» означает, что общий размер кучи сейчас на 100% больше (тоесть, вдвое) размера реально достижимых объектов после последнего цикла GC.»200» означает, что общий размер кучи на 200% больше (тоесть, в три раза), чем размер реально используемых объектов. Если вы хотите уменьшить общее количество времени работы GC, увеличьте GOGC. Если вы хотите отдать больше времени GC, и выиграть себе память — уменьшайте GOGC.

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

Заключение


Сборщик мусора Go 1.5 вводит нас в будущее, где паузы с остановкой мира более не являются преградой для безопасного и надежного языка. Это будущее, где приложения масштабируются без усилий вместе с новым железом, и, по мере того, как железо становится всё более мощным, сборщик мусора не будет помехой для ещё лучшего, и ещё более масштабирующегося софта. Это хорошее место для следующего десятилетия и того, что будет за ним. Если вы хотите узнать подробности, как мы убрали проблемы с паузами, посмотрите доклад Go GC: Latency Problem Solved presentation или слайды доклада.

© Habrahabr.ru