Розподіл ресурсів у великих кластерах. Лекція в Яндексі

Більшість складних завдань з даними вимагають чималої кількості ресурсів. Тому майже у кожного дата-центру в світі не один, а безліч клієнтів — навіть якщо усі вони виступають під загальним брендом. Компаніям потрібні потужності під різні сервіси та цілі, так і в процесі досягнення якої-небудь однієї з них доводиться мати справу з цілим набором підзадач. Як дата-центру впоратися з потоком охочих щось проаналізувати або порахувати? Надходять замовлення на обчислення потрібно виконувати у певному порядку, намагаючись нікого не обділити ресурсами. Ця лекція — про основні методи розподілу реальних завдань на великому кластері. Спосіб, про який розповів Гнат Колесніченко, застосовується для обслуговування майже всіх сервісів Яндекса.

Гнат — керівник однієї з груп в нашій службі технологій розподілених обчислень. Закінчив мехмат МДУ і Школу аналізу даних, в Яндексі з 2009 року.



Під катом — детальна розшифровка лекції та слайди.

Всім добрий вечір. Мене звуть Колесніченко Гнат, я працюю в Яндексі, в службі розподілених технологій і обчислень. І сьогодні я вам спробую розповісти про одну задачу, яку я зустрів в цілком реальному житті. Для початку давайте трохи побільше розповім про те, з чого складається моя робота, що ми робимо. А далі — трохи докладніше про деталі, і перейдемо в підсумку до задачі, зрозуміємо, в чому вона полягає.

Що за продукт ми робимо? Ми робимо продукт для розробників і аналітиків Яндекса. Завдання полягає в тому, що ми будуємо великі кластера і софт поверх них. Ці великі кластера і софт поверх них дозволяють зберігати великі обсяги даних і не тільки зберігати, але й обробляти. Під величезними обсягами я маю на увазі петабайты, десятки петабайт. Петабайт в тисячу разів більше терабайта, а десятки тисяч петабайт більше в десятки тисяч разів. Завдання в тому, щоб побудувати таку систему, в яку звичайні розробники і аналітики Яндекса могли б прийти, запустити там свій досить простий код, і він би швидко і распределенно на всьому кластері відпрацював, отримав би результат. Потім вони побудували б який-небудь свій графік, зрозуміли, що частка Яндекса зростає або падає і робили б вже якісь висновки, покращували свій софт.
image
Що з себе являє кластер в нашому випадку? У нашому випадку кластер дуже спрощено виглядає наступним чином. Це багато-багато серверів, які називаються обчислювальними нодами. Сервер — це, загалом те ж саме, що і ваш ноутбук, тільки набагато більш потужний, і коштує він не десь, а в дата-центрі в якійсь полиці. Типові характеристики сервера — не як у звичайних ноутбуках, де 4-8 ядер. У них 30 ядер, 128 Гбайт пам'яті, загалом, багато ресурсів, які можна використовувати для того, щоб запускати завдання.

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

Планувальник за фактом представляє з себе сервер або, може бути, кілька серверів. А з точки зору інтерфейсу — того, як з ним працюють користувачі і як він спілкується із зовнішнім світом, — у нього є два види спілкування. Один вид — це запуск обчислень, коли приходить розробник і каже сервера в деякому вигляді запустити написану ним програму. Далі планувальник каже: «Так, я вашу програму прийняв, запустив. Тепер ось тут ви можете дивитися, що з нею станеться, коли вона виконується чи не виконується». Крім того, він спілкується з нашими обчислювальними нодами, з серверами. Що йому повідомляють обчислювальні ноди? Обчислювальні ноди говорять: «Дивись, у мене є стільки-то вільних ресурсів, у мене половина CPU не включена, купа вільної пам'яті, це все не використовується. Дай мені якесь завдання», — на що планувальник відповідає: «О! Тримай нові завдання». І так кожна нода з цим одним-єдиним планувальником спілкується.

Ще детальніше це виглядає приблизно наступним чином. У планувальника повинна бути певна стратегія того, як він вирішує, які завдання запускати, коли вони до нього приходять, і на яких ноди. Користувач приходить і запускає свої обчислення. Планувальник запам'ятовує: «О, у мене є таке-то обчислення» — і десь їх зберігає у своїй внутрішній структурі даних. Крім того, у нього є деяка своя стратегія. І коли обчислювальна нода до нього приходить, повідомляє йому про ті завдання і ресурси, які у неї біжать, наша стратегія повинна відповісти, що саме ноде треба зробити з її завданнями або які запустити нові завдання. Наприклад, вона може сказати: «Запусти мені, будь ласка, два завдання мого першого обчислення». Може сказати: «Запусти одну задачу другого обчислення, а ще обірви одну задачу третього обчислення, тому що третє обчислення занадто багато всього робить. Вистачить йому це робити».

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

Я хочу розповісти про те, що ми на попередньому слайді називали стратегією: що це, які вони бувають, якими властивостями вони повинні мати, як вони повинні працювати.

Що повинна робити стратегія? Її важлива функція — вирішити, яке завдання запустити. У неї є багато різних обчислень, які замовили користувачі, і їй треба зрозуміти, завдання якого з цих обчислень, який з цих операцій треба запустити. Ще важливо зрозуміти, чого користувачі хочуть від системи. Очевидно, що користувачі запускають свої обчислення і хочуть якихось гарантій — хочуть, щоб обчислення завершилося і як можна швидше. Про те, що буде матися на увазі під «як можна швидше», ми поговоримо пізніше. І глобальне питання – якими властивостями повинна володіти стратегія?

Перш ніж ми будемо говорити про стратегію, ще треба згадати про ресурси. Це важливий constraint того, як ми будемо визначати, що запускати, які є ресурси. Два найбільш зрозумілих і базових ресурсу — оперативна пам'ять, доступна нам на ноди, і кількість процесорів. Як ми зрозуміємо, можна запустити яку-небудь завдання на якому-небудь ноде? Коли користувач запустив обчислення, він повинен нам повідомити, скільки воно з'їдає оперативної пам'яті і скільки CPU він збирається використовувати. Якщо він не повідомив, то треба вважати, що це дефолтний значення. Якщо реальне завдання користувача раптом з'їдає більше, ніж він замовив, — потрібно буде просто її вбивати і говорити користувачу: «Ти запустив невалидное обчислення. Не треба так робити. Піди поміняй свої обмеження». Але будемо вважати, що користувач знає, скільки його програма з'їдає CPU, оперативної пам'яті, і виходячи з цього будемо діяти.

