Producer-consumer pattern with consumer restrictions

Question

I have a processing problem that I am thinking is a classic producer-consumer problem with the two added wrinkles that there may be a variable number of producers and there is the restriction that no more than one item per producer may be consumed at any one time. I will generally have 50-100 producers and as many consumers as CPU cores on the server. I want to maximize the throughput of the consumers while ensuring that there are never more than one work item in process from any single producer.

This is more complicated than the classic producer-consumer problem which I think assumes a single producer and no restriction on which work items may be in progress at any one time. I think the problem of multiple producers is relatively easily solved by enqueuing all work items on a single work queue protected by a critical section.

I think the restriction on simultaneously processing work items from any single producer is harder because I cannot think of any solution that does not require each consumer to notify some kind of work dispatcher that a particular work item has been completed so as to lift the restriction on work items from that producer. In other words, if Consumer2 has just completed WorkItem42 from Producer53, there needs to be some kind of callback or notification from Consumer2 to a work dispatcher to allow the work dispatcher to release the next work item from Producer53 to the next available consumer (whether Consumer2 or otherwise).

Am I overlooking something simple here? Is there a known pattern for this problem? I would appreciate any pointers.

Answer 1

It sounds to me like your concurrency issue could be solved by using one queue per producer, where each producer queue refuses to dole out another work item until the previous one has completed. Then you just need each consumer to select fairly from amongst the non-empty producer queues. This should be pretty efficient if all producers generate work items at roughly the same rate and all work items require roughly the same amount of processing by the consumer.

If different producers generate work items at different rates or require different amounts of processing, you may need to change the priority to stop lower rate producers (or those producing higher complexity work units) effectively getting priority over higher rate (or low workload) producers.

One example would be for consumers to select the producer queue with the most items, not just those with no items, unfortunately this could produce other kinds of inefficiencies. How you balance your next work item priorities will thus require tweaking according to the dynamics of the system.