Scheduler 03: Heap and Timing Wheel

Follows Scheduler 02: Durable Job Store, and hands off to Scheduler 04: Leader Election.

Before you start. This series builds a small job scheduler: a program you hand a piece of work and a time, and it runs that work when the time comes, again and again if you ask it to. Our scheduler already survives a restart: every job’s next run time lives in a table on disk, not only in memory. Right now, finding out which jobs are due means walking that whole table, one job at a time, every single second. This lesson replaces that walk.

The idea in 30 seconds

Checking every job on every tick wastes almost all of that work, and it ties how precise the scheduler can be to how much it costs to run.
A heap keeps the soonest-due job on top for free, and only pays a little more to file a new one in.
A timing wheel is a wall of pigeonholes, one per tick: filing and firing are both one piece of arithmetic, and neither one cares how many cards are waiting.
The wheel’s speed costs precision - every job can fire up to one tick late - and rounding must always go up, never down.
The heap is almost always the right desk for a scheduler, because its jobs are meant to fire, not to be cancelled.
The wheel earns its place when almost every timer gets cancelled before it fires, which is why network software reaches for it instead.

Read the story · Skip to the numbers