Про CPU зрозуміло, що будь-яка програма користувача з'їдає одне CPU, тому що якщо додаток однопотоковий — а більшість людей пишуть однопоточні програми, — то це одне CPU. А про пам'ять вже більш складне питання: треба зрозуміти, скільки різних структур даних програма користувача виділить, скільки вона буде їсти цієї пам'яті. І завдання користувача — зрозуміти, скільки ж його програма споживає.
Бувають менш популярні ресурси, наприклад, інтенсивність використання мережі. Може статися так, що програма користувача ходить куди-небудь по мережі і що-небудь собі викачує. Бувають програми, які активно мучать диски. Якщо ви почнете постійно читати з випадкових місць з вашого жорсткого диска на машинці, то жорсткий диск швидко закінчиться і перестане вам відповідати за якесь розумне час. Так що це теж важливо враховувати. Якщо виконати багато завдань, які хочуть диск на одній машинці, то всі вони будуть працювати дуже повільно, а користувачеві, очевидно, цього не хочеться.

Нам користувач повідомляє, скільки різних ресурсів хоче кожне обчислення. І про ноди ми теж знаємо, скільки ресурсів на них. Можна піти в який-небудь Sysprog і дізнатися, скільки там пам'яті, скільки є вільних ядер і як зараз використовуються ресурси на нашому обчислювальному сервері.

Далі ми почнемо говорити про стратегії. І перша стратегія, зовсім проста, про яку я розповім — це стратегія FIFO. Давайте я намалюю, як вона влаштована.

Наш планувальник буде наші операції вибудовувати в деяку чергу. FIFO розшифровується як first input first output, просто позначаючи поняття черги. Припустимо, у нас були користувачі, які вони запускали операції і у нашого планувальника є деяка чергу операцій. Далі все, що треба вирішити нашої стратегії, коли прийшла наша нода з якимись своїми ресурсами, — це які завдання яких з цих операцій їй запустити. Давайте зараз введемо якісь приземлені числа — знання про наші ноди, наші операції, — і розглянемо виходячи з них конкретний приклад того, як працює стратегія FIFO. Тоді буде зрозуміло, як вона влаштована.

Нехай на нашій ноде 32 CPU і 63 Гбайт пам'яті. Перша операція хай складається з 1000 підзадач, і кожна підзадача нехай з'їдає 1 CPU і 4 Гбайт пам'яті. Це перше завдання.

Друга задача нехай буде зовсім інша — складається з 500 підзадач, кожна з яких вимагає, наприклад, 10 CPU і 1 Гбайт пам'яті. І так далі.

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

Стратегія FIFO буде діяти таким простим чином. Вони недарма намальовані один за одним. Це означає, що вони впорядковані за часом. Хто раніше прийшов, запустив операцію — у того вона перша в черзі і встала. Стратегія FIFO буде спочатку пропонувати першої операції: «Перша операція, у тебе ще яка-небудь задача, яку я можу запустити на ноді?». Якщо є, то він буде говорити ноде запустити завдання першої операції. До чого це все призведе?

Давайте ще, крім того, припустимо, що у нас таких нод 100 штук. Якщо у нас 100 штук нод, скільки всього ресурсів в кластері у нас зараз є?

— 3200 CPU і 6400 ГБ, тобто 6 з половиною ТБ.

— Так. І стратегія буде першим ділом запускати всі у першої операції. Нескладно помітити, що в якийсь момент у цієї першої операції вона все запустить, а всі ресурси ще не вичерпає. Тобто в якийсь момент ми прийдемо до того, що тут у нас вже запущена тисяча з тисячі завдань, а ресурси ще не вичерпалися, на ноди ще щось є. У цей момент стратегія піде така: «Ага, у мене ще є вільні ресурси. Треба що-небудь ще запустити». Вона піде до наступної операції, і почне запускати її завдання. Можна навіть зрозуміти, скільки завдань другої операції їй вдасться запустити в кращому випадку.

Давайте ми подивимося. Запустивши першу операцію, ми витратимо 1000 CPU і 4000 Гбайт пам'яті. Значить, у нас залишиться 2200 CPU і 2400 Гбайт пам'яті. Далі на ці ресурси, що залишилися вона буде запускати другу операцію. Тут страждають головним ресурсом буде CPU, тобто його буде не вистачати, тому що пам'яті вона хоче мало, а CPU — багато. Тому, мабуть, нам вдасться запустити 220 завдань другої операції. І на цьому стадія запуску завдань закінчиться до тих пір, поки які-небудь завдання наших операцій не почнуть закінчуватись. Як тільки завдання у першій або в другій операції почнуть закінчуватись, планувальник почне це враховувати. Тобто коли нода до нього приходить, вона повідомляє, не тільки які у неї зараз є вільні ресурси, а і який статус у тих завдань, які на неї вже були запущені. Вона повідомить про якісь завдання, що вони закінчилися. Планувальник такий: «Ага, вони закінчилися! Можна туди піти і що-небудь ще спланувати». Він буде йти і намагатися дивитися на другу операцію, щоб що-небудь спланувати, на третю операцію, щоб що-небудь спланувати.

Про 220 завдань другої операції тут є певний обман. Всі бачать, у чому цей обман полягає? Чому не завжди може вийти запустити 220 завдань другої операції?

— У сенсі, повинно вийти менше?

— Може в деякому випадку вийти менше. Я сподіваюся, що більше ми в принципі не зможемо, тому що це суперечить нашим обмеженням, але може вийти з деяких причин менше.

— Тому що куди-то ще йде пам'ять.

— У нас чесні обмеження, реально ми ніщо більше і не витрачаємо. Але проблема полягає в тому, що завдання другої операції хочуть 10 CPU, а може трапитися так, що ми на одній ноде зайняли 25 CPU першим завданням, і у неї залишилося 7 вільних, а 7 вільних, очевидно, не вистачає, і планувальник тоді не має права взяти і запустити хоча б одну задачу другої операції, тому що на неї немає достатньої кількості ресурсів. Тобто вільні ресурси є, але цих вільних ресурсів не вистачає. Це проблема гранулярности, про яку ми сьогодні, напевно, не будемо говорити, але потрібно розуміти, що вона є. Взагалі кажучи, хороший планувальник повинен це враховувати. Якщо він розуміє, що десь з-за гранулярности він не може запустити, значить, він повинен спробувати що-небудь у першої операції, наприклад, витіснити. Зрозуміло, що перша операція для нього більш зручна, її простіше запускати на інших ноди в силу того, щоб запустити хоча б одну задачу другої операції.

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

