Алгоритмы GC: поколенческая гипотеза, concurrent marking и write barrier

JVM-сервис имеет кучу 8 ГБ. 95% объектов живут менее 200 мс. Классический stop-the-world коллектор должен сканировать все 8 ГБ при каждом цикле. Generational коллектор сканирует только 256 МБ молодого поколения — и возвращает 95% мусора за ту же цену.

Mark-and-sweep: фундамент

Любой tracing GC следует одной схеме. Кратко паузит приложение, собирает корни GC: активные регистры CPU, стек каждого потока, глобальные переменные, JNI-дескрипторы. От корней обходит граф ссылок — каждый достижимый объект «живой»; всё недостижимое — «мусор». Маркирует живые объекты (переключает бит в заголовке или в побочной таблице). После маркировки выполняет sweep: проходит кучу, возвращает память немаркированных объектов в free-list.

Варианты компактизируют (перемещают живые объекты, устраняя фрагментацию) и могут использовать bump-pointer allocation для быстрых последующих аллокаций.

Наивный алгоритм — stop-the-world mark-and-sweep: пауза на всё, маркировка, очистка, возобновление. Полное время паузы растёт с размером кучи. Для кучи 32 ГБ это могут быть секунды — неприемлемо для latency-sensitive сервиса. Каждый современный GC — вариант, сокращающий эту паузу.

Поколенческая гипотеза

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

Generational коллекторы делят кучу на молодое поколение (small, собирается часто) и старое поколение (большое, собирается редко). Аллокации идут в молодое; выжившие «продвигаются» в старое после нескольких циклов.

Математика: если 95% объектов умирают в молодом поколении, minor GC возвращает 95% аллоцированных байт, пройдя только по (меньшей) молодой куче. Исключение: concurrent GC Go непоколенческий — единая куча, tri-color маркировка. Аргумент команды Go: простота рантайма и равномерный профиль пауз важнее выигрыша в throughput от поколенческого подхода.

Concurrent marking и write barriers

Чтобы добиться пауз ниже 10 мс на кучах в несколько ГБ, маркировка должна происходить пока приложение работает. Это concurrent marking: GC работает как параллельный поток, обходя граф объектов вместе с mutator-потоками (потоками приложения).

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

Два подхода:

• Snapshot-at-the-beginning (SATB): барьер маркирует старую ссылку, которую вот-вот перезапишут, обеспечивая её выживание в текущем цикле. Используется в G1, Shenandoah, ZGC, Go.
• Incremental-update: барьер маркирует новую ссылку, записанную в поле черного объекта. Используется в CMS, классическом V8 mark-compact.

Стоимость: ~2–10% CPU на каждой записи ссылки — цена concurrent маркировки.

Обзор рантаймов

Go: concurrent tri-color непоколенческий mark-sweep без компактизации. Запускается по rate аллокаций; pacer удерживает STW-паузы ниже 1 мс. GOGC управляет целевым ростом кучи (по умолчанию 100% = удвоение); GOMEMLIMIT (добавлен в 1.19) — мягкий лимит памяти.

JVM: G1 — по умолчанию для большинства серверов, region-based, generational с concurrent marking, паузы 10–50 мс типично. ZGC (JEP 333 + 377) — субмиллисекундные паузы на кучах до 16 ТБ, colored pointers + load barriers. Shenandoah (Red Hat) — схожие цели с Brooks pointers.

V8: generational Scavenger для молодого (semi-space copying), Mark-Compact для старого. Проект Orinoco добавил concurrent marking + parallel compaction (с 2017 г.). Куча ограничена на изолят (~1,5 ГБ по умолчанию в Node, настраивается через --max-old-space-size).

.NET: workstation/server GC, generational (gen 0/1/2 + LOH), background concurrent marking; настраивается через GCSettings.LatencyMode.

CPython: reference counting (объект освобождается при refcount=0, без больших пауз) + cycle collector для ссылочных циклов через трассировку; GIL сериализует мутацию, но подсчёт ссылок стоит ~10–20% throughput.