Kubernetes и моделирование на minizinc

Эта статья, скорее даже не статья, а заметка, и цель ее — подсветить саму идею полезности построения моделей, которые можно использовать в процессе принятия решений, при проектировании IT инфаструктур, да и в целом любых систем. Ну и, конечно, еще раз показать сам инструмент, и подход к мышлению, необходимый при использовании этого инструмента.

Minizinc

На самом деле об инструменте minizinc уже упоминалось на хабре:

• Constraint Programming или как решить задачу коммивояжёра, просто описав её / Хабр (habr.com)

• Задачи планирования и программирование в ограничениях / Блог компании Nexign / Хабр (habr.com)

По этому я всего лишь в двух словах напомню. Minizinc — это «constraint modeling language». По сути язык, позволяющий, в некотором смысле, декларативно описать проблему, и попросить систему решить ее за вас. Говоря проще, язык предоставляет возможность написать что-то вроде следующего:

# рыночек яблоки: стоят 13, утоляют голод на 2 часа, у нас их 1000 порций гречка: стоит 21, утоляет голод на 4 часа, у нас ее 400 порций хлеб: стоит 17, утоляет голод на 6 часов, у нас его 500 порций мясо: стоит 100, утоляет голод на 9 часов, у нас его 150 порций  # у нас есть бюджет = 10000  # покупаем продукты ограничение: цена яблок*количество + цена гречки*количество +  цена хлеба*количество + цена мяса*количество <= бюджет  найти: сколько и чего мы можем купить в рамках ограничений,   максимизировать время, на которое утоляется голод

Как видите, тут нет ответа на вопрос «как решать». Мы декларативно описываем входные данные, ограничения, которые у нас есть, цель, которую мы хотим достичь. Затем мы просим систему попытаться найти решение задачи.

Что можно с этим делать

Довольно часто, при проектировании инфраструктуры под Kubernetes (AKS) в Microsoft Azure, у заказчиков возникают странные вопросы, типа: какого размера будет все это добро, или, сколько все это будет нам стоит? Для того чтобы хоть как-то ответить на этот вопрос надо предположить какого размера виртуальные машины выбрать, сколько их должно быть, сколько они стоят в нужном регионе. Размер машин, в свою очередь, зависит от количества и прожорливости приложений, а так же от количества экземпляров каждого из них. И так далее. А ведь нам хочется еще и подобрать все это по минимальной цене. В общем и целом, входных переменных довольно много и свести их в кучу, да еще и для каждого размера виртуальных машин отдельно, скажем прямо — не самая интересная работа в мире.

Давайте попробуем с одной стороны немного упростить себе жизнь, а с другой стороны пощупаем моделирование в minizinc.

Общие соображения по ограничениям

Начнем с виртуальных машин. Первое и, наверное, самое важное — ресурсов машины, должно хватить на все запущенные экземпляры приложения. Другими словами, в сумме, приложения должны сожрать меньше, чем доступно на ноде. Кроме того, здесь стоит учесть нагрузку, которую создает сам Kubernetes. Для этого имеет смысл зарезервировать некий процент ресурсов, и не отдавать его приложениям. С другой стороны, чтобы ресурсы не простаивали, нужно иметь некую нижнюю планку потребления ресурсов. Так же, было бы хорошо, чтобы суммарно, все приложения влезали в кластер, а для этого модель должна определять необходимое количество нод, держа в уме нагрузку на приложения.

Переходим к приложениям. Положим, каждое приложение должно исполняться как минимум в 2х экземплярах, на случай отказа одного из них. При этом, эти экземпляры должны исполняться на разных нодах, по той же причине. Плюс к этому, было бы очень неплохо, если бы модель умела оценить количество нод, в зависимости от предполагаемой нагрузки на приложение.

Начнём, пожалуй

Обычно, модель состоит из нескольких кусков: объектов, учавствующих в модели, ограничений (constraints), описания решений, которые она должна найти, целевой функции, к которой мы стараемся стремиться. Целевой функции может не быть. тогда модель просто выдаст все «решения», которые она приняла

Начнем с описания приложений. Мы хотим запускать в кластере некое, заранее известное количество приложений, с известными максимальными значениями потребления ресурсов. Все эти значения — переменные, что дает нам возможность настраивать модель и менять ее поведение. Для моделирования «сложных» объектов в minizinc применяется следующий трюк. Задается некий ENUM тип, который используется как индекс в массивах со значениями атрибутов

