A Hierarchical Time Wheel stacks multiple circular ring buffers at increasing time granularities (ms -> s -> m -> h) to achieve O(1) timer insertion and cancellation.
TL;DR30-second simplified summary▾
Traditional delay queues rely on a binary min-heap (PriorityQueue) or Redis ZSET, where every timer insert and cancel pays O(log N) pointer/rebalance overhead. At 10 million active network timeouts or retry timers, heap lock contention and O(log N) churn become a major CPU bottleneck.
A Hierarchical Time Wheel (popularized by George Varghese & Tony Lauck, and used inside Linux, Netty, and Kafka's TimingWheel) organizes timers like the hands of a mechanical clock. Level 0 holds 60 slots of 1 second each; Level 1 holds 60 slots of 1 minute each; Level 2 holds 24 slots of 1 hour each. Inserting a timer hashes its deadline into the matching wheel and doubly-linked bucket in O(1) time.
As the finest wheel's cursor ticks forward, expired buckets trigger immediately, while coarser wheels cascade: when a minute-wheel slot becomes current, its entire linked list of tasks is demoted into the seconds wheel for fine-grained dispatch. Pairing the wheel with an OS delay queue (DelayQueue of non-empty buckets) avoids busy-waiting on empty ticks.
From patterns to decisions.
Replace O(log N) min-heap timer bottlenecks with O(1) hierarchical circular arrays capable of tracking millions of concurrent timeouts and delayed jobs.
O(log N) Min-Heap Churn vs. O(1) Ring-Buffer Buckets.
In a 10M-timer min-heap, every insert() and cancel() touches ~24 tree levels under a global lock. Because network timeouts and RPC deadlines are cancelled > 95% of the time before firing, paying O(log N) on every RPC hurts tail latency.
A Time Wheel turns insert and cancel into O(1) doubly-linked list append/unlink operations.
Min-Heap vs. Time Wheel Cost
1.Stage Objective: Compare binary min-heap / Redis ZSET timer costs against circular time-wheel arrays.
2.Level (Foundation): In a 10M-timer min-heap, every `insert()` and `cancel()` touches ~24 tree levels under a global lock. Because network timeouts and RPC deadl
3.Operational Invariant: Time wheels eliminate O(log N) tree rebalancing, making insert and cancel O(1) doubly-linked operations.
Caption: Time wheels eliminate O(log N) tree rebalancing, making insert and cancel O(1) doubly-linked operations.
Circular Slots, Tick Resolution & Overflow Rounds.
A single wheel with M slots and tick duration dt covers a horizon M * dt. A task due in k ticks lands in slot (cursor + k) % M.
Tasks beyond M * dt either store a rounds = k // M counter (requiring linear bucket scanning on every revolution) or overflow into a coarser hierarchical wheel.
Single Wheel Slot Mapping
1.Stage Objective: Understand how a single-level wheel maps deadlines to `(slot_idx, remaining_rounds)`.
2.Level (Foundation): A single wheel with `M` slots and tick duration `dt` covers a horizon `M * dt`. A task due in `k` ticks lands in slot `(cursor + k) % M`.
3.Operational Invariant: Deadlines map modulo M into circular slots, with distant tasks needing either rounds or hierarchy.
Caption: Deadlines map modulo M into circular slots, with distant tasks needing either rounds or hierarchy.
Multi-Level Clock Wheels & Bucket Cascading.
Stack wheels with exponentially larger tick sizes: e.g. Wheel 0 (60 x 1s = 60s), Wheel 1 (60 x 60s = 1h), Wheel 2 (24 x 1h = 24h).
When Wheel 1's cursor advances to slot s, all tasks in Wheel 1[s] have < 60s remaining and are cascaded (re-inserted) into Wheel 0 in O(1) per task. No task is ever scanned before its coarse bucket arrives.
3-Level Hierarchical Time Wheel
1.Stage Objective: Cover arbitrary time horizons (milliseconds to months) using compact stacked wheels.
2.Level (Intermediate): Stack wheels with exponentially larger tick sizes: e.g. Wheel 0 (`60 x 1s = 60s`), Wheel 1 (`60 x 60s = 1h`), Wheel 2 (`24 x 1h = 24h`).
3.Operational Invariant: Tasks cascade from Hours -> Minutes -> Seconds wheels only when their coarse bucket becomes current.
Caption: Tasks cascade from Hours -> Minutes -> Seconds wheels only when their coarse bucket becomes current.
Building a Thread-Safe Hierarchical Time Wheel.
Store a doubly-linked node handle inside each TimerTask so cancellation unlinks the node in O(1) without searching the bucket.
import threading
from collections import deque
class TimeWheel:
def __init__(self, tick_ms: int = 1000, wheel_size: int = 60, start_ms: int = 0) -> None:
if tick_ms <= 0 or wheel_size <= 0:
raise ValueError('tick_ms and wheel_size must be positive')
self.tick_ms = tick_ms
self.wheel_size = wheel_size
self.interval_ms = tick_ms * wheel_size
self.current_ms = start_ms
self.buckets: list[deque] = [deque() for _ in range(wheel_size)]
self.overflow: TimeWheel | None = None
self._lock = threading.Lock()
def add_task(self, expire_ms: int, task_id: str) -> None:
with self._lock:
delay = expire_ms - self.current_ms
if delay < self.tick_ms:
self.buckets[0].append((expire_ms, task_id))
elif delay < self.interval_ms:
idx = (expire_ms // self.tick_ms) % self.wheel_size
self.buckets[idx].append((expire_ms, task_id))
else:
if self.overflow is None:
self.overflow = TimeWheel(self.interval_ms, self.wheel_size, self.current_ms)
self.overflow.add_task(expire_ms, task_id)Cascading Add & Overflow Creation
1.Stage Objective: Implement O(1) insert, O(1) cancel via node handle, and cascading tick advancement.
2.Level (Intermediate): Store a doubly-linked node handle inside each `TimerTask` so cancellation unlinks the node in O(1) without searching the bucket.
3.Operational Invariant: Tasks exceeding the local wheel interval delegate lazily to an overflow wheel with coarser ticks.
Caption: Tasks exceeding the local wheel interval delegate lazily to an overflow wheel with coarser ticks.
Eliminating Empty-Tick Polling with Kafka's DelayQueue Hybrid.
A naive 1 ms ticker wakes up 1,000 times/second even if 999 slots are empty. Kafka's SystemTimer pairs the Hierarchical Time Wheel with a single OS DelayQueue storing only non-empty buckets ordered by bucket expiration.
The ticker thread sleeps until the next non-empty bucket's exact deadline, eliminating 99% of idle wakeups.
Time Wheel + DelayQueue Hybrid
1.Stage Objective: Avoid wasting CPU on empty wheel ticks when tasks are sparse.
2.Level (Advanced): A naive 1 ms ticker wakes up 1,000 times/second even if 999 slots are empty. Kafka's `SystemTimer` pairs the Hierarchical Time Wheel with a
3.Operational Invariant: Tracking only non-empty buckets in a DelayQueue removes idle polling while keeping O(1) task inserts.
Caption: Tracking only non-empty buckets in a DelayQueue removes idle polling while keeping O(1) task inserts.
Persisting In-Memory Wheels via Partitioned WALs.
An in-memory time wheel loses state on crash. Pair it with a partitioned Write-Ahead Log or RocksDB time-bucketed store: only load near-term buckets (e.g., next 15 minutes) into the RAM Time Wheel, while distant jobs stay on disk and stream in via a background lookahead loader.
Disk-Backed Lookahead Window
1.Stage Objective: Ensure scheduled delayed jobs survive process restarts without loading years of tasks into RAM.
2.Level (Advanced): An in-memory time wheel loses state on crash. Pair it with a partitioned Write-Ahead Log or RocksDB time-bucketed store: only load near-term
3.Operational Invariant: Keep only the next 15 minutes in the RAM wheel while distant jobs rest in time-bucketed RocksDB.
Caption: Keep only the next 15 minutes in the RAM wheel while distant jobs rest in time-bucketed RocksDB.
Handling Monotonic Clocks, GC Pauses & Firing Bursts.
Always drive local timeouts from a monotonic clock (CLOCK_MONOTONIC) rather than wall-clock NTP time to avoid backward jumps. For persistent wall-clock schedules (deliver_at_utc), use max(now, deadline) and cap worker-pool dispatch concurrency with a token bucket so a 10-second GC pause does not fire 500K timers simultaneously.
Monotonic Clock & Burst Smoothing
1.Stage Objective: Prevent missed deadlines and thundering-herd dispatch bursts after pauses.
2.Level (Advanced): Always drive local timeouts from a **monotonic clock** (`CLOCK_MONOTONIC`) rather than wall-clock NTP time to avoid backward jumps. For pers
3.Operational Invariant: Monotonic ticks and dispatch token buckets prevent backward clock jumps and post-pause bursts.
Caption: Monotonic ticks and dispatch token buckets prevent backward clock jumps and post-pause bursts.
Practice: Make the trade-off yourself.
Why does Kafka's `SystemTimer` combine a Hierarchical Time Wheel with a `DelayQueue` of non-empty buckets?