Skip to main content
← CONCEPTS / DISTRIBUTED SYSTEMS
An end-to-end domain learning journey

Hierarchical Time-Wheel Scheduler
& Delay Queues.

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.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

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.

Full walkthrough · 7 stages
01
STAGE 01 · WHY HEAPS BOTTLENECKfoundation

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.

STAGE 01 · WHY HEAPS BOTTLENECK

Min-Heap vs. Time Wheel Cost

Min-Heap vs TimeWheel CIngress / BaselineCore EngineScale ConstraintGuard & VerifyBottleneck SignalProduction OutcomeTarget SLAexposes

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.

02
STAGE 02 · SINGLE WHEELfoundation

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.

STAGE 02 · SINGLE WHEEL

Single Wheel Slot Mapping

Single Wheel SlotMappinInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

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.

03
STAGE 03 · HIERARCHICAL WHEELSintermediate

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.

STAGE 03 · HIERARCHICAL WHEELS

3-Level Hierarchical Time Wheel

3-LevelHierarchical TimValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

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.

04
STAGE 04 · IMPLEMENTATIONintermediate

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)
STAGE 04 · IMPLEMENTATION

Cascading Add & Overflow Creation

Cascading AddHot PathOverflow CreationPartition / IndexValidation GateLatency / RAM BoundProduction OutcomeScaled Statebounds

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.

05
STAGE 05 · SPARSE TICK OPTIMIZATIONadvanced

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.

STAGE 05 · SPARSE TICK OPTIMIZATION

Time Wheel + DelayQueue Hybrid

Time Wheel +DelayQueueFault TriggerCore EngineIsolation BoundaryGuard & VerifyFallback / QuarantineProduction OutcomeProtected Pathisolates

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.

06
STAGE 06 · DURABILITYadvanced

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.

STAGE 06 · DURABILITY

Disk-Backed Lookahead Window

Disk-BackedLookahead WiCheckpoint / LogCore EngineReplay / SyncGuard & VerifyConsistency GateProduction OutcomeRecovered Stateverifies

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.

07
STAGE 07 · CLOCK SKEW & DRIFTadvanced

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.

STAGE 07 · CLOCK SKEW & DRIFT

Monotonic Clock & Burst Smoothing

Monotonic ClockTelemetry SignalBurst SmoothingSLO ThresholdValidation GateCircuit BreakerProduction OutcomeSafe Degradationtrips

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 · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does Kafka's `SystemTimer` combine a Hierarchical Time Wheel with a `DelayQueue` of non-empty buckets?

Recommended Learning Flow