Наиболее сложные задачи обработки данных требуют значительного количества ресурсов.
Поэтому почти каждый дата-центр в мире имеет не одного, а множество клиентов — даже если все они работают под общим брендом.
Компаниям необходимы мощности для выполнения множества услуг и целей, и в процессе достижения любой из них им приходится иметь дело с целым набором подзадач.
Как дата-центр может справиться с потоком людей, желающих что-то проанализировать или посчитать? Поступающие заказы на расчеты необходимо выполнять в определенном порядке, стараясь никого не лишить ресурсов.
Эта лекция посвящена основным методам распределения реальных задач на большом кластере.
Метод, описанный Игнатом Колесниченко, используется для обслуживания практически всех сервисов Яндекса.
Игнат — руководитель одной из групп нашей службы технологий распределенных вычислений.
Окончил Механико-математический университет МГУ и Школу анализа данных в Яндексе с 2009 года.
Ниже приведена подробная стенограмма лекции и слайды.
Добрый вечер всем.
Меня зовут Колесниченко Игнат, я работаю в Яндексе, в сервисе распределенных технологий и вычислений.
И сегодня я попытаюсь рассказать вам об одной проблеме, с которой я столкнулся в вполне реальной жизни.
Для начала позвольте мне рассказать вам немного подробнее о том, в чем состоит моя работа и чем мы занимаемся.
А потом – еще немного о деталях, и наконец перейдем к задаче, поймем, что это такое.
Какой продукт мы производим? Мы делаем продукт для разработчиков и аналитиков Яндекса.
Проблема в том, что мы создаем большие кластеры и программное обеспечение на их основе.
Эти большие кластеры и программное обеспечение поверх них позволяют хранить огромные объемы данных и не только хранить их, но и обрабатывать.
Под огромными объемами я подразумеваю петабайты, десятки петабайт. Петабайт в тысячу раз больше терабайта, а десятки тысяч петабайт в десятки тысяч раз больше.
Цель — построить систему, в которую могли бы прийти обычные разработчики и аналитики Яндекса, запустить там свой достаточно простой код, и он бы работал быстро и распределялся по всему кластеру и получал результат. Тогда бы они построили какой-то свой график, поняли бы, что доля Яндекса растёт или падает и уже сделали бы какие-то выводы и улучшили бы свой софт. 
Что такое кластер в нашем случае? В нашем случае кластер выглядит очень упрощенно следующим образом.
Это много-много серверов, которые называются вычислительными узлами.
Сервер по сути такой же, как ваш ноутбук, только гораздо мощнее, и находится он не где-то, а в дата-центре на какой-то полке.
Типичные характеристики сервера не похожи на характеристики обычных ноутбуков, имеющих 4-8 ядер.
У них 30 ядер, 128 ГБ памяти, в общем много ресурсов, которые можно использовать для запуска задач.
Кроме того, чтобы управлять этими вычислительными узлами, чтобы там что-то запускать, чтобы что-то работало, чтобы хранить данные, нужна какая-то система.
И важной частью системы являются две вещи — метаинформационный сервер, который будет знать, где какие данные находятся в этом кластере и что на нем происходит, и планировщик, который будет решать, где какие задачи запускать.
Сегодня мы в основном будем говорить о планировщике.
Давайте подробнее рассмотрим, что это может быть.
Планировщик — это по сути сервер, а может быть и несколько серверов.
А с точки зрения интерфейса — как с ним взаимодействуют пользователи и как он общается с внешним миром — у него есть два типа общения.
Один тип — запуск вычислений, когда приходит разработчик и говорит серверу запустить написанную им программу в той или иной форме.
Тогда планировщик говорит: «Да, я принял вашу программу и запустил ее.
Теперь здесь вы можете увидеть, что с ним произойдет, когда оно будет исполнено или не исполнено».
Кроме того, он общается с нашими вычислительными узлами, с серверами.
Что ему говорят вычислительные узлы? Вычислительные узлы говорят: «Смотрите, у меня столько свободных ресурсов, у меня половина ЦП незанята, много свободной памяти, все это не используется.
Дайте мне какую-нибудь задачу», на что планировщик отвечает: «О! Держите новые задачи».
И так каждый узел общается с этим одним планировщиком.
Еще более подробно это выглядит примерно так.
Планировщик должен иметь некоторую стратегию того, как он решает, какие задачи запускать, когда они к нему поступают и на каких узлах.
Пользователь приходит и начинает свои расчеты.
Планировщик запоминает: «Ой, у меня есть такой-то расчет» — и сохраняет их где-то в своей внутренней структуре данных.
Кроме того, у него есть своя стратегия.
И когда к нему приходит вычислительный узел и рассказывает о задачах и ресурсах, которые на нем работают, наша стратегия должна ответить, что именно узлу нужно делать со своими задачами или какие новые задачи запускать.
Например, она может сказать: «Пожалуйста, решите мне две задачи из моего первого расчета».
Там может быть написано: «Запустите одну задачу второго расчета, а также завершите одну задачу третьего расчета, потому что третий расчет делает слишком много.
Прекрати это делать».
Теперь еще немного о расчетах и задачах, о том, что все это такое.
Ответ зависит от типа расчета, но в простом случае можно сказать, что пользователь приходит с каким-то собственным написанным кодом, будь то бинарник на Python или C++, говорит, какие ресурсы он хочет иметь в кластере и каким-то образом описывает это.
Стратегия каким-то образом запоминает и распределяет данные, которые вы хотите обработать — а они расположены на разных узлах — на кусочки.
И уже по этим кусочкам стратегия начинает расчет. Будем считать, что каждое вычисление — их еще называют операциями — состоит просто из некоторого набора задач.
Чуть дальше мы увидим, что под этим подразумевается.
Я хочу поговорить о том, что мы на предыдущем слайде называли стратегией: что это такое, какие они бывают, какими свойствами они должны обладать, как они должны работать.
Что должна делать стратегия? Его важная функция — решить, какую задачу запустить.
У нее много разных расчетов, которые заказали пользователи, и ей нужно понять, задачу какого из этих расчетов, какую из этих операций нужно запустить.
Также важно понимать, чего хотят пользователи от системы.
Очевидно, что пользователи запускают свои расчеты и хотят какой-то гарантии — они хотят, чтобы расчет завершился как можно скорее.
О том, что означает «как можно скорее», мы поговорим позже.
И глобальный вопрос: какими свойствами должна обладать стратегия? Прежде чем говорить о стратегии, нам еще нужно вспомнить о ресурсах.
Это важное ограничение на то, как мы будем определять, что запускать и какие ресурсы у нас есть.
Два самых понятных и базовых ресурса — это доступная нам на узлах оперативная память и количество процессоров.
Как мы поймем, можно ли на каком-то узле запустить какую-то задачу? Когда пользователь запускает расчет, он должен сообщить нам, сколько оперативной памяти он потребляет и сколько процессора он собирается использовать.
Если он не сообщил, то надо считать, что это значение по умолчанию.
Если реальная задача пользователя вдруг потребляет больше, чем он заказывал, вам нужно будет просто убить ее и сказать пользователю: «Вы запустили неверный расчет. Вам не обязательно этого делать.
Идите меняйте лимиты.
» Но мы будем считать, что пользователь знает, сколько его программа потребляет процессор и оперативную память, и будем действовать исходя из этого.
По поводу ЦП понятно, что любая пользовательская программа съедает один ЦП, потому что если приложение однопоточное - а большинство людей пишут однопоточные приложения - то это один ЦП.
А насчет памяти более сложный вопрос: нужно понимать, сколько различных структур данных выделит пользовательская программа, какой объем этой памяти она будет использовать.
И задача пользователя — понять, сколько потребляет его программа.
Есть менее популярные ресурсы, например интенсивность использования сети.
Может случиться так, что пользовательская программа заходит куда-то в сеть и что-то скачивает. Есть пользовательские программы, которые активно мучают диски.
Если вы начнете постоянно читать из случайных мест с жесткого диска на печатной машинке, то жесткий диск быстро разрядится и перестанет вам отвечать в разумные сроки.
Так что это тоже важно учитывать.
Если вы запускаете множество задач, всем из которых требуется диск на одной и той же машине, то все они будут работать очень медленно, а пользователь явно этого не хочет. Пользователь сообщает нам, сколько различных ресурсов требуется для каждого расчета.
А еще мы знаем об узлах, сколько у них ресурсов.
Можно зайти в какой-нибудь Sysprog и узнать, сколько там памяти, сколько свободных ядер и как в данный момент используются ресурсы на нашем вычислительном сервере.
Далее мы начнем говорить о стратегиях.
И первая стратегия, совершенно простая, о которой я расскажу, — это стратегия ФИФО.
Давайте я нарисую, как это будет устроено.
Наш планировщик выстроит наши операции в определенную очередь.
FIFO означает «первый вход — первый выход», что просто обозначает концепцию очереди.
Допустим, у нас были пользователи, они каким-то образом запускали операции, и у нашего планировщика есть некая очередь операций.
Тогда все, что должна решить наша стратегия, когда наш узел прибудет с некоторыми своими ресурсами, — это то, какие задачи какой из этих операций он должен запустить.
Давайте теперь представим некоторые обыденные цифры — знания о наших узлах, наших операциях — и на их основе рассмотрим конкретный пример того, как работает стратегия FIFO. Тогда будет понятно, как это работает. Пусть наш узел имеет 32 процессора и 63 ГБ памяти.
Пусть первая операция состоит из 1000 подзадач и каждая подзадача потребляет 1 процессор и 4 ГБ памяти.
Это первая задача.
Пусть вторая задача будет совсем другой — состоящей из 500 подзадач, каждая из которых требует, например, 10 CPU и 1 ГБ памяти.
И так далее.
Пришли пользователи, начали такие операции, и наша стратегия должна понять, какой из них дать этому узлу.
Допустим, в стратегию приходит свободная нода, и ей нужно решить, что с ней делать.
Стратегия ФИФО будет работать следующим простым способом.
Не зря их рисуют друг за другом.
Это означает, что они упорядочены по времени.
Кто пришёл первым, тот и начал операцию – тот был первым в очереди и встал.
Стратегия FIFO сначала спросит первую операцию: «Первая операция, есть ли у вас еще какая-нибудь задача, которую я могу запустить на узлеЭ» Если да, то он сообщит узлу выполнить задачу первой операции.
К чему все это приведет? Давайте также предположим, что у нас есть 100 таких узлов.
Если у нас 100 узлов, сколько всего ресурсов у нас сейчас в кластере? — 3200 ЦП и 6400 ГБ, то есть 6 с половиной ТБ.
- Да.
И стратегия будет заключаться в том, чтобы сначала запустить все при первой операции.
Легко заметить, что в какой-то момент первая операция исчерпает все ресурсы, но еще не исчерпает все ресурсы.
То есть в какой-то момент мы придем к тому, что у нас здесь уже запущено тысяча из тысячи задач, а ресурсы еще не исчерпаны; на узлах еще что-то есть.
На данный момент стратегия будет такой: «Да, у меня еще есть свободные ресурсы.
Нам нужно начать что-то еще».
Он перейдет к следующей операции и начнет выполнять свои задачи.
Можно даже понять, сколько задач второй операции он сможет выполнить в лучшем случае.
Давайте разберемся.
Запустив первую операцию, мы потратим 1000 ЦП и 4000 ГБ памяти.
Это означает, что у нас будет 2200 процессоров и 2400 ГБ памяти.
Затем он запустит вторую операцию, используя оставшиеся ресурсы.
Здесь главным страдающим ресурсом будет ЦП, то есть его будет недостаточно, потому что памяти ему нужно мало, а ЦП нужно много.
Поэтому, судя по всему, мы сможем запустить 220 задач второй операции.
И на этом этапе этап запуска задач закончится, пока некоторые задачи наших операций не начнут заканчиваться.
Как только задачи первой или второй операции начнут иссякать, планировщик начнет это учитывать.
То есть, когда к нему приходит нода, она сообщает не только о том, какие свободные ресурсы у нее есть на данный момент, но и каков статус тех задач, которые на ней уже запущены.
Она сообщит вам о некоторых заданиях, которые они завершились.
Планировщик сказал: «Да, их нет! Мы можем пойти туда и спланировать что-нибудь еще».
Он пойдет и попытается посмотреть на вторую операцию, чтобы что-то спланировать, на третью операцию, чтобы что-то спланировать.
Здесь есть некоторый обман по поводу 220 заданий второй операции.
Все видят, что это за обман? Почему не всегда можно запустить 220 задач второй операции? - Что значит, должно быть меньше? — В некоторых случаях может оказаться меньше.
Я надеюсь, что больше мы в принципе не сможем сделать, потому что это противоречит нашим ограничениям, но по каким-то причинам может оказаться меньше.
- Потому что память уходит куда-то еще.
— У нас честные ограничения, мы действительно больше ничего не тратим.
Но проблема в том, что задачи второй операции хотят 10 ЦП, и может случиться так, что на одном узле мы заняли 25 ЦП первой задачей, а у нее осталось 7 свободных, а 7 свободных явно недостаточно, и тогда планировщик не имеет права взять и запустить хотя бы одну задачу второй операции, потому что на нее не хватает ресурсов.
То есть свободные ресурсы есть, но этих бесплатных ресурсов недостаточно.
Это проблема детализации, о которой мы, наверное, сегодня не будем говорить, но надо понимать, что она существует. Вообще говоря, хороший планировщик должен это учитывать.
Если он понимает, что где-то из-за гранулярности он не может что-то запустить, то ему следует попробовать что-то на первой операции, например, вытеснить.
Понятно, что первая операция ему удобнее; его легче запустить на других узлах за счет того, что он может запустить хотя бы одну задачу второй операции.
Пойдем дальше.
Мне хотелось бы понять, какие у нас требования к стратегии.
В общем, их можно написать большой список.
Сегодня я рассмотрю три самых основных и важных из них.
Опишем подробнее, что они означают. 
Честность – сложное требование.
Что это значит? Стратегия FIFO имеет эту проблему.
Представьте, что у вас много пользователей, все они пришли, начали работу, и кому-то повезло, кто запустил первый.
А кому-то очень не повезло: он запустил его, но первая операция оказалась очень долгой, нудной и, по сути, никому не нужной, и человек запустил ее, например, по ошибке.
Тогда все остальные будут стоять и ждать, пока эта первая операция завершится, или пользователь ее отменит, или с ним что-нибудь произойдет. Понятно, что пользователю кластера это наверняка не очень приятно, что ваш сосед пришел, встал в очередь раньше вас и что-то долго делает. И все, и сделать ничего не можешь, а отчет нужно срочно прочитать, работа у тебя из-за этого застопорилась, а ты хочешь, чтобы тебе что-то гарантировали.
Что это будет значить? Допустим, у нас есть три пользователя: A, B и C. Эти пользователи могли бы как-то договориться о том, какая доля кластера кому принадлежит. Например, они могли бы просто, исходя из их важности или по каким-то другим причинам, договориться, что пользователь А имеет право на 20% кластера, пользователь Б имеет право на 30% кластера, а пользователь С имеет право на 50% кластера.
кластер.
И нам хотелось бы иметь возможность как-то передать эту информацию нашему планировщику, чтобы он учёл это в своей стратегии и распределил ресурс так, чтобы 20% кластера принадлежало пользователю А, 30% пользователю Б и 50% пользователю C. Когда мы говорим об этом, возникает наивный вопрос: если они так разделили ресурсы, то почему бы им не освободиться на три отдельных кластера, а не попробовать жить на одном? Для этого есть причина.
Причина вот в чем: я хочу, чтобы им было выгоднее объединиться, чем жить по отдельности.
Почему это может быть? Представьте, что задачи пользователя А для нашего кластера потребляют 1 процессор и 4 ГБ памяти.
Пользователь B имеет 10 процессоров и 1 ГБ памяти.
Я утверждаю, что тогда им выгоднее объединиться, чем жить по отдельности.
Почему это? Представьте, что у пользователя А есть 20 собственных машин, а у пользователя Б — 30 машин.
Они запустили все свои ресурсы на всех своих машинах.
Рисую два столбца: первый столбец — процессор, второй — память.
Я хочу понять в каждом из этих столбцов, насколько они будут заполнены с точки зрения ресурсов в целом по всему кластеру.
При этом напомню, что у нас на каждой машине было по 32 процессора и 64 ГБ памяти.
И, скажем так, у этих операций много своих задач, которые они запускают, то есть могут потреблять все ресурсы кластера.
Для этого пользователя А вы можете увидеть, например, что он съест всю память и половину процессора.
Наша машина имеет 64 ГБ памяти и 32 процессора.
Тогда сколько мы сможем пробежаться на 64 ГБ памяти? 16 таких задач.
16 задач — они, конечно, не съедят половину нашего процессора.
Хорошо, а как дела у второго пользователя? В обратном порядке.
Ему нужно много процессора и мало памяти.
Очевидно, он съест весь процессор и немного памяти.
Далее видно, что если бы они объединили свои узлы в один большой кластер и у А был бы свободный ЦП, а у Б — свободная память, то понятно, что они бы сказали им запустить себе что-то еще.
То есть им было бы выгоднее объединиться, чем жить по отдельности.
Это соображение чисто с точки зрения пользователей.
На самом деле, просто с человеческой точки зрения есть еще разные соображения – что чем больше у вас разных сущностей, тем сложнее их поддерживать, потому что понятно, что за каждым кластером должны стоять люди, которые за него отвечают, кто сможет что-то починить, если что-то сломается.
Поэтому чем меньше у вас таких субъектов, тем меньше вам нужно иметь отдельных людей, которые будут за этим следить.
Кроме того, ресурсы можно использовать более эффективно.
Однако важно понимать, как распределять ресурсы так, чтобы выполнялось следующее.
Что подразумевается под честностью? Чего не должно произойти, так это того, что пользователю А лучше отделиться, чем не отделиться.
Мне бы хотелось, чтобы стратегия была такой, чтобы всем было выгодно объединиться.
Стратегия FIFO явно не такая, потому что все собрались, поставили в очередь A, B и C, но A и B съели весь кластер, C ничего не получил.
Он скажет: «Ребята, это не сработает. Давай я возьму свои 50 машин, и ты сможешь завести их сам.
Таким образом у меня будет минимум 50 гарантированных машин, но по стратегии FIFO мне ничего не дали».
Я напишу английские версии.
Честность по-английски в данном контексте называется fairness. Второе свойство — ресурсы не должны простаивать.
По-английски это называется ужасным способом, а именно эффективностью по Парето.
Это термин, пришедший из экономики.
Не так важно.
Если вам интересно читать, то вы поймете, какими словами загуглить или яндексить все это дело.
Что значит «ресурсы не должны простаивать»? Это также естественное требование стратегии.
Если к нему приходит нода, у этой ноды есть свободные ресурсы и есть хотя бы одна задача, которую можно запустить на этой ноде, то планировщик должен ее взять, а не запускать.
Он не должен говорить: «Ну, я уже всем честно раздал.
Хватит, больше ничего делать не буду».
Так не пойдет. Если он понимает, что у него есть свободные ресурсы и он может что-то запустить с помощью этих ресурсов, то ему следует это запустить.
Это совершенно естественное требование.
И третье, тоже весьма важное и неочевидное требование – обманывать невыгодно.
По-английски это называется Strategyproofness. Как мы знаем, пользователь приходит и задает, сколько ресурсов должна потреблять одна задача его работы.
Не должно быть так, скажем, его задача хочет 1 ЦП и 4 ГБ памяти, а он нам просто сказал — 1 ЦП и 5 ГБ памяти.
Если случится так, что он нас обманет, и из-за этого мы дадим ему больше ресурсов, и он сможет запускать больше своих задач, то это будет бардак, потому что пользователям будет выгодно установить больший лимит в чтобы получить больше для себя.
Хотелось бы, чтобы пользователям было невыгодно обманывать.
Я хочу, чтобы они всегда говорили как можно правдивее о своих потребностях, чтобы, если они говорили неправду, это только ухудшало их положение.
Потому что иначе пользователи каким-то образом поделят кластеры, и тогда кто-то начнет кого-то обманывать и тем самым получит большую долю кластера.
Это будет нехорошо.
Это свойство на словах.
И потом, конечно, это можно как-то формализовать для каждой конкретной стратегии.
Сегодня мы рассмотрим одну из таких формализаций и ее значение.
Наверное, мы этого не докажем.
Речь идет о свойствах.
Теперь позвольте мне показать вам стратегию, которая удовлетворяет этим свойствам.
Это будет называться DRF — доминирующая справедливость ресурсов.
Эта стратегия будет частной, ее ресурсы не будут простаивать, то есть она будет эффективной по Парето и стратегически устойчивой.
Однако, к сожалению, у него будет одно неприятное свойство: каждый конкретный пользователь не может обмануть, чтобы ему стало лучше, но пользователи могут сговориться и обмануть систему таким хитрым способом, что кому-то из них станет легче, но никому – нет. становиться хуже.
Но я приведу пример, об этом мы поговорим чуть позже.
Чтобы поговорить о том, как работает доминирующая справедливость ресурсов, нам нужно ввести несколько концепций и определений.
Введем S — это будет вектор ресурсов всего нашего кластера.
Некоторые S=(S 1 ,.
,С р ).
В нашем случае было всего 3200 процессоров и 6400 ГБ памяти.
R здесь означает количество ресурсов.
Конечно, в зависимости от того, что вы можете учитывать в своей системе — в одних системах можно учитывать диск, в других нет — количество этих ресурсов варьируется.
Но всегда есть два очевидных — процессор и память.
Также давайте поставим несколько задач.
Операция 1, операция 2 и т. д. Имеется в виду расчеты, состоящие из каких-то конкретных задач.
К тому же, как мы уже говорили, люди их как-то распространяют. Пусть это распределение задано какими-то весами: будет вес 1, вес 2 и так далее, вес N. Пусть сумма весов равна единице.
Весы нормализованы.
То есть они как-то решили, какой вес должна иметь каждая операция и как они хотят разделить ресурсы и кластеры.
Еще нам понадобится такое понятие, как вектор требований операции — D к .
У нас был пример.
Этот вектор может быть 1000 * (1, 4).
1 – процессор, 4 – память.
Я пишу для удобства; это можно записать как (1000, 4000).
Когда у нас есть такой вектор, чтобы мы могли формально с ним работать и чтобы приземлиться, у нас, конечно, должны быть зафиксированы те же самые значения, точно так же, как мы измеряем процессор, память и т. д. Давайте скажем, мы даже зафиксировали их одинаково здесь и здесь, а потом удобно разделить одно на другое, чтобы понять, какую долю ресурсов всего кластера хочет наша конкретная операция.
Давайте представим, что мы посчитали такую вещь как ( Д к 1 / С 1 , Д к 2 / С 2 ,.
, Д к р / С р ).
Это будет вектор, состоящий из некоторых компонентов.
Каждый компонент представляет, какой процент всех ресурсов в этом кластере требуется операции.
После этого можно пойти и посмотреть максимальную составляющую среди всех этих чисел.
Давайте возьмем здесь argmax. Тогда этот компонент argmax будет называться доминирующим ресурсом этой операции.
Определение: доминирующий ресурс операции k. Пусть здесь останется 3200 и 6400, и пусть у нас будет D 1 = 1000 * 1,4. Тогда этот вектор будет выглядеть так: 1000 / 3200 , 4000 / 6400 .
Видно, что второй его компонент больше первого, поэтому доминирующим ресурсом для этой операции будет память.
А если мы посмотрим на другую нашу операцию, у которой было 10 ЦП и 1 ГБ памяти, то, наоборот, ее доминирующим ресурсом будет ЦП.
То есть доминирующим ресурсом является ресурс, доля которого в желаниях этой операции наибольшая.
При этом на каждую операцию работает наша доля.
Что-то начинается, что-то заканчивается, и в каждый момент времени существует такое понятие, как использование — под этим подразумевается фактическое потребление операции.
И ты к - это будет потребление ресурсов операцией К.
То есть, если в данный момент у нее выполняются какие-то ее задачи, то U к укажет, сколько общих ресурсов потребляют эти задачи в данный момент. То есть это тоже какой-то вектор, пропорциональный вектору D к - потому что мы запускаем все пропорционально вектору D к .
Определив потребление ресурсов операции k, мы можем ввести понятие u к .
Это и будет доля потребляемых ресурсов.
Хотелось бы сразу поговорить об акции.
Вся проблема в том, как это определить.
А доминирующая справедливость ресурсов говорит о том, как определить долю ресурсов кластера, потребляемую данной операцией.
Если у нас один ресурс, то определить это легко: берем количество этого ресурса и делим его на общий ресурс в кластере.
Но у нас много ресурсов, и они до конца не изучены.
Доминирующая справедливость ресурсов предполагает определять долю потребления ресурсов конкретной операцией, то есть одно число, просто как долю максимального ресурса в данной операции.
S=(S 1 ,.
,С р ).
Это число будет называться коэффициентом использования или долей ресурсов, потребляемых данной операцией.
Как только эта доля будет определена, можно будет начать говорить о справедливости в рамках стратегии ФДР.
Следующее, что будет называться честностью.
Будем говорить, что стратегия DRF является справедливой, если для какой-либо операции верно, что доля ресурсов, которые она израсходовала или потребляет за определенное количество итераций, больше или равна ее весу (U к ≥ Вт к ).
То есть, если операции было обещано 20% ресурсов кластера, то, по крайней мере, с точки зрения доминирующего ресурса этой операции, ей должно быть отдано 20% этого кластера.
Если бы она вообще не хотела самих ресурсов или хотела бы значительно меньше, ей бы дали меньше.
Это не совсем очевидно.
Но в некотором смысле понятно, почему, если стратегия ДФС честна, она будет честной и, в нашем общем случае, почему никто не выиграет от отделения.
Представьте, что кому-то пообещали 20%, ему таким образом дают 20%, а он взял и решил: «Нет, это не выгодно.
Я бы предпочел расстаться».
Тогда, в частности, по доминирующему ресурсу после разделения у него будет 20% в его небольшом кластере.
Это значит, что больше, чем здесь, он все равно запустить не сможет, потому что ресурсы у него ограничены.
И все плохо, он сопротивлялся.
А за счет того, что он с кем-то объединился, можно сделать так: когда другой хочет, наоборот, ЦП, а не память, они вдвоем съедят больше ресурсов в кластере и получат долю побольше чем обещанный им W к .
Мы объяснили, что означает справедливый DRF. Теперь, когда мы объяснили, что это такое, хотелось бы понять, существуют ли такие стратегии, и если да, то как должен быть структурирован алгоритм, обеспечивающий это.
Это будет выглядеть так.
Прежде чем рассказать, как это работает, давайте разберемся, почему оно существует. На самом деле понятно, почему он там — ведь, как мы только что рассуждали, если кто-то отделил свои 20% кластера, то он, когда заберет все, получит ровно вес W к в этом кластере.
Если рассматривать ресурсы кластера как два больших столбца ЦП и ОЗУ, то, скажем, кому-то обещали 50%, кому-то 20%, кому-то 30%.
Допустим, они как-то съели свои ресурсы: этот съел всё это и немного ОЗУ, а этот съел немного ЦП и всю ОЗУ.
Это операция 1, это операция 2, а это операция 3. И третья съела всю оперативку, но не весь ЦП.
Если наша стратегия хотя бы так распределит, то всё будет хорошо — U уже будет к ≥ Вт к .
Но учтите, что у нас еще остались ресурсы: у нас все еще есть процессоры, которые были недораспределены во второй и третьей операциях.
И еще есть нераспределенная оперативная память.
Стратегия может их как-то распределить.
Теперь мы увидим, как именно он это сделает, когда опишем алгоритм.
Если мы просто разделим ресурсы пропорционально, то распределить их так, чтобы каждый распоряжался своим ресурсом, конечно, получится.
Худший случай для нас — это когда им всем нужен один и тот же ресурс.
Тогда они все будут его придерживаться, все остальные будут использоваться недостаточно, и им будет все равно.
Результат будет эквивалентен тому, как если бы они были разделены на отдельные кластеры или не были разделены.
Но они будут использовать разные ресурсы, им нужна выгода.
Как будет построена стратегия? У нас есть операции: операция 1, 2, 3 и т. д. У нас есть свой планировщик.
Ему нужно как-то понять.
Теперь есть некоторая текущая ситуация.
Мы знаем веса этих операций — W 1 ,Вт 2 ,Вт 3 — и мы знаем их реальное текущее потребление.
Наша стратегия теперь должна быть понята как можно быстрее.
К ней пришел узел и сказал: «У меня есть свободные ресурсы.
Кого мне бежатьЭ» Нам нужно как можно быстрее разобраться, кого запускать.
Мы сделаем это следующим образом.
Наша стратегия будет просто повторяться, проходить через все наши операции и каждый раз выбирать ту, у которой наименьшее возможное значение S=(S 1 ,.
,С р ).
Выберем k так, чтобы выражение ты к / Вт к минимальный.
Как это сделать эффективнее – вопрос алгоритмический.
Вы можете создать в своей памяти какую-то очередь приоритетов и просто хранить в этой очереди заданные значения.
И когда у нас что-то заканчивается, мы Ю к мы будем уменьшаться, а когда что-то увеличится, мы увеличимся.
Что будет делать стратегия? Каждый раз она будет брать операцию, у которой это значение минимально, и говорить: «Ой, я сейчас для нее одну задачу запущу».
U увеличивается к как долго.
И повторять до тех пор, пока не закончатся свободные ресурсы на пришедшем к нему узле.
Таким образом она поймет, какой набор задач ей нужно запустить на этом узле, и пойдет и запустит их.
И обновит значение k. Для нас справедливо следующее: если мы начнём раздавать всё с нуля, то получим U к ≥ Вт к .
Поскольку мы это знаем, ясно, что если мы забудем о проблеме ошибки, эта стратегия точно найдет решение, для которого все U к будет больше или равно W к - потому что это дает минимальное значение каждый раз и в течение нескольких часов Теги: #Оптимизация серверов #ИТ-инфраструктура #Системное администрирование #Облачные вычисления #кластеры #стратегии #распределенные вычисления #деревья решений #распределение ресурсов
-
Либреофис 4.0.0
19 Oct, 24 -
Как И Зачем Делать Отчеты?
19 Oct, 24