Чесність – це непросте вимогу. Що під ним мається на увазі? У стратегії FIFO є така проблема. Уявіть, що у вас є багато користувачів, вони всі прийшли, позапускали операції, і комусь пощастило, хто запустив перший. А комусь- не дуже пощастило: він запустив, а перша операція виявилася дуже довгою, нудною, і, насправді, може бути, нікому не потрібною, і людина помилково її запустив, наприклад. Тоді всі будуть стояти і чекати, поки ця перша операції закінчиться, або її скасує, або що-небудь з нею станеться. Ясна річ, що користувача кластера, напевно, таке не дуже влаштовує, що твій сусід прийшов, раніше тебе встав в чергу, і щось довго робить. І все, і ти нічого не можеш зробити, а тобі треба терміново звіт почитати, в тебе робота із-за цього варто, і хочеться, щоб тобі що-небудь гарантували.

Що під цим буде матися на увазі? Припустимо, є у нас три користувача: А, В і С. Ці користувачі могли як-небудь домовитися, яка частка кластера кому належить. Наприклад, вони могли просто по своїй важливості або з якихось інших міркувань домовитися, що користувачу А належить 20% кластера, користувачеві належить 30% кластера, користувачеві Із — 50% кластера. І хочеться, щоб ми таку інформацію могли якось повідомити нашому планувальником, щоб він це міг врахувати у своїй стратегії і роздавати ресурс так, що 20% кластера належить користувачу А, 30% — користувачеві та 50% — користувачеві С.

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

Чому таке може бути? Уявіть, що завдання А для нашого кластера їдять 1 CPU і 4 Гбайт пам'яті. У користувача В це 10 CPU і 1 Гбайт пам'яті. Я стверджую, що тоді їм об'єднатися вигідніше, ніж жити по окремості.

Чому так? Уявіть, що у користувача А свої 20 машин, у користувача В — 30 машин. Вони запустили на всіх своїх машинах всі свої ресурси. Я малюю два стовпчика: перший стовпчик — CPU, другий — пам'ять. Я хочу зрозуміти в кожному цьому стовпчику, наскільки вони будуть заповнені з точки зору ресурсів сумарно на всьому кластері. При цьому я нагадаю, що у нас на кожній машинці було CPU 32 і 64 Гбайт пам'яті. І, припустимо, у цих операцій дуже багато своїх завдань, які вони запускають, тобто вони можуть всі ресурси кластера з'їсти.

У цього користувача А видно, наприклад, що він пам'ять з'їсть всю, а CPU — наполовину. У нас на машинці 64 Гбайт пам'яті і 32 CPU. Тоді скільки ми можемо запустити на 64 Гбайт пам'яті? 16 таких завдань. 16 завдань — вони, зрозуміло, наполовину наше CPU не з'їдять.

Окей, як у другого користувача справи? Протилежним чином. Він хоче багато CPU і мало пам'яті. Він, мабуть, з'їсть все CPU і скільки-то там пам'яті.

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

Що буде матися на увазі під чесністю? Що не повинно статися так, що користувачу А вигідніше відокремитися, ніж не відокремлюватися. Хочеться, щоб стратегія була такою, щоб всім було вигідно зібратися разом. Стратегія FIFO, очевидно, не є такою, тому що всі зібралися разом, встали в чергу А, В і С, але А і В з'їли весь кластер, не дісталося нічого. Він скаже: «Хлопці, так справа не піде. Давайте я свої 50 машин заберу, і ви самі запускайтесь. Так у мене буде хоча б 50 гарантованих машин, а так мені в стратегії FIFO нічого не дали». Напишу англійські версії. Чесність по-англійськи в даному контексті називають fairness.

Друга властивість — що ресурси не повинні простоювати. По-англійськи він називається страшним способом, а саме pareto efficiency. Це з економіки прийшов термін. Не так важливо. Якщо вам буде цікаво почитати, то ви будете розуміти, за якими словами все це справа гуглити або яндексить.

Що значить «ресурси не повинні простоювати»? Це теж природна вимога стратегії. Якщо до неї прийшла нода, у цій ноди є вільні ресурси і є хоча б одна задача, яку на цій ноде можна запустити, планувальник повинен взяти її і не запустити. Він не повинен говорити: «Ну, я вже начебто все по-чесному роздав. Вистачить, більше нічого не буду робити». Так не піде. Якщо він розуміє, що у нього є вільні ресурси і він на ці них щось може запустити, то він повинен це виконати. Це абсолютно природна вимога.

І третє, теж досить важливе і неочевидне вимога — що невигідно обманювати. По-англійськи це називається strategyproofness. Як ми знаємо, користувач приходить і визначає те, скільки ресурсів має з'їдати одне завдання його операції. Не повинно бути так, що, припустимо, його завдання хоче CPU 1 і 4 Гбайт пам'яті, а він взяв і сказав — 1 CPU і 5 Гбайт пам'яті. Якщо трапиться так, що він нас обдурить, а ми йому за рахунок цього ще й більше ресурсів дамо, і він зможе більше своїх завдань запустити, то це буде непорядок, тому що користувачам буде вигідно задати обмеження побільше, щоб собі побільше отримати. Хочеться, щоб користувачам було невигідно обманювати. Хочеться, щоб вони завжди говорили як можна більш правдиво про свої потреби, щоб, якщо вони говорять неправду, їм від цього стало тільки гірше. Тому що інакше користувачі поділять як-то кластери, а потім хто-небудь почне обманювати кого-небудь і за рахунок цього отримувати більшу частку кластера. Буде недобре. Це властивість на словах. А далі його, ясна річ, для кожної конкретної стратегії можна якось формалізувати. Ми сьогодні подивимося на одну таку формалізацію, що вона означає. Доводити, напевно, не будемо. Про це властивості.

