Hierarchical timing wheel

Deep dive

How it works

In: a timer deadline (tick); "advance to tick t" · Out: the timers whose deadline has passed · State: LEVELS × 64 slot lists, a 64-bit occupancy bitmap per level, the current tick · Cost: insert and cancel O(1); a timer cascades at most levels − 1 times.

1. Time is an integer tick count. Level L has 64 slots, each spanning 64^L ticks.
2. Insert deadline d at current time now: the level is given by the highest 6-bit digit in which d and now differ: level = (63 − lzcnt((now ^ d) | 63)) / 6. Slot = digit L of d.
3. Advance to tick t: for each level L ≥ 1 whose lower 6·L bits of t are all zero, take slot digit_L(t) and re-insert its timers relative to t (they land in lower levels or fire). Then fire level 0's slot t & 63.
4. Cancel: unlink the timer from its slot list (O(1) with an intrusive doubly linked list or slab index).
5. Next expiry (for epoll_wait timeout): lowest occupied slot via bitmaps, without walking empty ticks.

level 2 (4096-tick slots) [ ][ ][x][ ] ...  cascades when t crosses a 4096 boundary
level 1 (64-tick slots)   [ ][y][ ][ ] ...  cascades when t crosses a 64 boundary
level 0 (1-tick slots)    [a][ ][b][c] ...  fires slot (t & 63) every tick

Code

const LEVELS: usize = 6;
const BITS: u32 = 6;
const SLOTS: usize = 1 << BITS; // 64

pub struct Timer<T> { pub deadline: u64, pub data: T }

pub struct Wheel<T> {
    now: u64,
    slots: Vec<Vec<Vec<Timer<T>>>>, // [level][slot] -> timers
    occupied: [u64; LEVELS],        // bit s set <=> slot s non-empty
    len: usize,
    ready: Vec<Timer<T>>,           // inserted already expired
}

fn level_for(now: u64, deadline: u64) -> usize {
    let masked = (now ^ deadline) | (SLOTS as u64 - 1); // at least level 0
    ((63 - masked.leading_zeros()) / BITS) as usize
}

impl<T> Wheel<T> {
    pub fn new(start: u64) -> Self {
        let slots = (0..LEVELS).map(|_| (0..SLOTS).map(|_| Vec::new()).collect()).collect();
        Wheel { now: start, slots, occupied: [0; LEVELS], len: 0, ready: Vec::new() }
    }

    pub fn insert(&mut self, deadline: u64, data: T) -> Result<(), T> {
        if deadline <= self.now { self.ready.push(Timer { deadline, data }); return Ok(()); }
        let level = level_for(self.now, deadline);
        if level >= LEVELS { return Err(data); } // beyond the horizon (~2^36 ticks)
        self.put(level, Timer { deadline, data });
        Ok(())
    }

    fn put(&mut self, level: usize, t: Timer<T>) {
        let slot = ((t.deadline >> (level as u32 * BITS)) & (SLOTS as u64 - 1)) as usize;
        self.slots[level][slot].push(t);
        self.occupied[level] |= 1 << slot;
        self.len += 1;
    }

    fn take(&mut self, level: usize, slot: usize) -> Vec<Timer<T>> {
        if self.occupied[level] & (1 << slot) == 0 { return Vec::new(); }
        self.occupied[level] &= !(1 << slot);
        let v = std::mem::take(&mut self.slots[level][slot]);
        self.len -= v.len();
        v
    }

    /// Advance the clock to `to` and return expired timers in deadline order per tick.
    pub fn advance(&mut self, to: u64) -> Vec<Timer<T>> {
        let mut fired = std::mem::take(&mut self.ready);
        while self.now < to {
            if self.len == 0 { self.now = to; break; } // nothing pending: jump
            self.now += 1;
            let t = self.now;
            for level in (1..LEVELS).rev() {           // cascade coarse -> fine
                let shift = level as u32 * BITS;
                if t & ((1u64 << shift) - 1) != 0 { continue; }
                let slot = ((t >> shift) & (SLOTS as u64 - 1)) as usize;
                for tm in self.take(level, slot) {
                    if tm.deadline <= t { fired.push(tm); }
                    else { let l = level_for(t, tm.deadline); self.put(l, tm); }
                }
            }
            fired.extend(self.take(0, (t & (SLOTS as u64 - 1)) as usize));
        }
        fired
    }