enum appNames = {A, B, C, D, E}; array[appNames] of int: appRAM = [2,4,6,8,4]; array[appNames] of int: appCPU = [200,400,400,450,2250]; array[appNames] of int: appConnectionsPerInstance = [5,2,2, 2,2]; array[appNames] of int: appConnectionsFact = [20,4,3,4,10];

B данном случае, enum appnames задает список приложений. И затем, каждому приложению из списка ставится в соотвествие набор атрибутов: максимальный объем потребления RAM, CPU, некий коэффициент нагрузки на экземпляр, и предполагаемая нагрузка на каждый экземпляр, измеренная в тех же единицах.

Хорошо, с приложениями разобрались, теперь ноды кластера. Там, собственно, ровно то же самое. Нам нужно смоделировать объект ноды с его атрибутами, поэтому

enum nodeKinds = {D2sv5, D4sv5, D8sv5};  array[nodeKinds] of int: clusterNodeRAM = [8,16,32]; array[nodeKinds] of int: clusterNodeCPU = [2000,4000,8000]; array[nodeKinds] of float: clusterNodePrice = [0.048, 0.096, 0.192];

Тут я использую имена размеров виртуальных машин Microsoft Azure, их стоимость и параметры. Но в целом, все ровно то же самое, что и с приложениями.

Стоит сделать отступление и упомянуть, что в minizinc есть два типа «переменных»: обычные переменные, к которым мы все привыкли, и «decision variables». Последние представляют «решения», которые minizinc должен принять, чтобы требования и органичения модели были соблюдены. Иными словами, занчения обычных переменных мы должны задать вручную, а значения «decision variables» minizinc должен найти сам. До сих пор мы использовали только обычные переменные

Итак, с объектами модели определились, пришло время ограничений и «decision variables».

Прежде всего мы хотим описать сам кластер, который, как водится, состоит из одной или нескольких нод. Сделаем это примерно вот так

int: maxClusterSize = 6; set of int: CLUSTER = 1..maxClusterSize;

Теперь начинается самое интересное. На каждой ноде этого кластера мы хотим запусить одно или несколько приложений. Смоделируем это как некую матрицу, в которой измерениями будут ноды кластера и имена приложений, а значениями флажки, запущено приложение или нет. Что-то вроде этого.

Сделать это можно примерно вот так. Тут каждой ноде кластера CLUSTER мы ставим в соответствие список приложений, которые на ней исполняются. На пересечении стоит флаг, который говорит запущен на этой ноде экземпляр этого приложения или нет. Такая схема, в дополнение ко всему, косвенно гарантирует, что на каждой ноде может исполняться только один экземпляр каждого приложения. Другими словами если нам понадобится запусить два экземпляра приложения А, они гарантированно попадут на разные ноды.

array[CLUSTER, appNames] of var bool: runningApps;

Обратите внимание на слово var в этой строке. Это индикатор «decision variable». По сути эта строка говорит, что мы создаем массив, индексами которого являются ноды кластера и приложения, а значениями «decision variables». Это значает что minizinc должен будет принять решения по каждой из этих переменных, решив, как распределить приложения по нодам кластера.

Отлично, переходим к ограничениям (constraints). Для кажой ноды кластера мы должны определить такие условия, чтобы все запущенные экземпляры приложени влезали на ноду, и учесть зарезервированный объем ресурсов. Попробуем для начала с RAM

constraint forall (i in CLUSTER) (    sum(j in appNames) (runningApps[i,j] * appRAM[j]) >=    (clusterNodeRAM[???] * minNodeRAMConsumption) /\   sum(j in appNames) (runningApps[i,j] * appRAM[j]) <=    (clusterNodeRAM[???] * maxNodeRAMConsumption) );

Однако тут возникает несколько проблем, они помечены ???? поскольку он задан как множество с элементами типа int. Итерируя по CLUSTER, мы бежим по елементам типа int, а из них нельзя достать атрибутов ноды. Вторая проблема это выражение sum(j in appNames) (runningApps[i,j] * appRAM[j]) которое малость сбивает с толку, да еще и используется дважды.

