Распределение ресурсов в больших кластерах. Лекция в Яндексе
Игнат — руководитель одной из групп в нашей службе технологий распределенных вычислений. Окончил мехмат МГУ и Школу анализа данных, в Яндексе с 2009 года.
Под катом — подробная расшифровка лекции и слайды.
Всем добрый вечер. Меня зовут Колесниченко Игнат, я работаю в Яндексе, в службе распределенных технологий и вычислений. И сегодня я вам попробую рассказать про одну задачу, которую я встретил во вполне реальной жизни. Для начала давайте чуть побольше расскажу о том, из чего состоит моя работа, что мы делаем. А дальше — чуть подробнее о деталях, и перейдем в итоге к задаче, поймем, в чем она состоит.
Что за продукт мы делаем? Мы делаем продукт для разработчиков и аналитиков Яндекса. Задача состоит в том, что мы строим большие кластера и софт поверх них. Эти большие кластера и софт поверх них позволяют хранить огромные объемы данных, и не только хранить их, но и обрабатывать. Под огромными объемами я подразумеваю петабайты, десятки петабайт. Петабайт в тысячу раз больше терабайта, а десятки тысяч петабайт больше в десятки тысяч раз. Задача в том, чтобы построить такую систему, в которую обычные разработчики и аналитики Яндекса могли бы прийти, запустить там свой достаточно простой код, и он бы быстро и распределенно на всем кластере отработал, получил бы результат. Затем они построили бы какой-нибудь свой график, поняли, что доля Яндекса растет или падает и делали бы уже какие-то выводы, улучшали свой софт.
Что из себя представляет кластер в нашем случае? В нашем случае кластер очень упрощенно выглядит следующим образом. Это много-много серверов, которые называются вычислительными нодами. Сервер — это в целом то же самое, что и ваш ноутбук, только гораздо более мощный, и стоит он не где-то, а в дата-центре в какой-то полке. Типичные характеристики у сервера — не как в обычных ноутбуках, где 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, второй — память. Я хочу понять в каждом этом столбике, насколько они будут заполнены с точки зрения ресурсов суммарно на всем кластере. При этом я напомню, что у нас на каждой машинке было 32 CPU и 64 Гбайт памяти. И, допустим, у этих операций очень много своих задач, которые они запускают, то есть они могут все ресурсы кластера съесть.
У этого пользователя А видно, например, что он память съест всю, а CPU — наполовину. У нас на машинке 64 Гбайт памяти и 32 CPU. Тогда сколько мы можем запустить на 64 Гбайт памяти? 16 таких задач. 16 задач — они, понятно, наполовину наше CPU не съедят.
Окей, как у второго пользователя обстоят дела? Противоположным образом. Он хочет много CPU и мало памяти. Он, видимо, съест всё CPU и сколько-то там памяти.
Дальше видно, что если бы они вместе объединили свои ноды в один большой кластер и у А была бы свободная CPU, а у Б — свободная память, то понятно, что они сказали бы запустить что-нибудь еще себе. То есть им было бы выгоднее объединиться, чем жить по раздельности. Это соображение — чисто с точки зрения пользователей. На самом деле есть еще разные соображения просто с человеческой точки зрения — что чем больше у вас разных сущностей, тем тяжелее их поддерживать, потому что понятное дело, что за каждым кластером должны быть люди, которые за него ответственны, которые могут что-то починить, если что-то ломается. Поэтому чем у вас меньше таких сущностей, тем меньше вам нужно держать отдельных людей, которые за этим будут следить. Более того, можно эффективнее утилизировать ресурсы. Однако важно понять, как так распределить ресурсы, чтобы было верно следующее.
Что будет подразумеваться под честностью? Что не должно случиться так, что пользователю А выгоднее отделиться, чем не отделяться. Хочется, чтобы стратегия была такой, чтобы всем было выгодно собраться вместе. Стратегия FIFO, очевидно, не является такой, потому что все собрались вместе, встали в очередь А, В и С, но А и В съели весь кластер, С не досталось ничего. Он скажет: «Ребята, так дело не пойдет. Давайте я свои 50 машин заберу, и вы сами запускайтесь. Так у меня будет хотя бы 50 гарантированных машин, а так мне в стратегии FIFO ничего не дали». Напишу английские версии. Честность по-английски в данном контексте называют fairness.
Второе свойство — что ресурсы не должны простаивать. По-английски оно называется страшным способом, а именно pareto efficiency. Это из экономики пришедший термин. Не так важно. Если вам будет интересно почитать, то вы будете понимать, по каким словам все это дело гуглить или яндексить.
Что значит «ресурсы не должны простаивать»? Это тоже естественное требование стратегии. Если к ней пришла нода, у этой ноды есть свободные ресурсы и есть хотя бы одна задача, которую на этой ноде можно запустить, планировщик должен взять ее и не запустить. Он не должен говорить: «Ну, я уже вроде всем по-честному раздал. Хватит, больше ничего не буду делать». Так не пойдет. Если он понимает, что у него есть свободные ресурсы и он на эти них что-то может запустить, то он должен это запустить. Это совершенно естественное требование.
И третье, тоже достаточно важное и неочевидное требование — что невыгодно обманывать. По-английски это называется strategyproofness. Как мы знаем, пользователь приходит и задает то, сколько ресурсов должна съедать одна задача его операции. Не должно быть так, что, допустим, его задача хочет 1 CPU и 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 и RAM, то, допустим, тут пообещали кому-то 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). Вопрос: как наша стратегия поступит в этом случае? Какую долю кластера она даст в первой операции, какую во второй? Можно ли это понять из описания стратегии? Понимает ли кто-нибудь, какие здесь будут вектора и какую долю кластеры дадут первой операции, а какую второй?
Смотрите, как все будет происходить. Посмотрим на небольшой промежуток
