Фантом: большая сборка мусора

Эта статья — продолжение, начало здесь ^[1]. Для тех, кто не кликнул на ссылку, краткая вводная:

Мы обсуждаем сборку мусора в операционной системе Фантом, то есть в среде виртуальной (байткод-) машины, работающей в персистентной оперативной памяти. Размер персистентной памяти — порядка размера диска, то есть единицы терабайт на сегодня и, потенциально, десятки и сотни терабайт завтра.

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

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

Принятая мной идея схемы сборки мусора в такой среде выглядит как совокупность двух сборщиков.

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

Второй — медленный, недетерминированный (трудно предсказать время работы), но точный и бескомпромиссный. В традиционной среде такой сборщик требовал бы остановки мира (stop the world), но есть трюк — если сборку вести на полной копии состояния системы, то весь собранный в копии мусор будет мусором также и в более поздней версии того же состояния, что бы с ней ни происходило. Прелесть подхода в том, что Фантом реализует персистентность именно через создание «снапшотов» — полных копий состояния объектной памяти виртуальной машины. То есть — среда, в которой можно спокойно и рассудительно собирать мусор уже есть.

По сути дела в этот момент задача кажется тривиальной — на «обездвиженном пациенте» собирать мусор можно самым простым и незатейливым способом. Да? Похоже, что нет.

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

Вопрос второй — рестартуемость алгоритма. Было бы заманчиво реализовать сборщик как штатную программу под Фантом, которая, следовательно, живёт в персистентной памяти и перезапуски ОС для неё незаметны, всё состояние программы сохраняется и сборка мусора просто продолжается дальше после рестарта системы. Но в силу первого требования такая реализация может быть опасна — при нехватке памяти её может «доесть» пользовательский процесс и работа сборщика мусора будет остановлена. Это бы решалось через квотирование выделения памяти, но в текущей версии ОС его нет, ну и в целом решение выглядит очень изящно, но с точки зрения отладки окажется, скорее всего, похожим на ад.

Следовательно, хорошо бы опереть сборщик мусора на некоторую простую структуру данных, которую легко хранить и обрабатывать в линейном виде. Например — односвязный список, организованный как task list, из которого алгоритм вынимает атомарные задачи и в который добавляет задачи в процессе решения «вынутой» задачи.

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

В целом напрашивается такая наивная реализация: список необойдённых объектов roots, список посещённых объектов visited, и алгоритм, который сводится к:

• Для пустого roots и visited положить в него объект по адесу ноль
• Для непустого — прочитать и удалить адрес объекта, если его нет в visited — добавить его в visited, добавить в roots всех его детей
• Для пустого roots и непустого visited — пройти линейно все объекты в адресном пространстве снапшота, если они не встречаются в visited — пометить их как мусор в актуальном адресном пространстве (этот процесс тоже можно сделать рестартуемым, если записывать время от времени адрес памяти, который мы прошли)

Естественно, это очень неэффективный алгоритм, но его можно оптимизировать довольно тривиальным путём. Например, так: roots делаем не очередью, а стеком и хвост этого стека храним в памяти, при этом большое количество обходов leaf objects будет происходить без модификации дисковой части этого стека. Важно лишь чтобы в дисковую копию объекты попадали только целиком и уходили из неё только после обхода всех детей.

Проблема в том, что каждый шаг этого алгоритма требует просмотра всего visited, что потенциально — крушение всех надежд, фиаско.

Беда ещё и в том, что visited нельзя кешировать в памяти — его обязательно надо просмотреть целиком. Напрашивается очевидная идея — сделать его не списком, а деревом, отсортированным по адресу объекта. Тогда поиск объекта в дереве сократится логарифмически, и, главное — фрагменты дерева можно кешировать, поскольку полный перебор не нужен.

Кстати, если у вас есть идеи по поводу такого алгоритма, напишите, пожалуйста.

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

Во-первых, хорошо бы иметь некоторый аналог lost+found для таких ситуаций. Хотя и совершенно неясно, как его реализовать. Во-вторых, в актуальной работающей системе соответствующая страница может быть вполне жива. Поэтому справедливо было бы сделать вот как: проверить, есть ли эта страница в более поздних шотах или в памяти. Если есть в памяти — форсировать её помещение в снапшот, даже если она не менялась (обычно Фантом неизменившиеся страницы, конечно, не пишет повторно), остановить сборку и рестартовать её на более позднем снапшоте. Если же не повезло и страницы нигде нет, включить режим восстановления и по окончании обычной сборки эвристически поискать в мусоре поддеревья объектов ощутимого размера, которые из мусора исключить и «подвесить» в специальное место в объектной иерархии.

Что ещё важно?

В целом подсистема виртуальной персистентной памяти Фантома и его же виртуальная байткод-машина (объектная среда) ни черта друг про друга не знают. Вторая живёт в первой. И всё.

Но один достаточно типовой случай, который нуждается в связке между ними. Этот случай выглядит просто: между двумя снапшотами программа в ОС Фантом выделяет, использует и освобождает пару гигабайт объектов. Например, обсчитывает графику и в процессе создаёт временные данные. К началу снапшота они не нужны и неактуальны. Но память, в которой они лежали, «потрогана», модифицировалась. С точки зрения снапшоттера это — повод записать такую память в снапшот. В реальности её содержимое уже никому не интересно и, более того, должно быть обнулено от греха. Было бы логично при освобождении большого участка памяти сообщить пейджинговой подсистеме, что этот участок не только не dirty, а и вообще не нужен и сохранять его не нужно. А при восстановлении со снапшота его нужно читать как страницу нулей.

Это опять кажется тривиальным, но — нет. В предыдущей статье ^[1] говорилось о проблеме удаления объектов по обнулению счётчика ссылок и о том, что делать это можно только после прохода всеми нитями границы инструкции виртуальной машины.

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

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

А после — поздно, потому что тогда «ненужные» страницы, всё же, попадут в снапшот.

В итоге это означает, что нужно выполнить не очень очевидную цепочку операций:

1. Приостановить все треды на границе инструкции и сразу «отпустить» их
2. Провести освобождение объектов с нулевым счётчиком ссылок, которые были заявлены на удаление до этой остановки (проверяя, что счётчик всё ещё нулевой)
3. Приостановить все треды на границе инструкции ещё раз
4. Выполнить синхронную часть снапшота (в памяти)
5. «Отпустить» остановленные треды
6. Спокойно доделывать асинхронную часть снапшота (ввод-вывод)

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

• Старого, на котором собираем мусор
• Более актуального, который полон и пригоден к рестарту
• Последнего, который находится в процессе формирования

А может быть и ещё нескольких, которые хранятся в режиме бекапа/time machine.

На сём позвольте поставить точку с запятой, и задать вопрос: какую статистику по состоянию объектной среды вы бы считали полезной собрать в процессе сборки мусора? Мы всё равно обходим объекты, можно провести тот или иной анализ относительно бесплатно.

Автор: dzavalishin

Источник ^[2]