Loading page…
Schedule delayed jobs on a wheel of tick-sized slots, overflow far deadlines into coarser wheels, cascade them down as time passes, fire in deadline order and cancel in O(1).
Delayed work is everywhere: retry this message in 10 s (Day 4, section 2.3), time this request out in 30 s, run the report at 9:00 (Week 2, Day 5's trigger generator). The naive scheduler keeps a list and scans every job on every tick: O(jobs) per tick. A timing wheel is a circular array of slots, one tick each, like a clock face: a job goes into the slot its deadline falls in, and each tick only looks at one slot. A hierarchical wheel handles far-away deadlines with coarser wheels (minutes, hours), and moves jobs down to finer wheels as their time approaches (Varghese and Lauck, "Hashed and Hierarchical Timing Wheels", SOSP 1987). Kafka keeps its delayed requests in hierarchical timing wheels, and Netty's HashedWheelTimer is a single-level hashed wheel.
Build TimingWheel(tick, wheel_size, start=0). Times are integers (milliseconds); start is a multiple of tick.
| Method | Does |
|---|---|
schedule(job_id, deadline) |
adds a job. Scheduling an id that is already pending replaces its deadline |
cancel(job_id) |
removes a pending job; True if there was one, False otherwise (unknown, cancelled or already fired). O(1) |
advance(now) |
moves the clock to now and returns the ids of every job that became due, ordered by deadline, ties by the order they were scheduled |
where(job_id) |
(wheel, slot) for a job waiting in a wheel, else None |
levels() |
how many wheels exist (wheel 0 plus the overflow wheels created so far) |
pending() |
how many jobs are scheduled and not yet returned by advance |
The rules (in ticks; tick t is time t × tick):
e = ceil(deadline / tick). The current tick is cur (start // tick at first); advance(now) steps cur one tick at a time up to now // tick. A job is due once cur >= e, so it never fires early and fires less than one tick late. Time never goes backwards: an advance to an earlier time moves nothing, but still returns jobs that were already due.k has wheel_size slots of wheel_size**k ticks each. Its window starts at cur - cur % wheel_size**k and covers wheel_size**(k+1) ticks. A job with e > cur goes into the lowest wheel whose window contains it (e < window_start + wheel_size**(k+1)), slot (e // wheel_size**k) % wheel_size; a job with e <= cur is due at once. Create overflow wheels only when a deadline needs one. (This is the placement rule of Kafka's timing wheel, applied to the rounded-up expiry tick.)cur += 1. Then, for every wheel k >= 1 from the top down, if cur is a multiple of wheel_size**k, empty its slot (cur // wheel_size**k) % wheel_size and place each job again with the rule above: that is the cascade into a finer wheel. Finally empty wheel 0's slot cur % wheel_size: its jobs are due.With tick=1, wheel_size=4 at tick 0: a job at tick 3 sits in wheel 0, slot 3; tick 4 doesn't fit wheel 0's window (0-3), so it goes to wheel 1 (4 ticks a slot, window 0-15), slot 1; tick 17 goes to wheel 2 (16 ticks a slot), slot 1. At tick 16, wheel 2's slot 1 cascades and the tick-17 job drops into wheel 0, slot 1.
In JavaScript and TypeScript the methods have the same names, where returns [wheel, slot] or null, and start defaults to 0.
Real timers run on a clock thread and fire callbacks. Here advance is called by hand and returns ids; it steps through empty ticks one by one (Kafka instead keeps a DelayQueue of non-empty slots so the clock can jump straight to the next one); there's one thread, no persistence, and a job that is due waits until the next advance returns it.
Write your code, then run 3 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and the runtime restarts, your code stays.