Сборка мусора в персистентной модели: от терабайта и дальше
Привет всем. Продолжу о Фантоме. Для понимания полезно прочесть статью про персистентную оперативку, а так же общую статью про Фантом на Открытых Системах. Но можно и так.
Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (managed) пойнтерами, объектной байткод-машиной, не замечают рестарта ОС и, в целом, счастливы.
Очевидно, что такой среде нужна сборка мусора. Но — какая?
Есть несколько проблем, навязанных спецификой.
Во-первых, теоретически, объём виртуальной памяти в такой среде огромен — терабайты, всё содержимое диска. Ведь мы отображаем в память всё и всегда.
Во-вторых, нас категорически не устраивают stop the world алгоритмы. Если для обычного процесса остановка в полсекундны может быть приемлема, то для виртуальной памяти, которая, большей частью, на диске, это будут уже полчаса, а то как бы не полсуток!
Наконец, если считать, что полная сборка мусора составляет полсуток, нас, наверное, это не устроит — было бы здорово иметь какой-то быстрый процесс сбора мусора, хотя бы и не полностью честный, пусть он часть мусора теряет, но если удаётся быстро вернуть 90% — уже хорошо.
Тут нужна оговорка. Вообще говоря, в системе, которая располагает парой терабайт виртуальной памяти, это не так уж критично — даже если не делать освобождение памяти полсуток, возможно, не так много и набежит — ну, например, истратится 2–3, ну 5 гигабайт, ну даже и 50 гигабайт — не жалко, диск большой.
Но, скорее всего, это приведёт к большой фрагментации памяти — множество локальных переменных окажутся раскиданы по многим далеко расположенным страницам, при этом высока вероятность того, что небольшие вкрапления актуальной информации будут перемежены с тоннами неактуального мусора, что сильно повысит нагрузку на оперативную память.
Ок, итого у нас две задачи.
- Быстрый, недорогой, возможно — неполный (собирает не весь мусор), нон-стоп алгоритм для постоянного применения. Предполагается, что память, которой он будет «касаться» — реально в памяти, а не высвоплена на диск.
- Полный, возможно — долгий и дорогой, но тоже нон-стоп (!) алгоритм для всего адресного пространства. Предполагается, что доступ к «памяти» будет приводить его на диск с вероятностью в 99%.
Второе требование кажется нереальным, и таким, собственно, и является. Полная сборка памяти — это обход практически всех объектов (кое-что в некоторых алгоритмах можно оптимизировать), и если они на диске и диск терабайтный, то оценочное время — часы, хорошо если не сутки. Какой тут нон-стоп?
На помощь приходит интересная мысль, которая, как часто бывает, очевидна, как только её у кого-нибудь прочтёшь: объект, который был мусором вчера, будет мусором и завтра.
Это, на практике, означает, что если у нас есть вчерашняя фотография всей памяти системы, то сборку мусора можно сделать именно что по фотографии! При этом найденный в ней мусор можно освободить и в актуальной версии памяти тоже!
А ведь ОС с персистентной оперативной памятью именно что и занимается созданием полных «фотографий» состояния памяти.
(Надо сказать, что я очень люблю, когда возникают такие концептуальные совпадения — для меня они являются признаком того, что модель системы достаточно целостна и ортогональна.)
Таким образом, возникает удивительная ситуация — у нас есть «фотография» памяти системы, и по ней можно делать сборку мусора даже самыми банальными mark&sweep алгоритмами.
Напомню, как он устроен, вкратце: обходим по ссылкам все достижимые объекты и ставим им маркер: «не мусор». Потом обходим всё и то, что без маркера, то — мусор.
Однако, тут возникает целый сонм оптимизационных задач.
Начнём с очевидной: записывать на диск дорого и опасно, если случится сбой — мы потеряем снапшот системы, а это недопустимо.
Значит, нужна оптимизация. Напрашиваются два варианта.
Первый — в процессе сбора мусора делать отдельную копию снапшота. Жутко дорого — потребуется почти удвоить объем дисковой памяти. И перезаписать почти все страницы.
Второй — не трогать оргинал (что всегда хорошо), а маркеры складывать в отдельный параллельный (сортированный по адресам объектов?) буфер, вероятно, в виде хешмапа или сортированного дерева.
Навскидку выбор очевиден. Но, может быть, есть третий вариант?
Ещё один момент, который напрашивается — это маркировка поколений. Интуитивно кажется, что 90% данных не станут мусором условно никогда — код классов, объекты с музыкой и видео — всё это хранится веками и явно не требует ежедневной проверки.
Наверное, большую сборку можно делать иногда тоже частичной — например, раз в сутки обрабатывать только последнее поколение, раз в двое суток — два последних, а на выходные уж перетряхнуть всё. Генеральная уборка.
Однако, можно бы попросить у основного аллокатора и быстрого сборщика мусора хинтов. Например, если в процессе работы были модифицированы объекты из самого нижнего, условно «константного» поколения (где лежат классы и огромные константные объекты), то это могло бы быть триггером для полной сборки.
Собственно, на сегодня в ОС Фантом реализован только быстрый алгоритм — на базе счётчика ссылок. Полный сборщик ждёт своего героя.
С быстрым, кстати, всё тоже непросто. Там есть нерешаемая (не волнуйтесь, мы её почти решили:) проблема с races — синхронизация инкремента числа использований объекта.
Суть её проста. Мы с вами читаем из поля объекта А ссылку на объект Б. Поскольку мы теперь ей (ссылкой) владеем и хотим пользоваться, мы, конечно, увеличиваем на 1 счётчик ссылок внутри объекта Б.
object *b_ptr = a[xx];
b_ptr->ref_count++;
Но — вот беда — между этой парой строк случилось переключение контекста и другой тред в этот самый момент взял и стёр из объекта А эту самую ссылку на Б. И была она последняя. И счётчик ссылок ушёл в ноль, и стал объект удалённым. И тут-то мы начали ему счётчик ссылок увеличивать. А он уже убит, очищен, выделен кому-то ещё и содержит совсем другие данные.
Весело? И mutex на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.
Неприемлемо.
Решение выглядит так: фактически уничтожать объект только после того, как все нити всех виртуальных машин прошли границу инструкции виртуальной машины. Это гарантирует, что все декременты и инкременты закончились. Механизм для этого есть, он уже используется при снапшотах.
На этом на сегодня закончу, отметив, что я совершенно не коснулся задачи компактификации (она же дефрагментация) объектов. Тоже, вообще говоря, непочатый край. Отдельно есть задача написания аллокатора объектов с большой степенью локализации аллокации, причём с разбиением арен быстрых объектов по нитям. Здесь же — разнесение мьютексов аллокатора по аренам с тем, чтобы не возникало затора на входе в аллокатор.
Собственно, всё это — очень хороший пример задач, которые встают в проекте ОС Фантом — нет ничего нереального, но постоянно требуются хорошие инженерные решения для того, чтобы обойти на вид необходимые проблемы.
