时间戳

首页 > 解决方案 > 使用公平槽策略从队列中获取下一个任务

php - 使用公平槽策略从队列中获取下一个任务

问题描述

在我们的服务中，用户可以添加不同的任务，这些任务会在插槽可用时立即执行。
所有任务都存储在一个 mysql 表中。桌子看起来像

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

我们目前正在使用先进先出策略，但由于任务数量正在增加，并且我们不想限制用户可以添加多少任务，我们希望为其添加公平槽策略。通常，任务在完成前运行 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

我的方法是
-first：将每个用户的待处理任务数除以待处理任务总数（pending_tasks_of_user_x / pending_tasks）。
-second：然后将活动任务划分为可以同时运行的任务数量（active_tasks_of_user_x / concurrent_tasks）。

但现在我不知道如何进行。如果我的方法完全错误，我愿意接受。

要访问数据库，我正在使用 php。

编辑：

公平地说，我定义用户不必等待，直到其他用户的所有其他任务完成。例如，用户 2 有 76 个任务，用户 1 有 28 个任务。现在用户 5 添加了 3 个任务。我不希望用户 5 必须等到必须先执行用户 1 和 2 的所有任务才能执行用户 5 的任务。更像是用户 2 可以同时运行 8 个任务，用户 1 4 和用户 5 可以运行 2，或者类似的东西。如果可用的用户多于并发任务，则它应该相应地缩小，并且一些必须等待。

标签： phpmysqlmathtask

解决方案

我认为 公平共享调度在这种情况下是一个很好的方法。

将可用任务槽的总数除以具有待处理任务的用户总数。

15 / 5 = 3

所以每个用户现在可以一次运行 3 个任务。

这意味着任务少的用户会很快完成，而任务多的用户则需要等待更长的时间。

如果另一个用户出现，可用的任务将是

15 / 6 = 2.5

当然你不能运行一半的任务，但这可以在实际的排队算法中解决。

我认为您可以在 PHP 中实现这一点。我不认为这是我为你编写代码的地方。

算法应该是这样的：

  1. 任务槽是免费的，正在寻找要执行的新任务。
  2. 找到运行任务最少的用户。
  3. 查找该用户最早的待处理任务。
  4. 如果用户没有任何待处理的任务，请从考虑中删除该用户并从第 2 点重新开始。
  5. 运行挂起的任务。

这就是实现这一点所需要做的一切。

推荐阅读