Timing wheel vs heap for timers and delayed jobs: an interactive visualization

Servers juggle enormous numbers of timers: a timeout for every request in flight, a retry for every failed call, an expiry for every session and lock. Most are cancelled before they fire. A timing wheel stores timers in a circular array of buckets, one per tick, so scheduling and cancelling a timer is a constant-time list operation instead of a heap insert. Netty, Kafka and the Linux kernel all use one.

The playground has an eight-slot wheel ticking once a second. Add timers, tick the hand forward, and watch which bucket each timer waits in and when it fires.

How the wheel works

A timer due at tick t goes into bucket t mod 8, wherever the hand is. Each tick the hand moves to the next bucket and fires the timers in it that are due. Inserting costs one step whatever the number of timers, and cancelling is removing an entry from a short list, so a server can start and cancel millions of timeouts a second. A binary heap, the textbook alternative, pays about log2(n) comparisons per insert and per removal: about 20 each at a million timers.

The catch is delays longer than one lap. A 30-second timer on an 8-second wheel sits in its bucket for three passes of the hand before it is due, and is examined each time. With mostly short timeouts that cost is small; with a long tail of delays it grows. Two fixes:

• Rounds. Store how many laps remain with each entry and only decrement it, as Netty’s HashedWheelTimer does: cheap, but every long timer is still visited once per lap.
• Hierarchical wheels. Like the hands of a clock: a fine wheel for the next second, a coarser one for the next minute, another for the next hour. A long timer starts in a coarse wheel and moves down to a finer one as its time approaches. Kafka’s request purgatory and the Linux kernel’s timer wheel work this way.

Precision is the price: a timer fires on the first tick at or after its due time, so the tick size bounds the error. That suits timeouts and retries, where a few milliseconds do not matter, and is why heaps remain better for a small number of timers that must be exact.

A single-level timing wheel in code

class TimingWheel:
    def __init__(self, slots=512, tick_ms=10):
        self.slots = [[] for _ in range(slots)]
        self.tick_ms, self.now = tick_ms, 0          # now counts ticks

    def schedule(self, delay_ms, callback):
        due = self.now + max(1, delay_ms // self.tick_ms)
        self.slots[due % len(self.slots)].append((due, callback))   # O(1)
        return due

    def advance(self):                                 # called every tick_ms
        self.now += 1
        bucket = self.slots[self.now % len(self.slots)]
        ready = [t for t in bucket if t[0] <= self.now]
        bucket[:] = [t for t in bucket if t[0] > self.now]          # due on a later lap
        for _, callback in ready:
            callback()

In a system design interview

Timing wheels come up in delayed jobs and connection management: “Each gateway node holds a million open connections, each with an idle timeout that resets on every message. Resetting has to be cheap, so timeouts live in a hashed timing wheel with 1-second ticks; a reset moves the entry to a new bucket. For delayed jobs that must survive restarts, we keep them in a Redis sorted set by due time and a poller moves due jobs to the work queue.” Expect the follow-ups: durability of in-memory timers, and how delayed jobs are sharded so one poller is not a bottleneck.

Read the guide to delayed and scheduled jobs or background jobs, see deadline propagation for the timeouts these timers enforce, or watch a strong candidate design a job scheduler.

Questions people ask