Сучасний підхід до складання сміття



Останнім часом мені зустрічалося чимало статей, в яких не найвдалішим для мене чином просувається свіжий збирач сміття в Go. Деякі з статей написали розробники самої мови, і їх затвердження натякали на радикальний прорив у технології збирання сміття.

Ось первинний анонс про впровадження нового складальника, датований серпнем 2015-го:

Go створюється збирач сміття (GC) не тільки для 2015 року, але і для 2025-го, і ще далі… Складальник в Go 1.5 сповіщає про настання майбутнього, в якому паузи на збірку більше не є бар'єром для переходу на безпечний мову. Це майбутнє, в якому додатки без праці масштабуються разом з обладнанням, і в міру зростання потужності обладнання збирач сміття більше не є стримуючим фактором при створенні більш якісного, масштабованого. Go — хороший мова для використання як мінімум в найближчий десяток років.
Творці стверджують, що вони не просто вирішили проблему пауз на прибирання сміття, а пішли далі:

Одним з високорівневих способів вирішення проблем із продуктивністю є додавання GC-налаштувань (knobs), по одній на кожну проблему. Програміст може змінювати їх, підбираючи найкращу комбінацію для свого додатка. Недоліком цього підходу є те, що при впровадженні щороку однієї-двох нових налаштувань через десять років доведеться законодавчо регулювати працю людей, які будуть змінювати ці налаштування. Go не пішов по цьому шляху. Замість купи налаштувань ми залишили одну і назвали її GOGC.

Більш того, звільнившись від тягаря підтримки десятків налаштувань, розробники можуть зосередитися на поліпшенні runtime'а додатка.
Не сумніваюся, що багато користувачів Go були просто щасливі отримати новий підхід до runtime'в Go. Але у мене є претензії до цих заяв: вони виглядають як недостовірний маркетинговий булшит. А оскільки вони щоразу відтворюються в Мережі, прийшов час докладно з ними розібратися.

Реальність така, що в збирача сміття в Go не реалізовано жодних нових ідей або результатів досліджень. Як зізнаються автори, це просто складальник з паралельною поміткою та очищенням, заснований на ідеях 1970-х. Це примітно лише тому, що збирач був розроблений для оптимізації тривалості пауз за рахунок всіх інших важливих характеристик збирача. технічних і маркетингових матеріалах Go не згадується про всі ці побічні ефекти, тому багато програмісти не підозрюють про їх існування. У результаті створюється враження, що конкурентні мови — погано спроектований шлак. І автори Go лише підігрівають ці думки:

Для створення складальника на наступне десятиліття ми звернулися до алгоритмів з минулих десятиліть. У нашому збирача реалізований триколірний (tri-color) алгоритм паралельної позначки і очищення, запропонований Dijkstra в 1978 році. Це навмисне відміну від більшості сучасних збирачів «корпоративного» класу, яке, як ми вважаємо, найкраще відповідає особливостям сучасного обладнання і вимогам за рівнем затримки в сучасному.
Читаєш все це, і виникає думка, що за останні 40 років у сфері «корпоративних» збирачів сміття нічого краще запропоновано не було.

