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

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

Мотивация

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

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

Определение

Имеется m ресурсов. Общие мощности ресурсов составляют r ₁ ,..., r _m .

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

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

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

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

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

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

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

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

Когда есть один ресурс, который является узким местом (высоко востребован всеми пользователями), 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 — менеджере кластерных ресурсов — и обеспечил лучшую пропускную способность и справедливость по сравнению с ранее использовавшимися схемами справедливого распределения.

Смотрите также

Ссылки

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

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

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

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