Labutin
@Labutin
Web-разработчик

Какой можно выбрать алгоритм балансировки нагрузки с минимизацией ребалансировок?

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

Требуется распределить процессы между серверами, так чтобы перекос был как можно меньше: Отнощение (Максимальная загруженность)/(минимальная загруженность) стремилось к единице.

Это начальное распределение. Но P[i] может меняться (как увеличиваться, так и уменьшаться). Что будет приводить к разбалансировке. Новые процессы могут появляться, а старые исчезать. Что тоже нарушает балансировку.

Требуется разработать алгоритм ребалансировки, который поддерживает равномерную нагрузку, но при этом минимизирует количество перемещений процессов между серверами. Ребалансировка может происходить, например, раз в час. Т.е. нет необходимости ребалансировать в реальном времени. Между ребалансировками новые процессы могут просто добавляться на наименее загруженный сервер.
Систему можно не трогать если коэффициент разбалансировки меньше какого-то порогового значения, например 1.2. Коэффициент разбалансировки можно определить как (два разных подхода):
- Отношение максимальной и минимальной нагрузки.
- Максимум из отношений (максимальная загруженность)/(средняя зашруженость) и (средняя загруженность) / (минимальная загруженность).
Раз в час проверяется текущий коэффициент разбалансировки и, если требуется, то запускается ребалансировка.

У меня конечно есть мысли, как подойти к решению. Но тогда мой алгоритм потребует доказательств корректности. Например, что он не приведет к постоянной миграции какого-нибудь процесса между серверами. И у меня есть стойкое ощущение, что задача вполне распространенная и имеются общеизвестные алгоритмы для её решения.
  • Вопрос задан
  • 174 просмотра
Пригласить эксперта
Ответы на вопрос 1
vabka
@vabka
Токсичный шарпист
Думаю, вам будет интересна эта статья, где решается похожая задача:
Yandex Planner. Как планировать вычислительные мощности
И доклад:
Дефрагментация вычислительных ресурсов кластера

Ещё можно посмотреть, как работает шедулер в k8s:
https://habr.com/ru/companies/flant/articles/335552/
https://kubernetes.io/docs/concepts/scheduling-evi...
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы