Исследователи из Oracle и Уппсальского университета представила новый алгоритм сборки мусора — Mark–Scavenge. Он решает проблему избыточной работы, которая возникает при использовании доступности объекта как прокси для оценки его "живучести".

Команда Spring АйО перевела статью, в которой можно подробнее ознакомиться с подробностями работы нового алгоритма.

В этой статье представлен новый алгоритм сборки мусора под названием Mark-Scavenge, который демонстрирует, как использование доступности объекта в качестве прокси для определения его "живучести" в перемещающих сборщиках мусора приводит к избыточному перемещению данных, и как это можно исправить. Работа основана на последней статье, созданной в рамках научного сотрудничества между Oracle и Уппсальским университетом. Полный текст статьи доступен на сайте ACM.

Современные алгоритмы сборки мусора предполагают справедливость слабой гипотезы о поколениях, согласно которой большинство объектов "умирают молодыми" [4]. Для этого куча делится на так называемые young gen (молодое поколение) и old gen (старое поколение). Если слабая гипотеза о поколениях справедлива, то большинство объектов в молодой области могут потенциально стать мусором в любой момент времени. Таким образом, внутри молодого поколения алгоритм сборки мусора, который работает с "живыми" объектами, будет более эффективным, чем тот, который работает с мусором, так как количество "живых" объектов существенно меньше. Рассмотрим пример ниже, в котором сборщик мусора должен освободить память.

Рисунок 1: Освобождение памяти с помощью сборки мусора

Так как в регионах A и C находится по четыре "живых" объекта, а в регионе B — всего два, выбор менее населённого региона B для эвакуации оказывается наиболее эффективным. Память можно освободить только при полном освобождении региона. В этом примере объекты e и f перемещаются в регион D, а после обновления входящих указателей весь регион B становится свободным. Всё выглядит логично, но что на самом деле означает "живучесть" объекта для сборщика мусора? Согласно The Garbage Collection Handbook [1]:

Объект считается "живым", если он будет доступен в будущем при выполнении приложения.

К сожалению, информация о "настоящей живучести" объекта доступна лишь тем, кто способен предсказывать будущее. Чтобы не допустить heap corruption,, сборщик мусора не должен ошибочно помечать объект как "мертвый", если это не так. Вместо идеальных предсказаний сборщики мусора обычно используют доступность по указателям (pointer reachability) как прокси "живучести" [1]. Однако использование доступности может привести к выполнению избыточной работы: перемещению объектов, которые хоть и доступны, больше никогда не будут использоваться системой.

В OpenJDK, который мы изучали, все сборщики мусора используют доступность для оценки "живучести". Например, Serial и G1 делают это в процессе "очистки" (scavenging). Очистка предполагает обход кучи от корневых объектов с последующим перемещением доступных объектов. ZGC разделяет эти действия на фазы "маркировки" (Mark) и "эвакуации" (Evacuate): объекты помечаются как "живые" при обнаружении, а затем копируются, если они остаются "живыми" после маркировки.

Мы решили исследовать, насколько использование доступности в качестве критерия "живучести" приводит к копированию объектов, которые фактически являются мусором. Насколько нам известно, это первое опубликованное исследование такого рода. Наша первоначальная гипотеза заключалась в том, что сборщики, использующие отдельные фазы маркировки и эвакуации, работают хуже, так как информация о "живучести" объектов используется значительно позже их маркировки. Эта задержка, отсутствующая при очистке, может приводить к устареванию информации о "живучести". С другой стороны, рассчитанная карта "живых" объектов после маркировки позволяет эвакуировать только регионы с малым количеством живых объектов, что делает эвакуацию более избирательной: сосредотачиваясь на страницах, которые дают наибольшую отдачу (например, перемещение нескольких объектов для полного освобождения страницы). В конечном итоге, чтобы понять объём избыточной работы, нам пришлось проводить эксперименты.

Рисунок 2: Фазы Mark-Evacuate и Scavenge

Мы начали измерять избыточную работу в ZGC, так как он обладал наиболее подходящей инфраструктурой: барьерами загрузки (load-barriers). Без барьеров загрузки мы не смогли бы легко отследить доступ к объектам, то есть понять, использовались ли объекты программой в итоге. Мы модифицировали ZGC для идентификации молодых объектов, которые были доступны на этапе маркировки, но впоследствии так и не использовались до того, как стали недоступными в следующем цикле GC. Это позволяет выявить перемещение объектов сборщиком мусора, которое является избыточной работой. Мы измерили, сколько из этих объектов было перемещено сборщиком мусора. Мы называем это избыточной работой: перемещение фактически "мертвых" объектов.

