什么是实现循环队列的排队机制? [英] What are some queuing mechanisms for implementing round-robin queues?

问题描述

我有多个任务生产者，它们将工作添加到队列中.我也有多个消耗该队列的使用者.由于这些队列是FIFO，因此以添加队列的相同顺序出队.

I have multiple task producers that add work to a queue. I also have multiple consumers that feed off that queue. Since these queues are FIFO, they are dequeued in the same order they were added.

在我的场景中，任务从HTTP请求添加到队列中.每个任务都与一个帐户关联，并且没有速率限制.因此，有可能使一个帐户中的任务泛滥到消息队列中.

In my scenario, tasks are added to the queue from HTTP requests. Each task is associated with an account and there is no rate-limiting. Therefore it is possible to have tasks from one account flood the message queue.

为了解决这个问题，我一直在寻找一个队列实现，该队列实现允许我以循环方式从多个帐户处理排队的任务，以保持公平.

In order to solve this, I've been looking for a queue implementation which allows me process enqueued tasks from multiple accounts in round-robin fashion for fairness.

我目前一直在使用Redis和一些Lua脚本来模拟循环队列，但是想知道是否有任何现有的队列拓扑来实现这一目标?

I've currently resorted to using Redis with some Lua scripts thrown in to emulate a round robin queue but was wondering if there are any existing queueing topologies that accomplish this?

推荐答案

我通常这样做:

• 不要将任务直接放入工作队列中，而是为每个帐户创建一个单独的任务队列.每个请求都会将一个任务放入其帐户队列中，并且当帐户队列从空变为非空时，将帐户队列放入全局工作队列

当工作人员准备进行更多工作时，他们将从工作队列中获取帐户队列.当工作人员获取帐户队列时，它会执行第一个任务，并且该工作人员立即将帐户队列放回工作队列的末尾(如果它不为空).然后工人执行任务.

Workers take account queues from the work queue when they are ready for more work. When a worker takes an account queue, it takes out the first task and the worker immediately puts the account queue back at the end of the work queue if it's not empty. Then the worker performs the task.

使用此系统，每个帐户队列最多只能在工作队列中一次，并且所有与相关工作相关的帐户都在工作队列中均等地表示.

Using this system, each account queue is in the work queue at most once, and all accounts with associated work are equally represented in the work queue.

这很容易实现，但是您必须小心检测何时必须将帐户队列放入工作队列，因为可以有两个线程同时做出此决定，而您不会不想让帐户队列进入两次.

This is pretty easy to implement, but you do have to be careful about detecting when you have to put an account queue into the work queue, since there can be two threads making this decision at the same time, and you don't want the account queue to go in twice.

我这样简单:

• 每个帐户队列中都有一个原子布尔值，用于跟踪它是否在工作队列中.工作人员在出队帐户队列后立即将其设置为false.如果有人发现帐户队列为非空，则可以尝试将此布尔值CAS设置为true，如果成功，则将帐户队列放入工作队列.

• Have an atomic Boolean in each account queue that keeps track of whether or not it's in the work queue. The worker sets this to false immediately after dequeing the account queue. If anyone finds the account queue non-empty, they can try to CAS this boolean to true, and if successful put the account queue into the work queue.

帐户队列为空时，很有可能进入工作队列.确保这是无害的-如果工作人员未能从帐户队列中执行任务，则应该忘掉它，然后从工作队列中获取新的帐户队列.

There's a small chance that an account queue could get into the work queue when it's empty. Make sure this is harmless -- if a worker fails to take a task from an account queue, it should just forget about it and take a new account queue from the work queue.

这篇关于什么是实现循环队列的排队机制?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！