Hierarchical Timing Wheels for Millions of Timeouts

Every network operation with a deadline needs a timer, and a runtime handling a million concurrent connections may have a million deadlines pending. A timeout that fires late is a correctness bug; a timeout facility that costs more than the operation it guards is a throughput bug. The data structure that holds the deadlines therefore has to be cheap on all three of insertion, cancellation, and expiry.

The obvious structure is a sorted list or a heap. In a heap, insertion is O(log n), cancellation is O(log n) once the entry’s position is known, and finding the next deadline is O(1). A sorted array is cheaper to read from the front, but inserting into the middle of it costs O(n) because the tail has to shift. At a million pending timers that is twenty comparisons per heap operation and, worse, the per-tick cost is paid even when nothing expires, because the runtime must compare the current time against the earliest deadline. The comparison itself is cheap; the problem is that a heap’s nodes are scattered in memory and each comparison is a likely cache miss.

A timing wheel trades the ordering for arithmetic. Deadlines are bucketed by their value modulo the wheel size, and the runtime advances a pointer once per tick. Insertion is a division and a list push; expiry is a walk of one bucket. The resolution is the tick, and the range is the wheel size times the tick. Both are acceptable for network timeouts, where the useful resolution is milliseconds and the useful range is seconds to minutes.

The single-level wheel and its range limit

A wheel with N buckets and a tick of T milliseconds covers deadlines up to N × T. With N equal to 512 and T equal to one millisecond, the range is about half a second. A timeout of ten seconds cannot be represented, because ten seconds modulo 512 milliseconds lands in a bucket that will be visited many times before the deadline arrives.

Increasing N fixes the range and costs memory proportional to N. Increasing T fixes the range and coarsens the resolution. Neither is free, and the product N × T is the range, so the design is a direct trade between memory, resolution, and horizon.

The second problem is that a deadline in the past must be distinguished from a deadline one full revolution ahead. A bucket visited at time t holds timers whose deadline is congruent to t modulo N × T; without extra information the runtime cannot tell whether a timer in the current bucket is due now or due N × T later. The standard fix is to store the full deadline in each timer and compare it when the bucket is processed, which makes the expiry walk slightly more expensive but keeps the structure correct.

Cascading levels

The hierarchical wheel resolves the range problem by adding levels. Level 0 has N buckets of tick T and covers N × T. Level 1 has N buckets of tick N × T and covers N² × T. Level 2 covers N³ × T, and so on. A timer is inserted at the level where its deadline fits, computed from the difference between the deadline and the current time.

When the pointer at level 0 completes a revolution, the bucket at level 1 that corresponds to the elapsed interval is drained, and each timer in it is reinserted at a lower level. This is the cascade. A timer that was placed at level 1 because it was several seconds out gets reinserted into level 0 when the remaining time is less than level 0’s range, and from then on it is handled by the fast path.

The cost analysis is the interesting part. Insertion is O(1): compute the level from the deadline’s distance, compute the bucket by division, push onto a list. Expiry of a level-0 bucket is O(k) for k timers in it. Cascading a level-1 bucket is O(k) for k timers, each of which is reinserted at level 0 in O(1). A timer is cascaded at most once per level, so over its lifetime it is touched O(L) times for L levels, a constant of typically three or four.

/* Insert: pick the level by how far out the deadline is. */
void insert(TimerWheel *w, Timer *t) {
    uint64_t delta = (t->deadline - w->now) / w->tick;  /* in base ticks */
    int lvl = 0;
    while (lvl + 1 < w->levels && delta >= w->slots) {
        delta /= w->slots;            /* one level coarser per division */
        lvl++;
    }
    size_t idx = (delta + w->hand[lvl]) % w->slots;
    list_push(&w->bucket[lvl][idx], t);   /* doubly linked: O(1) removal */
}

The doubly linked list is not incidental. Cancellation of a timer requires removing it from whatever bucket holds it, and a singly linked list would require a scan. With back-pointers, cancellation is O(1) regardless of bucket occupancy. Runtimes that create a timer per operation and cancel most of them on the normal path depend on this: if cancellation were O(k), a bucket holding a thousand timers would make each cancellation cost a thousand pointer chases, and the normal path would be slower than the timeout path.

The tick and the clock

A wheel needs to be advanced. Two mechanisms exist. The first is a periodic wakeup: the event loop’s wait call takes a timeout equal to the time until the next bucket boundary, and the loop advances the wheel when it returns. This is exact and costs nothing when the loop is busy, because the wait is already happening. It fails when the loop is idle and the next boundary is far away, because the wait’s timeout rounds up to the clock’s granularity and the timer fires late by up to that granularity.