Для того чтобы побороть первую проблему, введем еще один индекс, который свяжет CLUSTER и nodeKind. Это даст нам возможность по номеру ноды доставать ее атрибуты. Вторая проблема решается добавлением еще одного массива «decision variables». Тут мы позволим minizinc самому решить, каким будет потребление, но мы жестко ограничим его, потребовав равенства с суммой потребления RAM всеми приложениями ноды. И это решение можно затем использовать для сравнения. Выходит примерно вот так

% индекс по нодам кластера array[CLUSTER] of var nodeKinds: nodes;  % дополнительный массив decision variable, % хранящий потребление ресурсов приложениями на ноде array[CLUSTER] of var int: nodeRAMConsumption;  % ну и собсно само ограничение, требующее чтобы значение в массиве % совпадало с суммой потребления ресурсов constraint forall (i in CLUSTER) (    nodeRAMConsumption[i] =   sum(j in appNames) (runningApps[i,j] * appRAM[j]) );  % в этом случае ограничение по RAM упрощается constraint forall (i in CLUSTER) (    nodeRAMConsumption[i] >= (clusterNodeRAM[nodes[i]] * minNodeRAMConsumption) /\   nodeRAMConsumption[i] <= (clusterNodeRAM[nodes[i]] * maxNodeRAMConsumption) );

Кроме того, в рамках этого ограничения мы добавляем требования нижней и верхней границы потребления используя знак конъюнкции /\

Ну а поскольку CPU и RAM это примерно про одно и то же, то ограничения для него выглядят идентично

array[CLUSTER] of var int: nodeCPUConsumption; constraint forall (i in CLUSTER) (    nodeCPUConsumption[i] =   sum(j in appNames) (runningApps[i,j] * appCPU[j]) );  constraint forall (i in CLUSTER) (    nodeCPUConsumption[i] >= (clusterNodeCPU[nodes[i]] * minNodeCPUConsumption) /\   nodeCPUConsumption[i] <= (clusterNodeCPU[nodes[i]] * maxNodeCPUConsumption) );

Итак, к этому моменту мы определили объекты application и потребовали от модели распределить их по node так, чтобы они влезали в каждую node . При этом учитывается требование к плотности и остается резерв на потребление самого кластера. Остался сущий пустяк, мы хотим, чтобы модель учитывала нагрузку на приложения. У нас есть максимальная нагрука на экземпляр, после которой необходимо добавить еще один —appConnectionsPerInstance, и текущая фактическая нагрузка — appConnectionsFact.На основе этих значений мы можем потребовать, чтобы модель посчитала количество экземпляров каждого приложения. И затем потребовать, чтобы суммарное количество экземпляров приложения в кластере совпадало с рассчетным.

% для каждого приложения нужна decision variable, в которой % minizinc определит нужное количество экземпляров  array[appNames] of var int: appInstanceCount;  % потребуем, чтобы количество нужных экземпляров совпадало % c отношением фактической накрузки к базовой  % округленное вверх до ближайшего целого constraint forall (j in appNames)(   appInstanceCount[j] = ceil(appConnectionsFact[j]/appConnectionsPerInstance[j]) );  % потребуем, чтобы количество приложений совпадало с решением % о количестве экземпляров, принятым выше constraint forall (j in appNames) (    sum(i in CLUSTER) (runningApps[i,j]) = appInstanceCount[j] );

Ну и наконец, целевая функция и требование к ее оптимизации. Сумма цен по всем нодам должна быть минимальной.

var float: cost =  (sum(i in nodes)(clusterNodePrice[i])) * 24 * 30 ; % target function to optimize solve minimize cost;

Ну, вот вроде и все рассуждения. Осталось только задать нужные значения, и оформить немного

