[Перевод] Современный подход к сборке мусора03.01.2017 21:18

В последнее время мне встречалось немало статей, в которых не самым удачным для меня образом продвигается свежий сборщик мусора в Go. Некоторые из статей написали разработчики самого языка, и их утверждения намекали на радикальный прорыв в технологии сборки мусора.

Вот первичный анонс о внедрении нового сборщика, датированный августом 2015-го:

В Go создаётся сборщик мусора (GC) не только для 2015 года, но и для 2025-го, и ещё дальше… Сборщик в Go 1.5 возвещает о наступлении будущего, в котором паузы на сборку больше не являются барьером для перехода на безопасный язык. Это будущее, в котором приложения без труда масштабируются вместе с оборудованием, и по мере роста мощности оборудования сборщик мусора больше не является сдерживающим фактором при создании более качественного, масштабируемого ПО. Go — хороший язык для использования как минимум в ближайший десяток лет.

Создатели утверждают, что они не просто решили проблему пауз на сборку мусора, а пошли куда дальше:

Одним из высокоуровневых способов решения проблем с производительностью является добавление GC-настроек (knobs), по одной на каждую проблему. Программист может менять их, подбирая наилучшую комбинацию для своего приложения. Недостатком этого подхода является то, что при внедрении каждый год одной-двух новых настроек через десять лет придётся законодательно регулировать труд людей, которые будут менять эти настройки. Go не пошёл по этому пути. Вместо кучи настроек мы оставили одну и назвали её GOGC.

Более того, освободившись от бремени поддержки десятков настроек, разработчики могут сосредоточиться на улучшении runtime«а приложения.

Не сомневаюсь, что многие пользователи Go были просто счастливы получить новый подход к runtime«у в Go. Но у меня есть претензии к этим заявлениям: они выглядят как недостоверный маркетинговый булшит. А поскольку они раз за разом воспроизводятся в Сети, пришло время подробно с ними разобраться.

Реальность такова, что в сборщике мусора в Go не реализовано никаких новых идей или результатов исследований. Как признаются сами авторы, это просто сборщик с параллельной пометкой и очисткой, основанный на идеях 1970-х. Это примечательно лишь потому, что сборщик был разработан для оптимизации продолжительности пауз за счёт всех остальных важных характеристик сборщика. В технических и маркетинговых материалах Go не упоминается обо всех этих побочных эффектах, поэтому многие программисты не подозревают об их существовании. В результате создаётся впечатление, что конкурентные языки — плохо спроектированный шлак. И авторы Go лишь подогревают эти мысли:

Для создания сборщика на следующее десятилетие мы обратились к алгоритмам из десятилетий прошлых. В нашем сборщике реализован трёхцветный (tri-color) алгоритм параллельной пометки и очистки, предложенный Dijkstra в 1978 году. Это намеренное отличие от большинства современных сборщиков «корпоративного» класса, которое, как мы считаем, лучше всего соответствует особенностям современного оборудования и требованиям по уровню задержки в современном ПО.

Читаешь всё это, и возникает мысль, что за последние 40 лет в сфере «корпоративных» сборщиков мусора ничего лучше предложено не было.Введение в теорию сборки мусора
При разработке алгоритма сборки мусора нужно учитывать ряд факторов:

• Пропускная способность программы: насколько алгоритм замедлит скорость работы программы? Иногда это выражается в процентах: отношение времени процессора, потраченного на сборку, ко времени, потраченному на полезную работу.
• Пропускная способность сборщика: сколько мусора может вычистить сборщик за определённое время работы процессора?
• Избыточность кучи: сколько памяти сверх теоретического минимума потребуется сборщику? Если в ходе сборки он размещает в памяти временные структуры, не приведёт ли это к резкому росту потребления памяти программой?
• Продолжительность пауз: на какой срок сборщик останавливает работу программы?
• Частота пауз: как часто сборщик останавливает работу программы?
• Распределение пауз: большинство пауз очень короткие и лишь несколько очень длинные? Или вы предпочитаете делать длительность пауз более равномерной?
• Производительность размещения в памяти: размещение в новой памяти выполняется быстро, медленно или непредсказуемо?
• Уплотнение: выдаёт ли сборщик сообщение об отсутствии памяти (out-of-memory, OOM), даже если места для удовлетворения его запроса достаточно, но оно рассеяно по куче в виде маленьких чанков? Если не выдаёт, то программа может начать замедляться и в конце концов просто встать, даже если памяти для продолжения работы достаточно.
• Многопоточность: насколько эффективно сборщик использует многоядерные машины?
• Масштабирование: насколько эффективно сборщик работает по мере увеличения размера куч?
• Настройка: насколько сложно настроить сборщик прямо из коробки, а также для достижения оптимальной производительности?
• Продолжительность прогрева: является ли алгоритм самонастраивающимся на основе измерений собственного поведения? Если да, то как долго он выходит в оптимальный режим работы?
• Освобождение страницы: алгоритм возвращает операционной системе неиспользуемую память? Если да, то когда?
• Портируемость: работает ли сборщик на процессорных архитектурах, предоставляющих более слабые гарантии консистентности памяти по сравнению с x86?
• Совместимость: с какими языками и компиляторами работает сборщик? Можно ли запустить его с языком, который создавался без учёта использования сборщиков, например С++? Нужно ли модифицировать компилятор? Если да, потребуется перекомпилировать всю программу и зависимости при изменении алгоритма сборщика?

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

