Hierarchical Timing Wheel

A timing wheel represents time as a circular array of buckets, where each bucket holds a linked list (or similar collection) of timer tasks scheduled to fire within that bucket’s time slot. A single-level wheel is cheap to build but forces a tradeoff: fine granularity requires an enormous number of buckets to cover long durations, wasting memory, while coarse granularity loses precision for near-term events. The hierarchical variant solves this by cascading multiple wheels of increasing granularity — for example, a millisecond wheel, a 100ms wheel, a second wheel, and a minute wheel — where a timer landing outside the range of the finest wheel is placed into a coarser overflow wheel and re-bucketed into a finer wheel only as its deadline approaches.

Under the hood, advancing the wheel is driven by a single ticking thread (or a monotonic clock check on each poll loop iteration) that advances a cursor pointer, executes every task in the bucket the cursor lands on, and cascades expired-but-not-yet-fine-grained tasks down a level. This is fundamentally the same design used by the Linux kernel’s legacy timer wheel, and it is the mechanism behind Kafka’s SystemTimer / purgatory (used for tracking delayed produce/fetch requests and request timeouts at broker scale), Netty’s HashedWheelTimer, and various QUIC/RPC stacks that need to arm and disarm deadline timers per-connection or per-request without heap contention.

• Insertion/removal cost: O(1) versus O(log n) for a binary heap or skip-list-based priority queue, because placement is a hash-like modulo operation on the deadline rather than a comparison-based tree rebalance.
• Cancellation: Cheap in principle (unlink from bucket), but many implementations use lazy deletion — marking a task cancelled and skipping it on expiration — to avoid pointer-chasing overhead under high churn, which means cancelled-but-unswept tasks still consume memory until their bucket rotates.
• Tick granularity tradeoff: Coarser tick intervals reduce CPU wakeups but introduce coalescing error — a timer set for 105ms in a 100ms-granularity wheel may fire anywhere in the 100–199ms window, which is unacceptable for tight SLA enforcement (e.g., p99 request-timeout accuracy).
• Long-duration timers: Require cascading through every intermediate wheel level as the deadline approaches, adding bookkeeping complexity and a class of bugs where a task appears “stuck” if a cascade step is missed after a clock skew or a paused ticking thread (e.g., GC pause on the ticking thread stalls every timer behind it).

The architectural implication is that timing wheels trade timer precision and per-timer overhead against system-wide scalability: they are the correct choice whenever the timer population is large and mostly short-lived (connection idle timeouts, request deadlines, rate-limiter token refills), and a poor choice when a small number of timers need microsecond-accurate firing, since a single ticking thread’s scheduling jitter and the wheel’s bucket granularity both dominate error at that scale. A related and easily confused failure mode is timer storms: if a large population of timers is armed with the same relative offset (a common anti-pattern when every connection in a fleet is given an identical keepalive interval), they all cascade into the same bucket and fire in the same tick, producing a CPU spike indistinguishable from a thundering herd — mitigated in practice by jittering deadlines before insertion. Understanding the wheel’s tick-to-bucket mapping is therefore essential not just for implementers of timer subsystems, but for anyone diagnosing why a broker’s request-timeout enforcement lags under load or why cancelled tasks are still visible in heap dumps long after their logical cancellation.