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.