The second is a kernel timer: a file descriptor from timerfd_create or an equivalent, registered with the event loop like any other descriptor, that becomes readable when the deadline passes. This gives the kernel’s clock resolution and lets the loop’s wait be indefinite otherwise. The cost is one more descriptor and one more registration, plus the syscall that arms the timer each time the earliest deadline changes.

Neither mechanism gives better resolution than the kernel’s clock. A periodic tick is bounded by the kernel’s timer frequency, and an hrtimer is bounded by the cost of arming a hardware timer and by the timer’s slack, so a runtime that promises microsecond timeouts on top of either is promising something the platform does not guarantee. The honest description is that timeouts are accurate to the timer resolution plus the loop’s dispatch latency, where the loop’s own wait timeout is the value described in readiness notification and the single-threaded event loop.

A third approach, used by kernels themselves, is to advance the wheel from a softirq or a timer interrupt rather than from a thread. The interrupt handler only notes that timer work is due and raises the softirq; the expiry and cascade work happens in the softirq, charged to whatever context was interrupted. This keeps the interrupt handler short, and it means the cost of a tick is paid in a place where it cannot be attributed to any one task. The userspace equivalent is to drain a bounded number of entries per tick and defer the rest, which bounds the latency contribution of any single tick.

Batching and the cost of a tick

The per-tick cost has two components: advancing the pointer, which is a few instructions, and processing expired entries, which is proportional to how many expired. If a runtime inserts a million timers with the same deadline, one tick processes a million entries, and that tick’s duration is the sum of a million list operations. The event loop is blocked for the duration, and every other timer and every I/O event is delayed.

The mitigation is to spread the work: process at most a fixed number of expired entries per iteration and leave the rest for the next iteration, or process a time-bounded slice. The first bounds the loop’s latency and makes the timers late by however many iterations the backlog takes; the second bounds latency and makes the timers late by a variable amount. Both are preferable to a stall, because a stall delays everything, including the timers that were already due.

The other side of the same coin is coalescing. Many timers with nearby deadlines do not need to fire at their exact times; firing them all at the next tick is indistinguishable to the caller and reduces the number of distinct buckets touched. Kernels coalesce aggressively for this reason, and runtimes that expose a coarse timer API can do the same. The trade is between precision and the cost of precision, and it is the same trade as the wheel’s resolution, applied at a different level.

Why not a heap

A binary heap is a perfectly reasonable timer structure for a few thousand deadlines. It is simpler than a wheel, has no resolution parameter, supports arbitrary intervals without a range limit, and gives exact ordering. The reasons wheels win at scale are memory locality and the constant factors, not the asymptotic complexity.

A heap’s per-insert cost includes a sift-up that touches O(log n) nodes, each a potential cache miss, and a cancellation requires finding the entry’s index, which needs an auxiliary map. A wheel’s insert touches one bucket and one list, both of which the runtime just computed the address of; the bucket array is contiguous and small enough to stay in cache at the levels that matter. The difference is a constant factor rather than an asymptotic one, and at a million timer operations per second the constant factor is what decides whether the timer facility fits on one core.

The heap also has a property that wheels lack: it can answer “what is the earliest deadline” in O(1) without advancing anything. A wheel must be advanced to discover that a bucket is empty, so an idle wheel with a distant earliest deadline costs one pointer advance per tick until the deadline arrives. Runtimes avoid that by tracking the earliest non-empty bucket or by arming the kernel timer to the exact earliest deadline, which is the usual hybrid: wheel for storage, kernel timer for wakeup.

Where the structure meets cancellation

Timeouts are set and cleared constantly, and the clearing path is the one that runs in the normal case. A request that completes before its deadline must cancel its timer, and the cancellation must not be more expensive than the timer was. That is why the wheel stores timers in doubly linked lists with back-pointers, and why a timer’s entry is embedded in the operation’s own state rather than allocated separately: the operation already exists, and adding a link to it costs two pointers.

The failure mode to guard against is a timer that fires for an operation that has already completed. The runtime must either remove the timer at completion, which requires the O(1) cancellation above, or mark the operation as complete and let the timer’s expiry find a tombstone. The first is the design that scales; the second accumulates garbage in the wheel proportional to the total number of operations rather than the pending ones, and the wheel’s memory becomes a record of history rather than a schedule. Runtimes that choose the first must ensure that every completion path cancels, including the cancellation path itself, the interaction described in cancellation and drop at suspension points.