Трёхцветная маркировка обычно объясняется так: белое — не найдено, серое — в очереди, чёрное — просканировано. Всё верно и ровно настолько же бесполезно, потому что главный вопрос остаётся за кадром: зачем вообще нужны три цвета, если для обхода графа достаточно двух — «посещён» и «не посещён»?

Так вот. Третий цвет существует ровно по одной причине: программа не останавливается на время сборки. И этот пост — про то, что из этого следует. В конце — интерактивная песочница, где барьер записи можно выключить и посмотреть, как GC съедает живой объект.

Зачем нужен третий цвет

Наивный сборщик делает mark & sweep за одну STW-паузу: остановили мир, обошли граф от корней, освободили всё, до чего не дошли. Корректно, просто — и пауза линейна по размеру живой кучи. На 10 ГБ живых данных это секунды, а не микросекунды.

Go пошёл другим путём ещё в 1.5: маркировка идёт конкурентно с программой (Go 1.5 GC: prioritizing low latency and simplicity). Мир останавливается дважды и ненадолго — на включение барьера со сканированием корней и на завершение маркировки. С Go 1.8 эти паузы «обычно меньше 100 микросекунд, а часто — порядка 10» (Go 1.8 release notes), и что важно — они больше не зависят от размера кучи.

Но конкурентность создаёт проблему, которой в STW-сборщике не существует. Пока коллектор обходит граф, мутатор (термин из Dijkstra et al., 1978 — программа, которая меняет граф объектов прямо во время обхода) переписывает указатели. И вот тут двух цветов уже не хватает.

Представьте: коллектор полностью просканировал объект B — прочитал все его поля, больше к нему не вернётся. В этот момент горутина выполняет B.next = W, где W — ещё не найденный белый объект, и одновременно обнуляет единственную другую ссылку на W. Формально W жив: он достижим от корней через B. Фактически коллектор его никогда не найдёт — в B он уже был.

Это классическая потеря объекта. Три цвета нужны, чтобы её поймать: «просканирован» (чёрный) и «найден, но не просканирован» (серый) — принципиально разные состояния, и правило корректности формулируется именно через них.

1 · маркер прошёл BBчёрныйXWбелый2 · мутатор: *B = W; X = nilBXWбелый за чёрным3 · sweepBWосвобождён · жив
Маркер не возвращается в чёрные объекты — значит, указатель, появившийся в чёрном объекте уже после сканирования, нужно ловить отдельно

Инвариант и барьер

Правило, которое держит всю конструкцию, формулируется в двух вариантах.

Сильный инвариант: чёрный объект никогда не содержит указатель на белый. Слабый инвариант: чёрный объект может указывать на белый, но только если этот белый достижим ещё и по цепочке от какого-нибудь серого. Слабый вариант допускает больше состояний и потому дешевле в поддержке — Go опирается именно на него.

Соблюдать инвариант нужно в момент, когда его можно нарушить, то есть при записи указателя в кучу. Отсюда барьер записи (write barrier) — небольшой фрагмент кода, который компилятор вставляет перед каждой такой записью. В наивном варианте (Dijkstra) он делает ровно одно: если записываемое значение белое — красит его в серое, то есть кладёт в очередь маркера. Белый объект, спрятанный за чёрным, немедленно перестаёт быть белым.

Реальный Go с версии 1.8 использует гибридный барьер — комбинацию delete-барьера Yuasa и insert-барьера Dijkstra (proposal 17503, Clements & Hudson). Псевдокод прямо из комментария в runtime/mbarrier.go:

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

Первая строка — это и есть отличие от учебного варианта: красится старое значение слота, а не только новое. Смысл в том, что коллектор получает snapshot графа на момент начала цикла: указатель, который мутатор разрывает, всё равно попадёт в очередь. Именно это позволило Go убрать финальное пересканирование стеков под STW — самую неприятную паузу в схеме до 1.8, которая линейно росла с числом горутин.

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

Дальше — два следствия, которые в учебниках обычно упоминают вскользь, а на практике они и делают схему рабочей.

Объекты, выделенные во время цикла, рождаются чёрными. Не серыми — чёрными. Логика простая: объект только что создан, внутри него ещё нечего сканировать, а если красить его в серый, маркер будет бесконечно догонять аллокации активной горутины. Цена — такие объекты гарантированно доживают до следующего цикла, даже если мусор. Это осознанный размен: floating garbage в обмен на завершаемость.