Тепер давайте я покажу стратегію, яка цим властивостям задовольняє. Називатися вона буде DRF — dominant resource fairness. Ця стратегія буде приватною, ресурси у неї не будуть простоювати, тобто вона буде pareto efficient і strategyproofness. Однак, на жаль, у ній буде одна неприємна властивість: кожен конкретний користувач не може обдурити так, щоб йому стало краще, але користувачі можуть змовитися і таким хитрим чином обдурити систему, що все-таки комусь із них стане краще, і нікому не стане гірше. Але про це я наведу приклад, ми трохи пізніше поговоримо.

Щоб розповісти про те, як працює dominant resource fairness, треба ввести трошки понять і визначень. Давайте введемо S — це буде вектор ресурсів всього нашого кластера. Деякий S=(S1,...,Sr). В нашому випадку було як раз 3200 CPU і 6400 Гбайт пам'яті. R тут означає кількість ресурсів. Ясна річ, в залежності від того, що ви можете у своїй системі враховувати — в якихось системах враховувати диск можна, в яких-то не можна, — кількість цих ресурсів буває різне. Але завжди є два очевидні — CPU і пам'ять.

Крім того, нехай у нас є деякі наші завдання. Операція 1 операція 2 і т. д. Маються на увазі обчислення, які складаються з якихось конкретних завдань. Крім того, як ми говорили, люди як їх розподіляють. Нехай цей розподіл буде задано деякими вагами: вага 1, вага 2 і так далі, вага N. Сума ваг нехай буде дорівнює одиниці. Ваги отнормированы. Тобто вони вирішили, яку вагу у якої операції має бути і як вони хочуть поділити ресурси і кластери.

Також нам потрібна така річ, як вектор вимог операції — Dk. У нас був приклад. Цей вектор може бути 1000 * (1, 4). 1 — CPU, 4 — пам'ять. Я для зручності пишу, можна було записати як (1000, 4000). Коли у нас є такий вектор, щоб формально з ним можна було працювати і щоб приземлитися, у нас, ясна річ, повинні бути однаковим способом зафіксовані величини, в яких ми міряємо CPU, пам'ять і т. д. Припустимо, ми їх навіть однаково зафіксували тут і тут, а далі зручно одне на інше поділити, щоб зрозуміти, яку частку ресурсів всього кластера хоче наша конкретна операція.

Уявімо, що ми порахували таку річ, як (Dk1/S1,Dk2/S2,...,Dkr/Sr). Це буде вектор, який складається з якихось компонент. Кожна компонента означає, яку частку від всіх ресурсів цього кластера хоче дана операція. Після цього можна піти і подивитися на максимальну компоненту серед усіх цих чисел. Візьмемо тут argmax. Тоді ця компонента argmax і буде називатися домінантним ресурсом цієї операції. Визначення — домінантний ресурс операції k.

Нехай у нас тут залишиться 3200 і 6400, і нехай у нас D1 = 1000 * 1,4. Тоді цей вектор буде виглядати наступним чином: 1000/3200, 4000/6400. Видно, що друга його компонента більше, ніж перша, тому домінантним ресурсом у цій операції буде пам'ять. А якщо ми подивимося на іншу нашу операцію, в якій було 10 CPU і 1 Гбайт пам'яті, то у неї, навпаки, домінантним ресурсом буде CPU. Тобто домінантний ресурс — це такий ресурс, частка якого в побажаннях цієї операції найбільша.

Крім цього, у кожної операції наша частка працює. Що запускається, щось закінчується, і в кожен момент часу є таке поняття, як usage — мається на увазі реальне споживання операції. І Uk — це буде споживання ресурсів операцією K. тобто якщо у неї зараз запущено скільки-то її завдань, то Uk означатиме, скільки всього ресурсів ці завдання зараз споживають. Тобто це теж якийсь вектор, який пропорційний вектора Dk — тому що ми всі запускаємо пропорційно вектора Dk. Коли у нас визначено споживання ресурсів операцією k, можна ввести поняття uk. Це буде частка спожитих ресурсів.

Хотілося б відразу говорити про частку. Вся проблема в тому, як її визначити. І dominant resource fairness говорить про те, як визначити частку ресурсів кластера, яку з'їла дана операція. Якщо у нас один ресурс, то визначити її просто: беремо кількість цього ресурсу і ділимо на сумарний ресурс в кластері. А у нас ресурсів багато, і вони до кінця не зрозумілі. Dominant resource fairness пропонує визначити частку споживання ресурсів конкретної операції, тобто одне число, просто як частку максимального ресурсу в даній операції. S=(S1,...,Sr). Це число буде називатися usage ratio або часток спожитих ресурсів даної операції.

Коли визначена така частка, можна почати говорити про чесність в рамках стратегії DRF. Чесністю буде називатися наступна річ. Скажімо, що стратегія DRF чесна, якщо для будь-якої операції вірно, що частка ресурсів, які вона спожила або споживає при деякій кількості ітерацій більше або дорівнює її вазі (Uk ≥ Wk). Тобто якщо операції пообіцяли 20% ресурсів кластера, значить, принаймні, за домінантним ресурсу цієї операції їй повинні дати 20% цього кластера. Якщо самих ресурсів вона взагалі не хотіла хотіла істотно менше — їй дадуть їх менше. Це не до кінця очевидно. Але в певному сенсі зрозуміло, чому, якщо стратегія DRF чесна, вона буде чесною і в нашому загальному випадку, чому нікому не буде вигідно відокремитися.

Уявіть, що комусь обіцяли 20%, йому 20% у такий спосіб дають, а він взяв і вирішив: «Ні, невигідно. Я краще отделюсь». Тоді у нього, зокрема, і за домінантним ресурсу після відділення буде матися в його маленькому кластері 20%. Це означає, що більше, ніж тут, він запустити все одно не міг, тому що в нього ресурси обмежені. І все погано, він уперся. А за рахунок того, що він з кимось об'єднався, можна зробити так: коли інший хоче, навпаки, CPU, а не пам'ять, вони удвох з'їдять більше ресурсів у кластері та отримають частку більше, ніж обіцяна їм Wk.

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

