Scheduling Thousands of *Recurring* Jobs

Question

I'm looking for general approaches and ideally libraries/tools for scheduling many thousands of recurring jobs.

A simple example is a feed aggregator, where I'd want to repeatedly poll thousands of feeds. I would never want to poll a website more than once an hour (overuses everyone's resources), but I could deal with polling websites less than once an hour if there isn't time to finish everything in an hour (and worry later about sharding the process or whatever to make it faster, if this keeps happening). So I'd basically want a framework where I can say "run this task as often as possible, but no more than once an hour".

An additionally nice feature would be for such a framework to exponentially decay unsuccessful tasks, i.e. if a feed URL was broken, it would be scheduled for 2 hours, then 4 hours, etc.

I've heard of an approach involving a binary tree which acts as a kind of giant cronjob-like data structure. The system would constantly trawl through this tree to see if any tasks are overdue. I don't have much more information than this. I've looked at tools like Resque, but they don't really seem to cover this use case.

Answer 1

You can use a list of triggerables, sorted ascending by the time of the next trigger. When you need to trigger something, you can always pick off the front of the list, O(1). When you need to (re)schedule something, you can fit it in the list in O(log N) time.

It would be fairly simple & straightforward, and you can leverage any form of timer API (your scheduler needs to wake up only when the front of the list needs to be triggered).