Understanding the Time Wheel Algorithm: From Simple Wheels to Hierarchical and Dynamic Wheels

The time wheel is a clever algorithm for implementing delayed tasks (timers) and is employed in frameworks such as Netty, Kafka, Zookeeper, and even the Linux kernel.

At its core, a time wheel consists of a circular array where each slot holds a doubly‑linked list of timer tasks; a pointer (currentTime) indicates the current slot and advances at a fixed tick interval.

When a task is added, its delay and expiration times are calculated, and the task is placed into the slot whose index corresponds to the expiration time modulo the wheel size. The article demonstrates this with a 20‑slot wheel where each slot represents 1 ms (or 1 s in the animation).

Because slots become expired as the pointer moves, expired slots can be reused for future tasks, enabling efficient memory usage.

When the first‑level wheel cannot accommodate a task whose expiration exceeds its range, the algorithm upgrades to a hierarchical time wheel: a second‑level wheel with larger slot spans (e.g., 20 s per slot) stores tasks that exceed the first level’s capacity. The second‑level pointer advances only when the first level completes a full rotation.

Tasks may be promoted or demoted between levels: if a task in the second level reaches its expiration window, it is moved back to the first level with the remaining delay.

The article also discusses the “dynamic” aspects of the wheel, such as how slots are continuously reused and how the system avoids wasted empty rotations by integrating a DelayQueue.

Overall, the time wheel provides a low‑overhead, scalable solution for managing large numbers of timers, supporting ranges from milliseconds up to several thousand seconds with only a few array elements.