Перш ніж розповідати, як він влаштований, давайте зрозуміємо, чому він є. Насправді, зрозуміло, чому він є — тому що, як ми тільки що говорили, якщо хтось відокремився зі своїми 20% кластера, то він, коли всі займе, отримає в точності вага Wk в цьому кластері. Якщо ми дивимося на ресурси кластера як на два великих стовпчика CPU і ПАМ'ЯТІ, то, припустимо, тут пообіцяли комусь 50%, комусь 20%, комусь 30%. Припустимо, вони як-то тут з'їли свої ресурси: цей з'їв усе це і трошки RAM, а цей з'їв скільки-то CPU і весь RAM. Це операція 1, це операція 2, а це операція 3. І третя з'їла весь RAM, але не всі CPU. Якщо наша стратегія навіть ось так розподілить, то вже буде все добре — вже буде Uk ≥ Wk. Але зауважимо, що у нас ще залишилися ресурси: у нас залишилися ще CPU, недораспределенные від другої і третьої операцій. І ще залишився нерозподілений RAM. Стратегія може як їх розподілити. Як саме вона це зробить, ми зараз побачимо, коли будемо описувати алгоритм.

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

Як буде влаштована стратегія? Є у нас операції: операція 1, 2, 3 і т. д. Є наш планувальник. Йому треба якось зрозуміти. Зараз є якась поточне положення. Ми знаємо ваги цих операцій — W1, W2, W3 — і знаємо їх реальне поточне споживання. У нашій стратегії тепер треба як можна швидше зрозуміти. До неї прийшла нода, сказала: «У мене є вільні ресурси. Кого мені запустити?» Нам треба якомога швидше зрозуміти, кого запустити.

Будемо робити наступним способом. Наша стратегія буде просто итерироваться, перебирати всі наші операції, і кожен раз вибирати ту, у якої як можна менше значення S=(S1,...,Sr). Вибираємо таке k, що вираз Uk/Wk мінімально. Як ефективніше це зробити — вже алгоритмічний питання. Можна яку-небудь чергу з пріоритетами завести у себе в пам'яті і в цій черги з пріоритетами просто зберігати вказані значення. І коли у нас щось завершується, ми Uk будемо зменшувати, а коли що-то збільшується — збільшувати. Що буде робити стратегія? Вона кожен раз буде брати операцію, в якій це значення мінімально, і говорити: «Ой, я одну задачу для неї зараз збираюся запустити». Збільшується Uk на скільки-то. І повторювати до тих пір, поки вільні ресурси на ноде, яка до неї прийшла, не закінчаться. Так вона зрозуміє, який набір завдань їй треба на цій ноде запустити, піде і запустить їх. І оновить значення k.

У нас вірно наступне: якщо ми почнемо все розподіляти з нуля, то вийде Uk ≥ Wk. Так як ми це знаємо, то зрозуміло, що якщо забути про питання похибки ця стратегія як раз знайде таке рішення, у якого все Uk будуть більші або дорівнюють Wk — тому що вона кожного разу дає мінімальне значення і потроху їх збільшує. З-за гранулярности таке не може трапитися. Ми бачили приклад, коли є у нас 10 CPU — а це дуже велика частка на кожній обчислювальної ноде — і може бути так, що ми першу роздали, а далі вже зазначені 10 CPU нікому дати не можемо. Це окреме питання, про який ми скоро поговоримо.

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

Ми зрозуміли, як влаштована стратегія, зрозуміли, що вона є чесною і в своєму сенсі, і в сенсі загального визначення чесності. Чому вона не допускає вигоди від одиничного обману? Давайте ми залишимо це вам як вправа. Це зовсім нескладно доводиться. Можна довести, що якщо хтось обдурив, то від цього стане тільки гірше. Можна навіть які-небудь міркування на пальцях провести. Наприклад, якщо операція обдурила з того ресурсу, який у неї домінантний, то потім це число у неї почне збільшуватися швидше, ніж раніше. Тобто їй начебто дали такий же шматочок, а воно у неї збільшилася сильніше. За рахунок того, що воно у неї збільшилася сильніше, їй за фактом дадуть менше цього ресурсу. Тому якщо операція запросила 1000 CPU замість одного, який їй реально потрібен, то їй дадуть зовсім мало CPU.

Давайте намалюємо якісь приклади. Коли ми будемо малювати приклади, можна трошки спрощено дивитися на картину. Можна вважати, що у наших операцій нескінченно великою demand, тобто запит ресурсів. І ще одне допущення, про який я говорив, — що вони хочуть ресурси у відсотках від ε.

Уявіть, що у нас є дві операції. Коли ми говоримо, що у них нескінченно великою demand, далі безглуздо говорити про якихось конкретних величинах. Безглуздо говорити, що у них 1000 CPU або 2000 Гбайт пам'яті. Нас, насправді, буде цікавити тільки пропорція, в якій кожна операція хоче своїх ресурсів. Давайте вважати, що пропорція, в якій перша операція хоче своїх ресурсів, — це (1, ½), а друга, наприклад, хоче в пропорції (½, 1). А роздавати ми будемо так: ми теж всі ресурси, які у нас є, отнормируем, і будемо вважати, що на нашому кластері одиничний вектор наших ресурсів, наприклад, такий — S=(S1,...,Sr). Питання: як наша стратегія надійде в цьому випадку? Яку частку кластера вона дасть у першій операції, яку в другій? Чи можна це зрозуміти з опису стратегії? Розуміє хто-небудь, які тут будуть вектора і яку частку кластери дадуть першої операції, а який другий?

Дивіться, як все буде відбуватися. Подивимося на невеликий проміжок часу, коли ми видаємо першою, а що-то видаємо другий, причому ми завжди видаємо тієї, яка мінімальна. Тому можна вважати, що коли у нас пройшло трохи часу, то ми дали трохи, і трохи ми дали однаково пропорційно що першою операції, що другий. Причому ми даємо пропорційно їх домінантним ресурсу. Через невеликий проміжок часу у нас вийде наступна картина. Тут буде (ε, ε/2), тут — (ε/2, ε), а ресурсів, які у нас залишаються незадіяними, вільними, буде стільки: (1 – 3ε/2, 1 – 3ε/2). Далі ця ε буде збільшуватися, і до яких пір? В який момент ми перестанемо що-небудь роздавати? Якою буде ситуація в кінці? Мені здається, треба вирішити просте рівняння. У нас все закінчиться в той момент, коли кількість ресурсів тут стане нульовим, необов'язково по всіх векторах, але в даному випадку — за всім, оскільки ми зможемо пропорційно всім роздати. Все закінчиться тоді, коли в корені стане нуль. Якщо ми роздаємо пропорційно, то тут вийде (⅔, ⅓), а тут, навпаки, (⅓, ⅔).

