algorithm - 将工作分配给节点而不对生产者不公平的公平算法

Question

我遇到了以下问题，我正在寻找一些想法。

我有 N 个工作生产者和 M 个消费者。 N个生产者生产工作并将其放入Q个消息队列，由消费者监控。

所以我们有

N    ->         -> M       In this example N producers put work in a round robin 
N    ->    Q    -> M       fashion to Q queues which are monitored for new work
N    ->         -> M       in a round robin fashion from M consumers
N    ->    Q    -> M
N    ->         -> M
N    ->    Q    -> M
N    ->         -> M
                -> M
                -> M

假设以下示例:

N1 有 100 个工作项要生产 N2 有 1 个工作项目要生产 N3 有 1 个工作项要生产

假设有Q1和Q2

N1 将 100 个工作项推送到 Q1 N2 将 1 个工作项推送到 Q2 N3 将 1 个工作项推送到 Q1(导致其循环)

N3 将等待 N1 的所有工作完成。

我正在寻找一种方法，以更加公平公正的方式在 N 和 M 之间分配工作。

谢谢

Answer 1

实现此目的的一种方法是更改​​您的队列，使它们不再是项目队列，而是生产者记录队列，每个生产者记录队列都包含一个项目队列。所以如果你有 N 个生产者，每个队列最多有 N 个条目。每个条目都包含来自该生产者的作业列表(队列)。

然后，消费者从队列中取出生产者记录，从生产者记录中删除该生产者的下一个作业，然后将生产者添加回队列。消费者然后继续处理该作业。如果消费者从生产者记录中删除了最后一个作业，则不要将生产者添加回队列。它将在下次生产者排队作业时重新创建。

我前段时间做了一个与网络爬虫项目非常相似的事情。效果非常好。