I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple of 15 seconds, with the maximum allowed period being 1 day.

The system needs to support adding new jobs and removing / replacing existing jobs. However, these occur relatively infrequently (aside from when the system starts up and has to add the initial batch of jobs), so it is okay to make trade-offs with regards to insertion / deletion time.

Jobs scheduling times should be spread out so as to avoid "spikes" in number jobs dispatched. For example, if we had a million jobs that all had a period of 15 seconds, we wouldn't want to dispatch all of them at the exact same time every 15 seconds, and then wait another 15 seconds not doing anything before doing it again. It would be better to spread them out so around 60-70k jobs are dispatched every second, as long as each job is still scheduled to run 15 seconds apart.

Currently, around 10% (maybe less) of the jobs in the system have a period of 15 seconds (the minimum possible), while the remaining jobs have periods between 30 seconds and 1 day.

Our current implementation uses something like a hashed timer wheel, which has 15,000 buckets representing the number of milliseconds in every 15 second interval. Jobs are added to a random bucket in the wheel, and on every tick of the wheel, we iterate through every job in the bucket, dispatching the ones that are "expired" and incrementing a counter for the remaining jobs. For example, a job with a 60 second period would only be dispatched once every 4 turns of the wheel, even though it is iterated over on every turn of the wheel. The problem here is that on each tick of the wheel, the majority of the jobs in the next bucket are not actually ready to be dispatched, but we have to iterate over them anyways to increment their counter.

Is there a better algorithm / data structure I can use to make this more efficient? I am considering implementing hierarchical timing wheels, so that the only times we need to iterate over a job are when it is re-inserted into a lower wheel, or when it is ready to be dispatched. My concern with this approach though, is that unlike the current hashed timer wheel approach, we need to remove and re-insert the job every time its period expires.

  • $\begingroup$ I'm a bit confused about the problem statement. You talk about inserting and deleting jobs, but I don't know what the output of the algorithm should be. I presume the output is a schedule, but I don't see a clear statement of what requirements it must satisfy. How will you evaluate a proposed schedule to determine whether it meets your requirements? What are the requirements? Are there any constraints on when a job can be scheduled, or how many jobs can be running at once? Is this a batch algorithm, where all jobs are known in advance, or a streaming algorithm? $\endgroup$ – D.W. Jun 1 '20 at 4:42
  • $\begingroup$ @D.W. When I talk about inserting and deleting jobs, I'm actually just referring to adding new jobs to the set of periodic jobs that the system schedules. The requirements are quite simple in that every job just needs to be dispatched periodically depending on its period (For example, a job with 15 second period should be dispatched every 15 seconds). $\endgroup$ – shmth Jun 1 '20 at 20:42
  • $\begingroup$ @D.W. Also just to clarify, the question "how many jobs can be running at once" doesn't exactly apply here, because the system itself is not actually responsible for running the jobs. It is only responsible for scheduling and dispatching them. The majority of jobs are known in advance and can be loaded up when the system first starts up, but the system should still support adding / removing occasional jobs on the fly. The difference here is that since most jobs are known in advance, it is acceptable if adding / removing jobs is expensive. $\endgroup$ – shmth Jun 1 '20 at 20:45

A standard approach for scheduling is a priority queue of future jobs: each job has a time at which it should be dispatched, and that time is the key for the priority queue.

When a new job arrives, pick a random time within its period, and schedule it to occur at that period. For instance, if a job arrives with a period of 75 seconds, pick a random number $t$ in the range [0,75), then schedule it to be first dispatched $t$ seconds from now. To schedule it, add it to the priority queue with its dispatch time as the key.

Each second, retrieve all jobs scheduled to be dispatched in this second, delete them from the priority queue, and dispatch them. Also schedule each to occur at a time in the future based on its period (thus inserting it back into the priority queue with a later dispatch time).

The randomization should ensure a reasonable balance of jobs, especially when you have a large number of jobs to schedule, and the priority queue should make it efficient to insert, delete, and dispatch jobs. In particular, all of those operations can be done in $O(\log n)$ time, where $n$ is the number of jobs.

You could check whether that will meet your requirements. If not, that should help clarify your specific requirements.

  • $\begingroup$ Thanks, my one concern with this is reinsertion into the priority queue, since it seems like a somewhat costly operation. $O(\log n)$ for each reinsert, but at each second, we may need to perform $O(n)$ of these reinserts. It is fine for the addition of new jobs to the system to be expensive, but for jobs that have already been added, they should ideally not have to be reinserted every time. I think this was one of the considerations that lead to the initial implementation with a hashed timing wheel instead of a priority queue. $\endgroup$ – shmth Jun 1 '20 at 20:52
  • $\begingroup$ @shmth probabilistically it's unlikely that you'll have all n of the jobs falling on the time second. Instead it's likely that the load will be evenly spread out among each of the time periods. If a wheel works better, then cool! All good. $\endgroup$ – D.W. Jun 2 '20 at 1:05

Your current design is already very efficient in both CPU time and memory usage. One way to increase performance at the cost of memory is to create a few copy of the hash table, each one containing objects sorted by range of remaining time. For example, one hash table contains every objects with more than 1 hour remaining time. Once an hour, you scan the entire hash table and subtract one hour to each (240 units of 15 second). If the new count brings the remaining to one hour or less, move it to the original hash table. Using only two hash table would speed up your process by a factor of 240 in the worst case or about 120 if the distribution is random.

Since we are just performing integer operation in a compact array, the timing of updating the second hash once an hour very low. Moving the objects to the first hash at least one hour before they expire also warranty no sudden rush of large amount of.process to dispatch once per hour.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.