Mark assist. Горутина, которая аллоцирует, обязана сама поработать маркером пропорционально выделенному объёму. Без этого одна аллоцирующая горутина легко опережает фоновых маркеров, куча растёт быстрее, чем сканируется, и цикл не сходится. Ассист — это встроенный в аллокатор механизм обратного давления; детали пропорций живут в pacer, переписанном в Go 1.18.

Собственно, поэтому «GC съедает CPU» на практике часто выглядит как «аллоцирующие горутины тормозят»: время уходит не в фоновых воркерах, а в ассистах.

STWбарьер on,корниконкурентная маркировкасерое → чёрное · программа работает · барьер ловит записи · mark assistSTWфинишконкурентная очисткавсё, что осталось белым, — мусор

ширина блоков условна: STW-паузы — десятки микросекунд, маркировка — миллисекунды и больше

Один цикл GC в Go: мир останавливается дважды и ненадолго, вся тяжёлая работа идёт параллельно с программой

Ещё одно свойство, которое стоит проговорить: трёхцветная маркировка спокойно собирает циклы мусора. A → B → A, недостижимые от корней, останутся белыми и будут освобождены — никакого специального кода для этого не нужно. Это фундаментальное преимущество перед подсчётом ссылок, где циклическая связка живёт вечно.

Песочница

Дальше — интерактивная модель одного цикла маркировки. Слева root set: стеки горутин и глобалы. Справа куча: объекты со связями, которые можно перетаскивать, связывать и рвать.

Кликните по двум объектам, чтобы связать их; по стрелке — чтобы удалить указательОткрыть песочницу в отдельной вкладке ↗

Что стоит попробовать по порядку:

  1. «Шаг цикла» — и смотрите на панель «Серый набор». Это очередь маркера. Каждый шаг: достали объект из очереди, прочитали его указатели, белые цели → серые, сам объект → чёрный. Цикл заканчивается, когда очередь пуста.
  2. Включите мутатор. Теперь параллельно с маркировкой идут записи указателей и аллокации. Обратите внимание, что новые объекты появляются сразу чёрными — то самое allocate-black, — и в журнале видно, как срабатывает барьер.
  3. Выключите барьер записи и нажмите «Эксперимент: потеря объекта». Мутатор перевешивает белый объект за чёрный и обнуляет исходную ссылку. Маркер в чёрное не возвращается — на фазе очистки живой объект уходит в освобождённые. Ровно тот баг, который барьер предотвращает.
  4. Включите барьер обратно и повторите эксперимент. В момент записи белый станет серым — в журнале появится строка [барьер], объект доживёт до конца цикла.
  5. Досмотрите первый цикл до конца и найдите пару F ⇄ G — это мусорный цикл, который освобождается без всякого специального кода.

Одна честная оговорка по модели: барьер в песочнице — это классический insert-барьер Dijkstra, «чёрный получил указатель на белый → красим белый в серый». Настоящий Go, как я писал выше, использует гибридный барьер и красит ещё и старое значение слота. Для того чтобы увидеть, зачем барьер вообще нужен, insert-варианта достаточно; для чтения mbarrier.go — уже нет.

Что изменилось с Green Tea

Всё вышесказанное — про инвариант и барьер — по-прежнему верно, но сам обход кучи в свежих версиях Go устроен иначе. В Go 1.25 появился экспериментальный сборщик Green Tea (issue #73581), а в Go 1.26 он включён по умолчанию; старая схема осталась за флагом GOEXPERIMENT=nogreenteagc, и её планируют убрать в 1.27.

Идея в том, что классический маркер ходит по отдельным указателям, разбросанным по памяти, и на небольших объектах это убивает локальность кэша: каждый шаг очереди — почти гарантированный промах. Green Tea работает не с отдельными объектами, а со страницами: серым становится не объект, а спан, и маркер обрабатывает его целиком, последовательно по памяти. Заявленный выигрыш — сокращение накладных расходов GC на 10–40% на реальных программах, плюс ещё около 10% на свежих amd64 (Ice Lake / Zen 4 и новее) за счёт векторных инструкций по битмапам страницы.

Что важно для этой статьи: поменялась единица работы маркера, а не протокол. Три цвета, инвариант и барьер записи никуда не делись — это по-прежнему трёхцветная конкурентная маркировка, просто очередь теперь хранит страницы, а не объекты.

Ссылки