Из-за сложности пространства проектных параметров сборка мусора представляет собой подобласть информатики, богато освещённую в исследовательских работах. Новые алгоритмы предлагаются и внедряются регулярно, как в академической, так и в коммерческой среде. Но, к сожалению, никто ещё не создал алгоритма, подходящего для всех случаев жизни.

Кругом сплошные компромиссы
Разберёмся с этим подробнее.

Первые алгоритмы сборки мусора разработали для однопроцессорных компьютеров и программ с маленькими кучами. Ресурсы процессора и памяти были дороги, а пользователи — нетребовательны, так что к паузам в работе программ относились лояльно. Создававшиеся в те времена алгоритмы старались поменьше задействовать процессор и минимизировать избыточное потребление памяти в куче. Это означало, что сборщик ничего не делал до тех пор, пока программа могла размещать в памяти данные. Затем она вставала на паузу до полного выполнения пометки и очистки кучи, чтобы как можно скорее освободить часть памяти.

У старых сборщиков есть преимущества: они просты; не замедляют программу, если не выполняют свою работу; не приводят к избыточному потреблению памяти. Консервативные сборщики, например Boehm GC, даже не требуют вносить изменения в компилятор или язык программирования! Это делает их подходящими для настольных приложений (обычно их кучи маленького размера), в том числе для видеоигр категории ААА; в них большая часть памяти занята файлами с данными, которые не нужно сканировать.

Алгоритмы, для которых характерны паузы полной остановки (Stop-the-world, STW) для выполнения пометки и очистки, чаще всего изучают на курсах по информатике. Иногда на собеседованиях я прошу кандидатов немного рассказать о сборке мусора. И чаще всего они представляют сборщик как чёрную коробку, внутри которой неизвестно что происходит, либо считают, что в нём используется очень старая технология.

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

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

На мощных системах вы также можете выполнять большие пакетные задания. Для них важны не паузы, а только общее время выполнения. В таких случаях лучше использовать алгоритм, который максимизирует пропускную способность (throughput), то есть отношение выполненной полезной работы ко времени, потраченному на сборку мусора.

Увы, нет ни одного алгоритма, полностью идеального. Также runtime ни одного языка не может определить, является ли ваша программа пакетным заданием или интерактивной программой, чувствительной к задержкам. Именно это, а не глупость разработчиков runtime«а, привело к появлению «настроек сборщика мусора». Это следствие фундаментальных ограничений информатики.

Гипотеза поколений (generational hypothesis)
В 1984 году было подмечено, что большинство размещений в памяти «умирают молодыми», то есть становятся мусором через очень короткое время после размещения. Это наблюдение, названное гипотезой поколений, — одно из сильнейших эмпирических наблюдений в сфере разработки языков программирования. Гипотеза вот уже несколько десятилетий подтверждается для самых разных языков: функциональных, императивных, не имеющих и имеющих типы данных.

Гипотеза поколений принесла пользу в том смысле, что алгоритмы сборки мусора стали использовать её плюсы. Так появились сборщики на основе поколений (generational collectors), которые имели ряд преимуществ по сравнению со старыми алгоритмами «остановить — пометить — очистить»:

• Пропускная способность сборщика: они могут собирать гораздо больше мусора и гораздо быстрее.
• Производительность размещения в памяти: при размещении новой памяти больше не нужно искать свободные слоты в куче. Так что размещение, по сути, стало бесплатным.
• Пропускная способность программы: фрагменты памяти стали аккуратно размещаться рядом друг с другом, что сильно улучшило эффективность использования кеша. Сборщики на основе поколений требуют, чтобы программа выполняла определённую работу по мере выполнения, но на практике это перевешивается преимуществами от изменений в работе кеша.
• Продолжительность пауз: большинство пауз (но не все) становятся короче.

Но у таких сборщиков есть и недостатки:

• Совместимость: алгоритмы перемещают данные в памяти и делают дополнительные манипуляции, когда программа в некоторых случаях пишет в указатель. Это означает, что сборщик должен быть тесно интегрирован с компилятором. Для С++ не существует сборщиков на основе поколений.
• Избыточность кучи: такие сборщики копируют фрагменты памяти туда и обратно между разными «пространствами». Поскольку должно быть достаточно места для копирования, возникает определённая избыточность размера кучи. К тому же такие сборщики требуют поддержки различных карт указателей (запоминаемые множества — remembered sets), что ещё больше повышает избыточность.
• Распределение пауз: хотя многие паузы очень коротки, иногда всё же требуются полные остановки на пометку и очистку в рамках всей кучи.
• Настройка: сборщики на основе поколений ввели понятие «молодое поколение», или «райское пространство» (eden space), и от его размера сильно зависит производительность программы.
• Продолжительность прогрева: в ответ на проблему настройки некоторые сборщики динамически адаптируют размер молодого поколения на основе данных о поведении выполняемой программы. Но теперь паузы стали зависеть и от продолжительности работы программы. Обычно это важно только для результатов бенчмарков.

Тем не менее выигрыш от использования сборщиков на основе поколений так велик, что сегодня этот тип абсолютно доминирует. Если вы готовы смириться с недостатками, то вам наверняка понравятся такие сборщики. Эти алгоритмы можно расширять всевозможными функциями, типичные современные сборщики могут быть в одном лице многопоточными, параллельными, уплотняющими (compacting) и использующими поколения.Параллельный сборщик в Go
Go — довольно обыкновенный императивный язык с типами значений. Пожалуй, его шаблоны доступа к памяти можно сравнить с С#, в котором используется гипотеза поколений, следовательно, применяется сборщик .NET.

По факту программы на Go обычно требуют наличия обработчиков запросов/откликов вроде HTTP-серверов. То есть они демонстрируют поведение, сильно завязанное на поколениях. Создатели Go думают, как это можно использовать в будущем с помощью таких вещей, как «сборщик, ориентирующийся на запросы» (request oriented collector). Как уже заметили, это просто переименованный сборщик на основе поколений с настроенной политикой срока владения.
Можно эмулировать такой сборщик в других runtime«ах для обработчиков запросов/откликов. Для этого нужно удостовериться, что молодое поколение достаточно велико, чтобы в него поместился весь мусор, генерируемый при обработке запроса.

Но несмотря на это, используемый сегодня в Go сборщик — это не сборщик на основе поколений. Он просто выполняет в фоне старую добрую процедуру пометки с очисткой.

У такого подхода есть одно преимущество: можно получить очень-очень короткие паузы. Но все остальные параметры ухудшатся. Например:

• Пропускная способность сборщика: время, необходимое для очистки кучи от мусора, увеличивается с размером кучи. Чем больше памяти использует ваша программа, тем медленнее эта память освобождается и тем больше времени компьютер тратит на сборку по сравнению с полезной работой. Вы избежите всего этого, только если программа вообще не распараллеливает своё выполнение, но вы можете без ограничений продолжать использовать ядра для сборки мусора.
• Уплотнение: поскольку оно не выполняется, программа может в результате фрагментировать всю кучу. Об этом мы ещё поговорим ниже. Также вы не получите преимуществ от аккуратного использования кеша.
• Пропускная способность программы: в каждом цикле сборщик должен делать много работы. На это уходит больше времени процессора, которое могло быть отдано самой программе, а она из-за этого работает медленнее.
• Распределение пауз: сборщик, выполняющийся одновременно с программой, может привести к тому, что в мире Java называется сбоем режима совместного выполнения (concurrent mode failure): программа генерирует мусор быстрее, чем треды сборщика успевают его чистить. В этом случае runtime«у приходится полностью останавливать программу и ждать завершения цикла очистки. Так что когда авторы Go утверждают, что паузы очень короткие, то это относится только к случаям, когда сборщику достаточно времени процессора, чтобы не отставать от программы. Кроме того, компилятору Go не хватает возможностей, чтобы надёжно и быстро ставить треды на паузу. То есть длительность пауз сильно зависит от выполняемого вами кода (например, base64-декодирование крупного блоба в одиночной горутине может привести к увеличению пауз).
• Избыточность кучи: учитывая медленность сборки мусора в куче с помощью пометки и очистки, вам нужно много места в запасе, чтобы не столкнуться со сбоем режима совместного выполнения. По умолчанию в Go предусмотрена стопроцентная избыточность… то есть он удваивает объём памяти, необходимой вашей программе.

Вот отрывок из одного поста, в котором рассказывается о вышеописанных недостатках:

Сервис 1 размещает больше памяти, чем Сервис 2, поэтому паузы полной остановки у него длиннее. Однако у обоих сервисов абсолютная продолжительность пауз остановки уменьшается на порядок. После включения на обоих сервисах мы наблюдали ~20%-й рост потребления сборщиком времени процессора.