include "all_equal.mzn";  % config section int: maxClusterSize = 6; float: minNodeRAMConsumption = 0.5; float: maxNodeRAMConsumption = 0.8; float: minNodeCPUConsumption = 0.1; float: maxNodeCPUConsumption = 0.8; % end config  % applications and their attributes enum appNames = {A, B, C, D, E}; array[appNames] of int: appRAM = [2,4,6,8,4]; array[appNames] of int: appCPU = [200,400,400,450,2250]; array[appNames] of int: appConnectionsPerInstance = [5,2,2, 2,2]; array[appNames] of int: appConnectionsFact = [4*5,2*2,3*2,2*2, 5*2];  % cluster nodes and their attributes enum nodeKinds = {D2sv5, D4sv5, D8sv5};  array[nodeKinds] of int: clusterNodeRAM = [8,16,32]; array[nodeKinds] of int: clusterNodeCPU = [2000,4000,8000]; array[nodeKinds] of float: clusterNodePrice = [0.048, 0.096, 0.192];  % CLUSTER node index set of int: CLUSTER = 1..maxClusterSize;  array[CLUSTER, appNames] of var bool: runningApps; % apps running on a node array[CLUSTER] of var nodeKinds: nodes;   % CONSTRAINTS % all nodes are of equal size constraint all_equal(nodes);  % assuming the load, calculate target number of pods array[appNames] of var int: appInstanceCount; constraint forall (j in appNames)(   appInstanceCount[j] = ceil(appConnectionsFact[j]/appConnectionsPerInstance[j]) );  % assuming the load, use calculated number of pods constraint forall (j in appNames) (    sum(i in CLUSTER) (runningApps[i,j]) = appInstanceCount[j] );  % supporting constraint to calculate and store RAM consumption array[CLUSTER] of var int: nodeRAMConsumption; constraint forall (i in CLUSTER) (    nodeRAMConsumption[i] =   sum(j in appNames) (runningApps[i,j] * appRAM[j]) );  % sum of RAM of all apps on the node >=minNodeRAMConsumption and <= maxNodeRAMConsumption of total node RAM constraint forall (i in CLUSTER) (    nodeRAMConsumption[i] >= (clusterNodeRAM[nodes[i]] * minNodeRAMConsumption) /\   nodeRAMConsumption[i] <= (clusterNodeRAM[nodes[i]] * maxNodeRAMConsumption) );  % supporting constraint to calculate and store CPU consumption array[CLUSTER] of var int: nodeCPUConsumption; constraint forall (i in CLUSTER) (    nodeCPUConsumption[i] =   sum(j in appNames) (runningApps[i,j] * appCPU[j]) );  % sum of CPU of all apps on the node >= minNodeCPUConsumption and <= maxNodeCPUConsumption of total node CPU constraint forall (i in CLUSTER) (    nodeCPUConsumption[i] >= (clusterNodeCPU[nodes[i]] * minNodeCPUConsumption) /\   nodeCPUConsumption[i] <= (clusterNodeCPU[nodes[i]] * maxNodeCPUConsumption) );  var float: cost =  (sum(i in nodes)(clusterNodePrice[i])) * 24 * 30 ; % target function to optimize solve minimize cost;  output [ if j = A then "\(nodes[i]); CPU:\(nodeCPUConsumption[i])/\(clusterNodeCPU[nodes[i]]); RAM:\(nodeRAMConsumption[i])/\(clusterNodeRAM[nodes[i]]), " else "" endif ++           if fix(runningApps[i,j]) = 1 then show(fix(appNames[j])) ++ ";" else "" endif ++           if j = E then "\n" else "" endif          | i in CLUSTER, j in appNames ];

Я намеренно опускаю секцию output поскольку, к сожалению, minizinc плохо это умеет. В конечном итоге на выходе с саданными параметрами мы получам следующее

D4sv5; CPU:2700/4000; RAM:12/16, D;E; D4sv5; CPU:2850/4000; RAM:10/16, A;B;E; D4sv5; CPU:2850/4000; RAM:12/16, A;C;E; D4sv5; CPU:2850/4000; RAM:12/16, A;C;E; D4sv5; CPU:2700/4000; RAM:12/16, D;E; D4sv5; CPU:1000/4000; RAM:12/16, A;B;C; ---------- ==========

Это означает, что наша модель решила, что все ноды должны быть рамера D4sv5. Кроме того для проверки выводится потребление CPU и RАМ приложениями на ноде против количества доступных CPU и RAM. ну и наконец расположения приложений по нодам. Строка ========== в выводе, это специальный индикатор, который говорит о том, что для заданных параметров minizinc считает это решение оптимальным.

В заключении хочу отметить что это не единственный тип задач, который можно моделировать с применением minizinc. Есть два отличных курса, которые можно порекомендовать: Basic Modeling for Discrete Optimization | Coursera, Advanced Modeling for Discrete Optimization | Coursera. А если хочется больше матана — Discrete Optimization | Coursera.

Удачного моделирования и оптимизации!