Збірка сміття в персистентной моделі: від терабайта і далі

Привіт всім. Продовжу про Фантоми. Для розуміння корисно прочитати статтю про персистентную оперативку, а також загальну статтю про Фантом на Відкритих Системах. Але можна і так.

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

Неприйнятно.

Рішення виглядає так: фактично знищувати об'єкт тільки після того, як всі нитки всіх віртуальних машин пройшли кордон інструкції віртуальної машини. Це гарантує, що всі декременты і инкременты закінчилися. Механізм для цього є, він вже використовується при снапшотах.

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

Власне, все це — дуже хороший приклад завдань, які постають у проекті ОС Фантом — немає нічого нереального, але постійно потрібні хороші інженерні рішення для того, щоб обійти на вигляд необхідні проблеми.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.