Garbage Collector in Go

Предисловие. Ребята в Go обновили GC и назвали ее "Green Tea". В связи с этим решил написать пост, где буду рассказывать в целом о том, как работает GC в Go. Начну с механики "Tri-color mark & sweep".

Что такое GC?

Garbage Collector (GC) или сборщик мусора - это автоматический менеджер памяти, встроенный в среду выполнения (runtime). Его основная задача - освободить разработчика от ручного управления памятью.

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

А как GC понимает, что нужно удалять, а что оставлять? Именно на этот вопрос я отвечу ниже.

Tri-color mark & sweep

Tri-color mark & sweep - это метод реализации алгоритма сборки мусора, при котором все объекты в памяти условно делятся на 3 цвета (состояния) для безопасного и эффективного определения мусора параллельно с работой основной программы.

Для выделения объектов используется 3 цвета:

1. Белый (White) - это кандидат на удаление. Также это исходный цвет для всех объектов по умолчанию.

2. Серый (Grey) - выделяется "обнаруженный, но не исследованный" объект. С этим объектом GC будет продолжать работать.

3. Черный (Black) - полностью проверенный объект (как и все его дочерние ветки/объекты).

Попробую визуально отразить работу GC.

Представим, что есть некий "Дочерний элемент", с которым связаны различные объекты: A, B, C, D, E, F, G

+-+------------------+
|д|-->[A]->[B]       |
|о|    \             |
|ч|     [C]          |
|э|            [E]   |
|л|--> [D]  [F]->[G] |
+-+------------------+

Как видим, объект А связан с дочерним элементом (я выделил его как "дочэл"), но у нас также есть дочерние объекты B и C, которые связаны с А. Аналогично и с D. Но также есть и элементы F, G и E, которые блуждают в памяти (т.е. не связаны с дочерним элементом).

Как я уже говорил выше, все объекты помечены как белые (по умолчанию). GC обходит все ветки начиная с дочернего элемента. Дойдя до A он помечает его серым цветом. Затем GC обходит его ветки (это В и С). Увидев их, он тоже помечает их серыми, а их родительские объекты (т.е. в нашем случае это A) помечает как черные. И так до конца всех связей и дойдя до последних элементов, GC также помечает их как черные. Т.к. в нашем случае после B и С больше нет веток, GC их тоже пометит как черные. Аналогично и для объекта D, но т.к. он связан с дочерним элементом и у него нет других веток, GC сразу пометит его как "черный".

+-------+------+----------+
| White | Grey |  Black   |
+-------+------+----------+
|E, F, G|      |A, B, C, D|
+-------+------+----------+

В итоге у нас останутся только черные и белые. GC будет оставлять черные, а белые удалит.

Как GC начинает свою работу?

GC выполняется в 4 этапа:

1. Stop the World
   ⤷ Safe-point goroutine.

2. Включение write-барьера
   ⤷ Start the world
   ⤷ Mark.

3. Stop the world
   ⤷ Очистка кэшей.

4. Выключение write-барьера
   ⤷ Start the world
   ⤷ Очистка

Подробное разъяснение:

1. На 1-ом этапе GC полностью замораживает наше приложение. Горутинам задаются некие "точки сохранения", после чего они замораживаются.

2. Далее идет процесс включения Write Barrier, чтобы наше приложение не могло "что-то записывать". После этого приложение размораживается и работает в режиме "на чтение" (readonly), т.к. чтение работе GC не мешает. Далее запускается mark-алгоритм, который обходит все ветки дерева (объекты) и помечает их цветами.

3. Приложение снова замораживается и очищаются кэши.

4. После этого выключается Write Barrier, чтобы наше приложение снова могло записывать данные и уже окончательно запускается само приложение. Далее проводится очистка неиспользуемых объектов.