Введення в теорію сміття
При розробці алгоритму складання сміття потрібно враховувати ряд факторів:

  • Пропускна здатність програми: наскільки алгоритм сповільнить швидкість роботи програми? Іноді це виражається у відсотках: відношення часу процесора, витраченого на збірку, до часу, витраченого на корисну роботу.
  • Пропускна здатність складальника: скільки сміття може вичистити складальник за певний час роботи процесора?
  • Надмірність купи: скільки пам'яті понад теоретичного мінімуму потрібно збирача? Якщо під час складання він розміщує в пам'яті тимчасові структури, не призведе це до різкого зростання споживання пам'яті програмою?
  • Тривалість пауз: на який термін складальник зупиняє роботу програми?
  • Частота пауз: як часто складальник зупиняє роботу програми?
  • Розподіл пауз: більшість пауз дуже короткі і лише декілька дуже довгі? Або ви віддаєте перевагу робити тривалість пауз більш рівномірною?
  • Продуктивність розміщення в пам'яті: розміщення в новій пам'яті виконується швидко, повільно або непередбачувано?
  • Ущільнення: видає складальник повідомлення про відсутність пам'яті (out-of-memory, OOM), навіть якщо місця для задоволення його запиту достатньо, але воно розсіяно по купі у вигляді маленьких чанків? Якщо не видає, то програма може почати сповільнюватися і врешті-решт просто встати, навіть якщо пам'яті для продовження роботи досить.
  • Багатопоточність: наскільки ефективно складальник використовує багатоядерні машини?
  • Масштабування: наскільки ефективно складальник працює по мірі збільшення розміру куп?
  • Параметри: наскільки складно налаштувати складальник прямо з коробки, а також для досягнення оптимальної продуктивності?
  • Тривалість прогріву: є алгоритм самоналаштуванням на основі вимірювань власної поведінки? Якщо так, то як довго він виходить на оптимальний режим роботи?
  • Звільнення сторінки: алгоритм повертає операційній системі невикористану пам'ять? Якщо так, то коли?
  • Портируемость: працює сборщик на процесорних архітектур, що надають більш слабкі гарантії консистентности пам'яті в порівнянні з x86?
  • Сумісність: з якими мовами і компіляторами працює складальник? Можна запустити його з мовою, який створювався без обліку використання збирачів, наприклад С++? Потрібно модифікувати компілятор? Якщо так, потрібно перекомпілювати всю програму і залежно при зміні алгоритму скадальника?
Як бачите, при розробці складальника потрібно враховувати багато різних факторів, і деякі з них впливають на архітектуру більш широкої екосистеми, пов'язаної з вашої платформою. Причому я не впевнений, що перерахував всі фактори.

Із-за складності простору проектних параметрів збірка сміття являє собою подобласть інформатики, багато освітлену в дослідницьких роботах. Нові алгоритми пропонуються і впроваджуються регулярно, як в академічній, так і в комерційному середовищі. Але, на жаль, ніхто ще не створив алгоритму, придатного для всіх випадків життя.

Кругом суцільні компроміси
Розберемося з цим докладніше.

Перші алгоритми складання сміття розробили для однопроцесорних комп'ютерів і програм з маленькими купами. Ресурси процесора і пам'яті були дороги, а користувачі — невибагливі, так що до пауз в роботі програм ставилися лояльно. Створювалися в ті часи алгоритми намагалися поменше задіяти процесор і мінімізувати надмірне споживання пам'яті в купі. Це означало, що складальник нічого не робив до тих пір, поки програма могла розміщувати в пам'яті дані. Потім вона вставала на паузу до повного виконання помітки і очищення купи, щоб якомога швидше звільнити частину пам'яті.

У старих збирачів є переваги: вони прості; не уповільнюють програму, якщо не виконують свою роботу; не призводять до надмірного споживання пам'яті. Консервативні збирачі, наприклад Boehm GC, навіть не вимагають вносити зміни в компілятор або мова програмування! Це робить їх придатними для настільних додатків (зазвичай їх купи маленького розміру), в тому числі для відеоігор категорії ААА; у них більша частина пам'яті зайнята файлами з даними, які не потрібно сканувати.

Алгоритми, для яких характерні паузи повної зупинки (Stop-the-world, STW) для виконання помітки і очищення, найчастіше вивчають на курсах з інформатики. Іноді на співбесідах я прошу кандидатів трохи розповісти про складання сміття. І найчастіше вони являють складальник як чорну коробку, всередині якої невідомо що відбувається, або вважають, що в ньому використовується дуже стара технологія.

