In a timer service holding millions of pending timeouts, how does a hierarchical timing wheel insert and fire timers without sorting them?
answer
- clock face of slots
- slot from delay divided by tick
- cursor advances every tick
- upper tick equals lower span
- re-insert by remaining delay
basics
~20 sA wheel of slots, one per fixed tick, holds lists of timers; a pointer advances each tick and fires that slot. Timers beyond the wheel's span go into coarser upper wheels and cascade down as their time approaches. Insertion is constant time.
solid answer
~50 sA timing wheel is a circular array of `N` slots, each covering one tick of length `t`. To add a timer due after delay `d`, compute its slot as roughly `(current + d / t) mod N` and append it to that slot's list — constant time, no ordering. A pointer advances one slot per tick and fires everything in the slot it reaches. One wheel only spans `N × t`, so a hierarchical design stacks wheels: each level's tick equals the whole span of the level below. A far-off timer lands in an upper wheel; when that slot comes round, its timers are re-inserted into a finer wheel by their remaining delay (cascading), until they fire from the lowest one. Precision is one lowest-level tick, and because the wheels live in memory, a durable store must sit behind them.
go deeper
Recall the picture: a ring of slots, a cursor that moves one slot per tick, and timers dropped into the slot matching their delay.
Explain slot arithmetic, why insertion is constant time, how levels multiply the span, and what cascading does with remaining delay.
Discuss precision set by the base tick, bursts of work at rotation boundaries, memory-only state, and loading the wheel from a durable store.
Weigh a wheel against a heap or a durable index for a given workload: cancellation rate, horizon, precision needs, and recovery after restarts.
## Why not keep timers sorted A **timer service** holds pending **timeouts**: 'wake this job at time T', 'expire this session in 30 minutes', 'retry this call in 5 seconds'. The obvious structure is a **priority queue** (a binary heap) ordered by due time: the soonest timer is always on top. Insertion and removal cost `O(log n)`, which is fine for thousands of timers but adds up with millions of inserts per second, most of which are cancelled before they fire. A **timing wheel** trades exact ordering for arithmetic. It never compares timers with each other; it computes *where* a timer belongs from its delay. ## A single wheel Picture a clock face with `N` **slots**. Each slot represents one **tick** of fixed length `t` (say one second) and holds an unsorted list of timers. A **cursor** points at the current slot and advances by one on every tick. - **Insert:** a timer due after delay `d` (with `d` smaller than the wheel's span) goes into the slot about `d / t` positions ahead of the cursor, modulo `N`. That is one division and one list append: **constant time**. - **Fire:** when the cursor reaches a slot, every timer in it is due; the service runs or dispatches them all. - **Cancel:** if the caller keeps a handle to the list entry, removal is also constant time. The limit is the **span**, `N × t`. A wheel of 60 one-second slots covers only one minute. Covering a year with one-second slots in a single flat wheel would need about 31.5 million slots, almost all empty. ## Stacking wheels A **hierarchical timing wheel** stacks several wheels, like the second, minute and hour hands of a clock. Each level's tick equals the full span of the level below it. 1. On insert, pick the **lowest level whose span covers the delay** and place the timer in that level's slot. 2. Upper-level cursors advance only when the level below completes a full rotation. 3. When an upper cursor reaches a slot, its timers are not fired; they are **cascaded** — re-inserted by their *remaining* delay into a finer level. 4. A timer eventually reaches the lowest wheel and fires from there, within about one lowest tick of its due time. ## A worked example Assume four levels, each with 60 slots, and a one-second base tick: | Level | Tick | Span | |---|---|---| | 0 | 1 second | 60 seconds | | 1 | 60 seconds | 1 hour | | 2 | 1 hour | 60 hours | | 3 | 60 hours | 3,600 hours, about 150 days | Four arrays of 60 slots — 240 slots in total — cover about 150 days at one-second precision. A timer due in roughly 2 hours 5 minutes is too long for level 1 but fits level 2, so it goes there. When level 2 reaches its slot, about 5 minutes remain, so it cascades into level 1; when that slot comes round, a few seconds remain and it cascades into level 0, then fires. Each timer is moved at most once per level it passes through. ## Costs compared | Structure | Insert | Per-tick work | Horizon | |---|---|---|---| | Binary heap | `O(log n)` | pop due timers, `O(log n)` each | unlimited | | Single wheel | `O(1)` | fire one slot | `N × t` only | | Hierarchical wheel | `O(1)` | fire one slot, plus occasional cascades | grows by a factor of `N` per level | A **hashed** variant keeps one wheel and stores a 'rounds remaining' count on each timer, so a slot visit must skip timers that are not yet due; the hierarchical form avoids that scanning by cascading instead. ## Practical caveats - **Precision is one base tick.** Timers do not fire at sub-tick precision; a one-second tick means firing within about a second. - **Empty ticks still cost something.** A cursor that advances every tick does work even when the wheel is empty; some designs track only non-empty slots so they can jump ahead. - **Memory only.** A wheel is an in-memory structure. It is lost on restart, so for durable jobs it acts as a near-term firing layer loaded from a durable due-time store, not as the store itself. - **Cancellation-heavy workloads suit it well.** Timeouts that are usually cancelled before firing cost only an append and a removal. - **Bounded horizon.** Timers beyond the top level's span need an overflow list or a durable store that feeds them in later.
- Why does a timing wheel not replace a durable job store in a reminder service?The wheel lives in one process's memory, so a restart loses every pending timer, and its horizon is bounded by the top level's span. Reminder services therefore keep the durable due-time store as the source of truth and load only jobs due soon into the wheel, which then fires them precisely and cheaply.
- What is the cost of cascading, and when does it happen?Cascading happens when an upper-level cursor reaches a slot: each timer in that slot is re-inserted into a finer level by its remaining delay. Each timer is moved at most once per level it passes through, so a timer placed in level 2 is moved at most twice before it fires. The work is constant per timer, but it arrives in bursts at rotation boundaries.
A hierarchical timing wheel works like a clock's hour, minute and second hands: you only need to watch the seconds closely once the hour and minute are right.
saying these in an interview costs you the question
- A timing wheel keeps the timers inside each slot sorted by due time.
- A timing wheel fires timers with precision finer than one tick.
- One flat wheel of one-second slots is a sensible way to cover a year.
- An in-memory timing wheel can serve as the durable job store.
- Timers in an upper wheel fire directly when their slot is reached.