java - What are some queuing mechanisms for implementing round-robin queues?

Question

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.

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.

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?

Answer 1

I usually do it like this:

• Instead of putting tasks directly into the work queue, make a separate task queue for each account. Each request puts a task into its account queue, and when the account queue goes from empty to non-empty, put the account queue into the global work queue

• 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.

I make it simple like this:

• 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.