Проблема в тому, що такі прості паузи на позначку і очищення вкрай погано масштабуються. Якщо додати ядра і збільшити співвідношення обсягів куп та розміщень в пам'яті, то алгоритм перестає добре працювати. Але іноді, коли застосовуються маленькі купи, навіть прості алгоритми цілком стерпно виконують своє завдання! У подібних ситуаціях ви можете скористатися подібним збирачем і мінімізувати надлишковість споживання пам'яті.

Інша крайність — використання куп розміром у сотні гігабайтів на машинах з десятками ядер. Наприклад, на серверах, які обслуговують біржові транзакції або пошукові запити. У подібних ситуаціях потрібно зробити паузи як можна коротше. І тоді краще можуть бути алгоритми, в цілому уповільнюють роботу програм за рахунок фонового збору сміття, але зате з дуже короткими паузами.

На потужних системах ви також можете виконувати великі пакетні завдання. Для них важливі не паузи, а тільки загальний час виконання. В таких випадках краще використовувати алгоритм, який максимізує пропускну здатність (throughput), тобто відношення виконаної корисної роботи до часу, витраченого на збірку сміття.

На жаль, немає жодного алгоритму, повністю ідеального. Також runtime жодної мови не може визначити, чи є ваша програма пакетним завданням або інтерактивною програмою, чутливої до затримок. Саме це, а не дурість розробників runtime'а, призвело до появи «налаштувань збирача сміття». Це наслідок фундаментальних обмежень інформатики.

Гіпотеза поколінь (generational hypothesis)
У 1984 році було помічено, що більшість розміщень в пам'яті «помирають молодими», тобто стають сміттям через дуже короткий час після розміщення. Це спостереження, названа гіпотезою поколінь, — одне з найсильніших емпіричних спостережень у сфері розробки мов програмування. Гіпотеза ось уже кілька десятиліть підтверджується для самих різних мов: функціональних, імперативних, не мають і які мають типи даних.

Гіпотеза поколінь принесла користь в тому сенсі, що алгоритми складання сміття стали використовувати її плюси. Так з'явилися збирачі на основі поколінь (generational collectors), які мали ряд переваг у порівнянні зі старими алгоритмами «зупинити — позначити — очистити»:

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

  • Сумісність: алгоритми переміщують дані в пам'яті і роблять додаткові маніпуляції, коли програма в деяких випадках пише в покажчик. Це означає, що постачальник повинен бути тісно інтегрований з компілятором. Для С++ не існує збирачів на основі поколінь.
  • Надмірність купи: збирачі копіюють фрагменти пам'яті туди і назад між різними «просторами». Оскільки має бути достатньо місця для копіювання, виникає певна надмірність розміру купи. До того ж такі збирачі вимагають підтримки різних карт покажчиків (запам'ятовуються безлічі — remembered sets), що ще більше підвищує надмірність.
  • Розподіл пауз: хоча багато паузи дуже короткі, іноді все ж потрібні повні зупинки на позначку і очищення в рамках всієї купи.
  • Параметри: збирачі на основі поколінь ввели поняття «молоде покоління», або «райське простір» (eden space), і від його розміру сильно залежить продуктивність програми.
  • Тривалість прогріву: у відповідь на проблему налаштування деякі збирачі динамічно адаптують розмір молодого покоління на основі даних про поведінку виконуваної програми. Але тепер паузи стали залежати і від тривалості роботи програми. Зазвичай це важливо тільки для результатів бенчмарків.
Проте виграш від використання збирачів на основі поколінь так великий, що сьогодні цей тип абсолютно домінує. Якщо ви готові змиритися з недоліками, то вам напевно сподобаються такі збирачі. Ці алгоритми можна розширювати всілякими функціями, типові сучасні збирачі можуть бути в одній особі багато, паралельними, ущільнюючими (compacting) і використовують покоління.

