Process many types of work in parallel, but sequential for each type of work

Question

Imagine there is a stream of requests for about 500 types of work. There can be say 5 workers in parallel. One type of work should be executed by at most one worker at the same time. The requests for a specific type of work should thus be done sequentially. So further requests for that active type of work should be enqueued till that current work is finished.

So, when the work of 1 type is being executed, only further requests for that type of work are enqueued. In the mean time all other types of work can continue.

In our Spring environment I tried a number of solutions for solving this situation like:

• 2- Each type of work is assigned a queue. So there will be many queues. Sometimes a type of work will disappear, so then the specific queue is deleted. So any type of work is out on the specific queue.
• 3- Have 1 message queue dispatching to a limited set of worker queues. That requires quite some logic for dispatching. There should be a standard solution for this problem.
• 4- Have 1 message queue in combination with database tables that contain the 'suspended' messages. The problem of this solution is that it is hard to process the messages of one type of work in the right, sequential order.
• 5- A bit awkward: just use a database table with workers reading the first (oldest) matching message. It works, but not ready with setting the right transaction boundaries. Is quite expensive in relation to database access

We started with experimenting with the dynamic creation of queues. This feels like very dynamically creating/suspending/resuming infrastructure. Is this right way to go?

The current solutions don't proof to be a good, solid solution.

How to model this in a good way? Is the option of dynamic creation, suspending and resuming of queues a good idea?

Answer 1

We started with experimenting with the dynamic creation of queues. This feels like very dynamically creating/suspending/resuming infrastructure. Is this right way to go?

How to model this in a good way? Is the option of dynamic creation, suspending and resuming of queues a good idea?

It seems Netflix just built something very similar to your use case/problem: https://netflixtechblog.com/timestone-netflixs-high-throughput-low-latency-priority-queueing-system-with-built-in-support-1abf249ba95f

As I understood, they've built what they call an "Exclusive Queue", on which a "message" can be stored with its metadata. Within this metadata there is a "exclusivity key", which causes the message to be non-dequeuable if there is already a consumer processing a previous message with this same key and value.

For this solution, among all components, it comprises a Redis cluster (they represent and persist queues as Sorted Sets; they persist message payloads & Queue metadata in Hashes), Apache Kafka for publishing internal events of this solution and Elasticsearch to store primary and secondary indexes of messages (which mean "current" and "historical" messages, respectively).

Not sure if this helps, you can just downvote if it's not related.

Answer 2

I'd tackle the problem from different angles.

Is the problem really well-understood?

You didn't explain what the reason for wanting to handle tasks of one kind sequentially. Are there resource contention reasons, possible data corruption, etc.? Your question starts with what you think is the solution to the underlying problem, but you don't say what this problem really is.

Design an algorithm

An algorithm can be designed and analysed for theoretical correctness without committing to a specific technology. You will need some kind of atomic operations to ensure that no two workers work on the same kind of task.

You should also check whether your algorithm handles peripheral issues such as resource (worker) starvation, cost of switching between item types, timeliness etc.

Choose an implementation technology

Pure message brokers such as ActiveMQ or RabbitMQ probably won't handle your one-worker-per-type requirement well. A database typically would have to be polled, unless you can offload part of the work into triggers and stored procedures. I'd look at Redis for a nice mix of data structures and flexibility.

Rough implementation idea

Work items are queued into one queue per item type. Queues (lists) are cheap. In addition, the item type indicator is pushed into an additional queue from which idle workers fetch item types to work on.

Idle workers check this queue and assign themselves to an item type if no other worker handles it already. That's where you need atomic primitives to ensure that only one worker handles an item type.

Workers assigned to an item type pick work items from the respective queue and execute them. Once their queue is empty, they return into the idle state. To avoid resource starvation and ensure fairness, workers may stop handling a queue after a set time or number of items.

There are a number of possible race conditions which need to be considered, of course.