Весь перший і весь другий ресурс ми роздали, причому роздали пропорційно. Відразу нагадаю, що вага W у нас тут був 0,5, а реальна частка U, яку ми дали, буде дорівнює⅔. У цій операції точно так само. Це той випадок, коли їм було вигідно об'єднатися.

Буває так, що неважливо, об'єдналися вони чи ні. Давайте намалюємо ще який-небудь приклад. Нехай тут, наприклад, (0,1), а тут (1,1). Як розподіляться ресурси після того, як DRF закінчить свою роботу і всі їх роздасть? Який вектор ресурсів буде дано першої операції, який вектор ресурсів буде дано другої операції? Можливо, які-небудь припущення або ідеї? У першої операції домінантним є що перший, що другий ресурс, у другої — тільки другий ресурс. Тому можна вважати, що домінантний у обох операцій другий ресурс, і тому воно буде роздавати пропорційно другого ресурсу.

Навпіл, так. Тобто буде (½, ½), (0, ½).

— А як ми визначаємо, яке рішення з двома буде?

— У нашій задачі спочатку був якийсь вектор реальних ресурсів на кластері, і тут теж були якісь реальні вектора споживання. А тут ми вже отнормировали, і те, що тут написано, — це після нормування. Причому ми це все отнормировали до одиниці, і як би максимальний ресурс у нас був дорівнює одиниці. Тобто всі ці вектора вже у спрощеній формі виглядають як одна компонента. У них обов'язково один цей домінантний ресурс, а всі інші — від 0 до 1. Вони теж можуть бути дорівнюють одному, але не більше одного бути не можуть. Тобто такий вектор визначає, в якій пропорції щодо всіх доступних на кластері ресурсів перебуває вимога в цій операції. Ця операція пропорційно хоче першого і другого ресурсу. А ця операція першого ресурсу не хоче взагалі, а хоче тільки другий.

Давайте я наведу приклад, як змова допомагає виграти, допомагає отримати собі додатковий ресурс. Приклад досить хитрий, але не те щоб суперсложный. І це теж хороший привід потренуватися на те, як DRF працює.

У нас буде чотири операції і три ресурсу. Перша операція буде хотіти тільки CPU. Друга операція теж буде хотіти тільки CPU, тобто тільки перший ресурс. Третя операція буде хотіти тільки пам'ять, а четверта операція буде трохи більш хитра — вона буде хотіти і пам'ять, і ще третій ресурс, давайте називати його мережею. Є у нас така картина. Я тут не малюю ваги. Коли я не малюю ваги, це означає, що роздати ми хочемо пропорційно. Тут можна було б малювати ваги, тобто за фактом ваги скрізь¼. Але коли вони всі однакові і дорівнюють¼, я просто їх опускаю, бо мається на увазі, що це і так зрозуміло. Коли ваги не будуть пропорційно розділені, ми будемо явно виписувати, скільки якої ваги на якому ребрі написано, тобто певною пропорційності вони лунають.

Давайте зрозуміємо, як у цьому випадку відпрацює DRF. Ось він пропорційно всім роздає. Щоб зрозуміти, як він працює, корисно уявити собі наступне. Завжди є якийсь ресурс, у якого сумарні вимоги тут найбільше. У якогось ресурсу сумарні вимоги тут найбільше?

— У першого CPU.

— Так, тому що у нього сумарні вимоги — 2, у пам'яті сумарні вимоги 1,5, а в мережі взагалі 1. Тому, коли ми будемо роздавати пропорційно, першим закінчиться цей ресурс. Це означає, що можна дійти до ситуації (½, 0, 0), (½, 0, 0). Цим ми теж повинні були дати ½ частку, тому тут буде (0, ½, 0), а тут — (0, ¼, ½). У неї домінантний ресурс третій, і ми їй стільки видали. Після цього у нас перший ресурс закінчився, і більше ми нічого ні першої, ні другої операції не даємо. Тепер ми даємо тільки третьої і четвертої операції, і теж даємо стільки, щоб у них все зростало пропорційно.

— Чому ми четвертої даємо мережа½?

— А ми хочемо, щоб у всіх була ½ з точки зору їх частки спожитих ресурсів.

— А іншим не треба.

— Ні, ми ще не дораздали, ми дивимося. Як працює алгоритм — він усім пропорційно роздає, підвищує частку. Потім якийсь ресурс міг закінчитися. Ми дійшли до того моменту, коли перший ресурс закінчився. Тепер він уже розуміє, що цим давати не треба нічого, тому що просто немає ресурсу, і він починає пропорційно давати цим. Коли він буде пропорційно роздавати другого і третього, чим це все завершиться?

— Ресурс закінчиться.

— Так. Який ресурс закінчиться?

— Другий.

— Так. Причому у них повинна бути пропорційна частка. Тут можна було б вирішити лінійні рівняння, але здається, що все і так зрозуміло. Все закінчиться, коли тут стане (0, ⅔, 0), а тут — (0, ⅓, ⅔). Тобто у нас тепер ресурсом, який ми зіткнемося, буде пам'ять, тому що пам'ять — другий за потреби ресурс в нашому кластері серед решти незаблокованих операцій. Раз ми у нього упремося, значить, нам треба зрозуміти, в який момент ми на ньому зупинимося. Далі у нас є у цього домінантний ресурс — мережа, у цього пам'ять, і треба зрозуміти, що мережа в два рази більше, ніж пам'ять. Вони в пропорції ½ по пам'яті і зупиняться. Тобто кінцева картина така: цього дали (½, 0, 0), цього (½, 0, 0), цього (0, ⅔, 0), — (0, ⅓, ⅔).

Для розуміння давайте випишемо тут ваги. Тут вага був¼, а usage½. Тобто ми дали в два рази більше, ніж він міг розраховувати. Тут теж¼,½. Ваги у них у всіх¼, а дали йому⅔, тобто навіть ще більше. І тут так само — вага¼, а дали⅔. Виявляється, що тепер деякі учасники цієї системи можуть змовитися і за рахунок цього виграти собі побільше ресурсів. Що означає змову групою? Це означає, що кілька учасників системи можуть змовитися, зібрати свої ресурси, і в результаті вийде так, що кожен з них отримає частку не менше, ніж у них була до цього, а хтось ще і строго більше. Тобто ясна річ, що іноді можна брехати, і нічого від цього не отримувати, не програвати. Таке можливо, тому що є якийсь четвертий ресурс, який ніхто не використовує на кластері, що ви про нього збрехали, ви його отримали, але він все одно не потрібен — частка у вас яка була, така і залишилася. Тут все хитріше. Можна набрехати наступним чином.

