Work load balance/Task distribution algorithm

Question

I'm looking for an algorithm to either use or as a jump point for load balancing.

Environment: We have ~7 job types that can be scheduled at any time by our users. Some jobs are fast, others are slow (lot of data processing). We have a single instance of a "job processor" that will discover jobs that have been scheduled and then execute them. The "job processor" will run up to 5 jobs at a time, "threads".

The problem is that one job could consume so many resources that the other 4 jobs don't get processed and even worse, the other scheduled jobs are delayed for long periods of time.

Some jobs can be scheduled as "run immediately" which makes them next in line.

Solution: Add more instances of the "job processor". We have a big VM server that IT is rolling out 3 VM's to each handle an instance of this "job processor".

By default, it's going to help but I believe that there should be more thought behind it.

My solution: In addition to making the "job processors" scale horizontally, I think there needs to be a way to determine which jobs an instance will grab based on current load of the instance and also allow for a bias.

I suggest we determine statistics for each job type (avg run time, etc) and give it a score of 1-5 (5 being long running). Each instance will determine what its current load is either based on the total score of the jobs its running currently and then factoring in it's bias. For example, I think we should be able to set an instance to be biased toward small jobs so it avoids larger jobs while another instance is biased toward medium jobs, etc.

I'm looking for advice on how to go about this. Jobs can consume large amounts of time, cpu and/or memory. My goal is to make sure each instance is only pulling down the work it's capable of doing while keeping the scheduled job queue moving along as quickly as possible.

One of the other devs suggested we leave the "job processors" alone to just pull whatever is in the queue next or "round robin". I say that this could lead to a potential issue where a single instance has pulled down too many large jobs and is struggling to get them done while the other instances are idle.

Answer 1

Part of what you are looking for is a "priority queue". At previous employers, we did a very primitive version of this, but my heuristic was to only allow some processors to handle short running jobs (short jobs could take minutes), while others were handling longer running jobs (the quarterly report could take almost 2 days to process). This guaranteed that short jobs always had processing time available. I also used a scoreboard that listed jobs ready to be run, and the first processor able to handle the task would pick it up and run it single threaded (they were cheap computers that hadn't been depreciated and so could not be discarded). Many folks use the opposite: a scheduler that tells processors which work unit to do next. My advice would be to have each instance running a single task - this drastically simplifies the scheduling.

Scheduling of arbitrary jobs of arbitrary lengths is a hard problem in distributed processing. Almost every decision is going to involve simulating lots of runs. Which is one of the quirks of queuing theory, which this stuff is going to be based on.

One of the other devs suggested we leave the "job processors" alone to just pull whatever is in the queue next or "round robin". I say that this could lead to a potential issue where a single instance has pulled down too many large jobs and is struggling to get them done while the other instances are idle.

This needs simulation to answer. My earlier scheme used something very similar. If you have stats on previous job runs, you can model it in Excel. I've picked up this book from another post recommending it and am looking to learn some techniques to better be able to answer problems like what you're describing. Actual numbers trump everything, so gather data and do simulations based on them.

Answer 2

I think your reasoning is sound and that your idea is good and friend's idea is good enough.

Perhaps you should also consider a "Pre-Process" process?

If your jobs are taking so much time that is causing unnecessary wait time in the queue, it may be possible to split a single large job into a series of smaller jobs that are preprocessing data into perhaps staging tables for the parent process.

Bringing the cost of an individual job down so that the disparity in average processing time is much lower would be a considerable alternative to a ranking system.

EDIT: I would also like to note that a ranking system derived from Time per Job can be heavily influenced by environment specific variables, (Eg. A job ranked low because of I/O access on a server with RAID configuration may not have a rank that makes sense on a server with a solid state HDD.)

This can be a pitfall in dermining rank based on the performance of a single environment.

Answer 3

Add more instances of the "job processor". We have a big VM server that IT is rolling out 3 VM's to each handle an instance of this "job processor".

Correct.

By default, it's going to help but I believe that there should be more thought behind it.

Incorrect.

Any more engineering is an absolute waste of time.

Consider the use cases in detail.

On a single processor Queue, the long-running job gets into the one-and-only processor first. Other jobs wait. You don't like this.

On a multiple processor Queues, the long-running job gets into one of the processors, leaving the others free. Problem solved.

Let's say that you have three long-running jobs that could get started concurrently. Then, you simply need 4 processors to handle the workload. Three will get long-running jobs, the fourth will handle the "instant" jobs.

Multiple processors working from a single queue of requests is the standard, widely-adopted, nearly universal solution. Nothing more is needed.

If you really, really think priorities are important, you use a priority queue instead of a FIFO queue and you manually assign simple priorities. Don't over-think it. More thinking is going to simply be a waste of time.