Подскажите, пожалуйста, может быть есть какой-то общеизвестный алгоритм, который решает мою задачу, которая, как мне кажется, вполне распространенная. И тогда мне не нужно будет изобретать велосипед :)
Задача следующая: равномерное распределение нагрузки с минимизацией ребалансировок.
Дано:
- N серверов. Мощность каждого S.
- Пул процессов, которые должны быть запущены на серверах. Каждый процесс требует P[i] ресурсов сервера. Процесс не может быть разделен на несколько серверов. Процесс по сути бесконечен. Это не задача, которая камотает какой-то время и завершается. Процесс работает и потребляет ресурсы бесконечно долго.
- Сумма P[i] сильно меньше N*S (имеется достаточное количество ресурсов для запуска всех процессов). Каждый P[i] < S (сервара достаточно мощные, что любой процесс может быть запущен).
Требуется распределить процессы между серверами, так чтобы перекос был как можно меньше: Отнощение (Максимальная загруженность)/(минимальная загруженность) стремилось к единице.
Это начальное распределение. Но P[i] может меняться (как увеличиваться, так и уменьшаться). Что будет приводить к разбалансировке. Новые процессы могут появляться, а старые исчезать. Что тоже нарушает балансировку.
Требуется разработать алгоритм ребалансировки, который поддерживает равномерную нагрузку, но при этом минимизирует количество перемещений процессов между серверами. Ребалансировка может происходить, например, раз в час. Т.е. нет необходимости ребалансировать в реальном времени. Между ребалансировками новые процессы могут просто добавляться на наименее загруженный сервер.
Систему можно не трогать если коэффициент разбалансировки меньше какого-то порогового значения, например 1.2. Коэффициент разбалансировки можно определить как (два разных подхода):
- Отношение максимальной и минимальной нагрузки.
- Максимум из отношений (максимальная загруженность)/(средняя зашруженость) и (средняя загруженность) / (минимальная загруженность).
Раз в час проверяется текущий коэффициент разбалансировки и, если требуется, то запускается ребалансировка.
У меня конечно есть мысли, как подойти к решению. Но тогда мой алгоритм потребует доказательств корректности. Например, что он не приведет к постоянной миграции какого-нибудь процесса между серверами. И у меня есть стойкое ощущение, что задача вполне распространенная и имеются общеизвестные алгоритмы для её решения.
Средний
Простой
Сложный