    pub fn len(&self) -> usize { self.len }
}

fn main() {
    let mut w = Wheel::new(0);
    for d in [5u64, 64, 65, 4_100, 300_000] { w.insert(d, d).ok(); }
    let mut got = Vec::new();
    for step in [10u64, 100, 5_000, 400_000] {
        got.extend(w.advance(step).into_iter().map(|t| (t.deadline, t.data)));
    }
    assert!(got.iter().all(|(d, x)| d == x));
    println!("{:?}", got.iter().map(|g| g.0).collect::<Vec<_>>()); // [5, 64, 65, 4100, 300000]
}

This reference advances tick by tick while timers are pending; production wheels jump straight to the next occupied slot using the bitmaps.

Complexity and constants

• Insert: a lzcnt, a shift and a push: order of 10-20 ns. Cancel: O(1) unlink (with intrusive lists).
• Cascading: a timer moves at most LEVELS − 1 times; most are cancelled before their first cascade.
• Memory: LEVELS × 64 list heads + per-timer node (~32-64 B with links and payload pointer); 1M timers ≈ order of 50 MB.
• Heap comparison: a binary heap at 1M timers costs ~20 levels of sift with cache misses per insert/cancel (order of 100s of ns); the wheel stays O(1).
• Precision: timers fire within one tick of their deadline (or, in the non-cascading Linux design, up to the level's granularity late).

Efficiency

• Cost: Insert is a lzcnt, a shift and a push: order of 10-20 ns; cancel is an O(1) unlink. A timer takes about 32-64 B, so 1M timers are order of 50 MB. A binary heap at 1M timers pays about 20 sift levels with cache misses per insert and cancel (order of 100s of ns). The bound is memory latency on slot lists.
• Levers:
  • Intrusive lists in a slab — O(1) cancel, no allocation per timer — mostly cancelled timeouts.
  • A bitmap per level — next expiry in one trailing_zeros, no walk over empty ticks — sparse or idle wheels.
  • No cascading (Linux timer_list) — zero cascade work, timers fire up to a level's granularity late — coarse timeouts such as keepalives.
  • One wheel per thread — no locks — thread-per-core servers.
  • Coarser tick — fewer wakeups — when precision beyond one tick is not needed.
• Naive → standard → state of the art:
  • Sorted list of timers · O(n) insert.
  • Binary heap · O(log n) insert and cancel, about 20 sift levels at 1M timers.
  • Hierarchical wheel with bitmaps and intrusive slab lists (Varghese and Lauck, Tokio) · O(1) insert and cancel, at most levels − 1 cascades per timer.

Implementation notes

• Store timers in a slab and link them intrusively; the handle returned to the user is the slab key, so cancel is O(1) without searching.
• Lazy cancellation (mark dead, skip when fired) is simpler but keeps memory until the slot is reached; fine for short timeouts.
• Compute next_expiration() from bitmaps: for level 0, rotate the bitmap by now & 63 and use trailing_zeros; for higher levels the earliest possible fire time is the slot start. Pass it as the epoll_wait/io_uring timeout.
• One wheel per thread/core: no locks, timers fire on the thread that owns the connection.
• Linux: timer_list uses 64 buckets per level with each level 8× coarser and no cascading: timeouts like TCP keepalive tolerate being late, and nearly all are cancelled before expiry.

Pitfalls

• Tick too coarse for the use (100 ms ticks for 50 ms deadlines) or too fine (1 µs ticks waste CPU when idle).
• Walking every empty tick after a long sleep: use bitmaps or jump when the wheel is empty.
• Firing callbacks while iterating a slot that callbacks insert into: take the slot out first (as above).
• Wall-clock ticks: use a monotonic clock, or a clock step fires or delays everything at once.

Variants and alternatives

In production

Linux kernel timer_list wheel, Tokio (tokio::time, 6 × 64 slots at 1 ms), Netty HashedWheelTimer, Kafka request purgatory. (nginx and HAProxy keep timers in trees instead: exact order at O(log n).)

Implementations

Sources

• George Varghese, Tony Lauck, Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility, SOSP 1987. paper
• Randy Brown, Calendar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem, CACM 1988. paper
• Tokio, time driver (hierarchical wheel). code