Доминирующая справедливость ресурсов

Справедливость доминантных ресурсов (DRF) — это правило справедливого разделения . Это особенно полезно для разделения вычислительных ресурсов между пользователями в средах облачных вычислений , где каждому пользователю может потребоваться разная комбинация ресурсов. DRF представили Али Годси , Матей Захария , Бенджамин Хиндман, Энди Конвински, Скотт Шенкер и Ион Стойка в 2011 году. ^[1]

Мотивация

В среде с одним ресурсом широко используемым критерием является максимальная и минимальная справедливость , целью которого является максимизация минимального количества ресурсов, предоставляемых пользователю. Но в облачных вычислениях необходимо совместно использовать различные типы ресурсов, такие как память, процессор, пропускная способность и дисковое пространство. Предыдущие справедливые планировщики, такие как Apache Hadoop , сводили настройку нескольких ресурсов к настройке одного ресурса, определяя узлы с фиксированным количеством каждого ресурса (например, 4 ЦП, 32 МБ памяти и т. д.) и разделяя слоты , которые доли узлов. Но этот метод неэффективен, поскольку не всем пользователям требуется одинаковое соотношение ресурсов. Например, некоторым пользователям требуется больше процессора, тогда как другим пользователям требуется больше памяти. В результате большинство задач либо недостаточно, либо чрезмерно используют свои ресурсы.

DRF решает проблему, максимизируя минимальное количество доминирующего ресурса, предоставляемого пользователю (затем второй минимум и т. д., в порядке лексиминов ). Доминирующий ресурс может быть разным для разных пользователей. Например, если пользователь A выполняет задачи с интенсивным использованием ЦП, а пользователь B выполняет задачи с интенсивным использованием памяти, DRF попытается уравнять долю ЦП, предоставленную пользователю А, и долю памяти, предоставленную пользователю Б.

Определение

Имеется m ресурсов. Суммарные мощности ресурсов равны r ₁ ,..., r _m .

Имеется n пользователей. Каждый пользователь выполняет индивидуальные задачи . Каждая задача имеет вектор спроса ( d ₁ ,.., d _m ), представляющий необходимое ей количество каждого ресурса. Неявно предполагается, что полезность пользователя равна количеству задач, которые он может выполнить. Например, если пользователь А запускает задачи с вектором спроса [1 ЦП, 4 ГБ ОЗУ] и получает 3 ЦП и 8 ГБ ОЗУ, то его полезность равна 2, поскольку он может выполнять только 2 задачи. В более общем смысле полезность пользователя, получающего x ₁ ,..., x _m, ресурсы _{равна min j} ( x _j / d _j ), то есть у пользователей есть утилиты Леонтьева .

Векторы спроса нормированы на доли мощностей. Например, если система имеет 9 ЦП и 18 ГБ ОЗУ, то указанный выше вектор спроса нормализуется до [1/9 ЦП, 2/9 ГБ]. Для каждого пользователя ресурс с наибольшей долей спроса называется доминирующим ресурсом . В приведенном выше примере доминирующим ресурсом является память, поскольку 2/9 — это наибольшая доля. Если пользователь Б запускает задачу с вектором спроса [3 ЦП, 1 ГБ], который нормализуется до [1/3 ЦП, 1/18 ГБ], то его доминирующим ресурсом является ЦП.

Целью DRF является поиск такого максимального значения x, при котором все агенты смогут получить как минимум x своего доминирующего ресурса. В приведенном выше примере этот максимальный x равен 2/3:

Пользователь А получает 3 задачи, для которых требуется 3/9 ЦП и 2/3 ГБ.
Пользователь Б получает 2 задачи, для которых требуется 2/3 ЦП и 1/9 ГБ.

Максимальный x можно найти, решив линейную программу; см. Лексикографическая максим-минутная оптимизация . Альтернативно, DRF может быть вычислен последовательно. ^[1]^{: Алгоритм 1} Алгоритм отслеживает объем доминирующего ресурса, используемого каждым пользователем. В каждом раунде он находит пользователя с наименьшим на данный момент выделенным доминирующим ресурсом и назначает следующую задачу этому пользователю. Обратите внимание, что эта процедура позволяет одному и тому же пользователю запускать задачи с разными векторами спроса.

Характеристики

DRF имеет несколько преимуществ перед другими политиками распределения ресурсов.