Змовлятися у нас будуть перші троє. Перший і другий просто візьмуть і збрешуть про мережу, яка їм не потрібна. Виявиться, що якщо вони збрешуть про мережу, то третій, який вимагає тільки пам'ять, несподівано отримає більше ресурсів, ніж було б, якби вони не збрехали. Буде (0, ½, 1). Тут таких ресурсів, які вимагають максимум, цілих два. Тут і з першого ресурсу сума 2, і по третьому ресурсу сума 2. Тому ми зупинимося тоді, коли зупиняться одночасно обидва цих ресурсу. Це буде в той момент, коли ми роздамо½, тобто прийдемо до такої ситуації: ( ½, 0, ¼), (½, 0, ¼), (0, ½, 0), (0, ¼, ½).

Наша стратегія DRF всім дала по ½ — здавалося б, все чесно і справедливо. Причому перший і третій ресурс у нас вже закінчилися. Тому залишився тільки другий ресурс — пам'ять, і ясна річ, кому його треба віддати. Його залишилася¼, значить, треба його цього і віддати. В результаті він отримає (0, ¾, 0), що, очевидно, більше, ніж (0, ⅔, 0). Таким чином, вийшла хитра річ: перші двоє набрехали про мережу, третій виграв по пам'яті, хоча мережа нікому з них трьох взагалі не була потрібна. Така проблема є, і як її вирішувати — незрозуміло. Історична довідка така: спочатку стверджувалося, що це властивість — воно з наступної статті про алгоритм DRF — вірно, та був доказ на пальцях. Ми просто теж займалися цим питанням, придумали свою стратегію для більш складного випадку, і теж спробували довести для неї властивості. Поки ми намагалися довести для неї властивості, ми знайшли контрприклад для нашої стратегії. Потім зрозуміли, що раз ми знайшли контрприклад для нашої стратегії, то давайте спробуємо його ж і для вихідної. І з'ясувалося, що і для вихідної стратегії це невірно. Вихідна стратегія не володіє цією властивістю. Далі ми спробували знайти стратегію, яка є одночасно і чесною, і такий, що ресурси не простоюють, і не допускає змови. Незрозуміло, чи існує така стратегія. Всі прості розумні стратегії — для них для всіх знаходиться який-небудь неприємний контрприклад, який порушує третя властивість. Є така чи ні — не до кінця зрозуміло. Здавалося б, завдання досить проста, комбінаторна — просто якісь вектора, як-то розподіляються ресурси, вимоги досить просто описуються. А є стратегія чи ні — не до кінця зрозуміло. І як знайти таку стратегію або як довести, що її немає, — теж не до кінця зрозуміло. Якщо вам це цікаво, то можете на дозвіллі подумати і щось придумати в цьому місці.

А я поки розповім про дві речі, які не згадані. Одна річ полягає в тому, що це все чудово, але на практиці описана стратегія DRF теж працювати не буде з однієї простої причини, в цілому схожою з тим, що у нас відбувалося в стратегії FIFO. Уявіть, що у вас є три користувача: A, B і C. Ви пообіцяли цьому 20%, цьому 30%, цьому 50%. Далі є у вас кластер, ніч, все простоює, ніхто нічого не запускає. Настає ранок, приходить користувач А і запускає величезну свою операцію. Ясна річ, що поки B і C нічого не запустили, ми маємо всі ресурси кластера віддати першому користувачу, тому що він запустив операцію, і чого ми будемо його зараз якось обмежувати? Ми віддамо всі ресурси, а після цього до нас прийдуть B і C зі своїми запитами. Вони прийдуть, поставлять операції, і нічого не станеться. А перша операція біжить і не збирається закінчуватися. Тобто як тільки завдання першої операції почнуть закінчуватись, то вивільнені ресурси будуть даватися В і С, але якщо у першій задачі все не закінчується і не закінчується, то не буде нічого діставатися, вони будуть незадоволені, будуть писати вам, дзвонити, прийдуть до вас ногами, почнуть скаржитися — відбудуться різні неприємності. Щоб такого не було, потрібно, щоб у вашій системі була певна стратегія витіснення. Стратегія витіснення — це певний план, що якщо комусь погано, то як би кого-небудь, кому дуже добре, трошки витіснити з кластера, сказати: «щось у вас багато біжить завдань. Давайте ми які-небудь припинимо».

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

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

Ще одна річ, про яку я не встиг поговорити, але коротко скажу — це те, що називається ієрархічним DRF або HDRF. На жаль, користувачам такого не вистачає. «20% кластера? Ні, це нам не дуже підходить. У нас є ще важливі завдання, неважливі завдання, ще щось». Люди хочуть, щоб у них була не плоска, а складна ієрархія. Хочуть, щоб цього — де нічого всередині немає — йому дали 30%. 30%, але у нього всередині є якісь свої переваги — є research-завдання, а є production-завдання. І він хоче, щоб research з того, що йому дали в кластері, дісталося 20%, а production — 80%. Тут, припустимо, теж два типи завдань, і він хоче, щоб їм дісталося по 50%. Далі є цей, і у нього теж якийсь розподіл — 30% і 70%. Тобто люди хочуть, щоб система була плоскою, а ієрархічною, і щоб scheduler — наш планувальник — це як-то враховував, щоб він розумів, що є така ієрархія, і прагнув кожному дати пропорційно тому, скільки йому обіцяно. Тут у нас є якийсь пул, яким ми пообіцяли 30%, а в ньому є подпул, яким ми пообіцяли 20%. Це означає, що всіх завдань, які біжать в цьому поддереве, має дістатися хоча б 30%, а серед них завдань з цього подпула має дістатися 30% * 20%, тобто 6%. Він хоче, щоб цього дісталося як мінімум 6% від ресурсів всього кластера. Є такі більш складні вимоги.

