Load spread across multiple Queues that contains work items to be processed by worker threads accessing queues

user_13192885 0
Viewed 48

i have a design requirement where data from various sources need to be processed by multiple threads, but constraint being - the thread that processes the data from a given source should always continue to process the data from that source.

I used a SingleThreadExecutor that takes a Q and used a consistent hash type approach where the source's hash % 10 is mapped to a thread that processes the data.

Only concern here is hashing may not be uniform and some threads may be more loaded than others. Is there any better ways or achieving this? Has anyone tried a similar design problem? What are some of the suggestions that could be tried to get uniform spread of load of data across given set of Queues or threads?

Thanks in advance.

algorithm java
1 Answers

This is an online problem. Since you do not know in advance how much processing each source will require, you can't achieve perfect balancing.

I'm not 100% sure what exactly you're describing as your solution, so my next few lines might be a duplication of what you've already said:

I would hold in some data structure a mapping of source/process where I would also keep the number of current number of jobs waiting on that process (from all sources).

When a new source appears I'd assign it to the process which has the smallest load.

In severe cases (e.g., only three sources left active, and all three are on the same process), I would queue the incoming jobs (temporarily) and when the process has finished handling the jobs it already in its queue I would re-distribute the source/process mapping.

Hope this makes sense and is useful.

user_30451710
Related