Пропорциональность : каждый пользователь получает как минимум столько ресурсов, сколько он мог бы получить в системе, в которой все ресурсы распределяются поровну между пользователями (авторы называют это условие «стимулом разделения»).
Стратегическая устойчивость : пользователь не может получить больше ассигнований, лгая о своих потребностях. Устойчивость к стратегиям важна, поскольку данные операторов облачных вычислений показывают, что пользователи пытаются манипулировать серверами, чтобы получить лучшее распределение.
Отсутствие зависти : ни один пользователь не предпочел бы, чтобы его выделил другой пользователь.
Эффективность по Парето : никакое другое распределение не является лучшим для некоторых пользователей и не хуже ни для кого.
Монотонность популяции : когда пользователь покидает систему, распределения оставшихся пользователей не уменьшаются.

Когда есть один ресурс, который является узким местом (очень востребован всеми пользователями), DRF сводится к максимальной и минимальной справедливости .

Однако DRF нарушает монотонность ресурсов : при добавлении ресурсов в систему некоторые выделения могут уменьшиться.

Расширения

Взвешенный DRF — это расширение DRF для настроек, в которых разные пользователи имеют разные веса (представляющие их разные права ). ^[1]^: 4.3

Паркс, Прокачча и Шах ^[2] формально расширить взвешенный DRF до ситуации, в которой некоторым пользователям не нужны все ресурсы (то есть у них может быть требование 0 к некоторому ресурсу). Они доказывают, что расширенная версия по-прежнему удовлетворяет требованиям пропорциональности, эффективности по Парето, отсутствия зависти, устойчивости к стратегиям и даже устойчивости к групповым стратегиям . С другой стороны, они показывают, что DRF может привести к плохому утилитарному социальному благосостоянию, то есть сумма полезностей может составлять лишь 1/ m от оптимума. Однако они доказывают, что любой механизм, удовлетворяющий требованиям пропорциональности, отсутствия зависти или стратегической устойчивости, может страдать от такого же низкого утилитарного благосостояния. Они также расширяют DRF до условий, в которых требования пользователей неделимы (как при справедливом распределении товаров ). Для неделимой обстановки они ослабляют свободу от зависти до EF1. Они показывают, что устойчивость стратегии несовместима с PO+EF1 или с PO+пропорциональностью. Однако механизм SequentialMinMax обеспечивает эффективность, пропорциональность и EF1.

Ван, Ли и Лян ^[3] настоящий DRFH — расширение DRF на систему с несколькими разнородными серверами.

Выполнение

DRF был впервые реализован в Apache Mesos — диспетчере ресурсов кластера, и это привело к повышению пропускной способности и справедливости по сравнению с использовавшимися ранее схемами справедливого распределения.

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с «Справедливость доминирующих ресурсов: справедливое распределение нескольких типов ресурсов» . 2011.
^ Паркс, Дэвид К.; Прокачча, Ариэль Д.; Шах, Нисарг (27 марта 2015 г.). «За пределами доминирующей справедливости ресурсов: расширения, ограничения и неделимость» . Транзакции ACM по экономике и вычислениям . 3 (1): 3:1–3:22. дои : 10.1145/2739040 . ISSN 2167-8375 .
^ Ван, Вэй; Ли, Баочунь; Лян, Бен (2014). Доминирующая справедливость использования ресурсов в системах облачных вычислений с гетерогенными серверами . стр. 583–591. arXiv : 1308.0083 . дои : 10.1109/INFOCOM.2014.6847983 . ISBN 978-1-4799-3360-0 . Проверено 20 декабря 2023 г.

[:0-1] Перейти обратно: ^а ^б ^с «Справедливость доминирующих ресурсов: справедливое распределение нескольких типов ресурсов» . 2011.

[2] Паркс, Дэвид К.; Прокачча, Ариэль Д.; Шах, Нисарг (27 марта 2015 г.). «За пределами доминирующей справедливости ресурсов: расширения, ограничения и неделимость» . Транзакции ACM по экономике и вычислениям . 3 (1): 3:1–3:22. дои : 10.1145/2739040 . ISSN 2167-8375 .

[3] Ван, Вэй; Ли, Баочунь; Лян, Бен (2014). Доминирующая справедливость использования ресурсов в системах облачных вычислений с гетерогенными серверами . стр. 583–591. arXiv : 1308.0083 . дои : 10.1109/INFOCOM.2014.6847983 . ISBN 978-1-4799-3360-0 . Проверено 20 декабря 2023 г.

[1]

[2]

[3]