Как вычисляется fair share ratio

Имеется дерево пулов, внутренние узлы которого являются пулами, а листья — операциями.

У каждой операции в дереве пулов имеются usage и demand — векторы ресурсов, задающие текущее потребление операцией ресурсов и максимально возможное потребление ресурсов. Данные характеристики (usage и demand) суммируются естественным образом по дереву и таким образом можно говорить о usage и demand внутренних узлов дерева. Кроме того, вектор ресурсов можно превратить в неотрицательное число, взяв отношение доминантного ресурса этого вектора к суммарному количеству данного ресурса на кластере. Таким образом, можно говорить о usage ratio и demand ratio в каждом узле дерева.

При вычислении fair share ratio для всех узлов дерева рекурсивно выполняется процедура деления fair share в данном узле между его детьми. В корне деление начинается с fair share, равного единице.

При раздаче fair share детям решается следующая задача. Пусть F — это величина fair share, которую необходимо раздать детям c_1, c_2, ... c_n. Вес детей обозначен w_1, w_2, ... w_n . Также у детей имеется верхнее ограничение на fair share, обозначаемое u_i. Данное ограничение вычисляется с учетом demand, гранулярности ресурсов, установленных resource limits и так далее. Нижнее ограничение на fair share обозначается l_i (задается min share ratio). Алгоритм, который делит fair share, ищет такой x, чтобы было выполнено:

Если у детей пула сумма min share ratio превышает единицу, она нормируется до 1. В общем случае, min share ratio сложная характеристика и её не рекомендуется выставлять у вложенных пулов. Иначе описанная выше задача не имела бы решения.

Несколько примеров вычисления fair share ratio:

Пусть в корне имеется два пула A и B, у пула A min share ratio равен 0.6, у пула B min share ratio равен 0.2. Пусть также в обоих пулах запущены объёмные операции с очень большим demand.

1. Вес у обоих пулов равен единице. В таком случае после вычисления fair share получится, что fair share ratio пула A равен 0.6, а fair share ratio пула B равен 0.4;
2. Вес пула A равен трём, а вес пула B равен единице. Тогда fair share ratio пула A будет равен 0.75, а fair share ratio пула B равен 0.25;
3. Вес у обоих пулов равен единице. Предположим, что помимо A и B имеется пул C, у которого нет min share ratio, а вес также равен 1. Тогда fair share ratio пула A будет равен 0.6, а fair share ratio пула B равен 0.2, и fair share ratio пула C также будет равен 0.2.