Як би таке зробити? Є наївне пропозицію: «А давайте складну ієрархію перетворимо в просту ієрархію». Ми можемо порахувати про кожну вершинку, скільки від частки всього кластера їй має дістатися. Ми порахували для цієї, вийшло 6%, а можемо для всіх інших порахувати. Тобто тут буде 6%, 20%, 15%, 35%, 12% і 12%. І є ідея: давайте просто з цієї ієрархії зробимо плоску, в якій будуть 6%, 20%, 15%, 35%, 12%, 12%. На жаль, така ідея не працює. Та не працює вона наступним способом. Так, цим дадуть стільки, скільки їм пообіцяли, але після цього може виявитися, що всього цього не дадуть його обіцяні 30%. А ми домовилися, що цього відділу в Яндексі повинні давати на кластері 30%. Ми цим всім видали, а сумарно 30% не набралося, тому що у цих можуть бути різні домінантні ресурси. Може бути, ця хоче пам'ять, ця хоче CPU, ця мережа. Ми сумарно роздали, і навіть якщо всі ресурси, які вони з'їли, скласти, то як вектор вони не будуть з'їдати 30% кластера. Така ось проблема. Тому доводиться підтримувати дерева.

Яке друге наївне рішення тут може бути? Давайте наш алгоритм DRF перетворимо наступним чином. Як він раніше діяв? Він знаходився в корені, дивився на ваги своїх дітей, дивився на їх споживання домінантного ресурсу і того, у кого це споживання домінантного ресурсу, поділена на вагу, мінімально, йшов і пропонував, давав завдання. Ми продовжимо робити так само. Просто коли ми підемо сюди, то далі повторимо вже на цьому поддереве ту ж саму операцію. Тобто ми спочатку зрозуміли, що цього поддереву дають найменше, а потім у цьому поддереве намагаємося зрозуміти, кому там знову дають найменше. Точно так само, вибираючи на кожному рівні в кожному вузлі мінімум серед дітей, серед відносин їх usage до ваги, ми будемо йти в мінімального до тих пір, поки не дійдемо до якогось листа. І вже в тому аркуші, тієї операції, що там лежить, запропонуємо завдання.

На жаль, так теж не працює. Покажу приклад, чому не працює така стратегія, яка називається naïve HDRF. Не працює вона з наступної причини. Давайте подивимося на таку нескладну ієрархію. У нас тут вимоги тільки з першого ресурсу, тут теж тільки по першому, а тут з другого. Що буде, якщо ми сюди застосуємо нашу naïve HDRF? В цілому все добре. Спочатку ми, напевно, прийдемо до того моменту, коли ми сюди дали половину, і сюди дали половину. Тобто тут у нас стала (½, 0), тут сумарний demand (1, 1), тому тут стало (½, ½), яка розподіляється як (½, 0), (0, ½). Після цього у нас залишився ще другий ресурс, і далі після деяких ітерацій тут стане (0, 1). Здавалося б, все добре. Цього дали половину CPU і всю пам'ять, а цього — іншу половину CPU. Начебто обіцянки для всіх дотримали. Але виникає така проблема. Припустимо, ми прийшли до такої ситуації, коли трапляється проблема: ця операція бере і починає закінчуватися, у неї закінчуються її завдання. Вона потихеньку зменшується, і стає 0. Що робить scheduler? Він дивиться в корені: «Цього я дав половину всього CPU, пам'ять він не просив. А цього я дав всю пам'ять, але ніякого CPU. Домінантний ресурс у цього — пам'ять, у цього — CPU. Раз у цього домінантний ресурс CPU і його½, а у цього пам'ять і вона 1, то треба давати тому, у кого поменше, тобто цього. Scheduler просто піде і почне давати цьому ще CPU. І в результаті ми прийдемо до ситуації, коли тут у нас (1, 0), (0, 0), а тут (0, 1). І як би ми це піддерево, цей пул не обдурили, але конкретно цю операцію — обдурили. Їй взагалі нічого не дісталося, у неї все закінчилося, і їй нічого більше не дають. Проблема.

Min satisfaction HDRF — один із способів вирішення цієї проблеми. Скажу на словах. Він полягає в наступному: давайте, коли ми будемо вибирати, кому давати, то будемо дивитися не лише на цей вектор і домінантний ресурс всього пулу, а для кожного вузла поддереве порахуємо ставлення. Зазвичай, коли у нас дерево, ці вузли, вершинки в дереві, позначаються якимись літерами, і пишуть usage S=(S1,...,Sr). Виявляється, що якщо вибирати мінімальні з усіх таких відносин, то тоді все буде добре. Тобто ми будемо дивитися на ставлення і в цьому вузлі, і в обох його дітей. А якщо в тих чи є ще діти, то і в них теж. Якщо наш алгоритм буде діяти таким чином, то тоді він усім дасть як мінімум обіцяну там частку.

На цьому ми підходимо до кінця.

Висновок. Як мені здається, те, що я сьогодні розповів, — хороший приклад того, як в ідеальній практичної задачі, яка постає в моїй цілком конкретній реальній роботі, виникає якась математична формалізація і математична задача. Це нечастий випадок, і те, що він стався, — це, по-моєму, дуже здорово. Тому що частіше за все математика і практика трошки окремо живуть, і зрідка щось з математики знаходить застосування в практиці. А коли вдається формалізувати практичну задачу, привести її до математично — це дуже здорово, і це дає свої плоди, тому що коли ти робиш щось навмання на практиці, найчастіше це не працює — ти отримуєш рішення навмання. А якщо ти можеш строго довести щось про рішення, то це дуже добре. Це значить, що раз ти зміг це строго довести, то, напевно, воно майже завжди буде добре працювати. В результаті min satisfaction HDRF — це те, що ми на роботі придумали, і він забезпечив на 5-10% більш ефективний алгоритм. Користувачі перестали страждати, перестали скаржитися, ми стали ефективніше використовувати ресурси кластера, і все стало добре. Крім того, ми знайшли ряд помилок в чужих статтях, поставили деякі нові питання, що теж здорово. Це цікаво взяти і дослідити. На жаль, часу не дуже вистачає. Може бути, у когось з вас або у когось з онлайн-слухачів на цей час знайдеться, і вони вирішать наші відкриті питання.

Всі. Всім дякую. Радий був тут виступати.
Джерело: Хабрахабр

0 коментарів

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