Паралельний складальник в Go
Go — досить звичайний імперативний мову з типами значень. Мабуть, його шаблони доступу до пам'яті можна порівняти з З#, в якому використовується гіпотеза поколінь, отже, застосовується складальник .NET.

За фактом програми Go зазвичай вимагають наявності обробників запитів/відповідей на зразок HTTP-серверів. Тобто вони демонструють поведінку, сильно зав'язане на поколіннях. Творці Go думають, як це можна використовувати у майбутньому з допомогою таких речей, як «складальник, який орієнтується на запити» (request oriented collector). Як вже помітили, це просто перейменований сборщик на основі поколінь з налаштованої політикою терміну володіння.
Можна емулювати такий складальник в інших runtime'ах для обробників запитів/відповідей. Для цього потрібно впевнитися, що молоде покоління досить великим, щоб в нього вмістився увесь сміття, що генерується при обробці запиту.

Але незважаючи на це, сьогодні використовується в Go складальник — це складальник на основі поколінь. Він просто виконує тлі стару добру процедуру позначки з очищенням.

У такого підходу є одна перевага: можна отримати дуже-дуже короткі паузи. Але всі інші параметри погіршаться. Наприклад:

  • Пропускна здатність складальника: час, необхідне для очищення від купи сміття, збільшується з розміром купи. Чим більше пам'яті використовує ваша програма, тим повільніше ця пам'ять звільняється, і тим більше часу комп'ютер витрачає на складання порівняно з корисною роботою. Ви уникнете всього цього, тільки якщо програма взагалі не розпаралелює своє виконання, але ви можете без обмежень продовжувати використовувати ядра для збирання сміття.
  • Ущільнення: оскільки воно не виконується, програма може в результаті фрагментувати всю купу. Про це ми ще поговоримо нижче. Також ви не отримаєте переваг від акуратного використання кеша.
  • Пропускна здатність програми: в кожному циклі складальник повинен робити багато роботи. На це йде більше часу процесора, яке могло бути віддано самій програмі, а вона з-за цього працює повільніше.
  • Розподіл пауз: складальник, що виконується одночасно з програмою, може призвести до того, що в світі Java називається збоєм режиму спільного виконання (concurrent failure mode): програма генерує сміття швидше, ніж треди складальника встигають його чистити. У цьому випадку runtime'у доводиться повністю зупиняти програму і чекати завершення циклу очищення. Так що коли автори Go стверджують, що паузи дуже короткі, то це відноситься тільки до випадків, коли збирачу достатньо часу процесора, щоб не відставати від програми. Крім того, компілятору Go не вистачає можливостей, щоб надійно і швидко ставити треди на паузу. Тобто тривалість пауз сильно залежить від виконуваного вами коду (наприклад, base64-декодування великого блоба в одиночній горутине може призвести до збільшення пауз).
  • Надмірність купи: з огляду на повільність сміття в купі з допомогою позначки і очищення, вам потрібно багато місця в запасі, щоб не зіткнутися зі збоєм режиму спільного виконання. За замовчуванням в Go передбачена стовідсоткова надмірність… тобто він подвоює обсяг пам'яті, необхідної вашій програмі.
Ось уривок з одного поста, в якому розповідається про вищеописаних недоліки:

Сервіс 1 розміщує більше пам'яті, ніж Сервіс 2, тому паузи повної зупинки у нього довше. Проте в обох сервісів абсолютна тривалість пауз зупинки зменшується на порядок. Після включення на обох сервісах ми спостерігали ~20%-й зростання споживання складальником часу процесора.
В даному випадку тривалість пауз в Go знизилася на порядок, але за рахунок уповільнення роботи складальника. Чи можна це вважати виправданим компромісом або тривалість пауз і так вже була досить низькою? Автор не сказав.

Однак настає момент, коли більше не має сенсу нарощувати можливості заліза для скорочення пауз. Якщо паузи на сервері знизяться з 10 до 1 мс, чи помітять це користувачі? А якщо для такого зниження вам буде потрібно збільшити апаратні ресурси вдвічі?

