Как правильно распределить задачи в зависимости от нагрузки?

Question

[iBird Rose]

Здравствуйте. В двух словах есть массив (пусть 1000 элементов) и в нем группы и их статистика по нагрузке в % соотношении:
group_id1 - 0.2%
group_id2 - 5%
group_id3 - 61%
...
group_id1000 - 3%

т.е. в общем сумма % всех 1000 элементов будет 100

Задача распределять по нагрузке эти 1000 групп на 30 серверов. Т.е. по сути задача распределить эти 1000 групп в массив из 30 элементов.
Пока даже идей нет как подойти к задаче. Есть идеи?)

UPD: есть группы нагрузка которых порой равна 60% от общей. значит их обработку нужно в этот момент вынести на отдельный сервер. соответственно тупо раскидать - не получится.
UPD 2: так же есть группы, которые вообще ничего не потребляют по сути, а значит можно огромную кучу вынести на 1 сервер. и пусть они там отдыхают

Answer 1

[longclaps]

Ты не поверишь.
Если задачи просто случайно раскидывать по серверам - в среднем максимальная нагрузка на сервер не превысит 5% от общей.
Вот пруф.

from random import random, randint

N, M = 1000, 30
tasks = [random() for _ in range(N)]
w = sum(tasks)
for i in range(N):
    tasks[i] /= w
servers = [0.] * M
for t in tasks:
    servers[randint(0, M - 1)] += t
print(min(servers), max(servers))

Comments

[iBird Rose]

есть группы нагрузка которых порой равна 60% от общей. значит их обработку нужно в этот момент вынести на отдельный сервер. соответственно тупо раскидать - не получится

[longclaps]

group_id1 - 0.2%
group_id2 - 5%
group_id3 - 1%
...
group_id100 - 3%

iBird Rose, обманул )
Ну да ничего. Берешь все задачи с весом больше/равно 5% (таких не более 20) и раскидываешь их по выделенным серверам. Остальные задачи - случайным образом по оставшимся серверам.

[Ильдар Гизетдинов]

longclaps, на самом деле неплохой вариант, вместо усложнения, можно примерные рамки в коде задать)

Answer 2

[⚡ Kotobotov ⚡]

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

Comments

[iBird Rose]

есть группы нагрузка которых порой равна 60% от общей. значит их обработку нужно в этот момент вынести на отдельный сервер. соответственно тупо раскидать - не получится

[⚡ Kotobotov ⚡]

если вам не известны никаких свойства данных, у вас все равно нет никаких вариантов предсказывать нагрузку.
такие моменты решаются тем, что данные нарезаются на еще более мелкие блоки.
например вместо 60% блока будут 10 блоков по 6%
и просто больше количество блоков будет раскидано

Answer 3

[d'Ivan]

Я предполагаю, что это задача об очередях сообщений (MQ). В смысле, что имея множество задач, их можно ставить в очередь(и). Так, множество обработчиков очереди (worker) будут брать задачи из очереди и обрабатывать их. Обработав задачу, берут следующую. И так со множества серверов. При этом общая нагрузка между серверами должна быть равномерной. Как я понимаю, ⚡ Kotobotov ⚡ имел в виду этот сценарий.