Мы запустили набор тестов DaCapo [2] и SPECjbb2015 [3] с использованием модифицированного ZGC и собрали информацию о реальной "живучести" (использовании) эвакуированных объектов. Каждая колонка в четвёртой группе — ZGC (barrier) — на графике ниже представляет отдельный тест и показывает процент ненужных объектов, которые были эвакуированы, так как больше не использовались и стали недоступными к следующему циклу GC. Данные демонстрируют высокий уровень избыточной эвакуации объектов из-за переоценки "живучести" на основе доступности по указателям и задержки между фазами маркировки и эвакуации.

Мы повторили эксперименты с G1 и Serial GC, используя менее точные измерения из-за отсутствия барьеров загрузки в этих сборщиках мусора. Результаты оказались схожими и не сильно отличались от точных измерений на основе барьеров загрузки (ZGC barrier). Хотя при "очистке" (scavenging) объекты эвакуируются сразу после обнаружения, все доступные объекты эвакуируются, что приводит к значительной избыточной работе. Наши данные показывают, что, несмотря на меньший промежуток времени между маркировкой и копированием при "очистке" по сравнению с Mark–Evacuate, это не обязательно снижает объём избыточной работы. Мы пришли к выводу, что использование доступности как приближения "живучести" в контексте перемещающего сборщика мусора приводит к значительным избыточным затратам.

Чем более конкурентный сборщик мусора, тем больше у него свободы в планировании своей работы. Однако конкурентный GC должен прогнозировать и учитывать скорость выделения памяти программой, так как он не останавливает выполнение программы во время сборки мусора. Чтобы компенсировать ошибки в прогнозировании, необходим "резерв" — буфер или доступная память, которая может быть использована при резких скачках выделения памяти, пока GC освобождает ресурсы. Этот резерв обычно не используется, но является необходимой мерой безопасности.

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

Mark–Scavenge выполняет обнаружение доступности объектов аналогично Mark-Evacuate и выбирает для эвакуации только слабо населённые регионы. В отличие от Mark-Evacuate, эвакуация не происходит сразу после маркировки. Это означает, что новая доступная память после маркировки появляется только из полностью освобождённых регионов. Наша идея заключается в том, что резерв памяти может быть использован для новых выделений после маркировки. Дополнительный резерв можно создать по запросу из слабо населённых регионов с использованием стандартной эвакуации, так как у нас есть информация о "живучести" для этих регионов. Если этого не происходит, объекты в таких регионах получают дополнительный цикл GC, чтобы стать недоступными, и тогда GC не придётся их эвакуировать, так как они уже "мертвые". Если объект остаётся доступным в следующем цикле GC, он эвакуируется и перемещается в режиме "очистки". Таким образом, Mark–Scavenge объединяет преимущества Scavenging и Mark–Evacuate: возможность избирательной эвакуации и отсутствие задержки между обнаружением и эвакуацией после — и это уникально для Mark–Scavenge — паузы.

Рисунок 4: Mark-Scavenge — откладывание эвакуации для сокращения избыточной работы

Мы реализовали Mark-Scavenge, заменив Mark-Evacuate для сбора молодых объектов в поколенческом ZGC. График ниже демонстрирует, как Mark-Scavenge позволяет существенно сократить объём избыточной работы.

Наиболее впечатляющий результат — сокращение перемещения "мертвых" объектов до 91%. Если сборщик мусора запускается с достаточным объёмом памяти, чтобы избежать задержек при выделении памяти, стоимость избыточной работы в основном скрыта. Однако на сильно нагруженной машине (например, при временных скачках скорости выделения памяти) преимущества в производительности становятся значительными: 2–4%. Наилучшие результаты были получены в SPECjbb2015, где показатели critical-jOPS (задержка) улучшились на 2–4%, а max-jOPS (пропускная способность) — на 2–8%. В стрессовой конфигурации задержка для Cassandra сократилась на 20% в 99-м, 99.9-м и 99.99-м перцентилях.

Наши результаты показывают, что приравнивание "живучести" объекта к его доступности приводит к значительному копированию мусорных данных в перемещающих сборщиках. На сильно нагруженных машинах это отрицательно сказывается на производительности, как демонстрирует наша реализация Mark-Scavenge в ZGC. Выводы этой работы позволят инженерам и исследователям сборки мусора продолжать совершенствовать современные подходы.

Ссылки:
[1] Jones et al., The Garbage Collection Handbook (2023)

[2] https://github.com/dacapobench/dacapobench/releases/tag/v23.11-chopin

[3] https://www.spec.org/jbb2015/

[4] Ungar, David. “Generation scavenging: A non-disruptive high performance storage reclamation algorithm”

Присоединяйтесь к русскоязычному сообществу разработчиков на Spring Boot в телеграм — Spring АйО, чтобы быть в курсе последних новостей из мира разработки на Spring Boot и всего, что с ним связано.

Ждем всех, присоединяйтесь

Mark–Scavenge: ждем, пока мусор выбросит себя сам