Go оптимізує тривалість пауз за рахунок пропускної здатності, причому настільки, що здається, ніби він хоче на порядок сповільнити роботу вашої програми, лише б зробити паузи трішки менше.

Порівняння з Java
Віртуальна машина Java HotSpot має декілька алгоритмів складання сміття. Ви можете вибирати їх через командний рядок. Жоден з них не намагається так сильно знизити тривалість пауз, як Go, тому що вони намагаються підтримувати баланс. Щоб відчути вплив компромісів, можна порівняти алгоритми один з одним, перемикаючись між різними складальниками. Як? За допомогою простого перезапуску програми, тому що компілювання виконується по мірі її виконання, так що різні бар'єри, необхідні для різних алгоритмів, можуть по мірі необхідності компілюватися і оптимізуватися в коді.

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

Якщо вам потрібно зменшити тривалість пауз, то можете переключитися на складальник з паралельною поміткою та очищенням (concurrent mark/sweep collector, CMS). Це саме близьке до того, що використовується в Go. Але це алгоритм на основі поколінь, тому паузи у нього довше, ніж у Go: молоде покоління ущільнюється під час пауз, тому що виконується переміщення об'єктів. В CMS є два типи пауз: коротше, близько 2-5 мс, та достовірніше, близько 20 мс. CMS працює адаптивно: оскільки він виконується одночасно (concurrent), то повинен припускати, коли йому запуститися (як і в Go). У той час як Go попросить вас сконфігурувати надмірність купи, CMS самостійно адаптується в ході runtime, намагаючись уникнути збоїв режиму одночасного виконання. Оскільки більша частина купи обробляється за допомогою звичайної позначки і очищення, то можна зіткнутися з проблемами і гальмами з-за фрагментації купи.

Найсвіжіше покоління складальника в Java називається G1 (від garbage first). За замовчуванням він працює починаючи з Java 9. Автори постаралися зробити його як можна більш універсальним. Здебільшого він виконується одночасно, заснований на поколіннях (generational) і ущільнює всю купу. У чому самонастраиваемый. Але оскільки він не знає, чого ви хочете (як і всі збирачі сміття), дозволяє регулювати компроміси: просто вкажіть максимальний об'єм пам'яті, який ви виділяєте, і розмір пауз в мілісекундах, а все інше алгоритм піджене самостійно, щоб виконати ваші вимоги. За замовчуванням тривалість пауз близько 100 мс, так що, якщо ви не зменшіть їх самостійно, не чекайте, що це зробить алгоритм: G1 віддасть перевагу швидкості роботи програми.

Паузи не зовсім консистентны: більшість дуже короткі (менше 1 мс), але є і кілька довгих (більше 50 мс), пов'язаних з ущільненням купи. G1 чудово масштабується. Відомі відгуки людей, які застосовували його на купах терабайтного розміру. Також у G1 є ряд приємних можливостей начебто дедуплікаціі рядків в купі.

Нарешті, був розроблений ще один новий алгоритм під назвою Shenandoah. Він внесений в OpenJDK, але в Java 9 не з'явиться, поки ви не станете використовувати спеціальні білди Java з Red Hat (спонсора проекту). Алгоритм розроблений з метою мінімізації тривалості пауз, незважаючи на розмір купи, яка в той же час ущільнюється. До недоліків відносяться велика надмірність купи і ряд бар'єрів: для переміщення об'єктів під час виконання програми необхідно одночасно зчитувати покажчик та взаємодіяти зі збирачем сміття. У цьому сенсі алгоритм аналогічний «невпинне» збирача з Azul.

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

А якщо хочете мінімізувати тривалість пауз за рахунок усіх інших параметрів за будь-яку ціну, то зверніться до збирача сміття з Go.
Джерело: Хабрахабр

0 коментарів

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