В данном случае продолжительность пауз в Go снизилась на порядок, но за счёт замедления работы сборщика. Можно ли это счесть оправданным компромиссом или длительность пауз и так уже была достаточно низкой? Автор не сказал.

Однако наступает момент, когда больше не имеет смысла наращивать возможности железа для сокращения пауз. Если паузы на сервере снизятся с 10 до 1 мс, заметят ли это пользователи? А если для такого снижения вам потребуется увеличить аппаратные ресурсы вдвое?

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

Сравнение с Java
Виртуальная машина Java HotSpot имеет несколько алгоритмов сборки мусора. Вы можете выбирать их через командную строку. Ни один из них не старается так сильно снизить продолжительность пауз, как Go, потому что они пытаются поддерживать баланс. Чтобы прочувствовать влияние компромиссов, можно сравнить алгоритмы друг с другом, переключаясь между разными сборщиками. Как? С помощью простого перезапуска программы, потому что компилирование выполняется по мере её исполнения, так что разные барьеры, необходимые для разных алгоритмов, могут по мере необходимости компилироваться и оптимизироваться в коде.

На современных компьютерах по умолчанию используется сборщик на основе поколений. Он создан для пакетных задач и изначально не обращает внимания на длительность паузы (её можно задавать в командной строке). Из-за возможности выбирать сборщик по умолчанию многие считают, что в Java паршивый сборщик мусора: из коробки Java пытается сделать так, чтобы ваше приложение работало как можно быстрее, с наименьшей избыточностью памяти, а на паузы наплевать.

Если вам нужно уменьшить продолжительность пауз, то можете переключиться на сборщик с параллельной пометкой и очисткой (concurrent mark/sweep collector, CMS). Это самое близкое к тому, что используется в Go. Но это алгоритм на основе поколений, поэтому паузы у него длиннее, чем в Go: молодое поколение уплотняется во время пауз, потому что выполняется перемещение объектов. В CMS есть два типа пауз: покороче, около 2—5 мс, и подлиннее, около 20 мс. CMS работает адаптивно: поскольку он выполняется одновременно (concurrent), то должен предполагать, когда ему запуститься (как и в Go). В то время как Go попросит вас сконфигурировать избыточность кучи, CMS самостоятельно адаптируется в ходе runtime, стараясь избежать сбоев режима одновременного выполнения. Поскольку большая часть кучи обрабатывается с помощью обычной пометки и очистки, то можно столкнуться с проблемами и тормозами из-за фрагментации кучи.

Самое свежее поколение сборщика в Java называется G1 (от garbage first). По умолчанию он работает начиная с Java 9. Авторы постарались сделать его как можно более универсальным. По большей части он выполняется одновременно, основан на поколениях (generational) и уплотняет всю кучу. Во многом самонастраиваемый. Но поскольку он не знает, чего вы хотите (как и все сборщики мусора), то позволяет регулировать компромиссы: просто укажите максимальный объём памяти, который вы ему выделяете, и размер пауз в миллисекундах, а всё остальное алгоритм подгонит самостоятельно, чтобы соблюсти ваши требования. По умолчанию длительность пауз около 100 мс, так что, если вы не уменьшите их самостоятельно, не ждите, что это сделает алгоритм: G1 отдаст предпочтение скорости работы приложения.

Паузы не совсем консистентны: большинство очень коротки (менее 1 мс), но есть и несколько длинных (более 50 мс), связанных с уплотнением кучи. G1 прекрасно масштабируется. Известны отзывы людей, которые применяли его на кучах терабайтного размера. Также у G1 есть ряд приятных возможностей вроде дедупликации строк в куче.

Наконец, был разработан ещё один новый алгоритм под названием Shenandoah. Он внесён в OpenJDK, но в Java 9 не появится, пока вы не станете использовать специальные билды Java из Red Hat (спонсора проекта). Алгоритм разработан с целью минимизации продолжительности пауз, невзирая на размер кучи, которая в то же время уплотняется. К недостаткам относятся большая избыточность кучи и ряд барьеров: для перемещения объектов во время выполнения приложения необходимо одновременно считывать указатель и взаимодействовать со сборщиком мусора. В этом смысле алгоритм аналогичен «безостановочному» сборщику из Azul.

Заключение
Цель этой статьи — не в том, чтобы убедить вас использовать другие языки или инструменты. Сборка мусора — это трудная, действительно трудная проблема, которая десятилетиями изучается армией учёных и программистов. Поэтому относитесь с подозрением к прорывным решениям, которые никто не заметил. Вероятнее всего, это просто странные или необычные замаскированные компромиссы, избегаемые другими по причинам, которые станут ясны позднее.

А если хотите минимизировать продолжительность пауз за счёт всех остальных параметров любой ценой, то обратитесь к сборщику мусора из Go.

Комментарии (0)