Получить следующую задачу из очереди, используя честную политику слотов - PullRequest
Новая
       18

Получить следующую задачу из очереди, используя честную политику слотов

0 голосов
/ 12 апреля 2019

На нашем сервисе пользователи могут добавлять различные задачи, которые выполняются, как только слот становится доступным.
Все задачи хранятся в таблице mysql.Таблица выглядит так: 

user_id | task   | status         | created_at | started_at 
int     | string | pending,active | datetime   | datetime

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

Я создал набор образцов данных:

Пример данных: 

158 total tasks
144 pending tasks 
 14 running tasks
 15 tasks can run at the same time

 # of pending tasks for each user    
 user 1 => 28 tasks
 user 2 => 76 tasks
 user 3 =>  5 tasks 
 user 4 => 22 tasks
 user 5 =>  3 tasks

 # of active tasks for each user
 user 1 =>  5 tasks
 user 2 =>  0 tasks
 user 3 =>  2 tasks 
 user 4 =>  4 tasks
 user 5 =>  3 tasks

Мой подход заключается в
-первом: разделите количество ожидающих задач для каждогопользователя по количеству ожидающих выполнения задач (pending_tasks_of_user_x / pending_tasks).
-секунда: затем разделите активные задачи на количество задач, которые могут выполняться одновременно (active_tasks_of_user_x / concurrent_tasks).

Нотеперь я не знаю, как поступить.Если мой подход совершенно неверен, я открыт для него.

Для доступа к базе данных я использую php.

РЕДАКТИРОВАТЬ:

Как честно, я определяю, чтоПользователь не должен ждать, пока все другие задачи других пользователей не будут выполнены.Например, у пользователя 2 есть 76 задач, а у пользователя 1 - 28 задач.Теперь пользователь 5 добавляет 3 задачи.Я не хочу, чтобы пользователь 5 ждал, пока все задачи пользователя 1 и 2 должны быть выполнены в первую очередь, прежде чем задачи пользователя 5 будут выполнены.Более того, как пользователь 2 может запускать 8 задач одновременно, пользователь 1 4 и пользователь 5 могут запускать 2 или что-то подобноеЕсли доступно больше пользователей, чем одновременных задач, оно должно соответственно уменьшиться, а некоторым придется подождать.

1 Ответ

1 голос
/ 12 апреля 2019

Я думаю, что Планирование справедливого распределения является хорошим подходом в этом случае.

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

15/5 = 3

Таким образом, каждый пользователь теперь может запускать 3 задачи одновременно.

Это означает, что пользователи с небольшим количеством задач будут выполнены быстро, и пользователям с большим количеством задач придется ждать дольше.

Если появится другой пользователь, доступные задачи будут

15/6 = 2,5

Конечно, вы не можете выполнить половину задачи, но это может быть решено в реальном алгоритме очередей.

Я думаю, вы могли бы реализовать это на PHP. Я не думаю, что это мое место, чтобы кодировать это для вас.

Алгоритм должен быть примерно таким:

  1. Слот задач освобождается и ищет новую задачу для выполнения.
  2. Найдите пользователя с наименьшим количеством запущенных задач.
  3. Найдите самое старое ожидающее задание этого пользователя.
  4. Если у пользователя нет отложенных задач, удалите его из рассмотрения и начните снова с пункта 2.
  5. Запустить отложенное задание.

Это все, что вам нужно сделать, чтобы реализовать это.

...