8 апреля 2016 в 14:49

Сборка мусора в персистентной модели: от терабайта и дальше

Привет всем. Продолжу о Фантоме. Для понимания полезно прочесть статью про персистентную оперативку, а так же общую статью про Фантом на Открытых Системах. Но можно и так.

Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (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 на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.

Неприемлемо.

Решение выглядит так: фактически уничтожать объект только после того, как все нити всех виртуальных машин прошли границу инструкции виртуальной машины. Это гарантирует, что все декременты и инкременты закончились. Механизм для этого есть, он уже используется при снапшотах.

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

Собственно, всё это — очень хороший пример задач, которые встают в проекте ОС Фантом — нет ничего нереального, но постоянно требуются хорошие инженерные решения для того, чтобы обойти на вид необходимые проблемы.
Дмитрий Завалишин @dzavalishin
карма
78,0
рейтинг 64,7
Архитектор
Самое читаемое Разработка

Комментарии (26)

  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    И mutex на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.

    Почему бы не сделать счетчик атомарным?
    • +2

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

  • +2
    Мне понравилась идея персистентной ОС, но я очень много не понимаю, а очень хочется. Может вам нужно сделать что-то вроде карты модулей и объектов в виде UML схемы. Это повысит порог вхождения в вашу ОС и привлечение новых людей. Ведь не обязательно понимать полностью как устроена и работает вся ОС, может кого-то заинтересует отдельная подсистема и человек будет работать над ней.
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Было бы здорово, но сделать это небанально.
        Если есть знаток того, как работают mem mapped files при fork, приглашаю в соучастники такой разработки. Это, видимо, единственный путь.
        • 0
          как работают mem mapped files при fork

          Мэппинг просто шарится между процессами.
  • +1
    Очевидно, что такой среде нужна сборка мусора.
    Не всем очевидно. Машина Тьюринга работает на бесконечной ленте и ни мусора ни его уборки не предполагает. Персистентная модель также крайне привлекает возможностью бескрайнего undo во всех его смыслах, что тоже не рифмуется с идеей мусора.
    • 0
      Всё верно.
      Дайте мне бесконечный диск и бесконечное адресное пространство. :)

      Насчёт undo — сборка мусора не противоречит. Снапшоты можно хранить и откатываться к ним.
  • –1
    object *b_ptr = a[xx];
    b_ptr->ref_count++; — В этом случае то что передался указатель на объект, у которого счётчик ссылок уже нул уже является ошибкой.
    • 0

      Где вы в статьё нашли «передачу указатель на объект с нулевым счётчиком ссылок»? Там прямо написано: сначала передали нормальный объект, а не мусор с нулевым счётчиком. Потом в другом потоке счётчик был обнулён.


      К примеру, у вас есть асинхронный словарь с кэшем. В одном из использующих кэш потоков из словаря уже взяли объект, но ещё не увеличили счётчик. А в другом произошло событие, из‐за которого кэш нужно очистить. Система решила переключится на другой до ref_count++ и выполняла его вплоть до ref_count--. Получился объект, на который ссылаются, но с нулевым счётчиком. При этом, когда его получали, всё было нормально.

  • 0
    У Вас со счетчиком ссылок проблема потому что Вы нарушаете идиому владения. Создавать копии ссылок на объект может только тот кто этим объектом владеет. В многопоточной системе каждый тред должен получать владение независимо, если треду А нужен объект которым владеет тред Б, то его обязательно необходимо запрашивать у треда Б через один из механизмов синхронизации.

    Если сам счетчик ссылок на объект по какой-то причине не умирает вместе с объектом а остается нулем, то можно еще атомарный CAS использовать.
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        В варианте когда указатель может протухнуть в любой момент такой код работать не будет. Он базируется на том что объект просто не умирает в течении некоего времени когда с ним возможна работа. Тот кто объект в конце подчищает уже после смерти потоков — тот и «владелец» объекта. Синхронизация обычно в таком коде сводится к тому что этот владелец ждет пока помрут потоки которые могут с объектом работать.

        А вообще mutex можно рассматривать как частный вариант идиомы владения. Взятие мьютекса соответствует взятию на себя «владения» ресурсом.
        • НЛО прилетело и опубликовало эту надпись здесь
  • +1

    Реф-каунтинг вообще штука капризная.
    Взять для примера те же цикличные или кольцевые ссылки (буде таковые разрешены) — как только граф где-то замкнулся в кольцо, мы имеем для всех объектов в том кольце (и соответственно других "деток" всех этих объектов рекурсивно) значение ref_count отличное от 0, и что особенно весело — навсегда (если не принимать меры). Самая красота начинается если где-то пересекаются два и более таких графа.
    Т.е. иногда просто невозможно установить — это leak как он есть или просто "долгоиграющая" кольцевая последовательность.


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


    И это только один пример, что называется навскидку, а тех граблей в теме реф-каунтинга и без атомарности хоть отбавляй...

    • НЛО прилетело и опубликовало эту надпись здесь
      • 0

        Вот враз видно человека не совсем в теме:


        • дано тупо два "объекта": наш A и какой-то B данный нам снаружи, надо добавить B в "дочки" нашему A, соответственно проинкементив его B->ref_count;
        • как не зная B (или всех "дочерних" связей B) исключить ситуацию (которая якобы "на нашей совести"), что у B уже есть какой-то "дочерний" X, для которого уже существует reference к A?
          Т.е. не зная полностью B (что часто именно так) случайно не замкнуть кольцо?

        Я уж не говорю про то, что даже полностью зная B со всеми "детками" его, это часто в принципе не реально, ибо:


        • на этом этапе запрещена "итерация" по B;
        • на этом этапе запрещена "итерация" по какому-либо "потомку" от B, т.к. может привести к неожиданному результату, находится в состоянии одномоментного изменения (например ротация дерева хэш-таблицы) или находится в состоянии деструкции и т.д. и т.п.;
        • итерация по детям предполагает смену или блокировку нитей (тупо запирание контекста, т.е. возможен deadlock, нежелательное распараллеливание потоков, и т.п. радости);
        • сводит на нет всю прелесть реф-каунтинга, ибо такая проверка — тупо очень долгая операция (т.е. по длительности и сложности не сопоставима с предполагаемой "атомарность" реф-каунтинга);

        Исключение конечно составляют частные случаи, когда A->ref_count == 0 (т.е. объект A реально нигде еще не референсирован, соответственно кольцо исключено), но такое на практике на самом деле очень и очень редко (т.е. грубо говоря "конструктор" и иже с ним)… Ну или B "примитивен" сам по себе, т.е. в принципе не может "владеть" другими объектами (не имеет "детей"), что хотя и не редкость, но лишь чуть-чуть улучшает ситуацию описанную выше.


        Если бы все просто было бы с реф-каунтингом в чистом его виде, люди не напридумывали бы нестрогие или невладеющие (weak) references, умный указатели (типа smart, shared или intrusive pointers), тот же GC и так далее и тому подобное.

        • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          В принципе, weak пойнтеры и в обычных GC средах бывают нужны.
    • 0
      Поэтому рефкаунт — не единственный механизм, а только быстрый и «грязный».
      • 0

        Ну про "быстрый" я согласен сразу… А вот про "грязный"… Как бы выразиться, каждому дереву — свой садовник (или тут поговорка про фломастеры)… Я к тому, что если оно оправдано, то и хорошо...

        • 0
          Ну, рефкаунт per se никак не умеет собирать циклы, как его ни поливай и не удобряй.
          Правда, вроде бы, есть наработки на тему loop break, но это уже не чистый рефкаунт.
          • 0

            В качестве примера приведу рефкаунтинг в тикле (tcl) — он там по случаю самодостаточен (в том смысле, что GC в чистом тикле в его прямом виде нет, от слова вовсе).


            Так вот техника проста до безобразия:


            • если кольцо исключено (у "связуемого" нет родителей или он "простейший", т.е. нет деток, или исключено согласно "бизнес"-логики) — имеем прямой рефкаунтинг.
            • иначе, либо простейший слабый указатель (если допустимо) ибо тикль имеет собственный mem-manager (не путать с GC).
            • либо банально вяжем дубликат от "связуемого" (т.к. тогда еще нет родителей, ибо refCount у свежесозданного дубликата соответственно равен 0 и действие однозначно не может замкнуть кольцо), и это часто возможно т.к. почти-что все объекты умеют или разрешают refCount-safe duplicate и опять же тикль имеет свой mem-manager (т.е. "duplicate" действие быстрое).
            • если все же оба варианта искючены — бросает ошибку can't duplicate, no reference posible "не можу, от слова совсем"

            И таких или подобных примеров — валом. Поэтому, имхо, имеет право на жизнь…


            Вообще имхо самый идеальный "GC" (в глобальном смысле), это тот который комбинирует все подходы и как можно меньше работает "в чистую" как GC (в прямом его смысле), т.е. как можно меньше объектов доходят до уровня и ложатся в garbage collection (т.е. собственно "отфильтровываются" другими "техниками").

  • 0
    А можно ли делать GC во время снапшотах или это так уже и есть?
    фактически уничтожать объект только после того, как все нити всех виртуальных машин прошли границу инструкции виртуальной машины. Это гарантирует, что все декременты и инкременты закончились. Механизм для этого есть, он уже используется при снапшотах.

    Это позволит очищать память как побочный эффект иного механизма сканирования памяти. Т.е. нужно будет разрулить только циклические ссылки.
    • 0
      В снапшоте нет сканирования памяти. (Все изменения фиксируются подсистемой виртуальной памяти процессора). Но делать уничтожение объектов, у которых refcount == 0 — можно, потому что в снапшоте все виртуальные машины точно на границе инструкции.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.