Producer and multiple consumers with limited types item

Question

I am implementing producer-consumer where items to be consumed are of 1000 types type-0, type-1, ..., type-999.

Producer inserts item of type-i in queue. Consumer uses that to update state machine for type-i(one state machine per type-i) based on item(type-i)removed from queue.There are multiple consumers that are reading from same queue (and one producer)

Condition is if some consumer is processing item of type-i then other consumers cannot process item of same type so if other consumers pick up next items of same type type-i, all consumers get blocked which is not good solution.

Another solution is to have 1000 queues and 1000 consumers for each type-i which is not feasible

Another solution is to have 10 queues and 10 consumers(one for each queue) and assign 100 types to Q-1, 100 types to Q2 etc. But problem is if consumer-j takes lots of time to process item-i all other items in queue will face delay though other consumer-k might be idle.

Whats good design pattern we can use here ?

UPDATE:

Solution-1 : (1 Queue - 1 Consumer) per type : Best solution but lot of threads

Solution-2: (1 Queue - m Consumers) per n Types : Problem is we might reach state where all consumers are waiting on processing type-i as first consumer still working on type-i item holding lock(type-i)

UPDATE 2:

Here ordering of items is IMP and cannot be altered. You can assume one state machine per type-i and consumer modifies state as per new item(of type-i) received. Now u can see why item ordering is important

Answer 1

First, I want to confirm that I understood the problem well. You have N different types of items in one main queue, and N consumers, each of which is responsible for exactly one type of items. A consumer responsible for processing items of type X cannot process items of type Y. Everything hereafter is based on this assumption.

Maybe you can arrange your consumers in a collection, and do a round robin peeking on the queue. Each consumer would just peek at the next item in queue to check if it is the item to process. If it is, the consumer would take the item from the queue and start processing, thus releasing the queue for other processors.

This approach would reduce mutual blocking of the consumers unless there are many items of the same type in a sequence in the main queue. In that case, other consumers would have to wait until the consumer in question processes all items. To avoid this problem, you can put a queue in each consumer, so that the consumer that finds the appropriate type on the main queue just puts it in its own queue, and processes it in a separate thread. This solution would result in as many threads as there are consumers, but if you use semaphore mechanism in each consumer, it might reduce that negative effect, since not all threads would be active at the same time.

If the number of threads is too large, you can always resort to the grouping of types, as you suggested. In that case, you could do some tweaking by assigning the types that appear most often in the main queue to different consumers, so that you make the most of parallelizing the work. Of course, if the types are uniformly distributed, then this approach cannot be used.